A Fast Algorithm for Identifying Hierarchical Clustering Structures using Constraint Graph = 제약조건 그래프를 이용한 계층적 클러스터링 구조식별 고속화 알고리즘

다국어 초록 (Multilingual Abstract)

OPTICS is a state-of-the-art algorithm for visualizing hierarchical clustering structures of multidimensional objects. However, OPTICS requires iterative distance computations for all objects, and thus is computed in O(n²) time that makes it unsuitable for massive datasets. Existing algorithms are not efficient to overcome the OPTICS issue. In this thesis, we propose a fast algorithm, called C-OPTICS, that alleviates the issue of time complexity using the constraint graph. C-OPTICS identifies the hierarchical clustering structures faster by reducing the number of distance computations while guaranteeing the hierarchical clustering structures identical to OPTICS. Both the qualities of the hierarchical clustering structures identified by C-OPTICS and its computational efficiency are demonstrated with experimental evaluations on synthetic and real datasets.

국문 초록 (Abstract)

OPTICS는 다차원 객체들의 계층적 클러스터링 구조를 시각화하는 최첨단 알고리즘이다. 하지만 OPTICS는 모든 객체들에 대한 반복적인 거리 계산으로 인해 O(n²) 시간을 요구하기 때문에 대용량 데이터 집합에 부적합하다. 기존의 알고리즘들 또한 최악의 경우에 이차 시간 복잡도를 가진다. 이를 개선하기 위해, 본 논문에서는 제약조건 그래프를 이용하여 OPTICS의 이차 시간 복잡도 문제를 완화하는 알고리즘인 C-OPTICS를 제안한다. C-OPTICS는 OPTICS의 결과와 동일한 계층적 클러스터링 구조를 보장하면서 동시에 거리 계산 횟수를 감소시켜 계산 효율성을 향상시킨다. 또한, C-OPTICS의 클러스터링 품질과 계산 효율성은 합성 및 실제 데이터 집합들에 대한 실험적 평가를 통해 입증된다.

목차 (Table of Contents)

• Ⅰ. Introduction 1
• 1.1 Background 1
• 1.2 Contribution 5
• 1.3 Thesis organization 6
• Ⅱ. Related work 7
• 2.1 OPTICS 7
• 2.1.1 Definition 7
• 2.1.2 Computation 9
• 2.2 Existing work 11
• Ⅲ. Proposed method 14
• 3.1 Partitioning step 15
• 3.2 Graph construction step 19
• 3.3 Plotting step 30
• Ⅳ. Performance evaluation 37
• 4.1 Experimental setup 37
• 4.1.1 Datasets 37
• 4.1.2 Competing methods 39
• 4.1.3 Clustering quality metrics 40
• 4.2 Experimental results 41
• 4.2.1 Clustering quality 42
• 4.2.2 Computational efficiency 45
• 4.2.3 Summary of experiments 51
• Ⅴ. Conclusion and Future work 53
• References 54
• Abstract (Korean) 58
• Acknowledgement 59