一種融合K-means和快速密度峰值搜索算法的聚類方法

盛　華　張桂珠

1(江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院　江蘇 無(wú)錫 214122)2(江南大學(xué)輕工過(guò)程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室　江蘇 無(wú)錫 214122)

?

一種融合K-means和快速密度峰值搜索算法的聚類方法

盛華1張桂珠2

1(江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院江蘇 無(wú)錫 214122)2(江南大學(xué)輕工過(guò)程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室江蘇 無(wú)錫 214122)

K-means算法的初始聚類中心是隨機(jī)選取的，不同的初始中心輸入會(huì)得出不同的聚類結(jié)果。針對(duì)K-means算法存在的問(wèn)題，提出一種融合K-means算法與聚類的快速搜索和發(fā)現(xiàn)密度峰算法的聚類算法(K-CBFSAFODP)。該算法是這樣考慮的：類簇中心被具有較低局部密度的鄰居點(diǎn)包圍，且與具有更高密度的任何點(diǎn)都有相對(duì)較大的距離，以此來(lái)刻畫(huà)聚類中心；再運(yùn)用K-means算法進(jìn)行迭代聚類，彌補(bǔ)了K-means聚類中心隨機(jī)選取導(dǎo)致容易陷入局部最優(yōu)的缺點(diǎn)；并且引入了熵值法用來(lái)計(jì)算距離，從而實(shí)現(xiàn)優(yōu)化聚類。在UCI數(shù)據(jù)集和人工模擬數(shù)據(jù)集上的實(shí)驗(yàn)表明，融合算法不僅能得到較好的聚類結(jié)果，而且聚類很穩(wěn)定，同時(shí)也有較快的收斂速度，證實(shí)了該融合算法的可行性。

聚類K-means算法CBFSAFODP算法初始聚類中心密度信息熵

0　引　言

聚類分析是一種無(wú)監(jiān)督的機(jī)器學(xué)習(xí)方法，是數(shù)據(jù)挖掘中的重要研究方向之一[1]。它基于“物以類聚”原理，即在同一個(gè)簇中的數(shù)據(jù)對(duì)象之間具有較高的相似度，而在不同簇?cái)?shù)據(jù)對(duì)象間具有較低的相似度。目前聚類分析已經(jīng)廣泛地應(yīng)用到許多領(lǐng)域，如模式識(shí)別、數(shù)據(jù)分析、圖像處理、市場(chǎng)分析、客戶關(guān)系管理等[2]。聚類分析的常用方法可大致劃分為五類：基于劃分的方法、基于層次的方法、基于密度的方法、基于網(wǎng)格的方法和基于模型的方法[3]。

在數(shù)據(jù)挖掘下的聚類分析方法中，K-means算法是運(yùn)用最廣泛的基于劃分的算法。它理論證實(shí)可靠、算法簡(jiǎn)單可行、收斂速度很快，對(duì)大數(shù)據(jù)集的處理很有效果。但K-means算法也存在一些缺陷：對(duì)K值的選擇沒(méi)有準(zhǔn)確依據(jù)、聚類結(jié)果的好壞嚴(yán)重依賴初始聚類中心的設(shè)定、容易陷入局部最優(yōu)解、只能處理數(shù)值屬性的數(shù)據(jù)以及無(wú)法檢測(cè)到的非球形簇[4]。

CBFSAFODP算法(Alex Rodriguez 和 Alessandro Laio 在 Science 上發(fā)表了一篇名為《Clustering by fast search and find of density peaks》的文章，本文姑且稱這篇文章中的算法為CBFSAFODP)是屬于數(shù)據(jù)挖掘下聚類分析方法中一種應(yīng)用廣泛的基于密度的算法。該算法簡(jiǎn)單新穎、對(duì)初始值不敏感、靈活性好、能檢測(cè)非球形簇以及能有效地處理大數(shù)據(jù)集，在解決聚類初始中心[5]選取方面很有針對(duì)性，目前已被應(yīng)用到數(shù)據(jù)挖掘。然而一些單一的聚類方法往往得不到最佳的聚類效果。

