新的有效率之密度式分群技術之設計與應用

Development and Application of New Efficient Density-Based Clustering Scheme

黃士育(Shih-Yu Huang)

指導教授 ： 蔡正發

國立屏東科技大學/管理學院/資訊管理系所/碩士(2009年)

https://doi.org/10.6346/NPUST.2009.00140

摘要

資料探勘不管是在那一個領域都扮演愈來愈重要的角色，主要的方法有類神經網路、決策樹、基因演算法、關連法則及分群方法等，而分群方法是最廣為使用的方法之一。分群演算法又可再區分為切割式、階層式、網格式、模型式、密度式及混合式等大類，其中密度式分群演算法具有分群正確率及雜訊濾除率高、分群結果穩定等特點，但執行速度慢則是其最大的缺點，本論文針對密度式演算法運算時間過長的缺點提出一個新的有效率的密度式分群演算法，稱為SO-DBSCAN，可大幅加快密度式分群演算法的執行速度。經由實驗結果証明本研究提出的演算法與其他學者提出的演算法相比可提升數十倍甚至數百倍的效能，當資料筆數愈大時，其顯現的效果愈明顯，尤其是在超大資料集中，更能顯示其優勢。

關鍵字

資料探勘 ； 分群技術 ； 密度式分群

並列摘要

How to discover useful knowledge from huge dataset is more and more important and difficult. Data mining is an important technique in identifying useful data. There are many methods can perform data mining for large databases in various business applications, such as decision trees, neural network, association rules, genetic algorithm and clustering algorithm. Typically, clustering schemes are classified as partitioning, hierarchical, density-based, model-based, grid-based and mixed methods.
This thesis proposes a new efficient density-based algorithm called SO-DBSCAN. According to the simulation results, the proposed SO-DBSCAN algorithm can reduce a lot of execution time comparing with two related density-based algorithms, involving DBSCAN and IDBSCAN approaches. Moreover, the presented SO-DBSCAN algorithm still has high quality clustering correctness rate and noise data filtering rate.

並列關鍵字

Data mining ； clustering algorithm ； density-based clustering

參考文獻

[22] C. F. Tsai, and C. C. Li, “DK-means: A Robust New Clustering Technique in Data Mining for Databases,” Electronic Commerce Studies, vol. 5, no. 4, pp. 419-437, 2007.

[1] J. J. Hopfield, “Neural networks and physical systems with emergent collective computational abilities,” Proceedings of the national academy of sciences, vol. 79, no. 8, pp. 2554-2558, 1982.

[2] M. Mitchell, An introduction to genetic algorithms, MIT Press, Cambridge, 1998.

[3] J. R. Quinlan, “Induction of decision trees,” Machine learning, vol. 1, no. 1, pp. 81-106, 1986.

[6] L. Kaufman, and P. J. Rousseeuw, Finding groups in data, Wiley, New York, 2008.