Метод ближайших соседей
Материал из MachineLearning.
м |
(→Основная формула) |
||
| (11 промежуточных версий не показаны.) | |||
| Строка 1: | Строка 1: | ||
'''Метод ближайших соседей''' — простейший [[метрический классификатор]], основанный на оценивании [[сходство|сходства]] объектов. Классифицируемый объект относится к тому классу, которому принадлежат ближайшие к нему объекты обучающей выборки. | '''Метод ближайших соседей''' — простейший [[метрический классификатор]], основанный на оценивании [[сходство|сходства]] объектов. Классифицируемый объект относится к тому классу, которому принадлежат ближайшие к нему объекты обучающей выборки. | ||
| + | |||
| + | == ? Что означает оператор квадратных скобок в данном контексте: == | ||
| + | * <tex>w(i,u) = [i=1]</tex> — простейший метод ближайшего соседа; | ||
| + | ::<tex>a(u) = \mathrm{arg}\max_{y\in Y} \sum_{i=1}^m \bigl[ x_{i; u}=y \bigr] w(i,u),</tex> | ||
| + | |||
== Введение == | == Введение == | ||
| - | '''Метод ближайшего соседа''' является, пожалуй, самым простым | + | '''Метод ближайшего соседа''' является, пожалуй, самым простым [[алгоритм]]ом [[классификация|классификации]]. |
Классифицируемый объект <tex>x</tex> относится к тому классу <tex>y_i</tex>, | Классифицируемый объект <tex>x</tex> относится к тому классу <tex>y_i</tex>, | ||
которому принадлежит ближайший объект обучающей выборки <tex>x_i</tex>. | которому принадлежит ближайший объект обучающей выборки <tex>x_i</tex>. | ||
| Строка 26: | Строка 31: | ||
== Основная формула == | == Основная формула == | ||
| - | Пусть задана [[обучающая выборка]] пар | + | Пусть задана [[обучающая выборка]] пар «объект-ответ» |
<tex>X^m = \{(x_1,y_1),\dots,(x_m,y_m)\}</tex>. | <tex>X^m = \{(x_1,y_1),\dots,(x_m,y_m)\}</tex>. | ||
| Строка 35: | Строка 40: | ||
Для произвольного объекта <tex>u</tex> расположим | Для произвольного объекта <tex>u</tex> расположим | ||
объекты обучающей выборки <tex>x_i</tex> в порядке возрастания расстояний до <tex>u</tex>: | объекты обучающей выборки <tex>x_i</tex> в порядке возрастания расстояний до <tex>u</tex>: | ||
| - | + | ::<tex>\rho(u,x_{1; u}) \leq \rho(u,x_{2; u}) \leq \cdots \leq \rho(u,x_{m; u}),</tex> | |
| - | <tex>\rho(u,x_{1; u}) \leq \rho(u,x_{2; u}) \leq \cdots \leq \rho(u,x_{m; u}), | + | |
| - | </tex | + | |
| - | + | ||
где через <tex>x_{i; u}</tex> обозначается | где через <tex>x_{i; u}</tex> обозначается | ||
тот объект обучающей выборки, который является <tex>i</tex>-м соседом объекта <tex>u</tex>. | тот объект обучающей выборки, который является <tex>i</tex>-м соседом объекта <tex>u</tex>. | ||
| Строка 44: | Строка 46: | ||
<tex>y_{i; u}</tex>. | <tex>y_{i; u}</tex>. | ||
Таким образом, произвольный объект <tex>u</tex> порождает свою перенумерацию выборки. | Таким образом, произвольный объект <tex>u</tex> порождает свою перенумерацию выборки. | ||
| + | В наиболее общем виде [[алгоритм]] ближайших соседей есть | ||
| + | {{rem| | ||
| + | {{ins|Возможно правильнее: | ||
| + | ::<tex>a(u) = \mathrm{arg}\max_{y\in Y} \sum_{i=1}^m \bigl[ y(x_{i; u})=y \bigr] w(i,u),</tex>}} | ||
| + | }} | ||
| + | ::<tex>a(u) = \mathrm{arg}\max_{y\in Y} \sum_{i=1}^m \bigl[ x_{i; u}=y \bigr] w(i,u),</tex> | ||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
где <tex>w(i,u)</tex> — заданная ''весовая функция'', | где <tex>w(i,u)</tex> — заданная ''весовая функция'', | ||
которая оценивает степень важности <tex>i</tex>-го соседа для классификации объекта <tex>u</tex>. | которая оценивает степень важности <tex>i</tex>-го соседа для классификации объекта <tex>u</tex>. | ||
| Строка 60: | Строка 63: | ||
* <tex>w(i,u) = [i\leq k] q^i</tex> — метод <tex>k</tex> экспоненциально взвешенных ближайших соседей, где предполагается <tex>q < 1</tex>; | * <tex>w(i,u) = [i\leq k] q^i</tex> — метод <tex>k</tex> экспоненциально взвешенных ближайших соседей, где предполагается <tex>q < 1</tex>; | ||
* <tex>w(i,u) = K\biggl(\frac{\rho(u,x_{i; u})}{h}\biggr)</tex> — [[метод парзеновского окна]] фиксированной ширины <tex>h</tex>; | * <tex>w(i,u) = K\biggl(\frac{\rho(u,x_{i; u})}{h}\biggr)</tex> — [[метод парзеновского окна]] фиксированной ширины <tex>h</tex>; | ||
| - | * <tex>w(i,u) = K\biggl(\frac{\rho(u,x_{i; u})}{\rho(u,x_{k+1; u})}\biggr)</tex> — [[метод парзеновского окна]] | + | * <tex>w(i,u) = K\biggl(\frac{\rho(u,x_{i; u})}{\rho(u,x_{k+1; u})}\biggr)</tex> — [[метод парзеновского окна]] переменной ширины; |
* <tex>w(i,u) = K\biggl(\frac{\rho(u,x_{i; u})}{h(x_{i; u})}\biggr)</tex> — [[метод потенциальных функций]], в котором ширина окна <tex>h(x_i)</tex> зависит не от классифицируемого объекта, а от обучающего объекта <tex>x_i</tex>. | * <tex>w(i,u) = K\biggl(\frac{\rho(u,x_{i; u})}{h(x_{i; u})}\biggr)</tex> — [[метод потенциальных функций]], в котором ширина окна <tex>h(x_i)</tex> зависит не от классифицируемого объекта, а от обучающего объекта <tex>x_i</tex>. | ||
| Строка 68: | Строка 71: | ||
=== Выбор числа соседей k === | === Выбор числа соседей k === | ||
| - | При <tex>k=1</tex> алгоритм ближайшего соседа неустойчив к шумовым выбросам: | + | При <tex>k=1</tex> [[алгоритм]] ближайшего соседа неустойчив к шумовым выбросам: |
он даёт ошибочные классификации не только на самих объектах-выбросах, | он даёт ошибочные классификации не только на самих объектах-выбросах, | ||
но и на ближайших к ним объектах других классов. | но и на ближайших к ним объектах других классов. | ||
| - | При <tex>k=m</tex>, наоборот, алгоритм чрезмерно устойчив и вырождается в константу. | + | При <tex>k=m</tex>, наоборот, [[алгоритм]] чрезмерно устойчив и вырождается в константу. |
Таким образом, крайние значения <tex>k</tex> нежелательны. | Таким образом, крайние значения <tex>k</tex> нежелательны. | ||
На практике оптимальное значение параметра <tex>k</tex> | На практике оптимальное значение параметра <tex>k</tex> | ||
| Строка 91: | Строка 94: | ||
Исключение из выборки шумовых и неинформативных объектов даёт несколько преимуществ одновременно: повышается качество классификации, | Исключение из выборки шумовых и неинформативных объектов даёт несколько преимуществ одновременно: повышается качество классификации, | ||
| - | сокращается объём хранимых данных | + | сокращается объём хранимых данных и уменьшается время классификации, затрачиваемое на поиск ближайших эталонов. |
| - | и уменьшается время классификации, затрачиваемое на поиск ближайших эталонов. | + | |
| - | Идея отбора эталонов реализована в | + | Идея отбора эталонов реализована в [[алгоритм]]е STOLP, описанном в книге {{S|Н. Г. Загоруйко}}. |
=== Сверхбольшие выборки === | === Сверхбольшие выборки === | ||
| Строка 118: | Строка 120: | ||
Если признаков слишком много, а расстояние вычисляется как сумма отклонений по отдельным признакам, то возникает [[проклятие размерности|проблема проклятия размерности]]. Суммы большого числа отклонений с большой вероятностью имеют очень близкие значения (согласно [[закон больших чисел|закону больших чисел]]). Получается, что в пространстве высокой размерности все объекты примерно одинаково далеки друг от друга; выбор <tex>k</tex> ближайших соседей становится практически произвольным. | Если признаков слишком много, а расстояние вычисляется как сумма отклонений по отдельным признакам, то возникает [[проклятие размерности|проблема проклятия размерности]]. Суммы большого числа отклонений с большой вероятностью имеют очень близкие значения (согласно [[закон больших чисел|закону больших чисел]]). Получается, что в пространстве высокой размерности все объекты примерно одинаково далеки друг от друга; выбор <tex>k</tex> ближайших соседей становится практически произвольным. | ||
| - | Проблема решается путём отбора относительно | + | Проблема решается путём отбора относительно небольшого числа [[отбор признаков|информативных признаков]] (features selection). |
В [[Алгоритм вычисления оценок|алгоритмах вычисления оценок]] строится множество различных наборов признаков (т.н. опорных множеств), для каждого строится своя функция близости, затем по всем функциям близости производится голосование. | В [[Алгоритм вычисления оценок|алгоритмах вычисления оценок]] строится множество различных наборов признаков (т.н. опорных множеств), для каждого строится своя функция близости, затем по всем функциям близости производится голосование. | ||
| Строка 130: | Строка 132: | ||
Такая «прецедентная» логика хорошо понятна экспертам во многих предметных областях (медицине, геологии, юриспруденции). | Такая «прецедентная» логика хорошо понятна экспертам во многих предметных областях (медицине, геологии, юриспруденции). | ||
| - | Для CBR крайне важно, чтобы число <tex>k</tex> было поменьше, а среди обучающих объектов не было выбросов; иначе классификации теряют свойство интерпретируемости. | + | Для CBR крайне важно, чтобы число <tex>k</tex> было поменьше, а среди обучающих объектов не было выбросов; иначе классификации теряют свойство интерпретируемости. Поэтому в CBR приходится применять и методы отбора эталонов, и оптимизацию метрик. |
| - | Поэтому в CBR приходится применять и методы отбора эталонов, и оптимизацию метрик. | + | |
== Литература == | == Литература == | ||
| Строка 143: | Строка 144: | ||
[[Категория:Метрические алгоритмы классификации]] | [[Категория:Метрические алгоритмы классификации]] | ||
| - | |||
| - | |||
| - | |||
Текущая версия
Метод ближайших соседей — простейший метрический классификатор, основанный на оценивании сходства объектов. Классифицируемый объект относится к тому классу, которому принадлежат ближайшие к нему объекты обучающей выборки.
Содержание |
? Что означает оператор квадратных скобок в данном контексте:
-
— простейший метод ближайшего соседа;
Введение
Метод ближайшего соседа является, пожалуй, самым простым алгоритмом классификации.
Классифицируемый объект относится к тому классу
,
которому принадлежит ближайший объект обучающей выборки
.
Метод ближайших соседей.
Для повышения надёжности классификации объект относится к тому классу, которому принадлежит большинство из его соседей —
ближайших к нему объектов обучающей выборки
.
В задачах с двумя классами число соседей берут нечётным, чтобы не возникало ситуаций неоднозначности, когда одинаковое число соседей принадлежат разным классам.
Метод взвешенных ближайших соседей.
В задачах с числом классов 3 и более нечётность уже не помогает,
и ситуации неоднозначности всё равно могут возникать.
Тогда -му соседу приписывается вес
,
как правило, убывающий с ростом ранга соседа
.
Объект относится к тому классу,
который набирает больший суммарный вес среди
ближайших соседей.
Гипотеза компактности
Все перечисленные методы неявно опираются на одно важное предположение, называемое гипотезой компактности: если мера сходства объектов введена достаточно удачно, то схожие объекты гораздо чаще лежат в одном классе, чем в разных. В этом случае граница между классами имеет достаточно простую форму, а классы образуют компактно локализованные области в пространстве объектов. (Заметим, что в математическом анализе компактными называются ограниченные замкнутые множества. Гипотеза компактности не имеет ничего общего с этим понятием, и должна пониматься скорее в «бытовом» смысле этого слова.)
Основная формула
Пусть задана обучающая выборка пар «объект-ответ»
.
Пусть на множестве объектов задана функция расстояния .
Эта функция должна быть достаточно адекватной моделью сходства объектов.
Чем больше значение этой функции, тем менее схожими являются два объекта
.
Для произвольного объекта расположим
объекты обучающей выборки
в порядке возрастания расстояний до
:
где через обозначается
тот объект обучающей выборки, который является
-м соседом объекта
.
Аналогичное обозначение введём и для ответа на
-м соседе:
.
Таким образом, произвольный объект
порождает свою перенумерацию выборки.
В наиболее общем виде алгоритм ближайших соседей есть
Возможно правильнее:
где — заданная весовая функция,
которая оценивает степень важности
-го соседа для классификации объекта
.
Естественно полагать, что эта функция неотрицательна и не возрастает по
.
По-разному задавая весовую функцию, можно получать различные варианты метода ближайших соседей.
-
-
— метод
ближайших соседей;
-
— метод
;
-
— метод парзеновского окна фиксированной ширины
;
-
— метод парзеновского окна переменной ширины;
-
— метод потенциальных функций, в котором ширина окна
зависит не от классифицируемого объекта, а от обучающего объекта
.
Здесь — заданная неотрицательная монотонно невозрастающая функция на
, ядро сглаживания.
Основные проблемы и способы их решения
Выбор числа соседей k
При алгоритм ближайшего соседа неустойчив к шумовым выбросам:
он даёт ошибочные классификации не только на самих объектах-выбросах,
но и на ближайших к ним объектах других классов.
При
, наоборот, алгоритм чрезмерно устойчив и вырождается в константу.
Таким образом, крайние значения
нежелательны.
На практике оптимальное значение параметра
определяют по критерию скользящего контроля,
чаще всего — методом исключения объектов по одному
(leave-one-out cross-validation).
Отсев шума (выбросов)
Обычно объекты обучения не являются равноценными. Среди них могут находиться типичные представители классов — эталоны. Если классифицируемый объект близок к эталону, то, скорее всего, он принадлежит тому же классу. Ещё одна категория объектов — неинформативные или периферийные. Они плотно окружены другими объектами того же класса. Если их удалить из выборки, это практически не отразится на качестве классификации. Наконец, в выборку может попасть некоторое количество шумовых выбросов — объектов, находящихся «в гуще» чужого класса. Как правило, их удаление только улучшает качество классификации.
Исключение из выборки шумовых и неинформативных объектов даёт несколько преимуществ одновременно: повышается качество классификации, сокращается объём хранимых данных и уменьшается время классификации, затрачиваемое на поиск ближайших эталонов.
Идея отбора эталонов реализована в алгоритме STOLP, описанном в книге Н. Г. Загоруйко.
Сверхбольшие выборки
Метод ближайших соседей основан на явном хранении всех обучающих объектов.
Сверхбольшие выборки () создают несколько чисто технических проблем:
необходимо не только хранить большой объём данных,
но и уметь быстро находить среди них
ближайших соседей произвольного объекта
.
Проблема решается двумя способами:
- выборка прореживается путём выбрасывания неинформативных объектов (см. выше);
- применяются специальные индексы и эффективные структуры данных для быстрого поиска ближайших соседей (например,
-деревья).
Проблема выбора метрики
Это наиболее сложная из всех проблем.
В практических задачах классификации редко встречаются такие «идеальные случаи», когда заранее известна хорошая функция расстояния .
Если объекты описываются числовыми векторами, часто берут евклидову метрику.
Этот выбор, как правило, ничем не обоснован — просто это первое, что приходит в голову.
При этом необходимо помнить, что все признаки должны быть измерены «в одном масштабе», а лучше всего — отнормированы. В противном случае признак с наибольшими числовыми значениями будет доминировать в метрике, остальные признаки, фактически, учитываться не будут.
Однако и нормировка является весьма сомнительной эвристикой, так как остаётся вопрос: «неужели все признаки одинаково значимы и должны учитываться примерно с одинаковым весом?»
Если признаков слишком много, а расстояние вычисляется как сумма отклонений по отдельным признакам, то возникает проблема проклятия размерности. Суммы большого числа отклонений с большой вероятностью имеют очень близкие значения (согласно закону больших чисел). Получается, что в пространстве высокой размерности все объекты примерно одинаково далеки друг от друга; выбор ближайших соседей становится практически произвольным.
Проблема решается путём отбора относительно небольшого числа информативных признаков (features selection). В алгоритмах вычисления оценок строится множество различных наборов признаков (т.н. опорных множеств), для каждого строится своя функция близости, затем по всем функциям близости производится голосование.
Рассуждения на основе прецедентов
Парадигма CBR, case based-reasoning,
возникла как одно из направлений искусственного интеллекта.
В экспертных системах важно не только классифицировать объекты,
но и выдавать пользователю объяснение предлагаемой классификации.
В методе ближайшего соседа такие объяснения выглядят весьма разумно:
«Объект отнесён к классу
потому, что к этому же классу относился близкий объект обучающей выборки
».
Такая «прецедентная» логика хорошо понятна экспертам во многих предметных областях (медицине, геологии, юриспруденции).
Для CBR крайне важно, чтобы число было поменьше, а среди обучающих объектов не было выбросов; иначе классификации теряют свойство интерпретируемости. Поэтому в 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).
