胡曉東，高嘉偉

(1.山西經(jīng)濟(jì)管理干部學(xué)院 電子信息工程系，山西 太原 030024； 2.山西大學(xué) 計(jì)算機(jī)學(xué)院，山西 太原 030024)

0 引 言

數(shù)據(jù)聚簇是目前最為流行也最為重要的一種數(shù)據(jù)分析手段[1]，其目標(biāo)是以數(shù)據(jù)對(duì)象集合分組的方式將其聚類成簇，使同一聚簇內(nèi)的數(shù)據(jù)對(duì)象具有最大的相似性，即同質(zhì)數(shù)據(jù)，而不同聚簇內(nèi)的數(shù)據(jù)對(duì)象間具有最大的差異性，即異質(zhì)數(shù)據(jù)[2]。數(shù)據(jù)聚簇廣泛應(yīng)用于諸多領(lǐng)域，如機(jī)器學(xué)習(xí)[3]、模式識(shí)別[4]、圖像處理[5]、數(shù)據(jù)挖掘[6]等。

目前，受萬有引力定理和物體運(yùn)動(dòng)規(guī)律的啟發(fā)，一種基于隨機(jī)種群的元啟發(fā)式算法被提出，即引力搜索算法GSA[7]。GSA的設(shè)計(jì)初衷是求解連續(xù)最優(yōu)化問題，與多數(shù)元啟發(fā)式算法相似，該算法擁有較好靈活性，且在加強(qiáng)搜索和開發(fā)能力的均衡性上表現(xiàn)突出。GSA的搜索策略是利用萬有引力定理將種群成員向著種群中最優(yōu)的K個(gè)解移動(dòng)。受該算法在變體最優(yōu)化問題中的啟發(fā)，本文提出一種基于分組的GSA算法GGSA實(shí)現(xiàn)大數(shù)據(jù)的聚簇求解。提出的GGSA算法與標(biāo)準(zhǔn)的GSA具有兩個(gè)方面的不同。首先，算法設(shè)計(jì)一種分組編碼策略，將數(shù)據(jù)聚簇問題的相關(guān)結(jié)構(gòu)映射為解的部分；其次，對(duì)于給定的聚簇編碼，適合于分組編碼的解的位置更新與速度更新公式在GGSA算法中被重新定義。為了評(píng)估GGSA算法在數(shù)據(jù)聚簇上的性能，選取了13種經(jīng)典的數(shù)據(jù)集進(jìn)行了測試。對(duì)于給定的D個(gè)聚簇的數(shù)據(jù)集，GGSA試圖通過隨機(jī)選擇的給定數(shù)據(jù)集的75%來尋找D個(gè)聚簇中心，這75%的數(shù)據(jù)集稱為GGSA的訓(xùn)練數(shù)據(jù)集。而剩余的25%數(shù)據(jù)集則用于評(píng)估GGSA算法的性能，稱之為測試集，而分類失誤比率CEP則用于評(píng)估算法在測試集中的聚簇性能。

1 相關(guān)研究

數(shù)據(jù)聚簇方法已有很多研究，傳統(tǒng)的數(shù)據(jù)聚簇算法的分類主要以分層和分割的方式進(jìn)行區(qū)分[8]。分層的聚簇算法主要以凝聚式模式或群集式模式遞歸尋找數(shù)據(jù)聚簇。凝聚式方法以單個(gè)數(shù)據(jù)對(duì)象作為一個(gè)分離聚簇，然后連續(xù)地合并最具最似性的聚簇直到滿足聚簇終止條件。群集式方法初始將所有數(shù)據(jù)對(duì)象視為一個(gè)聚簇，然后重復(fù)地分割每個(gè)聚簇為更小的聚簇，直到滿足終止條件。另一方面，分割式聚簇算法試圖在不構(gòu)建分層結(jié)構(gòu)的情況下同步尋找所有的聚簇。事實(shí)上，分割聚簇算法初始獲得的是不相交的聚簇集合，然后逐步提煉使其滿足最小化的預(yù)定義目標(biāo)函數(shù)，其目標(biāo)是在最小化聚簇間的聯(lián)系的同時(shí)最大化聚簇內(nèi)的聯(lián)系性，從而實(shí)現(xiàn)最大化的數(shù)據(jù)緊密度，該方法也是本文的研究方法背景。

