基于質(zhì)心自適應(yīng)選取的密度萬(wàn)有引力聚類算法

陳金鵬，李睿熙，楊 然，安俊秀+

(1.成都信息工程大學(xué) 并行計(jì)算實(shí)驗(yàn)室，四川 成都 610225；2.成都錦城學(xué)院 計(jì)算機(jī)與軟件學(xué)院，四川 成都 611731)

0 引 言

聚類分析是大數(shù)據(jù)分析中極其重要的方法之一，目的是將多個(gè)對(duì)象按照其相似性劃分成多個(gè)差異度較大的類，而這些類別中的對(duì)象相似度較高。劃分聚類算法[1]是在給定數(shù)據(jù)集的基礎(chǔ)上，通過(guò)一些相似性度量的公式，將這些數(shù)據(jù)點(diǎn)劃分成多個(gè)簇，每個(gè)簇中的點(diǎn)相似度較高而不同的簇之間相似度較低[2]。基于劃分的聚類算法有很多種，其中最典型的聚類算法是K-means算法[3]，該算法的主要思想是通過(guò)迭代計(jì)算不同數(shù)據(jù)點(diǎn)和給定簇中心的距離不同而分配給距離最近的簇。然而傳統(tǒng)的K-means算法有4大缺陷，這些缺陷主要是聚類效果對(duì)初始簇中心的選取結(jié)果具有依賴性[4,5]，k值難以確定[6,7]，沒(méi)有考慮簇與簇之間的關(guān)系[8]，只能發(fā)現(xiàn)圓簇以及離群點(diǎn)對(duì)聚類效果有影響[9]。基于以上問(wèn)題，Chunhui Yuan等在文獻(xiàn)[10]中針對(duì)k值選擇的不同，導(dǎo)致的聚類結(jié)果差距較大的問(wèn)題，給出了4種k值選擇方法，即肘部法、間隙統(tǒng)計(jì)、輪廓系數(shù)和Canopy算法。王建仁等在文獻(xiàn)[11]中對(duì)肘部法進(jìn)行了詳細(xì)的實(shí)驗(yàn)和運(yùn)用，通過(guò)k值和“肘點(diǎn)”的關(guān)系來(lái)確定k值點(diǎn)，提出了ET-SSE算法，該算法可以改進(jìn)k值的選擇。

萬(wàn)有引力聚類是將物理學(xué)中任意兩個(gè)粒子之間都存在相互吸引的引力這一思想引入到聚類中，使得聚類過(guò)程中不僅要考慮數(shù)據(jù)之間的距離，還要考慮數(shù)據(jù)的“質(zhì)量”，杜潔等在文獻(xiàn)[12]中提出數(shù)據(jù)的“質(zhì)量”可以使用局部合力來(lái)代替，使得數(shù)據(jù)點(diǎn)之間的關(guān)系變得更加緊湊，使用局部合力來(lái)替代萬(wàn)有引力公式中的質(zhì)量也為萬(wàn)有引力在聚類算法中的應(yīng)用起到了至關(guān)重要的效果。引力搜索算法GSA[13]將物理學(xué)的萬(wàn)有引力作為算法核心進(jìn)行了研究，為后續(xù)的引力算法研究奠定了基礎(chǔ)，該算法也存在一些缺點(diǎn)，容易早熟收斂，并且存在需要設(shè)定較多參數(shù)值的缺點(diǎn)。基于GSA算法的提出，Chao Liu等在文獻(xiàn)[14]中對(duì)粒子初始位置進(jìn)行了優(yōu)化，提出了AC-GSA算方法，該算法將自適應(yīng)慣性權(quán)重系數(shù)引入到公式中。Seyedali Mirjalili等在文獻(xiàn)[15]中對(duì)引力系數(shù)G進(jìn)行了改進(jìn)，使得算法能夠突破局部最優(yōu)解對(duì)全局聚類的影響。魏康園等在文獻(xiàn)[16]中針對(duì)經(jīng)典的引力搜索算法很容易在搜索的過(guò)程中得到一個(gè)局部最優(yōu)解，從而很早發(fā)生收斂的現(xiàn)象提出了A2F-GSA算法，該算法相比其它算法擁有更好的收斂性。Chen Lei等在文獻(xiàn)[17]中提出了Gravc算法，該算法通過(guò)設(shè)計(jì)一種基于局部密度的數(shù)據(jù)壓縮策略，減少了參與引力聚類算法的數(shù)據(jù)對(duì)象數(shù)量和每個(gè)對(duì)象的鄰域數(shù)量，并對(duì)傳統(tǒng)的重力模型進(jìn)行了優(yōu)化，以適應(yīng)數(shù)據(jù)壓縮策略造成的不同對(duì)象的質(zhì)量差異。引力聚類的思想可以用于其它多種聚類算法的改進(jìn)中，王治和等在文獻(xiàn)[18]中將引力聚類思想運(yùn)用在AP算法中，通過(guò)對(duì)偏向參數(shù)的依賴性的降低，極大地提高了稀疏數(shù)據(jù)集的聚類最終效果。肖輝輝等在文獻(xiàn)[19]中將引力聚類思想運(yùn)用在FPA算法中，較大提升了FPA算法的收斂速度、收斂精度、魯棒性。Zhiqiang Wang等在文獻(xiàn)[20]中根據(jù)引力模型推導(dǎo)出中心點(diǎn)度量，并區(qū)分了內(nèi)部點(diǎn)和邊界點(diǎn)，提出了局部引力LGC聚類算法，由于該算法需要確定多個(gè)參數(shù)且對(duì)參數(shù)取值敏感，因此該作者將社團(tuán)聚類引入其中，提出了CLA算法，該算法將LGC算法的參數(shù)減少到了1個(gè)，但是聚類效果相對(duì)下降。