為了克服CBFSAFODP算法在聚類效果上的不足，本文提出一種融合K-means算法與聚類的快速搜索和發(fā)現(xiàn)密度峰算法的聚類算法。K-CBFSAFODP是把K-means算法融入到CBFSAFODP中去，在執(zhí)行CBFSAFODP算法選取好聚類中心后，再運(yùn)用K-means算法進(jìn)行迭代聚類，彌補(bǔ)了K-means聚類中心隨機(jī)選取導(dǎo)致容易陷入局部最優(yōu)的缺點(diǎn)。該算法為聚類算法選擇初始聚類中心提供了一種新的思路，能夠更加合理地選取聚類數(shù)K以及初始聚類中心，極大程度上減少K-means算法因初始聚類中心的不合理選取導(dǎo)致聚類結(jié)果的不穩(wěn)定性[6]，以及過(guò)多依賴參數(shù)選擇問(wèn)題。實(shí)驗(yàn)結(jié)果表明，K-CBFSAFODP比單獨(dú)的K-means、CBFSAFODP具有更好的聚類效果。

1　聚類的快速搜索和發(fā)現(xiàn)密度峰算法

1.1算法思想

CBFSAFODP算法[7]基于這樣的設(shè)想：類簇中心被具有較低局部密度的鄰居點(diǎn)包圍，且與具有更高密度的任何點(diǎn)都有相對(duì)較大的距離。對(duì)于每一個(gè)數(shù)據(jù)點(diǎn)需要計(jì)算兩個(gè)量(ρi和δi)：一是局部密度；二是與高于該點(diǎn)的所有局部密度中與該點(diǎn)距離[8]的最小值，來(lái)刻畫(huà)聚類中心。然后對(duì)每個(gè)cluster確定其邊界區(qū)域[9]，再將其中的數(shù)據(jù)點(diǎn)進(jìn)一步分為cluster core和cluster halo，從而實(shí)現(xiàn)聚類的方法。

1.2算法聚類中心的選取

S={xi|xi∈Rn,i=1,2,…,n},IS={1,2,…,n}。設(shè)ρi包含Cj(j=1,2,…,k)個(gè)簇，Cj(j=1,2,…,k)表示初始的聚類中心，dij=dist(xi,xj)表示數(shù)據(jù)點(diǎn)xi與xj之間的(某種)距離。

(1) 樣本xi與xj之間的歐氏距離：

(1)

(2) xi局部密度ρi：包括Cut-off kernel 和 Gaussian kernel兩種計(jì)算方式。

Cut-off kernel:

(2)

其中，如果x<0，那么χ(x)=1，否則χ(x)=0;dc是一個(gè)截?cái)嗑嚯x。其實(shí)就是與點(diǎn)xi的距離小于dc的點(diǎn)的個(gè)數(shù)(不包括自己)，這意味著對(duì)于大數(shù)據(jù)集，分析結(jié)果對(duì)于dc的選擇具有很好的魯棒性。根據(jù)大量實(shí)驗(yàn)表明，dc一般取聚類中所有數(shù)據(jù)點(diǎn)之間相互距離按升序排列的2%位置的距離數(shù)值定義為dc。

Gaussian kernel:

(3)

對(duì)比定義可知，cut-off kernel為離散值，Gaussian kernel為連續(xù)值。相對(duì)而言，后者產(chǎn)生沖突的概率較小，即不同數(shù)據(jù)點(diǎn)具有相同局部密度之概率更小。

(3) 數(shù)據(jù)點(diǎn)xi的δi是點(diǎn)到任何比其密度大的點(diǎn)的距離的最小值。

則可定義如下：

(4)

圖1　數(shù)據(jù)點(diǎn)按照密度降序排列　　圖2　圖1中數(shù)據(jù)的決策圖

由圖2不難發(fā)現(xiàn)，第1號(hào)和第10號(hào)數(shù)據(jù)點(diǎn)由于同時(shí)具有較大的ρ值和δ值，于是從數(shù)據(jù)集中脫穎而出，而這兩個(gè)數(shù)據(jù)點(diǎn)恰好是圖1所示數(shù)據(jù)集中的兩個(gè)聚類中心。此外，編號(hào)為26、27、28的三個(gè)數(shù)據(jù)點(diǎn)在原始數(shù)據(jù)集中是“離群點(diǎn)”，它們?cè)趫D2中也有特點(diǎn)：其δ值很大，但ρ值很小。

