基于改進BPSO的聚類選擇性集成

畢 凱，王曉丹，邢雅瓊（空軍工程大學(xué)防空反導(dǎo)學(xué)院，陜西　西安710051）

基于改進BPSO的聚類選擇性集成

畢 凱，王曉丹，邢雅瓊
（空軍工程大學(xué)防空反導(dǎo)學(xué)院，陜西西安710051）

首先針對離散二進制粒子群（binary particle swarm optimization，BPS O）容易陷入局部收斂的問題，提出一種改進的BPS O算法。在分析高斯密度函數(shù)對尺度敏感性的基礎(chǔ)上，利用粒子群與全局最優(yōu)粒子的一致性動態(tài)調(diào)節(jié)尺度參數(shù)，并利用密度函數(shù)對稱區(qū)間的定積分確定全局最優(yōu)粒子的變異概率。而后將聚類的選擇性集成抽象為組合優(yōu)化問題，利用聚類成員有效性和差異性的加權(quán)組合定義適應(yīng)度并以改進BPS O的進化過程實現(xiàn)聚類的選擇性集成。最后基于標(biāo)準(zhǔn)數(shù)據(jù)集和圖像數(shù)據(jù)集驗證算法的有效性。

聚類選擇性集成；離散二進制粒子群；高斯密度函數(shù)；圖像分割

網(wǎng)址：w w w.sys-ele.co m

0 引 言

聚類集成是指無監(jiān)督情況下對同一數(shù)據(jù)集多種不同聚類結(jié)果的決策級融合。由于具有魯棒性、新穎性、穩(wěn)定性、并行性以及可擴展性等優(yōu)點［1］，使其一經(jīng)提出便受到普遍關(guān)注，已成為當(dāng)前聚類研究的重要方向并成功應(yīng)用于圖像分 割［2］、文本分類［3］、特征提?。?］、生物工程［5］等諸多領(lǐng)域。

文獻［6］于2002年首次提出選擇性集成學(xué)習(xí)的概念，并通過理論分析和實驗表明具有較好分類性能和較大差異性的基分類器更有利于構(gòu)造高性能的強分類器。與有監(jiān)督集成學(xué)習(xí)類似，聚類的選擇性集成已被提出并廣泛研究。聚類法和排序法是當(dāng)前常用的兩種聚類選擇性集成方法［7］。聚類法［7-8］首先以差異性作為劃分依據(jù)，通過聚類算法使差異性較小的聚類成員劃為同類，而差異性較大的聚類成員分為異類，而后在各類別中選擇有效性最高的聚類成員用于集成。排序法［9-10］則利用線性組合將有效性和差異性統(tǒng)一為適應(yīng)度，并依據(jù)適應(yīng)度的大小對全體聚類成員進行排序，而后利用適應(yīng)度最高的聚類成員用于集成。

需要指出的是，上述聚類選擇性集成方法雖然取得了一定研究進展，但仍存在以下問題：①聚類法中聚類算法的選擇。聚類算法通?；谔囟ǖ臄?shù)據(jù)結(jié)構(gòu)假設(shè)，當(dāng)真實數(shù)據(jù)與假設(shè)相符時能夠獲得良好的劃分結(jié)果，當(dāng)不符時劃分結(jié)果與實際相差甚遠。全體聚類成員的空間結(jié)構(gòu)通常是未知的，這將使聚類算法的選擇具有較大盲目性；②排序法中利用任一聚類成員與其余全體聚類成員間的平均差異性描述差異性，但選擇出聚類集合的整體差異性利用該描述存在一定誤差；③無論是聚類法還是排序法都需要確定選擇規(guī)模，而選擇規(guī)模通常與實際問題、全體集成規(guī)模和聚類成員的質(zhì)量等問題有關(guān)，因而人為設(shè)定選擇規(guī)模稍欠合理。

為解決上述問題，本文將聚類的選擇過程看作是組合優(yōu)化問題，提出一種基于離散二進制粒子群（binary particle swarm optimization，BPS O）的聚類選擇性集成方法。首先為避免陷入局部最優(yōu)解，給出一種基于改進高斯變異的離散粒子群進化算法，而后利用聚類成員有效性和差異性的加權(quán)組合定義適應(yīng)度，并基于改進離散粒子群的進化過程實現(xiàn)聚類的選擇性集成。

1 改進的BPSO

1.1 BPSO

