基于密度RPCL的K.medoids算法

摘 要：針對(duì)K.medoids算法需要事先給定聚類數(shù)目和初始聚類中心的問題，借助次勝者受罰競(jìng)爭學(xué)習(xí)算法RPCL確定數(shù)據(jù)集的類簇?cái)?shù)目，提出以密度RPCL作為預(yù)處理步驟的K.medoids聚類算法。通過密度RPCL算法對(duì)數(shù)據(jù)集進(jìn)行處理，從而確定K.medoids算法的合理類簇?cái)?shù)目，然后再運(yùn)行改進(jìn)K.medoids算法，由此提高K.medoids算法的聚類效率和聚類準(zhǔn)確性。采用UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)測(cè)試，使用不同的聚類結(jié)果評(píng)價(jià)指標(biāo)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析，證明本文基于密度RPCL的K.medoids算法具有很好的聚類效果。

關(guān)鍵詞：RPCL算法；K.medoids算法；密度；聚類數(shù)目；初始中心

聚類算法是模式識(shí)別、機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘等領(lǐng)域中一個(gè)重要的研究內(nèi)容，該算法根據(jù)一定的相似性準(zhǔn)則將樣本聚集為若干個(gè)類簇。

K.medoids算法是基于劃分的聚類算法，該算法用類中心的數(shù)據(jù)作為中心點(diǎn)來代表類。[1]Park 等人提出一種快速K.medoids 算法，在初始中心點(diǎn)的選擇和更新聚類中心上有了改進(jìn)[2]；自行提出改進(jìn)K.medoids 算法，使所選的初始中心點(diǎn)位于數(shù)據(jù)集中樣本分布密集區(qū)域，并且所選初始中心之間的空間距離較遠(yuǎn)，目的使其位于不同的類簇中。[3]

本文借助于基于密度的次者受罰競(jìng)爭學(xué)習(xí)算法[4.6] （RPCL） 來確定最佳的聚類數(shù)目值，在此基礎(chǔ)上運(yùn)行改進(jìn)的K.medoids 算法，從而改善聚類效果。通過UCI 機(jī)器學(xué)習(xí)數(shù)據(jù)庫數(shù)據(jù)集實(shí)驗(yàn)測(cè)試，表明基于密度RPCL 的K.medoids 算法具有非常好的聚類效果。

1 密度RPCL算法

競(jìng)爭學(xué)習(xí)算法 （Rival Penalized Competitive Learning，RPCL）[4]可以用于確定數(shù)據(jù)集的類簇?cái)?shù)目值，[5.7]但RPCL算法在學(xué)習(xí)時(shí)對(duì)學(xué)習(xí)率和遺忘率非常敏感。[4]在權(quán)值調(diào)整中RPCL算法只考慮了輸入數(shù)據(jù)和權(quán)矢量間相對(duì)位置的影響，卻忽略了數(shù)據(jù)集幾何結(jié)構(gòu)的影響。權(quán)值的調(diào)整就是數(shù)據(jù)對(duì)象對(duì)獲勝單元和次勝單元產(chǎn)生作用力，且使它們發(fā)生位移。獲勝單元和次勝單元的位移，不僅僅和數(shù)據(jù)樣本間的相對(duì)位置有關(guān)，還與數(shù)據(jù)樣本在整個(gè)數(shù)據(jù)集中的幾何位置有關(guān)。基于此，魏麗梅等[6]引入樣本密度，改進(jìn)了RPCL 算法調(diào)整權(quán)值的方法。但是該算法定義數(shù)據(jù)密度時(shí)需選擇部分參數(shù)，缺乏客觀性。

為克服傳統(tǒng)RPCL算法的不足，基于密度的RPCL算法[7]根據(jù)數(shù)據(jù)集樣本的自然分布為每個(gè)樣本定義密度，將該密度引入到節(jié)點(diǎn)權(quán)值調(diào)節(jié)公式，對(duì)各節(jié)點(diǎn)權(quán)矢量進(jìn)行調(diào)節(jié)，得到密度RPCL算法。[7]

2 基于密度RPCL 的K.medoids算法

基于密度RPCL 的K.medoids算法利用密度RPCL算法[7]對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理，然后運(yùn)行改進(jìn)K.medoids算法[3]而得到聚類結(jié)果。算法步驟描述如下。

Step1：由密度RPCL算法得到K.medoids算法的K值。

Step2：初始化中心點(diǎn)：首先計(jì)算數(shù)據(jù)集中數(shù)據(jù)樣本的密度值，將數(shù)據(jù)對(duì)象按照密度值升序排序；選擇密度值最小的數(shù)據(jù)作為中心點(diǎn)，并且從數(shù)據(jù)集中刪去該對(duì)象。計(jì)算該中心點(diǎn)的鄰域，從數(shù)據(jù)集中刪去其鄰域中的對(duì)象；用同樣方法選出K個(gè)初始中心點(diǎn)。

