基于改進高斯核度量和KPCA的數據聚類新方法①

余文利,余建軍,方建文

1(衢州職業技術學院 信息工程學院,衢州 324000)2(衢州學院 電氣與信息工程學院,衢州 324000)

基于改進高斯核度量和KPCA的數據聚類新方法①

余文利1,余建軍1,方建文2

1(衢州職業技術學院 信息工程學院,衢州 324000)2(衢州學院 電氣與信息工程學院,衢州 324000)

大多數超橢球聚類(hyper-ellipsoidal clustering,HEC)算法都使用馬氏距離作為距離度量,已經證明在該條件下劃分聚類的代價函數是常量,導致HEC無法實現橢球聚類.本文說明了使用改進高斯核的HEC算法可以解釋為尋找體積和密度都緊湊的橢球分簇,并提出了一種實用HEC算法-K-HEC,該算法能夠有效地處理橢球形、不同大小和不同密度的分簇.為實現更復雜形狀數據集的聚類,使用定義在核特征空間的橢球來改進K-HEC算法的能力,提出了EK-HEC算法.仿真實驗證明所提出算法在聚類結果和性能上均優于K-means算法、模糊C-means算法、GMM-EM算法和基于最小體積橢球(minimum-volume ellipsoids,MVE)的馬氏HEC算法,從而證明了本文算法的可行性和有效性.

數據聚類; 超橢球聚類; 最小體積橢球; 核主成分分析; 高斯核

聚類作為一種重要的數據分析手段,是機器學習、模式識別、計算機視覺和數據挖掘等領域的研究熱點[1].聚類分析就是把對象按照性質上的親疏程度分多個類或簇,使得簇內的數據具有較高的相似度,簇間的數據具有較高的相異度[2].盡管許多研究者在不斷努力,但目前仍沒有一種能夠處理所有聚類問題的最優算法,聚類仍然是一個困難和具有挑戰性的問題.

傳統的聚類算法如K-means、GMM-EM、模糊C-means(FCM)等,都是基于最小化簇內樣本點的歐氏距離和的通用聚類準則,基于歐氏度量的聚類算法傾向于將樣本點劃分到相同大小、相同密度和球形的分簇中,這些算法無法完成大而細長的分簇的劃分,而現實世界的數據常常以混合高斯分布的形式呈現,如橢球形或其他復雜形狀.為解決上述問題,人們提出了各種超橢球聚類算法(hyper-ellipsoidal clustering,HEC)[3-10],這些算法通常使用馬氏距離作為距離度量來建立橢球分簇.現有的HEC算法主要存在以下問題:1)過高的計算復雜度,導致在馬氏距離中直接計算協方差矩陣非常困難; 2)當分簇包含少量樣本點時,協方差矩陣可能是奇異的.為了克服以上的不足,文獻[3-5]提出基于改進馬氏距離和偽協方差矩陣的HEC算法,但是這些算法的時間復雜度仍然很高.另一方面,文獻[8-10]通過近似分簇體積,即找到最小體積橢球(minimum-volume ellipsoids,MVE),取代了協方差矩陣的計算,部分克服了以上的不足.以上大多數方法都是使用馬氏距離作為距離度量,已經證明直接將馬氏距離應用于聚類不能獲得橢球聚類[7],而且劃分聚類的代價函數也無法限定分簇的大小和分簇之間的關系.此外,因為這些算法在聚類時無需考慮樣本集的密度,所以基于MVE的HEC算法只有等密度分簇的情況才能工作得很好.

本文的目標是實現橢球聚類并給出改進的實用HEC算法的實現,首先,提出了使用改進高斯核度量的基于MVE的K-HEC算法,該算法能夠處理橢球形狀、不同大小和密度的分簇.為了增強K-HEC算法的能力,通過在特征空間中映射橢球,提出了EK-HEC算法,該算法能夠處理非線性和細長結構的分簇.在模擬數據集和標準評測數據集上的仿真實驗表明,本文算法在聚類結果和性能上與K-means算法、模糊C-means算法、GMM-EM算法和馬氏MVE-HEC算法相比有了很大的提高,從而驗證了本文算法在處理橢球形或復雜形狀數據集聚類時的可行性和有效性.

1 問題定義

其中D(xi,mk)為輸入模式與第k個分簇mk的均值向量之間的距離度量.

為了構造橢球分簇,HEC算法通常采用馬氏距離.然而在該條件下,劃分聚類的代價函數是常量[7].為了實現橢球聚類,本文使用式(3)的改進高斯核作為距離度量

