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, используемым выше. У деревьев с шаром и 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. Дерево KD

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

Ранним подходом к использованию этой агрегированной информации была структура данных дерево KD (сокращение от 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.

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 ближайших соседей на 2-мерных спроектированных точках, полученных каждым методом. Каждый образец данных относится к одному из 10 классов.

Примеры

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

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

Цель NCA — обучить оптимальную линейную матрицу преобразования размера (n_components, n_features), которая максимизирует сумму по всем образцам \(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. Сложность