# Which, When, and How: Hierarchical Clustering with Human-Machine Cooperation
###### Abstract  
Human-Machine 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's 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's 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. H 1 2016 9 88 10.3390/a9040088 10.  
machine first computes some complete clustering results, through using different merging criteria; (2) then, the human picks out the most correct one as the final result. A better HMC strategy that takes less time and human computation involves _real-time cooperations_. When the machine encounters an uncertain pair of data points in the middle of the cluster-building process, it can ask for human help through _question operations_. Then, the human would tell the machine whether that pair of data points are in the same cluster or not. The number of questions a machine can ask is limited by a fixed budget, due to the cost of human computations. We are interested in the machine's strategy on handling the question operations, which is challenging in terms of three problems (\"which\", \"when\", and \"how\"). Which question (i.e., pair of data points) should the machine ask? Suppose the machine is in the middle of the cluster-building process. Then, Figure 1 shows some interesting cases as follows: (1) data points 1 and 2 are currently in the same cluster, but the distance between them is large. Hence, the machine may want human assistance to check their assignment; (2) data points 3 and 4 are currently in different clusters, but the distance between them is small. These two clusters that contain 3 and 4 may merge into a larger one; (3) the data point 7 is in the middle of two clusters. The machine can decide whether to add 7 to 5's cluster or 6's cluster, by asking the human two questions. Moreover, this problem is further complicated, due to the _transitive relations_ of questions. As shown in Figure 1, let us assume that two questions return answers (from the human) in which data points 8 and 10 (the first question's answer), as well as 9 and 10 (the second question's answer), are in the same cluster. Based on these answers, the machine can derive that 8 and 9 are in the same cluster by transitivity. When should the machine ask the question? Asking a question can bring up the correctness of the clustering result, since the machine may have made some errors. If the machine asks questions in the early clustering stage, then it benefits from getting a good start (or foundation) as a trade-off on the risk: it may not reserve enough question operations for very hard decisions that may appear later. The number of available questions is important: if the machine holds a large number of available questions, then it can be aggressive (i.e., ask early); otherwise, it may be conservative (i.e., ask later). How does the machine adjust the current clustering result after obtaining the question's answer from the human? If the human agrees with the machine's clustering result, then everything is fine. Otherwise, the machine needs to adjust its clustering result, which is very complex due to the _coupled errors_ shown in Figure 2. Figure 2a shows the current clustering result of the machine.