運用分群數擺盪策略之差分自動分群演算法

Automatic Clustering Using Differential Evolution with Cluster Number Vibration Strategy

陳慎微(Shen-Wei Chen)

指導教授 ： 李維平

中原大學/商學院/資訊管理研究所/碩士(2010年)

https://doi.org/10.6840/cycu201000358

摘要

傳統的分割式分群演算法必須預先知道分群數，本研究提出以分群數擺盪策略輔助之差分自動分群演算法(V-ACDE)，可在演化過程中自動調整最佳分群數，運用分群數的擺盪策略可避免一般自動分群演算法會受到初始群數解好壞的影響，透過階段性過程中廣泛的搜尋，可避免陷入區域群數最佳解的情況發生。另外在效益上，一般的自動分群演算法將預設的解向量數設的比較大，因此在演算過程中必須花費較大的運算成本，而本研究所提出的分群數擺盪策略可以大大的減少這方面的運算成本，初始時並不需要太大的解向量數亦可達到差不多、甚至是更好的分群結果。
分群可分為硬式分群及軟式分群兩種，本研究分別依據其分群特性提出兩套演算法V-ACDE與FV-ACDE，其目的為驗證分群數擺盪策略並不因分群架構的不同而導致成效有異，另外，經由與ACDE演算法比較，證實本研究所提出的演算法具有一定程度的有效性與可靠性，在初始群數缺乏多樣性的情形下，仍然有辦法探索到較佳的分群數且適用於不同的分群架構。

關鍵字

Fuzzy c-means演算法 ； K-means演算法 ； 分割式分群演算法 ； 差分演算法

並列摘要

In this paper, an improved differential evolution algorithm (V-ACDE) with cluster number vibration strategy for automatic crisp/fuzzy clustering has been presented. The proposed algorithm needs no prior knowledge of the number of clusters of the data. Rather, it finds the optimal number of clusters on the processing with stable and fast convergence, cluster number vibration mechanism will search more possible cluster number in case of bad initial cluster number caused bad clusters. Superiority of the proposed algorithm is demonstrated by comparing it with one recently developed partitional clustering algorithm. Experimental results over four real life datasets and two artificial datasets, and the performance of proposed algorithm is mostly better than the other one.

並列關鍵字

Fuzzy c-means algorithm (FCM) ； K-means algorithm ； Partitional Clustering ； Differential Evolution (DE)

參考文獻

[54] 林豐澤，演化式計算上篇：演化式演算法的三種理論模式，智慧科技與應用統計學報，第3卷，第1期，2005年6月，29-56。

[2] J. Han and K. Micheline, Data Mining Concepts and Techniques. Morgan Kauffman, 2001.

[3] S. Bandyopadhyay, U. Maulik, “Genetic clustering for automatic evolution of clusters and application to image classification,” Pattern Recognition., vol. 35, no. 6, pp. 1197-1208, Jun. 2002.

[5] Y. Chen, K.D. Reilly, A.P. Sprague and Z. Guan, SEQOPTICS: a protein sequence clustering system, BMC Bioinform 7 (Suppl 4) (2006), p. S10.

[6] R. Krishnapuram, A. Joshi and L.Yi, “A fuzzy relative of the k-medoids algorithm with application to web document and snippet clustering,” in IEEE International Fuzzy Systems Conferences, Seoul, Korea, pp. 1281-1286, 1999.