多距離聚類(lèi)有效性指標(biāo)研究

劉 叢,陳倩倩,陳應(yīng)霞

1(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上海 200093) 2(華東師范大學(xué) 計(jì)算機(jī)科學(xué)與軟件工程學(xué)院,上海 200062)E-mail:Congl2014@usst.edu.cn

1 引 言

作為一種非監(jiān)督學(xué)習(xí)方法,聚類(lèi)已經(jīng)廣泛地應(yīng)用于圖像處理、數(shù)據(jù)挖掘、模式識(shí)別、計(jì)算機(jī)視覺(jué)等眾多領(lǐng)域.該方法使用某種規(guī)則將數(shù)據(jù)集劃分成一組互不重疊的子類(lèi),使得同一子類(lèi)中的元素具有極大的相似性,不同子類(lèi)中的元素具有極大的相異性[1].

近年來(lái)聚類(lèi)技術(shù)受到研究者的廣泛關(guān)注,大量的聚類(lèi)算法被相繼提出[1].可簡(jiǎn)單分為基于劃分的聚類(lèi)、基于密度的聚類(lèi)[2]、基于層次的聚類(lèi)、基于網(wǎng)格的聚類(lèi)以及基于模型的聚類(lèi).在眾多聚類(lèi)算法中,基于劃分的聚類(lèi)[3,4]研究最為廣泛.其使用類(lèi)內(nèi)緊湊度設(shè)計(jì)聚類(lèi)目標(biāo)函數(shù),并優(yōu)化該目標(biāo)以獲得最佳聚類(lèi)結(jié)果.但該類(lèi)算法含有以下幾個(gè)問(wèn)題:1)多數(shù)算法是基于歐氏距離而設(shè)計(jì),該距離在對(duì)超球型數(shù)據(jù)聚類(lèi)時(shí)效果比較好;但是對(duì)于非超球型數(shù)據(jù),效果并不理想;2)多數(shù)算法需要提前指定聚類(lèi)數(shù)目[5];3)通常使用基于梯度的優(yōu)化算法求解,對(duì)初始值比較敏感,容易陷入局部最優(yōu).

針對(duì)問(wèn)題1),使用不同的距離可以對(duì)非超球型數(shù)據(jù)聚類(lèi).基于密度的聚類(lèi)方法使用密度信息度量數(shù)據(jù)間的相似性.基于層次的聚類(lèi)使用類(lèi)間最大、類(lèi)間最小或平均距離作為數(shù)據(jù)的度量標(biāo)準(zhǔn).近年來(lái)許多新的距離如Path距離[6]、流行距離[7]、馬氏距離、切比雪夫距離、核距離[8]等被逐漸提出.但如何選擇合適的距離或者將多種距離融合在一起是目前面臨的一個(gè)挑戰(zhàn).將多種距離分別加權(quán)是一個(gè)很好的解決方法,但如何設(shè)置一個(gè)合適的權(quán)重非常困難.文獻(xiàn)[3,4]將加權(quán)思想引入目標(biāo)函數(shù)中,不同距離分配不同的權(quán)重,并根據(jù)不同數(shù)據(jù)進(jìn)行動(dòng)態(tài)變化,但該算法會(huì)導(dǎo)致數(shù)值比較小的距離分配較大的權(quán)重.針對(duì)問(wèn)題2),有效性指標(biāo)是常用的自動(dòng)檢測(cè)聚類(lèi)數(shù)目的方法.該方法使用類(lèi)內(nèi)緊湊度和類(lèi)間分離性來(lái)設(shè)計(jì)目標(biāo)函數(shù),通過(guò)尋找兩者之間的平衡來(lái)自動(dòng)獲得最佳聚類(lèi)數(shù)目.但該算法大都是基于歐氏距離而設(shè)計(jì),所以對(duì)非超球型數(shù)據(jù)效果不理想.文獻(xiàn)[8]使用核距離設(shè)計(jì)有效性指標(biāo)自動(dòng)檢測(cè)非超球型數(shù)據(jù)的聚類(lèi)數(shù)目,但核函數(shù)中的核參數(shù)需要手動(dòng)調(diào)節(jié),降低了算法的魯棒性.針對(duì)問(wèn)題3),進(jìn)化算法在求解全局最優(yōu)問(wèn)題上有非常好的優(yōu)勢(shì),該算法通過(guò)模擬自然界中的規(guī)律來(lái)獲得最優(yōu)解.近年來(lái)基于進(jìn)化算法的聚類(lèi)方法發(fā)展非常迅速[9,10].隨著研究的深入,基于多目標(biāo)進(jìn)化算法的聚類(lèi)方法也被相繼提出.MSFCA[11]利用全局模糊緊湊性和分散性作為兩個(gè)目標(biāo)函數(shù)設(shè)計(jì)聚類(lèi)算法并應(yīng)用在圖像分割中.MOCK[12]將類(lèi)內(nèi)緊湊度和類(lèi)間連通性作為兩個(gè)目標(biāo)函數(shù),并使用多目標(biāo)精英進(jìn)化策略算法PESA-II[13]對(duì)兩目標(biāo)同時(shí)優(yōu)化.MOEASSC[14]利用類(lèi)內(nèi)偏差和最小化權(quán)重熵與類(lèi)內(nèi)分散性作為兩個(gè)目標(biāo)函數(shù)得到穩(wěn)定性的聚類(lèi)結(jié)果.雖然基于進(jìn)化算法的聚類(lèi)方法越來(lái)越多的被提出,但現(xiàn)有的多目標(biāo)進(jìn)化算法大都是基于單一的距離度量,其中以歐氏距離最為常見(jiàn).該類(lèi)算法對(duì)處理超球型數(shù)據(jù)效果較好,但對(duì)非超球型數(shù)據(jù)效果不理想.

