Abstract

A fundamental challenge in clustering is detecting inherent cluster structures within data. This paper explores cluster detection in semi-supervised settings using planted bisection graph models, investigating the effects of pairwise constraints and known cluster assignments. The findings reveal that semi-supervision significantly alters the detection threshold, demonstrating that even a small amount of semi-supervised information can lower the phase transition threshold in cluster detectability, thereby enhancing clustering performance.

Date

January 1, 2010

Authors

Greg Ver Steeg

Journal

Relation