Clustering is an important application area for many fields including data mining, pattern recognition, machine learning, and statistical data analysis. In data mining, clustering is used to group the objects in databases into meaningful subclasses that are called clusters. There exists high similarity among database objects contained in the same cluster. Recently, clustering on large databases has been studied actively as an increasing number of applications, such as geographical information analysis and image analysis, involve huge amount of data. Conventional clustering methods require accessing the entire database from the disk at least once every time clustering is performed. They also have been focusing on the cost of processing memory-resident data, which must be read in from the disk. These methods, however, are becoming impractical as the databases are growing ever larger.
In this dissertation, we propose a disk-based clustering algorithm using a multidimensional file structure commonly maintained in large database applications. This algorithm accomplishs high efficiency and effectiveness for large databases while reducing the memory-residency constraint of existing clustering algorithms. The proposed algorithm is a new top-down approach using density information stored in the index nodes of a multidimensional file structure.
Generally, multidimensional indexes have the clustering property of storing similar objects in the same or adjacent data pages. By taking advantage of this property, we can find similar objects without incurring the high cost of accessing the objects themselves and calculating distances among them. In this dissertation we first formally define a cluster based on the notion of object density. For this definition, we introduce the concept of the region contrast partition based on the object density of the region. It divides the database space into the higher-density part containing objects to be included in the clusters and the lower-density part containing noise objects by using the clustering factor. Here, the cluster is defined by identifying the regions adjacent to one another from the higher-density part. The clustering factor is defined as the ratio of the number of all objects in high object-density regions over the total number of objects stored in the database.
Next, we present a straightforward algorithm that finds the clusters using the concept of the region contrast partition. We then propose a top-down clustering algorithm using density-based pruning, which improves the efficiency of the straightforward algorithm. As the size of the database becomes larger, the size of the index itself also becomes larger. Because the process of performing region contrast partition in the straightforward algorithm requires all index pages of the multidimensional index be accessed to find the set of dense regions, it degrades the performance. This overhead can be much alleviated using the density-based pruning, where we determine whether the leaf regions included in an internal region are all dense or all sparse using only the information stored in the internal entry (i.e., without accessing all leaf entries of the index) and prune the search space accordingly. For this pruning, we present a technique for determining the bounds and formally prove the correctness of the bounds.
We have performed extensive experiments to evaluate the performance of the proposed algorithm. Experimental results show that the proposed method reduces the elapsed time by up to 96 times compared with that of BIRCH, which is a well-known clustering method. The results also show that the proposed method accomplishes a quality of clustering similar or superior to that of BIRCH. The results also show that the performance improvement due to density-based pruning becomes more marked as the size of the database increases. It means that the proposed method is especially usable for large databases.
Next, we propose an approximate density-based pruning method that makes algorithm more efficient. In this approximate algorithm, we redefine the bounds so as to use the density information for internal regions as well as leaf regions.
The density-based pruning algorithm does not determine easily whether or not an internal node needs to be pruned when there is a large difference among the densities of leaf regions that belong to the region of this internal node. In the worst case, it is required to examine the entire leaf pages, resulting in significant performance degradation. For an arbitrary internal region in the multidimensional file structure, the density difference among the internal nodes in the next lower layer is less than that among its leaf nodes. The idea is to use the densities of the internal nodes as the bounding values. This makes the density differences among the nodes smaller. As a result, it allows us to prune a node without examining its entire leaf nodes. Experimental results show that the approximate density-based pruning algorithm improves the performance by up to 17% compared with the density-based pruning algorithm, while maintaining very similar accuracy of clusters.
From these results, we believe the proposed algorithms significantly enhance the clustering performance and are practically usable in large database applications.
클러스터링은 데이타 마이닝, 패턴 인식, 기계 학습 및 통계 데이타 분석 등과 같은 여러 분야에서 사용되는 중요한 응용 영역이다. 데이타 마이닝 분야에서의 클러스터링은 데이타베이스 객체들을 의미있는 부분 집합들로 그룹짓는 작업이다. 이러한 부분 집합을 클러스터라 하며, 동일한 클러스터에 속한 객체들간에는 매우 높은 유사성이 존재한다. 최근 공간 데이타 분석, 영상 분석 등과 같은 대용량 데이타를 관리하는 다양한 응용 업무들이 증가함에 따라, 대용량의 데이타베이스를 위한 클러스터링 기법이 많이 연구되고 있다. 기존의 클러스터링 방법들은 매번 클러스터링이 수행될 때마다 데이타베이스 전체를 디스크로부터 액세스 하도록 요구하고 있으며, 또한, 디스크로부터 읽어 들인 이들 데이타를 주기억장치상에서 효율적으로 처리하는 데 초점이 주어져 왔다. 그러나, 데이타베이스가 대용량화되면서 주기억장치 기반의 이들 알고리즘은 실용적으로는 더 이상 사용하기 어려운 단점이 있다.
본 학위논문에서는 기존의 주기억장치 기반 클러스터링 알고리즘들이 갖는 제약을 줄이면서 대용량 데이타베이스에 대해 높은 성능과 정확성을 유지할 수 있도록 하기 위하여 대부분의 대용량 데이타베이스 응용에서 이미 유지하고 있는 다차원 파일 구조를 이용한 디스크 기반 클러스터링 알고리즘을 제안한다. 제안하는 알고리즘은 다차원 파일 구조의 색인 노드에 저장되어 있는 밀도 정보를 이용하여 클러스터링의 성능을 향상시키는 새로운 하향식 (top-down) 클러스터링 접근 방법을 취한다.
일반적으로 다차원 파일 구조의 색인에서는 가까운 객체들이 동일하거나 혹은 인접한 페이지에 저장될 가능성이 큰 클러스터링 성질을 가진다. 이러한 다차원 색인의 클러스터링 성질을 사용하면 모든 객체들을 액세스하여 각 객체들간의 거리를 일일이 계산하는 노력을 들이지 않고도 이웃한 객체들을 식별할 수 있다. 본 학위논문에서는 우선 객체들의 밀도에 기반하여 클러스터를 정형적으로 정의한다. 이를 위하여, 객체를 포함하는 영역의 밀도를 이용한 영역 대조 분할 (region contrast partition) 개념을 도입한다. 영역 대조 분할이란 클러스터링 인수 (clustering factor) 를 사용하여 전체 색인 영역을 클러스터 대상이 되는 객체들을 포함하는 밀도가 큰 영역들의 집합과 노이즈 객체들을 포함하는 밀도가 작은 영역들의 집합으로 분할하는 것을 의미한다. 클러스터는 밀도가 큰 영역들의 집합을 대상으로 서로 인접한 영역들을 식별함으로써 정의된다. 여기서, 클러스터링 인수란 데이타베이스에 포함된 전체 객체수에 대한 클러스터 포함 객체수의 비율이다.
다음으로, 제안한 영역 대조 분할 개념에 근거하여 클러스터를 직관적으로 찾는 알고리즘을 제시하고, 제시한 직관적 알고리즘의 성능을 향상시키기 위하여 밀도 기반 전지 (density-based pruning) 를 이용한 하향식 클러스터링 알고리즘을 제안한다. 대용량 데이타베이스인 경우 색인 자체도 대용량이 되어, 직관적 알고리즘에서와 같이 클러스터를 찾기 위하여 전체 색인 영역을 대상으로 영역 대조 분할을 수행할 경우 성능이 저하되는 단점이 있다. 이러한 문제점을 해결하기 위하여 밀도 기반 전지 개념을 사용한다. 밀도 기반 전지는 색인의 모든 단말 영역들을 액세스하지 않고도 내부 영역에 속해 있는 단말 영역들이 모두 밀집 또는 희소임을 미리 판단하여 자신의 하위 영역들에 대한 불필요한 색인 검색을 줄임으로써 클러스터링 성능을 향상시키는 분기 한정 (branch-and-bound) 알고리즘에 기반한 개념이다. 본 학위논문에서는 이러한 전지를 위하여 색인 내부 영역들의 밀집도를 판단하는 기준이 되는 한계값 (bound) 을 제시하고 이의 정확성을 이론적으로 증명한다.
제안한 알고리즘의 성능을 평가하기 위하여 많은 실험을 수행하였다. 실험 결과, 제안한 방법은 잘 알려진 클러스터링 방법인 BIRCH와 비교하여 클러스터링 수행시간을 최대 96배까지 감소시킨 것으로 나타났다. 또한, 클러스터 정확성 측면에서도 BIRCH에 비해 우수하거나 유사한 것으로 나타났다. 실험 결과는 데이타베이스의 용량이 클수록 밀도 기반 전지에 의한 성능 향상 효과가 더욱 크게 나타남을 보여주고 있으며, 이는 제안한 방법이 대용량 데이타베이스에서 특히 유용하다는 것을 입증하는 것이다.
다음으로, 본 학위논문에서는 밀도 기반 전지에 사용되는 한계값의 기준 영역을 색인의 단말 영역이 아닌 내부 영역까지 포함시켜 재정의함으로써, 더욱 성능을 향상시키는 근사 밀도 기반 전지 개념을 제안한다. 밀도 기반 전지 알고리즘에서와 같이 색인의 단말 영역들이 갖는 밀도 값을 기준으로 한계값을 설정하게 되면, 내부 영역에 속한 단말 영역들간의 밀도 편차가 큰 경우 전지 여부에 대한 판별이 빨리 이루어지지 않는다. 최악의 경우에는 모든 단말 페이지를 검색하여야 하고, 이에 따라 성능이 저하될 수 있다. 다차원 파일 구조에서 임의의 내부 영역을 가정할 경우, 자신에 속한 바로 아래 계층의 내부 영역들간의 밀도 편차는 자신에 속한 단말 영역들간의 밀도 편차보다 크지 않으므로, 자신에 속한 바로 아래 계층의 내부 영역 밀도 값을 한계값으로 사용하게 되면, 밀도 편차가 상대적으로 작아지게 되어 전지 여부의 판별을 빨리 할 수 있게 된다. 제안한 근사 밀도 기반 전지 개념을 이용하여 성능 평가 실험을 수행한 결과, 밀도 기반 전지 알고리즘과 비교하여 정확성 측면에서는 큰 차이가 없는 반면 수행 시간 측면에서는 최대 17%의 성능 향상 효과가 있는 것으로 나타났다.
이 같은 결과로 볼 때, 제안한 알고리즘들은 특히 대용량 데이타베이스에서의 클러스터링 성능을 크게 향상시키는 기법으로서, 일반 데이타베이스 응용에 실용적으로 적용 가능하다고 판단된다.
