[논문]Fuzzy c-means의 문제점 및 해결 방안

허경용; 서진석; 이임건

doi:10.9708/jksci.2011.16.1.039

Fuzzy c-means의 문제점 및 해결 방안
Problems in Fuzzy c-means and Its Possible Solutions 원문보기

韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information, v.16 no.1, 2011년, pp.39 - 46

허경용 (동의대학교 영상미디어센터) , 서진석 (동의대학교 게임공학과) , 이임건 (동의대학교 영상정보공학과)

초록
AI-Helper

클러스터링은 주어진 데이터 집합을 균일한 특성을 가지는 몇 개의 그룹으로 묶는 대표적인 비교사 학습 방법 중 하나로 지금까지 다양한 형태의 알고리듬이 개발되어 다양한 응용 분야에서 사용되어 왔다. 이 중 fuzzy c-means (FCM)는 분할 기반의 클러스터링 기법에 속하는 알고리듬으로 1970년대에 정립된 이후 지금까지 사용되고 있는 대표적인 클러스터링 알고리듬 중의 하나이다. 하지만 FCM에는 여러 가지 문제점이 있으며 이를 해결하기 위해 지금까지도 다양한 FCM의 변형이 제안되고 있다. 이 논문에서는 먼저 FCM의 문제점을 살펴보고 이를 해결하기 위해 제안된 방법들을 통해 연구 방향을 제시하고자 한다. FCM의 문제점을 해결하고자 하는 대부분의 FCM 변형은 주어진 문제 영역의 지식을 활용하고 있다. 하지만 이 논문에서는 문제 영역을 한정하지 않고 모든 문제에 적용할 수 있는 일반적인 방안을 제시하는데 초점을 둔다. 제시하는 방안은 앞으로 더 많은 연구가 필요하지만 클러스터링을 연구하고자 하는 이들에게 최근의 연구 동향과 더불어 출발점을 제시할 수 있을 것으로 기대한다.

Abstract ▼ AI-Helper

Clustering is one of the well-known unsupervised learning methods, in which a data set is grouped into some number of homogeneous clusters. There are numerous clustering algorithms available and they have been used in various applications. Fuzzy c-means (FCM), the most well-known partitional clustering algorithm, was established in 1970's and still in use. However, there are some unsolved problems in FCM and variants of FCM are still under development. In this paper, the problems in FCM are first explained and the available solutions are investigated, which is aimed to give researchers some possible ways of future research. Most of the FCM variants try to solve the problems using domain knowledge specific to a given problem. However, in this paper, we try to give general solutions without using any domain knowledge. Although there are more things left than discovered, this paper may be a good starting point for researchers newly entered into a clustering area.

주제어

AI 본문요약
AI-Helper

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

문제 정의

하지만 많은 FCM의 변형이 존재한다는 사실은 FCM이 모든 문제에 적합한 것은 아니라는 반증이 될 수 있다. 따라서 이 논문에서는 FCM이 가지는 문제점들을 살펴보고 이를 해결할 수 있는 방법을 살펴봄으로써 향후 연구 방향을 제시한다. 기존의 많은 방법들이 문제 영역의 지식들을 활용하는 전용 방법들인데 반해 이 논문에서는 모든 문제에 적용이 가능한 범용 방법들에 중점을 둔다.
클러스터링은 주어진 데이터를 균일한 부분집합으로 나누는 비교사 학습법 중 하나로 특히 FCM은 1970년대 정립된 이후 지금까지도 널리 사용되는 대표적인 클러스터링 알고리듬 중 하나이다. 하지만 FCM은 여러 가지 해결되지 못한 문제들이 있으며 이 논문에서는 이들 문제점들을 살펴보고 이를 해결할 수 있는 연구 방향을 살펴 보았다. 비록 제시된 방법들이 기존 방법들에 비해 항상 나은 성능을 보이지는 않으며 향후 더 많은 연구가 필요한 방법들이지만 이들 사이에는 한 가지 공통점을 발견할 수 있다.

가설 설정

가우시안 혼합 모델로 데이터를 한정하는 경우 K의 결정은 EM (expectation maximization)[10]의 변형을 통해서도 가능하다. EM에 분할-병합을 도입하여 가우시안 컴포넌트의 개수를 결정하는 다양한 알고리듬이 제시되어 있으며[11][12], 여기에 가설 검증을 결합함으로써 휴리스틱을 배제한 엄밀한 알고리듬을 얻을 수 있을 것이다.
유클리드 거리를 사용하면서 잡음 민감성을 줄일 수 있는 방법으로는 노이즈 클러스터링(noise clustering)[13]과 regularization[14]이 있다. 노이즈 클러스터링은 가상의 노이즈 클러스터를 도입하고 이 클러스터에 소속되는 정도를 잡음의 정도로 가정함으로써 잡음의 영향을 줄인다. 하지만 모든 데이터 포인트에서 동일한 거리에 존재하는 노이즈 클러스터의 가정은 종종 원하지 않는 결과를 가져오므로 다양한 변형이 제안되었음에도 최근 관련 연구는 드문 실정이다.

