On K-Means Algorithm with Membership Constraints

• Activity Number: 297
• Type: Topic Contributed
• Date/Time: Tuesday, August 11, 2015 : 8:30 AM to 10:20 AM
• Sponsor: Section on Statistical Learning and Data Mining
• Author(s): Volodymyr Melnykov* and Igor Melnykov
• Companies: The University of Alabama and Colorado State University - Pueblo
• Keywords: K-means ; model-based clustering ; EM algorithm ; finite mixture models ; semi-supervised clustering

Abstract

K-means is one of the most popular clustering algorithms due to its fast performance and intuitive nature. While K-means is widely used in the unsupervised clustering framework, its application in the setting with partially known membership information is not obvious and not studied well. We consider a scenario with some membership information provided in the form of positive and negative constraints. Positive relations among observations imply that observations have to belong to the same cluster. On the contrary, negative relations require data points to belong to different clusters. The existing literature describes several empirical procedures for incorporating equivalence constraints in the K-means algorithm. In this work, we discuss a formal technique that allows for semi-supervised K-means clustering with positive and negative constraints which is established through considering parallels with semi-supervised model-based clustering setting.