除了傳統(tǒng)的數(shù)據(jù)聚類方法以外，基于算法聚類標(biāo)準(zhǔn)的不同還有幾種聚類方法[9]。第一種是基于鄰居共享相同聚類的聚類算法，這類方法主要有基于密度的算法[10]和最近鄰鄰居方法[11]，前者根據(jù)對(duì)象密度進(jìn)行聚類，后者則將近鄰對(duì)象歸屬于相同聚類中。雙聚類算法[12]同步通過行和列進(jìn)行數(shù)據(jù)聚類，多目標(biāo)聚類算法[13]則同步優(yōu)化了數(shù)據(jù)集的不同特征進(jìn)行聚類。重疊聚類算法[14]不同于多數(shù)的聚類算法，傳統(tǒng)算法中每個(gè)對(duì)象僅屬于一個(gè)聚類，而重疊聚類中每個(gè)對(duì)象可分屬于不同的聚類中，最具代表性的重疊聚類即為模糊C均值聚類算法[15]。

近年來，元啟發(fā)式方法廣泛應(yīng)用在數(shù)據(jù)聚類問題中。從優(yōu)化角度上看，聚類問題可建立模型為一類NP難的群組劃分問題[16]。這類算法需要搜索一個(gè)聚類的最優(yōu)解，可以降低搜索過程陷入局部最優(yōu)的風(fēng)險(xiǎn)。具體包括遺傳算法GA[17]、模擬退火算法SA[18]、禁忌搜索算法Tabu[19]、智能蜂群算法ABC[20]、貪婪隨機(jī)自適應(yīng)搜索算法GRASP[21]、迭代局部搜索算法ILS[22]、可變鄰居搜索算法VNS[23]、蟻群算法ACO[24]、粒子群優(yōu)化算法PSO[25]等。

引力搜索算法GSA是受牛頓的萬有引力定理的啟發(fā)而提出的一種元啟發(fā)式優(yōu)化算法。算法中，搜索空間中的一個(gè)對(duì)象因?yàn)橘|(zhì)量和重力的關(guān)系相互吸引，其吸引力與對(duì)象的質(zhì)量成正比，而與距離的平方成反比。GSA已經(jīng)被證明可應(yīng)用于不同類型的優(yōu)化方法中，包括數(shù)據(jù)聚類[26]、模糊系統(tǒng)識(shí)別[27]、分類問題[28]、排放負(fù)載分配[29]、風(fēng)力渦輪控制[30]以及供電系統(tǒng)[31]中。然而，傳統(tǒng)的引力搜索算法直接應(yīng)用于數(shù)據(jù)聚類問題時(shí)，在問題解的編碼機(jī)制和解的迭代更新機(jī)制上依然存在不足，會(huì)導(dǎo)致最優(yōu)解的搜索過程過早收斂，本文將從這兩個(gè)方面進(jìn)行改進(jìn)，并驗(yàn)證改進(jìn)后的聚類算法性能。

2 數(shù)據(jù)聚簇問題

數(shù)據(jù)對(duì)象距離的度量是數(shù)據(jù)聚簇問題的關(guān)鍵，兩個(gè)不同的數(shù)據(jù)對(duì)象Oi和Oj間的相似性與特征空間S中的距離是密切相關(guān)的，而空間S中的距離度量常用方式是Euclidean歐氏距離。衡量聚簇結(jié)果質(zhì)量的常用目標(biāo)函數(shù)為考慮聚簇內(nèi)聚度的二次誤差之和，可以評(píng)價(jià)一個(gè)給定數(shù)據(jù)分割的質(zhì)量，定義為

(1)

(2)

式中：|Ci|代表聚簇Ci的基數(shù)，即聚簇i中數(shù)據(jù)對(duì)象的數(shù)目。

