5
$\begingroup$

I am trying to cluster an extremely sparse text corpus, and I know the number of clusters (my data is the title and author list of scientific publications, for which I already know the number of categories).

Each entry in my corpus has between 5 and 20 features; the whole corpus has 80000 samples and between 5000–120000 features (I can filter out some features that occur very rarely, or those that occur extremely frequently). As you can see, the data are extremely sparse.

I am trying to identify the clusters by creating a TF-IDF matrix of the data and running k means on it. The algorithm completely fails, i.e. it puts more than 99% of the data in the same cluster. I am using Python scikit-learn for both steps. Here is some sample code (on data that actually works), in case it will help someone:

    from sklearn.cluster import KMeans 
    from sklearn.feature_extraction.text import TfidfVectorizer
    vectorizer = TfidfVectorizer()
    data = ['aa ab','aa ab','ac a_b','ac a_b','bc ba', 'bc ba', 'ba bc'] 
    vectorized = vectorizer.fit_transform(data)
    km = KMeans(n_clusters=3, init='random', n_init=1, verbose=1)
    km.fit(vectorized)
    print km.labels_

    [1 1 0 0 2 2 2]

My question is: Is there a better alternative to TF-IDF followed by k means for this problem? Does it make sense to start looking for different distance metrics on my TF-IDF data (e.g. cosine similarity), or am I bound to fail due to lack of data? Thanks!

$\endgroup$
  • $\begingroup$ I recently had good results clustering a corpus of essays with hierarchical clustering using cosine similarity. $\endgroup$ – Flounderer Jun 8 '14 at 22:50
8
$\begingroup$

For text vectors, there are good known similarities - cosine, and the variations used e.g. in Lucene for text retrieval.

k-means, however, may be a bad fit. Because the means computed will not have a realistic sparsity, but will be much more dense.

Anyway, there exist some k-means variations for text, such as spherical k-means. You may want to try CLUTO, which seems to be a more popular tool for clustering text.

Hierarchical clustering is probably a good candidate, too. But it does not scale to large data sets, as the usual implementations are $O(n^3)$. For 80000 documents, this will take quite some time.

$\endgroup$
  • $\begingroup$ Thanks, I was also thinking that sparsity will be an issue with k means. However, I do not see how the Euclidian norm will be different from cosine for choosing the clusters in simple k means: All that matters is that the norm is monotonic so that I preserve the geometric relation between the mean and the other vectors, or is this too simplistic? Spherical k means sounds interesting, I will try some more with available scikit packages, then have a look at CLUTO. Sorry I can't vote you up -not reputable enough yet! $\endgroup$ – nikosd Jun 11 '14 at 18:37
  • 1
    $\begingroup$ Euclidean and cosine aren't that different. On L2 normalized data, they are effecitvely the same (which is why spherical k-means converges - k-means minimizes variance, but if variance = cosines, then you are fine). I would not expect very good results (in particular as k-means is forced partitioning and doesn't handle outliers well), but this seems to be state of the art for text clustering. $\endgroup$ – Anony-Mousse Jun 11 '14 at 21:23
  • $\begingroup$ How does CLUTO fair in comparison to ELKI? In terms of computational time and memory? $\endgroup$ – Enthusiast Feb 5 '18 at 8:28
  • 1
    $\begingroup$ CLUTO is totally outdated/dead, 2006. $\endgroup$ – Anony-Mousse Feb 5 '18 at 9:06

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.