一種利用多主體領域系統(tǒng)進行數(shù)據(jù)聚類的新方法*

劉永立

(北京財貿職業(yè)學院信息物流系，北京101101)

一種利用多主體領域系統(tǒng)進行數(shù)據(jù)聚類的新方法*

劉永立*

(北京財貿職業(yè)學院信息物流系，北京101101)

提出一種數(shù)據(jù)聚類方法:MATS，該方法受蟻群算法啟發(fā)，同時應用存在性技術，例如密度概念和聚類有效性指數(shù)(DB -指數(shù))。MATS可以自動根據(jù)一些與數(shù)據(jù)集不直接相關的參數(shù)找到簇。實驗結果證明了MATS可以識別不規(guī)則簇并能有效應用于圖像分割，在圖像分割速度和效果方面比傳統(tǒng)聚類算法(如FCM算法)有明顯提高。

數(shù)據(jù)挖掘;多主體領域系統(tǒng);數(shù)據(jù)聚類;圖像分割

數(shù)據(jù)聚類是按照某種相似性度量，將具有相似特征的樣本歸為一類，使得類內差異相似度較小，類間差異較大。但目前為止，還沒有任何一種聚類技術(聚類算法)可以普遍適用于揭示不同的數(shù)據(jù)集結構，一般來說，不同的聚類技術應用于不同場合和領域。

數(shù)據(jù)聚類在很多領域都有應用。其中，在模式識別及圖像分割領域近年來有很多新的研究成果。Pwitt首先提出了圖像分割時應該采用模糊處理的方法［1］。同時訓練樣本圖像的匱乏又需要無監(jiān)督分析，而模糊聚類正好滿足這兩方面的要求，因此模糊聚類分析成為圖像分割中一個強大的研究分析工具［2］。

在實際中，應用最廣泛當屬Bezkek于1981年提出的模糊C-均值算法FCM(Fuzzy C-Means)，此算法在本質上是一種多次迭代局部尋優(yōu)的過程，其結果在很大程度上依賴于初始值的設定，很容易陷入局部最優(yōu)值。為解決此缺點，許多學者通過借鑒智能算法的全局尋優(yōu)、收斂速度快的優(yōu)點，將其與FCM結合在一起，可以得到許多基于智能計算的模糊聚類圖像分割算法。諸如文獻［3-4］中提到的結合蟻群算法、文獻［5］中提到的結合遺傳算法、文獻［6-7］中提到結合粒子群算法，這些算法都對用于圖像分割的模糊聚類算法進行了一定程度的改進和優(yōu)化。但是，由于這些智能算法自身的特點，造成算法搜索時間較長，收斂速度較慢，并且數(shù)據(jù)集較大時容易出現(xiàn)早熟現(xiàn)象。

因此，在本文中提出一種新的數(shù)據(jù)聚類方法:多主體領域系統(tǒng)(以下簡稱MATS)，這種方法是受蟻群優(yōu)化算法的啟發(fā)，同時應用了一些存在性技術，如:密度概念［8］和聚類有效性指數(shù)(DB-指數(shù))［9］。該算法根據(jù)一些與數(shù)據(jù)集不直接相關的參數(shù)找到簇，能有效用于圖像分割。實驗仿真結果證明了該算法的有效性，并通過與FCM算法、AAFCM算法進行比較，顯示出該方法在圖像分割的速度和效果方面較傳統(tǒng)算法有顯著提高。

1 數(shù)據(jù)聚類與MATS

聚類是一種常用的非監(jiān)督式分類技術，它基于相似性或相異性將輸入空間劃分到K區(qū)域中。分區(qū)或簇的數(shù)量事先可能知道，也可能不知道。輸入空間S由n個對象表示{X1，X2，…，Xn}，簇(主體)由C1，C2，…，Ck表示。其中Ci(i=1，2，…K)需要滿足如下條件:

(1)Ci≠φ i=1，2，…，K

