1.6. Ближайшие соседи (Nearest Neighbors)¶

Модуль sklearn.neighbors предоставляет функциональность для методов обучения на основе ближайших соседей с учителем и без учителя. Методы ближайших соседей без учителя лежат в основе многих других методов обучения, в частности, многомерного обучения и спектральной кластеризации. Методы ближайших соседей с учителем бывют двух видов: classification для данных с дискретными метками и regression для данных с непрерывными метками.

Принцип методов ближайших соседей заключается в том, чтобы найти заранее определенное количество обучающих образцов, наиболее близких по расстоянию к новой точке, и предсказать метку на их основе. Количество образцов может быть заданной пользователем константой (k-nearest neighbor learning - Метод K-ближайших соседей (KNN)) или меняться в зависимости от локальной плотности точек (radius-based neighbor learning).

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

Методы, основанные на соседях, известны как необобщающие методы машинного обучения, поскольку они просто “запоминают” все свои обучающие данные (возможно, преобразованные в быструю структуру индексации, такую как Ball Tree или KD Tree).

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

Классы в sklearn.neighbors могут работать с массивами NumPy или матрицами scipy.sparse в качестве входных данных. Для плотных матриц поддерживается большое количество возможных метрик расстояния. Для разреженных матриц поддерживаются произвольные метрики Минковского для поиска.

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

1.6.1. Обучение без учителям с помощью метода ближайших соседей¶

Класс NearestNeighbors реализует неконтролируемое обучение ближайших соседей. Он выступает в качестве единого интерфейса для трех различных алгоритмов поиска ближайших соседей: BallTree, KDTree и алгоритма грубой силы (brute-force), основанного на процедурах в sklearn.metrics.pairwise. Выбор алгоритма поиска соседей контролируется с помощью ключевого слова 'algorithm', которое должно быть одним из ['auto', 'ball_tree', 'kd_tree', 'brute']. Когда передается значение по умолчанию 'auto', алгоритм пытается определить наилучший подход на основе обучающих данных. Для обсуждения сильных и слабых сторон каждого варианта см. раздел Алгоритмы ближайших соседей.

Предупреждение

Что касается алгоритмов ближайших соседей, если два соседа \(k+1\) и \(k\) имеют одинаковые расстояния, но разные метки, тогда результат будет зависеть от порядка обучающих данных.

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-ближайших соседей (KNN). Такой разреженный граф полезен в различных ситуациях, использующих пространственные связи между точками для неконтролируемого обучения: в частности, смотрите Isomap, LocallyLinearEmbedding, и SpectralClustering.

1.6.1.2. Классы KDTree и BallTree¶

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

>>> 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.2. Классификация на основе ближайших соседей¶

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

scikit-learn реализует два различных классификатора ближайших соседей: KNeighborsClassifier реализует обучение на основе K-ближайших соседей каждой точки запроса, где \(k\) - целое значение, заданное пользователем. Класс RadiusNeighborsClassifier реализует обучение на основе количества соседей в пределах фиксированного радиуса \(r\) от каждой точки обучения, где \(r\) - значение с плавающей точкой, указанное пользователем.

Классификация по \(k\)-соседям в KNeighborsClassifier - наиболее часто используемая техника. Оптимальный выбор значения \(k\) сильно зависит от данных: в общем случае большее значение \(k\) подавляет влияние шума, но делает границы классификации менее четкими.

В случаях, когда выборка данных неравномерна, лучшим выбором может стать классификация соседей по радиусу в RadiusNeighborsClassifier. Пользователь задает фиксированный радиус \(r\), такой, что точки в более разреженных окрестностях используют меньше ближайших соседей для классификации. Для высокоразмерных пространств параметров этот метод становится менее эффективным из-за так называемого “проклятия размерности”.

В базовой классификации ближайших соседей используются равномерные веса: то есть значение, присваиваемое точке запроса, вычисляется простым большинством голосов ближайших соседей. При некоторых обстоятельствах лучше взвесить соседей так, чтобы более близкие соседи вносили больший вклад при обучении. Этого можно добиться с помощью ключевого слова weights. Значение по умолчанию, weights = 'uniform', присваивает равномерные веса каждому соседу. Значение weights = 'distance' присваивает веса, пропорциональные обратной величине расстояния от точки запроса. В качестве альтернативы для вычисления весов может быть задана пользовательская функция расстояния.

1.6.3. Регрессия на основе ближайших соседей¶

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

