속성 값 분포에 의한 거리 측정 방법을 이용한 범주 속성 데이터의 군집화 기법
A Categorical Data Clustering Method Using the Distance Measure Based on Distribution of Attribute Values
- 주제(키워드) 범주 속성 , 군집화 , 거리 측정 방법
- 발행기관 서강대학교 일반대학원
- 지도교수 정성원
- 발행년도 2012
- 학위수여년월 2012. 2
- 학위명 석사
- 학과 및 전공 일반대학원 컴퓨터공학과
- 실제URI http://www.dcollection.net/handler/sogang/000000047435
- 본문언어 한국어
- 저작권 서강대학교 논문은 저작원 보호를 받습니다.
초록/요약
군집화는 데이터 마이닝의 한 분야로 사전 정보 없이 데이터 객체들을 분석하여 서로 유사한 객체끼리 분류하는 과정이다. 군집화는 전통적으로 수치 속성을 갖는 데이터를 상대로 연구되어왔는데, 군집 분석에 대한 요구가 다양해지면서 상대적으로 소외되었던 범주 속성에 대한 군집화 기법의 중요도가 점차 부각되고 있다. 그런데 범주 속성에 대한 군집화는 데이터의 특성상 수치 속성에서 연구된 군집화 알고리즘을 그대로 적용할 수 없을 뿐 아니라 사용되는 유사도 측정 기법의 표현력의 한계로 인해 정확하고 빠른 결과를 내기 어렵다. 수치 속성에서 사용되는 중심 값 기법은 높은 성능과 함께 군집 간 유사도 계산 비용을 단축할 수 있는 한 방법이지만 이를 범주속성에 적용한 기법들은 불안정한 성능을 보이거나 군집 당 하나 이상의 중심 값이 정의되어 여러 개의 답을 도출해내는 비결정적인 군집화가 수행되는 한계를 보인다. 따라서 본 논문에서는 결정적이고 빠른 군집화를 수행하기 위한 방법으로 AVD(distance measure based on Attribute Value Distribution)에 의한 군집 간 유사도 측정을 제안한다. 제안하는 유사도 측정 기법은 각 군집이 구성원의 속성 값에 대한 등장빈도를 유지하는 것을 전제로 하며, 자주 등장하는 속성 값의 구성 비율을 근거로 상호 유사도를 측정한다. AVD의 성능을 시험하기 위하여 기존의 분할 군집화 알고리즘과 계층 군집화 알고리즘에 이를 적용하여 성능 평가를 수행하였다. 각 알고리즘의 실제 데이터들에 대한 실험결과는 데이터간 거리의 모호성이 감소하여 유일한 군집화 결과를 도출해내며, 기존의 알고리즘들에 비해 효과적인 군집화를 수행할 수 있음을 보여준다.
more초록/요약
Clustering which is one of the fundamental operations in data mining is the process of classification of data objects based on their similar properties. Traditionally, clustering has been studied toward numerical data. However, as variety demand of clustering analysis is arisen, the importance of clustering technique for categorical data is increased. The problem is that clustering method for numerical data cannot be directly applied to categorical data clustering because of differences of data property. Centroid method is one of the distance measures between clusters in numerical data space. It enables us to obtain good cluster quality and reduce the time to calculate distance. However, in the case of categorical data clustering, centroid method define more than one centroid vector so that we cannot obtai n unique solution. Because of this drawback, we propose a novel distance measure AVD(distance measure based on Attribute Value Distribution) for unique and fast clustering for categorical data. In our proposition, each cluster maintains the frequency of attribute values and calculates distance between two objects by their distribution ratio of attribute values. Experimental result on real data sets demonstrate that the proposed approach helps to draw a unique conclusion and clustering quality is improved.
more