王艷娥，安 健，梁 艷，康晶晶

(1.西安思源學(xué)院 理工學(xué)院，陜西 西安 710038；2.西安交通大學(xué)深圳研究院，廣東 深圳 518057；3.山西農(nóng)業(yè)大學(xué) 信息學(xué)院，山西 晉中 030800)

0 引 言

聚類是數(shù)據(jù)挖掘中一種無(wú)監(jiān)督學(xué)習(xí)分析數(shù)據(jù)的方法，基于“物以類聚”的思想，根據(jù)相似性原則將相似性較高數(shù)據(jù)劃歸同一類，相似性較低數(shù)據(jù)劃分為不同類[1]。聚類分析的無(wú)監(jiān)督特性，使聚類在醫(yī)療診斷、交通檢測(cè)、圖像處理、環(huán)境檢測(cè)和大數(shù)據(jù)等方面得到廣泛的應(yīng)用。聚類分析方法可分為：基于劃分式、基于網(wǎng)格、基于密度、基于層次和基于模型等五種類型[2-3]。

1 K-means算法和研究現(xiàn)狀

1.1 K-means算法

K-means算法[4]核心思想是隨機(jī)選取k個(gè)樣本作為初始聚類中心，以歐氏距離作為相似度指標(biāo)，兩個(gè)樣本之間距離越遠(yuǎn)相似性越低，距離越近相似性越高，通過(guò)不斷迭代聚類中心，將相似性高的樣本劃分為同一類，相似性低的樣本劃分為不同類。K-means具有明顯的缺陷：(1)需隨機(jī)選擇初始聚類中心；(2)對(duì)噪聲數(shù)據(jù)和異常點(diǎn)比較敏感；(3)需提前指定劃分類數(shù)，使得聚類結(jié)果常陷于局部最優(yōu)。因此關(guān)于K-means算法的優(yōu)化，現(xiàn)有文獻(xiàn)和相關(guān)學(xué)者主要是從這三方面展開(kāi)。文中算法主要研究的是初始聚類中心的選擇和噪聲數(shù)據(jù)。

1.2 K-means算法研究現(xiàn)狀

為了解決K-means算法的缺陷，眾多學(xué)者提出了基于密度優(yōu)化的解決方案。文獻(xiàn)[5]通過(guò)準(zhǔn)則函數(shù)確定樣本集的最佳聚類數(shù)，基于密度選擇初始聚類中心，在一定程度克服了K-means算法需要預(yù)先輸入類數(shù)和隨機(jī)選擇初始聚類中心的缺陷，聚類結(jié)果穩(wěn)定，但在選擇初始聚類中心時(shí)需根據(jù)經(jīng)驗(yàn)輸入樣本鄰域半徑和最小樣本密度兩個(gè)參數(shù)使得算法的聚類結(jié)果缺少客觀性；文獻(xiàn)[6]算法劃分出樣本空間的高密度區(qū)域，在高密度區(qū)域選擇距離最遠(yuǎn)的高密度樣本作為初始聚類中心，但高密度區(qū)域仍需要人為輸入樣本鄰域半徑和最小樣本密度，也使聚類結(jié)果受人為作用干擾大；文獻(xiàn)[7]以最大最小距離法為基礎(chǔ)，提出離積法的優(yōu)化K-means，該算法克服最大最小距離法易導(dǎo)致聚類中心稠密問(wèn)題，但最大最小距離法將樣本空間劃分為高密度區(qū)域和低密度區(qū)域需要人為輸入兩個(gè)參數(shù)，這缺點(diǎn)文獻(xiàn)[7]并沒(méi)有克服；文獻(xiàn)[8]提出噪聲點(diǎn)優(yōu)化K-means算法，在剔除噪聲點(diǎn)需要根據(jù)經(jīng)驗(yàn)設(shè)定兩個(gè)參數(shù)：樣本集最佳噪聲樣本數(shù)和判斷樣本是否為噪聲樣本的距離調(diào)節(jié)系數(shù)；文獻(xiàn)[5-8]手動(dòng)輸入?yún)?shù)需要?dú)v史經(jīng)驗(yàn)，聚類結(jié)果受人為干擾較大，使算法的普適性受到限制。文獻(xiàn)[9-10]提出將方差作為選擇初始聚類中心的指標(biāo)，選擇數(shù)據(jù)集中方差最小且處于不同區(qū)域的數(shù)據(jù)對(duì)象作為初始聚類中心，該算法的聚類結(jié)果穩(wěn)定，且對(duì)噪聲數(shù)據(jù)具有一定的免疫性，但選擇的初始聚類中心與數(shù)據(jù)集實(shí)際類中心存在差異，且沒(méi)有考慮噪聲樣本在聚類過(guò)程中的影響；文獻(xiàn)[11]使用平均距離作為計(jì)算樣本密度的指標(biāo)，在一定程度避免將噪聲點(diǎn)作為初始聚類中心，但選擇的初始聚類中心同樣與樣本集實(shí)際中心分布相差較大。

