Meta-Learning to Cluster

2019·Arxiv

Abstract

Abstract

Clustering is one of the most fundamental and wide-spread techniques in exploratory data analysis. Yet, the basic approach to clustering has not really changed: a practitioner hand-picks a task-specific clustering loss to optimize and fit the given data to reveal the underlying cluster structure. Some types of losses—such as k-means, or its non-linear version: kernelized k-means (centroid based), and DBSCAN (density based)—are popular choices due to their good empirical performance on a range of applications. Although every so often the clustering output using these standard losses fails to reveal the underlying structure, and the practitioner has to custom-design their own variation. In this work we take an intrinsically different approach to clustering: rather than fitting a dataset to a specific clustering loss, we train a recurrent model that learns how to cluster. The model uses as training pairs examples of datasets (as input) and its corresponding cluster identities (as output). By providing multiple types of training datasets as inputs, our model has the ability to generalize well on unseen datasets (new clustering tasks). Our experiments reveal that by training on simple synthetically generated datasets or on existing real datasets, we can achieve better clustering performance on unseen real-world datasets when compared with standard benchmark clustering techniques. Our meta clustering model works well even for small datasets where the usual deep learning models tend to perform worse.

1 Introduction

Clustering is one of the most ubiquitous techniques in data analysis that has important applications in numerous domains that extend far beyond machine learning [Xu et al., 2003, Cai et al., 2004, Tung et al., 2010, Xu and Tian, 2015]. The main objective of clustering is to group a set of objects in such a way that objects in the same group (cluster) are more similar to each other (with respect to some domain-specific notion of similarity), than to those in other groups.

The prevailing approach to clustering is to optimize a specific objective function (usually called the cluster loss) that encodes the desired domain-specific notion of similarity to reveal the underlying group structure in data. Certain cluster losses such as k-Means and DBSCAN [Ester et al., 1996] have shown promising results in various applications, such as object recognition [Stockman, 1987] and recommendation systems [Kim and Ahn, 2008]. In modern settings, as the data we collect has become more complex, more expressive cluster losses encoded by deep network architectures have shown some success as well [Hu et al., 2017, Aljalbout et al., 2018].

A practitioner usually hand-picks a cluster loss in an ad-hoc manner; they basically choose whichever loss (either a preexisting one, or a newly designed one) that seems to give a satisfactory result. And a priori, it is unclear how this choice can be made in a principled way, or better yet completely bypass this step and directly achieve a good clustering.

In this work, we want to take a step towards this direction. Rather than optimizing for a specific customdesigned loss, we develop a model that learns how to cluster. Such “learning to learn” approach comes under the framework of meta-learning. Instead of training on a large amount of data from a single task, meta-learning systems are trained on a large number of (similar) smaller tasks and are used to make predictions on newly available (similar) tasks. Deep meta-learning systems have shown remarkable success on supervised learning [Santoro et al., 2016, Mishra et al., 2017] and reinforcement learning tasks [Mirowski et al., 2016, Wang et al., 2018].

We propose a simple yet highly effective meta-learning model to solve for clustering tasks. Our model finds the cluster structure directly without having to choose a specific cluster loss for each new clustering problem. There are two key challenges in training such a model for clustering:

(i) since clustering is fundamentally an unsupervised problem, there is a lack of availability of true cluster identities for each training task, and

(ii) cluster label for each new datapoint depends upon the labels assigned to other datapoints in the same clustering task.

We systematically address each of these issues: (i) We show that trainining on simple synthetically generated datasets or other real world labelled datasets with similar statistics (such as having the same number of dimensions and number of categories) can generalize to real previously unseen datasets. (ii) We train sequentially and use a recurrent network (using LSTMs, Hochreiter and Schmidhuber [1997]) as our clustering model. A recurrent memory model helps assign clustering labels effectively based on data points seen before.

Our experiments reveal several remarkable observations: even if we train our meta-learning model just on simple synthetically generated data, we can achieve better clustering results on some real-world problems than by using popular preexisting linear and non-linear benchmark cluster losses. In addition, our meta model trained on labelled real datasets of different distributions can also transfer its clustering ability to unseen datasets. Moreover, by effectively learning how to cluster, unlike centroid-based clustering approaches like k-means, our meta-learning model also has the ability to approximate the right number clusters in simple tasks; thereby obviating the need to pre-specify the number of clusters. To best of our knowledge, this is the first clustering model using end-to-end deep meta-learning framework.

