{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T20:10:12Z","timestamp":1760213412260,"version":"build-2065373602"},"reference-count":41,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2016,12,21]],"date-time":"2016-12-21T00:00:00Z","timestamp":1482278400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS 1449860","CNS 1461932","CNS 1460971","CNS 1439672","CNS 1301774","ECCS 1231461"],"award-info":[{"award-number":["CNS 1449860","CNS 1461932","CNS 1460971","CNS 1439672","CNS 1301774","ECCS 1231461"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Human\u2013Machine Cooperations (HMCs) can balance the advantages and disadvantages of human computation (accurate but costly) and machine computation (cheap but inaccurate). This paper studies HMCs in agglomerative hierarchical clusterings, where the machine can ask the human some questions. The human will return the answers to the machine, and the machine will use these answers to correct errors in its current clustering results. We are interested in the machine\u2019s strategy on handling the question operations, in terms of three problems: (1) Which question should the machine ask? (2) When should the machine ask the question (early or late)? (3) How does the machine adjust the clustering result, if the machine\u2019s mistake is found by the human? Based on the insights of these problems, an efficient algorithm is proposed with five implementation variations. Experiments on image clusterings show that the proposed algorithm can improve the clustering accuracy with few question operations.<\/jats:p>","DOI":"10.3390\/a9040088","type":"journal-article","created":{"date-parts":[[2016,12,23]],"date-time":"2016-12-23T04:09:09Z","timestamp":1482466149000},"page":"88","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Which, When, and How: Hierarchical Clustering with Human\u2013Machine Cooperation"],"prefix":"10.3390","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5529-4080","authenticated-orcid":false,"given":"Huanyang","family":"Zheng","sequence":"first","affiliation":[{"name":"Computer and Information Sciences, Temple University, PA 19121, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jie","family":"Wu","sequence":"additional","affiliation":[{"name":"Computer and Information Sciences, Temple University, PA 19121, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2016,12,21]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"833","DOI":"10.1080\/001401300409044","article-title":"From human\u2013machine interaction to human\u2013machine cooperation","volume":"43","author":"Hoc","year":"2000","journal-title":"Ergonomics"},{"key":"ref_2","unstructured":"Swiechowski, M., Merrick, K., Mandziuk, J., and Abbass, H. (2015, January 22\u201327). Human\u2013Machine Cooperation in General Game Playing. Proceedings of the IARIA International Conference on Advances in Computer-Human Interactions (ACHI), Lisbon, Portugal."},{"key":"ref_3","first-page":"36","article-title":"Human\u2013Machine Cooperation in Large-Scale Multimedia Retrieval: A Survey","volume":"3","author":"Shirahama","year":"2015","journal-title":"J. Probl. Solving"},{"key":"ref_4","first-page":"43","article-title":"Integration of Ergonomics in the Design of Human\u2013Machine Systems","volume":"1","author":"Chauvin","year":"2014","journal-title":"Des. Hum. Mach. Coop. Syst."},{"key":"ref_5","first-page":"1","article-title":"Improving Human\u2013Machine Cooperative Classification via Cognitive Theories of Similarity","volume":"1","author":"Roads","year":"2016","journal-title":"Cognit. Sci."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Chang, J.C., Kittur, A., and Hahn, N. (2016, January 7\u201312). Alloy: Clustering with Crowds and Computation. Proceedings of the ACM Conference on Human Factors in Computing Systems (CHI), San Jose, CA, USA.","DOI":"10.1145\/2858036.2858411"},{"key":"ref_7","first-page":"39","article-title":"Human\u2013Machine Cooperative Grasping\/Manipulating System Using Force-Based Compliance Controller with Force Threshold","volume":"5","author":"Motoi","year":"2016","journal-title":"IEEJ J. Ind. Appl."},{"key":"ref_8","unstructured":"Biswas, A., and Jacobs, D. (2014, January 23\u201328). Active image clustering: Seeking constraints from humans to complement algorithms. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Columbus, OH, USA."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Kumar, N., Belhumeur, P., Biswas, A., Jacobs, D., Kress, W.J., Lopez, I., and Soares, J. (2012, January 8\u201316). Leafsnap: A computer vision system for automatic plant species identification. Proceedings of the European Conference on Computer Vision (ECCV), Amsterdam, The Netherlands.","DOI":"10.1007\/978-3-642-33709-3_36"},{"key":"ref_10","unstructured":"Pangning, T., Steinbach, M., and Kumar, V. (2006). Introduction to Data Mining, Pearson Education."},{"key":"ref_11","unstructured":"Balcan, M.F., and Gupta, P. (2010, January 27\u201329). Robust Hierarchical Clustering. Proceedings of the International Conference on Learning Theory (COLT), Haifa, Israel."},{"key":"ref_12","unstructured":"Ipeirotis, P., and Paritosh, P. (April, January 28). Managing crowdsourced human computaiton. Proceedings of the ACM International Conference on World Wide Web (WWW), Hyderabad, India."},{"key":"ref_13","unstructured":"Parameswaran, A., Sarma, A., Garciamolina, H., Polyzotis, N., and Widom, J. (September, January 29). Human-Assisted Graph Search: It\u2019s Okay to Ask Questions. Proceedings of the International Conference on Very Large Data Bases (VLDB), Seattle, Washington, DC, USA."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Park, T., and Saad, W. (2016, January 16\u201318). Learning with finite memory for machine type communication. Proceedings of the Conference on Information Systems and Sciences (CISS), Princeton, NJ, USA.","DOI":"10.1109\/CISS.2016.7460572"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2890495","article-title":"People do not feel guilty about exploiting machines","volume":"2","author":"Melo","year":"2016","journal-title":"ACM Trans. Comput. Hum. Interact."},{"key":"ref_16","unstructured":"Brew, A., Greene, D., and Cunningham, P. (2010, January 16\u201320). Using Crowdsourcing and Active Learning to Track Sentiment in Online Media. Proceedings of the European Conference on Artificial Intelligence (ECAI), Lisbon, Portugal."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Ramirez-Loaiza, M.E., Culotta, A., and Bilgic, M. (2014, January 27\u201331). Anytime Active Learning. Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), Quebec City, QC, Canada.","DOI":"10.1609\/aaai.v28i1.9015"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Wang, Z., and Ye, J. (2015). Querying discriminative and representative samples for batch mode active learning. ACM Trans. Knowl. Discov. Data, 17.","DOI":"10.1145\/2700408"},{"key":"ref_19","unstructured":"Wei, K., Iyer, R., and Bilmes, J. (2015, January 6\u201311). Submodularity in data subset selection and active learning. Proceedings of the IMLS International Conference on Machine Learning (ICML), Lille, France."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Loog, M., and Jensen, A.C. (2012, January 11\u201314). Constrained log-likelihood-based semi-supervised linear discriminant analysis. Proceedings of the joint IAPR International Workshops on Structural and Syntactic Pattern Recognition (SSPR) and Statistical Techniques in Pattern Recognition (SPR), Montreal, QC, Canada.","DOI":"10.1007\/978-3-642-34166-3_36"},{"key":"ref_21","unstructured":"Loog, M., and Jensen, A.C. (2014, January 19\u201323). Semi-supervised nearest mean classification through a constrained log-likelihood. Proceedings of the joint IAPR International Workshops on Structural and Syntactic Pattern Recognition (SSPR) and Statistical Techniques in Pattern Recognition (SPR), Grand Rapids, MI, USA."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Basu, S., Banerjee, A., and Mooney, R.J. (2004, January 22\u201324). Active Semi-Supervision for Pairwise Constrained Clustering. Proceedings of the International Conference on Data Mining (SDM), Lake Buena Vista, FL, USA.","DOI":"10.1137\/1.9781611972740.31"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Bilenko, M., Basu, S., and Mooney, R.J. (2004, January 4\u20138). Integrating constraints and metric learning in semi-supervised clustering. Proceedings of the IMLS International Conference on Machine Learning (ICML), Banff, AB, Canada.","DOI":"10.1145\/1015330.1015360"},{"key":"ref_24","unstructured":"Ahn, K., Cormode, G., Guha, S., McGregor, A., and Wirth, A. (2015, January 6\u201311). Correlation clustering in data streams. Proceedings of the IMLS International Conference on Machine Learning (ICML), Lille, France."},{"key":"ref_25","unstructured":"Ghoshdastidar, D., and Dukkipati, A. (2015, January 6\u201311). A provable generalized tensor spectral method for uniform hypergraph partitioning. Proceedings of the IMLS International Conference on Machine Learning (ICML), Lille, France."},{"key":"ref_26","unstructured":"Bahadori, M.T., Kale, D., Fan, Y., and Liu, Y. (2015, January 6\u201311). Functional subspace clustering with application to time series. Proceedings of the IMLS International Conference on Machine Learning (ICML), Lille, France."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Deng, K., Bourke, C., Scott, S., Sunderman, J., and Zheng, Y. (2007, January 28\u201331). Bandit-based algorithms for budgeted learning. Proceedings of the IEEE International Conference on Data Mining (ICDM), Omaha, NE, USA.","DOI":"10.1109\/ICDM.2007.91"},{"key":"ref_28","unstructured":"Kukliansky, D., and Shamir, O. (2015, January 6\u201311). Attribute Efficient Linear Regression with Distribution-Dependent Sampling. Proceedings of the IMLS International Conference on Machine Learning (ICML), Lille, France."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Amin, K., Kale, S., Tesauro, G., and Turaga, D.S. (2015, January 25\u201330). Budgeted Prediction with Expert Advice. Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), Austin, TX, USA.","DOI":"10.1609\/aaai.v29i1.9621"},{"key":"ref_30","unstructured":"Ali, A., Kolter, J.Z., Diamond, S., and Boyd, S. (2015, January 13\u201315). Disciplined convex stochastic programming: A new framework for stochastic optimization. Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), Amsterdam, The Netherlands."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"B\u00f6ck, R., Bonin, F., Campbell, N., and Poppe, R. (2015). Multimodal Analyses Enabling Artificial Agents in Human\u2013Machine Interaction, Springer.","DOI":"10.1007\/978-3-319-15557-9"},{"key":"ref_32","unstructured":"Aggarwal, C., Han, J., Wang, J., and Yu, P. (September, January 29). A framework for projected clustering of high dimensional data streams. Proceedings of the International Conference on Very Large Data Bases (VLDB), Toronto, ON, Canada."},{"key":"ref_33","unstructured":"Settles, B. (2010). Active Learning Literature Survey, University of Wisconsi. Technical Report."},{"key":"ref_34","unstructured":"Bache, K., and Lichman, M. UCI Machine Learning Repository. Available online: http:\/\/archive.ics.uci.edu\/ml."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Downar, L., and Duivesteijn, W. (2015, January 14\u201317). Exceptionally Monotone Models\u2013The Rank Correlation Model Class for Exceptional Model Mining. Proceedings of the IEEE International Conference on Data Mining (ICDM), Altantic City, NJ, USA.","DOI":"10.1109\/ICDM.2015.81"},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Achtert, E., Kriegel, H.P., Schubert, E., and Zimek, A. (2013, January 22\u201327). Interactive data mining with 3D parallel coordinate trees. Proceedings of the ACM Special Interest Group on Management of Data, New York, NY, USA.","DOI":"10.1145\/2463676.2463696"},{"key":"ref_37","unstructured":"Kumar, N., Berg, A., Belhumeur, P., and Nayar, S. (October, January 29). Attribute and Simile Classifiers for Face Verification. Proceedings of the IEEE International Conference on Computer Vision (ICCV), Kyoto, Japan."},{"key":"ref_38","unstructured":"Available online: https:\/\/cs.joensuu.fi\/sipu\/datasets\/."},{"key":"ref_39","unstructured":"Roy, N., and McCallum, A. (July, January 28). Toward optimal active learning through monte carlo estimation of error reduction. Proceedings of the IMLS International Conference on Machine Learning (ICML), Williamstown, MA, USA."},{"key":"ref_40","unstructured":"McCallumzy, A.K., and Nigamy, K. (1998, January 24\u201327). Employing EM and pool-based active learning for text classification. Proceedings of the IMLS International Conference on Machine Learning (ICML), Madison, WI, USA."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1209\/epl\/i2004-10483-y","article-title":"Hierarchical clustering using mutual information","volume":"2","author":"Kraskov","year":"2005","journal-title":"Europhys. Lett."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/9\/4\/88\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T19:28:58Z","timestamp":1760210938000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/9\/4\/88"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,21]]},"references-count":41,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2016,12]]}},"alternative-id":["a9040088"],"URL":"https:\/\/doi.org\/10.3390\/a9040088","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2016,12,21]]}}}