데이터의 군집을 찾아내는 문제는 패턴 인식, 이미지 처리, 시장 조사 등 많은 응용 분야에서 널리 사용되고 있다. 군집의 질을 결정하는 핵심 요소로는 유사 측도, 차원의 개수 등이 있다. 유사 측도는 데이터의 특성을 반영하여 다르게 정의되어야 하는데, 대부분 기존의 연구들은 데이터를 특징 지어주는 속성이 수치형으로 주어진 경우에 국한되어 있었다. 속성이 범주형으로 주어진 경우도 실생활에 많이 존재하지만, 범주형 변수에 대한 속성값의 유사성은 값의 순서가 고유하게 정해지지 않아서 정의하기 어렵다. 이에 더하여, 고차원 데이터에 대해서는 데이터 점들이 희박하게 위치하여 가까운 점과 먼 점간의 차이가 거의 없고, 군집화 결과가 좋지 않을 수 있다. 이 문제를 해결하기 위해 부분 차원 군집화 방법이 제안되어 왔다. 부분 차원 군집화 방법은 각 군집을 발견하기에 적합한 부분 차원을 선택하면서 군집화를 수행하는 방법이다. 본 논문에서는 범주형 속성으로 특징지어진 고차원 데이터를 부분 차원 군집화하기 위한 새로운 유사 측도를 제안한다. 유사 측도는 각 군집은 다른 군집과 구별되는 특정 정보를 잘 표현할 수 있어야 한다는 기본적인 가정 하에 속성들 사이의 상관성을 반영하여 정의되었다. 이들 모두를 반영한 유사측도는 기존에 존재하지 않았다는 점에서 본 연구는 의미가 있다. 실제 데이터 집합을 군집화하는 실험을 통해 제안하는 방법이 다른 군집화 방법보다 저차원 데이터와 고차원 데이터 모두에 대해 좀 더 정확한 군집 결과를 얻을 수 있음을 보였다.
데이터의 군집을 찾아내는 문제는 패턴 인식, 이미지 처리, 시장 조사 등 많은 응용 분야에서 널리 사용되고 있다. 군집의 질을 결정하는 핵심 요소로는 유사 측도, 차원의 개수 등이 있다. 유사 측도는 데이터의 특성을 반영하여 다르게 정의되어야 하는데, 대부분 기존의 연구들은 데이터를 특징 지어주는 속성이 수치형으로 주어진 경우에 국한되어 있었다. 속성이 범주형으로 주어진 경우도 실생활에 많이 존재하지만, 범주형 변수에 대한 속성값의 유사성은 값의 순서가 고유하게 정해지지 않아서 정의하기 어렵다. 이에 더하여, 고차원 데이터에 대해서는 데이터 점들이 희박하게 위치하여 가까운 점과 먼 점간의 차이가 거의 없고, 군집화 결과가 좋지 않을 수 있다. 이 문제를 해결하기 위해 부분 차원 군집화 방법이 제안되어 왔다. 부분 차원 군집화 방법은 각 군집을 발견하기에 적합한 부분 차원을 선택하면서 군집화를 수행하는 방법이다. 본 논문에서는 범주형 속성으로 특징지어진 고차원 데이터를 부분 차원 군집화하기 위한 새로운 유사 측도를 제안한다. 유사 측도는 각 군집은 다른 군집과 구별되는 특정 정보를 잘 표현할 수 있어야 한다는 기본적인 가정 하에 속성들 사이의 상관성을 반영하여 정의되었다. 이들 모두를 반영한 유사측도는 기존에 존재하지 않았다는 점에서 본 연구는 의미가 있다. 실제 데이터 집합을 군집화하는 실험을 통해 제안하는 방법이 다른 군집화 방법보다 저차원 데이터와 고차원 데이터 모두에 대해 좀 더 정확한 군집 결과를 얻을 수 있음을 보였다.
The problem of finding clusters is widely used in numerous applications, such as pattern recognition, image analysis, market analysis. The important factors that decide cluster quality are the similarity measure and the number of attributes. Similarity measures should be defined with respect to the ...
The problem of finding clusters is widely used in numerous applications, such as pattern recognition, image analysis, market analysis. The important factors that decide cluster quality are the similarity measure and the number of attributes. Similarity measures should be defined with respect to the data types. Existing similarity measures are well applicable to numerical attribute values. However, those measures do not work well when the data is described by categorical attributes, that is, when no inherent similarity measure between values. In high dimensional spaces, conventional clustering algorithms tend to break down because of sparsity of data points. To overcome this difficulty, a subspace clustering approach has been proposed. It is based on the observation that different clusters may exist in different subspaces. In this paper, we propose a new similarity measure for clustering of high dimensional categorical data. The measure is defined based on the fact that a good clustering is one where each cluster should have certain information that can distinguish it with other clusters. We also try to capture on the attribute dependencies. This study is meaningful because there has been no method to use both of them. Experimental results on real datasets show clusters obtained by our proposed similarity measure are good enough with respect to clustering accuracy.
The problem of finding clusters is widely used in numerous applications, such as pattern recognition, image analysis, market analysis. The important factors that decide cluster quality are the similarity measure and the number of attributes. Similarity measures should be defined with respect to the data types. Existing similarity measures are well applicable to numerical attribute values. However, those measures do not work well when the data is described by categorical attributes, that is, when no inherent similarity measure between values. In high dimensional spaces, conventional clustering algorithms tend to break down because of sparsity of data points. To overcome this difficulty, a subspace clustering approach has been proposed. It is based on the observation that different clusters may exist in different subspaces. In this paper, we propose a new similarity measure for clustering of high dimensional categorical data. The measure is defined based on the fact that a good clustering is one where each cluster should have certain information that can distinguish it with other clusters. We also try to capture on the attribute dependencies. This study is meaningful because there has been no method to use both of them. Experimental results on real datasets show clusters obtained by our proposed similarity measure are good enough with respect to clustering accuracy.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
기술한다. UCI machine Learning Repository [23] 에서 제공하는 Breast Cancer, Congressional voting, Soybean 데이터를 이용하여 제안하는 측도의 효용성을 평가하고자 하였다. 이 데이터들은 범주형 데이터 군집화 알고리즘의 성능을 측정하기 위해 널리 사용되어 왔다.
부분 차원 군집화 방법은 좋은 군집이라면 최소한몇몇의 속성에 대해 특정 속성값을 가진 집합으로 정의되어야 한다는 가정에 기초한다. 본 논문에서는 군집이 어떤 속성값과 연관되어 있는지를 반영하여 군집 내 속성값에 대한 편향성을 정의한다. 다시 말해, 속성의 편향성은 동일한 속성 At와 속성값 Xt에 대해서 각 군집 별로 다를 수 있고, 동일한 군집에 대해서도 속성 및 속성값 별로 다를 수 있다.
그러나 각 속성에서의 정보량과 엔트로피만을 이용하여 군집화를 수행하면 속성 간의 의존성을 무시하여 정확하지 못한 결과를 낼 가능성이 있다. 본 논문에서는 이러한 문제점들을 보완할 수 있는 새로운 유사 측도를 제안하였다. 그리고 개선된 k-평균 군집화 알고리즘에 제안하는 유사 측도를 사용하여 다양한 실험을 하였다.
본 논문에서는 좋은 군집은 특정 정보를 잘 표현할 수 있어야 한다는 기본적인 가정 하에 속성들 사이의 상관성을 반영한 새로운 유사 측도를 제안하였다. 개념적 군집화와 엔트로피 기반의 군집화는 범주형 데이터에 대해 대체로 좋은 결과를 낸다고 밝혀져 있다.
시도가 있었다. 이는 다른 확률 변수에 비하여 군집의 특정 정보를 표현하는 확률 변수를 압축함으로 고차원 데이터의 잡음을 줄이고, 더 조밀하고 엄정하게 내재된 구조를 잘 반영하는 자료를 산출하도록 한다. 여기서 군집의 특정 정보란 군집에 속하는 객체의 속성값으로 특징지어질 수 있다.
가설 설정
N개의 객체로 이루어진 데이터 집합 U에 대해 객체 각각을 특징지어 줄 수 있는 이개의 속성 Ai, A爲 …, Am을 선택하고, m차원 공간에 표시되어 있다고 가정한다. At(l^t< nF에는 유한한 이산형 값이 존재한다고 가정한다. Xt 는각 속성에서의 속성값을 가지는 이산형 랜덤 변수를 표현하고, U=(X1, X2, …, Xm)는 U에 속하는 값을 가질 수 있는 이산형 랜덤 변수를 나타내는 것으로 한다.
먼저 본 논문에서 사용할 표기법에 대해서 정의한다. N개의 객체로 이루어진 데이터 집합 U에 대해 객체 각각을 특징지어 줄 수 있는 이개의 속성 Ai, A爲 …, Am을 선택하고, m차원 공간에 표시되어 있다고 가정한다. At(l^t< nF에는 유한한 이산형 값이 존재한다고 가정한다.
군집화의 결과를 측정하기 위해, 우리는 이미 이상적으로 분류된 데이터를 알고 있다고 가정한다. 그리고 실험으로 얻어진 군집과 실제 분할에 모두 속하는 객체의 개수로 군집화의 질을 측정한다.
우선, 주어진 데이터 객체 각각을 특징지어 줄 수 있는 속성들이 주어졌다고 가정한다. 속성 변수의 특징에 따라 데이터 유형은 크게 수치형(numeric), 범주형(ca tegorical), 혼합형(mixed) 데이터로 나뉜다.
예제 2. 위의 표 3은 영화 데이터 베이스 개체로, 이상적 군집의 개수는 2이고 객체 5〜05는 각각 군집 Ci 또는 Cm] 이미 할당되었다고 가정한다. 09와 군집 C1, 09와 군집 C2와의 속성 director에 대한 유사도를 각각 구하는 방법에 대해서 생각해 본다.
제안 방법
본 논문에서는 이러한 문제점들을 보완할 수 있는 새로운 유사 측도를 제안하였다. 그리고 개선된 k-평균 군집화 알고리즘에 제안하는 유사 측도를 사용하여 다양한 실험을 하였다. 실제 데이터 집합을 군집화하는 실험을 통하여 제안하는 방법이 고차원 데이터는 물론 저차원 범주형 데이터에 대해서도 정확한 군집 결과를 찾을 수 있음을 보였다.
먼 점 초기화 알고리즘은 좋은 성능을 낸다는 것이 이미 밝혀진 바 있다. 둘째, 초기화 단계에서 N-k개의 객체를 분류할 때, 각 객체를 군집에 할당할 때마다 군집의 정보를 갱신하도록 한다. 본 논문에서 사용하는 군집화 알고리즘은 그림 2와 같다.
이에 따라 범주 효용은 군집의 정보가 주어졌을 경우 그렇지 않을 경우보다 정확히 예측되는 속성값들의 개수의 증가량의 추정을 의미한다. 범주 효용은 클래스 내(intraclass) 유사성과 클래스 간(interclass) 상이성을 평가한다. 이에 대한 더 자세한 설명은 본 논문에서 생략한다.
본 논문에서는 고차원 범주형 데이터의 부분 차원 군집화에 적합한 새로운 유사 측도를 정의한다 제안된 유사 측도는 좋은 군집은 특정 정보를 잘 표현할 수 있어야 한다는 기본적인 가정하에 속성들 사이의 상관성을 반영하여 정의한다. k-평균 군집화(k-Means cluste ring) 방법에 제안된 유사 측도를 사용하여 효과적인 군집화가 가능함을 보인다.
예제 2에서 객체와 군집간의 유사도를 계산하는 과정을 통해 군집화 과정에서 편향성이 어떠한 영향을 주는지 살펴보도록 한다.
k-평균 군집화(k-Means cluste ring) 방법에 제안된 유사 측도를 사용하여 효과적인 군집화가 가능함을 보인다. 제안하는 유사 측도의 유효성은 범주형 데이터 군집화 알고리즘의 성능을 측정하기 위해 널리 사용되는 데이터를 군집화한 결과로부터 측정하였다.
대상 데이터
본 논문에서는 제안된 유사 측도의 유효성올 검증하기 위해 Breast Cancer 데이터, Congressional voting 데이터, soybean 데이터를 군집화 하였다. 우선, Breast cancer 데이터는 699개의 객체로 이루어져 있고, 각 객체는 9개의 속성으로 특징지어진다, 객체는 benign 과 malignant 중의 한 군집으로 할당되어 있다, 군집들은 458개와 241개의 객체로 이루어진다.
soybean 데이터를 군집화 하였다. 우선, Breast cancer 데이터는 699개의 객체로 이루어져 있고, 각 객체는 9개의 속성으로 특징지어진다, 객체는 benign 과 malignant 중의 한 군집으로 할당되어 있다, 군집들은 458개와 241개의 객체로 이루어진다. 각 속성은 2〜10개의 중복되지 않는 속성값을 갖는다.
이론/모형
다르다. 첫째, 먼 점 초기 선택 알고리즘(furthest first algorithm)[22]을 사용하여 초기 군집의 정보가 군집화를 수행하는 데 적절한 정보를 제공하도록 한다. 먼 점 초기화 알고리즘은 좋은 성능을 낸다는 것이 이미 밝혀진 바 있다.
성능/효과
9 이상의 정확도로 정확한 군집을 찾는데 효과적인 것을 확인할 수 있다. Breast cancer 데이터의 적절한 군집은 엔트로피를 이용한 군집화 과정으로 찾을 수 있고, 제안된 유사 측도는 엔트로피 개념을 반영하여 적절하게 정의되었음을 알 수 있다.
COOLCAT 과 제안된 방법을 사용하여 군집화를 수행한 결과 모두가 0.9 이상의 정확도로 정확한 군집을 찾는데 효과적인 것을 확인할 수 있다. Breast cancer 데이터의 적절한 군집은 엔트로피를 이용한 군집화 과정으로 찾을 수 있고, 제안된 유사 측도는 엔트로피 개념을 반영하여 적절하게 정의되었음을 알 수 있다.
정의한다. k-평균 군집화(k-Means cluste ring) 방법에 제안된 유사 측도를 사용하여 효과적인 군집화가 가능함을 보인다. 제안하는 유사 측도의 유효성은 범주형 데이터 군집화 알고리즘의 성능을 측정하기 위해 널리 사용되는 데이터를 군집화한 결과로부터 측정하였다.
특히, 본 논문에서 제안한 군집화 방법을 사용하여 정확한 군집을 찾을 수 있는데, 이는 이상적 군집의 개수가 많아서 군집 각각이 특정한 정보를 포함할 가능성이 높게 되고, 식 (7) 에서부분 차원 군집화 방법의 개념을 이용해 정의한 편향성의 영향이 극대화 된 것이라 생각된다. 결과적으로, 실제 데이터 집합을 군집화하는 실험을 통해서, 제안하는 방법이 저차원 범주형 데이터 뿐만 아니라 고차원 범주형 데이터에 대해서도 정확한 군집을 찾는데 효과적임을 확인하였다.
그리고 개선된 k-평균 군집화 알고리즘에 제안하는 유사 측도를 사용하여 다양한 실험을 하였다. 실제 데이터 집합을 군집화하는 실험을 통하여 제안하는 방법이 고차원 데이터는 물론 저차원 범주형 데이터에 대해서도 정확한 군집 결과를 찾을 수 있음을 보였다.
표 10과 11은 각각 16개, 35개의 속성으로 각각 특징지어진 Congressional voting 데이터와 Soybean 데이터를 군집화한 결과이다. 이들은 본 논문에서 제안한 방법이 속성의 개수에 따라 군집화 결과가 영향을 받는 COOLCAT보다 좋은 군집화 결과를 얻을 수 있음을 보여준다. 제안한 방법이 고차원 데이터에 대해서도 좋은 결과를 가져오는 이유는 부분 차원 군집화 방법의 개념으로부터 정의된 편향성이 군집화 과정에서 잘 반영되었기 때문이다.
표 11의 결과로부터 Soybean 데이터는 ROCK으로 좋은 군집을 찾을 수 없는 데이터에 속한다고 판단할 수 있다. 이에 더하여, 제안된 방법은 k-평균 군집화에 기반하여 군집화 과정을 진행하였고, COOLCAT과 ROCK은 계층적 방법에 기반한 방법이라는 점에서 제안된 방법이 좀 더 빠르게 군집을 찾을 수 있다. 참고로 k-평균 군집화의 시간 복잡도는 O(kN)[28] 이고, 계층적 방법에 시간 복잡도는 O(N2logN)[29] 이다.
표 10과 표 11에서 Congressional voting 데이터에 대해서 ROCK을 사용한 군집화 결과가 제안한 방법을 사용한 군집화 결과보다 좋고, Soybean 데이터에 대해서는 그렇지 않은 것을 알 수 있다. 표 11의 결과로부터 Soybean 데이터는 ROCK으로 좋은 군집을 찾을 수 없는 데이터에 속한다고 판단할 수 있다.
참고문헌 (29)
H. Jiawei and K. Micheline, Data Mining: Concepts and Techniques, 2rd ed., pp.383-444, Morgan Kaufmann, 2006.
A. Ahmad and L. Dey, A k-mean clustering algorithm for mixed numeric and categorical data, Data & Knowledge Engineering, vol.63, Issue 2, pp.503-527, 2007.
P. H. A. Sneath and R. R. Sokal, Numerical Taxonomy: The Principles and Practice of Numerical Classication, W. H. Freeman and Company, 1973.
C. Ding, X. He, H. Zha, and H. D. Simon, Adaptive dimension reduction for clustering high dimensional data. Proceedings of Second IEEE International Conference on Data Mining, pp. 147-154, 2002.
L. Yu and H. Liu, Feature selection for highdimensional data: a fast correlation-based filter solution. Proceedings of the twentieth International Conference on Machine Learning, pp.856-863, 2003.
S. Raychaudhuri, P. D. Sutphin, J. T. Chang, and R. B. Altman, Basic microarray analysis: grouping and feature reduction. Trends in Biotechnology, vol.19, no.5, pp.189-193, 2001.
J. MacQueen, Some methods for classification and analysis of multivariate observation. Proceedings of the fifth Berkeley Symp. on Math. Statist. and Prob., vol.1, pp.281-297, 1966.
Z. Huang, Extensions to the k-means algorithm for clustering large data sets with categorical data. Data Mining and Knowledge Discovery, vol.2, no.3, pp.283-304, 1998.
L. Kaufman and P. Rousseeuw, Clustering by means of medoids. In Dodge, Y. (Ed.) Statistical Data Analysis based on the L1 Norm. pp.405-416, 1987.
Z. He, X. Xu and S. Deng, Squeezer: an efficient algorithm for clustering categorical data. Journal of Computer Science and Technology, vol.17, no.5, pp.611-624, 2002.
S. Guha, R. Rastogi and K. Shim, ROCK: a robust clustering algorithm for categorical attributes. Proceedings of the 15th International Conference on Data Engineering, pp.512-521, 1999.
D. H. Fisher, Knowledge acquisition via incremental conceptual clustering. Machine Learning, vol.2, no.2, pp.139-172, 1987.
M. Gluck and J. Corter, Information, Uncertainty, and the Utility of Categories. Proceedings of Seventh Annual Conference of Cognitive Science Society, pp.283-287, 1985.
Z. Huang and M.K. Ng, A fuzzy k-modes algorithm for clustering categorical data. IEEE Transactions on Fuzzy Systems, vol.7, no.4, pp.446-452, 1999.
K.B. McKusick and K. Thompson, COBWEB/3: A portable implementation, Report FIA-90-6-18-2, NASA, Ames Research Center, 1990.
Y. Reich and S.J. Fenves, The formation and use of abstract concepts in design. Concept Formation: Knowledge and Experience in Unsupervised Learning, Morgan Kaufmann, 1991.
G. Biswas, J. Weinberg, and C. Li, ITERATE: A conceptual clustering scheme for knowledge discovery in databases. Artificial Intelligence in the Petroleum Industry, B. Braunschweig and R. Day eds., pp.111-139, 1995.
P. Andritsos, P. Tsaparas, R.J. Miller and K.C. Sevcik, LIMBO: Scalable clustering of categorical data. Proceedings of the 9th International Conference on Extending DataBase Technology (EDBT), 2004.
D. Barbara, Y. Li and J. Couto, COOLCAT: an entropy-based algorithm for categorical clustering. Proceedings of ACM Conf. on Information and Knowledge Mgt. (CIKM), pp.582-589, 2002.
T. Cover, J. Thomas, Elements of information theory, Wiley InterScience, 1991.
D. Hochbaum and D. Shmoys, A best possible heuristic for the k-center problem. Mathematics of Operations Research, vol.10, no.2, pp.180-184, 1985.
C. J. Merz and P. Merphy, UCI Repository of Machine Learning Databases, 1996. Available from: .
Z. Huang, A fast clustering algorithm to cluster very large categorical data sets in data mining. Proceedings of SIGMOD Workshop on Research Issues on Data Mining and Knowledge Discovery, pp.1-8, 1997.
F. Cao, J. Liang and L. Bai, A new initialization method for categorical data clustering, Expert Systems With Applications: An International Journal archive, vol.36, Issue 7, pp.10223-102228, 2009.
M. Al-Razgan, C. Domeniconi and D. Barbara, Random Subspace Ensembles for Clustering Categorical Data. Studies in Computational Intelligence, Springer, 2008.
B. Broda and M. Piasecki, Experiments in Clustering Documents for Automatic Acquisition of Lexical Semantic Networks for Polish, Proceedings of the 16th International Conference Intelligent Information Systems, 2008, pp.203-202, 2008.
A. M. Fahim, G. Saake, A. M. Salem, F. A. Torkey, and M. A. Ramadan, k-Means for Spherical Clusters with Large Variance in Sizes, Proceedings of World Academy of Science, Engineering and Technology, vol.35, pp.177-182, 2008.
K. Qin, M. Xu, Y. Du, and S. Yue, Cloud Model and Hierarchical Clustering Based Spatial Data Mining Method and Application, Proceedings of the International Archives of the Photogrammetry, Remote Sensing and Spatial information Sciences, vol.37, pp.241-246, 2008.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.