數(shù)據(jù)聚簇過程可以分為兩類：無監(jiān)督聚簇和監(jiān)督聚簇。無監(jiān)督聚簇即自動(dòng)式的聚簇，訓(xùn)練數(shù)據(jù)集無需描述聚簇?cái)?shù)目。而監(jiān)督聚簇中訓(xùn)練數(shù)據(jù)集合需要描述訓(xùn)練目標(biāo)和聚簇?cái)?shù)目。本文所處理的數(shù)據(jù)集包括聚簇信息，因此，其優(yōu)化目標(biāo)是通過最小化目標(biāo)函數(shù)尋找D個(gè)聚簇的中心，即最小化數(shù)據(jù)對(duì)象與其聚簇中心的距離之和。本文中，在訓(xùn)練集OTrain上的一個(gè)聚簇C={C1,C2,…,CD}的適應(yīng)度定義為

(3)

3 引力算法GSA

標(biāo)準(zhǔn)的引力搜索算法GSA是受牛頓萬有引力定理的啟發(fā)發(fā)展而來的，這種群體優(yōu)化技術(shù)提供了一種模擬對(duì)象在多維空間中由于萬有引力影響帶來的相互關(guān)連的迭代方法。GSA的基本模型中，其初始目標(biāo)是解決連續(xù)優(yōu)化問題，即一個(gè)對(duì)象(代理agent)被引入D維解空間中，需要尋找最優(yōu)解。GSA中的每個(gè)代理的位置代表問題的一個(gè)候選解，因此，每個(gè)代理可表示為問題解空間中的矢量Xi。擁有越好性能的代理將擁有更大的質(zhì)量，由于更重的代理擁有更大的吸引半徑，因此擁有更大的吸引強(qiáng)度。在GSA的運(yùn)行周期中，每個(gè)代理會(huì)連續(xù)調(diào)整其位置Xi，向著種群中最優(yōu)的K個(gè)代理的位置移動(dòng)。

為了詳細(xì)描述GSA，考慮一個(gè)擁有s個(gè)搜索代理的D維空間，空間中第i個(gè)代理的位置可定義為

(4)

(5)

(6)

其中，Mi(t)和fiti(t)分別代表時(shí)間t時(shí)代理i的質(zhì)量值和適應(yīng)度值，worst(t)和best(t)分別定義為

(7)

(8)

利用運(yùn)行定律計(jì)算代理i的加速度為

(9)

其中：randj代表區(qū)間[0,1]內(nèi)的均勻分布的隨機(jī)數(shù)；Rij(t)代表D維歐氏空間中兩個(gè)代理i與j間的歐氏距離；ε代表一個(gè)極小值，避免公式中的分母為0，即兩個(gè)代理i與j間的歐氏距離可能為0，但分母不能為0；Kbest代表擁有最優(yōu)適應(yīng)度值和最大質(zhì)量值的最初的K個(gè)代理的集合，K代表時(shí)間的函數(shù)，算法開始時(shí)初始化為Kinitial，其值將隨著時(shí)間遞減；G(t)代表重力系數(shù)，擁有初始值Ginitial，其值也將隨著時(shí)間遞減至Gend，且

G(t)=G(Ginitial,Gend,t)

(10)

由此，代理i的速率更新可計(jì)算為當(dāng)前速率的部分與其加速度之和，如式(11)，而代理i的位置更新可計(jì)算為式(12)

(11)

(12)

其中，rand代表區(qū)域[0,1]間的均勻分布的隨機(jī)值。

標(biāo)準(zhǔn)的GSA算法的過程如算法1所示。

算法1:GSA(1)generate the initial population(2)evaluate the fitness value for each agent(3)calculate the mass value for each agent(4)while stopping criteria is not satisfied do(5) update G, K and Kbest(6) calculate the acceleration of each agent(7) calculate the velocity of each agent(8) update the position of each agent(9) evaluate the fitness for each agent(10)calculate the mass value for each agent(11)end while(12)return best solution found

