臺灣博碩士論文加值系統

近年來，資料探勘在各個領域的應用非常廣泛；其中的分群探勘這領域中，可以是獨立地探勘資料，也可以用來分析出資料庫的概況，做為資料分析的前置動作。但是在較常使用的K-Means及PAM演算法，起始值的選擇會嚴重影響最後的分群結果，且易陷入局部最佳解的情況；在以格子為基礎的分群法中，雖然花費的時間少，但在精確度上卻有待提升；而雖然以樣本為基礎的分群法被提出(如CLARA、CLARANS)，但樣本的選取會直接影響到最後的分群結果，雖然速度快，但分群後的精確度是否正確則為一大問題。因此我們發展出一種選擇適當起始值的演算法，藉此來減少亂數起始值對分群結果的影響，進而提升分群的速度，以及維持穩定的分群品質。我們使用平均切割格子的概念，結合格子演算法及密度演算法的優點，利用上述來做為K-Means起始值的選擇依據。藉此改進亂數選取起始值所造成的影響，再利用K-Means的流程，增加分群的精確度。本論文將此演算法與K-Means，針對不同的資料分佈進行分群探勘，並對其進行比較分析，由實驗結果證實了本演算法不僅能改進執行效率，更能提升分群結果的精確度。

Recently, data mining is applied to many fields widely. In particular, the clustering can analyze theprofile of databases in the data mining field. Many algorithms had been proposed for the clustering.However, most algorithms have either high speed or better accuracy for clustering, but not both. The most popular algorithm, K-Means, has less executive time-spending and better accuracy for clustering if the option of the starting-value is good. Unfortunately, the random options are not always good. In this paper, we propose a strategy based on the grid concept for the option of the starting-value to the K-Means. The objective is to improve the performance of the K-Means. Additionally, we made some experiments, and the results demonstrated that the strategy we proposed did have better performance than the traditional K-Means.

摘要 I
Abstract II
目次 III
表目錄 V
圖目錄 VI
第一章 緒論 1
1.1 研究動機 1
1.2 研究目的 2
1.3 論文架構 2
1.4 研究流程 3
第二章 相關研究 4
2.1 資料探勘 4
2.2 關聯規則 5
2.2.1 Apriori演算法 5
2.2.2頻繁模式樹 6
2.3分類分析 7
2.3.1 ID3分析 7
2.4分群分析 8
2.4.1切割式演算法 9
2.4.2 K-Means演算法 10
2.4.3 PAM演算法 13
2.4.4階層式演算法 14
2.4.5格子為基礎的分群法 15
2.4.6以密度為基礎的分群法 15
2.5 基因演算法概念 18
第三章 改良式演算法 20
3.1演算法介紹 20
3.2演算法流程 22
3.3演算法實例說明 24
第四章 實驗結果與分析 33
4.1 實驗數據資料 33
4.2 效能評估 35
4.2.1 DS1實驗結果 35
4.2.2 DS2實驗結果 37
4.2.3 DS3實驗結果 40
4.2.4 DS4實驗結果 41
4.2.5 DS5實驗結果 42
4.2.6 DS6實驗結果 44
4.2.7 DS7實驗結果 46
4.2.8 DS8實驗結果 47
4.2.9 DS9實驗結果 48
4.2.10 DS10實驗結果 49
4.3 精確度探討 50
4.3.1 DS1實驗結果 51
4.3.2 DS2實驗結果 51
4.3.3 DS3實驗結果 52
4.3.4 DS4實驗結果 52
4.3.5 DS5實驗結果 53
4.3.6 DS6實驗結果 53
4.3.7 DS7實驗結果 54
4.3.8 DS8實驗結果 54
4.3.9 DS9實驗結果 55
4.3.10 DS10實驗結果 55
4.4 物件數漸增時的執行效能 56
4.5 演算法分析與探討 57
4.5.1 資料平均分佈的問題探討 57
4.5.2 格子切割數目的問題 58
4.5.3 格子合併過程可能遇到的問題 61
4.6 實驗結果探討 62
第五章 結論與未來發展 63
5.1結論 63
5.2未來研究與發展建議 64
第六章 參考文獻 66

