1.6. Ближайшие соседи

1.6.1.1. Поиск ближайших соседей

Для простой задачи поиска ближайших соседей между двумя наборами данных можно использовать алгоритмы обучения без учителя из sklearn.neighbors:

>>> from sklearn.neighbors import NearestNeighbors
>>> import numpy as np
>>> X = np.array([[-1, -1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])
>>> nbrs = NearestNeighbors(n_neighbors=2, algorithm='ball_tree').fit(X)
>>> distances, indices = nbrs.kneighbors(X)
>>> indices
array([[0, 1],
       [1, 0],
       [2, 1],
       [3, 4],
       [4, 3],
       [5, 4]]...)
>>> distances
array([[0.        , 1.        ],
       [0.        , 1.        ],
       [0.        , 1.41421356],
       [0.        , 1.        ],
       [0.        , 1.        ],
       [0.        , 1.41421356]])

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

Также можно эффективно построить разреженный граф, отображающий связи между соседними точками:

>>> nbrs.kneighbors_graph(X).toarray()
array([[1., 1., 0., 0., 0., 0.],
       [1., 1., 0., 0., 0., 0.],
       [0., 1., 1., 0., 0., 0.],
       [0., 0., 0., 1., 1., 0.],
       [0., 0., 0., 1., 1., 0.],
       [0., 0., 0., 0., 1., 1.]])

Набор данных устроен так, что точки, близкие друг к другу по индексам, близки и в пространстве параметров, поэтому матрица K ближайших соседей имеет приблизительно блочно-диагональную структуру. Такой разреженный граф полезен в различных случаях, когда для обучения без учителя используются пространственные взаимосвязи между точками; в частности, см. Isomap, LocallyLinearEmbedding и SpectralClustering.

1.6.1.2. Классы KDTree и BallTree

Кроме того, для поиска ближайших соседей можно напрямую использовать классы KDTree или BallTree. Именно эту функциональность предоставляет используемый выше класс NearestNeighbors. Дерево Ball Tree и KD-дерево имеют одинаковый интерфейс; ниже приведен пример использования KD-дерева:

>>> from sklearn.neighbors import KDTree
>>> import numpy as np
>>> X = np.array([[-1, -1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])
>>> kdt = KDTree(X, leaf_size=30, metric='euclidean')
>>> kdt.query(X, k=2, return_distance=False)
array([[0, 1],
       [1, 0],
       [2, 1],
       [3, 4],
       [4, 3],
       [5, 4]]...)

Дополнительную информацию о доступных параметрах поиска ближайших соседей, в том числе о настройке стратегий запросов, метрик расстояния и т. д., см. в документации классов KDTree и BallTree. Список допустимых метрик можно получить с помощью KDTree.valid_metrics и BallTree.valid_metrics:

>>> from sklearn.neighbors import KDTree, BallTree
>>> KDTree.valid_metrics
['euclidean', 'l2', 'minkowski', 'p', 'manhattan', 'cityblock', 'l1', 'chebyshev', 'infinity']
>>> BallTree.valid_metrics
['euclidean', 'l2', 'minkowski', 'p', 'manhattan', 'cityblock', 'l1', 'chebyshev', 'infinity', 'seuclidean', 'mahalanobis', 'hamming', 'canberra', 'braycurtis', 'jaccard', 'dice', 'rogerstanimoto', 'russellrao', 'sokalmichener', 'sokalsneath', 'haversine', 'pyfunc']

1.6.4.1. Полный перебор

Быстрое вычисление ближайших соседей — активная область исследований в машинном обучении. Самая простая реализация поиска соседей предполагает полный перебор расстояний между всеми парами точек в наборе данных: для \(N\) образцов в \(D\) измерениях сложность этого подхода составляет \(O[D N^2]\). Эффективный поиск соседей полным перебором может быть весьма конкурентоспособным на небольших выборках данных. Однако по мере роста числа образцов \(N\) подход полного перебора быстро становится неприемлемым. В классах из sklearn.neighbors поиск соседей полным перебором задаётся с помощью ключевого слова algorithm = 'brute' и выполняется с использованием процедур, доступных в sklearn.metrics.pairwise.

1.6.4.2. K-D-дерево

Для устранения вычислительной неэффективности подхода полного перебора были разработаны различные древовидные структуры данных. В целом эти структуры стремятся уменьшить необходимое количество вычислений расстояний, эффективно кодируя агрегированную информацию о расстояниях для образца. Основная идея состоит в том, что если точка \(A\) находится очень далеко от точки \(B\), а точка \(B\) находится очень близко к точке \(C\), то мы знаем, что точки \(A\) и \(C\) находятся очень далеко друг от друга, и для этого не нужно вычислять расстояние между ними напрямую. Таким образом, вычислительную стоимость поиска ближайших соседей можно снизить до \(O[D N \log(N)]\) или меньше. Это значительное улучшение по сравнению с полным перебором при больших значениях \(N\).

Одним из первых подходов к использованию этой агрегированной информации стала структура данных KD-дерево (сокращение от K-dimensional tree — K-мерное дерево), которая обобщает двумерные квадродеревья и трёхмерные октодеревья для произвольного числа измерений. KD-дерево — это двоичная древовидная структура, которая рекурсивно разбивает пространство параметров вдоль осей данных, деля его на вложенные ортотропные области, в которые распределяются точки данных. Построение KD-дерева выполняется очень быстро: поскольку разбиение проводится только вдоль осей данных, вычислять расстояния в \(D\)-мерном пространстве не требуется. После построения ближайшего соседа для точки-запроса можно определить, выполнив всего \(O[\log(N)]\) вычислений расстояния. Хотя подход с KD-деревом очень эффективен для поиска соседей в пространствах малой размерности (\(D < 20\)), он становится неэффективным при значительном росте \(D\): это одно из проявлений так называемого «проклятия размерности». В scikit-learn поиск соседей с помощью KD-дерева задаётся ключевым словом algorithm = 'kd_tree' и выполняется с помощью класса KDTree.

1.6.4.3. Шаровое дерево

Для устранения неэффективности KD-деревьев в пространствах высокой размерности была разработана структура данных шаровое дерево. В отличие от KD-деревьев, которые разбивают данные вдоль декартовых осей, шаровые деревья делят данные на ряд вложенных гиперсфер. Это делает построение дерева более затратным, чем построение KD-дерева, но в результате получается структура данных, которая может быть очень эффективна для хорошо структурированных данных, даже в пространствах очень высокой размерности.

Шаровое дерево рекурсивно делит данные на узлы, задаваемые центроидом \(C\) и радиусом \(r\), так что каждая точка узла находится внутри гиперсферы, определяемой \(r\) и \(C\). Число точек-кандидатов для поиска соседей сокращается благодаря использованию неравенства треугольника:

При такой структуре достаточно одного вычисления расстояния между тестовой точкой и центроидом, чтобы определить нижнюю и верхнюю границы расстояний до всех точек узла. Благодаря сферической геометрии узлов шарового дерева оно может превосходить KD-дерево в пространствах высокой размерности, хотя фактическая производительность сильно зависит от структуры обучающих данных. В scikit-learn поиск соседей на основе шарового дерева задаётся ключевым словом algorithm = 'ball_tree' и выполняется с помощью класса BallTree. Также пользователь может напрямую работать с классом BallTree.

>>> from sklearn.neighbors import KDTree
>>> print(sorted(KDTree.valid_metrics))
['chebyshev', 'cityblock', 'euclidean', 'infinity', 'l1', 'l2', 'manhattan', 'minkowski', 'p']

1.6.5.1. Ближайший сжатый центроид

Классификатор NearestCentroid имеет параметр shrink_threshold, реализующий классификатор ближайшего сжатого центроида. По сути, значение каждого признака для каждого центроида делится на внутриклассовую дисперсию этого признака. Затем значения признаков уменьшаются на shrink_threshold. В частности, если значение какого-либо признака пересекает ноль, оно устанавливается равным нулю. Фактически это исключает влияние признака на классификацию. Например, такой подход полезен для удаления шумовых признаков.

В примере ниже небольшой порог сжатия повышает точность модели с 0.81 до 0.82.

Примеры

• Классификация по ближайшему центроиду: пример классификации с использованием ближайшего центроида и различных порогов сжатия.

1.6.7.1. Классификация

В сочетании с классификатором ближайших соседей (KNeighborsClassifier) NCA привлекателен для задач классификации, поскольку позволяет естественным образом обрабатывать многоклассовые задачи без увеличения размера модели и не вводит дополнительных параметров, требующих тонкой настройки пользователем.

На практике классификация с помощью NCA хорошо работает на наборах данных разного размера и сложности. В отличие от родственных методов, таких как линейный дискриминантный анализ, NCA не делает никаких предположений о распределениях классов. Классификация методом ближайших соседей позволяет естественным образом строить весьма нерегулярные границы принятия решений.

Чтобы использовать эту модель для классификации, нужно объединить экземпляр NeighborhoodComponentsAnalysis, который обучает оптимальное преобразование, с экземпляром KNeighborsClassifier, выполняющим классификацию в пространстве проекции. Ниже приведён пример с использованием этих двух классов:

>>> from sklearn.neighbors import (NeighborhoodComponentsAnalysis,
... KNeighborsClassifier)
>>> from sklearn.datasets import load_iris
>>> from sklearn.model_selection import train_test_split
>>> from sklearn.pipeline import Pipeline
>>> X, y = load_iris(return_X_y=True)
>>> X_train, X_test, y_train, y_test = train_test_split(X, y,
... stratify=y, test_size=0.7, random_state=42)
>>> nca = NeighborhoodComponentsAnalysis(random_state=42)
>>> knn = KNeighborsClassifier(n_neighbors=3)
>>> nca_pipe = Pipeline([('nca', nca), ('knn', knn)])
>>> nca_pipe.fit(X_train, y_train)
Pipeline(...)
>>> print(nca_pipe.score(X_test, y_test))
0.96190476...

На графике показаны границы принятия решений для классификации методом ближайших соседей и классификации с помощью анализа компонент окрестности на наборе данных iris. Для наглядности при обучении и оценке использованы только два признака.

1.6.7.2. Понижение размерности

NCA можно использовать для контролируемого понижения размерности. Входные данные проецируются на линейное подпространство, состоящее из направлений, минимизирующих целевую функцию NCA. Требуемую размерность можно задать с помощью параметра n_components. Например, на следующем рисунке сравнивается понижение размерности с помощью метода главных компонент (PCA), линейного дискриминантного анализа (LinearDiscriminantAnalysis) и анализа компонент окрестности (NeighborhoodComponentsAnalysis) на наборе данных Digits размером \(n_{samples} = 1797\) и с \(n_{features} = 64\) признаками. Набор данных делится на обучающую и тестовую выборки одинакового размера, а затем стандартизируется. Для оценки вычисляется точность классификации методом 3 ближайших соседей на точках двумерной проекции, полученной каждым методом. Каждый образец данных принадлежит одному из 10 классов.

Примеры

• Сравнение методов ближайших соседей с анализом компонент окрестности и без него
• Понижение размерности с помощью анализа компонент окрестности
• Обучение на многообразиях для рукописных цифр: локальное линейное вложение, Isomap…

1.6.7.3. Математическая формулировка

Цель NCA — обучить оптимальную матрицу линейного преобразования размером (n_components, n_features), которая максимизирует сумму вероятностей \(p_i\) по всем образцам \(i\), где \(p_i\) — вероятность правильной классификации образца \(i\), то есть:

где \(N\) = n_samples, а \(p_i\) — вероятность правильной классификации образца \(i\) согласно стохастическому правилу ближайших соседей в обученном пространстве вложения:

где \(C_i\) — множество точек того же класса, что и образец \(i\), а \(p_{i j}\) — функция softmax от евклидовых расстояний в пространстве вложения:

1.6.7.4. Реализация

Эта реализация соответствует описанию в исходной статье [1]. В качестве метода оптимизации сейчас используется L-BFGS-B из scipy с полным вычислением градиента на каждой итерации, чтобы избежать настройки скорости обучения и обеспечить стабильное обучение.

Дополнительную информацию см. в примерах ниже и в строке документации метода NeighborhoodComponentsAnalysis.fit.

1.6.7.5. Сложность