基于ARIA的K均值聚類算法研究

王雷， 劉小芳， 趙良軍

(四川輕化工大學(xué)a.自動化與信息工程學(xué)院;b.計算機學(xué)院, 四川自貢643000)

引言

聚類分析是數(shù)據(jù)挖掘的一種重要技術(shù)手段，而Kmeans算法是其中最常用的方法之一。曹躍等[1]用Kmeans算法來優(yōu)化鐵礦預(yù)配料智能調(diào)度；劉倩穎等[2]用Kmeans算法與BP神經(jīng)網(wǎng)絡(luò)相結(jié)合的方法來進行辦公建筑逐時電負荷預(yù)測；王亞濤等[3]將Kmeans算法和加權(quán)K近鄰算法相結(jié)合來進行室內(nèi)WIFI的定位。傳統(tǒng)Kmeans算法的聚類結(jié)果在很大程度上取決于初始聚類中心，但通常對于未知數(shù)據(jù)并不能很好地確定其最優(yōu)的初始中心點，因此，Kmeans算法并不總是收斂于全局最優(yōu)解，這將對研究造成嚴重的誤導(dǎo)。目前，已經(jīng)有許多研究著力于解決Kmeans算法易陷入局部最優(yōu)解的問題，如洪月華用[4]MPI蜂群算法對Kmeans算法進行優(yōu)化；廖武代等人[5]提出了一種基于人工蜂群優(yōu)化的K均值聚類算法；此外，Chen Z[6]、Lee J[7]和Diesposti R[8]等人都從群算法具有優(yōu)秀的全局搜索能力出發(fā)，將其與Kmeans算法相結(jié)合，以改進Kmeans算法易陷入局部最優(yōu)解的缺點。

針對Kmeans算法聚類過程中因計算各個數(shù)據(jù)之間的歐氏距離而耗時和易陷入局部最優(yōu)解的特點，本文將自適應(yīng)半徑免疫算法(Adaptive Radius Immune Algorithm，ARIA)[9]與傳統(tǒng)K均值聚類(Kmeans)算法結(jié)合，提出了一種ARIA-Kmeans算法。首先用ARIA算法對原始包含大量冗余信息的數(shù)據(jù)進行壓縮，獲得能夠代表原始數(shù)據(jù)分布以及密度信息的內(nèi)部鏡像數(shù)據(jù)，再用Kmeans算法對這個精簡數(shù)據(jù)集進行聚類，從而能以更少的時間和空間消耗找到全局最優(yōu)解。

1 算法簡介

1.1 自適應(yīng)半徑免疫算法(ARIA)

生物的免疫系統(tǒng)是一種自適應(yīng)的、自組織的、分布式的系統(tǒng)，是一種能夠抵擋外來病原體且具有復(fù)雜功能的防御系統(tǒng)，它的一大特點就是用有限的資源對數(shù)量龐大且種類多變的病毒入侵進行有效地應(yīng)對。受此特性的啟發(fā)，人們設(shè)計了一種對多峰值函數(shù)進行多峰值搜索和全局尋優(yōu)的新型算法，稱為人工免疫算法。人工免疫網(wǎng)絡(luò)算法在全局優(yōu)化、數(shù)據(jù)壓縮領(lǐng)域有著舉足輕重的地位，其原型是由Jeme N K[10]提出的，在此基礎(chǔ)上，Catro De[11]提出了aiNet算法；Fabricio O等人[12]對aiNet算法的優(yōu)勢與不足進行了詳細闡述，指出aiNet算法壓縮數(shù)據(jù)時未充分考慮數(shù)據(jù)密度信息。George B等人[9]在aiNet的基礎(chǔ)上考慮數(shù)據(jù)的密度信息，提出了ARIA算法。

ARIA算法是一種能夠從高冗余度數(shù)據(jù)中提取包含該數(shù)據(jù)集密度和空間分布信息的數(shù)據(jù)集的算法，與傳統(tǒng)的主成分提取算法相比，其優(yōu)點在于在壓縮數(shù)據(jù)的同時，能夠保留原始數(shù)據(jù)的密度信息[9]。因此，用ARIA算法處理獲得的數(shù)據(jù)更能代表原始數(shù)據(jù)的特征，有利于Kmeans算法進行全局最優(yōu)解的搜索。

