제주대학교 Repository

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

Metadata Downloads
Alternative Title
Improving Complexity of Selection Initial Point in enhanced K-Means Clustering
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 군집분석의 초기 평균값 선택 시간복잡도를 향상시키는 방법을 제시한다.
Author(s)
김경언
Issued Date
2012
Awarded Date
2012. 8
Type
Dissertation
URI
http://dcoll.jejunu.ac.kr/jsp/common/DcLoOrgPer.jsp?sItemId=000000005994
Alternative Author(s)
Kim, Kyoung-Un
Affiliation
제주대학교
Department
대학원 전산통계학과
Advisor
김철수
Table Of Contents
List of Tables ⅰ

List of Figures ⅱ

Abstract ⅲ

Ⅰ. 서론 1

Ⅱ. 연구배경 3
1. 데이터 마이닝과 군집분석 3
1) 데이터 마이닝 3
2) 데이터 마이닝의 필요성 5
3) 군집분석 5
4) 군집분석의 장·단점 7
5) 군집분석의 필요성 8
2. 군집분석의 요구사항 10
3. 주요 군집분석 방법 14

Ⅲ. k-means 군집분석과 강화된 k-means 군집분석 22
1. k-means 군집분석 알고리즘 22
2. 강화된 k-means 군집분석 24
1) k-means 군집분석의 강약점 24
2) 강화된 k-means 군집분석 알고리즘 25

Ⅳ. 제안하는 K-means 군집분석 27
1. 강화된 k-means 군집분석의 강약점 27
1) 강화된 k-means 군집분석의 강약점 27
2) 시간복잡도 28
2. 제안하는 k-menas 군집분석 28
1) 제안하는 k-means 군집분석 알고리즘 28
2) 시간복잡도 30

Ⅴ. 실험 결과 및 분석 31
1. 실험환경 31
2. 실험 데이터 31
1) IRIS data set 31
2) Image Segmentation data set 32
3. 실험 결과 33
1) IRIS data set 실험 결과 33
2) Image Segmentation data set 실험 결과 37

Ⅵ. 결론 41

Ⅶ. 참고문헌 43
Degree
Master
Publisher
제주대학교 대학원
Citation
김경언. (2012). 강화된 k-평균 군집분석에서 초기치 선정의 복잡도 개선
Appears in Collections:
General Graduate School > Computer Science and Statistics
Authorize & License
  • AuthorizeOpen
Files in This Item:

Items in Repository are protected by copyright, with all rights reserved, unless otherwise indicated.