Interactive Deep Clustering via Value Mining

We appreciate your positive feedback and suggestions. Below we provide the point-by-point response to your concerns.

Weakness 1: Inconsistent $\lambda_1, \lambda_2$ for different clustering models

We agree that it is daunting to tune the hyper-parameters for unsupervised tasks. In the previous version, we roughly tuned $\lambda_1, \lambda_2$ to produce relatively cluster-balanced inquiry samples. According to your suggestion, we applied our IDC to the pre-trained TCL clustering model with $\lambda_1=1, \lambda_2=1$ (the same configuration for ProPos). It turns out that IDC works well with the default hyper-parameters.

As a result, we decide to remove the two tunable parameters $\lambda_1, \lambda_2$ in the next version.

Weakness 2: Explanations of ablation study results

The representativeness metric encourages the model to select samples in high-density regions. As shown in Figure 3(b), with the "Hard+Rep" criterion, the selected samples will be heavily imbalanced across clusters. As a result, during the model finetuning, the hard samples would collapse into a few clusters (easy samples will be restricted by the regularization loss), leading to inferior performance even worse than the pre-trained baseline. Such a result is exactly our motivation for designing the diversity metric during sample selection.

We will supply the above explanations in the revised manuscript.

Weakness 3: More advanced utilization strategies

Thanks for the suggestion. We agree that more advanced strategies could utilize user feedback more thoroughly. Some potential directions would be introducing mixup augmentations, supervised contrastive loss, or focal loss to improve the model finetuning. We will explore these improvements in future works.

Limitation: Interaction cost

According to your comments, we asked three people to answer the 500 queries on CIFAR-20 and ImageNet-Dogs. On average, it took about 6 seconds to decide the cluster affiliation relative to the nearest cluster centers for each sample, and querying 500 samples requires about 50 minutes. Nevertheless, querying 100 samples, which takes only 10 minutes, already achieves half the performance improvement brought by 500 samples as shown in Fig. 4. In practice, the user could flexibly decide the number of queries based on the demand, making a trade-off between efficiency and performance.

We will add the above discussions to the revised manuscript.

Thanks for your recognition of the problem this work aims to address, as well as our simple yet effective idea. We sincerely appreciate your insightful and constructive comments. Below are the point-by-point responses to your concerns raised in weaknesses, questions, and limitations.

Weakness 1 & Limitation: Imperfect user feedback

We agree with you that providing accurate user feedback would be more costly when handling more complex data types. However, we would like to highlight the motivation of our work, namely, introducing user interaction to address the hard sample problem suffered by fully unsupervised clustering methods. If a data sample is so hard that even humans cannot distinguish it, then machine learning methods are more unlikely to correctly cluster it solely based on the data itself. In other words, by selecting the most valuable samples for user queries, our method provides a chance of grouping samples undistinguishable by clustering methods, with additional user interaction costs as low as possible. We believe such a solution caters to practical needs.

Moreover, in real-world genomic and medical applications, the users are very likely to be domain experts since not everyone has the demand for clustering genomic data. Besides, as we later show in the response to Weakness 3, our method is robust to the potential mistakes in the user feedback, which suits real-world applications.

Weakness 2: More evidence of performance improvement

According to your comments, we further assessed the experimental results and concluded that the performance improvement of our IDC on hard samples is not incremental. Specifically, following the common understanding, we treated samples with cluster assignment confidence lower than 0.9 as hard samples (we did not use the hardness metric defined in the paper as the logarithmic value is less intuitive). Note that the sample confidence for ProPos was computed through a cluster head initialized with Kmeans cluster centers. Then, to better understand the performance gain brought by IDC on hard samples, we partitioned hard samples into two subgroups, namely, i) hard-in, consisting of hard samples selected for query, and ii) hard-out, consisting of hard samples not selected for query. We reported the proportion of hard-in samples among all hard samples, and the clustering accuracy of hard-in/out samples before/after the model finetuning. Below are the results of IDC applied to the TCL and ProPos models, respectively.

From the above results, one could arrive at three conclusions: i) the selected query samples only take a small percentage among all hard samples. In other words, simply correcting the cluster assignments of selected samples could only bring small improvements on hard samples; ii) the clustering accuracy of selected hard samples improves significantly, which is natural since these samples are used for finetuning; and iii) the clustering accuracy of hard samples not selected for query also greatly increases after finetuning, which demonstrates that the user feedback benefits the held-out data as well.

To further show that the user feedback also boosts the clustering performance of samples not selected for interaction, we added a baseline by manually correcting the cluster assignments of the 500 query samples, denoted by TCL$^{\dagger}$ and ProPos$^{\dagger}$ in the table below.

The results show that solely correcting the cluster assignments of 500 samples brings marginal performance improvement since they are only a small portion of the data. On the contrary, our IDC effectively utilizes user feedback on 500 query samples, which leads to much better performance.

To sum up, the above results demonstrate that our user interaction strategy could greatly improve the clustering performance on samples, no matter whether they are selected for the user query. We will add the above results and discussions to the revised manuscript.

Due to the space limitation, we put the remaining part of the responses in the global author response above.

We appreciate your positive feedback and kind suggestions for our work. Below are the point-by-point responses to your concerns mentioned in the weaknesses and limitations sections.

Weakness 1 & Limitation 1: Imperfect user feedback

According to your advice, we asked three people to answer the 500 queries on CIFAR-20 and ImageNet-Dogs. We counted the number of correct user feedback and used the feedback to finetune the TCL clustering model. The results are shown in the table below. As requested, we also supplied more examples of user queries in Figure 3 in the attached PDF file.

