基于數據抽樣的自動k?means聚類算法

羅軍鋒+洪丹丹

摘 要： 為了解決傳統k?means算法需要輸入k值和在超大規模數據集進行聚類的問題，這里在前人研究基礎上，首先在計算距離時引入信息熵，在超大規模數據集采用數據抽樣，抽取最優樣本數個樣本進行聚類，在抽樣數據聚類的基礎上進行有效性指標的驗證，并且獲得算法所需要的k值，然后利用引入信息熵的距離公式再在超大數據集上進行聚類。實驗表明，該算法解決了傳統k?means算法輸入k值的缺陷，通過數據抽樣在不影響數據聚類質量的前題下自動獲取超大數據集聚類的k值。

關鍵詞： k?means算法； 信息熵； 最優樣本抽取； 有效性指標

中圖分類號： TN911?34； TP311文獻標識碼： A 文章編號： 1004?373X（2014）08?0019?03

Automatic k?means clustering algorithm based on data sampling

LUO Jun?feng， HONG Dan?dan

（Information center， Xian Jiaotong University， Xian 710049， China）

Abstract： In order to solve the problems of the traditional k?means algorithm in which k values ??needs to be input and the the ultra?large?scale data set needs to be clustered， on the basis of previous studies， the information entropy is brought in when distance is calculated， and data sampling method is adopted， that is， the optimal samples are extracted from the ultra?large?scale data set to conduct sample clustering. Based on the sample data clustering， the validity indexes are verified and k value required by the algorithm is obtained. The distance formula for information entropy is brought in to carry out clustering on the ultra?large data set. Experiments show that the algorithm can overcome the defects of traditional k?means algorithm for k value input， and can automatically obtain k values ??of ultra?large data clustering under the premise of not affecting the quality of the early data clustering.

Keywords： k?means algorithm； information entropy； optimal sample extraction； validity index

0引言

聚類是數據挖掘中重要的三個領域（關聯規則，聚類和分類）之一。它按照特定要求，對待分類的對象進行分類，要求類內相似度盡可能最大，同時類間相似度盡可能最小。k?means[1]算法因其簡單實用而成為應用和研究最廣泛的算法之一。但是該算法需要事先確定k值，而確定最佳k值一直也是聚類有效性研究的重要課題。一般情況下，確定最佳k值的基本思想為：在k值取值范圍內運行k?means算法，得到不同的結果，選擇合適的有效性評估指標對結果進行評估，最終確定最佳k值。近年來，許多研究人員對于如何確定最佳k值進行了深入的研究。包括聚類有效性指的研究，如XB（Xie?Beni）[2]，KL（Krzanowski?Lai）[3]，Sil（Silhouette）[4]，DB（Davies?Bouldin）[5]，IGP（In?Group Proportion）[6]，BWP（Between?Within Proportion）[7]。同時文獻[8]研究了k值最優解[kopt]及其上限[kmax]的條件，證明了[kmax≤n]。但是這些研究沒有基于海量數據之上，當數據量急劇擴大時，以上方法進行確定k值的效率由于數據的急劇擴大而得不償失。因此，本文借鑒前人的研究成果，首先通過引入信息熵對前人的有效性指標進行了改進，針對海量數據集的數據挖掘，提出了基于數據抽樣的k?means自動挖掘算法。該算法采用分段抽樣策略，以新指標為有效性驗證標準，通過引入統計最優數據抽樣數，得到抽樣數據的k值，然后將該k值應用到海量數據集上進行聚類，取得了良好的效果。

1相關概念和原理

1.1最優抽樣數和抽樣策略

衡量抽樣效果的兩個重要指標分別為樣本容量和樣本質量[9]。所謂樣本容量是指所抽取的樣本數，所謂樣本質量是抽樣樣本的代表性，是抽樣中的一個重要指標。在抽樣過程中，如果樣本集的容量越大，其與原數據集的相似程度也就越好，因而挖掘出來的結果與從原數據集挖掘結果的一致性也就越好。但是，抽樣后挖掘結果的準確性和效率是一對矛盾體，樣本量大，準確性高，效率低；樣本量小，準確性低，效率高。