算法說明：步驟(1)進(jìn)行種群初始化操作，生成約定數(shù)量部署于空間中的代理粒子，每個(gè)粒子代表求解問題的一個(gè)解；步驟(2)根據(jù)適應(yīng)度函數(shù)(利用式(3)計(jì)算)對(duì)空間中的每個(gè)代理的適應(yīng)度進(jìn)行評(píng)估；步驟(3)利用式(6)計(jì)算每個(gè)代理的質(zhì)量；步驟(4)～步驟(11)為算法的迭代求解過程，其中，步驟(5)利用式(10)更新相關(guān)參數(shù)，步驟(6)利用式(9)計(jì)算每個(gè)代理的加速度，步驟(7)利用式(11)計(jì)算每個(gè)代理的速率，步驟(8)利用式(12)更新每個(gè)代理在解空間中的位置，步驟(9)再次利用式(3)評(píng)估更新代理位置后代理的適應(yīng)度，步驟(10)利用式(6)計(jì)算新的代理質(zhì)量；最后，在經(jīng)過約定次數(shù)的迭代操作后，在步驟(12)返回找到的最優(yōu)代理，即問題的最優(yōu)解。

在GSA中，參數(shù)K和G可以均衡算法在局部開發(fā)和全局搜索間的性能。為避免陷入局部最優(yōu)，算法需要在初期迭代中利用搜索機(jī)制，而GSA算法可在初期利用較大的參數(shù)K值和G值完成搜索操作，即Kinitial和Ginitial必須較高。越大的參數(shù)K值可基于更多代理的位置加速代理在解空間中的移動(dòng)，進(jìn)而提升算法的搜索性能。同樣地，越大的G值也可以增加代理在解空間的移動(dòng)能力，增加其搜索性能。Kinitial和Ginitial值越高，解空間中更好的區(qū)域可在算法迭代中更可能被識(shí)別。因此，隨著算法的迭代進(jìn)行，GSA的搜索能力將減弱，開發(fā)能力將逐漸顯現(xiàn)。而降低參數(shù)K和G值可以提升其開發(fā)能力。越小的K值可基于更少的代理位置使代理在解空間中移動(dòng)，進(jìn)而提升其開發(fā)能力。同樣地，越小的G值則可以降低每個(gè)代理在解空間中的移動(dòng)性能，增強(qiáng)其開發(fā)能力。因此，解空間中更好的區(qū)域在迭代中更有可能被開發(fā)出來。

4 基于分組模型的引力搜索算法GGSA

為求解大數(shù)據(jù)的聚簇問題，本文提出了一種基于分組的引力算法GGSA，算法考慮數(shù)據(jù)的聚簇結(jié)構(gòu)設(shè)計(jì)了一種特定的聚簇編碼方式。在給定的編碼下，重新設(shè)計(jì)了代理的位置和速度更新公式。

4.1 解的編碼

問題解的表達(dá)必須適合且與處理的優(yōu)化問題具有很好的關(guān)聯(lián)性，這樣易于搜索操作符的控制，從而降低對(duì)解的搜索中的時(shí)間和空間復(fù)雜度。GGSA算法中解的編碼利用一種分組表達(dá)方式，由兩個(gè)不同的部分構(gòu)成：物品item部分和分組group部分。item部分由大小為n的數(shù)組構(gòu)成(n代表數(shù)據(jù)對(duì)象的數(shù)目)，group部分由D個(gè)分組(聚簇)標(biāo)簽的排列構(gòu)成。item部分中的每個(gè)成員可以對(duì)應(yīng)D個(gè)分組標(biāo)簽中的任意一個(gè)，代表對(duì)應(yīng)的物品可屬于給定標(biāo)簽聚簇中。圖1描述了GGSA中一種基于分組的解的編碼示例，其中，數(shù)據(jù)聚簇問題O={O1,O2,O3,O4,O5}的一個(gè)解可表示為C={C1={O1,O3},C2={O2,O4,O5}}。

圖1 5個(gè)數(shù)據(jù)對(duì)象聚簇中由兩個(gè)聚簇構(gòu)成的侯選解