該文在研究上述算法的基礎(chǔ)上，提出基于樣本規(guī)模的最優(yōu)超球體計(jì)算樣本密度，使樣本密度的計(jì)算具有一定的客觀性，克服文獻(xiàn)[5-8]根據(jù)經(jīng)驗(yàn)輸入?yún)?shù)的缺陷；文獻(xiàn)[9-11]雖然確保初始聚類中心不會(huì)落在噪聲樣本，但導(dǎo)致密度最大的樣本往往位于多個(gè)類的相交處，而不是數(shù)據(jù)集實(shí)際類中心。

2 基于密度去噪的K-means算法

2.1 DDK-means算法相關(guān)概念

設(shè)RP為待聚類的樣本空間，含有n個(gè)樣本的樣本集D={xi∈Dp,|i=1,2,…,n}，樣本空間可劃分為k類，設(shè)k個(gè)聚類中心為數(shù)據(jù)集C={ci∈C|i=1,2,…,k}。文中算法采用歐氏距離來(lái)衡量樣本相似度。距離越遠(yuǎn)相似度越低，反之相似性越高。

(1)樣本xi距離均值dm(xi)如下：

(1)

其中，j=1,2,…,n，且i≠j，dist(xi,xj)為樣本xi和xj的距離。

(2)樣本集的均方差msd如下：

(2)

(3)樣本集的超球體v的函數(shù)表示如下：

v=πR3

(3)

其中，R=μ*msd，μ為調(diào)節(jié)系數(shù)，初始值等于1。v的大小應(yīng)該與樣本集n的大小和類簇?cái)?shù)k相關(guān)。假設(shè)樣本集中所有樣本被均勻分配給k個(gè)類，那么每個(gè)類中應(yīng)包含樣本的個(gè)數(shù)n/k，考慮到噪聲數(shù)據(jù)，規(guī)定每類樣本的個(gè)數(shù)必須小于n/k，實(shí)際上不管樣本集中的樣本是否均勻分配給k類，通過(guò)規(guī)定超球體內(nèi)樣本個(gè)數(shù)不超過(guò)n/k都能計(jì)算出每個(gè)樣本的最佳μ和最佳局部密度。

(4)樣本xi的密度函數(shù)density(xi)如下：

(4)

從式(4)可以看出，density(xi)值與ρ(xi)密切相關(guān)，當(dāng)ρ(xi)的值越大說(shuō)明落入以xi為中心的超球體的樣本越多，樣本xi越接近類中心。當(dāng)ρ(xi)相同時(shí)，超球內(nèi)樣本與xi距離越近，距離均值越小，該類樣本密集度越高，則xi越接近高密集區(qū)域的類中心。作為樣本xi的密度density(xi)的值越大，xi成為初始聚類中心的權(quán)重越大。

(5)樣本集的密度值meanD表示如下：

(5)

(6)樣本集聚類誤差平方和SSE表示如下：

(6)

2.2 DDK-means算法原理

