可變網(wǎng)格優(yōu)化的K-means聚類方法

萬(wàn) 靜,張 超,何云斌,李 松

(哈爾濱理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,哈爾濱 150080)

1 引 言

聚類分析是數(shù)據(jù)挖掘的重要組成部分,已經(jīng)被廣泛地應(yīng)用到了很多領(lǐng)域,包括web搜索,圖像分割[1],生物學(xué)[2]等.聚類是一種無(wú)監(jiān)督學(xué)習(xí),即沒(méi)有提供類標(biāo)號(hào)信息.到目前為止,主要的聚類方法分如下幾類:基于劃分的方法,基于層次的方法,基于密度的方法,基于網(wǎng)格的方法,基于模型的方法等.

k-means聚類算法是數(shù)據(jù)挖掘中最經(jīng)典的算法之一,該聚類算法操作簡(jiǎn)單,對(duì)高維數(shù)據(jù)集[3],大數(shù)據(jù)集的處理上有較高的伸縮性,而且速度快.但是傳統(tǒng)的k-means算法也存在一些缺點(diǎn):

1)需要人為指定聚類數(shù)k,這需要有一定的經(jīng)驗(yàn).

2)對(duì)聚類初始中心的選取比較敏感,容易受到噪聲的影響,也容易收斂到局部最優(yōu)解.

3)只能發(fā)現(xiàn)球狀簇.針對(duì)以上的不足,國(guó)內(nèi)外許多學(xué)者從不同的角度對(duì)k-means算法進(jìn)行了改進(jìn).

在對(duì)最佳聚類數(shù)的獲取方面,文獻(xiàn)[4]提出一種基于k-means和粒度原理的改進(jìn)的模糊C均值算法,提高了聚類的有效性,但是對(duì)大數(shù)據(jù)的處理效率比較低.文獻(xiàn)[5]提出了一種最小最大k-means算法,該算法通過(guò)給聚類分配權(quán)重與迭代,解決了聚類初始化問(wèn)題,但是容易受到噪音的影響.文獻(xiàn)[6]根據(jù)傳統(tǒng)的k-means算法和核函數(shù),解決了非凸問(wèn)題,從而得到了最佳聚類數(shù),時(shí)間復(fù)雜度較低,對(duì)處理大規(guī)模數(shù)據(jù)集更高效.文獻(xiàn)[7]提出一種快速生成最小樹(shù)算法,所提出的算法采用分而治之方法,該算法提高了聚類質(zhì)量,不足之處是算法復(fù)雜度較高.

此外,在對(duì)初始中心點(diǎn)的選取方面,文獻(xiàn)[8]提出一種新的初始簇中心迭代算法,啟發(fā)式地選擇簇初始中心,得到了較好的聚類結(jié)果,有很好的穩(wěn)定性,但處理高維數(shù)據(jù)集效果欠佳.文獻(xiàn)[9]用Hilbert空間和Tikhonov正則理論結(jié)合k-means算法來(lái)減小數(shù)據(jù)的維度,得到了較好的效果.文獻(xiàn)[10]提出一種改進(jìn)初始聚類中心選擇的算法,該算法利用距離最大的兩個(gè)數(shù)據(jù)對(duì)象作為開(kāi)始的聚類中心對(duì)該聚類進(jìn)行分裂,如此反復(fù),直到得到指定聚類中心個(gè)數(shù),對(duì)處理大數(shù)據(jù)集效果不好.

針對(duì)k-means算法選取聚類中心點(diǎn)不具有代表性的缺點(diǎn),同時(shí)為了彌補(bǔ)k-means算法只能發(fā)現(xiàn)球狀簇的不足,為此,本文提出了基于可變網(wǎng)格劃分的k-means聚類方法.

2 基于可變網(wǎng)格的k-means聚類算法

