基于混沌PSO的大數據智能加權K均值聚類算法

劉 洪 基

(楚雄師范學院經濟與管理學院 云南 楚雄 675000)

0 引 言

當前，工業過程、移動互聯網、社交網絡和物聯網生成大量數據，并推動大數據應用的快速發展[1-2]。在各種大數據應用中，都有許多高維多視圖數據，高維多視圖數據通常以各種來源獲得的多個特征空間和不同結構進行描述[3]。傳統聚類方法將所有視圖作為一個統一的變量集，對此類具有數量、種類、速度、準確性和價值等多視圖的數據聚類效果較差[4]。在大數據環境下，如何實現高維多視圖數據的聚類以適應各種復雜的、大規模的應用是最具挑戰性的問題之一[5]。

由于大數據的廣泛應用，多視圖數據的聚類吸引了許多研究人員的關注。文獻[6]將多視圖任務的非監督特征選擇保留在集群結構中，然后提出一種交替算法來實現該結構。對于多視圖聚類問題，文獻[7]提出了一種新穎的多視圖關聯傳播算法，該算法特別適合于對兩個以上的視圖進行聚類。文獻[8]提出了局部自適應聚類(Local Adaptive Clustering,LAC)算法，該算法為每個聚類的每個特征分配權重，通過使用迭代算法最小化其目標函數。文獻[9]提出了一種多視圖數據的自動兩級變量加權K均值(Two-variables Weighted K-means,TWKM)聚類算法，該算法可以同時計算視圖和單個變量的權重，但是很容易導致在單個特征和單個視圖上具有較大權重的聚類，因此權重的分布不平衡。然而，上述算法主要關注于具有視圖方式關系的問題，而忽略了數據集高維特征的重要性，使得聚類結果與實際應用存在較大差異，此外，上述方法由于聚類性能的限制對大數據應用中更復雜的高維數據的聚類效果較差。

為了解決實際大數據應用中的高維多視圖數據聚類問題，并且進一步提升該聚類算法的聚類性能，提出一種基于混沌粒子群優化算法(Chaos Particle Swarm Optimization,CPSO)的智能加權K均值(Intelligent Weighted K-means,IWKM)聚類算法。

1 相關理論

1.1 加權K均值聚類算法

集群是數據對象的集合，這些數據對象在同一集群中彼此相似，但與其他集群中的對象不同[10]。給定數據對象集X=[xi,j]N×D，N是數據對象的數量，D是數據對象的維度。也就是說，數據對象具有D個特征。聚類問題試圖找到X的k分區。簇的中心是Z=[zk,j]C×D。U=[ui,k]N×C，主要通過模糊劃分矩陣描述對象是某些集群的隸屬度[9]。

作為具有敏感初始聚類中心的聚類算法，K均值被廣泛用于實際應用中，例如圖像分割和數據挖掘[11-12]。K均值的目標是找到一個分區，以最小化帶簇的平方和。在聚類過程中，用以下式子解決樣本劃分任務：

(1)

式中：U被定義為分區矩陣；ui,k是一個二進制變量；Z={Z1,Z2,…,Zk}是一組向量，表示k個簇的質心；(xi,j-zk,j)2是第i個對象與第j個變量上的第k個簇的中心之間的距離度量。

在經典的K均值聚類算法中，所有特征均具有相同的權重，在諸如消費者細分之類的聚類問題中，所有特征均得到同等對待。實際上，在許多實際應用中，數據集中不同特征對聚類的影響是不同的，因此有必要為不同特征分配不同的權重。K均值類型聚類中的自動變量加權是加權K均值聚類算法，目標函數為:

(2)

式中：U被定義為n×k分區矩陣；WF是特征的權重;β表示權重函數維度。

1.2 軟子空間聚類算法

軟子空間聚類算法根據維度在發現相應聚類中的作用來確定維度的子集。維度的貢獻是通過在聚類過程中分配給維度的權重來衡量的。文獻[13]提出了一種軟子空間聚類算法，目標函數的建模為：

(3)

式中：WCF=wcfk,j是每個集群中每個屬性的權重。

2 IWKM算法

2.1 高維多視圖數據的聚類

用于將X劃分為具有視圖和特征權重的集群的聚類建模為以下目標函數的最小化。

minFitness(U,Z,WV,WF)=

(4)

式中：U=[ui,k]N×C是一個N×C分區矩陣，其元素ui,k為二進制，其中ui,k=1表示對象i已分配給集群k;Z=[zk,j]C×D是一個N×C矩陣，其元素zk,j表示簇k的第j個特征;WV=[wvt]T是T視圖的權重;WF=[wfj]j∈Viewt是視圖t下的特征權重;wvtwfj(xi,j-zk,j)2是第i個對象與第k個簇的中心之間的第j個特征的加權距離度量;wvtwfj(zk,j-oj)2是第k個聚類與平均聚類中心之間的第j個特征的加權距離度量，oj是C個聚類的平均聚類中心。該值描述集群之間的耦合程度，越大表示相異性越大。

