4
$\begingroup$

I have asked on StackOverflow, but they suggested me to move here for better answers. I copy paste the question.

I have decided to play a little with similarities and clustering text. I have already created the tf-idf and symmatrix matrix of similarities. Now I want to implement something for clustering into groups.

I have performed some research and found hcluster (hierarchical clustering) and k-means libraries. Which of those is better in terms of accuracy? Do you know any better way, even if there isn't a suitable library. I could write the code, if I knew the algorithm.

Also, this way the complexity is $O(n^3)$. If I would like to sacrifice a little of accuracy to win on calculating time, do you have something to suggest?

$\endgroup$
2
  • 2
    $\begingroup$ Both hcluster and k-means are decades old. You may want to try something more recent, actually designed for text. I have no idea what $O(n^2)$ you are talking about: k-means is in $O(nki)$ with $ki \ll n$, whereas common hclust implementations are $O(n^3)$. $\endgroup$ Jul 29, 2013 at 21:29
  • $\begingroup$ It was a typo. It's actually $O(n^3)$. Do you have any suggestions for other ways? Especially for text? $\endgroup$
    – Tasos
    Jul 29, 2013 at 21:36

1 Answer 1

3
$\begingroup$

Late to answer, however thought it will be useful for others.

Key information that clustering algorithm uses is the similarity by distance.

K-means:

The objective of k-means is to minimize the total sum of the squared distance of every point to its corresponding cluster centroid.

enter image description here

Implementation takes place iterative, following two steps until convergence:

Expectation (E-step): Compute P(ci | E) for each example given the model, and probabilistically re-label the examples based on these posterior probability estimates.

Maximization (M-step): Re-estimate the model parameters, , from the probabilistically re-labeled data.

Pros:

  • Partitions are independent of each other.
  • Often used as an exploratory data analysis tool.
  • In one-dimension, a good way to quantize real valued variables into k non-uniform buckets.

Limitations:

  • K-means clustering needs the number of clusters to be specified.
  • K-means is extremely sensitive to cluster center initialization.
  • Bad initialization can lead to poor convergence speed and bad overall clustering.
  • Sensitivity to noise and outliers.

Hierarchical Clustering:

Produces a set of nested clusters organized as a hierarchical tree:

  • Initially consideres every point as its own cluster.
  • Among the current clusters, determines the two clusters ci and cj that are most similar.
  • Merges it into a parent cluster i.e., replace ci and cj with a cluster ci U cj.
  • Repeat, until the whole dataset is merged to one cluster.

Pros

  • Partitions can be visualized using a tree structure (a dendrogram).
  • Hierarchical clustering doesn’t need the number of clusters to be specied.
  • If you want k groups, just cut the (k-1) longest links.

Limitations:

  • Once a decision is made to combine two clusters, it cannot be undone.
  • No objective function is directly minimized.
  • Different schemes have problems with one or more of the following:
    • Sensitivity to noise and outliers.
    • Difficulty handling different sized clusters and convex shapes.
    • Breaking large clusters.

Things to remember:

  • A good clustering is one that achieves:
    • High within cluster similarity
    • Low inter cluster similarity
    • Choice of the similarity measure is very important for clustering.
  • Measuring the similarity between quantitative elements are much easier then the text. So understanding how similarity measure work and choosing the right measure is very important to get accurate clustering result. Cosine similarity measure is most commonly used for text clustering (not necessarily).
  • You can find here, a detailed paper on comparing the efficiency of different distance measures for text documents.

enter image description here

Python Link:

There is a good comparison and examples of clustering here!

R Link:

No clear consensus on which of the two clustering technique produces better clustering.

$\endgroup$
3
  • 2
    $\begingroup$ Could you explain how this reply addresses the question which focus specifically on text mining? $\endgroup$
    – chl
    Jan 22, 2015 at 14:15
  • $\begingroup$ Thanks chl for making me realize the missing link. I have edited the answer to stress on considering right similarity measure for text clustering and also given a link towards additional research. $\endgroup$ Jan 22, 2015 at 14:55
  • $\begingroup$ Question is about k-means and hierarchical for text clustering. So I have given the comparison and info about right similarity measure for text clustering. Not sure why it has been down voted. $\endgroup$ Jan 22, 2015 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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