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

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

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

1 引 言

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

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

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

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

2 相關(guān)工作

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

2.1 有效性指標(biāo)

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

(1)

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

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

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

1.Fork=kmintokmax;

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

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

4.k=k+1;

5.End For

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

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

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

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

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

(2)

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

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

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

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

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

3.1 距離定義

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

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

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

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

(3)

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

(4)

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

(5)

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

(6)

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

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

(7)

其中r表示一組需要求解的類代表點r={r1,…,rk}.

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

(8)

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

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

3.3 染色體編碼與初始化

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

γ={γ1,…,γkmax}

(9)

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

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

(10)

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

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

(11)

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

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

3.4 進(jìn)化算子

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

(12)

其中maxg表示最大迭代次數(shù),g表示當(dāng)前代數(shù).當(dāng)產(chǎn)生子代種群后,使用非支配排序在父代種群和子代種群中挑選較優(yōu)的popsize個染色體作為下一代種群.該進(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)計算參數(shù)α;

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

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

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

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

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

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

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

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

4 實驗結(jié)果與分析

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

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

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

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

4.1 聚類結(jié)果展示

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

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

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

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

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

4.2 精度對比

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

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

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

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

表1 不同聚類算法的聚類數(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 運行時間對比

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

通過表2可以得出,由于MoMDVI使用代表點編碼,該算法通過縮小染色體的長度來降低算法的運行時間,所以比MOEACDM算法使用更少的運行時間.

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

5 結(jié)束語

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

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