2 Related work

Deep Learning for Clustering. Aljalbout et al. [2018] provide an overview of all major frameworks that use deep learning for clustering tasks. Broadly, deep clustering consists of two parts: feature extraction phase and clustering phase. Usually feature extraction is done through an auto-encoder [Hinton and Salakhutdinov, 2006], which serves as a new representation for the subsequent clustering phase. Hu et al. [2017] propose an alternate approach using “self-augmentation”, which encourages the new representation to map the input data close to its augmentation, hence acting as a regularizer.

Though the extracted features can be used directly by standard clustering algorithms, deep learning models usually optimize further over specific clustering losses. Yang et al. [2017], for instance, propose to optimize over the k-means loss, thus encouraging learning k-means friendly feature representations. Xie et al. [2016b] on the other hand, use a loss based on student t-distribution and can accommodate for soft clusterings. Xie et al. [2016b], along with Hu et al. [2017], further explore information-theoretic losses to achieve good clusterings.

Like many deep architectures, deep clustering models require a large amount of data to train which may not be possible for many clustering problems. This pushes the need for a model that can work well in a data-limited scenario similar to one-shot or a few-shot learning settings in the supervised meta learning and this is where meta clustering can be effective.

Meta Learning. Meta learning, often referred to as learning to learn, is closely related to one-shot or few-shot learning. It has shown promising results in supervised learning. In the standard classification case, it can greatly benefit when training data is limited [Santoro et al., 2016]. In the reinforcement setting, it benefits by training more generalized agents rather than ones that specialize on a restricted domain [Wang et al., 2017].

Standard approaches to learn a meta-learning model include defining a distribution over the structure of input data to perform inference [Lake et al., 2011, Snell et al., 2017], or to use a memory model such as long short-term memory model (LSTM, Hochreiter and Schmidhuber, 1997) [Santoro et al., 2016, Wang et al., 2018] There are several generic gradient-based learning methods developed for meta-learning, such as MAML [Finn et al., 2017] and Reptile [Nichol et al., 2018].

To best of our knowledge, only a few works focus on using meta-learning framework for doing clustering. Closely related works by Ferrari and de Castro [2012] and Ferrari and de Castro [2015] estimate which of the preexisting clustering losses works well for a new clustering task. Their approach is therefore limited to losses which the user has to provide. In contrast, we implicitly learn an appropriate loss for the new clustering task. Garg [2018] pushes the framework further, laying down the theoretical foundations for meta clustering. But like Ferrari and de Castro [2012] and Ferrari and de Castro [2015], Garg [2018] uses meta-attributes (like computing data covariance) rather than directly from the input. Moreover, it learns binary similarity functions without explicitly returning the clustering and compare outputs with a simple majority rule. Another interesting line of work by Hsu et al. [2018] uses unsupervised learning to improve upon the downstream supervised learning task. Our work on the other hand, specifically focuses on learning unsupervised clustering, and shows empirical success. Notice that both supervised and reinforcement meta-learning require some sort “guidance” from data in the form of labels (supervised) or rewards (reinforcement). This is fundamentally different from the unsupervised meta learning. By using a recurrent model and doing multiple passes through datapoints, we achieve “self-guidance” and consequently good performance.

3 Meta Learning for Clustering

3.1 Problem Setup

A meta-clustering model M maps data points to cluster labels. During meta-learning, the model is trained to be able to adapt to a set of clustering tasks . At the end of meta-training, M would produce clustering labels for new test task

In our case, each training task consists of a set of data points (a dataset) and their associated cluster labels . Hence, each ). It is worth noting that and are themselves partitioned into subsets based on cluster identities. More specifically, and , where is the number of clusters in task i. Notice that unlike the supervised learning case, we allow the number of clusters for each task to vary. By introducing this cluster-specific generalization, our clustering model has the flexibility to potentially approximate the number of clusters during test time. Since labeling for a test task is yet to be determined, the structure of the test task is different from training and consists of only a set of datapoints

The cluster labels for training can either come from synthetically generated training tasks or by using labelled data from similar application domains. In Section 4, we will present experiments on training with synthetic data, real labeled data and mixture of the two.

