Кластеринг слов с Kmeans

Question

Как кластеризовать термины (1-2 слова), используя Kmeans. Я прочитал исследовательскую работу, в которой они использовали K-средства для объединения похожих терминов, используя расстояние Левенштейна. Пожалуйста, помогите мне, показывая пример кода.

Спасибо

Примечание: в исследовательской работе они вычислили матрицу подобия, используя расстояние Левенштейна, и использовали ее для кластеризации.

https://ieeexplore.ieee.org/document/7765062/

Answer 1

from nltk.metrics import distance
import scipy.spatial as spatial
import numpy as np
from scipy.cluster.vq import kmeans

# sample vocabulary list
words = ['test', 'text', 'best', 'fast', 'context', 'boost', 'faster', 'border']

# similarity matrix
word_vectors = np.array([
    [
        distance.edit_distance(w, _w)
        for _w in words
    ]
    for w in words
], dtype=np.float)

centroids, _ = kmeans(word_vectors, k_or_guess=3)

word_clusters = np.argmin([
    [spatial.distance.euclidean(wv, cv) for cv in centroids]
    for wv in word_vectors
], 1)

for k in range(centroids.shape[0]):
    print('k =', k)
    print([word for i, word in enumerate(words) if word_clusters[i] == k])

Результат:

k = 0
['faster', 'border']
k = 1
['test', 'text', 'best', 'fast', 'boost']
k = 2
['context']

Примечания:

1. Оригинальный словарь работает как список функций.Список мер расстояния до других слов работает как вектор признаков для любой фразы или слова.
2. Каждый кластер выполнен в таком функциональном пространстве.Следовательно, расстояние между двумя словами больше не является их расстоянием Левенштейна, а их расстоянием в таком пространстве.Вот почему мы используем другие меры, такие как spatial.distance.euclidean.
3. Kmean создает центроиды в этом пространстве признаков, каждое слово рассматривается как член кластера, если центроид кластера находится ближе всего к слову (извсе остальные центроиды).np.argmin([...], 1) находит такое присваивание для каждого слова.
4. Другие алгоритмы кластеризации также могут быть проверены в пространстве слов-признаков.(Список некоторых алгоритмов кластеризации в scikit-learn: https://scikit -learn.org / stable / modules / clustering.html )

Answer 2

Матрица инициализируется измерением в (m, n) -клетке расстояния Левенштейна между m-символьным префиксом одного и n-префиксом другого слова. Матрица может быть заполнена от верхнего левого до нижнего правого угла.

Answer 3

def get_levenshtein_distance(word1, word2):
word2 = word2.lower()
word1 = word1.lower()
matrix = [[0 for x in range(len(word2) + 1)] for x in range(len(word1) + 1)]

for x in range(len(word1) + 1):
    matrix[x][0] = x
for y in range(len(word2) + 1):
    matrix[0][y] = y

print(matrix)