基于處罰的K-均值優(yōu)化算法

谷欣超，梁鮮，曲福恒，才華，楊勇

（1.長(zhǎng)春理工大學(xué)　計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長(zhǎng)春　130022；2.長(zhǎng)春理工大學(xué)　電子信息工程學(xué)院，長(zhǎng)春　130022）

基于處罰的K-均值優(yōu)化算法

谷欣超1，梁鮮1，曲福恒1，才華2，楊勇1

（1.長(zhǎng)春理工大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長(zhǎng)春130022；2.長(zhǎng)春理工大學(xué)電子信息工程學(xué)院，長(zhǎng)春130022）

判斷聚類結(jié)果中是否存在誤分類的簇，即簇中包含的樣本不屬于同一類。若存在，則在已有聚類結(jié)果上使用加權(quán)方案，處罰誤分類的簇，輸出新的聚類結(jié)果。若不存在，則輸出已有聚類結(jié)果。限制簇集中存在誤分類的簇，消除初始聚類中心對(duì)K-均值算法的影響，提高聚類準(zhǔn)確率。實(shí)驗(yàn)結(jié)果表明，該算法與K-均值算法、優(yōu)化初始聚類中心的K-均值算法相比，在壞的初始化條件下，表現(xiàn)出更好的魯棒性；在含有噪音的數(shù)據(jù)集中，表現(xiàn)出更好的抗噪性能；聚類效果更好。

聚類算法；K-均值算法；初始聚類中心；聚簇

聚類分析是一種無(wú)監(jiān)督的機(jī)器學(xué)習(xí)算法［1-3］，根據(jù)數(shù)據(jù)的某種屬性的相似程度，將數(shù)據(jù)分類［4，5］，廣泛應(yīng)用于模式識(shí)別、數(shù)據(jù)挖掘、數(shù)據(jù)分析等研究領(lǐng)域。K-均值是聚類分析中的代表算法，算法簡(jiǎn)單，易于實(shí)現(xiàn)，但受初始聚類中心影響較大［6-10］。不同的初始聚類中心導(dǎo)致不同準(zhǔn)確率的聚類結(jié)果，易陷入局部最優(yōu)。當(dāng)數(shù)據(jù)集中存在噪音和孤立點(diǎn)時(shí)，現(xiàn)有方法很難選出合適的初始聚類中心。

K-均值算法將數(shù)據(jù)集劃分成誤差平方和大小不一的簇集，經(jīng)過(guò)分析，發(fā)現(xiàn)平方和較小的簇可抵消平方和較大的簇的影響，使整體的誤差平方和的累加和最小。在壞的初始化條件下，算法的聚類結(jié)果中會(huì)存在平均誤差較大的誤分類簇，即簇中包含的樣本屬于兩類以上，聚類結(jié)果偏離數(shù)據(jù)集的真實(shí)分布。為此，提出基于處罰的K-均值優(yōu)化算法。若判斷出聚類結(jié)果中存在誤分類簇，則使用加權(quán)方案進(jìn)行調(diào)整，得到新的準(zhǔn)確率更高的聚類結(jié)果。

1　K-均值算法

指定表示聚類個(gè)數(shù)K，聚類操作結(jié)束時(shí)，用包含聚類中心及樣本的類標(biāo)識(shí)表示聚類結(jié)果。設(shè)數(shù)據(jù)集為，K個(gè)聚類中心為V1，V2，..， Vk。令Cj（j=1，2，...，K）表示K個(gè)聚類的類別，則：

其中||Ci表示Ci類的樣本數(shù)量。

定義目標(biāo)準(zhǔn)則函數(shù)為：

表示每個(gè)數(shù)據(jù)對(duì)象到相應(yīng)聚類中心距離的平方和，即聚類均方誤差的最小值定義樣本間的相似性：

K-均值算法的流程如下：

（1）隨機(jī)選取K個(gè)初始聚類中心V1，V2，..，Vk；

（2）按照最小距離原則，對(duì)數(shù)據(jù)集聚類，確定每個(gè)樣本的類屬關(guān)系；

（3）使用公式（1）更新K個(gè)簇的中心；

（4）重復(fù)執(zhí)行（2）到（4），直到目標(biāo)準(zhǔn)則函數(shù)收斂或聚類中心穩(wěn)定。

初始聚類中心隨機(jī)產(chǎn)生，在壞的初始化條件下，聚類結(jié)果中因存在誤分類的簇，得到較低的聚類準(zhǔn)確率。即使更換初始聚類中心，聚類結(jié)果很難達(dá)到全局最優(yōu)。

2　基于處罰的K-均值優(yōu)化算法

2.1算法原理