(5) 由于圖2對(duì)確定聚類中心起到?jīng)Q定作用，因此也將這種由(ρi,δi)對(duì)應(yīng)的圖稱為決策圖。然后，需要注意的是，在確定聚類中心時(shí)，采用的是定性分析而不是定量分析，且包含了主觀因素，如圖3所示。不同的人可能得出不同的結(jié)果，聚類中心就很難分辨了。

圖3　決策圖中聚類中心難以確定例子

對(duì)于這些在決策圖中無(wú)法用肉眼判斷出聚類中心的情形(CBFSAFODP算法聚類中心個(gè)數(shù)的確定用“automatically”確實(shí)不太合適)，給出一種確定聚類中心個(gè)數(shù)的方法，即計(jì)算一個(gè)將ρ值和δ值綜合考慮的量：

γi=ρiδii∈IS

(6) 然而“若干個(gè)”到底是取多少個(gè)？本文算法首先把降序排列好的γ在坐標(biāo)平面上畫(huà)出來(lái)，以下標(biāo)為橫軸，γ為縱軸，如圖4所示。非聚類中心的γ值比較平滑，而從非聚類中心過(guò)渡到聚類中心時(shí)γ值有一個(gè)明顯的跳躍，這個(gè)跳躍用肉眼或數(shù)值檢測(cè)都可以判斷出來(lái)。

圖4　降序排列γ值示意圖

1.3CBFSAFODP算法步驟

Step1初始化及預(yù)處理：

Step1.1給定用于確定截?cái)嗑嚯xdc的參數(shù)t∈(0,1)；

Step1.2計(jì)算距離dij，并令dij=dji,i

Step1.3確定截?cái)嗑嚯xdc；

ni=0,i∈IS;

for i=1,2,…,N

{δqi=dmax;

for j=1,2,…,i-1

{

if(dist(xqi,xqi)<δqi)

{

δqi=dist(xqi,xqj);

nqi=qj;

}

}

}

Step3對(duì)非聚類中心數(shù)據(jù)點(diǎn)進(jìn)行歸類：

for i=1,2,…,N

if(cqi=-1)cqi=cnqi

Step4若nc>1，則將每個(gè)cluster中的數(shù)據(jù)點(diǎn)進(jìn)一步分為cluster core和cluster halo：

Step4.1初始化標(biāo)記hi=0,i∈IS；

for i=1,2,…,N-1

{

for j=i+1,i+2,…,N

{

if(ci≠cj且dist(xi,xj)

{

}

}

}

Step4.3標(biāo)識(shí)cluster halo：

for i=1,2,…,N

2　K-means算法

2.1K-means算法的思想

K-means算法[10]是以k為參數(shù)，把n個(gè)數(shù)據(jù)對(duì)象分為k個(gè)簇，每個(gè)簇內(nèi)的數(shù)據(jù)對(duì)象具有較高的相似度，而不同簇之間具有相對(duì)較低的相似度。相似度是通過(guò)計(jì)算一個(gè)簇內(nèi)數(shù)據(jù)對(duì)象的平均值得來(lái)的，相似度的定義是劃分關(guān)鍵，本文中是計(jì)算數(shù)據(jù)對(duì)象之間的賦權(quán)歐式距離[11]。K-means算法的基本思想是：首先在n個(gè)數(shù)據(jù)對(duì)象中隨機(jī)地選擇k個(gè)對(duì)象作為初始聚類中心;接著按最小距離原則來(lái)計(jì)算每個(gè)數(shù)據(jù)對(duì)象到聚類中心的距離，將其賦給最近的簇。然后，重新計(jì)算每個(gè)簇的平均值，計(jì)算收斂函數(shù)，直到各個(gè)聚類的中心不再變化，算法則終止。否則，重復(fù)上述過(guò)程。

2.2K-means算法的一般過(guò)程

輸入：簇的數(shù)目k以及n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)集。

輸出：E不變時(shí)滿足目標(biāo)函數(shù)值最小的k個(gè)簇。

