<p>I am working on a text processer which gives out similarities between a set of strings. After weighted <a href="http://en.wikipedia.org/wiki/Longest_common_subsequence_problem" rel="nofollow">LCS</a>, <a href="http://en.wikipedia.org/wiki/Levenshtein_distance" rel="nofollow">Levenshtein distance</a> and <a href="http://en.wikipedia.org/wiki/Metaphone" rel="nofollow">double metaphone matching</a>, I get buckets of strings such as </p>

<ul>
<li>Bucket for string $i \rightarrow [s, k, m]$</li>
<li>Bucket for string $j \rightarrow [i, s, k]$</li>
</ul>

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

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

<p>The other way is to iteratively check for the matches.</p>

<p>Could somebody help me do it better.</p>

CC BY-SA 2.5
2011-03-29T21:20:39.193Z
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
CC BY-SA 3.0
2011-04-13T06:08:09.553Z
So i used the connectivity analysis to deal with it. Its real fast.
Stattrav
CC BY-SA 3.0
2011-04-13T06:08:46.230Z
@Suresh Venkat I am more interested in learning what spectral methods you were referring to.
Stattrav
CC BY-SA 3.0
2011-04-13T07:02:16.030Z
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
<graph-algorithms><clustering><data-mining>
A better way to cluster items
Stattrav
# A better way to cluster items

(Asked by: username_0 on 2011-03-29)

I am working on a text processer which gives out similarities between a set of strings. After weighted [LCS](http://en.wikipedia.org/wiki/Longest_common_subsequence_problem), [Levenshtein distance](http://en.wikipedia.org/wiki/Levenshtein_distance) and [double metaphone matching](http://en.wikipedia.org/wiki/Metaphone), 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.

**Tags:** graph-algorithms, clustering, data-mining

> **Comments:**
> **username_1**: 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.  
> **username_0**: So i used the connectivity analysis to deal with it. Its real fast.  
> **username_0**: @username_1 I am more interested in learning what spectral methods you were referring to.  
> **username_1**: 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.  

---

## 0 answers

