王 勇，王李福，饒勤菲，鄒 輝

(重慶理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，重慶 400054)

半徑自適應(yīng)的初始中心點(diǎn)選擇K-medoids聚類算法

王 勇，王李福，饒勤菲，鄒 輝

(重慶理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，重慶 400054)

針對(duì)K-medoids(K為中心點(diǎn))聚類算法對(duì)初始聚類中心敏感、聚類結(jié)果依賴于初始聚類中心的缺陷，提出一種新的半徑自適應(yīng)的初始中心點(diǎn)選擇算法。該算法在每次迭代過(guò)程中都重新根據(jù)剩余樣本點(diǎn)的分布特征計(jì)算半徑，從而實(shí)現(xiàn)動(dòng)態(tài)計(jì)算相應(yīng)樣本點(diǎn)的局部方差和領(lǐng)域半徑，選取較優(yōu)的初始聚類中心點(diǎn)，實(shí)現(xiàn)良好的聚類效果。采用不同規(guī)模的UCI數(shù)據(jù)集和不同比例隨機(jī)點(diǎn)的模擬數(shù)據(jù)集進(jìn)行測(cè)試，利用5個(gè)通用的聚類評(píng)價(jià)指標(biāo)對(duì)性能進(jìn)行評(píng)價(jià)。結(jié)果表明：本算法性能較同類算法有明顯提高。

局部方差；初始聚類中心；聚類；K-medoids;自適應(yīng)

聚類在機(jī)器學(xué)習(xí)及模式識(shí)別中已經(jīng)成為研究的熱點(diǎn)，其在生物信息學(xué)、文本檢索、醫(yī)學(xué)圖像處理、網(wǎng)絡(luò)入侵檢測(cè)等領(lǐng)域有著廣泛的應(yīng)用[1-3]。目前聚類的方法主要分為以下幾類：基于層次的方法、基于密度的方法、基于網(wǎng)格的方法、基于模型的方法、基于劃分的方法和高維數(shù)據(jù)的方法[4-5]。其中，K-medoids聚類算法是基于劃分的經(jīng)典聚類算法之一[6]，因其對(duì)噪聲敏感性較低得到了較多的應(yīng)用[7]。然而，K-medoids聚類算法存在無(wú)法事先確定合適的聚類數(shù)目、算法復(fù)雜度較高、容易達(dá)到局部最優(yōu)、沒(méi)有統(tǒng)一的聚類評(píng)價(jià)準(zhǔn)則函數(shù)、初始中心點(diǎn)選擇誤差較大等缺陷[8]。為克服傳統(tǒng)K-medoids算法在初始聚類中心點(diǎn)選擇方面的不足，姚麗娟[5]通過(guò)矩陣方式求解高密度區(qū)域進(jìn)行初始中心點(diǎn)選取，從而縮小了初始中心點(diǎn)搜索范圍，降低了算法復(fù)雜度，但其需要設(shè)置一個(gè)經(jīng)驗(yàn)值θ來(lái)計(jì)算平均密度Mdensity，通過(guò)Mdensity的計(jì)算確定初始中心點(diǎn)的選擇范圍。馬菁等[9]提出了一種基于粒度的樣本相似度函數(shù)來(lái)選取初始中心點(diǎn)的思路，避免了傳統(tǒng)K-medoids聚類算法中很多不必要的中心點(diǎn)迭代計(jì)算，但其算法中閾值d的確定沒(méi)有可以度量的數(shù)學(xué)方法。謝娟英[10]通過(guò)對(duì)鄰域半徑的確立直接選取最大密度的樣本點(diǎn)作為初始中心點(diǎn)。當(dāng)數(shù)據(jù)規(guī)模較大時(shí)，該算法相比傳統(tǒng)的K-medoids聚類算法時(shí)間復(fù)雜度低，但是鄰域半徑大小只是一個(gè)經(jīng)驗(yàn)值，缺乏一定的理論指導(dǎo)。文獻(xiàn)[11]通過(guò)對(duì)鄰域周圍樣本點(diǎn)個(gè)數(shù)Num的設(shè)置來(lái)計(jì)算方差，并以方差作為半徑來(lái)確定初始中心點(diǎn)的選擇范圍，從而在一定程度提高了聚類的準(zhǔn)確性。不同的Num值對(duì)樣本的鄰域集合、局部方差大小有不同的影響，然而在定義所有樣本局部方差以及樣本鄰域集合時(shí)采用的是同一個(gè)值，并沒(méi)有考慮到樣本局部分布特征的不同對(duì)初始中心點(diǎn)選擇的影響。