Step1從給出的n個(gè)數(shù)據(jù)對(duì)象中隨機(jī)選出k個(gè)對(duì)象作為初始聚類中心來(lái)執(zhí)行；

Step2計(jì)算數(shù)據(jù)對(duì)象與各個(gè)簇的聚類中心的距離，將每個(gè)數(shù)據(jù)對(duì)象賦給與其距離最近的簇；

Step3重新計(jì)算每個(gè)新簇的均值，作為新的簇的聚類中心，nj表示第j個(gè)簇?cái)?shù)據(jù)對(duì)象個(gè)數(shù)，Cj表示第j個(gè)簇；

(5)

(6)

Step5直到E不再發(fā)生明顯的變化時(shí)，算法終止；否則轉(zhuǎn)向Step2。

3　融合K-means算法與聚類的快速搜索和發(fā)現(xiàn)密度峰算法

3.1K-CBFSAFODP算法思想

針對(duì)K-means算法隨機(jī)選取k個(gè)點(diǎn)作為初始聚類中心進(jìn)行迭代操作而導(dǎo)致聚類結(jié)果的不穩(wěn)定，本文提出了融合K-means算法與聚類的快速搜索和發(fā)現(xiàn)密度峰算法。該算法首先需要對(duì)每個(gè)數(shù)據(jù)計(jì)算兩個(gè)量，即ρi和δi,通過(guò)這兩個(gè)量來(lái)刻畫(huà)聚類中心。 ρi和δi值越大，該點(diǎn)越是可能是聚類中心。再運(yùn)用K-means算法進(jìn)行迭代聚類，且引入信息熵計(jì)算賦權(quán)歐式距離來(lái)更準(zhǔn)確地規(guī)范各對(duì)象的差異程度，從而更好地聚類。

3.2使用熵值法確定各數(shù)據(jù)對(duì)象間賦權(quán)歐氏距離

由于要對(duì)初始聚類中心以及k值做大量的預(yù)處理，來(lái)提高聚類的質(zhì)量，本文引入了信息熵來(lái)度量各屬性權(quán)重，計(jì)算各數(shù)據(jù)對(duì)象之間的權(quán)重系數(shù)。熵是體系混亂程度的度量。一個(gè)屬性的變異程度越大，則整個(gè)系統(tǒng)越是有序的，且該對(duì)象屬性的信息熵會(huì)越小，它提供的信息量就會(huì)越大，權(quán)重也就會(huì)變得越大；反之亦然。

(1) 設(shè)數(shù)據(jù)集有m個(gè)對(duì)象、n維屬性：

本文引入信息熵，計(jì)算各數(shù)據(jù)對(duì)象的賦權(quán)歐氏距離，可以更加入微地分析各個(gè)對(duì)象的差異程度。

(2) 首先對(duì)數(shù)據(jù)對(duì)象屬性進(jìn)行標(biāo)準(zhǔn)化處理，使不同量綱的數(shù)據(jù)可以進(jìn)行比較：

(7)

其中，Mij為數(shù)據(jù)對(duì)象xi的第j維屬性值比重，xij為屬性值。

(3) 分別計(jì)算第j維屬性的熵值和權(quán)值：

熵值：

(8)

權(quán)值：

(9)

(4) 賦權(quán)歐氏距離的計(jì)算公式為：

(10)

在選擇賦權(quán)歐氏距離作為相似性度量后，各個(gè)對(duì)象之間的差異程度能夠準(zhǔn)確地計(jì)算出來(lái)，從而可以提高聚類的準(zhǔn)確度。

3.3K-CBFSAFODP算法描述

輸入：待聚類的n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)集。

輸出：滿足目標(biāo)函數(shù)最小的k個(gè)簇。

Step1使用熵值法計(jì)算數(shù)據(jù)對(duì)象賦權(quán)歐式距離dij,并令dij=dji,i

Step5令γi=ρiδi， i∈IS， γ值越大，越有可能是聚類中心；

Step7計(jì)算數(shù)據(jù)對(duì)象與各個(gè)簇的聚類中心的距離，將每個(gè)數(shù)據(jù)對(duì)象賦給與其距離最近的簇；

Step8根據(jù)式(5)重新計(jì)算每個(gè)新簇的均值，作為新的簇的聚類中心；