1 基于密度萬(wàn)有引力的K-means改進(jìn)算法

任意兩個(gè)空間中的粒子之間都存在相互吸引的萬(wàn)有引力，牛頓的萬(wàn)有引力定律認(rèn)為這個(gè)力的大小與它們本身的質(zhì)量以及它們之間的距離有關(guān)。萬(wàn)有引力的大小與質(zhì)量成正比例關(guān)系，與距離成反比例關(guān)系，這個(gè)力的計(jì)算公式如式(1)所示

(1)

式中：mi和mj分別代表粒子i與粒子j的質(zhì)量，G表示引力常量，其值約為6.67×10-11N·m2/kg2，dij為粒子i與粒子j之間的距離。

針對(duì)傳統(tǒng)的K-means方法通過(guò)距離和中心點(diǎn)進(jìn)行聚類時(shí)沒(méi)有考慮簇與簇之間關(guān)系的問(wèn)題，本文根據(jù)萬(wàn)有引力公式進(jìn)行了改進(jìn)，并引入了K-means聚類中。從文獻(xiàn)[12]中提出公式中的“質(zhì)量”可以通過(guò)其周圍的點(diǎn)到此簇中心的局部合力來(lái)近似替代，本文通過(guò)引入“密度”的概念來(lái)近似替代此處的局部合力，因此，本文在萬(wàn)有引力公式中做了如下改動(dòng)：由于G是常量，在引力大小比對(duì)中可以忽略不計(jì)；萬(wàn)有引力中粒子的質(zhì)量，在本文中采用密度來(lái)進(jìn)行改進(jìn)計(jì)算，如式(2)所示

(2)

定義1 簇的密度ρi： 萬(wàn)有引力的大小與粒子的質(zhì)量成正比，而在數(shù)據(jù)集中粒子的質(zhì)量不可度量，而粒子在空間中的局部密度是可以度量的，因此本文萬(wàn)有引力公式中的質(zhì)量，結(jié)合文獻(xiàn)[12]所提出的辦法進(jìn)行改進(jìn)，簇的密度ρi可用近似替代萬(wàn)有引力公式中的質(zhì)量，其大小與簇中粒子和簇中粒子之間的距離有關(guān)，簇的密度ρi計(jì)算公式如式(3)所示

(3)

式中：K為簇內(nèi)點(diǎn)的數(shù)目，Ri為簇內(nèi)點(diǎn)到簇中心的距離。

定義2 圓簇：以簇中心為圓心，這個(gè)簇中距離簇中心最遠(yuǎn)的點(diǎn)到簇中心的距離為半徑作圓，若此簇中所有點(diǎn)都在這個(gè)圓內(nèi)，則稱這個(gè)簇為圓簇；反之，為非圓簇。

定義3 空簇：若一個(gè)簇中不包含任何數(shù)據(jù)點(diǎn)，則稱此簇為空簇。

由于空間中的單個(gè)點(diǎn)被視為質(zhì)量大小都相同的點(diǎn)，因此，每個(gè)點(diǎn)的密度也都相同，即ρj都相同；在計(jì)算過(guò)程中，常量G與ρj一樣，都不會(huì)影響不同點(diǎn)之間的密度萬(wàn)有引力的相對(duì)大小，因此，ρj的處理辦法與G一樣可以忽略不計(jì)。結(jié)合式(2)和式(3)，最終粒子之間的密度萬(wàn)有引力θ定義如式(4)所示

(4)

式(4)定義了數(shù)據(jù)集中點(diǎn)與點(diǎn)之間、點(diǎn)與簇的密度萬(wàn)有引力公式，使用密度萬(wàn)有引力作為K-means聚類中的歐氏距離，如算法1所示，本算法的優(yōu)勢(shì)在于將引力因素加入到了聚類算法中，可以發(fā)現(xiàn)非圓簇；另外如果在過(guò)程中出現(xiàn)了空簇，則直接刪除。

