蔣 麗 薛善良

（南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 南京 211106）

1 引言

數(shù)據(jù)挖掘可以從大量有關(guān)數(shù)據(jù)中挖掘出隱含的、先前未知的、對(duì)企業(yè)決策有潛在價(jià)值的知識(shí)和規(guī)則。聚類是數(shù)據(jù)分析中的一項(xiàng)重要技術(shù)，在許多領(lǐng)域都得到了廣泛應(yīng)用［1］，包括機(jī)器學(xué)習(xí)、模式識(shí)別、圖像分析等。到目前為止，已經(jīng)提出了許多經(jīng)典的聚類算法，比如基于劃分的K-means算法［2］、基于密度的DBSCAN算法［3］、基于層次的CURE算法［4］、基于網(wǎng)格的 STNG 算法［5］等。本文主要研究基于劃分的K-means聚類算法，由于它具有算法簡單且收斂速度快的優(yōu)點(diǎn)，所以得到較普遍的應(yīng)用，但由于該算法中K個(gè)聚類中心是隨機(jī)選取的，而實(shí)際數(shù)據(jù)集中可能存在孤立點(diǎn)和邊界點(diǎn)，我們?nèi)绻压铝Ⅻc(diǎn)和邊界點(diǎn)作為初始聚類中心，就會(huì)影響聚類結(jié)果。為解決這個(gè)問題，本文結(jié)合基于密度的思想，首先將數(shù)據(jù)集按密度劃分為核心點(diǎn)、邊界點(diǎn)和孤立點(diǎn)，刪除數(shù)據(jù)集中的孤立點(diǎn)和邊界點(diǎn)并取核心點(diǎn)的中心點(diǎn)作為初始聚類中心再進(jìn)行K-means聚類算法。改進(jìn)后的K-means聚類算法聚類效果更好，聚類準(zhǔn)確性更高。

2 K-means聚類算法思想及基本步驟

2.1 K-means聚類算法思想

1967年，MacQueen提出了K-means算法。K-means算法是一種基于劃分的經(jīng)典聚類算法。該算法最初隨機(jī)選擇K個(gè)數(shù)據(jù)樣本作為初始聚類中心，在每次的迭代過程中，根據(jù)計(jì)算相似度將每個(gè)數(shù)據(jù)樣本分配到最近的簇中，然后，重新計(jì)算簇的中心，也就是每個(gè)簇中所有數(shù)據(jù)的平均值。該算法結(jié)束的條件為聚類準(zhǔn)則函數(shù)達(dá)到最優(yōu)即收斂，從而使生成的每個(gè)聚類內(nèi)緊湊，類間獨(dú)立［6］。

2.2 K-means聚類算法基本步驟

input：包含n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)集合D以及聚類簇的個(gè)數(shù)K。

output：滿足聚類準(zhǔn)則函數(shù)收斂的k個(gè)聚類簇的集合。

K-means算法的具體步驟：

1）從數(shù)據(jù)集合D中隨機(jī)選擇K個(gè)數(shù)據(jù)對(duì)象作為初始聚類中心 Cj，j=1，2，3，…，k。

2）求出每個(gè)數(shù)據(jù)對(duì)象與初始聚類中心的距離D(Xi，Cj)，i=1，2，3，…，n，j=1，2，3，…，k。