所謂可變網(wǎng)格劃分就是對(duì)原始數(shù)據(jù)集的每一維進(jìn)行等深劃分,然后計(jì)算相鄰區(qū)間段的密度,對(duì)密度相似的區(qū)間段進(jìn)行合并,形成可變的網(wǎng)格劃分.在劃分后的網(wǎng)格中,每一維上的區(qū)間段個(gè)數(shù)不相同,而且區(qū)間段的長(zhǎng)度也不一定相同.可變網(wǎng)格劃分克服了固定網(wǎng)格劃分在處理高維數(shù)據(jù)集時(shí)的缺點(diǎn),可變網(wǎng)格劃分根據(jù)數(shù)據(jù)分布的特點(diǎn)進(jìn)行靈活劃分,極大的減少了網(wǎng)格數(shù)量,增加了效率.

2.1 相關(guān)定義

定義1.(相鄰區(qū)間段)網(wǎng)格劃分中,有共同邊界的區(qū)間段稱為相鄰區(qū)間段.

定義2.(等深劃分)已知k維數(shù)據(jù)集D包含N個(gè)數(shù)據(jù)點(diǎn),設(shè)第i維被分為q個(gè)區(qū)間,則劃分結(jié)果為每個(gè)區(qū)間段包含[N/q]個(gè)數(shù)據(jù)點(diǎn).

定義3.(區(qū)間段密度)[11]已知每個(gè)區(qū)間段包含相同數(shù)目的數(shù)據(jù)點(diǎn),第i維的第j段區(qū)間段表示為:Sij=(d(i)([N/q]*(j-1)+1),d(i)([N/q]*j)),d(i)(j)表示第i維的第j個(gè)元素值.則區(qū)間段密度可以用區(qū)間段的長(zhǎng)度來(lái)衡量,即|Sij|=(d(i)([N/q]*j)-d(i)([N/q]*(j-1)+1)).

定義4.(高密度網(wǎng)格與低密度網(wǎng)格)如果一個(gè)網(wǎng)格區(qū)間段密度大于給定的密度閾值,則稱這個(gè)網(wǎng)格為高密度網(wǎng)格,否則稱為低密度網(wǎng)格.

定義5.(噪聲數(shù)據(jù))如果一個(gè)網(wǎng)格與它相鄰的網(wǎng)格都是低密度網(wǎng)格,則可以把它看成噪聲數(shù)據(jù).

定義6.(相鄰區(qū)間段的密度相似性ρ)[11]已知第i維的第j段區(qū)間段密度|Sij|與其相鄰的第j+1段區(qū)間段密度|Si(j+1)|.若|Sij|<|Si(j+1)|,則ρ=|Sij|/|Si(j+1)|,否則,ρ=|Si(j+1)|/|Sij|,其中,0<ρ<1.

定義7.(密度閾值)設(shè)數(shù)據(jù)集D,總共有m個(gè)網(wǎng)格,第i個(gè)網(wǎng)格的密度為Dens(xi),則網(wǎng)格的密度閾值為

(1)

2.2 基于可變網(wǎng)格的k-means聚類算法描述

基于可變網(wǎng)格的k-means聚類算法主要思想為:首先用可變網(wǎng)格方法劃分?jǐn)?shù)據(jù)集,并與密度閾值相比較,選出大于密度閾值的網(wǎng)格,消除了孤立點(diǎn)的影響,然后對(duì)大于密度閾值的網(wǎng)格進(jìn)行k-means聚類,最后根據(jù)距離越遠(yuǎn)聚類效果越好的原則選出最優(yōu)的聚類結(jié)果.

基于可變網(wǎng)格的k-means聚類算法的具體過(guò)程為:首先將數(shù)據(jù)集D的每一維用快速排序法進(jìn)行升序排序,再等深劃分各維數(shù)據(jù),計(jì)算相鄰區(qū)間段的相似度ρ并與相似度閾值v進(jìn)行比較,如果ρ>v,則相鄰區(qū)間段進(jìn)行合并,否則不合并,遍歷所有區(qū)間段,得到合并后的結(jié)果.然后,根據(jù)|Sij|=(d(i)([N/q]*j)-d(i)([N/q]*(j-1)+1))計(jì)算合并后網(wǎng)格的密度并將結(jié)果記錄到集合c中,根據(jù)網(wǎng)格密度,計(jì)算網(wǎng)格密度閾值t,并將大于密度閾值的網(wǎng)格密度結(jié)果放入集合d中,對(duì)d中的網(wǎng)格用k-means聚類方法進(jìn)行網(wǎng)格聚類,輸出最優(yōu)的聚類結(jié)果.

