휴리스틱 진화에 기반한 효율적 클러스터링 알고리즘 = An Efficient Clustering Algorithm based on Heuristic Evolution

국문 초록 (Abstract)

클러스터링이란 한 군집에 포함된 데이타들 간의 유사한 성질을 갖도록 데이타들을 묶는 것으로 패턴인식, 영상처리 등의 공학 분야에 널리 적용되고 있을 뿐 아니라, 최근 많은 관심의 대상이 되고 있는 데이타 마이닝의 주요 기술로서 활발히 응용되고 있다.
클러스터링에 있어서 K-means나 FCM(Fuzzy C-means)와 같은 기존의 알고리즘들은 지역적 최적해에 수렴하는 것과 사전에 클러스터 개수를 미리 결정해야 하는 문제점을 가지고 있다. 본 논문에서는 진화 알고리즘을 사용하여 지역적 최적해에 수렴되는 문제점을 개선하였으며, 클러스터링의 특성을 분산도와 분리도로 정의하였다. 분산도는 임의의 클러스터의 중심으로부터 포함된 데이타들이 어느 정도 흩어져 있는지를 나타내는 척도인 반면, 분리도는 임의의 데이타와 모든 클러스터 중심간의 거리의 비율로서 얻어지는 소속정도를 고려하여 클러스터 중심간의 거리를 나타내는 척도이다. 이 두 척도를 이용하여 자동으로 적절한 클러스터 개수를 결정하게 하였다. 또한 진화알고리즘의 문제점인 탐색공간의 확대에 따른 수행시간의 증가는 휴리스틱 연산을 적용함으로써 크게 개선하였다. 제안한 알고리즘의 성능 및 타당성을 보이기 위해 이차원과 다차원 실험데이타를 사용하여 실험한 결과 제안한 알고리즘의 성능이 우수함을 나타내었다.

다국어 초록 (Multilingual Abstract)

Clustering is a useful technique for grouping data points such that points within a single group/cluster have similar characteristics. Many clustering algorithms have been developed and used in engineering applications including pattern recognition and image processing etc. Recently, it has drawn increasing attention as one of important techniques in data mining. However, clustering algorithms such as K-means and Fuzzy C-means suffer from difficulties. Those are the needs to determine the number of clusters apriori and the clustering results depending on the initial set of clusters which fails to gain desirable results.
In this paper, we propose a new clustering algorithm, which solves the above mentioned problems. In our method we use evolutionary algorithm to solve the local optima problem that clustering converges to an undesirable state starting with an inappropriate set of clusters. We also adopt a new measure that represents how well data are clustered. The measure is determined in terms of both intra-cluster dispersion and inter-cluster separability. Using the measure, in our method the number of clusters is automatically determined as the result of optimization process. And also, we combine heuristic that is problem-specific knowledge with a evolutionary algorithm to speed evolutionary algorithm search.
We have experimented our algorithm with several sets of multi-dimensional data and it has been shown that one algorithm outperforms the existing algorithms.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 기존의 클러스터링 알고리즘과 문제점
• 3. 진화알고리즘을 이용한 클러스터링 알고리즘
• 4. 실험
• 5. 결론
• 참고문헌
• 저자소개