Метрический классификатор

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

Текущая версия

Метрический классификатор (similarity-based classifier) — алгоритм классификации, основанный на вычислении оценок сходства между объектами. Простейшим метрическим классификатором является метод ближайших соседей, в котором классифицируемый объект относится к тому классу, которому принадлежит большинство схожих с ним объектов.

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

Разновидности метрических алгоритмов

К метрическим алгоритмам классификации относятся:

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

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

• Кластеризация
• Непараметрическая регрессия
• Многомерное шкалирование
• Визуализация, в частности, Карта сходства и Карта Кохонена

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

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

Беспризнаковое распознавание

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

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

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

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

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

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

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

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

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

Литература

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

Ссылки

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