優化初始聚類中心的改進K-means算法

唐東凱，王紅梅，胡 明，2，劉 鋼

1(長春工業大學 計算機科學與工程學院，長春 130012) 2(長春工程學院，長春 130021) E-mail：wanghm@ccut.edu.cn

1 引 言

聚類的目標是最大化同一個簇中數據對象的相似程度，并使不同簇中的數據對象的相似程度最小[1].根據聚類過程的不同，Han[2]等人，將聚類分成基于密度、基于劃分、基于模型、基于網格、基于層次的五種聚類模型.K-means算法最早由MacQueen[3]提出，是基于劃分模型中的一種，因其計算簡單、容易理解而被廣泛應用.

隨機選取初始中心點的方法，使得K-means算法易陷入局部最優解，且聚類結果不穩定.針對這一缺點，眾多學者提出了許多優化初始中心點的選擇方法.Arthu[4]等人提出了K-means++算法，該算法首先在數據集上隨機選取一個數據對象作為第一個初始中心點，再在剩余的數據對象中，計算到已有初始中心點的歐式距離，選擇距離值最大的數據對象作為第二個初始中心點，重復上述過程，直到選出k個初始中心點為止.文獻[5,6]引入智能算法的思想，在每次迭代計算初始中心點的時候分別使用粒子群算法和遺傳算法來迭代尋找最優解，選取使誤差平方和最小的數據對象作為初始中心點.成衛青[7]等人首先在數據集中選取兩個距離最遠的數據對象，其次再選取分別與這兩個數據對象距離最近的兩個數據對象作為初始中心點，使用K-means算法進行聚類，對聚類效果最差的那個簇，使用上述方法選取新的初始中心點，最后進行聚類.一些學者從數據對象的密度特征出發[8-10]，文獻[8]按照密度聚類的思想首先計算出每個數據對象的密度值，然后在高密度值的數據對象中選取相互距離最遠的數據對象作為初始中心點.文獻[9]也是先計算出每個數據對象的密度值，找出距離最高密度值最近的數據對象，然后用這兩個數據對象的中點作為第一個初始中心點，并以此為中心，以樣本間的平均距離為半徑畫圓，刪除在同一個圓內的所有數據對象，在剩余的數據對象中按上述方法繼續選擇初始中心點直到k個為止.文獻[10]以樣本的方差作為啟發信息，樣本間的平均距離作為半徑，在該區域選取方差最小的樣本作為初始聚類中心.

K-means算法易受離群點的影響，離群點的存在往往會影響初始中心點的選取，增加迭代次數，導致較差的聚類結果.對這一問題，冷泳林[11]等人首先使用基于距離的離群點檢測算法找出數據集中的離群點，在選擇初始中心點時避免選擇離群點作為初始中心點，只在非離群點中進行隨機選取.

在上述算法中有的解決了K-means算法隨機選取初始中心點的問題，但卻忽略的離群點對結果的影響，比如文獻[4-6]；有的雖然避免了離群點的影響，但最后還是隨機選取初始中心點，比如文獻[11].因此，針對K-means算法的兩種不足，本文使用離群因子來排除離群點的影響，最大最小算法來避免隨機選取初始中心點，提出了一種基于離群因子和最大最小算法的優化K-means初始中心選擇算法，即OFMMK-means算法(K-means algorithm based on Outlier Factor and Maximum and Minimum distances).實驗表明，在時間基本相同的情況下，OFMMK-means算法相比K-means算、K-means++算法，具有更好的聚類效果和較高的穩定性，另外還具有較少的迭代次數.

2 K-means算法

K-means算法核心思想是：設數據集含有n個數據對象，首先從這n個數據對象中隨機選取出k個對象作為初始聚類中心，對于剩余的對象根據每個數據對象與k個聚類中心的相似程度將其分配到最相似的簇中，然后對于每一個簇，將簇中的所有對象的平均值作為新的聚類中心，進行下次迭代.不斷重復該過程，直到簇中心不再發生變化，準則函數收斂，準則函數如公式(1)：

(1)

K-means算法初始聚類中心的選取是隨機的[12]，這樣容易造成聚類結果不穩定，且易陷入局部最優.另外，由于樣本中可能含有噪聲或者離群點，聚類中心對其比較敏感，也很容易導致較差的聚類結果.

3 OFMMK-means算法

