предисловие

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

KNN

Алгоритм k-ближайших соседей — это базовый метод классификации и регрессии.

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

Основная идея KNN также очень проста,Выборка также принадлежит классу, если большинство k ближайших соседей в пространстве признаков принадлежат к определенному классу., как показано на рисунке ниже, когда K=3, предполагается, что узел принадлежит к классу красного эллипса. Возникает ощущение, что «ближе к киновари — красное, ближе к чернильному — черное».

Принцип алгоритма очень прост, но он скрывает некоторые моменты, которые стоит изучить:

Как получить значение k?
Что такое «расстояние» в ближайшем расстоянии и как его лучше вычислить?
Если вы хотите рассчитать расстояние от всех точек модели для данных, производительность будет низкой, когда объем данных велик, как его улучшить?
В некоторых случаях видно, что данные очень близки к определенной точке, но есть еще две точки того же типа, которые находятся далеко, но входят в K. В этом случае не плохо ли классифицировать данные, как один и тот же тип этих двух точек?Разумно?
Что делать, если тренировочные данные несбалансированы?
Что, если размерность широты объекта очень велика (скажем, от 10 до 10 000)?
Как быть с типом (цвет: красный, желтый, синий и зеленый), содержащимся в функции?

Давайте решим некоторые проблемы, связанные с KNN, одну за другой.

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

Выбор гиперпараметра K

Гиперпараметры — это параметры, значения которых задаются перед началом процесса обучения, а не данные параметров, полученные в результате обучения. Например:

Скорость обучения для обучения нейронной сети.

скорость обучения

Гиперпараметры C и сигма для машин опорных векторов.

K из K ближайших соседей.

В KNN чем больше K, тем больше будет разграничение между классами.нежный, чем меньше К, тем большеотвесный. Чем меньше K, тем ниже будет частота ошибок (Error Rate) всей модели (разумеется, тем больше вероятность переобучения).

Дальнейшее чтение:переоснащение

Поскольку KNN обычно используется для классификации, K обычно является нечетным числом для облегчения голосования.

В общем, взаимосвязь между K и ошибкой проверки модели (ошибкой, которую модель применяет к данным проверки) показана на следующем рисунке.

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

Перекрестная проверка

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

The Validation Set Approach
Cross-Validation

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

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

На этом фоне был предложен метод перекрестной проверки (Cross-Validation).

Cross-validation (statistics) - wiki

Вот краткое введение в k-кратную перекрестную проверку, которая относится к сложению всех обучающих данных в k частей, как показано на следующем рисунке, когда количество сгибов k = 5.

Мы используем эти 5 наборов данных проверки и обучения для получения гиперпараметра KNN определенного значения, например, 5 показателей точности K = 1, а затем берем среднее значение показателей точности, чтобы получить уровень точности, когда гиперпараметр K равен 1 . Затем мы продолжаем вычислять точность при K=3 K=5 K=7, и тогда мы можем выбрать гиперпараметр K с наибольшей точностью.

Расстояние в KNN

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

В этой статье кратко представлены некоторые алгоритмы, а подробное введение будет позже в блоге.

Евклидово расстояние

Общее представление расстояния между двумя или более точками $d(x,y) = \sqrt{(x_1-y_1)^2 + (x_2-y_2)^2 + \cdot \cdot \cdot + (x_n-y_n)^2} = \sqrt{\sum_{i=1}^{n}(x_i-y_i)^2}$

Манхэттенское расстояние

Манхэттенское расстояние относится к сумме расстояний, проецируемых вектором на каждую координатную ось. Представьте, что вы едете от одного перекрестка к другому перекрестку в Манхэттене. Является ли расстояние по прямой линии расстоянием между двумя точками? По-видимому, нет, если только вы не сможете пройти через здание. Фактическое расстояние вождения - это «Манхэттенское расстояние», которое является источником названия Манхэттенское расстояние.В то же время, Манхэттенское расстояние также называют расстоянием городского квартала. $d_{12} = \sum_{k=1}^{n}|x_{1k}-y_{2k}|$

Расстояние Махаланобиса

Предложенный индийским статистиком П. К. Махаланобисом, он представляет собой ковариационное расстояние данных. Это эффективный метод для вычисления сходства между двумя наборами неизвестных выборок. В отличие от евклидова расстояния, оно учитывает связь между различными характеристиками (например: часть информации о росте приведет к информации о весе, потому что они связаны между собой), и является масштабно-независимым (масштабно-инвариантным), т.е. не зависит от шкалы измерения. Если ковариационная матрица является единичной матрицей, то расстояние Махаланобиса упрощается до евклидова расстояния.

( (\vec{x} - \vec{y})' {\rm \bf C}^{-1} (\vec{x} - \vec{y}) )^{\frac{1}{2}}

разное

Расстояние Чебышева
Расстояние Минковского
Стандартизированное евклидово расстояние
Расстояние Бхаттачарья
Расстояние Хэмминга
Косинус прилежащего угла (Косинус)
Коэффициент подобия Жаккара
Коэффициент корреляции Пирсона

Оптимизация производительности больших данных

Из принципа легко понять, что временная сложность самого простого алгоритма KNN составляет O (N), потому что для определенных данных он должен вычислять расстояние от всех точек в модели. Есть ли способ оптимизировать эту часть производительности? Здесь в основном два метода.

K-d tree

Деревья K-d — замечательное изобретение, позволяющее ?(?log?) (ожидаемое) время поиска ? ближайших точек к некоторой точке ?. Это чрезвычайно полезно, особенно в тех случаях, когда ?(?) время поиска уже не поддается обработке.

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

Подробности можно увидетьHow does a k-d tree find the K nearest neighbors?

Обратите внимание, что дерево K-D экспоненциально сложно для широты данных d, поэтому оно подходит для использования только тогда, когда широта данных мала.

Чувствительность к местности Hasing (LSH)

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

Так что LSH не может гарантировать определенную точность

Итак, как вы вставляете его, чтобы убедиться, чтоУзлы с близкими расстояниями имеют высокую вероятность попадания в один и тот же ковш.Шерстяная ткань? Детали не вводятся слишком много, я нашел статью, в которой в качестве примера используется сходство документов.статья, читатель может узнать об этом больше.

Важность образцов

В некоторых случаях видно, что данные очень близки к определенной точке, но есть еще две точки того же типа, которые находятся далеко, но входят в K. В этом случае не плохо ли классифицировать данные, как один и тот же тип этих двух точек?Разумно.

Например, на рисунке ниже, когда K=3, красная точка будет отнесена к категории «Предложение», но на самом деле эта точка может больше подходить для классификации как «Нет предложения».

Для решения этой проблемы существует метод Distance-weighted ближайший сосед. Основная идея состоит в том, чтобы позволить точкам, расположенным близко друг к другу, получить больший вес.

Kernelized KNN

stats.stackExchange.com/questions/4…

Сценарии применения KNN

Woohoo. Quora.com/what-are-in…

использованная литература

woohoo.data science.com/blog/IMBA…

zhuanlan.zhihu.com/p/25994179

zhuanlan.zhihu.com/p/30425907

Woohoo.Со слов аналитиков vi.com/blog/2018/0…

zhuanlan.zhihu.com/p/24825503

blog.CSDN.net/V_July_V/AR…

Woohoo.YouTube.com/watch?V=_ee…

Woohoo Quora.com/how-does-ah-ah-…

к data science.com/understand i…

stats.stackExchange.com/questions/4…

Woohoo. Quora.com/what-are-in…