基于密度RPCL的K.medoids算法

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

關鍵詞：RPCL算法；K.medoids算法；密度；聚類數目；初始中心

聚類算法是模式識別、機器學習和數據挖掘等領域中一個重要的研究內容，該算法根據一定的相似性準則將樣本聚集為若干個類簇。

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

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

1 密度RPCL算法

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

為克服傳統RPCL算法的不足，基于密度的RPCL算法[7]根據數據集樣本的自然分布為每個樣本定義密度，將該密度引入到節點權值調節公式，對各節點權矢量進行調節，得到密度RPCL算法。[7]

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

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

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

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

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

Step4：再次分配數據直至聚類誤差平方和沒有變化，算法結束；否則轉Step3。

3 實驗結果分析

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

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

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

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

4 結語

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

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

參考文獻：

[1]馬箐，謝娟英.基于粒計算的K-medoids 聚類算法[J].計算機應用，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].陜西師范大學學報（自然科學版），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算法提取聚類的最佳數目[J].上海大學學報，1999，40（8）：120.122.

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

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

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

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