OFMMK-means算法對于初始中心點的選取主要分三個過程：1)對數據集先進行基于密度的離群點檢測，計算出每個數據對象的離群因子；2)根據離群因子的大小對數據集進行升序排列；取前α*n(0<α≤1，n為樣本集的大小)個數據對象作為初始中心點的候選集；3)在候選初始中心點集上根據最大最小算法，選取距離最遠的數據對象作為初始中心點.下面分別對這三個過程進行介紹.

3.1 計算離群因子

K-means算法在隨機選取初始中心點時，如果數據集中存在離群點或噪聲，很容易使初始中心點偏離最優的聚類中心，降低聚類精度.所謂離群點是指明顯偏離數據集中其他對象的數據點.離群點檢測方法可以發現數據集中小部分偏離大多數數據行為或數據模型的異常數據，可以避免離群點對聚類的影響[13].

本文使用基于密度的離群點檢測算法-LOF算法[14]來計算數據對象的離群因子.離群因子的大小反映了數據對象的偏離程度，離群因子越大，則說明其偏離程度越高，越有可能是離群點；反之，離群因子越小，則說明它周圍的數據對象越多，其密度越大，越有可能是中心點.所以OFMMK-means算法使用離群因子來限定初始中心點的選取范圍，選取那些離群因子小的數據對象作為初始中心點可以更切合中心點的實際情況.下面介紹一下LOF算法中涉及的基本概念.

定義.對象p的第k距離(k-distance of an objectp).

對于一個正整數k，數據對象p的第k距離記為k-dis(p).在數據集D中，存在一個數據對象o，該數據對象與數據對象p之間的距離記作d(p，o).滿足以下條件，則取k-dis(p)等于d(p，o)：

1)至少存在k個數據對象o′∈D/{p}滿足d(p，o′)≤d(p，o)；

2)至多存在k-1個數據的對象o′∈D/{p}滿足d(p，o′)

該定義通過考察每一個數據對象與被考察對象之間的距離，并找出其中數值上為第k大的那個距離.根據定義，可進行離群因子的計算，以對象p為例：

第1步.構建對象p的第k距離鄰域

對象p的第k距離鄰域是指小于等于對象p的第k距離內的所有對象組成的集合.計算公式如(2).實際上該集合反映了數據對象的偏離程度，可以設想，如果該集合比較大，則說明該對象的第k距離鄰域比較大，則它的偏離程度就比較大，反之，若集合較小，則偏離程度就小.

Nk(p)={o∈D/{p}|d(p，o)≤k-dis(p)}

(2)

其中，d(p，o)表示數據對象p和數據對象o之間的歐式距離；k-dis(p)表示對象p的第k距離(見定義).

第2步.計算對象p的局部可達密度.

由第1步得出的對象p的第k距離鄰域，進而計算p的局部可達密度，對象p的局部可達密度是指對象p的Nk(p)內的所有對象的平均可達密度的倒數，具體計算公式如(3)：

(3)

考慮這樣一種情況，如果至少有k個對象和p有相同的坐標值，卻是不同的數據對象，那么公式(3)的分母就會趨近于0，而對象p的局部可達密度將趨于∞，相反如果數據對象p距離聚類簇較遠，相應的lrdk(p)值則較小.

第3步.計算對象p的離群因子.

結合公式(2)和(3)來計算p的離群因子，公式如下(4)：

(4)

分析公式(4)可知，LOFk(p)的大小反映的是數據對象p的第k距離范圍之內的空間點的平均分布密度，容易看出，若p的局部可達密度越小，p的Nk(p)內的對象可達密度越大，那么對象p的LOF值就越大.也就是說，一個對象的LOF值越大，那么該對象是離群點的概率也就越大.

綜合上述三步，可計算出數據集中的每個對象的離群因子，根據離群因子的大小可以知道離群點的分布情況，再進行初始中心點的選取時，就可以避免離群點的影響.

3.2 生成初始中心點候選集

3.1小節得出了數據集上每個數據對象的離群因子，離群因子的大小反映了該數據對象是中心點的可能性大小.也就是說，一個對象的離群因子越小，在實際聚類中，就越有可能是中心點；相反，那些離群因子大的對象，其偏離中心點的程度也就越大，在選擇初始中心點的時候，就應該避免選擇這樣的對象.

