Метод потенциальных функций
Материал из MachineLearning.
Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
Метод потенциальных функций - метрический классификатор, частный случай метода ближайших соседей. Позволяет с помощью простого алгоритма оценивать вес («важность») объектов обучающей выборки при решении задачи классификации.
Содержание |
Введение
Общая идея метода иллюстрируется на примере электростатического взаимодействия элементарных частиц. Известно, что потенциал («мера воздействия») электрического поля элементарной заряженной частицы в некоторой точке пространства пропорционален отношению заряда частицы (Q) к расстоянию до частицы (r): .
Основная формула
Пусть имеется пространство объектов с заданной метрикой и множество ответов . Пусть задана обучающая выборка пар «объект—ответ» .
Пусть также имеется классифицируемый объект .
Перенумеруем объекты обучающей выборки относительно удаления от объекта индексами () – то есть таким образом, что .
В общем виде, алгоритм ближайших соседей есть:
- , где – мера «важности» (вес) объекта из обучающей выборки относительно классифицируемого объекта .
Метод потенциальных функций заключается в выборе в качестве весовой функции следующего вида:
- , где
- . Константа нужна чтобы избежать проблем с делением на ноль. Для простоты обычно полагают .
- – расстояние от объекта u до i-того ближайшего к u объекта – .
- – параметр. Общий смысл – «потенциал» объекта , ;
- – параметр. Общий смысл – «ширина потенциала» объекта , . Вводится по аналогии с шириной окна в методе парзеновского окна.
Выбор параметров
Как мы уже заметили, в основной формуле метода потенциальных функций используются две группы параметров: и .
Ниже приведён алгоритм, который позволяет «обучать» параметры , то есть подбирать их значения по обучающей выборке .
Вход: Обучающая выборка из пар «объект-ответ» – .
Выход: Значения параметров для всех
1. Начало. Инициализация: для всех ;
2. Повторять {
3. Выбрать очередной объект из выборки ;
4. Если , то ;
5. } пока (то есть пока процесс не стабилизируется).
Преимущества и недостатки
Преимущества метода потенциальных функций:
- Метод прост для понимания и алгоритмической реализации;
- Порождает потоковый алгоритм;
- Хранит лишь часть выборки, следовательно, экономит память.
Недостатки метода:
- Порождаемый алгоритм медленно сходится;
- Параметры и настраиваются слишком грубо;
- Значения параметров зависят от порядка выбора объектов из выборки .