基于引力搜索機(jī)制的數(shù)據(jù)聚類(lèi)及特征選擇算法

張雪峰，杜孝平，王曉健，王 哲

(1.北京賽迪工業(yè)和信息化工程監(jiān)理中心有限公司 信息化管理與咨詢(xún)部，北京 100048；2.北京航空航天大學(xué) 軟件學(xué)院，北京 100191；3.湘潭大學(xué) 信息工程學(xué)院，湖南 湘潭 411105)

0 引 言

數(shù)據(jù)聚類(lèi)是將未標(biāo)記數(shù)據(jù)集分割為相似數(shù)據(jù)點(diǎn)群組，每個(gè)群組為一個(gè)聚類(lèi)，其內(nèi)的數(shù)據(jù)點(diǎn)具有最大相似性，而不同聚類(lèi)間數(shù)據(jù)點(diǎn)差異較大[1]。數(shù)據(jù)聚類(lèi)在圖像分割[2]、機(jī)器學(xué)習(xí)[3]、文本分析、模式識(shí)別[4]等方面得到了廣泛應(yīng)用。目前數(shù)據(jù)聚類(lèi)方法有兩類(lèi)：分層式方法和分割式方法。分層式方法的主要不足是：①靜態(tài)屬性，即數(shù)據(jù)點(diǎn)的移動(dòng)受限于分配的所屬聚類(lèi)內(nèi)；②重疊聚類(lèi)無(wú)法分離。分割式方法旨在將數(shù)據(jù)劃分為不相交聚類(lèi)集，該方法也是本文采用的聚類(lèi)方法。

多數(shù)分割聚類(lèi)方法在聚類(lèi)過(guò)程中給予所有特征相同重要性。但部分特征實(shí)際是不相關(guān)或冗余的，這在處理高維度數(shù)據(jù)集聚類(lèi)時(shí)尤其無(wú)法得到較好聚類(lèi)結(jié)果[5]。因此，有必要選擇使數(shù)據(jù)聚類(lèi)更適宜的相關(guān)特征。此外，獲得最優(yōu)聚類(lèi)數(shù)量也是分割聚類(lèi)的另一挑戰(zhàn)。求解數(shù)據(jù)聚類(lèi)問(wèn)題必須同步選擇相關(guān)特征和最優(yōu)聚類(lèi)數(shù)量[6]。為解決該問(wèn)題，本文利用引力搜索機(jī)制設(shè)計(jì)一種自動(dòng)式聚類(lèi)和特征選擇算法。算法試圖在沒(méi)有聚類(lèi)數(shù)量先驗(yàn)知識(shí)前提下，同步?jīng)Q策聚類(lèi)數(shù)量和相關(guān)特征。設(shè)計(jì)了一種復(fù)合代理表示方法，用于分別對(duì)聚類(lèi)和特征進(jìn)行編碼。同時(shí)，設(shè)計(jì)了一種臨界值概念用于尋找最優(yōu)聚類(lèi)數(shù)量和特征。最后通過(guò)9種數(shù)據(jù)示例集測(cè)試驗(yàn)證了算法的有效性和可行性。

1 相關(guān)工作

