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

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

（1.長春理工大學　計算機科學技術學院，長春　130022；2.長春理工大學　電子信息工程學院，長春　130022）

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

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

（1.長春理工大學計算機科學技術學院，長春130022；2.長春理工大學電子信息工程學院，長春130022）

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

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

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

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

1　K-均值算法

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

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

定義目標準則函數(shù)為：

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

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

（1）隨機選取K個初始聚類中心V1，V2，..，Vk；

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

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

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

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

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

2.1算法原理

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

2.2相關概念

定義1 誤分類簇

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

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

定義2 處罰因子

定義3 加權距離

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

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

定義4 記憶因子

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

添加記憶因子后，第t次迭代時簇S的權值為：

本文使用公式（6）更新每個簇的權值。

定義5 加權準則函數(shù)

第t次迭代時，每個簇的權值為Wt1，Wt2，...，Wtk，定義的加權準則函數(shù)為：

若給定閾值ξ超過連續(xù)兩次加權準則函數(shù)值變化量，處罰聚類過程結束。

2.3加權處罰聚類過程偽代碼描述

3　仿真實驗結果分析

使用UCI數(shù)據(jù)集驗證算法的抗噪性能、聚類性能及伸縮性。分別使用聚類準確率和聚類誤差平方和，以及常用的Adjusted Rand Index參數(shù)作為評價指標，用來衡量數(shù)據(jù)的外部標準類和聚類結果之間的一致程度。

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

3.1UCI數(shù)據(jù)集實驗

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

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

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

從表1中可知，誤分類簇的判斷準確率均在86%以上。說明數(shù)據(jù)集X的真實最小簇間間距與本文設置的dmin之間的誤差較小，對判斷誤分類簇的準確率影響不大。表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聚類準確率比較結果看，在所有數(shù)據(jù)集上K-均值算法的聚類準確率均低于本文算法。雖然在數(shù)據(jù)集A5上K-Means++算法的聚類準確率略高于本文算法1，但是其它數(shù)據(jù)集上本文算法的聚類準確率均高于K-Means++算法。從Adjusted Rand Index參數(shù)的比較結果看，本文算法的聚類效果最好。

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

3.2人工模擬數(shù)據(jù)集實驗

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

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

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

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

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

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

4　結論

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

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

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

［3］ 張赤，豐洪才，金凱，等.基于聚類分析的缺失數(shù)據(jù)最近鄰填補算法［J］.計算機應用與軟件，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］ 韓忠明，陳妮，張慧，等.一種非對稱距離下的層次聚類算法［J］.模式識別與人工智能，2014，27（5）：410-416.

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

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

［8］ 楊志，羅可.一種改進的基于粒子群的聚類算法［J］.計算機應用研究，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］.太原理工大學學報，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