2.2 CPSO和粒子編碼

(5)

(6)

ω=ωmax-(ωmax-ωmin)×g/gmax

(7)

粒子編碼是使用粒子群搜索最佳解的前提[14]。在IWKM中，初始聚類中心、視圖權重和特征權重被編碼為粒子表示形式。每個粒子由F×C+T+F維實數向量編碼。F是聚類問題中對象的特征數。群中的第i個粒子被編碼為：

(8)

2.3 精確擾動和CPSO

為了避免局部最優和過早收斂，利用跳躍或突變在豐富群體智能中粒子的搜索行為方面具有很大的優勢[15]。在CPSO中，混沌邏輯序列擾動被用于幫助粒子脫離局部最優并獲得更好的搜索質量，具有確定性、遍歷性和隨機性，將其定義為式(9)。

x(t+1)=r·x(t)·(1-x(t))

r∈N,x(0)∈[0,1]

(9)

式中：r是控制參數，x是變量，r=4，t=0,1,2,…。

本文將CPSO的精確擾動概括為以下過程的相互作用。

步驟1創建合適的擾動粒子：為了減少粒子搜索過程中總體穩定性的損失和CPU的計算代價，通過簡單的隨機抽樣方法從總共N_S個粒子中隨機選擇N_S/K_spark個粒子作為擾動對象。K_spark是Apache Spark中的工作程序節點數。

步驟2精確擾動時間：擾動的時間是粒子群過早收斂的時間。pBest和gBest之間的平均距離用于判斷粒子是否處于過早收斂狀態，記為式(10)。

(10)

式中：N_S和dim是群的粒子數和粒子的維度；Q_d代表過早收斂的閾值；如果d(pBest,gBest)≤Q_d，則出現過早收斂和局部最優，然后應采用適合N_S/K_spark粒子的擾動。

步驟3精確擾動維度：由于粒子具有一個以上的維，因此根據慣性的優先級，優先選擇一些具有較高慣性的維來進行擾動。第j維中的pBest和gBest的慣性可以由均方差給出，分別記為式(11)和式(12)。

Q_pBest

(11)

Q_gBest

(12)

式中：N_S和m是群的粒子數和當前迭代數。如果sd(pBestj)≤Q_pBest或sd(gBestj)≤Q_gBest，則第j維的pBest、gBest是惰性的，需要進行擾動。其中Q_pBest和Q_gBest分別是pBest和gBest的惰性閾值。

2.4 IWKM流程

IWKM算法的流程如圖1所示。

圖1 IWKM算法流程

3 實驗評估

3.1 測試環境和spark

在分布式和并行計算環境中，Apache Spark是一個重要的開源集群計算框架，它為隱式數據并行和容錯的整個集群編程提供了一個接口[16]。Spark的彈性分布式數據集(RDD)是分布式程序的工作集，可以提供受限形式的分布式共享內存。因此，本文選擇了Apache Spark作為大數據應用中IWKM的計算平臺。在本文實驗中，對IWKM進行了測試，并在包括Apache Spark和Single Node在內的各種計算環境中進行了比較。Single Node配備了Intel Core i5- 4210M 2.6 Hz，3.8 GB RAM和Ubuntu 14.04LTS操作系統。

Apache Spark有一個主節點，配置為Intel Core i7- 3820@3.6 GHz，64 GB DDRIII和1 TB高效云磁盤，十個工作節點，相關配置為Intel Xeon E5- 2690@2.9 GHz，16 GB DDRIII和500 GB高效云磁盤，應用版本為Apache Spark 1.6.0。

3.2 測試數據集

為了評估本文算法的性能，還通過RI(Rand Index)、JC(Jaccard coefficient)和Folk的評估指標，將IWKM與LAC、親和傳播(Affinity Propagation,AP)[17]、歸一化分割(Normalized Cut,Ncut)[11]、密度聚類(Density Clustering,DC)[18]和TWKM進行了比較。為了公平比較，PSO和CPSO使用相同的30人口規模和150個適應度值進行評估。IWKM和其他五種算法已在5個高維多視圖數據集中進行了測試，其中包括多特征數據集、互聯網廣告數據集、Spambase數據集、圖像分割集和心電圖數據集。這些數據集及其應用的基本信息如表1所示。

表1 高維多視圖數據集的特征