算法1：基于密度萬(wàn)有引力的K-means改進(jìn)算法

算法的輸入：含有S個(gè)點(diǎn)數(shù)據(jù)集S，聚類個(gè)數(shù)K。

算法的輸出：得到的結(jié)果是k個(gè)簇。

步驟1 選取K個(gè)點(diǎn)作為初始聚類簇中心。

步驟2 重復(fù)步驟3、步驟4、步驟5。

步驟3 根據(jù)式(4)分別計(jì)算每個(gè)樣本點(diǎn)到K個(gè)簇中心的密度萬(wàn)有引力，將其分配給引力最大的簇。

步驟4 更新簇的中心和簇的質(zhì)量，重新計(jì)算簇平均值。

步驟5 刪除不包含任何點(diǎn)的簇，并令k=k-1。

步驟6 直到所有簇中心不再變化，循環(huán)結(jié)束。

普通K-means算法在聚類時(shí)使用的是歐氏距離來(lái)對(duì)簇進(jìn)行劃分，這種辦法只考慮了兩點(diǎn)之間的距離，算法1使用改進(jìn)的萬(wàn)有引力密度公式替代了普通K-means算法的歐式距離公式，使得在聚類過(guò)程中不僅考慮了兩點(diǎn)之間的距離，還考慮了當(dāng)前簇的大小對(duì)點(diǎn)的影響。當(dāng)前簇密度越大，與點(diǎn)距離越近，則該簇對(duì)點(diǎn)存在的吸引作用就越大，最終將此點(diǎn)聚類。

2 基于質(zhì)心自適應(yīng)選取的密度萬(wàn)有引力聚類方法

2.1 基于質(zhì)心自適應(yīng)選擇的聚類簇中心選取算法

對(duì)于K-means算法中，每次需要給定簇的數(shù)量k，由于k值選擇的不同，聚類的最終結(jié)果會(huì)不同；另外在初始給定的k值相同的情況下，由于初始簇中心隨機(jī)選擇不同，也會(huì)造成最終聚類的結(jié)果不同，因此本文提出了一種基于質(zhì)心自適應(yīng)選擇的聚類簇中心選取算法，該算法通過(guò)設(shè)置一種初始簇中心的選取策略，來(lái)控制選擇更好的初始簇中心和自適應(yīng)選擇k值，從而達(dá)到減少迭代次數(shù)和更好的聚類效果。

該算法設(shè)有以下定義：

定義4 狀態(tài)標(biāo)記：簇中每一個(gè)點(diǎn)都擁有自己的一個(gè)狀態(tài)標(biāo)記，若該點(diǎn)的標(biāo)記為0，則該點(diǎn)需要進(jìn)行遍歷改變狀態(tài)；若該點(diǎn)的狀態(tài)t=-1， 則該點(diǎn)可能是離群點(diǎn)；若該點(diǎn)的狀態(tài)為t(t=0,1,2,…)， 則該點(diǎn)被t個(gè)簇中心所包含。

定義5 初始圓：以數(shù)據(jù)集中心點(diǎn)X和一個(gè)標(biāo)記t=0的點(diǎn)N組成的線段XN的長(zhǎng)度為直徑，線段XN的中點(diǎn)為圓心作出的圓稱為初始圓。

定義6 簇圓：以初始圓包含的點(diǎn)的質(zhì)心M為圓心，線段MX的長(zhǎng)度為半徑作出的圓稱為簇圓。

歐式距離[19]是聚類分析中最常用的公式，其本質(zhì)是對(duì)兩個(gè)對(duì)象之間最直觀的直線距離進(jìn)行計(jì)算，歐式距離的計(jì)算公式如式(5)所示

(5)

式中：dij為歐氏距離，xij代表數(shù)據(jù)對(duì)象1，yij代表數(shù)據(jù)對(duì)象2，n代表數(shù)據(jù)對(duì)象的個(gè)數(shù)。

本文中基于質(zhì)心自適應(yīng)選擇的聚類簇中心選取算法以數(shù)據(jù)集的中心點(diǎn)作為參照物，然后從離中心點(diǎn)最遠(yuǎn)的點(diǎn)開(kāi)始不斷作初始圓和簇圓，并同時(shí)改變本數(shù)據(jù)集中所有的點(diǎn)的標(biāo)記值，然后根據(jù)數(shù)據(jù)集本身的密集程度來(lái)劃分出簇中心和離群點(diǎn)，算法具體過(guò)程如算法2所示，本算法的優(yōu)勢(shì)在于可以在一定程度上找到離群點(diǎn)，并且可以為后續(xù)聚類減少迭代次數(shù)，也不需要一開(kāi)始給定k值。

