# Which, When, and How: Hierarchical Clustering with Human-Machine Cooperation
## 4 \"Which\", \"When\", and \"How\"
### The \"Which\" Problem  
For the \"which\" problem, a previous work [8] proposed that the machine should ask the pair of nodes leading to a quick convergence, which does not improve the clustering accuracy. However, the goal of HMCs is to balance the advantages and disadvantages of human computation and machine computation. The former method is accurate but costly, while the latter one is cheap but inaccurate. Therefore, using human resources to save the machine's computations is meaningless in HMCs. Our objective is to improve the machine's clustering accuracy with limited real-time help from humans. To better explain our idea, several definitions [32] are introduced as follows. **Definition 1**. : _The purity of a cluster is the fraction of the dominant data point type in it. The minimum purity is the minimum purity among all clusters. The cluster with the minimum purity is called the dirtiest cluster._Note that the definition of the minimum purity does not involve the cluster size. Therefore, a smaller cluster is more likely to have a lower purity, since an incorrectly clustered data point takes a larger fraction in the cluster. We intend to make small clusters pure, in order to limit error propagations. An example of the minimum purity is shown in Figure 3. The minimum purity is \(min\{\frac{6}{7},\frac{4}{6}\}=\frac{4}{6}\). A high minimum purity means that each cluster is pure. If the minimum purity of the machine's current clustering result is very low, then the machine should ask questions. However, the machine does not know the true minimum purity during its cluster-building process. The only thing it can do is to _estimate_ the minimum purity. Therefore, we have the following definition:  
**Definition 2**. : _The machine's certainty estimates the minimum purity of the current clustering result._  
The minimum purity can be used by the machine to verify the estimated-dirtiest cluster through question operations. A high certainty means that the machine considers its current clustering result to be correct, while a low certainty means that the machine doubts the accuracy of its current clustering result. Intuitively, the distance between the two clusters that are going to be merged in the next step may reveal the purity. One may think that merging two far-distance clusters leads to a low purity. However, this is incorrect in the sense that all currently existing clusters are far away from each other. Another method is to use the ratio of (1) the smallest distance between two different clusters to (2) the largest distance between two data points within the same cluster. A larger ratio seems to represent a higher purity, since clusters are far away from each other, and each cluster's size is small. However, this method is also incorrect. As shown in Figure 4, the ratio can be small, but the purity is high. Our solution to the \"which\" problem is a special _density-weighted uncertainty-sampling-based_ approach [33]. It focuses on the neighborhood consistency of pairs of data points. The neighbors of a data point are its \(k\)-nearest neighbors. If all neighbors of a data point have consistent behaviours (in terms of their clusters), then the machine's certainty is high. We use _local structures of pairs of data points to estimate the purity_. Suppose data points \(i\) and \(j\) are in the same cluster \(C\). We then have:  
\[Certainty(C)=\underset{i,j\in C}{min}\ \frac{P_{i}(C)+P_{j}(C)}{2}, \tag{1}\]  
where \(P_{i}(C)\) is the percentage of data point \(i\)'s neighbors that are currently in \(C\). The corresponding \(i\) and \(j\) that lead to the minimum certainty of \(C\) are called _the most questionable pair of data points_ in \(C\). The certainty is defined through pairwise data points, since the question operation has the format of  
Figure 4: Counter-example. Figure 3: An example of the purity calculation. Small circles and squares are data points of different types. Data points of the same type should be clustered. comparing two data points.