基于以上討論,給出基于可變網(wǎng)格的k-means聚類算法,具體算法如算法1所示.

算法1.VGOk-means()(基于可變網(wǎng)格的k-means聚類)

輸入:含N個(gè)對(duì)象的數(shù)據(jù)集D,期望劃分的聚類數(shù)k,相似度閾值v;

輸出:最優(yōu)聚類結(jié)果;

Begin

1.初始集合c={},d={},e={};

2.for(j=1 toi){

3.Dj←Sorting(Dj)};/*對(duì)數(shù)據(jù)的每一維采用快速排序法排序*/

4.Mj←Divide(Dj);/*等深劃分各維數(shù)據(jù)*/

5.|Sij|←Computer_dens(d(i)([n/q]*j)-d(i)([n/q]*(j-1)+1));/*計(jì)算區(qū)間段密度*/

6.ρ←Computer_similarity(|Sij|/|Si(j+1)|);/*計(jì)算各維相鄰區(qū)間相似度*/

7.If (ρ>v){

8.Mi←Merge(Mi,Mi+1);}/*將滿足條件的相鄰區(qū)間段進(jìn)行合并*/

9.Mi←iterate over _merge(Dj);/*循環(huán)遍歷數(shù)據(jù)集D的每一維,將滿足條件的區(qū)間合并*/

10.Dens(Mi)←Computer_dens[Dens(Mi)];/*根據(jù)(2)式,計(jì)算合并后網(wǎng)格的密度*/

11.c=c∪Dens(Mi);/*將計(jì)算的網(wǎng)格密度放入集合c中*/

12.Computer_min_DensThreshold(t);/*根據(jù)③式,計(jì)算最小密度閾值*/

13.If(Dens(Mi)>t){

14.d=d∪Mi;}/*將大于密度閾值的類簇放入集合d中*/

15.e←Use_k-means(d);/*用k-means聚類方法對(duì)d中高密度網(wǎng)格進(jìn)行聚類,結(jié)果放入集合e中*/

16.Output cluster(e);/*輸出最優(yōu)聚類結(jié)果*/

End

3 基于最大網(wǎng)格密度不唯一的k-means算法

本節(jié)研究最大密度不唯一時(shí)的網(wǎng)格中心點(diǎn)選取方法.本節(jié)提出的新方法結(jié)合密度的概念,選取高密度網(wǎng)格中的代表點(diǎn)作為初始中心點(diǎn),用網(wǎng)格中數(shù)據(jù)點(diǎn)數(shù)比網(wǎng)格的長(zhǎng)度來(lái)計(jì)算網(wǎng)格的密度.在k個(gè)高密度網(wǎng)格中分別選擇一個(gè)代表點(diǎn)作為初始中心點(diǎn).這樣選擇有利于消除孤立點(diǎn)被選為初始中心點(diǎn)的可能,降低了孤立點(diǎn)對(duì)聚類的影響.

3.1 相關(guān)定義和規(guī)則

定義8.(網(wǎng)格類簇的密度)設(shè)n維數(shù)據(jù)集D,對(duì)于每一維數(shù)據(jù),用網(wǎng)格中數(shù)據(jù)點(diǎn)數(shù)比區(qū)間段長(zhǎng)度表示最終網(wǎng)格類簇的密度,即:

Dens(xi)=Ni/Li

(2)

其中,Ni表示該網(wǎng)格中數(shù)據(jù)的總個(gè)數(shù),Li表示該網(wǎng)格的長(zhǎng)度.

