武 森，汪玉枝，高曉楠

北京科技大學(xué)經(jīng)濟(jì)管理學(xué)院，北京 100083?通信作者，E-mail: gaoxiaonan0001@163.com

聚類(lèi)分析是數(shù)據(jù)挖掘領(lǐng)域最為常見(jiàn)的技術(shù)之一，用于發(fā)現(xiàn)數(shù)據(jù)集中未知的對(duì)象類(lèi)[1]. 聚類(lèi)分析在客戶(hù)細(xì)分[2]、模式識(shí)別[3]、醫(yī)療決策[4]、異常檢測(cè)[5]等諸多領(lǐng)域有著廣泛的應(yīng)用前景. 傳統(tǒng)的聚類(lèi)算法能夠很好地處理均衡數(shù)據(jù)的聚類(lèi)問(wèn)題，但是現(xiàn)實(shí)生活中存在許多不均衡數(shù)據(jù)，例如醫(yī)療診斷[6]、故障診斷[7]等領(lǐng)域的數(shù)據(jù)中表現(xiàn)正常的數(shù)據(jù)量要遠(yuǎn)遠(yuǎn)大于表現(xiàn)異常的數(shù)據(jù)量. 這類(lèi)不均衡數(shù)據(jù)集的特點(diǎn)是同一數(shù)據(jù)集中歸屬于某一類(lèi)別的數(shù)據(jù)對(duì)象的數(shù)量和密度與其他類(lèi)別數(shù)據(jù)對(duì)象的數(shù)量和密度有較大差異，通常數(shù)據(jù)對(duì)象數(shù)量較多的類(lèi)稱(chēng)之為大類(lèi)，數(shù)據(jù)對(duì)象數(shù)量較少的類(lèi)稱(chēng)之為小類(lèi). 對(duì)于不均衡數(shù)據(jù)的聚類(lèi)問(wèn)題，傳統(tǒng)的聚類(lèi)算法處理能力較弱. 以著名的 K–means算法為例，K–means算法是經(jīng)典的劃分式聚類(lèi)算法，在處理不均衡數(shù)據(jù)集時(shí)，容易出現(xiàn)“均勻效應(yīng)”[8]，即聚類(lèi)時(shí)往往會(huì)產(chǎn)生相對(duì)均勻尺寸的類(lèi)，小類(lèi)中的數(shù)據(jù)對(duì)象會(huì)“吞掉”大類(lèi)中的部分?jǐn)?shù)據(jù)對(duì)象，造成聚類(lèi)結(jié)果中不同類(lèi)的數(shù)據(jù)對(duì)象數(shù)量和密度趨于一致.

為解決不均衡數(shù)據(jù)的聚類(lèi)問(wèn)題，研究者從不同角度提出了多種方法，大致可以分成以下三類(lèi)：（1）數(shù)據(jù)預(yù)處理[9?12]；（2）多中心點(diǎn)[13?14]；（3）優(yōu)化目標(biāo)函數(shù)[15?16]. 第一類(lèi)方法是數(shù)據(jù)預(yù)處理，此類(lèi)方法對(duì)數(shù)據(jù)集進(jìn)行欠采樣和過(guò)采樣處理后再進(jìn)行聚類(lèi)，但是欠采樣方法僅僅采用了屬于大類(lèi)中的一部分具有代表性的子集，導(dǎo)致大類(lèi)中大量的有效信息被忽略，影響了聚類(lèi)效果[17]；過(guò)采樣方法通過(guò)增加小類(lèi)中對(duì)象數(shù)量來(lái)進(jìn)行數(shù)據(jù)分析，使原有數(shù)據(jù)集達(dá)到均衡狀態(tài)，但是這樣做一方面可能導(dǎo)致過(guò)擬合，另一方面也可能給數(shù)據(jù)集帶來(lái)噪聲. 第二類(lèi)方法是多中心點(diǎn)的方法，此類(lèi)方法基于多中心的角度解決K–means的“均勻效應(yīng)”問(wèn)題，其思想是用多個(gè)類(lèi)中心代替單個(gè)類(lèi)中心代表一個(gè)類(lèi)，在某些情況下，借助該思想，K–means算法在迭代過(guò)程中根據(jù)距離“中心”最近的原則，能夠讓部分被錯(cuò)分到小類(lèi)中的數(shù)據(jù)對(duì)象校正回大類(lèi)中. 如亓慧提出了一種多中心的不均衡K_均值聚類(lèi)方法(MC_IK)[14]，具有一定的有效性和可行性. 但此類(lèi)方法對(duì)于一些大類(lèi)分布極其不均勻的不均衡數(shù)據(jù)聚類(lèi)問(wèn)題，不能全面地反映數(shù)據(jù)分布特征，導(dǎo)致算法的有效性降低. 第三類(lèi)方法是優(yōu)化目標(biāo)函數(shù)的方法，此類(lèi)方法從目標(biāo)函數(shù)優(yōu)化的角度提出新的算法，通過(guò)推導(dǎo)出相應(yīng)的聚類(lèi)優(yōu)化目標(biāo)函數(shù)，以解決“均勻效應(yīng)”問(wèn)題. 如楊天鵬通過(guò)優(yōu)化數(shù)據(jù)離散程度進(jìn)而優(yōu)化目標(biāo)函數(shù)，提出了一種基于變異系數(shù)的聚類(lèi)算法（CVCN）[15]. 這類(lèi)方法從目標(biāo)函數(shù)直接切入，相比于之前的聚類(lèi)算法是一種較為直接的新方法且有一定的實(shí)用性，但是此類(lèi)方法一般涉及目標(biāo)函數(shù)參數(shù)的求解，屬于非線性函數(shù)優(yōu)化問(wèn)題，難以得到全局最優(yōu)解，這決定了該類(lèi)算法的聚類(lèi)結(jié)果具有相對(duì)較大的隨機(jī)性，影響算法的聚類(lèi)精度.

