4
$\begingroup$

I am new to data science, I have clustered some data using Scipy agglomerative clustering. how can I fit new data into the learned clusters?

dm = pdist ( dataset ,lambda u,v: mlpy.dtw_std ( pd.Series(u).dropna().values.tolist(),pd.Series(v).dropna().values.tolist(),dist_only=True ))
z = hac.linkage(dm, method='average')
cluster = hac.fcluster(z, t=100, criterion='distance')
leader = scipy.cluster.hierarchy.fcluster(z, t=100, criterion='distance')

I would like to cluster new data into the same clusters, How can I do it?

$\endgroup$
1
  • $\begingroup$ So, it is a classification problem. $\endgroup$ – OmG Jan 1 '18 at 14:49
5
$\begingroup$

The word "prediction" does not belong to any specific type of machine learning. There is nothing wrong with "predicting" new data to the cluster it belongs to; (e.g. there are many applications that place new customers into pre-discovered market segments). A conditional probability, like that used in classification, is not "stronger" than an unsupervised approach, as it rests its assumption on properly labelled classes; something that is not guaranteed.

This is why there are packages that provide a predict function to clustering algorithms. Here is an example using the flexclust package with the kcaa function. That being said, the prediction step is usually handled by a supervised classifier, so the approach would be to sit a classifier on top of your learned clusters (treating cluster assignments as "labels").

You just have to reason about your weaknesses. As stated above, the weakness in classification is the assumption that labelled data is tagged correctly, whereas the weakness in clustering is that your discovered clusters are assumed to be valid. Unsupervised approached cannot be validated the same way it is done with classification. Clustering requires a variety of cluster validity techniques along with domain experience (e.g. show campaign managers your market segments to validate customer types).

Ultimately, you are just matching an incoming vector (new data) to the cluster most similar. For example, in k-means this could be accomplished by finding the smallest distance between the incoming vector and all the centroids of your clusters. This kind of pattern matching depends on the data you are using.

This works best for clustering techniques that have well-defined cluster objects with exemplars in the center, like k-means. Using hierarchical techniques means you would need to cut the tree to obtain flat clusters, then use the "label" assignment to run a classifier on top. This comes baked with a lot of assumptions, so you need to make sure you understand your data very well, and validate any clusters with non-technical users that have deep domain experience.

POSSIBLE APPROACH If you're bent on using hierarchical clustering, then here is the general approach. Note I am not suggesting this is the best way. Every approach comes baked with a number of assumptions. You will need to work to understand your data, attempt many models, validate with stakeholders, etc.

Readers can use the tutorial by Jörn Hees to get started in hierarchical clustering if needed:

Create some example data:

from matplotlib import pyplot as plt
from scipy.cluster.hierarchy import dendrogram, linkage
import numpy as np

np.random.seed(42)  
a = np.random.multivariate_normal([10, 0], [[3, 1], [1, 4]], size=[100,])
b = np.random.multivariate_normal([0, 20], [[3, 1], [1, 4]], size=[50,])
X = np.concatenate((a, b),)

Confirm clusters exist in synthetic data:

plt.scatter(X[:,0], X[:,1])
plt.show()

enter image description here

Generate the linkage matrix using the Ward variance minimization algorithm: (This assumes your data should be be clustered to minimize the overall intra-cluster variance in euclidean space. If not, try Manhattan, cosine or hamming. You can also try different linking options).

Z = linkage(X, 'ward')

Check the Cophenetic Correlation Coefficient to assess quality of clusters:

from scipy.cluster.hierarchy import cophenet
from scipy.spatial.distance import pdist

c, coph_dists = cophenet(Z, pdist(X))

0.98001483875742679

Calculate full dendrogram:

plt.figure(figsize=(25, 10))
plt.title('Hierarchical Clustering Dendrogram')
plt.xlabel('sample index')
plt.ylabel('distance')
dendrogram(
    Z,
    leaf_rotation=90.,  # rotates the x axis labels
    leaf_font_size=8.,  # font size for the x axis labels
)
plt.show()

enter image description here