為保證選取的初始聚類中心點(diǎn)盡可能位于不同的類簇，文獻(xiàn)[11]雖然采用了統(tǒng)一的Num值，考慮到了全局最優(yōu)的情況，但是好的聚類初始中心點(diǎn)選擇過(guò)程中既要考慮到全局最優(yōu)又要考慮到局部最優(yōu)，采用統(tǒng)一的Num值計(jì)算各個(gè)樣本點(diǎn)的鄰域半徑?jīng)]有考慮到各樣本局部分布特征的不同，因此更好的Num不應(yīng)當(dāng)是一個(gè)固定的值，而應(yīng)既能考慮到全局的最優(yōu)解，又能伴隨著局部樣本分布的變化而變化，具有自適應(yīng)的效果。本文提出了一種根據(jù)每一個(gè)樣本點(diǎn)的分布特征優(yōu)化局部方差和鄰域半徑的方法。為考慮全局分布特性，該方法通過(guò)全局半徑確定Num值，盡可能獲得全局最優(yōu)解。同時(shí)考慮到各個(gè)樣本局部分布特征的不同，選用在同一個(gè)半徑范圍外樣本點(diǎn)的數(shù)量作為每一個(gè)樣本的Num值，不同的樣本分布特性將會(huì)得到不同的Num值，從而重新定義樣本的局部方差和鄰域半徑。該方法能動(dòng)態(tài)計(jì)算出相應(yīng)樣本點(diǎn)的鄰域半徑，通過(guò)對(duì)鄰域半徑的確立，選取出較優(yōu)的初始聚類中心點(diǎn)。

1 基于局部方差的K-medoids算法

基于局部方差的K-medoids算法[10]思想來(lái)源于概率論和數(shù)理統(tǒng)計(jì)。當(dāng)數(shù)據(jù)在平均數(shù)附近波動(dòng)較大時(shí)，各數(shù)據(jù)與平均數(shù)之差的平方和較大，方差較大；反之則方差較小。根據(jù)定義，位于數(shù)據(jù)分布較為集中的區(qū)域或者中心區(qū)域方差較小。為了尋找較好的初始聚類中心，選擇的K個(gè)初始聚類中心不但要盡可能處于K個(gè)類簇的中心區(qū)域，而且應(yīng)盡量分別位于K個(gè)類簇，既保證初始聚類中心位于樣本分布密集區(qū)域，同時(shí)保障初始聚類中心位于不同的類簇。算法選取初始中心點(diǎn)的詳細(xì)步驟如下：

步驟1 輸入K，X，Num(其中K為類簇?cái)?shù)，X為數(shù)據(jù)集，Num值為近鄰樣本參數(shù))。

步驟2 計(jì)算X中各個(gè)樣本點(diǎn)xi的局部方差F(xi)，依據(jù)F(xi)值將X中的樣本按照升序排列，得到樣本集X′，同時(shí)初始化聚類中心點(diǎn)集M為空，即M={}。

步驟5 如果M中包含有K個(gè)中心點(diǎn)，即|M|=K，則轉(zhuǎn)步驟6，否則轉(zhuǎn)步驟3。

步驟6 輸出初始中心點(diǎn)集M。

該算法在定義樣本局部方差和鄰域半徑時(shí)采用統(tǒng)一的Num值，并未考慮樣本局部分布特征的不同對(duì)初始中心點(diǎn)選取的影響。雖然與傳統(tǒng)聚類算法相比聚類效果有一定提高，但當(dāng)其采用相同Num值計(jì)算樣本點(diǎn)的鄰域半徑時(shí)，可能會(huì)造成兩種情況：一是鄰域半徑過(guò)大，把不該刪除的樣本點(diǎn)即下一個(gè)待選取的中心點(diǎn)刪除，從而影響初始中心點(diǎn)的選取；二是鄰域半徑過(guò)小，該刪除的樣本點(diǎn)未能刪除，反而被選為下一個(gè)中心點(diǎn)，影響初始中心點(diǎn)的選取。同時(shí)，人為選取Num經(jīng)驗(yàn)值也會(huì)增加操作復(fù)雜度。

2 新的基于局部方差的K-medoids算法

為解決選取的初始聚類中心點(diǎn)既要考慮全局最優(yōu)又要考慮局部最優(yōu)的問(wèn)題，本文提出一種根據(jù)每一個(gè)樣本點(diǎn)的分布特征優(yōu)化局部方差和領(lǐng)域半徑的方法，可以選取出較優(yōu)的初始聚類中心點(diǎn)。

2.1 相關(guān)定義如下

Radius值定義為：

(1)

樣本xi周圍樣本點(diǎn)個(gè)數(shù)的Num值定義為：

Num=num[d(xi-xj)>t×Radius]

(2)

其中，t為從0到10步長(zhǎng)為1的半徑調(diào)節(jié)系數(shù)。

樣本xi的局部方差定義為

(3)

樣本xi的鄰域半徑定義為

(4)

neigh(xi)={xl|d(i,l)≤L1

l=1,2,…,n}

(5)

2.2 算法詳細(xì)步驟

本算法分為4個(gè)階段，流程框架如圖1所示。

圖1 算法流程框架

算法的詳細(xì)步驟如下：

a) 初始化聚類中心

步驟1 根據(jù)式(1)計(jì)算所有樣本點(diǎn)之間的平均距離作為Radius值，同時(shí)初始化聚類中心點(diǎn)集M為空，即M={}。

步驟2 每個(gè)樣本點(diǎn)以t×Radius作為半徑，根據(jù)式(2)計(jì)算得到n個(gè)樣本點(diǎn)各自的Num值，步驟如下：

① 令Num=0；

② 計(jì)算dj到di的距離dij，j=1,2,…,n；

③ 若dij>t×Radius，則Num++。

步驟3 根據(jù)式(3)計(jì)算每個(gè)樣本點(diǎn)的局部方差，再根據(jù)式(4)得到每個(gè)樣本點(diǎn)的鄰域半徑。

步驟4 取局部方差最小的樣本點(diǎn)作為初始聚類中心點(diǎn)，并加入到集合M中。

步驟5 按照式(4)和(5)刪除該中心點(diǎn)及其鄰域半徑內(nèi)的樣本點(diǎn)。

步驟6 重復(fù)步驟2～5，直到初始中心點(diǎn)集M中包含有K個(gè)中心點(diǎn)，即|M|=K。

步驟7 輸出中心點(diǎn)集M。

b) 構(gòu)造初始類簇

步驟1 將X中所有樣本點(diǎn)分配給M中距離最近的中心點(diǎn)，得到初始類簇劃分。

步驟2 計(jì)算聚類誤差平方和。

c) 更新類簇中心點(diǎn)

步驟1 在每一個(gè)類簇中重新計(jì)算每個(gè)樣本點(diǎn)到其他樣本點(diǎn)的距離，將距離和最小的樣本點(diǎn)作為新的類簇中心點(diǎn)。

步驟2 用新中心點(diǎn)替換原來(lái)的中心點(diǎn)。

d) 重新分配數(shù)據(jù)

步驟1 在X中計(jì)算每個(gè)樣本點(diǎn)到M中每個(gè)中心點(diǎn)的距離，將樣本分配到距離最近的中心點(diǎn)所在的類簇。

步驟2 計(jì)算當(dāng)前類簇的聚類誤差平方和，若沒(méi)有變化，則轉(zhuǎn)步驟c)繼續(xù)執(zhí)行，連續(xù)計(jì)算10次若沒(méi)有變化，則算法結(jié)束；否則轉(zhuǎn)步驟c)繼續(xù)執(zhí)行。

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

為測(cè)試本文算法的聚類性能，分別采用UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)[12]的經(jīng)典數(shù)據(jù)集和含有不同規(guī)模、不同比例的模擬數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)配置為Pentium(R) Dual-Core E5800 3.20GHz CPU,48G內(nèi)存，500G硬盤，Win7 64位操作系統(tǒng)的高性能計(jì)算機(jī)，使用Java語(yǔ)言在Myeclipse 10.0開(kāi)發(fā)環(huán)境下進(jìn)行算法實(shí)現(xiàn)。將改進(jìn)后的K-medoids算法與改進(jìn)前的K-medoids算法[10-11]進(jìn)行實(shí)驗(yàn)對(duì)比。

算法性能評(píng)價(jià)采用5個(gè)通用的聚類評(píng)價(jià)指標(biāo)：聚類誤差平方和、RI指數(shù)、Precision、Recall、F1值。若TP為同一類的樣本點(diǎn)被分到同一個(gè)簇，TN為不同類的樣本點(diǎn)被分到不同簇，F(xiàn)P為不同類的樣本被分到同一個(gè)簇，F(xiàn)N為同一類的樣本被分到不同簇，則有：

RI=(TP+TN)/(TP+FP+FN+TN)

(6)

Precision=TP/(TP+FP)

(7)

Recall=TP/(TP+FN)

(8)

F1=2×Recall×Precision/(Recall+Precision)

(9)

3.1 UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)數(shù)據(jù)集實(shí)驗(yàn)

采用UCI數(shù)據(jù)庫(kù)[12]常用的10個(gè)經(jīng)典測(cè)試數(shù)據(jù)集進(jìn)行測(cè)試，包括Iris、Wine、WDBC等。其中，大數(shù)據(jù)集選用包含2 310個(gè)樣本的Soybean-small數(shù)據(jù)集。數(shù)據(jù)集見(jiàn)表1，表中最后一列t為調(diào)節(jié)系數(shù)。

表1 數(shù)據(jù)集描述及相應(yīng)的t值

圖2顯示了不同算法在不同數(shù)據(jù)集上的測(cè)試評(píng)價(jià)指標(biāo)。通過(guò)實(shí)驗(yàn)結(jié)果比較可見(jiàn)：在數(shù)據(jù)集2(Iris)上除聚類誤差平方和指標(biāo)外其余各指標(biāo)低于另外兩個(gè)算法；數(shù)據(jù)集3(Wine)上Precision指標(biāo)略低于另外兩個(gè)算法，但是其余5個(gè)指標(biāo)均優(yōu)于Xie和Gao的算法；在數(shù)據(jù)集1(Soybean-small)上Recall指標(biāo)低于其余兩種算法，其余5個(gè)指標(biāo)均優(yōu)于Xie和Gao的算法。在剩余的4個(gè)數(shù)據(jù)集中，5項(xiàng)指標(biāo)均大幅優(yōu)于另外兩種算法。

以上關(guān)于UCI數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果分析表明：本文算法優(yōu)于改進(jìn)前算法，有效改進(jìn)了聚類效果，同時(shí)算法的伸縮性也有所提高。

3.2 人工模擬數(shù)據(jù)集實(shí)驗(yàn)

表2 隨機(jī)生成的帶隨機(jī)點(diǎn)的人工模擬數(shù)據(jù)集的生成參數(shù)

圖3顯示了不同算法在不同模擬數(shù)據(jù)集上的評(píng)價(jià)指標(biāo)。由實(shí)驗(yàn)結(jié)果比較可見(jiàn)：在隨機(jī)樣本比例為20%的小規(guī)模數(shù)據(jù)集以及隨機(jī)樣本比例分別為10%，15%的大規(guī)模數(shù)據(jù)集上，3種算法聚類性能評(píng)價(jià)指標(biāo)相當(dāng)；在其余的數(shù)據(jù)集上，本文算法均大幅優(yōu)于改進(jìn)前算法和基于鄰域的K中心點(diǎn)聚類算法。從圖中還可以看出：另外兩種算法出現(xiàn)較大波動(dòng)性，說(shuō)明本文算法較少受到隨機(jī)性點(diǎn)的影響，聚類效果更穩(wěn)定。

以上模擬數(shù)據(jù)集實(shí)驗(yàn)結(jié)果顯示：本文算法聚類效果更穩(wěn)定，對(duì)含有隨機(jī)性樣本點(diǎn)的數(shù)據(jù)集有更好的聚類效果。

圖2 UCI數(shù)據(jù)集的聚類結(jié)果比較

Fig.2 Comparison of clustering results on UCI datasets

圖3 不同比例隨機(jī)點(diǎn)人工模擬數(shù)據(jù)集上實(shí)驗(yàn)結(jié)果

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

本文針對(duì)現(xiàn)有K-medoids聚類算法的不足，提出了一種半徑自適應(yīng)的初始中心點(diǎn)選擇K-medoids 聚類算法。該算法結(jié)合了樣本的全局分布特征與局部分布特征，重新對(duì)局部方差和鄰域半徑進(jìn)行了優(yōu)化，從而提高了原聚類算法的性能。在UCI數(shù)據(jù)集以及含有不同比例隨機(jī)點(diǎn)的不同規(guī)模模擬數(shù)據(jù)集上的測(cè)試結(jié)果表明：本文算法可伸縮性較好，在含有不同比例隨機(jī)點(diǎn)的數(shù)據(jù)集中有更好的聚類效果，說(shuō)明本文算法聚類效果較好。

[1] 王勇，唐靖，饒勤菲，等.高效率的K-means最佳聚類數(shù)確定算法[J].計(jì)算機(jī)應(yīng)用,2014,34(5):1331-1335.

WANG Yong,TANG Jing,RAO Qinfei,et al.High efficient K-means algorithm for determining optimal number of clusters[J].Journal of Computer Applications,2014,34(5):1331-1335.

[2] 陳莊，羅告成.一種改進(jìn)的K-means算法在異常檢測(cè)中的應(yīng)用[J].重慶理工大學(xué)學(xué)報(bào)(自然科學(xué)),2015,29(5):66-70.

CHEN Zhuang,LUO Gaocheng.Improved K-means Algorithm Using in Anomaly Detection[J].Chongqing University of Technology(Natural Science),2015,29(5):66-70.

[3] 劉云.中文文本關(guān)鍵詞提取和文本聚類中聚類中心點(diǎn)選取算法研究[D].鎮(zhèn)江:江蘇大學(xué),2016.

LIU Yun.Research on Keyword Extraction Algorithm for Chinese Texts and Cluster Center Point Selection Algorithm in Text[D].Zhenjiang:Jiang Su University,2016.

[4] 孫吉貴,劉杰,趙連宇.聚類算法研究[J].軟件學(xué)報(bào),2008,19(1):48-61.

SUN Jigui,LIU Jie,ZHAO Lianyu.Clustering algorithm research[J].Journal of Software,2008,19(1):48-61.

[5] 金建國(guó).聚類方法綜述[J].計(jì)算機(jī)科學(xué),2014,41(11A):288-293.

JIN Jianguo.Review of Clustering Method[J].Computer Science,2014,41(11A):288-293.