針對(duì)上述問(wèn)題,近期我們?cè)岢鲆环N基于多目標(biāo)多距離度量的聚類(lèi)數(shù)目自動(dòng)確定算法(MOEACDM)[15],該算法分別使用兩個(gè)距離設(shè)計(jì)兩個(gè)目標(biāo)函數(shù),并使用非支配排序遺傳算法(NSGA-II)對(duì)其優(yōu)化.但該算法由于使用基于標(biāo)簽的編碼方式,所以導(dǎo)致算法時(shí)間復(fù)雜度比較大.基于此,本文提出基于多目標(biāo)進(jìn)化算法的多距離聚類(lèi)有效性指標(biāo)算法(Multiple distance validity index based on a multiobjective evolutionary algorithm)(MoMDVI).首先使用基于代表點(diǎn)的編碼來(lái)設(shè)計(jì)染色體;其次分別基于兩個(gè)距離設(shè)計(jì)兩個(gè)聚類(lèi)目標(biāo)函數(shù);并設(shè)計(jì)了基于差分進(jìn)化和分布估計(jì)兩種子代種群產(chǎn)生策略;最后使用RMMEDA算法[16]對(duì)其同時(shí)優(yōu)化.實(shí)驗(yàn)證明,提出的算法獲得了比較好的效果.

2 相關(guān)工作

本節(jié)主要介紹聚類(lèi)有效性指標(biāo)和多目標(biāo)優(yōu)化的兩個(gè)相關(guān)工作.

2.1 有效性指標(biāo)

有效性指標(biāo)是常用的自動(dòng)檢測(cè)聚類(lèi)數(shù)目方法.常用的有效性指標(biāo)包括XB指標(biāo)[17]、DB指標(biāo)[18]等.其主要思想為通過(guò)尋找類(lèi)內(nèi)緊湊度和類(lèi)間分離性之間的平衡來(lái)尋找最佳聚類(lèi)數(shù)目.給定含有n個(gè)數(shù)據(jù)樣本的待分類(lèi)數(shù)據(jù)X={x1,…,xn}.使用XB指標(biāo)將該數(shù)據(jù)集劃分到k個(gè)類(lèi){C1,…,Ck}中.XB指標(biāo)可描述為公式(1)所示.

(1)

算法1.XB指標(biāo)確定聚類(lèi)數(shù)目

輸入:數(shù)據(jù)集X,聚類(lèi)數(shù)目的搜索空間{kmin,…,kmax}

輸出:最佳聚類(lèi)數(shù)目k*

1.Fork=kmintokmax;