3）根據(jù)求出的距離，將每個(gè)數(shù)據(jù)對(duì)象劃分到最相似的簇中即若滿足 D(Xi，Cj)=min{D(Xi，Cj)，j=1，2，3，…，n｝，則 Xi∈Yj。

6）判斷：如果E≤ε，表示算法結(jié)束，否則，返回第2）步繼續(xù)執(zhí)行。

2.3 K-means聚類算法基本定義

1）樣本xi和xj之間的想異度通常用它們之間的距離d(xi，xj)來表示，距離越小，樣本 xi和 xj越相似；距離越大，樣本xi和xj越不相似。距離一般使用歐式距離，歐式距離公式如下：

2）簇中心指一個(gè)簇中所有對(duì)象組成的幾何中心點(diǎn)，簇的平均值在K-means算法中也稱為簇中心，簇中心的公式如下：

其中，Xi是數(shù)據(jù)集D中的每個(gè)數(shù)據(jù)對(duì)象，Cj是k個(gè)初始聚類中心。

4）聚類準(zhǔn)則函數(shù)收斂，則聚類操作結(jié)束。給定一個(gè)閾值ε，假設(shè)ε足夠小，在聚類過程中，當(dāng)

其中n是簇 j的樣本數(shù)目，Cj是指簇 j的中心［7］。

3）聚類準(zhǔn)則函數(shù)（SSE（sum of the squared error））

K-means聚類算法使用聚類準(zhǔn)則函數(shù)來評(píng)價(jià)聚類性能的好壞。聚類準(zhǔn)則函數(shù)公式為：成立時(shí)，則聚類函數(shù)收斂。

3 K-means算法的優(yōu)缺點(diǎn)

3.1 K-means算法的優(yōu)點(diǎn)

K-means算法是數(shù)據(jù)挖掘中最常用的聚類算法之一，在文本挖掘中應(yīng)用也較為普遍，具有以下優(yōu)點(diǎn)：

1）K-means聚類算法簡單、快捷、易行；

2）當(dāng)面對(duì)大數(shù)據(jù)集時(shí)，K-means算法是相對(duì)可伸縮的并且是高效的，它的復(fù)雜度是O（n*k*t），其中，n是所有對(duì)象的數(shù)量，k是簇的數(shù)目，t是迭代的次數(shù)。

3.2 K-means算法的缺點(diǎn)

1）K-means算法中必須事先給出k即要生成的簇的數(shù)目，K值的選定非常難以估計(jì)。很多時(shí)候，事先并不知道給定的數(shù)據(jù)集應(yīng)該分成多少個(gè)類別才最合適，對(duì)于不同的初始值，結(jié)果也可能不同。

2）在K-means算法中，首先要隨機(jī)產(chǎn)生K個(gè)聚類中心，初始聚類中心的選擇對(duì)聚類結(jié)果有較大的影響，一旦選擇到孤立點(diǎn)，可能無法得到有效的聚類結(jié)果。如圖1，圖（a）是實(shí)際的數(shù)據(jù)分布，圖（b）是選取了好的初始聚類中心得到的結(jié)果；圖（c）是選取不好的初始聚類中心得到的結(jié)果，從圖中可以看出，初始聚類中心的選取是至關(guān)重要的［9］。

3）K-means算法需要不斷地進(jìn)行樣本分類調(diào)整，不斷地計(jì)算調(diào)整后的新的聚類中心，因此，當(dāng)數(shù)據(jù)量非常大時(shí)，算法的時(shí)間開銷是非常大的。

圖1 基于K-means算法的一組對(duì)象的聚類

4 K值的確定以及基于密度選取初始聚類中心

Kmeans算法中，聚類數(shù)K值是用戶輸入，如果K值選取的不對(duì)，將影響聚類的結(jié)果，本文提出了基于類簇指標(biāo)來選取K值的方法，類簇指標(biāo)如類簇的平均半徑或直徑，經(jīng)過選取不同的K值進(jìn)行實(shí)驗(yàn)對(duì)比觀察類簇指標(biāo)，我們可以將上升或下降趨勢(shì)很明顯的類簇指標(biāo)作為我們要選取的K值。圖3是不同聚類數(shù)的聚類效果，圖4是類簇指標(biāo)的變化曲線。

考慮到K-means算法對(duì)孤立點(diǎn)的敏感性，本文提出了一種改進(jìn)的K-means聚類算法，采用基于密度的思想，通過設(shè)定ε（半徑）和MinPts（最小鄰域點(diǎn)數(shù)）將數(shù)據(jù)樣本劃分為核心點(diǎn)、邊界點(diǎn)和孤立點(diǎn)，排除孤立點(diǎn)和邊界點(diǎn)后，取簇中核心點(diǎn)的中心作為新的聚類中心，最后再進(jìn)行K-means聚類算法，實(shí)驗(yàn)表明，基于密度的K-means算法聚類效果更好。下面介紹基于密度思想的幾個(gè)概念。

1）密度參數(shù)：以空間某點(diǎn)為中心，以半徑ε做多維超球體，在球體內(nèi)所包含的對(duì)象個(gè)數(shù)稱為中心對(duì)象點(diǎn)的密度。個(gè)數(shù)越多，說明對(duì)象所處的區(qū)域數(shù)據(jù)密度越高；反之，說明數(shù)據(jù)對(duì)象所處的數(shù)據(jù)密度越低。

2）ε鄰域：給定對(duì)象半徑的ε內(nèi)的鄰域稱為該對(duì)象的ε鄰域，我們用Nε(p)表示點(diǎn) p的ε半徑內(nèi)的點(diǎn)的集合，即 Nε(p)={q|q∈D，D(p，q)≤ε}，其中，D(p，q)表示 p對(duì)象和q對(duì)象之間的距離，一般使用式（1）來計(jì)算［10］。

3）MinPts：給定點(diǎn)在ε鄰域內(nèi)成為核心對(duì)象的最小鄰域點(diǎn)數(shù)。對(duì)于有限的數(shù)據(jù)集，MinPts一般可用如下公式進(jìn)行計(jì)算：MinPts=integer（m/25）［11］，m為數(shù)據(jù)集中數(shù)據(jù)總個(gè)數(shù)，如果數(shù)據(jù)集中數(shù)據(jù)很多，MinPts的值一般確定為10～20之間。

4）ε：用戶輸入的半徑。我們假設(shè)數(shù)據(jù)集D是均勻分布，那么半徑ε可利用如下公式［12］進(jìn)行計(jì)算：其中，V是數(shù)據(jù)集D的容積，V利用如下公式計(jì)中對(duì)象的數(shù)量，n代表數(shù)據(jù)集的維度數(shù)量，Γ代表伽馬函數(shù)。

5）核心對(duì)象、邊界對(duì)象和孤立對(duì)象：給定ε及MinPts，若在半徑ε內(nèi)含有超過MinPts數(shù)目的點(diǎn)，則該對(duì)象為核心對(duì)象；邊界對(duì)象為在半徑ε內(nèi)點(diǎn)的數(shù)量小于MinPts，但在ε領(lǐng)域之內(nèi)至少有一個(gè)是核心對(duì)象；既不是核心對(duì)象也不是邊界對(duì)象稱為孤立對(duì)象。

圖2 半徑為ε，MinPts為3的各對(duì)象密度

如圖2所示，在半徑為ε，MinPts為3的情況下，圖（a）中的i對(duì)象就是核心對(duì)象，圖（b）中的j對(duì)象為邊界對(duì)象，圖（c）中的i對(duì)象為孤立對(duì)象。

改進(jìn)后的K-means聚類算法流程如下：

input：包含n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)集合D，最小鄰域點(diǎn)數(shù)MinPts。

