# Clustering text with python

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?

• 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)$. Jul 29, 2013 at 21:29
• It was a typo. It's actually $O(n^3)$. Do you have any suggestions for other ways? Especially for text? Jul 29, 2013 at 21:36

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.

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.
• 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.