粒子群優(yōu)化算法（particle swarm optimization，PSO）［11］是Kennedy和Ebethart于1995年提出的一種基于群體智能的隨機尋優(yōu)算法。通過對鳥群社會行為進行模擬，在多維解空間中利用一定規(guī)模的可行解構(gòu)成粒子群，并通過粒子間的相互作用，對解空間進行智能搜索，從而發(fā)現(xiàn)最優(yōu)解。由于具有原理簡單、易于實現(xiàn)、收斂速度快、群體搜索、協(xié)同搜索以及通用性強等優(yōu)點，近年來相關(guān)研究發(fā)展迅速。

設(shè)搜索空間為d維，群體中第i個粒子的位置為Xi= （xi1，xi2，…，xid），速度為Vi=（vi1，vi2，…，vid），它經(jīng)歷過的最佳位置為Pi=（pi1，pi2，…，pid），群體經(jīng)歷過的最佳位置為Pgbest=（pg1，pg2，…，pgd）。粒子分別按式（1）和式（2）更新自己的位置和速度：

式中，ω為慣性權(quán)重，較大時適于對解空間進行較大范圍搜索，較小時適于進行小范圍搜索；k為迭代次數(shù)；r1，r2為（0，1）之間的隨機數(shù)；c1，c2為加速因子，通常取2。每一維的位置和速度都被限制在一定的范圍內(nèi)，粒子飛行過程中如果位置和速度超過邊界范圍則取邊界值。Pi和Pgbest不斷更新，最后輸出的Pgbest就是全局最優(yōu)解。

BPSO是PSO的離散二進制版本，于1997年由Kennedy 和Ebethart提出［12］，開啟了PS O算法在離散問題領(lǐng)域的應(yīng)用。在二進制編碼中，BPS O限制粒子位置只能取0或1，需要指出的是，二進制粒子群算法中速度向量不再是位置變化，而僅表示概率，即每一維分量的取值為1或0的概率，引入模糊函數(shù)sigmoid：

利用式（4）替代式（2），有

式中，rand為［0，1］間的隨機數(shù)，通過分析可以發(fā)現(xiàn)當(dāng)最大飛行速度大于10時，sig（v）將趨近于0，為防止該函數(shù)趨近于0，可將速度限制于［-4，4］區(qū)間內(nèi)［13］。

1.2 改進BPSO

為避免BPS O可能陷入局部最優(yōu)，出現(xiàn)所謂的早熟現(xiàn)象，文獻［14］通過自適應(yīng)擾動慣性因子來增強粒子群跳出局部最優(yōu)的能力，文獻［15］提出通過增加粒子群的多樣性，以達到擺脫群體陷入局部極值的可能。需要指出的是，上述文獻均基于連續(xù)PS O算法易陷入局部極值的問題提出，而離散PS O的進化過程與連續(xù)PS O存在較大區(qū)別［16］。

分析BPS O的進化過程可以看到，粒子通過跟蹤個體極值Pi和群體極值Pgbest來更新自己，當(dāng)某一粒子發(fā)現(xiàn)一個局部最優(yōu)值，則其他粒子將迅速向其靠攏，此時粒子群可能陷入局部最優(yōu)。因而可以考慮通過對Pgbest進行適當(dāng)擾動以達到跳出局部極值并提高算法精度的目的［17］。

高斯變異是標(biāo)準(zhǔn)進化規(guī)劃中常用的變異算子［18］，標(biāo)準(zhǔn)高斯分布密度為N（0，1），期望為0，方差為1。對于個體X=（x1，x2，…，xd），經(jīng)過變異后得到一個新的個體X′= （x′1，x′2，…，x′d），其變異過程可描述為

考慮高斯概率密度函數(shù)的一般形式

式中，μ∈R，σ∈R+。密度函數(shù)p（x）的圖形如圖1所示。觀察可知，μ決定了密度函數(shù)的位置，σ的取值對高斯密度函數(shù)的形狀具有重要意義。σ越小函數(shù)圖像越收攏，x以較高概率分布于x=μ附近，σ越大則函數(shù)圖像越發(fā)散，x的分布則相對發(fā)散。不考慮密度函數(shù)的位置，本文令μ=0。

圖1 高斯概率密度函數(shù)

由式（6）可知，x在全體實數(shù)范圍內(nèi)取值，而在BPS O中變異本質(zhì)上是以一定的概率取反，為實現(xiàn)變異進行如下討論。