定義9.(最小密度閾值minDens)為了消除孤立點(diǎn)的影響和減少算法的計(jì)算,設(shè)定了最小密度閾值,

(3)

該值為類簇選取的下界值,除去了密度較低的點(diǎn),保證選取的類具有代表性.

規(guī)則1.(最大密度不唯一網(wǎng)格選取規(guī)則)當(dāng)網(wǎng)格的最大密度不唯一時(shí),則對(duì)每一個(gè)最大密度網(wǎng)格進(jìn)行聚類,最后比較聚類中心點(diǎn)距離之和,選出距離和最大的一組為最優(yōu)聚類結(jié)果.

3.2 基于最大網(wǎng)格密度不唯一的k-means算法描述

基于最大網(wǎng)格密度不唯一的k-means算法的主要思想為:首先根據(jù)可變網(wǎng)格劃分對(duì)數(shù)據(jù)進(jìn)行網(wǎng)格劃分處理,然后用k-means方法進(jìn)行聚類,當(dāng)出現(xiàn)最大網(wǎng)格密度不唯一的情況,分別對(duì)每個(gè)最大密度網(wǎng)格進(jìn)行聚類,找到與之對(duì)應(yīng)的一組最優(yōu)聚類,最后比較各組類簇的距離之和,輸出最優(yōu)的聚類結(jié)果.

算法的具體過(guò)程為:首先根據(jù)可變網(wǎng)格劃分將數(shù)據(jù)每一維進(jìn)行等深劃分,計(jì)算各相鄰區(qū)間的相似度,如果相似度大于給定閾值,相鄰區(qū)間進(jìn)行合并,否則不合并,直到遍歷完所有的維.然后計(jì)算合并后的網(wǎng)格密度,將大于最小密度閾值的網(wǎng)格放入一個(gè)集合中,從密度最大的網(wǎng)格開(kāi)始,尋找離它最遠(yuǎn)的類,以此類推,直到找到k個(gè)類為止.如果最大密度網(wǎng)格不止一個(gè),則將這些最大網(wǎng)格密度放入另一個(gè)集合中,分別以這些最大密度網(wǎng)格為中心聚類,最后比較各聚類的距離之和,距離之和最大的一類即為最優(yōu)聚類結(jié)果.

基于最大網(wǎng)格密度不唯一的k-means算法的算法描述如算法2所示:

算法2.NMGDk-means()(基于最大網(wǎng)格密度不唯一的k-means算法)

輸入:包含n個(gè)樣本的數(shù)據(jù)集D,期望劃分的聚類個(gè)數(shù)k,相似度閾值V;

輸出:k個(gè)最優(yōu)類簇;

Begin

1.令集合h={},g={},l={},m={},s={};

2.for(j=1 toi){

3.Dj←Sorting(Dj);}/*對(duì)數(shù)據(jù)的每一維采用快速排序法排序*/

4.M←Divide(Dj);/*將每一維進(jìn)行等深劃分,每個(gè)區(qū)間段包含[n/q]個(gè)數(shù)據(jù)點(diǎn)*/

5.|Sij|←Computer_density(d(i)([n/q]*j)-d(i)([n/q]*(j-1)+1));/*計(jì)算區(qū)間段密度*/

6.ρ←Computer_similarity(|Sij|/|Si(j+1)|);/*計(jì)算各維相鄰區(qū)間相似度*/

7.If (ρ>v){

8.Mi←Merge(Mi,Mi+1);}/*將滿足條件的相鄰區(qū)間段進(jìn)行合并*/

9.Mi←iterate over _merge(Dj);/*循環(huán)遍歷數(shù)據(jù)集D的每一維,將滿足條件的區(qū)間合并*/

10.Dens(Mi)←Computer_dens[Dens(Mi)];/*根據(jù)(2)式,計(jì)算合并后網(wǎng)格的密度*/

11.h=h∪Dens(Mi);/*將計(jì)算的網(wǎng)格密度放入集合h中*/