Another important distinction between supervised and the unsupervised case is that any permutation of the labeling does not change the cluster quality. This additional degree of freedom can potentially hinder the model optimization and the efficacy of the final prediction. We circumvent this issue by fixing a permutation during training, thereby limiting the parameter search space and accelerating the learning process (see Section 4.1 for details).

Figure 1: LSTM architecture of meta-learning for clustering.

3.2 Proposed Network Architecture and Algorithm

A Need for Memory-Based Model. Unlike the supervised case where classification label for a datapoint can be determined by its feature values alone, cluster identity for a datapoint depends solely on the identity assigned to its neighbors (previously seen data points). This necessitates using a memory based clustering model. We choose an LSTM network [Hochreiter and Schmidhuber, 1997] to capture long range dependencies as we do training and testing sequentially. Apart from storing sequential information over extended time intervals, LSTMs are also flexible enough to learn what kind of information should be passed or blocked for effective prediction (see Hochreiter and Schmidhuber, 1997 for details). LSTMs have also been shown to give good accuracies in supervised meta learning [Santoro et al., 2016]. Here we apply them for the unsupervised meta-clustering case.

At each time step t, our LSTM module takes in a datapoint x and a score vector from previous time step and outputs a new score for the current timestep. The score vector encodes the quality the predicted label assigned to the datapoint x.

In this work, we use four LSTMs stacked on top of each other. The first three layers all have 64 units with residual connections while the last layer can have number of hidden units as either (i) the number of clusters (if the desired number of clusters is known, like in the case of k-means), or (ii) the maximum number of possible clusters (if the number of clusters is unknown). See Figure 1 for more details.

Loss Function and Optimization. Our network architecture for meta-clustering optimizes for a loss function that is a combination of classification loss L(that ensures output labels match the training labels) and a local loss L(that ensures output labels for nearby datapoints match each other). Specifically,

where Φ denotes the parameters of our architecture, is a hyper-parameter controlling the trade-off between the two losses.

Learning the model parameters for the task proceeds as follows. Let be a datapoint with ground truth cluster label , and let ] be the predicted score vector (i.e. the normalized vector a) returned by our model (here K denotes the size of the output layer), and the individual components represent the predicted probability of belonging to cluster k. One can also view as a soft assignment of the datapoint to the K clusters.

Using these definitions, we define L

Note that r

N(j) denotes the nearest neighbors of jth datapoint. We chose the number of neighbors as 3 for all our experiments, which can be tuned further by cross-validation.

We train our model using Adam optimizer [Kingma and Ba, 2014]. Note that typical optimizers used for meta-learning, such as MAML [Finn et al., 2017] and Reptile [Nichol et al., 2018], are specifically geared towards optimizing for supervised meta-learning tasks, and do not perform as well in our case. This is likely due to the sequential nature of our model.

The overall training and testing (across all training and testing tasks) is performed as follows.

Observe that during each iteration in training, we randomly sample N (batchsize) training datasets from our given pool of training tasks. The datasets as well as their ground truth labels (for optimization) are fed into our LSTM network architecture sequentially. The LSTM cell states are kept across epochs. This enables the network to keep memory of previously seen data points.

During the testing phase, each test task is fed into the pre-trained network to obtain the clustering. It is important to note that datapoints in each dataset are shuffled across iterations during both the training and testing phases. This prevents potential prediction errors introduced by specific sequence orders.

3.3 The Possibility of Meta-Clustering

Kleinberg’s impossibility theorem [Kleinberg, 2002] states that clustering is impossible because there is no clustering algorithm that can simultaneously satisfy three very intuitive axioms that any clustering algorithm should follow (the so called axioms of Scale-Invariance, Richness, and Consistency). Interestingly, for meta clustering one can formulate a generalized set of axioms that are in fact consistent showing the possibility of meta-clustering in a specific framework as detailed by Garg [2018]. Since our framework is different from Garg [2018] (cf. Section 2), their result is not directly applicable. Luckily we can, however, formulate an alternate set of axioms that are more akin to our framework and achieve consistency. In this section, we will discuss how we can reframe the three axioms for meta-clustering to circumvent Kleinberg’s impossibility result.

Consider a finite set of points X and the class of all possible symmetric distance distance functions D(X) on X. A clustering algorithm A can be viewed as taking a distance function ) as an input and returning a partition—i.e., a clustering—of X. With this notation, Kleinberg’s clustering axioms for any clustering algorithm A can be stated as follows.