首先分析K-均值算法的聚類結(jié)果，判斷是否存在誤分類的簇。若不存在，則輸出已有的聚類結(jié)果。若存在，則在已有聚類結(jié)果之上，根據(jù)各個(gè)簇的平均誤差的大小為其分配權(quán)值，再次進(jìn)行K-均值聚類算法。每次迭代過(guò)程中，分配較大的權(quán)值給平均誤差較大的簇，分配較小的權(quán)值給平均誤差較小的簇。使用定義的處罰因子，對(duì)簇的處罰力度進(jìn)行控制。定義新的加權(quán)準(zhǔn)則函數(shù)，在分配樣本時(shí)通過(guò)計(jì)算加權(quán)距離，把樣本歸屬到加權(quán)距離最小時(shí)所對(duì)應(yīng)的簇中。因此，使平均誤差較大的簇失去一些距離簇心比較遠(yuǎn)的樣本，進(jìn)而使不屬于該簇的樣本歸屬到正確的簇中。具有較小平均誤差的簇會(huì)獲得一些屬于該簇但是距離簇心較遠(yuǎn)的樣本。每次迭代對(duì)簇的權(quán)值進(jìn)行更新時(shí)，通過(guò)引入記憶因子的概念，使上次更新迭代的權(quán)值對(duì)當(dāng)前更新迭代的權(quán)值進(jìn)行控制，進(jìn)而對(duì)算法的穩(wěn)定性進(jìn)行改善。以期經(jīng)過(guò)處罰操作，能對(duì)數(shù)據(jù)集做出正確的劃分，得到高準(zhǔn)確率的聚類結(jié)果。

2.2相關(guān)概念

定義1 誤分類簇

K-均值算法的聚類結(jié)果中，最小簇間間距為dmin。把第i（i=1，2，…，K）個(gè)簇聚為兩類，簇間間距為d。若d≥dmin，則第i個(gè)簇為誤分類簇。

若第i個(gè)簇是誤分類簇，即簇中包含的樣本屬于兩類或兩類以上，把該簇聚為兩類時(shí)，簇間間距大于等于dmin。第i個(gè)簇不是誤分類簇，即簇中包含的樣本屬于同一類，把該簇聚為兩類時(shí)，簇間間距小于dmin。設(shè)dmin為數(shù)據(jù)集X的最小簇間間距，與數(shù)據(jù)集X的真實(shí)最小簇間間距之間會(huì)有少量誤差，因此會(huì)影響判斷誤分類簇的準(zhǔn)確率。通過(guò)實(shí)驗(yàn)證明該方法的優(yōu)越性大于局限性。

定義2 處罰因子

定義3 加權(quán)距離

若判斷出K-均值算法的聚類結(jié)果中存在誤分類的簇，則進(jìn)行加權(quán)處罰聚類過(guò)程。待聚類數(shù)據(jù)集，第t-1次迭代結(jié)束時(shí)，K個(gè)聚類中心為，K個(gè)簇的標(biāo)示分別為，第t次迭代，簇S的權(quán)值WtS為：

由定義1和2可知，若第t-1次迭代時(shí)，簇S的平均誤差越大。那么第t次迭代過(guò)程中，分配給簇S的權(quán)值就越大，給予簇S的處罰因子PtS也越大。通過(guò)增加處罰力度，使每個(gè)樣本都盡量劃分到合適的簇中。

定義4 記憶因子

為了提高算法的穩(wěn)定性，在權(quán)值更新過(guò)程中，添加記憶因子α（0≤α≤1），用于控制上次迭代的權(quán)值對(duì)當(dāng)前更新的權(quán)值的影響。

添加記憶因子后，第t次迭代時(shí)簇S的權(quán)值為：

本文使用公式（6）更新每個(gè)簇的權(quán)值。

定義5 加權(quán)準(zhǔn)則函數(shù)

第t次迭代時(shí)，每個(gè)簇的權(quán)值為Wt1，Wt2，...，Wtk，定義的加權(quán)準(zhǔn)則函數(shù)為：

若給定閾值ξ超過(guò)連續(xù)兩次加權(quán)準(zhǔn)則函數(shù)值變化量，處罰聚類過(guò)程結(jié)束。

2.3加權(quán)處罰聚類過(guò)程偽代碼描述

3　仿真實(shí)驗(yàn)結(jié)果分析

使用UCI數(shù)據(jù)集驗(yàn)證算法的抗噪性能、聚類性能及伸縮性。分別使用聚類準(zhǔn)確率和聚類誤差平方和，以及常用的Adjusted Rand Index參數(shù)作為評(píng)價(jià)指標(biāo)，用來(lái)衡量數(shù)據(jù)的外部標(biāo)準(zhǔn)類和聚類結(jié)果之間的一致程度。

實(shí)驗(yàn)環(huán)境是WindowsXP操作系統(tǒng)，Intel CPU，2.55G內(nèi)存，721G硬盤，使用VS2008編程工具。

