[논문]Approximate k values using Repulsive Force without Domain Knowledge in k-means

Kim, Jung-Jae; Ryu, Minwoo; Cha, Si-Ho

doi:10.3837/tiis.2020.03.004

Approximate k values using Repulsive Force without Domain Knowledge in k-means 원문보기

KSII Transactions on internet and information systems : TIIS, v.14 no.3, 2020년, pp.976 - 990

Kim, Jung-Jae (Process and Engineering Research Lab. Control and Instrumentation Research Group, POSCO) , Ryu, Minwoo (Service Laboratoire Institute of Convergence Technology, KT R&D Center) , Cha, Si-Ho (Departement of Multimedia Science, Chungwoon University)

Abstract ▼ AI-Helper

The k-means algorithm is widely used in academia and industry due to easy and simple implementation, enabling fast learning for complex datasets. However, k-means struggles to classify datasets without prior knowledge of specific domains. We proposed the repulsive k-means (RK-means) algorithm in a previous study to improve the k-means algorithm, using the repulsive force concept, which allows deleting unnecessary cluster centroids. Accordingly, the RK-means enables to classifying of a dataset without domain knowledge. However, three main problems remain. The RK-means algorithm includes a cluster repulsive force offset, for clusters confined in other clusters, which can cause cluster locking; we were unable to prove RK-means provided optimal convergence in the previous study; and RK-means shown better performance only normalize term and weight. Therefore, this paper proposes the advanced RK-means (ARK-means) algorithm to resolve the RK-means problems. We establish an initialization strategy for deploying cluster centroids and define a metric for the ARK-means algorithm. Finally, we redefine the mass and normalize terms to close to the general dataset. We show ARK-means feasibility experimentally using blob and iris datasets. Experiment results verify the proposed ARK-means algorithm provides better performance than k-means, k'-means, and RK-means.

주제어

표/그림 (7)

그림 Fig. 1. Magnet position changes due to mutual repulsive forces
그림 Fig. 2. RK-means cluster locking problem
표 Table 1. ARK-means algorithm
그림 Fig. 3. Possibility of poor clusters concerning the number of initial clusters (k) for the indicated algorithms
그림 Fig. 4. Algorithm accuracy concerning dataset size for different initial k
표 Table 2. Experimental results of ARK-means accuracy using the blobs dataset
그림 Fig. 5. Algorithm accuracy and speed using the iris dataset

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

This experiment particularly focused on the proposed ARK-means feasibility. Therefore, we used the blobs dataset with N = 100, S = 3 to 6, and initial k = 10, 12, 14, and 16.

제안 방법

This paper proposed the ARK-means algorithm to resolve three specific significant problems with the RK-means algorithm. We performed three sets of experiments to verify ARK-means feasibility, with ARK-means achieving the highest performance compared with currentk-means, k’-means, and RK-means algorithms.
We performed three sets of experiments to verify ARK-means feasibility, with ARK-means achieving the highest performance compared with currentk-means, k’-means, and RK-means algorithms.

성능/효과

5-(b) shows the algorithm time to complete for initial k. All algorithms show have similar performance to k-means, although ARK-means is slightly improved since convergence to local optimum is guaranteed and convergence speed is improved by the term obtained the formula of the ARK-means algorithm.
We show ARK-means algorithm feasibility experimentally compared with RK-means and k’-means algorithms using blob and iris datasets. Experimental results verify that the proposed ARK-means algorithm provides more accurate performance than the other algorithms.
We assumed that the cluster centroids had repulsive forces between them,where each cluster had a mass proportion to the sum of errors between data and centroids. The key concept for RK-means was that clusters with larger mass represented a single data group better. Consequently, cluster centroids with larger mass would tend to maintain their current position, whereas cluster centroid with smaller mass would tend to search for positions to acquire larger mass.
We also discussed remaining practical ARK-means issues and challenging tasks to resolve them. Therefore, we can conclude with confidence that the proposed ARK-means algorithm will improve classification performance for large datasets, selecting initial k without domain knowledge. Although we improve classification performance based on proposed our algorithm, there are remain challenge tasks to apply the method in practice.

후속연구

Although we improve classification performance based on proposed our algorithm, there are remain challenge tasks to apply the method in practice. To this end, future research will include statistics based on selecting an initial point to reduce performance deviation in practice.

참고문헌 (26)

Y.-M. Cheung, "On rival penalization controlled competitive learning for clustering with automatic cluster number selection," IEEE Transactions on Knowledge and Data Engineering, vol. 17, no. 11, pp. 1583-1588, 2005.

상세보기
M. E. Celebi, H. A. Kingravi, Patricio A. vela, "A comparative study of efficient initialization methods for the k-means clustering algorithm," Expert Systems with Applications, vol 40, no. 1, pp. 200-210, 2013.

상세보기
T. Kanungo, D. M. Mount, N. S. Netanyahu, C. D. Piatko, R. Silverman, A. Y. Wu "An Efficient k-Means Clustering Algorithm: Analysis and Implementation," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 24, no. 7, pp. 881-892, 2002.

