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

賈旋，周治平

(江南大學 物聯網工程學院，江蘇 無錫 214122)

?

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

賈旋，周治平

(江南大學 物聯網工程學院，江蘇 無錫 214122)

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

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

中文引用格式：賈旋，周治平. 一種基于模板縮減的新型粒子群遺傳聚類算法[J]. 智能系統學報， 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.

聚類是將一批現實或抽象的數據對象分組成為多個類或簇的過程。隨著計算機技術、網絡技術和信息技術的迅速發展, 龐大、海量、復雜、高維的數據信息充斥在當前世界的各個領域。如何處理這些數據并從中快速、準確地提取有益的信息, 越來越引起人們的普遍關注。面對這些大規模復雜數據，聚類算法需要具有可伸縮性、處理不同類型的數據、發現任意形狀的簇、處理高維數據等能力。而對于這些問題與要求，傳統的聚類分析方法已然顯得無力。

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

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

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

1.1粒子群聚類算法

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

(1)

(2)

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

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

(3)

(4)

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

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

1.2模板縮減

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

1.2.1靜態模板檢測

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

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

(5)

式中：μ和σ分別表示簇Ci中所有模板到簇心的平均距離和標準偏差。

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

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

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

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

(6)

(7)

1.3廣義遺傳算法

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

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

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

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

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

(8)

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

(9)

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

該聚類算法的實現過程如下：

Begin

Initialize

輸入樣本數據集X,聚類數據k;

設置粒子群數m,替換粒子數C;

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

while 不滿足停止準則

根據式(1)計算每個粒子適應度

更新Pid和Pgd；

for i=1:M-C

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

根據最近鄰法則劃分;

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

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

end for

end for

for i=1:C

在區間[1,n-l]中生成一個隨機整數l；

選擇第l代種群與當種群進行交叉、變異操作生成第n+1代種群；

end for

end while

輸出最優Pgd對應的廣義遺傳算法種群中的最優分類；

End

1.5計算復雜度分析

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

2　實驗結果分析

2.1實驗環境

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

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

表1　實驗數據集的特性

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

2.2實驗分析

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

各數據集實驗結果如表2所示。

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

圖1　周期執行時間圖Fig.1　The graph of cycle time

圖2　目標函數收斂圖Fig.2　The convergence graph of objective function

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

對表2的數據具體分析，可以看出：

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

表2　各數據集實驗結果

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

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

3　結束語

隨著規模龐大、結構復雜數據的不斷出現，對其聚類往往需要耗費大量的時間。但是當今大量文獻研究往往都著眼于提高其準確度，很少針對聚類速度。本文基于模板縮減的粒子群聚類算法，將其與一種改進的廣義遺傳算法充分結合，不僅能夠提高種群的多樣性而且能夠對模板縮減過程中必要的信息進行存儲保護。實驗表明，本文算法能夠在基本不降低聚類精度的前提下，顯著地縮短聚類時間。但是本文基本模板縮減的粒子群聚類算法，精度不可避免帶有些許的損失，特別是當類數增加時誤差會較大。對于這一問題，應該是還沒有將遺傳算法的全部優點挖掘出來，下一步還有待改進。

[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]秦全德, 李麗, 程適, 等. 交互學習的粒子群優化算法[J]. 智能系統學報, 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]張亮, 楊國正. 一種變維搜索的量子粒子群優化聚類算法[J]. 小型微型計算機系統, 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年生，教授，博士，主要研究方向為智能檢測、自動化裝置、網絡安全等。

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

網絡出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20160315.1051.006.html

2015-07-29.網絡出版日期：2016-03-15.

江蘇省自然科學基金項目(BK20131107)；江蘇省產學研聯合創新資金-前瞻性聯合研究項目(BY2013015-33).

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

TP18

A

1673-4785(2016)04-0561-06