謝志明，王 鵬，黃 焱

(1.汕尾職業技術學院 信息工程系，廣東 汕尾 516600；2.汕尾市創新工業設計研究院 云計算與數據中心工程設計研究所，廣東 汕尾 516600；3.西南民族大學 計算機科學與技術學院，四川 成都 610041；4.淮陰師范學院 計算機科學與技術學院，江蘇 淮安 223300)

多維數據K-means譜聚類算法改進研究

謝志明1,2，王 鵬3，黃 焱4

(1.汕尾職業技術學院 信息工程系，廣東 汕尾 516600；2.汕尾市創新工業設計研究院 云計算與數據中心工程設計研究所，廣東 汕尾 516600；3.西南民族大學 計算機科學與技術學院，四川 成都 610041；4.淮陰師范學院 計算機科學與技術學院，江蘇 淮安 223300)

針對傳統K-means算法不能自動確定初始聚類數目k和譜聚類算法對參數敏感的問題，提出了一種基于譜聚類的K-means(PK-means)算法。該算法在對k值選取時進行了創新改進，將計算所得的高密度數據點按規律排序，選擇密度點前96%的進行聚類，可以以較高的準確率取得聚類數目k，同時采用了不受參數影響且穩定性更高的基于譜聚類模糊的相似性度量方法，利用FCM算法求隸屬度矩陣確定數據點間的相似性。應用PK-means算法、K均值算法與密度敏感的譜聚類算法(DSSC)進行了多維非線性數據處理的測試實驗。實驗結果表明，無論是對于低維數據集還是高維數據集，K-means算法的處理效率是最低的，DSSC算法稍好，而PK-means算法優勢明顯，其相比傳統聚類算法具有更高的聚類精度和更強的魯棒性，且維數越高，聚類性能表現越突出。

K-means算法；譜聚類算法；聚類；FCM算法；隸屬度矩陣

0 引 言

聚類(Clustering)是一種將類似的對象通過物理或抽象對象集合的方式劃分成若干個簇或類的過程。聚類的對象無類別標識，屬于無監督學習模式，特征是使簇內的對象相似度盡可能小，簇間的對象相似度盡可能大[1-2]。聚類算法自提出以來就已成為數據挖掘領域方面一直研究的課題，伴隨著云計算、大數據技術的相繼問世，對聚類算法的研究更是方興未艾，目前研究較多的聚類算法主要有基于劃分的K-means、基于分層的CURE、基于網格的STRING、基于密度的DBSCANE和基于模型的SOM等方法[3-4]。

K-means算法是數據挖掘領域中應用最廣泛的一種聚類分析方法，因簡單、高效、收斂快和線性時間復雜度優勢而被廣泛應用，并被用于大數據分析，其突出特點是局部搜索能力強[5-6]。但是該算法也有明顯的缺點，主要表現在初始聚類中心對聚類結果影響很大，易使算法過早陷入局部最優解；其次聚類數目k難以確定，迭代次數的增加加大了系統I/O的輸出和資源的消耗，總耗時增加；第三是孤立點對算法的影響也很大，會導致聚類結果不確定，魯棒性不高[7]。

