Рубрики
Без рубрики

Построение матрицы соседей с помощью python

От математической формулы до реализации python с помощью python: матрица соседей.

Автор оригинала: Estelle S..

В какой-то момент у меня появилась такая модель, как эта:

Y ~ = W ⋅ Y \Тильда{и} \cdot и ​ Y ​ ~ ​ ​ = W ⋅ Y

где W-матрица, которая может быть определена как (например):

w i j = 1 направо{ij} w ​ i j ​ ​ = 1

если j находится в пределах K ближайших соседей i, то в противном случае 0.

Вот рецепт, который я использовал для создания матрицы W с помощью numpy, scipy и matplotlib для визуализации.

Если вы уже знакомы с scipy cKDTree и sparse matrix, вы можете сразу перейти к последнему разделу .

Примерные данные

Для демонстрации я создал фиктивный набор данных с размерами N=12 train samples и M=3 test samples:

import numpy as np
XY_train = np.array([[1.07712572, 0.50598419], [1.40709049, 1.29030559], [0.55806126, 1.23385926], [-0.92287428, 0.50598419], [-0.59290951, 1.29030559], [-1.44193874, 1.23385926], [-0.92287428, -1.49401581], [-0.59290951, -0.70969441], [-1.44193874, -0.76614074], [1.07712572, -1.49401581], [1.40709049, -0.70969441], [0.55806126, -0.76614074]])
XY_test = np.array([[1, 1], [-1, 1], [-1, -1], [1, -1]])

Давайте посмотрим на эти точки перераспределения: красные точки-это данные поезда, в то время как зеленые точки принадлежат тестовым данным.

Примерные данные

Найти соседей

Найти соседей с помощью современных инструментов довольно просто. Я выбираю здесь использовать scipy, потому что позже в этом посте я буду использовать другие инструменты из этого пакета, но sklearn или другие пакеты также могут выполнить эту работу. С помощью scipy сначала создайте cKDTree с набором данных train:

from scipy.spatial import cKDTree
tree = cKDTree(XY_train)

дерево которое можно запросить во второй раз:

K = 3
result = tree.query(XY_test, k=K)

Здесь мы спросили трех ближайших соседей в образце поезда элементов в тестовом образце. По умолчанию используется дерево.запрос возвращает как индексы соседей, так и соответствующие расстояния. Мы оставим их обоих.

distances, indices = result

Давайте сосредоточимся на массиве indexes .

array([[0, 1, 2], [3, 4, 5], [6, 7, 8], [9, 10, 11]])

Это массив numpy с M (количеством тестовых выборок) строк и K (количеством соседей) столбцов. Как преобразовать это в искомую матрицу, которая на нашем примере должна выглядеть так:

Может быть интересно посмотреть на выбранных соседей по участку:

import matplotlib.pyplot as plt
n = 0 # first element in the test dataset
xy_test = XY_test[n]
index = indices[n]
neighbours = XY_train[index]
plt.clf()
plt.scatter(xy_test[0], xy_test[1], color="red")
plt.scatter(neighbours[:,0], neighbours[:,1], color="blue")
plt.xlabel("x")
plt.ylabel("y")
plt.xlim(-2, 2)
plt.ylim(-2, 2)
plt.show()
Выбранные соседи для тестовой точки 0

Итак, поиск соседей, похоже, работает так, как и ожидалось! Давайте посмотрим, как преобразовать массив indexes в полностью пригодную для использования матрицу, которая для нашей цели должна выглядеть следующим образом:

  1  1  1  0  0  0  0  0  0  0  0  0
  0  0  0  1  1  1  0  0  0  0  0  0
  0  0  0  0  0  0  1  1  1  0  0  0
  0  0  0  0  0  0  0  0  0  1  1  1

поскольку соседями тестового наблюдения 0 (первый ряд) являются наблюдения поезда 0, 1 и 2, соседями тестового наблюдения 1 (второй ряд) являются наблюдения поезда 3, 4 и 5 и т. Д.

Создание матрицы

Сначала мы хотели бы использовать индексацию numpy для создания нашей матрицы следующим образом

import numpy as np
a = np.array([1, 2, 3, 4, 5, 6])
i = [0, 0, 1, 1, 2, 2]
a[i]
# array([1, 1, 2, 2, 3, 3])

но вы поймете, что он не работает более чем с одним массивом измерений.

Решение, которое я выбираю, заключается в использовании разреженных матриц scipy, которые могут быть созданы из списка индексов. Например, создание диагональной матрицы размера N=4 с разреженной матрицей можно записать в виде:

from scipy import sparse
i_index = [0, 1, 2, 3]
j_index = [0, 1, 2, 3]
values = [1, 1, 1, 1]
matrix = sparse.coo_matrix((values, (i_index, j_index)), shape=(4, 4))
print(matrix)
# (0, 0)	1
# (1, 1)	1
# (2, 2)	1
# (3, 3)	1

Таким образом, scipy берет первые элементы массивов i_index и j_index , i и j и помещает первый элемент массива values в позицию [i, j] в конечной матрице. Или, другими словами, значение элемента (0, 0) равно 1, элемент (1, 1) также равен 1… Все не указанные элементы являются нулевыми.

Если вы предпочитаете представление массива, вы можете посмотреть на результат с помощью:

matrix.toarray() # transforms sparse matrix into numpy array just for visualization
#array([[1, 0, 0, 0],
# [0, 1, 0, 0],
# [0, 0, 1, 0],
# [0, 0, 0, 1]])

где вы можете увидеть диагональную матрицу.

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

array([[0, 0, 0, 1], [0, 0, 1, 0], [0, 1, 0, 0], [1, 0, 0, 0]])

На этот раз код таков::

i_index = [3, 2, 1, 0] # <== this is the only change with respect to previous example!
j_index = [0, 1, 2, 3]
values = [1, 1, 1, 1]
matrix = sparse.coo_matrix((values, (i_index, j_index)), shape=(4, 4))

NB: переключение с разреженного представления на плотное возможно только тогда, когда размер матрицы относительно мал, иначе это создаст проблемы с памятью (причина, по которой существуют разреженные матрицы!)

Итак, как же создать эту W-матрицу?

Для матрицы W j_index , то есть столбцы, соответствуют индексам соседей:

j_index = indices.flatten()
#array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11])

Индексы строк, i_index затем соответствуют индексу в тестовом образце, но повторяются K раз, чтобы соответствовать порядку j_index :

i_index = np.repeat(np.array(range(M), dtype=int), repeats=K, axis=0).ravel()
#array([0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3])

Это означает, что для первой строки (rowindex 0) будут единицы для столбцов 0, 1 и 2. Для второй строки (1) будут единицы в столбцах 3, 4, 5… Если вы еще раз посмотрите на позиции образцов теста/поезда (первый рисунок), то это согласуется!

Для значений мы можем использовать “1”:

values = np.ones(M * K) # M = number of test sample, K = number of neighbours

или функция в зависимости от расстояний например:

values = 1. / distances.flatten()**2

И в конце концов наша матрица выглядит так (со значениями “1” ):

matrix = sparse.coo_matrix((values, (i_index, j_index)), shape=(M, N)) 
# array([[1., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
# [0., 0., 0., 1., 1., 1., 0., 0., 0., 0., 0., 0.],
# [0., 0., 0., 0., 0., 0., 1., 1., 1., 0., 0., 0.],
# [0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 1.]])

Вернемся к нашей первоначальной проблеме

Теперь мы можем вычислить наше точечное произведение (либо с разреженной, либо с плотной версией матрицы):

y_tilde = matrix.dot(y) # where y has shape (N, )

И вот мы здесь, проблема решена!

Найдите эту статью и многое другое на моем сайте: steelasia.github.io