算法2：基于質(zhì)心自適應(yīng)選擇的聚類簇中心選取算法

算法的輸入：含有S個(gè)點(diǎn)數(shù)據(jù)集S。

算法的輸出：得到的結(jié)果是k個(gè)簇中心和狀態(tài)標(biāo)記不同的點(diǎn)。

步驟1 首先計(jì)算整個(gè)數(shù)據(jù)集的質(zhì)心，以此質(zhì)心作為整個(gè)數(shù)據(jù)集的中心，記作X。

步驟2 計(jì)算數(shù)據(jù)集中每個(gè)點(diǎn)到數(shù)據(jù)集中心X的距離，并將這個(gè)距離按照由大到小排序，每個(gè)點(diǎn)按此順序分別記作xi， 距離記作di，i從1到S，并將每個(gè)點(diǎn)的初始狀態(tài)記為t=0。

步驟3 按照步驟2中的排好順序的點(diǎn)，從x1開(kāi)始到xS， 依次遍歷狀態(tài)標(biāo)記為0的點(diǎn)。

步驟4 重復(fù)步驟5、步驟6、步驟7。

步驟5 根據(jù)此點(diǎn)xi和整個(gè)數(shù)據(jù)集的質(zhì)心X，做出初始圓，并將此點(diǎn)xi狀態(tài)標(biāo)記為t=-1。

步驟6 以此初始圓內(nèi)的所有點(diǎn)作為一個(gè)整體，計(jì)算為此圓的質(zhì)心Y，做出簇圓，并將簇圓中所有點(diǎn)的狀態(tài)數(shù)值t=t+1， 如果這個(gè)點(diǎn)是離群點(diǎn)(即狀態(tài)標(biāo)記t=-1的點(diǎn))，則這個(gè)狀態(tài)數(shù)值t=t+2。

步驟7 直到所有點(diǎn)的狀態(tài)都不為0，循環(huán)結(jié)束。

常規(guī)的K-means聚類算法對(duì)于初始點(diǎn)的選擇是隨機(jī)的，其改進(jìn)算法也存在較多的選擇，會(huì)導(dǎo)致初始選舉不一致導(dǎo)致聚類結(jié)果不一致。本文算法2可以以數(shù)據(jù)集質(zhì)心作為出發(fā)點(diǎn)，并向周邊擴(kuò)展尋找簇中心，得到唯一的初始選舉結(jié)果，且該初始結(jié)果在數(shù)據(jù)集全面覆蓋分布均勻。該算法與已有算法相比較，算法實(shí)現(xiàn)簡(jiǎn)單，并且可以較好地確保一開(kāi)始選擇的初始簇中心和分配的點(diǎn)位于各個(gè)簇的中心位置，所得到的k值為本次聚類中最大的簇?cái)?shù)目，并覆蓋數(shù)據(jù)集中所有的點(diǎn)。

2.2 基于質(zhì)心自適應(yīng)選取的密度萬(wàn)有引力聚類算法

基于質(zhì)心自適應(yīng)選取的密度萬(wàn)有引力聚類(CASG-means)算法首先根據(jù)算法2對(duì)簇中心進(jìn)行選擇，然后通過(guò)算法1的改進(jìn)算法思路進(jìn)行結(jié)合，最終得到了算法3的聚類算法，CASG-means算法改進(jìn)的具體步驟如圖1所示。

圖1 CASG-means算法改進(jìn)的步驟

算法3：基于質(zhì)心自適應(yīng)選取的密度萬(wàn)有引力聚類算法

算法的輸入：含有S個(gè)點(diǎn)數(shù)據(jù)集S。

算法的輸出：得到的結(jié)果是k個(gè)簇，以及標(biāo)記為t=-1的離群點(diǎn)。

步驟1 執(zhí)行算法2，得到k個(gè)簇和狀態(tài)標(biāo)記不同的點(diǎn)。

步驟2 對(duì)每個(gè)標(biāo)記狀態(tài)t=1的點(diǎn)，直接分配給步驟1最終所在的簇中，并更新每個(gè)簇的簇中心。

步驟3 重復(fù)步驟4、步驟5、步驟6、步驟7。

步驟4 對(duì)標(biāo)記t>0的所有點(diǎn)(第一次循環(huán)不再分配狀態(tài)標(biāo)記t=1的點(diǎn))，根據(jù)式(4)分別計(jì)算每個(gè)樣本點(diǎn)到K個(gè)簇中心的密度萬(wàn)有引力，將其分配給引力最大的簇。

步驟5 更新簇的中心和簇的質(zhì)量，重新計(jì)算簇平均值。

步驟6 刪除不包含任何點(diǎn)的簇，并令k=k-1。

步驟7 直到所有簇中心不再變化，循環(huán)結(jié)束。