另外，當樣本量增加超過一定規模后，準確性不會有足夠的提升，將在保證結果準確性的情況下，抽取的最小樣本量為最優樣本數（Optimal Sample Size，OSS），準確尋找最優樣本數非常麻煩，為此，本文引入文獻[9]中的統計最優樣本數來代替OSS。

1.2基于熵權重的距離度量

為提高算法的性能，對數據集中計算數據對象距離時采用加權距離，權重值的計算使用信息熵來確定。數據集中的各維屬性對聚類結果的影響程度不同，并且不同的鄰居對該數據的歸類也有不同的影響。于是，本文借鑒文獻[10]，引入信息熵的概念度量屬性權重的大小，并進一步求得相鄰對相之間的權重系數，最終求出基于熵權重的距離計算公式。

具體步驟如下：

（1） 設有如下屬性值矩陣，其具有n個對象，m維屬性：

? [X=x11…x1m???xn1…xnm]

（2） 構造屬性值屬性比重矩陣。為了方便不同的量綱屬性值進行比較，對屬性值進行了標準化處理。處理方法為：

[rij=max(xij)-xijmax(xij)-min(xij)]

式中：[rij]為對象[xi]的第 j 維屬性的屬性值比重。

（3） 分別計算第 j 維屬性的熵值，權值：

熵值：[Hj=-i=1nrijlnrijlnn]

權值：[wj=1-Hjj=1m（1-Hj）]， [0≤wj≤1，j=1mwj=1]

（4） 計算相鄰對象間的權重系數。設對象[xj]是數據對象[xi]的某個鄰居，則二者間的權重系數的計算公式如下：

[wij=p=1mwp×xjpxop] （1）

式中：[xop]表示對象[xi]的第 p 維屬性值，對象[xo]是對象[xi]的鄰居，[wp]是第p維屬性的權值。

從式（1）中可以看出，相鄰對象的權重系數是由對象的所有屬性，其所有鄰居共同決定，這樣在隨后計算距離時就最大限度地考慮了相鄰對象之間的相互影響及其所有屬性的影響。

那么基于信息熵的距離計算公式為：

[d(xi,xj)=wij×k=1m(xik-xjk)2]（2）

利用改進的距離計算公式可以更為準確地計算出各個數據對象之間的差距程度，在一定程度上提高了聚類的精確度。

1.3聚類有效性指標

好的聚類劃分應使類內盡可能相似，類間盡可能不相似。目前，評價聚類結果優劣的指標很多，前面都提到過，本文選擇BWP指標進行了局部改變，修改后的指標能更好地評價聚類劃分的結果。

設k={X，R}為聚類空間，其中 [X=x1,x2,...,xn]，需要將樣本聚類為c類則修改前的評價有效性指標BWP為：

[BWP(j,i)=min1≤k≤c,k≠j(1nkp=1nkxp(k),xi(j)2)-1nj-1q=1,q≠injxq(j),xi(j)2min1≤k≤c,k≠j(1nkp=1nkxp(k),xi(j)2)+1nj-1q=1,q≠injxq(j),xi(j)2] （3）

由于修改前的BWP指標在計算距離時只是使用簡單距離公式計算距離，沒有考慮到各屬性的權重，因此，本文在計算距離時引入信息熵，使用加權的距離公式，修改后的指標公式為：

[N_BWP(j,i)=min1≤k≤c,k≠j(1nkp=1nkd(xp(k),xi(j)))-1nj-1q=1,q≠injd(xq(j),xi(j))min1≤k≤c,k≠j(1nkp=1nkd(xp(k),xi(j)))+1nj-1q=1,q≠injd(xq(j),xi(j))] （4）

2基于數據抽樣的自動k?means聚類算法

結合以上分析，提出的具體算法歸納如下：

（1） 確定最優抽樣數OSS；

（2） 在全部數據集中采用簡單隨機抽樣策略抽取OSS個數據進行抽樣樣本數據聚類；

（3） 選擇聚類數的搜索范圍[[kmin，kmax]]，并且從[kmin]循環至[kmax]：

①調用k?means算法，距離公式采用式（2）對應的距離公式；

②利用式（4）計算單個樣本的BWP指標值；

③計算在該聚類數的平均BWP指標值，即求所有單個樣本BWP的簡單算術平均。

