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

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

1 голос
/ 14 июня 2019

Сегодня утром я боролся с проблемой в офисе.

Мне нужно найти способ сгруппировать строки из списка.Трудно объяснить, вот пример:

Допустим, у меня есть следующий список: 

['MONTREAL EDUCATION BOARD', 'Île de Montréal', 'Montréal',
       'Ville de Montréal', 'MONTREAL CITY', 'Monrtéal', 'Mont-réal',
       'Toronto', 'Toronto city', 'Tornoto', 'What is this', 'Bananasplit',
       'Banana', 'StLouis', 'St-Louis', 'Saint Louis']

Мне нужно найти способ сгруппировать эти значения вместе в зависимости от их сходства: 

[['MONTREAL EDUCATION BOARD'],
 ['Île de Montréal', 'Montréal','Ville de Montréal', 'MONTREAL CITY', 'Monrtéal', 'Mont-réal'],
 ['Toronto', 'Toronto city', 'Tornoto'],
 ['anything'],
 ['Bananasplit', 'Banana'],
 ['StLouis', 'St-Louis', 'Saint Louis']
]

Это был бы идеальный случай.Очевидно, что это может иметь (и будет) ошибки.Мне нужно сделать это с около 10 000 списков, которые содержат от 5 до 15 000 строк в каждом.Мне нужно минимизировать ошибку и получить лучшие группы, которые я могу.

Я использую слегка модифицированную версию fuzzywuzzy.Сначала я снимаю акценты и пишу с заглавной буквы все буквы для более точного расстояния Левенштейна.

Я пытался установить порог (скажем, 80), перебирать список, делать группу из каждой строки и братьиз дубликатов элементов.Очевидно, это не тот результат, который мне нужен, потому что мне нужно, чтобы каждый элемент появлялся только в одном списке (и это не так, потому что A можно связать с B, B с C, но не с A до C). 

    groups = []
    for curr in lst:
        curr_grp = []
        for item in lst:
            ratio = normalized.partial_ratio(curr, item)
            if ratio > SET_THRESHOLD:
                curr_grp.append((item, ratio))

        groups.append(curr_grp)

Я думаю , что можно найти способ найти наиболее оптимальную конфигурацию из моего вывода: 

[[('MONTREAL EDUCATION BOARD', 100),
  ('Montréal', 100), # Will probably have to use ratio() and not partial_ratio() because
  ('Monrtéal', 88),  # this can't happen, EDUCATION BOARD is NOT Montreal
  ('Mont-réal', 89)],
 [('Île de Montréal', 100),
  ('Montréal', 100),
  ('Ville de Montréal', 93),
  ('Monrtéal', 88),
  ('Mont-réal', 94)],
 [('MONTREAL EDUCATION BOARD', 100),
  ('Île de Montréal', 100),
  ('Montréal', 100),
  ('Ville de Montréal', 100),
  ('MONTREAL CITY', 100),
  ('Monrtéal', 88),
  ('Mont-réal', 88)],
 [('Île de Montréal', 93),
  ('Montréal', 100),
  ('Ville de Montréal', 100),
  ('Monrtéal', 88),
  ('Mont-réal', 94)],
 [('Montréal', 100),
  ('MONTREAL CITY', 100),
  ('Monrtéal', 88),
  ('Mont-réal', 89)],
 [('MONTREAL EDUCATION BOARD', 88),
  ('Île de Montréal', 88),
  ('Montréal', 88),
  ('Ville de Montréal', 88),
  ('MONTREAL CITY', 88),
  ('Monrtéal', 100)],
 [('MONTREAL EDUCATION BOARD', 89),
  ('Île de Montréal', 94),
  ('Montréal', 88),
  ('Ville de Montréal', 94),
  ('MONTREAL CITY', 89),
  ('Mont-réal', 100)],
 [('Toronto', 100), ('Toronto city', 100), ('Tornoto', 86)],
 [('Toronto', 100), ('Toronto city', 100), ('Tornoto', 86)],
 [('Toronto', 86), ('Toronto city', 86), ('Tornoto', 100)],
 [('What is this', 100)],
 [('Bananasplit', 100), ('Banana', 100)],
 [('Bananasplit', 100), ('Banana', 100)],
 [('StLouis', 100), ('St-Louis', 86), ('Saint Louis', 86)],
 [('StLouis', 86), ('St-Louis', 100)],
 [('StLouis', 86), ('Saint Louis', 100)]]