利用標(biāo)準(zhǔn)的GSA優(yōu)化一個(gè)連續(xù)函數(shù)時(shí)，通常每個(gè)解可表示為實(shí)值長度為D的矢量(D為空間中的搜索維度)，而每個(gè)值則對(duì)應(yīng)一個(gè)變量。類似地，利用GGSA算法解決數(shù)據(jù)聚簇問題，由D個(gè)聚簇構(gòu)成的一個(gè)解也可以表示為長度為聚簇?cái)?shù)目的結(jié)構(gòu)。換言之，GGSA算法中的分組group即為標(biāo)準(zhǔn)GSA中的變量，在第d個(gè)維度上對(duì)象的位置即代表第d個(gè)參數(shù)的值，它決定了該數(shù)據(jù)對(duì)象屬于第d個(gè)聚簇。本文中，在可行解X中聚簇?cái)?shù)目以D表示。

分組編碼的屬性可以使解具有較低的冗余度。若問題的一個(gè)解擁有多個(gè)不同的編碼，則認(rèn)為該編碼具有冗余度。在這種情況下，問題的解空間與算法的編碼空間之間的映射關(guān)系是一對(duì)多的關(guān)系。算法編碼冗余會(huì)擴(kuò)大搜索空間，且無法適應(yīng)搜索操作符的搜索過程，從而降低算法效率。

4.2 GGSA的公式更新

給定解的分組表達(dá)，本節(jié)的目標(biāo)是重新定義式(9)、式(11)和式(12)，使得算法可以數(shù)據(jù)聚簇方式替代標(biāo)準(zhǔn)GSA中的標(biāo)量方式。重定義等式的主要特征是使其可以在連續(xù)空間內(nèi)運(yùn)行。

為識(shí)別GSA的主要搜索操作符，假設(shè)代理構(gòu)成的種群被初始化在問題的解空間中。若應(yīng)用GSA求解優(yōu)化問題，則算法會(huì)試圖在問題解空間中移動(dòng)代理的位置，進(jìn)而尋優(yōu)?；谑?12)，這種代理位置的移動(dòng)是通過典型的加“+”操作符實(shí)現(xiàn)的，它需要兩個(gè)輸入?yún)?shù)，即代理i的當(dāng)前位置和代理的移動(dòng)長度。然后，返回解空間的新位置作為輸出。代理i的移動(dòng)長度即為其速度?；谑?11)，代理i的移動(dòng)長度由兩類移動(dòng)長度構(gòu)成：獨(dú)立移動(dòng)長度IML和依賴移動(dòng)長度DML。IML為代理對(duì)其它代理位置未知僅對(duì)自身位置已知的情況下得到的移動(dòng)長度，該移動(dòng)長度僅取決于它先前的移動(dòng)長度(或先前的速度)，本質(zhì)上是先前移動(dòng)長度的一部分。另外，DML是代理通過考慮Kbest集合中所有成員位置的情況下得到的移動(dòng)長度。式(9)顯示了代理的DML的計(jì)算方式。根據(jù)式(9)，代理的DML取決于多個(gè)因素，包括：代理j的位置(j∈Kbest)，代理i與j間在第d個(gè)維度上的線性距離，代理i與j間的歐氏距離，代理j的質(zhì)量值以及引力系數(shù)值。為了重新定義式(9)、式(11)和式(12)，使其可以分組的形式操作替代標(biāo)量操作，需要重新定義3個(gè)操作符：線性距離操作符“-”、歐氏距離操作符以及移動(dòng)操作符“+”。

標(biāo)準(zhǔn)GSA中，線性距離操作符量化的是兩個(gè)標(biāo)量間的線性距離，該操作符需要重新定義使其能夠量化兩個(gè)數(shù)據(jù)聚簇間的距離。聚簇距離度量方式有多種，一種是聚簇間的最小距離，即兩個(gè)最鄰近成員間的距離；另一種是聚簇間的最大距離，即兩個(gè)相距最遠(yuǎn)的成員間的距離。而k均值距離度量方式則是以成員與聚簇中心的距離來度量。本文設(shè)計(jì)一種基于杰卡德距離(Jaccard distance)的聚簇間距度量方法。令C1和C2為基數(shù)為|C1|和|C2|的兩個(gè)數(shù)據(jù)聚簇，聚簇C1和C2間的杰卡德距離定義為