(2)Ci∩Cj=φ i，j=1，2，…，K，and i≠j

(3)C1∪C2∪C3∪…∪CK=S

若根據(jù)數(shù)據(jù)在聚類中的積聚規(guī)則以及應用這些規(guī)則的方法，可以將聚類算法分為傳統(tǒng)聚類算法和聚類新算法。在傳統(tǒng)聚類算法中，包括基于劃分的聚類、基于層次的聚類、基于密度的聚類等多種算法;在聚類新算法中，包括模糊聚類、基于流增量的聚類、基于生物智能的聚類等多種聚類算法。

本文提出了一種新的聚類算法:多主體領域系統(tǒng)(MATS)，該方法受蟻群優(yōu)化算法的啟發(fā)，一方面借鑒了模糊聚類的思想，另一方面利用傳統(tǒng)聚類算法中的密度概念以及聚類有效性參數(shù)——DB-參數(shù)來解決聚類問題。具體來說，該算法分為如下兩步。

步驟1:首先在隨機位點(對象)上初始化K主體，并使用靶向步驟來搜索入侵的對象。而協(xié)調步驟則用于解決爭奪同一對象的主體之間的沖突，因為一個對象只能屬于一個主體。然后使用入侵步驟來幫助主體占據(jù)靶向對象。最后，系統(tǒng)將沒有對象的主體清除掉。步驟1將一直重復直到所有對象都被占據(jù)。

步驟2:系統(tǒng)首先利用所有現(xiàn)有的主體來計算半徑r以滿足領域規(guī)則;然后使用聚類有效性參數(shù)——DB-參數(shù)找尋到符合領域規(guī)則的簇對;最后，使用密度概念在主體之間建立起領域策略，并組合或調整主體。步驟2將一直重復直到無法再建立更深層的領域策略。

2 MATS算法描述

2.1 靶向功能

假設輸入空間S由n個對象{X1，X2，…，Xn}表示，Ok是屬于主體k的對象集。因此，本文可以將S分為對象集Ok和Fk，其中Fk是不屬于主體k的對象集。當主體k搜尋入侵對象時，它將隨機選擇從它在Ok的位點中選擇對象i，并根據(jù)與Fk的歐幾里得距離用對象i找到候選對象集Rk。最后，主體將從Rk中隨機選擇一個對象t。

必須要注意的是，對象t必須是對象i的近鄰對象，從而使得主體k的散度最小化。換句話說就是，t∈nb(i)，其中nb(i)是對象i的近鄰對象。因此，需要進行預處理來找尋每個對象的近鄰對象r。但是當聚類數(shù)據(jù)庫較大時這必將影響MATS的效率。為解決這個問題，本文使用局部框架方法來有效進行預處理。局部框架方法意味著我們能在邊長為L的正方形中找尋到對象i的近鄰對象r。

2.2 協(xié)調步驟

在此方法中，主體是平行的競爭者，因此爭奪同一對象的主體之間會發(fā)生沖突。為解決此問題，該系統(tǒng)使用決定條件來協(xié)調主體。在決定條件中的優(yōu)先次序如下:(1)距離:決定哪個主體和對象最為接近;(2)對象數(shù)量:決定哪個主體占據(jù)最多的對象; (3)分散程度:決定哪個主體有更為緊湊的對象。

2.3 入侵步驟

當主體k能占據(jù)對象t時，可以用式(1)來計算氣味λ(k，t)，即主體k在對象t上存留的氣味量。在式(1)中，d(k，t)是對象t和主體k位置之間的距離。此外，主體k必須考慮到對象t的狀態(tài)。如果對象t未被占據(jù)，主體t可以直接占據(jù)。如果對象t已被主體k'所占據(jù)，則主體k要和主體k'比較二者之間的氣味。

2.4 計算半徑

