尹曉麗

(山西大學商務學院 基礎教學部,太原 030006)

重心隨機漂移KMeans聚類算法的設計

尹曉麗

(山西大學商務學院 基礎教學部,太原 030006)

利用KMeans聚類算法進行聚類過程中，有可能會產生孤立聚點，這種情況一旦發(fā)生，會嚴重影響算法的聚類效果。為避免產生孤立聚點，本文改進了KMeans聚類算法，設計了一類重心隨機漂移(Center Random Drift，簡稱CRD)KMeans聚類算法。該算法會首先判斷生成的聚點是否是孤立聚點，利用CRD算法對孤立聚點進行替換，從而有效避免了孤立聚點的產生。通過在Matlab環(huán)境下進行圖像聚類對比實驗發(fā)現，針對色彩豐富的圖片，新算法和傳統(tǒng)KMeans算法性能沒有明顯差異，而針對圖片色彩比較單一的圖片，傳統(tǒng)的KMeans聚類算法聚類效果不佳，新算法依然可以有效聚類。

KMeans聚類；機器學習；CRD KMeans聚類；Matlab

0 引言

隨著人工智能、物聯(lián)網以及互聯(lián)網的發(fā)展，獲取大規(guī)模數據變得越來越容易，各種數據平臺的快速發(fā)展逐漸奠定了當代大數據應用的基礎[1]。對大量數據進行初步的加工往往要求將某些相似的數據進行分類，聚類是一種利用數據的分布特點進行數據加工的常用技術。在人工智能應用中，聚類算法屬于無監(jiān)督學習的一種。KMeans聚類是著名的聚類算法之一，其簡潔、高效使其成為科技工作者最青睞的聚類工具[2]。

針對傳統(tǒng)KMeans聚類算法隨機選取初始聚類中心造成聚類精度及效率較低的問題，近年來，有大量相關的研究成果發(fā)表。文獻[3-6]討論了KMeans聚類算法在不同編程環(huán)境的實現問題。文獻[7]利用了遺傳算法的全局尋優(yōu)能力，對K均值算法進行改進，以克服傳統(tǒng)K均值算法的局部性和對初始中心的敏感性。文獻[8]采用密度敏感的相似性度量來計算對象的密度，啟發(fā)式生成樣本初始中心；文獻[9]提出通過計算每個數據對象的密度參數，然后選取處于高密度分布的點作為初始距離中心；文獻[10]提出基于密度參數和距離理論的初始聚類中心的確定和孤立點的判斷方法，對孤立點問題給出了解決辦法；文獻[11]采用僅對代表性數據點而非數據集中所有數據點進行迭代聚類的方法，能夠在保證聚類質量的前提下，有效提高聚類效率；文獻[12]則利用擬蒙特卡洛(Quasi-Monte Carlo,QMC)方法序列分布的超均勻性特點，對整個樣本空間中的樣本分布進行采樣估計，從而得到初始聚類中心。上述算法在初始聚點的選取方面做了有效的改進，取得了較好的效果，但一定程度上增加了算法的復雜度，本文設計的算法將在保持傳統(tǒng)KMeans聚類算法簡單實用的特點基礎上，解決隨機選擇初始聚點導致的聚類效率較低的問題，并通過圖像聚類實驗對算法的有效性進行了驗證。

1 孤立聚點分析

KMeans聚類算法的實現步驟是先選k個點作為初始聚點，然后對所有的點進行一次遍歷，為每個點尋找一個最近的聚點，實現所有點按聚點進行分類，然后重新計算每類點的均值作為新的聚點，重復這個過程直到各個數據點與所屬聚點的距離的平方和達到最小(這也是評價Kmeans算法最后聚類效果的評價標準)就能實現所有點的聚類。但有些情況下會出現下面定義的孤立聚點。

定義1. 若隨機生成的聚點中，存在聚點使得所有點都不屬于該聚點，則稱該聚點為孤立聚點。

圖1 孤立聚點示意

如圖1所示，p1, p2是原始點集，c1, c2是隨機生成的聚點，因為p1, p2都離c1更近，所以顯然c2是孤立聚點。