3.1UCI數(shù)據(jù)集實(shí)驗(yàn)

測(cè)試算法的伸縮性及聚類性能，測(cè)試數(shù)據(jù)集描述如表1所示。首先測(cè)試本文算法判斷誤分類簇的準(zhǔn)確性。在測(cè)試數(shù)據(jù)集上分別100次運(yùn)行K-均值算法，使用本文算法對(duì)每次得到的聚類結(jié)果進(jìn)行判斷，統(tǒng)計(jì)判斷準(zhǔn)確率如表1最后一列所示。分別運(yùn)行本文算法1（α=0.1）、本文算法2（α=0.2）、本文算法3（α=0.3）、K-均值算法、K-Means++算法各100次，對(duì)平均聚類結(jié)果進(jìn)行比較。算法的聚類誤差平方和的比較結(jié)果如表2所示。算法的聚類準(zhǔn)確率與Adjusted Rand Index參數(shù)的比較結(jié)果如圖1所示。

表1　UCI數(shù)據(jù)集描述

表2　UCI數(shù)據(jù)集各算法的聚類誤差平方和的比較結(jié)果

從表1中可知，誤分類簇的判斷準(zhǔn)確率均在86%以上。說(shuō)明數(shù)據(jù)集X的真實(shí)最小簇間間距與本文設(shè)置的dmin之間的誤差較小，對(duì)判斷誤分類簇的準(zhǔn)確率影響不大。表2表明，在數(shù)據(jù)集A4、A5上，K-均值算法的聚類誤差平方和最優(yōu)，在數(shù)據(jù)集A4、A5上，本文算法的聚類誤差平方和明顯優(yōu)于K-均值算法。在數(shù)據(jù)集A5上，K-Means++算法的聚類誤差平方和最優(yōu)，在數(shù)據(jù)集A5上本文算法1的聚類誤差平方和稍低于K-Means++算法，但是本文算法2和本文算法3均優(yōu)于K-Means++算法。

從圖1聚類準(zhǔn)確率比較結(jié)果看，在所有數(shù)據(jù)集上K-均值算法的聚類準(zhǔn)確率均低于本文算法。雖然在數(shù)據(jù)集A5上K-Means++算法的聚類準(zhǔn)確率略高于本文算法1，但是其它數(shù)據(jù)集上本文算法的聚類準(zhǔn)確率均高于K-Means++算法。從Adjusted Rand Index參數(shù)的比較結(jié)果看，本文算法的聚類效果最好。

上述實(shí)驗(yàn)結(jié)果表明，本文算法提高了K-均值算法的聚類性能，優(yōu)化了算法的伸縮性，并且優(yōu)于優(yōu)化初試聚類中心的K-均值算法。

3.2人工模擬數(shù)據(jù)集實(shí)驗(yàn)

為了測(cè)試本文算法對(duì)含有噪音數(shù)據(jù)的聚類能力，隨機(jī)生成兩組分別含有10%、20%、30%噪音的符合正態(tài)分布的二維人工模擬數(shù)據(jù)集對(duì)算法進(jìn)行測(cè)試。第一組數(shù)據(jù)集包含4個(gè)類簇，樣本集的規(guī)模為800。該組數(shù)據(jù)集按噪音比例由小到大排列分別為D1、D2、D3。在該組數(shù)據(jù)集上，本文算法判斷誤分類簇的準(zhǔn)確率分別為92.7%、95.2%、88.5%。第二組數(shù)據(jù)集包含6個(gè)類簇，樣本集的規(guī)模為12000。該組數(shù)據(jù)集按噪音比例由小到大排列分別為S1、S2、S3。在該組數(shù)據(jù)集上，本文算法判斷誤分類簇的準(zhǔn)確率分別為96.3%、89.4%、94.7%。在6個(gè)人工模擬數(shù)據(jù)集上分別運(yùn)行本文算法1、本文算法2、本文算法3、K-均值算法、K-Means++算法各100次，比較平均聚類結(jié)果。表3給出了各算法聚類誤差平方和的比較結(jié)果。圖2是各算法聚類準(zhǔn)確率與Adjusted Rand Index參數(shù)的比較結(jié)果。

在含有不同比例噪音的人工模擬數(shù)據(jù)集上，本文算法判斷誤分類簇的準(zhǔn)確率均在88%以上。說(shuō)明在含有噪音的數(shù)據(jù)集上，本文算法判斷誤分類簇的有效性高于局限性。表3表明，在測(cè)試數(shù)據(jù)上，K-均值算法和K-Means++算法的聚類誤差平方和均高于本文算法。圖2表明，在測(cè)試數(shù)據(jù)集上，在聚類準(zhǔn)確率和Adjusted Rand Index參數(shù)方面本文算法的最優(yōu)。

