臺灣博碩士論文加值系統

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

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.

目錄 iv
圖目錄 v
表目錄 vi
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的與問題 3
1.3 研究範圍與限制 4
1.4 研究流程 5
1.5 論文架構 6
第二章 文獻探討 7
2.1 分群技術 7
2.1.1 硬式分群定義 7
2.1.2 軟式分群定義 7
2.1.3 資料相似度 8
2.1.4 K-means演算法 8
2.1.5 Fuzzy c-means演算法 9
2.2 演化式計算 10
2.3 分群效度指標 14
2.4 自動分群相關研究 16
第三章 研究方法 18
3.1 V-ACDE演算法介紹 18
3.1.1 V-ACDE演算法流程 19
3.1.2 分群數擺盪策略 21
3.1.3 V-ACDE虛擬碼 26
3.2 針對演化過程出現不合理解的措施 26
第四章 實驗結果與分析 28
4.1 實驗環境說明 28
4.1.1 測試環境 28
4.1.2 實驗資料集說明 28
4.1.3 演算法參數設定 30
4.2 V-ACDE與ACDE的分群效益比較 – 以硬式分群架構 30
4.3 FV-ACDE與ACDE的分群效益比較 – 以軟式分群架構 34
第五章 結論與未來研究方向 39
參考文獻 40