為防止主體重復性爭奪同一對象導致步驟1中無止境的競爭，可以使用密度概念來建立領域原則。當步驟1完成后，輸入空間D中所有的對象都由主體k劃分為k候選簇。由于主體隨機劃分領域，一個簇可能包含多于一個候選簇。因此如果候選簇屬于同一個簇的話，有必要找到一個原則來連接這些候選簇［10］。

Tao CW提出了一個有效的標準:使用密度概念來找出候選簇之間的關聯(lián)度［11］。因此半徑值對于找尋到對象的鄰域非常必要。

半徑值會影響對象的鄰域和散度，因此每個維度數(shù)據(jù)點的散度都是一個重要的因素［12］。例如，如果數(shù)據(jù)點的散度很大，而其鄰域很小，則可能在任何一個數(shù)據(jù)點的鄰域中都不存在數(shù)據(jù)點。另一方面，如果散度很小，而其鄰域很大，則整個數(shù)據(jù)集可能落在所有數(shù)據(jù)點的鄰域中。根據(jù)Tao CW的論點，通過選取散度不同的候選簇的不同半徑值，可以合理地解決該問題［13］。盡管可以用標準偏差大概地表示半徑，但本文還是使用了數(shù)據(jù)點的散度來表示半徑。半徑值r的定義參見下面式(2)和式(3)。

這里I∈K。

當Ci是候選簇i時，Zi是Ci的中心，如式(3)中的定義。其中ni是Ci中包含的對象數(shù)量。

2.5 應用DB-參數(shù)

DB-參數(shù)是由Davies D L和Bouldin D W在1979年提出的一種聚類有效性參數(shù)［14］。該參數(shù)是簇內散度和簇間距比例的函數(shù)，見式(5)，其中dij是候選簇i和j中心之間的歐幾里得距離，見式(4)中的定義。ri和rj由式(2)計算出來，式(2)用于計算候選簇i(Ci)內的散度。其中Zi是Ci的中心，并在式(3)中進行定義。此外，ni是Ci中的對象數(shù)量。

2.6 領域策略

領域策略用于評估簇對的關系。在MATS中有兩種領域策略。一種是完全關聯(lián)策略，另一種是部分關聯(lián)策略。完全關聯(lián)策略表示簇對之間的關聯(lián)度很高，因此它們之間是關聯(lián)的。換句話說，這些簇對應該屬于一個簇。部分關聯(lián)策略則意味著簇對之間的關聯(lián)度中等，因此它們彼此之間可以交換對象。換句話說，一個簇對含有屬于另一個簇對的對象，而且這兩對簇可以互相交換對象。

在MATS中，完全關聯(lián)策略首先在簇對(Ci，Cj)中進行檢驗，因為候選簇Ci和Cj如果完全關聯(lián)的話不存在部分關聯(lián)策略。首先計算出簇對(Ci，Cj)的半徑值rij。見式(6):

隨后，p2，p3，…，ps-1均勻分布在連接CCi和 CCj的線上。其中p1=CCi，ps=CCj，。CCi是候選簇Ci的中心，而候選簇Ci是Ci所有對象的中數(shù)。CCj是候選簇Cj的中心，而候選簇Cj是Cj所有對象的中數(shù)。|p2-p1|=|p3-p2|=…=|ps-ps-1|=|ps-p1|/(s+ 1)=rij/2以半徑值rij為參數(shù)來計算pm的密度，密度函數(shù)見式(7)。

其中m是Ci和Cj之間的數(shù)據(jù)點，m=1，2，…，s。

hi是Ci的對象數(shù)

hj是Cj的對象數(shù)Xl是屬于Ci或Cj的對象l。

式(8)定義是由Tao CW提出的評估標準，用來評估簇對(Ci，Cj)之間是否存在完整關聯(lián)。在式(8)中，α是一個很重要的參數(shù)，它可以影響聚類的結果。盡管Tao CW將α設置為4，但在MATS中通過一些測試被設置為17。

