K—means聚類算法的實例教學研究

王麗娟　郝志峰　蔡瑞初　溫雯　劉添添

摘要：針對數(shù)據(jù)挖掘課程理論知識多、講解抽象難懂的教學實際，重點研究數(shù)據(jù)挖掘課程的經(jīng)典算法K-means聚類算法的實例教學策略，以提高學生對數(shù)據(jù)挖掘算法的學習興趣，加強實際應用能力。研究內(nèi)容包括選擇實例、講解實例、擴展實例和教學評價4部分。選擇合適的實例提升學生學習興趣；講解實例使得學生掌握基本的K-means算法；擴展實例增強學生實際應用K-means算法的能力；最后教學評價進一步完善教學質(zhì)量和效果。

關(guān)鍵詞：數(shù)據(jù)挖掘；實例教學；K-means

0 引言

隨著沃爾瑪超市發(fā)布的啤酒和尿布營銷規(guī)則，數(shù)據(jù)挖掘（Data mining）逐步進入人們的日常生活，并且在生產(chǎn)和消費等各個領域都發(fā)揮著重要的指導作用。由于數(shù)據(jù)挖掘的重要作用，各個高校紛紛開設本科生以及研究生的數(shù)據(jù)挖掘課程。

數(shù)據(jù)挖掘是研究如何從大量數(shù)據(jù)中挖掘隱藏于其中的知識或者信息的科學。數(shù)據(jù)挖掘通常借助計算機科學、統(tǒng)計、在線分析處理、情報檢索、機器學習、專家系統(tǒng)和模式識別等諸多技術(shù)來實現(xiàn)上述目標。該課程涉及大量數(shù)學和統(tǒng)計模型，較為抽象，而且具有很強的時效性，知識更新?lián)Q代快。本科生或者研究生在學習這門課程的時候，概念較多，算法抽象，難以入門，更難于應用算法求解實際問題。為了獲取較好的課堂教學效果，數(shù)據(jù)挖掘課程采用實例教學策略教學。

實例教學策略通過工具軟件仿真建模，演示數(shù)據(jù)挖掘算法的具體運行過程，使得學生自己納入數(shù)據(jù)挖掘算法學習、開發(fā)和研究過程。數(shù)據(jù)挖掘課程的實例教學策略包括選擇實例、講解實例、擴展實例和教學評價4個部分，如圖1所示。

以K-means聚類算法實例作為數(shù)據(jù)挖掘?qū)嵗虒W的研究對象。具體講解7個仿真數(shù)據(jù)的聚類問題；通過Matlab軟件仿真K-means算法執(zhí)行過程，使得學生了解K-means算法及其設計策略；擴展實例重點分析K-means算法中參數(shù)設置，使得學生真正掌握該算法，求解實際的聚類問題；教學評價進一步促進教師改進教學的不足，提升教學質(zhì)量。

1 K-means聚類算法理論基礎

聚類的思想在日常生活中廣泛應用，如：物以類聚，人以群分。聚類是根據(jù)相似度形成數(shù)據(jù)的劃分，使得同一類對象屬于相同的類，而不同的對象位于不同的類。相似性度量是聚類算法的核心問題。常用的相似性度量如歐氏距離和夾角余弦等。K-means算法是一種基于歐氏距離的分割聚類算法。

K-means算法的基本思想：依據(jù)聚類個數(shù)C形成數(shù)據(jù)的C個劃分，計算每個劃分的類心，更新數(shù)據(jù)的類別為當前所屬劃分，不斷迭代調(diào)整聚類及其類心，直至所有數(shù)據(jù)的類屬不再改變?yōu)橹埂＞垲悅€數(shù)c與K-means中的K對應表示聚類個數(shù)。