（4） 求得平均BWP指標中最大時對應的k為最佳聚類數

（5） 在全部數據集中采用式（2）的距離公式，以上一步求的最佳聚類數k進行聚類。

3仿真實驗與分析

本文實驗采用Matlab 2012b開發環境，在Intel（R） Core（TM） i5CPU 3.4 GHz，4 GB內存，Windows XP操作系統上運行。本實驗選取UCI機器學習數據庫中的Mushroom Database作為實驗數據。該數據庫包含8 124個實例，23個屬性。在實驗前，需要將stalk?root屬性上的空缺值補齊，然后進行實驗。描繪該測試數據集的樣本容量和樣本質量關系曲線如圖1所示。

圖1 Mushroom數據集的學習曲線

設切線斜率閾值為0.2，計算出本數據集的OSS為604。為了實驗，本文先后抽取了403，1 005，1 501和604這4種樣本進行抽樣聚類，結果下面會詳細分析。針對上述6組樣本進行了本算法的仿真實驗，考慮到k?means算法本身由于初始聚類中心的不確定性，因此，本實驗進行了10次實驗，實驗結果如表1所示。從表中可以看出，第一，隨著樣本數的增加，聚類精度也是提高的，但是，精度的提高速度越來越慢，說明本文引入的抽樣方法是最優確定抽樣樣本數的方法；第二，從傳統的k?means算法和本文算法比較來看，不論樣本數的多寡，本文的聚類精度都比傳統k?means算法精度高。

4結語

本文通過在傳統距離公式中引入信息熵，并進行加權處理，并將此改進引入到有效性指標中，針對大規模數據集的數據挖掘，提出了基于數據抽樣的k?means自動挖掘算法，該算法采用隨機抽樣策略，以新指標為有效性驗證標準，通過引入統計最優數據抽樣數，得到抽樣數據的k值，然后將該k值應用到大規模數據集上進行聚類，取得了良好的效果。

表1 兩種算法抽樣樣本的精度比較

參考文獻

[1] MACQUEEN James. Some methods for classification and analysis of multivariate observations [C]// Proceedings of 5?th Berkeley Symposium on Mathematical Statistics and Probability. California， USA： [s.n.]，1967： 281?297.

[2] GAO Xiao?shan， LI Jing， TAO Da?cheng. Fuzziness measurement of fuzzy sets and its application in cluster validity analysis [J]. International Journal of Fuzzy Systems， 2007， 9 （4）： 188?191.

[3] DUDOIT Sandrine， FRIDLYAND Jane. A prediction?based resampling method for estimating the number of clusters in a dataset [J]. Genome biology， 2002， 3（7）： 1?22.

[4] ROUSSEEUW P J. Silhouettes： a graphical aid to the interpretation and validation of cluster analysis [J]. Journal of computational and applied mathematics， 1987， 20： 53?65.

[5] 周世兵，徐振源，唐旭清.基于近鄰傳播算法的最佳聚類數確定方法比較研究[J].計算機科學，2011，38（2）：225?228.

[6] KAPP A V， TIBSHIRANI R. Are clusters found in one dataset present in another dataset? [J]. Biostatistics， 2007， 8（1）： 9?31.

[7] 周世兵，徐振源，唐旭清.k?means算法最佳聚類數確定方法[J].計算機應用，2010（8）：1995?1998.

[8] 楊善林，李永森，胡笑旋，等.k?means算法中的k值優化問題研究[J].系統工程理論與實踐，2006，26（2）：97?101.

[9] 于海濤.抽樣技術在數據挖掘中的應用研究[D].合肥：合肥工業大學，2006.

[10] 唐波.改進的k?means聚類算法及應用[J].軟件，2012（3）：36?40.

（4） 計算相鄰對象間的權重系數。設對象[xj]是數據對象[xi]的某個鄰居，則二者間的權重系數的計算公式如下：

[wij=p=1mwp×xjpxop] （1）

式中：[xop]表示對象[xi]的第 p 維屬性值，對象[xo]是對象[xi]的鄰居，[wp]是第p維屬性的權值。

