K-means算法研究

胡朝清

（德宏師范高等專科學校，云南德宏 678400）

1 應用程序設計

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

圖1 程序構件圖

主程序通過命令行解析模塊獲取用戶輸入參數，創建聚類分析模塊和數據讀取模塊，通過數據讀取模塊將輸入文件讀取到聚類分析模塊中，然后調用聚類分析模塊將數據進行分類并直接輸出。

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

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

1.2 數據文件讀取模塊（data＿reader）

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

圖2 通用的數據讀取框架

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

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

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

圖3 K-means算法實現類圖

2 算法實現［5－6］

程序主要基于STL來實現，下面分別從數據結構和算法實現兩方面進行分析。

2.1 數據結構

在輸入數據上使用一個vector保存，每個元素為一個結構體，包括元組名稱和數據兩部分，如圖4所示。

圖4 輸入數據存儲

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

由于聚類中心數據量不大，在聚類過程中又需要頻繁讀寫，因此使用vector保存數據。聚類中心結構保存如圖5所示。

圖5 聚類中心位置

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

圖6 聚類結果

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

2.2 算法實現

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

3 實驗結果

測試數據集在不同聚類數目下的聚類結果正確率如圖7所示。

3.1 iris.data

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

3.2 wine.data

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

3.3 glass.data

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

圖7 聚類結果正確率分析

4 實驗分析

4.1 初始數據點對聚類的影響

當數據集各類型數據之間距離比較遠，而聚類內部距離比較近時，如果聚類個數與類型數相符時，聚類初始數據點不會影響到聚類結果。如果聚類個數與類型數不等時，初始數據點會影響到聚類結果。如果數據集各類型數據之間不能保持相對聚集的特性時，聚類結果對初始數據點位置高度敏感。

4.2 如何確定類別個數

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

4.3 遞增式聚類

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

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

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

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

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

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

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

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

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