Нечеткая группа, группировка похожих слов

этот вопрос задается здесь раньше

Что такое хорошая стратегия группировки похожих слов?

но нет четкого ответа на вопрос о том, как «группировать» предметы. Решение на основе difflib – это в основном поиск, для данного элемента, difflib может вернуть наиболее похожее слово из списка. Но как это можно использовать для группировки?

Я хотел бы уменьшить

['ape', 'appel', 'apple', 'peach', 'puppy'] 

в

 ['ape', 'appel', 'peach', 'puppy'] 

или

 ['ape', 'apple', 'peach', 'puppy'] 

Одна идея, которую я пробовал, – для каждого элемента – перебирать список, если get_close_matches возвращает более одного совпадения, используйте его, если не сохранить слово как есть. Это отчасти сработало, но оно может предложить яблоко для аппликации, а затем для яблока, эти слова просто переключают места, и ничего не изменится.

Я был бы признателен за любые указатели, имена библиотек и т. Д.

Примечание. Также с точки зрения производительности у нас есть список из 300 000 элементов, а get_close_matches выглядит немного медленнее. Кто-нибудь знает о решении на базе C / ++?

Благодаря,

Примечание. Дальнейшее исследование показало, что kmedoid является правильным алгоритмом (а также иерархической кластеризацией), поскольку kmedoid не требует «центров», он берет / использует точки данных сами по себе как центры (эти точки называются медоидами, отсюда и название). В случае группировки слов медоид будет представительным элементом этой группы / кластера.

5 Solutions collect form web for “Нечеткая группа, группировка похожих слов”

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

Возможные способы:

  • Выберите первое встреченное слово.
  • Выберите первое лексикографическое слово.
  • Выведите шаблон для всех слов.
  • Выберите уникальный индекс.
  • Используйте soundex как шаблон.

Однако группировка слов может быть сложной. Если А похож на В, а В подобен С, А и С не обязательно похожи друг на друга. Если B является представителем, то как A, так и C могут быть включены в группу. Но если A или C является представителем, другой не может быть включен.


Переход по первому варианту (первое встреченное слово):

 class Seeder: def __init__(self): self.seeds = set() self.cache = dict() def get_seed(self, word): LIMIT = 2 seed = self.cache.get(word,None) if seed is not None: return seed for seed in self.seeds: if self.distance(seed, word) <= LIMIT: self.cache[word] = seed return seed self.seeds.add(word) self.cache[word] = word return word def distance(self, s1, s2): l1 = len(s1) l2 = len(s2) matrix = [range(zz,zz + l1 + 1) for zz in xrange(l2 + 1)] for zz in xrange(0,l2): for sz in xrange(0,l1): if s1[sz] == s2[zz]: matrix[zz+1][sz+1] = min(matrix[zz+1][sz] + 1, matrix[zz][sz+1] + 1, matrix[zz][sz]) else: matrix[zz+1][sz+1] = min(matrix[zz+1][sz] + 1, matrix[zz][sz+1] + 1, matrix[zz][sz] + 1) return matrix[l2][l1] import itertools def group_similar(words): seeder = Seeder() words = sorted(words, key=seeder.get_seed) groups = itertools.groupby(words, key=seeder.get_seed) return [list(v) for k,v in groups] 

Пример:

 import pprint print pprint.pprint(group_similar([ 'the', 'be', 'to', 'of', 'and', 'a', 'in', 'that', 'have', 'I', 'it', 'for', 'not', 'on', 'with', 'he', 'as', 'you', 'do', 'at', 'this', 'but', 'his', 'by', 'from', 'they', 'we', 'say', 'her', 'she', 'or', 'an', 'will', 'my', 'one', 'all', 'would', 'there', 'their', 'what', 'so', 'up', 'out', 'if', 'about', 'who', 'get', 'which', 'go', 'me', 'when', 'make', 'can', 'like', 'time', 'no', 'just', 'him', 'know', 'take', 'people', 'into', 'year', 'your', 'good', 'some', 'could', 'them', 'see', 'other', 'than', 'then', 'now', 'look', 'only', 'come', 'its', 'over', 'think', 'also', 'back', 'after', 'use', 'two', 'how', 'our', 'work', 'first', 'well', 'way', 'even', 'new', 'want', 'because', 'any', 'these', 'give', 'day', 'most', 'us' ]), width=120) 

