데이터 클러스터링을 위한 혼합 시뮬레이티드 어닐링
Hybrid Simulated Annealing for Data Clustering
2
조회
0
다운로드
4
인용
0
참고문헌
키워드
초록
Data clustering determines a group of patterns using similarity measure in a dataset and is one of the most important and difficult technique in data mining. Clustering can be formally considered as a particular kind of NP-hard grouping problem. K-means algorithm which is popular and efficient, is sensitive for initialization and has the possibility to be stuck in local optimum because of hill climbing clustering method. This method is also not computationally feasible in practice, especially for large datasets and large number of clusters. Therefore, we need a robust and efficient clustering algorithm to find the global optimum (not local optimum) especially when much data is collected from many IoT (Internet of Things) devices in these days. The objective of this paper is to propose new Hybrid Simulated Annealing (HSA) which is combined simulated annealing with K-means for non-hierarchical clustering of big data. Simulated annealing (SA) is useful for diversified search in large search space and K-means is useful for converged search in predetermined search space. Our proposed method can balance the intensification and diversification to find the global optimal solution in big data clustering. The performance of HSA is validated using Iris, Wine, Glass, and Vowel UCI machine learning repository datasets comparing to previous studies by experiment and analysis. Our proposed KSAK (K-means+SA+K-means) and SAK (SA+K-means) are better than KSA(K-means+SA), SA, and K-means in our simulations. Our method has significantly improved accuracy and efficiency to find the global optimal data clustering solution for complex, real time, and costly data mining process.
Abstract
Data clustering determines a group of patterns using similarity measure in a dataset and is one of the most important and difficult technique in data mining. Clustering can be formally considered as a particular kind of NP-hard grouping problem. K-means algorithm which is popular and efficient, is sensitive for initialization and has the possibility to be stuck in local optimum because of hill climbing clustering method. This method is also not computationally feasible in practice, especially for large datasets and large number of clusters. Therefore, we need a robust and efficient clustering algorithm to find the global optimum (not local optimum) especially when much data is collected from many IoT (Internet of Things) devices in these days. The objective of this paper is to propose new Hybrid Simulated Annealing (HSA) which is combined simulated annealing with K-means for non-hierarchical clustering of big data. Simulated annealing (SA) is useful for diversified search in large search space and K-means is useful for converged search in predetermined search space. Our proposed method can balance the intensification and diversification to find the global optimal solution in big data clustering. The performance of HSA is validated using Iris, Wine, Glass, and Vowel UCI machine learning repository datasets comparing to previous studies by experiment and analysis. Our proposed KSAK (K-means+SA+K-means) and SAK (SA+K-means) are better than KSA(K-means+SA), SA, and K-means in our simulations. Our method has significantly improved accuracy and efficiency to find the global optimal data clustering solution for complex, real time, and costly data mining process.
참고문헌 (19)
- Gungor, Z., "K-harmonic means data clustering with simulated annealing heuristic", Applied Mathematics and Computation, 184(2), pp.199~209 (2007)
- Hruschka, E.R., "A survey of evolutionary algorithms for clustering", IEEE Transactions on systems, man, and cybernetics-Part C(Applications and reviews), 39(2), pp.133~155 (2009)
- Kirkpatrick, S., "Optimization by simulated annealing", Science, 220(4598), pp.671~680 (1983)
- Krishna, K., "Genetic K-means algorithm", IEEE Transactions on Systems, Man, and Cybernetics, Part B(Cybernetics), 29(3), pp.433~439 (2002)
- Kumar, Y., "A two-step artificial bee colony algorithm for clustering", Neural computing & Applications, 28(3), pp.537~551 (2017)
- Maulik, U., "Genetic algorithmbased clustering technique", Pattern Recognition, 33(9), pp.1455~1465 (2000)
- Michalewicz, Z., "Genetic Algorithms+Data Structures = Evolution Programs" (1992), Springer Verlag Berlin Heidelberg
- 오승준, "범주형 값들이 순서를 가지고 있는 데이터들의 클러스터링 기법", 산업경영시스템학회지, 26(1), pp.17~21 (2003), 한국산업경영시스템학회
- Perim, G. T., "K-Means Initialization Methods for Improving Clustering by Simulated Annealing", 11th Ibero-American Conference on AI, 5290, pp.133~142 (2008)
- Selim, S.Z., "A simulated annealing algorithm for the clustering problem", Pattern Recognition, 24(10), pp.1003~1008 (1991)
- 서명교, "군집기반 열간조압연설비 상태모니터링과 진단", 품질경영학회지, 45(1), pp.25~38 (2017), 한국품질경영학회[DOI]
- Singh, S.S., "K-means v", s K-medoids :A Comparative Study, 2011, ~
- Sun, L. X., "Cluster analysis by simulated annealing", Computers & Chemistry, 18(2), pp.103~108 (1994)
- Sun, L. X., "Cluster analysis by the K-means algorithm and simulated annealing", Chemometrics and intelligent Laboratory Systems, 25(1), pp.51~60 (1994)
- "UCI machine learning repository Cloud datasets"[URL]
- "UCI machine learning repository Glass datasets"[URL]
- "UCI machine learning repository Iris datasets"[URL]
- "UCI machine learning repository Vowel datasets"[URL]
- "UCI machine learning repository Wine datasets"[URL]