scikit-learn реализует два различных регрессора соседей: KNeighborsRegressor реализует обучение на основе K-ближайших соседей каждой точки запроса, где \(k\) - целое значение, заданное пользователем. RadiusNeighborsRegressor реализует обучение на основе соседей в пределах фиксированного радиуса \(r\) от точки запроса, где \(r\) - значение с плавающей точкой, указанное пользователем.

В базовой регрессии ближайших соседей используются равномерные веса: то есть каждая точка в локальной окрестности вносит одинаковый вклад в классификацию точки запроса. При некоторых обстоятельствах может быть выгодно взвесить точки таким образом, чтобы близкие точки вносили больший вклад в регрессию, чем далекие. Этого можно добиться с помощью ключевого слова weights. Значение по умолчанию, weights = 'uniform', присваивает всем точкам одинаковые веса. Значение weights = 'distance' присваивает веса, пропорциональные обратной величине расстояния до точки запроса. В качестве альтернативы можно задать пользовательскую функцию расстояния, которая будет использоваться для вычисления весов.

../_images/sphx_glr_plot_regression_001.png

Использование с несколькими выходами ближайших соседей для регрессии продемонстрировано в Face completion with a multi-output estimators. В этом примере входами X являются пиксели верхней половины лиц, а выходами Y - пиксели нижней половины этих лиц.

../_images/sphx_glr_plot_multioutput_face_completion_001.png

1.6.4. Алгоритмы ближайших соседей¶

1.6.4.1. Грубая сила (Brute Force)¶

Быстрое вычисление ближайших соседей - активная область исследований в машинном обучении. Самая наивная реализация поиска соседей включает в себя грубое вычисление расстояний между всеми парами точек в наборе данных: для \(N\) выборок в \(D\) измерениях, этот подход масштабируется как \(O[D N^2]\). Эффективный грубый поиск соседей может быть очень конкурентоспособным для небольших выборок данных.

Однако с ростом числа выборок \(N\) подход грубой силы быстро становится невыполнимым. В классах внутри sklearn.neighbors поиск соседей методом грубой силы задается с помощью ключевого слова algorithm = 'brute', а вычисляется с помощью процедур, доступных в sklearn.metrics.pairwise`.

1.6.4.2. K-D дерево (KD tree)¶

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

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

Ранним подходом к использованию этой совокупной информации была структура данных KD tree (сокращение от K-dimensional tree), которая обобщает двумерные Quad-trees и трехмерные Oct-trees на произвольное число измерений. KD-дерево представляет собой бинарную древовидную структуру, которая рекурсивно разбивает пространство параметров по осям данных, разделяя его на вложенные ортотропные области, в которые подаются точки данных. Построение KD-дерева происходит очень быстро: поскольку разбиение выполняется только по осям данных, не требуется вычислять \(D\)-мерные расстояния. После построения ближайший сосед точки запроса может быть определен только с помощью \(O[\log(N)]\) вычислений расстояния.

Хотя подход KD-дерева очень быстр для поиска соседей в низкой размерности (\(D < 20\)), он становится неэффективным, когда \(D\) становится очень большим: это одно из проявлений так называемого “проклятия размерности”. В scikit-learn поиск соседей по KD-дереву задается с помощью ключевого слова algorithm = 'kd_tree', а вычисляется с помощью класса KDTree`.

1.6.4.3. Ball Tree (Шаровое дерево)¶

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

Ball Tree рекурсивно делит данные на узлы, определяемые центроидом \(C\) и радиусом \(r\), таким образом, что каждая точка в узле лежит внутри гиперсферы, определяемой \(r\) и \(C\). Количество точек-кандидатов для поиска соседей уменьшается за счет использования неравенства треугольника:

\[|x+y| \leq |x| + |y|\]

При такой настройке для определения нижней и верхней границы расстояния до всех точек в узле достаточно одного вычисления расстояния между тестовой точкой и центроидом.

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

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

1.6.4.4. Выбор алгоритма ближайших соседей¶

Выбор оптимального алгоритма для конкретного набора данных - сложная задача, зависящая от множества факторов:

количества выборок \(N\) (т.е. n_samples) и размерности \(D\) (т.е. n_features).
- Brute force время запроса растет как \(O[D N]\).
- Ball tree время запроса растет примерно как \(O[D \log(N)]\).
- KD-дерево время запроса изменяется с \(D\) способом, который трудно точно охарактеризовать.

