多中心的非平衡K-均值聚類方法

亓 慧

（太原師范學(xué)院 計(jì)算機(jī)系，山西 太原030012）

0 引 言

隨著計(jì)算機(jī)技術(shù)和網(wǎng)絡(luò)技術(shù)的迅猛發(fā)展，現(xiàn)實(shí)世界中需要處理的數(shù)據(jù)越來越復(fù)雜，《Science》及《Nature》等雜志近年來都聚焦大數(shù)據(jù)處理問題.如何從大規(guī)模的復(fù)雜數(shù)據(jù)中挖掘到人類需要的重要信息，成為人工智能乃至信息學(xué)科的一個(gè)重要研究課題［1-4］.

作為一種最典型的數(shù)據(jù)挖掘任務(wù)，聚類已經(jīng)得到了許多研究人員的廣泛關(guān)注，并設(shè)計(jì)了多種針對(duì)不同類型數(shù)據(jù)的方法，如劃分聚類［5］、層次聚類［6］、密度聚類［7］、網(wǎng)格聚類［8］、概率聚類［9］和譜聚類［10］等.

在這些聚類方法中，K-均值聚類是一種最為經(jīng)典，使用最為廣泛的劃分聚類方法［11-14］.其本質(zhì)就是實(shí)現(xiàn)對(duì)數(shù)據(jù)的劃分，使得劃分后的數(shù)據(jù)類間的不相似度盡可能高，類內(nèi)的相似度盡可能高.但是，對(duì)于非平衡數(shù)據(jù)的聚類問題［15］，傳統(tǒng)K-均值聚類方法往往容易將分布在區(qū)域較大類中的部分樣本錯(cuò)誤地劃分到區(qū)域分布較小的類中，即在非平衡分布數(shù)據(jù)集上得到的聚類結(jié)果存在均勻效應(yīng).目前，已經(jīng)提出了一些解決非平衡數(shù)據(jù)聚類的改進(jìn)方法，如基于下采樣的非平衡聚類［16］、基于密度的非平衡聚類［17］、基于熵的非平衡聚類［18］、基于魯棒性的非平衡聚類［19］等方法，但這些方法往往是針對(duì)較為均衡的非平衡聚類或只有個(gè)別少數(shù)樣本（如噪聲問題）聚類問題的方法，對(duì)于傳統(tǒng)非平衡數(shù)據(jù)的聚類問題，依然缺乏有效的解決方法.

本文針對(duì)K-均值聚類中存在的均勻效應(yīng)現(xiàn)象，提出一種多中心的非平衡K-均值聚類方法，以消減非平衡分布數(shù)據(jù)聚類時(shí)產(chǎn)生的均勻效應(yīng).該方法通過對(duì)聚類結(jié)果中較大的類別進(jìn)行二次聚類的方式對(duì)處于聚類模糊邊界的樣本進(jìn)行劃分，減小聚類均勻效應(yīng).

1 傳統(tǒng)K-均值聚類及均勻效應(yīng)

式中：xpi表示樣本xi的第p個(gè)分量；cpj表示類心cj的第p個(gè)分量，新類心的更新如下

式中：xjq為第j類樣本集的第q個(gè)樣本；cj為第j類樣本集的類心；nj為第j類樣本集中包含的樣本個(gè)數(shù).反復(fù)循環(huán)迭代直到中心收斂為止.

但是，由于傳統(tǒng)K-均值聚類方法僅根據(jù)樣本與類中心的距離進(jìn)行聚類，對(duì)于非平衡分布數(shù)據(jù)的聚類問題，傳統(tǒng)K-均值聚類方法往往容易將分布在較大區(qū)域的類別的邊界附近樣本錯(cuò)誤地劃分到分布較小區(qū)域的類別當(dāng)中，導(dǎo)致非平衡分布樣本聚類過程產(chǎn)生均勻效應(yīng)，得到錯(cuò)誤的聚類結(jié)果.圖1中，樣本分布區(qū)域A明顯大于樣本分布區(qū)域B，從人類認(rèn)知角度，顯然聚為A區(qū)域樣本和B區(qū)域樣本更合適，但如果采用傳統(tǒng)K-均值聚類方法則容易導(dǎo)致部分A區(qū)域中的樣本錯(cuò)誤劃分到B區(qū)域所屬類別當(dāng)中，即產(chǎn)生均勻效應(yīng).本文通過引入多中心聚類的概念，構(gòu)建模糊工作集，對(duì)其區(qū)域內(nèi)樣本進(jìn)行二次聚類，通過衡量模糊工作集中聚類不確定樣本與各類別子聚類結(jié)果的關(guān)系，進(jìn)一步對(duì)其進(jìn)行正確劃分，得到更符合人類認(rèn)知的非平衡數(shù)據(jù)聚類結(jié)果.