2.{C1,…,Ck}=FCM(X,k);//使用FCM聚類(lèi)算法和當(dāng)前類(lèi)數(shù)目k對(duì)數(shù)據(jù)聚類(lèi),并獲得聚類(lèi)結(jié)果{C1,…,Ck}.

3.使用公式(1)計(jì)算當(dāng)前聚類(lèi)結(jié)果的XB值;

4.k=k+1;

5.End For

6.最佳聚類(lèi)數(shù)目k*=min(XB{kmin,…,kmax}).

該算法的缺陷有兩點(diǎn):①模型基于歐氏距離設(shè)計(jì),對(duì)超球型數(shù)據(jù)效果比較好,但對(duì)非超球型數(shù)據(jù)效果不理想.②使用不同的k值多次運(yùn)行FCM算法,增加了出現(xiàn)局部解的概率.

2.2 多目標(biāo)進(jìn)化算法

在現(xiàn)實(shí)生活中,很多工程問(wèn)題可以通過(guò)優(yōu)化多個(gè)目標(biāo)函數(shù)而獲得最優(yōu)決策,稱(chēng)之為多目標(biāo)優(yōu)化問(wèn)題.該問(wèn)題描述為公式(2)所示.

F(Θ)=(f1(Θ),…,fM(Θ))

(2)

其中Θ=(θ1,…,θh)表示一組h維的決策向量.F(Θ)表示含有M個(gè)子目標(biāo)值的目標(biāo)向量.在多目標(biāo)優(yōu)化問(wèn)題中,各個(gè)目標(biāo)往往是互相沖突的,因此不可能使所有目標(biāo)同時(shí)達(dá)到最優(yōu),而是獲得一組各個(gè)目標(biāo)值所折衷的解集,稱(chēng)之為Pareto front解集.

定義1.Pareto支配:如果Θ1支配Θ2,可記作Θ1Θ2,當(dāng)且僅當(dāng)對(duì)任意的l1∈{1,…,M},滿(mǎn)足fl1(Θ1)≤fl1(Θ2)并且存在一個(gè)l2∈{1,…,M},滿(mǎn)足fl2(Θ1)

定義2.Pareto front:Pareto最優(yōu)解集在函數(shù)空間上對(duì)應(yīng)的曲面,即為Pareto front,簡(jiǎn)稱(chēng)為PF.對(duì)于PF中的任意一個(gè)解Θ*,在當(dāng)前解集中不能找到另一個(gè)解Θ′,滿(mǎn)足Θ′Θ*.

3 基于多目標(biāo)進(jìn)化算法的多距離有效性指標(biāo)(MoMDVI)

本節(jié)主要介紹提出算法的主要細(xì)節(jié),包括距離定義、目標(biāo)函數(shù)設(shè)置、染色體編碼與初始化,進(jìn)化算子改進(jìn)及聚類(lèi)結(jié)果輸出.

3.1 距離定義

首先選擇距離空間.可選的距離有很多,包括歐氏距離、Path距離[6]、流行距離[7]、馬氏距離、切比雪夫距離、核距離等.理想狀態(tài)下,選擇的距離越多,其覆蓋的數(shù)據(jù)結(jié)構(gòu)也會(huì)越多.但過(guò)多的距離會(huì)導(dǎo)致過(guò)多的目標(biāo)函數(shù),也增加算法的運(yùn)行時(shí)間.所以在此使用兩種具有較大差異性的距離,分別為歐氏距離和Path距離.原因在于歐氏距離比較適合處理超球型數(shù)據(jù)集,而Path距離適合處理非超球型的數(shù)據(jù)集.

X={x1,…,xn}表示含有n個(gè)數(shù)據(jù)點(diǎn)的待分類(lèi)數(shù)據(jù)集.d(xj1,xj2)表示數(shù)據(jù)xj1和xj2的距離,滿(mǎn)足j1,j2∈{1,…,n}.d1(xj1,xj2)表示兩個(gè)數(shù)據(jù)的歐氏距離,d2(xj1,xj2)表示兩個(gè)數(shù)據(jù)的Path距離.

3.2 目標(biāo)函數(shù)設(shè)置

