Meta-k: Towards Unsupervised Prediction of Number of Clusters
Authors: Azade Farshad
Samin Hamidi
Nassir Navab
Venue:  (2021)
Keywords: Clustering
Self-supervised learning
Meta-learning

Abstract: Data clustering is a well-known unsupervised learning approach. Despite the recent advances in clustering using deep neural networks, determining the number of clusters without any information about the given dataset remains an existing problem. There have been classical approaches based on data statistics that require the manual analysis of a data scientist to calculate the probable number of clusters in a dataset. In this work, we propose a new method for unsupervised prediction of the number of clusters in a dataset given only the data without any labels. We evaluate our method extensively on randomly generated datasets using the scikit-learn package and multiple computer vision datasets and show that our method is able to determine the number of classes in a dataset effectively without any supervision.

Under review as a conference paper at ICLR 2021
META-K: TOWARDS SELF-SUPERVISED PREDICTION OF NUMBER OF CLUSTERS
Anonymous authors Paper under double-blind review
ABSTRACT
Data clustering is well-known unsupervised learning approach. Despite the re- cent advances clustering using deep neural networks, determining the number of clusters without any information about the given dataset remains an existing problem. There have been classical approaches based on data statistics that re- quire the manual analysis of data scientist calculate the probable number of clusters in a dataset. In this work, we propose a new method for unsupervised prediction of the number of clusters in a dataset given only the data without any labels. We evaluate our method extensively on randomly generated datasets using the scikit-learn package and multiple computer vision datasets and show that method is able to determine the number of classes in a dataset effectively without any supervision.
INTRODUCTION
Clustering is important task in machine learning, and it has wide range of applications (Lung et al.] (2004); Aminzadeh Chatterjee (184)): Gan et al.] (2007)). Clustering often consists of two steps: the feature extraction step and the clustering step. There have been numerous works on clustering (Xu & Tian (2015)), and among the proposed algorithmss, K-Means (Bock (2007) is renowned for its simplicity and performance. Despite its popularity, K-Means has several shorteom- ings discussed in (Ortega et al. (2009); Shibao & Keyun (2007). In particular, with an increase in the dimensionality of the input data, K-Means' performance decreases (Prabhu & Anbazhagan (011)) This phenomenon is called the curse of dimensionality (Bellman (2015)). Dimensionality reduction and feature transformation methods have been used to mínimize this effect. These meth- ods map the original data into a new feature space, in which the new data-points are easier to be separated and clustered [Min et al. (0018)). Some examples of existing data transformation meth- ods are: PCA (Wold al. (197)) kernel methods (Hofmann et al. (2008) ) and spectral methods (Ng et al. (002)). Although these methods are effective, a highly complex latent structure of data can still challenge them ((Saul et al.) 20066] Min al.] 2018)) ). Due to the recent enhancements in deep neural networks ( (Liu et al. (2017)) and because of their inherent property of non-linear transformations, these architectures have the potential to replace classical dimensionality reduction
methods.
In the research field of deep clustering, popularized by the seminal paper "Unsupervised Deep Em- bedding for Clustering Analysis" (Xie et al. (2016)), deep neural networks are adopted as the feature extractor and are combined with clustering algorithm perform the clustering task. A unique loss function is defined which updates the model. Deep clustering methods typically take k. the number of clusters, as a hyper parameter.. real-worid scenarios, where datasets are not labeled, assigning wrong value to this parameter can reduce the overall accuracy of the model. Meta-learning, framework that allows model to use information from its past tasks to learn new task quickly or with little data, has been adopted by handful of papers (Ferrari & de Castrol (2012); Ferrari & De Castro (2015); Garg Kalai (2018): Kim et al. (0019;; [Tiang & Vermal (2019)) 9)) to improve the performance of clustering tasks. Closest our work is the approach proposed by Garg & Kalai 2018) that tries to predict the number of clusters in K-Means clustering using meta-in veeta-informatin..
To solve the same issue, propose Meta-k, gradient-basee method for finding the optimal number of clusters and an attempt to have a self-supervised approach for clustering. Our work is based on the observation that network can take input points and learn parameters predict the best number

---

Under review as a conference paper at ICLR 2021
VoJ(TT)
Encoder
Decoder
N
B
FC
T
OR
z!
K-Means
s s(C)
Figure 1: This figure shows outline of method. The green and blue dashed lines show two possible inputs to the clustering. The green part shows the high dimensional input (e.g. images) feature extraction using an auto-encoder and the blue line shows the low dimensional input. The right part of the figure shows the prediction of and how we update the controller network.
of clusters, k. The predicted k, along with the points in the dataset, are the inputs to the clustering algorithm K-Means. For the clusters created, the silhouette score (Rousseeuw) (1987) calculated. Using this metric value the reward signal, controller. As a result, in the next iteration, the controller gives higher probabilities to the that causes better (closer 1) silhouette scores be calculated.
compute the policy gradient to update the
To be able to perform optimized clustering on both low- and nigh-dimensional spaces, we augment model with feature extraction module, deep auto-encoder. In this regard, work is related to the idea of learning to learn or meta-learning, a general framework to use the information that is learned in task for improving future task. FFigure shows the diagram of our model for low- and high-dimensional data. We evaluate our method in multiple scenarios on different clustering tasks using synthetic and computer vision datasets, and we show that our approach can predict the number of clusters in most settings with an insignificant error.
Our contributions are:
A novel self-supervised approach for predicting the number of clusters using policy gradi- ent methods.
Extensive evaluation synthetic scikit-learn
[Pedregosa et al. (211h) datasets and well-
known vision datasets MNIST [LeCun et al. (2010)) and Rashion-MNIST (iiao et al. (2017))
Our results show that our approach able to predict the number of clusters in most scenar- ios identical or very close to the real number of data clusters.
We plan to release the source code of this work upon its acceptance.
2 RELATED WORK
There is vast amount of unlabeled data in many scientific fields that can be used for training neural networks. Unsupervised learning makes use of these data, and clustering is one of the most important tasks in unsupervised learning. For unsupervised clustering, the classical K-means algorithm (Lloyd (1822) has been used extensively due to its simplicity and effectiveness. If the data is distributed compactly around distinctive centroids, then the K-Means algorithm works well, but in real life, such scenarios are rare. Therefore, research has focused on transforming the data into lower- dimensional space in which K- K-Means can perform successfully. our data points are small images, then PCA (Wold al. (1987) ) is commonly used for this transformation. Other methods include non- non-linear transformation such as kernel methods (Hofmann et al. (2008) and spectral methods (Ng
al. )2002)).
2

---

Under review as a conference paper at ICLR 2021
Deep learning has also been used for unsupervised clustering specifically because it can process high dimensional data effectively by learning embedding spaces (Schmidhuber (2015)). Deep clustering includes two phases: the feature extraction phase and the clustering phase. Although the extracted features can be fed directly to standard clustering al algorithms, deep learning models usually optimize further over specific clustering losses. [Xie et al. (016) use loss, based on student t-distribution and can accommodate for soft clustering. They train stacked denoising auto-encoder as their feature extraction architecture. [Caron et al. (2018) is an unsupervised training method that employs pseudo labels generated by the K-Means algorithm applied to the output of convolutional network for the task of classification. Even though (Xie et al. 2016) Caron et al.) (0188) achieve promising results, the number of clusters in K-Means and the classifier architecture remain as seper-parameters needed to be tuned.
To optimize the task of clustering, we can leverage the meta-learning framework. According to Vanschoren (20T8). "Meta-learning, or learning to learn, the science of systematically observing how different machine learning approaches perform on wide range of learning tasks, and then learning from this experience, or meta-data, to learn new tasks much faster than otherwise possi- ble." Meta- veeta-lernning is closely related one-shot or few-shot learning, and it has shown promising results in supervised learning tasks. When data is limited or quick weight optimization is a must, meta-learning can benefit standard classification and also challenges in the area of Reinforcement Learning.
To our knowledge, there only a few works that focus using a meta-learning framework for unsupervised learning tasks. Ferraai & de Castro (2012); & De Castro (2015) estimate which of the pre-existing clustering algorithms works well for new clustering task. Their approach is limited to the algorithms that the user must provide and the number of clusters in K-Means is a hyper-parametess Garg Kalai (2018) Focuses on the theoretical foundations for meta-clustering and uses antta-stsiibuts for learning the best number of clusters. The 399 datasets provided for training a binary similarity function are all labeled, and this means that during training, the number of clusters for each dataset is known. Kim et al. (2019) proposes novel meta-learner called MI.C- Net that mimics numerous clustering tasks during the training to learn an effective embedding space for new clustering tasks. In this regard, their work has resemblance to metric-based meta-learning algorithms, and learning the best number of clusters is out of their focus. In Jiang & Verma (2019), framework is introduced, which finds the cluster structure directly without having choose specific cluster loss for each clustering problem. They propose a stacked-LSTT LSTM (Hochreiter & Schmidhuber (1997) their architecture, and the number of clusters hyper-parameter of this network.
3 META-K
Our proposed method, Meta-K, is attempt to self-supervise the unsupervised clustering task by automating the process of finding the best number of clusters, k. We adopted the meta-learning framework and the policy gradient algorithm in Meta-K. Our pipeline has two phases, training and inference. During the training phase, given we have high dimensional input x, we train our feature extractor ((x) using reconstruction loss as shown in Equation 1
[(x, 2) = 1
(I)
When the auto-encoder is fully-trained, a low dimensional latent representation 2 is learned by the model. is shown in previous research that the K-Means algorithm, in particular, performs better when the inputs are of lower dimensions; therefore, we use this representation input to the clustering algorithm.
The extracted features from the encoder (z) or low dimensional input .z/ are fed to both the K-Means algorithm (with a randomly sampled value from a predefined range with Gaussian distribution) and the controller network 0(11) which has the job of predicting k. The controller network consists of multiple fully connected layers with a final layer, with fixed output length that shows the range of the k values predicted by the controller. The length of this vector is denoted by We update the parameters of (2/) using the policy gradient method for the chosen & value. In a standard reinforcement learning setting, the gradient is considered 1 when certain action is taken and it
3

---

Under review as a conference paper at ICLR 2021
is set to 0 for the other actions. In our pipeline.
the value of silhouette score s(C) for the gradients. In other words, the goal of the controller is to find the value of & which gives us the highest silhouette score. Silhouette score is metric to evaluate the quality of clusters when do not have access to the labels. [Equation 2 shows the calculation of silhouette score.
s(C)
1
b(x:) - a(x) #EUC max(a(x), b(z)}
Σ
JUC|
Where 6 is the mean distance to the points in the nearest cluster, and the mean intra-cluster distance to all the points. C' is the clustering output from K-Means and x: is each data point belonging to an assigned cluster. The output of s(C) is in the range of (-1,1) with showing the perfect clustering. During the inference phase, the inputs are fed to the controller. The number of clusters is
predicted by the network, and K-means clustering is performed using the predicted value. Figure shows the outline of our method. Over the next sections, we explain our approach in detail.
3.1 POLICY GRADIENT OPTIMIZATION
To try to map our model to the reinforcement learning (RL) framework, we can look at the batch of inputs iteration as observations O₁, the controller as the policy network π (ay) and its output as the distribution of actions E A. We need to randomly sample an action a₂ from the action space A and perform that action on the environment. Here we use the sampled value as the input k for the K-Means algorithm. K-Means gets two inputs, k and the batch of input features v/. The output the clusters (C) created by this algorithm. By calculating the silhouette score s(C), we compute our reward signal E R(a). In our problem, we think of silhouette score the reward function as it needs to be maximized. the K-Means algorithm builds clusters that are well separated and cohesive. Therefore, silhouette score is maximized. The controller (policy network) has the goal of maximizing the cumulative discounted reward R2 Ei=o **r++ with the discount factor (0, 1] in one more trajectories. In RI terminology, the cumulative reward also called return. In our setting, one trajectory can be defined as one epoch. For example, in case have a batch size of 100 and dataset with size 1000, then our trajectory has 10 steps. The cumulative reward means the sum of silhouette scores computed for each batch. Our problem can be defined as a multi-armed bandit (MAB) problem which is simplified version of Markov decision process ( (Van Otterlo & Wiering (012)). In MAB settings, there are no states, only actions and rewards. keep taking actions (clustering with K- Means on the latent images) and receive rewards (silhouette score) but the state of the environment does not change.
our controller has learned the optimum number of clusters, then
To train the policy network, we take advantage of simple form of policy gradient algorithm. Our policy is stochastic and we have no environment transitions. Also, we will take our return as a finite- horizon undiscounted return. Having these assumptions, we can compute the gradient in Equa- tion
When evaluating the performance of the controller, need to consider the value for return. If it increases, then it means our model is learning.
Environment transitions and policy can be stochastic deterministic. Assuming both are stochastic, we can formulate the probability of trajectory that has steps, given action a, and policy network as:
T-1
P(T = II ((a))((a))
(3)
1=
Then the expected return, denoted ((T) is:
J(T)= /
(4)
Since consider R(r) sCC), Equation can be written
4

---

In our case we can Under review as a conference paper at ICLR 2021
J(T) / P(F]T)s(C)) = Er~a(s(C))
(5)
And the optimization problem in RL will be:
argmaar (T(T)
(6)
where n" is the optimal policy.
RL algorithms be categorized based what they learning (the policy, the value function, the Q-function, or the environment model) and whether or not the agent has access to a model of the environment (access - model-based, no access - model-free). In the model-free group of algorithms, there is a major sub-group called policy optimization. Policy optimization methods rely directly upon optimizing parameterized policies with respect to the expected return (long-term cumulative reward) by gradient ascent.
To show how these algorithms update the policy network directly, we assume that our policy is stochastic, parameterized policy denoted by v/o and our return R(T) is finite-horizon undiscounted return. Our goal to maximize the expected return J(T+) ET [R(r)]. Therefore we must optimize the policy by gradient ascent ([quatiinn 7
0k+1 02 VV
Algorithms that optimize the policy this way are called "Policy Gradient Algorithms" and Policy Gradient Theorem is the theoretical foundation of these algorithms. This theorem makes it possible for the gradient the policy performance (TT) to be numerically computed.
To be able to derive the expectation, we need to know the formula of the probability of trajectory and a trick in calculus called the log-derivative trick. We have already shown the formula for probability of trajectory in Equation 3
The log- degivviive trick tells us that the derivative of log æ with respect to x is 1 =. use it like the following:
voP(T P(H(0)V
(8)
Taking those two above formulas in mind, then write log P()
log P(T = Σ
(log P(a.) + log (a()))
(9)
t=
We take the gradient of the above formula i.c. Vo log P(r(0). Considering that the environment has no dependence on 8, the gradients for log P(a,) are zero. Therefore, Equation becomes:
V log P(r = Ve log (a()))
(10)
What we get at the end is expectation that can be estimated by sampling. Samples are acquired by letting the agent act in the environment, according to the policy until it reaches the terminal state, repeating this over and over and collecting set of samples (episodesstrajeccoriiss) The gradient would be:
T V log (a))s
9
Σ TED
(1I)
D
Where [D] is the number of samples (trajcctories/episodee)) Using this expression we can compute the policy gradient and update the network. This expression is the simplest version of VoJ(m
5

---

In this section, we compute the error of each experiment by subtracting the predicted value of k: from the ground truth value ke and normalize by dividing by K' (E [|k Then we calculate the average of all of these етто values along the classes. Tabll 2 shows the ablation study of our Under review as a conference paper at ICLR 2021
4 EXPERIMENTS
To evaluate our method, we generate numerous datasets using the scikit-learn package with different numbers of classes ranging from 5 to 50, different numbers of samples, and different feature counts. We denote the number of features by and the length of the output vector of the controller by n_acts. This means that network predicts & values in the range of (2, n_acts). In the experiments of subsection 4.2] n. acts or the actions vector has a length of 50 all experiments. We investigated variation of method, where we backpropagate the gradients learned by the controller to the encoder network. However, this didn't 't give us any improvement. We aim to investigate this problem further.
4.1 IMPLEMENTATION DETAILS
The different proposed architectures for our controller are shown in Table 1 In all experiments we Adam optimizer for the controller with learning rate 0.01, 31 0.9, B2 0.999. For the scikit-learn experiments, we train the model for 15 epochs, with E (10, 20, 30), n_acts = 50. The generated dataset is randomly split into two parts of 0.9, 0.1 respectively for the train and test splits. For the experiments on MNIST and FMNIST FaashonnMNISST we train the controller for 100 epochs on the training set with n acts 20, d 10. The auto-encoder architecture used for the feature extraction is similar to the one from Xie et al. (2016) (d 500fc 500fc 2000fc 10) with d being the input dimensions and 10 the size of latent dimension z. The autoencoder network trained with Adam optimizer and the learning rate of le 2.
Table 1: Controller Architecture. The depth of the model increases from top bottom. Activation function Tanh is not added for the brevity. applied to all the layers but the output layer. d the input feature dimension and naacts is the length of the actions vector (range of possible k's).
Controller
Architecture
MLP1
d-100fc-n acts 1-100f-100fcc acts
MLP2
MLP3
d-100fe-100fc- 10t00off--0ff--aacctt
4.2 ABLATION STUDY
method using different settings and with the mentioned error metric. The full results of this table are available in the Appendix. We increase the number of samples and the number of features in the dataset, and we see that with an increase in both of these parameters the model's performance increases. The lowest error value is achieved with MLP2 model, 10,000 samples of data, and 30 features. In all of the experiments of this section, n. acas is equal to 50.
Table 2: Results on the scikit-learn datasets generated with make. blobs function Here we show the average differences error for datasets of 5 to 50 classes.
# of Samples
# of Features (d)
MLP1
MLP2
MLP3
1000
10
0.2166
0.2283
0.2166
1000
20
0.2579
0.2226
0.2129
1000
30
0.2676
0.1639
0.1934
10000
10
0.1465
0.1508
0.1353
10000
20
0.1935
0.1234
0.1266
10000
30
0.1758
0.1216
0.1380

---

Under review as a conference paper at ICLR 2021
4.3 COMPARISON WITH PREVIOUS WORKS
To compare our approach with previous work, we evaluate our method, the classical silhouette score baseline and Leeta--nsupervise--Leamm dataset. For the silhouette score baseline, we calculate the silhouette score for 20 k values ranging from to 21 with step size and find the & which gives us the highest silhouette score. For method, we train a binary classification model (Multivariate linear
from Garg & Kalai (2018) on the same synthetic
the Meta- Sesupervised-Leaneee regression with lasso) on a setting similar to the one mentioned the original paper (instead 339 training datasets, we train the model on 75 classification datasets downloaded from OpenMI. and evaluate on the scikit-learn datasets. The datasets downloaded from the OpenML website have at most 10,000 samples, 500 features, and 10 classes, and no missing data. We apply data cleaning on each of them to make sure they include no NaN and no iinf values. The Meta-Unsupervised- Learning method learns mapping from the silhouette score to the average random index and tries to predict the & that would maximize the average random index. Based on the experiments in the ablation study we chose the model with
30, acls 20 and MLP2 controller. We show in Table 3) that our method is able to predict almost perfectly. Although the baseline approach achieves similar better results, is not feasible to this method when the range of possible k's is broad.
Table 3: Comparison to previous works. Experiment settings: # of Samples=10,000, dataset=blobs
Ground truth
Meta-k
Garg Kalai
(0188)
Baseline (Silhouette score)
2
3
3
3
4
4
3
5
5
2
6
3
7
7
10
7
8
6
10
9
10
10
10
10
10
As it can be seen in Table 4 sionality.
Meta-K achieves higher performance in datasets with higher dimen-
Table 4: Comparison to previous works on MNIST FMNIST datasets.
Dataset
Ground truth
Meta-k
Garg & Kalai 20188
Bascline (Silhouette score)
MNIST
10
10
10
FMNIST
10
8
9
7
We show different clustering evaluation metric FMNIST experiments, the metrics (silhouette score, normalized mutual info, and rand index) reach their maximum at k = 9, k 7, 12, which is sub-optimal.
Figure It can be seen that in the MNIST and
http://www.opemml.og

---

Under review as a conference paper at ICLR 2021
0.-
Baseline
sil all-score
0.
Baseline Meta-K
mutual-info
andom-index
Metrics
0.
04-
andom-index
0.3
25
5.0
75
10.0
12.5
15.0
17.5
20.0
MNIST
FMIST
Figure 2:
Results on MNIST & Fashion-MNIS: datasets. The green square shows the predicted value by Meta-K and the red circle shows the maximum value on the specific metric.
4.4 POLICY GRADIENT OPTIMIZATION
Figure shows the return function of the controller training MNIST and FMNIST datasets. The return plot is an indication how well the model is trained using the policy gradient optimization.
02100
0.2075
0.24
02050
0.22
0.2025
return
0.20
0.2000
0.9755
0214
W
01925
80
300
20
80
100
spochs
MNIST
FMIST
Figure 3: The graphs cumulative return for MNIST & FMNIST datasets
5 CONCLUSION
In this paper, we proposed self-supervised approach find the optimal number of clusters for any dataset in the K-Means algorithm. We showed in our experiments that our method is able to predict the number of clusters effectively without any direct supervision. Even though our method is able to predict the number of clusters in most scenarios with distinctive features, it would be challenging the input features are compact and not separable. Another limitation of our work that it is dependent on the silhouette score, and the method would perform poorly if silhouette score doesn't achieve a good clustering evaluation. However our method is not limited to silhouette score and any other clustering evaluation metric can be used well. Another point is that method dependent on the feature extraction network and if the encoder network is not trained properly, the controller training would also be challenging. We plan improve approach by using other metrics than silhouette score, adaptive layers, and Gaussian Mixture Models (GMMs) to have an end-to-end pipeline for fully automated clustering.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Fred Aminzadeh and Shankar Chatterjee. Applications of clustering in exploration seismology. Geoexploration, 23(1):147-159, 1984.
Richard E Bellman. Adaptive control processes: a guided tour, volume 2045, Princeton university
press, 2015.
Mlans-Hrrmam Bock. Clustering methods: a history of k-means algorithms. In Selected contribu- tions in data analysis and classification, pp. 161-172. Springer, 2007.
Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for unsu- pervised learning of visual features. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 132-149, 2018.
Daniel G Ferrari and Leandro Nunes de Castro. Clustering algorithm recommendation: meta- learning approach. In International Conference on Swarm, Evolutionary, and Memetic Comput- ing, pp. 143-150. Springer, 2012.
Daniel Gomes Ferrari and Leandro Nunes De Castro. Clustering algorithm selection by meta- learning systems: A new distance-based problem characterization and ranking combination meth- ods. Information Sciences, 301:181-194, 2015.
Guojun Gan, Chaoqun Ma, and Jianhong Wu. Data clustering: theory, algorithms, and applications. SIAM, 2007.
Vikas Garg and Adam T Kalai. Supervising unsupervised learning. In Advances in Neural Informa- fion Processing Systems, pp. 4991-5001, 2018.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
Thomas Hofmann, Bernhard Schölkopf, and Alexander J Smola. Kernel methods in machine learn- ing. The annals of statistics, pp. 1171-1220, 2008
Yibo Jiang and Nakul Verma. Meta-learning to cluster. arXiv preprint arXiv: 1910.. 14134, 2019.
Han-Ul Kim, Yeong Jun Koh, and Chang-Su Kim. Meta learning for unsupervised clustering. In BMVC, pp. 249, 2019.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://yann. www.unnneeeun.ccm www.....o//ex////iiiii. 2. 2010.
Weibo Liu, Zidong Wang, Xiaohui Liu, Nianyin Zeng, Yurong Liu, and Fuad E Alsaadi. A survey of deep neural network architectures and their applications. Neurocomputing, 234:11-26, 2017.
Stuart Lloyd. Least squares quantization in pem. IEEE transactions on information theory, 28(2): 129-137, 1982.
Chung-Horng Lung, Marzia Zaman, and Amit Nandi. Applications of clustering techniques to software partitioning, recovery and restructuring. Journal of Systems and Software, 73(2):227- 244, 2004.
Erxue Min, Xifeng Guo, Qiang Liu, Gen Zhang, Jianjing Cui, and Jun Long. A survey of clustering with deep learning: From the perspective of network architecture. IEEE Access, 6:39501-39514, 2018.
Andrew Y Ng. Michael I Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. In Advances in neural information processing systems, pp. 849-856, 2002.
Joaquín Pérez Ortega, Ma Del. Roco Boone Rojas, and Mara J Somodevilla. Research issues k- means algorithm: An experimental trial using matlab. In CEUR workshop proceedings: semantic web and technologies, pp. 83-96, 2009.

---

Under review as a conference paper at ICLR 2021
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, Vanderplas, A. Passos, D. Couraaeeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
Prabhu and N Anbazhagan. Improving the performance of k-means clustering for high dimen- sional data set. International journal computer science and engineering, 3(6)2331722222, 2011.
Peter Rousseeuw. Silhouettes: graphical aid to the interpretation and validation of cluster analy- sis. Journal of computational and applied mathematics, 20:53-65. 65, 1987.
Lawrence K Saul, Kilian Q Weinberger, Fei Sha, Jihun Ham, and Daniel D Lee. Spectral methods for dimensionality reduction. Semi-supervised learning, 3, 2006.
Jürgen Schmidhuber. Deep learning in neural networks: An overview. Neural nefworks, 61:85-117, 2015.
Sun Shibao and Qin Keyun. Research on modified k-means data cluster algorithm. Engineering, 33(13):200-200 201, 2007.
Computer
Martijn Van Otterlo and Marco Wiering. Reinforcement learning and markov decision processes. In Reinforcement Learning, pp. 3-42. Springer, 2012.
Joaquin Vanschoren. Meta-learning: survey. arXiv preprint arXiv:1810.033545 2018.
Svante Wold, Kim Esbensen, and Paul Geladi. Principal component analysis. Chemometrics and intelligent laboratory systems, 2(1-3):37-52, 1987.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmark- ing machine learning algorithms. CoRR, hts//7008.07747, 2017. URL httt:://aaxxi..coo org/
/bs//708.. 07747
Junyuan Xie, Ross Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis. In International conference on machine learning, pp. 478 487, 2016.
Dongkuan Xu and Yingjie Tian. A comprehensive survey of clustering algorithms. Annals of Data Science, 162, 2015.
A
APPENDIX
Tables 5
10 show the ouptut of our method in different configurations.
Table 5: Experimentation results on the scikit-learn datasets created with make blobs function. Vari- able were to: Samples=1000, Features=10
# Classes
MLPI
MLP2
MLP3
10
6
20
21
22
23
25
24
23
30
34
24
27
35
34
34
35
40
34
34
35
45
34
34
34
50
35
mean diff 0.216635
0.228302
0.216611
10

---

Under review as a conference paper at ICLR 2021
Table 6: Experimentation results on the scikit-learn datasets created with make blobs function. Vari- able were set to: # Samples=1000, Features=20
# Classes
MLPI
MLP2
MLP3
2
10
15
15
25
13
14
25
33
22
22
33
35
34
34
34
34
34
34
45
34
34
34
50
34
35
34
mean diff
0.257968
0.222635
0.212968
Table 7: Experimentation results the scikit-learn datasets created with make function. Vari- able were set to: #Samples=1000, #Features=30
Classes
MLPI
MLP2
MLP3
10
13
12
15
25
17
14
20
24
17
21
25
22
23
24
35
35
34
34
31
45
34
34
35
mean diff 0.267635
0.163968
0. 0.193484
As expected, by increasing the size of the datasets, model's predictions became accurate. However, even with a dataset of size 1000, our model's performance was acceptable when classes were of size 35. A change the number of features (space dimensionality) did not make visible difference here.

---

Under review as a conference paper at ICLR 2021
Table Experimentation results on the scikit-learn datasets created with make blobs function. Vari- able were set to: #Samples=10,000, # #Feature==10
# Classes
MLPI
MLP2
MLP3
5
12
15
16
14
12
18
19
21
25
19
23
22
30
22
25
26
35
34
27
32
40
34
27
36
45
39
31
34
50
36
41
34
mean diff
0. 0.146524
0. 0.150802
0.135349
Table 9: Experimentation results the scikit-learn datasets created with make_blobs function. Vari- able were set to: 10000l # #eaturre==20
Classes
MLP1
MLP2
MLP3
10
6
15
16
14
16
20
16
19
19
20
20
23
30
23
26
30
35
33
29
33
33
45
39
37
37
mean diff 0.193548
0.123421
0. 0.126659
Table 10: Experimentation results on the scikit-learn datasets created with make blobs function. Variable were set to: #Samples=10, 000, #Features=00
# Classes
MLP1
MLP2
MLP3
10
15
16
14
14
20
18
20
17
25
23
20
30
31
21
26
40
33
37
36
45
33
37
35
50
33
37
41
mean diff
0.175881
0.121659
0. 1.30799
12


Reviews:
[{"review_id": "QhuIBTyFt14", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The reviewed paper presents a completely unsupervised framework Meta-K for predicting the number of clusters. The approach advocated in the paper comprises two main parts: autoencoder for feature extraction and multilayer perceptron (MLP) for predicting the number of clusters. Autoencoder is used if necessary to decrease the dimensionality of the input data. The MLP is trained using policy gradient optimization schema to predict the best (according to silhouette score) number of clusters k in the given dataset. Overall, the authors show that their approach achieves near-optimum results on both a number of synthetic datasets as well as on two well-known computer vision datasets: MNIST and FMNIST.\n\nStrong points:\n* Overall, the paper is well written. The reading flow is smooth and clear without major disturbances. Alike text, figures (especially Figure 1), greatly facilitates the understanding of the paper.  \n* The review of the related literature seems to be very thorough and lists most of the relevant papers in the field. This section helps to put the current work into context and explain the limitations of approaches proposed by past research.\n\nWeak points as well as reasons for the score:\n* The main problem with the paper seems to be the apparent discrepancy between the performance and complexity of the proposed approach (Meta-k), and the baseline method (silhouette score). While both methods are completely unsupervised, the former is a complex composite pipeline, which includes two neural networks, one of which is trained using a reinforcement learning framework, the latter is a simple formula that can be calculated for as many clusters as necessary in a relatively short time. Both methods, according to the authors, perform on par, with the baseline being marginally better on synthetic data. Moreover, according to the paper, the Meta-k framework is trained to find the best number of clusters by maximizing the silhouette score in the first place. Unfortunately, the authors largely omitted a question of why their approach should be preferred over the baseline. Only once, when commenting on results of the comparison with baseline, the authors noted: \"although the baseline approach achieves similar or better results, it is not feasible to use this method when the range of possible k's is broad\", not disclosing details as to what exactly about a broad range of k's makes the baseline method infeasible, and why Meta-k must be preferred in such circumstances. Overall, the benefit of using a more complex method, such as Meta-k should be clearly stated in the paper and also extensively experimentally verified.\n\n* The lack of experimentation is the second most important concern and also the reason for the current score. Meta-k has been used on several datasets, including a number of synthetic datasets generated using sklearn package and also well-known MNIST and FMNIST. While experiments on synthetic data is a great way to confirm the initial hypothesis about the model, superior performance on real-world data is what can be of interest to the community. Although, MNIST and FMNIST are good starting points, a lot more datasets exist where the number of clusters (i.e. classes) is known: e.g. CIFAR-10, CIFAR-100, ImageNet, etc. \nThe same can be said about the competitors, as currently only one approach (except baseline) is compared to Meta-k. \n\n* Also, it is not made clear to the readers why policy gradient optimization was used for training the controller network, rather than for example common SGD with custom loss based on silhouette score. The RL training in such circumstances and without proper explanations seems to be an excessive measure.\n\n* The paper can be better structured. Section 3, might have been called \"Methods\", where the authors could have described not only their proposed solution but also the competitor approache(s) that they decided to compare with. It might be a good idea to move some part of the policy gradient optimization discussion to supplementary materials, leaving more room for experiments and results. Section \"Experiments\" might have been split into \"Experiments\" and \"Results\", with \"Experiments\" focusing on performed experiments and their setup, while \"Results\" remaining more focused on obtained outcomes and relevant interpretation.\n\n* Large parts of the introduction are overlapping or repeated in related work, it is not necessary to discuss relevant literature in the introduction, this part should be moved to related work completely.  \n\n* Over a number of occasions (in the abstract, introduction, and related work) the authors point out a close relationship between their approach and meta-learning or 'learning to learn' concept, hence the name of the approach (Meta-k). However, nowhere in the paper, the authors seem to clarify which part of their method performs meta-learning. While it might be understood that the authors refer to the fact that their approach trains the controller network using the unsupervised signal from the silhouette score. It is however might be a good idea to make this connection explicit.\n\nMinor comments:\n\n* Training curves for the policy gradient optimization presented in Section 4.4 are left with no interpretation, and to the reader it remains unclear why they were presented in the final section in the first place.\n\n* Caption of Figure 1 should ideally also explain what x, x', z, and other variables mean.\n\n* The third item on the list of contributions, interprets experimental results and can hardly be considered as a contribution of the paper.\n\n* Some of the terms related to reinforcement learning, such as environment transitions or finite-horizon undiscounted return must be explained before use.\n\n* Figure 2, could have been made more clear by adding vertical lines that would correspond to the true value of the number of clusters.     \n\n* All acronyms, such as MLP should be defined before being used.", "extra_scores": {}, "extra_text": {}}, {"review_id": "90ti6wK9urs", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper uses policy gradients in a bandit setting to learn the optimal number of clusters, k,  in k-means clustering based on the silhouette score. Finding k that leads to the highest silhouette score is a more specific problem that what the paper title promises. The approach is well-described and supported by experiments on simulated and real-world data.\nPhrasing the task at hand as hyper-parameter optimization problem, it could be tackled with a variety of well known tools, e.g. Gaussian Process based HPO, grid search, random sampling, etc. The authors need to compare the policy gradient method to these existing approaches.\n\nDetailed comments:\n- k values for competitors are not chosen properly\n- clearly written and presented\n- is the generation of synthetic data noise-free?\n- what is the y-axis in Fig.2 ?\n- \"the phenomenon is called the curse of dimensionality\" -> maybe better: \"the underlying phenomenon\"\n- eq. (6): argmax should be formatted as \\text{argmax).\n- Please check spacing and parentheses around citations.\n- \"our approach can predict the number of clusters in most settings with an insignificant error.\" -> \"insignificant\" is vacuous, here.\n- eq. 8 is not correct\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "2-QYQvPIsD", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a method to determine the number of clusters k to use with k-means. The method uses a of policy gradient inspired method without states to predict the number of clusters to use.\n\nThe idea of the paper and the presented results are promising and indicate that the idea has merit. However, there are several concerns with the paper as it stands. The underlying assumption of the paper appears to be that there is a single correct value of clusters is correct and that the used metric is capable of reliably telling good from bad clustering solutions apart. \n\nAnother aspect that is entirely ignored in the discussion and description of the method is that the training of the policy is performed in batches. This means that unless the the data in each batch is well distributed over all classes present in the data the metric would seem to be different for different batches leading to an optimization problem with a moving target. From the text it is not clear to me how this challenge is addressed by the proposed method. In practice it is impossible to guarantee either balancedness or stratification of the data presented to an unsupervised algorithm so it would seem unreasonable to require this. This is a crucial challenge for the proposed method which is sadly not addressed at all.\n\nFrom a related work point of view the paper focuses only on k-means and ignores other clustering methods which determine the number of clusters on their own, e.g. Affinity Propagation or LDA. While k-means and spectral clustering are widely used it would be good to include and compare to other methods that already are capable of determining the number of clusters directly from data. Furthermore, the paper does not speak to or compare with the well established methods to determine k for k-means such as the BIC or AIC.\n\nAnother aspect that the experiments don't really make clear is what the advantage of the proposed method is compared to simply increasing k and using the proposed metric for each value and picking the best k as was done for the baseline method. Obviously there is a cost involved in running k-means repeatedly but training the policy is not free either and guaranteeing convergence of a deep network to a reasonable solution would seem more challenging than just computing the metric value repeatedly. A discussion of this would be greatly appreciated.\n\nThe description of the method is at times a bit hard to follow. This is partly due to the paper intermixing description of the method and background information. An example of this is 3.1 where RL without with some variation on MDP is introduced intermingled with the actual setup used for the proposed method. It would have been easier to read if first the entire MDP and bandit setting was presented before describing how this is used in the proposed method. Certain aspects also never become clear. It appears that the network outputs a high-dimensional feature vector which is used to determine k. Figure 1 makes this output appear to be a scalar when the text makes it sound like a vector or distribution. Overall this adds to the challenge that as it stands it would be hard to implement the proposed method, the general idea is conveyed but many of the nuanced details remain unclear. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers were unanimous that this submission is not ready for publication at ICLR. Concerns were raised about clarity of the exposition, as well as lack of sufficient experiments comparing to related work.
Decision: Reject