output：排除孤立點(diǎn)和邊界點(diǎn)的聚類結(jié)果。

1）根據(jù)數(shù)據(jù)集D合輸入的最小鄰域點(diǎn)數(shù)MinPts計(jì)算出ε。

2）利用式（1）計(jì)算出數(shù)據(jù)集中每個(gè)點(diǎn)之間的距離，存儲(chǔ)在相異度矩陣dis中。

3）從dis中取出第一個(gè)點(diǎn)到其它所有點(diǎn)的距離 dis（1，：），找到在 ε范圍內(nèi)所有的點(diǎn) find（（dis（1，：）＜= ε），根據(jù)其數(shù)量length（find（（dis（1，：）＜=ε））區(qū)分點(diǎn)的類型并進(jìn)行處理從而將數(shù)據(jù)集中每個(gè)數(shù)據(jù)點(diǎn)劃分為核心點(diǎn)，邊界點(diǎn)和孤立點(diǎn)，然后將孤立點(diǎn)和邊界點(diǎn)從數(shù)據(jù)集中刪除。數(shù)據(jù)集D中數(shù)據(jù)對(duì)象個(gè)數(shù)為N，假設(shè)邊界點(diǎn)個(gè)數(shù)為Nb，孤立點(diǎn)個(gè)數(shù)為No，那么經(jīng)過處理后的數(shù)據(jù)集D中數(shù)據(jù)對(duì)象的個(gè)數(shù)為（N-Nb-No）即剩余核心點(diǎn)的個(gè)數(shù)。