針對(duì)上述問(wèn)題，本文借助近鄰思想，提出基于近鄰的不均衡數(shù)據(jù)聚類(lèi)算法（CABON）. 首先運(yùn)用K–means算法對(duì)數(shù)據(jù)對(duì)象進(jìn)行初始聚類(lèi)，針對(duì)聚類(lèi)結(jié)果中部分?jǐn)?shù)據(jù)對(duì)象類(lèi)別可能劃分錯(cuò)誤的問(wèn)題，從數(shù)據(jù)對(duì)象與其最近的兩個(gè)類(lèi)中心距離差值的計(jì)算出發(fā)，給出了類(lèi)別待定集的定義及構(gòu)造規(guī)則，用以確定初始聚類(lèi)結(jié)果中類(lèi)別歸屬有待進(jìn)一步核定的數(shù)據(jù)對(duì)象集合. 其次針對(duì)類(lèi)別待定集中數(shù)據(jù)對(duì)象所屬類(lèi)別的重新劃分問(wèn)題，提出了一種新的類(lèi)的劃分規(guī)則，通過(guò)查找類(lèi)別待定集中每個(gè)數(shù)據(jù)對(duì)象的最近鄰居，借助近鄰思想，將類(lèi)別待定集的數(shù)據(jù)對(duì)象按照從集合邊緣到中心的順序依次歸入其最近鄰居所在的類(lèi)別中，能夠?qū)⒊醮尉垲?lèi)結(jié)果中類(lèi)別錯(cuò)分的數(shù)據(jù)對(duì)象校正回正確的類(lèi)，并且定義了一種類(lèi)別待定集的動(dòng)態(tài)調(diào)整機(jī)制，提高數(shù)據(jù)對(duì)象類(lèi)別劃分的準(zhǔn)確率，從而進(jìn)一步消減K–means算法的“均勻效應(yīng)”，得到最終的聚類(lèi)結(jié)果.

1 相關(guān)概念與規(guī)則

1.1 K–means算法的“均勻效應(yīng)”

K–means算法是劃分式聚類(lèi)的經(jīng)典算法，在K–means算法迭代過(guò)程中，采用一個(gè)類(lèi)中所有對(duì)象的平均值作為該類(lèi)新的中心，然后根據(jù)距離“中心”最近原則，重新確定所有對(duì)象的類(lèi)別，這會(huì)導(dǎo)致K–means算法在處理不均衡數(shù)據(jù)集時(shí)，出現(xiàn)部分?jǐn)?shù)據(jù)對(duì)象與多個(gè)類(lèi)中心距離相近的情況，從而導(dǎo)致這部分的數(shù)據(jù)對(duì)象歸屬類(lèi)別被錯(cuò)分. 文獻(xiàn)[8]介紹了K–means算法的“均勻效應(yīng)”，即K–means習(xí)慣于將大類(lèi)中的部分對(duì)象劃分到小類(lèi)中，從而使獲得的類(lèi)擁有相對(duì)均勻的尺度. 如圖1（a）所示，展示了一個(gè)由Python人工合成的二維不均衡數(shù)據(jù)集的真實(shí)分布，兩個(gè)類(lèi)的數(shù)據(jù)對(duì)象的數(shù)量和密度有較大差別；圖 1（b）為 K–means算法對(duì)圖 1（a）中數(shù)據(jù)集的聚類(lèi)結(jié)果，可以看到，聚類(lèi)后小類(lèi)“吞掉”了大類(lèi)中的部分?jǐn)?shù)據(jù)對(duì)象，使得兩個(gè)類(lèi)的數(shù)據(jù)對(duì)象的數(shù)量和密度趨于相近，此為K–means算法所產(chǎn)生的“均勻效應(yīng)”現(xiàn)象. 從類(lèi)中心的角度來(lái)說(shuō)，因?yàn)閱蝹€(gè)類(lèi)中心不能充分反映一個(gè)大類(lèi)的特征，導(dǎo)致大類(lèi)中的部分?jǐn)?shù)據(jù)對(duì)象被劃分到小類(lèi)中[18]. 在K–means算法迭代過(guò)程中，當(dāng)大類(lèi)中心與小類(lèi)中心的距離越來(lái)越近，大類(lèi)中的部分對(duì)象極易被錯(cuò)分到小類(lèi)中，最終的聚類(lèi)結(jié)果產(chǎn)生的“均勻效應(yīng)”就越顯著.

圖1 二維不均衡數(shù)據(jù)集的真實(shí)分布和 K–means的聚類(lèi)結(jié)果. （a）數(shù)據(jù)集真實(shí)分布；（b） K–means的聚類(lèi)結(jié)果Fig.1 Real distributions of two-dimensional unbalanced data sets and clustering results of the K–means algorithm: (a) real distribution of datasets; (b) the clustering result of the K–means algorithm