Вывод:

 [['after'], ['also'], ['and', 'a', 'in', 'on', 'as', 'at', 'an', 'one', 'all', 'can', 'no', 'want', 'any'], ['back'], ['because'], ['but', 'about', 'get', 'just'], ['first'], ['from'], ['good', 'look'], ['have', 'make', 'give'], ['his', 'her', 'if', 'him', 'its', 'how', 'us'], ['into'], ['know', 'new'], ['like', 'time', 'take'], ['most'], ['of', 'I', 'it', 'for', 'not', 'he', 'you', 'do', 'by', 'we', 'or', 'my', 'so', 'up', 'out', 'go', 'me', 'now'], ['only'], ['over', 'our', 'even'], ['people'], ['say', 'she', 'way', 'day'], ['some', 'see', 'come'], ['the', 'be', 'to', 'that', 'this', 'they', 'there', 'their', 'them', 'other', 'then', 'use', 'two', 'these'], ['think'], ['well'], ['what', 'who', 'when', 'than'], ['with', 'will', 'which'], ['work'], ['would', 'could'], ['year', 'your']] 

Вы должны решить в словах закрытых матчей, какие слова вы хотите использовать. Можно получить первый элемент из списка, возвращаемого get_close_matches, или просто использовать случайную функцию в этом списке и получить один элемент из закрытых совпадений.

Для этого должно быть какое-то правило.

 In [19]: import difflib In [20]: a = ['ape', 'appel', 'apple', 'peach', 'puppy'] In [21]: a = ['appel', 'apple', 'peach', 'puppy'] In [22]: b = difflib.get_close_matches('ape',a) In [23]: b Out[23]: ['apple', 'appel'] In [24]: import random In [25]: c = random.choice(b) In [26]: c Out[26]: 'apple' In [27]: 

Теперь удалите c из исходного списка, thats it … Для c ++ вы можете использовать Levenshtein_distance

Вот еще одна версия, использующая алгоритм распространения Affinity.

 import numpy as np import scipy.linalg as lin import Levenshtein as leven import matplotlib.pyplot as plt from sklearn.cluster import KMeans from sklearn.cluster import AffinityPropagation import itertools words = np.array( ['the', 'be', 'to', 'of', 'and', 'a', 'in', 'that', 'have', 'I', 'it', 'for', 'not', 'on', 'with', 'he', 'as', 'you', 'do', 'at', 'this', 'but', 'his', 'by', 'from', 'they', 'we', 'say', 'her', 'she', 'or', 'an', 'will', 'my', 'one', 'all', 'would', 'there', 'their', 'what', 'so', 'up', 'out', 'if', 'about', 'who', 'get', 'which', 'go', 'me', 'when', 'make', 'can', 'like', 'time', 'no', 'just', 'him', 'know', 'take', 'people', 'into', 'year', 'your', 'good', 'some', 'could', 'them', 'see', 'other', 'than', 'then', 'now', 'look', 'only', 'come', 'its', 'over', 'think', 'also', 'back', 'after', 'use', 'two', 'how', 'our', 'work', 'first', 'well', 'way', 'even', 'new', 'want', 'because', 'any', 'these', 'give', 'day', 'most', 'us']) print "calculating distances..." (dim,) = words.shape f = lambda (x,y): -leven.distance(x,y) res=np.fromiter(itertools.imap(f, itertools.product(words, words)), dtype=np.uint8) A = np.reshape(res,(dim,dim)) af = AffinityPropagation().fit(A) cluster_centers_indices = af.cluster_centers_indices_ labels = af.labels_ unique_labels = set(labels) for i in unique_labels: print words[labels==i] 

