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

（長春工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，吉林 長春 130012）

0 引言

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

1 進(jìn)化K－means算法

1.1 K－means算法簡介

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

其中：P表示集合中的點(diǎn)；Ci代表第i個(gè)簇；dist（P，Ci）表示點(diǎn)P到簇Ci的質(zhì)心的距離.

1.2 F－EAC算法簡介

F－EAC算法將變異與K－means強(qiáng)大的局部搜索能力相結(jié)合，通過適應(yīng)度函數(shù)SP（Ci）評價(jià)簇的變異率，簇的適應(yīng)度值越高其變異率就越低.在待分裂的簇中隨機(jī)選擇2個(gè)點(diǎn)作為分裂的基準(zhǔn)，每次將待變異的簇分裂后通過執(zhí)行K－means算法將變異的結(jié)果迅速穩(wěn)定.F－EAC算法根據(jù)分裂的結(jié)果可以自適應(yīng)調(diào)整K值，使聚類的結(jié)果更加合理.

設(shè)xi表示簇中的一個(gè)對象，則其適應(yīng)度函數(shù)SS（xi）定義為

其中：a（xj）表示xj到其他簇質(zhì)心的距離；b（xi）表示xi到其所屬簇質(zhì)心距離；SS（xi）表示簇中對象xi的穩(wěn)定度.整個(gè)簇的適應(yīng)度記為f（Ci），即

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

2 改進(jìn)F－EAC算法

2.1 F－EAC算法中的問題

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

圖1 類邊界相對模糊圖

2.2 改進(jìn)F－EAC算法相關(guān)定義

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

其中ai表示點(diǎn)a在第i個(gè)屬性上的值.

定義2 設(shè)簇Ci為待分裂的簇，其分裂點(diǎn)記為m1和m2，分裂的方向點(diǎn)記為sf（Ci），即

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

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

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

2.3 改進(jìn)F－EAC算法偽代碼

輸入：全局點(diǎn)集Σ，K 個(gè)初始中心Oi（i＝1，2，…，k）

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

%loopMax為最大迭代次數(shù)，currentLoop為當(dāng)前迭代次數(shù)

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

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

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

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

⑤ 以O(shè)i（i＝1，2，…，k）為質(zhì)心進(jìn)行 K－means聚類，生成K′個(gè)簇Di（i＝1，2，…，k），質(zhì)心分別為Oi′（i＝1，2，…，k）；

⑥ 若currentLoop＜loopMax，currentLoop＝currentLoop＋1，轉(zhuǎn)第⑦步；否則，輸出以O(shè)′i（i＝1，2，…，k）為質(zhì)心的k個(gè)簇Ci（i＝1，2，…，k）；

%對分裂結(jié)果進(jìn)行檢測

⑦ 據(jù)公式（7）計(jì)算EFL，若EFL＞1，轉(zhuǎn)第③步；否則，令Dmax＝Cspliti，轉(zhuǎn)第④步.

2.4 改進(jìn)F－EAC算法分析

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

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

圖2 類邊界相對明顯圖

3 實(shí)驗(yàn)及分析

3.1 實(shí)驗(yàn)描述

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

表1 Iris數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

表2 Wine數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

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

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

如表2所示，在實(shí)驗(yàn)2中，F(xiàn)－EAC算法只在第8，10，11這三組初始質(zhì)心上得到了較好的結(jié)果，其余9組數(shù)據(jù)都因?yàn)槌跏假|(zhì)心中2個(gè)質(zhì)心存在于同一類別內(nèi)而導(dǎo)致待變異簇的頻繁更換，分裂無法產(chǎn)生質(zhì)變的效果；在處理全部的12組數(shù)據(jù)時(shí)改進(jìn)F－EAC通過評價(jià)質(zhì)心間距離是否被增大來判斷分裂是否合理，通過持續(xù)正確的分裂將最終聚類結(jié)果準(zhǔn)確度保持在74.72%以上，平均準(zhǔn)確度為74.86%，優(yōu)于F－EAC的60.206%，說明改進(jìn)F－EAC取得了相對不錯的聚類準(zhǔn)確度.兩組實(shí)驗(yàn)都說明改進(jìn)后的算法相對于傳統(tǒng)算法在聚類結(jié)果的穩(wěn)定性及準(zhǔn)確度上都有較明顯的提高.

4 結(jié)論

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

［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初始聚類中心的優(yōu)化［J］.計(jì)算機(jī)工程與設(shè)計(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］張健沛，楊悅，楊靜，等.基于最優(yōu)劃分的 K－means初始聚類中心選取算法［J］.系統(tǒng)仿真學(xué)報(bào)，2009，21（9）：2586－2590.

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

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

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

［8］陶新民，徐晶，楊立標(biāo)，等.一種改進(jìn)的粒子群和K 均值混合聚類算法［J］.電子信息學(xué)報(bào)，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］王留正，何振峰.基于全局性分裂算子的進(jìn) K－mean算法［J］.計(jì)算機(jī)應(yīng)用，2012，32（11）：3005－3008.