Step3：更新所有的類簇中心：把數(shù)據(jù)對(duì)象分配給距離最近的中心點(diǎn)，為每一類尋找一個(gè)新的中心點(diǎn)，使聚類誤差平方和最小。

Step4：再次分配數(shù)據(jù)直至聚類誤差平方和沒有變化，算法結(jié)束；否則轉(zhuǎn)Step3。

3 實(shí)驗(yàn)結(jié)果分析

通過UCI數(shù)據(jù)集測(cè)試本文基于密度RPCL 的改進(jìn)K.medoids算法。

用UCI中的Iris等6個(gè)常用數(shù)據(jù)集對(duì)基于密度RPCL 的K.medoids算法（簡稱本文K.medoids算法）和改進(jìn)的K.medoids算法進(jìn)行比較。UCI數(shù)據(jù)集描述如表1所示。

通過計(jì)算聚類誤差平方和、聚類時(shí)間和聚類準(zhǔn)確率來評(píng)價(jià)實(shí)驗(yàn)結(jié)果。[8]在各數(shù)據(jù)集上兩種算法分別運(yùn)行20次，文中實(shí)驗(yàn)結(jié)果為20次實(shí)驗(yàn)的平均值。表2是改進(jìn)K.medoids算法和本文K.medoids算法的聚類誤差平方和與聚類時(shí)間結(jié)果比較。圖1是兩種算法聚類準(zhǔn)確率結(jié)果比較。

由表2得到，在所有數(shù)據(jù)集上，本文算法的聚類誤差平方和都少于改進(jìn)K.medoids算法，本文算法的時(shí)間性能在部分?jǐn)?shù)據(jù)集上和改進(jìn)K.medoids算法持平，原因在于運(yùn)行密度RPCL算法耗費(fèi)了時(shí)間，但是本文算法因?yàn)檫x擇了合適的聚類數(shù)目和最佳初始聚類中心，又加快了算法的收斂速度。上圖顯示，本文算法的聚類準(zhǔn)確率高于改進(jìn)K.medoids算法。由以上分析可得，本文基于密度RPCL 的K.medoids算法有效改善了現(xiàn)有K.medoids算法的時(shí)間性能，聚類效果更優(yōu)。

4 結(jié)語

本文針對(duì)K.medoids算法需要事先確定聚類數(shù)目以及初始化聚類中心的缺陷，利用RPCL算法的性能，提出一種用密度RPCL算法對(duì)K.medoids進(jìn)行預(yù)處理，期望得到最佳的數(shù)據(jù)類簇?cái)?shù)目，在此基礎(chǔ)上運(yùn)行改進(jìn)K.medoids算法。

UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫數(shù)據(jù)集上的實(shí)驗(yàn)表明：本文所提出的基于密度RPCL 的K.medoids算法為K.medoids聚類提供了合適的聚類數(shù)目；改進(jìn)K.medoids算法為K.medoids聚類優(yōu)化了初始聚類中心；聚類運(yùn)行時(shí)間、聚類誤差平方和以及聚類準(zhǔn)確率的比較結(jié)果顯示，本文基于密度RPCL 的K.medoids算法獲得良好的聚類效果。不足之處是在于本文算法只是針對(duì)球型數(shù)據(jù)分析，對(duì)于非球形數(shù)據(jù)的分析還需要進(jìn)一步研究。

參考文獻(xiàn)：

[1]馬箐，謝娟英.基于粒計(jì)算的K-medoids 聚類算法[J].計(jì)算機(jī)應(yīng)用，2012，32（7）：1973.1977.

[2]Park H S，Jun C H.A simple and fast algorithm for K.medoids clustering[J].Expert Systems with Applications，2009，36 （2）：3336.3341.

[3]謝娟英，郭文娟，謝維信.基于鄰域的K中心點(diǎn)聚類算法[J].陜西師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2012，40（4）：16.22.

[4]XU L，KRZYZAK A，OJA E.Rival penalized competitive learning for clustering analysis[J].RBF Net，and Curve Detection.IEEE Trans.on Neural Networks，1993，4（4）：636.649.

[5]李聽，鄭宇，江芳澤.用改進(jìn)的RPCL算法提取聚類的最佳數(shù)目[J].上海大學(xué)學(xué)報(bào)，1999，40（8）：120.122.

[6]魏立梅，謝維信.聚類分析中競(jìng)爭學(xué)習(xí)的一種新算法[J].電子科學(xué)學(xué)刊，2000，22 （1）：13.18.

[7]謝娟英，郭文娟，謝維信，等.基于樣本空間分布密度的改進(jìn)次勝者受罰競(jìng)爭學(xué)習(xí)算法[J].計(jì)算機(jī)應(yīng)用，2012，32（3）：638.642.

[8]張惟皎，劉春煌，李芳玉.聚類質(zhì)量的評(píng)價(jià)方法[J].計(jì)算機(jī)工程，2005，31（20）：10.12.

作者簡介：第一作者郭文娟（1986.），女，甘肅武威人，講師，研究方向?yàn)橹悄苄畔⑻幚怼?/p>