Алгоритм k ближайших соседей

Содержание

Алгоритм КНН – поиск ближайших соседей

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

  • Алгоритм ленивого обучения – KNN – это алгоритм ленивого обучения, потому что он не имеет специальной фазы обучения и использует все данные для обучения во время классификации.

  • Непараметрический алгоритм обучения – KNN также является непараметрическим алгоритмом обучения, потому что он не предполагает ничего о базовых данных.

Алгоритм ленивого обучения – KNN – это алгоритм ленивого обучения, потому что он не имеет специальной фазы обучения и использует все данные для обучения во время классификации.

Непараметрический алгоритм обучения – KNN также является непараметрическим алгоритмом обучения, потому что он не предполагает ничего о базовых данных.

Работа алгоритма КНН

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

Шаг 1 – Для реализации любого алгоритма нам нужен набор данных. Таким образом, во время первого шага KNN мы должны загрузить данные обучения, а также данные испытаний.

Шаг 2 – Далее нам нужно выбрать значение K, то есть ближайшие точки данных. K может быть любым целым числом.

Шаг 3 – Для каждой точки в тестовых данных сделайте следующее –

  • 3.1 – Рассчитайте расстояние между данными испытаний и каждой строкой данных тренировки с помощью любого из методов, а именно: Евклидово, Манхэттенское или Хэмминговское расстояние. Наиболее часто используемый метод расчета расстояния – евклидов.

  • 3.2 – Теперь, основываясь на значении расстояния, отсортируйте их в порядке возрастания.

  • 3.3 – Далее он выберет верхние K строк из отсортированного массива.

  • 3.4 – Теперь он назначит класс контрольной точке на основе наиболее часто встречающегося класса этих строк.

3.1 – Рассчитайте расстояние между данными испытаний и каждой строкой данных тренировки с помощью любого из методов, а именно: Евклидово, Манхэттенское или Хэмминговское расстояние. Наиболее часто используемый метод расчета расстояния – евклидов.

3.2 – Теперь, основываясь на значении расстояния, отсортируйте их в порядке возрастания.

3.3 – Далее он выберет верхние K строк из отсортированного массива.

3.4 – Теперь он назначит класс контрольной точке на основе наиболее часто встречающегося класса этих строк.

Шаг 4 – Конец

пример

Ниже приведен пример для понимания концепции K и работы алгоритма KNN.

Предположим, у нас есть набор данных, который можно построить следующим образом:

Теперь нам нужно классифицировать новую точку данных с черной точкой (в точке 60, 60) в синий или красный класс. Мы предполагаем, что K = 3, то есть он найдет три ближайшие точки данных. Это показано на следующей диаграмме –

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

Реализация в Python

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

КНН как классификатор

Во-первых, начните с импорта необходимых пакетов Python –

import numpy as np import matplotlib.pyplot as plt import pandas as pd

Затем загрузите набор данных iris с веб-ссылки следующим образом:

path = «https://archive.ics.uci.edu/ml/machine-learning-databases/iris/iris.data»

Далее нам нужно назначить имена столбцов для набора данных следующим образом:

headernames =

Теперь нам нужно прочитать набор данных в pandas dataframe следующим образом:

dataset = pd.read_csv(path, names = headernames) dataset.head()

Предварительная обработка данных будет выполняться с помощью следующих строк сценария.

X = dataset.iloc.values y = dataset.iloc.values

Далее, мы разделим данные на разделение на поезда и тесты. Следующий код разделит набор данных на 60% данных обучения и 40% данных тестирования –

from sklearn.model_selection import train_test_split X_train, X_test, y_train, y_test = train_test_split(X, y, test_size = 0.40)

Далее, масштабирование данных будет сделано следующим образом –

from sklearn.preprocessing import StandardScaler scaler = StandardScaler() scaler.fit(X_train) X_train = scaler.transform(X_train) X_test = scaler.transform(X_test)

Далее обучаем модель с помощью класса sklearn класса KNeighborsClassifier следующим образом –

from sklearn.neighbors import KNeighborsClassifier classifier = KNeighborsClassifier(n_neighbors = 8) classifier.fit(X_train, y_train)

