一種基于模板縮減的新型粒子群遺傳聚類算法

賈旋，周治平

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無(wú)錫 214122)

?

一種基于模板縮減的新型粒子群遺傳聚類算法

賈旋，周治平

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無(wú)錫 214122)

針對(duì)群聚類算法的速度問(wèn)題，提出一種基于模板縮減法加速的新型粒子群廣義遺傳(PSO-GGA)聚類算法。為了充分地同模板縮減法相結(jié)合，該算法采用一種廣義遺傳算法與粒子群算法串行使用，既能增加種群多樣性，又能對(duì)模板縮減操作中需要保護(hù)的模板進(jìn)行儲(chǔ)存。同時(shí)，對(duì)每個(gè)周期替換粒子數(shù)量采用一種遞增策略來(lái)充分吸取粒子群快速尋優(yōu)和遺傳算法搜索空間大的特性。實(shí)驗(yàn)表明：對(duì)8個(gè)數(shù)據(jù)集進(jìn)行測(cè)試，該算法能夠在基本不降低聚類品質(zhì)的基礎(chǔ)上，顯著地縮短聚類時(shí)間。

模板縮減；粒子群；廣義遺傳算法；聚類

中文引用格式：賈旋，周治平. 一種基于模板縮減的新型粒子群遺傳聚類算法[J]. 智能系統(tǒng)學(xué)報(bào)， 2016, 11(4): 561-566.

英文引用格式：JIA Xuan, ZHOU Zhiping. A novel PSO-GGA for clustering based on pattern reduction[J]. CAAI Transactions on Intelligent Systems, 2016, 11(4): 561-566.

聚類是將一批現(xiàn)實(shí)或抽象的數(shù)據(jù)對(duì)象分組成為多個(gè)類或簇的過(guò)程。隨著計(jì)算機(jī)技術(shù)、網(wǎng)絡(luò)技術(shù)和信息技術(shù)的迅速發(fā)展, 龐大、海量、復(fù)雜、高維的數(shù)據(jù)信息充斥在當(dāng)前世界的各個(gè)領(lǐng)域。如何處理這些數(shù)據(jù)并從中快速、準(zhǔn)確地提取有益的信息, 越來(lái)越引起人們的普遍關(guān)注。面對(duì)這些大規(guī)模復(fù)雜數(shù)據(jù)，聚類算法需要具有可伸縮性、處理不同類型的數(shù)據(jù)、發(fā)現(xiàn)任意形狀的簇、處理高維數(shù)據(jù)等能力。而對(duì)于這些問(wèn)題與要求，傳統(tǒng)的聚類分析方法已然顯得無(wú)力。

為解決這些問(wèn)題，研究者們嘗試引入各種群智能算法，其中粒子群優(yōu)化算法(PSO)逐漸引起人們的注意，并在聚類分析中取得了比傳統(tǒng)方法更好的效果。從粒子群算法被提出用來(lái)解決聚類問(wèn)題開(kāi)始，大批學(xué)者開(kāi)展了對(duì)它的研究，如文獻(xiàn)[1]提出了一種結(jié)合自適應(yīng)慣性權(quán)重參數(shù)和無(wú)線折疊迭代混沌映射的混沌粒子群的模糊聚類方法；文獻(xiàn)[2]中結(jié)合Newton移動(dòng)規(guī)則提出了重心加速粒子群算法；文獻(xiàn)[3]提出一種多優(yōu)量子粒子群算法，以解決基因表達(dá)數(shù)據(jù)的聚類問(wèn)題；文獻(xiàn)[4]利用一種交互學(xué)習(xí)策略在兩個(gè)種群中確定學(xué)習(xí)種群與被學(xué)習(xí)種群來(lái)增加粒子群算法的全局搜索能力；文獻(xiàn)[5]將基于K均值的粒子群聚類算法應(yīng)用于無(wú)線傳感網(wǎng)能源節(jié)約的管理策略中；文獻(xiàn)[6]將粒子群聚類算法應(yīng)用于多級(jí)閾值轉(zhuǎn)化法中，以解決傳統(tǒng)計(jì)算復(fù)雜度指數(shù)性增長(zhǎng)問(wèn)題。

