6

I have around 10000+ strings and have to identify and group all the strings which looks similar(I base the similarity on the number of common words between any two give strings). The more number of common words, more similar the strings would be. For instance:

  1. How to make another layer from an existing layer
  2. Unable to edit data on the network drive
  3. Existing layers in the desktop
  4. Assistance with network drive

In this case, the strings 1 and 3 are similar with common words Existing, Layer and 2 and 4 are similar with common words Network Drive(eliminating stop word)

The steps I'm following are:

  1. Iterate through the data set
  2. Do a row by row comparison
  3. Find the common words between the strings
  4. Form a cluster where number of common words is greater than or equal to 2(eliminating stop words)
  5. If number of common words<2, put the string in a new cluster.
  6. Assign the rows either to the existing clusters or form a new one depending upon the common words
  7. Continue until all the strings are processed

I am implementing the project in C#, and have got till step 3. However, I'm not sure how to proceed with the clustering. I have researched a lot about string clustering but could not find any solution that fits my problem. Your inputs would be highly appreciated.

  • 1
    Not sure if you saw this programmers.stackexchange.com/questions/101937/… – Brad Jun 26 '13 at 22:06
  • @Brad- I saw the link, however, I'm not sure how to start with the clustering. I was wondering if there would be some sample code for clustering strings and then I can take it further from there. – pk188 Jun 26 '13 at 23:16
  • 1
    Answered you on chat; I saw you ping me but I'm not sure if you read my answer, I explained there how your current approach might not work and which alternative approach (Spell Correction + Stemmer + LSH + Jaccard) you could try. – Tamara Wijsman Jun 27 '13 at 18:30
  • @Tom- I saw your reply, thank you for sharing this information. I will try Jaccard and LSH, and will post my findings soon! – pk188 Jun 27 '13 at 23:02
1

One technique that can be used to perform clustering on multi-dimensional numeric data is the Kohonen self-organising feature map. It's a little too involved to describe here, but should be included in any beginner's level text on machine learning.

This just leaves the problem of how to convert your data to numeric form. To do this, I'd first run an an analysis to find a reasonable number (say 100) of words that appear in many of your strings, but not too many. You're looking for words in the middle of the frequency distribution, as these carry the most useful information. You can then use the presence or absence of these words as inputs to your feature map.

-1

Similar to this question/answer and I've used the c# algorithim posted there in the past and it works like a charm here's the algorithim from the linked answer:

public class SimilarityTool
{
    public double CompareStrings(string str1, string str2)
    {
        List<string> pairs1 = WordLetterPairs(str1.ToUpper());
        List<string> pairs2 = WordLetterPairs(str2.ToUpper());

        int intersection = 0;
        int union = pairs1.Count + pairs2.Count;

        for (int i = 0; i < pairs1.Count; i++)
        {
            for (int j = 0; j < pairs2.Count; j++)
            {
                if (pairs1[i] == pairs2[j])
                {
                    intersection++;
                    pairs2.RemoveAt(j);//Must remove the match to prevent "GGGG" from appearing to match "GG" with 100% success

                    break;
                }
            }
        }

        return (2.0 * intersection) / union;
    }
  • While Stack Overflow concentrates on code, Programmers.SE focuses on the concepts. How does this work? How does it do its clustering? How does this "Form a cluster where number of common words is greater than or equal to 2(eliminating stop words)" (which is where the OP got confused)? – user40980 Aug 19 '15 at 19:33
  • 1
    Thanks for the guidance I'll keep it in mind in my future answers. – P. Roe Aug 20 '15 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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