Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Constrained clustering
open-in-new
<h2 id="types-of-constraints">Types of constraints</h2> <p>Both a must-link and a cannot-link constraint define a relationship between two data instances. Together, the sets of these constraints act as a guide for which a constrained clustering algorithm will attempt to find chunklets (clusters in the dataset which satisfy the specified constraints). </p> <ul><li>A <i>must-link constraint</i> is used to specify that the two instances in the must-link relation should be associated with the same cluster.</li> <li>A <i>cannot-link constraint</i> is used to specify that the two instances in the cannot-link relation should <i>not</i> be associated with the same cluster.</li></ul> <p>Some constrained clustering algorithms will abort if no such clustering exists which satisfies the specified constraints. Others will try to minimize the amount of constraint violation should it be impossible to find a clustering which satisfies the constraints. Constraints could also be used to guide the selection of a clustering model among several possible solutions.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> </p> <h2 id="examples">Examples</h2> <p>Examples of constrained clustering algorithms include: </p> <ul><li>COP K-means <a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a></li> <li>PCKmeans (Pairwise Constrained K-means) <a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a></li> <li>CMWK-Means (Constrained Minkowski Weighted K-Means) <a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Pourrajabi, M.; Moulavi, D.; Campello, R. J. G. B.; Zimek, A.; Sander, J.; Goebel, R. (2014). "Model Selection for Semi-Supervised Clustering". Proceedings of the 17th International Conference on Extending Database Technology (EDBT). pp. 331–342. doi:10.5441/002/edbt.2014.31. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Wagstaff, K.; Cardie, C.; Rogers, S.; Schrödl, S. (2001). "Constrained K-means Clustering with Background Knowledge". Proceedings of the Eighteenth International Conference on Machine Learning. pp. 577–584. <a href="/wiki/Kiri_Wagstaff" target="_blank">/wiki/Kiri_Wagstaff</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Basu, Sugato; Banerjee, Arindam; Mooney, Raymond J. (April 2004). Active Semi-Supervision for Pairwise Constrained Clustering (PDF). Proceedings of the 2004 SIAM International Conference on Data Mining. pp. 333–344. <a href="/wiki/Raymond_J._Mooney" target="_blank">/wiki/Raymond_J._Mooney</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>de Amorim, R. C. (2012). "Constrained Clustering with Minkowski Weighted K-Means". Proceedings of the 13th IEEE International Symposium on Computational Intelligence and Informatics. pp. 13–17. doi:10.1109/CINTI.2012.6496753. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> </ol>