多特征數據集是從荷蘭實用程序圖的集合中提取的手寫數字數據集，其中包含2 000個屬于10類(0～9)的數字對象。每類有200個對象。每個對象均由649個特征表示，這些特征分為以下六個視圖：1) Mfeat-fou視圖包含76個字符形狀的傅里葉系數；2) Mfeat-fac視圖包含216個配置文件相關性；3) Mfeat-kar視圖包含64個Karhunen-Love系數；4) Mfeat-pix視圖包含240個像素窗口；5) Mfeat-zer視圖包含47個Zernike時刻；6) Mfeat-mor視圖包含6個形態特征。

互聯網廣告數據集包含來自各種網頁的3 279幅圖像，這些圖像被分類為廣告或非廣告。有20幅圖片的值缺失。我們的實驗在3 259個實例上進行，刪除了缺失值的實例。在六個視圖中描述了實例。視圖1包含3種圖像幾何形狀(寬度、高度和長寬比)；視圖2在包含圖片的頁面網址(基本網址)中包含457個詞組；視圖3包含495個圖像URL的短語(圖像URL)；視圖4在圖像所指向的頁面的URL中包含472個短語(目標URL)；視圖5包含111個錨文本；視圖6包含19個圖像的文本alt(替代)html標簽(alt文本)。

Spambase是一個數據集，其垃圾郵件的收集來自郵局主管和具有現場垃圾郵件的個人，非垃圾郵件的收集來自現場工作和個人電子郵件，其中包含4 601個屬于2類(垃圾郵件、非垃圾郵件)的對象。每個對象都由57個要素表示，這些要素分為三個視圖，分別是單詞頻率視圖、字符頻率視圖和大寫游程視圖。1) 單詞頻率視圖包含word類型的48個連續實數屬性；2) 字符頻率視圖包含char類型的6個連續實數屬性；3) 大寫游程視圖包含測量連續大寫字母序列長度的3個連續實數屬性。

在該數據集中，從7幅室外圖像的數據庫中隨機抽取了2 310個實例。手動分割圖像以為每個像素創建一個分類。每個實例都是一個3×3的區域。數據集包含19個特征，可分為2個視圖：形狀視圖包含9個有關形狀信息的特征，而RGB視圖包含10個有關顏色信息的特征。

自動處理2 126例胎兒心電圖(Cardiotocograms,CTG)并測量相應的診斷特征。CTG還由三位專家產科醫生進行分類，并為他們每個人分配了共識分類標簽。分類既涉及形態學模式(A，B，C，…)，也涉及胎兒狀態(N，S，P)。因此，該數據集可用于10類或3類實驗。在此實驗中，將其用作3類數據集。在數據集中，可以將21個要素劃分為3個視圖：每秒指標、可變性視圖和直方圖視圖。

3.3 評估指標

本文使用的三個外部標準可以定義如下：

(1)RI=(SS+DD)/(SS+SD+DS+DD)，RI越大，說明聚類結果與真實情況越吻合。

(2)JC=SS/(SS+SD+DS)，該指標用于衡量兩個數據的相似度，JC越大，相似度越大，聚類精度越高。

3.4 參數分析

為了分析3個參數(Q_d、Q_gbest和Q_pBest)對高維多視圖數據的聚類性能的影響，在Single Node上對3個數據集(Mfeat數據集、互聯網廣告數據集Spambase數據集)中的IWKM進行了測試。為了減少統計錯誤，所有數據集均獨立進行了10次模擬。

根據過早收斂的閾值評估，將Q_d在Mfeat和Spambase數據集中以5步長設置在[5，45]。將Q_d在互聯網廣告數據集中以3步長設置在[2，20]。關于它們的平均評價指標的統計結果如圖2所示?？梢钥闯?，當Q_d分別選擇為30、8和25時，IWKM具有在Single Node上的3個數據集中進行聚類的最佳性能。參數Q_gbest和Q_pBest是維度慣性的閾值，用于測量每個維度中位置的可感知變化是否發生。三個數據集上的參數Q_gbest和Q_pBest也與Q_d類似地進行分析。關于它們的平均評價指標的統計結果分別示于圖3和圖4。由于在Spambase中JC和RI的值幾乎相等，因此JC和RI的曲線重疊。根據參數分析的結果，將選擇最佳參數值Q_d、Q_gbest和Q_pBest并在下一個實驗中進行測試。

(a) 多特征數據集

(b) 互聯網廣告數據集

(c) Spambase數據集圖2 參數Q_d變化曲線

(a) 多特征數據集

(b) 互聯網廣告數據集

(c) Spambase數據集圖3 參數Q_gbest變化曲線

(a) 多特征數據集

(b) 互聯網廣告數據集

(c) Spambase數據集圖4 參數Q_pbest變化曲線

3.5 PSO和CPSO的比較

