이웃 군집의 밀도추정을 통한 순차데이터 군집화

Abstract

순차패턴 마이닝(sequential pattern mining)이란 데이터마이닝(data mining)의 한 분야로 데이터로부터 공통적으로 나타나는 순차적인 패턴을 찾는 것이다. 최근 다양한 형태의 데이터가 수집되면서 순차데이터 분석에 대한 연구도 여러 분야에서 진행되고 있다. 그리고 다른 데이터 마이닝 분야에서처럼 순차데이터 분석에도 데이터 구조를 파악하고 주요 패턴을 추출하는데 군집화는 필수적으로 수행되어진다. 순차 데이터에 대한 군집화 방법론은 대부분 초기 군집 개수를 설정해야하고 유사도를 기반으로 군집을 형성하기 때문에 잡음점에 민감하고 불규칙한 모양과 형태를 갖는 군집을 탐색하기 힘들다. 또한, 기존 연구된 순차데이터의 밀도 기반 군집화의 경우는 다양한 밀도를 포함하는 군집에 대해서 적절한 해결책을 제시하지 못하고 있다. 이에 본 연구에서는 순차데이터의 이웃 군집의 밀도를 고려한 군집화 기법을 소개한다. 제안하는 알고리즘은 유사도를 기반으로 군집화를 진행하는 것이 아니라 각 군집별로 은닉 마코프 모델을 생성하고 이를 바탕으로 특정 관측치가 각 군집에 속할 소속도를 계산한 뒤, 해당 관측치를 소속도가 높은 군집으로 속하게 한다. 단지 거리의 유사성만으로 군집을 형성하는 것이 아니라 해당 관측치가 각 군집에 속할 소속도를 상대적으로 비교하여 군집화를 진행함으로서 다양한 크기와 밀도를 포함하는 군집들을 탐색할 수 있다.|This study introduces a clustering algorithm of sequences based on the estimation of densities of the nearest neighboring clusters. Recently, mining sequence data has became an interesting research topic and been studied in various fields. In addition, the clustering method in sequence mining area is necessarily used for understanding the data structure. The proposed method in this thesis generates a hidden Markov model(HMM) in each cluster and calculates membership degrees representing how the objects belong to each cluster, and each object is assigned to the cluster with maximum membership degree. The proposed algorithm is not similarity-based but density-based, with which assigns each object to cluster by comparing relative membership degrees. Proposed algorithm can find clusters of various shapes and sizes.; This study introduces a clustering algorithm of sequences based on the estimation of densities of the nearest neighboring clusters. Recently, mining sequence data has became an interesting research topic and been studied in various fields. In addition, the clustering method in sequence mining area is necessarily used for understanding the data structure. The proposed method in this thesis generates a hidden Markov model(HMM) in each cluster and calculates membership degrees representing how the objects belong to each cluster, and each object is assigned to the cluster with maximum membership degree. The proposed algorithm is not similarity-based but density-based, with which assigns each object to cluster by comparing relative membership degrees. Proposed algorithm can find clusters of various shapes and sizes.