Step9根據(jù)式(6)計(jì)算E值；

Step10直到E不再發(fā)生明顯的變化時(shí)，算法終止；否則轉(zhuǎn)向Step7。

4　實(shí)驗(yàn)分析

為了驗(yàn)證融合算法的效果，本文對(duì)CBFSAFODP算法 、K-means算法以及K-CBFSAFODP算法進(jìn)行了對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)采用了Matlab R2013a開(kāi)發(fā)環(huán)境，Intel(R) Core(TM)2 Duo CPU 2.20 GHz,6 GB 內(nèi)存，在Windows 7操作系統(tǒng)上運(yùn)行。

實(shí)驗(yàn)使用了UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中的Iris、Wine和自定義人工數(shù)據(jù)集Dataset作為實(shí)驗(yàn)數(shù)據(jù)。對(duì)K-means算法、CBFSAFODP以及本文改進(jìn)的算法K-CBFSAFODP在選取不同初始聚類中心運(yùn)行100次后進(jìn)行比較鑒定，發(fā)現(xiàn)融合的K-CBFSAFODP算法在聚類誤差平方和、迭代次數(shù)、聚類時(shí)間和聚類的準(zhǔn)確率等方面有極大的優(yōu)化提升。實(shí)驗(yàn)的數(shù)據(jù)集概述情況如表1所示。

表1　實(shí)驗(yàn)數(shù)據(jù)集的構(gòu)成描述

為了說(shuō)明初始中心選取的有效性，本文選取UCI 上Iris數(shù)據(jù)進(jìn)行驗(yàn)證。Iris數(shù)據(jù)集包含150條樣本記錄，分別取自3種不同的鳶尾花的花朵樣本，每一類各50條記錄，其中每一條記錄都含有4個(gè)屬性：sepal length、sepal width、petal width和petal length，共聚成3類。初始聚類中心選取對(duì)比如表2所示。

表2　初始聚類中心選取對(duì)比

由表2可以看出，本文算法的Iris數(shù)據(jù)集初始化聚類中心與實(shí)際數(shù)據(jù)中心非常接近，表明該算法對(duì)Iris數(shù)據(jù)比較有效，同理對(duì)于Wine和dataset數(shù)據(jù)集也有一樣的效果。

由圖5可得知，聚類的每條屬性在聚類過(guò)程中作用是真實(shí)不同的，應(yīng)加以區(qū)分對(duì)待。K-means算法恰恰忽略了數(shù)據(jù)對(duì)象屬性對(duì)聚類作用的差異度，使得聚類結(jié)果與本來(lái)聚類結(jié)果之間存在很大差異。

圖5　計(jì)算得到Iris數(shù)據(jù)集各屬性對(duì)應(yīng)的權(quán)值

如表3所示，可以看出本文算法在誤差平方和以及迭代次數(shù)上明顯優(yōu)于K-means算法。

表3　比較兩個(gè)算法在UCI數(shù)據(jù)集的誤差平方和以及迭代次數(shù)

關(guān)于算法聚類結(jié)果的評(píng)價(jià)，除了常用的聚類誤差平方和、聚類時(shí)間和聚類準(zhǔn)確率評(píng)價(jià)方法之外，還可以采用F-measure指標(biāo)、Rand指數(shù)和Jaccard系數(shù)對(duì)聚類結(jié)果進(jìn)行比較分析。后三個(gè)評(píng)價(jià)指標(biāo)都是在已知正確分類信息的前提下對(duì)聚類算法的聚類結(jié)果進(jìn)行評(píng)價(jià)的有效指標(biāo)。

F-measure采用信息檢索的精確率和召回率思想。數(shù)據(jù)所屬的類i可看作是集合Ni中等待查詢的項(xiàng)；由算法產(chǎn)生的簇Ck可看作是集合Nk中檢索到的項(xiàng)；Nik是簇Ck中類i的數(shù)量。類i和簇Ck的精確率和召回率分別是：

精確率:Precision(i,Ck)=Nik/Nk

召回率:Recall(i,Ck) = Nik/Ni

F-Measure是Precision和Recall的加權(quán)調(diào)和平均(α是參數(shù)):