12.Computer_min_DensThreshold(t);/*根據(jù)(3)式,計(jì)算最小密度閾值*/

13.If(Dens(Mi)>t){

14.g=g∪Mi;}/*將大于密度閾值的類簇放入集合g中*/

15.s←Use_k-means(g);/*用k-means聚類方法對(duì)g中高密度網(wǎng)格進(jìn)行聚類*/

16.l=l∪max{Mi∈s∣Dens(Mi)},i=i+j;/*將有相同最大密度值的類簇放入集合l中,并記錄l中的個(gè)數(shù),記為i*/

17.If(|i|=1){

18.D1←maxDens(Mi);}

19.D←Computer_MaxDistance(D1,D2);

20.m=m∪{i=1 tok|Di};

21.until Cluster.number=k;/*在集合g中,計(jì)算離D1距離最遠(yuǎn)的類簇并記為D2,將D1,D2放入集合m中,直到m中有k個(gè)類簇*/

22.C←Computer_SumDist[Dist(Di,Di+1)];/*根據(jù)定義7計(jì)算類間距離之和*/

23.If(|i|>1){

24. forMi∈lDo

25.Ci←Computer_SumDist(Di,Di+1);}/*對(duì)每一個(gè)Mi,根據(jù)18-22步求出k個(gè)類簇,并求出Mi對(duì)應(yīng)類簇的距離之和Ci*/

26.s←Computer_Max(Ci);/*計(jì)算出距離和最大的一組即為所求*/

27.Output Cluster;/*輸出最優(yōu)聚類結(jié)果*/

End

3.3 對(duì)動(dòng)態(tài)增量數(shù)據(jù)的聚類

本節(jié)在3.2節(jié)論述的基礎(chǔ)上進(jìn)一步提出了動(dòng)態(tài)增量聚類方法,該方法可用于對(duì)動(dòng)態(tài)增量式數(shù)據(jù)進(jìn)行聚類.所提方法的主要思想:在可變網(wǎng)格k-means聚類基礎(chǔ)上進(jìn)行更新操作,當(dāng)有數(shù)據(jù)到來(lái)時(shí),只關(guān)心數(shù)據(jù)影響到的網(wǎng)格和類.因此該算法有較好的伸縮性和高效的效率.

算法具體過(guò)程:首先根據(jù)可變網(wǎng)格劃分規(guī)則對(duì)初始樣本集進(jìn)行動(dòng)態(tài)劃分,形成初始網(wǎng)格,然后對(duì)新加入的樣本集進(jìn)行分配操作,如果該樣本屬于已有的網(wǎng)格,則直接把該樣本加入到對(duì)應(yīng)網(wǎng)格中,并進(jìn)行記錄,如果該樣本不屬于已有的網(wǎng)格,則創(chuàng)建一個(gè)新的網(wǎng)格,加入該樣本并進(jìn)行記錄,對(duì)每個(gè)樣本都進(jìn)行上述操作,經(jīng)過(guò)時(shí)間t,對(duì)相似度高的相鄰網(wǎng)格進(jìn)行合并,并且重新計(jì)算密度閾值,最后,對(duì)高密度網(wǎng)格進(jìn)行k-means聚類操作,輸出最終的聚類結(jié)果.基于以上討論,動(dòng)態(tài)增量聚類算法的具體算法如算法3所示.

算法3.GDIk-means()(基于網(wǎng)格的動(dòng)態(tài)增量k-means聚類)

輸入:初始樣本集D,期望劃分聚類數(shù)K,相似度閾值V,時(shí)間間隔t;

輸出:最優(yōu)聚類結(jié)果;

Begin

1.令集合d={},g={},s={};

2.gi←Computer_gridPartition(Di);/*劃分網(wǎng)格,形成初始網(wǎng)格*/

g←join_NewDataSet(X);/*加入新的樣本集X={x1,x2,…,xn},其中,xi=(xi1,xi2,…,xid),xij表示d維空間的樣本對(duì)象*/