圖2 MC_IK算法中模糊工作集構(gòu)造規(guī)則存在缺陷示意圖. （a）數(shù)據(jù)集真實(shí)分布；（b）MC_IK對(duì)數(shù)據(jù)集初次聚類(lèi)結(jié)果Fig.2 Schematic diagram of the defects in the construction rules of the MC_IK algorithm’s fuzzy working set: (a) real distribution of data sets; (b) initial clustering result of the MC_IK algorithm on datasets

1.2 類(lèi)別待定集

類(lèi)別待定集是數(shù)據(jù)集中所屬類(lèi)別有待進(jìn)一步核定的數(shù)據(jù)對(duì)象構(gòu)成的集合，對(duì)應(yīng)地，數(shù)據(jù)集中所屬類(lèi)別確定的數(shù)據(jù)對(duì)象構(gòu)成的集合稱(chēng)之為類(lèi)別確定集. 在CABON算法中，首先運(yùn)用K–means對(duì)數(shù)據(jù)對(duì)象進(jìn)行聚類(lèi)，得到初始聚類(lèi)結(jié)果. 由于傳統(tǒng)的K–means算法不能很好地處理不均衡數(shù)據(jù)的聚類(lèi)問(wèn)題，因此在初始聚類(lèi)結(jié)果中會(huì)造成部分?jǐn)?shù)據(jù)對(duì)象在算法迭代過(guò)程中與多個(gè)類(lèi)中心距離都較為相近，以至于無(wú)法準(zhǔn)確確定其類(lèi)別，出現(xiàn)類(lèi)別錯(cuò)分的情況.基于此，本文定義了一種構(gòu)造規(guī)則來(lái)確定類(lèi)別待定集，并進(jìn)一步提出一種新的類(lèi)的劃分規(guī)則實(shí)現(xiàn)對(duì)類(lèi)別待定集中數(shù)據(jù)對(duì)象的重新劃分，得到最終聚類(lèi)結(jié)果，從而處理不均衡數(shù)據(jù)的“均勻效應(yīng)”問(wèn)題.

已有研究MC_IK算法提出過(guò)一種模糊工作集的定義：對(duì)于任意一個(gè)數(shù)據(jù)對(duì)象，若與初次聚類(lèi)結(jié)果中任意兩類(lèi)或兩類(lèi)以上的類(lèi)中心距離差小于預(yù)設(shè)閾值，則將此數(shù)據(jù)對(duì)象歸入模糊工作集[14]. 但是，這種構(gòu)造方法可能將普通數(shù)據(jù)對(duì)象劃歸到模糊工作集中，存在模糊工作集構(gòu)造不精準(zhǔn)的缺點(diǎn)，影響算法的聚類(lèi)效果. 如圖2（a）所示，三角形、圓圈、正方形和四角星分別代表了四種類(lèi)別，其類(lèi)中心分別是c1、c2、c3、c4，圖 2（b）是圖 2（a）中數(shù)據(jù)集的初次聚類(lèi)結(jié)果，可以看到，Cluster 1和Cluster 2之間發(fā)生了“均勻效應(yīng)”. 對(duì)于對(duì)象x1，根據(jù)MC_IK算法定義的模糊工作集的構(gòu)造規(guī)則，其與初次聚類(lèi)結(jié)果中類(lèi)中心c3、c4的距離差值最小，若此距離差值小于預(yù)設(shè)閾值可將數(shù)據(jù)對(duì)象x1歸入模糊工作集. 但實(shí)際上對(duì)象x1與初次聚類(lèi)結(jié)果中最近的兩個(gè)類(lèi)中心為c1、c2，且距離c1、c2的距離差值較大，這種情況下可以把對(duì)象x1直接歸入距離最近的類(lèi)別c2中，不屬于模糊工作集. 因此，MC_IK算法定義的構(gòu)造規(guī)則會(huì)導(dǎo)致部分對(duì)象被誤分到模糊工作集，影響算法的聚類(lèi)效果.

因此，在MC_IK算法定義的模糊工作集的基礎(chǔ)上，本文將數(shù)據(jù)集中所屬類(lèi)別有待進(jìn)一步核定的數(shù)據(jù)對(duì)象構(gòu)成的集合定義為類(lèi)別待定集，構(gòu)造規(guī)則為：使用K–means算法對(duì)數(shù)據(jù)對(duì)象進(jìn)行聚類(lèi)得到初始聚類(lèi)結(jié)果后，對(duì)于任意一個(gè)數(shù)據(jù)對(duì)象，若與初始聚類(lèi)結(jié)果中最近的兩個(gè)類(lèi)中心距離差小于預(yù)設(shè)閾值δ（即類(lèi)別待定集構(gòu)造閾值），則將此數(shù)據(jù)對(duì)象歸入類(lèi)別待定集. 圖 3（a）為用 K–means算法對(duì)原始數(shù)據(jù)對(duì)象聚類(lèi)得到的初始聚類(lèi)結(jié)果，產(chǎn)生了“均勻效應(yīng)”；圖3（b）根據(jù)本文定義的構(gòu)造規(guī)則確定了類(lèi)別待定集，虛線內(nèi)數(shù)據(jù)對(duì)象距離最近的兩個(gè)類(lèi)中心距離差小于預(yù)設(shè)閾值δ，構(gòu)成了類(lèi)別待定集. 相比于MC_IK算法中定義的模糊工作集，本文提出的類(lèi)別待定集構(gòu)造方法可以有效避免歸屬類(lèi)別確定的數(shù)據(jù)對(duì)象被錯(cuò)分到類(lèi)別模糊不確定的集合里的情形，能夠準(zhǔn)確識(shí)別可能被錯(cuò)分的數(shù)據(jù)對(duì)象，為后續(xù)數(shù)據(jù)對(duì)象的重新劃分打好基礎(chǔ).