本小節(jié)同時(shí)對(duì)特征選擇和聚類(lèi)問(wèn)題的相關(guān)工作做概述性研究。K-means算法是最早的一種經(jīng)典數(shù)據(jù)聚類(lèi)算法[7]，由于其最終解過(guò)多依賴(lài)于初始的質(zhì)心選擇，因此較容易存在嚴(yán)重的局部最優(yōu)情況。文獻(xiàn)[8]提出一種基于改進(jìn)和聲搜索的聚類(lèi)算法，將狀態(tài)反饋機(jī)制引入到和聲搜索算法中，通過(guò)判斷和聲記憶庫(kù)中最優(yōu)和聲和最差和聲之間的差異來(lái)動(dòng)態(tài)調(diào)整和聲記憶庫(kù)考慮概率和移動(dòng)步長(zhǎng)，使算法能夠快速地收斂到全局最優(yōu)解。文獻(xiàn)[9]提出一種基于蟻群優(yōu)化思想的聚類(lèi)和特征選擇算法FS_ACO。算法使用了基于包裝的思路，并利用連續(xù)回溯選擇技術(shù)實(shí)現(xiàn)特征提取。文獻(xiàn)[10]提出基于粒子群優(yōu)化的數(shù)據(jù)聚類(lèi)和特征選擇算法CFS_PSO。文獻(xiàn)通過(guò)隨機(jī)化特征選擇機(jī)制改進(jìn)了粒子群的搜索行為，以此選擇相關(guān)特征，而聚類(lèi)解則在所選特征的基礎(chǔ)上進(jìn)行迭代求解。文獻(xiàn)[11]提出一種模因算法NMA_CFS尋找數(shù)據(jù)聚類(lèi)和特征選擇解，利用了局部搜索機(jī)制在編碼染色體中提煉數(shù)據(jù)聚類(lèi)，但種群多樣性的不足使得算法會(huì)出現(xiàn)早熟，從而收斂在局部最優(yōu)解上。文獻(xiàn)[12]設(shè)計(jì)了一種自冶的和聲搜索聚類(lèi)算法HS_CFS，算法針對(duì)模糊聚類(lèi)對(duì)初值和聚類(lèi)中心的依賴(lài)性，采用和聲搜索尋找最佳聚類(lèi)質(zhì)心，并且改進(jìn)了和聲搜索的調(diào)音概率和隨機(jī)帶寬，加速了算法收斂。文獻(xiàn)[13]則提出改進(jìn)文化基因聚類(lèi)算法INMA_CFS，首先，基于特征與標(biāo)記間的依賴(lài)將特征按照適應(yīng)度進(jìn)行排名，使用遺傳搜索建立多標(biāo)記類(lèi)；然后使用局部?jī)?yōu)化方案向被選的特征集中增加精英樣本或刪除較弱樣本。對(duì)部分基因進(jìn)行改良，且在搜索過(guò)程中逐漸改變優(yōu)化操作的次數(shù)，從而降低了整體計(jì)算成本。以上算法并沒(méi)有考慮到數(shù)據(jù)集的變異特征，該特征是一種統(tǒng)計(jì)屬性，且極大取決于數(shù)據(jù)點(diǎn)及其特征的數(shù)量。而數(shù)據(jù)聚類(lèi)數(shù)量又直接或間接地取決于特征數(shù)量，給定數(shù)據(jù)集,其冗余特征可能影響聚類(lèi)性能。因此，識(shí)別和尋找相關(guān)特征對(duì)于數(shù)據(jù)聚類(lèi)過(guò)程具有關(guān)鍵影響。

以上研究概述表明元啟發(fā)式方法是選擇數(shù)據(jù)特征和同步數(shù)據(jù)聚類(lèi)的有效手段，但以上方法并沒(méi)有考慮到數(shù)據(jù)集的變化特點(diǎn)(統(tǒng)計(jì)屬性)，該屬性直接取決于特征選擇的數(shù)量和數(shù)據(jù)點(diǎn)。而聚類(lèi)數(shù)量直接或間接取決于特征數(shù)量，在給定數(shù)據(jù)集中的冗余特征可能一定程度上會(huì)影響聚類(lèi)算法的性能。因此，盡可能選擇相關(guān)特征剔除冗余特征是至關(guān)重要的。鑒于引力搜索算法所依賴(lài)的初始參數(shù)數(shù)量較其它智能群體算法更少，選擇該算法作為特征選擇和聚類(lèi)的優(yōu)化手段將具有一定可行性。

2 數(shù)據(jù)聚類(lèi)與引力搜索模型

2.1 數(shù)據(jù)聚類(lèi)模型

(1)每個(gè)聚類(lèi)擁有至少一個(gè)數(shù)據(jù)點(diǎn)，即Cg≠?,g=1,2,…,K；

(2)兩個(gè)不相似的聚類(lèi)不存在共同的數(shù)據(jù)點(diǎn)，即Cg∩Ch=?,g,h=1,2,…,K，且g≠h；

數(shù)據(jù)點(diǎn)是否屬于某一個(gè)特定聚類(lèi)內(nèi)取決于其相似性，該相似性通常以數(shù)據(jù)點(diǎn)與聚類(lèi)中心的歐氏距離度量。數(shù)據(jù)點(diǎn)xl與聚類(lèi)Cg的聚類(lèi)中心mg的歐氏距離定義為

(1)