如果簇對(Ci，Cj)中不存在完全關聯(lián)，那么將會核實簇對(Ci，Cj)中是否存在部分關聯(lián)。起先，Ci的對象以半徑值為ri分散在Ci(內部)和Ci(外部)中。換句話說，如果對象n屬于Ci，而對象n和CCi的距離比半徑值ri小的話，則對象n歸類于Ci(內部)。反之，對象n歸類于Ci(外部)。同理，Cj的對象分散在Cj(內部)和Cj(外部)中。

用于檢測簇對(Ci，Cj)是否存在部分關聯(lián)的標準在式(9)中進行了定義。在式(9)中，Wi是屬于Ci(外部)，但更接近于Cj的對象所組成的對象集。Wj是由屬于Cj(外部)，但更接近于Ci的對象所組成的對象集

3 實驗仿真與結果

為了驗證新方法的效果，我們將包含512×512個三維數(shù)據(jù)點的圖片進行分級，以證實MATS在多媒體數(shù)據(jù)分割方面的有效性。

該數(shù)據(jù)集包含512×512個三維(RGB)數(shù)據(jù)點(262144)。為減少計算量，我們首先使用局部框架方法將鄰域的數(shù)據(jù)點整合進L=10的對象中。經過局部框架方法處理后，對象數(shù)量為7623。然后我們用這些參數(shù):k=40，r=150，L=255/20來運行MATS將這些對象進行聚類。同時為了與傳統(tǒng)算法比較，從而驗證MATS算法的可靠性和效率，采用MATLAB7.0仿真環(huán)境，對圖(a)再次分別用FCM、基于蟻群算法的FCM(AAFCM)進行分割處理，F(xiàn)CM、AAFCM的初始參數(shù)m=3，單步最小變化為0.000 06，最大迭代次數(shù)90。整體分割效果如圖1所示。

通過比對發(fā)現(xiàn)，若采用MATS算法，大概需要時間5 s完成步驟1。候選簇的數(shù)量為36，然后用這個候選簇來運行步驟2。步驟2的運行時間大概為10 s，并得到了13個簇;若采用FCM和AAFCM算法，相同設備上算法運行時間分別是53.6 s和47.2 s。從時間上面來看，MATS有明顯提高。3種算法的迭代次數(shù)和收斂時間如表1所示。

圖1 分割效果比對

表1 3種算法迭代次數(shù)及收斂時間比較

為了進一步評價不同算法對圖片分割的差異性，對分割結果用如下評價指標:劃分系數(shù)vpc、劃分熵vpe、類間關聯(lián)度vxp作進一步的定量分析。當聚類結果最優(yōu)時，劃分系數(shù)值vpc應該最大，劃分熵值vpe應該最小，類間關聯(lián)度值vxp應該最小。比較結果如表2所示，可見AAFCM和MATS分割效果要明顯優(yōu)于FCM算法，且MATS分割算法有效性評價指標比AAFCM有了較大提高。

表2 3種算法評價指標比對

從視覺觀察3種分割結果，由于FCM聚類算法的局部收斂不足，明顯看出FCM算法分割的邊界模糊，尤其是在櫻桃和檸檬的分割中，效果較差。AAFCM算法和MATS算法分割結果比較，在葡萄和檸檬的分割中差異不大，但在櫻桃的分割中，由于MATS算法在步驟1中使用局部框架方法對數(shù)據(jù)進行了整合，并在步驟2中應用DB-參數(shù)和領域策略進行調整，使得分割結果保留了更多的細節(jié)信息。由此可見，MATS算法能克服傳統(tǒng)算法對初始參數(shù)的依賴，并在一定程度上避免陷入局部極值。

4 結論

