2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ do you have any information about the data generating process? if not you can just treat this as a (multi) classification problem $\endgroup$ – oW_ Sep 22 '19 at 18:58
  • $\begingroup$ 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. $\endgroup$ – Reinstate Monica Sep 24 '19 at 14:10
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ There are no clusters in KNN. $\endgroup$ – Rodolphe LAMPE Sep 23 '19 at 6:38
  • $\begingroup$ 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 ? $\endgroup$ – Gyan Ranjan Sep 23 '19 at 6:44
1
$\begingroup$

It's classification, isn't it?

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Rodolphe LAMPE Sep 23 '19 at 6:37
  • 1
    $\begingroup$ If you have clusters, these are labels you can use for training a classifier. $\endgroup$ – Has QUIT--Anony-Mousse Sep 24 '19 at 5:50
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$
0
$\begingroup$

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)

enter image description here

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

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)

enter image description here

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

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

enter image description here

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

enter image description here

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

enter image description here

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

enter image description here

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

enter image description here

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

enter image description here

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.