從式（1）中可以看出，相鄰對象的權重系數是由對象的所有屬性，其所有鄰居共同決定，這樣在隨后計算距離時就最大限度地考慮了相鄰對象之間的相互影響及其所有屬性的影響。

那么基于信息熵的距離計算公式為：

[d(xi,xj)=wij×k=1m(xik-xjk)2]（2）

利用改進的距離計算公式可以更為準確地計算出各個數據對象之間的差距程度，在一定程度上提高了聚類的精確度。

1.3聚類有效性指標

好的聚類劃分應使類內盡可能相似，類間盡可能不相似。目前，評價聚類結果優劣的指標很多，前面都提到過，本文選擇BWP指標進行了局部改變，修改后的指標能更好地評價聚類劃分的結果。

設k={X，R}為聚類空間，其中 [X=x1,x2,...,xn]，需要將樣本聚類為c類則修改前的評價有效性指標BWP為：

[BWP(j,i)=min1≤k≤c,k≠j(1nkp=1nkxp(k),xi(j)2)-1nj-1q=1,q≠injxq(j),xi(j)2min1≤k≤c,k≠j(1nkp=1nkxp(k),xi(j)2)+1nj-1q=1,q≠injxq(j),xi(j)2] （3）

由于修改前的BWP指標在計算距離時只是使用簡單距離公式計算距離，沒有考慮到各屬性的權重，因此，本文在計算距離時引入信息熵，使用加權的距離公式，修改后的指標公式為：

[N_BWP(j,i)=min1≤k≤c,k≠j(1nkp=1nkd(xp(k),xi(j)))-1nj-1q=1,q≠injd(xq(j),xi(j))min1≤k≤c,k≠j(1nkp=1nkd(xp(k),xi(j)))+1nj-1q=1,q≠injd(xq(j),xi(j))] （4）

2基于數據抽樣的自動k?means聚類算法

結合以上分析，提出的具體算法歸納如下：

（1） 確定最優抽樣數OSS；

（2） 在全部數據集中采用簡單隨機抽樣策略抽取OSS個數據進行抽樣樣本數據聚類；

（3） 選擇聚類數的搜索范圍[[kmin，kmax]]，并且從[kmin]循環至[kmax]：

①調用k?means算法，距離公式采用式（2）對應的距離公式；

②利用式（4）計算單個樣本的BWP指標值；

③計算在該聚類數的平均BWP指標值，即求所有單個樣本BWP的簡單算術平均。

（4） 求得平均BWP指標中最大時對應的k為最佳聚類數

（5） 在全部數據集中采用式（2）的距離公式，以上一步求的最佳聚類數k進行聚類。

3仿真實驗與分析

本文實驗采用Matlab 2012b開發環境，在Intel（R） Core（TM） i5CPU 3.4 GHz，4 GB內存，Windows XP操作系統上運行。本實驗選取UCI機器學習數據庫中的Mushroom Database作為實驗數據。該數據庫包含8 124個實例，23個屬性。在實驗前，需要將stalk?root屬性上的空缺值補齊，然后進行實驗。描繪該測試數據集的樣本容量和樣本質量關系曲線如圖1所示。

圖1 Mushroom數據集的學習曲線

設切線斜率閾值為0.2，計算出本數據集的OSS為604。為了實驗，本文先后抽取了403，1 005，1 501和604這4種樣本進行抽樣聚類，結果下面會詳細分析。針對上述6組樣本進行了本算法的仿真實驗，考慮到k?means算法本身由于初始聚類中心的不確定性，因此，本實驗進行了10次實驗，實驗結果如表1所示。從表中可以看出，第一，隨著樣本數的增加，聚類精度也是提高的，但是，精度的提高速度越來越慢，說明本文引入的抽樣方法是最優確定抽樣樣本數的方法；第二，從傳統的k?means算法和本文算法比較來看，不論樣本數的多寡，本文的聚類精度都比傳統k?means算法精度高。

4結語

本文通過在傳統距離公式中引入信息熵，并進行加權處理，并將此改進引入到有效性指標中，針對大規模數據集的數據挖掘，提出了基于數據抽樣的k?means自動挖掘算法，該算法采用隨機抽樣策略，以新指標為有效性驗證標準，通過引入統計最優數據抽樣數，得到抽樣數據的k值，然后將該k值應用到大規模數據集上進行聚類，取得了良好的效果。

