http://qs321.pair.com?node_id=261046

artist has asked for the wisdom of the Perl Monks concerning the following question:

Hi

I have approximately 5000 items. I like to group similar items together. My items are 'phrases' or 'words'. So list like (perl monks yahoo monk google aperl goxgle)) could be written after grouping as (perl aperl monks monk yahoo google goxgle). Preserving the order would be good but not neccessarily if it cannot be achieved. Of course, the sorting would help to some extent but not for the ultimate results. I like to use modules like String::Approx or others effectively.

Thanks artist

Replies are listed 'Best First'.
Re: Group Similar Items
by blokhead (Monsignor) on May 27, 2003 at 16:42 UTC
    You may want to check out Text::Levenshtein, which calculates the edit distance metric (how many character changes, deletions, insertions to change one string to the other) of two strings. Calculate the edit distance between of all pairs of strings. Then pick out some string of your list and group it with ones that are within a certain distance threshold. Keep doing this until you've partitioned your original set of strings into nearby groups.

    That's a very rough way of doing it, but it may give you a starting point. There are certainly better ways to choose a group than to pick a random string and just pick all its nearby ones. That original string might be on the very edge of a group, and you'd miss the ones at the opposite end. You may want to look into using some graph algorithms to find strongly connected components within this metric.

    Also, the fact that the edit measure is a distance metric means you can probably do better than checking all pairs of strings, but you'll have to leave that optimization to a more math-savvy monk.

    blokhead

      the distance approach is great if you are considering biological sequences, but i am not sure how well it will scale if you are considering text or phrases;

      the key problem you will face is determining the right substitution/gap penalties with your distance metric.not so important with words, but important for phrases. if the text is words, determining similarity via phonemes sounds more natural.

      if you don't have an appropriate substitution/deletion penalty matrix, you could get quite dissimilar phrases clustered together.
Re: Group Similar Items
by traveler (Parson) on May 27, 2003 at 17:56 UTC
    On first thought, here is where I might start. Maybe someone who has taken an algorithms class recently might have a better idea. The overall concept is to create a hash of lists. The first item in each list is the "key". Each item in the input is compared with each key. If it is "close enough" to a key, it is added to that key's list, if not, it is installed as a new key.

    It can be made much slower and more accurate if the input item is compared with all keys and the item is placed in the list with closest key if it is close enough to any of them.

    The algorithm is not perfect and somewhat depandant on the input order. It might be "good enough" and it might be a starting point. In any case, perhaps it will get you or some other monk thinking on the right track to a better solution.

    HTH, --traveler

      I like this approach! To extend the idea even further, if the phrases are short and there is a small number of mismatch types, each item could be reduced to several canonical forms, and those could be used as keys to the hash. For example, cat could be reduced to ca?, c?t, and ?at, to cover single-letter substitutions. So cat is found in that hash as a value in three different buckets. Faced with the word hat, one of its canonical forms, ?at also keys into a bucket containing cat and gets added there.

      Other canonical forms might be obtained from Text::Soundex or Text::Metaphone where "similar" means "sound alike".

      How to then transform this hash of word affinities into a single list with no repeats is left as an exercize for the reader. :-)

      Update:

      To flesh out the soundex idea a little, here's a short example:

      use strict; use Text::Soundex; my @inwords = qw(holly perl monks yahoo monk holey google eperl holy g +oxgle kugel april); my (%hash, @outwords); push @{$hash{soundex($_)}}, $_ foreach @inwords; push @outwords, @{$hash{$_}} foreach keys %hash; print join(' ', @outwords);
      It prints:
      google goxgle kugel perl holly holey holy yahoo april monks monk eperl
      Since each word in this example has but one canonical form, it appears in the hash exactly once. So there are no repeats to untangle as with the cat/hat illustration.
Re: Group Similar Items
by dree (Monsignor) on May 27, 2003 at 21:19 UTC
    You could use Text::PhraseDistance that tries to give a measure of the degree of proximity of 2 given phrases.

    In this way you can build a set of phrases with associated different weights.
Re: Group Similar Items
by wufnik (Friar) on May 28, 2003 at 07:45 UTC
    i am going to recommend one of Ken Williams' modules again, this time AI::Categorizer, which seems purposely designed for the problem of grouping the text.

    I should add it will be much better for classifying phrases than single words, where approaches based on either phoneme matching or edit distance would be faster/better.

    in particular, this module will be able to deal with the classification of your phrases into groups.

    a number of different classifiers for your phrases can be used, including naive bayes, Support Vector Machines, and Decision Trees. in the pod for this module you will also find useful references on the problem.

    ...wufnik

    -- in the world of the mules there are no rules --