2 CRD-KMeans聚類算法

2.1 算法核心思想

設p1,p2,…pm是待聚類點集，z1,z2,…,zk是隨機設置的k個聚點，不妨設前k-1個聚點是正常聚點，只有zk是孤立聚點。則采用以下方法對zk進行更新：

其中，ai是滿足以下要求的一組隨機數：

(1)0

當隨機生成的聚點中包含多個孤立聚點時，可利用非孤立聚點，重復采用上述方法依次更新孤立聚點，從而生成新的一組聚點。

注1：ai為滿足(2.1-2.2)約束的隨機取值保證了代替所有孤立聚點的新聚點都是非孤立聚點的隨機凸組合，故將改算法命名為重心隨機漂移KMEAN聚類算法(簡稱CRD-KMeans)。

2.2 設計步驟

CRD-KMeans聚類算法的設計分為以下幾個步驟：

(1)初始化，即創(chuàng)建對象集X，設置聚點數目k，在X中隨機選取k個對象作為初始聚類點；

(2)按聚點分類，即為每個數據對象計算最接近的聚類中心，完成針對當前聚點的分類；

(3)利用重心隨機漂移算法更新可能產生的孤立聚點；

(4)為各組對象重新計算平均值，作為新的聚點；

(5)設定迭代中止條件，一般設置為當各個像素點與所在類的距離的平方和更新幅度小于閾值(tol)時停止迭代。

反復執(zhí)行(2)-(4)，直至滿足終止條件。

2.3 算法核心代碼

以下是實現更新孤立聚點的偽代碼：

{ st=[];

j=0;

for i=1:k//k表示聚點數目

if notEmpty(Z(i))//如果第i個聚點不是孤立聚點，執(zhí)行下面的代碼：

st=[st;Z(i)];//將非孤立聚點保存在st中

j=j+1;//j用于記錄非孤立聚點數

end

end

for i=1:k

if isEmpty(Z(i))//如果第i個聚點是孤立聚點，執(zhí)行下面的代碼

a=rand(1,j);//生成一個j維隨機行向量，元素為隨機正數

a=a/sum(a); //將a化為單位向量

Z(i)=a*st;//利用矩陣運算生成新聚點代替原來的孤立聚點

end

end

}

其中，Z是聚點集，isEmpty(Z(i))和notEmpty(Z(i))用于判斷Z(i)是否是孤立聚點，st用于存儲非孤立聚點，a為滿足約束(2.1-2.2)的隨機行向量，該算法可實現將全部孤立聚點更新為非孤立聚點的隨機凸組合。

3 實驗驗證

實驗采用了兩張圖片，一張色彩比較豐富，另一張色彩比較簡單。分別針對兩張圖片用傳統(tǒng)KMeans算法和本文設計的CRD-KMeans算法進行了兩組實驗。具體步驟是：對圖片的像素點進行聚類，用聚點代替像素點重構圖像。

實驗參數設置及運行結果如表1所示。

表1 實驗參數設置及運行結果

表1中，tol表示迭代終止的閾值(即J的改變小于tol時迭代終止)；K表示聚點個數；N表示迭代結束后進行迭代的總次數；J表示迭代結束后各個像素點與所在類的距離的平方和。相同條件下，J越小越好。

圖2 針對第一張圖的實驗結果

圖3 針對第二張圖的實驗結果

表1和圖2表明，針對色彩較豐富的圖片，兩種算法都進行了64次迭代，最終形成10個聚點，各個像素點與所在類的距離的平方和都為1.4094e+07，兩種算法的聚類效果沒有明顯區(qū)別。表1的數據顯示，針對色彩比較簡單的圖片，實驗設定聚點個數都為4，傳統(tǒng)的KMeans算法迭代3次后迭代步驟結束，各個像素點與所在類的距離的平方和為2.2646e+08；而CRD-KMeans算法迭代了4次，J的值為4.2869e+05，明顯優(yōu)于傳統(tǒng)KMeans算法。圖3的實驗結果直觀地表明CRD-KMeans算法很好地完成了聚類。