隨著研究的不斷深入，基于粒子群的聚類算法越來(lái)越成熟、可伸縮性越來(lái)越強(qiáng)、可處理的數(shù)據(jù)類型也越來(lái)也多、使用場(chǎng)合越來(lái)越廣。同時(shí)，聚類精度也得到了極大的提高，已基本達(dá)到臨界值，很難再有較大的提升。但是，這些研究也大都著眼于此，少有文獻(xiàn)以提升聚類效率、降低聚類時(shí)間為目標(biāo)，以期在處理大規(guī)模數(shù)據(jù)時(shí)也能將聚類時(shí)間控制在一個(gè)可接受的范圍內(nèi)。以上述文獻(xiàn)為例，都是結(jié)合了新型策略的粒子群聚類算法，以提高聚類精度、擴(kuò)大適應(yīng)場(chǎng)景為目標(biāo)，都未考慮聚類時(shí)間。針對(duì)這一問(wèn)題，本文采用一種基于粒子群的模板縮減[4]法，用來(lái)發(fā)現(xiàn)并移除那些在之后的聚類周期中不會(huì)或者小概率會(huì)改變簇的模板，以此來(lái)提升聚類效率，減小聚類算法周期的執(zhí)行時(shí)間。但是在此過(guò)程中不可避免地會(huì)使聚類精度有所下降，對(duì)此本文采用一種能夠充分結(jié)合該模板縮減法的廣義遺傳算法來(lái)提升降低的精度。以期在基本不降低聚類品質(zhì)的前提下，縮短大量的聚類時(shí)間。

1　基于模板縮減的粒子遺傳聚類算法

1.1粒子群聚類算法

在粒子群聚類算法中，每一個(gè)聚類解可以看做搜索空間中的一個(gè)粒子。首先，生成初始群體，即在可行解空間中隨機(jī)初始化m個(gè)粒子，每個(gè)粒子代表一種可行解，并由目標(biāo)函數(shù)式(1)確定一個(gè)適應(yīng)度值。

(1)

(2)

式中：n為數(shù)據(jù)個(gè)數(shù)，k為聚簇的個(gè)數(shù)，d為數(shù)據(jù)的維數(shù)，xi為第i個(gè)數(shù)據(jù)點(diǎn)，zi為第i個(gè)簇Ci的中心，wij為數(shù)據(jù)xi對(duì)簇Cj的隸屬度值。

每個(gè)粒子都將在解空間中運(yùn)動(dòng)，并由運(yùn)動(dòng)速度決定其飛行方向和距離。粒子通過(guò)式(3)、(4)不斷調(diào)整自己的速度Vi和位置Xi來(lái)搜索新解。同時(shí)每個(gè)粒子自己搜索到的最優(yōu)解Pid，以及整個(gè)粒子群經(jīng)歷過(guò)的最優(yōu)位置Pgd。

(3)

(4)

粒子通過(guò)不斷地學(xué)習(xí)更新，最終飛至解空間中最優(yōu)解所在的位置，搜索過(guò)程結(jié)束，最后輸出的Pgd就是全局最優(yōu)解。

在粒子群聚類的每個(gè)周期中，粒子調(diào)整完速度和位置后，還需要通過(guò)最近鄰聚類對(duì)模板進(jìn)行分類，從而得到目標(biāo)函數(shù)中的參數(shù)為wij。對(duì)于最近鄰聚類而言，首先需要計(jì)算樣本到每個(gè)簇心的距離，再取最小值以判斷出模板所屬簇，這一步需要耗費(fèi)大量時(shí)間。但是，在不斷的搜索過(guò)程中，必然會(huì)存在一些“靜態(tài)模板”在搜索前期就處于“最優(yōu)”狀態(tài)，即在之后搜索過(guò)程中不改變其所屬簇的模板。如果找到這些“靜態(tài)模板”，并將其移除以避免再次的最近鄰聚類就可以節(jié)省大量的聚類時(shí)間。