圖3 類(lèi)別待定集的構(gòu)造過(guò)程示意圖. （a）K–means算法對(duì)數(shù)據(jù)集的初始聚類(lèi)結(jié)果；（b）CABON 算法構(gòu)造類(lèi)別待定集圖示Fig.3 Schematic of the construction process of the undetermined-cluster set: (a) initial clustering result of the K-means algorithm on data sets; (b)undetermined-cluster set constructed by the CABON algorithm

1.3 類(lèi)別待定集中數(shù)據(jù)對(duì)象的劃分規(guī)則

初始類(lèi)別待定集構(gòu)造完成后，為了將該集合中數(shù)據(jù)對(duì)象準(zhǔn)確地劃分到正確的類(lèi)中，CABON算法定義了一種新的類(lèi)的劃分規(guī)則. 規(guī)則描述如下：（1）查找類(lèi)別待定集中每個(gè)數(shù)據(jù)對(duì)象在類(lèi)別確定集中的最近鄰居，這些最近鄰居數(shù)據(jù)對(duì)象構(gòu)成一個(gè)集合，稱(chēng)之為最近鄰居集；（2）依據(jù)距離最近鄰居距離最小原則，確定類(lèi)別待定集的邊界對(duì)象，并將邊界對(duì)象歸入其最近鄰居所在類(lèi)別中；（3）將已經(jīng)重新劃分過(guò)類(lèi)別的邊界對(duì)象從類(lèi)別待定集中刪除，并添加到類(lèi)別確定集中，動(dòng)態(tài)調(diào)整類(lèi)別待定集；（4）重復(fù)第（2）、（3）步，直到類(lèi)別待定集為空.

在上述規(guī)則中可以看出，CABON算法在實(shí)現(xiàn)過(guò)程中，類(lèi)別待定集中的對(duì)象不是固定不變的，因?yàn)轭?lèi)別待定集固定的思路仍會(huì)導(dǎo)致數(shù)據(jù)對(duì)象類(lèi)別錯(cuò)分的情況，利用上述規(guī)則中類(lèi)別待定集的動(dòng)態(tài)調(diào)整機(jī)制可以避免這一情況的發(fā)生. 如圖4所示，三角形和圓圈分別代表初始聚類(lèi)得到的兩種類(lèi)別，虛線內(nèi)對(duì)象代表已構(gòu)造好的類(lèi)別待定集. 按照上述類(lèi)別待定集中數(shù)據(jù)對(duì)象的劃分規(guī)則，隨著類(lèi)別待定集的動(dòng)態(tài)調(diào)整，對(duì)象x1應(yīng)歸入大類(lèi)Cluster1中. 若類(lèi)別待定集是固定的，即虛線內(nèi)對(duì)象在算法的迭代過(guò)程中不發(fā)生變化，CABON算法在計(jì)算類(lèi)別待定集中數(shù)據(jù)對(duì)象與類(lèi)別確定集中數(shù)據(jù)對(duì)象之間的距離時(shí)，對(duì)象x1與對(duì)象x3的距離略大于對(duì)象x1與 對(duì) 象x2的 距 離 (d(x1,x3)>d(x1,x2))， 且d(x1,x2)為距離集合里的最小值，因此對(duì)象x1的最近鄰居為小類(lèi)中的對(duì)象x2，其類(lèi)別也將與對(duì)象x2一致.如此一來(lái)，類(lèi)別待定集中原本應(yīng)歸入大類(lèi)中的對(duì)象會(huì)被錯(cuò)分到小類(lèi)中. 故在此基礎(chǔ)上，我們定義類(lèi)別待定集和類(lèi)別確定集是動(dòng)態(tài)變化的：當(dāng)類(lèi)別待定集中的邊界對(duì)象類(lèi)別確定后，將此邊界對(duì)象從類(lèi)別待定集中剔除并添加至類(lèi)別確定集中，此對(duì)象的類(lèi)別確定后就有可能成為類(lèi)別待定集其他數(shù)據(jù)對(duì)象的最近鄰居. 將類(lèi)別待定集的每一數(shù)據(jù)對(duì)象按照從集合邊緣到中心的順序依次歸入其最近鄰居所在的類(lèi)別中，實(shí)現(xiàn)類(lèi)別待定集動(dòng)態(tài)調(diào)整的過(guò)程，以避免上述類(lèi)別待定集固定所導(dǎo)致的數(shù)據(jù)對(duì)象類(lèi)別錯(cuò)分的后果.

圖4 CABON 算法固定類(lèi)別待定集的情況示意圖Fig.4 Schematic of the CABON algorithm’s fixed of the undeterminedcluster set

