[paper reivew] A dirichlet multinomial mixture model-based approach for short text clustering

date

Mar 2, 2023

slug

dmmm

author

status

Public

Introduction

short text clustering은 sparsity ploblem을 가진다. 대부분의 단어들은 각 short text에서 한번만 발생한다. TF-IDF 같은 방법론은 이러한 short text에 효과적이지 못함. 또한 Vector space model을 사용할 경우 sparse하고 high dimensinal한 vector를 다뤄야한다는 문제가 생김.

collapsed Gibbs Sampling algorithm for the Dirichlet Multinomial Mixture model 제안.

또한, 각 문서들은 학생, 학생들이 본 영화는 단어에 비유하여 GSDMM 과정을 설명하는 Movie Group Process 제안

short text clustering 문제를 비슷한 관심사를 공유하는 그룹을 만들기 위해 학생들을 clustering 하는 문제에 비유할 수 있다.

본 논문의 contribution은 다음과 같다

1) short text clustering에 Dirichlet Multinomial Mixture (DMM)을 적용하는 첫번째 시도이다. sparse ad high dimensinal problem을 다루는 것을 가능하게 함.

2) DMM을 위한 collapsed Gibbs Sampling algorithm 제안. cluster 결과의 completness와 homoginity 사이에 좋은 밸런스를 유지하며 cluster 개수를 자동으로 추론할 수 있으며 빠를게 수렴함.

3) GSDMM의 이해를 돕기 위한 Movie Group Process (MGP) 제안.

APPROACH

Movie Group Process

영화 토론 수업에 비유하여 GSDMM 과정 설명. 비슷한 영화를 본 학생들을 같은 그룹에 나누고자함. 각 학생은 그 학생이 작성한 시청 영화 목록을 가지고 있다. 최종 목적은 같은 그룹의 학생들은 비슷한 영화 리스트를, 다른 그룹의 학생들은 다른 영화 리스트를 가지도록 clustering 하는 것.

이때 input은 D명의 학생들(document)이고 각 학생은 영화 리스트(document의 단어)로 representation됨. 모든 학생이 작성한 총 영화(words)의 개수를 V라고 한다면 short text의 sparse characteristic에 의해 각 short text의 단어 개수(L)는 작지만(often less than ) V는 매우 크다.(often larger than )

(K-means와 같은 clustering 방법은 각 documnet를 V 차원의 vector로 표현한다. 따라서 document의 단어 개수가 적음에도 불구하고 V 길이에 vector로 표현하기 때문에 높은 시간 및 공간 복잡도를 가질 뿐만 아니라 high-dimensional problem 발생.)

큰 식당에서 우선 학생들을 random하게 개의 table에 앉힌 후 다시 학생들에게 다음 룰에 따라 차례로 table을 선택하도록 한다.

1) 더 많은 학생이 있는 table을 선택해야하고

2) 비슷한 영화 리스트를 공유하고 있는 table을 선택해야한다.

이 과정을 반복하면 어떤 table은 인원이 증가하고 어떤 table은 인원이 점점 감소할 것이며 각 table의 학생들은 비슷한 영화 리스트를 공유할 것이다.

rule1은 clustering 결과의 높은 comletness 이끌어냄. completness는 ground true group의 모든 멤버들이 같은 cluster에 할당되어야한다는 것을 의미. rule1은 인기있는 table은 더 인기 있도록 하는 경향을 만들기 때문에 ground true group의 학생들이 실제로 같은 cluster에 들어가도록 할 가능성을 높인다.

rule2는 clustering 결과의 높은 homogeneity 이끌어냄. homogeneity는 각 cluster가 하나의 ground true group의 member들이 포함되어야 한다는 것을 의미.

이러한 MGP는 GSDMM의 collapsed gibbs sampling 알고리즘과 같다.