當(dāng)α=1時(shí)，就是最常見(jiàn)的F1，即：

F-measure可看成分類i的評(píng)判分值。對(duì)聚類結(jié)果來(lái)說(shuō)，其總F-measure可由每個(gè)分類i的F-measure加權(quán)平均得到：

其中：|i|為分類i中所有對(duì)象的數(shù)目。

Rand指數(shù)和Jaccard系數(shù)評(píng)價(jià)指標(biāo)的定義如下：設(shè)U和V分別是基于數(shù)據(jù)集的兩種劃分；其中U是已知正確劃分，而V是通過(guò)聚類算法得到的劃分，定義a、b、c、d四個(gè)參數(shù)。設(shè)a表示U和V都在同一類的樣本對(duì)數(shù)目；b表示在U中為同一類，而在V中卻不是同一類的樣本對(duì)數(shù)目；c表示在V中為同一類，而在U中卻不是同一類的樣本對(duì)數(shù)目；d表示U和V都不在同一類的樣本對(duì)數(shù)目。n(n-1)/2=a+b+c+d,其中，n為數(shù)據(jù)集中所有樣本數(shù)。令M=a+b+c+d，則M表示所有的樣本對(duì)。Rand指數(shù)和Jaccard系數(shù)的定義如下：

Rand指數(shù)：R=(a+d)/M

Jaccard系數(shù)：J=a/(a+b+c)

其中，R表示Rand指數(shù)；J表示Jaccard系數(shù)。

由上述定義可知，F(xiàn)-Measure是Precision和Recall的加權(quán)調(diào)和平均，最優(yōu)劃分期望其值盡可能大；Rand指數(shù)表示聚類結(jié)果與原始數(shù)據(jù)樣本分布的一致性；Jaccard系數(shù)表示正確聚類的樣本對(duì)越多，聚類效果越好。

由圖6、圖7和圖8可知，F(xiàn)-measure、Rand指數(shù)和Jaccard系數(shù)的三個(gè)聚類有效性指標(biāo)顯示，K-CBFSAFODP算法優(yōu)于K-means算法和CBFSAFODP算法。圖9、圖10和圖11是對(duì)Iris、Wine和自定義數(shù)據(jù)集Dataset分別應(yīng)用K-means、CBFSAFODP和K-CBFSAFODP聚類準(zhǔn)確率對(duì)比圖。從圖中可以看出，K-CBFSAFODP算法的聚類準(zhǔn)確率要明顯優(yōu)于K-means算法和CBFSAFODP算法。且融合算法K-CBFSAFODP首先進(jìn)行了一個(gè)優(yōu)化初始聚類中心的過(guò)程，因此比原有算法更加穩(wěn)定，能得到更準(zhǔn)確的聚類中心，快速地到達(dá)收斂?？傊?，實(shí)驗(yàn)結(jié)果表明，本文提出的K-CBFSAFODP具有穩(wěn)定性強(qiáng)、準(zhǔn)確率高、收斂速度快的優(yōu)點(diǎn)。

圖6　聚類結(jié)果的F-measure指標(biāo)　　圖7　聚類結(jié)果的Rand指數(shù)

圖8　聚類結(jié)果的Jaccard系數(shù)　　圖9　Iris數(shù)據(jù)集上的測(cè)試

圖10　Wine數(shù)據(jù)集上的測(cè)試　　圖11　dataset數(shù)據(jù)集上的測(cè)試

5　結(jié)　語(yǔ)

K-means算法初始聚類中心選取的隨機(jī)性所帶來(lái)的聚類結(jié)果的不穩(wěn)定性，以及要求用戶事先指定K值，限制了許多實(shí)際應(yīng)用。本文引入了信息熵以及快速搜索和查找聚類的密度峰，用信息熵對(duì)數(shù)據(jù)對(duì)象屬性進(jìn)行賦權(quán)來(lái)計(jì)算對(duì)象間的距離，來(lái)規(guī)范數(shù)據(jù)的屬性，提高聚類的準(zhǔn)確率；然后利用數(shù)據(jù)點(diǎn)的局部密度以及高于該點(diǎn)的所有局部密度中與該點(diǎn)距離的最小值，對(duì)數(shù)據(jù)集的初始中心進(jìn)行預(yù)處理，來(lái)刻畫(huà)初始聚類中心。提出了融合CBFSAFODP算法和K-means算法的聚類算法K-CBFSAFODP。融合的算法給聚類中心以及聚類個(gè)數(shù)K值的選取提供了新的有效依據(jù)，從而擺脫了隨機(jī)選取聚類中心導(dǎo)致的聚類結(jié)果的不穩(wěn)定性和用戶操作的難度，大大提高了聚類的質(zhì)量和穩(wěn)定性。

