基于密度優化初始聚類中心的K-means算法

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

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

0 引 言

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

1 K-means算法和研究現狀

1.1 K-means算法

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

1.2 K-means算法研究現狀

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

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

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

2.1 DDK-means算法相關概念

設RP為待聚類的樣本空間，含有n個樣本的樣本集D={xi∈Dp,|i=1,2,…,n}，樣本空間可劃分為k類，設k個聚類中心為數據集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的函數表示如下：

v=πR3

(3)

其中，R=μ*msd，μ為調節系數，初始值等于1。v的大小應該與樣本集n的大小和類簇數k相關。假設樣本集中所有樣本被均勻分配給k個類，那么每個類中應包含樣本的個數n/k，考慮到噪聲數據，規定每類樣本的個數必須小于n/k，實際上不管樣本集中的樣本是否均勻分配給k類，通過規定超球體內樣本個數不超過n/k都能計算出每個樣本的最佳μ和最佳局部密度。

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

(4)

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

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

(5)

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

(6)

2.2 DDK-means算法原理

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

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

2.3 DDK-means算法實現

根據DDK-means算法原理，算法實現步驟分如下兩步：

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

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

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

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

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

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

第4步：計算樣本集的密度meanD。

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

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

第7步：算法1結束。

第二步，算法2根據算法1的結果，通過不斷調節不同聚類中心之間的距離，在初始聚類中心候選集中選擇密度最高且處于不同區域的樣本作為初始聚類中心。再根據選擇的最優初始聚類中心，先針對非噪聲數據完成聚類，再將非噪聲數據劃分到不同的類簇中，從而剔除噪聲數據對聚類過程產生的影響。

算法2:具體實現的步驟如下：

輸入：構造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步：根據每個樣本與聚類中心的距離將非噪聲數據劃分到K個類中，重新計算K個類的聚類中心。

第5步：根據式(6)，計算SSE，如果SSE發生變化轉到第3步，否則轉到第6步。

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

3 DDK-means算法仿真實驗

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

3.1 實驗數據集

3.1.1 乳腺癌數據集

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

3.1.2 UCI數據集和人工模擬數據集

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

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

表1 人工模擬數據集各項參數

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

3.2 實驗結果與分析

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

為加強K-means算法評價指標的穩定性，采取在測試數據集上重復執行K-means算法100次，K-means算法的各項評價指標是執行100次后的平均值。

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

3.2.1 乳腺癌數據集與UCI數據集聚類結果分析

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

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

表2中加粗數據表示該算法的聚類誤差平方和評價指標最佳。從表2中的實驗結果數據可以看出，文獻[9]、文獻[11]在Iris和Ionosphere數據集的聚類誤差平方和明顯優于K-means算法，在其他數據集中與K-means算法相同；文中算法在乳腺癌數據集以及幾個常用的UCI數據集中的聚類誤差平方和均明顯低于K-means算法、文獻[9]和文獻[11]；結果說明，文中算法能夠將相似性高的樣本劃分為同一類，相似性低的樣本劃分為不同類，聚類的結果更符合數據集的原始分布。

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

表3 UCI數據集四種算法聚類時間比較

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

圖1 四種算法在UCI數據集上的結果比較

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

3.2.2 人工數據集結果分析

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

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

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

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

表4 人工模擬數據集聚類誤差平方和比較

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

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

表5 人工模擬數據集運行時間比較

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

圖3 四種算法在不同噪聲比人工數據集上的運行結果

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

4 結束語

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