OFMMK-means算法產生候選初始中心點集的步驟：

第1步.根據3.1節計算出數據集D中每個數據對象i的離群因子LOFk(i)；

第2步.對數據集D按離群因子的大小，進行升序排序，并記為DL；

第3步.在DL上，選取前α*n(0<α≤1，n為數據集的大小)個數據對象作為候選初始中心點集，記為DCL.

OFMMK-means算法在產生候選初始中心點集時，在第三步引入了一個取樣參數α，α的取值過小，可能導致初始中心點集中在一個簇中，導致迭代次數增加，聚類效果較差.α取值過大，也容易選出較差的初始中心點.所以，α的取值本文通過實驗來確定.

3.3 選取初始中心點

OFMMK-means算法使用距離盡可能遠的數據對象作為初始聚類中心點，可以避免初始聚類中心過于鄰近的情況，這樣數據集能得到較好的劃分.Katsavounidis[15]等人于1994年提出最大最小法，它是聚類算法中初始聚類中心點的選擇方法之一.最大最小算法的初始中心點如公式(5)：

Ci=max{Disj;j=1，2，…，n}

(5)

其中，Disj數據對象j到中心點的最小距離；n為樣本個數；Disj的計算方法如公式(6)所示：

(6)

其中，C表示初始中心點集合；d(Ci，xj)為數據對象xj到初始中心Ci的歐式距離.

OFMMK-means算法使用最大最小距離來選取初始中心點，其過程描述如下：

Input：數據集D，聚類個數k

Output：k個初始中心點

Step1.令C=?，在D中隨機選取一個對象作為第一個初始中心C1，C={C1}；

Step2.在D剩余數據對象中，計算每個對象與C1的歐氏距離，選取值最大的那個作為第二個初始中心C2，C={C1，C2}；

Step3.repeat

對于xj(xj∈D/C)(j=1，2，…，n)按照公式(6)計算xj到初始中心的最小距離；

按照公式(5)，選出最大距離的對象作為Ci，C={C1，C2}∪{Ci}；

untili>k

Step4.輸出k個初始中心點.

OFMMK-means算法使用最大最小算法來選取初始中心點，可以避免初始中心點位于相同簇中，可以減少迭代的次數.

3.4 OFMMK-means算法描述

綜合上述3個過程，下面給出OFMMK-means算法的整體描述：

Input：數據集D，聚類個數k，取樣比例α

Output：完成聚類的k個簇

Step1.對D中的每一個數據對象，根據3.1小節離群因子的計算過程來計算每個對象i的離群因子LOFk(i)；

Step2.根據離群因子的大小，按照3.2小節產生候選初始中心點集DCL；

Step3.使用數據集DCL作為3.3小節中最大最小算法的輸入數據集，并按最大最小算法過程選出k個初始中心點；

Step4.從Step3中得到的k個中心點出發，執行K-means算法，得出聚類結果.

為了去除離群點，OFMMK-means算法根據離群因子的大小對數據集進行升序排列，并產生包含中心點的候選集，之后在候選集上根據最大最小距離來排除兩個初始中心點位于相同簇中的可能.則OFMMK-means算法減小了K-means算法對初始中心點敏感的程度.

4 實驗結果與分析

為了驗證本文算法OFMMK-means的有效性，選取UCI機器學習數據庫上的Iris、Wine、Balance-scale這3個基準數據集作為測試數據集.本文使用Python來實現所提出的算法以及涉及的相關算法，語言版本為Python2.7.0.運行環境為：Intel(R)Core(TM) i5-3470 CPU，3.20GHz，8.00GB，操作系統是Windows8.1系統，64位.

三個測試數據集的統計信息如表1所示：

表1 測試數據集信息Table 1 Details of test data

4.1 驗證參數α的取值

聚類結果用準確率作為評價指標，實驗4.2和4.3采用相同的評價標準.設樣本集D包括k個類，聚類準確率的表示如式(7)所示：

(7)

其中，ai表示被正確劃分到類Ci中的樣本數；|D|表示樣本總數.

OFMMK-means算法比K-means算法多了一個參數α，α的大小決定初始中心點的選擇范圍的大小，因此α的取值要適當.本文將在上述三種測試數據集上使用OFMMK-means算法進行聚類，并驗證α的取值，如圖1所示.

