基于自適應的粗糙C-均值聚類算法

嚴靜靜，張騰飛

(南京郵電大學 自動化學院,江蘇 南京 210023)

基于自適應的粗糙C-均值聚類算法

嚴靜靜，張騰飛

(南京郵電大學 自動化學院,江蘇 南京 210023)

粗糙C-均值的提出，首次將粗糙集與聚類算法結合起來。隨后，眾多學者對其進行了廣泛研究。然而，絕大多數算法在研究簇的下近似、邊界對象時，使用統一的權重，忽略了這些對象本身的差異性以及對所在簇的貢獻。針對此問題，文中提出一種改進的聚類方法。通過樣本對象偏移其所在簇心的程度，設定不同的簇偏移量，距離簇心越近的樣本對象其簇偏移量越大，反之越小。通過此舉以客觀描述這些樣本對象對其所在簇的貢獻，使得最終聚類結果更加精確、簇內更加緊密、簇間更加稀疏。實例計算結果以及通過MATLAB對數據庫中IRIS的數據集進行仿真驗證，表明提出的改進算法具有一定的可行性。

聚類；粗糙集；粗糙C-均值；簇偏移量

1 概 述

聚類是滿足同類對象相似而不同類對象差異的一種數據分類過程。通過優化對象函數，分組N個樣本對象為c個可能的簇，實現簇內對象具有較高的相似性，簇間對象具有較低的相似性[1]。

傳統的聚類技術強制劃分數據對象到某個簇中，然而在許多數據挖掘應用中，這種要求過于局限。在某些情況下，數據對象可能屬于兩個或兩個以上的簇。由此可知，類邊界嚴重交叉重疊[2]。Bezdek提出模糊聚類如模糊C均值(FCM)，定義0～1之間的模糊隸屬度，使某個對象屬于多個簇成為可能。2002年，Lingras[3-4]在Web數據挖掘時，把粗糙集理論融入到K-均值算法中，定義三種集合：上近似、下近似、邊界。下近似中的對象一定屬于所在的簇，上近似中的對象可能屬于所在或者其他的簇，在解決邊界重疊問題上具有一定的可行性。然而，Lingras在計算簇心時，只考慮了邊界為空和邊界非空的情況。當下近似為空時，算法會出現數值不穩定；計算對象是否屬于上下近似時，使用絕對距離公式，忽視了存在的離散數據點。Peters[5]針對上(下)近似為空時，對相應的下(上)近似權重賦值為1；考慮到離散點的干擾，用相對距離代替絕對距離，并通過實例，證明其優勢。文獻[6-7]提出粗糙模糊算法和模糊粗糙算法，通過加入模糊隸屬度，每個類有一個模糊下近似和模糊邊界，下近似中的對象有明確的權重值，而邊界對象有模糊的權重值，有效提高了邊界精度。

上述粗糙C-均值算法在計算簇心時，上、下近似使用統一的權重值，忽視了樣本對象內部的差異性。根據樣本對象對其所在簇的貢獻程度，無法使用一致的度量值來衡量，否則必將導致某些點的錯誤分類。

文中通過計算樣本對象偏移簇心的程度，每個對象分別賦予不同的權重值，越是靠近簇心的樣本對象其所在簇的權值越大，表明此對象對樣本貢獻最重。通過實驗數據，對比不同的聚類算法，證明了文中提出算法的可行性。

2 粗糙C-均值聚類算法

2.1 粗糙C-均值聚類算法的基礎

粗糙C-均值聚類算法流程如下：

步驟1：初始化參數，設置聚類個數c，任意選取c個樣本中心Ci(i=1,2,…,c)，距離閾值ε，權重值wl,wu。

步驟2：計算每個對象xk到簇心Ci(i=1,2,…,c)的歐氏距離。dik，djk為xk到簇心ci,cj的歐氏距離。

步驟4：更新簇心公式。

(1)

步驟5：重復步驟2～4，直到沒有新的劃分對象。

2.2 粗糙C-均值聚類算法的改進