• Scale-Invariance. For any distance function

• Richness. For any finite X and clustering C of X, there exists a distance function ) such that A(d) = C.

• Consistency. Let C be the clustering produced by some distance function Consider any distance function ), such that for all are in the same cluster in are in different clusters in ). Then it must be the case that

Garg [2018] suggests a re-framing of these axioms for meta-clustering. Specifically, by introducing a variant of Scale-Invariance, Garg [2018] shows that there is a meta-clustering algorithm that satisfies the new Scale-Invariance axiom and whose output always satisfies Richness and Consistency. Different from their version, we consider a formulation that is more appropriate and applicable in our setting.

Suppose M is a meta-clustering algorithm as described in Section 3.1. We can view M to consist of two steps. First, M takes a distance function d on the input dataset X and outputs a clustering algorithm A (instead of a clustering), i.e. M[d] = A. Second, the clustering algorithm A, in turn, will do the clustering via d and outputs a partition C, i.e. A(d) = C. Essentially, M[d](d) = C. M is trained in the meta-training phase to adapt to clustering tasks, provided with datasets and true clustering labels, unlike Garg [2018] which returns one clustering algorithm based on training datasets and labels. In our case, the LSTM architecture does both the steps, performing clustering on input data X but also adapting to X. The adaptation happens through the change of activations and gates’ values inside the LSTM. But how the activations and gates’ values of LSTM are changed for different input data is determined by the LSTM weights which are trained during meta-training and are fixed through meta-testing. The meta version of the axioms in our setting are as follows.

• Meta-Scale-Invariance. For any

• Meta-Richness. For any finite X and clustering C of X, there exists ) such that M[d](d) = C.

• Meta-Consistency. Let C be the clustering produced by some distance function ), that is M[d](d) = C. Consider any distance function ), such that for all , if are in the same cluster in are in different clusters in Then it must be the case that

The original consistency axiom requires can shrink intracluster and expand intercluster distances. The impossibility arises from the fact that the distance distortion (shrinking and expansion) of could have been from any distance function either the original d or some other that may produce a different clustering. By introducing a level of indirection through meta-learning, we can essentially specify which distance function (d or some other ) the clustering algorithm uses, thus resolving the conflict. In fact the following holds true.

Theorem 1. There is a meta clustering algorithm that satisfies Meta-Scale-Invariant and Meta-Richness, Meta-Consistency for |X| > 2.

Proof. Similar to Kleinberg [2002], let’s consider the family of single-linkage clustering functions. Each single-linkage clustering function has a threshold . The single-linkage clustering function operates by initializing each point as its own cluster and adding edges between two points if their distance is below the end, the connected components of the output graph are the clusters.

We can construct a meta-clustering algorithm as a following two step procedure. Let 1 be a fixed constant. Now given any dataset X (such that |X| > 2).

• (Meta-step, i.e. the choosing the clustering algorithm A) Given a distance function d on |X|, we can pick a single-linkage clustering function choosing ). Observe that this step is akin to M[d], basically, (for the specified

• (Clustering-step, i.e. applying A to the dataset for clustering) Once is picked, we can run single-linkage (with threshold with distance function d. This step is akin to A(d).

We will show that the meta-clustering algorithm as described above satisfy the three meta-clustering axioms.

Meta-Scale-Invariance. Suppose M[d](d) = C, or equivalently, as defined above). By the construction of the meta clustering algorithm, ] returns a single linkage function . It is trivial to show that ), that is, the scaling gives back exactly the same clustering C.

Meta-Richness. Consider an arbitrary partition C with at least two clusters. We can construct the following distance function d such that if are in the same cluster in to verify that this is a valid distance metric. Since 1, the threshold would be strictly larger than 1. Therefore, meta-clustering can successfully recover C. If C only has one cluster, we arbitrarily select a pair of data points valid metric. There will be no edge between while the other nodes are connected. Because |X| > 2, we know there exits at least another node such that and is connected and and is connected. Therefore, there is still only one connected component and thus one cluster.

Meta-Scale-Consistency. Suppose M[d] returns a single-linkage clustering function with threshold , that is, . Now consider applying this clustering function to a different distance function defined as follows. Let C be the clustering produced by d, that is . If are in the same cluster in C then . And, if are in different clusters in C then . Observe that the single-linkage clustering function with threshold will create the same graph for d and and thus ), producing the same clusters.

