Метод потенциальных функций
Материал из MachineLearning.
(→Выбор параметров) |
(переработка) |
||
Строка 1: | Строка 1: | ||
{{Задание|osa|Константин Воронцов|25 января 2010}} | {{Задание|osa|Константин Воронцов|25 января 2010}} | ||
- | '''Метод потенциальных функций''' - [[метрический классификатор]], частный случай [[Метод ближайших соседей|метода ближайших соседей]]. | + | '''Метод потенциальных функций''' - [[метрический классификатор]], частный случай [[Метод ближайших соседей|метода ближайших соседей]]. Позволяет с помощью простого алгоритма оценивать вес («важность») объектов [[Выборка|обучающей выборки]] при решении задачи классификации. |
== Введение == | == Введение == | ||
- | Общая идея метода иллюстрируется на примере электростатического взаимодействия элементарных частиц. Известно, что потенциал электрического поля элементарной заряженной частицы в некоторой точке пространства пропорционален отношению ''заряда'' частицы (Q) к расстоянию до частицы (r): <tex>\varphi(r) \sim \frac{Q}{r}</tex> | + | Общая идея метода иллюстрируется на примере электростатического взаимодействия элементарных частиц. Известно, что потенциал («мера воздействия») электрического поля элементарной заряженной частицы в некоторой точке пространства пропорционален отношению ''заряда'' частицы (Q) к расстоянию до частицы (r): <tex>\varphi(r) \sim \frac{Q}{r}</tex>. |
+ | |||
+ | |||
+ | |||
== Основная формула == | == Основная формула == | ||
+ | Пусть имеется пространство объектов <tex>X</tex> с заданной метрикой <tex>\rho: X \times X \to R</tex> и множество ответов <tex>Y</tex>. | ||
+ | Пусть задана [[обучающая выборка]] пар «объект—ответ» | ||
+ | <tex>X^m = \{(x_1,y_1),\dots,(x_m,y_m)\} \subseteq X \times Y</tex>. | ||
- | <tex> | + | Пусть также имеется классифицируемый объект <tex>u \in X</tex>. |
- | * <tex>K(r) = \frac{1}{r+a}</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> из [[Выборка|обучающей выборки]] относительно классифицируемого объекта <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>\rho(u,x_u{(i)})</tex> – расстояние от объекта u до i-того ближайшего к u объекта – <tex>x_u^{(i)}</tex>. | ||
- | * <tex>\gamma(x_u^{(i)})</tex> – параметр; | + | * <tex>\gamma(x_u^{(i)})</tex> – параметр. Общий смысл – «потенциал» объекта <tex>x_i \in X^l</tex>, <tex>i=\overline{1,l}</tex>; |
- | * <tex>h(x_u{(i)})</tex> – параметр. | + | * <tex>h(x_u{(i)})</tex> – параметр. Общий смысл – «ширина потенциала» объекта <tex>x_i \in X^l</tex>, <tex>i=\overline{1,l}</tex>. Вводится по аналогии с шириной окна в [[Метод парзеновского окна|методе парзеновского окна]]. |
- | + | ||
- | + | ||
Строка 26: | Строка 38: | ||
Как мы уже заметили, в основной формуле метода потенциальных функций используются две группы параметров: | Как мы уже заметили, в основной формуле метода потенциальных функций используются две группы параметров: | ||
* <tex>\gamma(x_i)</tex> – «потенциал» объекта <tex>x_i \in X^l</tex>, <tex>i=\overline{1,l}</tex> | * <tex>\gamma(x_i)</tex> – «потенциал» объекта <tex>x_i \in X^l</tex>, <tex>i=\overline{1,l}</tex> | ||
- | * <tex>h(x_i)</tex> – «ширина потенциала» объекта <tex>x_i \in X^l</tex>, <tex>i=\overline{1,l}</tex> – | + | * <tex>h(x_i)</tex> – «ширина потенциала» объекта <tex>x_i \in X^l</tex>, <tex>i=\overline{1,l}</tex> – аналог ширины окна в [[Метод парзеновского окна|методе парзеновского окна]]. |
Ниже приведён алгоритм, который позволяет «обучать» параметры <tex>(\gamma(x_1), \dots, \gamma(x_n))</tex>, то есть подбирать их значения по обучающей выборке <tex>X^l</tex>. | Ниже приведён алгоритм, который позволяет «обучать» параметры <tex>(\gamma(x_1), \dots, \gamma(x_n))</tex>, то есть подбирать их значения по обучающей выборке <tex>X^l</tex>. | ||
- | Вход: Обучающая выборка из <tex>l</tex> | + | Вход: Обучающая выборка из <tex>l</tex> пар «объект-ответ» – <tex>X^l=((x_1,y_1), \dots, (x_l,y_l) )</tex>. <br /> |
- | Выход: Значения параметров <tex>\gamma_i \equiv \gamma(x_i)</tex> для <tex>i=\overline{1,l}</tex> <br /> <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 /> | 1. Начало. Инициализация: <tex>\gamma_i:=0</tex> для всех <tex>i=\overline{1,l}</tex>; <br /> | ||
2. Повторять {<br /> | 2. Повторять {<br /> | ||
Строка 37: | Строка 49: | ||
4. Если <tex>a(x_i) \not= y_i</tex>, то <tex>\gamma_i:=\gamma_i+1</tex>;<br /> | 4. Если <tex>a(x_i) \not= y_i</tex>, то <tex>\gamma_i:=\gamma_i+1</tex>;<br /> | ||
5. } пока <tex>Q(a,X^l) > \varepsilon</tex> (то есть пока процесс не стабилизируется).<br /> | 5. } пока <tex>Q(a,X^l) > \varepsilon</tex> (то есть пока процесс не стабилизируется).<br /> | ||
+ | |||
+ | |||
+ | == Преимущества и недостатки == | ||
+ | |||
+ | Преимущества метода потенциальных функций: | ||
+ | |||
+ | * Метод прост для понимания и алгоритмической реализации; | ||
+ | * Порождает потоковый алгоритм; | ||
+ | * Хранит лишь часть выборки, следовательно, экономит память. | ||
+ | |||
+ | Недостатки метода: | ||
+ | |||
+ | * Порождаемый алгоритм медленно сходится; | ||
+ | * Параметры <tex>\{\gamma_i\}</tex> и <tex>\{h_i\}</tex> настраиваются слишком грубо; | ||
+ | * Значения параметров <tex>(\gamma_1,\dots,\gamma_l)</tex> зависят от порядка выбора объектов из выборки <tex>X^l</tex>. |
Версия 12:41, 3 января 2010
![]() | Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
Метод потенциальных функций - метрический классификатор, частный случай метода ближайших соседей. Позволяет с помощью простого алгоритма оценивать вес («важность») объектов обучающей выборки при решении задачи классификации.
Содержание |
Введение
Общая идея метода иллюстрируется на примере электростатического взаимодействия элементарных частиц. Известно, что потенциал («мера воздействия») электрического поля элементарной заряженной частицы в некоторой точке пространства пропорционален отношению заряда частицы (Q) к расстоянию до частицы (r): .
Основная формула
Пусть имеется пространство объектов с заданной метрикой
и множество ответов
.
Пусть задана обучающая выборка пар «объект—ответ»
.
Пусть также имеется классифицируемый объект .
Перенумеруем объекты обучающей выборки относительно удаления от объекта
индексами
(
) – то есть таким образом, что
.
В общем виде, алгоритм ближайших соседей есть:
, где
– мера «важности» (вес) объекта
из обучающей выборки относительно классифицируемого объекта
.
Метод потенциальных функций заключается в выборе в качестве весовой функции следующего вида:
-
, где
-
-
. Константа
нужна чтобы избежать проблем с делением на ноль. Для простоты обычно полагают
.
-
– расстояние от объекта u до i-того ближайшего к u объекта –
.
-
– параметр. Общий смысл – «потенциал» объекта
,
;
-
– параметр. Общий смысл – «ширина потенциала» объекта
,
. Вводится по аналогии с шириной окна в методе парзеновского окна.
Выбор параметров
Как мы уже заметили, в основной формуле метода потенциальных функций используются две группы параметров:
-
– «потенциал» объекта
,
-
– «ширина потенциала» объекта
,
– аналог ширины окна в методе парзеновского окна.
Ниже приведён алгоритм, который позволяет «обучать» параметры , то есть подбирать их значения по обучающей выборке
.
Вход: Обучающая выборка изпар «объект-ответ» –
.
Выход: Значения параметровдля всех
![]()
1. Начало. Инициализация:для всех
;
2. Повторять {
3. Выбрать очередной объектиз выборки
;
4. Если, то
;
5. } пока(то есть пока процесс не стабилизируется).
Преимущества и недостатки
Преимущества метода потенциальных функций:
- Метод прост для понимания и алгоритмической реализации;
- Порождает потоковый алгоритм;
- Хранит лишь часть выборки, следовательно, экономит память.
Недостатки метода:
- Порождаемый алгоритм медленно сходится;
- Параметры
и
настраиваются слишком грубо;
- Значения параметров
зависят от порядка выбора объектов из выборки
.