Наконец нам нужно сделать прогноз. Это можно сделать с помощью следующего скрипта –

y_pred = classifier.predict(X_test)

Затем распечатайте результаты следующим образом –

from sklearn.metrics import classification_report, confusion_matrix, accuracy_score result = confusion_matrix(y_test, y_pred) print(«Confusion Matrix:») print(result) result1 = classification_report(y_test, y_pred) print(«Classification Report:»,) print (result1) result2 = accuracy_score(y_test,y_pred) print(«Accuracy:»,result2)

Выход

Confusion Matrix: ] Classification Report: precision recall f1-score support Iris-setosa 1.00 1.00 1.00 21 Iris-versicolor 0.70 1.00 0.82 16 Iris-virginica 1.00 0.70 0.82 23 micro avg 0.88 0.88 0.88 60 macro avg 0.90 0.90 0.88 60 weighted avg 0.92 0.88 0.88 60 Accuracy: 0.8833333333333333

КНН в качестве регрессора

Во-первых, начните с импорта необходимых пакетов Python –

import numpy as np import pandas as pd

Затем загрузите набор данных iris с веб-ссылки следующим образом:

path = «https://archive.ics.uci.edu/ml/machine-learning-databases/iris/iris.data»

Далее нам нужно назначить имена столбцов для набора данных следующим образом:

headernames =

Теперь нам нужно прочитать набор данных в pandas dataframe следующим образом:

data = pd.read_csv(url, names = headernames) array = data.values X = array Y = array data.shape output🙁150, 5)

Затем импортируйте KNeighborsRegressor из sklearn, чтобы соответствовать модели –

from sklearn.neighbors import KNeighborsRegressor knnr = KNeighborsRegressor(n_neighbors = 10) knnr.fit(X, y)

Наконец, мы можем найти MSE следующим образом –

print («The MSE is:»,format(np.power(y-knnr.predict(X),2).mean())) The MSE is: 0.12226666666666669

Плюсы и минусы КНН

Pros

  • Это очень простой алгоритм для понимания и интерпретации.

  • Это очень полезно для нелинейных данных, потому что в этом алгоритме нет предположения о данных.

  • Это универсальный алгоритм, поскольку мы можем использовать его как для классификации, так и для регрессии.

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

Это очень простой алгоритм для понимания и интерпретации.

Это очень полезно для нелинейных данных, потому что в этом алгоритме нет предположения о данных.

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

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

Cons

  • Это вычислительно немного дорогой алгоритм, потому что он хранит все данные обучения.

  • Требуется большой объем памяти по сравнению с другими контролируемыми алгоритмами обучения.

  • Прогнозирование медленное в случае большого N.

  • Он очень чувствителен к масштабу данных, а также к несущественным функциям.

Это вычислительно немного дорогой алгоритм, потому что он хранит все данные обучения.

Требуется большой объем памяти по сравнению с другими контролируемыми алгоритмами обучения.

Прогнозирование медленное в случае большого N.

Он очень чувствителен к масштабу данных, а также к несущественным функциям.

Применение КНН

Ниже приведены некоторые из областей, в которых KNN может быть успешно применен:

Банковская система

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

Расчет кредитных рейтингов

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

Политика

С помощью алгоритмов KNN мы можем классифицировать потенциального избирателя по разным классам, таким как «Буду голосовать», «Не буду голосовать», «Буду голосовать за партию» Конгресс «,» Буду голосовать за партию «BJP».

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

Метод ближайших соседей

Материал из MachineLearning.

(Перенаправлено с KNN) Перейти к: навигация, поиск

Метод ближайших соседей — простейший метрический классификатор, основанный на оценивании сходства объектов. Классифицируемый объект относится к тому классу, которому принадлежат ближайшие к нему объекты обучающей выборки.

? Что означает оператор квадратных скобок в данном контексте:

  • — простейший метод ближайшего соседа;

Введение

Метод ближайшего соседа является, пожалуй, самым простым алгоритмом классификации. Классифицируемый объект относится к тому классу , которому принадлежит ближайший объект обучающей выборки .

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

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