其中mk和Qk分別是第k個分簇的均值向量和協方差矩陣.變量α∈[0,1]控制著式(3)的第1項和第2項的權重.式(3)的第1項表示馬氏距離,第2項與由協方差矩陣Qk表示的第k個橢圓分簇的容積成正比.則聚類代價函數改寫為

代價函數EC(P)達到最優的必要條件為通過最小化式(4)得到劃分的分簇中心表示為

證畢.

定理1.如果改進高斯核式(3)作為式(2)的聚類代價函數的距離度量,則

證畢.

2 橢球和復雜形狀聚類

本文提出了兩種最小化分簇體積權重和的HEC算法—K-HEC算法和EK-HEC算法.其中K-HEC算法是使用改進高斯核和MVE近似的迭代HEC算法,它將樣本劃分到指定數量的橢球分簇中; EK-HEC算法是K-HEC算法的擴展,它通過使用定義在核特征空間的橢球來改善K-HEC算法的聚類能力,以便能處理更復雜形狀樣本集的聚類.

2.1 K-HEC算法

K-HEC算法開始于一個初始的聚類,最終將初始的聚類劃分為C個分簇,在此過程中算法迭代查找改進的劃分矩陣的分配,分簇體積的權重和不斷縮小,直到分簇結果沒有進一步可能的改進為止.

因此,本文使用三個近似方法來尋找MVE.首先,推導式(9)所示的L?wner-John橢球體[11]凸優化問題,該問題可以幾何解釋為最小化橢球體的體積.

其次,通過近似計算包含矩陣Q特征向量和的目標函數來求解式(10)所示凸優化問題[8,11].

最后,使用Khachiyan的快速近似算法[12]來尋找MVE.