圖5展示了類(lèi)別待定集中數(shù)據(jù)對(duì)象根據(jù)CABON算法所定義的類(lèi)劃分規(guī)則實(shí)現(xiàn)類(lèi)劃分的過(guò)程. 首先，圖5（a）在圖3（b）構(gòu)造的類(lèi)別待定集的基礎(chǔ)上，確定了類(lèi)別待定集中每一個(gè)數(shù)據(jù)對(duì)象在類(lèi)別確定集中的最近鄰居；其次，根據(jù)二者距離的大小選擇距離最小的數(shù)據(jù)對(duì)象作為邊界對(duì)象，即圖5（a）中虛線內(nèi)有顏色填充的對(duì)象為此次迭代中的邊界對(duì)象，而虛線外有相同顏色填充的對(duì)象為邊界對(duì)象對(duì)應(yīng)的最近鄰居；最后，根據(jù)近鄰思想將邊界對(duì)象歸入其最近鄰居所在的類(lèi)中，由此確定邊界對(duì)象的類(lèi)別，進(jìn)而將邊界對(duì)象由類(lèi)別待定集劃分到類(lèi)別確定集中（圖 5（b））. 圖 5 展示了類(lèi)別待定集中數(shù)據(jù)對(duì)象類(lèi)別重新劃分的一次迭代過(guò)程，經(jīng)過(guò)多次迭代后，類(lèi)別待定集中的數(shù)據(jù)對(duì)象為空，表示所有數(shù)據(jù)對(duì)象已實(shí)現(xiàn)了類(lèi)別的重新劃分，得到了最后的聚類(lèi)結(jié)果.

2 CABON 算法過(guò)程

Step 1：對(duì)數(shù)據(jù)集X用經(jīng)典的 K–means算法聚類(lèi)，得到初始聚類(lèi)結(jié)果；

Step 2：構(gòu)造類(lèi)別待定集. 對(duì)于任意一個(gè)數(shù)據(jù)對(duì)象(i=1,2,…,n)，選擇距離最近的兩個(gè)類(lèi)與(s,t=1,2,…,k,s≠k)，且它們的類(lèi)中心為和，若與數(shù)據(jù)對(duì)象的距離符合如下關(guān)系：

Step 3：查找最近鄰居集. 根據(jù)類(lèi)別待定集中數(shù)據(jù)對(duì)象與類(lèi)別確定集中數(shù)據(jù)對(duì)象的距離大小，在類(lèi)別確定集中選取距離最小的對(duì)象集合作為的最近鄰居集對(duì)應(yīng)類(lèi)別待定集中數(shù)據(jù)對(duì)象在類(lèi)別確定集中的最近鄰居)；

Step 4：確定邊界對(duì)象. 查找到距離最近鄰居最小的數(shù)據(jù)對(duì)象， 確定為類(lèi)別待定集的邊界對(duì)象，將此邊界對(duì)象歸入其最近鄰居所 在的類(lèi)別中；同時(shí)將邊界對(duì)象從類(lèi)別待定集中剔除并添加到類(lèi)別確定集中；

Step 5：重復(fù) Step 3 至 Step 4，直到類(lèi)別待定集為空集、類(lèi)別確定集為全集時(shí)停止.

圖5 類(lèi)別待定集中數(shù)據(jù)對(duì)象類(lèi)別重新劃分過(guò)程示意圖. （a）邊界對(duì)象確定過(guò)程；（b）類(lèi)別待定集調(diào)整過(guò)程Fig.5 Schematic of the reclassification process of data objects in the undetermined-cluster set: (a) determination of boundary objects; (b) the adjustment process of undetermined-cluster set

由CABON算法的具體實(shí)現(xiàn)步驟可知CABON算法具有兩個(gè)顯著特點(diǎn)：（1）從計(jì)算數(shù)據(jù)對(duì)象與其最近的兩個(gè)類(lèi)中心距離差的角度，提出了類(lèi)別待定集的構(gòu)造方法，彌補(bǔ)已有研究構(gòu)造模糊工作集時(shí)部分對(duì)象被誤分這一不足；（2）基于近鄰思想，為類(lèi)別待定集中對(duì)象重新定義一種新的類(lèi)的劃分規(guī)則. 利用類(lèi)別待定集對(duì)象的最近鄰居作為確定其類(lèi)別的參照依據(jù)，可以更精確地劃分類(lèi)別待定集對(duì)象所歸屬的類(lèi)別，并且CABON算法中類(lèi)別待定集的動(dòng)態(tài)調(diào)整機(jī)制大大降低了對(duì)象歸屬類(lèi)別錯(cuò)分的概率，從而保證聚類(lèi)結(jié)果的質(zhì)量.

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

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

為了驗(yàn)證CABON算法解決K–means“均勻效應(yīng)”問(wèn)題的有效性，實(shí)驗(yàn)分別在6個(gè)人工數(shù)據(jù)集和4 個(gè) UCI（University of California Irvine）真實(shí)數(shù)據(jù)集上進(jìn)行，詳細(xì)信息見(jiàn)表1，編號(hào)1～6為人工數(shù)據(jù)集具體信息，真實(shí)分布如圖6所示，其中編號(hào)1～3描述的是測(cè)試聚類(lèi)常用的Flame[19]、Aggregation[20]、Jain[21]數(shù)據(jù)集，編號(hào)4～6描述的是Python合成的3個(gè)數(shù)據(jù)集，分別為 DS1、DS2、DS3. 另外，表 1編號(hào)7～10為真實(shí)數(shù)據(jù)集的具體信息，實(shí)驗(yàn)采用了加州大學(xué)歐文分校提出的UCI標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)中的Wine[22]、 Newthyroid[23]、 Ionosphere[24]和 Heart[25]這4個(gè)數(shù)據(jù)集.

