基于密度優(yōu)化初始聚類中心的K-means算法

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

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

0 引 言

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

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

1.1 K-means算法

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

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

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

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

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

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

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

(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的大小和類簇數(shù)k相關(guān)。假設(shè)樣本集中所有樣本被均勻分配給k個類，那么每個類中應(yīng)包含樣本的個數(shù)n/k，考慮到噪聲數(shù)據(jù)，規(guī)定每類樣本的個數(shù)必須小于n/k，實際上不管樣本集中的樣本是否均勻分配給k類，通過規(guī)定超球體內(nèi)樣本個數(shù)不超過n/k都能計算出每個樣本的最佳μ和最佳局部密度。

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

(4)

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

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

(5)

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

(6)

2.2 DDK-means算法原理

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

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

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

根據(jù)DDK-means算法原理，算法實現(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個樣本的密度、D1,D2,D3和D4，其中D1∪D2=D,D1∩D2=?，D3∪D4=D,D3∩D4=?。

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

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

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

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

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

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

輸出：樣本集的k個劃分。

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

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

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

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

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

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

3 DDK-means算法仿真實驗

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

3.1 實驗數(shù)據(jù)集

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

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

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

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

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

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

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

3.2 實驗結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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