Supervised clustering

I'm working on a clustering problem. I have a training set composed of sets of points where the clusters are known and I want to find the good clusters on a testing dataset. It's a kind of supervised clustering.

I looked for articles about supervised clustering but I didn't find a lot of informations. There is "semi-supervised clustering" which consists of using informations on couples of points (must-link or don't-link relations) but, in my task, I don't have this kind of information. There are also some kind of "metric learning supervised clustering" which uses the labelized clusters to estimate a metric that would produce the given clusters using k-means. That kind of technique could help me but there is not much articles about it and I wonder if I'm not finding the good keywords or something.

What are the techniques/algorithms to cluster data points using labelized data (training points with known clusters) ?

• do you have any information about the data generating process? if not you can just treat this as a (multi) classification problem – oW_ Sep 22 at 18:58
• How do the training and test sets relate? This question is key as you need some way to transfer information from the training set to the test set. – Reinstate Monica Sep 24 at 14:10

What you are looking for is called KNN algorithm, also knows as k-nearest neighbours. It’s a supervised algorithm where you have points and their clusters given and you use these to learn a pattern for test points.

• There are no clusters in KNN. – Rodolphe LAMPE Sep 23 at 6:38
• Yeah, KNN uses the labels which can be thought of as clusters. Since you have your points clustered, you can name these clusters as 1,2,3 and hence each point within cluster 1 will automatically get label 1. Makes sense ? – Gyan Ranjan Sep 23 at 6:44

It's classification, isn't it?

You have labeled training data. You want to label your test set accordingly. Use a classifier...

• The training data points are not labeled, I just have clusters of them. It means that I know that this set of points is differrent than an other set of points but I don't have a label for any of them. – Rodolphe LAMPE Sep 23 at 6:37
• If you have clusters, these are labels you can use for training a classifier. – Anony-Mousse Sep 24 at 5:50

KNN algorithm is a solution but it doesn't scale well. Cost of KNN is $$O(n.log(n))$$ per request if you made $$n$$ ones it become $$O(n^2.log(n))$$ and don't scale at all. It is applicable if your cluster are not too big and you don't have too many request to apply. You could imagine something faster but usually less accurate as ANN (approximate neirest neibors) or even faster but also more prone to errors $$K$$-Means/Modes/Prototypes model approach.

Principle is as follow, if you have your clusters, you can use a representant of each clusters called the prototype it can be found in various way.

On real space you could use the mean or the median as prototype. For binary space use the majority vote. For mixed space combine for example mean/media and majority vote.

You can also take randomly a point of your cluster which is the medoid approach this one has the advantage to work on any metric space. Once you have one prototype per cluster, you just have to associate your unknow point to the cluster of its neirest prototype.

Complexity with these approaches fall to $$O(c)$$ per request where $$c$$ is the number of cluster, if you don't have millions of clusters this technique will be easy to implement (depending on your metric space) and work fast.