4 Experiments

We evaluate the efficacy of our proposed LSTM network architecture for Meta-Clustering by performing various synthetic and real-world experiments that measures how various aspects of the input data (such as representation dimension, number of true clusters, etc.) affect the prediction quality.

We start by describing our synthetic data generation process.

Figure 2: Sample synthetic datasets generated by our procedure.

4.1 Synthetic Dataset Generation

Generating Gaussian-shaped clusters. The most basic kind of clustering are those where each cluster is generated from a multivariate Gaussian distribution with a random mean and covariance. Specifically, to generate K clusters in d dimensions, we sample the means and covariances Σdenotes the cluster id) as

orth() denotes the orthogonalization of , and parameters control the magnitude of the entries in the covariance matrix. Smaller results in overlapping clusters, and thus results in harder to distinguish clusters.

Generating curved shaped clusters by adding simple nonlinearities. Mere Gaussian shaped data generation may not capture the complex nature of some real world data. We therefore introduce simple nonlinearities to our synthetically generated random Gaussian clusters. For any point x and two arbitrary coordinates p, q, we apply the following:

We apply this transformation to points in a cluster several times (each time selecting two different coordinates). See Figure 2 for example datasets generated by this process.

Assigning the cluster identity. While we can assign labels to the randomly generated clusters with any permutation, the extra degree of freedom makes the training harder. Instead, the clusters are sorted by the first dimension of their mean vectors and the cluster ids are assigned sequentially.

4.2 Baseline Methods and Evaluation Criteria

We use several popular clustering methods as baselines to compare the quality of our proposed Meta-Clustering.

Table 1: Average Error rate of meta-clustering on synthetic dataset (100 samples).

• k-means – it is arguably the most popular clustering method; the number of clusters needs to be prespecified; can only find convex clusters.

• Kernelized k-means – it is a nonlinear extension to k-means that can potentially find arbitrary shaped clusters. We use radial basis function (rbf) kernel for all our experiments.

• Spectral Clustering – it is another very popular nonlinear extension to k-means that can potentially find arbitrary shaped clusters.

• DBSCAN – it is a density based clustering that can find arbitrary shaped clusters, and is robust to noise. The user does not need to specity the number of clusters. It is most effective on low-dimensional clustering problems.

• DEC – it is a deep learning based clustering algorithm [Xie et al., 2016a]. It employs an auto-encoder as feature extractor and uses soft assignment to calculate loss to optimize. Because auto-encoder needs to be trained for each dataset, the runtime can be long when presented with samples from multiple datasets and it is most effective when dataset is large.

The reported results use the best parameter settings for each of the baseline methods. The clustering quality is evaluated using the 0-1 loss. Since any permutation of labels should not change the clustering quality, the best permutation of the predictions also needs to be taken into account using the Kuhn-Munkres algorithm.

4.3 Experiments on Synthetic Datasets

We first evaluate our model on synthetic test datasets by training on synthetic datasets. Training and test datasets are generated the same way but drawn independently.

2-D case study. Table 1 shows the performance of our meta-clustering model when compared to the other benchmark clustering methods. The model is trained on synthetic dataset with two clusters. Since the datasets generated are arbitrary shaped clusters (and not necessarily convex), centroid based methods that operate in the input representation like k-means is not expected to work well. Remarkably even more flexible methods such as spectral clustering do not yield significant improvement over k-means either. Our meta-clustering method (second to last column in Table 1) performs the best, demonstrating the power of

Figure 3: Clustering results when varying number of clusters in the test task.

Table 2: Error rates on UKM, MNIST and IRIS datasets (trained on synthetic data)

the meta-learning framework: when trained on similar related tasks. Meta-clustering in some sense learns the right notion of cluster loss and can outperform even the most popular cluster losses for simplest of tasks.

Location and Scale Invariance. Meta clustering can also do well on datasets that are not limited to where the training data resides in the representation space. In this experiment, our data points during test were translated and scalded by a factor of 3. As shown in the last column of Table 1, meta-clustering still performs comparably. This indirectly suggests that meta-clustering does not cluster simply based on what is observed in the training data, and generalizes well. This observation is further corroborated in Section 4.4 by testing the synthetically trained model on real datasets and Section 4.5 by training and testing on real datasets of different distributions.