대상 데이터

계층적 클러스터링이 클러스터의 분할 또는 병합 과정에서 국부적인 정보만을 활용하는 단점이 있다면 분할 기반 클러스터링은 반복 최적화 알고리듬의 사용으로 연산량의 요구가 큰 단점이 있다. 이 논문은 이들 중 가장 널리 사용되고 있는 분할 기반 클러스터링 기법을 대상으로 한다.

후속연구

이러한 이론을 이용한 것으로 명시적으로 언급하지는 않았지만 많은 FCM의 변형들이 기존 이론의 틀에서 설명될 수 있는 것을 볼 때, 향후 FCM의 연구 방향은 기존 이론의 적용 범위를 명확히 하는 일반화된 알고리듬으로의 발전과 클러스터링이라는 주제에 맞게 이론을 재정립하는 방향으로 진행될 것으로 생각된다. 또한 이 논문에서는 다루지 않았지만 FCM의 개선에 더불어 주어진 문제의 사전 지식을 활용함으로써 보다 나은 성능을 얻을 수 있을 것이다.
하지만 FCM은 여러 가지 해결되지 못한 문제들이 있으며 이 논문에서는 이들 문제점들을 살펴보고 이를 해결할 수 있는 연구 방향을 살펴 보았다. 비록 제시된 방법들이 기존 방법들에 비해 항상 나은 성능을 보이지는 않으며 향후 더 많은 연구가 필요한 방법들이지만 이들 사이에는 한 가지 공통점을 발견할 수 있다. 즉, 수학 또는 통계학에서 정립된 이론들을 도입하여 FCM의 문제점을 해결하고자 하는 시도들이 다른 방법들에 비해 활용도 및 확장 가능성이 높다는 점이다.
FCM의 문제점을 해결하기 위해 도입된 수학 및 통계학 이론들로는 가설 검증, regularization, robust statistics, 커널 이론, 그래프 이론, 정보 이론 등이 있다. 이러한 이론을 이용한 것으로 명시적으로 언급하지는 않았지만 많은 FCM의 변형들이 기존 이론의 틀에서 설명될 수 있는 것을 볼 때, 향후 FCM의 연구 방향은 기존 이론의 적용 범위를 명확히 하는 일반화된 알고리듬으로의 발전과 클러스터링이라는 주제에 맞게 이론을 재정립하는 방향으로 진행될 것으로 생각된다. 또한 이 논문에서는 다루지 않았지만 FCM의 개선에 더불어 주어진 문제의 사전 지식을 활용함으로써 보다 나은 성능을 얻을 수 있을 것이다.
기존의 많은 방법들이 문제 영역의 지식들을 활용하는 전용 방법들인데 반해 이 논문에서는 모든 문제에 적용이 가능한 범용 방법들에 중점을 둔다. 제시하는 방법들은 현재 연구가 진행 중인 방법들로 향후 많은 연구가 필요하지만 지금까지 소개된 방법들 중 성능이 우수할 뿐만이 아니라 확장 및 발전 가능성이 높은 방법들로 FCM 뿐만이 아니라 클러스터링의 문제를 해결하기에 현 시점에서 좋은 출발점이 될 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	계층적 클러스터링에는 어떠한 방법이 있는가?	이 중 대표적인 클러스터링 기법으로는 계층적 클러스터링 (hierarchical clustering)과 분할 기반 클러스터링 (partitional clustering)이 있다. 계층적 클러스터링은 클러스터의 계층 구조를 구성하는 방식으로 하나의 클러스터에서 시작해서 연속적으로 클러스터를 나누어 가는 하향식 (top-down) 방법과 하나의 데이터 포인트로 구성되는 N개의 클러스터에서 시작해서 클러스터를 뭉쳐 가는 상향식 (bottom-up) 방법이 있다. 이에 비해 분할 기반 클러스터링은 K개의 원형(prototype)을 설정하고 가장 가까운 원형에 데이터 포인트를 할당하는 과정을 반복함으로써 K개 원형을 찾아내는 방식이다.
	분할 기반 클러스터링 기법 중 K-means이 hard clustering이라고도 불리는 이유는?	분할 기반 클러스터링 기법은 일반적으로 K-means[2]를그 시초로 생각한다. K-means는 주어진 K개 원형에 데이터 포인트가 속하는지의 여부를 속하거나 (1로 표현) 속하지 않는 (0으로 표현) 이산적인 값으로 나타내므로 hard clustering이라고도 불린다. 이러한 소속 여부 표시 방법은 클러스터들이 중첩되어 나타나거나 잡음이 첨가된 경우에는 대처하기 어려우므로 소속 정도를 연속적인 소속도 값으로 나타내는 fuzzy c-means(FCM)가 제안되었다.
	분할 기반 클러스터링이란?	계층적 클러스터링은 클러스터의 계층 구조를 구성하는 방식으로 하나의 클러스터에서 시작해서 연속적으로 클러스터를 나누어 가는 하향식 (top-down) 방법과 하나의 데이터 포인트로 구성되는 N개의 클러스터에서 시작해서 클러스터를 뭉쳐 가는 상향식 (bottom-up) 방법이 있다. 이에 비해 분할 기반 클러스터링은 K개의 원형(prototype)을 설정하고 가장 가까운 원형에 데이터 포인트를 할당하는 과정을 반복함으로써 K개 원형을 찾아내는 방식이다. 계층적 클러스터링이 클러스터의 분할 또는 병합 과정에서 국부적인 정보만을 활용하는 단점이 있다면 분할 기반 클러스터링은 반복 최적화 알고리듬의 사용으로 연산량의 요구가 큰 단점이 있다.

