李 莉，李妍琰

（1.河南工程學院 計算機學院，河南 鄭州451191；2.河南財經(jīng)政法大學 計算機與信息工程學院，河南 鄭州450002）

0 引 言

相對于傳統(tǒng)的聚類算法，多目標聚類能夠綜合考慮多種已有聚類方法的評價標準，避免了單一評價標準對數(shù)據(jù)結(jié)構(gòu)描述存在偏差的影響。典型的多目標聚類算法如Handl等人［1］提出的多目標進化聚類算法 MOCK，及Saha等人［2］提出的基于模擬退火的多目標聚類算法VAMOSA。國內(nèi)也有學者提出了相應(yīng)的多目標聚類算法，張歡等人［3］改進MOCK算法并將其應(yīng)用于挖掘機故障數(shù)據(jù)的聚類分析中，取得了比k均值更低的錯誤識別率。秦亮等人［4］提出的算法中采用了與MOCK相同的目標函數(shù)，設(shè)計了一種免疫克隆選擇算法對其進行優(yōu)化，取得了比MOCK運算速度更快、錯誤率更低的識別結(jié)果。聚類集成是另外一種有效提高傳統(tǒng)聚類方法性能的技術(shù)，將多個聚類成員所得的聚類結(jié)果進行綜合，從而得到好于單一聚類成員的結(jié)果。由于多目標聚類最終得到多個不同的解，因此將其與聚類集成技術(shù)結(jié)合是可行的。并且多目標聚類集成技術(shù)可以進一步提高聚類結(jié)果的質(zhì)量，解決多目標聚類中不易自動選取單個解的問題。Qian等人［5］以MOCK算法為基礎(chǔ)，將聚類得到的所有候選解集成，并用于文本圖像的分割中。Zhu等人［6］則將多目標進化聚類與軟子空間聚類相結(jié)合，提出了一種多目標聚類集成算法，其在集成階段利用圖分割方法將所有解集成。上述算法將多目標聚類與集成技術(shù)進行了簡單的結(jié)合，但多目標聚類算法所得的解集中包含多個類數(shù)下的劃分結(jié)果，存在大量欠劃分或者過劃分的解，與真實的數(shù)據(jù)結(jié)構(gòu)相差巨大，如果直接利用所有的解進行集成，其聚類結(jié)果會受質(zhì)量較差解的影響，通常只能達到所有解的平均水平。另外，由于個體編碼所表達的類數(shù)是不同的，常見的交叉變異算子不能很好應(yīng)用于聚類過程中，構(gòu)建合理高效的多目標聚類算法也是保證聚類質(zhì)量的重要環(huán)節(jié)。為此，提出了一種基于熱點解搜索和差分進化的多目標聚類集成算法，利用高效的差分進化機制實現(xiàn)優(yōu)化，并針對聚類過程中編碼長度不一的情況，對差分進化的交叉和變異算子進行了相應(yīng)地改進；在優(yōu)化過程中不斷找出當前種群里的熱點解，用其作為差分進化中的 “best”個體，引導種群的優(yōu)化方向，加強潛在最優(yōu)解區(qū)域的搜索；在后續(xù)的集成操作中，再基于熱點解的概念對優(yōu)化所得的解集進行篩選，去除了質(zhì)量較差解對集成結(jié)果的影響。

1 多目標優(yōu)化問題描述與熱點解的搜索方法

1.1 多目標優(yōu)化問題描述

多目標優(yōu)化問題的定義為

式中：x——解空間的n維變量，gi（x）——目標空間的第i個函數(shù)取值，一共有m個目標函數(shù)。

在式 （1）中每個目標函數(shù)均要達到最小化，但各個目標函數(shù)之間存在一定的矛盾關(guān)系，一部分目標函數(shù)取值的減小會引起另一部分目標函數(shù)取值的增加。因此理想狀態(tài)下同時最小化各個目標函數(shù)是無法實現(xiàn)的，其最終得到的實際是一組折中解集。該解集稱為Pareto解集，其定義如下：

（1）Pareto占優(yōu)：對于解空間的變量x1和x2，若對于所有的目標函數(shù)均有g(shù)i（x1）≤gi（x2），并且存在目標函數(shù)gj（x）使得gj（x1）＜gj（x2），則稱解x1對x2Pareto占優(yōu)。