針對該算法存在的諸多不足，已有專家學者進行了一系列的改進方案。文獻[8]利用不同聚類結果子簇之間的交集構造出關于子簇的加權連通圖，并通過其連通性合并子簇，使聚類結果在精度和效率上有了一定的提高。文獻[9]提出了依據密度點分布的情況，將高密度分布的點定為初始聚類中心，該算法比隨機選取初始聚類中心準確率高了許多，但由于選取的多個聚類中心有可能距離較為接近，失去代表性。文獻[10]提出了當最大密度參數值不唯一時，最大密度參數選取的合理方案，該方案不僅提高了聚類精度，還有效避開了對孤立點的選取。文獻[11]提出了以數據對象鄰域為基礎，選擇位于數據集樣本密集區且相距較遠的數據對象作為初始聚類中心，該算法對噪聲數據具有較強的抗干擾能力。文獻[12]基于距離最遠的樣本點最不可能分到同一個簇中的事實，構造了一種將文本相似度轉換為文本距離的方法，該方法能有效降低聚類耗時，提高F度量值。文獻[13]利用數據對象的分布密度以及計算最近兩點的垂直中點方法來確定k個初始聚類中心，該算法在低維數據集下有較高的準確率和穩定性，聚類高維數據集時準確率不高。文獻[14]利用直方圖將數據樣本空間進行了最優劃分，依據樣本分布特點確定初始聚類中心，這種算法減少了對參數的依賴，其聚類結果的準確率和效率都有了明顯提高；若針對的是高維或超高維樣本數據，伴隨迭代次數的增加，運算過程將趨于復雜化，從而導致算法效率下降。

改進K-means算法的方法很多，既能高效處理多維非線性數據又能自動確定聚類數k的改良方法和研究則很少。為此，利用K-means算法在低維樣本空間收斂速度快、擴展性好等優點，結合譜聚類算法在高維樣本空間能高效聚類任何形狀類型的數據集且對維數不敏感，可避免因維數所引起奇異性問題的優勢，提出了一種基于譜聚類的多維數據K-means聚類改進算法。其可將基于局部識別方法的譜聚類算法拓展至可全域收斂求最優解[15]，因此適用于多維非線性數據的聚類。

1 聚類數k值的確定

K-means算法和譜聚類算法都不能自動獲取到聚類數目，為解決這一問題，提出依據高密度數據點分布情況來實現聚類數目的自動確定。一般來說，數據集在低維空間中會呈現特定的分布且類類之間是不連續的，而將數據集轉移到高維空間，仍沿用低維空間的方法找到的高密度區域線性數據點進行聚類，k值的確定則變得容易許多。

輸入整個數據集X，計算每個數據點的k近鄰圖，建立一個N×N的矩陣S，其中數據集X為N維，則矩陣元素Sij的值為：

(1)

如果xi屬于xj的k鄰域，或xj屬于xi的k鄰域，則Sij=dij，否則，Sij=0。其中，Sij表示第i個元素和第j個元素之間的相似性度量，dij使用高斯核函數進行計算：

(2)

其中，‖xi-xj‖表示歐氏距離測度；dij表示數據點xi和xj的鄰接程度，由此構造了數據集X的鄰接矩陣。

由上述鄰接矩陣可定義每個數據點的相對密度，通過式(3)求得每個數據點的相對密度：

(3)

對所有數據點以降序方式重新排序，選取相對密度較高的數據點(一般選取密度最大的前96%的數據點作為高密度數據點)對其聚類，確定聚類數目k。

Xseeds={xi|den(xi)>T96,xi∈X}

(4)

2 基于譜聚類模糊的度量相似性

高斯核函數是傳統譜聚類算法中用于計算兩點間相似性度量的常用方法，是在歐幾里得距離的基礎上加入尺度參數σ擴展形成的，其聚類結果的好壞受參數影響很大，具有明顯的局限性。由于高斯核函數對尺度參數敏感，如以不同的參數挨個嘗試去做聚類，不僅增加了設備運算成本還浪費了大量時間，降低了算法效率，因此選取一種良好的相似性度量方法很有必要。文獻[16]提出了一種基于路徑相似度測量的魯棒性譜聚類算法(RPB-SC)，通過定義高斯核的鄰域加權尺度因子計算相似度和以路徑聚類思想調節全局相似度，有效減弱高斯核尺度參數的影響,提高聚類性能。實驗選取了不受參數影響且穩定性更高的基于譜聚類模糊的相似性度量方法，利用模糊C均值(Fuzzy C-Means，FCM)算法求隸屬矩陣，其任意兩點間的相似性關系可根據每個數據點對聚類中心的隸屬度關系推導求得[17]。