據(jù)上所述,傳統(tǒng)的有效性指標(biāo)在處理非超球型數(shù)據(jù)時(shí)效果并不理想,基于此本文分別使用兩個(gè)距離設(shè)計(jì)兩個(gè)有效性指標(biāo).該指標(biāo)考慮類(lèi)內(nèi)緊湊度和類(lèi)間分離性之間的平衡.首先考慮類(lèi)內(nèi)緊湊度.傳統(tǒng)有效性指標(biāo)通常通過(guò)數(shù)據(jù)點(diǎn)到類(lèi)中心之間的距離計(jì)算類(lèi)內(nèi)緊湊度.但在Path距離空間中,類(lèi)中心已失去了其物理意義.因此本文通過(guò)類(lèi)代表點(diǎn)來(lái)代替類(lèi)中心點(diǎn),類(lèi)代表點(diǎn)是類(lèi)中的一個(gè)實(shí)際樣本.當(dāng)分為k類(lèi)時(shí),類(lèi)內(nèi)緊湊度如公式(3)所示.

(3)

其中ri是X中的一個(gè)數(shù)據(jù),滿(mǎn)足ri∈X.在公式(3)中ri表示第i個(gè)類(lèi)的類(lèi)代表點(diǎn),并滿(mǎn)足i∈{1,…,k}.該緊湊度Com(k)隨著k值的增加呈減小趨勢(shì).其次考慮類(lèi)間分離性,在此使用任意兩個(gè)類(lèi)的類(lèi)代表點(diǎn)來(lái)設(shè)計(jì)類(lèi)間分離性.可表示為如公式(4)所示.

(4)

i1,i2∈{1,…,k}表示任意兩個(gè)類(lèi)的類(lèi)代表點(diǎn)的序號(hào).Sep(k)隨著k值的增加呈現(xiàn)增加的趨勢(shì).通過(guò)尋找Com(k)和Sep(k)之間的平衡來(lái)自動(dòng)檢測(cè)最佳聚類(lèi)數(shù)目.由于Com(k)和Sep(k)具有不同的數(shù)量級(jí),故分別對(duì)緊湊度和分離性進(jìn)行歸一化處理.首先歸一化類(lèi)內(nèi)緊湊度Com(k),當(dāng)k=1時(shí),Com(1)可取最大值;當(dāng)k=kmax時(shí)Com(kmax)可取最小值,其中kmax表示可接受的最大類(lèi)數(shù)目上限.極端條件下,當(dāng)k=n時(shí),Com(n)=0.歸一化后的類(lèi)內(nèi)緊湊度如公式(5)所示.

(5)

其次歸一化類(lèi)間分離性Sep(k),當(dāng)k=1時(shí),Sep(1)可取最小值;當(dāng)k=kmax時(shí),Sep(kmax)可取最大值.歸一化后的類(lèi)間分離性如公式(6)所示.

(6)

根據(jù)類(lèi)內(nèi)緊湊度和類(lèi)間分離性之間的平衡,建立新的有效性指標(biāo)如公式(7)所示:

F(k,r)=Comnor(k)+Sepnor(k)

(7)

其中r表示一組需要求解的類(lèi)代表點(diǎn)r={r1,…,rk}.

將公式(7)中的距離分別改寫(xiě)成歐氏距離和Path距離,則基于歐氏距離和Path距離的有效性指標(biāo)表示如公式(8)所示:

(8)

其中Comd1(k)和Comd2(k)分別表示基于歐氏距離和Path距離的類(lèi)內(nèi)緊湊度.Sepd1(k)和Sepd2(k)分別表示基于歐氏距離和Path距離的類(lèi)間分離性.Comd1(1),Comd2(1),Sepd1(kmax)和Sepd2(kmax)需要提前計(jì)算.對(duì)于Comd1(1)和Comd2(1),通過(guò)遍歷尋找分成1類(lèi)時(shí)的類(lèi)內(nèi)緊湊度.對(duì)于Sepd1(kmax)和Sepd2(kmax),可使用Kmedoids算法[19]將數(shù)據(jù)分為kmax類(lèi)來(lái)獲得.

接下來(lái)通過(guò)多目標(biāo)算法來(lái)求解兩個(gè)未知參數(shù)k和r={r1,…,rk}.

3.3 染色體編碼與初始化