[1] A.K. Jain and R.C. Dubes, Algorithm for Clustering Data, Prentic Hall, New Jersey, 1988.
[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.
[4] M.G.H. Omran, A. Salman, and A.P. Engelbrecht, ”Dynamic clustering using particle swarm optimization with application in unsupervised image classification,” in Proc. 5th World Enformatika Conf. (ICCI), Prague, Czech Republic, 2005.
[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.
[7] B. Mobasher, R. Cooley and J. Srivatstava, “Creating adaptive web sites through usage-based clustering of URLs,” in Knowledge and Data Enginnnring Workshop,1999.
[8] G. Gautam, and B.B. Chaudhuri, “A Novel Genetic Algorithm for Automatic Clustering.” Pattern Recognition Letters, Vol. 25, 2004, pp. 173-187.
[9] T.S. Chen, C.C. Lin, Y.H. Chiu and R.C. Chen, “Combined Density- and Constraint-based Algorithm for Clustering,” In Proceedings of 2006 International Conference on Intelligent Systems and Knowledge Engineering, 2006.
[10] S. Guha, R. Rastogi and K. Shim, “CURE: an efficient clustering algorithm for large databases,” in ACM SIGMOD International Conference on the Management of Data, Seattle, WA, USA, pp. 73-84, 1998.
[11] G. Karypis, E.-H. Han, and V. Kumar, “Chameleon: Hierarchical clustering using dynamic modeling,” IEEE Comput., vol. 32, pp. 68–74, Aug. 1999.
[12] J. MacQueen, “Some Methods for Classification and Analysis of Multivariate Observations,” Proc. Fifth Berkeley Symp. Math. Statistics and Probability, vol. 1, pp. 281-296, 1967.
[13] M. Ester, H. Kriegel, J. Sander, and X. Xu, “A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases,” Proc. ACM SIGKDD Int'l Conf. Knowledge Discovery and Data Mining, pp. 226-231, 1996.
[14] M. Ankerst, M. Breunig, H.-P. Kriegel, and J. Sander, “OPTICS: Ordering Points To Identify the Clustering Structure,” Proc. 1999 ACM Special Interest Group on Management of Data, pp. 49–60, 1999.
[15] W. Wang, J. Yang, and R.R. Muntz, "Sting: A Statistical Information Grid Approach to Spatial Data Mining," Proc. 23rd Int'l Conf. Very Large Databases, Morgan Kaufmann, 1997, pp. 186-195.
[16] G. Sheikholeslami, S. Chatterjee, and A. Zhang, “WaveCluster: A Multi-Resolution Clustering Approach for Very Large Spatial Databases,” Proc. Very Large Date Bases Conf., pp. 428-439, Aug. 1998.
[17] R. Aggrawal et al., "Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications," Proc. ACM SIGMOD Int'l Conf. Management of Data, ACM Press, 1998, pp. 94-105.
[18] A.K. Jain, M.N. Murty, and P.J. Flynn, “Data clustering: A review,” ACM Comput. Surv., vol.31, no. 3, pp. 264-323, Sep. 1999.
[19] H.-P. Schwefel, Numerical Optimization of Computer Models. Chichester: Wiley, 1981.
[20] S. Das, A. Konar, U.K. Chakraborty, “Automatic Fuzzy Segmentation of Images with Differential Evolution”, 2006 IEEE Congress on Evolutionary Computation , Sheraton Vancouver Wall Centre Hotel, Vancouver, BC, Canada July 16-21, 2006.
[21] S. Das, A. Abraham, A. Konar, “Automatic Clustering Using an Improved Differential Evolution Algorithm,” IEEE Trans. Syst, Man Cybernetics, Part A, vol. 38 no. 1, pp. 218-237, 2008.
[22] Y. Chen, C. Tang, J. Zhu, C. Li, S. Qiao, R. Li, J. Wu, “Clustering Without Prior Knowledge Based on Gene Expression Programming,” Proceedings of the Third International Conference on Natural Computation, Vol. 3, pp. 451-455, 2007.
[23] S. Das, A. Abraham, and A. Konar, “Automatic kernel clustering with a multi-elitist particle swarm optimization algorithm,” Pattern Recognition Letters, vol. 29, Issue 5, pp. 688-699, 2008.
[24] Y. Liu, M. Ye, J. Peng, H. Wu, “Finding the Optimal Number of Clusters Using Genetic Algorithms,” Cybernetics and Intelligent Systems, pp. 1325-1330, 2008.
[25] S. Saha, S. Bandyopadhyay, “A new point symmetry based fuzzy genetic clustering technique for automatic evolution of clusters,” Information Sciences: an International Journal, vol. 2179, Issue. 19, pp. 3230-3246, Sep. 2009.
[26] D. Kundu, K. Suresh, S. Ghosh, S. Das, A. Abraham, Y. Badr, “Automatic Clustering Using a Synergy of Genetic Algorithm and Multi-objective Differential Evolution,” Proceedings of the HAIS, 4th International Conference, pp. 177-186, 2009.
[27] J. Handl and J. Knowles. Multiobjective clustering with automatic determination of the number of clusters. Technical Report TR-COMPSYSBIO-2004-02, UMIST, Manchester, UK, 2004.
[28] R. Storn and K. Price. “Differential evolution-A simple and efficient heuristic for global optimization over continuous spaces,” J.Glob.Optim., vol. 11, no. 4, pp.341-359, Dec. 1997.
[29] M.M. Ali, and A. Torn, ”Population set-based global optimization algorithms:some modications and numerical studies.” Comput. Oper: Res., vol.31, issue 10, pp. 1703-1725, Sep. 2004.
[30] S. Paterlinia and T. Krink, “Differential evolution and particle swarm optimization in partional clustering,” Comput. Stat. Data Anal., vol.50, no.5, pp. 1220-1247, Mar. 2006.
[31] S. Paterlini and T. Krink, “High performance clustering with differential evolution,” in Proc. IEEE Congr. on Evolutionary Computation (CEC’2004), pp. 2004–2011, 2004.
[32] S. Bandyopadhyay and U. Maulik, “An Evolutionary Technique Based on K-Means Algorithm for Optimal Clustering in RN,” Information Sciences-Applications: An Int’l J., vol. 146, pp. 221-237, Oct. 2002.
[33] R. Storn and K. Price, “Minimizing the real function of the ICEC'96 contest by differential evolution,” in Proc. IEEE Conf. Evolutionary Computation Nagoya, Japan, 1996, pp. 842-844.
[34] R. Storn, K. Price, “Differential evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces”, Journal of Global Optimization, vol. 11, Issue. 4, pp. 341-359, 1997.
[35] M.G.H. Omran, A.P. Engelbrecht, A. Salman, “Differential Evolution Methods for Unsupervised Image Classification,” Proceedings of the Seventh Congress on Evolutionary Computation (CEC-2005), Edinburgh, Scotland, IEEE Press, 2005.
[36] M. Halkidi, Y. Batistakis, M. Vazigiannis, “On clustering validation techniques,” J. Intell. Inform. Syst. (JIIS), vol. 17, (2-3), pp. 107-145, 2003.
[37] J.C. Dunn, “Well seperated clusters and optimal fuzzy partitions,” J. Cybern., vol. 4, pp. 95-104, 1974.
[38] D.L. Davies and D.W. Bouldin, “A cluster separation measure,” IEEE Trans. On Pattern Analysis and Machine Intelligence, Vol. 1, No. 4, pp. 224-227, 1979.
[39] C.H. Chou, M.C. Su, and E. Lai, “A new cluster validity measure and its application to image compression,” Pattern Analysis and Application, Vol. 7, No. 2, pp. 205-220, 2004.
[40] X.L. Xie and G. Beni, “A Validity Measure for Fuzzy Clustering,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 13, pp. 841-847, 1991.
[41] M.C. Su, C.H. Chou, E. Lai, “A new cluster validity measure for clusters with different densities,” in: ISATED International Conference on Intelligent Systems & Control, Salzburg, Austria, pp. 276-281, 2003.
[42] J. Kennedy and R. Eberhart, “A discrete binary version of the particle swarm algorithm,” in Proc. IEEE Int. Conf. Systems, Man, Cybernetics, Computational Cybernetics, Simulation, vol. 5, 1997, pp. 4104–4108.
[43] I. Saha, U. Maulik, S. Bandyopadhyay, “A new Differential Evolution based Fuzzy Clustering for Automatic Cluster Evolution,” International Advance Computing Conference, pp. 706-711, 2009.
[44] K. Suresh, D. Kundu, S. Ghosh, S. Das and A. Abraham, “Automatic Clustering with Multi-objective Differential Evolution Algorithms,” IEEE Congress on Evolutionary Computation (CEC 2009), Trondheim, Norway, IEEE Press, 2009.
[45] S. Das, S. Sil, U.K. Chakraborty, “Kernel-based clustering of image pixels with modified Differential Evolution”, Evolutionary Computation, pp. 3472-3479, 2008.
[46] U.Maulik and S. Bandyopadhyay, “Performance evaluation of some clustering algorithms and validity indices,” IEEE Trans. Pattern Anal. Mach.Intell., vol. 24, no. 12, pp. 1650–1654, Dec. 2002.
[47] S. Saha, S. Bandyopadhyay, “Performance Evaluation of Some Symmetry-Based Cluster Validity Indexes,” Sys. Man, and Cybernetics, Part C: App. And Reviews, Vol. 39, Issue 4, pp. 420-425, July 2009.
[48] M.G.H. Omran, A.P. Engelbrecht, “Self-Adaptive Differential Evolution Methods for Unsupervised Image Classification,” Cybernetics and Intelligent Systems, pp.1-6, 7-9 June, 2006.
[49] J.C. Dunn, "A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters", Journal of Cybernetics 3: 32-57, 1973.
[50] J.C. Bezdek, Pattern Recognition with Fuzzy Objective Function Algoritms, Plenum Press, New York, 1981.
[51] F. Hoppner, F. Klawonn, K. Rudolf and T. Runkler, Fuzzy Cluster Analysis: Methods for Classification, Data Anallysis, and Image Recognition, John Wiley, Chichester.
[52] J. Leski, “Towards a robust fuzzy clustering,” Fuzzy Sets and Systems, vol. 137, no. 2, pp. 215-233 2, July, 2003.
[53] S.L. Yang, Y.S. Li, X.X. Hu and R.Y. Pan, “Optimization Study on k Value of K-means algorithm”, Systems Engineering-Theory & Practice, 2006, 26(2):97-101.
[54] 林豐澤，演化式計算上篇：演化式演算法的三種理論模式，智慧科技與應用統計學報，第3卷，第1期，2005年6月，29-56。