서지주요정보
(A) new similarity measure for categorical attribute-based clustering = 범주형 속성 기반 군집화를 위한 새로운 유사 측도
서명 / 저자 (A) new similarity measure for categorical attribute-based clustering = 범주형 속성 기반 군집화를 위한 새로운 유사 측도 / Min Kim.
저자명 Kim, Min ; 김민
발행사항 [대전 : 한국과학기술원, 2009].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8020691

소장위치/청구기호

학술문화관(문화관) 보존서고

MCS 09046

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

The problem of finding clusters is widely used in numerous applications, such as pattern recognition, image analysis, market analysis. The important factors that decide cluster quality are the similarity measure and the number of attributes. Similarity measures should be defined with respect to the data types. Existing similarity measures are well applicable to numerical attribute values. However, those measures do not work well when the data is described by categorical attributes, that is, when no inherent similarity measure between values. In high dimensional spaces, conventional clustering algorithms tend to break down because of sparsity of data points. To overcome this difficulty, a subspace clustering approach has been proposed. It is based on the observation that different clusters may exist in different subspaces. In this paper, we propose a new similarity measure for clustering of high dimensional categorical data. The measure is defined based on the fact that a good clustering is one where each cluster should have certain information that can distinguish it with other clusters. We also try to capture on the attribute dependencies. Experimental results on real datasets show clusters obtained by our proposed similarity measure are good enough with respect to clustering accuracy.

데이터의 군집을 찾아내는 문제는 패턴 인식, 이미지 처리, 시장 조사 등 많은 응용 분야에서 널리 사용되고 있다. 군집의 질을 결정하는 핵심 요소로는 유사 측도, 차원의 개수 등이 있다. 군집화를 하기 위해 주어지는 데이터 유형은 크게 범주형과 수치형이 있다. 유사 측도는 데이터의 특성을 반영하여 다르게 정의되어야 하는데, 대부분 기존의 연구들은 데이터를 특징지어주는 속성이 수치형으로 주어진 경우에 국한되어 있었다. 속성이 범주형으로 주어진 경우도 실생활에 많이 존재하지만, 범주형 변수에 대한 속성값의 유사성은 값의 순서가 고유하게 정해지지 않아서 기존의 유사 측도를 가지고 좋은 군집화 결과를 얻기가 어렵다. 이에 더하여, 고차원 데이터에 대해서는 데이터 점들이 희박하게 위치하여 가까운 점과 먼 점간의 차이가 거의 없고, 군집화 결과가 좋지 않을 수 있다. 이 문제를 해결하기 위해 부분 차원 군집화 방법이 제안되어 왔다. 부분 차원 군집화 방법은 각 군집을 발견하기에 적합한 부분 차원을 선택하면서 군집화를 수행하는 방법이다. 본 논문에서는 범주형 속성으로 특징지어진 고차원 데이터를 부분 차원 군집화하기 위한 새로운 유사 측도를 제안한다. 범주형 데이터 군집화 방법으로 많이 사용되는 개념적 군집화와 엔트로피 기반 군집화 방법은 대체로 좋은 군집화 결과를 낸다는 것이 알려져 있으나, 속성 간의 의존성을 무시하여 정확한 군집을 찾지 못할 가능성이 있다. 제안한 유사 측도는 각 군집은 다른 군집과 구별되는 특정 정보를 잘 표현할 수 있어야 한다는 기본적인 가정 하에 속성들 사이의 상관성을 반영하여 정의된다. 그리고 개선된 k-평균 군집화 알고리즘에 제안한 측도를 사용하여 군집화를 수행하도록 한다. 실제 데이터 셋을 군집화하는 실험을 통하여 제안하는 방법이 고차원 데이터는 물론 저차원 범주형 데이터에 대해서도 정확한 군집 결과를 찾을 수 있음을 보인다.

서지기타정보

서지기타정보
청구기호 {MCS 09046
형태사항 v, 22 p. : 삽도 ; 26 cm
언어 영어
일반주기 저자명의 한글표기 : 김민
지도교수의 영문표기 : Myoung-Ho Kim
지도교수의 한글표기 : 김명호
학위논문 학위논문(석사) - 한국과학기술원 : 전산학전공,
서지주기 References : p. 20-22
주제 clustering,;similarity measure,;k-means clustering;;
군집화 ,;유사 측도,;k-평균 군집화 ;;
QR CODE qr code