（2）Pareto解集：若解空間其它變量均不能Pareto占優(yōu)解x1，則稱x1為Pareto占優(yōu)解。這樣的解通常存在多個，它們之間互不占優(yōu)，其構(gòu)成的集合稱為Pareto解集，即優(yōu)化所得的折中解集。

在聚類算法中，存在多種描述聚類質(zhì)量的評價標準。這些標準均從某一方面描述聚類的質(zhì)量，具有一定的片面性。而它們之間又存在一定的矛盾關(guān)系，例如評價類內(nèi)方差的標準會傾向于將每個樣本看作一個獨立的類，而評價類間距離總量的標準又會傾向于將整個數(shù)據(jù)看作一個類。可見，將聚類算法轉(zhuǎn)換為一個多目標優(yōu)化問題既是合理的，又能全面描述數(shù)據(jù)的結(jié)構(gòu)［7］。

1.2 熱點解的搜索方法

熱點解是指在Pareto解集中目標函數(shù)取值發(fā)生突變的位置上的解。即相對于周圍的Pareto占優(yōu)解，熱點解的一部分目標函數(shù)值大幅增大 （或減小），而另一部分目標函數(shù)值減小 （或增大）的幅度卻很小。這種幅值的變化可以通過式 （2）進行描述

式中：T——解x1相對于x2，其目標函數(shù)取值減小的總量與目標函數(shù)取值增大的總量之比。為了不受函數(shù)取值量級的影響，所有目標函數(shù)的取值必須先進行歸一化處理［8］。

用S表示一個Pareto解集的子集，該子集的元素在目標函數(shù)空間上的歐式距離相近。對于任意一個解x∈S，按照式 （3）找出其相對于S中其它解的最小變化量u（x，S）。它表示每單位衰減量 （即目標函數(shù)值增加總量）下解x在一些目標函數(shù)上的最小提升量 （即減小量）。再按照式 （4）找出所有解的最小變化量中的最大值u（x＊，S），x＊即為區(qū)域S中的熱點解

在多目標聚類中，熱點解往往對應(yīng)Pareto解集中一些關(guān)鍵的聚類劃分結(jié)果，這些解能夠很好反映數(shù)據(jù)的真實結(jié)構(gòu)。數(shù)據(jù)如圖1所示。

圖1 數(shù)據(jù)類數(shù)變化過程中目標函數(shù)取值變化

當劃分結(jié)果由一個類變化到2個類時，類內(nèi)方差顯著減小，而類間距離總量增大相對較??；當變化到8個類時，類內(nèi)方差減小較小，類間距離總量則會有較大增加。

2 MCEASKD的設(shè)計

本文提出的多目標聚類集成算法以差分進化算子為基本搜索算子，在進化和集成過程中均利用了熱點解以提高求解的質(zhì)量。

2.1 目標函數(shù)設(shè)計

MCEASKD同時優(yōu)化2個目標函數(shù)，分別為常見的類內(nèi)方差和類間距離總量，其具體定義如式 （5）和式 （6）所示

式中：k——個體x所表示的總類數(shù)，d——數(shù)據(jù)的維數(shù)，Ni——第i個類的樣本總數(shù)，xij——第i個類在第j維上的類中心取值，zpj——第i個類中第p個樣本在第j維上的取值。

2.2 改進的差分進化算法

MCEASKD以概率選擇的形式使用了2種差分進化算子，分別為DE／rand／1／bin和DE／best／1／bin。二者變異部分的定義如式 （7）所示

式中：F——張量因子，個體a、b、c從當前種群中選取，并且保證a≠b≠c。對于算子DE／rand／1／bin，個體a、b、c均從種群中隨機選取，用于加強種群在整個空間中的全局搜索能力；而對于DE／best／1／bin，個體a則從當前找到的熱點解中隨機選取，個體b、c從種群中隨機選取，用于提高算法的收斂速度。2種差分進化算子交叉部分的定義如式 （8）所示

式中：CR——交叉率參數(shù)，個體i隨機從種群中選取，且i≠a≠b≠c，j0表示隨機選取的某一維變量，rand（）——0和1之間的隨機數(shù)。

