Clustering words into groups

Question

This is a Homework question. I have a huge document full of words. My challenge is to classify these words into different groups/clusters that adequately represent the words. My strategy to deal with it is using the K-Means algorithm, which as you know takes the following steps.

1. Generate k random means for the entire group
2. Create K clusters by associating each word with the nearest mean
3. Compute centroid of each cluster, which becomes the new mean
4. Repeat Step 2 and Step 3 until a certain benchmark/convergence has been reached.

Theoretically, I kind of get it, but not quite. I think at each step, I have questions that correspond to it, these are:

1. How do I decide on k random means, technically I could say 5, but that may not necessarily be a good random number. So is this k purely a random number or is it actually driven by heuristics such as size of the dataset, number of words involved etc

2. How do you associate each word with the nearest mean? Theoretically I can conclude that each word is associated by its distance to the nearest mean, hence if there are 3 means, any word that belongs to a specific cluster is dependent on which mean it has the shortest distance to. However, how is this actually computed? Between two words "group", "textword" and assume a mean word "pencil", how do I create a similarity matrix.

3. How do you calculate the centroid?

4. When you repeat step 2 and step 3, you are assuming each previous cluster as a new data set?

Lots of questions, and I am obviously not clear. If there are any resources that I can read from, it would be great. Wikipedia did not suffice :(

Answer 1

As you don't know exact number of clusters - I'd suggest you to use a kind of hierarchical clustering:

1. Imagine that all your words just a points in non-euclidean space. Use Levenshtein distance to calculate distance between words (it works great, in case, if you want to detect clusters of lexicographically similar words)
   
2. Build minimum spanning tree which contains all of your words
   
3. Remove links, which have length greater than some threshold
   
4. Linked groups of words are clusters of similar words
   

Here is small illustration:

P.S. you can find many papers in web, where described clustering based on building of minimal spanning tree

P.P.S. If you want to detect clusters of semantically similar words, you need some algorithms of automatic thesaurus construction