1.2模板縮減

模板縮減就是發(fā)現(xiàn)并壓縮靜態(tài)模板[7]的過(guò)程，而所謂的靜態(tài)模板就是那些在之后的聚類過(guò)程中基本不會(huì)改變其所在簇的模板。這種模板縮減的方法，可分為兩步：靜態(tài)模板檢測(cè)和靜態(tài)模板壓縮。

1.2.1靜態(tài)模板檢測(cè)

文獻(xiàn)[8]采用兩種方法結(jié)合的形式來(lái)檢測(cè)模板是否有著大概率在下一周期聚類時(shí)不改變其所在簇：1)模板到其簇心的距離在一個(gè)很小的范圍內(nèi)；2)在幾個(gè)連續(xù)的迭代周期內(nèi)不改變簇的模板。

1)通過(guò)判斷模板到簇心的距離來(lái)確定靜態(tài)模板。準(zhǔn)確地說(shuō)，該方法只認(rèn)定每個(gè)簇中到簇心的距離小于γ的模板是靜態(tài)的。

(5)

式中：μ和σ分別表示簇Ci中所有模板到簇心的平均距離和標(biāo)準(zhǔn)偏差。

通常來(lái)說(shuō)，γ不僅可以用來(lái)作為一個(gè)閾值來(lái)篩選靜態(tài)模板，而且還是一個(gè)用來(lái)平衡準(zhǔn)確度和算法收斂速度的參數(shù)。

2)通過(guò)判斷模板連續(xù)保持在相同簇的次數(shù)Sij來(lái)確定靜態(tài)模板。直觀上來(lái)講，一個(gè)靜態(tài)模板連續(xù)保持在同一個(gè)簇的迭代周期數(shù)Smax越大，則該模板是靜態(tài)模板的可能性就越高。而設(shè)定多大的Smax作為閥值就取決于聚類算法的收斂速度或者是最終解的質(zhì)量。

不難發(fā)現(xiàn)，對(duì)于方法2，需要對(duì)周期的每個(gè)粒子參數(shù)樣本分類數(shù)據(jù)進(jìn)行儲(chǔ)存，才可以計(jì)算連續(xù)次數(shù)Sij。假設(shè)Smax=3,就至少需要參考之前兩個(gè)迭代周期中的樣本分類數(shù)據(jù)，才可以判斷出哪些模板可視為“靜態(tài)模板”。對(duì)于文獻(xiàn)[8]的方法來(lái)說(shuō)，Sij的儲(chǔ)存不止麻煩而且對(duì)于算法而言沒(méi)有任何幫助，只會(huì)增加算法的復(fù)雜度。但是本文基于廣義遺傳算法的粒子群聚類算法就可以很好地解決這一問(wèn)題。對(duì)于廣義遺傳算法而言，本身就有保護(hù)分類數(shù)據(jù)的特點(diǎn)，而且還可以通過(guò)遺傳算法來(lái)增加其樣本多樣性。因此，本文算法不僅可以對(duì)分類的數(shù)據(jù)用一種新型的方式進(jìn)行儲(chǔ)存，還可以很好地利用這些數(shù)據(jù)產(chǎn)生新的遺傳粒子以替換適應(yīng)值低的PSO粒子。1.2.2靜態(tài)模板壓縮

靜態(tài)模板壓縮操作是為了記錄、傳送靜態(tài)模板的信息給后期的其他操作，以確保沒(méi)有多余的計(jì)算被執(zhí)行。該操作的數(shù)學(xué)表達(dá)形式如式(6)所示。

(6)

(7)

1.3廣義遺傳算法

