Accelerated Simulated Annealing을 이용한 2단계 군집화 방법 및 응용 = Two-stage clustering method using accelerated simulated annealing and its applications

국문 초록 (Abstract)

군집화 분석의 주된 목적은 주어진 데이터를 일정한 기준에 따라 적절히 군집별로 나누어 같은 군집에 배정된 개체들은 유사성(similarity)을 갖게 하고, 서로 다른 군집 간에는 이질성이 표출되도록 하는 것이다. 군집화가 잘 이루어지면 데이터를 군집별로 묶어 특성을 파악할 수 있게 되어 데이터 규모를 축소할 수 있으므로 뒤따르는 분석이 용이해질 수 있다, 또한 복잡한 구조의 일차적인 데이터로부터 보다 간단한 구조의 데이터를 얻을 수 있게 된다. 그러나 대부분 경우 동질군집들의 결정은 데이터의 구조특성 및 군집수에 대한 사전정보가 충분하지 않은 상태에서 이루어지므로 군집화 분석은 본질적으로 매우 복잡한 문제가 된다. 더욱이 다양한 성격의 문제에 보편적으로 유효하게 적용할 수 있는 범용의 군집화 방법이 거의 제시되지 못하고 있는 실정이다.
본 연구에서는 ASA 알고리듬을 이용하여 계층적 군집화 방법의 간편성과 최적화 방법의 정확성을 함께 살릴 수 있고 다양한 상황에서 군집수의 결정 및 군집화 분석을 동시에 효과적으로 수행할 수 있는 군집화 방법을 제시한다.
우선 계산상 효율적이지만 정확성이 다소 떨어지는 계층적 군집화 기법을 이용하여 1단계 군집화를 되도록 최적에 �貂�수행한 후 simulated annealing에 근거한 ASA 알고리듬을 이용하여 군집화 결과를 효과적으로 개선해 가는 2단계 기법인 ASA 군집화 방법을 제시하고 다양한 데이터에 적용하여 그 타당성을 확인한다.
그 다음으로 적절한 군집수의 결정문제가 토론된다. 기존의 방법들을 비교 분석하고 일부 방법에 대한 개선방안이 제시된다. 이런 개선된 방법을 이용하여 ASA 군집화 방법에서 필요한 1단계 계층적 군집화의 군집수를 결정하게 된다.
마지막으로 군집화 결과의 타당성 검정방법 들을 비교 분석하고 적절한 수정을 통해 보다 효과적인 방법을 제시한다. 특히 시뮬레이션 분석을 통해 ASA 군집화 결과에 대한 타당성 검정을 효과적으로 수행할 수 있는 분석방법을 구체화하여 제시한다.
결론적으로 본 연구에서는 ASA 군집화 방법을 토론함으로서 보다 다양한 군집화 문제에 대한 분석을 효과적으로 수행할 수 있는 방법을 제시했다는 데서 그 의미가 있다. 특히 다양한 실험을 통해 본 연구에서 제안된 방법의 유효성을 확인할 수 있었다.

다국어 초록 (Multilingual Abstract)

The main task of clustering is to partition a set of objects(or entities) into several clusters in a way that objects within the same cluster are similar to each other. One benefit of clustering is the reduction of the size of data. More important benefit is that more useful information can be obtained by organizing the complicated original data into the simpler form of the clustered data. However, clustering is one example of the very complicated combinatorial optimization problem since in most cases no prior information on the number of clusters or the cluster structure of the given data is given. And due to the complexity of the problem, so far there are few or no consistently efficient clustering methods for various types of problem.
In this thesis we propose a general purpose clustering method that can determine the proper number of clusters as well as efficiently carry out cluster analysis for various clustering problems. The method is based on accelerated simulated annealing(ASA) algorithm and utilizes both the advantage of computational efficiency of the hierarchical clustering method and the benefit of accuracy of the optimization clustering method. More specifically, we do the followings.
First, we propose a two-stage clustering method based on accelerated simulated annealing(ASA) algorithm and test the validity of the method using various artificial and real data sets, In the first stage of the method, we use computationally efficient hierarchical methods to get reasonably good clusters for the given data. And in the second stage, the clustering results from the first stage is improved by the ASA algorithm using specially designed perturbation schemes.
Second, the problem of determining the proper number of clusters is discussed. Several existing procedures and their advantages and disadvantages are compared and illustrated by some examples. Some improved methods are proposed and implemented to determine the number of clusters for the hierarchical clustering in the first stage of our method.
Finally we discuss some statistical procedures to test the validity of clustering result.
Extensive experimental results are also given to demonstrate the apparent usefulness of our ASA clustering methods.

목차 (Table of Contents)

• 목차
• ▣ 국문 초록 = I
• ▣ 표 목차 = V
• ▣ 그림 목차 = VII
• 제1장 서론 = 1
• 제2장 연구 배경 및 목적 = 4
• 2.1 군집화 분석방법 = 4
• 2.1.1 계층적 접근방법 = 5
• 2.1.2 최적화 접근방법 = 9
• 2.2 군집화 분석과정에 제기되는 문제 = 14
• 2.3 연구내용 및 방법 = 16
• 제3장 적절한 군집수의 결정 = 18
• 3.1 기존의 군집수 결정방법 및 장단점 = 18
• 3.2 본 연구에서 제안하는 방법 = 26
• 3.2.1 군집화 기준에 의한 그래프방법 = 26
• 3.2.2 통합기준치 증가폭에 의한 방법 = 27
• 3.2.3 ASA 군집화에 의한 결정 = 29
• 3.3 시뮬레이션을 통한 방법비교 = 30
• 제4장 ASA를 이용한 2-단계 군집화 방법 = 34
• 4.1 ASA 알고리듬 = 34
• 4.2 ASA를 이용한 2-단계 군집화과정 = 41
• 4.2.1 군집화 문제의 정의 = 41
• 4.2.2 1단계: 계층적 군집화 = 43
• 4.2.3 군집화 기준의 정의 = 44
• 4.2.4 전체 알고리듬 = 46
• 제5장 정량적(Quantitative)데이터에 대한 적용사례 = 50
• 5.1 모의데이터에 대한 적용 예 = 50
• 5.2 실제데이터에 대한 적용 예 = 55
• 제6장 정성적(qualitative)데이터에 대한 적용사레 = 65
• 6.1 웹 - 문서 데이터에 대한 적용사례 = 65
• 6.2 Lecturers 데이터(Dorndorf, 1994)에서의 적용 = 69
• 제7장 군집화 결과에 대한 타당성 검정 = 74
• 7.1 기존의 일부 방법 = 74
• 7.2 적절한 군집수의 선택에 대한 검정 = 80
• 7.3 군집구조의 적절성에 대한 검정 = 87
• 제8장 결론 = 93
• ▣ 참고 문헌 = 95
• ▣ 부록 = 99
• ▣ 영문 초록 = 103