2.2 引力搜索算法模型

引力搜索算法GSA[14]是基于萬(wàn)有引力和物體質(zhì)量間的相互影響發(fā)展來(lái)的一種元啟發(fā)式算法。GSA中，給定問(wèn)題的可能解考慮為代理集合，代理的質(zhì)量決定代理的性能。由于引力的影響，代理之間會(huì)相互吸引，導(dǎo)致代理會(huì)朝著擁有更大質(zhì)量的代理進(jìn)行全局移動(dòng)。問(wèn)題的解即對(duì)應(yīng)于代理在空間中的位置，適應(yīng)度函數(shù)則決定了代理的慣性質(zhì)量。GSA的執(zhí)行步驟如下：

步驟1 代理初始化。隨機(jī)初始化P個(gè)代理位置為

(2)

步驟2 適應(yīng)度評(píng)估，計(jì)算最優(yōu)適應(yīng)度。對(duì)于所有代理，計(jì)算每次迭代中的適應(yīng)度。最優(yōu)和最差適應(yīng)度的計(jì)算方法為(對(duì)于最大化問(wèn)題)

(3)

(4)

其中，fitnessi(T)表示代理i時(shí)刻T的適應(yīng)度，Best(T)和Worst(T)分別表示時(shí)刻T所有代理中的最優(yōu)適應(yīng)度和最差適應(yīng)度。

步驟3 計(jì)算引力常量。時(shí)間t時(shí)的引力常量表示為Gc(t)，定義為

(5)

式中：G0和α為常量，Tmax為最大迭代次數(shù)。

步驟4 計(jì)算代理的引力質(zhì)量。時(shí)間T時(shí)代理i的引力質(zhì)量表示為Massi(T)，基于當(dāng)前種群的適應(yīng)度進(jìn)行計(jì)算

(6)

其中

(7)

步驟5 計(jì)算代理引力和加速度。時(shí)間T時(shí)在維度D上代理i受到代理j的引力定義為

(8)

(9)

步驟6 代理位置和速度更新。下一迭代T+1時(shí)代理的位置和速度可計(jì)算為

(10)

(11)

步驟7 終止條件。重復(fù)步驟2～步驟6，直接迭代過(guò)程達(dá)到最大迭代次數(shù)為止。

3 算法詳細(xì)設(shè)計(jì)

本節(jié)的主要工作是設(shè)計(jì)一種基于引力搜索機(jī)制的數(shù)據(jù)聚類(lèi)與特征選擇算法。首先，提出一種變量合成代理表示策略使得算法可以同步尋找最優(yōu)的聚類(lèi)和特征數(shù)量，然后，為每個(gè)聚類(lèi)中心和特征選擇設(shè)計(jì)了一種臨界值機(jī)制，代理通過(guò)相應(yīng)的臨界值可以對(duì)聚類(lèi)中心和特征進(jìn)行編碼，最后通過(guò)引力搜索的迭代過(guò)程，不斷評(píng)估代理的適應(yīng)度，最終得到最優(yōu)的聚類(lèi)和特征選擇。

3.1 基于引力搜索的數(shù)據(jù)聚類(lèi)與特征選擇算法GSA_CFS

GSA_CFS算法步驟如下：

步驟1 初始化算法參數(shù)，包括代理(種群)數(shù)量、最大聚類(lèi)數(shù)量Kmax(由式(12)計(jì)算)以及最大迭代次數(shù)；

步驟2 生成每個(gè)代理，使其包括Kmax個(gè)聚類(lèi)中心數(shù)、Kmax+D個(gè)主動(dòng)臨界值，其中，D代表每個(gè)數(shù)據(jù)點(diǎn)的維度(見(jiàn)3.1.1節(jié))。初始時(shí)，聚類(lèi)中心和主動(dòng)臨界值隨機(jī)產(chǎn)生。

步驟3 重復(fù)以下步驟，直到滿(mǎn)足終止條件：

(1)通過(guò)評(píng)估選擇臨界值(見(jiàn)3.1.4節(jié))，尋找每個(gè)代理的主動(dòng)聚類(lèi)中心和特征；

(2)對(duì)于每個(gè)數(shù)據(jù)點(diǎn)，計(jì)算其與代理i的每個(gè)主動(dòng)聚類(lèi)中心的歐氏距離；

