羅軍鋒+洪丹丹

摘 要： 為了解決傳統(tǒng)k?means算法需要輸入k值和在超大規(guī)模數(shù)據(jù)集進(jìn)行聚類的問題，這里在前人研究基礎(chǔ)上，首先在計(jì)算距離時(shí)引入信息熵，在超大規(guī)模數(shù)據(jù)集采用數(shù)據(jù)抽樣，抽取最優(yōu)樣本數(shù)個(gè)樣本進(jìn)行聚類，在抽樣數(shù)據(jù)聚類的基礎(chǔ)上進(jìn)行有效性指標(biāo)的驗(yàn)證，并且獲得算法所需要的k值，然后利用引入信息熵的距離公式再在超大數(shù)據(jù)集上進(jìn)行聚類。實(shí)驗(yàn)表明，該算法解決了傳統(tǒng)k?means算法輸入k值的缺陷，通過數(shù)據(jù)抽樣在不影響數(shù)據(jù)聚類質(zhì)量的前題下自動(dòng)獲取超大數(shù)據(jù)集聚類的k值。

關(guān)鍵詞： k?means算法； 信息熵； 最優(yōu)樣本抽?。?有效性指標(biāo)

中圖分類號： TN911?34； TP311文獻(xiàn)標(biāo)識碼： 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引言

聚類是數(shù)據(jù)挖掘中重要的三個(gè)領(lǐng)域（關(guān)聯(lián)規(guī)則，聚類和分類）之一。它按照特定要求，對待分類的對象進(jìn)行分類，要求類內(nèi)相似度盡可能最大，同時(shí)類間相似度盡可能最小。k?means[1]算法因其簡單實(shí)用而成為應(yīng)用和研究最廣泛的算法之一。但是該算法需要事先確定k值，而確定最佳k值一直也是聚類有效性研究的重要課題。一般情況下，確定最佳k值的基本思想為：在k值取值范圍內(nèi)運(yùn)行k?means算法，得到不同的結(jié)果，選擇合適的有效性評估指標(biāo)對結(jié)果進(jìn)行評估，最終確定最佳k值。近年來，許多研究人員對于如何確定最佳k值進(jìn)行了深入的研究。包括聚類有效性指的研究，如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]。同時(shí)文獻(xiàn)[8]研究了k值最優(yōu)解[kopt]及其上限[kmax]的條件，證明了[kmax≤n]。但是這些研究沒有基于海量數(shù)據(jù)之上，當(dāng)數(shù)據(jù)量急劇擴(kuò)大時(shí)，以上方法進(jìn)行確定k值的效率由于數(shù)據(jù)的急劇擴(kuò)大而得不償失。因此，本文借鑒前人的研究成果，首先通過引入信息熵對前人的有效性指標(biāo)進(jìn)行了改進(jìn)，針對海量數(shù)據(jù)集的數(shù)據(jù)挖掘，提出了基于數(shù)據(jù)抽樣的k?means自動(dòng)挖掘算法。該算法采用分段抽樣策略，以新指標(biāo)為有效性驗(yàn)證標(biāo)準(zhǔn)，通過引入統(tǒng)計(jì)最優(yōu)數(shù)據(jù)抽樣數(shù)，得到抽樣數(shù)據(jù)的k值，然后將該k值應(yīng)用到海量數(shù)據(jù)集上進(jìn)行聚類，取得了良好的效果。

1相關(guān)概念和原理

1.1最優(yōu)抽樣數(shù)和抽樣策略

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

另外，當(dāng)樣本量增加超過一定規(guī)模后，準(zhǔn)確性不會(huì)有足夠的提升，將在保證結(jié)果準(zhǔn)確性的情況下，抽取的最小樣本量為最優(yōu)樣本數(shù)（Optimal Sample Size，OSS），準(zhǔn)確尋找最優(yōu)樣本數(shù)非常麻煩，為此，本文引入文獻(xiàn)[9]中的統(tǒng)計(jì)最優(yōu)樣本數(shù)來代替OSS。

1.2基于熵權(quán)重的距離度量

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

具體步驟如下：

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

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

（2） 構(gòu)造屬性值屬性比重矩陣。為了方便不同的量綱屬性值進(jìn)行比較，對屬性值進(jìn)行了標(biāo)準(zhǔn)化處理。處理方法為：

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

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

（3） 分別計(jì)算第 j 維屬性的熵值，權(quán)值：

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

權(quán)值：[wj=1-Hjj=1m（1-Hj）]， [0≤wj≤1，j=1mwj=1]

（4） 計(jì)算相鄰對象間的權(quán)重系數(shù)。設(shè)對象[xj]是數(shù)據(jù)對象[xi]的某個(gè)鄰居，則二者間的權(quán)重系數(shù)的計(jì)算公式如下：

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

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

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

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

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