采用模板壓縮方法減少計(jì)算時(shí)間的過(guò)程中，不可避免地會(huì)導(dǎo)致聚類精度的下降，也就是說(shuō)會(huì)比傳統(tǒng)PSO聚類更容易陷入“早熟”收斂。文獻(xiàn)[8]采用一種“多星”操作來(lái)解決這一問(wèn)題，即通過(guò)隨機(jī)選取種群中粒子相互交叉產(chǎn)生新的粒子，類似于一種簡(jiǎn)易的“遺傳”算法。但是，在粒子群尋優(yōu)的過(guò)程中，所有粒子都不斷地向著個(gè)體最優(yōu)解和全局最優(yōu)解靠近。也就是說(shuō)，在迭代了許多代后，整個(gè)種群可能已經(jīng)大部分收斂，但是還沒(méi)有得到穩(wěn)定的全局最優(yōu)解。此時(shí)整個(gè)種群的平均適應(yīng)度值較高，而且最優(yōu)個(gè)體的適應(yīng)度值與全體適應(yīng)度均值間的差別不大，即使在種群中隨機(jī)選取粒子進(jìn)行交叉產(chǎn)生新的粒子，也沒(méi)有足夠的力量推動(dòng)種群的尋優(yōu)找到最優(yōu)解，從而陷入到“局部”最優(yōu)。

為了解決這一問(wèn)題，本文更好地吸取了遺傳算法的優(yōu)點(diǎn)，修改了一種廣義遺傳算法來(lái)增加樣本多樣性，提高算法跳出“局部”最優(yōu)的能力。考慮到在自然演化中，近親繁殖往往不利于種群的繁榮，而遠(yuǎn)親雜交往往會(huì)培育出更優(yōu)良的品種；變異作為一種重要的進(jìn)化方式，是保持物種多樣性的必要手段。因此，我們首先對(duì)每個(gè)迭代周期產(chǎn)生的分類數(shù)據(jù)進(jìn)行儲(chǔ)存，以擴(kuò)大遺傳種群的數(shù)量，因?yàn)橹挥蟹浅４蟮姆N群量才能更好地進(jìn)行遠(yuǎn)親雜交。再?gòu)闹羞x取一組種群粒子與當(dāng)前的“優(yōu)質(zhì)”粒子進(jìn)行交叉、變異，生成新的粒子。此處，通過(guò)系數(shù)l來(lái)避免“近親”繁殖，即不選擇近代生成的種群粒子。該算法通過(guò)不斷地補(bǔ)充、記錄、生成新的種群粒子，在不斷尋優(yōu)的過(guò)程中，也增加了粒子群聚類的樣本多樣性。

1.4基于模板縮減的新型粒子群遺傳聚類算法

該算法創(chuàng)新性地將一種修改后的新型廣義遺傳算法同基于模板縮減的粒子群聚類算法相結(jié)合，在充分同模板縮減相結(jié)合的同時(shí)，也提高了樣本多樣性。

基于模板縮減的粒子群聚類算法，其對(duì)于初始中心的敏感性不僅沒(méi)有降低反而會(huì)更加敏感，將嚴(yán)重導(dǎo)致聚類精度的不穩(wěn)定。本文通過(guò)選取10%的樣本進(jìn)行簡(jiǎn)單的k-means聚類，來(lái)初始簇心。同時(shí)，為了更好地提高由模板縮減而降低的聚類精度，本文在聚類迭代中并行k-means，即在重新分配完粒子后，使用式(8)來(lái)重新計(jì)算簇心。

(8)

考慮到迭代前期粒子群聚類不需要太多的遺傳粒子，而后期特別是當(dāng)粒子群聚類陷入局部最優(yōu)時(shí)往往需要較大量的遺傳粒子來(lái)增加其調(diào)出陷阱的能力。因此，對(duì)替換粒子量C采用一種遞增策略來(lái)解決這一矛盾。

(9)

式中：prN代表壓縮后模板的數(shù)量，PN表示模板的總數(shù)量。Φmin表示沒(méi)有模板縮減時(shí)，最小替換個(gè)數(shù)；Φmax表示最大可以增加的替換個(gè)數(shù)；