均方差在概率統(tǒng)計(jì)中用于測(cè)量樣本集的分布程度，對(duì)于數(shù)據(jù)集可以通過(guò)均方差測(cè)量數(shù)據(jù)集的整個(gè)離散程度，當(dāng)均方差的值越大說(shuō)明數(shù)據(jù)集越分散，均方差越小數(shù)據(jù)集越集中。文中以均方差作為計(jì)算最優(yōu)超球體的基礎(chǔ)，將整個(gè)聚類分為兩個(gè)階段：第一階段計(jì)算每個(gè)樣本的局部密度。在大小相同的超球體內(nèi)，某個(gè)樣本的超球體內(nèi)樣本個(gè)數(shù)越多，則說(shuō)明該樣本處于高密度區(qū)域，作為初始聚類中心的權(quán)重就越大。根據(jù)式(3)計(jì)算所有樣本的局部密度，當(dāng)多個(gè)樣本的超球體內(nèi)的樣本數(shù)相同時(shí)，則某個(gè)樣本的超球體內(nèi)樣本緊密度起作用，越緊密，樣本的密度越大，樣本作為初始聚類中心的權(quán)重越大。當(dāng)各個(gè)樣本的超球體內(nèi)的樣本數(shù)不同時(shí)，則超球體內(nèi)的樣本數(shù)起作用，樣本的超球體內(nèi)樣本數(shù)越多，樣本密度越大，該樣本作為初始聚類中心的權(quán)重越大。

第二階段根據(jù)密度選取最佳的聚類中心，完成整個(gè)樣本集的劃分。選擇大于樣本集平均密度的樣本作為初始聚類中心的候選集，同時(shí)在非初始聚類中心候選集中選取樣本密度較低的樣本作為噪聲樣本，將整個(gè)樣本集劃分為非噪聲樣本集和噪聲樣本集；接著在候選樣本集中同樣以均方差作為基礎(chǔ)，通過(guò)可控的伸縮尺度調(diào)節(jié)樣本的距離，選出k個(gè)密度較大且處于不同密度區(qū)域的樣本作為初始聚類中心，然后對(duì)非噪聲樣本集進(jìn)行聚類，完成非噪聲樣本的劃分；最后對(duì)噪聲樣本集中的樣本，根據(jù)它們與k個(gè)中心的相似度，將噪聲樣本劃分給對(duì)應(yīng)的類。

2.3 DDK-means算法實(shí)現(xiàn)

根據(jù)DDK-means算法原理，算法實(shí)現(xiàn)步驟分如下兩步：

第一步，算法1：根據(jù)新定義的樣本密度，將初始樣本集劃分為初始聚類中心候選樣本集、非初始聚類中心候選集、噪聲樣本集和非噪聲樣本集。求解樣本密度的算法描述如下:

輸入：xi，{xi∈D|i=1,2,…,n}，D為樣本集；k；密度調(diào)節(jié)系數(shù)μ=1；初始聚類中心候選集D1=φ；非初始聚類中心候選集D2=φ；非噪聲數(shù)據(jù)集D3=φ；噪聲數(shù)據(jù)集D4=φ。

輸出：n個(gè)樣本的密度、D1,D2,D3和D4，其中D1∪D2=D,D1∩D2=?，D3∪D4=D,D3∩D4=?。

第1步：根據(jù)式(1)、式(2)計(jì)算樣本集的均方差msd。

第2步：根據(jù)式(3)計(jì)算樣本集的超球體。

第3步：根據(jù)式(4)計(jì)算每個(gè)樣本的密度。如果樣本的最大密度遠(yuǎn)遠(yuǎn)小于n/k，轉(zhuǎn)到第2步，增大式(3)中的μ的值，重新計(jì)算超球體，使得超球體內(nèi)樣本個(gè)數(shù)增大，增大到剛好小于或等于n/k，轉(zhuǎn)到第4步。如果樣本最大密度遠(yuǎn)遠(yuǎn)大于n/k，轉(zhuǎn)到第2步，減少式(3)中μ的值，重新計(jì)算超球體，使得超球體內(nèi)樣本個(gè)數(shù)減少，減少到剛好小于或等于n/k，轉(zhuǎn)到第4步。

第4步：計(jì)算樣本集的密度meanD。

第5步：構(gòu)造初始聚類中心候選集D1，{xi∈D1|density(xi)>meanD,i=1,2,…,n}，非初始聚類中心候選集D2=D-D1。

