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

李俊麗

(晉中學(xué)院信息技術(shù)與工程學(xué)院　晉中　030619)

?

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

李俊麗

(晉中學(xué)院信息技術(shù)與工程學(xué)院晉中030619)

摘要隨著數(shù)據(jù)挖掘技術(shù)的發(fā)展，聚類分析算法越來(lái)越多，由于分析高維數(shù)據(jù)有時(shí)會(huì)陷入所謂維災(zāi)難，傳統(tǒng)的聚類算法在聚類高維數(shù)據(jù)時(shí)性能會(huì)降低很多。針對(duì)這種情況，提出了子空間聚類算法，極大地改善了這個(gè)問題。K-Means算法是一種應(yīng)用很廣泛的聚類算法，與子空間聚類算法結(jié)合可以應(yīng)用于高維數(shù)據(jù)聚類。介紹了三類基于K-Means的軟子空間聚類算法，并對(duì)每種算法進(jìn)行了描述和分析，最后指出了進(jìn)一步的研究方向。

關(guān)鍵詞K-Means算法; 軟子空間聚類; 高維數(shù)據(jù)聚類

Class NumberTP301

1引言

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

在高維數(shù)據(jù)中，簇通常是嵌入在原始數(shù)據(jù)空間的子空間，且不同的簇可以嵌入到不同的子空間中，所以子空間聚類方法在高維數(shù)據(jù)聚類中是必需的。子空間聚類算法是從高維數(shù)據(jù)空間中發(fā)現(xiàn)隱藏在不同低維子空間中的簇類。很多文獻(xiàn)提出了許多子空間聚類算法來(lái)處理高維數(shù)據(jù)，旨在從子空間而不是整個(gè)數(shù)據(jù)空間發(fā)現(xiàn)簇類[4～5]。此類算法能有效減少數(shù)據(jù)冗余和不相關(guān)屬性對(duì)聚類過(guò)程的干擾，從而提高在高維數(shù)據(jù)集上的聚類結(jié)果。將K均值聚類算法與子空間聚類相結(jié)合能夠更好地應(yīng)用在高維數(shù)據(jù)聚類中，從而克服了傳統(tǒng)聚類技術(shù)的不足之處。

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

2.1K-Means算法

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

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

輸入:簇的個(gè)數(shù)k以及數(shù)據(jù)集合D

輸出:滿足條件的k個(gè)簇

step1. 從數(shù)據(jù)集D中隨機(jī)選擇k個(gè)點(diǎn)作為初始簇中心；

step2. repeat；

step3. 計(jì)算每個(gè)點(diǎn)與各個(gè)中心點(diǎn)的距離，把對(duì)象指派到最近的簇中心，形成K個(gè)簇；

step4. 重新計(jì)算每個(gè)簇的均值，作為新的簇中心；

step5. until簇中心不再發(fā)生變化為止。

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

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

2.2軟子空間聚類

軟子空間聚類算法是通過(guò)對(duì)各個(gè)數(shù)據(jù)簇類中的單個(gè)特征加權(quán)，獲得每個(gè)數(shù)據(jù)特征的重要性，從而發(fā)現(xiàn)大權(quán)重的特征所在的子空間[9～11]。相比較于硬子空間聚類算法來(lái)說(shuō)，由于對(duì)數(shù)據(jù)的處理有更好的靈活性與適應(yīng)性，人們對(duì)軟子空間聚類算法的關(guān)注越來(lái)越多。

為了更好地獲得每個(gè)簇類所在的最佳子空間，人們將K-Means聚類算法與軟子空間聚類算法相結(jié)合，采用了經(jīng)典的K-Means型算法的結(jié)構(gòu)，并且在其基礎(chǔ)之上增加了一個(gè)迭代的步驟來(lái)計(jì)算加權(quán)公式，從而得出每個(gè)簇類及其相關(guān)聯(lián)的維度的權(quán)重集合，然后更新權(quán)值向量。

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

3.1模糊加權(quán)軟子空間聚類算法

2004年，E.Y. Chan等通過(guò)引入模糊權(quán)重指數(shù)和模糊加權(quán)指數(shù)，提出了模糊加權(quán)軟子空間聚類算法[12]，其目標(biāo)函數(shù)定義如下:

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

(1)

subject to

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

模糊加權(quán)軟子空間聚類算法運(yùn)用模糊優(yōu)化技術(shù)對(duì)目標(biāo)函數(shù)優(yōu)化，對(duì)于不同的數(shù)據(jù)集，根據(jù)需要對(duì)模糊指數(shù)的取值進(jìn)行調(diào)整。因此，相比較于經(jīng)典加權(quán)算法，模糊加權(quán)算法具有很好的適應(yīng)性。

