胡朝清

（德宏師范高等專(zhuān)科學(xué)校，云南德宏 678400）

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

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

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

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

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

命令行解析模塊為程序?qū)崿F(xiàn)一個(gè)簡(jiǎn)單易用且功能強(qiáng)大的用戶交互界面，通過(guò)命令行的方式獲取用戶需要的參數(shù)，包括數(shù)據(jù)文件路徑、數(shù)據(jù)集名稱(chēng)所在列、將數(shù)據(jù)集分割成為聚類(lèi)的個(gè)數(shù)、判斷浮點(diǎn)數(shù)是互相等的閾值等［2］。使用命令行作為交互界面不僅使用方便，而且便于通過(guò)腳本實(shí)現(xiàn)自動(dòng)貨批量處理，為該程序與其它程序整合和集成提供了方便。該模塊通過(guò)調(diào)用GNU getopt模塊實(shí)現(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ù)分析模塊定義為一個(gè)抽象類(lèi)solver，提供add＿data和solve兩個(gè)抽象方法。當(dāng)數(shù)據(jù)讀取模塊成功地從輸入流中獲取一行數(shù)據(jù)時(shí)，調(diào)用solver的add＿data方法，將數(shù)據(jù)添加到solver的sovle方法對(duì)數(shù)據(jù)進(jìn)行處理。當(dāng)使用不同的算法分析數(shù)據(jù)時(shí)，只需要繼承solver類(lèi)，在子類(lèi)中實(shí)現(xiàn)自己的solve方法即可，無(wú)須再考慮數(shù)據(jù)讀取和文件格式解析的問(wèn)題。

1.3 聚類(lèi)分析模塊（k＿means）［3－4］

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

圖3 K-means算法實(shí)現(xiàn)類(lèi)圖

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

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

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

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

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

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

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

圖5 聚類(lèi)中心位置

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

圖6 聚類(lèi)結(jié)果

雖然vector在增長(zhǎng)過(guò)程中可能會(huì)消耗一些額外時(shí)間，但由于每輪迭代后并不釋放vector占用的空間，這類(lèi)額外開(kāi)鎖會(huì)非常小，可以忽略不計(jì)。

2.2 算法實(shí)現(xiàn)

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

3 實(shí)驗(yàn)結(jié)果

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

3.1 iris.data

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

3.2 wine.data

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

3.3 glass.data

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

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

4 實(shí)驗(yàn)分析

4.1 初始數(shù)據(jù)點(diǎn)對(duì)聚類(lèi)的影響

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

4.2 如何確定類(lèi)別個(gè)數(shù)

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

4.3 遞增式聚類(lèi)

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

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

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

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

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

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

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

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

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