大數據挖掘中的混合差分進化K-Means無監督聚類算法

吳雅琴，王曉東

(內蒙古醫科大學 計算機信息學院， 呼和浩特 010110)

近年來，隨著計算機和互聯網技術的快速發展，人們在工作和生活中產生了各種形式的數據，如文本、圖像、音頻、視頻等，這些數據的存儲量正變得越來越大。如何準確和有效地從這些海量數據中抽取出隱藏的、有價值的信息成為計算機科學領域中的研究熱點，由此數據挖掘技術應運而生[1-2]。數據挖掘又稱知識發現，即“從數據中挖掘知識”，可以看作信息技術自然進化的結果。聚類分析作為大數據挖掘中最為重要的方法之一，已經得到了人們越來越多的關注[3]。其中，K-Means無監督聚類算法是現有聚類算法中最為典型的劃分算法。目前，K-Means聚類算法在情報檢索、機器學習、專家系統(依靠過去的經驗法則)和模式識別等領域得到了廣泛應用[4]。

K-Means聚類算法作為聚類分析中廣泛應用的一種經典算法，具有算法結構簡單、運行效率高且適用范圍大等優點。文獻[5]將基于K-Means聚類算法的自動圖譜識別應用于電纜監測，其能夠對內部放電、沿面放電和干擾信號做出準確的判斷。文獻[6]提出了一種K-means聚類算法，并將其應用于大數據圖像檢索，獲得了較高的檢索準確率。但是，K-Means聚類算法對初始參數設置有較大的依賴性，此外，其聚類結果的魯棒性較低且易陷入局部最優解。因此，許多文獻對K-Means聚類算法進行了改進和優化[7-10]。這些方法在一定程度上克服了K-Means聚類算法的缺陷，但仍需繼續優化和完善。

為了解決上述問題，提高K-Means聚類算法的聚類穩定度和速度，本文提出了一種改進的混合差分進化算法，并將混合差分進化算法引入K-Means聚類中。通過個體適值函數把種群視為2個子種群的混合體，按照不同的變異策略和參數對2個子種群分別進行動態更新，提高了獲取全局最優的概率。該算法較好地解決了K-Means聚類算法容易陷入局部最優陷阱的問題。實驗結果表明：相比K-Means聚類算法、基于差分進化的K-均值聚類算法，本文方法較好地提高了聚類的有效性和穩定性。

1 K-Means聚類算法基本原理

1.1 算法基本思想

作為一種基于距離的聚類劃分算法，K-Means聚類算法具有結構簡單、運行效率高且適用范圍大等優點[4]。K-Means聚類算法一般通過如式(1)所示的目標函數來實現優化。

(1)

可以看出，式(1)所示的目標函數是一個誤差平方和計算過程。其中：E為聚類準則函數；K為聚類的總數；Cj,j=1,2,…,K為聚類中的簇；x為簇Cj中的一個聚類目標；mj為簇Cj的平均大小。通常來說，E值越小則聚類效果越好。反之，E值越大則聚類質量越差。

1.2 K-Means聚類算法的基本流程

K-Means聚類算法的輸入參數為數值K和數據集X中聚類目標的數量n，輸出為使聚類準則函數E達到最小的K個聚類。K-Means聚類算法的基本流程如圖1所示。

1.3 K-Means聚類算法存在的問題分析

K-Means聚類算法的主要缺點分為3個方面[3]：① 初始參數依賴性較高，且算法容易產生局部最優解；② 容易受噪聲數據和離群數據點的干擾；③K-Means聚類算法作為一種基于歐式距離的硬聚類算法，僅對球形狀簇表現出較好的聚類性能。④ 對聚類數目K的值較為敏感。針對上述缺點中的局部最優解陷阱問題，本文引入差分進化算法，并與K-Means聚類算法進行結合。

圖1 K-Means聚類算法流程

2 差分進化算法

差分進化算法是一種基于群體智能的新型啟發式算法，能夠通過演化技術計算種群中個體間的差異信息，并按照適應值的結果擇優選擇符合要求的下一代種群，從而完成種群的進化[11]。差分進化算法是一種具有良好穩健性和全局搜索能力的全局優化算法[12]。

設X為初始種群，N為種群的大小，Xi(t)(t=1,2,…,N)為當前種群中進化個體，t為進化過程的迭代次數。種群中個體變異操作的過程如式(2)所示。

Vi(t)=(vi1(t),vi2(t),…,viD(t))=

Xp1(t)+F(Xp2(t)-Xp3(t))

(2)

其中：Xp1(t)、Xp2(t)、Xp3(t)是從當前進化種群中隨機選擇的3個不同個體；F是縮放權值。經驗表明：F=0.6時效果較好；D為種群中個體的維度，即變異個體Vi(t)由D個分量構成。

當前種群中的進化個體Xi(t)與Vi(t)進行交叉操作，生成競爭個體Ui(t)=(ui1(t),ui2(t),…,uiD(t))(由D個分量構成)。競爭個體Ui(t)中j-th分量的計算方法如式(3)所示。

(3)

其中：z是一個隨機整數，且z∈{1,2,…,D}；CR∈[0,1]，為交叉概率，經驗表明，CR取值在0.3～0.9較為適宜。