文獻[7]將模糊集的模糊隸屬度加入到C-均值算法可以處理重疊問題，將粗糙集的上、下近似加入到C-均值算法可以定義不確定的、模糊的、不完備的類，改進后的算法能高效選取聚類原型。文獻[8-13]提出粗糙模糊C均值融合算法。該算法通過粗糙集上、下近似的引入改變了模糊C均值算法中隸屬度函數的分布情況,修正了模糊隸屬度計算公式(2)和簇心的更新公式(3)。

模糊隸屬度uik表明對象xk與類Ui的關聯程度，隸屬度越大表明對象對其類關聯程度越高、簇作用越大。

(2)

將模糊隸屬度加入粗糙集質心迭代公式：

Vi=

(3)

文獻[6,8]將下近似中的對象的權重值設為1，認為下近似中的對象肯定是屬于所在的類，對其類關聯程度最高，簇心迭代公式更新為:

Vi=

(4)

3 基于自適應的粗糙K-均值聚類算法

3.1 對象偏移質心程度的偏移量

文中提出的算法(IMP-RCM)基于對象偏移簇心程度的偏移量，在進行公式迭代時，每個樣本對象的權重值設為:

(5)

約束條件：

其中:σij為樣本對象到簇心的標準差;mi為類i中樣本數。

從式中可以看出類內對象離簇心越近，σij值越小，其對所在類的貢獻越大，分配的權重值越大。反之，如果偏移度越大，σij樣本對象到簇心距離越遠，對其所在類的貢獻越低，相應的樣本對象獲得的權重值越低。

對于wl與wu值的公式，文中不再使用默認參數值，而是參照樣本中上、下近似對象的個數，wl(wu)是樣本下(上)近似對象的個數比樣本數。

(6)

3.2 基于自適應的粗糙C-均值聚類算法

文中提出的算法(IMP-RCM)是在式(4)的基礎上進行改進。式(4)中簇內樣本對象權重是所有樣本總數的倒數，忽視樣本個體對類的貢獻差異。文中將式(5)引入到簇心迭代公式中。同時式(4)中wl、wu受初始參數影響較大，提出式(6)，考慮上、下近似樣本的對象個數。

步驟1：初始化參數，設置聚類個數c，任意選取c個樣本中心Ci(i=1,2,…,c)，距離閾值ε。

步驟2：計算權重值wl、wu，以及每個對象xk到樣本中心Ci(i=1,2,…,c)的歐氏距離。dik，djk為xk到質心ci,cj的歐氏距離。

步驟4：更新簇心公式。

Vi=

(7)

步驟5：重復步驟2～4，直到沒有新的劃分對象。

在步驟4中，不再是傳統意義上對象權重值都是固定值，在每次迭代過程中，簇心越來越收斂，趨于穩定。

4 實驗仿真分析

為了驗證算法的處理效果，文中對UCI數據庫中的IRIS數據集進行MATLAB仿真分析。IRIS數據特征見表1。

表1 IRIS數據集特征

先通過主成分分析法將IRIS數據集進行降維處理，隨后采用HCM算法、粗糙RCM算法、文中改進的RCM算法對降維后的數據集進行聚類分析。聚類分布圖分別為圖1～3所示。其中，▽、△、○分別表示IRIS的三個類對象，即簇1、簇2、簇3；黑圓×表示簇心。簇1相距簇2、簇3較遠，而且簇2與簇3邊界交叉重疊。

圖1 HCM算法IRIS數據點分布

圖2 RCM算法IRIS數據點分布

HCM算法強制認為非此即彼的劃分，沒有考慮邊界嚴重交織、模糊的劃分。圖2標出有些點屬于某個簇是不科學的；粗糙RCM的權重wl=0.7，wu=0.3。文中改進的權重值屬于自適應值，從圖2看出，出現劃分的錯誤點，而改進算法得到的簇心(見圖3)較圖2更科學，與所在簇更緊密。

圖3 文中改進的RCM算法IRIS數據點分布

5 結束語

文中主要針對絕大多數算法在研究簇的下近似、邊界對象時，使用統一的權重，忽略了這些對象本身的差異性以及對所在簇的貢獻差異，提出一種新的改進方法。通過對樣本對象偏移其所在簇心的程度，設定不同的簇偏移量，以客觀描述這些樣本對象對其所在簇的貢獻，使得最終聚類結果更加精確、簇內更加緊密、簇間更加稀疏。通過MATLAB仿真，對比以往的聚類，表明基于自適應的粗糙C-均值聚類算法的聚類效果更優。