令F（x）表示變異概率

分析可知，對于任意的x∈（0，+∞），F(xiàn)（x）∈（0，1）。對于確定的x，F(xiàn)（x）為σ的單調(diào)減函數(shù)，當(dāng)σ→0時，F(xiàn)（x）→1，當(dāng)σ→+∞時，F(xiàn)（x）→0?？紤]到BPS O進化過程的不同變異需要，這里定義動態(tài)的σ。

式中，λ為縮放系數(shù)，用于控制σ（k）的變化范圍；ξ為略小于1的數(shù)，xij==pgj用于判斷二者是否相等，若相等取值為1，否則取值為0。分析式（8）可知，在進化的初始階段，k值較小且各粒子與全局最優(yōu)解的一致性較弱，因而σ（k）取值較小使Pgbest具有較高的變異概率，進而使種群可在較曠闊空間內(nèi)進行搜索。隨著進化過程不斷進行，1-ξk取值趨近于1，各粒子不斷向全局最優(yōu)解靠攏，σ（k）取值不斷增加，使得變異概率降低，避免過度變異而錯過全局最優(yōu)解?；谏鲜龇治霾⒖际剑?），則全局最優(yōu)解Pgbest的變異操作可表示為

此外，考慮到慣性權(quán)重ω對進化過程的非線性影響，采用文獻［19］的策略，采用非線性方法自適應(yīng)調(diào)整慣性權(quán)重ω。具體公式為

綜上改進的BPS O算法流程可表示如下。

算法1 改進的BPS O

輸入 最大迭代次數(shù)km ax；粒子群規(guī)模T；收斂閾值d；加速因子c1、c2；慣性權(quán)重ωm ax，ωmin；變異次數(shù)n；縮放系數(shù)λ；積分區(qū)間x。

輸出 最優(yōu)解Pgbest。

步驟1 隨機初始化速度和各粒子位置；

步驟2 計算適應(yīng)度，標(biāo)記各粒子為經(jīng)歷過最佳位置Pi，將適應(yīng)度最高粒子標(biāo)記為全局最佳位置Pgbest；

步驟3 判斷算法是否滿足收斂條件（最大適應(yīng)度或最大迭代次數(shù)要求），若滿足轉(zhuǎn)向步驟7；

步驟4 利用式（10）計算慣性權(quán)重，利用式（1）更新粒子飛行速度，利用式（3）、式（4）更新粒子位置；

步驟5 計算各粒子適應(yīng)度，若Pi和Pgbest優(yōu)于歷史最佳位置，則更新Pi和Pgbest；

步驟6 利用式（7）～式（9）對Pgbest進行變異，并計算適應(yīng)度，若優(yōu)于則更新Pgbest，并轉(zhuǎn)向步驟3，否則直接轉(zhuǎn)向步驟3；

步驟7 輸出算法最優(yōu)解Pgbest。

2 基于改進BPSO的聚類選擇性集成

2.1 聚類選擇性集成的問題描述

聚類集成通?？擅枋鰹椋涸O(shè)數(shù)據(jù)集合Y=｛y1，y2，…，yN｝，N為數(shù)據(jù)規(guī)模，Π=｛π1，π2，…，πM｝為數(shù)據(jù)集Y上M個獨立的聚類結(jié)果，其中πi=｛ci1，ci2，…，ciki｝為聚類成員，ki為類別數(shù)。對于任意y，若y∈cij則表示該數(shù)據(jù)點在第i個聚類成員中類別為j。聚類集成本質(zhì)上是利用合理的方法對M個獨立聚類結(jié)果的一致性分析和決策。

聚類成員有效性和差異性對于集成結(jié)果具有十分重要的影響。有效性用于保障聚類成員的基本正確率，全集成結(jié)果、聚類成員的全部結(jié)果等集成趨勢通常被作為有效性評價的客觀標(biāo)準(zhǔn)［7 9］。此外還有方法通過分析聚類結(jié)果與數(shù)據(jù)集合的空間結(jié)構(gòu)相似性確定其有效性，如輪廓指標(biāo)（Silhouette index）、Dunn指標(biāo)、Davies-Bouldin指標(biāo)、Gap統(tǒng)計等［10］。差異性其目的在于使各聚類成員的錯誤相互獨立，通過集成使正確劃分不斷積累而錯誤劃分相互抵消。調(diào)整的蘭德指數(shù)（adjusted rand index，A RI）、規(guī)范化互信息（normalized mutualinformation，N MI）、信息熵（entropy）、條件熵（conditional entropy）、Double Fault Measure、Coincident Fai lure Diversity、Measurement of Inter-Rater Agreement等通常被用于描述聚類成員間差異性。