設(shè)定選擇 DE／rand／1／bin的概率為ps，選擇 DE／best／1／bin的概率為1－ps。在進化前期算法應(yīng)加強全局搜索，在后期應(yīng)加強熱點解附近的搜索，因此本文設(shè)定的取值隨進化代數(shù)線性增加，如式 （9）所示

式中：p0、p1和t0——預先設(shè)定值，t——當前進化代數(shù)，tmax——最大進化代數(shù)。

由于本文采用類中心編碼的方式，個體之間的有效編碼長度往往不同，傳統(tǒng)的差分進化算子無法應(yīng)用在聚類中。因此做了如下改進：假設(shè)個體x1、x2、x3、x4所表示的類數(shù)分別為k1、k2、k3和k4；找出類數(shù)最少的個體，設(shè)其編碼長度為k·d＝min ｛k1、k2、k3、k4｝·d；然后分別從個體x1、x2、x3、x4中隨機選取k個類的編碼存入ya、yb、yc、yi中 （y的編碼長度為k·d），再執(zhí)行相應(yīng)的差分進化算子，然后用新生成的yi’替換x4中相應(yīng)位置的取值，最終得到新的解x’。

2.3 改進的集成操作

在集成操作之前，先將優(yōu)化得到的Pareto解集按照某一目標函數(shù)取值 （如g1（x））升序排列。然后找出各個目標函數(shù)取值的最大和最小值，對其進行歸一化處理。再將按照g1（x）的取值將所有解等分為h個區(qū)間，找出每個區(qū)間中的熱點解，存入集合Sk。對于集合Sk中的每個解，在目標空間上按照歐式距離度量找到其l個最近鄰Pareto占優(yōu)解，存入集合Sn中。最后，按照文獻 ［9］提出的基于超圖分割的集成算法HGPA，將集合和中的所有解集成，集成的結(jié)果即為最終的聚類結(jié)果。

2.4 算法流程描述

MCEASKD的算法流程如下所示：①設(shè)定可選類數(shù)的范圍為1～kmax，進化種群為P，進化代數(shù)t＝0，首先隨機生成kmax個個體，它們所表示的類數(shù)依次為1、2、…、kmax，再隨機生成剩余的｜P｜－kmax個個體，其中每個個體的類數(shù)在1和kmax之間隨機選擇，按式 （5）和式 （6）計算所有個體的目標函數(shù)值；②當進化代數(shù)t＜t0時，根據(jù)算子DE／rand／1／bin生成新個體，否則根據(jù)概率ps選擇DE／rand／1／bin或DE／best／1／bin生成新個體；③反復執(zhí)行步驟②，直到得到與種群P相同的個體數(shù)量，記為子代種群P’，將P和P’中的個體合并，按照NSGAII［10］中提出的非劣排序方法和擁擠距離方法更新種群P；④若達到最大進化代數(shù)tmax，則停止迭代，選出種群P中的所有Pareto解，再從中找出所有的熱點解及其鄰域個體，對其進行集成操作，輸出集成后的結(jié)果，否則繼續(xù)優(yōu)化，令t＝t＋1。

3 實驗與分析

選取三組UCI數(shù)據(jù)［11］用于驗證所提算法 MCEASKD的有效性。這三組數(shù)據(jù)分別為Vehicle、Ionosphere和Sonar。它們的樣本數(shù)量分別為846、351和208個，特征維數(shù)分別為18、34和60個，類數(shù)分別為4、2和2個。

為了更好的說明本文算法的性能，選取2種多目標聚類集成算法用于對比分析：第一種為文獻 ［1］所提出的MOCK算法與本文所提基于熱點解搜索的集成方法相結(jié)合而形成的新算法，記為MOCKE；第二種為本文算法不經(jīng)過熱點解的篩選而直接進行集成操作而形成的算法，記為MCEAD。MOCKE中多目標聚類環(huán)節(jié)的參數(shù)設(shè)置與文獻［1］相同，集成環(huán)節(jié)參數(shù)設(shè)置與本文算法相同。MCEAD的所有參數(shù)設(shè)置均與本文算法相同。本文算法MCEASKD的具體參數(shù)設(shè)置為：種群P的大小為100，最大進化代數(shù)為tmax200，最大類數(shù)kmax為20，參數(shù)t0為50，p0和p1分別為0.05和0.4，差分進化的參數(shù)CR取值為0.9，張量因子F 對于 DE／rand／1／bin的取值為0.7，對于 DE／best／1／bin的取值為0.2，區(qū)間劃分數(shù)量h為10，鄰域個數(shù)l為4。