從人工模擬數(shù)據(jù)集的實(shí)驗(yàn)測(cè)試結(jié)果可以看出，在含有噪音的數(shù)據(jù)集上，本文算法的聚類結(jié)果準(zhǔn)確率高且穩(wěn)定，證明本文算法的抗噪性能較強(qiáng)。

圖1　UCI數(shù)據(jù)集上算法的聚類準(zhǔn)確率與Adjusted Rand Index參數(shù)的比較

表3　人工模擬數(shù)據(jù)集上算法的聚類誤差平方和的比較結(jié)果

圖2　模擬數(shù)據(jù)集上算法的聚類準(zhǔn)確率與Adjusted Rand Index參數(shù)的比較

4　結(jié)論

K-均值算法因初始聚類中心的影響，易得到準(zhǔn)確率較低的聚類結(jié)果。為此，很多學(xué)者從不同角度對(duì)K-均值算法進(jìn)行改進(jìn)。本文提出基于處罰的K-均值優(yōu)化算法，對(duì)準(zhǔn)確率較低的聚類結(jié)果進(jìn)行加權(quán)處罰。以期提高劃分?jǐn)?shù)據(jù)集的準(zhǔn)確率，進(jìn)而得到全局最優(yōu)的聚類結(jié)果。由UCI數(shù)據(jù)集的實(shí)驗(yàn)測(cè)試與人工模擬數(shù)據(jù)集的實(shí)驗(yàn)測(cè)試表明，本文算法的聚類性能及伸縮性能較好，且抗噪性能較強(qiáng)。

［1］Han Jiawei，Kamber M.Data Mining：Concepts and Techniques［M］.Beijing：China Machine Press，2011：5-15.

［2］ 張俊溪，吳曉軍.一種新的基于進(jìn)化計(jì)算的聚類算法［J］.計(jì)算機(jī)工程與應(yīng)用，2011，4（24）：111-114.

［3］ 張赤，豐洪才，金凱，等.基于聚類分析的缺失數(shù)據(jù)最近鄰填補(bǔ)算法［J］.計(jì)算機(jī)應(yīng)用與軟件，2014，31（5）：282-284.

［4］ Yu H，Li Z，Yao N.Research on optimization method for K-Means clustering algorithm［J］.Journal of Chinese Computer Systems，2012，33（10）：2273-2277.

［5］ 韓忠明，陳妮，張慧，等.一種非對(duì)稱距離下的層次聚類算法［J］.模式識(shí)別與人工智能，2014，27（5）：410-416.

［6］ 黃德才，李曉暢.基于相對(duì)密度的混合屬性數(shù)據(jù)增量聚類算法［J］.控制與決策，2013，28（6）：815-822.

［7］ 傅德勝，周辰.基于密度的改進(jìn)K均值算法及實(shí)現(xiàn)［J］.計(jì)算機(jī)應(yīng)用，2011，31（2）：432-434.

［8］ 楊志，羅可.一種改進(jìn)的基于粒子群的聚類算法［J］.計(jì)算機(jī)應(yīng)用研究，2014，31（9）：2597-2600.

［9］OnodaT，SakaiM，YamadaS.Carefulseeding method based on independent components analysis forK-meansclustering［J］.JournalofEmerging Technologies in Web Intelligence，2012，4（1）：51-59.

［10］ 韓曉紅，胡彧.K-means聚類算法研究［J］.太原理工大學(xué)學(xué)報(bào)，2009，40（3）：236-239.

An Optimal K-Means Algorithm Based on Weighted Penalty

GU Xinchao1，LIANG Xian1，QU Fuheng1，CAI Hua2，YANG Yong1
（1.School of Computer Science and Technology，Changchun University of Science and Technology，Changchun 130022；2.School of Electronic and Information Engineering，Changchun University of Science and Technology，Changchun 130022）

Judge the misclassification clustering existence in the K-means algorithm clustering or not，that is to mean the samples contained in the clustering do not belong to the same class.If existence，then utilizes a weighting scheme on existing clustering results，penalty for misclassification clustering to get the new clustering results.If not，to output the existing clustering results.To limit the misclassification clustering in the set and eliminate the influence of the initial clustering center of K-means algorithm would assure the clustering accuracy be advanced.The experimental results show that the proposed method is more robust in the unsatisfactory initialization conditions，have more noise immunity in a noisy data set，and clustering more accuracy to compare with the K-means algorithm，the K-means algorithm of optimized the initial clustering center.

clustering algorithm；K-means algorithm；initial clustering center；cluster

TP391.41

A

1672-9870（2015）06-0103-05

2015-10-27

谷欣超（1976-），男，碩士，講師，E-mail：guxinchao@foxmail.com

楊勇（1970-），男，博士，教授，E-mail：yy@cust.edu.cn