劉永立

(北京財(cái)貿(mào)職業(yè)學(xué)院信息物流系，北京101101)

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

劉永立*

(北京財(cái)貿(mào)職業(yè)學(xué)院信息物流系，北京101101)

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

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

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

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

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

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

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

聚類是一種常用的非監(jiān)督式分類技術(shù)，它基于相似性或相異性將輸入空間劃分到K區(qū)域中。分區(qū)或簇的數(shù)量事先可能知道，也可能不知道。輸入空間S由n個(gè)對(duì)象表示{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ī)則以及應(yīng)用這些規(guī)則的方法，可以將聚類算法分為傳統(tǒng)聚類算法和聚類新算法。在傳統(tǒng)聚類算法中，包括基于劃分的聚類、基于層次的聚類、基于密度的聚類等多種算法;在聚類新算法中，包括模糊聚類、基于流增量的聚類、基于生物智能的聚類等多種聚類算法。

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

步驟1:首先在隨機(jī)位點(diǎn)(對(duì)象)上初始化K主體，并使用靶向步驟來(lái)搜索入侵的對(duì)象。而協(xié)調(diào)步驟則用于解決爭(zhēng)奪同一對(duì)象的主體之間的沖突，因?yàn)橐粋€(gè)對(duì)象只能屬于一個(gè)主體。然后使用入侵步驟來(lái)幫助主體占據(jù)靶向?qū)ο?。最后，系統(tǒng)將沒(méi)有對(duì)象的主體清除掉。步驟1將一直重復(fù)直到所有對(duì)象都被占據(jù)。

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

2 MATS算法描述

2.1 靶向功能

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

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

2.2 協(xié)調(diào)步驟

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

2.3 入侵步驟

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

2.4 計(jì)算半徑

為防止主體重復(fù)性爭(zhēng)奪同一對(duì)象導(dǎo)致步驟1中無(wú)止境的競(jìng)爭(zhēng)，可以使用密度概念來(lái)建立領(lǐng)域原則。當(dāng)步驟1完成后，輸入空間D中所有的對(duì)象都由主體k劃分為k候選簇。由于主體隨機(jī)劃分領(lǐng)域，一個(gè)簇可能包含多于一個(gè)候選簇。因此如果候選簇屬于同一個(gè)簇的話，有必要找到一個(gè)原則來(lái)連接這些候選簇［10］。

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

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

這里I∈K。

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

2.5 應(yīng)用DB-參數(shù)

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

2.6 領(lǐng)域策略

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

在MATS中，完全關(guān)聯(lián)策略首先在簇對(duì)(Ci，Cj)中進(jìn)行檢驗(yàn)，因?yàn)楹蜻x簇Ci和Cj如果完全關(guān)聯(lián)的話不存在部分關(guān)聯(lián)策略。首先計(jì)算出簇對(duì)(Ci，Cj)的半徑值rij。見式(6):

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

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

hi是Ci的對(duì)象數(shù)

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

式(8)定義是由Tao CW提出的評(píng)估標(biāo)準(zhǔn)，用來(lái)評(píng)估簇對(duì)(Ci，Cj)之間是否存在完整關(guān)聯(lián)。在式(8)中，α是一個(gè)很重要的參數(shù)，它可以影響聚類的結(jié)果。盡管Tao CW將α設(shè)置為4，但在MATS中通過(guò)一些測(cè)試被設(shè)置為17。

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

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

3 實(shí)驗(yàn)仿真與結(jié)果

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

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

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

圖1 分割效果比對(duì)

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

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

表2 3種算法評(píng)價(jià)指標(biāo)比對(duì)

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

4 結(jié)論

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

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

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

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

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

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

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

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

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

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

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

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

［12］趙福星，呂玉澤，鄭小梅，等.基于固定任務(wù)混頻的壽命相關(guān)載荷分布特性［J］.航空動(dòng)力學(xué)報(bào)，2013，28(1):32-37.

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

［14］曹永春，邵亞斌，田雙亮，等.一種基于分組遺傳算法的聚類新方法［J］.西華大學(xué)學(xué)報(bào)，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 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1005-9490(2014)01-0150-04

項(xiàng)目來(lái)源:國(guó)家自然科學(xué)基金項(xiàng)目(61272350)

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

EEACC:7210G

劉永立(1970-)，男，漢族，河北涿州市人，北京財(cái)貿(mào)職業(yè)學(xué)院講師，北京郵電大學(xué)軟件工程碩士，研究方向?yàn)槟Ｊ阶R(shí)別、人工智能WEB軟件開發(fā)，cgyliu @126.com。