(3)分配數(shù)據(jù)點(diǎn)至距離最小的聚類(lèi)中；

(4)如果沒(méi)有數(shù)據(jù)點(diǎn)分配至一個(gè)聚類(lèi)中，則通過(guò)3.1.5節(jié)中的方法重新計(jì)算聚類(lèi)中心；

(5)利用GSA算法修改代理，通過(guò)代理的適應(yīng)度值指導(dǎo)代理搜索過(guò)程；

(6)分配選擇臨界值至每個(gè)聚類(lèi)及聚類(lèi)中的每個(gè)特征，選擇臨界值基于修改的代理進(jìn)行計(jì)算，見(jiàn)3.1.2節(jié)；

(7)基于部署(3)～(6)計(jì)算的選擇臨界值計(jì)算聚類(lèi)中心和特征的截止臨界值；

步驟4 在最后一次迭代中，最優(yōu)代理將提供最優(yōu)的特征子集和聚類(lèi)中心以及聚類(lèi)數(shù)量。

3.1.1 代理表示及初始化

算法利用一種變量合成代理表示策略對(duì)擁有不同聚類(lèi)數(shù)量的特征和聚類(lèi)中心進(jìn)行編碼。算法中，對(duì)于N個(gè)數(shù)據(jù)點(diǎn)，一個(gè)代理由維度為(Kmax+D)+(Kmax×D)的實(shí)數(shù)矢量組成，每個(gè)數(shù)據(jù)點(diǎn)擁有D個(gè)維度，最大聚類(lèi)數(shù)量為Kmax。此時(shí)，聚類(lèi)數(shù)量的上限值為Kmax，等于給定數(shù)據(jù)集中數(shù)據(jù)點(diǎn)的數(shù)量的開(kāi)方

(12)

第一部分(Kmax+D)由兩個(gè)記錄Kmax和D組成，所分配的值為[0,1]間的正實(shí)數(shù)值。第一個(gè)記錄Kmax的值用于對(duì)聚類(lèi)過(guò)程中對(duì)應(yīng)的聚類(lèi)是否被激活進(jìn)行決策，第二個(gè)記錄D的值表明是否對(duì)應(yīng)的特征被激活。第二部分(Kmax×D)表示維度D中每個(gè)維度上的Kmax個(gè)聚類(lèi)中心。在特定時(shí)間t時(shí)代理i的矢量表示為圖1所示，此時(shí)，i代表種群規(guī)模，i=1,2,…,P。

圖1 代理編碼表示

其中，mcij為代理i的第j個(gè)聚類(lèi)中心，TCij為聚類(lèi)中心mcij對(duì)應(yīng)的臨界值，TFij為代理i的每個(gè)聚類(lèi)中第j個(gè)特征的臨界值，TCij和TFij分別表示選擇活躍聚類(lèi)中心和特征時(shí)的選擇臨界值。以下以一個(gè)實(shí)例對(duì)其說(shuō)明：

實(shí)例1：令Kmax=4，D=3，即最大聚類(lèi)數(shù)量為4，空間為3維。代理編碼如圖2所示。

圖2 實(shí)例1

矢量中的前4個(gè)記錄(0.6,0.7,0.4,0.3)代表對(duì)應(yīng)4個(gè)聚類(lèi)的聚類(lèi)選擇臨界值，后面的3個(gè)記錄(0.7,0.3,0.8)表示特征選擇臨界值(由于每個(gè)聚類(lèi)擁有3個(gè)特征)。剩余的記錄表示4個(gè)聚類(lèi)中心，即(4.9,3.2,1.6)、(5.7,4.4,1.0)、(6.9,3.0,4.9)和(7.7,3.1,2.4)。

3.1.2 臨界值計(jì)算

聚類(lèi)數(shù)量本質(zhì)上對(duì)應(yīng)于給定數(shù)據(jù)集的變化。因此，對(duì)于聚類(lèi)中心的選擇臨界值定義為

(13)

對(duì)應(yīng)于每個(gè)聚類(lèi)的相同特征與所有聚類(lèi)間的關(guān)聯(lián)通過(guò)以下公式計(jì)算

(14)