該聚類算法的實(shí)現(xiàn)過(guò)程如下：

Begin

Initialize

輸入樣本數(shù)據(jù)集X,聚類數(shù)據(jù)k;

設(shè)置粒子群數(shù)m,替換粒子數(shù)C;

選取10%的X,初始化種群P(0);

while 不滿足停止準(zhǔn)則

根據(jù)式(1)計(jì)算每個(gè)粒子適應(yīng)度

更新Pid和Pgd；

for i=1:M-C

根據(jù)式(3)、(4)更新粒子i的速度和位置；

根據(jù)最近鄰法則劃分;

保存到廣義遺傳算法的種群中；

根據(jù)式(8)重新計(jì)算聚類中心；

end for

end for

for i=1:C

在區(qū)間[1,n-l]中生成一個(gè)隨機(jī)整數(shù)l；

選擇第l代種群與當(dāng)種群進(jìn)行交叉、變異操作生成第n+1代種群；

end for

end while

輸出最優(yōu)Pgd對(duì)應(yīng)的廣義遺傳算法種群中的最優(yōu)分類；

End

1.5計(jì)算復(fù)雜度分析

從1.4中的算法流程中可以看出，每個(gè)周期需要進(jìn)行以下5步計(jì)算：適應(yīng)度計(jì)算、粒子更新、最近鄰劃分、靜態(tài)模板檢測(cè)和縮減、遺傳粒子計(jì)算。其中，適應(yīng)度計(jì)算和最近鄰劃分，由于需要對(duì)數(shù)據(jù)到各個(gè)簇心的距離，其計(jì)算復(fù)雜度最高，為O(mn′n2)；減部分，只需要對(duì)劃分后的數(shù)據(jù)進(jìn)行求平均值、比較和刪除操作，所以其計(jì)算復(fù)雜度為O(mn′n)；其余操作，可忽略不計(jì)。綜上，本文算法的計(jì)算復(fù)雜度為O(rmn′n2)，其中r表示迭代周期數(shù)，n′表示非靜態(tài)模板數(shù)?？梢钥闯?，隨著靜態(tài)模板數(shù)的增加其計(jì)算復(fù)雜度逐漸減小，從而達(dá)到了降低聚類時(shí)間的目的。

2　實(shí)驗(yàn)結(jié)果分析

2.1實(shí)驗(yàn)環(huán)境

目前，大部分對(duì)于粒子群聚類算法的改進(jìn)基本都是從適應(yīng)值函數(shù)、編碼方式、參數(shù)調(diào)整等方面著手。而本文算法，只是從模板方面著手進(jìn)行縮減，每個(gè)周期需要對(duì)多少個(gè)樣本分類對(duì)目前的粒子群改進(jìn)沒(méi)有絲毫的影響，只需要調(diào)整不同編碼方式就可以同這些改進(jìn)措施完美銜接。同時(shí)，雖然很多改進(jìn)措施是通過(guò)混合不同的策略來(lái)優(yōu)化粒子群的聚類算法，但大多都是將采用的策略同粒子群并行使用，對(duì)每個(gè)周期需要對(duì)多少個(gè)樣本進(jìn)行操作沒(méi)有要求。例如，文獻(xiàn)[9]提出的基于模糊c均值和粒子群的模糊聚類方法；文獻(xiàn)[10]提出了使用邊界約束策略的自適應(yīng)粒子群聚類；這類文獻(xiàn)，只是引入一些改進(jìn)策略混合并行使用來(lái)改善粒子群算法的一些缺陷，同樣對(duì)每個(gè)周期對(duì)多少個(gè)樣本進(jìn)行操作也沒(méi)有影響，同本文算法銜接沒(méi)有任何問(wèn)題；更典型的，像文獻(xiàn)[11]這些針對(duì)粒子群聚類算法需要預(yù)先設(shè)定聚類中心個(gè)數(shù)的問(wèn)題進(jìn)行算法改進(jìn)的策略，對(duì)粒子群算法本身沒(méi)有什么變動(dòng)，和本文算法就更談不上什么沖突了；所以，本次試驗(yàn)只采用基本的粒子群聚類(PSO)和典型的混合k-means的kmPSO[12]混合聚類算法(記為KP)進(jìn)行實(shí)驗(yàn)分析，并同文獻(xiàn)[7]的MPREPSO算法(MP)比較來(lái)測(cè)試本文算法的性能。