Adapting to the Number of Clusters. It is worth noting that our model has the ability to approximate the number of clusters in the new clustering task. Though, there is still a limit on the maximum number of clusters (determined by the output dimension of our LSTM architecture). In this experiment, our model is constrained to output up to 5 clusters. The training data consists of synthetically generated clusters with the number of clusters varying between 1 and 5. We sample more training datasets with higher number of clusters to prevent training models that are biased towards returning fewer clusters. Figure 3 shows the results on test datasets, showing the ability of our meta-clustering architecture to adapt to given dataset.

4.4 Training with Synthetic Data

We also evaluate our method on several real datasets. Our primary goal is to evaluate how our clustering algorithm performs on real datasets even when the training is done on synthetic datasets. Training configurations (number of clusters, feature dimensions, number of data points) for synthetic data will match the test case.

User Knowledge Modeling [Kahraman et al., 2013] is a dataset about the students’ knowledge on the subject of Electrical DC Machines. Each example has five attributes describing various aspects of a student’s knowledge. Students are classified into four knowledge levels: “very low”, “low”, “medium” and “high”.

During training, we randomly generate 100 synthetic datasets per epoch and train for 50 epochs. Each synthetic datasets consists of 100 data points and 2 clusters. The generation process is the same as described in Section 4.1. For test, we sample 100 points from “low” and “high” classes, and evaluate the trained model by averaging the error rates of 100 runs. The result is shown in Table 2. Notice that meta-clustering gets competitive error rates.

MNIST database [Lecun et al., 1998] of handwritten digits has 70,000 examples. We preprocess the dataset by applying PCA down to 2 dimensions. We trained the model on synthetic datasets the same way as described for UKM dataset but with 1000 data points per dataset. During test, we sample 1000 data points from two randomly selected two digits each time and the error rate shown in Table 2 is the average over 100 samples. Table 2 shows that meta clustering outperforms other standard clustering methods. For a fair comparison, the auto-encoder in DEC is re-trained for each sample because each clustering algorithm should only look at the sample given.

Iris dataset [Dheeru and Karra Taniskidou, 2017] contains three classes with a total of 150 data points and 4

Figure 4: Visualized comparison of k-means and meta-clustering on Iris dataset. Visualization made by projecting the data onto the top two principal component. Center: Iris data with ground truth labelling, Left: clustering produced by k-means, Right: clustering produced by meta-clustering. Quantitatively, error rate measure shows Meta-clustering produces significantly better quality clusters.

features. The model is trained similarly as before with 150 data points per synthetic dataset and tested on the 150 iris data points without sampling. Table 2 shows that our model performs much better than the standard benchmarks. Figure 4 shows the clustering result on this data in detail. Notice that our method (right plot) can uncover the two clusters on the right much better than k-means (left plot).

4.5 Training with Real Data

Following Garg [2018], we also train our model the on the repository of classfication datasets from openml [Vanschoren et al., 2013] database. By excluding labels, they can be viewed as clustering problems. For each experiment, we fetch all the datasets in openml repository that satisfied the desired feature dimensions and number of clusters (classes). We then randomly selected 10% of the queried datasets for test and the rest for training. To emphasize the generalization power of our model, we do not tune the hyperparamters for each experiment and instead keep the architecture same for all the experiments. We randomly sample datapoints from each dataset to form meta-training and meta-test datasets. For each experiment, every meta-training or meta-test dataset has the same number of datapoints. To avoid imbalanced clusters dominating meta-training, we choose to sample each cluster uniformly (similar to Hsu et al., 2018).

Table 3 shows the results when varying k (the number of clusters), N (the number of data points per meta dataset) and the range of feature dimensions. The feature dimension range is chosen such that the average number of datasets per feature dimension is high for effective training. We padded every dataset with zeros such that they all have the same dimension in each case. Results show that our Meta Clustering method typically has the lowest error rate.

Note that in some cases, there may not be enough datasets for training or the available datasets are not diverse enough or inherently hard to cluster. Unlike other deep clustering models, our model is only designed to learn to cluster so the performance can be limited by raw features. But as shown in the previous section, training on synthetic dataset can be helpful to clustering real data. Therefore, we augment the openml datasets with synthetic datasets for models that are under-trained by the available openml datasets, specifically, the experiments with k = 3 (28 datasets available) and k = 4 (20 datasets available). For k = 3, the newly trained model significantly out-performs other baselines. For k = 4, the error rate dropped getting closer to the best clustering algorithm in this experiment. Observe that it does not surpass every benchmark partially because the generalization ability of the model is limited by the training datasets; poorly chosen training datasets can be detrimental to meta clustering.

