基于K-Means的軟子空間聚類算法研究綜述*

李俊麗

(晉中學院信息技術與工程學院　晉中　030619)

?

基于K-Means的軟子空間聚類算法研究綜述*

李俊麗

(晉中學院信息技術與工程學院晉中030619)

摘要隨著數據挖掘技術的發展，聚類分析算法越來越多，由于分析高維數據有時會陷入所謂維災難，傳統的聚類算法在聚類高維數據時性能會降低很多。針對這種情況，提出了子空間聚類算法，極大地改善了這個問題。K-Means算法是一種應用很廣泛的聚類算法，與子空間聚類算法結合可以應用于高維數據聚類。介紹了三類基于K-Means的軟子空間聚類算法，并對每種算法進行了描述和分析，最后指出了進一步的研究方向。

關鍵詞K-Means算法; 軟子空間聚類; 高維數據聚類

Class NumberTP301

1引言

聚類分析[1～2]將數據劃分成有意義或有用的簇，是解決數據匯總問題的起點，在廣泛的領域扮演重要角色。這些領域包括心理學和其他社會科學、生物學、統計學、模式識別、信息檢索、機器學習和數據挖掘。在過去的幾十年中，將聚類的不同類型區分為:層次的(嵌套的)與劃分的(非嵌套的)，互斥的、重疊的與模糊的，完全的與部分的等。 K-Means算法[3]是一種基于原型的、劃分的聚類技術，由于其算法思想比較簡單，聚類速度較快，且方便處理大量數據而得到了廣泛的應用。但是隨著數據發展的維數越來越高，K-Means聚類算法和其他傳統的算法一樣，在聚類高維數據時性能會降低很多。

在高維數據中，簇通常是嵌入在原始數據空間的子空間，且不同的簇可以嵌入到不同的子空間中，所以子空間聚類方法在高維數據聚類中是必需的。子空間聚類算法是從高維數據空間中發現隱藏在不同低維子空間中的簇類。很多文獻提出了許多子空間聚類算法來處理高維數據，旨在從子空間而不是整個數據空間發現簇類[4～5]。此類算法能有效減少數據冗余和不相關屬性對聚類過程的干擾，從而提高在高維數據集上的聚類結果。將K均值聚類算法與子空間聚類相結合能夠更好地應用在高維數據聚類中，從而克服了傳統聚類技術的不足之處。

2K-Means算法與軟子空間聚類

2.1K-Means算法

K-Means算法具有很長的歷史，但是仍然是當前研究的重要課題。最早的K-Means算法由MacQueen提出。K-Means算法是一個經典的聚類算法，其算法基本思想:首先，從原始目標數據集合中，隨機選擇k個數據點作為初始的k個簇的中心，其中k是用戶指定的參數，即所期望的簇的個數。然后，計算其他非中心的數據點到k個簇中心的距離，根據其與中心的距離，選取距離最近的簇類，然后把該數據點分配到這個簇中，不斷重復這個過程。最后當所有的點都被劃到一個簇后，重新更新簇中心點，直到簇不發生變化為止。

K-Means算法的基本步驟如下:

輸入:簇的個數k以及數據集合D

輸出:滿足條件的k個簇

step1. 從數據集D中隨機選擇k個點作為初始簇中心；

step2. repeat；

step3. 計算每個點與各個中心點的距離，把對象指派到最近的簇中心，形成K個簇；

step4. 重新計算每個簇的均值，作為新的簇中心；

step5. until簇中心不再發生變化為止。

K-Means算法需要事先確定k的大小以及初始聚類中心，而且只能發現超球狀的簇，對初始中心非常敏感。對K-Means算法的改進主要從確定k的大小以及k個初始中心的選擇等方面進行。

Bradley和Fayyad以某種方式處理了K-Means算法的初始化問題[6]，Anderberg[7]、Jain和Dubes[8]的書詳細地介紹了K-Means算法和它的一些變形。

2.2軟子空間聚類

軟子空間聚類算法是通過對各個數據簇類中的單個特征加權，獲得每個數據特征的重要性，從而發現大權重的特征所在的子空間[9～11]。相比較于硬子空間聚類算法來說，由于對數據的處理有更好的靈活性與適應性，人們對軟子空間聚類算法的關注越來越多。