仿真實(shí)驗(yàn)基于MATLAB2010b平臺(tái)，計(jì)算機(jī)的硬件配置為：Intel Core i5-4200M CPU 2.5 GHz、4 GB RAM。選取UCI數(shù)據(jù)庫(kù)中的8個(gè)典型數(shù)據(jù)集在該環(huán)境下對(duì)本文和比較算法進(jìn)行測(cè)試。其中，數(shù)據(jù)集的特性如表1所示。

表1　實(shí)驗(yàn)數(shù)據(jù)集的特性

根據(jù)聚類準(zhǔn)確度、運(yùn)行時(shí)間對(duì)本文的基于模板縮減的粒子群廣義遺傳聚類算法(PR-PSO-GGA)聚類性能進(jìn)行分析比較，考慮到實(shí)驗(yàn)要求，4種基于粒子群的聚類算法參數(shù)一致，設(shè)置同文獻(xiàn)[7]相同：w=0.72，c1=c2=2。每種算法獨(dú)立運(yùn)行20次，計(jì)算各自的適應(yīng)度值、accuracy[8]、Rand Index[3]指標(biāo)和運(yùn)行時(shí)間,聚類結(jié)果如表2所示。其中，適應(yīng)度值函數(shù)由式(1)定義。

2.2實(shí)驗(yàn)分析

對(duì)于評(píng)價(jià)聚類算法的聚類品質(zhì)而言，低適應(yīng)度值一定代表著高品質(zhì)，但較高accuracy值和Rand Index值卻不一定意味著較高的品質(zhì)。因?yàn)椋诹Ｗ尤旱木垲愃惴ǘ际菄@著適應(yīng)度值在不斷地尋優(yōu)，以期找到最低的適應(yīng)度值，這就意味著適應(yīng)度值越低該聚類算法的尋優(yōu)能力越強(qiáng)，聚類算法的聚類品質(zhì)也就越高。accuracy和Rand Index指標(biāo)作為外部評(píng)價(jià)指標(biāo)和目標(biāo)函數(shù)有著密切聯(lián)系，只能大致評(píng)價(jià)聚類結(jié)果，不能完美地表現(xiàn)粒子群聚類算法尋優(yōu)能力的優(yōu)劣。因此，本文實(shí)驗(yàn)分析將根據(jù)適應(yīng)度值來(lái)評(píng)價(jià)聚類結(jié)果，聚類accuracy和Rand Index值僅作為參考數(shù)據(jù)。

各數(shù)據(jù)集實(shí)驗(yàn)結(jié)果如表2所示。

從表2中可以看出，針對(duì)不同的數(shù)據(jù)集，基于模板縮減的粒子群廣義遺傳算法的聚類時(shí)間只需要原算法20%左右的時(shí)間，對(duì)有些數(shù)據(jù)集甚至只需要10%的聚類時(shí)間。這些縮短的聚類時(shí)間一部分是由于模板縮減法移除模板降低的周期執(zhí)行時(shí)間所造成的，另一部分是由于串行了廣義遺傳算法減小了收斂周期所造成的,具體可參考圖1和圖2。

圖1　周期執(zhí)行時(shí)間圖Fig.1　The graph of cycle time

圖2　目標(biāo)函數(shù)收斂圖Fig.2　The convergence graph of objective function

