2
$\begingroup$

I am trying to cluster some words by affinity. Using Word2Vec I obtained vector representation of every word that I can cluster with a normal unsupervised method.

Of these words, though, I know the classification of some of them, for example I know:

Colors group ==> red, blue, yellow
Gender group ==> man, woman

UNKNOWN ==> shoes, brown, beautiful.

As the example shows, brown should be categorized as a Color, but shoes and beautiful should be different clusters.

How could I use this information to create a semi-supervised model in order to cluster every word?


While the question is generic, I actually tried to create a program in Python, I tried the scikit methods sklearn.semi_supervised.LabelSpreading and sklearn.semi_supervised.LabelSpreading.
These, though, are not what I need since they only assign the known labels to the remaining objects, meaning that I would end up only with my Colors and Gender group.

$\endgroup$
1
$\begingroup$

One strategy that seems good here is instance-level constrained clustering. These methods are semi-supervised algorithm that have "must-link" and "cannot-link" constraints between instances of known labels. So in your example, you would bind the 4 pairs (red, blue), (red, yellow), (blue, yellow), and (man, woman) as "must-link", and the 6 pairs (red, man), (red, woman), ..., (yellow, woman) as "cannot-link".

The results are similar to unsupervised clustering. For example, if you were to use DBSCAN (ignoring the labels/constraints), you would not need to specify the number of clusters/groups you're trying to achieve, and the algorithm would even find "outliers".

In fact, there is a version of DBSCAN that supports instance-level constraints, called C-DBSCAN. It is described in the work "Density-based semi-supervised clustering" by Ruiz et al (2010).

I do not know of any out-of-the-box implementations available, but I have a working version of C-DBSCAN I implemented for an experiment. However it is not documented nor is it performant/production level. You can find it at my lab's repository if you're interested (also contains the C-DenStream, which is the data streams version of it, but it does not seem to fit your problem).

| improve this answer | |
$\endgroup$
  • $\begingroup$ I found constrained clustering very interesting, though I did not find many implementations to try it $\endgroup$ – Nicolò Gasparini Aug 8 '18 at 15:39

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.