Python3 - Группировка похожих строк вместе - PullRequest
Новая
       7

Python3 - Группировка похожих строк вместе

3 голосов
/ 08 мая 2020

Я хочу сгруппировать строки вместе с сайта художественной литературы. Заголовки сообщений обычно имеют следующий формат: 

titles = ['Series Name: Part 1 - This is the chapter name',
    '[OC] Series Name - Part 2 - Another name with the word chapter and extra oc at the start',
    "[OC] Series Name = part 3 = punctuation could be not matching, so we can't always trust common substrings",
    '{OC} Another cool story - Part I - This is the chapter name',
    '{OC} another cool story: part II: another post title',
    '{OC} another cool story part III but the author forgot delimiters',
    "this is a one-off story, so it doesn't have any friends"]

Разделители и c не всегда присутствуют, и могут быть некоторые варианты.

Я бы начал путем нормализации строки до буквенно-цифровых c символов. 

import re
from pprint import pprint as pp

titles = []  # from above

normalized = []
for title in titles:
    title = re.sub(r'\bOC\b', '', title)
    title = re.sub(r'[^a-zA-Z0-9\']+', ' ', title)
    title = title.strip()
    normalized.append(title)

pp(normalized)

, что дает 

   ['Series Name Part 1 This is the chapter name',
 'Series Name Part 2 Another name with the word chapter and extra oc at the start',
 "Series Name part 3 punctuation could be not matching so we can't always trust common substrings",
 'Another cool story Part I This is the chapter name',
 'another cool story part II another post title',
 'another cool story part III but the author forgot delimiters',
 "this is a one off story so it doesn't have any friends"]

Результат, на который я надеюсь, будет: 

['Series Name', 
'Another cool story', 
"this is a one-off story, so it doesn't have any friends"]  # last element optional

Я знаю несколько разных способов сравнения строк ...

difflib.SequenceMatcher.ratio ()

Расстояние редактирования Левенштейна

Я также слышал о Jaro-Winkler и FuzzyWuzzy.

Но все, что действительно важно, это то, что мы можем получить число, показывающее сходство между строками.

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

Я нашел другой пост , который, кажется, сделал первую часть .. ... но тогда я не знаю, как продолжить дальше.

scipy.cluster сначала выглядело многообещающе ... но потом я был в пути.

Другая мысль заключалась в том, чтобы каким-то образом объединить itertools.combinations () с functools.reduce () с одной из вышеперечисленных метрик расстояния.

Могу ли я слишком много обдумывать? Кажется, это должно быть просто, но в моей голове это просто не имеет смысла.

Ответы [ 2 ]

3 голосов
/ 08 мая 2020

Это реализация идей, изложенных в ответе CKM: { ссылка }

Сначала удалите знаки препинания - это не важно для вашей цели - используя этот ответ: { ссылка }

Затем мы воспользуемся одним из методов, описанных здесь: https://blog.eduonix.com/artificial-intelligence/clustering-similar-sentences-together-using-machine-learning/, чтобы сгруппировать похожие предложения. 

from nltk.tokenize import RegexpTokenizer

tokenizer = RegexpTokenizer(r'\w+') # only alphanumeric characters

lol_tokenized = []
for title in titles:
    lol_tokenized.append(tokenizer.tokenize(title))

Затем получите числовое c представление ваших заголовков: 

import numpy as np 
from gensim.models import Word2Vec

m = Word2Vec(lol_tokenized,size=50,min_count=1,cbow_mean=1)  
def vectorizer(sent,m): 
    vec = [] 
    numw = 0 
    for w in sent: 
        try: 
            if numw == 0: 
                vec = m[w] 
            else: 
                vec = np.add(vec, m[w]) 
            numw += 1 
        except Exception as e: 
            print(e) 
    return np.asarray(vec) / numw 

l = []
for i in lol_tokenized:
    l.append(vectorizer(i,m))

X = np.array(l)

Ого, это было много.
Теперь вам нужно выполнить кластеризацию. 

from sklearn.cluster import KMeans

clf = KMeans(n_clusters=2,init='k-means++',n_init=100,random_state=0)
labels = clf.fit_predict(X)
print(labels)
for index, sentence in enumerate(lol_tokenized):
    print(str(labels[index]) + ":" + str(sentence))

[1 1 0 1 0 0 0]
1:['Series', 'Name', 'Part', '1', 'This', 'is', 'the', 'chapter', 'name']
1:['OC', 'Series', 'Name', 'Part', '2', 'Another', 'name', 'with', 'the', 'word', 'chapter', 'and', 'extra', 'oc', 'at', 'the', 'start']
0:['OC', 'Series', 'Name', 'part', '3', 'punctuation', 'could', 'be', 'not', 'matching', 'so', 'we', 'can', 't', 'always', 'trust', 'common', 'substrings']
1:['OC', 'Another', 'cool', 'story', 'Part', 'I', 'This', 'is', 'the', 'chapter', 'name']
0:['OC', 'another', 'cool', 'story', 'part', 'II', 'another', 'post', 'title']
0:['OC', 'another', 'cool', 'story', 'part', 'III', 'but', 'the', 'author', 'forgot', 'delimiters']
0:['this', 'is', 'a', 'one', 'off', 'story', 'so', 'it', 'doesn', 't', 'have', 'any', 'friends']

Потом можно вытащить те, у которых индекс == 1: 

for index, sentence in enumerate(lol_tokenized): 
    if labels[index] == 1: 
        print(sentence) 

['Series', 'Name', 'Part', '1', 'This', 'is', 'the', 'chapter', 'name']
['OC', 'Series', 'Name', 'Part', '2', 'Another', 'name', 'with', 'the', 'word', 'chapter', 'and', 'extra', 'oc', 'at', 'the', 'start']
['OC', 'Another', 'cool', 'story', 'Part', 'I', 'This', 'is', 'the', 'chapter', 'name']
1 голос
/ 08 мая 2020

Ваша задача попадает в так называемый semantic similarity. Я предлагаю вам поступить следующим образом:

  1. Получите отображение ваших строк через Glove / Word2ve c или популярный BERT. Это даст вам числовое c представление ваших заголовков.
  2. Затем выполните кластеризацию, начиная с k-средних scikit, а затем вы можете go для расширенных методов кластеризации.
...