참고문헌 (40)

R. Xu and D. Wunsch, Clustering, Wiley-IEEE Press, 2008.
J. B. MacQueen, "Some methods for classification and analysis of multivariate observations," Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, University of California Press, pp. 281-297, 1967.
L. A. Zadeh, "Fuzzy sets," Information and Control vol. 8, no. 3, pp. 338-353, 1965.

상세보기
E. H. Ruspini, "A new approach to clustering," Information and Control, vol. 16, pp. 22-32, 1969.
J. C. Dunn, "A fuzzy relative of the ISODATA process and its use in detecting compact well separated clusters," Journal of Cybernetics, pp. 32-57, 1974
J. C. Bezdek, Pattern Recognition with Fuzzy Objective Function Algorithms, Springer, 1981.
H. Frigui and R. Krishnapuram, "Clustering by competitive agglomeration," Pattern Recognition, vol. 30, no. 7, pp. 1109-1119, 1997.

상세보기
Gyeongyong Heo, Young Woon Woo, "Extensions of X-means with Efficient Learning the Number of Clusters ," Journal of the KIMICS, Vol. 12, No. 4, pp. 772-780, 2008
G. Heo and P. Gader, "Learning the Number of Gaussian Components Using Hypothesis Test," Proceedings of the 2009 International Joint Conference on Neural Networks, pp. 1206-1212, 2009.
A. P. Dempster, N. M. Laird, and D. B. Rubin, "Maximum Likelihood from Incomplete Data via the EM Algorithm," Journal of the Royal Statistical Society, Series B, vol. 39, no. 1, pp. 1-38, 1977.
Z. Zhang, C. Chen, J. Sun, and K. L. Chan, "EM algorithms for Gaussian mixtures with split-and-merge operation," Pattern Recognition, vol. 36, no. 9, pp. 1973-1983, 2003.

상세보기
Y. Li and L. Li, "A Novel Split and Merge EM Algorithm for Gaussian Mixture Model," Proceedings of the 5th International Conference on Natural Computation, pp. 479-483, 2009.
R. N. Dave, "Characterization and detection of noise in clustering," Pattern Recognition Letters, vol. 12, no. 11, pp. 657-664, 1991.

상세보기
Y. Namkoong, G. Heo, and Y. W. Woo, "An Extension of Possibilistic Fuzzy C-Means with Regularization," Proceedings of the 2010 IEEE International Conference on Fuzzy Systems, pp. 696-701, 2010.
A. Tikhonov, "On solving incorrectly posed problems and method of regularization," Dokl. Acad. Nauk USSR, vol. 151, pp. 501-504, 1963.
G. Heo, P. Gader, and H. Frigui, "RKF-PCA: Robust Kernel Fuzzy PCA," Neural Networks, vol. 22, no. 5-6, pp. 642-650, 2009.

상세보기
C. F. Lin and S. D. Wang, "Fuzzy support vector machines," IEEE Transactions on Neural Networks, vol. 13, no. 2, pp. 464-471, 2002.