為了更好地獲得每個簇類所在的最佳子空間，人們將K-Means聚類算法與軟子空間聚類算法相結合，采用了經典的K-Means型算法的結構，并且在其基礎之上增加了一個迭代的步驟來計算加權公式，從而得出每個簇類及其相關聯的維度的權重集合，然后更新權值向量。

3基于K-Means的軟子空間聚類算法

3.1模糊加權軟子空間聚類算法

2004年，E.Y. Chan等通過引入模糊權重指數和模糊加權指數，提出了模糊加權軟子空間聚類算法[12]，其目標函數定義如下:

JAWA =∑Ci=1∑Nj=1uij∑Dk=1wτikd(xjk,vik)

(1)

subject to

利用Lagrange乘子優化方法最小化公式得到算法模糊隸屬度和特征加權系數的迭代公式。這是提出的第一個模糊加權軟子空間聚類算法。根據公式可以看出，若某個維度的距離為零時，上式就會失去意義。因此，2005年Jing L等給出了FWKM(Feature Weighting K-Means)算法[13]，算法中提出了一個估算參數σ的公式，該算法在以上目標函數中加了一個取值足夠小的估算參數σ，通過給維度的距離增加一個大于 0 的參數σ，避免了當距離為零時，計算中出現的不便。后來， Gan G等又提出了FSC( A fuzzy subspace algorithm for clustering high dimensional data)，給出了另一個模糊加權軟子空間聚類算法[14]，該算法發現在子空間聚類中，每個維度的原始數據與每個簇以不同權重相關聯。而且密度越高，分配到該維度的權重越大。也就是說，所有維度的原始數據與每個簇相關聯，但他們關聯的程度不同。此算法增加了設置參數，用來控制在計算距離中的關鍵程度。

模糊加權軟子空間聚類算法運用模糊優化技術對目標函數優化，對于不同的數據集，根據需要對模糊指數的取值進行調整。因此，相比較于經典加權算法，模糊加權算法具有很好的適應性。

3.2熵加權軟子空間聚類

熵加權軟子空間聚類算法是通過將信息熵概念引入到軟子空間聚類算法中，在一定程度上由信息熵控制聚類中的各權向量[15]。2006年，Carlotta Domeniconi等提出LAC(Locally adaptive metrics for clustering high dimensional data)算法[16]，此算法在各個簇中給每個特征分配一個權值，使用一個迭代算法來最小化其目標函數，通過用一個固定的常量取代最大平均距離證明了算法的收斂性。2007年Jing L等提出EWSC(entropy weighting Subspace Clustering)算法[17]，此算法是熵加權軟子空間聚類算法的典型代表，其目標函數定義如下:

JEWSC= ∑Nj=1∑Ci=1umij∑Dk=1wik(xjk-vik)2

(2)

subject to

此算法擴展了K-Means聚類過程，在聚類過程中增加了一個額外的步驟，自動計算每個簇類的所有維度的權重。在大多數的軟子空間聚類方法中，只考慮了類內信息，很少有算法考慮到軟子空間聚類的類間信息。因此，2010年Deng ZH等提出 ESSC(Enhanced soft subspace clustering)算法[18]，與其它軟子空間聚類算法相比，該算法在聚類過程中采用了類內和類間兩種信息，對于高維數據可以得到更好的聚類結果。

現有的子空間聚類算法僅對特征子空間進行聚類，沒有考慮特征組權重的問題，在聚類高維數據時沒有使用特征組的信息，以下介紹特征組加權，在加權子空間聚類的基礎上，融入更多的特征組信息對改進現有的算法是很有意義的。

3.3特征組加權軟子空間聚類

如果軟子空間聚類在特征子空間上直接進行，特征組差異往往被忽略，而且特征子空間權重對噪聲和缺失值比較敏感。此外，對于特征較少的特征組，特征較多的特征組將獲得更多的權重。為了解決這個問題，X.Chen等引入了給特征組分配權值的概念，進而提出了一種新的子空間聚類算法稱為FGKM算法[19]。此算法將相關特征聚集為特征組，在子空間同時進行特征組和單個特征的聚類，特征組加權減少了權重對噪聲和缺失值的敏感性，通過引入特征組加權，能夠消除特征組中的總體差異引起的不平衡現象。