在ARIA算法中，Ag表示抗原集合，Ab表示抗體集合，Ra表示各個抗體的抑制半徑，r*為半徑乘數(shù)，mi為變異比率，decay*為衰減系數(shù)，E為密度估計的鄰域半徑，gen*代表迭代的代數(shù)，dim為輸入?yún)?shù)(原始數(shù)據(jù))的維度，自適應(yīng)半徑免疫算法的實現(xiàn)步驟如下：

(1) 參數(shù)初始化，隨機生成初始抗體種群Ab。

(2) 對于大小為N的抗原集合AgN×d∈Rd中的每個抗原ag，從當(dāng)前的抗原集合Ag中選擇出與其具有最高親和力的個體，再根據(jù)式(1)進行超突變：

ab*=ab+mi×rand×(ag-ab)

(1)

其中，rand是一個(0,1)之間的隨機數(shù)。

(3) 更新抗體ab，ab=ab*。

(4) 未被刺激到的抗體淘汰。

(5) 對每個抗體計算其鄰域密度den，該密度為以ab為球心，E為半徑的超球體內(nèi)部抗體ag的數(shù)量，并記錄下最大密度為denmax。

(6) 計算更新每個抗體ab的壓縮半徑Ra：

(2)

(7) 根據(jù)式(3)計算抗體集合中各個抗體之間的歐氏距離，表征其親密度，距離越大親密度越小：

(3)

(8) 比較djk與max(abj,abk)，如果兩抗體之間的距離小于它們各自抑制半徑中較大的一個，就淘汰掉抑制半徑較大的一個，將最后沒被淘汰的抗體加入記憶抗體集合Abm。

(9) 更新鄰域半徑，E=average(Ra)，即新的鄰域半徑E為記憶抗體抑制半徑Ra的平均值。

mi=decay*×mi

(4)

否則生成新的集合Ab=Abm+Abd。

(11) 重復(fù)上述的步驟(2)～(10)，直到達到迭代次數(shù)，輸出表征抗原集合內(nèi)部鏡像數(shù)據(jù)的記憶抗體集合Abm。

1.2 K均值(Kmeans)聚類算法

給定Kmeans算法的數(shù)據(jù)集，X={x1,x2,…,xm}，其中xi(i=1,2,…,m)是d維的數(shù)據(jù)，即xi∈Rd，代表數(shù)據(jù)集X中每個數(shù)據(jù)有d個屬性，xi={xi1,xi2,…,xid}。Kmeans算法要將數(shù)據(jù)劃分為k個簇，即分為k類，可以表示為C={C1,C2,…,Ck}，每個聚類中心為Cj(j=1,2,…,k)。k個聚類中心必須滿足以下條件：

(1)Cj≠φ

其中，i≠j，Ci∩Cj=φ。按照上述約束條件進行K均值聚類。

(1) 隨機產(chǎn)生k個聚類中心C1,C2,…,Ck∈Rd，作為Kmeans算法的初始聚類中心。

(2) 根據(jù)式(5)計算每一個樣本xi的所屬類別Ci，即樣本所屬類別為與其歐氏距離最小的聚類中心代表的類別：

(5)

(3) 根據(jù)式(6)更新聚類中心，將屬于Ci的數(shù)據(jù)xi求幾何平均，獲得新的聚類中心：

(6)

(4) 不斷重復(fù)步驟(2)和(3)，直至目標(biāo)函數(shù)解收斂：

(7)

其中，xi為被劃分到類別中心cj的數(shù)據(jù)樣本，其意義是描述所有數(shù)據(jù)樣本到它們所屬聚類中心的歐氏距離的平方和，其值越小表示聚類劃分結(jié)果越緊湊和獨立，聚類的效果也就越好[13]。

2 ARIA-Kmeans算法實現(xiàn)

2.1 算法思路簡介