式中：TFq表示數(shù)據(jù)集中第q個(gè)特征的臨界值，Vrq表示數(shù)據(jù)集中第q個(gè)特征的方差，Vrq,i表示第i個(gè)聚類(lèi)中特征q的方差，K代表數(shù)據(jù)集的聚類(lèi)數(shù)量。

TFq描述聚類(lèi)結(jié)構(gòu)中特征q的重要性均值，該值接近于1，表明當(dāng)前解中的所有聚類(lèi)在該特征下相互遠(yuǎn)離，使其可用于決定聚類(lèi)結(jié)構(gòu)。

3.1.3 截止臨界值計(jì)算

聚類(lèi)選擇的截止臨界值定義為

(15)

類(lèi)似地，特征選擇的截止臨界值定義為

(16)

算法開(kāi)始時(shí)，截止臨界值Tcutoff_center和Tcutoff_feature均設(shè)置為0.5。

實(shí)例2：實(shí)例1中代理的聚類(lèi)中心和特征選擇分別為(0.6,0.7,0.4,0.3)和(0.7,0.3,0.8)，基于以上截止臨界值概念，Tcutoff_center和Tcutoff_feature分別為0.5和0.6。

3.1.4 活躍聚類(lèi)中心及特征提取

代理中的聚類(lèi)中心和特征選擇是基于相應(yīng)的截止臨界值的，即Tcutoff_center和Tcutoff_feature。若聚類(lèi)中心的臨界值TCij大于Tcutoff_center，則相應(yīng)的聚類(lèi)中心mij被選擇分割數(shù)據(jù)集合；否則，不被選擇?；钴S聚類(lèi)中心提取規(guī)則如下：

若TCij>Tcutoff_center，則代理i的聚類(lèi)中心j是活躍的，即mij是活躍的，否則，聚類(lèi)中心j不活躍；此時(shí)，TCij代表代理i的第j個(gè)聚類(lèi)中心，Tcutoff_center為聚類(lèi)中心的截止臨界值。

類(lèi)似地，活躍特征提取規(guī)則如下：

若TFij>Tcutoff_feature，則代理i的每個(gè)聚類(lèi)中心的特征j是活躍的，否則，特征j不活躍。此時(shí)，TFij代表代理i的第j個(gè)特征，Tcutoff_feature為特征的截止臨界值。

若在GSA算法執(zhí)行過(guò)程中，不存在任一臨界值大于截止臨界值，則隨機(jī)選擇兩個(gè)臨界值并初始化至大于截止臨界值。

實(shí)例3：實(shí)例1中代理的聚類(lèi)中心和特征選擇臨界值分別為(0.6,0.7,0.4,0.3)和(0.7,0.3,0.8)，實(shí)例2中的聚類(lèi)中心截止臨界值Tcutoff_center和特征截止臨界值Tcutoff_feature分別為0.5和0.6。首先，聚類(lèi)中心臨界值用于選擇給定數(shù)據(jù)集的聚類(lèi)數(shù)量，根據(jù)以上提出的規(guī)則，僅有兩個(gè)聚類(lèi)中心的臨界值(0.6和0.7)大于0.5，且對(duì)應(yīng)的活躍聚類(lèi)中心為(4.9,3.2,1.6)和(5.7,4.4,1.0)?；钴S聚類(lèi)中心圓形區(qū)域部分，如圖3所示。然后，特征選擇臨界值用于從對(duì)應(yīng)的活躍聚類(lèi)中選擇重要的特征形式，此時(shí)，兩個(gè)特征選擇的臨界值(0.7和0.8)大于截止臨界值0.6，則在每個(gè)活躍聚類(lèi)中心中的第一個(gè)和第三個(gè)特征被選擇，即粗體部分。

圖3 實(shí)例3

3.1.5 聚類(lèi)中心確認(rèn)

有可能一個(gè)特定聚類(lèi)不存在任一數(shù)據(jù)點(diǎn)，即可能出現(xiàn)空聚類(lèi)。在一個(gè)聚類(lèi)中心超過(guò)分布點(diǎn)的邊界時(shí)會(huì)出現(xiàn)這種情況。該問(wèn)題可以通過(guò)重新對(duì)特定代理的聚類(lèi)中心進(jìn)行重新初始化解決?，F(xiàn)在分配n/K個(gè)數(shù)據(jù)點(diǎn)至每個(gè)聚類(lèi)中心，使得每個(gè)數(shù)據(jù)點(diǎn)被分配至離其最近的特定聚類(lèi)中。