Можно ли найти наиболее оптимальное подмножество этогосписок, где каждый элемент появляется только в одной группе?(так с наибольшим количеством очков?) Примите во внимание, что мои списки будут НАМНОГО больше, поэтому я не могу протестировать каждую конфигурацию, потому что это займет годы.

Иначе, есть еще один более эффективный способ сделать то, чтоЯ пытаюсь сделать?

Спасибо!

1 Ответ

1 голос
/ 15 июня 2019

Вы можете использовать словарь для постепенного объединения групп только с городами, которые еще не были сгруппированы.

Обратите внимание, что у меня нет суеты, поэтому я создал калькулятор коэффициентов гетто для проверки решения.Я также удалил символы ударения, чтобы сделать это проще (моей целью было не создать хорошую функцию сравнения строк) 

from collections import Counter
stripJunk = str.maketrans("","","- ")
def getRatio(a,b):
    a = a.lower().translate(stripJunk)
    b = b.lower().translate(stripJunk)
    total  = len(a)+len(b)
    counts = (Counter(a)-Counter(b))+(Counter(b)-Counter(a))
    return 100 - 100 * sum(counts.values()) / total

Вот логика группировки (вы можете заменить мою пользовательскую функцию getRatio ()с записью от fuzzywuzzy): 

data = ['MONTREAL EDUCATION BOARD', 'Ile de Montreal', 'Montreal',
       'Ville de Montreal', 'MONTREAL CITY', 'Monrteal', 'Mont-real',
       'Toronto', 'Toronto city', 'Tornoto', 'What is this', 'Bananasplit',
       'Banana', 'StLouis', 'St Louis', 'Saint Louis']

treshold     = 75
minGroupSize = 1

from itertools import combinations

paired = { c:{c} for c in data }
for a,b in combinations(data,2):
    if getRatio(a,b) < treshold: continue
    paired[a].add(b)
    paired[b].add(a)

groups    = list()
ungrouped = set(data)
while ungrouped:
    bestGroup = {}
    for city in ungrouped:
        g = paired[city] & ungrouped
        for c in g.copy():
            g &= paired[c] 
        if len(g) > len(bestGroup):
            bestGroup = g
    if len(bestGroup) < minGroupSize : break  # to terminate grouping early change minGroupSize to 3
    ungrouped -= bestGroup
    groups.append(bestGroup)

Переменная groups - это список, который будет содержать наборы названий городов (групп).Города будут появляться только в одной группе. 

# With a treshold of 75%:
{'MONTREAL CITY', 'Montreal', 'Monrteal', 'Mont-real'}
{'St Louis', 'StLouis', 'Saint Louis'}
{'Toronto', 'Toronto city', 'Tornoto'}
{'Ville de Montreal', 'Ile de Montreal'}
{'MONTREAL EDUCATION BOARD'}
{'Bananasplit'}
{'Banana'}
{'What is this'}

При более низком пороге (или лучшей функции сравнения) вы получите меньше групп: 

# With a treshold of 65%:
{'Monrteal', 'Montreal', 'Ville de Montreal', 'MONTREAL CITY', 'Mont-real', 'Ile de Montreal'}
{'Toronto', 'Toronto city', 'Tornoto'}
{'Saint Louis', 'StLouis', 'St Louis'}
{'Banana', 'Bananasplit'}
{'What is this'}
{'MONTREAL EDUCATION BOARD'}

С точки зрения производительности это будетпроизводить результаты в разумные сроки для относительно небольших наборов данных.Группе 1600 городов понадобилось 83 секунды.Из-за природы O (N ^ 2) цикла комбинаций () это, вероятно, станет непрактичным, когда вы получите 15 000 элементов в списке.

Цикл группировки начинается с больших групп.Это занимает около половины времени обработки.Вероятно, вы могли бы сэкономить часть этого времени, остановив его, когда достигнете достаточно маленькой группы.То есть если вам не нужны базиллионы 1-2 городских групп.Я попытался остановить цикл группировки, когда размер группы становится меньше 3, а 1600 городов были обработаны за 48 секунд (таким образом, значительная экономия для моих смоделированных данных).Тем не менее, вы не сможете значительно повысить производительность при использовании реальных данных.

...