本節(jié)重點(diǎn)介紹染色體編碼與初始種群生成.由于聚類(lèi)數(shù)目也是需求解的一個(gè)參數(shù),所以本節(jié)需要用到可變長(zhǎng)編碼方式.現(xiàn)有的編碼方式有很多,如基于標(biāo)簽的編碼、基于實(shí)數(shù)的編碼等.由于基于標(biāo)簽的編碼會(huì)產(chǎn)生較大的染色體長(zhǎng)度,繼而導(dǎo)致運(yùn)行時(shí)間較長(zhǎng),在此使用基于實(shí)數(shù)的編碼方式.如前所述,可接受的聚類(lèi)數(shù)目上限為kmax,故本節(jié)的染色體長(zhǎng)度為kmax.染色體可表示如公式(9)所示.

γ={γ1,…,γkmax}

(9)

其中γi表示第i個(gè)基因并滿(mǎn)足γi∈(0,1].由于最佳類(lèi)數(shù)目k*應(yīng)滿(mǎn)足k*≤kmax,所以對(duì)每個(gè)基因γi設(shè)置一個(gè)標(biāo)簽來(lái)判斷該基因是否能被選中作為類(lèi)代表點(diǎn).γi≤0.5表示該基因可被選中作為有效代表點(diǎn),并參與后續(xù)計(jì)算.γi>0.5表示該基因不能作為有效代表點(diǎn),直接將其舍棄.將所有γi≤0.5的基因挑選出,可獲得一組類(lèi)代表點(diǎn)基因,如公式(10)所示.

γv={γv1,…,γvk}

(10)

其中k表示有效代表點(diǎn)的數(shù)目,滿(mǎn)足k≤kmax.下一步將γvi映射成一組整數(shù),該整數(shù)表示類(lèi)代表點(diǎn)在整個(gè)數(shù)據(jù)中的序號(hào).該映射方式為公式(11)所示.

Iγvi=「γvi*n*2?

(11)

其中Iγvi∈{0,…,n}表示第i個(gè)類(lèi)代表點(diǎn)所在整個(gè)數(shù)據(jù)集中的序號(hào).再次解碼,則獲得k個(gè)代表點(diǎn)r={r1,…,rk},其中ri=xIγvi.

初始種群一般通過(guò)隨機(jī)生成.為了提高算法的收斂速度,本文使用一種預(yù)聚類(lèi)算法來(lái)產(chǎn)生該初始種群.據(jù)上所述,本文的染色體是一組表示類(lèi)代表點(diǎn)序號(hào)的實(shí)數(shù),該組實(shí)數(shù)解可通過(guò)Kmedoids算法獲得.在預(yù)聚類(lèi)中,需要將兩個(gè)距離和不同的聚類(lèi)數(shù)目加入其中.據(jù)此分析,初始種群由三種策略組成:(1)部分種群通過(guò)隨機(jī)生成;(2)部分種群通過(guò)使用Kmedoids算法使用歐氏距離和不同的聚類(lèi)數(shù)目生成;(3)部分種群使用Kmedoids算法使用Path距離和不同的聚類(lèi)數(shù)目生成.

3.4 進(jìn)化算子

本文使用RMMEDA算法作為多目標(biāo)算法優(yōu)化器.據(jù)文獻(xiàn)[20]所示,在迭代初期正則化信息并不明確,會(huì)導(dǎo)致建立的模型會(huì)略有偏差.基于此,本文使用差分進(jìn)化算子來(lái)彌補(bǔ)RMMEDA算子產(chǎn)生的缺陷.α表示差分進(jìn)化算子和RMMEDA算子產(chǎn)生的種群數(shù)目比例.popsize表示的種群規(guī)模.popsize*(1-α)個(gè)染色體由RMMEDA算子建模采樣獲得,popsize*α個(gè)染色體由差分進(jìn)化算子獲得.α隨著迭代次數(shù)的增加而發(fā)生變化,由于迭代前期正則化信息不明顯,過(guò)多的使用差分進(jìn)化算法來(lái)產(chǎn)生新的種群,迭代后期隨著正則化信息越來(lái)越明確,過(guò)多的使用RMMEDA算子產(chǎn)生新的種群.則α變化如公式(12)所示.

(12)