3.2 評(píng)價(jià)指標(biāo)

為了評(píng)估CABON算法及對(duì)比算法的聚類(lèi)效果，本文引入了4個(gè)評(píng)價(jià)指標(biāo)，分別是聚類(lèi)精度（Accuracy）[26]、F 值（F-measure）[8]、標(biāo)準(zhǔn)化互信息（Normalized mutual information， NMI）[15, 27, 28]和 蘭德指數(shù)（Rand index，RI）[29?30]，4 個(gè)評(píng)價(jià)指標(biāo)的取值上界均為1，指標(biāo)值越接近1，聚類(lèi)效果越好.

設(shè)k為聚類(lèi)個(gè)數(shù)，N為數(shù)據(jù)集中數(shù)據(jù)對(duì)象的個(gè)數(shù)，為數(shù)據(jù)集的實(shí)際類(lèi)分布，為數(shù)據(jù)集的聚類(lèi)結(jié)果為和的共同部分的基數(shù)，則聚類(lèi)精度（Accuracy）的公式如（1）所示：

F-measure的計(jì)算公式如（2）所示：

其中：Recall和Precision分別表示數(shù)據(jù)集中真實(shí)聚類(lèi)結(jié)果與聚類(lèi)結(jié)果相比的召回率和準(zhǔn)確率；β表示Recall和Precision的相對(duì)重要性，通常設(shè)為1.

NMI的計(jì)算公式如（3）所示：

其中：N為數(shù)據(jù)集的數(shù)據(jù)對(duì)象數(shù)量，為 屬于類(lèi)i的數(shù)據(jù)對(duì)象數(shù)量；為屬于類(lèi)的數(shù)據(jù)對(duì)象數(shù)量；為真實(shí)數(shù)據(jù)集中類(lèi)i與聚類(lèi)結(jié)果類(lèi)相一致的數(shù)據(jù)對(duì)象數(shù)量；R、K分別對(duì)應(yīng)真實(shí)數(shù)據(jù)集和聚類(lèi)結(jié)果類(lèi)中的類(lèi)個(gè)數(shù).

RI的計(jì)算公式如（4）所示：

表 1 數(shù)據(jù)集參數(shù)信息Table 1 Parameter information for the data set

其中：a表示被聚類(lèi)結(jié)果和真實(shí)結(jié)果判定為同一類(lèi)別的數(shù)據(jù)對(duì)的數(shù)目；b表示聚類(lèi)結(jié)果和真實(shí)結(jié)果都將判定為不同類(lèi)別的數(shù)據(jù)對(duì)的數(shù)目；h表示聚類(lèi)結(jié)果認(rèn)為同類(lèi)，但真實(shí)結(jié)果認(rèn)為不同類(lèi)的數(shù)據(jù)對(duì)的數(shù)目；g表示聚類(lèi)結(jié)果認(rèn)為不同類(lèi)，但真實(shí)結(jié)果認(rèn)為同類(lèi)的數(shù)據(jù)對(duì)的數(shù)目.

圖6 人工數(shù)據(jù)集真實(shí)分布. （a） Flame；（b） Aggregation；（c） Jain；（d） DS1；（e） DS2；（f） DS3Fig.6 True distribution of synthetic data sets: (a) Flame; (b) Aggregation; (c) Jain; (d) DS1; (e) DS2; (f) DS3

3.3 實(shí)驗(yàn)設(shè)計(jì)

實(shí)驗(yàn)將CABON算法與K–means、MC_IK[14]和CVCN[15]算法進(jìn)行對(duì)比. K–means算法是經(jīng)典的聚類(lèi)算法，作為對(duì)比算法可比較不同算法降低“均勻效應(yīng)”影響的程度；MC_IK和CVCN算法分別從多中心和優(yōu)化目標(biāo)函數(shù)的角度有效降低了不均衡數(shù)據(jù)聚類(lèi)中“均勻效應(yīng)”問(wèn)題的影響. 對(duì)比實(shí)驗(yàn)通過(guò)將CABON算法和這些算法進(jìn)行對(duì)比，以衡量CABON算法處理不均衡數(shù)據(jù)聚類(lèi)問(wèn)題降低“均勻效應(yīng)”影響的能力. 在設(shè)定實(shí)驗(yàn)參數(shù)方面，參數(shù)k是輸入的聚類(lèi)個(gè)數(shù)，可參考實(shí)驗(yàn)數(shù)據(jù)集類(lèi)的數(shù)量設(shè)定.δ為構(gòu)造類(lèi)別待定集事先設(shè)定的參數(shù)，取值范圍根據(jù)數(shù)據(jù)集的大小而確定. 在本實(shí)驗(yàn)中，若數(shù)據(jù)集較小，閾值δ的取值范圍設(shè)定為0.5～1.5，以0.5為初始值、0.1為步長(zhǎng)確定一個(gè)最優(yōu)取值區(qū)間，表現(xiàn)為閾值δ在此區(qū)間內(nèi)時(shí)聚類(lèi)評(píng)價(jià)指標(biāo)值最高；最優(yōu)取值區(qū)間確定后，縮短步長(zhǎng)為0.01，在此區(qū)間內(nèi)選擇一個(gè)最優(yōu)值作為此數(shù)據(jù)集的類(lèi)別待定集構(gòu)造閾值，表現(xiàn)為閾值δ取到此參數(shù)值時(shí)聚類(lèi)評(píng)價(jià)指標(biāo)值最高. 同樣地，若數(shù)據(jù)集較大，閾值δ的取值范圍設(shè)定為1.0～2.0，以1.0為初始值、0.1為步長(zhǎng)確定一個(gè)最優(yōu)取值區(qū)間后，縮短步長(zhǎng)為0.01，在此區(qū)間內(nèi)再次選擇一個(gè)最優(yōu)值作為此數(shù)據(jù)集的類(lèi)別待定集構(gòu)造閾值.