有效的聚類選擇性集成通?；谟行院筒町愋缘木C合考慮，如文獻［8］利用重采樣技術(shù)（resampling technique，R T）通過對比聚類算法在整體數(shù)據(jù)集和隨機數(shù)據(jù)子集的分類一致性確定該聚類成員的有效性，利用Rand index計算任意聚類成員與其他聚類成員的差異性之和，文獻［9］中利用N MI和A RI評價聚類成員的有效性，同時利用N MI計算任意兩聚類成員間的差異性，文獻［10］在對多種內(nèi)部評價方法進行分析的基礎(chǔ)上給出了一種組合有效性評價方法，并將其與基于Jaccard的差異性方法聯(lián)合選擇聚類成員。

2.2 基于改進BPSO的聚類選擇性集成

聚類的選擇性集成過程可抽象為0-1組合優(yōu)化問題，1表示聚類成員被選擇，0表示聚類成員未被選擇。對于規(guī)模為M的聚類集成，其選擇問題的規(guī)模為2M，雖然利用分支定界法能夠求得全局最優(yōu)組合，但算法復(fù)雜度較高，難以應(yīng)用于實際問題。這里利用算法1所述改進的BPSO算法，通過離散粒子群進化過程實現(xiàn)聚類成員的選擇。

如第2.1節(jié)所述，有效性和差異性對集成結(jié)果具有重要影響。對于聚類算法，由于缺乏必要的先驗信息，通常難以準(zhǔn)確評價其有效性。這里令π*表示全體聚類成員的集成結(jié)果，假設(shè)π*能夠表示更為合理的數(shù)據(jù)類別劃分，考慮利用π*作為聚類有效性評價的參考劃分，利用N MI度量任意聚類成員πi與π*間一致性，則有效性可描述為

其值越大表示πi與π*的一致性越高，即πi的有效性越高，其值越小則表示πi的有效性越低。同樣考慮N MI描述選擇出聚類成員子集的整體差異性

Π′為規(guī)模為M′的聚類成員子集，πi，πj∈Π′。與有效性描述相反，D（Π′）其值越小表示聚類成員子集的差異性越大，反之則差異性越小。通過對聚類有效性和差異性的加權(quán)線性組合，以獲取單一目標(biāo)的集成適應(yīng)度函數(shù)，其表示為

式中，α為有效性和差異性的權(quán)重調(diào)節(jié)因子，用于平均二者的影響，文獻［8］指出其值取0.5更有利于獲得較好選擇集成結(jié)果。

在BPSO算法中，初始種群通常隨機產(chǎn)生，因此初始的最優(yōu)粒子也是隨機的，這可能使得它一開始就嚴重偏離最優(yōu)粒子，延緩進化速度。如果粒子群一開始就掌握了一個較優(yōu)解，使得粒子群一開始就朝著比較合理的方向進行搜索，這樣必然會縮短粒子群的進化過程。因此在粒子群的初始化階段，可利用式（11）計算全體聚類成員的有效性，將有效性最高的m個聚類成員標(biāo)記為選擇，以保證初始進化的較合理方向。綜上基于改進BPSO的聚類選擇性集成過程可描述如下。

算法2 基于改進BPS O的聚類選擇集成

輸入 數(shù)據(jù)集合、聚類成員生成方法G、集成方法E、集成規(guī)模M、平衡因子α、初始選擇規(guī)模m及算法1相關(guān)參數(shù)。

輸出 選擇性集成結(jié)果。

步驟1 利用方法G生成規(guī)模為M的全體聚類成員πi，利用集成方法E（如文獻［1］中基于相似分割的聚類算法（cluster-based similarity partitioning algorithm，CSPA）、變換圖算法（meta-clustering algorithm，M CL A）、超圖劃分算法（hypergraphpartitioning algorithm，H GPA）等求取全集成結(jié)果π*；

步驟2 利用式（11）計算全體聚類成員πi的有效性；

