亓 慧

（太原師范學院 計算機系，山西 太原030012）

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

則將樣本xi歸入工作集；

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

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

3 實驗結(jié)果及分析

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

首先采用傳統(tǒng)聚類方法進行聚類，聚類個數(shù)參數(shù)取3，得到的聚類結(jié)果如圖4所示.從圖中可以看出，采用傳統(tǒng)聚類方法時，分布在較大正態(tài)分布區(qū)域的樣本由于均勻效應(yīng)被聚為了其他類別，如圖中橢圓區(qū)域內(nèi)的多數(shù)樣本在構(gòu)造數(shù)據(jù)集時是屬于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)建模糊工作集，并對模糊工作集中的樣本進行了結(jié)合二次聚類進行了重新劃分，使得原本與A類聚類中心距離較大的樣本，通過衡量其與A類二次聚類后得到的子類中心距離，將其歸入距離較小的A類樣本的子類，最終正確歸入A類，有效避免了非平衡分布數(shù)據(jù)聚類問題中的均勻效應(yīng).

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

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

4 結(jié)束語

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

［1］鐘曉，馬少平，張鈸，等.數(shù)據(jù)挖掘綜述［J］.模式識別與人工智能，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］.軟件學報，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］.計算機工程與應(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］.計算機科學，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］.軟件學報，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］劉廣聰，黃婷婷，陳海南.改進的二分K均值聚類算法［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］.模式識別與人工智能，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.