引入自檢策略的進化K－means算法

宋天勇，趙 輝，李萬龍，王 璐，田世元

（長春工業大學計算機科學與工程學院，吉林 長春 130012）

0 引言

隨著大數據時代的到來，人們越來越關注如何從海量數據中高效地提取更多的知識.聚類就是通過計算對象間的相似度，按照類間相似性小、類內相似性高智能的將待聚類集合劃分成若干簇［1－2］.聚類結果的準確度及劃分簇的可解釋性成為評價聚類算法的主要依據.聚類方法可分為劃分法、層次法、基于密度的方法及基于網格的方法等.其中基于劃分法中的K－means算法憑借其簡單、收斂速度快等優勢在工業中得到了廣泛的應用［3］，但K－means算法有2個主要缺陷：（1）K的個數需要用戶輸入；（2）局部最優問題，即K－means產生的解是局部最優解而非全局最優解.目前已有很多文獻已對K－means的缺陷進行了改進，例如：文獻［1－2］提出通過迭代的選取彼此距離最遠的點作為初始質心的方法；文獻［4－7］在聚類時考慮密度因素，通過在密度較大的區域選取合適的初始質心；文獻［8］提出將傳統K－means算法與智能算法相結合的改進算法；文獻［9］提出一種改進聚類準則函數的K－means算法；文獻［10］提出了計算效率較高的進化K－means聚類算法（Fast Evolutionary Algorithms for Clustering，F－EAC），提出對部分簇進行分裂來調整聚類效果；文獻［11－12］對F－EAC算法進行改進，提出基于一種全局性分裂算子的改進算法.F－EAC算法在分裂的過程中忽視了周邊簇對待分裂簇的影響，而王留正等只改進了分裂算子的選取，待分裂簇更新過于頻繁問題并未得到改善.針對這一問題，本文提出一種改進的進化K－means算法，通過在分裂完成后對分裂的結果進行評價來檢測是否需要重新計算待分裂簇，阻止錯誤的待分裂選取，從而得到更好的聚類結果.本文通過理論分析和實驗驗證了引入自檢策略的F－EAC算法相對于F－EAC算法具有較大的優越性.

1 進化K－means算法

1.1 K－means算法簡介

K－means在運行前要求用戶輸入聚類個數K，然后從待聚類集合Σ中隨機選取K個對象作為初始質心，通過迭代計算最終得到K個穩定的質心.傳統K－means中每個質心可代表一個簇，每一次迭代中要求計算Σ中全部點與K個質心的距離，Σ中的每個點被分配到與其最近的簇中.一輪劃分完畢后，根據劃分好的K個簇計算出新的K個質心，通過收斂準則函數是否收斂來判斷質心是否穩定，若穩定則聚類結束，否則繼續迭代.其聚類準則函數為

其中：P表示集合中的點；Ci代表第i個簇；dist（P，Ci）表示點P到簇Ci的質心的距離.

1.2 F－EAC算法簡介

F－EAC算法將變異與K－means強大的局部搜索能力相結合，通過適應度函數SP（Ci）評價簇的變異率，簇的適應度值越高其變異率就越低.在待分裂的簇中隨機選擇2個點作為分裂的基準，每次將待變異的簇分裂后通過執行K－means算法將變異的結果迅速穩定.F－EAC算法根據分裂的結果可以自適應調整K值，使聚類的結果更加合理.

設xi表示簇中的一個對象，則其適應度函數SS（xi）定義為

其中：a（xj）表示xj到其他簇質心的距離；b（xi）表示xi到其所屬簇質心距離；SS（xi）表示簇中對象xi的穩定度.整個簇的適應度記為f（Ci），即

其中｜Cj｜表示簇Cj中成員的數目.根據公式（3）簇的變異率

2 改進F－EAC算法

2.1 F－EAC算法中的問題

F－EAC算法優先考慮分裂穩定度最低的簇，通過隨機選取分裂算子將待分裂簇分裂，每次分裂都可能引發簇的變異率改變，使得整個聚類過程中任意2次分裂方向彼此相反.FEAC算法可能出現頻繁更換變異對象而導致分裂效果弱化，無法得到較好的聚類結果（如圖1所示）.類別C1和C4被劃分為同一個簇C7，簇C2、簇C3雖屬于同一類別卻被劃分為2個簇.由C1和C4組成的簇進行分裂，分裂后生成包含C3和C4的新簇C8.因為C3和C4之間相異度較大，C8的變異率將迅速升高，根據公式（4）可知，F－EAC算法將待變異簇更換成簇C8，但此時C7中仍有部分C4成員需要繼續分裂.F－EAC算法將每次分裂孤立起來，不能以更寬闊的視角處理整個分裂過程，在對于一個連貫的分裂中的過渡階段處理上存在缺陷.