3.If(xi∈gi){

4.gi←Add_data(xi);

5.d←Computer_density(gi);}/*xi屬于已存在的網(wǎng)格單元,把xi加入到該網(wǎng)格,重新計(jì)算網(wǎng)格密度并記錄*/

6.else{

7.gj←Create_NewGrid(xi);

8.d←Computer_density(gj);}/*xi不屬于已存在的網(wǎng)格單元,則創(chuàng)建一個(gè)新的網(wǎng)格放入該數(shù)據(jù)并記錄*/

9.set_time(t);

10.gi←Merge(gi,gi+1);

11.v←Update_DensThreshold(v);/*設(shè)置一個(gè)時(shí)間間隔t,每隔t時(shí)間對(duì)網(wǎng)格進(jìn)行一次合并,并更新密度閾值一次*/

12.If(Dens(gi)

13.delect(gi);}/*對(duì)小于密度閾值的網(wǎng)格進(jìn)行剪枝刪除操作*/

14.s←Use_k-means(g);/*對(duì)高密度網(wǎng)格進(jìn)行k-means聚類*/

15.Output cluster(s);/*輸出聚類結(jié)果*/

End

4 基于網(wǎng)格優(yōu)化的k-means聚類和聚類有效性指標(biāo)的k值優(yōu)化

在空間聚類中,有效性指標(biāo)對(duì)最佳聚類數(shù)k有確定性作用.計(jì)算最佳聚類數(shù)主要思想是;首先在聚類數(shù)的搜索范圍內(nèi)[kmin,kmax]內(nèi),根據(jù)確定的k值對(duì)樣本數(shù)據(jù)集進(jìn)行聚類,其次利用有效性指標(biāo)對(duì)聚類結(jié)果進(jìn)行測(cè)試,最優(yōu)聚類結(jié)果所對(duì)應(yīng)的k值就是最佳聚類數(shù),記為kopt.

算法4.VGOk_BWP_k-means()(基于VGOk-means和BWP指標(biāo)的優(yōu)化算法)

輸入:含n個(gè)樣本的數(shù)據(jù)集D,相似度閾值v;

輸出:BWP指標(biāo)最大時(shí)對(duì)應(yīng)的最佳聚類數(shù)kopt;

Begin

1.令集合c={},g={},s={};

3.Fork=kmintokmaxDo

4.c←Chose_initialCenterPoint(ci);/*根據(jù)基于最大網(wǎng)格密度不唯一的k-means算法,選出k個(gè)初始中心點(diǎn)*/

5.s←Use_VGOK-means(D);/*根據(jù)網(wǎng)格優(yōu)化的k-means聚類方法對(duì)樣本進(jìn)行聚類*/

6.g←Computer_argBWP(s);/*對(duì)每個(gè)聚類結(jié)果計(jì)算平均BWP指標(biāo)值,并進(jìn)行記錄*/

7.Fori=kmintokmaxDo

8.if(argBWP(si)

9.argBWP(si)=argBWP(si+1);

10.i++;}

11.kopt←Chose_MaxBWP(si);/*比較計(jì)算的BWP指標(biāo)值,平均值最大所對(duì)應(yīng)的k為最佳聚類數(shù)kopt*/

12.Output Cluster(kopt);/*輸出最佳聚類數(shù)kopt*/

End

5 實(shí)驗(yàn)結(jié)果與分析

5.1 基于網(wǎng)格優(yōu)化的k-means聚類算法實(shí)驗(yàn)分析