其中maxg表示最大迭代次數(shù),g表示當(dāng)前代數(shù).當(dāng)產(chǎn)生子代種群后,使用非支配排序在父代種群和子代種群中挑選較優(yōu)的popsize個(gè)染色體作為下一代種群.該進(jìn)化算子如算法2所示.

算法2.進(jìn)化算子

輸入:第g代種群pop(g)={γ1(g),…,γpopsize(g)}

輸出:第g+1代種群pop(g+1)={γ1(g+1),…,γpopsize(g+1)}

1.使用公式(12)計(jì)算參數(shù)α;

2.提取pop(g)正則化信息,并使用該信息進(jìn)行建模;

3.對(duì)上述模型進(jìn)行采樣,獲得popsize*(1-α)個(gè)子代染色體,

offpop(g)={off_γ1(g),…,off_γpopsize*(1-α)(g)};

4.使用差分進(jìn)化算法產(chǎn)生popsize*α個(gè)子代染色體

offpop(g)={off_γpopsize*(1-α)+1(g),…,off_γpopsize(g)};

5.使用非支配排序與擁擠距離從pop(g)∪offpop(g)中選擇popsize個(gè)染色體作為第g+1代種群.

3.5 輸出最佳聚類(lèi)結(jié)果

迭代結(jié)束后,可獲得最終的popsize個(gè)染色體.使用非支配排序,從所有染色體中選出Pareto front解集,也稱(chēng)為非支配解集.每個(gè)非支配解都被認(rèn)為是可行解,并且可使用公式(10)和(11)映射成一組類(lèi)代表點(diǎn).將數(shù)據(jù)集中的剩余數(shù)據(jù)劃分到與其最近的類(lèi)代表點(diǎn)所在的類(lèi)中.由于在尋找最近類(lèi)代表點(diǎn)時(shí)可使用歐氏距離和Path距離.所以針對(duì)每組類(lèi)代表點(diǎn),剩余數(shù)據(jù)都可獲得兩種歸類(lèi)方式.如果Pareto front中含有PFsize個(gè)非支配解集,則最終可獲得2*PFsize聚類(lèi)結(jié)果.而后使用人工選擇的方式挑選出最佳聚類(lèi)結(jié)果.

4 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證MoMDVI算法的有效性,本文使用8個(gè)測(cè)試數(shù)據(jù)展示本文算法的優(yōu)勢(shì).該數(shù)據(jù)包括3個(gè)超球型數(shù)據(jù)、3個(gè)非超球型數(shù)據(jù)及2個(gè)真實(shí)數(shù)據(jù).其中部分測(cè)試數(shù)據(jù)如圖1所示.

圖1 測(cè)試數(shù)據(jù)集Fig.1 Testing datasets

Data_separated、Data_connected1和Data_connected2為3個(gè)超球型數(shù)據(jù),每個(gè)數(shù)據(jù)含有若干超球型的類(lèi).這3個(gè)數(shù)據(jù)為人工生成數(shù)據(jù).Data_circle、Spiral和Flame[21]為非超球型數(shù)據(jù).其中第一個(gè)數(shù)據(jù)為人工生成數(shù)據(jù),后兩個(gè)為現(xiàn)有文獻(xiàn)中常用的非超球型數(shù)據(jù).Iris和Wine為兩個(gè)UCI真實(shí)數(shù)據(jù).

實(shí)驗(yàn)中,MoMDVI參數(shù)設(shè)置如下,為了降低運(yùn)行時(shí)間,將kmax設(shè)置為10.種群規(guī)模popsize設(shè)置為200,最大迭代次數(shù)maxg設(shè)置為100.為了定量的評(píng)估提出算法的性能,本實(shí)驗(yàn)采用最常用的Rand指標(biāo)[22]和F-measure指標(biāo)[23]對(duì)聚類(lèi)效果進(jìn)行評(píng)價(jià),計(jì)算指標(biāo)時(shí),每個(gè)數(shù)據(jù)的分類(lèi)標(biāo)記已知.在實(shí)驗(yàn)中兩個(gè)指標(biāo)簡(jiǎn)寫(xiě)為R和F,每個(gè)聚類(lèi)結(jié)果對(duì)應(yīng)的聚類(lèi)數(shù)目用clusternumber(CN)表示.

4.1 聚類(lèi)結(jié)果展示

