Deep Plug-and-Play Clustering with Unknown Number of Clusters
Authors: An Xiao
Hanting Chen
Tianyu Guo
QINGHUA ZHANG
Yunhe Wang
Venue: Accepted by TMLR ()

Abstract: Clustering is an essential task for the purpose that data points can be classified in an unsupervised manner. Most deep clustering algorithms are very effective when given the number of clusters K. However, when K is unknown, finding the appropriate K for these algorithms can be computationally expensive via model-selection criteria, and applying algorithms with an inaccurate K can hardly achieve the state-of-the-art performance. This paper proposes a plug-and-play clustering module to automatically adjust the number of clusters, which can be easily embedded into existing deep parametric clustering methods. By analyzing the goal of clustering, a split-and-merge framework is introduced to reduce the intra-class diversity and increase the inter-class difference, which leverages the entropy between different clusters. Specifically, given an initial clustering number, clusters can be split into sub-clusters or merged into super-clusters and converge to a stable number of K clusters at the end of training. Experiments on benchmark datasets demonstrate that the proposed method can achieve comparable performance with the state-of-the-art works without requiring the number of clusters.


Published in Transactions on Machine Learning Research (05/2023)
Deep Plug-and-Play Clustering with Unknown Number of Clusters
An Xiao Huowei Noah's Ark Lab
on.ziao
Hanting Chen
chenbantinggghuuuuusccco
Huawei Noah's Ark Lab
Tianyu Guo
Hiangu.ggu@@huawes.ccm
Huawei Noah's Ark
Qinghua Zhang
a. changginnghuuc@huwee..com
Huawei Noah's Ark Lab
Yunhe Wang"
yunhe. wunhe.wang@huawei.coo
Huowei Noah's Ark Lab
Reviewed on OpenReview: https: openreview. net/ formm id= w...66bbcggg0 cggaaa
Abstract
Clustering is essential task for the purpose that data points can be classified in an unsu- pervised manner. Most deep clustering algorithms are very effective when given the number of clusters K. However, when K is unknown, finding the appropriate K for these algorithms can be computationally expensive via model-scloction criteria, and applying algorithms with an inaccurate can hardly achieve the stale-of-the-art performance. This paper proposes a plug-and and-play clustering module automatically adjust the number of clusters, which can be easily embedded into existing deep parametric clustering methods. By analyzing the goal of clustering, split-and-merge framework is introduced to reduce the intra-class diversity and increase the inter-class difference, which leverages the entropy between different clus- ters. Specifically, given an initial clustering number, clusters can be split into sub-clusters or merged into super-clusters and converge to a stable number of clusters at the end of training. Experiments on benchmark datasets demonstrate that the proposed method can achieve comparable performance with the statc-of-the-art works without requiring the number of clusters.
1 Introduction
Clustering is a fundamental problem in unsupervised learning, widely applied to various applications computer vision. The goal of clustering is to partition similar data into the same cluster and dissimilar data into different clusters. Since the late 20th century, quite a few seminal works have been proposed to address this problem, including K-means (MacQueen et al. 1967), DBSCAN (Ester et al. 1996), OPTICS (Ankerst ct al. 1999). STING (Wang et al. 1997), etc. With the success of neural networks, deep clustering methods have become one of the mainstteam choices in unsupervised classification since they achieve much higher performance than the traditional methods, especially in computer vision field. Xie et al. (2016) propose deep- embedded clustering to learn the representations and clusters using deep networks simultancously. Yang et al. 20177) utilize a deep wetw to learn a K-means- <-meens-friendly space for the clustering task.
Ghasedi Dizaji et al.
*Corresponding author.

---

Published in Transactions on Machine Learning Research (05/2023)
Data
Parametric Deep Clustering Model
V
K
Deep Clustering Model
Proposed Plug Component
K Updater
Split or Merge Block
Split phase
Merge phase
A A
AAA
A
A
AZA
A
A
A
A
O
444
*
A
A A
A
A x
A A
A AA
A
A A A
A AAA
O O Original Data
A
A
A
*
x
K = 2
Split
K
Merge
= 3
Proposed plug-and-play module can be applied in existing deep clustering methods. The split phase split the dissimilar data points in one clusters to minimize the inter-class diversity. The merge phase merge the similar data points in different clusters to maximize the intra-class diversity.
Figure 1:
(2017) introduce a convolutional auto-encoder to joint learn the embedding and cluster assignments. Yang al. (2016) utilize the variational auto-encoder model the data generatively with Gaussian Mixture Model.
Although the works above have achieved great success, an important issue has not been well addressed, i.e., the vast majority of existing deep clustering algorithms require the providing number of clusters when applied to an unlabeled dataset. Furthermore, these deep methods usually cluster different data points by the fully-connected layer, which is optimized end-to-end and should be pre-defined before the training process. Therefore, a series of works focus on finding the appropriate clustering numbers for clustering. Antoniak (1974) proposes the Dirichlet Process to calculate the number of clusters in Gaussian Mixture Model. Rodriguez & Laio (2014) utilize the grid search to find the optimal number of clusters. However, be computationally expensive via model-selection criteria, especially for deep clustering methods whose training process is time-consuming. There exists few deep clustering works (Chen 2015 Shah & Koltun 2018 Wang et al. 2021 Zhao et al.) 2019 Tapaswi et al. 2019 Ronen et al. 2022 trying to analyze the clustering task without knowing the number of clusters. For example, Tapaswi et al.
applying these algorithms
2009 introduce the ball cluster learning to carve the data space into balls for each cluster. Ronen et al.
(002 propose the DecpDPM by extending the Dirichlet Process Gaussian Mixture Model. However, the performance of these deep non-parametric methods (namely, methods that do not require the number of clusters K) are still far from aforementioned parametric methods, since it is difficult train the clustering network and find the best K simultancously.
In this paper, we propose deep plug-and-play clustering method with unknown number of clusters, which is illustrated in Figure[[ Instead of developing an effective non non- -on-mmamttricc method, we aim to introduce a plug- and-play module that can be casily embedded into the stato-of-tho-art parametric clustering method without affecting its performance. Specifically, we analyze the goal of clustering in the non-parametric situation, that is to minimize the intra-class diversity and maximize the inter-class difference. A class split scheme is
2

---

Published in Transactions on Machine Learning Research (05/2023)
introduced to split cluster into sub-clusters if intra-class diversity is large. The clusters will be merged when the inter-class difference between clusters is small. We measure the similarity by leveraging the entropy between data points. The proposed algorithm can be applied to existing clustering methods and achieve state-of-the-ar performance in various datasets without knowing the number of chusters. Experimental results demonstrate that the proposed split and merge scheme can successfully find the clustering numbers and train the clustering network.
2 Related Works
Deep Clustering methods. Deep learning has shown its great power in several fields, with no exception for the clustering method. From the very beginning, deep belief networks (DBN) were introduced to establish a deep clustering framework. Starting from this, AE (Bengio et al. 2006) extends DBN process input with continnous value and proposes an unsupervised pro-train strategy to describe the similarity. DAE (Vin- cent et al. 2010) further enhance DBN with denoising prior. With the development of neural networks, DeCNN (Ziler et al., 2010) builds a deconvolution module to extract mid-level representations in an unsu- pervised way with a sparsity constraint, which achieves noisc-robust clustering results. Several in-style idcas have been injected into the deep clustering methods in recent years. DDC (Chang et al. 2019) combines global and local constraints to investigate patterns' relationships and enhance the discriminative ability of features. CC (Li et al. 2021 proposes an online clustering method with the utilization of contrastive learning principles.
From the perspective of feature extraction and clustering, JULE Yang et al. 2016) updates clusters and features alternatively in a recurrent process. Furthermore, DAC (Chang et al. 2017) bridges feature extrac- tion with clustering by defining the clustering problem as a binary pairwise-classfficate framework. While SCAN (Van Gansbeke et al. 2020) disentangles the feature extraction step and the clustering step again, which prevents the model from being influenced by low-level features. Mcanwhile, ADC (Hacusser et al., 2018) introduces centroid variables and optimizes them according to the objective training function, which allows no more additional classifiers to be trained separately.
In practice, the number of clusters & is usually not casy to access. Based on this situation, several methods are proposed to estimate k or avoid using it. Lewis et al. (0044) utilizes DPM sampler to get k. DeepDPM (Ronen et al. 2022 proposes a split or merge strategy and tries to remove the requirement. of k.
Non-parametric Classical Clustcring. A group of classical clustcring algorithms is free of the prior of k. Density-basce clustering algorithms are a representative family of clustering algorithms that do not require parameter k. DBSCAN (Ester al.] 1996) is based on density and does not require the prior of k. Later, Optics (Ankerst et al. 1999) is proposed to address the shortage of DBSCAN that makes it hard to fit the data of varying densities. Another well-known family of non- non-parametric clustering algorithms is the hierarchical clustering algorithm, such as BIRCH (Zhang et al. 1996). CHAMELEON (Karypis et al.
1999,, ROCk (Guha et al.) 2000
3 Method
Denote [ as the whole N data points, the goal for clustering is to partition these data points into different groups, where similar data should be put in the same group. There are various index to measure the performance of clustering results Halkidi et al. (2002), including Sum of Squared Error (SSE), Silhouette Coefficient, Calinski-Harabe Index, measurement for the evaluating the clustering results: Compactness and Separation. Given K as the number of clusters, the Compactness CP and Separation SP can be formulated as:
Index, ctc. For the case of analysis, we take two basic
CP= ΣV
d(x xf),
kE[R]
(1)
k
SP =
Σ
d(x
xx)) )
[G[K]]]]
3

