類似した文字列をグループ化

Question

私は検索用語の束を分析しようとしています。つまり、同様の用語が同様の有効性を持つはずだと思うので、用語をグループ化したいと思います。例えば、

Term    Group 
NBA Basketball  1 
Basketball NBA  1 
Basketball   1 
Baseball   2 

それは不自然な例ですが、うまくいけば、それは私がやろうとしているかを説明します。だから、私が説明したことをするための最善の方法は何ですか？私はnltkがそれらの行に沿って何かを持っているかもしれないと思ったが、私はほとんどそれに慣れていない。

おかげ

Answer 1

あなたはこれらの用語をクラスタ化するだろう、との類似性メトリックのために私は、文字グラムレベルでDice's Coefficientをお勧めします。たとえば、文字列を比較する2文字のシーケンスに分割します（term1 = "NB"、 "BA"、 "A"、 "B"、 "Ba" ...）。

nltkはダイスをnltk.metrics.association.BigramAssocMeasures.dice()として提供しているようですが、調整が可能な方法で実装するのは簡単です。単語レベルではなく文字でこれらの文字列を比較する方法は次のとおりです。

import sys, operator 

def tokenize(s, glen): 
    g2 = set() 
    for i in xrange(len(s)-(glen-1)): 
    g2.add(s[i:i+glen]) 
    return g2 

def dice_grams(g1, g2): return (2.0*len(g1 & g2))/(len(g1)+len(g2)) 

def dice(n, s1, s2): return dice_grams(tokenize(s1, n), tokenize(s2, n)) 

def main(): 
    GRAM_LEN = 4 
    scores = {} 
    for i in xrange(1,len(sys.argv)): 
    for j in xrange(i+1, len(sys.argv)): 
     s1 = sys.argv[i] 
     s2 = sys.argv[j] 
     score = dice(GRAM_LEN, s1, s2) 
     scores[s1+":"+s2] = score 
    for item in sorted(scores.iteritems(), key=operator.itemgetter(1)): 
    print item 

このプログラムは、以下の類似度スコアが生成され、あなたの文字列で実行されます。

./dice.py "NBA Basketball" "Basketball NBA" "Basketball" "Baseball" 

('NBA Basketball:Baseball', 0.125) 
('Basketball NBA:Baseball', 0.125) 
('Basketball:Baseball', 0.16666666666666666) 
('NBA Basketball:Basketball NBA', 0.63636363636363635) 
('NBA Basketball:Basketball', 0.77777777777777779) 
('Basketball NBA:Basketball', 0.77777777777777779) 

少なくとも、この例では、バスケットボールと野球間のマージン用語があるべきそれらを別々のグループにクラスタリングするのに十分です。あるいは、コード内の類似度スコアをしきい値で直接使用することもできます。