Расстояния должны были быть преобразованы в сходства, я сделал это, взяв отрицательное расстояние. Выход

 ['to' 'you' 'do' 'by' 'so' 'who' 'go' 'into' 'also' 'two'] ['it' 'with' 'at' 'if' 'get' 'its' 'first'] ['of' 'for' 'from' 'or' 'your' 'look' 'after' 'work'] ['the' 'be' 'have' 'I' 'he' 'we' 'her' 'she' 'me' 'give'] ['this' 'his' 'which' 'him'] ['and' 'a' 'in' 'an' 'my' 'all' 'can' 'any'] ['on' 'one' 'good' 'some' 'see' 'only' 'come' 'over'] ['would' 'could'] ['but' 'out' 'about' 'our' 'most'] ['make' 'like' 'time' 'take' 'back'] ['that' 'they' 'there' 'their' 'when' 'them' 'other' 'than' 'then' 'think' 'even' 'these'] ['not' 'no' 'know' 'now' 'how' 'new'] ['will' 'people' 'year' 'well'] ['say' 'what' 'way' 'want' 'day'] ['because'] ['as' 'up' 'just' 'use' 'us'] 

Другим методом может быть использование матричной факторизации с использованием SVD. Сначала мы создаем матрицу расстояний слов, для 100 слов это будет 100 х 100 матриц, представляющих расстояние от каждого слова до всех других слов. Затем SVD запускается на этой матрице, u в результате u, s, v можно рассматривать как членскую силу для каждого кластера.

Код

 import numpy as np import scipy.linalg as lin import Levenshtein as leven import matplotlib.pyplot as plt from sklearn.cluster import KMeans import itertools words = np.array( ['the', 'be', 'to', 'of', 'and', 'a', 'in', 'that', 'have', 'I', 'it', 'for', 'not', 'on', 'with', 'he', 'as', 'you', 'do', 'at', 'this', 'but', 'his', 'by', 'from', 'they', 'we', 'say', 'her', 'she', 'or', 'an', 'will', 'my', 'one', 'all', 'would', 'there', 'their', 'what', 'so', 'up', 'out', 'if', 'about', 'who', 'get', 'which', 'go', 'me', 'when', 'make', 'can', 'like', 'time', 'no', 'just', 'him', 'know', 'take', 'people', 'into', 'year', 'your', 'good', 'some', 'could', 'them', 'see', 'other', 'than', 'then', 'now', 'look', 'only', 'come', 'its', 'over', 'think', 'also', 'back', 'after', 'use', 'two', 'how', 'our', 'work', 'first', 'well', 'way', 'even', 'new', 'want', 'because', 'any', 'these', 'give', 'day', 'most', 'us']) print "calculating distances..." (dim,) = words.shape f = lambda (x,y): leven.distance(x,y) res=np.fromiter(itertools.imap(f, itertools.product(words, words)), dtype=np.uint8) A = np.reshape(res,(dim,dim)) print "svd..." u,s,v = lin.svd(A, full_matrices=False) print u.shape print s.shape print s print v.shape data = u[:,0:10] k=KMeans(init='k-means++', k=25, n_init=10) k.fit(data) centroids = k.cluster_centers_ labels = k.labels_ print labels for i in range(np.max(labels)): print words[labels==i] def dist(x,y): return np.sqrt(np.sum((xy)**2, axis=1)) print "centroid points.." for i,c in enumerate(centroids): idx = np.argmin(dist(c,data[labels==i])) print words[labels==i][idx] print words[labels==i] plt.plot(centroids[:,0],centroids[:,1],'x') plt.hold(True) plt.plot(u[:,0], u[:,1], '.') plt.show() from mpl_toolkits.mplot3d import Axes3D fig = plt.figure() ax = Axes3D(fig) ax.plot(u[:,0], u[:,1], u[:,2],'.', zs=0, zdir='z', label='zs=0, zdir=z') plt.show() 