從圖1中可以看出，在前半部分，三種測試集的聚類精度隨著α值的增大而增大，在α取0.4左右時，達到最大值.當α值繼續增加時，聚類精度開始下降，這是因為候選初始中心點集變大，選擇范圍變大.值得注意的是，當α取值為1時，OFMMK-means算法已完全退化，相當于在全部測試數據集上，選取k個距離較遠的數據對象作為初始中心點，這過程和K-means++算法相同.

4.2 驗證OFMMK-means算法的有效性

本文的對比算法是K-means算法、K-means++算法以及本文算法OFMMK-means算法.三種算法分別在三種測試數據集上分別運行10次，取聚類精度的平均值作為最終結果.另外，根據實驗4.1，OFMMK-means算法中的參數α取0.4.

圖2顯示的是三種算法的聚類精度.首先從圖2中可以看出，在三種測試數據集上，OFMMK-means算法的聚類精度均高于其余兩種算法.也可以看出，K-means++算法優于K-means算法，這是因為K-means++算法的初始中心點不再是隨機選取的，而是根據最大最小算法思想選取距離相對較遠的數據對象作為中心點.但是它并沒有考慮到離群點對聚類結果的影響，可能會選擇距離較遠的離群點作為初始簇心，所以相較于排除離群點的OFMMK-means算法來說，其聚類精度稍低.圖3是三種算法在測試數據集上的運行時間.從圖3可以看出，OFMMK-means算法在三種數據集上執行時間與其他兩種算法的執行時間基本相同，差距不大.圖2和圖3分別從準確率和運行時間上驗證了OFMMK-means算法的有效性.

圖1 α值對準確率的影響Fig.1 Effect of α on accuracy

圖2 三種算法在測試數據集上準確率Fig.2 Accuracy of the three algorithms on the test data set

圖3 三種算法在測試數據集上的運行時間Fig.3 Time of the three algorithms on the test data set

4.3 驗證初始聚類中心對聚類精度的影響

K-means算法易受初始中心點的影響，不同的初始中心點，最終的聚類精度也會不同.由于篇幅限制，只給出K-means算法、K-means++算法和OFMMK-means算法在Iris數據集上的詳細情況，如表2所示，三種算法分別共運行了20次，并給出了每次運行時所選取的初始中心點(用其編號表示)、迭代次數、準確率和運行時間(單位為ms).

表2 三種算法在Iris測試數據集上的詳細結果Table 2 Results of the three algorithms on the Iris test data set

從表2中可以看出，K-means算法和K-means++算法的平均準確率分別是72.24%和75.94%，而OFMMK-means算法的平均準確率比K-means算法高了12.68%，比K-means++算法高了8.98%，達到84.92%.并且從20次的運行結果看，K-means算法和K-means++算法最壞情況下準確率是52.67%，最高是89.33%和90.03%，聚類結果非常不穩定.而OFMMK-means算法的20次運行結果都相對穩定，且最高準確率為91.67%.因此，從聚類精度上看，OFMMK-means算法具有較高的聚類精度和較好穩定程度.從運行時間上來看，OFMMK-means算法比其他兩種算法執行時間略高，是因為OFMMK-means算法在聚類前需要算出每個對象的離群因子，但是因為優化了初始中心的選擇，K-means算法和K-means++算法的平均迭代次數分別是6.7和5.6，OFMMK-means算法的平均迭代次數是5.1，OFMMK-means算法具有較小的迭代次數，從而20次運行時間的均值與其他兩種算法相差不多，不到1秒，基本相同.

5 結 論

針對K-means算法對初始中心點比較敏感且易受孤立點影響的缺陷，本文首先引入基于密度的離群點檢測算法，來消除孤立點對聚類結果的影響.其次，根據每個對象的離群因子的大小對樣本集進行升序排列，保證了中心點位于較前的位置，并產生候選初始中心點集，隨后根據最大最小算法，在候選初始中心點集中選取離群因子較小且相對距離較遠的數據對象作為初始中心點，跳出了K-means算法的隨機選擇策略，保證了聚類結果的穩定性.實驗表明，在時間基本相同的情況下，相對于K-means算法和K-means++算法，本文提出的算法OFMMK-means具有較高的聚類準確率和較好的穩定性，并且對于聚類的平均迭代次數，OFMMK-means算法的平均迭代次數也較小.因此，本文提出的聚類算法是有效的、可行的.