實(shí)例4：考慮三維特征空間中擁有150個(gè)數(shù)據(jù)點(diǎn)的數(shù)據(jù)集，活躍聚類(lèi)數(shù)量為3。假設(shè)一個(gè)特定代理的聚類(lèi)中心為((1.9,0.52,-0.02),(5.0,4.1,0.9),(7.1,2.2,1.8))。沒(méi)有任一數(shù)據(jù)點(diǎn)分配至聚類(lèi)中心(1.9,0.52,-0.02)，由于該中心處于數(shù)據(jù)點(diǎn)分布的邊界以外?；谝陨咸岬降钠骄?jì)算公式n/K，即30個(gè)數(shù)據(jù)點(diǎn)被分配至最近的聚類(lèi)中心。因此，最新形成的聚類(lèi)中心為(4.128,3.269,1.601),(3.900,2.832,1.266)和(5.789,3.456,0.976)。

3.1.6 適應(yīng)度計(jì)算

聚類(lèi)算法的性能取決于聚類(lèi)標(biāo)準(zhǔn)。本文選擇I-index指標(biāo)對(duì)聚類(lèi)算法性能做出評(píng)估，定義為

(17)

(18)

(19)

其中，K為分割數(shù)據(jù)集所選的聚類(lèi)數(shù)量，P值取2。I-index取值越高，聚類(lèi)解的質(zhì)量越好。

本文研究了與聚類(lèi)和特定數(shù)量相關(guān)的兩個(gè)優(yōu)化問(wèn)題，并將其合并至I-index中。

問(wèn)題1：尋找最優(yōu)的聚類(lèi)數(shù)量。本文通過(guò)考慮Kmax的影響，設(shè)計(jì)了以下懲罰函數(shù)

Penality1=Kmax-K

(20)

該懲罰函數(shù)偏好更少的聚類(lèi)數(shù)量，它與(Kmax-K)成比例。

問(wèn)題2：尋找最優(yōu)的特征數(shù)量。多數(shù)的聚類(lèi)指標(biāo)沒(méi)有考慮合適的特征數(shù)量。特征選擇即從所有特征量中選擇d個(gè)特征D。保留重要特征有助于確保聚類(lèi)性能，為了降低特征數(shù)量對(duì)性能的影響，引入另一懲罰函數(shù)

(21)

結(jié)合以上定義，聚類(lèi)評(píng)估指標(biāo)可定義為

fitness=I(K)×Penality1×Penality2

(22)

(23)

3.2 復(fù)雜度分析

(1)算法的初始化時(shí)間復(fù)雜度為O(agentsize×stringlength)，agentsize為代理數(shù)量，stringlength為每個(gè)編碼代理的長(zhǎng)度，而stringlength則為O((Kmax+D)+(Kmax×D))，D為數(shù)據(jù)集的維度，Kmax為最大聚類(lèi)數(shù)量。

(2)算法的活躍聚類(lèi)和特征提取時(shí)間復(fù)雜度為O(agentsize×Kmax×D)。

(3)適應(yīng)度計(jì)算包括3步：數(shù)據(jù)點(diǎn)至不同聚類(lèi)的分配對(duì)于每個(gè)代理的時(shí)間為O(n2×Kmax)，聚類(lèi)中心更新時(shí)間為O(Kmax)，適應(yīng)度計(jì)算的時(shí)間為O(n×Kmax)。算法的步驟3需要在所有代理上遞歸，即3個(gè)子步驟乘以agentsize次。因此，步驟3的總體時(shí)間要求(計(jì)算適應(yīng)度)為agentsize×(n2×Kmax+Kmax+n×Kmax)=O(agentsize×n2×Kmax)。

(4)算法的代理質(zhì)量計(jì)算時(shí)間為O(agentsize×stringlength)。

(5)算法的加速度計(jì)算時(shí)間為O(agentsize×stringlength)。

(6)算法的代理速度和位置更新計(jì)算時(shí)間為O(agentsize×stringlength)。

綜上，若stringlength遠(yuǎn)小于n，則每次迭代的時(shí)間復(fù)雜度為O(agentsize×n2×Kmax)，算法的總體時(shí)間復(fù)雜度則為O(agentsize×n2×Kmax×Maxgen)，Maxgen即為最大代數(shù)。

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