這種算法中，高維數據基于它們的自然特性被分為特征組。算法給出一個新的優化模型定義優化過程。其目標函數定義如下:

JFGKM =∑kl=1{∑ni=1∑Tt=1∑j∈Gtui,lwl,tvl,jd(xi,j,zl,j)

(3)

subject to

該算法通過在子空間中對特征組和單個特征進行加權，自動計算出兩種類型的子空間熵。但是，FGKM算法的缺點是要求在聚類之前就確定特征組信息，而且在聚類過程中要作為輸入給出。在大多數情況下，我們無法確定一個高維數據集特征組的信息。因此，G. Gan等在FGKM算法的基礎上提出了AFGKM軟子空間聚類算法[20]，此算法能夠在聚類迭代過程中自動確定特征組信息，通過加入特征組自動選擇功能從而擴展了FGKM算法，AFGKM算法會產生比FGkM算法更準確的聚類結果。

4基于K-Means的軟子空間聚類進一步研究方向

基于K-Means的軟子空間聚類算法的共同特點是:首先定義目標函數，利用一些優化方法求出最小化的解；其次，經過推導得出權值向量的迭代計算公式；最后，目標函數是否有效決定了聚類結果的好壞。基于K-Means的算法都具有較好的擴展性，在計算高維數據時，具有較好的適用性。但是，其也繼承了K-Means 算法的缺點，為了進一步提高算法的穩定性，選擇適當的初始簇中心是其關鍵步驟。

因而進一步的研究工作歸納如下:

1) 對于高維數據而言,目前尚缺乏有效的初始簇中心選擇的方法，選擇初始簇中心的方法不同，聚類結果反差會很大。

2) 現有的算法在定義加權方式時都引入了一些難以確定的參數，需要用戶提供專門的領域知識來設置它們的輸入參數，而且不同簇使用了相同的參數，這樣對于不同結構的簇，參數不能自動調節，致使算法的適用性降低了很多，算法對于不同聚類問題的泛化能力也降低了很多。

3) 現有的軟子空間聚類算法大多數是不完備的，沒有考慮到子空間的優化問題，而只是過多關心數據集劃分的優化問題。

4) 現有的軟子空間聚類算法都是基于批處理技術的聚類算法不能很好地應用于高維數據流。

5) 以上提到的算法還存在很多需要改進的地方，如參數設置的合理性，算法效率的提高等等。

5結語

軟子空間聚類算法受到越來越多的關注，文中首先介紹了傳統的K-Means聚類算法,然后在此基礎上結合子空間聚類算法給出了幾種基于K-Means的軟子空間聚類算法,通過對每種算法進行了綜述和分析,指出了一些不足之處，最后確定了進一步研究的方向，對以后的子空間聚類的研究有一定指導意義。

參 考 文 獻

[1] Jiawei Han, Micheline Kamber.數據挖掘:概念與技術[M].范明,孟小峰,譯.北京:機械工業出版社,2006.

[2] D.Hand, H.Mannila, P.Smyth.數據挖掘原理[M].張銀奎,廖麗,宋俊,等譯.北京:機械工業出版社,2003.

[3] J.MacQueen. Some methods for classification and analysis of multivariate observations[C]//Proc. of the 5th Berkeley Symp. On Mathematical Statistics and Classification, pages 345-375.World Scientific, Singapore, January，1996.

[4] L. Parsons, E. Haque, H. Liu, Subspace clustering for high dimensional data: a review[J]. ACM SIGKDD Explorations Newsletter,2004,6(1):90-105.

[5] H. Kriegel, P. Kroger, A. Zimek, Clustering high-dimensional data: a survey on subspace clustering, pattern based clustering, and correlation clustering[J]. ACM Transactions on Knowledge Discovery from Data,2009,3(1):1-58.