表 2 人工數(shù)據(jù)集不同算法聚類(lèi)結(jié)果（Accuracy 指標(biāo)）Table 2 Clustering results of artificial data set with different algorithms (Accuracy indicators)

3.4 實(shí)驗(yàn)結(jié)果

（1）人工數(shù)據(jù)集實(shí)驗(yàn)結(jié)果.

表2～表5給出了CABON、K–means、MC_IK和CVCN算法對(duì)人工數(shù)據(jù)集的聚類(lèi)結(jié)果. 從表2～表5中可以看出，CABON算法在大多數(shù)情況下明顯優(yōu)于其他三種算法，這在一定程度上說(shuō)明CABON算法能夠消減K–means算法產(chǎn)生的“均勻效應(yīng)”.對(duì)于Flame、Aggregation數(shù)據(jù)集，CABON的各個(gè)指標(biāo)值均優(yōu)于對(duì)比算法，但是CABON在處理Jain數(shù)據(jù)集時(shí)的F-measure、NMI值略低于CVCN算法，其原因在于Jain為非球形不均衡數(shù)據(jù)集，CABON對(duì)部分此類(lèi)數(shù)據(jù)集中的數(shù)據(jù)對(duì)象聚類(lèi)時(shí)無(wú)法準(zhǔn)確構(gòu)建類(lèi)別待定集，從而影響最后的聚類(lèi)結(jié)果.

對(duì)于 3個(gè)合成的數(shù)據(jù)集（DS1、DS2、DS3），CABON算法的聚類(lèi)精度均優(yōu)于對(duì)比算法. DS1和DS2數(shù)據(jù)集在數(shù)據(jù)對(duì)象的數(shù)量和密度上有較大差異，CABON處理這兩個(gè)數(shù)據(jù)集時(shí)取得了較好的聚類(lèi)效果；對(duì)于DS3數(shù)據(jù)集，K–means算法對(duì)其聚類(lèi)時(shí)在多個(gè)類(lèi)之間產(chǎn)生了“均勻效應(yīng)”，CABON算法的聚類(lèi)精度、F-measure、RI指標(biāo)值均接近于1，驗(yàn)證了該算法處理此類(lèi)問(wèn)題的有效性. 同時(shí)，CVCN算法在DS3數(shù)據(jù)集上的各個(gè)指標(biāo)值均低于K–means算法，這在一定程度上說(shuō)明CVCN算法在處理多類(lèi)非均勻數(shù)據(jù)聚類(lèi)問(wèn)題上處理能力較弱. 另外，MC_IK 算法在DS1、DS2、DS3數(shù)據(jù)集上的實(shí)驗(yàn)表現(xiàn)較K–means而言有不同程度的提升，表明MC_IK算法對(duì)K–means在DS1、DS2、DS3上產(chǎn)生的“均勻效應(yīng)”有消減作用.

表 3 人工數(shù)據(jù)集不同算法聚類(lèi)結(jié)果（F-measure 指標(biāo)）Table 3 Clustering results of artificial data set with different algorithms (F-measure indicators)

表 4 人工數(shù)據(jù)集不同算法聚類(lèi)結(jié)果（NMI指標(biāo)）Table 4 Clustering results of artificial data set with different algorithms (NMI indicators)

表 5 人工數(shù)據(jù)集不同算法聚類(lèi)結(jié)果（RI指標(biāo)）Table 5 Clustering results of artificial data set with different algorithms (RI indicators)

圖7 Flame 數(shù)據(jù)集不同算法聚類(lèi)結(jié)果圖示. （a） CABON；（b） K–means；（c） MC_IK；（d） CVCNFig.7 Graphical representations of clustering results with different algorithms on Flame data sets: (a) CABON; (b) K–means; (c) MC_IK; (d) CVCN

圖8 Aggregation 數(shù)據(jù)集不同算法聚類(lèi)結(jié)果圖示. （a） CABON；（b） K–means；（c） MC_IK；（d） CVCNFig.8 Graphical representations of clustering results with different algorithms on Aggregation data sets: (a) CABON; (b) K–means; (c) MC_IK; (d)CVCN

圖7～圖 12是 CABON、K–means、MC_IK和CVCN算法對(duì)人工數(shù)據(jù)聚類(lèi)結(jié)果的圖示，這與表2～表5中的數(shù)據(jù)基本吻合. 綜上，人工數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明CABON算法能夠有效消減不均衡數(shù)據(jù)聚類(lèi)的“均勻效應(yīng)”.

（2）真實(shí)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果.