The above results demonstrate that: i) it is not difficult for the user to correctly predict the cluster affiliations of the query samples, and ii) IDC is robust to the mistakes in the user feedback, which suits real-world applications.

Weakness 2: Explanations on Cop-Kmeans results

Cop-Kmeans is a semi-supervised clustering method built upon the vanilla K-means. Given the pairwise constraints (i.e., must-link and cannot-link), Cop-Kmeans forces sample pairs with must-link constraints to be assigned to the same cluster and vice versa. In practice, the pairwise constraints often conflict with the cluster assignments made by the vanilla K-means. As a result, the cluster centers would deviate from the underlying data distribution due to "outliers" introduced by the pairwise constraints, leading to inferior clustering performance. Such a limitation of Cop-Kmeans could be attributed to the fixed features during the Kmeans process. In other words, Cop-Kmeans fails when the input features are intrinsically inseparable by assigning each sample to the nearest cluster center. In comparison, the proposed IDC could adjust the features by optimizing the cluster head, overcoming the intrinsic limitation of Cop-Kmeans.

We will add the above discussion to the revised manuscript.

Weakness 3: Marginal improvements against random selection on ImageNet-Dogs

As you pointed out, the superiority of our sample selection strategy against the random selection baseline on ImageNet-Dogs is less significant than that on CIFAR-20. Such a result is in fact reasonable since ImageNet-Dogs contains only 1/3 samples compared with CIFAR-20 (see dataset summary table below).

In other words, for the same number of query images, its proportion relative to the entire dataset on ImageNet-Dogs is larger than that on CIFAR-20. As the proportion increases, the performance gap between different sample selection strategies will be less significant, which explains the relatively marginal performance improvement against random selection on ImageNet-Dogs. For a more reasonable validation, to keep the proportion consistent, we investigate the selected sample number $M$ in the range 0-200 with an interval of 25 for ImageNet-Dogs. The results are provided in Figure 1 in the attached PDF file. As can be seen, when querying for 50 samples, our sample selection strategy outperforms random selection by 3.88 in terms of clustering ACC, larger than the gap of 2.3/0.42 ACC when querying 200/700 samples. The above results demonstrate the superiority of our sample selection strategy, especially when only a small portion of samples are queried.

We will add the above results and discussions in the Appendix in the next version.

Thanks for your positive feedback and detailed suggestions for our work. Below are the point-by-point responses to your concerns.

Weakness 1: The relative performance improvement

According to your comments, we added a baseline by manually correcting the cluster assignments of the 500 query samples, denoted by TCL$^{\dagger}$ and ProPos$^{\dagger}$ in the table below.

The results show that solely correcting the cluster assignments of 500 samples brings marginal performance improvement since they are only a small portion of the data. On the contrary, our IDC effectively utilizes user feedback on 500 query samples, which leads to much better performance. We will add the baseline to the revised manuscript.

Weakness 2 & Question 2: Inconsistent $\lambda_1, \lambda_2$ for different clustering models

In the previous version, we roughly tuned $\lambda_1, \lambda_2$ to produce relatively cluster-balanced inquiry samples. According to your suggestion, we applied our IDC to the pre-trained TCL clustering model with $\lambda_1=1, \lambda_2=1$​ (the same configuration for ProPos). It turns out that IDC works well with the default hyper-parameters.

As a result, we decide to remove the two tunable parameters $\lambda_1, \lambda_2$ in the next version.

Weakness 3: Design of interaction interface

Thanks for the suggestion, we will provide a user-friendly interaction interface to aid real-world applications.

Question 1: Time complexity and scalability

The proposed sample selection process consists of computing three metrics (hardness, representativeness, and diversity) and selecting the most valuable sample. Denote the number of samples as $N$, the number of clusters as $C$, and the number of query samples as $M$, the time complexity of these steps is analyzed as follows.

For the hardness metric, we compute the cosine distance to the two nearest centers for each sample, which is of $O(NC)$ time complexity.

For the representativeness metric, we compute the sum of Euclidean distance of $K$ nearest neighbors for each sample, which is of $O(NK)$ time complexity. Note that the $K$ nearest neighbors search is of $O(N+KlogK)$ time complexity, which could be omitted.

For the diversity metric, we compute the cosine distance to samples previously selected for each sample, which is of $O(NM)$ time complexity.

Finally, selecting the most valuable sample selection requires $O(M)$ time complexity.

In summary, as the number of query samples $M$ are usually larger than the number of clusters as $C$ and the number of nearest neighbors $K$, the overall time complexity of the sample selection process is $O(NM)$. Since only a small portion of samples are selected for query (i.e., $M<<N$), our sample selection strategy scales to large datasets.

Question 3: Interaction time cost

We asked three people to answer the 500 queries on CIFAR-20 and ImageNet-Dogs. On average, it took about 6 seconds to decide the cluster affiliation relative to the nearest cluster centers for each sample, and querying 500 samples requires about 50 minutes. Nevertheless, querying 100 samples, which takes only 10 minutes, already achieves half the performance improvement brought by 500 samples as shown in Fig. 4. In practice, the user could flexibly decide the number of queries based on the demand, making a trade-off between efficiency and performance.

Question 4: Cluster head initialization

Thanks for pointing out the cluster head initialization strategy proposed in the mentioned work. However, the authors did not release the code. We tried initializing the cluster head following the instructions in the paper but failed to reproduce the results. We will keep paying attention to the mentioned work and update the cluster head initialization strategy when applicable.