Clustering with Soft and Group Constraints

@incollection{citeulike:2594275, abstract = {Several clustering algorithms equipped with pairwise hard constraints between data points are known to improve the accuracy of clustering solutions. We develop a new clustering algorithm that extends mixture clustering in the presence of (i) soft constraints, and (ii) group-level constraints. Soft constraints can reflect the uncertainty associated with a priori knowledge about pairs of points that should or should not belong to the same cluster, while group-level constraints can capture larger building blocks of the target partition when afforded by the side information. Assuming that the data points are generated by a mixture of Gaussians, we derive the EM algorithm to estimate the parameters of different clusters. Empirical study demonstrates that the use of soft constraints results in superior data partitions normally unattainable without constraints. Further, the solutions are more robust when the hard constraints may be incorrect.}, author = {Law, Martin H. and Topchy, Alexander and Jain, Anil K. }, citeulike-article-id = {2594275}, journal = {Structural, Syntactic, and Statistical Pattern Recognition}, keywords = {clustering}, pages = {662--670}, posted-at = {2008-03-26 14:07:55}, priority = {2}, title = {Clustering with Soft and Group Constraints}, url = {http://www.springerlink.com/content/5x8b5wf4vxvknav2 }, year = {2004} }

TY - CHAP ID - citeulike:2594275 TI - Clustering with Soft and Group Constraints JF - Structural, Syntactic, and Statistical Pattern Recognition SP - 662 EP - 670 N2 - Several clustering algorithms equipped with pairwise hard constraints between data points are known to improve the accuracy of clustering solutions. We develop a new clustering algorithm that extends mixture clustering in the presence of (i) soft constraints, and (ii) group-level constraints. Soft constraints can reflect the uncertainty associated with a priori knowledge about pairs of points that should or should not belong to the same cluster, while group-level constraints can capture larger building blocks of the target partition when afforded by the side information. Assuming that the data points are generated by a mixture of Gaussians, we derive the EM algorithm to estimate the parameters of different clusters. Empirical study demonstrates that the use of soft constraints results in superior data partitions normally unattainable without constraints. Further, the solutions are more robust when the hard constraints may be incorrect. KW - clustering AU - Law, Martin AU - Topchy, Alexander AU - Jain, Anil PY - 2004/// UR - http://www.springerlink.com/content/5x8b5wf4vxvknav2 ER -