根據(jù)免疫網(wǎng)絡(luò)和Kmeans算法的應(yīng)用背景，建立研究數(shù)據(jù)集X={x1,x2,…,xm}，其中xi(i=1,2,…,m)是d維數(shù)據(jù)，代表一個抗原對象。依據(jù)ARIA的原理，隨機創(chuàng)建P個與xi同型的數(shù)據(jù)作為抗原，在每一次迭代過程中，從抗體集合中選擇出與抗原歐氏距離最小的個體對抗原進行表征。完成一次抗原表征之后，淘汰未被刺激的抗原，再計算抗原與抗原之間的歐氏距離，若兩個抗原之間的歐式距離小于它們較大的抑制半徑，則淘汰抑制半徑大的抗體，將其作為冗余抗體信息的表征，由此最終得到能夠表征抗原屬性的抗體集合。K均值算法將數(shù)據(jù)集X劃分成k個簇，在獲得抗體的基礎(chǔ)上進行多次聚類，選擇出性能最好的中心點作為初始中心點，將Kmeans算法推廣到完整數(shù)據(jù)集上，即可獲得目標(biāo)的聚類結(jié)果。

2.2 ARIA-Kmeans算法的實現(xiàn)步驟

(1) 參數(shù)初始化，并生成隨機的抗體集合。

(2) 根據(jù)式(1)和式(2)對初始抗體進行選擇、刺激、超突變，未被刺激的抗體被淘汰。

(3) 根據(jù)式(3)淘汰集合中冗余的抗體，并更新抑制半徑Ra和鄰域半徑E。

(5) 重復(fù)步驟(2)～(4)，直到達到迭代次數(shù)，輸出記憶抗體集合Abm。

(6) Kmeans算法在Abm上進行聚類，并記錄每一次迭代，由式(7)計算得到的目標(biāo)函數(shù)值，直到達到最大迭代次數(shù)。

(7) 選用目標(biāo)函數(shù)值最小的聚類中心，作為初始中心。

(8) 擴展到完整數(shù)據(jù)集，獲得更優(yōu)的聚類中心。

ARIA-Kmeans算法實現(xiàn)流程如圖1 所示。

圖1 ARIA-Kmeans算法實現(xiàn)流程圖

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

ARIA-Kmeans算法是從全局最優(yōu)、運算時間效率、聚類結(jié)果穩(wěn)定度的角度對Kmeans算法進行優(yōu)化。實驗中，將對ARIA-Kmeans和傳統(tǒng)Kmeans算法從目標(biāo)函數(shù)收斂值、運行時間、分類正確率及其穩(wěn)定度4個方面進行對比測試；目標(biāo)函數(shù)收斂值越小越好；運行時間指兩個算法分別用于聚類的時間。實驗環(huán)境：計算機主機i7-6700HQ CPU，主頻2.60 GHz，運行內(nèi)存16 GB；仿真軟件為Matlab2016b。ARIA算法對數(shù)據(jù)進行預(yù)處理時，抗體進化代數(shù)gen*=50，衰減因子decay*=0.8，突變因子mi=1.0，鄰域半徑E的初始值隨機產(chǎn)生，抑制半徑Ra在計算過程中自適應(yīng)調(diào)節(jié)。

用4組不同大小的數(shù)據(jù)集測試算法的目標(biāo)函數(shù)收斂值、時間效率、分類正確率及其穩(wěn)定度，它們分別包含1500、2500、5000、10 000個數(shù)據(jù)樣本，每一組按高斯分布Gussian=(μ,Cov)，其中參數(shù)向量μ為均值，參數(shù)矩陣Cov為協(xié)方差，聚類中心數(shù)為5。5種高斯分布分別如下：

3.1 算法目標(biāo)收斂值比較

各樣本數(shù)下，Kmeans和ARIA-Kmeans算法的目標(biāo)收斂值如圖2 ～圖5 所示，其中縱坐標(biāo)為目標(biāo)函數(shù)收斂值，橫坐標(biāo)為迭代次數(shù)。

圖2 樣本1500時Kmeans和ARIA-Kmeans算法的收斂值

圖3 樣本2500時Kmeans和ARIA-Kmeans算法的收斂值