表6～表9給出了CABON、K–means、MC_IK和CVCN算法分別對(duì)4個(gè)真實(shí)數(shù)據(jù)集進(jìn)行聚類(lèi)的結(jié)果，從表6～表9中可以看出，對(duì)于UCI上的4個(gè)真實(shí)數(shù)據(jù)集，CABON算法在大多數(shù)情況下明顯優(yōu)于其他三種算法. 對(duì)于Wine數(shù)據(jù)集而言，CABON算法的NMI值略低于MC_IK算法，但是其他三個(gè)指標(biāo)值均高于對(duì)比算法；對(duì)于Newthyroid、Ionosphere數(shù)據(jù)集，CABON算法的各個(gè)指標(biāo)值均優(yōu)于對(duì)比算法；對(duì)于Heart數(shù)據(jù)集，CABON算法聚類(lèi)精度和F-measure值略低于CVCN算法，但是NMI值和RI值均高于對(duì)比算法. 以上結(jié)果表明，CABON算法對(duì)于UCI中的真實(shí)不均衡數(shù)據(jù)集也能有效解決“均勻效應(yīng)”問(wèn)題，提高聚類(lèi)效果.

圖9 Jain 數(shù)據(jù)集不同算法聚類(lèi)結(jié)果圖示. （a） CABON；（b） K–means；（c） MC_IK；（d） CVCNFig.9 Graphical representations of clustering results with different algorithms on Jain data sets: (a) CABON; (b) K–means; (c) MC_IK; (d) CVCN

圖10 DS1 數(shù)據(jù)集不同算法聚類(lèi)結(jié)果圖示. （a） CABON；（b） K–means；（c） MC_IK；（d） CVCNFig.10 Graphical representations of clustering results with different algorithms on DS1 data sets: (a) CABON; (b) K–means; (c) MC_IK; (d) CVCN

圖11 DS2 數(shù)據(jù)集不同算法聚類(lèi)結(jié)果圖示. （a） CABON；（b） K–means；（c） MC_IK；（d） CVCNFig.11 Graphical representations of clustering results with different algorithms on DS2 data sets: (a) CABON; (b) K–means; (c) MC_IK; (d) CVCN

圖12 DS3 數(shù)據(jù)集不同算法聚類(lèi)結(jié)果圖示. （a） CABON；（b） K–means；（c） MC_IK；（d） CVCNFig.12 Graphical representations of clustering results with different algorithms on DS3 data sets: (a) CABON; (b) K–means; (c) MC_IK; (d) CVCN

表 6 UCI數(shù)據(jù)集不同算法聚類(lèi)結(jié)果（Accuracy 指標(biāo)）Table 6 Clustering results of UCI dataset with different algorithms(Accuracy indicators)

表 7 UCI數(shù)據(jù)集不同算法聚類(lèi)結(jié)果（F-measure 指標(biāo)）Table 7 Clustering results of UCI dataset with different algorithms(F-measure indicators)

表 8 UCI數(shù)據(jù)集不同算法聚類(lèi)結(jié)果（NMI指標(biāo)）Table 8 Clustering results of UCI dataset with different algorithms(NMI indicators)

表 9 UCI數(shù)據(jù)集不同算法聚類(lèi)結(jié)果（RI指標(biāo)）Table 9 Clustering results of UCI dataset with different algorithms(RI indicators)

總體來(lái)說(shuō)，本文提出的CABON算法明顯優(yōu)于其他三種對(duì)比算法. 人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果，驗(yàn)證了CABON算法在解決不均衡數(shù)據(jù)聚類(lèi)的“均勻效應(yīng)”問(wèn)題和提高聚類(lèi)效果上的可行性和有效性.

4 結(jié)論

（1）針對(duì) K–means算法的“均勻效應(yīng)”問(wèn)題，從計(jì)算數(shù)據(jù)對(duì)象與其最近的兩個(gè)類(lèi)中心距離差的角度，給出了類(lèi)別待定集的定義，解決了已有研究構(gòu)造模糊工作集時(shí)部分?jǐn)?shù)據(jù)對(duì)象類(lèi)別被錯(cuò)分這一問(wèn)題，間接提高了算法的聚類(lèi)質(zhì)量.

（2）針對(duì)不均衡數(shù)據(jù)的聚類(lèi)問(wèn)題，提出了基于近鄰的不均衡數(shù)據(jù)聚類(lèi)算法（CABON）. CABON算法在對(duì)給定的數(shù)據(jù)集進(jìn)行初始聚類(lèi)后，針對(duì)初始聚類(lèi)結(jié)果按照預(yù)設(shè)閾值δ構(gòu)造類(lèi)別待定集，基于近鄰思想將類(lèi)別待定集中數(shù)據(jù)對(duì)象歸入其最近鄰居所在的類(lèi)別中，并動(dòng)態(tài)更新類(lèi)別待定集，得到最終的聚類(lèi)結(jié)果.

（3）人工數(shù)據(jù)集和UCI真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明，CABON算法能夠有效消減K–means算法所產(chǎn)生的“均勻效應(yīng)”. 與K–means以及專(zhuān)門(mén)針對(duì)不均衡數(shù)據(jù)聚類(lèi)的MC_IK和CVCN算法的實(shí)驗(yàn)對(duì)比表明，CABON算法的聚類(lèi)精度有明顯提升.