本節(jié)使用Data_connected1和Data_circle兩個(gè)數(shù)據(jù)集展示使用MoMDVI算法產(chǎn)生的Pareto front和對(duì)應(yīng)的聚類(lèi)結(jié)果.由于每個(gè)非支配集需使用歐氏距離(ED)和Path距離(PD)對(duì)剩余數(shù)據(jù)歸類(lèi),所以每個(gè)非支配集對(duì)應(yīng)兩個(gè)聚類(lèi)結(jié)果.在此使用ED和PD區(qū)分.

圖2 Data_connected1的Pareto front集和對(duì)應(yīng)聚類(lèi)結(jié)果Fig.2 Pareto front and clustering results of Data_connected1

首先分析Data_connected1數(shù)據(jù).如圖2(a)所示,該數(shù)據(jù)得到5個(gè)Pareto非支配解,我們選擇3個(gè)點(diǎn)進(jìn)行聚類(lèi)結(jié)果分析,圖中已用橢圓標(biāo)記.圖2(b)、(c)和(d)分別對(duì)應(yīng)圖2(a)中被橢圓標(biāo)記的非支配解.由該圖可以看出使用歐氏距離對(duì)第2個(gè)標(biāo)記的非支配解解碼,可以獲得最佳聚類(lèi)效果.

其次分析Data_circle數(shù)據(jù),如圖3(a)所示.可得到9個(gè)Pareto點(diǎn),仍然選擇3個(gè)Pareto點(diǎn)分析.圖3(d)中的第2個(gè)圖為最佳的聚類(lèi)結(jié)果,可以看出Path距離更適應(yīng)于處理非超球型數(shù)據(jù)集.

圖3 Data_circle的Pareto front集和對(duì)應(yīng)聚類(lèi)結(jié)果Fig.3 Pareto front and clustering results of Data_circle

4.2 精度對(duì)比

為了驗(yàn)證MoMDVI算法的有效性,本節(jié)將其與現(xiàn)有的算法進(jìn)行比較.首先選擇兩種常用的有效性指標(biāo)XB和PBM[24]指標(biāo).由于本文算法是基于進(jìn)化算法而設(shè)計(jì),第三種對(duì)比算法為GCUK[25]算法,該算法使用遺傳算法對(duì)DB指標(biāo)進(jìn)行優(yōu)化.第四種對(duì)比方法為RAC-Kmeans算法[26].前三種對(duì)比算法都是基于歐氏距離設(shè)計(jì)的,第四種算法不需要考慮距離選擇.

對(duì)比算法的參數(shù)設(shè)置如下.對(duì)于XB、PBM、GCUK和MoMDVI,kmax設(shè)置為10.對(duì)于RAC-Kmeans,該參數(shù)設(shè)置為n.對(duì)于GCUK和MoMDVI,種群規(guī)模popsize設(shè)置為200,最大迭代次數(shù)maxg設(shè)置為100.

在對(duì)比過(guò)程中,使用的指標(biāo)為Rand和F-measure指標(biāo).每種算法分別運(yùn)行10次,Mean_R、Mean_F、Max_R和Max_F分別表示兩種指標(biāo)在10次運(yùn)行中獲得的平均值和最大值.CN表示獲得的最佳聚類(lèi)數(shù)目其中括號(hào)中表示10次運(yùn)行獲得該聚類(lèi)數(shù)目的次數(shù).

