Построение матрицы соседей с помощью python
В какой-то момент я остановился на такой модели:
где W — матрица, которую можно определить как (например):
если j находится в пределах K ближайших соседей i, 0 в противном случае.
Вот рецепт, который я использовал для создания матрицы W, используя numpy, scipy и matplotlib для визуализации.
Если вы уже знакомы с scipy cKDTree и разреженной матрицей, вы можете напрямую перейти к последний раздел.
Образец данных
Я создал фиктивный набор данных для демонстрации с размерами N=12 обучать образцы и M=3 образцы для испытаний:
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 с набором данных поезда:
from scipy.spatial import cKDTree
tree = cKDTree(XY_train)
tree который можно запросить во второй раз:
K = 3
result = tree.query(XY_test, k=K)
Здесь мы запросили трех ближайших соседей в выборке поездов элементов в тестовой выборке. По умолчанию, tree.query возвращает как индексы соседей, так и задействованные расстояния. Мы сохраним их обоих.
distances, indices = result
Давайте сосредоточимся на indices множество.
array([[0, 1, 2], [3, 4, 5], [6, 7, 8], [9, 10, 11]])
Это пустой массив с 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()
Итак, поиск соседей работает, как и ожидалось! Давайте посмотрим, как преобразовать indices массив в полную пригодную для использования матрицу, которая для нашей цели должна выглядеть так:
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])
Это означает, что для первой строки (индекс строки 0) будут единицы для столбцов 0, 1 и 2. Для второй строки (1) будут единицы в столбцах 3, 4, 5… Если вы снова посмотрите на тест /train сэмплирует позиции (первый рисунок), это соответствует!
Для значений мы можем использовать «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, )
И вот, проблема решена!
Найдите эту и другие статьи на моем сайте: Stellasia.github.io