第6步：構(gòu)造噪聲數(shù)據(jù)集D4和非噪聲數(shù)據(jù)集D3。其中D4=ρ*D2，0≤ρ≤1，即在D2中選擇樣本密度最小的前ρ*|D2|樣本作為噪聲樣本；構(gòu)造非噪聲樣本集D3，D3=D-D4。

第7步：算法1結(jié)束。

第二步，算法2根據(jù)算法1的結(jié)果，通過(guò)不斷調(diào)節(jié)不同聚類中心之間的距離，在初始聚類中心候選集中選擇密度最高且處于不同區(qū)域的樣本作為初始聚類中心。再根據(jù)選擇的最優(yōu)初始聚類中心，先針對(duì)非噪聲數(shù)據(jù)完成聚類，再將非噪聲數(shù)據(jù)劃分到不同的類簇中，從而剔除噪聲數(shù)據(jù)對(duì)聚類過(guò)程產(chǎn)生的影響。

算法2:具體實(shí)現(xiàn)的步驟如下：

輸入：構(gòu)造k空集合S1,S2,…,Sk，初始化為c1∈S1,c2∈S2,…,ck∈Sk；n個(gè)樣本的密度、D1,D2,D3和D4。

輸出：樣本集的k個(gè)劃分。

第1步：在D1中選擇密度最大的樣本作為第一個(gè)初始聚類中心c1。

第2步：在D1選擇樣本xi作為第二個(gè)初始聚類中心c2，xi滿足dist(xi,c1)>msd。

第3步：在D1選擇樣本xr作為第r+1個(gè)聚類中心，xr滿足條件dist(xr,c1)>msd/(r-1)&& dist(xr,c2)>msd/(r-1)&&…&& dist(xr,cr-1)>msd/(r-1)，其中2≤r≤k。直到選擇出第k個(gè)初始聚類中心。

第4步：根據(jù)每個(gè)樣本與聚類中心的距離將非噪聲數(shù)據(jù)劃分到K個(gè)類中，重新計(jì)算K個(gè)類的聚類中心。

第5步：根據(jù)式(6)，計(jì)算SSE，如果SSE發(fā)生變化轉(zhuǎn)到第3步，否則轉(zhuǎn)到第6步。

第6步：根據(jù)噪聲數(shù)據(jù)與聚類中心的聚類，將噪聲數(shù)據(jù)劃分到K個(gè)類中，完成聚類。

3 DDK-means算法仿真實(shí)驗(yàn)

為驗(yàn)證文中算法的有效性，分別在乳腺癌數(shù)據(jù)集、UCI[12]數(shù)據(jù)庫(kù)中常用的幾個(gè)數(shù)據(jù)集以及人工數(shù)據(jù)集中進(jìn)行測(cè)試，并與傳統(tǒng)的K-means方法、文獻(xiàn)[9,11]中的算法進(jìn)行比較。所有算法的實(shí)驗(yàn)環(huán)境為：Win7操作系統(tǒng)、COREi5處理器、2G內(nèi)存、Matlab R2012a處理軟件。

3.1 實(shí)驗(yàn)數(shù)據(jù)集

3.1.1 乳腺癌數(shù)據(jù)集

用于測(cè)試的乳腺癌數(shù)據(jù)集為wdbc和breast-cancer-wisconsin。breast-cancer-wisconsin數(shù)據(jù)集包含699個(gè)樣本(實(shí)際的病例數(shù)據(jù))，其中16個(gè)樣本有缺失屬性，文中算法對(duì)缺失屬性的樣本采用丟棄的方法，最終數(shù)據(jù)集包含683個(gè)樣本，其中444個(gè)樣本為良性腫瘤，239個(gè)樣本為惡性腫瘤。

3.1.2 UCI數(shù)據(jù)集和人工模擬數(shù)據(jù)集

為驗(yàn)證文中算法的普適性，在UCI數(shù)據(jù)庫(kù)中選取機(jī)器學(xué)習(xí)用來(lái)進(jìn)行測(cè)試的數(shù)據(jù)集進(jìn)行驗(yàn)證，包括Iris、Wine、Ionosphere、Soybean-small和Seed數(shù)據(jù)集。