表1 兩種算法抽樣樣本的精度比較

參考文獻

[1] MACQUEEN James. Some methods for classification and analysis of multivariate observations [C]// Proceedings of 5?th Berkeley Symposium on Mathematical Statistics and Probability. California， USA： [s.n.]，1967： 281?297.

[2] GAO Xiao?shan， LI Jing， TAO Da?cheng. Fuzziness measurement of fuzzy sets and its application in cluster validity analysis [J]. International Journal of Fuzzy Systems， 2007， 9 （4）： 188?191.

[3] DUDOIT Sandrine， FRIDLYAND Jane. A prediction?based resampling method for estimating the number of clusters in a dataset [J]. Genome biology， 2002， 3（7）： 1?22.

[4] ROUSSEEUW P J. Silhouettes： a graphical aid to the interpretation and validation of cluster analysis [J]. Journal of computational and applied mathematics， 1987， 20： 53?65.

[5] 周世兵，徐振源，唐旭清.基于近鄰傳播算法的最佳聚類數確定方法比較研究[J].計算機科學，2011，38（2）：225?228.

[6] KAPP A V， TIBSHIRANI R. Are clusters found in one dataset present in another dataset? [J]. Biostatistics， 2007， 8（1）： 9?31.

[7] 周世兵，徐振源，唐旭清.k?means算法最佳聚類數確定方法[J].計算機應用，2010（8）：1995?1998.

[8] 楊善林，李永森，胡笑旋，等.k?means算法中的k值優化問題研究[J].系統工程理論與實踐，2006，26（2）：97?101.

[9] 于海濤.抽樣技術在數據挖掘中的應用研究[D].合肥：合肥工業大學，2006.

[10] 唐波.改進的k?means聚類算法及應用[J].軟件，2012（3）：36?40.

（4） 計算相鄰對象間的權重系數。設對象[xj]是數據對象[xi]的某個鄰居，則二者間的權重系數的計算公式如下：

[wij=p=1mwp×xjpxop] （1）

式中：[xop]表示對象[xi]的第 p 維屬性值，對象[xo]是對象[xi]的鄰居，[wp]是第p維屬性的權值。

從式（1）中可以看出，相鄰對象的權重系數是由對象的所有屬性，其所有鄰居共同決定，這樣在隨后計算距離時就最大限度地考慮了相鄰對象之間的相互影響及其所有屬性的影響。

那么基于信息熵的距離計算公式為：

[d(xi,xj)=wij×k=1m(xik-xjk)2]（2）

利用改進的距離計算公式可以更為準確地計算出各個數據對象之間的差距程度，在一定程度上提高了聚類的精確度。

1.3聚類有效性指標

好的聚類劃分應使類內盡可能相似，類間盡可能不相似。目前，評價聚類結果優劣的指標很多，前面都提到過，本文選擇BWP指標進行了局部改變，修改后的指標能更好地評價聚類劃分的結果。

設k={X，R}為聚類空間，其中 [X=x1,x2,...,xn]，需要將樣本聚類為c類則修改前的評價有效性指標BWP為：

[BWP(j,i)=min1≤k≤c,k≠j(1nkp=1nkxp(k),xi(j)2)-1nj-1q=1,q≠injxq(j),xi(j)2min1≤k≤c,k≠j(1nkp=1nkxp(k),xi(j)2)+1nj-1q=1,q≠injxq(j),xi(j)2] （3）

由于修改前的BWP指標在計算距離時只是使用簡單距離公式計算距離，沒有考慮到各屬性的權重，因此，本文在計算距離時引入信息熵，使用加權的距離公式，修改后的指標公式為：

[N_BWP(j,i)=min1≤k≤c,k≠j(1nkp=1nkd(xp(k),xi(j)))-1nj-1q=1,q≠injd(xq(j),xi(j))min1≤k≤c,k≠j(1nkp=1nkd(xp(k),xi(j)))+1nj-1q=1,q≠injd(xq(j),xi(j))] （4）

2基于數據抽樣的自動k?means聚類算法

結合以上分析，提出的具體算法歸納如下：

（1） 確定最優抽樣數OSS；