1. 張紘愷(2003)，”應用分群技術於資料探勘之研究”，國立高雄應用科技大學電子與資訊工程研究所碩士論文.
2. 陳榮昌，林育臣，”群聚演算法之比較及群聚參數的分析與探討”， 第三屆網際網路應用與發展研討會，遠東技術學院，2002.
3. 陳奕學(2002)，”空間資料叢集演算法之設計”，義守大學資訊工程研究所碩士論文.
4. 翁振恭(2003)，”使用基因演算法於拓撲最佳化之研究”， 大葉大學自動化工程學系碩士論文.
5. Agrawal, R. and Srikant, R., “FastAlgorithms for Mining Association Rules”, Proceedings of the 20th International Conference on Very Large Databases, Santiago. Chile, September, pp. 487-499, 1994. (Apriori)
6. Clair， D. C. St.， Sabharwal， C. L. and Hacke， K. R. ，“Formation of clusters and resolution of ordinal attributes in ID3 classification trees”，Proc. of ACM/SIGAPP Symposium on Applied Computing: Technological Challenges of the 1990’s， pp. 590-597， 1992. (ID3)
7. Fang Yuan，Zeng-Hui Meng，Hong-Xia Zhang，Chun-Ru Dong，” A new algorithm to get the initial centroids”， Proceedings of the Third International Conference on Machine Learning and Cybernetics,Shanghai,26-29 August 2004.
8. G. Karypis， E.-H. Han， and V. Kumar. “CHAMELEON: Hierarchical Clustering Using Dynamic Modeling”. COMPUTER， 32:68-75， 1999. (CHAMELEON)
9. Jiawei Han，Jian Pei，Yiwen Yin "Mining Frequent Patterns without Candidate Generation" Proceedings of the 2000 ACM SIGMOD International Conference on Management of data,2000,Pages 1-12. (FP-Tree)
10. J. MacQueen. “Some Methods for Classification and Analysis of Multivariate Observations”. In Proc. 5th Berkeley Symp. Math. Statistics， Prob. 1:281-297.,1967 (K-Means)
11. K. Alsabti， S. Ranka， and V. Singh， “An Efficient K-Means Clustering Algorithm，” PPS/SPDP Workshop on High Performance Data Mining， 1997。
12. L. Kaufman and P. J. Rousseeuw. “Finding Groups in Data: an Introduction to Cluster Analysis”. John Wiley & Sons， 1990. (PAM)
13. M. Ester， H. -P. Kriegel， J. Sander， X. Xu. “Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise”. In Proc. 1996 Int. Conf. Knowledge Discovery and Data Mining (KDD’96)， pages 226-231， Portland， OR， Aug. 1996. (DBSCAN)
14. Peng Yuqing，Hou Xiangdan，Liu Shang.”The K-Means Clustering Algorithm Based On Density And Colony”. IEEE Int.Conf. 2003 Nwural Networks & Signal Processing Nanjing，China，December 14-17. (ANT+GIRD)
15. Rakesh Agrawal, Ramakrishnan Srikant, “Mining Sequential Patterns,” Proc. Of the Int’l Conference on Data Engineering(ICDE),Taipei, Taiwan, March 1995, Pages 2- 8. (Apriori-Like)
16. R. T. Ng and J. Han， “Efficient and Effective Clustering Methods for Spatial Data Mining” Proceedings of the 20th International Conference on Very Large Data Bases， pp. 144-155， 1994. (CLARANS)
17. R. C. Dubes and A. K. Jain， ‘Algorithms for Clustering Data”， Prentice Hall， 1988.
18. R. Agrawal， J. Gehrke， D. Gunopulos， P. Raghavan(1998)， ”Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications”. Int. Conf. Management of Data， 94-105， Seattle， Washington. (CLIQUE)
19. Smyth， P.， Piatetsky， S. G. and Fayyad， U.， ”From Data Mining to Knowledge Discovery in Database”， Cambridge， AAA/MIT Press， 1996.(KDD)
20. S. Guha， R. Rastogi， and K. Shim. “CURE: An efficient clustering algorithm for large databases”. In Proc. 1998 ACM-SIGMOD Int. Conf. Management of Data (SIGMOD’98)， pages 73-84， Seattle， WA， June 1998. (CURE)
21. S. Guha， R. Rastogi， and K. Shim. “ROCK: A Robust Clustering Algorithm For Categorical Attribute”. In Proc. 1999 Int. Conf. Data Engineering (ICDE’99)， pages 512-521， Sydney， Australia， Mar. 1999. (ROCK)
22. T. Zhang， R. Ramakrishnan， M. Livny. “BIRCH: An Efficient Data Clustering Method for Very Large Databases”. In Proc. 1996 ACM-SIGMOD Int. Conf. Management of Data (SIGMOD’96)， pages. 103-114.( BIRCH)
23. V. Estivill-Castro and I. Lee. “AMOEBA: Hierarchical Clustering Based on Spatial Proximity Using Delaunay Diagram”. In Proc. 9th Int. Spatial Data Handling (SDH2000)， pages 10-12， Beijing， China， Aug. 2000.( AMOEBA)
24. V. Estivill-Castro and I. Lee. “AUTOCLUST: Automatic Clustering via Boundary Extraction for Massive Point Data Sets”. In Proc. 5th Int. Conf. Geo-Computation， pages 23-25， University of Greenwich， Kent， UK. Aug. 2000.( AUTOCLUST)
25. Wang， Yang， R。 Muntz. “STING: A Statistical Information grid Approach to Spatial Data Mining”. In Proc. 1997 Int. Conf. Very Large Data Bases(VLDB’97)， pages 186-195， Athens， Greece， Aug. 1997. ( STING)
26. Yu-Fang Zhang，Jia-Li Mao，Zhong-Tang Xiong，” An efficient clustering algorithm”. IEEE Proceedings of Second International Conference on Machine Learning and Cybernetics,Xi'an,2-5 Novermber 2003. (Ant+GIRD)
27. Z. Huang. “Extensions to the K-Means Algorithm For Clustering large Data sets with Categorical values”. Data mining and knowledge discovery， 2:283-304， 1998. (K-Protypes)
28. Jyh-Shing Roger Jang, "Data Clustering and Pattern Recognition," http://www.cs.nthu.edu.tw/~jang.
29. Goldberg, D. E., ”Genetic Algorithms in Search,Optimization and Machine Learning”, Addison-Wesley,1998.