為進(jìn)一步驗(yàn)證文中算法的合理性，生成包含不同噪聲比的人工模擬數(shù)據(jù)集。關(guān)于人工模擬數(shù)據(jù)集高斯分布的相關(guān)參數(shù)如表1所示。

表1 人工模擬數(shù)據(jù)集各項(xiàng)參數(shù)

用于進(jìn)行算法測(cè)試的人工模擬數(shù)據(jù)集包含6組數(shù)據(jù)集，6數(shù)據(jù)集各包含1 800個(gè)樣本，類別數(shù)為3，每類簇包含600個(gè)樣本，每類數(shù)據(jù)集按照不同的高斯分布生成。按照表1所示的各項(xiàng)參數(shù)生成含有不同噪聲比的數(shù)據(jù)集，噪聲比分別為0%，10%，20%，30%，40%，50%，其中噪聲產(chǎn)生在第3類，噪聲數(shù)據(jù)的標(biāo)準(zhǔn)差為4。

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

文中算法在乳腺癌數(shù)據(jù)集、UCI數(shù)據(jù)集和人工模擬數(shù)據(jù)集的測(cè)試結(jié)果分析，通過(guò)常用的聚類效果評(píng)價(jià)指標(biāo)：聚類誤差平方和、聚類時(shí)間、聚類準(zhǔn)確率[13]、Rand index[14]、Jaccard coefficient[15]、Adjusted rand index[16]進(jìn)行比較。傳統(tǒng)K-means算法，隨機(jī)選擇初始聚類中心，聚類結(jié)果不穩(wěn)定，

為加強(qiáng)K-means算法評(píng)價(jià)指標(biāo)的穩(wěn)定性，采取在測(cè)試數(shù)據(jù)集上重復(fù)執(zhí)行K-means算法100次，K-means算法的各項(xiàng)評(píng)價(jià)指標(biāo)是執(zhí)行100次后的平均值。

為驗(yàn)證文中算法能夠很好地克服以上算法存在的缺陷，將文中算法與傳統(tǒng)K-means算法、文獻(xiàn)[9,11]提出的算法進(jìn)行對(duì)比。

3.2.1 乳腺癌數(shù)據(jù)集與UCI數(shù)據(jù)集聚類結(jié)果分析

K-means算法、文獻(xiàn)[9]、文獻(xiàn)[11]和文中算法在乳腺癌數(shù)據(jù)集和UCI數(shù)據(jù)集上的聚類誤差平方和、運(yùn)行時(shí)間如表2和表3所示。

表2 四種算法在UCI數(shù)據(jù)集上的聚類誤差平方和比較

表2中加粗?jǐn)?shù)據(jù)表示該算法的聚類誤差平方和評(píng)價(jià)指標(biāo)最佳。從表2中的實(shí)驗(yàn)結(jié)果數(shù)據(jù)可以看出，文獻(xiàn)[9]、文獻(xiàn)[11]在Iris和Ionosphere數(shù)據(jù)集的聚類誤差平方和明顯優(yōu)于K-means算法，在其他數(shù)據(jù)集中與K-means算法相同；文中算法在乳腺癌數(shù)據(jù)集以及幾個(gè)常用的UCI數(shù)據(jù)集中的聚類誤差平方和均明顯低于K-means算法、文獻(xiàn)[9]和文獻(xiàn)[11]；結(jié)果說(shuō)明，文中算法能夠?qū)⑾嗨菩愿叩臉颖緞澐譃橥活?，相似性低的樣本劃分為不同類，聚類的結(jié)果更符合數(shù)據(jù)集的原始分布。