Determine the number of clusters (e.g. can be done manually by looking for any large jumps in the dendrogram...see Jörn's blog for plotting function):

enter image description here

Retrieve clusters: (using our max distance determined from reading dendrogram)

from scipy.cluster.hierarchy import fcluster

max_d = 50
clusters = fcluster(Z, max_d, criterion='distance')

Map cluster assignments back to original frame:

import pandas as pd

def add_clusters_to_frame(or_data, clusters):
    or_frame = pd.DataFrame(data=or_data)
    or_frame_labelled = pd.concat([or_frame, pd.DataFrame(clusters)], axis=1)
    return(or_frame_labelled)

df = add_clusters_to_frame(X, clusters)
df.columns = ['A', 'B', 'cluster']

df.head()

enter image description here

Build a classifier using this "labelled" data:

Here, I'll just use the original data and the assigned clusters along with a knn classifier:

np.random.seed(42)
indices = np.random.permutation(len(X))
X_train = X[indices[:-10]]
y_train = clusters[indices[:-10]]
X_test  = X[indices[-10:]]
y_test  = clusters[indices[-10:]]

# Create and fit a nearest-neighbor classifier
from sklearn.neighbors import KNeighborsClassifier
knn = KNeighborsClassifier()
knn.fit(X_train, y_train) 

res = knn.predict(X_test)
print(res)
print(y_test)

predicted labels: [2 2 1 1 2 2 1 2 2 1]

test labels: [2 2 1 1 2 2 1 2 2 1]

As with any classifier, your incoming data needs to be in the same representation as your training data. As new data arrives you run it against the predict function provided by your classifier (here we use sci-kit learn's knn.predict). This effectively assign new data to the cluster it belongs.

Ongoing cluster validation would be required in the model monitoring step of the machine learning workflow. New data can change the distribution and results of your approach. BUT, this isn't unique to unsupervised as all machine learning approaches will suffer from this (all models eventually go stale). As argued by Jörn in the reference above, manual inspection typically trumps automated approaches, so regular visual/manual inspection of the flat clusters is recommended.

$\endgroup$
6
  • $\begingroup$ I really confused. So It's possible to assign new data to a learned cluster, how can I find the smallest distance between new data and the clusters in agglomerative clustering with predefined function in Scipy? $\endgroup$ – user3806649 Jan 1 '18 at 22:26
  • $\begingroup$ If you must use hierarchical clustering, you'll need to use cut_tree to obtain a vector of cluster membership. Then you would sit a classifier like k-NN on top of this, using the "labels" learned by clustering. But hierarchical clustering doesn't give a well-defined object/cluster, like k-means, so decide if hierarchical is really the best approach. $\endgroup$ – Cybernetic Jan 1 '18 at 23:29
  • $\begingroup$ Thanks, I use criterion='distance' to forms flat clusters. I thought of finding the leader of each cluster by finding instance which has minimum overall distance from the other members of the cluster. And assigned new data to the cluster whose leader has a minimum distance from the new data. But I don't know how can I do it programatically. $\endgroup$ – user3806649 Jan 2 '18 at 10:38
  • $\begingroup$ Added an approach above. Let me know if you're still confused. $\endgroup$ – Cybernetic Jan 2 '18 at 18:44
  • $\begingroup$ Is it true if I use the leader of each cluster (instance which minimum overall distance from the other member) as train data in the phase building the classifier? also, I use predefined distance function as Scipy agglomerative clustering metric. How can I use the predefined metric for the prediction phase? $\endgroup$ – user3806649 Jan 2 '18 at 20:46
1
$\begingroup$

Clustering is not predictive.

I.e., the models do not generalize to new data.

Usually your best approach is to do a 1 nearest neighbor classification, but you could train any other classifier on your data set.

$\endgroup$
4
  • $\begingroup$ So, what the sklearn.cluster.AgglomerativeClustering.fit_predict do? $\endgroup$ – user3806649 Jan 1 '18 at 18:22
  • $\begingroup$ See the code. It calls fit. I think the whole predict API ln clustering is a huge mistake. Clustering is not classification. For example, the y is ignored without warning, and I have seen several questions here where people incorrectly used fit(col1, col2) and wondered why col2 was ignored. Big API misdesign to even call these methods fit and predict. $\endgroup$ – Has QUIT--Anony-Mousse Jan 1 '18 at 18:27
  • $\begingroup$ I have confused with this function, It first calls fit and then predicts the same input. It says in the explanation that it Compute cluster centers and predict cluster index for each sample.. $\endgroup$ – user3806649 Jan 1 '18 at 20:26
  • $\begingroup$ fit_predict for clustering is just fit, then return the labels. It does not predict. github.com/scikit-learn/scikit-learn/blob/master/sklearn/… but you can find many questions here about the problems of predicting with clustering, because clustering algorithms are not commonly designed to allow predicting. $\endgroup$ – Has QUIT--Anony-Mousse Jan 1 '18 at 21:53

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.