從圖1可以看出，MP和本文算法開(kāi)始的周期執(zhí)行時(shí)間高于PSO和KP算法，并隨著迭代次數(shù)的增加周期執(zhí)行時(shí)間迅速減小。這說(shuō)明基于模板壓縮法粒子群算法雖說(shuō)會(huì)增加算法復(fù)雜度，但隨著算法的運(yùn)行其周期執(zhí)行時(shí)間越來(lái)越短,將大大節(jié)約總體聚類時(shí)間。從圖2可以看出，算法迅速下降到一個(gè)較低值并在短期內(nèi)完成聚類。這表明較其他算法，本文算法有著較快收斂速度和較低收斂周期。

對(duì)表2的數(shù)據(jù)具體分析，可以看出：

1)比起典型的粒子群聚類而言，本文算法不僅縮短了大量的時(shí)間，而且聚類精度也有所提高。典型的粒子群聚類算法只通過(guò)粒子間的個(gè)體協(xié)作與競(jìng)爭(zhēng)來(lái)搜索最優(yōu)解，不可避免會(huì)陷入“局部最優(yōu)”中，同時(shí)收斂周期也較長(zhǎng)。因此，雖然模板縮減法會(huì)降低聚類精度，但是本文算法通過(guò)廣義遺傳算法等一系列的措施卻可以在縮短聚類時(shí)間的基礎(chǔ)上提高其聚類精度。

表2　各數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

3)比起MP聚類算法，本文算法對(duì)于Iris等數(shù)據(jù)集既能縮短聚類時(shí)間，也能提高聚類精度。而對(duì)于數(shù)據(jù)Wall following而言雖說(shuō)本文算法降低了千分之幾的精度，但是卻縮短了1/10的聚類時(shí)間。同MP算法相比，本文算法雖然增加了廣義遺產(chǎn)算法等一系列操作，但是這些操作大多能與模板縮減法相結(jié)合且不會(huì)增加太多計(jì)算復(fù)雜性，如圖1所示，本文算法同MP算法在開(kāi)始的周期執(zhí)行時(shí)間基本相等。所以本文算法能夠在增強(qiáng)聚類精度的基礎(chǔ)上提高部分聚類速度。

總體來(lái)看，本文算法能夠在基本不降低聚類算法精度的前提下，縮短大量的聚類時(shí)間。

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

隨著規(guī)模龐大、結(jié)構(gòu)復(fù)雜數(shù)據(jù)的不斷出現(xiàn)，對(duì)其聚類往往需要耗費(fèi)大量的時(shí)間。但是當(dāng)今大量文獻(xiàn)研究往往都著眼于提高其準(zhǔn)確度，很少針對(duì)聚類速度。本文基于模板縮減的粒子群聚類算法，將其與一種改進(jìn)的廣義遺傳算法充分結(jié)合，不僅能夠提高種群的多樣性而且能夠?qū)δ０蹇s減過(guò)程中必要的信息進(jìn)行存儲(chǔ)保護(hù)。實(shí)驗(yàn)表明，本文算法能夠在基本不降低聚類精度的前提下，顯著地縮短聚類時(shí)間。但是本文基本模板縮減的粒子群聚類算法，精度不可避免帶有些許的損失，特別是當(dāng)類數(shù)增加時(shí)誤差會(huì)較大。對(duì)于這一問(wèn)題，應(yīng)該是還沒(méi)有將遺傳算法的全部?jī)?yōu)點(diǎn)挖掘出來(lái)，下一步還有待改進(jìn)。

[1]LI Chaoshun, ZHOU Jianzhong, KOU Pangao, et al. A novel chaotic particle swarm optimization based fuzzy clustering algorithm[J]. Neurocomputing, 2012, 83: 98-109.

[2]BEHESHTI Z, SHAMSUDDIN S M H. CAPSO: Centripetal accelerated particle swarm optimization[J]. Information sciences, 2014, 258: 54-79.

[3]SUN Jun, CHEN Wei, FANG Wei, et al. Gene expression data analysis with the clustering method based on an improved quantum-behaved particle swarm optimization[J]. Engineering applications of artificial intelligence, 2012, 25(2): 376-391.