Гипотеза компактности

Все перечисленные методы неявно опираются на одно важное предположение, называемое гипотезой компактности: если мера сходства объектов введена достаточно удачно, то схожие объекты гораздо чаще лежат в одном классе, чем в разных. В этом случае граница между классами имеет достаточно простую форму, а классы образуют компактно локализованные области в пространстве объектов. (Заметим, что в математическом анализе компактными называются ограниченные замкнутые множества. Гипотеза компактности не имеет ничего общего с этим понятием, и должна пониматься скорее в «бытовом» смысле этого слова.)

Основная формула

Пусть задана обучающая выборка пар «объект-ответ» .

Пусть на множестве объектов задана функция расстояния . Эта функция должна быть достаточно адекватной моделью сходства объектов. Чем больше значение этой функции, тем менее схожими являются два объекта .

Для произвольного объекта расположим объекты обучающей выборки в порядке возрастания расстояний до :

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

Возможно правильнее:

где — заданная весовая функция, которая оценивает степень важности -го соседа для классификации объекта . Естественно полагать, что эта функция неотрицательна и не возрастает по .

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

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

Здесь — заданная неотрицательная монотонно невозрастающая функция на , ядро сглаживания.

Основные проблемы и способы их решения

Выбор числа соседей k

При алгоритм ближайшего соседа неустойчив к шумовым выбросам: он даёт ошибочные классификации не только на самих объектах-выбросах, но и на ближайших к ним объектах других классов. При , наоборот, алгоритм чрезмерно устойчив и вырождается в константу. Таким образом, крайние значения нежелательны. На практике оптимальное значение параметра определяют по критерию скользящего контроля, чаще всего — методом исключения объектов по одному (leave-one-out cross-validation).

Отсев шума (выбросов)

Обычно объекты обучения не являются равноценными. Среди них могут находиться типичные представители классов — эталоны. Если классифицируемый объект близок к эталону, то, скорее всего, он принадлежит тому же классу. Ещё одна категория объектов — неинформативные или периферийные. Они плотно окружены другими объектами того же класса. Если их удалить из выборки, это практически не отразится на качестве классификации. Наконец, в выборку может попасть некоторое количество шумовых выбросов — объектов, находящихся «в гуще» чужого класса. Как правило, их удаление только улучшает качество классификации.

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

Идея отбора эталонов реализована в алгоритме STOLP, описанном в книге Н. Г. Загоруйко.

Сверхбольшие выборки

Метод ближайших соседей основан на явном хранении всех обучающих объектов. Сверхбольшие выборки () создают несколько чисто технических проблем: необходимо не только хранить большой объём данных, но и уметь быстро находить среди них ближайших соседей произвольного объекта .

Проблема решается двумя способами:

  • выборка прореживается путём выбрасывания неинформативных объектов (см. выше);
  • применяются специальные индексы и эффективные структуры данных для быстрого поиска ближайших соседей (например, -деревья).

Проблема выбора метрики

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

Однако и нормировка является весьма сомнительной эвристикой, так как остаётся вопрос: «неужели все признаки одинаково значимы и должны учитываться примерно с одинаковым весом?»

Если признаков слишком много, а расстояние вычисляется как сумма отклонений по отдельным признакам, то возникает проблема проклятия размерности. Суммы большого числа отклонений с большой вероятностью имеют очень близкие значения (согласно закону больших чисел). Получается, что в пространстве высокой размерности все объекты примерно одинаково далеки друг от друга; выбор ближайших соседей становится практически произвольным.

Проблема решается путём отбора относительно небольшого числа информативных признаков (features selection). В алгоритмах вычисления оценок строится множество различных наборов признаков (т.н. опорных множеств), для каждого строится своя функция близости, затем по всем функциям близости производится голосование.

Рассуждения на основе прецедентов

Парадигма CBR, case based-reasoning, возникла как одно из направлений искусственного интеллекта. В экспертных системах важно не только классифицировать объекты, но и выдавать пользователю объяснение предлагаемой классификации. В методе ближайшего соседа такие объяснения выглядят весьма разумно: «Объект отнесён к классу потому, что к этому же классу относился близкий объект обучающей выборки «. Такая «прецедентная» логика хорошо понятна экспертам во многих предметных областях (медицине, геологии, юриспруденции).

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