設現有一N維數據集X和C個聚類中心Ci(i=1,2,…,c)，1

(5)

其中，uij表示第j個數據點分別屬于第i類的程度，用0～1之間的數值表示，當對隸屬度矩陣歸一化后，該數據集的隸屬度總和為1。

(6)

模糊聚類的目標函數最小化后得到的隸屬度矩陣為：

(7)

其中，U為隸屬度矩陣；ci為模糊組I的聚類中心；dij=‖ci-xj‖為數據集ci到各個聚類中心的歐氏距離；m∈[1，∞)是一個控制模糊度的加權指數，影響隸屬度矩陣的模糊程度。

構造新的目標函數，此函數是使式(7)達到最小值的一個必要條件：

(8)

其中，λj(j=1,2,…,n)是式(6)n個約束式的拉格朗日乘子。

使式(7)達到最小化目標函數的兩個特定先決條件為：

(9)

(10)

FCM的最小目標函數通過式(9)、(10)交替更新簇ci的中心和隸屬矩陣U，直至目標函數值小于某個閾值或兩次目標函數值一個小于某個閾值，則算法停止。其過程可簡單描述為：先隨機初始化初始聚類中心，然后求隸屬度矩陣，再計算目標函數，迭代(FCM聚類算法迭代過程較為簡單)。確定隸屬度矩陣后，即可確定集群中任意兩點的相似性，如果為同一聚類中心，則相似性的概率較大，反之則較小。

基于FCM算法模糊聚類的相異性計算的實現過程如下：

Step1：輸入經FCM算法計算得到的隸屬度和最近的聚類中心數；

Step2：按照降序排列隸屬度矩陣U中的每一列，獲得一個新的矩陣U'；

Step4：令Sij=Sji；

Step5：輸出數據集的模糊相異性情況。

3 算法實現過程及實驗結果分析

3.1PK-means算法

提出的改良K-means算法是在譜聚類算法的基礎上進行擴展的，記作PK-means。由于譜聚類算法具有優秀的處理高維數據的特性，結合K-means算法后能更好地完成對高維非線性數據的聚類。將上述兩種聚類算法合二為一，使PK-means算法不僅具有自動確定聚類數目k的能力，同時還引入了譜聚類模糊的度量相似性法則來保證聚類的準確度。其算法過程如下：

Step1：確定初始聚類數k，可依據提出的自動確定聚類數目的方法進行計算；

Step2：通過FCM模糊聚類的相異性計算方法，確定相似性矩陣S；

Step6：利用K-means算法對標準化后的矩陣M'進行聚類。

3.2實驗環境和實驗數據選取

3.2.1 實驗環境

實驗選用的平臺是Windows 7專業版64位，Intel Core i5-3470 CPU @ 3.20 GHz，8.00 GB內存，1T SATA硬盤，MATLAB R2010b語言編程環境。

3.2.2 UCI實驗數據

為驗證該算法的高效性和準確率，選取了低維數據集和高維數據集作為實驗的數據源，這些數據源均來自國際上專用于測試聚類算法性能的UCI數據庫[9]。低維數據源選取了Iris、Glass和Wine，分別為4維、7維和13維，類別數為3、9和3；高維數據源選取了USPS、Yale和WebKB-Comell，抽取的樣本數均為800個。其中USPS手寫數據集的維數是256，16×16像素的灰度圖像，每一數字400幅，類別數為5；Yale人臉數據集的維數是1 024，每個人臉分割的紋理圖像是32×32像素，類別數為15；另外，特選取了維數高達4 143，類別數為7的WebKB-Comell文本數據集。實驗將使用三種不同的聚類算法，即K-means算法、密度敏感的譜聚類算法(Density-Sensitive Spectral Clustering，DSSC)[18]和PK-means算法，對所選取的多維數據集進行聚類。其中，將選擇聚類效果最優的參數進行對比驗證，實驗次數為30，驗證聚類結果的準確率。