[1] Datta Souptik,Giannella Chris,Kargupta Hillol.Approximate Distributed K-Means Clustering over a Peer-to-Peer Network[J].IEEE Transactions on Knowledge and Data Engineering,2009,21(10):1372-1388.

[2] Zhou Tao,Lu Huiling.Clustering algorithm research advances on data mining[J].Computer Engineering and Applications,2012,48(12):100-111.

[3] Wang Jun,Wang Shitong,Deng Zhaohong.Survey on challenges in clustering analysis research[J].Control and Decision,2012,27(3):321-328.

[4] 於躍成,劉彩生,生佳根.分布式約束一致高斯混合模型[J].南京理工大學(xué)學(xué)報(bào),2013,37(6):799-806.[5] 黃敏,何中市,邢欣來(lái),等.一種新的K-means聚類中心選取算法[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(35):132-134.

[6] Fahim A M,Salem A M,Torkey F A,et al.An efficient enhanced k-means clustering algorithm[J].Journal of Zhejiang University SCIENCE A,2006,7(10):1626-1633.

[7] Rodriguez A,Liao A.Machine Learning.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492-1496.

[8] 陳磊磊.不同距離測(cè)度的K-Means文本聚類研究[J].軟件,2015,36(1):56-61.

[9] Qiu Baozhi,Wang Bo.Cluster boundary detection technology for categorical data[J].Journal of Computer Applications,2012,32(6):1654-1656.

[10] 吳夙慧,成穎,鄭彥寧,等.K-means算法研究綜述[J].現(xiàn)代圖書(shū)情報(bào)技術(shù),2011(5):28-35.

[11] 高孝偉.熵權(quán)法在教學(xué)評(píng)優(yōu)中的應(yīng)用研究[J].中國(guó)地質(zhì)教育,2008,17(4):100-104.

A CLUSTERING METHOD COMBINING K-MEANS AND FAST SEARCH ALGORITHM OF DENSITY PEAKS

Sheng Hua1Zhang Guizhu2

1(SchoolofIoTEngineering,JiangnanUniversity,Wuxi214122,Jiangsu,China)2(KeyLaboratoryofAdvancedProcessControlforLightIndustry(MinistryofEducation),JiangnanUniversity,Wuxi214122,Jiangsu,China)

The initial clustering centre of K-means algorithm is selected randomly, different initial centre inputs will get different clustering results. Aiming at this problem of K-means algorithm, we proposed a clustering algorithm which combines K-means algorithm and clustering with the fast density peaks search and finding algorithm (K-CBFSAFODP). This algorithm has the following considerations: the class cluster centre is surrounded by neighbour points with lower local density, and has relatively larger distance to any point with higher density, this is used to depict the cluster centre; then the K-means algorithm is employed for iterative clustering, this makes up the defect that to randomly select K-means clustering centre leads to falling into local optima easily. Moreover, the algorithm introduces entropy method to calculate the distance, thereby realises the optimisation of clustering. It is demonstrated by the experiments on UCI datasets and artificial simulation dataset that this combination algorithm can get better clustering results, and the clusters is very stable as well; meanwhile it also has fast convergence speed. These confirm the feasibility of the combination algorithm.

ClusteringK-means algorithmCBFSAFODP algorithmInitial clustering centresDensityInformation entropy

2015-07-01。江蘇省自然科學(xué)基金項(xiàng)目(BK201401 65)。盛華，碩士生，主研領(lǐng)域：數(shù)據(jù)挖掘，大數(shù)據(jù)。張桂珠，副教授。

TP18

A

10.3969/j.issn.1000-386x.2016.10.058