（2） 在全部數據集中采用簡單隨機抽樣策略抽取OSS個數據進行抽樣樣本數據聚類；

（3） 選擇聚類數的搜索范圍[[kmin，kmax]]，并且從[kmin]循環至[kmax]：

①調用k?means算法，距離公式采用式（2）對應的距離公式；

②利用式（4）計算單個樣本的BWP指標值；

③計算在該聚類數的平均BWP指標值，即求所有單個樣本BWP的簡單算術平均。

（4） 求得平均BWP指標中最大時對應的k為最佳聚類數

（5） 在全部數據集中采用式（2）的距離公式，以上一步求的最佳聚類數k進行聚類。

3仿真實驗與分析

本文實驗采用Matlab 2012b開發環境，在Intel（R） Core（TM） i5CPU 3.4 GHz，4 GB內存，Windows XP操作系統上運行。本實驗選取UCI機器學習數據庫中的Mushroom Database作為實驗數據。該數據庫包含8 124個實例，23個屬性。在實驗前，需要將stalk?root屬性上的空缺值補齊，然后進行實驗。描繪該測試數據集的樣本容量和樣本質量關系曲線如圖1所示。

圖1 Mushroom數據集的學習曲線

設切線斜率閾值為0.2，計算出本數據集的OSS為604。為了實驗，本文先后抽取了403，1 005，1 501和604這4種樣本進行抽樣聚類，結果下面會詳細分析。針對上述6組樣本進行了本算法的仿真實驗，考慮到k?means算法本身由于初始聚類中心的不確定性，因此，本實驗進行了10次實驗，實驗結果如表1所示。從表中可以看出，第一，隨著樣本數的增加，聚類精度也是提高的，但是，精度的提高速度越來越慢，說明本文引入的抽樣方法是最優確定抽樣樣本數的方法；第二，從傳統的k?means算法和本文算法比較來看，不論樣本數的多寡，本文的聚類精度都比傳統k?means算法精度高。

4結語

本文通過在傳統距離公式中引入信息熵，并進行加權處理，并將此改進引入到有效性指標中，針對大規模數據集的數據挖掘，提出了基于數據抽樣的k?means自動挖掘算法，該算法采用隨機抽樣策略，以新指標為有效性驗證標準，通過引入統計最優數據抽樣數，得到抽樣數據的k值，然后將該k值應用到大規模數據集上進行聚類，取得了良好的效果。

表1 兩種算法抽樣樣本的精度比較

參考文獻

[1] MACQUEEN James. Some methods for classification and analysis of multivariate observations [C]// Proceedings of 5?th Berkeley Symposium on Mathematical Statistics and Probability. California， USA： [s.n.]，1967： 281?297.

[2] GAO Xiao?shan， LI Jing， TAO Da?cheng. Fuzziness measurement of fuzzy sets and its application in cluster validity analysis [J]. International Journal of Fuzzy Systems， 2007， 9 （4）： 188?191.

[3] DUDOIT Sandrine， FRIDLYAND Jane. A prediction?based resampling method for estimating the number of clusters in a dataset [J]. Genome biology， 2002， 3（7）： 1?22.

[4] ROUSSEEUW P J. Silhouettes： a graphical aid to the interpretation and validation of cluster analysis [J]. Journal of computational and applied mathematics， 1987， 20： 53?65.

[5] 周世兵，徐振源，唐旭清.基于近鄰傳播算法的最佳聚類數確定方法比較研究[J].計算機科學，2011，38（2）：225?228.

[6] KAPP A V， TIBSHIRANI R. Are clusters found in one dataset present in another dataset? [J]. Biostatistics， 2007， 8（1）： 9?31.

[7] 周世兵，徐振源，唐旭清.k?means算法最佳聚類數確定方法[J].計算機應用，2010（8）：1995?1998.

[8] 楊善林，李永森，胡笑旋，等.k?means算法中的k值優化問題研究[J].系統工程理論與實踐，2006，26（2）：97?101.

[9] 于海濤.抽樣技術在數據挖掘中的應用研究[D].合肥：合肥工業大學，2006.

[10] 唐波.改進的k?means聚類算法及應用[J].軟件，2012（3）：36?40.