4.1 環(huán)境搭建

GSA_CFS算法的運(yùn)行與多個(gè)不同的控制參數(shù)相關(guān)，包括：代理數(shù)量P、最大迭代次數(shù)Maxgen和引力常量G0。實(shí)驗(yàn)中設(shè)置P=30，Maxgen=100，G0=100。參數(shù)固定后，算法運(yùn)行20次并取結(jié)果的平均值進(jìn)行性能評(píng)估。引用UCI數(shù)據(jù)庫(kù)中8種實(shí)際的測(cè)試數(shù)據(jù)集對(duì)算法性能進(jìn)行仿真測(cè)試，所選取的測(cè)試數(shù)據(jù)集涵蓋了低、中和高維度的數(shù)據(jù)實(shí)例，表1描述了所選的8種經(jīng)典數(shù)據(jù)集的特征，然后同其它數(shù)據(jù)聚類(lèi)算法進(jìn)行仿真測(cè)試。

表1 測(cè)試數(shù)據(jù)集相關(guān)描述

4.2 特征選擇的相關(guān)性

所選特征的價(jià)值可以通過(guò)特征選擇的頻率和調(diào)和分值LS確定。特征選擇的頻率定義為

(24)

式中：分子表示特定特征在算法運(yùn)行中被選擇的次數(shù)，分母表示算法實(shí)施聚類(lèi)獨(dú)立運(yùn)行的次數(shù)。表2是GAS_CFS算法得到的不同數(shù)據(jù)集中特征選擇的頻率和LS情況?？梢钥吹?，對(duì)于Iris數(shù)據(jù)集，GAS_CFS算法非常頻繁地選擇了特征量3和4，該特征也擁有較高的LS值。對(duì)于Wine數(shù)據(jù)集，GAS_CFS算法頻繁選擇了特征量1、6、7和13。類(lèi)似地，對(duì)于Glass，1、3、4、7是最頻繁的特征選擇。對(duì)于Haberman，最頻繁的特征選擇是1和3。其它數(shù)據(jù)集的特征量選擇結(jié)果也可以依次看出。

表2 特征選擇頻率及其LS值

4.3 聚類(lèi)選擇的相關(guān)性

為了區(qū)分不同聚類(lèi)的重要性，需要計(jì)算所選聚類(lèi)數(shù)量的頻率及其對(duì)應(yīng)的聚類(lèi)準(zhǔn)確率Ac。聚類(lèi)頻率計(jì)算為

(25)

式中：分子表示特定聚類(lèi)在算法運(yùn)行中被選擇的次數(shù)，分母表示算法實(shí)施聚類(lèi)獨(dú)立運(yùn)行的次數(shù)。表3是GAS_CFS算法得到的不同數(shù)據(jù)集中聚類(lèi)選擇的頻率及其聚類(lèi)準(zhǔn)確率Ac的情況。對(duì)于Iris數(shù)據(jù)集，算法生成了3個(gè)聚類(lèi)，對(duì)應(yīng)的聚類(lèi)準(zhǔn)確率較高。對(duì)于Wine，算法也生成了3個(gè)聚類(lèi)。對(duì)于Glass，生成聚類(lèi)數(shù)量較為頻繁的是5和6個(gè)。對(duì)于Haberman則最為頻繁的聚類(lèi)數(shù)是2。其它數(shù)據(jù)集的聚類(lèi)量選擇結(jié)果及聚類(lèi)準(zhǔn)確率也可以依次看出。

表3 聚類(lèi)選擇頻率及聚類(lèi)準(zhǔn)確率

4.4 同類(lèi)型算法的性能對(duì)比