圖1 類邊界相對模糊圖

2.2 改進F－EAC算法相關定義

定義1 d（a，b）表示a，b的歐式距離，計算公式為

其中ai表示點a在第i個屬性上的值.

定義2 設簇Ci為待分裂的簇，其分裂點記為m1和m2，分裂的方向點記為sf（Ci），即

其中：NC代表Ci的近鄰簇集合；｜NC｜代表近鄰簇的個數；Oj表示近鄰簇Cj的質心.對于?xk∈Ci，?m1和m2∈Ci，使得d（m1，sf（Ci））≤d（xk，sf（Ci）），且d（m1，m2）≥d（xk，m1）.

定義3 設第L輪Ci為待分裂簇，Ci分裂前質心為Oi（i＝1，2，…，k），記為Σf；Ci分裂后質心為O′i（i＝1，2，…，k），記為Σa；則評價函數EFL表示為

其中｜Σf｜表示集合Σf中成員的個數.若EFL＞1，第L＋1輪重新計算待分裂簇；否則，第L＋1輪待分裂簇仍為Ci.

2.3 改進F－EAC算法偽代碼

輸入：全局點集Σ，K 個初始中心Oi（i＝1，2，…，k）

輸出：K 個簇Ci（i＝1，2，…，k）

%loopMax為最大迭代次數，currentLoop為當前迭代次數

① 輸入loopMax，Oi（i＝1，2，…，k），全局點集Σ，currentLoop＝1；

② 對Σ中的每個對象進行 K－means聚類，生成K 個簇Ci（i＝1，2，…，k），質心分別為Oi（i＝1，2，…，k）；

③ 根據公式（4）計算SP（Ci）i（i＝1，2，…，k），取最大值的簇記為Dmax；

④ 依據定義2得到Dmax中的m1和m2及sf（Dmax）以m1和m2為基準將Dmax分裂，計算m2所在部分的質心Osplit，保存Osplit；

⑤ 以Oi（i＝1，2，…，k）為質心進行 K－means聚類，生成K′個簇Di（i＝1，2，…，k），質心分別為Oi′（i＝1，2，…，k）；

⑥ 若currentLoop＜loopMax，currentLoop＝currentLoop＋1，轉第⑦步；否則，輸出以O′i（i＝1，2，…，k）為質心的k個簇Ci（i＝1，2，…，k）；

%對分裂結果進行檢測

⑦ 據公式（7）計算EFL，若EFL＞1，轉第③步；否則，令Dmax＝Cspliti，轉第④步.

2.4 改進F－EAC算法分析

（1）類與類之間邊界明顯時，改進F－EAC算法將待分裂簇分裂后，由于類與類之間的區別較為明顯，待分裂簇分裂后其變異率迅速下降，在較短的時間內失去繼續分裂的意義（見圖2）.在圖2中，待分裂簇C1分裂后，簇C2將吸收一部分成員，簇C1的變異率迅速減小，說明簇C1在當前狀態下已穩定，失去分裂的意義；同理，簇C2分裂后變異率也迅速降低，保持穩定.

（2）類與類之間邊界不明顯時，聚類對象從需要分裂的狀態達到類間相異度較大、類內相異度較小的狀態所需的定向持續分裂次數較多.在質心調整過程中必然生成同時包含多個類別的簇，由于F－EAC算法強調對當前類間相異度小、類內相異度大的簇進行分裂，包含多個類別的簇就會成為下一個分裂對象，分裂就可能沿著反方向進行，分裂效果被削弱.如圖1中，類別C1和C4被劃分為同一個簇C7，簇C2、簇C3雖屬于同一類別卻被劃分為2個簇.由C1和C4組成的簇進行分裂，分裂后生成包含C3和C4的新簇C8.因為C3和C4之間相異度較大，C8的變異率將迅速升高，但由于簇C7成員間相異度較大，根據公式（4）簇C7的變異率仍高于其余3個簇，按照改進F－EAC算法偽代碼中的第⑦步，簇C7繼續分裂，這保證了正確的分裂的連續性.

圖2 類邊界相對明顯圖

3 實驗及分析

3.1 實驗描述

實驗機器配置：操作系統為Windows7；處理器為inter core i3－3110M，主頻2.4GHz；內存為4GB；開發平臺為matlab 2012a，myEclipse 8.5.實驗數據選自UCI公共測試數據集中的Iris數據集和Wine數據集，實驗中loopMax取值19，且對F－EAC和改進算法用相同的12組初始質心做測試.整個實驗過程包括2組實驗，在實驗（1）中在Iris數據集上的測試，在實驗（2）中采用Wine數據集作為測試對象.2組實驗結果表明，改進后的算法在聚類結果的穩定性及準確度上相對于F－EAC都有較大的提高（見表1和2）.

