Semi-supervised clustering is a subset of machine learning techniques for improving clustering performance by taking additional information: while traditional clustering algorithms take unlabeled data as input, semi-supervised clustering algorithms additionally assume a small amount of labeled data or a small number of clustering constraints. Semi-supervised clustering is an important area of machine learning research since we often have to deal with such partially labeled dataset in practice.
The algorithm presented in this thesis assumes the latter form of additional information, where we specify our clustering preference on a subset of the data via pairwise must-link and cannot-link constraints. Specifically, we present a semi-supervised extension of Probabilistic Latent Semantic Analysis (PLSA), which we call Penalized PLSA (PPLSA). PLSA has gained popularity over the recent years for document indexing and clustering tasks, and our aim is to improve its performance by extending it to incorporate pair- wise constraints. Through a number of semi-supervised clustering experiments, we show that PPLSA can achieve performance improvement over PLSA, and one of the well-known semi-supervised clustering algorithms called HMRF-KMeans.
준감독 군집화는 추가적인 정보를 활용하여 군집화 성능을 높이기위한 기계 학습 기법 중 하나이다. 전통적인 군집화 방법이 레이블이 없는 데이터만을 입력으로 받는 것에 비해, 준감독 군집화 방법은 적은 수의 레이블된 데이터 혹은 군집화에 대한 제약 조건이 함께 주어지는 것을 가정한다. 준감독 군집화 방법은 기계 학습 연구에서 중요한 분야인데, 이는 실제 상황에서 종종 부분적으로 레이블이 주어진 데이터를 다루어야 할 필요가 있기 때문이다.
본 논문에서 나타내고 있는 알고리즘은 위에서 언급한 두 종류의 추가 정보 중 두 번째 형태를 가정하고 있다. 이 알고리즘은 부분적으로 주어지는 이항 제약 조건 (pairwise constraint)인 must-link와 cannot-link를 통해 군집화 선호도를 만들게 된다. 특별히, 본 논문에서는 확률적 잠재 의미 분석 모델, Probabilistic Latent Semantic Analysis (PLSA)를 확장하여, Penalized PLSA (PPLSA)를 제안했다. PLSA는 최근 문서의 인덱싱과 군집화에 널리 사용되고 있는 모델인데, 본 논문에서는 이항 제약 조건을 활용하여 PLSA의 성능을 향상시켰다. 본 논문에서는 다양한 데이터 셋에 대하여 PPLSA가 PLSA보다 좋은 성능을 보이고, 또한 널리 알려진 준감독 군집화 방법인 HMRF-KMeans보다도 좋은 성능을 보이는 것을 보일 수 있었다.
