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

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

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

0 引 言

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

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

1 基于密度萬有引力的K-means改進算法

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

(1)

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

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

(2)

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

(3)

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

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

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

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

(4)

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

算法1：基于密度萬有引力的K-means改進算法

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

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

步驟1 選取K個點作為初始聚類簇中心。

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

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

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

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

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

普通K-means算法在聚類時使用的是歐氏距離來對簇進行劃分，這種辦法只考慮了兩點之間的距離，算法1使用改進的萬有引力密度公式替代了普通K-means算法的歐式距離公式，使得在聚類過程中不僅考慮了兩點之間的距離，還考慮了當前簇的大小對點的影響。當前簇密度越大，與點距離越近，則該簇對點存在的吸引作用就越大，最終將此點聚類。

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

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

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

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

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

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

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

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

(5)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 CASG-means算法改進的步驟

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

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

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

步驟1 執(zhí)行算法2，得到k個簇和狀態(tài)標記不同的點。

步驟2 對每個標記狀態(tài)t=1的點，直接分配給步驟1最終所在的簇中，并更新每個簇的簇中心。

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

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

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

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

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

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

3 實驗與分析

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

3.1 實驗環(huán)境

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

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

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

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

圖2 5種算法在數(shù)據(jù)集1上的對比實驗

圖3 5種算法在數(shù)據(jù)集2上的對比實驗

圖4 5種算法在數(shù)據(jù)集3上的對比實驗

圖5 5種算法在數(shù)據(jù)集4上的對比實驗

圖6 5種算法在數(shù)據(jù)集5上的對比實驗

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

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

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

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

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

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

3.3 算法迭代次數(shù)和離群點、簇數(shù)目、耗時減少對比

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

普通K-means算法和CASG-means算法對比實驗的結(jié)果見表1。通過實驗可以得出結(jié)論，CASG-means算法相比于普通K-means算法的平均迭代次數(shù)減少了5.19次，減少概率為96.67%，簇數(shù)目平均減少了1.33個，簇數(shù)目減少的概率為63.33%，離群點的平均個數(shù)為1.9%，識別出離群點的概率為73.33%。

表1 普通K-means算法和CASG-means算法對比

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

表2 K-means++算法和CASG-means算法對比

ISODATA算法和CASG-means算法對比實驗的結(jié)果見表3。通過實驗可以得出結(jié)論，CASG-means算法相比于ISODATA算法的平均簇數(shù)目減少多了0.2個。

表3 ISODATA算法和CASG-means算法對比

4 結(jié)束語

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