王雷， 劉小芳， 趙良軍

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

引言

聚類分析是數據挖掘的一種重要技術手段，而Kmeans算法是其中最常用的方法之一。曹躍等[1]用Kmeans算法來優(yōu)化鐵礦預配料智能調度；劉倩穎等[2]用Kmeans算法與BP神經網絡相結合的方法來進行辦公建筑逐時電負荷預測；王亞濤等[3]將Kmeans算法和加權K近鄰算法相結合來進行室內WIFI的定位。傳統(tǒng)Kmeans算法的聚類結果在很大程度上取決于初始聚類中心，但通常對于未知數據并不能很好地確定其最優(yōu)的初始中心點，因此，Kmeans算法并不總是收斂于全局最優(yōu)解，這將對研究造成嚴重的誤導。目前，已經有許多研究著力于解決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算法相結合，以改進Kmeans算法易陷入局部最優(yōu)解的缺點。

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

1 算法簡介

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

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

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

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

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

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

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

(1)

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

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

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

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

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

(2)

(7) 根據式(3)計算抗體集合中各個抗體之間的歐氏距離，表征其親密度，距離越大親密度越?。?/p>

(3)

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

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

mi=decay*×mi

(4)

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

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

1.2 K均值(Kmeans)聚類算法

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

(1)Cj≠φ

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

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

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

(5)

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

(6)

(4) 不斷重復步驟(2)和(3)，直至目標函數解收斂：

(7)

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

2 ARIA-Kmeans算法實現

2.1 算法思路簡介

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

2.2 ARIA-Kmeans算法的實現步驟

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

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

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

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

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

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

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

ARIA-Kmeans算法實現流程如圖1 所示。

圖1 ARIA-Kmeans算法實現流程圖

3 實驗結果與分析

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

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

3.1 算法目標收斂值比較

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

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

3.2 算法運行時間比較

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

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

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

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

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

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

用傳統(tǒng)Kmeans進行的多次聚類中，由于其初始中心點隨機產生，聚類結果的優(yōu)劣程度參差不齊，少數情況下獲得理想的初始聚類中心時，才能擁有較高的分類正確率。在實驗中，兩種算法獲得的最高分類正確率是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 結束語

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