步驟3 標(biāo)記有效性最高的前m個聚類成員位置為1，并初始化全局最優(yōu)解Pgbest，隨機初始化T-1個粒子；

步驟4 利用算法1求解全局最優(yōu)解Pgbest；

步驟5 選擇Pgbest所對應(yīng)聚類成員，利用集成方法E進行求解，獲得選擇性集成結(jié)果。

3 實驗與驗證

為驗證本文所提聚類選擇集成方法的有效性，分別在標(biāo)準(zhǔn)數(shù)據(jù)集和圖像數(shù)據(jù)集進行實驗。

3.1 標(biāo)準(zhǔn)數(shù)據(jù)集實驗

實驗數(shù)據(jù)為11組U CI標(biāo)準(zhǔn)數(shù)據(jù)集，其詳細描述如表1所示。

表1 實驗數(shù)據(jù)描述

通過對譜聚類（nystrm spectral clustering，NSC）算法進行采樣和尺度參數(shù)擾動生成差異性聚類成員，采樣規(guī)模為50，尺度參數(shù)擾動范圍為［0.1，0.6］。改進BPSO中令最大迭代次數(shù)為100，初始速度為0，群體規(guī)模為30，加速因子均取2，慣性權(quán)重分別為0.9和0.4，變異次數(shù)為30，縮放系數(shù)為10，積分區(qū)間為1，初始選擇規(guī)模為20。集成算法采用文獻［1］中描述的CSPA和M CLA，全集成規(guī)模為50，平衡因子α為0.5。以集成結(jié)果與標(biāo)準(zhǔn)類標(biāo)簽的F M（Fowlkes Mal lows，F(xiàn) M）指標(biāo)作為評價標(biāo)準(zhǔn)

對于兩劃分π1，π2，a表示既屬于π1中同一聚類，又屬于π2中同一聚類的樣本對個數(shù)，b表示屬于π1中同一聚類，但不屬于π2中同一聚類的樣本對個數(shù)，c表示不屬于π1中同一聚類，但屬于π2中同一聚類的樣本對個數(shù)。F M指標(biāo)越大，表明兩劃分結(jié)果越接近，反之亦然。

實驗1 首先就改進BPSO算法的收斂性和有效性進行分析，實驗數(shù)據(jù)包括Iris、Ecol i、Sonar、Ionosphere 4個數(shù)據(jù)集，對比算法包括BPSO、混沌BPSO1（chaotic BPSO，CBPSO1）和CBPSO2［20］，實驗結(jié)果如圖2所示。

圖2 多種離散粒子群算法在4個數(shù)據(jù)集上適應(yīng)度與迭代次數(shù)關(guān)系

分析圖2可以看到，在4個標(biāo)準(zhǔn)數(shù)據(jù)集上，與BPSO、CBPSO1和CBPSO2相比，本文所提改進的離散粒子群算法—gBPSO能夠發(fā)現(xiàn)更優(yōu)的Pgbest；收斂速度方面，BPSO與CBPSO1相當(dāng)，gBPSO次優(yōu)，CBPSO2收斂速度最快，但可以看到CBPSO2較快的收斂速度是由于其陷入局部最優(yōu)解無法跳出而得到的。綜上可見本文所提方法更能夠兼顧收斂性和有效性。

實驗2 為驗證本文所提聚類選擇性集成方法的有效性，在表1所示標(biāo)準(zhǔn)數(shù)據(jù)集上進行驗證，考慮到M C L A較高的有效性，實驗中均以M C L A全集成結(jié)果作為有效性參考，利用CSP A和M C L A的全集成和選擇性集成結(jié)果分別如表2和表3所示，由于CSP A僅適用于規(guī)模小于1 000的數(shù)據(jù)集，因而表2未給出Seg ment數(shù)據(jù)集實驗結(jié)果。表2和表3中全集成方法（all cluster ensemble，A E）為全集成結(jié)果，選擇聚類集成算法（select cluster ensemble，SCE）為文獻［7］中利用集成適應(yīng)度排序的聚類選擇性集成，基于協(xié)方差的聚類集成算法（cluster select ensemble based on covariance，CSE V）為文獻［22］中基于協(xié)方差矩陣的聚類選擇性集成，BPSO、CBPSO1、CBPSO2、gBPSO分別為利用不同的粒子群算法進行選擇性集成的結(jié)果，選擇規(guī)模均為20，表中數(shù)據(jù)均為20次獨立重復(fù)實驗的均值，最優(yōu)選擇集成結(jié)果被加粗。

