基于密度RPCL的K.medoids算法

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

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

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

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

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

1 密度RPCL算法

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

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

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

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

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

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

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

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

3 實驗結(jié)果分析

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

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

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

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

4 結(jié)語

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

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

參考文獻：

[1]馬箐，謝娟英.基于粒計算的K-medoids 聚類算法[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中心點聚類算法[J].陜西師范大學(xué)學(xué)報（自然科學(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]李聽，鄭宇，江芳澤.用改進的RPCL算法提取聚類的最佳數(shù)目[J].上海大學(xué)學(xué)報，1999，40（8）：120.122.

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

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

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

作者簡介：第一作者郭文娟（1986.），女，甘肅武威人，講師，研究方向為智能信息處理。