本文采用RI指標［12］和FM指標［13］來評價各種算法的聚類結(jié)果，2種指標的取值均是越大說明聚類結(jié)果越好。三組UCI數(shù)據(jù)在每種算法上均測試30次［14］，其測試所得的RI指標均值和FM指標均值分別見表1和表2。

可見，本文提出的算法MCEASKD無論在RI指標還是在FM指標上均高于2種對比算法的結(jié)果，其中RI取值提高了0.0021～0.0524，F(xiàn)M取值提高了0.0134～0.0591。此外，MCEASKD和MOCKE采用了相同的基于熱點解篩選的集成操作，其對比結(jié)果說明提出的改進差分算子具有良好的尋優(yōu)性能，使得所得Pareto解集的質(zhì)量普遍好于MOCK算法所得結(jié)果，為后續(xù)集成操作提供了更多好的集成成員。而MCEASKD與MCEAD的區(qū)別在于是否在集成操作階段使用了基于熱點解的篩選步驟，對比結(jié)果說明本文提出的篩選方法可以有效去除Pareto解集中質(zhì)量較差解對算法性能的影響。

表1 3種算法的測試結(jié)果在RI指標上的對比

表2 3種算法的測試結(jié)果在FM指標上的對比

本文算法中的區(qū)間劃分數(shù)量h和鄰域個數(shù)l決定著熱點解的數(shù)量以及最后用于集成操作的解的數(shù)量，是算法中的重要參數(shù)。因此，此處以Vehicle數(shù)據(jù)為例，分析了上述2個參數(shù)對算法性能的影響。首先，將區(qū)間劃分數(shù)量h由5變化到20，而保持鄰域個數(shù)l始終為4，其結(jié)果如圖2所示。

圖2 區(qū)間劃分數(shù)量h對算法質(zhì)量的影響

其次，將區(qū)間劃分數(shù)量h固定為10，而將鄰域個數(shù)l由1變化到20，其結(jié)果如圖3所示。

圖3 鄰域個數(shù)l對算法質(zhì)量的影響

從圖2和圖3中的實驗結(jié)果表明，區(qū)間劃分數(shù)量h和鄰域個數(shù)l均不宜過大；否則，會使得進化過程中選中的熱點解數(shù)量過多，從而起不到引導種群進化方向的作用；還會使得集成操作之前的篩選步驟失效，一些質(zhì)量較差的解會進入集成操作中，從而影響集成的質(zhì)量。

4 結(jié)束語

本文提出了一種熱點解搜索和差分進化的多目標聚類集成算法MCEASKD。該算法在優(yōu)化過程和集成過程中均對若干熱點解進行了搜索。這些熱點解既能用于引導差分進化的搜索方向，提高了差分進化的尋優(yōu)能力，還能用于在集成操作前篩選掉一些質(zhì)量較差的Pareto占優(yōu)解，提高了后續(xù)的聚類集成的效果。此外，提出了在差分進化算子中利用多個個體的最小編碼部分進行變異和交叉，解決了聚類中個體編碼長度不一而影響差分進化算子使用的問題。最后在三組UCI數(shù)據(jù)上的實驗測試結(jié)果表明，本文算法具有良好的性能，其改進的尋優(yōu)過程和集成操作對算法性能的提升均有顯著作用。此外，算法中參數(shù)對性能影響的分析結(jié)果也揭示了其相應(yīng)的設(shè)置規(guī)律。

［1］Handl J，Knowles J.An evolutionary approach to multiobjective clustering ［J］.IEEE Transactions on Evolutionary Computation，2007，11 （1）：56－76.

［2］Saha S，Bandyopadhyay S.A symmetry based multiobjective clustering technique for automatic evolution of clusters ［J］.Pattern Recognition，2010，43 （3）：738－751.