圖4 樣本5000時Kmeans和ARIA-Kmeans算法的收斂值

圖5 樣本10 000 時Kmeans和ARIA-Kmeans算法的收斂值

從圖2 ～圖5 可知，在50次聚類中，Kmeans算法的收斂值不穩(wěn)定，時大時小，而ARIA-Kmeans算法的收斂值趨向于一個固定值，目標(biāo)函數(shù)收斂的穩(wěn)定性好；傳統(tǒng)的Kmeans算法由于初始中心不確定，目標(biāo)函數(shù)極易收斂于局部最優(yōu)，從而得不到理想的聚類結(jié)果，而ARIA-Kmeans算法是在預(yù)先對原始數(shù)據(jù)進行壓縮得到其內(nèi)部鏡像數(shù)據(jù)來表征其整體特性之后，再用Kmeans算法對此內(nèi)部鏡像數(shù)據(jù)進行多次聚類，就可以搜索得到鏡像數(shù)據(jù)的最優(yōu)聚類中心，然后將此最優(yōu)聚類中心作為Kmeans算法的初始中心擴展到完整數(shù)據(jù)集，這樣可逼近全局最優(yōu)的聚類效果，即收斂函數(shù)最小。由此可見ARIA-Kmeans算法解決了傳統(tǒng)Kmeans算法對初始聚類中心不確定而導(dǎo)致的局部最小問題。

3.2 算法運行時間比較

對上述4組數(shù)據(jù)進行試驗，Kmeans和ARIA-Kmeans算法的運行時間如圖6 所示，其中，橫坐標(biāo)表示樣本的數(shù)量，縱坐標(biāo)表示目標(biāo)函數(shù)收斂所用的時間。

從圖6 可知，樣本數(shù)為1500、2500、5000、10 000時，ARIA-Kmeans算法目標(biāo)函數(shù)收斂的時間均小于傳統(tǒng)Kmeans算法，且隨著數(shù)據(jù)集的增大，兩種算法消耗的時間差值越來越大，說明ARIA-Kmeans算法在運行時具有較高的時間效率。

圖6 Kmeans和ARIA-Kmeans算法運行時間

3.3 算法分類正確率和穩(wěn)定性比較

選擇樣本大小為5000的數(shù)據(jù)集?？紤]到傳統(tǒng)Kmeans對初始中心點敏感，且初始中心點隨機性較大，因此，聚類次數(shù)分別選擇了20次、50次、100次。Kmeans和ARIA-Kmeans的平均分類正確率見表1。

表1 Kmeans和ARIA-Kmeans算法的平均分類正確率

用傳統(tǒng)Kmeans進行的多次聚類中，由于其初始中心點隨機產(chǎn)生，聚類結(jié)果的優(yōu)劣程度參差不齊，少數(shù)情況下獲得理想的初始聚類中心時，才能擁有較高的分類正確率。在實驗中，兩種算法獲得的最高分類正確率是92.04%。

從表1可知，傳統(tǒng)Kmeans算法多次迭代的分類平均正確率低于90.00%，而ARIA-Kmeans算法的分類平均正確率都穩(wěn)定在91.95%左右，且接近最高正確率92.04%。由此說明ARIA-Kmeans算法的分類正確率不僅穩(wěn)定，而且是穩(wěn)定在最高正確率附近；較傳統(tǒng)Kmeans算法而言， ARIA-Kmeans算法能獲得較高的分類正確率，且分類性能穩(wěn)定。

4 結(jié)束語

本文針對傳統(tǒng)Kmeans算法對初始聚類中心敏感，易陷入局部最優(yōu)和對大數(shù)據(jù)集聚類速度慢的缺點，提出了一種ARIA-Kmeans算法。實驗結(jié)果表明，ARIA-Kmeans算法解決了傳統(tǒng)Kmeans算法易陷入局部最小的問題。相對于傳統(tǒng)的Kmeans算法，ARIA-Kmeans算法能找到更優(yōu)聚類中心，在保證分類正確率的前提下，提高了算法運行的效率和穩(wěn)定性，并且聚類數(shù)據(jù)集越大，這種優(yōu)勢越明顯。