{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:49:35Z","timestamp":1763459375474,"version":"3.45.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,12,3]],"date-time":"2017-12-03T00:00:00Z","timestamp":1512259200000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1055113"],"award-info":[{"award-number":["IIS-1055113"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2017,5,31]]},"abstract":"<jats:p>\n                    Clustering can be improved with the help of side information about the similarity relationships among instances. Such information has been commonly represented by two types of constraints:\n                    <jats:italic toggle=\"yes\">pairwise<\/jats:italic>\n                    constraints and\n                    <jats:italic toggle=\"yes\">relative<\/jats:italic>\n                    constraints, regarding similarities about instance pairs and triplets, respectively. Prior work has mostly considered these two types of constraints separately and developed individual algorithms to learn from each type. In practice, however, it is critical to understand\/compare the usefulness of the two types of constraints as well as the cost of acquiring them, which has not been studied before. This paper provides an extensive comparison of clustering with these two types of constraints. Specifically, we compare their impacts both on\n                    <jats:italic toggle=\"yes\">human users<\/jats:italic>\n                    that provide such constraints and on the\n                    <jats:italic toggle=\"yes\">learning system<\/jats:italic>\n                    that incorporates such constraints into clustering. In addition, to ensure that the comparison of clustering is performed on equal ground (without the potential bias introduced by different learning algorithms), we propose a probabilistic semi-supervised clustering framework that can learn from either type of constraints. Our experiments demonstrate that the proposed semi-supervised clustering framework is highly effective at utilizing both types of constraints to aid clustering. Our user study provides valuable insights regarding the impact of the constraints on human users, and our experiments on clustering with the human-labeled constraints reveal that relative constraint is often more efficient at improving clustering.\n                  <\/jats:p>","DOI":"10.1145\/2996467","type":"journal-article","created":{"date-parts":[[2016,12,5]],"date-time":"2016-12-05T11:47:16Z","timestamp":1480938436000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Comparing Clustering with Pairwise and Relative Constraints"],"prefix":"10.1145","volume":"11","author":[{"given":"Yuanli","family":"Pei","sequence":"first","affiliation":[{"name":"Oregon State University, Corvallis, OR"}]},{"given":"Xiaoli Z.","family":"Fern","sequence":"additional","affiliation":[{"name":"Oregon State University, Corvallis, OR"}]},{"given":"Teresa Vania","family":"Tjahja","sequence":"additional","affiliation":[{"name":"Oregon State University, Corvallis, OR"}]},{"given":"R\u00f3mer","family":"Rosales","sequence":"additional","affiliation":[{"name":"LinkedIn, Mountain View, CA"}]}],"member":"320","published-online":{"date-parts":[[2016,12,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-23528-8_14"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-013-5397-9"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1661445.1661640"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014062"},{"key":"e_1_2_1_5_1","volume-title":"On mean field convergence and stationary regime. CoRR abs\/1111.5710","author":"Benam Michel","year":"2011","unstructured":"Michel Benam and Jean-Yves Le Boudec. 2011. On mean field convergence and stationary regime. CoRR abs\/1111.5710 (2011)."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015330.1015360"},{"key":"e_1_2_1_7_1","volume-title":"Pattern Recognition and Machine Learning","author":"Bishop Christopher M.","unstructured":"Christopher M. Bishop. 2007. Pattern Recognition and Machine Learning (1st ed.). Springer.","edition":"1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339616"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2014.114"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2014.115"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273496.1273523"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502550"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00521-012-1207-8"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2011.5995478"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10462-011-9236-8"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2997189.2997276"},{"key":"e_1_2_1_17_1","volume-title":"Advances in Psychology. North-Holland, 139--183.","author":"Hart Sandra G.","year":"1988","unstructured":"Sandra G. Hart and Lowell E. Staveland. 1988. Development of NASA-TLX (task load index): Results of empirical and theoretical research. In Human Mental Workload, Vol. 52: Advances in Psychology. North-Holland, 139--183."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-010-0313-0"},{"key":"e_1_2_1_19_1","first-page":"841","article-title":"On discriminative vs. generative classifiers: A comparison of logistic regression and naive bayes","volume":"14","author":"Jordan A.","year":"2002","unstructured":"A. Jordan. 2002. On discriminative vs. generative classifiers: A comparison of logistic regression and naive bayes. In Proceedings of Advances in Neural Information Processing Systems 14 (2002), 841.","journal-title":"Proceedings of Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1630659.1630742"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.190715"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2005.210"},{"key":"e_1_2_1_23_1","volume-title":"Jain","author":"Law Martin H. C.","year":"2005","unstructured":"Martin H. C. Law, Alexander P. Topchy, and Anil K. Jain. 2005. Model-based clustering with probabilistic constraints. In Proceedings of SIAM Conference on Data Mining. 641--645."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/17.3.282"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020564"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.38"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-15-37"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281242"},{"key":"e_1_2_1_29_1","first-page":"299","article-title":"Semi-supervised clustering with pairwise constraints: A discriminative approach","volume":"2","author":"Lu Zhengdong","year":"2007","unstructured":"Zhengdong Lu. 2007. Semi-supervised clustering with pairwise constraints: A discriminative approach. Journal of Machine Learning Research 2 (2007), 299--306.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/2976040.2976147"},{"key":"e_1_2_1_31_1","unstructured":"MicrosoftResearch. 2005. Image Database. Retrieved from: http:\/\/research.microsoft.com\/en-us\/projects\/ObjectClassRecognition\/."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/2354409.2354975"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273496.1273581"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICVGIP.2008.47"},{"volume-title":"Psychometric Theory","author":"Nunnally J. C.","key":"e_1_2_1_35_1","unstructured":"J. C. Nunnally and Ira Bernstein. 1994. Psychometric Theory. McGraw Hill, Inc."},{"key":"e_1_2_1_36_1","volume-title":"Tjahja","author":"Pei Yuanli","year":"2014","unstructured":"Yuanli Pei, Xiaoli Z. Fern, R\u00f3mer Rosales, and Teresa V. Tjahja. 2014. Discriminative clustering with relative constraints. http:\/\/arxiv.org\/abs\/1501.00037."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150444"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622737.1622741"},{"key":"e_1_2_1_39_1","unstructured":"Mark Schmidt. 2012. L-BFGS software. Retrieved from: http:\/\/www.di.ens.fr\/&sim;mschmidt\/Software\/minFunc.html."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/2981345.2981351"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/2981345.2981404"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/1619410.1619472"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/645530.655669"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993077.1993078"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835877"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973440.48"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2008.05.018"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/2968618.2968683"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2009.11.005"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.1262179"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.68"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TGRS.2008.918647"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2996467","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2996467","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2996467","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:42:58Z","timestamp":1763458978000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2996467"}},"subtitle":["A Unified Framework"],"short-title":[],"issued":{"date-parts":[[2016,12,3]]},"references-count":52,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,5,31]]}},"alternative-id":["10.1145\/2996467"],"URL":"https:\/\/doi.org\/10.1145\/2996467","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2016,12,3]]},"assertion":[{"value":"2015-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-09-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-12-03","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}