Если вы поступаете в колледж, вы, вероятно, участвовали как минимум в паре студенческих организаций. Я начинаю свой первый семестр в качестве аспиранта в Рочестерском технологическом институте, и здесь более 350 организаций. Они отсортированы по разным категориям в зависимости от интересов учащегося. Что определяет эти категории и кто говорит, какая организация к какой категории относится? Я уверен, что если бы вы спросили людей, управляющих этими организациями, они бы не сказали, что их организация похожа на чью-то другую, но в некотором смысле вы знаете, что они похожи. Братства и женские клубы одинаково заинтересованы в греческой жизни. Внутренний футбол и клубный теннис имеют одинаковый интерес к спорту. Группа латиноамериканцев и группа американцев азиатского происхождения одинаково заинтересованы в культурном разнообразии. Возможно, если вы измерили мероприятия и собрания, проводимые этими организациями, вы могли бы автоматически определить, к какой категории принадлежит организация. Я воспользуюсь студенческими организациями, чтобы объяснить некоторые концепции k-ближайших соседей, возможно, самого простого алгоритма машинного обучения. Построение модели состоит только из хранения набора обучающих данных. Чтобы сделать прогноз для новой точки данных, алгоритм находит ближайшие точки данных в обучающем наборе данных - его «ближайших соседей».

Как это работает

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

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

Вместо того, чтобы рассматривать только ближайшего соседа, мы можем также рассмотреть произвольное число соседей k. Отсюда и название алгоритма k-ближайших соседей. При рассмотрении более чем одного соседа мы используем голосование для присвоения метки. Это означает, что для каждой контрольной точки мы подсчитываем, сколько соседей принадлежит классу 0 и сколько соседей принадлежит классу 1. Затем мы назначаем класс, который встречается чаще: другими словами, класс большинства среди k-ближайших соседей. В следующем примере используются пять ближайших соседей:

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

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

Реализация с нуля

Вот псевдокод алгоритма kNN для классификации одной точки данных (назовем ее A):

Для каждой точки в нашем наборе данных:

  • рассчитать расстояние между точкой A и текущей точкой
  • отсортировать расстояния в порядке возрастания
  • взять k элементов с наименьшим расстоянием до A
  • найти среди этих элементов самый высокий класс
  • вернуть класс большинства в качестве нашего прогноза для класса A

Код Python для функции находится здесь:

Давайте углубимся в код:

  • Функция knnclassify принимает 4 входа: входной вектор для классификации, называемый A, полная матрица обучающих примеров, называемая dataSet, вектор меток, называемый метки и k - количество ближайших соседей, которые будут использоваться при голосовании. В векторе меток должно быть столько элементов, сколько строк в матрице dataSet.
  • Мы вычисляем расстояния между A и текущей точкой, используя евклидово расстояние.
  • Затем мы сортируем расстояния в порядке возрастания.
  • Затем самые низкие расстояния k используются для голосования по классу A.
  • После этого мы берем словарь classCount и разлагаем его на список кортежей, а затем сортируем кортежи по второму элементу в кортеже. Сортировка выполняется в обратном порядке, поэтому мы получаем от наибольшего к наименьшему.
  • Наконец, мы возвращаем метку наиболее часто встречающегося элемента.

Реализация через Scikit-Learn

Теперь давайте посмотрим, как мы можем реализовать алгоритм kNN с помощью scikit-learn:

Давайте посмотрим на код:

  • Сначала мы генерируем набор данных iris.
  • Затем мы разделяем наши данные на обучающий и тестовый набор, чтобы оценить эффективность обобщения.
  • Затем мы указываем количество соседей (k) до 5.
  • Затем мы подбираем классификатор, используя обучающую выборку.
  • Чтобы делать прогнозы на основе тестовых данных, мы вызываем метод прогноз. Для каждой точки данных в тестовом наборе метод вычисляет ближайших соседей в обучающем наборе и находит среди них наиболее распространенный класс.
  • Наконец, мы оцениваем, насколько хорошо наша модель обобщает, вызывая метод score с тестовыми данными и тестовыми метками.

Запуск модели должен дать нам точность набора тестов 97%, то есть модель правильно предсказала класс для 97% выборок в наборе тестовых данных.

Сильные и слабые стороны

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

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

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

В заключение

Алгоритм k-ближайших соседей - простой и эффективный способ классификации данных. Это пример обучения на основе экземпляров, когда вам нужно иметь под рукой экземпляры данных для выполнения алгоритма машинного обучения. Алгоритм должен иметь полный набор данных; для больших наборов данных это подразумевает большой объем хранилища. Кроме того, вам необходимо рассчитать измерение расстояния для каждого фрагмента данных в базе данных, а это может быть обременительно. Дополнительным недостатком является то, что kNN не дает вам представления о базовой структуре данных; вы не знаете, как выглядит «средний» или «образцовый» экземпляр из каждого класса.

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

Справочные источники:

— —

Если вы хотите следить за моей работой над машинным обучением, вы можете проверить мои Medium и GitHub, а также другие проекты на https://jameskle.com/ . Вы также можете написать мне в Твиттере, написать мне напрямую или найти меня в LinkedIn. Или присоединяйтесь к моей рассылке, чтобы получать мои последние мысли прямо на ваш почтовый ящик!