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

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

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

0 引言

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

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

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

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

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

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

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

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

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

K-means算法描述如下：

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

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

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

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

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

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

2.1 實(shí)例選擇

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

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

2.2 實(shí)例講解

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

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

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

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

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

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

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

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

2.3 拓展實(shí)例

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4 教學(xué)評(píng)價(jià)

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

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

3 結(jié)語(yǔ)

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

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