設數(shù)據(jù)集X={X₁，X₂，…，X_n}為待聚類的對象集，每個對象Ⅸ（1≤j≤n）由s個屬性組成，記作X_j={X_j，…，X_js），其中x_jk是對象X_j的第k維屬性值。第i類數(shù)據(jù)的中心定義為v_i，其中vi的任一屬性值通過該類數(shù)據(jù)相應特征的平均值計算得到，即（1）式中：|v_i|為第i個聚類v_i所包含的數(shù)據(jù)個數(shù)。第i個聚類中心v_i與第j個數(shù)據(jù)點X_j的歐氏距離定義為（2）

根據(jù)式（2），將數(shù)據(jù)點劃分到距離最近的數(shù)據(jù)類。重復計算類心v_i和數(shù)據(jù)類屬，不斷地迭代，調(diào)整聚類。當聚類目標函數(shù)的變化值達到指定的閾值，即聚類不再改變或者發(fā)生較小的改變，算法可以停止，獲得聚類結(jié)果。聚類目標函數(shù)定義為（3）式中：d_ij為第i個聚類中心v_i與第h個數(shù)據(jù)點X_j的歐氏距離。目標函數(shù)J反映所有數(shù)據(jù)到其所屬類心的距離之和。如果和較小，則表示數(shù)據(jù)靠近其所屬類心，聚類內(nèi)聚性好，聚類效果好；否則，表示每類數(shù)據(jù)比較分散，內(nèi)聚性差，聚類效果差。

K-means算法描述如下：

（1）初始化：確定聚類個數(shù)C，隨機選取C個數(shù)據(jù)作為聚類中心v_i。

（2）更新聚類：計算所有數(shù)據(jù)到C個中心v_i的距離，對每個數(shù)據(jù)選取與其最近的類心，將該數(shù)據(jù)歸人該類。

（3）更新聚類中心：根據(jù)每個數(shù)據(jù)的類屬，將同一類數(shù)據(jù)的特征值平均得到更新的聚類中心。

（4）迭代：計算該劃分的對應的目標函數(shù)，的值，重復（2）～（4），直至J的值不變化或者J變化值達到指定的較小的閾值。

2 K-means聚類算法的實例教學

K-means算法采用了梯度下降和期望最大化等數(shù)學模型，算法較為復雜抽象。單純根據(jù)上面的分析，學生無法形成直觀的印象，因此，K-means算法需用實例教學策略。實例教學策略能夠通過Matlab軟件直觀呈現(xiàn)7個仿真數(shù)據(jù)的K-means算法聚類過程，將抽象的算法具象呈現(xiàn)，從而降低算法的難度，提升學生學習興趣。例1介紹了基本的K-means算法，屬于實例講解。但是在實際應用中，數(shù)據(jù)存在噪聲、異常和缺失等情況，數(shù)據(jù)聚類結(jié)果較為復雜，因此，需要具體研究算法的參數(shù)，增強算法的健壯性。例2和例3分別討論了聚類類數(shù)變化和類心變化的實例拓展過程。

2.1 實例選擇

實際的聚類問題如文本聚類和圖像聚類問題。文本聚類指計算機自動根據(jù)文本的語義，將文本分為政治、經(jīng)濟、軍事、體育等類別。圖像聚類是指計算機根據(jù)圖片的顏色、紋理或輪廓自動識別圖片的類型，分成海灘圖片、森林圖片、街道圖片、日出日落照片等類型。無論文本信息還是圖片信息均需要轉(zhuǎn)換成每個實例的若干特征描述，即每個實例形成一個空間坐標點。聚類的過程就是根據(jù)空間點距離的遠近，形成數(shù)據(jù)的劃分，使得相似的數(shù)據(jù)（彼此靠近的數(shù)據(jù)）分成一類，不相似的數(shù)據(jù)（距離較遠的數(shù)據(jù)）位于不同類。

由于課堂講述的時間有限，因此將實例規(guī)模限定為7個2維仿真數(shù)據(jù)，如表1所示，數(shù)據(jù)初始分布如圖2（a）所示。7個仿真數(shù)據(jù)的聚類過程如下所示。

2.2 實例講解

本節(jié)重點介紹如何通過K-means算法聚類表1所示的7個仿真數(shù)據(jù)的聚類過程。

例1：初始化：設7個數(shù)據(jù)分成C=2類，隨機選?。╔₃，X₂）作為2個類心，用紅色+號標記。

第1次聚類：根據(jù)圖2（a）中的類心，計算每個數(shù)據(jù)到類心的距離如表2所示，從中選取距離較近的類心作為當前該數(shù)據(jù)的類屬。第1次迭代后得到聚類為{X₁X₃X₆}{X₂X₄X₅X₇}，如圖2（b）中2個圓圈所示，目標函數(shù)J=17.9。

更新第1次聚類的類心：根據(jù)圖2（b）中數(shù)據(jù)分布重新計算2類的類心得到圖2（b）中2個新的紅色加號。

第2次聚類：根據(jù)圖2（b）中的新類心，第2次迭代計算每個數(shù)據(jù)到類心的距離，如表3所示，選擇最近的類心作為當前類屬，得到聚類為{X₁X₃}{X₂X₄X₆X₇}，如圖2（c）中2個圓圈所示，目標函數(shù)J=16.60降低。

更新第2次聚類的類心：根據(jù)圖2（c）中數(shù)據(jù)分布重新計算2類的類心得到圖2（c）中2個新的紅色加號。

第3次聚類，如圖2（d）所示，目標函數(shù)的值J=16.60，前后2次誤差為0，聚類無改變，算法結(jié)束。

通過以上實例的講解，學習到K-means算法的過程：根據(jù)初始數(shù)據(jù)類劃分，更新每類的類心；根據(jù)更新的類心，更新數(shù)據(jù)類劃分，重復上述過程，直到數(shù)據(jù)劃分不改變或者僅有較小的改變結(jié)束聚類過程。

2.3 拓展實例

K-means算法的參數(shù)包括兩方面，分別是：①聚類個數(shù)C不同，聚類結(jié)果是否相同？②初始聚類中心不同，聚類結(jié)果是否不同？如果聚類中心不正確，是否能得到正確的聚類結(jié)果？針對上述2個問題，通過2組實例數(shù)據(jù)分析K-means聚類算法的性能。

例2：設7個2維數(shù)據(jù)如表1所示。初始狀態(tài)數(shù)據(jù)分布如圖3（a）所示。聚類過程如下：

（1）初始化：設7個數(shù)據(jù)分成C=2類，隨機選取X₁和X₇作為2個類心，用紅色+號標記。

（2）第1次聚類：根據(jù)圖3（a）中的類心，計算每個數(shù)據(jù)到類心的距離如表4所示，從中選取距離較近的類心作為當前該數(shù)據(jù)的類屬。第1次迭代后得到聚類為：{X₁X₂X₃X₄}{X₅X₆X₇}，如圖3（b）中2個圓圈所示，目標函數(shù)J=12.60。

（3）更新第1次聚類的類心：根據(jù)圖3（b）中數(shù)據(jù)分布重新計算2類的類心得到圖3（b）中2個新的紅色加號。

（4）第2次聚類如圖3（c）所示，目標函數(shù)的值J=12.60，前后2次誤差為0，聚類無改變，算法結(jié)束。

上述實例說明：無論初始聚類中心如何設置，迭代過程會不斷修正，使其收斂到一個局部最優(yōu)的聚類結(jié)果。但是，初始聚類中心不同，聚類結(jié)果不同。作為初始聚類中心比更合適，因為前者最終聚類目標函數(shù)比后者低，聚類結(jié)果更合理。

接下來，研究聚類類數(shù)對聚類結(jié)果的影響，設計實驗對比不同聚類類數(shù)的聚類結(jié)果。

例3：設7個2維數(shù)據(jù)如表1所示。初始狀態(tài)數(shù)據(jù)分布如圖4（a）所示。聚類過程如下：

（1）初始化：設7個數(shù)據(jù)分成C=3類，隨機選取{X₃X₄₇}作為3個初始聚類中心，用紅色+號標記。

（2）第1次聚類：根據(jù)圖4（a）中的類心，計算每個數(shù)據(jù)到類心的距離如表5所示，從中選取距離較近的類心作為當前該數(shù)據(jù)的類屬。第1次迭代后得到聚類為{X₁X₃}{X₂X₄}{X₅X₆X₇），如圖4（b）中3個圓圈所示，目標函數(shù)，/=7.99。

（3）更新第1次聚類的類心：根據(jù)圖4（b）中數(shù)據(jù)分布重新計算2類的類心得到圖4（b）中2個新的紅色加號。

（4）第2次聚類如圖4（c）所示，目標函數(shù)的值J=7.99，前后2次誤差為0，聚類無改變，算法結(jié)束。

上述實例說明：初始聚類類數(shù)C不同，聚類結(jié)果不同。C=3作為初始聚類類數(shù)比C=2更合適，因為前者最終聚類目標函數(shù)比后者低，聚類結(jié)果更合理?？梢愿鶕?jù)先驗知識或者專家經(jīng)驗確定初始的聚類類數(shù)的范圍，在此范圍內(nèi)多次運行聚類算法，從中選擇最合適的聚類類數(shù)及其聚類結(jié)果作為最終的聚類結(jié)果。

2.4 教學評價

實例教學策略所選擇的仿真問題和仿真數(shù)據(jù)來源于實際問題，可以極大調(diào)動學生學習興趣。實例教學策略通過Matlab軟件仿真將抽象的聚類過程具象呈現(xiàn)在學生面前，降低了算法學習的難度，易于學習。實例拓展分析了實際問題所遇到的參數(shù)設置，可以提升學生在實際中應用K-means算法求解的操作能力。

設計問卷對比研究傳統(tǒng)教學策略和實例教學策略2種教學方法學生喜歡程度。問卷包括A～E共5個等級及其對應分值，分別是：非?？菰铮?2分）、比較枯燥（-1分）、一般（0分）、比較有趣（1分）和非常有趣（2分）。本次調(diào)查分傳統(tǒng)教學法和實例教學策略兩部分內(nèi)容，分別發(fā)放問卷50份，回收問卷48份，回收率96%，問卷有效率為100%。傳統(tǒng)教學策略的投票結(jié)果如表6所示；實例教學策略的投票結(jié)果如表7所示。調(diào)查結(jié)果顯示：學生更喜歡通過實例教學策略學習數(shù)據(jù)挖掘課程，實例教學策略的綜合得分遠遠高出傳統(tǒng)教學策略的得分。

3 結(jié)語

K-means聚類算法采用了期望最大化和梯度下降等數(shù)學方法，迭代求解數(shù)據(jù)聚類，其求解過程抽象復雜，不易于在有限課時范圍內(nèi)開展大規(guī)模的理論分析，學生學習較為困難。實例教學策略能夠深入淺出、形象具體地展現(xiàn)K-means聚類的方方面面，加深學生對于算法的理解，為學生進一步應用算法解決實際問題奠定基礎，具有較好的教學效果。未來將深入研究數(shù)據(jù)挖掘課程中其他算法的實例教學策略。

（見習編輯：張勛）