聚類是已知的一種探究數(shù)據(jù)分析工具，它將數(shù)據(jù)分類到不同的簇中。傳統(tǒng)的聚類算法遇到很多難題，例如:(1)需要提前知道一些數(shù)據(jù)信息;(2)很難找到不規(guī)則簇;(3)聚類較大數(shù)據(jù)庫時效率低下等。本文提出的多主體領域系統(tǒng)(MATS)是在傳統(tǒng)聚類算法基礎上借鑒了蟻群優(yōu)化算法的思想，并進行了改進。該算法與FCM算法、AAFCM算法等傳統(tǒng)算法相比，在圖像分割速度和精度方面有一定程度的提高，并克服了傳統(tǒng)算法依賴初始參數(shù)、容易陷入局部極值的缺點。

［1］孫吉貴，劉杰，趙連宇.聚類算法研究［J］.軟件學報，2008，19 (1):48-61.

［2］Xu Rui.Survey of Clustering Algorithm［J］.IEEE Tran on Neural Networks，2005，16(3):645-678.

［3］李積英，黨建武.量子蟻群模糊聚類算法在圖像分割中的應用［J］.光電工程，2013，40(1):126-131.

［4］楊立才，趙莉娜，吳曉晴.基于蟻群算法的模糊C均值聚類醫(yī)學圖像分割［J］.山東大學學報(工學版)，2007，6(3):51 -54.

［5］白楊.蟻群算法在磁共振圖像分割中的應用［J］.中國醫(yī)學影像技術，2007，23(9):1402-1404.

［6］楊凱，蔣華偉.模糊C均值聚類圖像分割的改進遺傳算法研究［J］.計算機工程與應用，2009，45(33):179-183.

［7］張利彪.基于粒子群優(yōu)化算法的模糊C均值聚類［J］.吉林大學學報，2006，44(2):217-221.

［8］陳治亞.一種基于微粒群的模糊聚類算法［J］.計算機工程，2007，33(2):198-199.

［9］周濤，陸惠玲.數(shù)據(jù)挖掘中聚類算法研究進展［J］.計算機工程與應用，2012，48(12):102.

［10］楊海波，華驚宇，劉半藤.基于減聚類優(yōu)化算法的無線傳感網絡分簇路由協(xié)議研究［J］.傳感技術學報，2012，25(11):1603-1606.

［11］李成法，陳貴海，葉懋，等.一種基于非均勻分簇的無線傳感器網絡路由協(xié)議［J］.計算機學報，2007，30(1):27-36.

［12］趙福星，呂玉澤，鄭小梅，等.基于固定任務混頻的壽命相關載荷分布特性［J］.航空動力學報，2013，28(1):32-37.

［13］吳振華，尹志軍.基于優(yōu)化簇半徑的WSNs非均勻分簇路由［J］.計算機工程與設計，2010，31(15):3374-3378.

［14］曹永春，邵亞斌，田雙亮，等.一種基于分組遺傳算法的聚類新方法［J］.西華大學學報，2013，32(1):39-43.

A NEW Data Clustering Using M ulti-Agent Turf System*

LIU Yongli*
(Beijing Vocational Collegeof Financeand Commerce，Beijing 101101，China)

A new data clusteringmethod MATSwas proposed，which was inspired by Ant Colony Algorithm，In addition，there are some existence techniquewas also utilized in ourmethod，such as the density conceptand cluster validity index(DB-index).MATS can automatically find clusters，depending on a few parameters that are not directly related to the data set.The experiment results verified thatMATS is able to discover clusterwith varying shapes and it is effective when applied to image segmentation.

datamining;multi-agent turf system;data clustering;image segmentation

10.3969/j.issn.1005-9490.2014.01.036

TP311.13 文獻標識碼:A 文章編號:1005-9490(2014)01-0150-04

項目來源:國家自然科學基金項目(61272350)

2013-04-18修改日期:2013-06-23

EEACC:7210G

劉永立(1970-)，男，漢族，河北涿州市人，北京財貿職業(yè)學院講師，北京郵電大學軟件工程碩士，研究方向為模式識別、人工智能WEB軟件開發(fā)，cgyliu @126.com。