# Which, When, and How: Hierarchical Clustering with Human-Machine Cooperation
## 4 \"Which\", \"When\", and \"How\"
### The \"How\" Problem  
This subsection focuses on the \"how\" problem. Once the human's answer disagrees with the machine's result, the machine should adjust its clustering result, which is complex due to the coupled errors. Suppose \(i\) and \(j\) are the most questionable pair of data points in the estimated-dirtiest cluster \(C\), where the human's answer disagrees with this result. Local adjustment refers to the case where the machine splits \(C\) into two clusters that, respectively, include \(i\) and \(j\). Global adjustment refers to the case where the machine gives up the current result and re-starts the clustering from the beginning. Local adjustments have a low time complexity and a low accuracy, while global adjustments have a high time complexity and a high accuracy.  
Our solution to the \"how\" problem is (1) first tracing back to a previous clustering state; (2) then doing local adjustment; and (3) finally resuming the building of the clustering hierarchy. It is shown in Figure 6 (assume that the human's answer disagrees with the machine's clustering results for the two questions). The depth of the back-tracing represents the trade-off between the time complexity and the accuracy. To limit the depth of the back-tracing, the machine only traces back to the hierarchy of the latest adjustment, as shown in Figure 6 (for the first question, the machine traces back to the initial state). After doing local adjustment, the machine resumes building the clustering hierarchy without question operations. The question operations are disabled until the machine goes back up the hierarchy that was present when it asked the question. Once the adjustment of the current question is finished, the state of the clustering is saved as the point to trace back to for the next question. Since each hierarchical state is calculated at most twice, this scheme _at most doubles the time complexity_.  
Let us go over the machine's process of dealing with the human's answers. Suppose \(i\) and \(j\) are the most questionable pair of data points in the dirtiest cluster \(C\): (1) if the human returns an answer that \(i\) and \(j\) are in the same cluster (agree with the machine), then everything is fine. \(i\) and \(j\) are removed for further questioning, and their distance is set to be 0; (2) if the human returns an answer that \(i\) and \(j\) are not in the same cluster (disagree with the machine), the machine traces back and then uses the local adjustment, which is referred to as a local splitting of \(C\). In other words, \(C\) is divided into two clusters. The remaining data points in \(C\) choose to join \(i\)'s cluster or \(j\)'s cluster, according to the distance (join the nearest one). \(i\) and \(j\) are removed for the further questions, and their distance is set to be infinity. After this local adjustment, the machine resumes building the clustering hierarchy. The questions  
Figure 6: The solution to the “how” problem.  
are disabled until the machine goes back to the point in the hierarchy at which it asked the question. In addition, note that the transitive relations of questions may bring the machine a derived answer in which two data points in different clusters should be in the same cluster. For this case, we refer to the local adjustment as a merge of the two clusters corresponding to those two data points. The distance between those two data points is set to be zero.