算法3結(jié)合了算法2的基于質(zhì)心自適應(yīng)選擇的聚類簇中心選取策略，并應(yīng)用了算法1的密度萬(wàn)有引力公式替換歐氏距離，不僅增強(qiáng)了點(diǎn)與點(diǎn)之間、點(diǎn)與簇之間的吸引關(guān)系，還解決了算法2中可能存在由于數(shù)據(jù)分布不均勻?qū)е碌亩鄠€(gè)初始簇中心分布距離較近的問(wèn)題，對(duì)距離較近的簇進(jìn)行了吸引合并，最終可以自適應(yīng)生成合適的簇?cái)?shù)目，并且可以識(shí)別出離群點(diǎn)。與現(xiàn)有的改進(jìn)算法相比較，具有實(shí)現(xiàn)簡(jiǎn)單、可以根據(jù)數(shù)據(jù)點(diǎn)的實(shí)際分簇情況對(duì)簇進(jìn)行合并的優(yōu)勢(shì)。

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

本章將對(duì)本文所提出的算法3：基于質(zhì)心自適應(yīng)選取的密度萬(wàn)有引力聚類算法(CASG-means算法)進(jìn)行實(shí)驗(yàn)，所涉及到的實(shí)驗(yàn)分別為聚類效果對(duì)比實(shí)驗(yàn)、迭代次數(shù)、離群點(diǎn)數(shù)目和簇減少數(shù)目。

3.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)環(huán)境配置如下：Intel(R) Core(TM) i7-9750H CPU @2.60 Hz，16 GBytes，Windows 10家庭中文版，所用代碼依賴于Python3.6(base)。實(shí)驗(yàn)在30個(gè)不同的數(shù)據(jù)集上做了對(duì)比效果，數(shù)據(jù)集為python隨機(jī)數(shù)生成的人工合成數(shù)據(jù)集，其中簇中心用實(shí)心圓點(diǎn)標(biāo)記，離群點(diǎn)用“x”標(biāo)記，k值的選擇為基于質(zhì)心自適應(yīng)選擇的聚類簇中心選取策略的簇?cái)?shù)目。

3.2 數(shù)據(jù)聚類效果對(duì)比

普通K-means算法較為成熟的改進(jìn)算法有K-means++算法[22]和ISODATA算法[23]，因此本次實(shí)驗(yàn)將本文提出的3個(gè)新算法與K-means++算法和ISODATA算法進(jìn)行對(duì)比實(shí)驗(yàn)。因此本節(jié)將對(duì)以下5個(gè)算法的聚類結(jié)果進(jìn)行對(duì)比：①基于密度萬(wàn)有引力的K-means改進(jìn)算法；②基于質(zhì)心自適應(yīng)選擇的聚類簇中心選取策略改進(jìn)的K-means算法；③基于質(zhì)心自適應(yīng)選取的密度萬(wàn)有引力聚類(CASG-means)算法；④K-means++算法；⑤ISODATA算法。

本節(jié)數(shù)據(jù)集選自第一節(jié)30個(gè)不同數(shù)據(jù)集中的其中5個(gè)經(jīng)典的例子進(jìn)行對(duì)比說(shuō)明，在本節(jié)的所有實(shí)驗(yàn)圖中(如圖2～圖6所示)，每一次實(shí)驗(yàn)結(jié)果分為6個(gè)圖片，圖(a)是質(zhì)心自適應(yīng)選擇的聚類簇中心，圖(b)是上述算法①結(jié)果，圖(c)是上述算法②結(jié)果，圖(d)是上述算法③結(jié)果，圖(e)是上述算法結(jié)果，圖(f)是上述算法⑤結(jié)果。在本次實(shí)驗(yàn)中，所有的k值取值為圖(a)所劃分出來(lái)的簇?cái)?shù)目，算法⑤中的最大迭代次數(shù)取值為算法③在相同數(shù)據(jù)集所用的迭代次數(shù)。

圖2 5種算法在數(shù)據(jù)集1上的對(duì)比實(shí)驗(yàn)

圖3 5種算法在數(shù)據(jù)集2上的對(duì)比實(shí)驗(yàn)

圖4 5種算法在數(shù)據(jù)集3上的對(duì)比實(shí)驗(yàn)

圖5 5種算法在數(shù)據(jù)集4上的對(duì)比實(shí)驗(yàn)

圖6 5種算法在數(shù)據(jù)集5上的對(duì)比實(shí)驗(yàn)