表1 Iris數據集上的實驗結果

表2 Wine數據集上的實驗結果

3.2 實驗分析

如表1所示，在實驗1中第1，2，4，6，8，10和12組初始質心分布較為合理，F－EAC算法在這7組初始質心上劃分的較為準確；第3，5，7，9和11組初始質心出現圖1中的問題，F－EAC算法會因為頻繁更換待分裂簇，導致分裂出現倒退現象，降低了聚類的準確度.本次實驗中F－EAC算法聚類結果的準確度在47%～92%之間波動；改進F－EAC在處理第3，5，7，9，11組初始質心時通過連續的分裂將存在于同一個類別內的2個質心間的距離加大，始終保證分裂對增大質心間距離的有效性，最終得到3個分布較為合理的簇，將聚類準確度提高到90%以上；當處理初始質心分布較為合理的第1，2，4，6，8，10，12組數據時仍將聚類準確度保持在90%以上，總體聚類準確度達到91.50%.

如表2所示，在實驗2中，F－EAC算法只在第8，10，11這三組初始質心上得到了較好的結果，其余9組數據都因為初始質心中2個質心存在于同一類別內而導致待變異簇的頻繁更換，分裂無法產生質變的效果；在處理全部的12組數據時改進F－EAC通過評價質心間距離是否被增大來判斷分裂是否合理，通過持續正確的分裂將最終聚類結果準確度保持在74.72%以上，平均準確度為74.86%，優于F－EAC的60.206%，說明改進F－EAC取得了相對不錯的聚類準確度.兩組實驗都說明改進后的算法相對于傳統算法在聚類結果的穩定性及準確度上都有較明顯的提高.

4 結論

F－EAC算法通過分裂引發變異而提高聚類質量，但選取分裂基準時存在隨機性，文獻［12］雖然在選擇分裂基準上對F－EAC算法進行了改進，但這種改進加強了分裂的指向性，在面對圖1中的問題時其性能將略遜于F－EAC算法.本文在首先利用K－means算法快速地使分裂的結果形成局部最優，通過對分裂前后評價函數評價此次分裂是否有利于產生更好的結果，只有當產生的分裂阻礙聚類質量提高的情況下才重新計算每個簇的變異率，能夠有效地控制待變異簇頻繁的更新.實驗結果表明，改進FEAC在保證算法產生的變異合理情況下能夠連續地沿著正確的變異方向進行分裂，在處理類與類之間重疊或需要多次定向分裂對象時具有較好的效果.

［1］LAI YU－XIA，LIU JIAN－PING.Optimization study on initial center of K－means algorithm［J］.Computer Engineering and Applications，2008，44（10）：147－149.

［2］仝雪姣，孟凡榮，王志曉.對 K－means初始聚類中心的優化［J］.計算機工程與設計，2011，32（8）：2721－2723.

［3］JAIN A K.Data clustering 50years beyond K－means［J］.Pattern Recognition Letters，2010，31（8）：651－666.

［4］張健沛，楊悅，楊靜，等.基于最優劃分的 K－means初始聚類中心選取算法［J］.系統仿真學報，2009，21（9）：2586－2590.

［5］牛琨，張舒博，陳俊.融合網格密度的聚類中心初始化方案［J］.北京郵電大學學報，2007，30（2）：6－10.

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

［7］韓凌波，王強，蔣正鋒，等.一種改進的 K－means初始聚類中心選取算法［J］.計算機工程與應用，2010，46（17）：150－152.

［8］陶新民，徐晶，楊立標，等.一種改進的粒子群和K 均值混合聚類算法［J］.電子信息學報，2011，32（1）：92－97.

［9］ZHANG XUE－FENG，ZHANG GUI－ZHEN，LIU PENG.Improved K－means algorithm based on clustering criterion function［J］.Computer Engineering and Applications，2011，47（11）：123－127.

［10］ALVES V，CAMPELLO R J G B，HRUSCHKA E R.Towards a fast evolutionary algorithm for clustering ［C］／／IEEE Congress on Evolutionary Computation.Washington，DC：IEEE Computer Society，2006：1776－1783.

［11］NALDI M C，CAMPELLO R J G B HRUSCHKA E R，et al.Efficiency issues of evolutionary K－means［J］.Applied Soft Computing，2011，11（2）：1938－1952.

［12］王留正，何振峰.基于全局性分裂算子的進 K－mean算法［J］.計算機應用，2012，32（11）：3005－3008.