We also explore the case when the number of clusters is not fixed but rather chosen from a range. For methods like k-means, the choice of k can be ambiguous. While there are approaches like Elbow methods to choose k, such heuristics are hard to apply across different datasets in the openml repository. So for clustering algorithm that requires k, we use the maximum number of possible clusters. This is also a fair comparison because the output dimension of our meta model is also fixed in the same way as described in Section 3.2. Table 4 demonstrates that meta-clustering outperforms in this case as well (including the deep clustering DEC benchmark).

Table 3: Error rate on openml test datasets (100 samples). The second error rate of the Meta clustering column, if needed, comes from models trained with real datasets and synthetic datasets.

5 Discussion and Conclusion

In this paper, we present a novel deep learning algorithm for learning to cluster. Instead of directly optimizing a specific cluster loss on a given dataset [Yang et al., 2017], we propose to learn a meta-algorithm that can adapt to new clustering tasks.

Just like the success of any transfer learning problem depends on the similarity between the training and the test tasks, the quality of our meta-clustering is also expected to depend on that. Nevertheless, we show that our meta-clustering model can perform better than important clustering benchmarks when trained with simple synthetic datasets or on existing labeled datasets.

References

E. Aljalbout, V. Golkov, Y. Siddiqui, and D. Cremers. Clustering with deep learning: Taxonomy and new methods. CoRR, abs/1801.07648, 2018. URL http://arxiv.org/abs/1801.07648.

D. Cai, X. He, Z. Li, W.-Y. Ma, and J.-R. Wen. Hierarchical clustering of www image search results using visual, textual and link information. In Proceedings of the 12th annual ACM international conference on Multimedia, pages 952–959. ACM, 2004.

D. Dheeru and E. Karra Taniskidou. UCI machine learning repository, 2017. URL http://archive.ics. uci.edu/ml.

Table 4: Error rate on openml test datasets with unknown k (100 samples).

M. Ester, H. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96), Portland, Oregon, USA, pages 226–231, 1996. URL http://www.aaai.org/ Library/KDD/1996/kdd96-037.php.

D. G. Ferrari and L. N. de Castro. Clustering algorithm recommendation: A meta-learning approach. In Swarm, Evolutionary, and Memetic Computing - Third International Conference, SEMCCO 2012, Bhubaneswar, India, December 20-22, 2012. Proceedings, pages 143–150, 2012. doi: 10.1007/978-3-642-35380-2\ 18. URL https://doi.org/10.1007/978-3-642-35380-2_18.

D. G. Ferrari and L. N. de Castro. Clustering algorithm selection by meta-learning systems: A new distance- based problem characterization and ranking combination methods. Inf. Sci., 301:181–194, 2015. doi: 10.1016/j.ins.2014.12.044. URL https://doi.org/10.1016/j.ins.2014.12.044.

C. Finn, P. Abbeel, and S. Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In ICML, 2017.

V. Garg. Supervising unsupervised learning. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montr´eal, Canada., pages 4996–5006, 2018. URL http://papers.nips.cc/paper/ 7747-supervising-unsupervised-learning.

G. E. Hinton and R. R. Salakhutdinov. Reducing the dimensionality of data with neural networks. Science, 313(5786):504–507, 2006.

S. Hochreiter and J. Schmidhuber. Long short-term memory. Neural computation, 9(8):1735–1780, 1997.

K. Hsu, S. Levine, and C. Finn. Unsupervised learning via meta-learning. CoRR, abs/1810.02334, 2018.

W. Hu, T. Miyato, S. Tokui, E. Matsumoto, and M. Sugiyama. Learning discrete representations via information maximizing self-augmented training. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, pages 1558–1567, 2017. URL http://proceedings.mlr.press/v70/hu17b.html.

H. T. Kahraman, S. Sagiroglu, and I. Colak. The development of intuitive knowledge classifier and the modeling of domain dependent data. Knowledge-Based Systems, 37:283–295, Jan. 2013. ISSN 0950-7051. doi: 10.1016/j.knosys.2012.08.009. URL http://dx.doi.org/10.1016/j.knosys.2012.08.009.