3.2熵加權(quán)軟子空間聚類

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

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

(2)

subject to

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

現(xiàn)有的子空間聚類算法僅對(duì)特征子空間進(jìn)行聚類，沒有考慮特征組權(quán)重的問題，在聚類高維數(shù)據(jù)時(shí)沒有使用特征組的信息，以下介紹特征組加權(quán)，在加權(quán)子空間聚類的基礎(chǔ)上，融入更多的特征組信息對(duì)改進(jìn)現(xiàn)有的算法是很有意義的。

3.3特征組加權(quán)軟子空間聚類

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

這種算法中，高維數(shù)據(jù)基于它們的自然特性被分為特征組。算法給出一個(gè)新的優(yōu)化模型定義優(yōu)化過(guò)程。其目標(biāo)函數(shù)定義如下:

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

(3)

subject to

該算法通過(guò)在子空間中對(duì)特征組和單個(gè)特征進(jìn)行加權(quán)，自動(dòng)計(jì)算出兩種類型的子空間熵。但是，F(xiàn)GKM算法的缺點(diǎn)是要求在聚類之前就確定特征組信息，而且在聚類過(guò)程中要作為輸入給出。在大多數(shù)情況下，我們無(wú)法確定一個(gè)高維數(shù)據(jù)集特征組的信息。因此，G. Gan等在FGKM算法的基礎(chǔ)上提出了AFGKM軟子空間聚類算法[20]，此算法能夠在聚類迭代過(guò)程中自動(dòng)確定特征組信息，通過(guò)加入特征組自動(dòng)選擇功能從而擴(kuò)展了FGKM算法，AFGKM算法會(huì)產(chǎn)生比FGkM算法更準(zhǔn)確的聚類結(jié)果。

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

基于K-Means的軟子空間聚類算法的共同特點(diǎn)是:首先定義目標(biāo)函數(shù)，利用一些優(yōu)化方法求出最小化的解；其次，經(jīng)過(guò)推導(dǎo)得出權(quán)值向量的迭代計(jì)算公式；最后，目標(biāo)函數(shù)是否有效決定了聚類結(jié)果的好壞。基于K-Means的算法都具有較好的擴(kuò)展性，在計(jì)算高維數(shù)據(jù)時(shí)，具有較好的適用性。但是，其也繼承了K-Means 算法的缺點(diǎn)，為了進(jìn)一步提高算法的穩(wěn)定性，選擇適當(dāng)?shù)某跏即刂行氖瞧潢P(guān)鍵步驟。

因而進(jìn)一步的研究工作歸納如下:

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

2) 現(xiàn)有的算法在定義加權(quán)方式時(shí)都引入了一些難以確定的參數(shù)，需要用戶提供專門的領(lǐng)域知識(shí)來(lái)設(shè)置它們的輸入?yún)?shù)，而且不同簇使用了相同的參數(shù)，這樣對(duì)于不同結(jié)構(gòu)的簇，參數(shù)不能自動(dòng)調(diào)節(jié)，致使算法的適用性降低了很多，算法對(duì)于不同聚類問題的泛化能力也降低了很多。

3) 現(xiàn)有的軟子空間聚類算法大多數(shù)是不完備的，沒有考慮到子空間的優(yōu)化問題，而只是過(guò)多關(guān)心數(shù)據(jù)集劃分的優(yōu)化問題。

4) 現(xiàn)有的軟子空間聚類算法都是基于批處理技術(shù)的聚類算法不能很好地應(yīng)用于高維數(shù)據(jù)流。

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

5結(jié)語(yǔ)

軟子空間聚類算法受到越來(lái)越多的關(guān)注，文中首先介紹了傳統(tǒng)的K-Means聚類算法,然后在此基礎(chǔ)上結(jié)合子空間聚類算法給出了幾種基于K-Means的軟子空間聚類算法,通過(guò)對(duì)每種算法進(jìn)行了綜述和分析,指出了一些不足之處，最后確定了進(jìn)一步研究的方向，對(duì)以后的子空間聚類的研究有一定指導(dǎo)意義。

參 考 文 獻(xiàn)

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

[2] D.Hand, H.Mannila, P.Smyth.數(shù)據(jù)挖掘原理[M].張銀奎,廖麗,宋俊,等譯.北京:機(jī)械工業(yè)出版社,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日

作者簡(jiǎn)介：李俊麗,女,講師，碩士,研究方向：數(shù)據(jù)挖掘。

中圖分類號(hào)TP301

DOI：10.3969/j.issn.1672-9730.2016.05.011