Abstract
Several semi-supervised clustering algorithms have been proposed to create clusters by exploring side information collected from users. The side information mainly has two categories: one is seed indication information based on global cluster situation; the other is pairwise link constraint which is relatively local side information. This paper focuses on the latter: local side information. We show in this paper there is still limitation of the current semi-supervised clustering algorithms. The side information that sampling collected from users may cover fewer representative instances, named as sampling bias here, which would mislead current algorithms and give rise to non-ignorable difference between identified clusters and the true clusters perceived by users. To address the limitation, we present a new clustering algorithm, named perception transform analysis (PTA), taking user’s perception words together with traditional side information into account by modeling user’s perception words in the form of perception vectors. This paper focuses on local side information, which means each perception vector models the concepts behind a must-link constraint and can be collected from users together with must-links. To verify the effectiveness of the proposed algorithm, we compare it with the state-of-the-art semi-supervised clustering algorithms. Extensive experiments are conducted on real datasets and the results demonstrate its advantages and robustness to sampling bias.