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

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

Версия от 21:07, 22 сентября 2008; Vokov (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

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

Введение

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

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

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

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

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

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

Пусть задана обучающая выборка пар «объект—ответ» $X^m = \{(x_1,y_1),\dots,(x_m,y_m)\}$ .

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

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

$\rho(u,x_{1; u}) \leq \rho(u,x_{2; u}) \leq \cdots \leq \rho(u,x_{m; u}),$

где через $x_{i; u}$ обозначается тот объект обучающей выборки, который является $i$ -м соседом объекта $u$ . Аналогичное обозначение введём и для ответа на $i$ -м соседе: $y_{i; u}$ . Таким образом, произвольный объект $u$ порождает свою перенумерацию выборки.

В наиболее общем виде алгоритм ближайших соседей есть

$a(u) = \mathrm{arg}\max_{y\in Y} \sum_{i=1}^m \bigl[ x_{i; u}=y \bigr] w(i,u),$

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

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

$w(i,u) = [i=1]$ — простейший метод ближайшего соседа;
$w(i,u) = [i\leq k]$ — метод $k$ ближайших соседей;
$w(i,u) = [i\leq k] q^i$ — метод $k$ экспоненциально взвешенных ближайших соседей, где предполагается $q < 1$ ;
$w(i,u) = K\biggl(\frac{\rho(u,x_{i; u})}{h}\biggr)$ — метод парзеновского окна фиксированной ширины $h$ ;
$w(i,u) = K\biggl(\frac{\rho(u,x_{i; u})}{\rho(u,x_{k+1; u})}\biggr)$ — метод парзеновского окнапеременной ширины;
$w(i,u) = K\biggl(\frac{\rho(u,x_{i; u})}{h(x_{i; u})}\biggr)$ — метод потенциальных функций, в котором ширина окна $h(x_i)$ зависит не от классифицируемого объекта, а от обучающего объекта $x_i$ .

Здесь $K(r)$ — заданная неотрицательная монотонно невозрастающая функция на $[0,+\infty)$ , ядро сглаживания.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: классификация и снижение размерности. — М.: Финансы и статистика, 1989.
Журавлев Ю. И., Рязанов В. В., Сенько О. В. «Распознавание». Математические методы. Программная система. Практические применения. — М.: Фазис, 2006. ISBN 5-7036-0108-8.
Загоруйко Н. Г. Прикладные методы анализа данных и знаний. — Новосибирск: ИМ СО РАН, 1999. ISBN 5-86134-060-9.
Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. — Springer, 2001. ISBN 0-387-95284-5.

Ссылки

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

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B1%D0%BB%D0%B8%D0%B6%D0%B0%D0%B9%D1%88%D0%B8%D1%85_%D1%81%D0%BE%D1%81%D0%B5%D0%B4%D0%B5%D0%B9»

Категории: Метрические алгоритмы классификации | Классификация | Машинное обучение | Энциклопедия анализа данных