表2 標(biāo)準(zhǔn)數(shù)據(jù)集聚類選擇性集成結(jié)果（CSPA）

表3 標(biāo)準(zhǔn)數(shù)據(jù)集聚類選擇性集成結(jié)果（M CL A）

分析上述實驗結(jié)果，首先將選擇性集成結(jié)果與全集成結(jié)果進行對比可以看到，SC E、CSR V、BPS O、CBPS O1、CBPS O2、gBPS O 6種選擇性集成方法分別在6/6、6/6、6/7、7/ 5、6/7、7/9個數(shù)據(jù)集上取得優(yōu)于全集成的聚類結(jié)果，表明對聚類成員的適當(dāng)選擇是進一步提高聚類集成精度的有效途徑。進一步，將本文所提方法與其他5種選擇方法進行對比可以看到，gBPS O在5/4個數(shù)據(jù)集上取得最優(yōu)聚類選擇集成結(jié)果，在2/2個數(shù)據(jù)集上取得次優(yōu)聚類選擇集成結(jié)果，優(yōu)于其他選擇性集成方法。

綜上，基于標(biāo)準(zhǔn)數(shù)據(jù)集的實驗結(jié)果顯示本文所提gBPSO不僅具有較快的收斂速度和全局尋優(yōu)性能，同時將其應(yīng)用與聚類的選擇性集成也取得了較高的分類正確性。

3.2 圖像數(shù)據(jù)集實驗

為進一步驗證本文所提選擇性集成方法的正確性，在圖像數(shù)據(jù)集上進行分割實驗，實驗結(jié)果如圖3所示。

圖3 分割實驗圖像

實驗3 合成紋理圖像分割，實驗圖像如圖3（a）所示，為一5類合成紋理圖像，圖像大小為256×256。利用11×11中值濾波器、2種高斯差分（difference of Gaussian，D O G）濾波器和6種高斯偏移差分（difference of offset Gaussian，D O O G）濾波器（見圖4）共提取9維特征信息。

圖4 D O G和D O O G濾波器示意圖

利用N SC、N SC+M C L A、N SC+SC E+M C L A（選擇規(guī)模為20）、N SC+gPS O+M C L A進行分割，上述集成算法中利用隨機采樣和擾動尺度參數(shù)生成聚類成員，采樣規(guī)模為100，尺度擾動范圍［0.1，0.6］，全集成規(guī)模為30，其他參數(shù)設(shè)置與3.1節(jié)相同，圖像分割結(jié)果如圖5所示。

圖5 紋理圖像分割結(jié)果

在圖5中將利用改進粒子群算法進行聚類選擇性集成的分割結(jié)果（如圖5（d）所示）與其他方法的分割結(jié)果進行對比可以看到，選擇后的分割結(jié)果不僅能夠一定程度上消除分類誤差（如圖中下方區(qū)域），而且能夠更好描述分割的邊界區(qū)域。

實驗4 SA R圖像分割，實驗圖像如圖3（b）所示，為美國華盛頓特區(qū)波托馬克河的局部描述，圖像大小為150× 150，圖中主要地物包括河流、植被以及人工建筑。對該圖像提取基于3層非下采樣小波分解的10維能量特征組成特征空間［21］，為更好描述圖像信息，觀測窗口為7×7。這里固定譜聚類尺度參數(shù)為0.1，通過差異性采樣生成不同的分類結(jié)果，采樣規(guī)模為100，全集成規(guī)模為30，圖像分割結(jié)果如圖6所示。

圖6 SAR圖像分割結(jié)果

分析圖6，首先將3幅集成分割圖像（b）（c）（d）與單聚類分割圖像（a）進行對比，可以看到集成分割能夠?qū)⒑影度斯そㄖ飬^(qū)分開來，究其原因，采樣數(shù)據(jù)點的質(zhì)量對于N SC聚類結(jié)果具有重要影響，當(dāng)對圖像中人工建筑物的采樣不足時，可能造成對其的錯分，將多次基于隨機采樣的分類結(jié)果進行集成，能夠有效避免單次采樣的不足，具有更好的圖像分類能力；進一步對比3幅集成圖像可以看到，圖6（c）在河流中心島嶼的分類中存在明顯的雜斑，且對于河岸建筑的分類較為粗糙，整體效果劣于圖6（b）和圖6（d），而圖6（d）與圖6（b）對于河岸的分類效果相當(dāng)，但在河流中心島嶼中橋梁和島邊緣的錯分上，圖6（d）明顯優(yōu)于圖6（b），可見本文方法對于圖3（b）具有更好的分割效果。

