3
$\begingroup$

I have the following case.

Say I have a set of 100 celebrities and I form 4 clusters using k-means. Lets assume that these 4 clusters are music, sports, politics, movies.

Now say if I want to include 2 new data, will clustering work? If so how will the data be included to appropriate clusters... I mean do I have to start clustering from the scratch with 102(100 + 2 new) celebrities or can the 2 new ones alone be included to already existing clusters.

$\endgroup$
  • 1
    $\begingroup$ Probably this is duplicate question but I won't check. Short answer: Make a classifier where you treat the labels you assigned during clustering as classes. When new points appear, use the classifier you trained using the data you originally clustered, to predict the class the new data have (ie. the cluster they are in). At some-point though you should redo this clustering-classification procedure, the clustering will most probably evolve after you accumulate enough new data so the original class/cluster member will be obsolete. $\endgroup$ – usεr11852 Jan 29 '17 at 0:57
  • 1
    $\begingroup$ BTW, I think a title change to something like: "How to assign new data to an existing clustering" will be more appropriate. The current title is a bit misleading as to what you want to achieve. $\endgroup$ – usεr11852 Jan 29 '17 at 1:04
  • 1
    $\begingroup$ If you want to determine which existing cluster new points belong to, you can find which centroid they're closest to, which is how K-means defines cluster membership. If you want to update the existing clusters, you can run K-means again, but initialize the centroids with their current values. $\endgroup$ – user20160 Jan 29 '17 at 3:27
  • $\begingroup$ @usεr11852 I'm curious about the reasoning behind training a classifier to learn the mapping onto clusters. Could you elaborate on why you'd do this? I can see why in the case of clustering algorithms that don't provide a straightforward mapping. Because k-means assigns points to the nearest centroid (i.e. Voronoi partition on input space), why not just use that mapping? Would be glad to hear your thoughts. $\endgroup$ – user20160 Jan 29 '17 at 3:42
  • $\begingroup$ Thank you... will this method of using unsupervised learning be better for this kind of scenario or would you suggest using classification instead. Coz if there are say 1000 celebrities being clustered and if we add 2 or 3 new data...won't running the k-means from the beginning cause performance issues.... Thanks $\endgroup$ – vidhya9 Jan 29 '17 at 8:17
6
$\begingroup$

Assigning new points to a clustering algorithm is always a bit perplexing because the results of a clustering algorithm are imperfect; they represent a snapshot of a (hopefully good) segmentation of the current data. How good they generalise to new data and what is the actual definition of good are open questions. Maybe we derive that clustering based on some cluster stability approach, maybe we derived it using some information criterion, maybe we use some heuristic like the GAP statistic or the Davies-Bouldin index; they are many ways. Nevertheless despite the ambiguity of a good clustering, all is not lost as soon as we have clusters, we have classes.

Given a particular clustering segmentation, we can train a robust classifier where we treat the labels we previously assigned during clustering as classes. In that way we can account more intuitively for the non-robustness of the clustering labels. Let me stress, that this will not be perfect exactly because our initial data were not perfect but it will allow us to account naturally for a certain degree of uncertainty. In addition as we expect the clustering we have to reflect "some structure" it is a cheap and straightforward way to encapsulate that structure. Following this rationale, when new points appear, we can use the classifier we trained using the data originally clustered, to predict the classes of the new data have (ie. the cluster they are in). Not only that, but we will be able to explain, to some degree, why we picked that cluster based on the intuition gained from the classifier.

As mentioned in the comments, at some point though we should redo this clustering-classification procedure because the clustering will most probably evolve after we accumulate enough new data. This "evolution" will be first noticed on points that lay close to the border of two clusters. To that extent, a single new point might "pull" the centre of a cluster away from that border-point enough to lead into a change of cluster membership, ie. render our original cluster/class assignment obsolete. When we should retrain is again not well defined; I would suggest as soon as we have computational time or we believe that the underlying structure of our data should have changed substantially (ie. we have concept-drift).

$\endgroup$
0
$\begingroup$

I guess just 2 points is not gonna mess it so badly, but for more than 10% (to say a number) it might be better to recalculate the centroids (just an opinion)

def Labs( dataset,centroids ):    
l = []
for i in range(len(dataset)):
    m = []
    for j in range(n):        
        p = np.linalg.norm(dataset[(i),:]-centroids[(j),:])
        m.append(p)
    po = np.argmin(m)
    l.append(po)
return pd.DataFrame(np.array(l) + 1,columns =['Lab'])
$\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.