首先,為了測(cè)試基于網(wǎng)格優(yōu)化的k-means聚類算法的有效性,采用數(shù)據(jù)集為UCI中的Balance Scale、University、Japanese vowels數(shù)據(jù)集,數(shù)據(jù)來(lái)源(http://archive.ics.uci.edu/ml/).

數(shù)據(jù)集詳情描述如表1所示.

表1 樣本數(shù)據(jù)集
Table 1 Sample data set

數(shù)據(jù)集樣本個(gè)數(shù)屬性個(gè)數(shù)類別個(gè)數(shù)BalanceScale62544University285175Japanesevowels640128

對(duì)基于網(wǎng)格優(yōu)化的k-means聚類算法與傳統(tǒng)的k-means聚類算法在準(zhǔn)確率與時(shí)間花費(fèi)上性能進(jìn)行分析,本實(shí)驗(yàn)對(duì)上述UCI中的Balance Scale、University、Japanese vowels數(shù)據(jù)集進(jìn)行聚類,并對(duì)結(jié)果進(jìn)行了記錄與分析,實(shí)驗(yàn)結(jié)果如表2所示.

表2 實(shí)驗(yàn)結(jié)果分析
Table 2 Analysis of experimental results

數(shù)據(jù)集本文方法傳統(tǒng)的k?means方法正確率/%時(shí)間/ms正確率/%時(shí)間/msBalanceScale93．2514289．17110University88．537676．3662Japanesevowels82．6716373．45127

從表2對(duì)比可以看出,本文提出的基于網(wǎng)格優(yōu)化的k-means聚類算法比傳統(tǒng)的k-means算法正確率有了明顯提高,表明基于網(wǎng)格優(yōu)化的k-means聚類算法是有效的.

5.2 基于可變網(wǎng)格優(yōu)化的k-means算法及BWP指標(biāo)的k值選取分析

此實(shí)驗(yàn)首先用基于可變網(wǎng)格優(yōu)化的k-means算法選出k個(gè)簇,其次對(duì)聚類結(jié)果用BWP指標(biāo)進(jìn)行評(píng)估,并展示結(jié)果.本實(shí)驗(yàn)使用的人工數(shù)據(jù)集ID1與ID2.

表3 樣本數(shù)據(jù)集
Table 3 Sample data set

數(shù)據(jù)集維數(shù)樣本數(shù)類數(shù)ID121864ID23963

基于不唯一最大網(wǎng)格密度算法的聚類數(shù)k與其BWP指標(biāo)關(guān)系如圖1,圖2所示.BWP指標(biāo)的取值范圍為[-1,1].BWP指標(biāo)越接近于1,說(shuō)明聚類效果越好.所以,BWP最大時(shí)所對(duì)應(yīng)的聚類數(shù)是最佳聚類數(shù).圖1所示:當(dāng)k=4時(shí),BWP指標(biāo)的平均值avg(4)=0.684.此時(shí)的BWP最大,所以k=4時(shí)是最佳聚類數(shù).同理,圖2中,k=3時(shí),BWP指標(biāo)的平均值avg(3)=0.634,此時(shí)的BWP指標(biāo)最大,由此可得k=3時(shí)是最佳聚類數(shù).

圖1 ID1聚類數(shù)k與BWP指標(biāo)關(guān)系Fig．1 ID1clusternumberkandBWPindexrelations圖2 ID2聚類數(shù)k與BWP指標(biāo)關(guān)系Fig．2 ID2clusternumberkandBWPindexrelations

最后,根據(jù)上面得到的最佳聚類數(shù)kopt對(duì)ID1和ID2數(shù)據(jù)集進(jìn)行聚類,得到了最優(yōu)的聚類結(jié)果,如圖3,圖4所示.

圖3 數(shù)據(jù)集ID1的聚類結(jié)果Fig．3 DatasetID1clusteringresults圖4 數(shù)據(jù)集ID2的聚類結(jié)果Fig．4 DatasetID2clusteringresults

實(shí)驗(yàn)結(jié)果說(shuō)明:基于可變網(wǎng)格優(yōu)化的k-means聚類和BWP指標(biāo)的結(jié)合能得到正確的聚類數(shù),并且提高了聚類的準(zhǔn)確率和結(jié)果的有效性.

6 結(jié)束語(yǔ)

傳統(tǒng)的k-means聚類算法通過(guò)隨機(jī)選取k個(gè)初始中心進(jìn)行聚類,對(duì)聚類結(jié)果的影響比較大,而且容易陷入局部最優(yōu)解.針對(duì)以上不足,本文提出了基于可變網(wǎng)格優(yōu)化的k-means聚類算法,結(jié)合BWP指標(biāo)得到了最佳的聚類數(shù),提高了聚類算法的有效性.實(shí)驗(yàn)結(jié)果表明,基于可變網(wǎng)格優(yōu)化的k-means聚類算法能夠高質(zhì)量的選取聚類中心,并且準(zhǔn)確率有了很大程度的提高,實(shí)驗(yàn)結(jié)果證明了算法的有效性.

[1] Dhanachandra N,Manglem K,Chanu Y J.Image segmentation using k-means clustering algorithm and subtractive clustering algorithm [J].Procedia Computer Science,2015,54:764-771.

[2] Tang Dong-ming,Zhu Qing-xin,Yang Fan,et al.An efficient cluster analysis method for protein sequences[J].Journal of Software,2011,22(8):1827-1837.

[3] Tang Ying-jun,Huang Shu-ying,Yang Yong，et al.Adaptive k-means to high dimensional feature of image [J].Journal of Chinese Computer Systems,2016,37 (8):1854-1856.

[4] Lu W J,Yan Z Z.Improved FCM Algorithm based on k-means and granular computing [J].Journal of Intelligent Systems,2015,24(2):215-222.

[5] Tzortzis G,Likas A,Tzortzis G.The MinMax k-Means clustering algorithm[J].Pattern Recognition,2014,47 (7):2505-2516.

[6] Yu S,Tranchevent L C,Moor B D,et al.Optimized data fusion for kernel k-means clustering[J].IEEE Transactions on Software Engineering,2012,34(5):1031-1039.

[7] Zhong C,Malinen M,Miao D,et al.A fast minimum spanning tree algorithm based on K-means[J].Information Sciences,2015,295(C):1-19.

[8] Cai Yu-hao,Liang Yong-quan,Fan Jian-cong,et al.Optimizing initial cluster centroids by weighted local variance in k-means algorithm [J].Journal of Frontiers of Computer Science and Technology,2016,10(5):732-741.

[9] García M L L,García-Ródenas R,Gómez A G.K-means algorithms for functional data[J].Neurocomputing,2015,151:231-245.

[10] Chen Guang-ping,Wang Wen-peng,Huang Jun,et al.Improved initial clustering center selection method for k-means algorithm [J].Journal of Chinese Computer Systems,2012,33(6):1320-1323.

[11] Sheng Kai-yuan,Qian Xue-zhong,Wu Qin,et al.Density biased sampling algorithm based on variable grid division[J].Journal of Computer Applications,2013,33(9):2419-2422.

附中文參考文獻(xiàn)：

[2] 唐東明,朱清新,楊 凡,等.一種有效的蛋白質(zhì)序列聚類分析方法[J].軟件學(xué)報(bào),2011,22(8):1827-1837.

[3] 唐穎軍,黃淑英,楊 勇,等.圖像高維數(shù)據(jù)的K-means自適應(yīng)聚類算法[J].小型微型計(jì)算機(jī)系統(tǒng),2016,37(8):1854-1856.

[8] 蔡宇浩,梁永全,樊建聰,等.加權(quán)局部方差優(yōu)化初始簇中心的K-means算法[J].計(jì)算機(jī)科學(xué)與探索,2016,10(5):732-741.

[10] 陳光平,王文鵬,黃 俊,等.一種改進(jìn)初始聚類中心選擇的 K-means算法[J].小型微型計(jì)算機(jī)系統(tǒng),2012,33(6):1320-1323.

[11] 盛開(kāi)元,錢(qián)雪忠,吳 秦,等.基于可變網(wǎng)格劃分的密度偏差抽樣算法[J].計(jì)算機(jī)應(yīng)用,2013,33(9):2419-2422.