상세보기
P. J. Huber and E. M. Ronchetti, Robust Statistics, 2nd edition, Wiley, 2009.
R. Krishnapuram and J. M. Keller, "A Possibilistic Approach to Clustering," IEEE Transactions on Fuzzy Systems vol. 1, no. 2, pp. 98-110, 1993.

상세보기
N. R. Pal, K. Pal, J. M. Keller and J. C. Bezdek, "A Possibilistic Fuzzy c-Means Clustering Algorithm," IEEE Transactions on Fuzzy Systems vol. 13, no. 4, pp. 517-530, 2005.

상세보기
Gyeongyong Heo, Sewoon Choe, Young Woon Woo, " Improvement of the PFCM(Possibilistic Fuzzy C-Means) Clustering Method," Journal of the KIMICS, Vol. 13, No. 1, pp. 177-185, 2009.
B. Feil and J. Abonyi, "Geodesic Distance Based Fuzzy Clustering," Advances in Soft Computing, vol. 39/2007, pp. 50-59, 2007.
F. Fouss, A. Pirotte, J. M. Renders, and M. Saerens, "Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation," IEEE Transactions on Knowledge and Data Engineering, vol. 19, no. 3, pp. 355-369, 2007.

상세보기
B. Scholkopf and A. J. Smola, Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press, Cambridge, MA, 2001.
M. Girolami, "Mercer kernel-based clustering in feature space," IEEE Transactions on Neural Networks, vol. 13, no. 3, pp. 780-784, 2002.

상세보기
M. Filippone, F. Camastra, F. Masulli, and S. Rovetta, "A survey of kernel and spectral methods for clustering," Pattern Recognition, vol. 41, no. 1, pp. 176- 190, 2008.

상세보기
J. Shi and J. Malik, "Normalized cuts and image segmentation," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 2, no. 8, pp. 888-905, 2000.
U. von Luxburg, "A tutorial on spectral clustering," Statistics and Computing, vol. 17, no. 4, pp. 395-416, 2007.

상세보기
Gyeongyong Heo, Kwang-Baek Kim, Young Woon Woo, "Magnifying Block Diagonal Structure for Spectral Clustering ," Journal of Korea Multimedia Society, Vol. 11, No. 9, pp. 1302-1309, 2008
I. S. Dhillon, Y. Guan, and B. Kulis, "A unified view of kernel k-means, spectral clustering and graph cuts," Department of Computer Science, University of Texas, Tech. Rep. TR-04-25, 2005.
M. Garey, D. Johnson, and H. Witsenhausen, "The complexity of the generalized Lloyd-Max problem," IEEE Transactions on Information Theory, vol. 28, no. 2, pp. 255-256, 1982.

상세보기
J. He, M. Lan, C. L. Tan, S. Y. Sung, and H. B. Low, "Initialization of cluster refinement algorithms: A review and comparative study," Proceedings of the 2004 IEEE International Joint Conference on Neural Networks, pp. 297-302, 2004.
A. Likas, N. Vlassis, and J. J. Verbeek, "The global k-means clustering algorithm," Pattern Recognition, vol. 36, pp. 451-461, 2003.

상세보기
G. Heo and P. Gader, "An Extension of Global Fuzzy C-means Using Kernel Methods," Proceedings of the 2010 IEEE International Conference on Fuzzy Systems, pp. 690-695, 2010.
X. L. Xie and G. Beni, "A validity measure for fuzzy clustering," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 13, no. 8, pp. 841-847, 1991.

상세보기
M. Meila, "Comparing clusterings - an information based distance," Journal of Multivariate Analysis, vol. 98, no. 5, pp. 873-895, 2007.

상세보기
D. Pascual, F. Pla, and J. S. Sanchez, "Cluster validation using information stability measures," Pattern Recognition Letters, vol. 31, pp. 454-461, 2010.

상세보기
Q. Deng, Y. Luo, and J. Ge, "Dual threshold based unsupervised face image clustering," Proceedings of the 2nd International Conference on Industrial Mechatronics and Automation, pp. 436-439, 2010.
D. Jiang, C. Tang, A. Zhang, "Cluster analysis for gene expression data: a survey," IEEE Transactions on Knowledge and Data Engineering, vol. 16, no. 11, pp. 1370-1386, 2004.

상세보기
L. J. P. van der Maaten, E. O. Postma, and H. J. van den Herik, "Dimensionality Reduction: A Comparative Review," Tilburg University, Technical Report, TiCC-TR 2009-005, 2009.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증