算法1.K-HEC算法輸入:d維空間的n個樣本輸出:劃分矩陣P步驟1.確定分簇數C,從樣本集中隨機選擇C個樣本,設定為分簇的中心,記作mk;步驟2.首先使用樣本與分簇中心mk歐氏距離來確定劃分矩陣的初始分配x={xi∈Rd}n i=1■■■■■Pik=1,ifDEuc(xi,mk)＜DEuc(xi,mj),j=1,2,...,Candj≠k Pik=0,otherwise步驟3.計算新的分簇中心和屬于該分簇的樣本的數量mk=∑n∑ni i=1Pikxi=1Pik,nk=∑n i=1Pik步驟4.使用MVE近似算法計算偽協方差矩陣Qk;步驟5.使用式(3)的改進高斯核度量、mk和Qk確定劃分矩陣P的一個新的分配{Pik=1,ifDMGK(xi,mk;Qk)＜DMGK(xi,mj;Qj)Pik=0,otherwise步驟6.如果劃分矩陣P沒有變化,則算法停止.否則重復步驟3到步驟5.

2.2 EK-HEC算法

大部分劃分聚類算法在對非線性和細長結構數據集進行聚類時,不能取得理想的效果,為此人們提出了譜聚類算法[13]和核方法[14].為了在非線性和細長結構數據集上執行聚類,本文使用了核主成分分析(Kernel principal component analysis,KPCA).通過RBF核函數,能夠有效地在與基于非線性映射的輸入空間相關聯的高維特征空間中計算主成分.KPCA的原理如下所示.

EK-HEC算法通過在核空間中執行K-HEC算法實現復雜形狀聚類,算法的具體描述如算法2.

算法2.EK-HEC算法輸入:d維空間的n個樣本輸出:劃分矩陣P Kij=Φ(xi)·Φ(xj)=K(xi,xj);x={xi∈Rd}n i=1步驟1.計算核矩陣K,i,j = 1,2,...,n;步驟2.解式(12),找到非零的特征值;步驟3.使用非零特征值αk(k=1,2,…,p),計算樣本Ф(x)在特征向量Vk上的投影;?x=(Vk·Φ(x))=∑n i =1αkiK(xi,x)步驟4.確定分簇數C,在特征空間中隨機選擇C個樣本,將它們設置為分簇的中心,記作 ;?mk ?mk步驟5.使用歐氏距離計算樣本與分簇中心 的距離,確定劃分矩陣P的初始分配■■■■■Pik=1,ifDEuc(?xi,?mk)＜DEuc(?xi,?mj),j=1,2,...Candj≠k Pik=0,otherwise步驟6.計算新的分簇中心和屬于新分簇的樣本數?mk=∑ni=1Pik?xi/∑n i=1Pik,nk=∑n i=1Pik ?Qk步驟8.使用式(3)的改進高斯核度量、 和 確定劃分矩陣P的新的分配步驟7.使用MVE近似算法計算偽協方差矩陣 ;?mk ?Qk■■■■■Pik=1,ifDEuc(?xi,?mk;?Qk)＜DEuc(?xi,?mj;?Qj),j=1,2,...Candj≠k Pik=0,otherwise步驟9.如果劃分矩陣P沒有變化,則算法終止; 否則重復步驟6至步驟8.

3 仿真實驗

3.1 實驗描述

為驗證K-HEC算法和EK-HEC算法的有效性,在模擬數據集和基準評測數據集上進行了實驗.K-HEC算法和 EK-HEC 算法是在 Matlab 上使用CVX[15]和LMI工具箱編程實現,在Intel(R)Xeon? CPU W5590@line-height:15.5pt3.33GHZ的微機Windows XP環境下運行.在性能評估時,使用誤分類率(Misclassification rate,MCR)和歸一化互信息(Normalized mutual information,NMI)作為評價指標,分別定義如下

其中X、Y是兩個隨機變量,I(X,Y)是互信息,H(X)和H(Y)是X和Y的熵.

3.2 實驗結果與分析

3.2.1 模擬數據集

為了說明本文所提出算法的有效性,在實驗中使用了2個模擬數據集(具體描述如表1所示).模擬數據集1用以驗證K-HEC算法對于不同大小、不同密度和橢圓形分簇的聚類能力,該數據集包含一個圓形的分簇和一人細長橢圓形的分簇.K-HEC算法在模擬數據集1上使用式(9)-式(11)三種不同的MVE近似方法所提到的聚類結果是一樣的,因此忽略式(9)和式(10)的方法,使用式(11)方法的K-HEC算法在數據集1上的聚類結果如圖1所示.

表1 模擬數據集

圖1 不同算法在模擬數據集1上的聚類結果

從圖1(b)可以看出,K-means算法在模擬數據集1上不能得到正確的聚類; 從(c)可以看出,馬氏HEC算法雖然將樣本劃分為不同大小的兩個橢圓分簇,但當兩個分簇距離較近時聚類結果也不準確; (d)表明本文提出的K-HEC算法通過調整α的值來控制改進高斯核的第1項和第2項的權重,從而最小化分簇體積權重和,使得聚類后分簇的緊湊性和密度達到最大.

模擬數據集2包含一個高斯分布分簇和一個香蕉形分簇,用于驗證EK-HEC算法的有效性,該算法專門設計用于復雜幾何形狀樣本集的聚類.K-means算法、HEC算法、K-HEC算法和EK-HEC算法在模擬數據集2上的聚類結果如圖2(b)～(f)所示.

圖2 不同算法在模擬數據集2上的聚類結果

從圖2可以看出,K-means算法、馬氏HEC算法以及K-HEC算法有相似的聚類結果.可以注意到,雖然聚類結果相似,但是由每個算法所確定的聚類的決策邊界仍有很大的不同.與其他算法相比,基于Moshtagh方法的MVE近似的Moshtagh-K-HEC算法建立了清晰的決策邊界,而馬氏HEC算法和LMI-K-HEC算法有重疊的決策邊界.EK-HEC算法按照預期找到了正確的分簇,僅有一個樣本錯分.圖3描述了EK-HEC算法在模擬數據集2上的聚類結果,其中(a)和(b)分別描述了在算法在輸入空間和特征空間的聚類結果,映射到特征空間的樣本得到很好的分離,并且能夠通過橢圓的決策邊界實現聚類.

圖3 EK-HEC算法在模擬數據集2上的聚類結果

3.2.2 基準評測數據集

為了評估本文提出算法的性能,在來自UCI的3個基準評測數據集(具體描述見表2)上與K-means算法、模糊C-means算法、GMM-EM算法和馬氏距離MVE-HEC算法進行了比較實驗.6種算法在MCR和NMI兩個評判準則上的比較結果如圖4所示,由圖4可知,K-HEC算法在MCR和NMI兩個指標上均優于K-means、模糊C-means、GMM-EM和HEC算法,EK-HEC算法與其他算法相比有更好或類似的聚類性能.

表2 來自UCI的基準評測數據集

4 結語

本文將基于MVE的HEC算法與改進的高斯核相結合,提出了K-HEC算法,通過應用定義在核空間的橢圓聚類,增強了K-HEC算法聚類能力,提出了EK-HEC算法.K-HEC算法能夠處理不同大小、不同密度和橢球形壯的分簇,EK-HEC算法能夠處理非線性和細長結構的復雜幾何形狀的分簇.在模擬數據集和UCI基準評測數據集上的仿真實驗表明,K-HEC算法能夠通過建立緊湊的分類邊界有效地分離各分簇,EK-HEC算法在非線性和細長結構的數據集上完成了正確的聚類.本文算法無論在聚類能力和性能方面均優于K-means、模糊C-means、GMM-EM和HEC算法,從而驗證了本文算法的可行性和有效性.

圖4 基準評測數據集上的聚類性能比較

1Duda RO,Hart PE,Stork DG.Pattern Classification.New York:John Wiley & Sons,2012.

2Nagpal A,Jatain A,Gaur D.Review based on data clustering algorithms.Proc.of the 2013 IEEE Conference on Information & Communication Technologies (ICT).JeJu Island,Korea.2013.298–303.

3Mao JC,Jain AK.A self-organizing network for hyperellipsoidal clustering (HEC).IEEE Trans.on Neural Networks,1996,7(1):16–29.[doi:10.1109/72.478389]

4Wang S,Ma F,Shi W,et al.The hyperellipsoidal clustering using genetic algorithm.Proc.of the 1997 IEEE International Conference on Intelligent Processing Systems.Beijing,China.1997,1.592–596.

5Ichihashi H,Ohue M,Miyoshi T.Fuzzy C-means clustering algorithm with pseudo Mahalanobis distances.Proc.of the 3rd Asian Fuzzy Systems Symposium.Changwon,Korea.1998.148–152.

6Moshtaghi M,Rajasegarar S,Leckie C,et al.An efficient hyperellipsoidal clustering algorithm for resource-constrained environments.Pattern Recognition,2011,44(9):2197–2209.[doi:10.1016/j.patcog.2011.03.007]

7Wang S,Xia SW,Mao JC,et al.Comments on “a self-organizing network for hyperellipsoidal clustering (HEC)”.IEEE Trans.on Neural Networks,1997,8(6):1561–1563.[doi:10.1109/72.641479]

8Lee HS,Park JY,Park DH.Hyper-ellipsoidal clustering algorithm using linear matrix inequality.Journal of Korean Institute of Intelligent Systems,2002,12(4):300–305.[doi:10.5391/JKIIS.2002.12.4.300]

9Kumar M,Orlin JB.Scale-invariant clustering with minimum volume ellipsoids.Computer & Operations Research,2008,35(4):1017–1029.

10Shioda R,Tun?el L.Clustering via minimum volume ellipsoids.Computational Optimization and Applications,2007,37(3):247–295.[doi:10.1007/s10589-007-9024-1]

11Boyd S,Vandenberghe L.Convex optimization.Cambridge,UK:Cambridge University Press,2004.

12Todd MJ,Yildirim EA.On Khachiyan’s algorithm for the computation of minimum-volume enclosing ellipsoids.Discrete Applied Mathematics,2007,155(13):1731–1744.[doi:10.1016/j.dam.2007.02.013]

13Cao JZ,Chen P,Zheng Y,et al.A max-flow-based similarity measure for spectral clustering.ETRI Journal,2013,35(2):311–320.[doi:10.4218/etrij.13.0112.0520]

14Shawe-Taylor J,Cristianini N.Kernel methods for pattern analysis.Cambridge,UK:Cambridge University Press,2004.

15CVX Research,Inc.CVX:Matlab software for disciplined convex programming,version 2.0.http://cvxr.com/cvx.[2013-04].

Novel Data Clustering Method Based on A Modified Gaussian Kernel Metric and Kernel PCA

YU Wen-Li1,YU Jian-Jun1,FANG Jian-Wen21(College of Information Engineering,Quzhou College of Technology,Quzhou 324000,China)2(College of Electrical and Information Engineering,Quzhou University,Quzhou 324000,China)

Most hyper-ellipsoidal clustering(HEC)algorithms use the Mahalanobis distance as a distance metric.It has been proven that HEC,under this condition,cannot be realized since the cost function of partitional clustering is a constant.We demonstrate that HEC with a modified Gaussian kernel metric can be interpreted as a problem of finding condensed ellipsoidal clusters(with respect to the volumes and densities of the clusters)and propose a practical HEC algorithm named K-HEC that is able to efficiently handle clusters that are ellipsoidal in shape and that are of different size and density.We then try to refine the K-HEC algorithm by utilizing ellipsoids defined on the kernel feature space to deal with more complex-shaped clusters.Simulation experiments demonstrate the proposed methods have a significant improvement in the clustering results and performance over K-means algorithm,fuzzy C-means algorithm,GMM-EM algorithm and HEC algorithm based on minimum-volume ellipsoids using Mahalanobis distance.

data clustering; hyper-ellipsoidal clustering; minimum-volume ellipsoids; kernel PCA; Gaussian kernel

余文利,余建軍,方建文.基于改進高斯核度量和KPCA的數據聚類新方法.計算機系統應用,2017,26(10):150–155.http://www.c-sa.org.cn/1003-3254/5988.html

2017-01-11; 采用時間:2017-02-15