Your browser does not support the PubReader view.
Go to this page to see a list of supporting browsers.
Korean Academic Society of Business Administration
[ Article ]
korean management review - Vol. 46, No. 4, pp.1201-1226
ISSN: 1226-1874 (Print)
Print publication date 31 Aug 2017
Received 06 Dec 2016 Revised 18 May 2017 Accepted 07 Jul 2017
DOI: https://doi.org/10.17287/kmr.2017.46.4.1201

Fuzzy K-means 군집분석을 위한 다양한 유효성 지수 개발

이수현* ; 김재윤** ; 정영선***
*(주저자) 전남대학교 기후특성화대학원, 박사후연구원 lovingsh79@jnu.ac.kr
**(공저자) 전남대학교 경영학부, 교수 jaeyun@jnu.ac.kr
***(교신저자) 전남대학교 산업공학과, 조교수 young.jeong@jnu.ac.kr
Various Validity Indices for Fuzzy K-means Clustering
Soo-Hyun Lee* ; Jae-Yun Kim** ; Young-Seon Jeong***
*Post-Doc., The Graduate Program on Climate Change, Sustainability and Business, Chonnam National University, First Author
**Professor, Dept. of Business Administration, Chonnam National University, Co-Author
***Assistant Professor, Dept. of Industrial Engineering, Chonnam National University, Corresponding Author

초록

경영학 분야에서는 군집분석을 이용하여 동질적인 특성을 지닌 집단을 도출하고 이를 재무, 마케팅, 생산관리 분야 등에서 다양하게 활용하고 있다. 따라서 군집분석에 의한 군집화 결과는 기업의 가치를 극대화 시킬 수 있는 핵심자원의 역할을 하고 있다. 본 연구에서는 군집분석에서 필요한 군집화 결과의 유효성을 검증하는 군집화 유효성 지수(clustering validity index)의 개발에 관한 이론적 연구를 다루고자 한다. 구체적으로, 다양한 형태의 데이터에서 군집화의 유효성 검증 성능이 우수하다고 알려진 Dunn(DU) 지수, Calinski and Harabasz(CH) 지수, 그리고 Davies-Bouldin(DB) 지수들을 응집도와 분리도의 개념으로 분해하고, 각 CVI의 응집도 계산에 서포트 벡터 데이터 표현(support vector data description) 개념을 반영하여 새로운 CVI들을 제안하였다. 그리고 Fuzzy K-means 알고리즘으로 다양한 속성을 갖는 벤치마크 문제를 군집분석한 결과의 유효성을 검증하였다. 새로운 CVI들은 CH와 DB 지수의 약점을 개선하였음을 확인하였다. CH 지수는 노이즈와 비대칭 데이터에서 약점을 가지고 있었고, DB 지수는 부분군집과 임의형상 데이터에서 약점을 가지고 있었다. 본 연구를 통해 SVDD 개념을 CVI의 응집도에 반영할 수 있으며, 이를 반영한 새로운 CVI들은 군집화 유효성 검증에 효과적임을 확인할 수 있었다. 본 연구에서 제안한 CVI의 응집도 계산방법은 기존에 알려진 다양한 CVI의 응집도에 적용이 가능할 것으로 기대된다. 이는 군집분석 대상이 확대되고 연구가 다양해지고 있는 상황에서 군집분석 및 CVI의 이론 확장, 그리고 SVDD 적용범위 확장에 공헌할 것으로 기대된다.

Abstract

Cluster analysis (or Clustering) is used in many different fields such as finance, marketing, and operations management to draw homogeneous cases. Due to that reason, the result extracted from cluster analysis is stated to be the core element to maximize the firm's value. Because the number of clusters in clustering problems is usually unknown, it is significant to evaluate the clustering results produced by different parameter settings. After a range of possible number of clusters are evaluated, the best partition is selected based on the cluster validity analysis. Cluster validity index (CVI) is an indicator to provide a way of validating the quality of clustering algorithms and determine the correct number of clusters in datasets. A CVI is composed of the summation or ratio of compactness and separability measures in which compactness indicates the concentration of data in each cluster and separability refers to the inter-cluster distances. A good clustering result will have smaller compactness and larger separability values. This research will cover the theoretical research of CVI to verify the effectiveness of Fuzzy K-means clustering results among the analytical research methods. Depending on the different combination of compactness and separability measures, several CVIs have been developed. The CVIs calculated by the ratio of compactness to separability or vice versa such as Dunn index, DB index, and XB index were proposed, and the weighted sum of these two measurements was developed as SD index and S_Dbw index. In addition, several variants of conventional CVIs have been recently proposed. However, most of existing CVIs are sensitive to arbitrary shapes of clusters, sub-clusters, and outliers because the measure of compactness of those clusters is not obvious in the original domain. We suggest new CVIs by calculating the concept of Support Vector Data Description (SVDD) in each particular cluster calculation of CVI by separating the compactness and separability about some indices well known to prove effectiveness: Dunn (DU), Calinski and Harabasz (CH), and Davies-Bouldin (DB). By conducting efficiency comparisons utilizing Fuzzy K-means clustering algorithm and various benchmarking instances, the performance rate of new CVIs has been verified with outstanding performance. The performance of noise, skewed, sub-cluster, and arbitral shapes data in the new CVIs is promising in particular. The concept of SVDD has been applied to the compactness by this research and newly created CVIs were verified to be efficient in regards to cluster effectiveness. The compactness calculation method suggested in this research is expected to be widely applied in many different CVIs. As the research of cluster analysis become more expanded and the research follows the step of diversity, this research is expected to contribute the application scope of SVDD and the expansions of both cluster analysis and the concept of CVI

Keywords:

Clustering, CVI, SVDD, Compactness, Fuzzy K-means

키워드:

군집분석, 유효성 지수, 서포트 벡터 데이터 표현, 응집도, 퍼지 K-평균

Acknowledgments

본 연구는 제1저자의 박사학위 논문 일부를 재정리한 내용임

References

  • 김민호·Ramakrishna, R.S.(2005), “비형식의 군집 유효화 지수의 분석과 새로운 지수 개발,” 한국컴퓨터종합학술대회, 32, 601-603.
  • 김민호·유현진·Ramakrishna, R.S.(2005), “고차원 응용에서의 군집 유효성 평가 기법,” 한국정보과학회 2005 가을 학술발표 문집(II), 32, 715-717.
  • 김영옥·이수원(2002), “최적의 군집을 찾기 위한 상대적 군집 평가 방법,” 한국정보과학회 2002 가을 학술발표논문집, 29, 334-336.
  • 송동성·김표재·장형진·최진영(2007), “Negative data를 고려한 K-means Support Vector Data Description,” 대한전기학회 학술대회 논문집, 310-312.
  • 신경석·김재윤(2011), “클러스터 수가 주어지지 않는 클러스터링 문제를 위한 공생 진화알고리즘,” 품질경영학회지, 39, 98-108.
  • 안현철·김경재·한인구(2005), “Support Vector Machine을 이용한 고객구매예측모형,” 한국지능정보시스템학회논문지, 11, 69-81.
  • 오은녕·이희상(2002), “클러스터링 기법을 이용한 이동통신의 고객 세분화 연구,” 한국경영과학회 추계학술대회논문집, 421-424.
  • 용환승·나연묵·박종수·승현우·이민수·이상준·최린(2007), “데이터마이닝,” 서울, 인피니티북스.
  • 이만재(2012), “빅 데이터 어낼리틱스와 공공 데이터 활용,” 정보과학회지, 30, 33-39.
  • 이신원·안동언·정성종(2004), “K-Means 알고리즘을 이용한 계층적 클러스터링에서 클러스터 계층 깊이와 초기값 선정,” 정보관리학회지, 21, 173-185.
  • 이신원(2012), “K-means 클러스터링에서 초기 중심 선정 방법 비교,” 한국인터넷정보학회, 13, 1-8.
  • 이수현(2015), “빅 데이터의 군집분석을 위한 군집화 유효성 지수 개발과 응용,” 전남대학교 대학원 박사학위논문.
  • 전치혁(2012), “데이터마이닝 기법과 응용,” 서울, 한나래.
  • 황인수(2002), “데이터 마이닝에서 그룹 세분화를 위한 2단계 계층적 클러스터링 알고리듬,” 경영과학, 19, 189-196.
  • 허경용·서진석·이임건(2011), “Fuzzy c-means의 문제점 및 해결 방안,” 한국컴퓨터정보학회 논문지, 16, 39-46.
  • Bezdek, J. C.(1981), “Pattern Recognition with Fuzzy Objective Function Algorithm,” Plenum Press, 13, 367-373. [https://doi.org/10.1007/978-1-4757-0450-1]
  • Calinski, R. B., and J. Harabasz(1974), “A Dendrite Method for Cluster Analysis,” Communications in Statistics, 3, 1-27. [https://doi.org/10.1080/03610917408548446]
  • Chang, H. J., P. J. Kim, J. H. Choi, and J.Y. Choi (2007), “Support Vector Data Description Using Clustering Method,” International Technical Conference on Circuits Systems, Computers and Communications, 1132-1133.
  • Davies, D., and D. Bouldin(1979), “A Cluster Separation Measure,” IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-1, 224-227. [https://doi.org/10.1109/TPAMI.1979.4766909]
  • Dunn, J. C.(1973), “A Fuzzy Relative of the ISODATA Process and its Use in Detecting Compact Well Separated Cluster,” Journal of Cybermetics, 3, 32-57. [https://doi.org/10.1080/01969727308546046]
  • Dunn, J. C.(1974), “Well Separated Clusters and Optimal Fuzzy Partitions,” Journal of Cybernetics, 4, 95-104. [https://doi.org/10.1080/01969727408546059]
  • Halkidi, M., and M. Vazirgiannis(2001), “Clustering Validity Assessment: Finding the Optimal Partitioning of a Data Set,” Proceedings of 2001 IEEE International Conference on Data Mining, 187-194.
  • Halkidi, M., Y. Batistakis, and M. Vazirgiannis (2001), “On Clustering Validation Techniques,” Journal of Intelligent Information Systems, 17, 107-145. [https://doi.org/10.1023/A:1012801612483]
  • Hruschka, E. R., R. G. B. Campello, A. A. Freitas, and A. P. L. Carvalho(2009), “A Survey of Evolutionary Algorithms for Clustering,” IEEE Transactions on Systems, Man, and Cybernetics-Part C: Applications and Reviews, 39, 133-155. [https://doi.org/10.1109/TSMCC.2008.2007252]
  • Jain, A. K., M. N. Murty and P. J. Flyn(1999), “Data Clustering: A Review,” ACM Computing Surveys, 31, 264-323. [https://doi.org/10.1145/331499.331504]
  • Ji, R., D. Liu, M. Wu, and J. Liu(2008), “The Application of SVDD in Gene Expression Data Clustering,” The 2nd International Conference on Bioinformatics and Biomedical Engineering, 371-374. [https://doi.org/10.1109/ICBBE.2008.94]
  • Liu, Y., Z. Li, H. Xiong, X. Gao, J. Wu, and S. Wu (2013), “Understanding and Enhancement of Internal Clustering Validation Measures,” IEEE Transactions on Cybernetics, 43, 982-994. [https://doi.org/10.1109/TSMCB.2012.2220543]
  • MacQueen J. B.(1967), “Some Methods for Classification and Analysis of Multivariate Observations,” Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability, 281-297.
  • Maulik, U., and S. Bandyopadhyay(2002), “Performance Evaluation of Some Clustering Algorithms and Validity Indices,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 24, 1650-1654. [https://doi.org/10.1109/TPAMI.2002.1114856]
  • Niazmardi, S., S. Homayouni, and A. Safari(2013), “An Improved FCM Algorithm Based on the SVDD for Unsupervised Hyperspectral Data Classification,” IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 6, 831-839. [https://doi.org/10.1109/JSTARS.2013.2244851]
  • Raspini, E. H.(1969), “A New Approach to Clustering,” Information and Control, 16, 22-32. [https://doi.org/10.1016/S0019-9958(69)90591-9]
  • Saitta, S., B. Raphael, and I. F. C. Smith(2008), “A Comprehensive Validity Index for Clustering,” Intelligent Data Analysis, 12, 529-548. [https://doi.org/10.3233/IDA-2008-12602]
  • Tax, D. M. J., and R. P. W. Duin(2004), “Support Vector Data Description,” Machine Learning, 54, 45-66. [https://doi.org/10.1023/B:MACH.0000008084.60811.49]
  • Tay, F. E. H., and L. J. Cao(2006), “Modified Support Vector Machines in Financial Time Series Forecasting,” Neurocomputing ,48, 847-861. [https://doi.org/10.1016/S0925-2312(01)00676-2]
  • Theodoridis, S. and K. Koutroumbas(2006), Pattern Recognition, Academic Press.
  • Vapnik, V.(1979), Estimation of Dependences Based on Empirical Data[in Russian], Nauka.
  • Xie, XL, Beni, G.(1991), “A Validity Measure for Fuzzy Clustering,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 13, 841-847. [https://doi.org/10.1109/34.85677]
  • Xu, J., J. Yao, and L. Ni(2011), “Fault Detection Based on SVDD and Cluster Algorithm,” International Conference on Electronics, Communications and Control, 2050-2052. [https://doi.org/10.1109/ICECC.2011.6067662]
  • Xu, R. and D. II Wunsch(2005), “Survey of Clustering Algorithms,” IIEEE Transactions on Neural Networks, 16, 645-678. [https://doi.org/10.1109/TNN.2005.845141]

• 저자 이수현은 전남대학교 수학과에서 학사, 동 대학교에서 경영학 석사, 박사학위를 취득하였다. 현재 전남대학교 기후특성화대학원에서 박사후연구원으로 재직 중이다. 관심분야는 최적화, 비즈니스 애널리틱스, 환경경영, 지속가능경영, 생산설비의 수명주기분석 등이다.

• 저자 김재윤은 현재 전남대학교 경영학부 교수로 재직 중이다. 전남대학교 산업공학과에서 학사, 석사, 박사 학위를 취득하였다. 주요 연구분야는 AHP/DEA/BSC 기반 경영성과측정, 생산시스템의 분석과 설계, 진화연산기법을 이용한 조합최적화 문제 해결 등이다.

• 저자 정영선은 현재 전남대학교 산업공학과 조교수로 재직 중이다. 전남대학교 산업공학과를 졸업하였으며, 고려대학교에서 산업공학과 석사, Rutgers University Industrial and Systems Engineering에서 박사학위를 취득하였다. 주요 연구관심분야는 빅데이터 분석, 이상 공정시스템 탐지 방법론 개발, 지능형 교통시스템 구축 등이다.