Группировка похожих строк - PullRequest
Новая
       6

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

3 голосов
/ 25 декабря 2011

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

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

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

1 Ответ

7 голосов
/ 26 декабря 2011

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

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

...