臺灣博碩士論文加值系統

分割式分群演算法是資料探勘領域中重要的一支，它能夠將一資料庫內的所有資料點，根據其關連屬性予以任意分成 群，然而，大部分的資料庫都存在著真正的原始分群數，因此，叢集效度指標的目的就是評估並找出這個真正的分群數值。本論文是針對目前叢集效度指標對大多數真實資料庫評估普遍出現錯誤的問題，提出了一種植基於遺傳基因演算法之最佳化技術的適應性叢集效度指標。該演算法應用遺傳基因演算法的最佳化技術，調整評估函式中的適應性叢集效度指標之權重值，訓練出一個最佳化的適應性叢集效度指標。利用真實的資料庫對演算法進行了測試，結果表明，與現有的其他效度指標，本文提出的基於遺傳基因演算法之最佳化技術的適應性叢集效度指標，能夠準確判斷出大部分真實資料庫的正確原始群數。

The partitioning method is an important research branch in data mining area, and it partitions the dataset into an arbitrary number k of clusters according to the correlation attribute of all elements of the dataset. Most datasets have the original clusters number, which is estimated with cluster validity index. But most current cluster validity index methods give the error estimation for most real datasets. In order to solve this problem, this thesis applies the optimization technology of genetic algorithm to the new adaptive cluster validity index, which is called the Gene Index (GI). The algorithm applies genetic algorithm to adjust the weight value of the valuation function of adaptive cluster validity index to train an optimal cluster validity index. The algorithm is tested with many real datasets, and results show the proposed algorithm can give higher performance and accurately estimate the original cluster number of real datasets compared with the current cluster validity index methods.

摘 要 i
ABSTRACT ii
誌　謝 iii
目　錄 iv
表目錄 v
圖目錄 vi
一、 緒論 1
1.1 前言 1
1.2 研究動機與目的 1
1.3 論文架構 2
二、 分割式分群法及叢集效度指標之文獻探討 4
2.1. 分割式分群法 4
2.2. 叢集效度指標 14
2.3. 結語 37
三、 植基於遺傳演算法之適應性叢集效度指標 40
3.1. 遺傳演算法概述 40
3.2. 本研究的適應性基因叢集效度指標 42
3.3. 實驗設計的前置作業 44
3.4. 應用遺傳演算法於我們的適應性基因叢集效度指標 46
四、 實驗結果及分析 49
4.1. 實驗結果 49
4.2. 結果分析與討論 51
五、 結論 66
參考文獻 67

[1]D.E. Goldberg, 1989, Genetic Algorithms in Search Optimization and Machine Learning, Addison Wesley.
[2]J.C. Bezdeck, R. Ehrlich, and W. Full, 1984, “FCM:Fuzzy C-Means Algorithm”, Computers and Geosciences.
[3]J.C. Bezdek, 1981, Pattern recognition with fuzzy objective function algorithm algorithms, New York.
[4]N.L. XIE and G. BENI, 1991, “A Validity measure for fuzzy clustering”, IEEE Trans. , PAMI-3, (8) , pp. 841-846.
[5]S.II. Kwon, 1998, “Cluster validity index for fuzzy clustering”, ELECTRONICS LETTER, vol. 34, no. 22, pp. 2176-2177.
[6]A.-O. Boudraa, 1999, “Dynamic estimation of number of clusters in data sets”, ELECTRONICS LETTER, vol. 35, no. 19, pp. 1606-1608.
[7]D.-J. KIM, Y.-W. PARK, and D.-J. Park, 2001, “A Novel Validity Index for Determination of the Optimal Number of Clusters”, IEICE. Trans. Inf. & Syst. , vol. E84 D, no 2, pp. 281-285, February.
[8]http://www.ics.uci.edu/~mlearn/MLRepository.html
[9]曾憲雄，蔡秀滿，蘇東興，曾秋蓉，王慶堯，民94年，資料探勘 Data mining，第六章，旗標出版，臺北市。
[10]G.H. Ball and D.J. Hall, 1965, “ISODATA: A novel method of data analysis and classification”, Technical Report, Stanford Universuty.
[11]J. C. Dunn, 1973, “A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters,” J. Cybern. , vol. 3, no. 3, pp. 32–57.
[12]L. J. Hubert and P. Arabie, 1985, “Comparing partitions”, J. Classification, vol. 2, pp. 193–218.
[13]D. L. Davies and D. W. Bouldin, 1979, “A cluster separation measure”, IEEE Trans. Pattern Anal. Machine Intell. , vol. 1, no. 4, pp. 224–227.
[14]Y. FUKUYAMA and M. SUGENO, 1989, “A new method of choosing the number of clusters for the FCM method”, Proc. 5th Fuzzy Syst. Symp, pp. 247-250.
[15]R.C. DUBES, 1987, “How many clusters are best? – An experiment”, Pattern Recognit. , vol. 20, pp. 645-663.
[16]J.M. COGGINS and A.K. JAIN, 1985, “A spatial filtering approach to texture analysis”, Pattern Recognit. , vol. 3, pp. 195-203.
[17]R. DUBES and A.K. JAIN, 1979, “Validity studies in clustering methodologies”, Pattern Recognit. , vol. 11, pp. 235-253.