為了驗證CPSO在IWKM中聚類中心、視圖權重和特征權重的優化，我們在Single Node上的三個高維多視圖數據集中測試了CPSO和PSO。通過CPSO和PSO將數據集運行10次，圖5記錄并比較了各種算法的平均結果。在CPSO中，提出一種精確的擾動，包括合適的擾動粒子、精確的擾動時間和擾動維數，以提高優化性能?？梢钥闯?，CPSO可以在Single Node上的所有三個高維多視圖數據集中實現更好的解決方案精度，并盡早獲得最佳解決方案。顯然，CPSO在IWKM集群方面比PSO具有更好的性能。因此，可以得出結論，作為一種重要的優化方法，CPSO可以幫助IWKM在高維多視圖數據中獲得更好的初始聚類中心、視圖權重和特征權重。

(a) 多特征數據集

(b) 互聯網廣告數據集

(c) Spambase數據集圖5 PSO與CPSO的比較

3.6 IWKM視圖權重比較

為了進一步評估獲得視圖權重的性能，在五個不同的高維多視圖數據集中測試了TWKM和IWKM。兩個算法在數據集中運行了10次，并記錄了IWKM和TWKM的平均結果并在表2中進行了比較。顯然，IWKM和TWKM可以為5個高維多視圖數據集獲得有效權重。特別是在互聯網廣告和圖像分割這兩個數據集中，TWKM和IWKM在獲得視圖權重方面具有相似的性能。但是，在Apache Spark和Single Node上，在其他3個數據集(Mfeat、Spambase和心電圖)中，IWKM可以獲得比TWKM更好、更合理的視圖權重。TWKM計算出的視圖權重常常集中在一個視圖上，這與現實應用不符。IWKM計算的權重比TWKM計算的權重更合理，并且特征的權重處于相同情況。因此，可以得出結論，在視圖權重方面，IWKM比TWKM具有更好的性能。

表2 TWKM和IWKM計算的視圖權重

續表2

利用CPSO進行優化得到六個聚類算法的最優參數值如表3所示。為了進一步驗證本文算法在大數據應用中對高維多視圖數據進行聚類的綜合性能，在Apache Spark和Single Node兩種不同的計算平臺上，通過RI、JC和Folk的評估指標，在五個高維多視圖數據集中將IWKM與其他五種算法進行了比較。

表3 實驗中六種聚類算法的參數值

在實驗中，視圖數與特征數的乘積記錄為pf×v，用于描述高維多視圖數據的復雜性。特征數越大，高維多視圖數據越復雜。在表1中，根據pf×v的值，Mfeat的數據集(特征數：649，視圖數：6，pf×v=649×6=3 894)、互聯網廣告數據集(特征數：1 557，視圖數：6，pf×v=1 557×6=9 342)比Spambase數據集(特征數：57，視圖數：3，pf×v=57×3=171)、圖像分割數據集(特征數：19，視圖數：2，pf×v=19×2=38)、心電圖數據集(特征數：21，視圖數：3，pf×v=21×3=63)更復雜。

表4總結了IWKM與其他五種算法在Apache Spark和Single Node上的綜合比較。比較它們的平均結果(10倍)和標準偏差以減少統計誤差。從這些結果中，可以看到IWKM在Mfeat數據集和互聯網廣告數據集中明顯優于的其他五種算法。在Spambase數據集中，IWKM的性能優于TWKM和DC，但AP在Mfeat數據集中的效果最差。在Mfeat數據集中，DC和IWKM均比LAC、AP、Ncut和TWKM更好。在互聯網廣告數據集中，AP、TWKM和IWKM的性能優于LAC、Ncut和DC。LAC明顯優于Spambase數據集中的其他五種算法(包括IWKM)，但Spambase數據集的復雜度低于Mfeat數據集和互聯網廣告數據集。因此，可以得出結論，在這些復雜的數據集中，IWKM在針對具有更多視圖和更高維度數據集來說，例如多特征和互聯網廣告數據集，勝過其他五種算法。在心電圖數據集中，IWKM優于其他的五種算法。但是，在圖像分割中，Ncut和TWKM的性能要優于IWKM。由于心電圖數據集比圖像分割數據集更為復雜，因此高維多視圖數據集越復雜，IWKM的性能越好?？傊?，IWKM可以更加有效地處理大數據應用中的高維多視圖數據集的聚類。同時，在這些復雜的數據集中，IWKM優于其他五種算法。

表4 五種算法的比較

4 結 語

針對傳統聚類算法無法處理大數據中多視圖高維數據問題，提出一種基于混沌粒子群優化算法的智能加權K均值聚類算法。通過實驗證明了CPSO可以幫助IWKM在高維多視圖數據中獲得更好的初始聚類中心、視圖權重和特征權重，為聚類精度的提升提供良好的初始值要求。另外本文方法能夠有效實現多視圖高維數據的聚類，且針對視圖越多、維數越高、數據越復雜的數據集越能夠體現該算法的優越性。