(13)

式中：DistJ(C1,C2)代表兩個(gè)分組C1和C2間的差異度，它決定了兩個(gè)聚簇分離的遠(yuǎn)近。如果有C1=C2，則差異度為0；如果有C1∩C2=?，則差異度為1。通常情況下，有0≤DistJ(C1,C2)≤1。

為重新定義歐氏距離操作符，GGSA算法將以聚簇操作代替標(biāo)準(zhǔn)GSA算法中的標(biāo)量操作。換言之，類似于GSA，其代理在第d個(gè)維度上的位置代表d維變量的值，GGSA中代理的位置將決定數(shù)據(jù)屬于第d個(gè)聚簇。令C={C1,C2,…,CD}，C’={C’1,C’2,…,C’D}，表示數(shù)據(jù)對(duì)象的兩個(gè)候選聚簇，定義聚簇C和C’間的歐氏距離為

(14)

利用以上公式計(jì)算DistJ(.,.)時(shí)，距離計(jì)算之前需要適當(dāng)對(duì)聚簇進(jìn)行配對(duì)。為降低隨機(jī)聚簇配對(duì)的負(fù)面影響，算法需要重新對(duì)C和C’聚簇進(jìn)行索引分配，使得最為相似的聚簇總能完成配對(duì)。本文使用一種最大權(quán)重雙向配對(duì)MWM方法進(jìn)行聚簇的配對(duì)操作，MWM排序規(guī)則以一個(gè)擁有兩種結(jié)點(diǎn)的完全雙向相似圖開始進(jìn)行聚簇配對(duì)，一種為源結(jié)點(diǎn)，一種為目標(biāo)結(jié)點(diǎn)。每個(gè)源結(jié)點(diǎn)對(duì)應(yīng)于C中的一個(gè)聚簇，每個(gè)目標(biāo)結(jié)點(diǎn)對(duì)應(yīng)于C’中的一個(gè)聚簇。兩個(gè)結(jié)點(diǎn)間的邊以結(jié)點(diǎn)間的相似度賦予一個(gè)權(quán)重值，該相似度即為杰卡德系數(shù)，為(|C1∩C2|/|C1∪C2|)。令Gb表示一個(gè)加權(quán)完全雙向相似圖，Gb中的配對(duì)即尋找未入射至任一普通結(jié)點(diǎn)的邊的子集。若屬于匹配的結(jié)點(diǎn)是一條邊的入射結(jié)點(diǎn)，則該匹配會(huì)覆蓋該結(jié)點(diǎn)。通過這種方式，尋找Gb中的具有最大權(quán)重和的匹配(即最大權(quán)重匹配)以及對(duì)C’中的聚簇重新進(jìn)行索引分配(重新排序)，使得參與匹配的邊的雙方終止結(jié)點(diǎn)(聚簇)將擁有相同的索引，并且滿足C和C’中具有最相似的聚簇進(jìn)行配對(duì)的目標(biāo)。

(15)

(16)

4.3 GGSA的新解生成方法

GGSA算法利用兩階段生成新的解。第一個(gè)階段為繼承階段，即解Xi(t+1)可以繼承解Xi(t)的部分基因，這使得解Xi(t+1)可能會(huì)丟失部分物品Item。第二個(gè)階段為重新插入階段，該階段可以使得丟失的item可以重新插入已有的聚簇中。

(17)

算法2是GGSA中代理i在迭代t+1時(shí)生成新解的過程。

算法2：

