항목간의 유사도와 엔트로피를 고려한 클러스터링 알고리듬

Abstract

현대 사회에서 쏟아지는 정보량은 헤아릴 수 없을 만큼 대단히 많으며 대용량의 데이터 집합에서 유용한 지식을 추출하기 위해서는 원시 데이터의 정보를 최대한 활용하고, 적절한 기법들을 사용하여 적절한 군집을 생성하는 것이 필요하다. 군집화(clustering)는 주어진 객체들 중에서 유사한 것들을 몇몇의 집단으로 그룹화하여 각 집단의 성격을 파악하는데, 실제적으로 각 객체가 유사한지를 평가할 수 있는 도구가 필요하다. 기존의 군집화에서 객체 간에 유사하다는 의미는 각 군집(cluster)안에 있는 객체들이 같은 속성 값이 많을수록 객체 간에 유사성이 높아 유사도가 높은 객체끼리 군집을 이루게 된다. 그 중에서도 범주형 속성을 갖는 군집화는 범주형 값을 수치형으로 변환하여 객체간의 유사성을 측정 하는 방법이다. 본 논문에서는 카테고리를 기반으로 하는 항목간의 유사도 척도와 항목간의 엔트로피 척도를 이용하여 보다 정확한 군집화 알고리즘을 제안하였다. 제안하는 k-rt 알고리듬은 카테고리 기반의 분류트리를 이용하여 항목간의 유사도를 측정하며, 각 클러스터의 엔트로피 척도를 이용해 클러스터의 대표 값을 찾아가는 방법을 사용한다. 제안하는 알고리듬과 k-tode 방법을 사용하는 기존 알고리듬과 비교하면, 제시된 방법이 Information Gain값이 더 높은 것을 알 수있다. 따라서, 제안된 알고리듬을 사용하여 보다 정확한 군집분석의 수행이 가능하며 이를 통해 고객들의 니즈와 구매 선호도에 따라 적절한 타겟 마케팅(Target Marketing)을 할 수 있다.; In traditional data clustering, similarity of a cluster is measured by pairwise similarity of objects. Different from those of the traditional data, the features of market-basket data are known to be of high dimensionality and sparsity. Without explicitly considering the presence of the taxonomy, most prior efforts on clustering market-basket data can be viewed as dealing with items in the leaf level of the taxonomy tree. Clustering transactions across different levels of the taxonomy is of great importance for marketing strategies as well as for the result representation of the clustering techniques for marketbasket data. In view of the features of market-basket data, I devisesin this paper a novel measurement to perform the clustering. With this category and entropy based adherence measurement, we develop an efficient clustering algorithm, called algorithm k-rt for market-basket data with the objective to minimize the category and entropy based adherence. The distance of an item to a given cluster is defined as the number of links between this item and its nearest node. The category and entropy based adherence of a transaction to a cluster is then defined as the average distance of the items in this reprensentative transaction to that cluster. A validation model based on information gain is also devised to assess the quality of clustering for market-basket data. As validated by synthetic datasets, it is shown by my experimental results, with the taxonomy information, algorithm k-rt devised in this papersignificantly outperforms the prior works in both the execution efficiency and the clustering quality as measured by information gain, indicating the usefulness of category and entropy based adherence in market-basket data clustering.