利用改進(jìn)的距離計(jì)算公式可以更為準(zhǔn)確地計(jì)算出各個(gè)數(shù)據(jù)對象之間的差距程度，在一定程度上提高了聚類的精確度。

1.3聚類有效性指標(biāo)

好的聚類劃分應(yīng)使類內(nèi)盡可能相似，類間盡可能不相似。目前，評價(jià)聚類結(jié)果優(yōu)劣的指標(biāo)很多，前面都提到過，本文選擇BWP指標(biāo)進(jìn)行了局部改變，修改后的指標(biāo)能更好地評價(jià)聚類劃分的結(jié)果。

設(shè)k={X，R}為聚類空間，其中 [X=x1,x2,...,xn]，需要將樣本聚類為c類則修改前的評價(jià)有效性指標(biāo)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指標(biāo)在計(jì)算距離時(shí)只是使用簡單距離公式計(jì)算距離，沒有考慮到各屬性的權(quán)重，因此，本文在計(jì)算距離時(shí)引入信息熵，使用加權(quán)的距離公式，修改后的指標(biāo)公式為：

[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基于數(shù)據(jù)抽樣的自動(dòng)k?means聚類算法

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

（1） 確定最優(yōu)抽樣數(shù)OSS；

（2） 在全部數(shù)據(jù)集中采用簡單隨機(jī)抽樣策略抽取OSS個(gè)數(shù)據(jù)進(jìn)行抽樣樣本數(shù)據(jù)聚類；

（3） 選擇聚類數(shù)的搜索范圍[[kmin，kmax]]，并且從[kmin]循環(huán)至[kmax]：

①調(diào)用k?means算法，距離公式采用式（2）對應(yīng)的距離公式；

②利用式（4）計(jì)算單個(gè)樣本的BWP指標(biāo)值；

③計(jì)算在該聚類數(shù)的平均BWP指標(biāo)值，即求所有單個(gè)樣本BWP的簡單算術(shù)平均。

（4） 求得平均BWP指標(biāo)中最大時(shí)對應(yīng)的k為最佳聚類數(shù)

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

3仿真實(shí)驗(yàn)與分析

本文實(shí)驗(yàn)采用Matlab 2012b開發(fā)環(huán)境，在Intel（R） Core（TM） i5CPU 3.4 GHz，4 GB內(nèi)存，Windows XP操作系統(tǒng)上運(yùn)行。本實(shí)驗(yàn)選取UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫中的Mushroom Database作為實(shí)驗(yàn)數(shù)據(jù)。該數(shù)據(jù)庫包含8 124個(gè)實(shí)例，23個(gè)屬性。在實(shí)驗(yàn)前，需要將stalk?root屬性上的空缺值補(bǔ)齊，然后進(jìn)行實(shí)驗(yàn)。描繪該測試數(shù)據(jù)集的樣本容量和樣本質(zhì)量關(guān)系曲線如圖1所示。

圖1 Mushroom數(shù)據(jù)集的學(xué)習(xí)曲線

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

4結(jié)語

本文通過在傳統(tǒng)距離公式中引入信息熵，并進(jìn)行加權(quán)處理，并將此改進(jìn)引入到有效性指標(biāo)中，針對大規(guī)模數(shù)據(jù)集的數(shù)據(jù)挖掘，提出了基于數(shù)據(jù)抽樣的k?means自動(dòng)挖掘算法，該算法采用隨機(jī)抽樣策略，以新指標(biāo)為有效性驗(yàn)證標(biāo)準(zhǔn)，通過引入統(tǒng)計(jì)最優(yōu)數(shù)據(jù)抽樣數(shù)，得到抽樣數(shù)據(jù)的k值，然后將該k值應(yīng)用到大規(guī)模數(shù)據(jù)集上進(jìn)行聚類，取得了良好的效果。

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

參考文獻(xiàn)

[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] 周世兵，徐振源，唐旭清.基于近鄰傳播算法的最佳聚類數(shù)確定方法比較研究[J].計(jì)算機(jī)科學(xué)，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算法最佳聚類數(shù)確定方法[J].計(jì)算機(jī)應(yīng)用，2010（8）：1995?1998.

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

[9] 于海濤.抽樣技術(shù)在數(shù)據(jù)挖掘中的應(yīng)用研究[D].合肥：合肥工業(yè)大學(xué)，2006.

[10] 唐波.改進(jìn)的k?means聚類算法及應(yīng)用[J].軟件，2012（3）：36?40.

（4） 計(jì)算相鄰對象間的權(quán)重系數(shù)。設(shè)對象[xj]是數(shù)據(jù)對象[xi]的某個(gè)鄰居，則二者間的權(quán)重系數(shù)的計(jì)算公式如下：

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

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

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

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

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

利用改進(jìn)的距離計(jì)算公式可以更為準(zhǔn)確地計(jì)算出各個(gè)數(shù)據(jù)對象之間的差距程度，在一定程度上提高了聚類的精確度。

1.3聚類有效性指標(biāo)

好的聚類劃分應(yīng)使類內(nèi)盡可能相似，類間盡可能不相似。目前，評價(jià)聚類結(jié)果優(yōu)劣的指標(biāo)很多，前面都提到過，本文選擇BWP指標(biāo)進(jìn)行了局部改變，修改后的指標(biāo)能更好地評價(jià)聚類劃分的結(jié)果。

設(shè)k={X，R}為聚類空間，其中 [X=x1,x2,...,xn]，需要將樣本聚類為c類則修改前的評價(jià)有效性指標(biāo)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指標(biāo)在計(jì)算距離時(shí)只是使用簡單距離公式計(jì)算距離，沒有考慮到各屬性的權(quán)重，因此，本文在計(jì)算距離時(shí)引入信息熵，使用加權(quán)的距離公式，修改后的指標(biāo)公式為：

[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基于數(shù)據(jù)抽樣的自動(dòng)k?means聚類算法

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

（1） 確定最優(yōu)抽樣數(shù)OSS；

（2） 在全部數(shù)據(jù)集中采用簡單隨機(jī)抽樣策略抽取OSS個(gè)數(shù)據(jù)進(jìn)行抽樣樣本數(shù)據(jù)聚類；

（3） 選擇聚類數(shù)的搜索范圍[[kmin，kmax]]，并且從[kmin]循環(huán)至[kmax]：

①調(diào)用k?means算法，距離公式采用式（2）對應(yīng)的距離公式；

②利用式（4）計(jì)算單個(gè)樣本的BWP指標(biāo)值；

③計(jì)算在該聚類數(shù)的平均BWP指標(biāo)值，即求所有單個(gè)樣本BWP的簡單算術(shù)平均。

（4） 求得平均BWP指標(biāo)中最大時(shí)對應(yīng)的k為最佳聚類數(shù)

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

3仿真實(shí)驗(yàn)與分析

本文實(shí)驗(yàn)采用Matlab 2012b開發(fā)環(huán)境，在Intel（R） Core（TM） i5CPU 3.4 GHz，4 GB內(nèi)存，Windows XP操作系統(tǒng)上運(yùn)行。本實(shí)驗(yàn)選取UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫中的Mushroom Database作為實(shí)驗(yàn)數(shù)據(jù)。該數(shù)據(jù)庫包含8 124個(gè)實(shí)例，23個(gè)屬性。在實(shí)驗(yàn)前，需要將stalk?root屬性上的空缺值補(bǔ)齊，然后進(jìn)行實(shí)驗(yàn)。描繪該測試數(shù)據(jù)集的樣本容量和樣本質(zhì)量關(guān)系曲線如圖1所示。

圖1 Mushroom數(shù)據(jù)集的學(xué)習(xí)曲線

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

4結(jié)語

本文通過在傳統(tǒng)距離公式中引入信息熵，并進(jìn)行加權(quán)處理，并將此改進(jìn)引入到有效性指標(biāo)中，針對大規(guī)模數(shù)據(jù)集的數(shù)據(jù)挖掘，提出了基于數(shù)據(jù)抽樣的k?means自動(dòng)挖掘算法，該算法采用隨機(jī)抽樣策略，以新指標(biāo)為有效性驗(yàn)證標(biāo)準(zhǔn)，通過引入統(tǒng)計(jì)最優(yōu)數(shù)據(jù)抽樣數(shù)，得到抽樣數(shù)據(jù)的k值，然后將該k值應(yīng)用到大規(guī)模數(shù)據(jù)集上進(jìn)行聚類，取得了良好的效果。

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

參考文獻(xiàn)

[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] 周世兵，徐振源，唐旭清.基于近鄰傳播算法的最佳聚類數(shù)確定方法比較研究[J].計(jì)算機(jī)科學(xué)，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算法最佳聚類數(shù)確定方法[J].計(jì)算機(jī)應(yīng)用，2010（8）：1995?1998.

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

[9] 于海濤.抽樣技術(shù)在數(shù)據(jù)挖掘中的應(yīng)用研究[D].合肥：合肥工業(yè)大學(xué)，2006.

[10] 唐波.改進(jìn)的k?means聚類算法及應(yīng)用[J].軟件，2012（3）：36?40.

（4） 計(jì)算相鄰對象間的權(quán)重系數(shù)。設(shè)對象[xj]是數(shù)據(jù)對象[xi]的某個(gè)鄰居，則二者間的權(quán)重系數(shù)的計(jì)算公式如下：

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

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

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

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

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

利用改進(jìn)的距離計(jì)算公式可以更為準(zhǔn)確地計(jì)算出各個(gè)數(shù)據(jù)對象之間的差距程度，在一定程度上提高了聚類的精確度。

1.3聚類有效性指標(biāo)

好的聚類劃分應(yīng)使類內(nèi)盡可能相似，類間盡可能不相似。目前，評價(jià)聚類結(jié)果優(yōu)劣的指標(biāo)很多，前面都提到過，本文選擇BWP指標(biāo)進(jìn)行了局部改變，修改后的指標(biāo)能更好地評價(jià)聚類劃分的結(jié)果。

設(shè)k={X，R}為聚類空間，其中 [X=x1,x2,...,xn]，需要將樣本聚類為c類則修改前的評價(jià)有效性指標(biāo)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指標(biāo)在計(jì)算距離時(shí)只是使用簡單距離公式計(jì)算距離，沒有考慮到各屬性的權(quán)重，因此，本文在計(jì)算距離時(shí)引入信息熵，使用加權(quán)的距離公式，修改后的指標(biāo)公式為：

[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基于數(shù)據(jù)抽樣的自動(dòng)k?means聚類算法

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

（1） 確定最優(yōu)抽樣數(shù)OSS；

（2） 在全部數(shù)據(jù)集中采用簡單隨機(jī)抽樣策略抽取OSS個(gè)數(shù)據(jù)進(jìn)行抽樣樣本數(shù)據(jù)聚類；

（3） 選擇聚類數(shù)的搜索范圍[[kmin，kmax]]，并且從[kmin]循環(huán)至[kmax]：

①調(diào)用k?means算法，距離公式采用式（2）對應(yīng)的距離公式；

②利用式（4）計(jì)算單個(gè)樣本的BWP指標(biāo)值；

③計(jì)算在該聚類數(shù)的平均BWP指標(biāo)值，即求所有單個(gè)樣本BWP的簡單算術(shù)平均。

（4） 求得平均BWP指標(biāo)中最大時(shí)對應(yīng)的k為最佳聚類數(shù)

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

3仿真實(shí)驗(yàn)與分析

本文實(shí)驗(yàn)采用Matlab 2012b開發(fā)環(huán)境，在Intel（R） Core（TM） i5CPU 3.4 GHz，4 GB內(nèi)存，Windows XP操作系統(tǒng)上運(yùn)行。本實(shí)驗(yàn)選取UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫中的Mushroom Database作為實(shí)驗(yàn)數(shù)據(jù)。該數(shù)據(jù)庫包含8 124個(gè)實(shí)例，23個(gè)屬性。在實(shí)驗(yàn)前，需要將stalk?root屬性上的空缺值補(bǔ)齊，然后進(jìn)行實(shí)驗(yàn)。描繪該測試數(shù)據(jù)集的樣本容量和樣本質(zhì)量關(guān)系曲線如圖1所示。

圖1 Mushroom數(shù)據(jù)集的學(xué)習(xí)曲線

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

4結(jié)語

本文通過在傳統(tǒng)距離公式中引入信息熵，并進(jìn)行加權(quán)處理，并將此改進(jìn)引入到有效性指標(biāo)中，針對大規(guī)模數(shù)據(jù)集的數(shù)據(jù)挖掘，提出了基于數(shù)據(jù)抽樣的k?means自動(dòng)挖掘算法，該算法采用隨機(jī)抽樣策略，以新指標(biāo)為有效性驗(yàn)證標(biāo)準(zhǔn)，通過引入統(tǒng)計(jì)最優(yōu)數(shù)據(jù)抽樣數(shù)，得到抽樣數(shù)據(jù)的k值，然后將該k值應(yīng)用到大規(guī)模數(shù)據(jù)集上進(jìn)行聚類，取得了良好的效果。

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

參考文獻(xiàn)

[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] 周世兵，徐振源，唐旭清.基于近鄰傳播算法的最佳聚類數(shù)確定方法比較研究[J].計(jì)算機(jī)科學(xué)，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算法最佳聚類數(shù)確定方法[J].計(jì)算機(jī)應(yīng)用，2010（8）：1995?1998.

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

[9] 于海濤.抽樣技術(shù)在數(shù)據(jù)挖掘中的應(yīng)用研究[D].合肥：合肥工業(yè)大學(xué)，2006.

[10] 唐波.改進(jìn)的k?means聚類算法及應(yīng)用[J].軟件，2012（3）：36?40.