4 結(jié) 論

本文首先針對BPS O易于陷入局部極值，利用高斯密度函數(shù)上對稱區(qū)間的定積分表示變異概率并通過擾動全局最優(yōu)粒子以實現(xiàn)跳出矩陣最優(yōu)的目的?？紤]到高斯密度函數(shù)的尺度敏感性，利用迭代次數(shù)和粒子群與全局最優(yōu)的一致性自適應(yīng)調(diào)節(jié)尺度參數(shù)。而后將聚類的選擇性集成問題抽象為組合優(yōu)化問題，定義聚類成員的有效性、差異性以及適應(yīng)度函數(shù)，通過粒子群的進化過程實現(xiàn)聚類成員的選擇。實驗結(jié)果驗證了本文方法的有效性。

［1］Strehl A，G hosh J.Cluster ensem bles-a knowledge reuse framework for combining multiple partitions［J］.Journal of Machine Learning Research，2002，3（3）：583-617.

［2］Jia J H，Liu B X，Jiao L C.Soft spectral clustering ensem bleapplied to image segmentation［J］.Frontiers of Computer Science in China，2011，5（1）：66-78.

［3］Lu Z M，Li C，Zhang Q.A document cluster ensemble spectral algorithm based on affinity propagation［J］.Journal of Harbin Engineering University，2012，33（7）：899-905.（盧志茂，李純，張綺.近鄰傳播的文本聚類集成譜算法［J］.哈爾濱工程大學(xué)學(xué)報，2012，33（7）：899-905.）

［4］Hong Y，K wong S，Chang Y，et al.Unsupervised feature selective clustering ensembles and population based incrementallearning algorithm［J］.Pattern Recognition，2008，41（9）：2742-2756.

［5］H u X，Park E，Zhang X.Microarray gene cluster identification and annotation through cluster ensemble and E M-based informative textual summarization［J］.IE E E Trans.on Information Technology in Biomedicine，2009，13（5）：832-840.

［6］Zhou ZH，W u J X，Tang W.Ensem bling neural networks：many could be better than all［J］.ArtificialIntelligence，2002，137（1-2）：239-263.

［7］Fern X Z，LinW.Cluster ensem ble selection［J］.Statistical Analysis and Data Mining，2008，1（1）：128-141.

［8］Zhang C X，Zhang J S.A survey of selective ensem ble learning algorithm［J］.Chinese Journal of Com puters，2011，34（8）：1399-1410.（張春霞，張講社.選擇性集成學(xué)習(xí)算法綜述［J］.計算機學(xué)報，2011，34（8）：1399--1410.）

［9］H ong Y，Sam K，W ang H L，et al.Resam pling-based selective clustering ensembles［J］.Pattern Recognition Letters，2009，30 （3）：298-305.

［10］Naldi M C，Carvalho A C，Campello R J.Cluster ensemble selection based on relative validity indexes［J］.Data Mining& Knowledge Discovery，2013，27（2）：259-289.

［11］Kennedy J，Eberhart R C.Particle swarm optimization［C］∥Proc.of the IE E E International Conference on N eural Networks，1995：1942-1948.

［12］Kennedy J，Eberhart R C.A discretebinary version of the particle swarm algorith m［C］∥Proc.of the World Multiconferenceon Systemics，Cybernetics and Inform atics，Piscata way，1997：4104-4109.

［13］Fan K，Zhang R Q，Xia G P.Solving a class of job-shop schedul ing problem based on improved BPSO algorithm［J］.Systems Engineering-Theory&Practice，2007，27（11）：111-117.（樊坤，張人千，夏國平.基于改進BPSO算法求解一類作業(yè)車間調(diào)度問題［J］.系統(tǒng)工程與理論實踐，2007，27（11）：111-117.）

［14］Alberto GV，Rafael P.Introducing dynamic diversity into a discrete particle swarm optimization［J］.Computer and Operation Research，2009，36（3）：951-966.