4 結語

本文設計的CRD-KMeans算法保持了傳統(tǒng)的KMeans聚類算法簡單高效的特點，同時解決了傳統(tǒng)KMeans聚類算法可能產生孤立聚點從而導致聚類效果不佳的問題。雖然傳統(tǒng)的KMeans聚類算法設定足夠大的聚點數k也可以在一定程度上避免出現孤立聚點導致的聚類異常，但增加了計算量和人工試錯的成本。在數據規(guī)模較大的情況下，CRD-KMeans聚類算法的優(yōu)勢更加明顯。因此，CRD-KMeans聚類算法比傳統(tǒng)的KMeans聚類算法適應范圍更廣，更具有實用性。

[1] 王若倪,趙慧玲. 大數據技術發(fā)展趨勢及燈塔大數據行業(yè)應用平臺[J]. 中興通訊技術, 2016, 22(3): 57-61.

[2] 孫吉貴,劉杰,趙連宇. 聚類算法研究[J]. 軟件學報, 2008, 19(1): 48-61.

[3] 吳再龍,張云泉,徐建良，等. 基于OpenCL的Kmeans算法的優(yōu)化研究[J]. 計算機科學與探索, 2014, 8(10): 1162-1176.

[4] 陳壽文,李明東. 基于面向對象思想KMeans算法實現[J]. 滁州學院學報, 2008, 10(3): 42-44.

[5] 孫宇鋒. 基于Matlab的模糊聚類分析及應用[J]. 韶關學院學報(自然科學版), 2006, 27(9):1-4.

[6] 宋麗紅. K-均值聚類的Matlab仿真設計[J]. 實驗技術與管理, 2010, 27(10): 101-103.

[7] 賴玉霞,劉建平,楊國興. 基于遺傳算法的K均值聚類分析[J]. 計算機工程, 2008, 34(20): 200-202.

[8] 汪中,劉貴全,陳恩紅. 一種優(yōu)化初始中心點的K-means算法[J]. 模式識別與人工智能, 2009, 22(2): 299-304.

[9] 韓凌波,王強,蔣正鋒,等. 一種改進的K-means初始聚類中心選取算法[J]. 計算機工程與應用, 2010, 46(17): 150-152.

[10] 楊金花,劉顯為. K-means聚類算法初始中心選擇研究[J]. 河南科學, 2016, 34(3): 348-351.

[11] 趙文沖,蔡江輝,趙旭俊,等. 一種影響空間下的快速K-means聚類算法[J]. 小型微型計算機系統(tǒng), 2016, 37(9): 2060-2064.

[12] 莊瑞格, 倪澤邦, 劉學藝.基于擬蒙特卡洛的K均值聚類中心初始化方法[J].濟南大學學報(自然科學版), 2017, 31(1):35-41.

責任編輯：程艷艷

Design of Center Random Drift (CRD) KMeans Clustering Algorithm

YIN Xiaoli

(Department of Basic Teaching, Business College of Shanxi University, Taiyuan 030006, China)

KMeans clustering algorithm will probably generate isolated points during clustering process, once this happens, it will seriously deteriorate the effect of the clustering algorithm. In order to avoid generating isolated points, an algorithm called center random drift (CRD) KMeans clustering is designed, which will firstly determine whether the cluster point is isolated, and if it is, it will be replaced by using CRD algorithm, so as to avoid the isolated point effectively. Through comparative experiments of image clustering in Matlab environment, it is found that there is no significant difference between the new algorithm and the traditional KMeans algorithm for the colorful pictures, while for a picture with a single color, the traditional KMeans clustering algorithm’s clustering effect is poor, but the new algorithm can still work effectively.

KMeans clustering; machine learning; CRD KMeans clustering; Matlab

2017-04-20

國家社會科學規(guī)劃基金(16BTJ034)

尹曉麗(1984-)，女，山西臨汾人，講師、碩士，主要從事自然語言處理、智能控制方面研究。

TP301

A

1009-3907(2017)08-0035-04