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. Experimental results on real datasets show clusters obtained by our proposed similarity measure are good enough with respect to clustering accuracy.
데이터의 군집을 찾아내는 문제는 패턴 인식, 이미지 처리, 시장 조사 등 많은 응용 분야에서 널리 사용되고 있다. 군집의 질을 결정하는 핵심 요소로는 유사 측도, 차원의 개수 등이 있다.
군집화를 하기 위해 주어지는 데이터 유형은 크게 범주형과 수치형이 있다. 유사 측도는 데이터의 특성을 반영하여 다르게 정의되어야 하는데, 대부분 기존의 연구들은 데이터를 특징지어주는 속성이 수치형으로 주어진 경우에 국한되어 있었다. 속성이 범주형으로 주어진 경우도 실생활에 많이 존재하지만, 범주형 변수에 대한 속성값의 유사성은 값의 순서가 고유하게 정해지지 않아서 기존의 유사 측도를 가지고 좋은 군집화 결과를 얻기가 어렵다.
이에 더하여, 고차원 데이터에 대해서는 데이터 점들이 희박하게 위치하여 가까운 점과 먼 점간의 차이가 거의 없고, 군집화 결과가 좋지 않을 수 있다. 이 문제를 해결하기 위해 부분 차원 군집화 방법이 제안되어 왔다. 부분 차원 군집화 방법은 각 군집을 발견하기에 적합한 부분 차원을 선택하면서 군집화를 수행하는 방법이다.
본 논문에서는 범주형 속성으로 특징지어진 고차원 데이터를 부분 차원 군집화하기 위한 새로운 유사 측도를 제안한다. 범주형 데이터 군집화 방법으로 많이 사용되는 개념적 군집화와 엔트로피 기반 군집화 방법은 대체로 좋은 군집화 결과를 낸다는 것이 알려져 있으나, 속성 간의 의존성을 무시하여 정확한 군집을 찾지 못할 가능성이 있다. 제안한 유사 측도는 각 군집은 다른 군집과 구별되는 특정 정보를 잘 표현할 수 있어야 한다는 기본적인 가정 하에 속성들 사이의 상관성을 반영하여 정의된다. 그리고 개선된 k-평균 군집화 알고리즘에 제안한 측도를 사용하여 군집화를 수행하도록 한다. 실제 데이터 셋을 군집화하는 실험을 통하여 제안하는 방법이 고차원 데이터는 물론 저차원 범주형 데이터에 대해서도 정확한 군집 결과를 찾을 수 있음을 보인다.