通過適應度值對比競爭個體和當前種群中的進化個體，并按照式(4)方法在上述兩者中進行擇優選擇更新種群[13]。

(4)

3 混合差分進化K-Means聚類算法

在種群的迭代進化過程中，根據貪婪選擇策略，傳統的差分進化算法會以較大的概率阻止適應度較差的個體進入下一代種群。這種情況會造成迭代末期時種群個體之間的差異較小，多樣性較低，容易導致種群中大多數個體都集中在一個局部極值點附近。這種情況下，無論如何進行變異、交叉和選擇，進化后的種群都與上一代種群十分類似，無法產生新的個體。針對該情況，本文通過個體適值函數把種群視為2個子種群的混合體，并按照不同的變異策略和參數對2個子種群分別進行動態更新，提高了獲取全局最優的概率。

3.1 混合差分進化算法

首先按照參數δ對種群進行劃分，前δ%個個體為子種群X′，其余個體為子種群X″。在每次迭代進化的最后，根據式(5)更新參數δ。

δ=δmin+rand·(δmax-δmin)

(5)

按照不同的變異策略和參數對2個子種群分別進行動態更新。對于子種群X′中個體Xi(t)，采用的變異策略如式(6)所示。

Vi(t)=Xi(t)+Fi(t)·(Xp1(t)-Xp2(t))+

Fi(t)·(Xp3(t)-Xp4(t))

(6)

其中：Fi(t)為個體Xi(t)相應的縮放權值；Xp1(t)、Xp2(t)、Xp3(t)、Xp4(t)是從當前進化種群中隨機選擇出來的4個不同個體。

對于子種群X″中個體Xi(t)，采用的變異策略如式(7)所示。

Vi(t)=Xi(t)+Fi(t)·(Xδbest-Xi(t))+

Fi(t)·(Xp5(t)-Xp6(t))

(7)

其中：Xδbest為從子種群X′中隨機選擇的個體；Xp5(t)、Xp6(t)是從當前進化種群中隨機選擇出來的2個不同個體。

對于子種群X′和X″中的個體Xi(t)，若通過Fi(t)生成的后代能夠進入下一代，則記錄到集合SF中，下一代個體Xi(t+1)對應的縮放權值可以按照式(8)產生，否則按照式(9)產生。

(8)

(9)

其中：fiti為當前個體的適應度值，fitb為當前種群中個體的最佳適應度值，fitw為當前種群中個體的最差適應度值；meanA(SF)為集合SF中所有對象的算術平均值。

按照以上縮放權值的動態更新方法，能夠充分考慮所產生后代存活情況。這種按照不同的變異策略和縮放權參數對2個子種群分別進行動態更新的方法可有效提高獲取全局最優的概率。

3.2 基于混合差分進化的 K-Means聚類算法

基于混合差分進化的K-Means聚類算法流程如圖2所示。

4 實驗結果與分析

為了驗證提出的混合差分進化的K-Means聚類算法的性能，將本文算法與另外2種典型聚類算法(K-Means聚類算法和基于差分進化的K-均值聚類算法)進行對比，以驗證本文算法的聚類性能。仿真環境為 Matlab 7.0，實驗平臺為Windows 10 64位操作系統，CPU為i5-4570處理器，4 GB內存。實驗使用的數據集是UCI 數據庫中的3個數據集，如表1所示。實驗參數設置如表2所示。

表1 實驗數據集參數

圖2 基于混合差分進化的 K-Means聚類算法流程

參數數值種群規模40λmax0.4λmin0.2初始縮放權重 Fi(0)0.6CR0.2D20The maximum number of iterations2 000

IRIS、Glass和Vowel數據集，實驗結果見表3～5。圖3為20維的收斂特性。

通過表3～5可以看出，在最小類內距離和最大類內距離結果方面，相比其他兩種算法，本文算法的數值結果均為最小。這表明本文方法的最大類內距離和最小類內距離之間的差值都有較大的減少。此外，本文方法具有最小的平均類內距離，說明聚類結果波動范圍較小，穩定性較高。

表3 IRIS數據集的實驗結果

表4 Glass數據集的實驗結果

表5 Vowel數據集的實驗結果

圖3 收斂特性比較

在算法平均收斂代數方面，相比基于差分進化的K-均值聚類算法，本文算法的收斂速度有所提升，這是因為采用了雙種群混合策略。圖3的曲線結果也驗證了本文算法的收斂優勢，表明其具有良好的尋優能力。

上述實驗結果驗證了本文算法的可行性和高效性。相比其他兩種算法，本文算法能以較快的速度獲得全局最優值，并具有更好的魯棒性。

5 結束語

本文提出了一種改進的混合差分進化算法，并將混合差分進化算法引入K-Means聚類中。通過個體適值函數把種群視為2個子種群的混合體，并按照不同的變異策略和參數對2個子種群分別進行動態更新，提高了獲取全局最優的概率。該算法較好地解決了K-Means聚類算法容易陷入局部最優陷阱的問題。實驗結果表明：相比K-Means聚類算法、基于差分進化的K-均值聚類算法，本文方法能有效提高聚類質量和收斂速度。