表3是四種算法在樣本集上運(yùn)行時(shí)間比較。從表3可以看出K-means算法在聚類時(shí)間上明顯優(yōu)于文獻(xiàn)[9]、文獻(xiàn)[11]和文中算法，結(jié)果產(chǎn)生的原因是其他三種算法在選擇最優(yōu)的初始聚類中心時(shí)有一定的時(shí)間開(kāi)銷；但文中算法在運(yùn)行時(shí)間上明顯優(yōu)于文獻(xiàn)[9]和文獻(xiàn)[11]，文中算法在對(duì)樣本進(jìn)行聚類時(shí)，減少反復(fù)聚類時(shí)的樣本集規(guī)模，噪聲樣本并沒(méi)有參與反復(fù)聚類的過(guò)程，當(dāng)對(duì)非噪聲樣本完成聚類后，噪聲樣本一次性直接劃分給相似性高的類；同時(shí)由于文中算法選擇的初始聚類中心更接近樣本集實(shí)際中心的分布，使得反復(fù)聚類的迭代次數(shù)減少，進(jìn)一步降低了時(shí)間開(kāi)銷。

表3 UCI數(shù)據(jù)集四種算法聚類時(shí)間比較

圖1是K-means、文獻(xiàn)[9]、文獻(xiàn)[11]和文中算法在乳腺癌數(shù)據(jù)集和UCI數(shù)據(jù)集上在聚類準(zhǔn)確率、Rand index、Jaccard coefficient和Adjusted rand index參數(shù)指標(biāo)的比較折線圖。圖1(a)中，文中算法在這幾個(gè)數(shù)據(jù)集上的聚類準(zhǔn)確率最優(yōu)，K-means算法的聚類結(jié)果最差；圖1(b)中，文中算法的Rand index明顯優(yōu)于其他三種算法，K-means算法的聚類效果最差；圖1(c)中，文中算法的Jaccard coefficient均優(yōu)于其他三種算法，而且在wdbc、Iris和Seeds樣本集的優(yōu)勢(shì)明顯；圖1(d)中，文中算法的Adjusted rand index在wdbc、Iris、Wine、Seeds數(shù)據(jù)上明顯優(yōu)于其他三中算法，在breast-cancer-wisconsin和Ionoshpere數(shù)據(jù)上也具有一定的優(yōu)勢(shì)。

圖1 四種算法在UCI數(shù)據(jù)集上的結(jié)果比較

通過(guò)在乳腺癌數(shù)據(jù)集和常用的UCI數(shù)據(jù)集進(jìn)行聚類結(jié)果的比較，證明文中提出的優(yōu)化DDK-means算法的聚類效果明顯優(yōu)于其他三種聚類方法，其中K-means算法的聚類效果最差，文獻(xiàn)[9]和文獻(xiàn)[11]的聚類結(jié)果相似，文中算法有效地克服了優(yōu)化后初始聚類中心與樣本實(shí)際類中心差異較大的缺陷。

3.2.2 人工數(shù)據(jù)集結(jié)果分析

在人工模擬數(shù)據(jù)集上對(duì)K-means算法、文獻(xiàn)[9]、文獻(xiàn)[11]和文中算法進(jìn)行測(cè)試。除了在六種聚類效果評(píng)價(jià)指標(biāo)進(jìn)行對(duì)比外，對(duì)四種算法選擇的初始聚類中心進(jìn)行了比較，四種算法選擇的初始聚類中心如圖2所示。圖2中黑白相間的圓表示不同算法在不同噪聲比數(shù)據(jù)集中選擇的初始聚類中心。