3.3低維數據集實驗對比分析

選取低維數據集，計算其聚類的正確率，對實驗結果取平均值，如表1所示。平均正確率條形圖如圖1所示。

表1 三種算法處理低維數據集的聚類精度比 %

由表1和圖1可以看出，在低維空間時，DSSC算法比傳統的K-means算法在聚類方面性能要好，但相較于PK-means算法效率還尚有差距。究其原因，PK-means算法所體現的優勢在于，首先DSSC算法的相似性度量是對參數敏感的，而PK-means算法是基于隸屬度矩陣，不會選擇到敏感的參數；其次，PK-means算法有效地解決了K-means算法中不能高效選取簇的初始數目的問題。此外，這三種算法都有一個共同特點，隨著維數的升高，其聚類效果稍有下降，維數越高下降越明顯。為了能更好地體現PK-means算法的高效性和準確性，下面將對高維數據集進行同樣的類似實驗。

圖1 三種聚類算法處理低維數據集的平均正確率條形圖

3.4高維數據集實驗對比分析

選取高維數據集，計算其聚類的正確率，對實驗結果取平均值，如表2所示。平均正確率條形圖如圖2所示。

表2 三種算法處理高維數據集的聚類精度比 %

圖2 三種聚類算法處理高維數據集的平均正確率條形圖

從表2和圖2可以看出，在高維空間，隨著數據集維數的增大，聚類的正確率也有所下降。其中，K-means算法聚類正確率受維度數變化下降最為明顯，其次是DSSC算法，PK-means算法雖也有影響，但和前兩種算法相比，受到的波動則可算之微乎其微。

綜上，三種聚類算法處理低維數據集的準確率要高于高維數據集的準確率，而無論是在處理低維數據集還是高維數據集，K-means算法都是最低的，其次是DSSC算法，而PK-means算法優勢明顯，且維數越高，聚類性能表現越突出。

4 結束語

充分利用K-means算法收斂快和譜聚類算法對數據集維度數不敏感的特點，提出了PK-Means算法。通過高密度數據點計算并對其聚類，可較容易地獲得聚類數目k，有效解決了初始聚類中心選擇和孤立點的問題；利用模糊的度量元素相異性方法降低了譜聚類算法對參數的敏感性，并采用FCM求隸屬度矩陣的方法確定譜聚類算法中的相似度，消除了對敏感參數的選擇。實驗結果表明，PK-means算法較其他兩種算法具有更高的聚類精度與穩定性，尤其對于高維數據更具優勢。然而，該算法仍存在著較大的改進空間，當面對多維海量數據時，在實現分布式處理方式并提高集群的運行效率方面仍需要進一步深入研究。

[1] Han Jiawei,Kamber M.Data mining concepts and techniques[M].2nd ed.Beijing:China Machine Press,2006:402-404.

[2] Nagpal A,Jatain A，Gaur D.Review based on data clustering algorithms[C]//Proceedings of IEEE conference on information & communication technologies.[s.l.]:IEEE,2013:298-303.

[3] 王 慧,申石磊.一種改進的特征加權K-means聚類算法[J].微電子學與計算機,2010,27(7):161-163.

[4] Aggarwal C C,Li Yan,Wang Jianyong,et al.Frequent pattern mining with uncertain data[C]//Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining.New York:ACM Press,2009:29-38.

[5] 曹永春,蔡正琦,邵亞斌.基于K-means的改進人工蜂群聚類算法[J].計算機應用,2014,34(1):204-207.

[6] Huang Z.Extensions to the k-means algorithm for clustering large data sets with categorical values[J].Data Mining and Knowledge Discovery,1998,2(3):283-304.

[7] 邢長征,谷 浩.基于平均密度優化初始聚類中心的k-means算法[J].計算機工程與應用,2014,50(20):135-138.

[8] 雷小鋒,謝昆青,林 帆,等.一種基于K-Means局部最優性的高效聚類算法[J].軟件學報,2008,19(7):1683-1692.