[1]MitraS,BankaH,PedryczW.Rough-fuzzycollaborativeclustering[J].IEEETransonSystems,ManandCybernetics,PartB:Cybernetics,2006,36(4):795-805.

[2]LingrasP,PetersG.Roughclustering[J].WileyInterdisciplinaryReviews:DataMiningandKnowledgeDiscovery,2011,1

(1):64-72.

[3]LingrasP,WestC.Intervalsetclusteringofwebuserswithroughk-means[J].Journal of Intelligent Information Systems,2004,23(1):5-16.

[4] Pawan L,Rui Y,Chad W.Comparison of conventional and roughk-means clustering[C]//Proc of 9th international conference on rough sets,fuzzy sets,data mining,and granular computing.Berlin:Springer,2003:130-137.

[5] Georg P.Some refinements of roughk-means clustering[J].Pattern Recognition,2006,39(8):1481-1491.

[6] Hu Qinghua,Yu Daren.An improved clustering algorithm for information granulation[C]//Proc of 2nd international conference on FSKD.Berlin:Springer,2005:494-504.

[7] Maji P,Pal S K.RFCM:A hybrid clustering algorithm using rough and fuzzy sets[J].Fundamenta Informaticae,2007,80(4):475-496.

[8] 王 丹,吳孟達.粗糙模糊C均值融合聚類[J].國防科技大學學報,2011,33(3):145-150.

[9] Maji P,Paul S.Robust rough-fuzzy c-means algorithm:design and applications in coding and non-coding RNA expression data clustering[J].Fundamenta Informaticae,2013,124:153-174.

[10] Lai J Z C,Juan E Y T,Lai F J C.Rough clustering using generalized fuzzy clustering algorithm[J].Pattern Recognition,2013,46(9):2538-2547.

[11] Peters G,Crespo F,Lingras P,et al.Soft clustering - fuzzy and rough approaches and their extensions and derivatives[J].International Journal of Approximate Reasoning,2013,54(2):307-322.

[12] Scitovski R,Sabo K.Analysis of the k-means algorithm in the case of data points occurring on the border of two or more clusters[J].Knowledge-based Systems,2014,57(2):1-7.

[13] Velmurugan T.Performance based analysis between k-means and fuzzy c-means clustering algorithms for connection oriented telecommunication data[J].Applied Soft Computing,2014,19(6):134-146.

RoughC-means Clustering Algorithm Based on Self-adaption

YAN Jing-jing，ZHANG Teng-fei

(College of Automation,Nanjing University of Posts and Telecommunications,Nanjing 210023,China)

RoughC-meansisproposedtocombinetheroughsetwithclusteringalgorithmfirst.Inthefollowing,manyscholarshavebeendoingextensiveresearch.However,fortheobjectsinthelowapproximationorboundary,themostofalgorithmsuseunifiedweights,ignoringthedifferenceoftheobjectsthemselvesandthecontributiontotheclasses.Aimingatthisproblem,animprovedclusteringmethodisputforward.Basedondegreeofobjectsdeviatedcentroidofclusters,itsetsdifferentoffsetstohighlighttheseobjectsoncontributiontotheclassesinthispaper,makingtheresultofclusteringmoreprecise,intra-classesmoreclose,andinter-classesmoresparse.TheexperimentalresultsandsimulationverificationonIRISbyMATLABshowsthemethodisfeasible.

clustering;rough set;roughC-means;offsetsofclasses

2015-06-17

2015-09-23

時間：2016-02-18

江蘇省普通高校研究生科研創新計劃項目(46888LX14819)

嚴靜靜(1990-)，女，碩士生，研究方向為模式識別與智能系統；張騰飛,副教授,博士,研究方向為智能信息處理、智能控制等。

http://www.cnki.net/kcms/detail/61.1450.TP.20160218.1634.054.html

TP

A

1673-629X(2016)03-0067-04

10.3969/j.issn.1673-629X.2016.03.016