賈旋，周治平

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

?

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

賈旋，周治平

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

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

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

中文引用格式：賈旋，周治平. 一種基于模板縮減的新型粒子群遺傳聚類算法[J]. 智能系統(tǒng)學(xué)報， 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ù)據(jù)對象分組成為多個類或簇的過程。隨著計算機(jī)技術(shù)、網(wǎng)絡(luò)技術(shù)和信息技術(shù)的迅速發(fā)展, 龐大、海量、復(fù)雜、高維的數(shù)據(jù)信息充斥在當(dāng)前世界的各個領(lǐng)域。如何處理這些數(shù)據(jù)并從中快速、準(zhǔn)確地提取有益的信息, 越來越引起人們的普遍關(guān)注。面對這些大規(guī)模復(fù)雜數(shù)據(jù)，聚類算法需要具有可伸縮性、處理不同類型的數(shù)據(jù)、發(fā)現(xiàn)任意形狀的簇、處理高維數(shù)據(jù)等能力。而對于這些問題與要求，傳統(tǒng)的聚類分析方法已然顯得無力。

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

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

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

1.1粒子群聚類算法

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

(1)

(2)

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

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

(3)

(4)

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

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

1.2模板縮減

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

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

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

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

(5)

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

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

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

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

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

(6)

(7)

1.3廣義遺傳算法

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

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

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

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

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

(8)

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

(9)

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

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

Begin

Initialize

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

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

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

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

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

更新Pid和Pgd；

for i=1:M-C

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

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

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

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

end for

end for

for i=1:C

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

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

end for

end while

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

End

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

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

2　實驗結(jié)果分析

2.1實驗環(huán)境

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

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

表1　實驗數(shù)據(jù)集的特性

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

2.2實驗分析

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

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

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

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

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

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

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

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

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

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

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

3　結(jié)束語

隨著規(guī)模龐大、結(jié)構(gòu)復(fù)雜數(shù)據(jù)的不斷出現(xiàn)，對其聚類往往需要耗費大量的時間。但是當(dāng)今大量文獻(xiàn)研究往往都著眼于提高其準(zhǔn)確度，很少針對聚類速度。本文基于模板縮減的粒子群聚類算法，將其與一種改進(jìn)的廣義遺傳算法充分結(jié)合，不僅能夠提高種群的多樣性而且能夠?qū)δ０蹇s減過程中必要的信息進(jìn)行存儲保護(hù)。實驗表明，本文算法能夠在基本不降低聚類精度的前提下，顯著地縮短聚類時間。但是本文基本模板縮減的粒子群聚類算法，精度不可避免帶有些許的損失，特別是當(dāng)類數(shù)增加時誤差會較大。對于這一問題，應(yīng)該是還沒有將遺傳算法的全部優(yōu)點挖掘出來，下一步還有待改進(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é)報, 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]張亮, 楊國正. 一種變維搜索的量子粒子群優(yōu)化聚類算法[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年生，碩士研究生，主要研究方向為人工智能與模式識別。

周治平，男，1962年生，教授，博士，主要研究方向為智能檢測、自動化裝置、網(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é)基金項目(BK20131107)；江蘇省產(chǎn)學(xué)研聯(lián)合創(chuàng)新資金-前瞻性聯(lián)合研究項目(BY2013015-33).

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

TP18

A

1673-4785(2016)04-0561-06