Результат

 any ['and' 'an' 'can' 'any'] do ['to' 'you' 'do' 'so' 'go' 'no' 'two' 'how'] when ['who' 'when' 'well'] my ['be' 'I' 'by' 'we' 'my' 'up' 'me' 'use'] your ['for' 'or' 'out' 'about' 'your' 'our'] its ['it' 'his' 'if' 'him' 'its'] could ['would' 'people' 'could'] this ['this' 'think' 'these'] she ['the' 'he' 'she' 'see'] back ['all' 'back' 'want'] one ['of' 'on' 'one' 'only' 'even' 'new'] just ['but' 'just' 'first' 'most'] come ['some' 'come'] that ['that' 'than'] way ['say' 'what' 'way' 'day'] like ['like' 'time' 'give'] in ['in' 'into'] get ['her' 'get' 'year'] because ['because'] will ['with' 'will' 'which'] over ['other' 'over' 'after'] as ['a' 'as' 'at' 'also' 'us'] them ['they' 'there' 'their' 'them' 'then'] good ['not' 'from' 'know' 'good' 'now' 'look' 'work'] have ['have' 'make' 'take'] 

Выбор k для числа кластеров важен, k = 25 дает гораздо лучшие результаты, чем k = 20, например.

Код также выбирает репрезентативное слово для каждого кластера, выбирая слово, координата которого [..] ближе всего к центроиду кластера.

Вот подход, основанный на медоидах. Сначала установите MlPy. На Ubuntu

 sudo apt-get install python-mlpy 

затем

 import numpy as np import mlpy class distance: def compute(self, s1, s2): l1 = len(s1) l2 = len(s2) matrix = [range(zz,zz + l1 + 1) for zz in xrange(l2 + 1)] for zz in xrange(0,l2): for sz in xrange(0,l1): if s1[sz] == s2[zz]: matrix[zz+1][sz+1] = min(matrix[zz+1][sz] + 1, matrix[zz][sz+1] + 1, matrix[zz][sz]) else: matrix[zz+1][sz+1] = min(matrix[zz+1][sz] + 1, matrix[zz][sz+1] + 1, matrix[zz][sz] + 1) return matrix[l2][l1] x = np.array(['ape', 'appel', 'apple', 'peach', 'puppy']) km = mlpy.Kmedoids(k=3, dist=distance()) medoids,clusters,a,b = km.compute(x) print medoids print clusters print a print x[medoids] for i,c in enumerate(x[medoids]): print "medoid", c print x[clusters[a==i]] 

Выход

 [4 3 1] [0 2] [2 2] ['puppy' 'peach' 'appel'] medoid puppy [] medoid peach [] medoid appel ['ape' 'apple'] 

Большой список слов и использование k = 10

 medoid he ['or' 'his' 'my' 'have' 'if' 'year' 'of' 'who' 'us' 'use' 'people' 'see' 'make' 'be' 'up' 'we' 'the' 'one' 'her' 'by' 'it' 'him' 'she' 'me' 'over' 'after' 'get' 'what' 'I'] medoid out ['just' 'only' 'your' 'you' 'could' 'our' 'most' 'first' 'would' 'but' 'about'] medoid to ['from' 'go' 'its' 'do' 'into' 'so' 'for' 'also' 'no' 'two'] medoid now ['new' 'how' 'know' 'not'] medoid time ['like' 'take' 'come' 'some' 'give'] medoid because [] medoid an ['want' 'on' 'in' 'back' 'say' 'and' 'a' 'all' 'can' 'as' 'way' 'at' 'day' 'any'] medoid look ['work' 'good'] medoid will ['with' 'well' 'which'] medoid then ['think' 'that' 'these' 'even' 'their' 'when' 'other' 'this' 'they' 'there' 'than' 'them'] 
  • Обнаружение иностранных слов
  • Выбор наиболее свободного текста из набора возможностей с помощью проверки грамматики (Python)
  • Как мне подойти к этой задаче классификации имен?
  • gensim Doc2Vec vs tensorflow Doc2Vec
  • Python Arabic NLP
  • Точная репликация текстовой предварительной обработки текста в python
  • анализ имен n-грамм на неанглийских языках (CJK и т. д.)
  • Извлечение глагольных стеблей из списка глаголов
  • Каким образом можно найти связанные имена с помощью Интернета?
  • Анализатор времени на естественном языке
  • NLTK не смог найти stanford-postagger.jar! Установите переменную среды CLASSPATH
  • Python - лучший язык программирования в мире.