圖1 非平衡分布數(shù)據(jù)聚類的均勻效應(yīng) Fig.1 The uniform effect of unbalanced data clustering

2 多中心的非平衡K-均值聚類算法

實(shí)際生活中，經(jīng)常會(huì)遇到大量非平衡數(shù)據(jù)的聚類問題，傳統(tǒng)K-均值聚類方法往往容易產(chǎn)生均勻效應(yīng)，導(dǎo)致較差的非平衡聚類結(jié)果.為解決這個(gè)問題，本文提出了一種多中心的非平衡K-均值聚類算法.該方法首先對(duì)整個(gè)樣本集進(jìn)行聚類，并選擇與聚類結(jié)果中任意兩個(gè)或兩個(gè)以上聚類中心距離相近的樣本構(gòu)成模糊工作集；然后對(duì)各聚類結(jié)果進(jìn)行二次聚類，得到聚類結(jié)果中各類的子類集合，同時(shí)根據(jù)工作集中樣本與每個(gè)類中最近子類中心的距離關(guān)系，對(duì)模糊工作集中的樣本進(jìn)行二次歸類，有效避免了傳統(tǒng)K-均值聚類方法處理非平衡數(shù)據(jù)聚類時(shí)產(chǎn)生的均勻效應(yīng)問題.

多中心的非平衡K-均值聚類方法示意圖如圖2所示.圖中，從人的認(rèn)知的角度講，該訓(xùn)練集應(yīng)該聚為A區(qū)域樣本和B區(qū)域樣本兩類，且A區(qū)域中的樣本x應(yīng)該屬于A類，但由于A區(qū)域較大，其邊界樣本x與A類中心的距離要大于與B類中心的距離，因此傳統(tǒng)K-均值聚類方法錯(cuò)誤地將樣本x劃分到B類，產(chǎn)生了非平衡數(shù)據(jù)聚類的均勻效應(yīng).而本文提出的MC＿IK方法在傳統(tǒng)K-均值聚類基礎(chǔ)上，選擇邊界附近類似樣本x這種類別最不確定的樣本構(gòu)成模糊工作集，并對(duì)聚類結(jié)果中的每類數(shù)據(jù)分別進(jìn)行二次聚類，此時(shí)，如果A類樣本中存在一個(gè)子類中心cA，使得樣本x與A類中最相似的子類類心cA的距離就有可能小于B類中最相似的子類類心cB的距離，此時(shí)就將樣本的歸屬由B類校正成為A類.

圖2 多中心的非平衡K-均值聚類 Fig.2 Imbalanced K-means clustering with multiple centers

具體地，多中心的非平衡K-均值聚類算法執(zhí)行過程如下.

初始化：假設(shè)樣本集合為X=｛xi｝ni=1，初始聚類參數(shù)為k（0），多中心化子類參數(shù)為k，工作集選擇參數(shù)為δ.

Step 1：對(duì)樣本集X進(jìn)行初始標(biāo)準(zhǔn)K-均值聚類，得到初始聚類劃分結(jié)果

Step 2：構(gòu)造模糊工作集.對(duì)于任意一個(gè)樣本xi，如果存在至少兩個(gè)類Xs與Xt，且它們的類心cs和ct與該樣本的距離符合如下關(guān)系：

則將樣本xi歸入工作集；

Step 3：構(gòu)造多中心類別.對(duì)Step 1得到的聚類結(jié)果中的每個(gè)類Xj并行執(zhí)行Step 1的聚類方法（聚類參數(shù)為多中心化子類參數(shù)k）聚為k個(gè)子類，即得到二次聚類結(jié)果

Step 4：對(duì)模糊工作集中的每個(gè)樣本xi，重新判斷其與每個(gè)子類X2jp（j=1，…，k0；p=1，…，k）的類中心距離，并將樣本xi歸入距離最小的中心所屬類別Xj中；

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

