Взаимосвязь терминов второго порядка в текстах

Question

По сути, Я хочу переопределить это видео .

Учитывая совокупность документов, я хочу найти термины, которые наиболее похожи друг на друга.

Мне удалось сгенерировать матрицу совпадений, используя этот поток SO , и использовать видео для генерации матрицы ассоциации.Далее я хотел бы сгенерировать матрицу со случайностью второго порядка.

Постановка задачи: Рассмотрим матрицу, в которой строки матрицы соответствуют терму, а записи в строках соответствуют верхним k терминам, аналогичным этому.срок.Скажем, k = 4, и у нас есть n терминов в нашем словаре, тогда матрица M имеет n строк и 4 столбцов.

ЕСТЬ:

M = [[18,34,54,65],   # Term IDs similar to Term t_0
     [18,12,54,65],   # Term IDs similar to Term t_1
     ...
     [21,43,55,78]]   # Term IDs similar to Term t_n.

Итак, M содержит для каждого идентификатора термина наиболее близкие идентификаторы термина.Теперь я хотел бы проверить, сколько из этих похожих терминов совпадают.В приведенном выше примере M кажется, что термин t_0 и термин t_1 очень похожи, потому что три из четырех терминов совпадают, а термины t_0 и t_n не похожи, потому что термины отсутствуютматч.Давайте напишем M как серию списков.

M = [list_0,   # Term IDs similar to Term t_0
     list_1,   # Term IDs similar to Term t_1
     ...
     list_n]   # Term IDs similar to Term t_n.

ХОЧУ:

C = [[f(list_0, list_0), f(list_0, list_1), ..., f(list_0, list_n)],
     [f(list_1, list_0), f(list_1, list_1), ..., f(list_1, list_n)],
     ...
     [f(list_n, list_0), f(list_n, list_1), ..., f(list_n, list_n)]]

Я хотел бы найти матрицу C, которая имеет в качестве своих элементов,функция f применяется к спискам M.f(a,b) измеряет степень сходства между двумя списками a и b.В соответствии с приведенным выше примером степень сходства между t_0 и t_1 должна быть высокой, тогда как степень сходства t_0 и t_n должна быть низкой.

Мои вопросы:

1. Что является хорошим выбором для сравнения порядка двух списков?То есть, что является хорошим выбором для функции f?
2. Есть ли уже доступное преобразование, которое принимает в качестве входных данных матрицу, подобную M, и производит матрицу, подобную C?Желательно пакет с питоном?

Спасибо, r0f1

Answer 1

На самом деле, косинусное сходство в этом случае может быть не таким уж плохим.Проблема в том, что вы не хотите использовать индексные векторы (т. Е. [18,34,54,65] и т. Д. В вашем случае), но вам нужны векторы длины n, которые везде равны нулю, за исключением значений в вашем индексном векторе.К счастью, вам не нужно явно создавать эти векторы, но вы можете просто посчитать, сколько индексов имеют два вектора индексов:

def f(u, v):
    return len(set(u).intersection(set(v)))

Здесь я опустил постоянный коэффициент нормализации k.Есть некоторые более сложные вещи, которые можно сделать (например, ядро ​​TF-IDF), но я бы остановился на этом для начала.

Для того, чтобы эффективно выполнить это с использованием numpy, вам нужносделать две вещи:

Преобразовать f в ufunc, то есть в numy векторизованную функцию.Вы можете сделать это с помощью uf = np.frompyfunc(f, 2, 1) (при условии, что в какой-то момент вы сделали import numpy as np).

Сохранить M как массив списков 1d (в основном то, что вы указали во втором листинге кода).Это немного сложнее, потому что numpy пытается быть умным здесь, но вы хотите что-то еще.Вот как это сделать:

n = len(M)
Marray = np.empty(n, dtype='O')  # dtype='O' allows you to have elements of type list
for i in range(n):
    Marray[i] = M[i]

Теперь Marray содержит, по сути, то, что вы описали во втором листинге кода.Затем вы можете использовать новый метод ufunc outer, чтобы получить матрицу сходства.Вот как все это будет работать вместе для вашего M из примера (при условии n=3):

M = [[18, 34, 54, 65],
     [18, 12, 54, 65],
     [21, 43, 55, 78]]
