Supervised clustering

Question

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) ?

Answer 1

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.

Answer 2

It's classification, isn't it?

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

Answer 3

To be honest, I have never heard of "semi-supervised clustering" until right now. There are quite a few clustering techniques out there. Here are 7 popular tequines for clustering. I put together some sample code for you (below). I made it as automated as possible (just copy/paste). Hopefully this will get you pointed in the right direction. Just feed your own data into the X variable (make sure it is an arry).

So: X = df['A'].to_numpy()

from sklearn.cluster import KMeans
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
import numpy as np
#%matplotlib inline
from sklearn import datasets#Iris Dataset
iris = datasets.load_iris()
X = iris.data#KMeans
km = KMeans(n_clusters=3)
km.fit(X)
km.predict(X)
labels = km.labels_#Plotting
fig = plt.figure(1, figsize=(7,7))
ax = Axes3D(fig, rect=[0, 0, 0.95, 1], elev=48, azim=134)
ax.scatter(X[:, 3], X[:, 0], X[:, 2],
          c=labels.astype(np.float), edgecolor="k", s=50)
ax.set_xlabel("Petal width")
ax.set_ylabel("Sepal length")
ax.set_zlabel("Petal length")
plt.title("K Means", fontsize=14)

########################################

from sklearn.mixture import GaussianMixture
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
import numpy as np
%matplotlib inline
from sklearn import datasets#Iris Dataset
iris = datasets.load_iris()
X = iris.data#Gaussian Mixture Model
gmm = GaussianMixture(n_components=3)
gmm.fit(X)
proba_lists = gmm.predict_proba(X)#Plotting
colored_arrays = np.matrix(proba_lists)
colored_tuples = [tuple(i.tolist()[0]) for i in colored_arrays]
fig = plt.figure(1, figsize=(7,7))
ax = Axes3D(fig, rect=[0, 0, 0.95, 1], elev=48, azim=134)
ax.scatter(X[:, 3], X[:, 0], X[:, 2],
          c=colored_tuples, edgecolor="k", s=50)
ax.set_xlabel("Petal width")
ax.set_ylabel("Sepal length")
ax.set_zlabel("Petal length")
plt.title("Gaussian Mixture Model", fontsize=14)

########################################

import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
import sklearn.cluster as cluster
import time
#%matplotlib inline
sns.set_context('poster')
sns.set_color_codes()
plot_kwds = {'alpha' : 0.25, 's' : 80, 'linewidths':0}

data = X

plt.scatter(data.T[0], data.T[1], c='b', **plot_kwds)
frame = plt.gca()
frame.axes.get_xaxis().set_visible(False)
frame.axes.get_yaxis().set_visible(False)


def plot_clusters(data, algorithm, args, kwds):
    start_time = time.time()
    labels = algorithm(*args, **kwds).fit_predict(data)
    end_time = time.time()
    palette = sns.color_palette('deep', np.unique(labels).max() + 1)
    colors = [palette[x] if x >= 0 else (0.0, 0.0, 0.0) for x in labels]
    plt.scatter(data.T[0], data.T[1], c=colors, **plot_kwds)
    frame = plt.gca()
    frame.axes.get_xaxis().set_visible(False)
    frame.axes.get_yaxis().set_visible(False)
    plt.title('Clusters found by {}'.format(str(algorithm.__name__)), fontsize=24)
    plt.text(-0.5, 0.7, 'Clustering took {:.2f} s'.format(end_time - start_time), fontsize=14)


plot_clusters(data, cluster.KMeans, (), {'n_clusters':5})

plot_clusters(data, cluster.AffinityPropagation, (), {'preference':-5.0, 'damping':0.95})

plot_clusters(data, cluster.MeanShift, (0.175,), {'cluster_all':False})

plot_clusters(data, cluster.SpectralClustering, (), {'n_clusters':6})

plot_clusters(data, cluster.AgglomerativeClustering, (), {'n_clusters':6, 'linkage':'ward'})

plot_clusters(data, cluster.DBSCAN, (), {'eps':0.025})

Answer 4

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.