選擇7種典型的數(shù)據(jù)聚類(lèi)算法進(jìn)行性能對(duì)比，包括：K均值算法K-means[7]、改進(jìn)的和聲搜索聚類(lèi)算法MHSC[8]、基于蟻群優(yōu)化的特征選擇與聚類(lèi)算法FS_ACO[9]、基于粒子群優(yōu)化的特征選擇與聚類(lèi)算法CFS_PSO[10]、基于文化基因算法的聚類(lèi)算法NMA_CFS[11]、自冶和聲搜索聚類(lèi)算法HS_CFS[12]以及改進(jìn)文化基因聚類(lèi)算法INMA_CFS[13]。算法的最大迭代次數(shù)和種群規(guī)模分別設(shè)置為500和30，每個(gè)數(shù)據(jù)集按序運(yùn)行20次，聚類(lèi)質(zhì)量的度量根據(jù)平均值和標(biāo)準(zhǔn)方差進(jìn)行衡量，以展示算法的魯棒性。表4是相關(guān)對(duì)比算法的主要參數(shù)設(shè)置。

表4 對(duì)比算法的相關(guān)參數(shù)設(shè)置

表5給出所有測(cè)試數(shù)據(jù)集中算法得到的聚類(lèi)數(shù)量、特征數(shù)量及聚類(lèi)準(zhǔn)確率的均值結(jié)果。

表5 性能比較結(jié)果

對(duì)于Iris，GSA_CFS擁有最優(yōu)的聚類(lèi)準(zhǔn)確率，然后依次是HS_CFS、NMA_CFS、CFS_PSO、INMA_CFS、FS_ACO、MHSC、K-Means。GSA_CFS、INMA_CFS、NMA_CFS、CFS_PSO、FS_ACO和HS_CFS都可以正確聚類(lèi)數(shù)量和特征，而本文算法則在每次運(yùn)行過(guò)程均選擇了特征量3和4。

對(duì)于Wine，GSA_CFS獲得了比其它算法更高的聚類(lèi)準(zhǔn)確率，其聚類(lèi)數(shù)量為3，NMA_CFS、CFS_PSO、FS_ACO和HS_CFS選擇的特征數(shù)量為6，而INMA_CFS生成了7個(gè)特征，而本文算法找到的最佳特征量為4。

對(duì)于Glass數(shù)據(jù)集，所有聚類(lèi)算法產(chǎn)生的聚類(lèi)數(shù)量均為6，INMA_CFS、NMA_CFS、CFS_PSO、FS_ACO和GSA_CFS得到的特征數(shù)量均為4。然而，HS_CFS的特征數(shù)量為3，本文算法則比其它算法提供了改進(jìn)效果更好的聚類(lèi)準(zhǔn)確率。

對(duì)于Haberman數(shù)據(jù)集，本文算法的聚類(lèi)準(zhǔn)確率為62.5%，HS_CFS和NMA_CFS分別為56.9%和55.8%。FS_ACO、CFS_PSO和HS_CFS生成的特征數(shù)量為2。INMA_CFS、NMA_CFS與本文算法在聚類(lèi)和特征數(shù)量上得到相似的結(jié)果。

對(duì)于Bupa數(shù)據(jù)集，GSA_CFS算法得到的聚類(lèi)量和特征量均為2，而NMA_CFS、FS_ACO、CFS_PSO和HS_CFS提供了不同準(zhǔn)確的聚類(lèi)量。HS_CFS得到的特征量為2。顯然，本文算法在聚類(lèi)和特征量的聚類(lèi)準(zhǔn)確率要高于其它算法。

對(duì)于Cancer數(shù)據(jù)集，所有算法均得到了準(zhǔn)確的聚類(lèi)和特征，但聚類(lèi)準(zhǔn)確率上本文算法是高于其它算法的。對(duì)于Vowel和CMC數(shù)據(jù)集，GSA_CFS得到了最佳的聚類(lèi)準(zhǔn)確率，其它依次是HS_CFS、FS_ACO、CFS_PSO、NMA_CFS、INMA_CFS、MHSC以及K-Means算法。

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

設(shè)計(jì)了一種基于引力搜索機(jī)制的數(shù)據(jù)聚類(lèi)與特征選擇算法。首先，提出一種變量合成代理表示策略使得算法可以同步尋找最優(yōu)的聚類(lèi)和特征數(shù)量，然后，為每個(gè)聚類(lèi)中心和特征選擇設(shè)計(jì)了一種臨界值機(jī)制，代理通過(guò)相應(yīng)的臨界值可以對(duì)聚類(lèi)中心和特征進(jìn)行編碼，最后通過(guò)引力搜索的迭代過(guò)程，不斷評(píng)估代理的適應(yīng)度，最終得到最優(yōu)的聚類(lèi)和特征選擇。