Литература

Ссылки

  • Машинное обучение (курс лекций, К.В.Воронцов). МФТИ (2004), ВМиК МГУ (2007).

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

Методология13 комментариевВерсия для печати

Введение

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

Так, подобно приведенному выше примеру, сходство объектов лежит в основе алгоритма k-ближайших соседей (k-nearest neighbor algorithm, KNN). Алгоритм способен выделить среди всех наблюдений k известных объектов (k-ближайших соседей), похожих на новый неизвестный ранее объект. На основе классов ближайших соседей выносится решение касательно нового объекта. Важной задачей данного алгоритма является подбор коэффициента k – количество записей, которые будут считаться близкими.

Алгоритм KNN широко применяется в Data Mining.

Алгоритм KNN

Рассмотрим задачу классификации.

Пусть имеется m наблюдений, каждому из которых соответствует запись в таблице. Все записи принадлежат какому-либо классу. Необходимо определить класс для новой записи.

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

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

  1. d(x,y) ≥ 0, d(x,y) = 0 тогда и только тогда, когда x = y;
  2. d(x,y) = d(y,x);
  3. d(x,z) ≤ d(x,y) + d(y,z), при условии, что точки x, y, z не лежат на одной прямой.

Где x, y, z — векторы признаков сравниваемых объектов.

Для упорядоченных значений атрибутов находится Евклидово расстояние:

$D_E = \sqrt{\sum \limits_{i}^{n}(x_i\,-\,y_i)^2}$,

где n – количество атрибутов.

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

$dd\,(x,\,y)= \begin{cases} 0, \ x=y \\ 1, \ x\neq y \end{cases} $.

Часто перед расчетом расстояния необходима нормализация. Приведем некоторые полезные формулы.

Минимаксная нормализация:

$X^\times = \frac{X\,-\,\min \,\bigl(X\bigr )}{\max \,\bigl(X\bigr )\,-\,\min \,\bigl(X\bigr )}$.

Нормализация с помощью стандартного отклонения:

$X^\times = \frac{X\,-\,X_{cp}}{\sigma_x}$,

где $\sigma_x$ – стандартное отклонение, Xср – среднее значение.

При нахождении расстояния иногда учитывают значимость атрибутов. Она определяется экспертом или аналитиком субъективно, полагаясь на собственный опыт. В таком случае при нахождении расстояния каждый i-ый квадрат разности в сумме умножается на коэффициент Zi. Например, если атрибут A в три раза важнее атрибута B (ZA = 3, ZB = 1), то расстояние будет находиться следующим образом:

$D_E = \sqrt{3 (x_A\,-\,y_A)^2\,+\,(x_B\,-\,y_B)^2}$.

Подобный прием называют растяжением осей (stretching the axes), что позволяет снизить ошибку классификации.

Следует отметить, что если для записи B ближайшем соседом является А, то это не означает, что В – ближайший сосед А. Данная ситуация представлена на рисунке 1. При k = 1 ближайшей для точки B будет точка A, а для A – X. При увеличении коэффициента до k = 7, точка B так же не будет входить в число соседей.

На следующем шаге, когда найдены записи, наиболее похожие на новую, необходимо решить, как они влияют на класс новой записи. Для этого используется функция сочетания (combination function). Одним из основных вариантов такой функции является простое невзвешенное голосование (simple unweighted voting).

Простое невзвешенное голосование

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

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

Но что делать в случае, если несколько классов набрали равное количество голосов? Эту проблему снимает взвешенное голосование (weighted voting).

Взвешенное голосование

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

$votes\,(class) = \sum\limits_{i=1}^{n}\frac{1}{d^2\,(X,\,Y_i )}$,

где d2(X, Yi) – квадрат расстояния от известной записи Yi до новой X, n – количество известных записей класса, для которого рассчитываются голоса, class — наименование класса.