n = len(M)  # i.e. 3
uf = np.frompyfunc(f, 2, 1)
Marray = np.empty(n, dtype='O')
for i in range(n):
    Marray[i] = M[i]
similarities = uf.outer(Marray, Marray).astype('d')  # convert to float instead object type
print(similarities)
# array([[4., 3., 0.],
#        [3., 4., 0.],
#        [0., 0., 4.]])

Я надеюсь, что это ответит на ваши вопросы.

Answer 2

Вы задали два вопроса, один несколько открытый (первый) и другой, который имеет окончательный ответ, поэтому я начну со второго:

Есть ли уже преобразование?доступно, что принимает в качестве входных данных матрицу, подобную M, и производит матрицу, подобную C?Предпочтительно пакет python?

Ответ - да, есть один пакет с именем scipy.spatial.distance , который содержит функцию, которая принимает матрицу типа M и производитматрица типа C.В следующем примере показана функция:

import numpy as np
from scipy.spatial.distance import pdist, squareform

# initial data
M = [[18, 34, 54, 65],
     [18, 12, 54, 65],
     [21, 43, 55, 78]]

# convert to numpy array
arr = np.array(M)

result = squareform(pdist(M, metric='euclidean'))
print(result)

Выход

[[ 0.         22.         16.1245155 ]
 [22.          0.         33.76388603]
 [16.1245155  33.76388603  0.        ]]

Как видно из приведенного выше примера, pdist принимаетM матрица и генерирует матрицу C.Обратите внимание, что вывод pdist представляет собой матрицу сжатых расстояний , поэтому вам необходимо преобразовать ее в квадратную форму, используя squareform .Теперь перейдем ко второму вопросу:

Что является хорошим выбором для сравнения порядка двух списков?То есть, что является хорошим выбором для функции f?

Учитывая, что порядок имеет значение в вашем конкретном случае, я предлагаю вам взглянуть на коэффициенты ранговой корреляции, такие как: Kendall или Spearman , оба представлены в пакете scipy.stats вместе с целым рядом других коэффициентов.Пример использования:

import numpy as np
from scipy.spatial.distance import pdist, squareform
from scipy.stats import kendalltau, spearmanr

# distance function
kendall = lambda x, y : kendalltau(x, y)[0]
spearman = lambda x, y : spearmanr(x, y)[0]


# initial data
M = [[18, 34, 54, 65],
     [18, 12, 54, 65],
     [21, 43, 55, 78]]

# convert to numpy array
arr = np.array(M)

# compute kendall C and convert to square form
kendall_result = 1 - squareform(pdist(arr, kendall))  # subtract 1 because you want a similarity
print(kendall_result)
print()

# compute spearman C and convert to square form
spearman_result = 1 - squareform(pdist(arr, spearman))  # subtract 1 because you want a similarity
print(spearman_result)
print()

Выход

[[1.         0.33333333 0.        ]
 [0.33333333 1.         0.33333333]
 [0.         0.33333333 1.        ]]

[[1.  0.2 0. ]
 [0.2 1.  0.2]
 [0.  0.2 1. ]]

Если они не соответствуют вашим потребностям, вы можете взглянуть на расстояние Хэмминга Например:

import numpy as np
from scipy.spatial.distance import pdist, squareform

# initial data
M = [[18, 34, 54, 65],
     [18, 12, 54, 65],
     [21, 43, 55, 78]]

# convert to numpy array
arr = np.array(M)

# compute match_rank C and convert to square form
result = 1 - squareform(pdist(arr, 'hamming'))
print(result)

Вывод

[[1.   0.75 0.  ]
 [0.75 1.   0.  ]
 [0.   0.   1.  ]]

В конце концов выбор функции подобия будет зависеть от вашего конечного приложения, поэтому вам потребуетсяПопробуйте различные функции и посмотрите те, которые соответствуют вашим потребностям.И scipy.spatial.distance, и scipy.stats предоставляют множество функций расстояния и коэффициентов, которые вы можете попробовать.

Далее

1. Следующая бумага содержит раздел о сходстве списков

Answer 3

Я бы предложил косинусное сходство, поскольку каждый список является вектором.

     from sklearn.metrics.pairwise import cosine_similarity

     cosine_similarity(list0,list1)