전역 최적화를 위한 강건한 K-means
Robust K-means for Global Optimization
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
K-means is a popular and efficient data clustering method which is one of the most important technique in data mining. K-means is sensitive for initialization and has the possibility to be stuck in local optimum because of hill climbing clustering method. Therefore, we need a robust K-means (RK-means) not only to reduce this possibility but also to increase the probability to search the global optimal clustering solution. The objective of this paper is to propose RK-means with best initial solution from good solutions with good central data for each cluster. The central data of each cluster is selected based on Roulette wheel probabilistic selection using sum of relative distance rate of each data. They have a problem in high density data because they deterministically select the central data for just one initial solution of K-medoid. Our proposed initial solution is the good starting point to find the robust solution by K-means with reducing the possibility being stuck in local optimal solutions. The performance of proposed RK-means data clustering is validated using machine learning repository datasets (Iris, Wine, Glass, Vowel, Cloud) comparing to original K-means by experiment and analysis. Our simulation shows that RK-means using probabilistically relative distance rate are better than K-means with random initialization. The minimum squared distance by RK-means with smaller deviation is lower than that by K-means with higher deviation. RK-means is competitive comparing to data clustering methods based on simulated annealing (SA) and hybrid K-means with SA (KSA & KSAK).
Abstract
K-means is a popular and efficient data clustering method which is one of the most important technique in data mining. K-means is sensitive for initialization and has the possibility to be stuck in local optimum because of hill climbing clustering method. Therefore, we need a robust K-means (RK-means) not only to reduce this possibility but also to increase the probability to search the global optimal clustering solution. The objective of this paper is to propose RK-means with best initial solution from good solutions with good central data for each cluster. The central data of each cluster is selected based on Roulette wheel probabilistic selection using sum of relative distance rate of each data. They have a problem in high density data because they deterministically select the central data for just one initial solution of K-medoid. Our proposed initial solution is the good starting point to find the robust solution by K-means with reducing the possibility being stuck in local optimal solutions. The performance of proposed RK-means data clustering is validated using machine learning repository datasets (Iris, Wine, Glass, Vowel, Cloud) comparing to original K-means by experiment and analysis. Our simulation shows that RK-means using probabilistically relative distance rate are better than K-means with random initialization. The minimum squared distance by RK-means with smaller deviation is lower than that by K-means with higher deviation. RK-means is competitive comparing to data clustering methods based on simulated annealing (SA) and hybrid K-means with SA (KSA & KSAK).
참고문헌 (15)
- Arthur, D., "k-means++: the advantages of careful seeding", Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (2007), SIAM
- Celebi, M.E, "A comparative study of efficient initialization methods for the k-means clustering algorithm", Expert Syst. Appl, 40(1), pp.200~210 (2013)
- Fränti, Pasi, "How much can k-means be improved by using better initialization and repeats?", Pattern Recognition, 93(9), pp.95~112 (2019)
- Kang, B., "Two-Step Artificial Bee Colony Data Clustering Based on Silhouette", Management Science Review, 42, pp.21~29 (2018)
- Khan, S. S., "Cluster center initialization algorithm for K-means clustering", Pattern Recognition Letters, 25(11), pp.1293~1302 (2004)
- Kim, S., "Efficient Data Clustering using Fast Choice for Number of Clusters", J. Soc. Korea Ind. Syst. Eng, 41(2), pp.1~8 (2018)
- Kim, S., "Hybrid Simulated Annealing for Data Clustering", Journal of Society of Korea Industrial and Systems Engineering, 40(2), pp.92~98 (2017)
- Krishna K, "Genetic K-means algorithm", IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 29(3), pp.433~439 (1999)
- Likas, A., "The global k-means clustering algorithm", Pattern Recognition, 36(2), pp.451~461 (2003)
- Park, Jun, "A simple and fast algorithm for K-medoids clustering", Expert Systems with Applications, 36, pp.3336~3341 (2009)
- Perim, G. T., "K-Means Initialization Methods for Improving Clustering by Simulated Annealing", 11th Ibero-American Conference on AI, 5290, pp.133~142 (2008)
- Singh, Chauhan, "K-means v", s K-medoids: A Comparative Study, 2011, ~
- Selim, S. Z., "A simulated annealing algorithm for the clustering problem", Pattern Recognition, 24(10), pp.1003~1008 (1991)
- "UCI machine learning repository datasets"[URL]
- Xie, J., "An Efficient Global K-means Clustering Algorithm", Journal of Computers, 6(2) (2011)