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

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

Принцип, лежащий в основе методов ближайшего соседа, состоит в том, чтобы найти предопределенное количество обучающих выборок, ближайших по расстоянию к новой точке, и предсказать метку по ним. Количество выборок может быть заданной пользователем константой (обучение k-ближайшего соседа) или изменяться в зависимости от локальной плотности точек (обучение соседей на основе радиуса). Расстояние, как правило, может быть любой метрической мерой: стандартное евклидово расстояние является наиболее распространенным выбором. Соседи на основе методов известны как не-обобщающего машины методы обучения, так как они просто «вспомнить» все его подготовки данных (возможно , превращается в быструю индексной структуры , такие как Tree мячем или KD Tree ).

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

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

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

1.6.1. Неконтролируемые ближайшие соседи

NearestNeighbors реализует неконтролируемое обучение ближайших соседей. Он действует как единый интерфейс для трех различных ближайших соседей алгоритмов: BallTreeKDTree и грубая сила алгоритма , основанной на рутинах в 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-ближайших соседей. Такой разреженный граф является полезным в различных обстоятельствах , которые делают использование пространственных отношений между точками для неконтролируемого обучения: в частности, см. IsomapLocallyLinearEmbedding, и 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 для получения дополнительной информации о параметрах, доступных для поиска ближайших соседей, включая спецификацию стратегий запросов, метрики расстояния и т. Д. Список доступных метрик см. В документации DistanceMetric класса.

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’ назначает веса, обратно пропорциональные расстоянию от точки запроса. В качестве альтернативы может быть предоставлена ​​определяемая пользователем функция расстояния, которая будет использоваться для вычисления весов.

Использование ближайших соседей с несколькими выходами для регрессии демонстрируется в завершении Face с оценками с несколькими выходами . В этом примере входы X — это пиксели верхней половины граней, а выходы Y — пиксели нижней половины этих граней.

Примеры:

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

1.6.4.1. Грубая сила

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

1.6.4.2. KD Tree

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

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

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

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

Шаровое дерево рекурсивно делит данные на узлы, определяемые центроидом. $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).
    • Время запроса грубой силы увеличивается по мере того, как $O[DN]$
    • Время запроса дерева шара растет примерно как $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≤D$ многообразия, на котором лежат данные, которое может быть линейно или нелинейно вложено в пространство параметров. Разреженность относится к степени, в которой данные заполняют пространство параметров (это следует отличать от концепции, используемой в «разреженных» матрицах. Матрица данных может не иметь нулевых записей, но структура может быть «разреженной» в этом смысл).
    • Время запроса грубой силы не зависит от структуры данных.
    • Шаровые дерево и KD дерево раз запроса могут быть в значительной степени зависят от структуры данных. В общем, более разреженные данные с меньшей внутренней размерностью приводят к более быстрому времени запроса. Поскольку внутреннее представление дерева KD выровнено с осями параметров, оно, как правило, не демонстрирует таких улучшений, как дерево шариков для произвольно структурированных данных.

      Наборы данных, используемые в машинном обучении, обычно очень структурированы и очень хорошо подходят для древовидных запросов.
  • количество соседей $k$ запрошен для точки запроса.
    • Время запроса грубой силы в значительной степени не зависит от значения $k$
    • Время запроса Ball tree и KD tree будет медленнее, чемkувеличивается. Это связано с двумя эффектами: во-первых, большимkприводит к необходимости поиска большей части пространства параметров. Во-вторых, используя $k>1$ требует внутренней организации очереди результатов по мере обхода дерева.

      В виде $k$ становится большим по сравнению с $N$, возможность обрезать ветви в древовидном запросе снижается. В этой ситуации запросы методом грубой силы могут быть более эффективными.
  • количество точек запроса. И для дерева шаров, и для дерева 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

Как отмечалось выше, для небольших размеров выборки поиск методом перебора может быть более эффективным, чем запрос на основе дерева. Этот факт учитывается в дереве шаров и дереве KD за счет внутреннего переключения на поиск методом грубой силы внутри листовых узлов. Уровень этого переключателя можно указать с помощью параметра 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.5. Ближайший классификатор центроидов

Классификатор NearestCentroid представляет собой простой алгоритм , который представляет каждый класс, центр тяжести его членов. По сути, это делает его похожим на фазу обновления метки KMeans алгоритма. У него также нет параметров для выбора, что делает его хорошим базовым классификатором. Однако он страдает от невыпуклых классов, а также когда классы имеют резко разные дисперсии, поскольку предполагается одинаковая дисперсия во всех измерениях. См. Раздел «Линейный дискриминантный анализ ( LinearDiscriminantAnalysis)» и «Квадратичный дискриминантный анализ» ( QuadraticDiscriminantAnalysis) для более сложных методов, которые не делают этого предположения. Использовать значение по умолчанию 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. Ближайший усохший центроид

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

В приведенном ниже примере использование небольшого порога усадки увеличивает точность модели с 0,81 до 0,82.

Примеры:

1.6.6. Трансформатор ближайших соседей

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

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

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

>>> from sklearn.manifold import Isomap
>>> from sklearn.neighbors import KNeighborsTransformer
>>> from sklearn.pipeline import make_pipeline
>>> estimator = make_pipeline(
...     KNeighborsTransformer(n_neighbors=5, mode='distance'),
...     Isomap(neighbors_algorithm='precomputed'),
...     memory='/path/to/cache')

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

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

  • матрица CSR (хотя COO, CSC или LIL будут приняты).
  • только явно хранить ближайшие окрестности каждой выборки относительно обучающих данных. Это должно включать те, которые находятся на расстоянии 0 от точки запроса, включая диагональ матрицы при вычислении ближайших окрестностей между обучающими данными и самим собой.
  • каждая строка data должна хранить расстояние в порядке возрастания (необязательно. Несортированные данные будут стабильно отсортированы, что приведет к дополнительным вычислительным затратам).
  • все значения в данных должны быть неотрицательными.
  • ни indices в одной строке не должно быть дубликатов (см. 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. Анализ компонентов окружения

Анализ компонентов соседства (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) и анализа соседних компонентов (NeighborhoodComponentsAnalysis) в наборе данных Digits, наборе данных с размером $n_{samples}=1797$ а также $n_{features}=64$. Набор данных разделяется на обучающий и тестовый набор равного размера, а затем стандартизируется. Для оценки точность классификации 3-х ближайших соседей вычисляется по 2-мерным прогнозируемым точкам, найденным каждым методом. Каждая выборка данных принадлежит к одному из 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_{ij}$ — 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. Расстояние Махаланобиса

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 . Для метода оптимизации в настоящее время используется scipy L-BFGS-B с вычислением полного градиента на каждой итерации, чтобы избежать настройки скорости обучения и обеспечить стабильное обучение.

См. Примеры ниже и строку документации 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. Операция не требует дополнительной космической сложности.

Рекомендации:

  1. «Анализ соседних компонентов» , Дж. Голдбергер, С. Роуис, Дж. Хинтон, Р. Салахутдинов, Достижения в системах обработки нейронной информации, Vol. 17 мая 2005 г., стр. 513-520.
  2. Запись в Википедии об анализе компонентов соседства