結合基因演算法之兩階段式模糊分群法

A Two-staged Fuzzy Clustering Algorithm with Genetic Algorithm

陳立偉(Li-Wei Chen)

指導教授 ： 詹前隆 博士

元智大學/資訊學院/資訊管理學系/碩士(2001年)

摘要

集群分析是一種資料探勘的技術，其目的在於發掘資料中可能潛藏的模式，進而達到企業行銷與管理之用。而這方面的研究，大部分都著重於提升最後結果的品質(例如利用全域最佳化的方法來求解)，而較少考量到求解過程的效率問題。然而，隨著「全球化」與「網際網路」的影響，企業的資料量變得異常地龐大，因此在如此競爭激烈的環境下，資料分析技術的效率便成為搶奪致勝先機的一個重要關鍵。
在本研究中，我們提出了一個兩階段式的模糊分群演算法來滿足實務上大量資料分析的需求。而我們根據四個部份(Nc最大值的決定、啟始方法的有效性、分群結果的品質、分群的收斂時間)來驗證所提出的演算法，並以四個標準測試資料集(Iris Plants Data, Balance Scale Weight & Distance Data, Wisconsin Breast Cancer Data, and Contraceptive Method Choice Data)測試之。根據實驗的結果，我們的演算法的確改善了FCM演算法的區域最佳化問題，以及基因演算法的效率問題。因此就實務方面，我們的演算法可以快速地提供一個可接受的結果，作為企業回應外部環境變化的參考。

關鍵字

基因演匴法 ； 以熵為基礎的參數啟始法 ； FCM演算法 ； 模糊分群 ； 兩階段式分群法

並列摘要

Cluster analysis is a kind of data mining techniques, and its goal is to find the hiding patterns from the unknown data. In related studies, most of them are focused on the improvement of the clustering results, and less on the efficiency of clustering. However, the efficiency of data analysis technique is getting increasingly important in practice, while the analysis of huge amount of data is needed (due to the influence of globalization and internet).
In this paper, we propose a two-staged fuzzy clustering algorithm to meet the practical need. We test our algorithm based on the four parts (the maximum of Nc, the effectiveness of the initialization method, the quality of the clustering results, and the converging time of clustering) with four standard test data sets: Iris Plants Data, Balance Scale Weight & Distance Data, Wisconsin Breast Cancer Data, and Contraceptive Method Choice Data. According to the results of experiments in this study, our algorithm has improved not only the problem of local optimization of FCM algorithm, but also the efficiency of GA. Therefore, our proposed algorithm can provide faster clustering results with an acceptable quality of clustering for practical needs.

並列關鍵字

Genetic Algorithm ； Entropy-based Initialization Method ； FCM Algorithm ； Fuzzy Clustering ； Two-staged Clustering

參考文獻

1.Al-Sultan K. S., and C. A. Fedjki, “A Tabu search-based algorithm for the fuzzy clustering problem,” Pattern Recognition, Vol. 30, Issue 12, pp.2023-2030, Elsevier Science Ltd., Dec. 1997.

2.Bäck T., Evolutionary Algorithms in Theory and Practice, New York: Oxford University Press, 1996.

3.Bezdek J. C., Pattern Recognition with Fuzzy Objective Function Algorithms, Plenum, New York, 1981.

5.Egan M. A., “Locating clusters in noisy data: A genetic fuzzy c-means clustering algorithm,” Conference of the North American on Fuzzy Information Processing Society - NAFIPS, 20-21 Aug. 1998, pp.178-182.

6.Hall L. O., J. C. Bezdek, S. Boggavarpu, and A. Bensaid, “Genetic fuzzy clustering,” Industrial Fuzzy Control and Intelligent Systems Conference, and the NASA Joint Technology Workshop on Neural Networks and Fuzzy Logic, NAFIPS/IFIS/NASA ''94, Proceedings of the First International Joint Conference of the North American Fuzzy Information Processing Society Biannual Conference, 18-21 Dec. 1994, pp.411-415.