Метод потенциальных функций
Материал из MachineLearning.
м (→См. также) |
м (→См. также: викификация) |
||
Строка 88: | Строка 88: | ||
* [[Метод парзеновского окна]] | * [[Метод парзеновского окна]] | ||
* [[Сеть радиальных базисных функций]] | * [[Сеть радиальных базисных функций]] | ||
- | |||
+ | == Ссылки == | ||
* [http://en.wikipedia.org/wiki/Nearest_neighbor_search Nearest neighbour search (english wikipedia)] | * [http://en.wikipedia.org/wiki/Nearest_neighbor_search Nearest neighbour search (english wikipedia)] | ||
[[Категория:Метрические алгоритмы классификации]] | [[Категория:Метрические алгоритмы классификации]] | ||
{{Задание|osa|Константин Воронцов|25 января 2010}} | {{Задание|osa|Константин Воронцов|25 января 2010}} |
Версия 23:22, 18 января 2010
Метод потенциальных функций - метрический классификатор, частный случай метода ближайших соседей. Позволяет с помощью простого алгоритма оценивать вес («важность») объектов обучающей выборки при решении задачи классификации.
Содержание |
Постановка задачи классификации
Приведём краткую постановку задачи классификации в общем виде.
Пусть имеется пространство объектов и конечное множество классов . На множестве задана функция расстояния . Каждый объект из относится к некоторому классу из посредством отображения .
Пусть также задана обучающая выборка пар «объект—ответ»: .
Требуется построить алгоритм , который по заданной выборке аппроксимирует отображение .
Идея метода
Общая идея метода иллюстрируется на примере электростатического взаимодействия элементарных частиц. Известно, что потенциал («мера воздействия») электрического поля элементарной заряженной частицы в некоторой точке пространства пропорционален отношению заряда частицы (Q) к расстоянию до частицы (r): .
Метод потенциальных функций реализует полную аналогию указанного выше примера. При классификации объект проверяется на близость к объектам из обучающей выборки. Считается, что объекты из обучающей выборки «заряжены» своим классом, а мера «важности» каждого из них при классификации зависит от его «заряда» и расстояния до классифицируемого объекта.
Основная формула
Перенумеруем объекты обучающей выборки относительно удаления от объекта индексами () — то есть таким образом, что .
В общем виде, алгоритм ближайших соседей есть:
- , где — мера «важности» (вес) объекта из обучающей выборки относительно классифицируемого объекта .
Метод потенциальных функций заключается в выборе в качестве весовой функции следующего вида:
- , где
- — функция, убывающая с ростом аргумента. Константа нужна чтобы избежать проблем с делением на ноль. Для простоты обычно полагают .
- — расстояние от объекта u до i-того ближайшего к u объекта — .
- — параметр. Общий смысл — «ширина потенциала» объекта , . Вводится по аналогии с шириной окна в методе парзеновского окна.
- — параметр. Общий смысл — «заряд» или степень «важности» объекта , при классификации;
Выбор параметров
Как мы уже заметили, в основной формуле метода потенциальных функций используются две группы параметров: и .
«Ширина окна потенциала» выбирается для каждого объекта из эмпирических соображений.
«Важность» объектов выборки можно подобрать, исходя из информации, содержащейся в выборке. Ниже приведён алгоритм, который позволяет «обучать» параметры , то есть подбирать их значения по обучающей выборке .
Алгоритм
Вход
Обучающая выборка из пар «объект-ответ» — .
Описание алгоритма
- Начало. Инициализация: для всех ;
- Повторять:
- Выбрать очередной объект из выборки ;
- Если , то ;
- Выбрать очередной объект из выборки ;
- Пока (то есть пока процесс не стабилизируется);
- Вернуть значения для всех .
Результат
Значения параметров для всех
Преимущества и недостатки
Преимущества метода потенциальных функций:
- Метод прост для понимания и алгоритмической реализации;
- Порождает потоковый алгоритм;
- Хранит лишь часть выборки, следовательно, экономит память.
Недостатки метода:
- Порождаемый алгоритм медленно сходится;
- Параметры и настраиваются слишком грубо;
- Значения параметров зависят от порядка выбора объектов из выборки .
Замечания
Полученные в результате работы алгоритма значения параметров позволяют выделить из обучающей выборки подмножество эталонов — наиболее значимых с точки зрения классификации объектов. Как нетрудно видеть, теоретически на роль эталона подходит любой объект с ненулевой «значимостью» .
См. также
- Классификация
- Метрический классификатор
- Метод ближайших соседей
- Метод парзеновского окна
- Сеть радиальных базисных функций
Ссылки
Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |