Data Clustering is one of the most frequently used tools in Data Mining, which refers to the process of partitioning data so that intra-group similarities are maximized and inter-group similarities are minimized at the same time. Data clustering enables us to get a rough idea about the composition of the given dataset. It is especially useful when there is little knowledge about the given dataset.
But as datasets become larger in their volumes and higher in their dimensions, more efficient clustering methods are required. Especially, the high dimensionality of a dataset makes it very difficult to generate a meaningful clustering result because the distance between any data object pair becomes similar in a high dimension.
In this thesis, we present a study of an effective data clustering for a large volume of high dimensional datasets. To deal with the curse of dimensionality, the proposed method follows the philosophy of subspace clustering which assumes that important dimensions can be different between clusters.
We first define a new similarity measure devised for high dimensional datasets. To measure the similarity between two data objects, the proposed similarity measure focuses on the number of dimensions that two objects are near enough from each other, rather than merely averaging the similarities along all dimensions. We then present a novel way to find out each cluster's important dimensions(i.e. subspace). The suggested subspace finding method uses the nearest neighbor query results to gather the information required for selecting important dimensions. The gathered information is used to determine whether each dimension is important or not based on a binomial probability model. Finally we propose an algorithm which adopts our similarity measure and subspace finding method to perform clustering on a large volume of high dimensional dataset.
Through the experiment results on various datasets, the proposed algorithm is shown to meet many requirements for good clustering methods such as accuracy of results, robustness to the noise and the cluster density, and scalability to the dataset size and the dimensionality.
데이타 클러스터링은 데이타 마이닝에서 가장 많이 쓰이는 도구 중 하나로서 데이타를 그룹 내부의 유사성을 최대화하고 그룹들 사이의 유사성을 최소화하도록 그룹화하는 작업을 말한다. 데이타 집합에 데이타 클러스터링 알고리즘을 적용함으로써 우리는 주어진 데이타 집합이 어떠한 성질의 그룹들로 이루어졌는지에 대한 기초적인 지식을 얻을 수 있다. 데이타 클러스터링의 이러한 특성은 주어진 데이타 집합에 대한 지식이 거의 없는 상황에서 특히 유용하다.
그러나 분석해야 할 데이타 집합들의 크기가 커지고 고차원이 되어감에 따라서 좀 더 빠른 클러스터링 알고리즘이 필요하게 되었다. 더욱이 고차원에서는 모든 데이타 객체들 간의 거리가 유사해지기 때문에 의미있는 클러스터링 결과를 생성해내기가 어려워진다.
본 논문에서는 대용량 고차원 데이타 집합을 위한 효과적인 데이타 클러스터링에 관한 연구를 제안한다. 제안하는 방법은 차원의 저주라고 불리는 고차원에서의 문제점을 해결하기 위해서 클러스터별로 중요하게 여기는 차원이 다를 수 있다고 가정하는 부차원 클러스터링 패러다임에 기반한다.
본 논문에서는 먼저 고차원에 특화시킨 새로운 유사성 척도를 정의한다. 두 데이타 객체들 사이의 유사도를 측정하기 위하여 단순히 각 차원별 유사도를 합하는 대신 제안하는 유사성 척도는 두 객체가 얼마나 많은 차원에서 연관성을 가지는지를 측정하여 이를 유사도로 사용한다. 또한 본 논문은 각 클러스터별로 중요한 차원들을 찾아내기 위한 새로운 방식을 제안한다. 제안된 부차원 결정 방식은 최근접 이웃 검색 질의를 사용하여 중요 차원을 선택하기 위한 정보를 모은 후에 이진 확률 모델을 활용하여 클러스터별 부차원을 확정한다. 마지막으로 대용량 고차원 데이타 집합을 겨냥하여 본 논문에서 제안하는 유사성 척도와 부차원 결정 방식을 채용한 새로운 데이타 클러스터링 알고리즘을 제시한다.
다양한 데이타 집합에 대한 실험을 통해서 제안된 알고리즘은 결과의 정확성, 노이즈와 낮은 밀도의 클러스터들에 대한 견고함, 데이타 집합의 크기와 차원의 증가에 대한 확장성 등 좋은 클러스터링 알고리즘이 갖추어야 할 요건들 중 주요한 것들을 모두 만족시켰다. 더욱이 제안된 알고리즘은 부차원 클러스터링 알고리즘임에도 불구하고 알고리즘의 수정 없이도 전차원에 대한 클러스터링 알고리즘으로 사용될 수 있어서 활용성이 좋다.