K-means算法的初始聚類中心是隨機(jī)產(chǎn)生，初始聚類中心不穩(wěn)定，圖2中的K-means初始聚類中心是隨機(jī)選取其中一次的結(jié)果；文獻(xiàn)[9]、文獻(xiàn)[11]和文中算法選擇的初始聚類中心穩(wěn)定。圖2選取具有代表性的無(wú)噪聲數(shù)據(jù)集、20%噪聲數(shù)據(jù)集、50%噪聲數(shù)據(jù)集，在這三個(gè)數(shù)據(jù)集上運(yùn)行K-means算法、文獻(xiàn)[9]、文獻(xiàn)[11]和文中算法；圖2(a)～(d)分別是K-means算法、文獻(xiàn)[9]、文獻(xiàn)[11]和文中算法在三個(gè)數(shù)據(jù)集中選擇的初始聚類中心。圖2(a)是K-means算法選擇的初始聚類中心，隨機(jī)選擇的初始聚類使得初始的中心往往不夠理想，不同類簇的初始聚類中心可能位于在同一類中，甚至可能為噪聲數(shù)據(jù)，這樣極大概率導(dǎo)致K-means聚類結(jié)果不穩(wěn)定且趨于局部最優(yōu)；圖2(b)是文獻(xiàn)[9]選擇的初始聚類中心，文獻(xiàn)[9]基于方差優(yōu)化后選擇的初始聚類中心穩(wěn)定，能夠保證聚類中心分布在不同區(qū)域，且初始聚類中心穩(wěn)定，但從圖中可以看出文獻(xiàn)[9]選擇的初始聚類中心偏離數(shù)據(jù)集真實(shí)的聚類中心；圖2(c)是文獻(xiàn)[11]選擇的初始聚類中心，圖2(c)能夠保證初始聚類中心選擇穩(wěn)定，且處于不同的區(qū)域，但初始聚類中仍然偏離數(shù)據(jù)集真實(shí)中心；圖2(d)是文中算法的結(jié)果，可以看出文中算法選擇的初始聚類中心分別位于三類樣本密集區(qū)域，初始聚類中心更接近樣本集實(shí)際類中心。

圖2 四種算法選擇的初始聚類中心

表4和表5是四種算法在不同噪聲比的6組人工模擬數(shù)據(jù)集上的聚類誤差平方和比較和算法運(yùn)行時(shí)間比較。

表4 人工模擬數(shù)據(jù)集聚類誤差平方和比較

表4中用加粗?jǐn)?shù)據(jù)表示該算法的聚類評(píng)價(jià)指標(biāo)最佳。從表4中提供的數(shù)據(jù)可以看出，文中算法在不同噪聲比的人工模擬數(shù)據(jù)集上的聚類誤差平方和均明顯優(yōu)于K-means算法、文獻(xiàn)[9]和文獻(xiàn)[11]；文獻(xiàn)[9]和文獻(xiàn)[11]在人工模擬數(shù)據(jù)集中的聚類誤差平方和與K-means相同。

表5中K-means算法在不同噪聲比人工模擬數(shù)據(jù)集的運(yùn)行時(shí)間明顯均優(yōu)于其他三種算法，但文中算法的運(yùn)行時(shí)間均優(yōu)于文獻(xiàn)[9]和文獻(xiàn)[11]。

表5 人工模擬數(shù)據(jù)集運(yùn)行時(shí)間比較

圖3(a)～(d)分別是K-means、文獻(xiàn)[9]、文獻(xiàn)[11]和文中算法在不同噪聲比的人工模擬數(shù)據(jù)集上在聚類準(zhǔn)確率、Rand index、Jaccard coefficient和Adjusted rand index四種評(píng)價(jià)指標(biāo)的比較折線圖，可以看出文中算法在四種聚類評(píng)價(jià)指標(biāo)上均明顯優(yōu)于其他三種算法。

圖3 四種算法在不同噪聲比人工數(shù)據(jù)集上的運(yùn)行結(jié)果

人工模擬數(shù)據(jù)集上的聚類結(jié)果進(jìn)一步說(shuō)明，文中算法能夠克服選擇的初始聚類中心與數(shù)據(jù)集實(shí)際中心分布差異較大的問(wèn)題。

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

針對(duì)現(xiàn)有基于密度優(yōu)化K-means算法存在的問(wèn)題，提出密度去噪的DDK-means算法，通過(guò)樣本集的規(guī)模和樣本類簇?cái)?shù)對(duì)樣本密度的最大值進(jìn)行限定，同時(shí)根據(jù)樣本集的密度均值剔除樣本集中的噪聲樣本，克服需要手動(dòng)輸入?yún)?shù)以及噪聲樣本參與整個(gè)聚類的缺陷。與同類文獻(xiàn)對(duì)比，實(shí)驗(yàn)結(jié)果證明文中算法不僅在乳腺癌數(shù)據(jù)集的聚類結(jié)果穩(wěn)定、聚類準(zhǔn)確率提高明顯、對(duì)噪聲數(shù)據(jù)不敏感，且在其他UCI數(shù)據(jù)集上也具有較優(yōu)的聚類效果。