一個有效率的密度式分群演算法與取樣技術之研究

An Efficient Density-Based Clustering Algorithm with Sampling Technique

宋俊毅(Chun-Yi Sung)

指導教授 ： 蔡正發

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

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

摘要

本論文提出一個新的分群演算法，該演算法提出改良的方法在密度式分群演算法。在查詢鄰近資料的程序中，當資料點被分群後，在作鄰近資料點查詢時，該資料點不需要再被查詢一次。在擴張種子篩選程序中，該程序重新定義八個標記邊界點，根據較遠的離心程度去追加種子點，與使用K-Nearest Neighbor的方法在一個連續的擴張種子中刪除第2或第3的擴張種子。本論文設計了二個實驗去驗證本論文所提之改善方法，實驗結果顯示，本論文所提出之DBSCALE 演算法之執行時間較低於DBSCAN, SDBSCAN, IDBSCAN 與KIDBSCAN 等分群演算法，分群正確率之差異為0.29%，雜訊濾除率則為0.14%。

關鍵字

資料探勘 ； 分群技術 ； 密度式分群演算法 ； 取樣技術

並列摘要

This thesis presents a novel clustering algorithm that incorporates neighbor searching and expansion seed selection into a density-based clustering algorithm. Data Points that have been clustered need not be input again when searching for neighborhood data point, and the algorithm redefines eight Marked Boundary Objects to add expansion seeds according to far centrifugal force, which increases coverage. Experimental results indicate that the proposed DBSCALE has a lower execution time cost than DBSCAN, SDBSCAN, IDBSCAN and KIDBSCAN clustering algorithms. DBSCALE has a maximum deviation in clustering correctness rate of 0.29%, and a maximum deviation in noise data clustering rate of 0.14%.

並列關鍵字

data mining ； clustering technique ； density-based clustering algorithm ； sampling technique

參考文獻

[1] Agrawal, R., Gehrke, J., Gunopulos, D., Raghavan, P., “Automatic Subspace Clustering of High Dimensional Data for Data Mining application,” Proceedings of ACM SIGMOD International Conference on Management of Data, pp. 94-105, 1998.

[4] Borah, B., Bhattacharyya, D.K., “An Improved Sampling-Based DBSCAN for Large Spatial Databases,” Proceedings of International Conference on Intelligent Sensing and Information, pp. 92-96, 2004.

[6] Carpenter, G., Grossberg, S., Rosen, D.,“Fuzzy ART: Fast Stable Learning and Categorization of Analog Patterns by An Adaptive Resonance System,” Neural Networks, vol. 4, pp. 759-771, 1991.

[7] Duan, L., Xu, L., Guo, F., Lee, J., Yan, B. “A Local-Density Based Spatial Clustering Algorithm with Noise,” Information Systems, vol. 32, pp. 978-986, 2007.

[10] Guha, S., Rastogi, R., Shim, K., “ROCK: A Robust Clustering Algorithm for Categorical Attributes,” Proceedings of 15th International Conference on Data Engineering, pp. 512-521, 1999.