(1)//MWM ordering rule (2)ford=1 to Ddo (3) pair cluster d of Xi(t) with the most similar cluster in Xj(t)(for all Xj(t)∈Kbest) by MWM pairing procedure (4)//Inheritance phase繼承階段 (5)calculate the value of EuclidianJ(Xi(t),Xj(t))(for all Xj(t) ∈Kbest) using Eq.(14) (6)for d=1 to Ddo (7) calculate the value of DistJ(xdj(t),xdi(t))(for all Xj(t)∈Kbest) using Eq.(13) (8) compute vdi(t+1) using Eq.(15) (9) calculate the value of ndi(t+1) by Eq.(17) (10) randomly select ndi(t+1) items fromcluster xdi(t) and allocate them to new cluster xdi(t+1) (11)end for (12)//Reinsertion phase重新插入階段 (13)for each data Oj that have not been selected in the inheritance phase do (14) allocate data Oj to an existing cluster with the closest center (15)output: solution Xi(t+1)

5 仿真實(shí)驗(yàn)

5.1 實(shí)驗(yàn)環(huán)境配置

本節(jié)利用UCI數(shù)據(jù)庫[32]中13種實(shí)際的測試數(shù)據(jù)集對(duì)算法性能進(jìn)行仿真測試，所選取的測試數(shù)據(jù)集涵蓋了低、中和高維度的數(shù)據(jù)實(shí)例，后文中首先描述了所選的13種經(jīng)典數(shù)據(jù)集的特征，然后同另外4種啟發(fā)式數(shù)據(jù)聚簇算法進(jìn)行仿真測試。

本文利用提出的算法求解了不同測試數(shù)據(jù)集的聚簇問題，算法利用C語言編程實(shí)現(xiàn)，硬件環(huán)境為2.2 GHz的Intel CPU。算法運(yùn)行中的固定參數(shù)設(shè)置如下：數(shù)據(jù)對(duì)象數(shù)量s設(shè)置為20，K的初始值Kinitial設(shè)置為10，G的初始值Ginitial設(shè)置為1，G的終止值Gend設(shè)置為0.5，算法的最大迭代次數(shù)設(shè)置為200。同時(shí)，兩種基于時(shí)間的線性函數(shù)用于降低參數(shù)G和K的值。

5.2 性能評(píng)價(jià)指標(biāo)

對(duì)于每一個(gè)數(shù)據(jù)集，實(shí)驗(yàn)首先記錄了算法聚簇后的分類失誤比率指標(biāo)CEP，該指標(biāo)表示測試集中錯(cuò)誤分類的數(shù)據(jù)比率，其計(jì)算方法如下：首先，對(duì)全部測試數(shù)據(jù)進(jìn)行分類，并統(tǒng)計(jì)錯(cuò)誤分類的數(shù)據(jù)量。由于對(duì)于特定的測試數(shù)據(jù)集，每個(gè)數(shù)據(jù)實(shí)例的實(shí)際分類標(biāo)簽是可以提前知道的。然后，錯(cuò)誤分類的數(shù)據(jù)量與測試集中總的數(shù)據(jù)實(shí)例數(shù)量相除，并乘以100即可得到百分比，即計(jì)算方式為

除此之外，進(jìn)一步引入聚類內(nèi)的距離之和度量聚類算法的性能，該指標(biāo)表示一個(gè)聚類內(nèi)的數(shù)據(jù)矢量與聚類質(zhì)心間的距離。聚類內(nèi)距離之和越小，表明數(shù)據(jù)聚類結(jié)果的質(zhì)量越高。定義為

其中，zj表示聚類j的質(zhì)心質(zhì)量，xp表示第p個(gè)數(shù)據(jù)矢量，d表示每個(gè)質(zhì)心矢量的特征量，nj表示聚類j的數(shù)據(jù)矢量數(shù)量，Cj表示形成聚類j的數(shù)據(jù)矢量的子集。

5.3 數(shù)據(jù)集描述

本文所選取的13種測試數(shù)據(jù)集為機(jī)器學(xué)習(xí)領(lǐng)域最為常用的測試數(shù)據(jù)，表1顯示了測試數(shù)據(jù)集的特征，包括數(shù)據(jù)實(shí)例數(shù)量、數(shù)據(jù)特征數(shù)量以及分類數(shù)量。每一個(gè)數(shù)據(jù)集中，隨機(jī)選擇75%的數(shù)據(jù)用于訓(xùn)練集的訓(xùn)練過程，剩余25%的數(shù)據(jù)用于算法的測試過程。表1同時(shí)給出了訓(xùn)練和測試集的數(shù)量。訓(xùn)練階段后，可以獲得聚簇中心作為從訓(xùn)練集中提煉出來的知識(shí)而用于分類測試集。