［3］ZHANG Huan，WANG Jinkun，CHEN Cheng.Research on the fault diagnosis of the excavator to be based on the multi－objective optimization clustering ［J］.Construction Machinery Technology ＆ Management，2013，26 （6）：115－117 （in Chinese）.［張歡，王錦錕，陳程.基于多目標優(yōu)化聚類的挖掘機故障診斷研究 ［J］.建設(shè)機械技術(shù)與管理，2013，26 （6）：115－117.］

［4］QIN Liang，ZHANG Wenguang，SHI Xianjun，et al.Multi－objective clustering method based on immune clonal algorithm［J］.Information and Control，2013，42 （1）：8－12 （in Chinese）.［秦亮，張文廣，史賢俊，等.基于免疫克隆算法的多目標聚類方法 ［J］.信息與控制，2013，42 （1）：8－12.］

［5］Qian Xiaoxue，Zhang Xianrong，Jiao Licheng，et al.Unsupervised texture image segmentation using multiobjective evolutionary clustering ensemble algorithm ［C］／／IEEE Congress on Evolutionary Computation.Piscataway，NJ，USA：IEEE，2008：3561－3567.

［6］Zhu Lin，Cao Longbing，Yang Jie.Multiobjective evolutionary algorithm－based soft subspace clustering ［C］／／IEEE Congress on Evolutionary Computation.NY，USA：IEEE，2012.

［7］LIN Jikeng，WANG Xudong，CHEN Yushan，et al.Distribution network reconfiguration based on feasible solution search and adaptive immune algorithm ［J］.Journal of Tianjin University （Science and Technology），2008，41 （12）：1505－1511（in Chinese）.［林濟鏗，王旭東，陳云山，等.基于可行解搜索和自適應(yīng)免疫算法的配網(wǎng)重構(gòu) ［J］.天津大學學報，2008，41 （12）：1505－1511.］

［8］XUE Yu，ZHUANG Yi，MENG Xin，et al.Self－adaptive learning based ensemble algorithm for solving matrix eigenvalues［J］.Journal of Computer Research and Development，2013，50 （7）：1435－1443 （in Chinese）.［薛羽，莊毅，孟新，等.自適應(yīng)學習集成優(yōu)化算法及矩陣特征值求解 ［J］.計算機研究與發(fā)展，2013，50 （7）：1435－1443.］

［9］Strehl A，Ghosh J.Cluster ensembles：A knowledge reuse framework for combining multiple partitions ［J］.Journal of Machine Learning Research，2008，3 （3）：583－617.

［10］Deb K，Pratap A，Agarwal S，et al.A fast and elitist multiobjective genetic algorithm：NSGA－II ［J］.IEEE Transactions on Evolutionary Computation，2002，6 （2）：182－197.

［11］University of California，Irvine.UCI machine learning repository ［EB／OL］.［2013－09－20］.http：／／archive.ics.uci.edu／ml／datasets.html.

［12］WANG Junling，ZHOU Jianlin，BAO Fang，et al.Fuzzy C means clustering algorithm based on space distance of nearest pixels ［J］.Computer Engineering and Design，2013，34（7）：2476－2482 （in Chinese）.［王軍玲，周建林，包芳，等.基于臨近像素空間距離的模糊C均值聚類算法 ［J］.計算機工程與設(shè)計，2013，34 （7）：2476－2482.］

［13］MAO Guojun，CAO Yongcun.Clustering models and algorithms for distributed data streams based on data synopsis ［J］.Computer Science，2013，40 （6）：187－191 （in Chinese）.［毛國君，曹永存.基于數(shù)據(jù)概要描述的分布式數(shù)據(jù)流聚類模型與算法 ［J］.計算機科學，2013，40 （6）：187－191.］

［14］DENG Zelin，TAN Guanzheng，F(xiàn)AN Bishuang，et al.Effect of different distance measure methods on performance of artificial immune recognition system ［J］.Application Research of Computer，2011，28 （6）：2043－2045 （in Chinese）.［鄧澤林，譚冠政，范必雙，等.不同的距離測量方法對人工免疫識別系統(tǒng)的性能影響 ［J］.計算機應(yīng)用研究，2011，28 （6）：2043－2045.］