數(shù)據(jù)集1的數(shù)據(jù)分布的特點(diǎn)是隨機(jī)均勻分布，對(duì)此數(shù)據(jù)集運(yùn)行上述5種算法，其實(shí)驗(yàn)結(jié)果如圖2所示。如圖2(a)所示，本次選擇出來(lái)了5個(gè)簇中心和1個(gè)離群點(diǎn)，本次實(shí)驗(yàn)中k=5。 圖2(b)的算法①結(jié)果圖中簇的數(shù)目沒(méi)有減少，迭代次數(shù)為16次。圖2(c)的算法②結(jié)果圖中出現(xiàn)了1個(gè)離群點(diǎn)，迭代次數(shù)為5次。圖2(d)的算法③結(jié)果圖中出現(xiàn)了1個(gè)離群點(diǎn)，簇的數(shù)目沒(méi)有減少，迭代次數(shù)為5次，算法平均耗時(shí)約0.25 μs。圖2(e)的算法④結(jié)果與圖2(d)的算法③結(jié)果一致，迭代次數(shù)為16次，算法平均耗時(shí)約為0.28 μs，算法③比算法④的平均耗時(shí)減少了約0.03 μs，迭代次數(shù)減少了11次；圖2(f)的算法⑤分出了5個(gè)簇，與算法③相同，但是由于中迭代次數(shù)很小，導(dǎo)致算法運(yùn)行不充分，部分簇中的點(diǎn)并沒(méi)有完全劃分到理想的簇中，導(dǎo)致存在一些簇的邊緣點(diǎn)距離自身簇較遠(yuǎn)，但是距離其它簇更近。

數(shù)據(jù)集2的數(shù)據(jù)分布特點(diǎn)是一半密集一半稀疏，但密集程度相差較小，對(duì)此數(shù)據(jù)集運(yùn)行上述5種算法其實(shí)驗(yàn)結(jié)果如圖3所示。如圖3(a)所示，本次選擇出來(lái)了6個(gè)簇中心，沒(méi)有離群點(diǎn)，本次實(shí)驗(yàn)中k=6。 圖3(b)的算法①結(jié)果圖中簇的數(shù)目減少了1個(gè)，迭代次數(shù)為12次。圖3(c)的算法②結(jié)果圖中沒(méi)有出現(xiàn)離群點(diǎn)，迭代次數(shù)為16次。圖3(d)的算法③結(jié)果圖中簇的數(shù)目減少了1個(gè)，沒(méi)有出現(xiàn)離群點(diǎn)，迭代次數(shù)為6次，算法平均耗時(shí)約為0.275 μs。圖3(e)的算法④迭代次數(shù)為25次，算法平均耗時(shí)約為0.4 μs，算法③的最終簇?cái)?shù)目比算法④少1個(gè)，算法平均耗時(shí)減少了約0.125 μs，迭代次數(shù)減少了19次；圖3(f)的算法⑤分出了5個(gè)簇，相比于一開(kāi)始給定的k值簇?cái)?shù)量減少了1個(gè)，與算法③相同，但是隨著迭代次數(shù)的增加，由于算法⑤的特性，不斷進(jìn)行簇的分裂與合并，簇的數(shù)目也在不斷發(fā)生變化，與算法③相比，算法⑤的結(jié)果并不穩(wěn)定。

數(shù)據(jù)集3的數(shù)據(jù)分布特點(diǎn)是中央稀疏邊緣密集，但密集程度相差較小，對(duì)此數(shù)據(jù)集運(yùn)行上述5種算法，其實(shí)驗(yàn)結(jié)果如圖4所示。如圖4(a)所示，本次選擇出來(lái)了5個(gè)簇中心和1個(gè)離群點(diǎn)，本次實(shí)驗(yàn)中k=5。 圖4(b)的算法①結(jié)果圖中簇的數(shù)目減少了1個(gè)，迭代次數(shù)為8次。圖4(c)的算法②結(jié)果圖中出現(xiàn)了1個(gè)離群點(diǎn)，迭代次數(shù)為10次。圖4(d)的算法③結(jié)果圖中出現(xiàn)了1個(gè)離群點(diǎn)，簇?cái)?shù)目減少了1個(gè)，迭代次數(shù)為8次，算法平均耗時(shí)約為0.265 μs。圖4(e)的算法④迭代次數(shù)為10次，算法平均耗時(shí)約為0.28 μs，算法③的最終簇?cái)?shù)目比算法④少2個(gè)，算法平均耗時(shí)減少了約0.015 μs，迭代次數(shù)減少了2次；圖4(f)的算法⑤分出了4個(gè)簇，相比于一開(kāi)始給定的k值簇?cái)?shù)量減少了1個(gè)，與算法③相同，但是除了簇?cái)?shù)目不穩(wěn)定以外，隨著迭代次數(shù)增加，簇中心點(diǎn)仍在發(fā)生明顯移動(dòng)，說(shuō)明由于迭代次數(shù)較少，算法⑤結(jié)果仍然在不斷優(yōu)化中。