[9] 韓凌波,王 強,蔣正鋒,等.一種改進的k-means初始聚類中心選取算法[J].計算機工程與應用,2010,46(17):150-152.

[10] 黃 敏,何中市,邢欣來,等.一種新的k-means聚類中心選取算法[J].計算機工程與應用,2011,47(35):132-134.

[11] 謝娟英,郭文娟,謝維信,等.基于樣本空間分布密度的初始聚類中心優化K-均值算法[J].計算機應用研究,2012,29(3):888-892.

[12] 翟東海,魚 江,高 飛,等.最大距離法選取初始簇中心的K-means文本聚類算法的研究[J].計算機應用研究,2014,31(3):713-715.

[13] 周煒奔,石躍祥.基于密度的K-means聚類中心選取的優化算法[J].計算機應用研究,2012,29(5):1726-1728.

[14] 張健沛,楊 悅,楊 靜,等.基于最優劃分的K-Means初始聚類中心選取算法[J].系統仿真學報,2009,21(9):2586-2590.

[15] 周 林,平西建,徐 森,等.基于譜聚類的聚類集成算法[J].自動化學報,2012,38(8):1335-1342.

[16] 范 敏,李澤明,石 欣.基于路徑相似度測量的魯棒性譜聚類算法[J].計算機應用研究,2015,32(2):372-375.

[17] 孫曉霞,劉曉霞,謝倩茹.模糊C-均值(FCM)聚類算法的實現[J].計算機應用與軟件,2008,25(3):48-50.

[18] 王 玲,薄列峰,焦李成.密度敏感的譜聚類[J].電子學報,2007,35(8):1577-1581.

ResearchonModificationofK-meansSpectralClusteringAlgorithmofMultidimensionalData

XIE Zhi-ming1,2，WANG Peng3，HUANG Yan4

(1.Department of Information Engineering，Shanwei Polytechnic，Shanwei 516600，China； 2.Institute of Cloud Computing & Data Center Engineering Design，Shanwei Institute of Innovative Industrial Design，Shanwei 516600，China；3.School of Computer Science and Technology，Southwest University for Nationalities，Chengdu 610041，China；4.School of Computer Science and Technology，Huaiyin Normal University，Huaian 223300，China)

Aiming at the problem that the traditionalK-means algorithm cannot determine the initial cluster numberkautomatically and spectral clustering algorithm is sensitive to parameter,a newK-means algorithm based on spectral clustering called PK-means is proposed.It makes improvement and innovation in selection ofkvalues,sorts the calculated high density data points orderly,and then picks out the frontal 96% density point to cluster,so that the number of clusterskcan be obtained with high accuracy.In the meantime,it also selects the unaffected and higher stable similarity measure method based on spectral clustering fuzziness and uses the FCM algorithm for membership degree matrix so as to determine the similarity between data points.The PK-means,K-means and DSSC have been employed to deal with multi-dimensional nonlinear datasets.The experimental results show that whether the selected data source is low dimension or high dimension,the efficiency ofK-means is the lowest,followed by DSSC,and PK-means owns obvious advantages which always has the higher clustering accuracy and stronger robustness than the traditional clustering algorithm.The higher the dimension,the more prominent the clustering performance.

K-means algorithm；spectral clustering algorithm；clustering；FCM algorithm；degree of membership matrix

TP301.6

A

1673-629X(2017)10-0060-05

2016-10-27

2017-02-20 < class="emphasis_bold">網絡出版時間

時間：2017-07-11

國家自然科學基金資助項目(60702075)；廣東省科技廳高新技術產業化科技攻關項目(2011B010200007)；廣東省高等職業教育質量工程教育教學改革項目(GDJG2015244，GDJG2015245)

謝志明(1977-)，男，講師，碩士，研究方向為云計算與大數據、算法設計。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170711.1456.068.html

10.3969/j.issn.1673-629X.2017.10.013