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