4）掃描所有核心點(diǎn)，取每個(gè)簇中核心點(diǎn)的中心作為K-means聚類算法的聚類中心；

5）進(jìn)行傳統(tǒng)的K-means聚類算法。

附：相異度矩陣dis。

其中，d(i，j)代表對(duì)象i和j之間的相異度，值越小，說明相似性越高，反之，相似性越低。

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

為了檢驗(yàn)改進(jìn)算法的有效性，對(duì)原始算法和改進(jìn)算法進(jìn)行了對(duì)比實(shí)驗(yàn)，用于實(shí)驗(yàn)的CPU是Intel（R）Core（TM）i5-3210M CPU@2.50Ghz，內(nèi) 存 為4GB，實(shí)驗(yàn)軟件環(huán)境：操作系統(tǒng)為64位win7，編程軟件用MatlabR2010b。

圖3 不同聚類數(shù)目的聚類結(jié)果

圖4 類簇指標(biāo)的變化曲線

圖3中的數(shù)據(jù)是用三個(gè)二元正態(tài)高斯分布生成，輸入不同的聚類數(shù)目k=2，3，4，5，得到不同的聚類結(jié)果，從圖中可以看到K=3時(shí)，聚類效果最好。圖4分別是不同的聚類數(shù)目的類簇指標(biāo)，從圖中可以明顯看到，當(dāng)k=3時(shí)，類簇指標(biāo)發(fā)生明顯的變化趨勢(shì)，所以K的正確取值應(yīng)該為3。

表1 傳統(tǒng)K-means與改進(jìn)的K-means聚類算法的準(zhǔn)確率

觀察圖5和圖6會(huì)發(fā)現(xiàn)，數(shù)據(jù)集相同的情況下，傳統(tǒng)的K-means聚類算法沒有排除孤立點(diǎn)和邊界點(diǎn)，準(zhǔn)確率只有70%，聚類質(zhì)量不優(yōu)，聚類結(jié)果將沒有多大的參考意義，改進(jìn)后的K-means聚類算法排除了孤立點(diǎn)和邊界點(diǎn)，準(zhǔn)確率達(dá)到98%，聚類結(jié)果更具有參考價(jià)值。

圖5 傳統(tǒng)K-means算法聚類結(jié)果圖

圖6 改進(jìn)的K-means算法聚類結(jié)果圖

6 結(jié)語

K-means聚類算法是一種被廣泛應(yīng)用的算法，但初始聚類中心是隨機(jī)確定的，實(shí)際數(shù)據(jù)集中存在孤立點(diǎn)，當(dāng)簇中存在孤立點(diǎn)和邊界點(diǎn)就會(huì)嚴(yán)重影響簇的中心點(diǎn)的位置，影響聚類結(jié)果的準(zhǔn)確性和聚類的質(zhì)量。本文改進(jìn)了初始聚類中心的隨機(jī)選取，將基于密度的思想引入到K-means算法中，避免了隨機(jī)選取到孤立點(diǎn)和邊界點(diǎn)的情況，實(shí)驗(yàn)表明該算法具有良好的性能，但還需要做進(jìn)一步的研究：當(dāng)數(shù)據(jù)量增大時(shí)，算法的運(yùn)行時(shí)間也隨之增大，如何節(jié)省算法的運(yùn)行時(shí)間是下一步要研究的內(nèi)容。