Для малых \(D\) (меньше 20 или около того) стоимость составляет примерно \(O[D\log(N)]\), и запрос KD-дерева может быть очень эффективным.

Для больших \(D\) стоимость возрастает почти до \(O[DN]\), и накладные расходы из-за древовидной структуры могут привести к запросам, которые медленнее, чем грубая сила.

Для небольших наборов данных (\(N\) меньше 30 или около того), \(\log(N)\) сравним с \(N\), и алгоритмы грубой силы могут быть более эффективными, чем древовидный подход. И KDTree, и BallTree решают эту проблему, предоставляя параметр размер листа: он управляет количеством образцов, при котором запрос переключается на перебор. Это позволяет обоим алгоритмам приблизиться к эффективности перебора для малых \(N\).

структура данных: внутренняя размерность данных и/или разнородность данных. Внутренняя размерность относится к размерности \(d \le D\) многообразия, на котором лежат данные, которое может быть линейно или нелинейно вложено в пространство параметров. Разреженность относится к степени заполнения данными пространства параметров (следует отличать от понятия, используемого в “разреженных” матрицах. Матрица данных может не иметь нулевых записей, но структура все равно может быть “разреженной” в этом смысле).
- в режиме “грубой силы” время выполнения запросов не зависит от структуры данных.
- Время выполнения Ball Tree и KD-дерево может сильно зависеть от структуры данных. Как правило, более разреженные данные с меньшей собственной размерностью приводят к более быстрому выполнению запросов. Поскольку внутреннее представление KD-дерева выравнивается по осям параметров, для произвольно структурированных данных оно обычно не показывает такого улучшения, как Ball Tree.
Наборы данных, используемые в машинном обучении, как правило, очень структурированы и хорошо подходят для запросов на основе деревьев.
количество соседей \(k\), запрашиваемых для точки запроса.
- Время выполнения запроса в режиме “грубой силы” практически не зависит от значения \(k\).
- Время выполнения Ball Tree и KD-дерево будет замедляться по мере увеличения \(k\). Это связано с двумя эффектами: во-первых, увеличение \(k\) приводит к необходимости поиска в большей части пространства параметров. Во-вторых, использование \(k > 1\) требует внутренней очереди результатов по мере обхода дерева.
Когда \(k\) становится большим по сравнению с \(N\), возможность обрезать ветви в запросе на основе дерева уменьшается. В этой ситуации более эффективными могут быть запросы с применением грубой силы.
количество точек запроса. И ball tree, и дерево KD требуют этапа построения. Стоимость этого построения становится пренебрежимо малой, если амортизировать ее на множество запросов. Однако если будет выполнено лишь небольшое количество запросов, построение может составлять значительную часть общей стоимости. Если требуется очень мало точек запроса, грубая сила лучше, чем метод, основанный на дереве.

В настоящее время algorithm = 'auto' выбирает 'brute', если проверяется любое из следующих условий:

входные данные разрежены
metric = 'precomputed'
\(D > 15\)
\(k >= N/2\)
effective_metric_ не в VALID_METRICS список для любого 'kd_tree' или 'ball_tree'

В противном случае выбирается первое из 'kd_tree' и 'ball_tree', которое имеет effective_metric_ в списке VALID_METRICS. Эта эвристика основана на следующих предположениях:

количество точек запроса по крайней мере того же порядка, что и количество точек обучения
leaf_size близок к значению по умолчанию 30
когда \(D > 15\), внутренняя размерность данных, как правило, слишком высока для древовидных методов

1.6.4.5. Влияние параметра `leaf_size`¶

Как отмечалось выше, при небольших размерах выборки поиск методом грубой силы может быть более эффективным, чем запрос на основе дерева. Этот факт учитывается в ball tree и KD tree путем внутреннего переключения на поиск методом грубой силы в узлах листьев. Уровень этого переключения можно задать с помощью параметра leaf_size. Выбор этого параметра имеет множество эффектов:

время построения

Большой размер leaf_size приводит к более быстрому построению дерева, так как требуется создать меньше узлов.

время запроса

Как большой, так и малый leaf_size может привести к неоптимальному времени запроса.

Если leaf_size приближается к 1, накладные расходы на обход узлов могут значительно замедлить время выполнения запроса. Если leaf_size приближается к размеру обучающего набора, запросы становятся по сути грубой силой.