本文與傳統(tǒng)K-均值聚類方法進(jìn)行了對(duì)比.實(shí)驗(yàn)構(gòu)造了非平衡正態(tài)分布的聚類數(shù)據(jù)集，三個(gè)分布中心依次分別為（2，2），（2，-2），（0，0），協(xié)方差矩陣依次分別為和且每類數(shù)據(jù)集的規(guī)模均為100，共300個(gè)，數(shù)據(jù)集分布如圖3所示.初始聚類參數(shù)直接設(shè)置為3，多中心化子類參數(shù)設(shè)置為5.圖中橢圓區(qū)域內(nèi)的樣本為需要關(guān)注的邊界樣本.

首先采用傳統(tǒng)聚類方法進(jìn)行聚類，聚類個(gè)數(shù)參數(shù)取3，得到的聚類結(jié)果如圖4所示.從圖中可以看出，采用傳統(tǒng)聚類方法時(shí)，分布在較大正態(tài)分布區(qū)域的樣本由于均勻效應(yīng)被聚為了其他類別，如圖中橢圓區(qū)域內(nèi)的多數(shù)樣本在構(gòu)造數(shù)據(jù)集時(shí)是屬于A類，而采用傳統(tǒng)K-均值聚類方法使得大多數(shù)數(shù)據(jù)集都聚為了B和C類，即發(fā)生了聚類的均勻效應(yīng).

圖4 傳統(tǒng)聚類方法得到的聚類結(jié)果 Fig.4 Clustering results of traditional clustering method

采用本文提出的多中心非平衡K-均值聚類方法得到的聚類結(jié)果如圖5所示.可以看出，由于通過構(gòu)建模糊工作集，并對(duì)模糊工作集中的樣本進(jìn)行了結(jié)合二次聚類進(jìn)行了重新劃分，使得原本與A類聚類中心距離較大的樣本，通過衡量其與A類二次聚類后得到的子類中心距離，將其歸入距離較小的A類樣本的子類，最終正確歸入A類，有效避免了非平衡分布數(shù)據(jù)聚類問題中的均勻效應(yīng).

圖5 MC＿IK方法聚類結(jié)果圖 Fig.5 Clustering result figure of MC＿IK method

綜上可看出，本文提出的多中心的非平衡K-均值聚類方法通過提取聚類邊界樣本構(gòu)建模糊工作集，然后對(duì)聚類結(jié)果進(jìn)行二次聚類，即得到每個(gè)類的子類，通過比較模糊工作集中樣本與各類別子類中心的距離，以對(duì)模糊工作集中的樣本進(jìn)行正確分類，使聚類結(jié)果受樣本不均衡分布的影響減弱，減小了非平衡聚類的均勻效應(yīng)，能有效處理非平衡數(shù)據(jù)聚類問題.

4 結(jié)束語

針對(duì)傳統(tǒng)K-均值聚類方法解決非平衡分布數(shù)據(jù)聚類任務(wù)時(shí)產(chǎn)生均勻效應(yīng)的問題，本文提出一種多中心的非平衡K-均值聚類方法，消減非平衡數(shù)據(jù)聚類的均勻效應(yīng).該方法首先對(duì)整個(gè)樣本集進(jìn)行聚類，產(chǎn)生初始聚類結(jié)果，并選擇與初始聚類結(jié)果中任意兩個(gè)或兩個(gè)以上聚類中心距離同時(shí)較近的類別模糊樣本構(gòu)成模糊工作集，然后對(duì)聚類結(jié)果中各類別分別進(jìn)行二次聚類，得到二次聚類的子聚類結(jié)果，即獲得各類的子類集合，同時(shí)根據(jù)模糊工作集中的樣本與各子類中心的相似性，對(duì)工作集中的樣本進(jìn)行二次歸類，從而消減模糊工作集中樣本聚類的錯(cuò)誤，有效避免了非平衡聚類的均勻效應(yīng).在未來的工作中，將進(jìn)一步結(jié)合其他非平衡數(shù)據(jù)處理方法，提高M(jìn)C＿IK方法處理非平衡聚類問題的性能，并將其應(yīng)用到網(wǎng)絡(luò)入侵檢測(cè)、疾病檢驗(yàn)等實(shí)際非平衡聚類應(yīng)用問題當(dāng)中.

［1］鐘曉，馬少平，張鈸，等.數(shù)據(jù)挖掘綜述［J］.模式識(shí)別與人工智能，2001，14（1）：48-55.Zhong Xiao，Ma Shaoping，Zhang Bo，et al.Summary of data mining［J］.Pattern Recognition and Artificial Intelligence，2001，14（1）：48-55.（in Chinese）