數(shù)據(jù)集4的數(shù)據(jù)分布特點(diǎn)是均勻分布在其中3個(gè)象限中，最后一個(gè)象限存在單獨(dú)一個(gè)點(diǎn)，對(duì)此數(shù)據(jù)集運(yùn)行上述5種算法，其實(shí)驗(yàn)結(jié)果如圖5所示。如圖5(a)所示，本次選擇出來(lái)了6個(gè)簇中心和1個(gè)離群點(diǎn)，本次實(shí)驗(yàn)中k=6。 圖5(b)的算法①結(jié)果圖中簇的數(shù)目減少了2個(gè)，迭代次數(shù)為21次。圖5(c)的算法②結(jié)果圖中出現(xiàn)了1個(gè)離群點(diǎn)，迭代次數(shù)為29次。圖5(d)的算法③結(jié)果圖中出現(xiàn)了1個(gè)離群點(diǎn)，簇的數(shù)目減少了2個(gè)，迭代次數(shù)為14次，算法平均耗時(shí)約為0.335 μs。圖5(e)的算法④迭代次數(shù)為17次，算法平均耗時(shí)約為0.405 μs，由于離群點(diǎn)的影響，導(dǎo)致這個(gè)離群點(diǎn)成為了一個(gè)單獨(dú)的簇，算法③的最終簇?cái)?shù)目比算法④少2個(gè)，平均耗時(shí)減少了約0.07 μs，迭代次數(shù)減少了3次；圖5(f)的算法⑤分出了5個(gè)簇，相比于一開(kāi)始給定的k值簇?cái)?shù)量減少了1個(gè)，比算法③的簇多1個(gè)，由于離群點(diǎn)的影響，這個(gè)離群點(diǎn)被錯(cuò)誤歸為了其中的某個(gè)簇，并且在算法⑤反復(fù)分裂和合并簇的過(guò)程中，這個(gè)離群點(diǎn)也被反復(fù)歸為不同的簇，說(shuō)明離群點(diǎn)對(duì)算法⑤的影響大，而算法③一開(kāi)始將這個(gè)點(diǎn)標(biāo)記為離群點(diǎn)，使得后續(xù)迭代過(guò)程中不會(huì)受到此點(diǎn)的影響。

數(shù)據(jù)集5的數(shù)據(jù)分布特點(diǎn)是中央密集邊緣稀疏，并且密集程度相查較大，對(duì)此數(shù)據(jù)集運(yùn)行上述5種算法，其實(shí)驗(yàn)結(jié)果如圖6所示。如圖6(a)所示，本次選擇出來(lái)了7個(gè)簇中心和5個(gè)離群點(diǎn)，本次實(shí)驗(yàn)中k=7。 圖6(b)的算法①結(jié)果圖中簇的數(shù)目減少了2個(gè)，迭代次數(shù)為14次。圖6(c)的算法②結(jié)果圖中出現(xiàn)了5個(gè)離群點(diǎn)，迭代次數(shù)為24次。圖6(d)的算法③結(jié)果圖中出現(xiàn)了5個(gè)離群點(diǎn)，簇?cái)?shù)目減少了2個(gè)，迭代次數(shù)為5次，算法平均耗時(shí)約為0.28 μs。圖6(e)的算法④迭代次數(shù)為23次，算法平均耗時(shí)約為0.55 μs，由于離群點(diǎn)的影響，導(dǎo)致這個(gè)離群點(diǎn)將其它簇中的點(diǎn)取出，并單獨(dú)構(gòu)成了一個(gè)簇，算法③的最終簇?cái)?shù)目比算法④少2個(gè)，平均耗時(shí)減少了約0.27 μs，迭代次數(shù)減少了18次；圖6(f)的算法⑤分出了6個(gè)簇，相比于一開(kāi)始給定的k值簇?cái)?shù)量減少了1個(gè)，比算法③的簇多1個(gè)，由于數(shù)據(jù)集中心簇的影響，這個(gè)簇與其它簇的邊緣點(diǎn)在算法⑤反復(fù)分裂和合并簇的過(guò)程中，反復(fù)的發(fā)生改變，使得要想得到理想的結(jié)果，需要更大的迭代次數(shù)，而算法③在引力的吸引下，將中間的簇吸引成為空簇，使得這個(gè)簇對(duì)聚類的影響效果較小。