Новая запись соотносится с классом, набравшим наибольшее количество голосов. При этом вероятность того, что несколько классов наберут одинаковые голоса, гораздо ниже. Совершенно очевидно, что при k = 1 новой записи присваивается класс самого ближайшего соседа.

Примеры работы алгоритма KNN

Решим задачу классификации для ирисов (используя данные об ирисах Фишера, которые доступны по ). Имеется набор данных, собранных Р. Фишером, о 150 цветках трех классов: Iris Setosa, Iris Versicolour, Iris Virginica, по 50 записей для каждого. Известна длина и ширина чашелистика и лепестка всех этих ирисов.

Для простоты рассмотрим только два входных поля: длина чашелистика и длина лепестка, а также выходное – класс цветка.

Необходимо определить класс двух цветков со следующими значениями длины чашелистика и лепестка в сантиметрах: 5,3 и 1,6 (первый), 6,1 и 4,8 (второй). На рисунке 2 показано размещение новых (светло-зеленая точка – цветок 1, красная – цветок 2) записей среди уже известных.

d(цветок1, A) $= \sqrt{{\bigl(5,3\,-\,5,3\bigr)}^2\,+\,{\bigl(1,6\,-\,1,5\bigr)}^2 } = \sqrt{0\,+\,0,01 } = 0,1$

d(цветок1, В) $ = \sqrt{{\bigl(5,3\,-\,5,2\bigr)}^2\,+\,{\bigl(1,6\,-\,1,5\bigr)}^2 } = \sqrt{0,01\,+\,0,01 } = 0,141421356$

d(цветок1, C) $= \sqrt{{\bigl(5,3\,-\,5,2\bigr)}^2\,+\,{\bigl(1,6\,-\,1,5\bigr)}^2 } = \sqrt{0,01\,+\,0,01 } = 0,141421356$

Полученные сведения объединим в таблицу 1.

Таблица 1 – 3 ближайших соседа для цветка 1

Теперь определим класс нового цветка. Воспользуемся простым невзвешенным голосованием. Так как все три цветка A, B и C принадлежат к классу Iris-Setosa, то он получает 100% голосов, и первому цветку присваиваем этот класс. Если увеличить (рисунок 3) на диаграмме окрестность около первого цветка, то можно увидеть, что он окружен точками синего цвета, соответствующие цветам класса Iris-Setosa.

Теперь рассмотрим более сложный случай cо вторым цветком.

Зададим k = 3 и предположим, что длина лепестка вдвое важнее длины чашелистика. Ближайшими тремя соседями будут следующие цветки:

A(6,1; 4,7), B(6; 4,8), C(6,2 4,8)

Покажем, чему для них равны расстояния:

d(цветок2, A)$= \sqrt{{\bigl(6,1\,-\,6,1\bigr)}^2\,+\,2\,{\bigl(4,8\,-\,4,7\bigr)}^2 } = \sqrt{0,02 } = 0,141421356$

d(цветок2, B)$= \sqrt{{\bigl(6,1\,-\,6\bigr)}^2\,+\,2\,{\bigl(4,8\,-\,4,8\bigr)}^2 } = \sqrt{0,01 } = 0,1$

d(цветок2, C)$= \sqrt{{\bigl(6,1\,-\,6,2\bigr)}^2\,+\,2\,{\bigl(4,8\,-\,4,8\bigr)}^2 } = \sqrt{0,01 } = 0,1$

В и С – это Iris Virginica, а A – Iris Versicolour.

Объединим полученные сведения в таблицу 2.

Таблица 2 – Три ближайших соседа для цветка 2

Запись Длина чашелистика Длина лепестка Расстояние Класс
Цветок 2 6,1 4,8
A 6,1 4,7 0,14 Iris Versicolour
B 6 4,8 0,1 Iris Virginica
C 6,2 4,8 0,1 Iris Virginica

Рассмотрим взвешенное голосование.

$Votes\,\bigl(IrisVersicolour\bigr) = \frac{1}{{\Bigl(\sqrt{0,02}\Bigr)}^2} = \frac{1}{0,02} = 50$

