강화된 k-평균 군집분석에서 초기치 선정의 복잡도 개선

Abstract

In situations that a lot of data overflow, data mining is attracting attention because it is to extract useful informations and patterns from data. Clustering is an important technique in data mining. It is to group data into clusters such that the similarities among data within the same cluster are maximal while dissimilarities among data from different clusters are maximal. As active subject of research, it is finding a way that can be an effective and efficient clustering. K-means clustering proposed by MacQueen(1967)[1] is famous and useful method of partition-based clustering. It is simple and can be used for a variety of data types. But k-meas clustering is quite sensitive to positions of initial points. If chosen initial points is too close, it lower accuracy and increase execution time of iterative relocation. Enhanced k-means clustering proposed by Abdul Nazeer and Sebastian(2009)[2] complemented k-means clustering's defects. Its accuracy is higher and execution time of iterative relocation is lower than k-means clustering. But total execution time is higher than k-means clustering. In this paper, we propose an algorithm that improves time-complexity of selection initial points in enhanced k-means clustering proposed by Abdul Nazeer and Sebastian(2009).

방대한 양의 데이터가 넘쳐 나오는 상황에서 데이터의 유용한 정보나 패턴을 추출해내야 하는 필요성의 기인해 데이터 마이닝은 주목을 받고 있다. 군집분석은 데이터 마이닝의 중요한 기법으로, 군집 내 데이터의 유사성을 최대로 하는 반면 군집 간 비유사성을 최대로 데이터를 군집화 시키는 방법이다. 군집분석은 연구의 활발한 주체로서 효과적이고 효율적인 군집분석을 할 수 있는 방법을 찾고 있다. 군집분석의 여러 가지 기법 중 분할기법을 사용하는 MacQueen(1967)이 제안한 k-means 군집분석[1]은 가장 유명하면서도 많이 사용되고 있다. k-means 군집분석은 간단하면서도 다양한 데이터 형태에 적용될 수 있다. 그러나 k-means 군집분석은 초기 평균값의 의존도가 너무 높아 초기 평균값 임의 선택 시에 인접한 객체들이 선택된다면 클러스터링 정확도는 저하될 뿐 아니라 객체의 재배정에도 시간을 많이 할애하게 된다. MacQueen(1967)이 제안한 k-means 군집분석의 초기 평균값 선택과 객체의 재배정에서의 단점을 보안하여 Abdul Nazeer와 Sebastian(2009)이 제안한 강화된 k-means 군집분석[2]은 클러스터링 결과의 정확도를 크게 향상 시켰으며, 객체의 재배정 시간을 단축 시켰다. Abdul Nazeer와 Sebastian(2009)이 제안한 강화된 k-means 군집분석 역시 정확도의 향상과 객체 재배정 과정의 실행시간을 단축 시켰지만, MacQueen(1967)이 제안한 k-means 군집분석 보다 알고리즘 전체 실행시간이 길어진다는 단점이 있다. 본 논문에서는 Abdul Nazeer와 Sebastian(2009)이 제안한 강화된 k-means 군집분석의 초기 평균값 선택 시간복잡도를 향상시키는 방법을 제시한다.