상세보기
D. Arthur, S. Vassilvitskii. "k-means++: the advantages of careful seeding," Nikhil Bansal, Kirk Pruhs, and Clifford Stein, editors, SODA, SIAM, pp.1027-1035, 2007.
C. Fang, W. Jin, J. Ma, "k'-Means algorithms for clustering analysis with frequency sensitive discrepancy metics," Pattern Recognition Letters, vol. 34, no. 5, pp. 580-586, Apr. 2013.

상세보기
H. Khatter, V. Aggarwal, A. K. Ahlawat, "Performance Analysis of the Competitive Learning Algorithms on Gaussian Data in Automatic Cluster Selection," in Proc. of IEEE International Conference on Computational Intelligence & Communication Technology (CICT), U.P., India, 12-13 Feb. 2016.
K. Wagstaff, C. Cardie, S. Rogers, S. Schroedl, "Constrained K-means Clustering with Background Knowledge," in Proc. of the Eighteenth International Conference on Machine Learning, pp. 577-584, 2001.
A. K. Jain, "Data clustering: 50 years beyond K-means," Pattern Recognition Letters, vol. 31, no. 8, pp. 651-666, June 2010.

상세보기
J. Baek, Y. Kim, B. Chung, C. Yim, "Linear Spectral Clustering with Contrast-limited Adaptive Histogram Equalization for Superpixel Segmentation," IEIE Transactions on Smart Processing and Computing, vol. 8, no. 4, pp. 255-264, August, 2019.

상세보기
J. Lei, T. Jiang, K. Wu, H. Du, G. Zhu, Z. Wang, "Robust K-means algorithm with automatically splitting and merging clusters and its applications for surveillance data," Multimedia Tools and Applications, vol. 75, no. 19, pp. 12043-12059, Oct. 2016.

상세보기
D. T. Pham, S. S. Dimov, C. D. Nguyen, "Selection of K in K-means clustering," in Proc. of ImechE, vol. 2019 Part C: Journal of Mechanical Engineering Science, vol. 219, pp. 103-119, 2005.
T. M. Kodinariya, P. R. Makwana, "Review on determining number of Cluster in K-Means Clustering," International Journal of Advance Research in Computer Science and Management Studies, vol. 1, no. 6, pp. 90-95, 2013.
P. S. Bradley, U. M. Fayyad, "Refining Initial Points for K-Means Clustering," in Proc. of the 15th International Conference on Machine Learning (ICML98), San Francisco, USA, pp. 91-99, 1998.
D. Pelleg, A. Moore, "X-means: Extending K-means with Efficient Estimation of the Number of Clusters," in Proc. of the 17th International Conference on Machine Learning (ICML2000), pp. 727-734, 2000.
M. K. Ng, J. Z. Huang, L. Jing, "An Entropy Weighting k-Means Algorithm for Subspace Clustering of High-Dimensional Sparse Data," IEEE Transactions on Knowledge & Data Engineering, vol. 19, pp. 1026-1041, 2007.

상세보기
J. Luo, J. Ma, "Image segmentation with the competitive learning-based MS model," in Proc. of the 2015 IEEE International Conference on Image Processing (ICIP), Quebec, Canada, 27-30 Sep. 2015.
Y.-M. Cheung, "Rival penalization controlled competitive learning for data clustering with unknown cluster number," in Proc. of the 9th International Conference on Neural Information Process (ICONIP '02), Singapore, 18-22 Nov. 2002.
J. Ma, T. Wang, "A cost-function approach to rival penalized competitive learning (RPCL)," IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 36, no. 4, pp. 722-737, 2006.

상세보기
H. Xie, X. Luo, C. Wang, S. Liu, X. Xu, X. Tong, "Multispectral remote sensing image segmentation using rival penalized controlled competitive learning and fuzzy entropy," Soft Computing, vol. 20, no. 12, pp. 4709-4722, Dec. 2016.

상세보기
J. MacQueen, "Some methods for classification and analysis of multivariate observations," in Proc. of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, California, USA, 16 Jan. 2008.
J. Qin, W. Fu, H. Gao, W. X. Zheng, "Distributed k-means algorithm and fuzzy c-means algorithm for sensor networks based on multiagent consensus theory," IEEE Transactions on Cybernetics, vol. 47, no. 3, pp. 772-783, Mar. 2016.

상세보기
L. Xu, A, Krzyzak, E. Oja, "Rival penalized competitive learning for clustering analysis, RBF net, and curve detection," IEEE Transactions on Neural networks, vol. 4, no. 4, pp. 636-649, 1993.

상세보기
G.-J. Yu, K.-Y. Yeh, "A K-Means Based Small Cell Deployment Algorithm for Wireless Access Networks," in Proc. of 2016 International Conference on Networking and Network Applications (NaNA), Hokkaido, Japan, 23-25 July 2016.
K. R. Zalik, "An efficient k'-means clustering algorithm," Pattern Recognition Letters, vol. 29, no. 9, pp. 1385-1391, 2008.

상세보기
D. Arthur, S. Vassilvitskii, "k-means++: the advantages of careful seeding," in Proc. of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, pp. 1027-1035, 2007.
Scikit-learn, "Machine Learning in Python," Pedregosa et al., JMLR 12, pp. 2825-2830, 2011.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증