K—means聚類算法的實(shí)例教學(xué)研究

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

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

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

0 引言

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

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

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

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

1 K-means聚類算法理論基礎(chǔ)

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

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

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

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

K-means算法描述如下：

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

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

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

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

2 K-means聚類算法的實(shí)例教學(xué)

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

2.1 實(shí)例選擇

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

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

2.2 實(shí)例講解

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

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

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

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

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

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

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

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

2.3 拓展實(shí)例

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

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

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

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

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

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

上述實(shí)例說明：無論初始聚類中心如何設(shè)置，迭代過程會(huì)不斷修正，使其收斂到一個(gè)局部最優(yōu)的聚類結(jié)果。但是，初始聚類中心不同，聚類結(jié)果不同。作為初始聚類中心比更合適，因?yàn)榍罢咦罱K聚類目標(biāo)函數(shù)比后者低，聚類結(jié)果更合理。

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

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

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

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

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

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

上述實(shí)例說明：初始聚類類數(shù)C不同，聚類結(jié)果不同。C=3作為初始聚類類數(shù)比C=2更合適，因?yàn)榍罢咦罱K聚類目標(biāo)函數(shù)比后者低，聚類結(jié)果更合理。可以根據(jù)先驗(yàn)知識(shí)或者專家經(jīng)驗(yàn)確定初始的聚類類數(shù)的范圍，在此范圍內(nèi)多次運(yùn)行聚類算法，從中選擇最合適的聚類類數(shù)及其聚類結(jié)果作為最終的聚類結(jié)果。

2.4 教學(xué)評價(jià)

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

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

3 結(jié)語

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

（見習(xí)編輯：張勛）