속성 값 집합의 조합을 이용한 범주형 데이터 클러스터링

Abstract

데이터 마이닝 분야에서 클러스터링 기법은 패턴인식, 고객 세분화, 추세 분석과 같은 분야에서 널리 연구되어졌고 사용되어져 왔다. 클러스터링이란 물리적 혹은 추상적 객체들을 서로 비슷한 객체들의 집합으로 그룹화 하는 과정으로, 하나의 클러스터에 속하는 객체들 간에는 서로 다른 클러스터 내의 객체들과는 구분되는 유사성을 갖게 된다. 이런 클러스터링 기법은 주로 수치형 데이터에 적합한 거리기반 클러스터링에 초점이 맞춰져 연구되어졌다. 하지만 실제 데이터베이스에 있는 데이터들 중에는 범주형이 많으며 실제 데이터 마이닝의 응용 분야에서 범주형 데이터를 많이 다루고 있다. 본 연구에서는 범주형 데이터를 클러스터링 함에 있어서 기존의 유사도를 이용한 클러스터링 방법이 아닌 범주형 데이터가 가지고 있는 각 객체의 속성 값들을 조합을 이용한 새로운 클러스터링 알고리듬 두 개를 제안하고 데이터 레벨링 방법에 대해 제안한다. 첫 번째 제안하는 FAVC 알고리듬은 초기 클러스터를 랜덤하게 설정한 후 초기 클러스터를 기반으로 데이터 집합에 있는 각 튜플이 가진 속성 값들의 조합, 즉 속성 값들의 부분집합들의 빈도수를 계산하여 가장 많은 빈도수를 가진 초기 클러스터에 할당한다. 새롭게 생성된 클러스터를 기준으로 다시 각 튜플의 속성 집합의 속성 값들의 조합의 빈도수를 계산하게 된다. 클러스터가 변화가 없을 때 까지 반복하게 된다. 두 번째 제안하는 LAVC 알고리듬은 속성 값들의 조합을 이용하는데 있어서 한 객체가 동일한 클러스터링 결과 값에 대해서 임의의 클러스터에 그룹화 되는 것이 아니라 각 클러스터와 상관관계(연관성)를 갖고 있는 클러스터에 객체를 그룹화 하고자 한다. 그러므로 기존의 클러스터링 결과보다 좀더 연관성이 높은 속성들로 그룹화 됨으로써 사용자의 의사결정에 도움을 줄 수 있는 클러스터링 결과를 도출하고자 한다. 데이터 마이닝 기법 중의 하나인 연관규칙에서 항목들 간의 연관성의 척도로서 사용되는 향상도(Lift)를 이용한 범주형 클러스터링 알고리듬을 제안한다. 실제 데이터와 가상 데이터를 이용해 제안하는 알고리듬(FAVC와 LAVC)과 기존 알고리듬들과의 비교 실험을 하였다. 제안하는 알고리듬들이 기존 알고리듬들에 비해 클러스터링 결과와 실행 시간 면에서 더 효과적임을 알 수 있다. 대용량 데이터 집합에 대해 대부분의 클러스터링 알고리듬은 샘플링 방법을 주로 이용하는데, 샘플링을 이용하여 일부의 데이터를 클러스터링을 한 후 클러스터링 되지 않은 나머지 데이터를 적합한 클러스터로 할당하는 것을 데이터 레벨링(Data Labeling)이라 한다. 마지막으로 FAVC 알고리듬을 기반으로 한 데이터 레벨링 방법을 제안한다. 실제 데이터와 가상 데이터를 이용해 제안하는 알고리듬과 기존 알고리듬과의 비교 실험을 하였다. 기존 알고리듬에 비해 FAVC 알고리듬을 기반으로 한 데이터 레벨링 방법이 클러스터링 결과와 실행 시간 면에서 더 좋은 결과를 보여준다.