［15］Zhang C S，Sun J G，Ouyang D T.A self-adaptive discete particle swarm optimization algorithm［J］.Acta Electronica Sinica，2009，37（2）：298-304.（張長勝，孫吉貴，歐陽丹彤.一種自適應(yīng)離散粒子群算法及其應(yīng)用研究［J］.電子學(xué)報，2009，37（2）：298-304.）

［16］Tao X M，W ang Y，Zhao C H，et al.Discrete particle swarm optimization based on double-scale cooperationm utation［J］. Journalof H arbin Engineering University，2011，32（12）：1617 -1623.（陶新民，王妍，趙春暉，等.雙尺度協(xié)同變異的離散粒子群算法［J］.哈爾濱工程大學(xué)學(xué)報，2011，32（12）：1617-1623.）

［17］Yao X，W ang X D，Zhang Y X，et al.Feature selection algorith m using PSO with adaptive mutation-basedtdistribution［J］.Systems Engineering and Electronics，2013，35（6）：1335-1341.（姚旭，王曉丹，張玉璽，等.基于自適應(yīng)t分布變異的粒子群特征選擇方法［J］.系統(tǒng)工程與電子技術(shù)，2013，35（6）：1335-1341.）

［18］Zhou F J，W ang X J，Zhang M.Evolutionary progra m ming using mutations based on thetprobability distribution［J］.Acta Electronica Sinica，2008，36（4）：667-671.（周方俊，王向軍，張民.基于t分布變異的進化規(guī)劃［J］.電子學(xué)報，2008，36（4）：667-671.）

［19］Gao Y L，Ren Z H.Adaptive particle swarm optimization algorithm with mutation operator［J］.Com puter Engineering and Applications，2007，43（25）：43-47.（高岳林，任子暉.帶有變異算子的自適應(yīng)粒子群優(yōu)化算法［J］.計算機工程與應(yīng)用，2007，43（25）：43-47.）

［20］Chuang L Y，Yang C S，W u K C，et al.Gene selection and classification using taguchi chaotic binary particle swarm optimization［J］.E xpert Systems with Applications，2011，38（10）：13367-13377.

［21］Kersten P B G，Lee J S，Ainsworth T L.U nsupervised classification of polarimetric synthetic aperture radar images using fuzzy clustering and E M clustering［J］.IE E E Trans.on Geoscience and Remote Sensing，2005，43（3）：519-527.

［22］Lu X Y，Yang Y，W ang H J.Selective clustering ensemble based on covariance［C］∥Proc.of the11th International Workshop，2013：179-189.

Cluster ensemble selection based on improved BPSO

BI Kai，W A N G Xiao-dan，XIN G Ya-qiong
（School of Air and Missile Defense，Air Force Engineering University，Xi’an 710051，China）

At first，as binary particle swarm optimization（BPS O）relapses into local extremism easily，an improved BPS O is proposed.By analyzing the scale sensitivity of Gaussian density function，the scale parameter is regulated based on the consistency between particle swarm and the global optimal particle.The mutation probability of the global optimal particle is determined by the definite integral in symmetric interval of the Gaussian density function.Then，the cluster ensemble selection is modeled as a combinatorial optimization problem.The fitness of each cluster memberis defined by weighted co m position of effectiveness and difference，and the cluster ensemble selection is carried out based on the mimproved BPS O.Finally，experiments on standard dataset and image dataset show that the proposed method is effective.

cluster ensemble selection；binary particle swarm optimization（BPS O）；Gaussian density function；image segmentation

T P 391

A

10.3969/j.issn.1001-506 X.2016.03.33

1001-506 X（2016）03-0692-07

2015-01-28；

2015-06-17；網(wǎng)絡(luò)優(yōu)先出版日期：2015-09-01。

網(wǎng)絡(luò)優(yōu)先出版地址：http：//w w w.cnki.net/kcms/detail/11.2422.T N.20150901.0928.006.html

國家自然科學(xué)基金（60975026，61273275）資助課題

畢 凱（1985-），男，博士研究生，主要研究方向為智能信息處理、機器學(xué)習(xí)。

E-mail：bk3039633@163.com

王曉丹（1966-），女，教授，博士研究生導(dǎo)師，主要研究方向為智能信息處理、機器學(xué)習(xí)。

E-mail：sh milyqq520@163.com

邢雅瓊（1986），女，博士，主要研究方向為智能信息處理、機器學(xué)習(xí)。

E-mail：sh milyds520@163.com