[6] P.S.Bradley and U.M.Fayyad. Refining Initial Points for K-Means Clustering[C]//Proc. of the 15th Intl. Conf. on Machine Learning, pages 91-99, Madison, WI, July 1998. Morgan Kaufmann Publishers Inc.

[7] M. R. Anderberg. Cluster Analysis for Applications[M]. New York: Academic Press, New York,1973.

[8] A. K. Jain and R. C. Dubes. Algorithms for Clustering Data. Prentice Hall Advanced Reference Series[M]. New York: Prentice Hall,1988.

[9] C. Bouveyron, S. Girard, C. Schmid, High dimensional data clustering[J]. Computational Statistics & Data Analysis,2007,52(1):502-519.

[10] C.-Y. Tsai, C.-C. Chiu, Developing a feature weight self-adjustment mechanism for a k-means clustering algorithm[J]. Computational Statistics & Data Analysis,2008,52(10):4658-4672.

[11] G. Milligan, A validation study of a variable weighting algorithm for cluster analysis[J]. Journal of Classification,1989,6(1):53-71.

[12] E.Y. Chan, W.K. Ching, M.K. Ng, and J.Z. Huang, An Optimization Algorithm for Clustering Using Weighted Dissimilarity Measures[J], Pattern Recognition,2004,37(5):943-952.

[13] L. Jing, M.K. Ng, J. Xu, J.Z. Huang, Subspace Clustering of Text Documents with Feature Weighting k-Means Algorithm[C]//Proc. Ninth Pacific-Asia Conf. Knowledge Discovery and Data Mining,2005:802-812.

[14] G.J. Gan, J.H. Wu, A convergence theorem for the fuzzy subspace clustering (FSC) algorithm[J]. Pattern Recognition,2008,41:1939-1947.

[15] H. Cheng, K.A. Hua, K. Vu, Constrained locally weighted clustering[C]//Proceedings of the VLDB Endowment, vol. 1, Auckland, New Zealand,2008:90-101.

[16] C. Domeniconi, D. Gunopulos, S. Ma, B. Yan, M. Al-Razgan, and D. Papadopoulos, Locally Adaptive Metrics for Clustering High Dimensional Data[J]. Data Mining and Knowledge Discovery,2007,14:63-97.

[17] L.P. Jing, M.K. Ng, Z.X. Huang, An Entropy Weighting k-Means Algorithm for Subspace Clustering of High-Dimensional Sparse Data[J], IEEE Trans. on Knowledge & Data Eng,2007,19(8):1026-1041.

[18] Z.H. Deng, K.S. Choi, F.L. Chung and S.T. Wang, Enhanced soft subspace clustering integrating within-cluster and between-cluster information[J], Pattern Recognition,2010,43:767-781.

[19] X. Chen, Y. Ye, X. Xu, J.Z. Huang. A feature group weighting method for subspace clustering of high-dimensional data[J]. Pattern Recognition,2012,45(1):434-446.

[20] Guojun Gan, Michael Kwok-Po Ng. Subspace clustering with automatic feature grouping[J]. Pattern Recognition,2015,48:3703-3713.

Summary of Soft Subspace Clustering Algorithm Based on K-Means

LI Junli

( School of Information Technology and Engineering, Jinzhong College, Jinzhong030619)

AbstractWith the development of data mining, clustering algorithm is becoming more and more. The difficulties associated with analyzing high-dimensional data are sometimes referred to as the curse of dimensionality. So the performance of traditional clustering algorithm in high-dimensional data clustering will reduce a lot. For this situation, subspace clustering algorithm greatly improves the problem . K-Means algorithm is a widely used clustering algorithm. Combined with subspace clustering algorithm it can be applied to high-dimensional data clustering. This paper introduces three kinds of soft subspace clustering algorithm based on K-Means, then each algorithm is summarized and analyzed. Finally it points out the future research direction.

Key WordsK-Means algorithm, soft subspace clustering, high-dimensional data clustering

* 收稿日期：2015年11月7日,修回日期：2015年12月23日

作者簡介：李俊麗,女,講師，碩士,研究方向：數據挖掘。

中圖分類號TP301

DOI：10.3969/j.issn.1672-9730.2016.05.011