Хорошим компромиссом между этими значениями является leaf_size = 30, значение параметра по умолчанию.

память

С увеличением leaf_size уменьшается объем памяти, необходимый для хранения древовидной структуры. Это особенно важно в случае шарового дерева, которое хранит \(D\)-мерный центроид для каждого узла. Объем памяти, необходимый для хранения BallTree, приблизительно равен 1 / leaf_size, умноженному на размер обучающего набора.

leaf_size не используется для запросов грубой силы.

1.6.4.6. Метрики валидации для алгоритмов ближайших соседей¶

Список доступных метрик см. в документации класса DistanceMetric и метрик, перечисленных в sklearn.metrics.pairwise.PAIRWISE_DISTANCE_FUNCTIONS. Обратите внимание, что метрика “косинус” использует cosine_distances.

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

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

1.6.5. Классификатор ближайшего центроида¶

Классификатор NearestCentroid - это простой алгоритм, который представляет каждый класс по центроиду его членов. По сути, это делает его похожим на фазу обновления меток в алгоритме K-means (K-средних). У него также нет параметров для выбора, что делает его хорошим базовым классификатором. Однако он страдает на невыпуклых классах, а также когда классы имеют резко отличающиеся дисперсии, поскольку предполагается равная дисперсия во всех измерениях. Более сложные методы, в которых это предположение не делается, см. в Линейном Дискриминантном Анализе (Линейный Дискриминантный Анализ и Квадратичный Дискриминантный Анализ) и Квадратичном дискриминантном анализе (Линейный Дискриминантный Анализ и Квадратичный Дискриминантный Анализ). Использование по умолчанию NearestCentroid очень простое:

>>> from sklearn.neighbors import NearestCentroid
>>> import numpy as np
>>> X = np.array([[-1, -1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])
>>> y = np.array([1, 1, 1, 2, 2, 2])
>>> clf = NearestCentroid()
>>> clf.fit(X, y)
NearestCentroid()
>>> print(clf.predict([[-0.8, -1]]))
[1]

1.6.5.1. Разделение по центроидам (Nearest Shrunken Centroid)¶

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

Это полезно, например, для удаления зашумленных признаков.

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

1.6.6. Предварительно расчет с помощью ближайших соседей (Nearest Neighbors Transformer)¶

Многие модели scikit-learn опираются на ближайших соседей: Некоторые классификаторы и регрессоры, такие как KNeighborsClassifier и KNeighborsRegressor, а также некоторые методы кластеризации, такие как DBSCAN и SpectralClustering, и некоторые вложения ембединги (embeddings), такие как TSNE и Isomap.

Все эти модели могут внутренне вычислять ближайших соседей, но большинство из них также принимают предварительно вычисленных ближайших соседей sparse graph, как задано в kneighbors_graph и radius_neighbors_graph. В режиме mode='connectivity' эти функции возвращают бинарный разреженный граф смежности, как требуется, например, в SpectralClustering.

При mode='distance' они возвращают разреженный граф расстояний, как требуется, например, в DBSCAN. Чтобы включить эти функции в конвейер scikit-learn, можно также использовать соответствующие классы KNeighborsTransformer и RadiusNeighborsTransformer. Преимущества этого API для разреженных графов многочисленны.

Во-первых, предварительно вычисленный граф может быть использован многократно, например, при изменении какого-либо параметра модели. Это может быть сделано вручную пользователем или с помощью свойств кэширования конвейера (pipeline) scikit-learn:

>>> import tempfile
>>> from sklearn.manifold import Isomap
>>> from sklearn.neighbors import KNeighborsTransformer
>>> from sklearn.pipeline import make_pipeline
>>> from sklearn.datasets import make_regression
>>> cache_path = tempfile.gettempdir()  # we use a temporary folder here
>>> X, _ = make_regression(n_samples=50, n_features=25, random_state=0)
>>> estimator = make_pipeline(
...     KNeighborsTransformer(mode='distance'),
...     Isomap(n_components=3, metric='precomputed'),
...     memory=cache_path)
>>> X_embedded = estimator.fit_transform(X)
>>> X_embedded.shape
(50, 3)

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

Наконец, предварительные вычисления могут быть выполнены пользовательскими моделями для использования различных реализаций, таких как приближенные методы ближайших соседей или реализации со специальными типами данных. Предварительно вычисленный граф соседей sparse graph должен быть отформатирован как в выводе radius_neighbors_graph:

матрица CSR (Сжатое хранение строкой - Compressed Sparse Row) (хотя будут приняты COO (Список координат Coordinate list), CSC (Сжатое хранение столбцов - Compressed Sparse Column) или LIL (Список списков LIL - List of Lists)).
только явное хранение ближайших соседей каждого образца относительно обучающих данных. Сюда должны входить те, которые находятся на расстоянии 0 от точки запроса, включая диагональ матрицы при вычислении ближайших окрестностей между обучающими данными и собой.
в data каждой строки должны храниться расстояния в порядке возрастания (необязательно. Неотсортированные данные будут отсортированы в стабильном порядке, что увеличит вычислительные затраты).
все значения в данных должны быть неотрицательными.
ни в одной строке не должно быть дубликатов индексов (см. https://github.com/scipy/scipy/issues/5807).
если алгоритм, которому передается предварительно вычисленная матрица, использует K-ближайших соседей (в отличие от радиусного соседства), то в каждой строке должно храниться не менее k соседей (или k+1, как объясняется в следующем примечании).

Примечание

Когда запрашивается конкретное количество соседей (с помощью KNeighborsTransformer), определение n_neighbors неоднозначно, поскольку оно может либо включать каждую точку обучения в качестве ее собственного соседа, либо исключать их. Ни тот, ни другой вариант не является идеальным, поскольку их включение приводит к различному количеству несамостоятельных соседей во время обучения и тестирования, а их исключение приводит к различию между fit(X).transform(X) и fit_transform(X), что противоречит API scikit-learn.

В KNeighborsTransformer мы используем определение, которое включает каждую обучающую точку как своего соседа в счет n_neighbors. Однако, по соображениям совместимости с другими моделями, использующими другое определение, при mode == 'distance' будет вычисляться один дополнительный сосед.

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

1.6.7. Анализ компонентов соседства (Neighborhood Components Analysis)¶

Анализ компонентов соседства (Neighborhood Components Analysis NCA, NeighborhoodComponentsAnalysis) - это алгоритм обучения с использованием метрики расстояния, целью которого является повышение точности классификации ближайших соседей по сравнению со стандартным евклидовым расстоянием.

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

На рисунке выше мы рассматриваем некоторые точки из случайно сгенерированного набора данных. Мы сосредоточились на стохастической KNN-классификации точки № 3. Толщина связи между образцом 3 и другой точкой пропорциональна расстоянию между ними и может рассматриваться как относительный вес (или вероятность), который стохастическое правило предсказания ближайших соседей присвоит этой точке. В исходном пространстве у образца 3 много стохастических соседей из разных классов, поэтому правильный класс не очень вероятен. Однако в спроецированном пространстве, выученном с помощью NCA, единственные стохастические соседи, имеющие незначительный вес, принадлежат к тому же классу, что и образец 3, и гарантирует, что последний будет хорошо классифицирован. Подробнее см. в математической формулировке.

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...

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

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

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

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

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

\[\underset{L}{\arg\max} \sum\limits_{i=0}^{N - 1} p_{i}\]

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

\[p_{i}=\sum\limits_{j \in C_i}{p_{i j}}\]

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

\[p_{i j} = \frac{\exp(-||L x_i - L x_j||^2)}{\sum\limits_{k \ne i} {\exp{-(||L x_i - L x_k||^2)}}} , \quad p_{i i} = 0\]

1.6.7.3.1. Расстояние Махаланобиса (Mahalanobis distance)¶

NCA можно рассматривать как обучение метрики (квадратичного) расстояния Махаланобиса:

\[|| L(x_i - x_j)||^2 = (x_i - x_j)^TM(x_i - x_j),\]

где \(M = L^T L\) - симметричная положительная полубесконечная матрица размера (n_features, n_features).

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

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

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

1.6.7.5. Сложность¶

1.6.7.5.1. Обучение¶

NCA хранит матрицу парных расстояний, занимая n_samples ** 2 памяти.

Временная сложность зависит от количества итераций, выполняемых алгоритмом оптимизации. Однако можно задать максимальное количество итераций с помощью аргумента max_iter. Для каждой итерации временная сложность составляет O(n_components x n_samples x min(n_samples, n_features)).

1.6.7.5.2. Преобразование¶

Здесь операция transform возвращает \(LX^T\), поэтому ее временная сложность равна n_components * n_features * n_samples_test. Пространственная сложность операции не добавляется.