謝志明，王 鵬，黃 焱

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

多維數(shù)據(jù)K-means譜聚類算法改進(jìn)研究

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

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

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

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

0 引 言

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

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

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

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

1 聚類數(shù)k值的確定

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

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

(1)

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

(2)

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

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

(3)

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

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

(4)

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

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

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

(5)

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

(6)

模糊聚類的目標(biāo)函數(shù)最小化后得到的隸屬度矩陣為：

(7)

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

構(gòu)造新的目標(biāo)函數(shù)，此函數(shù)是使式(7)達(dá)到最小值的一個必要條件：

(8)

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

使式(7)達(dá)到最小化目標(biāo)函數(shù)的兩個特定先決條件為：

(9)

(10)

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

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

Step1：輸入經(jīng)FCM算法計算得到的隸屬度和最近的聚類中心數(shù)；

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

Step4：令Sij=Sji；

Step5：輸出數(shù)據(jù)集的模糊相異性情況。

3 算法實現(xiàn)過程及實驗結(jié)果分析

3.1PK-means算法

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

Step1：確定初始聚類數(shù)k，可依據(jù)提出的自動確定聚類數(shù)目的方法進(jìn)行計算；

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

Step6：利用K-means算法對標(biāo)準(zhǔn)化后的矩陣M'進(jìn)行聚類。

3.2實驗環(huán)境和實驗數(shù)據(jù)選取

3.2.1 實驗環(huán)境

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

3.2.2 UCI實驗數(shù)據(jù)

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

3.3低維數(shù)據(jù)集實驗對比分析

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

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

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

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

3.4高維數(shù)據(jù)集實驗對比分析

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

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

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

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

綜上，三種聚類算法處理低維數(shù)據(jù)集的準(zhǔn)確率要高于高維數(shù)據(jù)集的準(zhǔn)確率，而無論是在處理低維數(shù)據(jù)集還是高維數(shù)據(jù)集，K-means算法都是最低的，其次是DSSC算法，而PK-means算法優(yōu)勢明顯，且維數(shù)越高，聚類性能表現(xiàn)越突出。

4 結(jié)束語

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

[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] 王 慧,申石磊.一種改進(jìn)的特征加權(quán)K-means聚類算法[J].微電子學(xué)與計算機(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ìn)人工蜂群聚類算法[J].計算機(jī)應(yīng)用,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] 邢長征,谷 浩.基于平均密度優(yōu)化初始聚類中心的k-means算法[J].計算機(jī)工程與應(yīng)用,2014,50(20):135-138.

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

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

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

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

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

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

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

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

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

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

[18] 王 玲,薄列峰,焦李成.密度敏感的譜聚類[J].電子學(xué)報,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">網(wǎng)絡(luò)出版時間

時間：2017-07-11

國家自然科學(xué)基金資助項目(60702075)；廣東省科技廳高新技術(shù)產(chǎn)業(yè)化科技攻關(guān)項目(2011B010200007)；廣東省高等職業(yè)教育質(zhì)量工程教育教學(xué)改革項目(GDJG2015244，GDJG2015245)

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

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

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