$Votes\,\bigl(IrisVirginica\bigr) = \frac{1}{0,1^2}\,+\, \frac{1}{0,1^2} = \frac{2}{0,01} = 200$

Так как 200>50, то второй цветок классифицируется как Iris Virginica.

Области применения алгоритма KNN

Алгоритм k-ближайших соседей имеет широкое применение. Например:

  1. Обнаружение мошенничества. Новые случаи мошенничества могут быть похожи на те, которые происходили когда-то в прошлом. Алгоритм KNN может распознать их для дальнейшего рассмотрения.
  2. Предсказание отклика клиентов. Можно определить отклик новых клиентов по данным из прошлого.
  3. Медицина. Алгоритм может классифицировать пациентов по разным показателям, основываясь на данных прошедших периодов.
  4. Прочие задачи, требующие классификацию.

В заключение отметим достоинства и недостатки алгоритма KNN.

Перечислим положительные особенности.

  1. Алгоритм устойчив к аномальным выбросам, так как вероятность попадания такой записи в число k-ближайших соседей мала. Если же это произошло, то влияние на голосование (особенно взвешенное) (при k>2) также, скорее всего, будет незначительным, и, следовательно, малым будет и влияние на итог классификации.
  2. Программная реализация алгоритма относительно проста.
  3. Результат работы алгоритма легко поддаётся интерпретации. Экспертам в различных областях вполне понятна логика работы алгоритма, основанная на нахождении схожих объектов.
  4. Возможность модификации алгоритма, путём использования наиболее подходящих функций сочетания и метрик позволяет подстроить алгоритм под конкретную задачу.

Алгоритм KNN обладает и рядом недостатков. Во-первых, набор данных, используемый для алгоритма, должен быть репрезентативным. Во-вторых, модель нельзя «отделить» от данных: для классификации нового примера нужно использовать все примеры. Эта особенность сильно ограничивает использование алгоритма

Литература

Метод k-ближайших соседей

Метод k-ближайших соседей (K-nearest neighbor)

Разделы: Алгоритмы

Loginom: Кластеризация (обработчик)

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

Число k – это количество соседних объектов в пространстве признаков, которые сравниваются с классифицируемым объектом. Иными словами, если k=10, то каждый объект сравнивается с 10-ю соседями. Метод широко применяется в технологиях Data Mining.

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

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

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

Вопрос. а Если нужно по 3 параметрам например (x,y,z). Делаем просто несколько сравнений типа по (xy) (xz) (yz) ? или есть N мерный вариант? или тут че нить другое надо?
Допустим у нас есть куча живности, у них параметры,
1. рост(длина),
2. вес,
и 3. например функция отвечающая за покрытие животности (Типа вначале гладкая кожа (дельфины например) -> шерсть(коровы->кошачьи->овцы, и т.д.) -> чешуя -> перья -> еще че нить.) ну и эта выражено через линейную функцию например(типа от сложного покрытия к простому).
Ну и мы типа закинули пару сотню зверюх в эту систему чтобы наметить границы животных классов. А потом он уже сам их добавляет например.
кек. Пока писал Нашел ответ на вики.
Алгоритм может быть применим к выборкам с большим количеством атрибутов (многомерным). Для этого перед применением нужно определить функцию дистанции.
Как я понял по расстоянию до ближайшего значения с известным классом для каждого параметра. А там потом сводить это все к единому значению.
(можно даже наверно свои параметры оценки накинуть, например рост и вес в меньшей степени будут влиять на класс нежели тип покрытия).

и там же следом про нормализацию и пределы.
Как раз то что могло бы пригодится для 3го параметра.
Спасиб за интересную инфу.
Самое то на ночь потупить.)
Какую книгу по Машинному обучение и «data mining» посоветовал бы? (RU|EN)
А еще этот метод можно было бы в гейм деве юзать? Например — классическая рпг, Несколько параметров типа статов — а этим методом выдавать Класс к которому ты ближе всего. Не встречал такого?(В «Князе 2» было что то похожее но не это, да и наверно много где, там вроде тупо по двум самым прокачанным статам звание давалось)..
Ох бля. МНого букв получилось..

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *