Группировка похожих строк

Question

Я пытаюсь проанализировать множество терминов поиска, так много, что в отдельности они мало что говорят. Тем не менее, я хотел бы сгруппировать термины, потому что я думаю, что подобные термины должны иметь схожую эффективность. Например,

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

Это надуманный пример, но, надеюсь, он объясняет, что я пытаюсь сделать. Итак, что лучший способ сделать то, что я описал? Я думал, что у nltk может быть что-то в этом роде, но я едва знаком с ним.

Благодаря

Answer 1

Вы хотите объединить эти термины, и для метрики подобия я рекомендую Dice's Coefficient на уровне символов грамм. Например, разделите строки на двухбуквенные последовательности для сравнения (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) 

По крайней мере, для этого, например, разница между баскетбол и бейсбол термины должны быть достаточных для их кластеризации в отдельные группы. Кроме того, вы можете использовать оценки подобия более непосредственно в своем коде с порогом.