K. Kim and H. Ahn. A recommender system using ga k-means clustering in an online shopping market. Expert systems with applications, 34(2):1200–1209, 2008.

D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. CoRR, abs/1412.6980, 2014.

J. M. Kleinberg. An impossibility theorem for clustering. In Advances in Neural Information Processing Systems 15 [Neural Information Processing Systems, NIPS 2002, December 9-14, 2002, Vancouver, British Columbia, Canada], pages 446–453, 2002. URL http://papers.nips.cc/paper/ 2340-an-impossibility-theorem-for-clustering.

B. M. Lake, R. Salakhutdinov, J. Gross, and J. B. Tenenbaum. One shot learning of simple visual concepts. In Proceedings of the 33th Annual Meeting of the Cognitive Science Society, CogSci 2011, Boston, Massachusetts, USA, July 20-23, 2011, 2011. URL https://mindmodeling.org/cogsci2011/papers/0601/ index.html.

Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278–2324, Nov 1998. ISSN 0018-9219. doi: 10.1109/5.726791.

P. Mirowski, R. Pascanu, F. Viola, H. Soyer, A. J. Ballard, A. Banino, M. Denil, R. Goroshin, L. Sifre, K. Kavukcuoglu, D. Kumaran, and R. Hadsell. Learning to navigate in complex environments. CoRR, abs/1611.03673, 2016. URL http://arxiv.org/abs/1611.03673.

N. Mishra, M. Rohaninejad, X. Chen, and P. Abbeel. A simple neural attentive meta-learner. 2017.

A. Nichol, J. Achiam, and J. Schulman. On first-order meta-learning algorithms. CoRR, abs/1803.02999, 2018.

A. Santoro, S. Bartunov, M. Botvinick, D. Wierstra, and T. P. Lillicrap. Meta-learning with memory- augmented neural networks. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, pages 1842–1850, 2016. URL http://jmlr. org/proceedings/papers/v48/santoro16.html.

J. Snell, K. Swersky, and R. S. Zemel. Prototypical networks for few-shot learning. NIPS, 2017.

G. Stockman. Object recognition and localization via pose clustering. Computer vision, graphics, and image processing, 40(3):361–387, 1987.

F. Tung, A. Wong, and D. A. Clausi. Enabling scalable spectral clustering for image segmentation. Pattern Recognition, 43(12):4069–4076, 2010.

J. Vanschoren, J. N. van Rijn, B. Bischl, and L. Torgo. Openml: Networked science in machine learning. SIGKDD Explorations, 15(2):49–60, 2013. doi: 10.1145/2641190.2641198. URL http://doi.acm.org/10. 1145/2641190.2641198.

J. X. Wang, Z. Kurth-Nelson, D. Tirumala, H. Soyer, J. Z. Leibo, R. Munos, C. Blundell, D. Kumaran, and M. Botvinick. Learning to reinforcement learn. CoRR, abs/1611.05763, 2017.

J. X. Wang, Z. Kurth-Nelson, D. Kumaran, D. Tirumala, H. Soyer, J. Z. Leibo, D. Hassabis, and M. M. Botvinick. Prefrontal cortex as a meta-reinforcement learning system. Nature Neuroscience, 21:1–9, 2018.

J. Xie, R. Girshick, and A. Farhadi. Unsupervised deep embedding for clustering analysis. In International conference on machine learning, pages 478–487, 2016a.

J. Xie, R. B. Girshick, and A. Farhadi. Unsupervised deep embedding for clustering analysis. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, pages 478–487, 2016b. URL http://jmlr.org/proceedings/papers/v48/xieb16.html.

D. Xu and Y. Tian. A comprehensive survey of clustering algorithms. Annals of Data Science, 2(2): 165–193, Jun 2015. ISSN 2198-5812. doi: 10.1007/s40745-015-0040-1. URL https://doi.org/10.1007/ s40745-015-0040-1.

W. Xu, X. Liu, and Y. Gong. Document clustering based on non-negative matrix factorization. In Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, pages 267–273. ACM, 2003.

B. Yang, X. Fu, N. D. Sidiropoulos, and M. Hong. Towards k-means-friendly spaces: Simultaneous deep learning and clustering. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, pages 3861–3870, 2017. URL http://proceedings. mlr.press/v70/yang17b.html.

designed for accessibility and to further open science