[4]秦全德, 李麗, 程適, 等. 交互學(xué)習(xí)的粒子群優(yōu)化算法[J]. 智能系統(tǒng)學(xué)報(bào), 2012, 7(6): 547-553.

QIN Quande, LI Li, CHENG Shi, et al. Interactive learning particle swarm optimization algorithm[J]. CAAI transactions on intelligent systems, 2012, 7(6): 547-553.

[5]SOLAIMAN B F, SHETA A F. Energy optimization in wireless sensor networks using a hybrid K-means PSO clustering algorithm[J]. Turkish Journal of electrical engineering and computer sciences, 2015.

[6]DASH P, NAYAK M. Multilevel thresholding using PSO clustering[J]. International journal of computer applications, 2014, 97(18): 27-32.

[7]CHIANG M C, TSAI C W, YANG C S. A time-efficient pattern reduction algorithm for k-means clustering[J]. Information sciences, 2011, 181(4): 716-731.

[8]TSAI C W, HUANG K W, YANG C S, et al. A fast particle swarm optimization for clustering[J]. Soft computing, 2015, 19(2): 321-338.

[9]FILHO T M S, PIMENTEL B A, SOUZA R M C R, et al. Hybrid methods for fuzzy clustering based on fuzzy c-means and improved particle swarm optimization[J]. Expert systems with applications, 2015, 42(17/18): 6315-6328.

[10]RANA S, JASOLA S, KUMAR R. A boundary restricted adaptive particle swarm optimization for data clustering[J]. International journal of machine learning and cybernetics, 2013, 4(4): 391-400.

[11]張亮, 楊國(guó)正. 一種變維搜索的量子粒子群優(yōu)化聚類算法[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2012, 33(4): 804-808.

ZHANG Liang, YANG Guozheng. A quantum particle swarm optimization clustering algorithm using variable dimensions searching[J]. Journal of Chinese computer systems, 2012, 33(4): 804-808.

[12]AHMADYFARD A, MODARES H. Combining PSO and k-means to enhance data clustering[C]//Proceedings of International Symposium on Telecommunications. Tehran, Iran, 2008: 688-691.

賈旋，男，1992年生，碩士研究生，主要研究方向?yàn)槿斯ぶ悄芘c模式識(shí)別。

周治平，男，1962年生，教授，博士，主要研究方向?yàn)橹悄軝z測(cè)、自動(dòng)化裝置、網(wǎng)絡(luò)安全等。

A novel PSO-GGA for clustering based on pattern reduction

JIA Xuan, ZHOU Zhiping

(School of Internet of Things Engineering, Jiangnan University, Wuxi 214122, China)

To address the flaws in clustering speed, this paper proposes a novel PSO-GGA clustering algorithm based on pattern reduction. To fully combine the pattern reduction method, the algorithm uses a generalized genetic algorithm in serial to improve the particle swarm optimization algorithm. This can increase the diversity of samples and protect patterns that need to be saved for compression. At the same time, to determine the number of particles needed to replace the poor particles an incremental strategy is employed. This fully embodies the PSO’s ability for rapid search optimization and the genetic algorithm’s advantage of a large search space. The experimental results show that the clustering time only required 20 percent compared to the original algorithm without showing any obvious decline in accuracy.

pattern reduction; PSO; generalized genetic algorithm; clustering

10.11992.tis.201507026

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20160315.1051.006.html

2015-07-29.網(wǎng)絡(luò)出版日期：2016-03-15.

江蘇省自然科學(xué)基金項(xiàng)目(BK20131107)；江蘇省產(chǎn)學(xué)研聯(lián)合創(chuàng)新資金-前瞻性聯(lián)合研究項(xiàng)目(BY2013015-33).

賈旋. E-mail：6141905027@vip.jiangnan.edu.cn.

TP18

A

1673-4785(2016)04-0561-06