［2］Deufemia V，Risi M，Tortora G.Sketached symbol recognition using latent-dynamic conditional random fields and distance-based clustering［J］.Pattern Recognition，2014，47（3）：1159-1171.

［3］Portela N M，Cavalcanti G，Ren T I.Semi-supervised clustering for MR brain image segmentation［J］.Expert Systems with Applications，2014，41（4）：1492-1497.

［4］Voevodski K，Balcan M F，Roglin H，et al.Active clustering of biological sequences［J］.Journal of Machine Learning Research，2012，13，203-225.

［5］張敏，于劍.基于劃分的模糊聚類算法［J］.軟件學(xué)報(bào)，2004，15（6）：858-868.Zhang Min，Yu Jian.Fuzzy partitional clustering algorithms［J］.Journal of Software，2004，15（6）：858-868.（in Chinese）

［6］Rudi L.A fast quartet tree heuristic for hierarchical clustering［J］.Pattern Recognition，2011，44（3）：662-677.

［7］陳昊，侯慧群，楊承志，等.SA-BFSN：一種自適應(yīng)基于密度聚類的算法［J］.計(jì)算機(jī)工程與應(yīng)用，2012，48（36）：186-189.Chen Hao，Hou Huiqun，Yang Chengzhi，et al.SABFSN：adaptive algorithm based on density clustering［J］.Computer Engineering and Applications，2012，48（36）：186-189.（in Chinese）

［8］Su M C，Chou C H.A modified version of the k-means algorithm with distance based on cluster symmetry［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2001，23（6）：674-680.

［9］許華杰，李國徽，楊兵，等.基于密度的不確定性數(shù)據(jù)概率聚類［J］.計(jì)算機(jī)科學(xué)，2009，36（5）：68-71.Xu Huajie，Li Guohui，Yang Bing，et al.Probabilistic density-based clustering of uncertain data［J］.Computer Science，2009，36（5）：68-71.（in Chinese）

［10］王玲，薄列峰，焦李成.密度敏感的半監(jiān)督譜聚類［J］.軟件學(xué)報(bào)，2007，18（10）：2412-2422.Wang Ling，Bo Liefeng，Jiao Licheng.Density-sensitive semi-supervised spectral clustering［J］.Journal of Software，2007，18（10）：2412-2422.（in Chinese）

［11］Celebi M E，Kingravi H A，Vela P A.A comparative study of efficient initialization methods for the kmeans clustering algorithm［J］.Expert Systems with Applications，2013，40（1）：200-210.

［12］Elkan C.Using the triangle inequality to accelerate kmeans［C］.Proceedings of the Twentieth International Conference on Machine Learning（ICML2003），Menlo Park，AAAI Press，2003：147-153.

［13］劉廣聰，黃婷婷，陳海南.改進(jìn)的二分K均值聚類算法［J］.計(jì)算機(jī)應(yīng)用與軟件，2015，32（2）：261-263，277.Liu Guangcong，Huang Tingting，Chen Hainan.Improved bisecting k-means clustering algorithm［J］.Computer Applications and Software，2015，32（2）：261-263，277.（in Chinese）

［14］Vinnikov A，Shai Shalev-Shwartz.K-means recovers ICA filters when independent components are sparse［C］.Proceedings of the 31st International Conference on Machine Learning.Beijing，China，2014：712-720.

［15］陳思，郭躬德，陳黎飛.基于聚類融合的不平衡數(shù)據(jù)分類方法［J］.模式識(shí)別與人工智能，2010（6）：772-780.Chen Si，Guo Gongde，Chen Lifei.Clustering ensembles based classification method for imbalanced data sets［J］.Pattern Recognition and Artificial Intelligence，2010（6）：772-780.（in Chinese）

［16］Yen S J，Lee Y S.Cluster-based under-sampling approaches for imbalanced data distributions［J］.Expert Systems with Applications，2009，36（3）：5718-5727.

［17］Ester M，Kriegel H P，Sander J，et al.A densitybased algorithm for discovering clusters in large spatial datasets with noise［C］.Proceedings of the 2nd International Conference on ACM Special Interest Group Knowledge Discovery Data Mining，1996：226-231.

［18］Jing L P，Ng M K，Huang Z X.An entropy weighting k-means algorithm for subspace clustering of high-dimensional sparse data［J］.IEEE Transactions on Knowledge Data Engineering，2007，19（8）：1026-1041.

［19］Zhang J S，Leung Y W.Robust clustering by pruning outliers［J］.IEEE Transactions on Systems，Man and Cybernetics B，2003，33（6）：983-998.