表1 13種測試數(shù)據(jù)集的特征

5.4 結(jié)果分析

算法在13種經(jīng)典的測試數(shù)據(jù)集中進(jìn)行了測試，其生成的計(jì)算結(jié)果與以下幾種典型的元啟發(fā)式算法進(jìn)行了性能對(duì)比，包括：標(biāo)準(zhǔn)引力搜索算法GSA[33]、智能蜂群算法ABC[34]、粒子群算法PSO[35]以及螢火蟲算法FA[36]，對(duì)比結(jié)果見表2。

表2 算法的分類失誤比率

表2表明，在所有測試數(shù)據(jù)集，本文算法GGSA優(yōu)于PSO和標(biāo)準(zhǔn)GSA，在其中10個(gè)數(shù)據(jù)集，GGSA優(yōu)于ABC，而在其它3種數(shù)據(jù)集中，ABC和GGSA幾乎表現(xiàn)出相同的性能。對(duì)比FA算法，GGSA也得到了可接受的結(jié)果，僅在數(shù)據(jù)集Cancer、Heart和Thyriod中，F(xiàn)A要優(yōu)于GGSA。而且，對(duì)于所有測試集，GGSA的平均CEP為8.9%，而FA為11.36%，標(biāo)準(zhǔn)GSA為11.41%，ABC為13.13%，PSO為15.99%。由表2的最后一行的平均值可以看到，本文的GGSA算法是5種元啟發(fā)式算法中排序第一的算法。

表3為5種數(shù)據(jù)聚類算法在所有數(shù)據(jù)集中的聚類內(nèi)距離測試結(jié)果。所記錄的值為20次仿真實(shí)驗(yàn)測試得到的平均值。可以看到，本文基于分組模型的引力搜索機(jī)制下的數(shù)據(jù)聚類算法得到的聚類內(nèi)距離的均值是小于其它4種算法的，且在不同的測試數(shù)據(jù)集中得到的結(jié)果均體現(xiàn)出了一定的優(yōu)勢，這說明算法在處理不同屬性和不同分類量的數(shù)據(jù)集時(shí)具有很好的適應(yīng)性和魯棒性。其它4種算法之間，并沒有體現(xiàn)出在不同測試數(shù)據(jù)集下的絕對(duì)性能優(yōu)勢，即在不同數(shù)據(jù)集上得到的聚類距離的差距是不一致的。如FA算法在Balance、Cancer-Int、Thyroid等數(shù)據(jù)集中是除了GGSA算法之外表現(xiàn)最好的一種算法，但它在其它數(shù)據(jù)集中得到的測試結(jié)果不是最優(yōu)的，這說明算法在處理具有不同特征的數(shù)據(jù)時(shí)并不能保證性能的穩(wěn)定性。

表3 算法的聚類內(nèi)距離度量

6 結(jié)束語

為求解數(shù)據(jù)聚簇問題，提出一種基于分組的引力搜索算法GGSA。該算法在解決數(shù)據(jù)聚簇上的優(yōu)勢在于：首先，基于分組模型的解的編碼方式最大限度降低的編碼的冗余度，使數(shù)據(jù)聚簇問題的相關(guān)結(jié)構(gòu)與引力搜索空間中解間映射關(guān)系得到了最好的表達(dá)；其次，算法中搜索代理的位置與速度更新機(jī)制與標(biāo)準(zhǔn)GSA是類似的，但利用了基于差異的分組因子替換了標(biāo)準(zhǔn)GSA中的算術(shù)操作符。聚簇差異性度量的使用允許算法以聚簇操作代替原始的標(biāo)量操作。通過仿真實(shí)驗(yàn)的評(píng)估，驗(yàn)證了基于分組的GSA算法在分類失誤比率指標(biāo)上要優(yōu)于同類型的幾種數(shù)據(jù)聚簇算法。