Метод потенциальных функций
Материал из MachineLearning.
м (→См. также) |
|||
(28 промежуточных версий не показаны.) | |||
Строка 1: | Строка 1: | ||
- | + | '''Метод потенциальных функций''' - [[метрический классификатор]], частный случай [[Метод ближайших соседей|метода ближайших соседей]]. Позволяет с помощью простого алгоритма оценивать вес («важность») объектов [[Выборка|обучающей выборки]] при решении задачи [[классификация|классификации]]. | |
- | '''Метод потенциальных функций''' - [[метрический классификатор]], частный случай [[Метод ближайших соседей|метода ближайших соседей]]. | + | |
- | == | + | == Постановка задачи классификации == |
+ | |||
+ | Приведём краткую [[задача классификации|постановку задачи классификации]] в общем виде. | ||
+ | |||
+ | Пусть имеется пространство объектов <tex>X</tex> и конечное множество классов <tex>Y</tex>. На множестве <tex>X</tex> задана функция расстояния <tex>\rho: X \times X \to [0, + \infty]</tex>. Каждый объект из <tex>X</tex> относится к некоторому классу из <tex>Y</tex> посредством отображения <tex>y^*:~X \to Y, </tex>. | ||
+ | |||
+ | Пусть также задана [[обучающая выборка]] пар «объект—ответ»: | ||
+ | <tex>X^m = \{(x_1,y_1),\dots,(x_m,y_m)\} \subseteq X \times Y</tex>. | ||
+ | |||
+ | Требуется построить [[алгоритм]] <tex>a(u,X^l)</tex>, который по заданной выборке <tex>X^l</tex> [[аппроксимация|аппроксимирует]] отображение <tex>y^*(u)</tex>. | ||
+ | |||
+ | |||
+ | == Идея метода == | ||
+ | |||
+ | Общая идея метода иллюстрируется на примере электростатического взаимодействия элементарных частиц. Известно, что потенциал («мера воздействия») электрического поля элементарной заряженной частицы в некоторой точке пространства пропорционален отношению ''заряда'' частицы (Q) к расстоянию до частицы (r): <tex>\varphi(r) \sim \frac{Q}{r}</tex>. | ||
+ | |||
+ | Метод потенциальных функций реализует полную аналогию указанного выше примера. При классификации объект проверяется на близость к объектам из обучающей выборки. Считается, что объекты из [[выборка|обучающей выборки]] «заряжены» своим классом, а мера «важности» каждого из них при [[классификация|классификации]] зависит от его «заряда» и расстояния до классифицируемого объекта. | ||
- | |||
== Основная формула == | == Основная формула == | ||
- | <tex> | + | Перенумеруем объекты обучающей выборки <tex>x_i \in X^l</tex> относительно удаления от объекта <tex>u</tex> индексами <tex>x_u^{p}</tex> (<tex>p=\overline{1,l}</tex>) — то есть таким образом, что <tex>\rho(u,x_u^{(1)}) \leq \rho(u,x_u^{(2)}) \leq \dots \leq \rho(u,x_u^{(l)})</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>x_u^{(i)}</tex> из [[Выборка|обучающей выборки]] относительно классифицируемого <br />объекта <tex>u</tex>. | |
- | + | ||
- | |||
- | + | '''Метод потенциальных функций''' заключается в выборе в качестве <tex>w(i,u)</tex> весовой функции следующего вида: | |
+ | :: <tex>w(i,u)=\gamma(x_u^{(i)}) K \left(\frac{\rho(u,x_u{(i)})}{h(x_u{(i)})}\right)</tex>, где | ||
- | + | * <tex>K(r) = \frac{1}{r+a}</tex> — функция, убывающая с ростом аргумента. Константа <tex>a</tex> нужна чтобы избежать проблем с делением на ноль. Для простоты обычно полагают <tex>a=1</tex>. | |
+ | |||
+ | * <tex>\rho(u,x_u{(i)})</tex> — расстояние от объекта u до i-того ближайшего к u объекта — <tex>x_u^{(i)}</tex>. | ||
+ | * <tex>h(x_u{(i)})</tex> — параметр, задающий ''«ширину потенциала»'' объекта <tex>x_i \in X^l</tex>, <tex>\left(i=\overline{1,l}\right)</tex>. Вводится по аналогии с шириной окна в [[Метод парзеновского окна|методе парзеновского окна]]. | ||
+ | |||
+ | * <tex>\gamma(x_u^{(i)})</tex> — параметр, задающий ''«заряд»'', то есть степень «важности» объекта <tex>x_i \in X^l</tex>, <tex>\left(i=\overline{1,l}\right)</tex> при классификации; | ||
== Выбор параметров == | == Выбор параметров == | ||
- | + | Как мы уже заметили, в основной формуле метода потенциальных функций используются две группы параметров: <tex>\{h(x_i)\}</tex> и <tex>\{\gamma(x_i)\}</tex>. | |
+ | |||
+ | «Ширина окна потенциала» <tex>h(x_i)</tex> выбирается для каждого объекта из эмпирических соображений. | ||
+ | |||
+ | «Важность» <tex>\gamma(x_i)</tex> объектов выборки можно подобрать, исходя из информации, содержащейся в выборке. Ниже приведён алгоритм, который позволяет «обучать» параметры <tex>(\gamma(x_1), \dots, \gamma(x_n))</tex>, то есть подбирать их значения по обучающей выборке <tex>X^l</tex>. | ||
+ | |||
+ | === Алгоритм === | ||
+ | |||
+ | ==== Вход и результат ==== | ||
+ | |||
+ | ===== Вход ===== | ||
+ | Обучающая выборка из <tex>l</tex> пар «объект-ответ» — <tex>X^l=\left((x_1,y_1), \dots, (x_l,y_l) \right)</tex>. <br /> | ||
+ | |||
+ | ===== Результат ===== | ||
+ | Значения параметров <tex>\gamma_i \equiv \gamma(x_i)</tex> для всех <tex>i=\overline{1,l}</tex> <br /> <br /> | ||
+ | |||
+ | ==== Описание алгоритма ==== | ||
+ | 1. Инициализация: <tex>\gamma_i:=0</tex> для всех <tex>i=\overline{1,l}</tex>; <br /> | ||
+ | 2. Повторять пункты 3-4, пока <tex>Q(a,X^l) > \varepsilon</tex> (то есть пока процесс не стабилизируется): <br /> | ||
+ | 3. Выбрать очередной объект <tex>x_i</tex> из выборки <tex>X^l</tex>;<br /> | ||
+ | 4. Если <tex>a(x_i) \not= y_i</tex>, то <tex>\gamma_i:=\gamma_i+1</tex>;<br /> | ||
+ | 5. Вернуть значения <tex>\gamma_i</tex> для всех <tex>i=\overline{1,l}</tex>. | ||
+ | |||
+ | |||
+ | == Преимущества и недостатки == | ||
+ | |||
+ | Преимущества метода потенциальных функций: | ||
+ | |||
+ | * Метод прост для понимания и алгоритмической реализации; | ||
+ | * Порождает потоковый алгоритм; | ||
+ | * Хранит лишь часть выборки, следовательно, экономит память. | ||
+ | |||
+ | Недостатки метода: | ||
+ | |||
+ | * Порождаемый алгоритм медленно сходится; | ||
+ | * Параметры <tex>\{\gamma_i\}</tex> и <tex>\{h_i\}</tex> настраиваются слишком грубо; | ||
+ | * Значения параметров <tex>(\gamma_1,\dots,\gamma_l)</tex> зависят от порядка выбора объектов из выборки <tex>X^l</tex>. | ||
+ | |||
+ | == Замечания == | ||
+ | |||
+ | Полученные в результате работы алгоритма значения параметров <tex>(\gamma_1,\dots,\gamma_l)</tex> позволяют выделить из обучающей выборки подмножество [[эталон|эталонов]] — наиболее значимых с точки зрения классификации объектов. Как нетрудно видеть, теоретически на роль эталона подходит любой объект <tex>x_i</tex> с ненулевой «значимостью» <tex>\left(\gamma_i>0 \right)</tex>. | ||
+ | |||
+ | == См. также == | ||
+ | |||
+ | * [[Классификация]] | ||
+ | * [[Метрический классификатор]] | ||
+ | * [[Метод ближайших соседей]] | ||
+ | * [[Метод парзеновского окна]] | ||
+ | * [[Сеть радиальных базисных функций]] | ||
+ | * [[Метод потенциального бустинга]] | ||
- | |||
+ | * [http://en.wikipedia.org/wiki/Nearest_neighbor_search Nearest neighbour search (en.wikipedia.org)] | ||
+ | * [http://www.codenet.ru/progr/alg/ai/htm/gl3_6.php Метод потенциальных функций (www.codenet.ru)] | ||
+ | * [http://www.delphikingdom.com/asp/viewitem.asp?catalogid=1299 Алгоритм распознавания на основе метода потенциальных функций (www.delphikingdom.com) ] | ||
- | + | [[Категория:Метрические алгоритмы классификации]] | |
- | + | {{Задание|osa|Константин Воронцов|27 января 2010}} | |
- | + | ||
- | + | ||
- | + |
Текущая версия
Метод потенциальных функций - метрический классификатор, частный случай метода ближайших соседей. Позволяет с помощью простого алгоритма оценивать вес («важность») объектов обучающей выборки при решении задачи классификации.
Содержание |
Постановка задачи классификации
Приведём краткую постановку задачи классификации в общем виде.
Пусть имеется пространство объектов и конечное множество классов
. На множестве
задана функция расстояния
. Каждый объект из
относится к некоторому классу из
посредством отображения
.
Пусть также задана обучающая выборка пар «объект—ответ»:
.
Требуется построить алгоритм , который по заданной выборке
аппроксимирует отображение
.
Идея метода
Общая идея метода иллюстрируется на примере электростатического взаимодействия элементарных частиц. Известно, что потенциал («мера воздействия») электрического поля элементарной заряженной частицы в некоторой точке пространства пропорционален отношению заряда частицы (Q) к расстоянию до частицы (r): .
Метод потенциальных функций реализует полную аналогию указанного выше примера. При классификации объект проверяется на близость к объектам из обучающей выборки. Считается, что объекты из обучающей выборки «заряжены» своим классом, а мера «важности» каждого из них при классификации зависит от его «заряда» и расстояния до классифицируемого объекта.
Основная формула
Перенумеруем объекты обучающей выборки относительно удаления от объекта
индексами
(
) — то есть таким образом, что
.
В общем виде, алгоритм ближайших соседей есть:
, где
— мера «важности» (вес) объекта
из обучающей выборки относительно классифицируемого
объекта.
Метод потенциальных функций заключается в выборе в качестве весовой функции следующего вида:
-
, где
-
-
— функция, убывающая с ростом аргумента. Константа
нужна чтобы избежать проблем с делением на ноль. Для простоты обычно полагают
.
-
— расстояние от объекта u до i-того ближайшего к u объекта —
.
-
— параметр, задающий «ширину потенциала» объекта
,
. Вводится по аналогии с шириной окна в методе парзеновского окна.
-
— параметр, задающий «заряд», то есть степень «важности» объекта
,
при классификации;
Выбор параметров
Как мы уже заметили, в основной формуле метода потенциальных функций используются две группы параметров: и
.
«Ширина окна потенциала» выбирается для каждого объекта из эмпирических соображений.
«Важность» объектов выборки можно подобрать, исходя из информации, содержащейся в выборке. Ниже приведён алгоритм, который позволяет «обучать» параметры
, то есть подбирать их значения по обучающей выборке
.
Алгоритм
Вход и результат
Вход
Обучающая выборка из пар «объект-ответ» —
.
Результат
Значения параметров для всех
Описание алгоритма
1. Инициализация:для всех
;
2. Повторять пункты 3-4, пока(то есть пока процесс не стабилизируется):
3. Выбрать очередной объектиз выборки
;
4. Если, то
;
5. Вернуть значениядля всех
.
Преимущества и недостатки
Преимущества метода потенциальных функций:
- Метод прост для понимания и алгоритмической реализации;
- Порождает потоковый алгоритм;
- Хранит лишь часть выборки, следовательно, экономит память.
Недостатки метода:
- Порождаемый алгоритм медленно сходится;
- Параметры
и
настраиваются слишком грубо;
- Значения параметров
зависят от порядка выбора объектов из выборки
.
Замечания
Полученные в результате работы алгоритма значения параметров позволяют выделить из обучающей выборки подмножество эталонов — наиболее значимых с точки зрения классификации объектов. Как нетрудно видеть, теоретически на роль эталона подходит любой объект
с ненулевой «значимостью»
.
См. также
- Классификация
- Метрический классификатор
- Метод ближайших соседей
- Метод парзеновского окна
- Сеть радиальных базисных функций
- Метод потенциального бустинга
- Nearest neighbour search (en.wikipedia.org)
- Метод потенциальных функций (www.codenet.ru)
- Алгоритм распознавания на основе метода потенциальных функций (www.delphikingdom.com)
![]() | Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |