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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟6 輸出初始中心點集M。

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

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

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

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

Radius值定義為：

(1)

樣本xi周圍樣本點個數(shù)的Num值定義為：

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

(2)

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

樣本xi的局部方差定義為

(3)

樣本xi的鄰域半徑定義為

(4)

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

l=1,2,…,n}

(5)

2.2 算法詳細步驟

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

圖1 算法流程框架

算法的詳細步驟如下：

a) 初始化聚類中心

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

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

① 令Num=0；

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

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

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

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

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

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

步驟7 輸出中心點集M。

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

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

步驟2 計算聚類誤差平方和。

c) 更新類簇中心點

步驟1 在每一個類簇中重新計算每個樣本點到其他樣本點的距離，將距離和最小的樣本點作為新的類簇中心點。

步驟2 用新中心點替換原來的中心點。

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

步驟1 在X中計算每個樣本點到M中每個中心點的距離，將樣本分配到距離最近的中心點所在的類簇。

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

3 實驗仿真分析

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

算法性能評價采用5個通用的聚類評價指標(biāo)：聚類誤差平方和、RI指數(shù)、Precision、Recall、F1值。若TP為同一類的樣本點被分到同一個簇，TN為不同類的樣本點被分到不同簇，F(xiàn)P為不同類的樣本被分到同一個簇，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機器學(xué)習(xí)數(shù)據(jù)庫數(shù)據(jù)集實驗

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

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

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

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

3.2 人工模擬數(shù)據(jù)集實驗

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

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

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

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

Fig.2 Comparison of clustering results on UCI datasets

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

4 結(jié)束語

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

[1] 王勇，唐靖，饒勤菲，等.高效率的K-means最佳聚類數(shù)確定算法[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] 陳莊，羅告成.一種改進的K-means算法在異常檢測中的應(yīng)用[J].重慶理工大學(xué)學(xué)報(自然科學(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)鍵詞提取和文本聚類中聚類中心點選取算法研究[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é)報,2008,19(1):48-61.

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

[5] 金建國.聚類方法綜述[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].計算機工程與應(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] 朱曄，馮萬興，郭鈞天,等.一種改進的K-中心點聚類算法及在雷暴聚類中的應(yīng)用[J].武漢大學(xué)學(xué)報(理學(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í)煳?，羅可.兩種新搜索策略對K-medoids聚類算法建模[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] 馬菁，謝娟英.基于粒計算的K-medoids聚類算法[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中心點聚類算法[J].陜西師范大學(xué)學(xué)報(自然科學(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].計算機應(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 基金項目：國家自然科學(xué)基金資助項目(61173184)

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

王勇，王李福，饒勤菲，等.半徑自適應(yīng)的初始中心點選擇K-medoids聚類算法[J].重慶理工大學(xué)學(xué)報(自然科學(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