表1展示了5種算法分別對(duì)8個(gè)測(cè)試數(shù)據(jù)聚類(lèi)結(jié)果.通過(guò)該表可以得出,所有算法對(duì)于數(shù)據(jù)Data_separated都能獲得比較好的聚類(lèi),原因在于該數(shù)據(jù)比較簡(jiǎn)單.對(duì)于數(shù)據(jù)Data_connected1和Data_connected2,所有的算法都可以獲得相對(duì)較好的聚類(lèi)效果,但MoMDVI獲得的結(jié)果精度最高.通過(guò)這3個(gè)數(shù)據(jù)可知,MoMDVI處理超球型數(shù)據(jù)時(shí),可以獲得比較好的效果.對(duì)于非超球型數(shù)據(jù)Spiral、Data_circle和Flame,算法XB、PBM和GCUK都不能獲得好的效果,這表明歐氏距離對(duì)非超球型數(shù)據(jù)效果不理想.使用算法RAC-Kmeans和MoMDVI對(duì)數(shù)據(jù)Spiral和Data_circle聚類(lèi),可以獲得比較好的聚類(lèi)效果;但是對(duì)于數(shù)據(jù)Flame,MoMDVI算法比RAC-Kmeans獲得更好聚類(lèi)效果.這表明MoMDVI對(duì)非超球型數(shù)據(jù)聚類(lèi)也可以獲得比較好的聚類(lèi)效果.對(duì)于真實(shí)數(shù)據(jù)Iris和Wine數(shù)據(jù),所有算法聚類(lèi)結(jié)果相差不大,但MoMDVI算法在聚類(lèi)精度上更有優(yōu)勢(shì).因此通過(guò)該實(shí)驗(yàn)可以得出基于兩種距離設(shè)計(jì)的MoMDVI算法對(duì)球型數(shù)據(jù)和非球型都表現(xiàn)出比較好的聚類(lèi)效果.

表1 不同聚類(lèi)算法的聚類(lèi)數(shù)目(CN)及準(zhǔn)確度(Mean_R/Max_R,Mean_F/Max_F)的比較Table 1 Comparison of the CN、Mean_R/Max_R and Mean_F/Max_F by different clustering algorithms

4.3 運(yùn)行時(shí)間對(duì)比

由于MoMDVI為解決MOEACDM[15]具有較高的時(shí)間復(fù)雜度而設(shè)計(jì).本節(jié)對(duì)比兩種算法的運(yùn)行時(shí)間.兩種算法使用相同的種群規(guī)模(popsize=200)和相同的迭代次數(shù)(maxg=200).使用的運(yùn)行軟件為Matlab2014b,使用的電腦配置為2.5G赫茲CPU,4G內(nèi)存.表2為兩種算法在4個(gè)數(shù)據(jù)集上運(yùn)行使用時(shí)間.

通過(guò)表2可以得出,由于MoMDVI使用代表點(diǎn)編碼,該算法通過(guò)縮小染色體的長(zhǎng)度來(lái)降低算法的運(yùn)行時(shí)間,所以比MOEACDM算法使用更少的運(yùn)行時(shí)間.

表2 兩種算法使用相同參數(shù)獲得運(yùn)行時(shí)間Table 2 Comparison computation time(s)by using two methods with the same(popsize,maxg)

5 結(jié)束語(yǔ)

針對(duì)傳統(tǒng)有效性指標(biāo)僅考慮歐氏距離的缺陷,本文提出了一種基于多距離的有效性指標(biāo)(MoMDVI)來(lái)自動(dòng)檢測(cè)最佳聚類(lèi)數(shù)目.該算法使用歐氏距離和Path距離分別設(shè)計(jì)有效性指標(biāo)來(lái)自動(dòng)檢測(cè)聚類(lèi)數(shù)目,并使用多目標(biāo)進(jìn)化算法對(duì)兩種有效性指標(biāo)進(jìn)行并行優(yōu)化.由于在Path距離中,類(lèi)中心點(diǎn)已失去其意義,本文使用類(lèi)代表點(diǎn)代替類(lèi)中心來(lái)設(shè)計(jì)有效性指標(biāo).每個(gè)染色體由一系列實(shí)數(shù)組成,部分實(shí)數(shù)可轉(zhuǎn)化為類(lèi)代表點(diǎn)序號(hào)的形式.在設(shè)計(jì)進(jìn)化算子時(shí),將差分進(jìn)化算子與RMMEDA進(jìn)化算子融合,使其更快收斂.提出的算法既能自動(dòng)檢測(cè)超球型數(shù)據(jù)聚類(lèi)數(shù)目,也可以自動(dòng)檢測(cè)非超球型數(shù)據(jù)聚類(lèi)數(shù)目.

提出的算法還有兩個(gè)問(wèn)題需要改進(jìn).第一,本文算法只使用歐氏距離和Path距離作為兩種距離進(jìn)行分析,接下來(lái)可以考慮將更多的距離加入到算法模型中.第二,如何在最終Pareto非支配集中自動(dòng)選擇最佳解也是下一步需要考慮的工作.