[6] 姚麗娟，羅可，孟穎.一種新的k-medoids聚類算法[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(19),153-157.

YAO Lijuan,LUO Ke,MENG Ying.Newk-medoids clustering algorithm[J].Computer Engineering and Applications,2013,49(19):153-157.

[7] 朱曄，馮萬(wàn)興，郭鈞天,等.一種改進(jìn)的K-中心點(diǎn)聚類算法及在雷暴聚類中的應(yīng)用[J].武漢大學(xué)學(xué)報(bào)(理學(xué)版),2015,61(5):497-502.

ZHU Ye,FENG Wanxing,GUO Juntian,et al.ImprovedK-Medoids Algorithm Based on Density Information for Thunderstorm Clustering[J].Journal of Wuhan University(Nat Sci Ed),2015,61(5):497-502.

[8] 潘楚，張?zhí)煳?，羅可.兩種新搜索策略對(duì)K-medoids聚類算法建模[J].小型微型計(jì)算機(jī)系統(tǒng),2015,36(7):1453-1457.

PAN Chu,ZHANG Tianwu,LUO Ke.ModelingK-medoids Clustering Algorithm by Two New Search Strategies[J].Journal of Chinese Computer Systems,2015,36(7):1453-1457.

[9] 馬菁，謝娟英.基于粒計(jì)算的K-medoids聚類算法[J].計(jì)算機(jī)應(yīng)用,2012,32(7):1973-1977.

MA Jing,XIE Juanying.New K-medoids clustering algorithm based on granular computing[J].Journal of Computer Applications,2012,32(7):1973-1977.

[10]謝娟英，郭文娟，謝維信.基于鄰域的K中心點(diǎn)聚類算法[J].陜西師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2012(7):16-22.

XIE Juanying,GUO Wenjuan,XIE Weixin.A neighborhood-based K-medoids clustering algorithm[J].Journal of Shanxi Normal University(Natural Science Edition),2012(7):16-22.

[11]謝娟英，高瑞.Num-近鄰方差優(yōu)化的K-medoids聚類算法[J].計(jì)算機(jī)應(yīng)用研究,2015,32(1):30-34.

XIE Juanying,GAO Rui.OptimizedK-medoids clustering algorithm by variance of Num-near neighbor[J].Application Research of Computers,2015,32(1):30-34.

[12]FRANK A,ASUNCOIN A.UCI machine learning repository[EB/OL].[2016-10-12].http://archive.ics.uci.edu/ml.

(責(zé)任編輯 楊黎麗)

Radius-Adaptive on Selection of Initial Centers inK-Medoids Clustering

WANG Yong, WANG Li-fu, RAO Qin-fei, ZOU Hui

(College of Computer Science and Engineering, Chongqing University of Technology, Chongqing 400054, China)

For the defect ofK-medoids clustering algorithm which was sensible to the initial center and depended on the initial center, this paper proposed a new selection of initial centers algorithm through radius adaptive. The algorithm calculated each radius according to distribution of the remaining sample in each iteration, thus to dynamically calculate local variance and neighborhood radius for corresponding sample and then select the optimum initial cluster centers to achieve good clustering effect. Using different size of UCI data sets and simulated data sets with different ratios of random points for testing and using the five general clustering index to evaluate its performance, the results show that the performance of this algorithm is better than other similar algorithms.

local variance; initial cluster center; clustering algorithm;K-medoids; adaptive

2016-11-20 基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(61173184)

王勇(1974—)，男，重慶人，博士，副教授，主要從事多媒體和網(wǎng)絡(luò)研究，E-mail： ywang@cqut.edu.cn；通訊作者 王李福(1989—)，男，重慶墊江人，碩士研究生，主要從事圖像處理研究,E-mail: hellowanglifu@163.com。

王勇，王李福，饒勤菲，等.半徑自適應(yīng)的初始中心點(diǎn)選擇K-medoids聚類算法[J].重慶理工大學(xué)學(xué)報(bào)(自然科學(xué))，2017(2):95-101.

format：WANG Yong, WANG Li-fu, RAO Qin-fei, et al.Radius-Adaptive on Selection of Initial Centers inK-Medoids Clustering[J].Journal of Chongqing University of Technology(Natural Science)，2017(2):95-101.

10.3969/j.issn.1674-8425(z).2017.02.017

TP301

A

1674-8425(2017)02-0095-07