通過(guò)上述實(shí)驗(yàn)對(duì)比可以發(fā)現(xiàn)，基于密度萬(wàn)有引力的K-means改進(jìn)算法在可以對(duì)部分簇中的點(diǎn)進(jìn)行吸引，可能形成空簇，從而減少簇的數(shù)量，與K-menas算法一樣，由于初始點(diǎn)選擇不一樣，聚類的效果也是不一樣的。基于質(zhì)心自適應(yīng)選擇的聚類簇中心選取策略改進(jìn)的K-means算法則是在K-means算法的基礎(chǔ)上自動(dòng)根據(jù)數(shù)據(jù)點(diǎn)的分布情況生成簇中心，無(wú)需預(yù)先給定k值，并且可以識(shí)別出離群點(diǎn)。CASG-means算法結(jié)合了本文中K-means算法的兩種改進(jìn)思路，同時(shí)改進(jìn)了K-means算法因?yàn)閗值和初始簇中心選擇的不確定性，自動(dòng)生成了初始簇中心和離群點(diǎn)，并且還結(jié)合了引力聚類算法，在過(guò)程中自適應(yīng)調(diào)整了簇的數(shù)目。而對(duì)比現(xiàn)有的較為成熟的改進(jìn)算法K-means++算法，迭代次數(shù)和耗時(shí)均有減少，并且可以減少離群點(diǎn)的影響；而對(duì)比ISODATA算法，CASG-means算法能在迭代次數(shù)較小的情況下獲得良好的結(jié)果。

3.3 算法迭代次數(shù)和離群點(diǎn)、簇?cái)?shù)目、耗時(shí)減少對(duì)比

本次實(shí)驗(yàn)在前文所述的30個(gè)隨機(jī)數(shù)據(jù)集上對(duì)普通K-means算法、K-means++算法、ISODATA算法和CASG-means算法做對(duì)比實(shí)驗(yàn)，在計(jì)算普通K-means算法和K-means++算法的迭代次數(shù)時(shí)，由于這兩個(gè)算法每次聚類的迭代次數(shù)都不同，因此每個(gè)數(shù)據(jù)集上取20次普通K-means算法的平均迭代次數(shù)作為本數(shù)據(jù)集普通K-means算法的迭代次數(shù)。

普通K-means算法和CASG-means算法對(duì)比實(shí)驗(yàn)的結(jié)果見(jiàn)表1。通過(guò)實(shí)驗(yàn)可以得出結(jié)論，CASG-means算法相比于普通K-means算法的平均迭代次數(shù)減少了5.19次，減少概率為96.67%，簇?cái)?shù)目平均減少了1.33個(gè)，簇?cái)?shù)目減少的概率為63.33%，離群點(diǎn)的平均個(gè)數(shù)為1.9%，識(shí)別出離群點(diǎn)的概率為73.33%。

表1 普通K-means算法和CASG-means算法對(duì)比

K-means++算法和CASG-means算法對(duì)比實(shí)驗(yàn)的結(jié)果見(jiàn)表2。通過(guò)實(shí)驗(yàn)可以得出結(jié)論，CASG-means算法相比于K-means++算法的平均迭代次數(shù)減少了5.29次，平均耗時(shí)減少了0.044 μs。

表2 K-means++算法和CASG-means算法對(duì)比

ISODATA算法和CASG-means算法對(duì)比實(shí)驗(yàn)的結(jié)果見(jiàn)表3。通過(guò)實(shí)驗(yàn)可以得出結(jié)論，CASG-means算法相比于ISODATA算法的平均簇?cái)?shù)目減少多了0.2個(gè)。

表3 ISODATA算法和CASG-means算法對(duì)比

4 結(jié)束語(yǔ)

本文提出了一種基于質(zhì)心自適應(yīng)選取的密度萬(wàn)有引力聚類(CASG-means)算法，該算法基于以下2點(diǎn)進(jìn)行改進(jìn)：①通過(guò)質(zhì)心自適應(yīng)選擇的方法自適應(yīng)尋找k值和初始簇心點(diǎn)，并判斷出離群點(diǎn)；②使用密度萬(wàn)有引力改進(jìn)公式，代替歐式距離公式，使得各個(gè)點(diǎn)之間通過(guò)引力相互聚類，并且隨著部分簇中的數(shù)據(jù)點(diǎn)被其它簇全部吸引，最終形成空簇，簇的數(shù)量減少，減少了迭代次數(shù)。實(shí)驗(yàn)結(jié)果表明，CASG-means算法相比于普通K-means算法迭代次數(shù)平均減少了5.19次，減少概率為96.67%，簇?cái)?shù)目平均減少了1.33個(gè)，簇?cái)?shù)目減少的概率為63.33%，離群點(diǎn)的平均個(gè)數(shù)為1.9%，識(shí)別出離群點(diǎn)的概率為73.33%；CASG-means算法相比于K-means++算法平均迭代次數(shù)減少了5.29次，算法平均耗時(shí)減少了0.044 μs；CASG-means算法相比于ISODATA算法簇?cái)?shù)目平均減少0.2個(gè)，因此CASG-means的聚類的效果相比于其它成熟的K-means改進(jìn)算法更加理想。在未來(lái)的研究中，將從算法耗時(shí)、離群點(diǎn)識(shí)別準(zhǔn)確度、密度萬(wàn)有引力公式優(yōu)化等角度出發(fā)對(duì)CASG-means算法進(jìn)行優(yōu)化。