K-means算法研究

胡朝清

（德宏師范高等?？茖W(xué)校，云南德宏 678400）

1 應(yīng)用程序設(shè)計

K-means算法首先接受輸入量k；然后將n個數(shù)據(jù)對象劃分為k個聚類，以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較小。聚類相似度是利用各聚類中對象的均值所獲得一個“中心對象”（引力中心）來進(jìn)行計算的［1］。依據(jù)K-means聚類的原理，在做應(yīng)用程序設(shè)計時，一般將程序分為主程序、命令行解析模塊、數(shù)據(jù)文件讀取模塊和聚類分析模塊4大部分，各部分關(guān)系如圖1所示。

圖1 程序構(gòu)件圖

主程序通過命令行解析模塊獲取用戶輸入?yún)?shù)，創(chuàng)建聚類分析模塊和數(shù)據(jù)讀取模塊，通過數(shù)據(jù)讀取模塊將輸入文件讀取到聚類分析模塊中，然后調(diào)用聚類分析模塊將數(shù)據(jù)進(jìn)行分類并直接輸出。

1.1 命令行解析模塊（cmd＿parser）

命令行解析模塊為程序?qū)崿F(xiàn)一個簡單易用且功能強(qiáng)大的用戶交互界面，通過命令行的方式獲取用戶需要的參數(shù)，包括數(shù)據(jù)文件路徑、數(shù)據(jù)集名稱所在列、將數(shù)據(jù)集分割成為聚類的個數(shù)、判斷浮點數(shù)是互相等的閾值等［2］。使用命令行作為交互界面不僅使用方便，而且便于通過腳本實現(xiàn)自動貨批量處理，為該程序與其它程序整合和集成提供了方便。該模塊通過調(diào)用GNU getopt模塊實現(xiàn)命令行的解析，接受以下參數(shù)：

1.2 數(shù)據(jù)文件讀取模塊（data＿reader）

由于在數(shù)據(jù)挖掘和數(shù)據(jù)分析中，經(jīng)常需要進(jìn)行數(shù)據(jù)讀取操作，因此為了讓程序能夠盡量通用，方便以后的擴(kuò)展，組織文件讀取模塊和數(shù)據(jù)分析模塊，其使用方式如圖2所示。

圖2 通用的數(shù)據(jù)讀取框架

在此，將數(shù)據(jù)分析模塊定義為一個抽象類solver，提供add＿data和solve兩個抽象方法。當(dāng)數(shù)據(jù)讀取模塊成功地從輸入流中獲取一行數(shù)據(jù)時，調(diào)用solver的add＿data方法，將數(shù)據(jù)添加到solver的sovle方法對數(shù)據(jù)進(jìn)行處理。當(dāng)使用不同的算法分析數(shù)據(jù)時，只需要繼承solver類，在子類中實現(xiàn)自己的solve方法即可，無須再考慮數(shù)據(jù)讀取和文件格式解析的問題。

1.3 聚類分析模塊（k＿means）［3－4］

數(shù)據(jù)讀取完畢后，程序通過k＿means類對數(shù)據(jù)進(jìn)行處理。k＿means類繼承自solver類，將解題過程分為“初始化”、“迭代計算”和“輸出結(jié)果”3個步驟進(jìn)行，如圖3所示。

圖3 K-means算法實現(xiàn)類圖

2 算法實現(xiàn)［5－6］

程序主要基于STL來實現(xiàn)，下面分別從數(shù)據(jù)結(jié)構(gòu)和算法實現(xiàn)兩方面進(jìn)行分析。

2.1 數(shù)據(jù)結(jié)構(gòu)

在輸入數(shù)據(jù)上使用一個vector保存，每個元素為一個結(jié)構(gòu)體，包括元組名稱和數(shù)據(jù)兩部分，如圖4所示。

圖4 輸入數(shù)據(jù)存儲

雖然在迭代過程中只對數(shù)據(jù)集進(jìn)行順序操作，不進(jìn)行隨機(jī)訪問，但使用list會造成讀取效率降低。雖然vector在初始化數(shù)據(jù)集的時候空間增長時有一些額外開銷，但讀取完畢之后就不再存在這樣的內(nèi)存占用，因此是比較值得的。而讀取完畢后就不再對該數(shù)據(jù)進(jìn)行任何寫操作，因此，也不必考慮vector的內(nèi)存失效問題。

由于聚類中心數(shù)據(jù)量不大，在聚類過程中又需要頻繁讀寫，因此使用vector保存數(shù)據(jù)。聚類中心結(jié)構(gòu)保存如圖5所示。

圖5 聚類中心位置

聚類結(jié)果僅進(jìn)行“尾部添加”操作，無須隨機(jī)訪問，似乎比較適合使用list。但是由于每次迭代完畢后，都需要將結(jié)果集清空重新進(jìn)行下一輪迭代，而list的銷毀需要消耗線性時間復(fù)雜度，因此，仍然使用vector保存聚類結(jié)果，如圖6所示。

圖6 聚類結(jié)果

