A better way to cluster items

I am working on a text processer which gives out similarities between a set of strings. After weighted LCS, Levenshtein distance and double metaphone matching, I get buckets of strings such as

• Bucket for string $i \rightarrow [s, k, m]$
• Bucket for string $j \rightarrow [i, s, k]$

This effectively implies that $i,j,s,k,m$ belong to the same cluster.

One of the ways I could do this is to build a connectivity graph and cluster all the connected components.

The other way is to iteratively check for the matches.

Could somebody help me do it better.

• What is "better" ? if the only information you have is the connectivity structure, then you need graph based approaches, and spectral methods might be of use. – Suresh Venkat Mar 29 '11 at 21:20
• So i used the connectivity analysis to deal with it. Its real fast. – Stattrav Apr 13 '11 at 6:08
• @Suresh Venkat I am more interested in learning what spectral methods you were referring to. – Stattrav Apr 13 '11 at 6:08
• Look for spectral graph partitioning on google. The idea is to use the connectivity (as encoded by the Laplacian) to split the graph into pieces. – Suresh Venkat Apr 13 '11 at 7:02