---

Published in Transactions on Machine Learning Research (05/2023)
where x denotes the i-th sample in the k-th cluster, d(.,)) -) is metric to evaluate the distance between two samples, and [K] is the positive integer set from 1 to K, i.c. (1, K}. Compactness measures the distance between samples in the same class, while the Separation measures the distance between samples in different classes. The goal of clustering can be regarded to minimize Compactness and maximize Separation. Since the number of clusters K usually unknown real-world applications, we also need find the optimal value of K for the clustering algorithm. For the simplicity of notation, we denote D k) = Eig d(x,, x5) as the inter-class similarity and k2) Eig d(x{1 x) the intra-class similarity The whole optimization problem to clustering with unknown number of clusters can be formulated as:
k k E ksE
arg min K
Σ KE[K]
((
k2),
(2)
where À is hyper-parameter to balance the two terms and is divided by K to calculate the averaged distance between clusters. When utilizing traditional clustering algorithm, one search the number of clusters K in traversal since the compulational cost is small. However, this traversal searching is unsuitable for deep learning based clustering algorithms since they are computationally expansive. To this end, we propose a plug-and-play clustering module to gradually adjust by a split and merge scheme during one training process for deep clustering methods.
3.1 Cluster Split to Minimize Inter-Clat Diversity
We first consider the situation that current number of clusters K' smaller than the optimal value K In this situation, the first term in the optimization problem - becomes the dominate term, since many dissimilar data points are classifted into the same cluster due to the limited clustering numbers, though they are generally supposed to belong to different clusters. Therefore, split scheme to increase the number of clusters is required.
As it is difficult to directly estimate the optimal value K we propose to increase K in a greedy manner. Given a clustering number K", a parametric clustering method can classify the data points into K' classes. We aim to investigate whether the points in each cluster can be further divided into two clusters. We propose hierarchical clustering algorithm solve this problem.
As mentioned above, optimize the clustering network by minimizing the intra-class similarity between the data points. Hence, if data points in one cluster can be easily divided into two sub-clusters, the points in this cluster are dissimilar and ought to be further separated. We then determine whether each cluster should be split by analyzing optimization problem 2
Proposition 1. When sub- clusters K' and K2 satisfy the following equation:
k kk
K +1 +2) D(K ((K
2
A
D(k1, k2),
(3)
K(K +1)
applying the split phase will decrease the value of optimization problem
In order to determine whether a cluster should be split, similarity between the data points in two sub-clusters nceds to be evaluated. There are various metrics to measure the similarity between distributions, including mutual information, Kullback-Leible (KL) divergence, Jensen-Shanne (JS) divergence and Wasserstein distance. We the JS divergence to measure the similarity between two sub-clusters, since it is symmetry
4

---

Published in Transactions on Machine Learning Research (05/2023)
and easy to calculate. Specifically, the JS divergence can be formulated as:
1 2 JS(K = DKL (K'
K' + +K²
K +K2
+ DKL(K
2
2
2
2xx
2xx=(x
Σ PRI(X; log(
Pkaa(x log(
(x Pxa(xx
Px Pxo(x (4)
Σ (Pxc(x)5) ( + Piea (x, 162 log(P (xx ()
log( Pki (x (xxxx) + (x K²
where Pki() (.) or (-) denote the probability of data points classified into cluster K or K². By introducing the JS divergence, we can evaluate whether the two sub-clusters are dissimilar. When the JS divergence becomes larger, two sub-clusters can be divided more easily. Therefore, we set threshold T, for splitting the clusters. If the JS divergence of the two sub-clusters JS(K* 2 Ts the split operation is employed in the main clustering stage for the k-th cluster. Specifically, the weights for k-th cluster will be copycatted for another cluster and the number of clusters is therefore increased. In fact, the threshold can be determined by inequation
3 by utilizing the JS divergence as the distance measurement:
2A +1 +2) 1S(
E
JS(k1l1b2)
K(K+ 11)
k2((]
(5)
A 2K(A+K+1)
JS(K
Σ
JS(K)
kn [A
Therefore, we can set the threshold for the determination of split according to following equation:
T, 2K + 11)
Σ
JS(kil142)
(6)
We split the data points in each cluster & into two sub-clusters k- and k22 utilizing the algorithm A. More concretely, we directly add K' assistant 2-class classification feed-forward neural networks to the K' di- mensional output of algorithm A, and the overall number of clusters is expanded to 2K" To make the sub-clusters different after split, introduce a split loss for separating the newly added cluster with the original cluster by maximizing the JS divergence between the two sub-clusters:
Lsplit
Torii 7 Σ JSkilk())
where Lors denotes the original training loss of algorithm A. We set ay kG and ky are the split sub- clusters, otherwise Oay 0. By hierarchically dividing the sub-clusters and introducing the JS divergence, can split the dissimilar data in one cluster into sub-clusters, therefore increasing the number of clusters.
3.2 Cluster Merge Maximize Intra-Class Diversity
Another important assumption in clustering is that the data point in different clusters should be dissimilar. When the number of clusters is much higher than its optimal value, the similar data point could be divided into different clusters, which reduces the inter-class diversity of the clustering algorithm. Consequently, we also propose a class merge scheme to decrease the nunber of clusters and merge the similar data points in different clusters into the one cluster.
Same as the problems mentioned in split scheme, is difficult and unstable to directly merge all the similar clusters for deep clustering methods. Thus, we apply a greedy manner to merge two clusters at one time. The JS divergence can measure the similarity of the data points between two clusters. Denote & the
5

---

Published in Transactions on Machine Learning Research (05/2023)
Algorithm Deep plug-and-play clustering with unknown number of clusters.
Require: parametric clustering algorithm A, an initial number of clusters K", the split and merge hyper- parameter X, and the dataset X' to be clustered.
Initialize the clustering network W, set current number of cluster K* K';
repeat
3: Apply the algorithm A to training the network W with current number of cluster K"
4: Phase 1: Split clusters.
5: for in [K*] do
6:
Split data X; of i-th cluster into two sub-clusters K and K2 using algorithm A; Calculate the JS(K' [[A2) and the threshold T, according to Equ. 6
if JS( JS(K'1| > T, then Split and increase K"; end if end for
10:
11:
12:
Apply the algorithm A to training the network N with K and Equ.
13:
Phase 2: Merge clusters.
14:
Find candidate merge clusters K and K' according Equ. Calculate the JS* and the threshold Tmm according Equ. 12
15:
16:
if JS(K*| < Tm then
17:
Merge K* and KJ, decrease K end if
18:
19:
Apply the algorithm A to training the network N with K"; until convergence
20:
Ensure: A well-trained clustering network N with an accurately estimated number of clusters K
current number of clusters, aim to find the most similar clusters KJ and K?, which can be formulated as:
K K2
arg min J8(k
(8)
ky (kk
By traversing the data points in all clusters and calculating the JS divergence pariwiscly for each two clusters, we select two clusters with the largest JS divergence. Likewise, we set a threshold T,, to determine whether we should merge the clusters. the JS divergence of these two clusters meets JS(K* [|²)) I Tm: they will merged into one cluster. Specifically, the weights in the fully connected layer for the two clusters will averaged obtain the weight of the merged cluster. Without loss of generalization, we can assume that the two clusters K and 8² are the last two clusters.
Proposition 2. When two clusters K2 and K² satisfy the following equation:
kn of Σ
22
2A +2)))(( + D(K' K2) K(K
A
D(k2, k2).
(9)
applying the merge phase will decrease the value of optimization problem where Km denotes the merged cluster.
By utilizing the JS divergence the distance measurement, have:
k Σ
2A +2
A
JS(K'IKK)
JS(A) (k2).
(10)
K(K - 1)
kn K
Finally, the relationship based on JS divergence can be formulated as follows,
ki
JS(K2 2(K 1)(1 K)
Σ
JS(kil/k)
(11)
Ag (K--2 2),

---

Published in Transactions on Machine Learning Research (05/2023)
Then we set the threshold for the determination of merge according to following equation,
by Au
T 2(K 1)(2 K)
J8(k)lkk))
(12)
in 2
Same as the strategy of the split phase, if the JS divergence between two merged clusters JS(K2 ( is smaller than the threshold obtained above, these two clusters will be decided to be merged.
3.3 Split-Merge Scheme to Estimate the Number of Clusters
The overall algorithm the proposed method can be found in Algorithm| [ First, the network trained by paramctric clustering algorithm A with an initial number of clusters K'. When K' far from the optimal value K* the performance of the network will sulfer degradation. In order to sovle the problem, we propose to iteratively apply the split and merge module to estimate the number of clusters automatically alongside the training process. Concretely, the training process of our method is as following, we first train the whole network till the current loss does not decrease anymore. Then we compute the value of current Tm and T, for merge or split, separately. When the network training is converged at the current. K clusters, the threshold T, will be larger than Tm. By measuring the distances of samples between every two clusters and comparing to Tm, we will start merge operation if the condition is satisfied. Once merge is executed, we will pass the split phase and directly jump into the next loop. The situation the same for split, once split condition is satisfied, merge phased is passed. And the end of whole training, the inferred K converges when JS divergence is between T'm and The proposed module can be applied in various parametric clustering algorithms to achieve a accurate estimation of the number of clusters and the performances are comparable to the original clustering algorithms.
Lemma 3.
The split and merge condition and cannot be satisfied simultaneously.
Lemma 4. The wumber of clusters can only be monotonically changed during the training process.
Elitke Proof. We denote V(K) as ΣME[K] D(k,k) 2/ EkikkE(K)) the split condition equal to:
D(k kg)- From Proposition 1, we conclude that
k #22
Σ k(k
A K ++
Σ
D(k2, k2) S
Σ D(K k)
A K
Σ kL,KE]|K]
D(k,, (13)
kEIIK KEI
(IK-
KE[K]
which can be formulated as V(K + 1) < V(K). From the proof of Proposition 2, we can also conclude that the merge condition 9 is equal to V(K - 1) < V(K). From the proof of Lemma 3, we conclude that there is impossible that V(K - 1) < V(K) and V(K +1) V(K). Therefore, it remains the probability that V(K +) < V(K) < V(K 1), V(K+ +1) V(K) V(K 1) and V(K + +1) > V(K) < V(K 1). If V(K + > ((K) V(K- 1), the algorithm converged. If V(K +) < V(K) < V(K - 1) meets the split condition and the number of clusters K grows to K + 1, the merge condition cannot be satisfied since VKK + 1) < VKK,, which means the number of clusters K + cannot go back K. The proof is same when meets the merge condition. Therefore, the number clusters can only be monotonically changed.
Proposition 5 (Convergence of the proposed algorithm). The split-merge scheme using the inequa- tion and will converge at an O speed, where the ramber of acting the split-merge schemes. Moreover, the scheme will recover the ground truth number of clusters K* when
kI Σ
A
K" arg min
Σ D(k,k) KE[K]
D(ki,
(14)
K
From Lemma 4, since the the number of clusters can only be monotonically changed and bounded (K 2 1 and K < m where m is the number of samples), the proposed algorithm can finally converge. Moreover, we conclude that the algorithm convergod when V(K*+I V(K*) V(K* which mcans 14is is satisfiod.
The complete proof of the above lemmas and proposition can be found in the appendix.
7

---

Published in Transactions on Machine Learning Research (05/2023)
Table 1: Comparison with srate-of-the-ars methods. Kg denotes the initial number of clusters.
Method
CIFAR-10
CIFAR-100
STL-10
ImageNet-10
Metric
NMI
ACC
ART
NMI
ACC
ARI
NMI
ACC
ARI
NMI
ACC
ART
AC
(Gowda & Krishna
1978
10.5
22.8
6.5
9.8
13.8
3.4
23.9
33.2
14.0
13.8
24.2
6.7
NMF
CCat al. 2009
19.0
3.4
7.9
2.6
4.6
6.5
AE
BBngto et a.. 2006
23.9
31.4
16.9
10.0
16.5
4.8
25.0
30.3
16.1
21.0
31.7
15.2
DAE
Vincent et 2010
25.1
29.7
16.3
11.1
15.1
4.6
22.4
30.2
15.2
20.6
30.4
13.8
DCGAN
[aadoor
2015
26.5
31.5
17.6
12.0
15.1
4.5
21.0
29.8
13.9
22.5
34.6
15.7
DeCNN
Zeiler et at.
24.0
28.2
17.4
9.2
13.3
3.8
22.7
29.9
16.2
18.6
31.3
14.2
VAE
Kingma & Welling
2013
24.5
29.1
16.7
10.8
15.2
4.0
20.0
28.2
14.6
19.3
33.4
16.8
JULE
Yang et al.
2016
19.2
27.2
13.8
10.3
13.7
3.3
18.2
27.7
16.4
17.5
30.0
13.8
DEC
Xie et. al.
2016
25.7
30.1
16.1
13.6
18.5
5.0
27.6
35.9
18.6
28.2
38.1
20.3
DAC
Chang
2017
39.6
52.2
30.6
23.8
47.0
25.7
32.7
30.2
ADC
Hacusser et al. 2018
32.5
16.0
53.0
DDC
Chang el al.
2019
42.4
52.4
32.9
37.1
48.9
26.7
43.3
57.7
34.5
DCCM
Wu al.
2019
49.6
62.3
40.8
28.5
32.7
17.3
37.6
48.2
26.2
60.8
71.0
55.5
Ji
al.
51.3
61.7
41.1
25.7
43.1
49.9
29.5
MMDC
Shiran & Weinshall
2021
57.2
70.0
25.9
31.2
49.8
61.1
71.9
81.1
PICA
Huang et al.
2020
56.1
64.5
46.7
29.6
32.2
15.9
78.2
85.0
73.3
DCCS
Zhao al.
2020
56.9
65.6
46.9
37.6
48.2
26.2
60.8
71.0
55.5
DHOG
Darlow & Stor key
2020
58.5
66.6
49.2
25.8
26.1
11.8
48.3
27.2
GATChustr [Niu et al.
2020
47.5
61.0
40.2
21.5
28.1
11.6
44.6
58.3
36.3
59.4
73.9
55.2
IDF Tao et al. 2021
71.4
81.5
66.3
42.6
42.5
26.4
64.3
75.6
57.5
89.8
95.4
90.1
CC [15 al. 202
70.5
79.0
63.7
43.1
42.9
26.6
76.4
85.0
72.6
85.9
89.3
82.2
MiCE 1sai
2020
73.7
83.5
69.8
43.6
44.0
28.0
63.5
75.2
57.5
SCAN Van Gansbeks al. 2020
71.2
81.8
66.5
44.1
42.2
26.7
65.4
75.5
59.0
86.2
92.0
83.3
Ours k3=3)
71.9
82.4
67.5
45.2
43.8
28.1
64.3
74.5
57.6
88.6
91.2
87.1
Ours Kg=20)
71.1
81.6
66.2
65.1
74.7
58.9
86.9
91.8
84.7
Ours
(K==3)
43.1
27.8
4
Experiments
In this section, we evaluate the effectiveness of the proposed method by comparison with the state-of-the-ee and ablation studies.
Datasets and Metrics. We conduct experimental evaluation the CIFAR-10 Krizhevsky al. 2009 CIFAR100-20 (Krizhevsky et al.) 2009), STL-10 (Coates et al. 2011). ImageNet-10 (Deng al. 2009 and ImageNet-50 (Deng et al.) 2009) datascts. We train and evaluate these datasets using their train and validation split to study the generalization properties of the proposed method. To evaluate the clustering performance of various methods, we adopt three standard evaluation metrics: Clustering Accuracy (ACC), Normalized Mutual Information (NMI) and Adjusted Rand Index (ARI).
Training details. We apply the proposed plug-and-play module in the deep clustering method SCAN (Van Gansbeke et al., 2020) without changing their original training settings, including the learning rate, weight decay, neural network architecture, data pre-processing and augmentation. For the proposed method, the hyper-parameters À is set as 2.0.
4.1 Comparison with the State-of-the-art
To demonstrate the effectiveness of the proposed method, report the performance with the widely used deep clustering method SCAN (Van Gansbeke et al. 2020). Table I shows the results the CIFAR-10. CIFAR100-20, STI-10 and ImageNet-10 datascts. As a result, traditional clustering algorithms such as AC and NMF can hardly achieve good performance on these datasets, which results in 200 accuracies. Deep Dearning-baseee clustering methods, such as DDC, DAC and DCCM, achieve much better performances. However, the statc-of-tho-art clustering algorithms (e.g., CC, MiCE and SCAN) are parametric, which requires the exact number of clusters K. Therefore, we propose a plug-and-play module solve this problem. We apply the proposed module to the SCAN algorithm. For CIFAR-10, STL-10 and ImageNet-10,

---

Published in Transactions on Machine Learning Research (05/2023)
Table 2: Comparison of the mean inferred value for K for different initiations.
Dataset
Initial
3
20
30
CIFAR-10
10::0
1010
CIFAR100-20
19.7#2.1
19.8+1.5
STL-10
9.720.5
10.3+0.9
ImageNET-10
10:00
10.3+00.5
Table 3: Comparison with state-of-the-art methods (3 runs) on the ImageNet-50 dataset.
Init k
Inferred k
ACC
MNI
ART
SCAN Van Gansbeke et al.
2020
50
73.7+1.7
79.7
61.8+13
SCAN Van Gansbeke ct al.
2020
19.4+0.11
60.6
23.0+0.33
DBSCAN Ester al. [996]
16.0
24.0.10.0
52.010.0
9.0+0.0
moVB Hughes & Suddert h
[2013
46.2+11.3
55.04:2.0
70.0+1.0
43.0+1.0
DPM Sampler Dinari et al.
(0199)
72.042.6
57.0+1..0
72.0+0.0
43.0=1.0
DecpDPM Ronen et al. (2022
10
55.
66.0+1.0
77.0+0.0
54.0++10
Ours
10
50.6
73.311.3
80.1
62.3+1.5
we set the initial numbers of clusters Ko to 3 and 20, which covers both scenarios when the initial Ko is less or greater than the ground-truth truth value of the number of clusters. Likewise, we set Kg for CIFAR100-20 be 3 and 30. As shown in Table [ our proposed method still achieves comparable performance with these parametric methods matter whether the initial cluster number is small or large. Besides, method can automatically adjust the number of clusters, we report the inferred nunber of clusters in Table The results demonstrate that inferred K for our split-merge module at the end of training is close to the real number of clusters K with different initiations, suggesting that our method effectively adjusts the number of clusters during training. Note that all results are averaged from 3 different runs.
We further evaluate the proposed method on the ImageNet-50 dataset, which is more complicated since 50 categories of images need to be clustered. We compare the proposed method with both parametric and non-parametric algorithms. As shown in Table 3 the parametric clustering algorithm (SCAN) achieves the best performance (73.7% accuracy) when given the actual number of clusters. However, in real-world scenarios, the number of clusters is usually unknown, and thus these parametric algorithms can hardly be applied (e.g., When k=10, the accuracy of SCAN degrades to 19.4). Although the non-parametric clustering methods do not require the number of clusters, currently, the state-of-the-art method (DeepDPM) can only achieve a 66.0% accuracy, 77.0% NMI and 54.0% ART on this dataset, which much lower than parametric algorithms. The proposed split-merge module can address the aforementioned problem and achieve the best performance without the exact number of clusters. Moreover, the number of clusters estimated by ours is 50.6, which is ideally close to the ground ruth (50) and better than the estimated value of DeepDPM (55.3), further indicating the effectiveness of the proposed method in more complicated scenarios.
4.2 Generalizability of the Proposed Module
On different deep clustering frameworks. We combine our proposed split-merge module with another two paramatric deep clustering methods: NNM (Dang et al.) 2021) and GCC (Zhong al. 2021). Table 4 shows the clustering performances on CIFAR-10 with different initial K. Results show that for various parametric methods, when K diverges form the ground-truth K, the performances deteriorate to a large extend. However, when embedded with our proposed module, those methods acheive much better clustering accuracies (e.g.,, when K=3, the accuracy of GCC increase from 29.0% to 84.1%) and yield an accurate close to the GT.
On different domains of data. We
9

---

Published in Transactions on Machine Learning Research (05/2023)
Table 4: Performance of the proposed module with different clustering methods.
Initial K
Method
ACC
NMI
ART
Inferred K
NNM
28.910.3
45.2:0.4
25.820.1
NNM+ Ours
80.5+1122
75.1
69.3+0.77
9.3 +0.5
3
GCC
29.0+:0.1
45.240.4
27.9+0.11
GCC+Ours
84.1#2.6
78.0#1.6
74.7#2.1
10.7 #0.5
NNM
84.1+0.1
74.8+0.1
70.2+0.2
NNM+Ours
84.3+00.1
75.0
70.8+t.11
10.0+..0
10
GCC
85.6+0.1
76.7#0.2
72.8+0.1
GCC+Ours 85.8+0.8
77.6+0.55
73.6+1.5
10.0++..0
NNM
50.2:11.9
63.611.6
44.8+t0.3
NNM+Ours 80.4
74.1#1.2
68.7+2.4
10.7
20
GCC 49.8++0.2
68.2+0.22
49.2+0..3
GCC+Ours
85.2:10.6
77.4
72.4+1.2
10.0+:.00
Table 5: Results on the CIFAR-10 dataset using different numbers of clusters Ko-
Ko
3
10
15
20
30
40
50
100
SCAN
28.6
82.2
58.8
45.9
33.4
25.9
21.9
11.9
Ours 82.4
82.4
82.9
81.6
82.0
77.5
70.9
72.4
Inferred
10
10
10
10
10
11
12
12
4.3
Ablation Studies
In this subsection, we further conduct ablation studies, including various initial clustering numbers Ko and different components to analyze the proposed method.
Various initial clustering numbers Kg- As is shown in Algorithm I the proposed method needs an initial number of clusters Ko to train the clustering network, then the split and merge module can be applied, Therefore, it is essential to investigate the influence of Ko in the proposed method. Table 5 shows the models starting with different numbers of clusters. We compare the proposed method with parametric clustering algorithm: SCAN.
Obviously, the performance of SCAN is sensitive to the number of clusters since cannot adjust cluster numbers automatically during the training process. When the ground-truth number of clusters K* is known (Ko K* =0), SCAN can achieve the best accuracy (82.2%). However, when there is a gap between Ko and K*, the performance of SCAN degrades a lot. For example, when Ko=3 and Ko=100, the accuracies of SCAN are only 28.6% and 11.9%, which are far from its optimal accuracy (82.2%). In contrast, when utilizing the split and merge module, the proposed hod achieves stable 822 accuracy (Kn from 3 to 30), which outperforms the original SCAN by a large margin. Even if the initial number is nowhere near the ground-truth clusters (Ko from 40 to 100), the proposed method can still achieve accuracies above 70.0% and generate cluster numbers close to 10.
As is mentioned in the methods, the proposed threshold formulas in split or merge phase involve pre-defined X, which is an oracle hyper-parameter and cannot be known in advance. However, fixed hyper-parameter that remains constant during the optimization process. We conduct an experiment to study the impact of different values of À in Table 6 Results show that when À is within a reasonable scope, the clustering performances remain steady. Besides, X is robust. for different datasets with different number of clusters. We set À = 2 for all datasets, which avoids the heavy
Various values of hyper-parameter
clarify here that the value of X does not affect the optimization problem, as it is a
tuning works.
Different components of the proposed method. To evaluate the effectiveness of each component in the proposed method, conduct ablation study in Table 7 We first study the case that the initial number of
10

---

Published in Transactions on Machine Learning Research (05/2023)
Table 6: Results of the proposed method with different values of X.
1.5
1.8
2.2
2.50
CIFAR-20 20
39.84
43.57
44.71
41.34
41.40
STL-10
69.46
71.14
78.40
76.49
75.53
Table 7: Performance of the proposed method under different ablations.
K
Ko=10
Ko=20
20
ACC
NMI
ARI
ACC
NMI
ARI
ACC
NMI
ARI
No split/ merge
28.7
46.2
26.4
82.2
71.6
66.8
47.3
62.3
43.2
No split
28.9
46.1
26.4
75.4
68.9
62.1
81.2
70.9
65.6
No merge
79.7
71.3
66.9
82.1
71.5
66.8
47.1
61.7
42.6
No split loss
28.6
44.5
25.3
77.6
69.9
63.3
81.7
71.1
66.4
Full method
82.4
72.2
67.9
82.4
71.7
67.4
82.7
72.3
67.7
clusters is less than the ground truth, i.c., K6=3. If no split and morge schome exists, the clustering algorithm can only achieve 28.7% accuracy since the number clusters remains unchanged during training. If there is no split phase, the performance of the proposed method is still bad. The proposed method can achieve 79.7% accuracy when involving the split module, which indicates that the split phase useful when the number of clusters is relatively small. Moreover, the split loss is essential to split the two sub-clusters. Otherwise, the proposed method can only achieve 28.6% accuracy even if the split phase is included. When the full method is adopted, the proposed method achieves the best performance (82.4% accuracy).
We then evaluate the situation that the initial number of clusters greater than the ground truth, i.c., Ko=20. Similarly, the merge phase not applied, the proposed method cannot achieve satisfying perfor- mance since close clusters cannot be merged. By utilizing the merge and split phase, the proposed method achieves an 82.7% accuracy, which suggests that each component is essential.
Running Times. We compare the rumning time of our method with different initial K to the original SCAN. Results show that the rumning time has varying degrees of increase, C.g., on CIFAR-10, when the initial K = 3, the running time is 3x compared to a single run of SCAN. However, it is still much more efficient than training SCAN multiple times with a different K for model selection. Thus, the value and impact of our proposed module are clear.
4.4 Visualization Results.
We conduct visualization on the CIFAR-10 dataset to investigate the training process of the proposed method. Figure 2 shows the t-sne visualization of the proposed method during training, where different colors denote data points from different categories. The initial number of clusters is set to 3. At the beginning of training, the number of clusters is much smaller than the ground ruth. Therefore, the data points hardly be divided in both feature and output spaces. During the training process, the proposed method gradually adjusts the number of clusters by splitting the clusters. As result, the network trained by the proposed method converges to k=10, and the data points are classified in different clusters, as shown in the figure, resulting in the best accuracy (82.5%).
5 Conclusion
Deep clustering algorithms have achieved great success in unsupervised learning. However, most of these algorithms are paramotric, which requires the number of clusters. When the number clusters unknown, the performance of existing deep clustering algorithms suffers a lot. To this end, we propose a plug-and- aang-and-play module that can be directly applied to existing parametrie clustering methods by analyzing the JS divergence
11

---

Published in Transactions on Machine Learning Research (05/2023)
1=3, ACC=28.9 epochs -20
k=5, ACC=46.8 epochs =40
k=8, ACC=65.7 epochs -60
k=10, ACC=82.5 epochs 150
Figure 2: The training process of the proposed method. The images in the top row and the bottom row are the t-sne visualization results of features and outputs, respectively,
between clusters. Specifically, split scheme is introduced to minimize the distance between data points the same clusters. In contrast, merge scheme is roduced to maximize the distance between data points in different clusters. As a result, the proposed method can successfully adjust the number of clusters when added to the cxisting clustering algorithms, achieving the statc-of-the-art performance without knowing the number of clusters. Visualization and ablation studies demonstrate the effectiveness of the proposed algorithm in finding the accurate number of clusters.
References
Mihael Ankerst, Markus M Breunig, Hans-Peter Kriegel, and Jörg Sander. Optics: Ordering points identify the clustering structure. ACM Sigmod record, 28(2):49-60, 1999.
Charles Antoniak. Mixtures of dirichlet processes with applications bayesian nonparametric problems. The annals of statistics, pp. 1152 1174, 1974.
Yoshua Bengio, Pascal Lamblin, Dan Popovici, and Hugo Larochelle. Greedy layer-wise training of deep networks. Advances in neurol information processing systems, 19, 2006.
Deng Cai, Xiaofei He, Xuanhui Wang, Hujun Bao, and Jiawei Han. Locality preserving nonnegative matrix factorization. In Pwestt-ffrrtt international joint conference on artificial intelligence, 2009.
Jianlong Chang, Lingfeng Wang, Gaofeng Meng, Shiming Xiang, and Chunhong Pan. Deep adaptive image clustering, In Proceedings of the IEEE international conference on computer vision, pp. 5879-5887, 2017.
Jianlong Chang, Yiwen Guo, Lingfeng Wang, Gaofeng Meng, Shiming Xiang, and Chunhong Pan. Deep discriminative clustering analysis. arXiv preprint orXiw:1955006691 2019.
Gang Chen. Deep learning with nonparametric clustering, arXiv preprint arXiv: MXXi:1501.0300 2015.
Adam Coates, Andrew Ng, and Honglak Lee. An analysis of single-layer networks in unsupervised feature learning. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pp. 215-223. JMLR Workshop and Conference Proceedings, 2011.
Zhiyuan Dang, Cheng Deng, Xu Yang, Kun Wei, and Heng Huang. Nearest neighbor matching for deep clustering. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pottern Recognition, pp. 13693 13702, 2021.
12

---

Published in Transactions on Machine Learning Research (05/2023)
Luke Nicholas Darlow and Amos Storkey. arXiv:2003.08821, 2020.
Dhog:
Deep hierarchical object grouping. arXiv preprint
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei- Imagenet: A large-scale hierarchical image database. 2009 IEEE conference on computer vision and pottern recognition, pp. 248-255. Iecc, 2009.
Or Dinari, Angel Yu, Oren Freifeld, and John Fisher. Distributed meme inference in dirichlet process mixture models using julia, In 2019 19th IEEE/ACM International Symposium on Cluster, Cloud and IEFE, 2019.
Grid Computing (CCGRID), pp.
Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu, et al. A density-based algorithm for discovering clusters in large spatial databases with noise. In kdd, volume 96, pp. 226 231, 1996.
Kamran Ghasedi Dizaji, Amirhosscin Herandi, Cheng Deng, Weidong Cai, and Heng Huang. Deep clustering via joint convolutional autoencoder embedding and relative entropy minimization. In Proceedings of the IEFE international conference. on computer vision, pp. 5740,5745, 2017.
K. Chidananda Gowda and G Krishna. Agglomerative clustering using the concept of mutual nearest neigh- bourhood. Pattern recognation, 10(2):105-112, 1978.
Sudipto Guha, Rajeev Rastogi, and Kyuscok Shim. Rock: A robust clustering algorithm for categorical allribules. Information systems, 25(5):345 366, 2000.
Philip Hacusser, Johannes Plapp, Vladimir Golkov, Elie Aljalbout, and Daniel Cremers. Associative deep clustering: Training classification network with no labels. In German Conference on Paltern Recognition, pp. 18-32, Springer, 2018.
Maria Halkidi, Yannis Batistakis, and Michalis Vazirgiannis. Clustering validity checking methods: Part ii. ACM Signod Record, 31(3)119-2,, 2002.
Jiabo Huang, Shaogang Gong, and Xiatian Zhu. Deep semantic clustoring by partition confidence maximi- sation. Tn Proceedings of the IEEE/CVF Conference on Compuler Vision and Pallern Recognition, pp. 8849 8858, 2020.
Michael C Hughes and Erik Sudderth. Memoized online variational inference for dirichlet process mixture models. Advances in newral information processing systems, 26, 2013.
Xu Ji, Joao Henriques, and Andrea Vedaldi. Invariant information clustering for unsupervised image classification and segmentation. In Proceedings of the IEEE/CVP International Conference Computer Vision, pp. 9874-9874, 2019.
George Karypis, Eui-Hong Han, and Vipin Kumar. Chameleon: Hierarchical clustering using dynamic modeling. Computer, 32(8):68 75, 1999.
Diederik P Kingma and Max Welling. Auto-cncoding variational baycs arXiv preprint arX:::111266114 2013.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
David Lewis, Yiming Yang. Tony Russell-Rosse and Fan Li. Rev1: A new benchmark collection for text categorization research. Journal of machine learning research, 5(Apr):361 397, 2004.
Yunfan Li, Peng Hu, Zitao Liu, Dezhong Peng, Joey Tianyi Zhou, and Xi Peng. Contrastive clustering, Tn 2021 AAAI Conference on Artificial Intelligence (AAAI), 2021.
James MacQueen et al. Some methods for classification and analysis of multivariate observations. In
Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, volume 1, pp. 281 297. Oakland, CA, USA, 1967.
13

---

Published in Transactions on Machine Learning Research (05/2023)
Chuang Niu, Jun Zhang, Ge Wang, and Jimin Liang. Gatcluster: Self-supervised gausian--atention network for image clustering. In European Conference on Computer Vision, pp. 735-751. Springer, 2020.
Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolu- tional generative adversarial networks. arXiv preprint wrXx:1511.004444 2015.
Alex Rodriguez and Alessandro Laio. Clustering by fast search and find of density peaks. science, 344(6191): 1492 1496, 2014.
Mcitar Ronen, Shahaf E Finder, and Oren Freifeld. Deepdpm: Deep clustoring with an unknown number of clusters. arXiv preprint wxXv:2208.14500 2022.
Sohil Atul Shah and Vladlen Koltun. Deep continuous clustering. arXie preprint arXiv: 2018.
Guy Shiran and Daphna Weinshall. Multi-modal deep clustering: Unsupervised partitioning of images. In 2020 25th International Conference on Pattern Recognition (ICPR), pp. 4728-4736 IEEE, 2021.
Yaling Tao, Kentaro Takagi, and Kouta Nakata. Clustering-rreenlly representation learning via instance discrimination and feature decorrelation. arXiv preprint Xrx::2206..000 001011,,, 2021.
Makarand Tapaswi, Mare T Law, and Sanja Fidler. Video face clustering with unknown number of clusters. In Proceedings of the IEEE/CVE /CFF International Conference on Computer Vision, pp. 5027-5036, 2019.
Tsung Wei Tsai, Chongxuan Li, and Jun Zhu. Mice: Mixture of contrastive experts for unsupervised image clustering. In International Conference on Learning Representations, 2020.
Wouter Van Gansbeke, Simon Vandenhende, Stamatios Georgoulis, Marc Proesmans, and Luc Van Gool. Scan: Learning to classify images without labels. In European Conference on Computer Vision, pp. 268 285. Springer, 2020.
Pascal Vincent, Hugo Larochelle, Isabelle Lajoie, Yoshua Bengio, Pierre-Antoine Manzagol, and Léon Botton. Stacked denoising autoencoders: Learning useful representations in a deep network with local denoising criterion. Journal of machine learning research, 11(1)), 2010.
Wei Wang, Jiong Yang, Richard Muntz, et al. Sting: A statistical information grid approach to spatial data mining. In Vldb, volume 97, pp. 186-195. Citescer, 1997.
Zeya Wang, Yang Ni, Baoyu Jing, Deqing Wang, Hao Zhang, and Eric Xing. Dnb: A joint learning framework for deep bayesian nonparametric clustering. IEFF Transactions Neural Networks and Learning Systems, 2021.
Jianlong Wu, Keyu Long, Fei Wang, Chen Qian, Cheng Li, Zhouchen Lin, and Hongbin Zha. Deep compre- hensive correlation mining for image clustering. In Proceedings of the IEEE/CVF International Conference on Compuler Vision, pp. 8150 8159, 2019.
Junyuan Xie, Ross Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis. In International conference machine learning, pp. 478-487. PMLR, 2016.
Bo Yang, Xiao Fu, Nicholas Sidiropoulos, and Mingyi Hong. Towards k-meals-friendly spaces: Simultane- ous deep learning and clustering. In international conference on machine learning, pp. 3861 3870. PMLR, 2017.
Jianwei Yang, Devi Parikh, and Dhruv Batra. Joint unsupervised learning of deep representations and image clusters. In Proceedings of the IEFE conference on computer vision and pattern recognation, pp. 5147-5156. 2016.
Matthew D Zeiler, Dilip Krishnan, Graham W Taylor, and Rob Fergus. Deconvolutional networks. In 2010 IEEE Computer Society Conference on computer vision and pottern recognition, pp. IEEE, 2010.
14

---

Published in Transactions on Machine Learning Research (05/2023)
Tian Zhang, Raghu Ramakrishnan, and Miron Livny. Birch: efficient data clustering method for very large databases. ACM sigmod record, 25(2):103-114, 1996.
Junjie Zhao, Donghuan Lu, Kai Ma, Yu Zhang, and Yefeng Zheng. Deep image clustering with category-style representation. In European Conference on Computer Vision, pp. 54-70. Springer, 2020.
Tingting Zhao, Zifeng Wang, Aria Masoomi, and Jennifer G Dy. Streaming adaptive nonparametric varia- tional autoencoder. Xiv preprint arXiv:196.. 1906.03333, 2019.
Huasong Zhong, Jianlong Wu, Chong Chen, Jianqiang Huang, Minghua Deng, Liqiang Nie, Zhouchen Lin, and Xian-Sheng Hua. Graph contrastive clustering. In Proceedings of the IEEE/CVF International Conference Computer Vision, pp. 9224-9233, 2021.
A Appendix
Proof of Proposition 1.
Proof. For simplicity, we suppose cluster K is split into two sub-clusters K and K2, the optimization problem becomes:
h #
min
Σ
A(k
A
Σ
D(ki, k2),
(15)
K +
AE(K-II,,K
1|,KK
If the optimal value of problem 15 is smaller than that before split, the split phase should be applicd. Therefore, the split condition can be formulated as:
K E
Σ kkk
A
((k1,))) k2) Σ
D(K, k)
A
D(ki, (16)
+
K
kEi[K- KI
ky
K2
kE(K]
k2
We can combine the same part in equation
16 and obtain:
2A K +1
Σ D(K
D(K2,K2 D(K,K) -
D(ki,
(17)
K
K K+1
AE (ECLKKK)
Since Ka and K² are split from K, we have:
D)K =
E
D(k +
(18)
K²)
and for any k
D(K = D(k, K.) + D(K, 12).
(19)
Further, conclude the following result:
k kzz
2A
A
+2) D(K) .K3) 2 K(K +1) K K+1 [
D(ki,
(20)
k [[K
Proof of Proposition 2.
15

---

Published in Transactions on Machine Learning Research (05/2023)
Proof. Similar with the class split phase, can determine the threshold by analyzing the optimization problem:
by tk
A
min Σ
k)k,
Σ
A22)
(21)
K
(E( k2)
( -2 K1,
where Km is the merged cluster. The merge condition can be formulated as:
ka Σ
E k(k
D(k &
Σ
D(K,k)
A
Σ k2|K]
k2).
(22)
K
K
kE (E([K2],
kE[K]
Following the same strategy with equation
16 and
17
obtain:
(x²
A
2A D(k,k)
D(KT KT))
Σ
A2) S
Σ
D(K K,
(23)
K-1 K
kE(K-1.K)
Then, we also conclude as follows:
k
22
+2 11,3) K
A K(K - 1)
Σ
D(k
(24)
M[K ([K-(())) km
Proof of Lemma 3.
Proof. Suppose that there are two clusters Kt and K2 satisfy both the merge and split condition, then we have:
kitks
2X
K +2 D(K' 13) ,(K',K))
Σ
D(K1,)2),
(25)
K(K 1) ky ( 21
and
2A
A
K(K +1) K +1 +2) D(K', k3)
D(ki, k2).
(26)
which means:
k
k of kz
A
A
Σ
D(Ki, 2 D(K', K2) 2
D(ki,
(27)
2(K 1) K)
2K( K +1)
(
The inequation can be simplified as:
A kn
ks
Σ E Km)
D(ki, 2
D(k1,
2(K 1)(2 K)
2K(N K +1)
ki ((
ks to
kighhe
1
D(ki, - 2D(K2
>
D(ki, k2)
KK - 1)(A K)
K(A + K 1)
ko
(28)
(K 1)(2 K)
Σ
D(k,, 2D(K "D(K',K' ,K2)
K(A + K 11)
kokk
- 2K
Σ
22) K3)
2K(A + K +1)
k
16

---

Published in Transactions on Machine Learning Research (05/2023)
Therefore, we have:
kz
kizk22
2-2K 2K 2K + k K 11)
Σ
ke) 2 D(K', K2) Z 2K(A + K +
A
Σ
D(k1,k2)
(29)
which raises contradiction. Therefore, the split and merge condition cannot be met simultaneously.
Proof of Proposition 5.
Proof. From the proof of lemma 4, since the the number of clusters only be monotonically changed and bounded (K 2 1 and K I where m is the number of samples), the proposed algorithm can finally converge.
Moreover, we conclude that the algorithm converged when V(K* +1) V(K*) < V(K*- - 1), which means
of kg
X
K" arg min
Σ D(k,k)
k)
D(k1,
(30)
K
KE[K]
For the convergence speed, as shown in algorithm | the number of clusters can be changed up to about twice (each two classes satisfy the merge condition and merge into one class or each class satisfies the split condition and be split into two classes). Therefore, the proposed algorithm will converge at an O ()) speod, where is the number of acting the split-merge schemes.
17


Reviews:
[{"review_id": "Y2c2iWfroI", "reviewer": "Reviewer_TuEe", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths: \n\n* The plug-and-play nature of the proposed framework is interesting\n* The paper is very well aligned with classic hierarchical clustering approaches like BIRCH\n\n## Weaknesses: \n\n* Critical - Too many crucial details are missing from the paper \n  * How is the JS divergence calculated on the empirical measures? The authors briefly mention that they use binary feed-forward classifiers to measure the JS divergence. First, this strategy requires training a binary classifier to evaluate the JS divergence between **any** two empirical distributions, which raises a question about the computational efficiency of the proposed approach. Second, training such binary classifiers will only approximate the JS divergence. \n  * When it comes to splitting a cluster, the subclusters $K_1$ and $K_2$ are unknown. An optimization is required over $K_1$ and $K_2$ to maximize the JS divergence between the subclusters. Also, given that calculating the JS divergence requires training a binary classifier, it needs to be clarified how this optimization is carried out.\n  * It is unclear why the proposed schema should converge! There is no clarification regarding the convergence of the proposed framework. \n  * Is the network trained from scratch on the new $K$ after split or merge, or is it fine-tuned? \n\n* False Promise - The approach is motivated by saying that existing approaches that dynamically update $K$ are costly for deep clustering algorithms. However, the proposed approach is also very costly. In addition to requiring an initial deep clustering (baseline), the proposed algorithm iteratively updates $K$, where in each iteration, the deep clustering algorithm must be executed after the split and after the merge phases. Even not considering the computational complexity of the split and merge steps, each iteration requires running the deep clustering algorithm twice! To make matters worse, there is no guarantee that the method will converge in a few iterations. \n\n* Writing - The paper can benefit from rewriting some sentences, and fixing some typos: \n  * E.g., Page 4, Section 3.1, second line: \"becomes the dominate term\" should be \"becomes the dominant term\"\n  * E.g., Page 4, Section 3.1, last line: \"inequation 3\" should be \"inequality 3\"\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a simple split-and-merge schema for finding the correct number of clusters for any deep clustering approach that requires the number of clusters as input. At its core, the proposed method is similar to hierarchical clustering algorithms (like BIRCH) that split and merge clusters to minimize the within-cluster distance and maximize the between-cluster distances. In short, after training the deep clustering algorithm of interest with a predefined number of clusters $K'$, the authors carry out a cluster split step based on the Jensen-Shannon (JS) divergence between two possible subclusters and obtain a new $K$. Then, they retrain (or possibly fine-tune) the clustering network based on the new $K$, and enter a merge phase, where different clusters are merged to minimize the within-cluster and maximize the between-cluster distances. The process is repeated until convergence. The authors apply their plug-and-play split-and-merge algorithm to SCAN and show improvement in clustering performance compared to various baselines on CIFAR-10, CIFAR-100, STL-10, and ImageNet-10 datasets.\n\nUnfortunately, too many critical details are currently missing from the paper.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please refer to the weaknesses enumerated above. ", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Y0NyV3br3V", "reviewer": "Reviewer_r4rJ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is easy to follow. But some drawbacks and suggestions are as follows:\n\n1. The authors claim \"current number of clusters K' is smaller than the optimal value K^∗.\" in the first paragraph of section 3.1. This is one of the basic assumptions of this paper. Are there any observations or proofs to support this?\n\n2. In section 3.1, \"the optimization problem 2\" is often used but what does it refer to?\n\n3. The authors use \"plug\" to describe their contribution, but \"framework\" would be more appropriate. \"plug\" often describe a relatively independent module rather than a learning strategy.\n\n4. How to guarantee the proposed strategy (Alg. 1) is convergent. There is no theoretical proof, and this is also not obvious.\n\n\n5. In table 1, how the NMI, ACC and ARI are computed. To my knowledge, the computation requires the ground-truth label, which means the proposed method groups the data with the right class number (e.g. 10 classes for CIFAR10, 100 classes for CIFAR100). But apparently, this is not always the case. \n\n6. How to explain the hyper-parameter \\lambda, since the authors want to eliminate the widely-used hyper-parameter, i.e. class number, but introduce another one. In Table 6, we can see the performance is not stable when setting the parameter \\lambda with different values.\n\n7. In table 5, the proposed method is initialized with different K. Does it separate the data into groups with a same class number? If not, how to compare their performance. \n\n8. Another popular metric, Purity, could be considered in the experiments.\n\n9. In the tables, there are lots of \"-\". what do they mean?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a clustering strategy to group data without knowing the class number.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see Section *Strengths And Weaknesses", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "IwULYHIWZp", "reviewer": "Reviewer_zo9S", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n\nThe paper deals with a hyper-parameter selection problem in clustering. This is essentially a “model order selection” problem in the literature, and is known to be a hard problem even if the mixtures are linear. The proposed approach is intuitive, and works to a certain extent.\nThe experiments show that the algorithm does estimate K well, given different initialization. This shows the robustness to the initial guess, which is an important trait of such algorithms.\nThe method is flexible, as it can be combined with any clustering methods as an additional module.\n\nWeakness\n     \nThe theoretical support for the proposed method is relatively weak. For example, proposition 1 is used to justify the splitting criterion. But proposition 1 only states that under certain conditions the cost value of (1) will decrease. However, this seems to be an indirect measure of success as (1) is also affected by a hyper-parameter lambda. Decreasing (1) does not necessarily mean “good” clustering structure found.\n\nThere are some points that were not crystal clear. The clarity of the technical assumptions may be improved. For example, the choice of D(.) seems to be a bit casual. This work uses the JS divergence, using “symmetry and easy to calculate” as the motivation. But does this implicitly assume that the support of K^1 and K^2 are the same? There is another assumption that x are iid as distribution comparison is used as a criterion. It is unclear how the non-iid case would affect the performance.\n\nThe depth of the submission may not be satisfactory. The sample complexity is not discussed, but the JS-divergence can only be approximated by samples.\n\nAs an algorithm, the convergence issue was not discussed. Will the method ever converge, or is there a risk of diverge? There is a lack of discussion.\n\nI found that the title of the submission may not exactly reflect the contribution. The title implies that this is a ``deep plug and play’’ work, but the method actually can be combined with any clustering method. The method does not really exploit any “deep learning” structure or property. Having “deep” in the title is a little misleading.\n\nAt a higher level, the method may be problematic when combining with some clustering methods. The criterion (1) uses its own definition of clusters (e.g., maximizing intra-cluster distance while minimizing inter-class distance). This was fleshed out using a distribution “distance” metric. But plenty of clustering methods do not use the “distance” metric in (1). For example, k-means uses Euclidean distance, and subspace clustering uses angles between susbpaces. It is understandable that the D(.) function in (1) can be replaced by other divergence measures, but how they will work in practice is unclear and not supported by analysis or numerical evidence.\n\nFinally, split-and-merge using the 2-cluster clustering method (like in line 6 of algorithm 1) as a subroutine to check if a cluster needs to be split is a long-existing idea; see Chaudhuri, Debasis, B. B. Chaudhuri, and C. A. Murthy. \"A new split-and-merge clustering technique.\" Pattern Recognition Letters 13.6 (1992): 399-409. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This submission provides a clustering method that automatically adjusts the number of clusters. The method applies a clustering algorithm to the dataset, and then examines if the found clusters should be split or merged under certain criteria. The method can be combined with any existing clustering methods, and thus the title includes “plug and play”.\n\n", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- analyzing the convergence properties of the algorithm\n\n- specify the assumptions needed for the algorithm to succeed (i.e., recovering the ground truth K)\n\n- discussing (or analyzing) how the sample complexity would affect the performance\n\n- modify the title and remove \"deep clustering\"\n\n- discuss the relation between this method and existing split-and-merge methods in the literature\n\n- discuss the impact of different D(.) functions when combining with different clustering criteria\n\n- To make the claims/goals of the paper clearer. For example, \"Instead of developing an effective non-parametric method, we aim to introduce a plug-and-play module that can be easily embedded into the state-of-the-art parametric clustering method without\naffecting its performance.\" This is a little vague as it could be perceived as that the method can be embedded with many clustering methods. But the experiments were done by just combining the method with SCAN (Van Gansbeke et al., 2020). If that is the case, the method seems to be tuned for SCAN, but not \"plug and play\" for other clustering methods. In addition, it is debatable if SCAN is \"the state-of-the-art\".", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies a simple split-and-merge schema for finding the correct number of clusters for any deep clustering approach, which requires the number of clusters as input. At its core, the proposed method is similar to hierarchical clustering algorithms that split and merge clusters to minimize the within-cluster distance and maximize the between-cluster distances. In a nutshell, after training the deep clustering algorithm of interest with a predefined number of clusters, the authors carry out a cluster split step based on the Jensen-Shannon (JS) divergence between two possible subclusters and obtain a new. Then, they retrain the clustering network and enter a merge phase, where different clusters are merged to minimize the within-cluster and maximize the between-cluster distances. The authors apply their plug-and-play split-and-merge algorithm to SCAN and show improvement in clustering performance compared to various baselines on CIFAR-10, CIFAR-100, STL-10, and ImageNet-10 datasets.

The general plug-and-play idea could lead more papers to focus on the deep clustering problem, which is good for the area. Specifically, the plug-and-play nature of the proposed framework is very interesting, and the paper is very well aligned with classic hierarchical clustering approaches like BIRCH. However, there still exists some potential issues (see https://openreview.net/forum?id=6rbcq0qacA&noteId=vmXRjmIzfU) proposed by reviewer zo9S, e.g., convergence theorem (Proposition 5), which should be further revised and fixed (see https://openreview.net/forum?id=6rbcq0qacA&noteId=bI1RVoQZjE). In general, the main idea of this paper is interesting and reasonable. The authors address most of reviewers' concerns in their rebuttal. Thus, I would like to recommend accept with minor revision.
Decision: Accept (poster)