雖然vector在增長過程中可能會消耗一些額外時間，但由于每輪迭代后并不釋放vector占用的空間，這類額外開鎖會非常小，可以忽略不計。

2.2 算法實現(xiàn)

程序初始化時，在聚類中心數(shù)組中填充數(shù)據(jù)集中的前n組數(shù)據(jù)，然后開始迭代：將數(shù)據(jù)集中的每個數(shù)據(jù)與聚類中心點的距離進(jìn)行比較，將數(shù)據(jù)焦距的數(shù)據(jù)添加到與之最近的中心點所對應(yīng)的結(jié)果集里，在添加過程中直接累加各結(jié)果集的向量和，為一次迭代完成后重新計算聚類中心提供方便，提高程序運行的效率。當(dāng)一次迭代和前一次迭代之間聚類中心沒有再移動時，認(rèn)為迭代已經(jīng)完成，進(jìn)入輸入聚類結(jié)果階段［7－8］。

3 實驗結(jié)果

測試數(shù)據(jù)集在不同聚類數(shù)目下的聚類結(jié)果正確率如圖7所示。

3.1 iris.data

該數(shù)據(jù)集中包含3種數(shù)據(jù)，一共4維。從圖7中可以看出，當(dāng)聚類個數(shù)小于3時，聚類正確類較低，當(dāng)聚類個數(shù)大于等于數(shù)據(jù)集中包含數(shù)據(jù)類型時，聚類正確率較高。

3.2 wine.data

該數(shù)據(jù)焦距包含3種數(shù)據(jù)，一共13維。從圖7中可以看出，當(dāng)聚類個數(shù)小于3時，聚類正確類較低，當(dāng)聚類個數(shù)大于等于數(shù)據(jù)集中包含數(shù)據(jù)類型時，聚類正確率較高。

3.3 glass.data

該數(shù)據(jù)集中包含6種數(shù)據(jù)，一共9維。從圖7中可以看出，當(dāng)聚類個數(shù)小于6時，聚類正確率較低，當(dāng)聚類個數(shù)大于等于數(shù)據(jù)集中包含數(shù)據(jù)類型時，聚類正確率較高。

圖7 聚類結(jié)果正確率分析

4 實驗分析

4.1 初始數(shù)據(jù)點對聚類的影響

當(dāng)數(shù)據(jù)集各類型數(shù)據(jù)之間距離比較遠(yuǎn)，而聚類內(nèi)部距離比較近時，如果聚類個數(shù)與類型數(shù)相符時，聚類初始數(shù)據(jù)點不會影響到聚類結(jié)果。如果聚類個數(shù)與類型數(shù)不等時，初始數(shù)據(jù)點會影響到聚類結(jié)果。如果數(shù)據(jù)集各類型數(shù)據(jù)之間不能保持相對聚集的特性時，聚類結(jié)果對初始數(shù)據(jù)點位置高度敏感。

4.2 如何確定類別個數(shù)

通過測定每一個聚類的邊界，然后計算每個聚類之間邊界的距離。如果類別個數(shù)增加到一定數(shù)量后，繼續(xù)增加時，沒有出現(xiàn)兩個距離較遠(yuǎn)的聚類，而是出現(xiàn)兩個緊貼的聚類時，說明聚類個數(shù)已經(jīng)大于類別個數(shù)，通過這樣的方式可以判斷出應(yīng)該劃分的類別個數(shù)。

4.3 遞增式聚類

當(dāng)把新的數(shù)據(jù)點加入已經(jīng)聚合好的聚類時，可以直接使用迭代算法重新調(diào)整聚類劃分。由于絕大部分點在這個過程中都不會出現(xiàn)大范圍調(diào)整，因此可以在比較小的運算量下完成該計算。

［1］ 吳夙慧，成穎，鄭彥寧，等.K-means算法研究綜述［J］.現(xiàn)代圖書情報技術(shù)，2011（5）：28-35.

［2］ 馮超.K-means聚類算法的研究［D］：［碩士學(xué)位論文］.大連：大連理工大學(xué)，2007.

［3］ 周愛武，于亞飛.K-means聚類算法的研究［J］.計算機(jī)技術(shù)與發(fā)展，2011（2）：62-65.

［4］ 吳夙慧，成穎，鄭彥寧，等.文本聚類中文本表示和相似度計算研究綜述［J］.情報科學(xué)，2012，30（4）：623-627.

［5］ 周麗娟.改進(jìn)粒子群算法和蟻群算法混合應(yīng)用于文本聚類［J］.長春工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2009，30（3）：341-346.

［6］ 袁方，周志勇，宋鑫.初始聚類中心優(yōu)化的K-means算法［J］.計算機(jī)工程，2007，33（3）：65-66.

［7］ 李鈺，孟祥萍.基于Gabor濾波器的圖像紋理特征提［J］.長春工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2008，29（1）：78-81.

［8］ 石云平.聚類K-means算法的應(yīng)用研究［J］.國外電子測量技術(shù)，2009，29（8）：28-31.