Метод потенциальных функций

Материал из MachineLearning.

(Различия между версиями)

Текущая версия

Метод потенциальных функций - метрический классификатор, частный случай метода ближайших соседей. Позволяет с помощью простого алгоритма оценивать вес («важность») объектов обучающей выборки при решении задачи классификации.

Содержание

1 Постановка задачи классификации
2 Идея метода
3 Основная формула
4 Выбор параметров
- 4.1 Алгоритм
  - 4.1.1 Вход и результат
    - 4.1.1.1 Вход
    - 4.1.1.2 Результат
  - 4.1.2 Описание алгоритма
5 Преимущества и недостатки
6 Замечания
7 См. также

Постановка задачи классификации

Приведём краткую постановку задачи классификации в общем виде.

Пусть имеется пространство объектов $X$ и конечное множество классов $Y$ . На множестве $X$ задана функция расстояния $\rho: X \times X \to [0, + \infty]$ . Каждый объект из $X$ относится к некоторому классу из $Y$ посредством отображения $y^*:~X \to Y,$ .

Пусть также задана обучающая выборка пар «объект—ответ»: $X^m = \{(x_1,y_1),\dots,(x_m,y_m)\} \subseteq X \times Y$ .

Требуется построить алгоритм $a(u,X^l)$ , который по заданной выборке $X^l$ аппроксимирует отображение $y^*(u)$ .

Идея метода

Общая идея метода иллюстрируется на примере электростатического взаимодействия элементарных частиц. Известно, что потенциал («мера воздействия») электрического поля элементарной заряженной частицы в некоторой точке пространства пропорционален отношению заряда частицы (Q) к расстоянию до частицы (r): $\varphi(r) \sim \frac{Q}{r}$ .

Метод потенциальных функций реализует полную аналогию указанного выше примера. При классификации объект проверяется на близость к объектам из обучающей выборки. Считается, что объекты из обучающей выборки «заряжены» своим классом, а мера «важности» каждого из них при классификации зависит от его «заряда» и расстояния до классифицируемого объекта.

Основная формула

Перенумеруем объекты обучающей выборки $x_i \in X^l$ относительно удаления от объекта $u$ индексами $x_u^{p}$ ( $p=\overline{1,l}$ ) — то есть таким образом, что $\rho(u,x_u^{(1)}) \leq \rho(u,x_u^{(2)}) \leq \dots \leq \rho(u,x_u^{(l)})$ .

В общем виде, алгоритм ближайших соседей есть:

$a(u) = \mathrm{arg}\max_{y\in Y} \sum_{i=1}^m \bigl[ x_{i; u}=y \bigr] w(i,u)$ , где $w(i,u)$ — мера «важности» (вес) объекта $x_u^{(i)}$ из обучающей выборки относительно классифицируемого
объекта $u$ .

Метод потенциальных функций заключается в выборе в качестве $w(i,u)$ весовой функции следующего вида:

$w(i,u)=\gamma(x_u^{(i)}) K \left(\frac{\rho(u,x_u{(i)})}{h(x_u{(i)})}\right)$ , где

$K(r) = \frac{1}{r+a}$ — функция, убывающая с ростом аргумента. Константа $a$ нужна чтобы избежать проблем с делением на ноль. Для простоты обычно полагают $a=1$ .

$\rho(u,x_u{(i)})$ — расстояние от объекта u до i-того ближайшего к u объекта — $x_u^{(i)}$ .

$h(x_u{(i)})$ — параметр, задающий «ширину потенциала» объекта $x_i \in X^l$ , $\left(i=\overline{1,l}\right)$ . Вводится по аналогии с шириной окна в методе парзеновского окна.

$\gamma(x_u^{(i)})$ — параметр, задающий «заряд», то есть степень «важности» объекта $x_i \in X^l$ , $\left(i=\overline{1,l}\right)$ при классификации;

Выбор параметров

Как мы уже заметили, в основной формуле метода потенциальных функций используются две группы параметров: $\{h(x_i)\}$ и $\{\gamma(x_i)\}$ .

«Ширина окна потенциала» $h(x_i)$ выбирается для каждого объекта из эмпирических соображений.

«Важность» $\gamma(x_i)$ объектов выборки можно подобрать, исходя из информации, содержащейся в выборке. Ниже приведён алгоритм, который позволяет «обучать» параметры $(\gamma(x_1), \dots, \gamma(x_n))$ , то есть подбирать их значения по обучающей выборке $X^l$ .

Алгоритм

Вход и результат

Вход

Обучающая выборка из $l$ пар «объект-ответ» — $X^l=\left((x_1,y_1), \dots, (x_l,y_l) \right)$ .

Результат

Значения параметров $\gamma_i \equiv \gamma(x_i)$ для всех $i=\overline{1,l}$

Описание алгоритма

1. Инициализация:  для всех ; 

2. Повторять пункты 3-4, пока  (то есть пока процесс не стабилизируется): 

    3.  Выбрать очередной объект  из выборки ;

    4.  Если , то ;

5. Вернуть значения  для всех .

Преимущества и недостатки

Преимущества метода потенциальных функций:

Метод прост для понимания и алгоритмической реализации;
Порождает потоковый алгоритм;
Хранит лишь часть выборки, следовательно, экономит память.

Недостатки метода:

Порождаемый алгоритм медленно сходится;
Параметры $\{\gamma_i\}$ и $\{h_i\}$ настраиваются слишком грубо;
Значения параметров $(\gamma_1,\dots,\gamma_l)$ зависят от порядка выбора объектов из выборки $X^l$ .

Замечания

Полученные в результате работы алгоритма значения параметров $(\gamma_1,\dots,\gamma_l)$ позволяют выделить из обучающей выборки подмножество эталонов — наиболее значимых с точки зрения классификации объектов. Как нетрудно видеть, теоретически на роль эталона подходит любой объект $x_i$ с ненулевой «значимостью» $\left(\gamma_i>0 \right)$ .

См. также

Данная статья является непроверенным учебным заданием.

Студент: Участник:osa

Преподаватель: Участник:Константин Воронцов

Срок: 27 января 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BF%D0%BE%D1%82%D0%B5%D0%BD%D1%86%D0%B8%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D1%85_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B9»

Категории: Метрические алгоритмы классификации | Непроверенные учебные задания

@@ Строка 23: / Строка 23: @@
 == Основная формула ==
-Перенумеруем объекты обучающей выборки <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>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>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>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>h(x_u{(i)})</tex> – параметр. Общий смысл – «ширина потенциала» объекта <tex>x_i \in X^l</tex>, <tex>\left(i=\overline{1,l}\right)</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>\gamma(x_u^{(i)})</tex> — параметр, задающий ''«заряд»'', то есть степень «важности» объекта <tex>x_i \in X^l</tex>, <tex>\left(i=\overline{1,l}\right)</tex> при классификации;
 == Выбор параметров ==
@@ Строка 47: / Строка 48: @@
 «Важность» <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 />
-.   Начало. Инициализация: <tex>\gamma_i:=0</tex> для всех <tex>i=\overline{1,l}</tex>; <br />
+==== Вход и результат ====
-.   Повторять {<br />
-.1   Выбрать очередной объект <tex>x_i</tex> из выборки <tex>X^l</tex>;<br />
+===== Вход =====
-.2   Если <tex>a(x_i) \not= y_i</tex>, то <tex>\gamma_i:=\gamma_i+1</tex>;<br />
+Обучающая выборка из <tex>l</tex> пар «объект-ответ» — <tex>X^l=\left((x_1,y_1), \dots, (x_l,y_l) \right)</tex>. <br />
-.   } пока <tex>Q(a,X^l) > \varepsilon</tex> (то есть пока процесс не стабилизируется);<br />
-. Вернуть значения <tex>\gamma_i</tex> для всех <tex>i=\overline{1,l}</tex>.
+===== Результат =====
+Значения параметров <tex>\gamma_i \equiv \gamma(x_i)</tex> для всех <tex>i=\overline{1,l}</tex>  <br /> <br />
+==== Описание алгоритма ====
+. Инициализация: <tex>\gamma_i:=0</tex> для всех <tex>i=\overline{1,l}</tex>; <br />
+. Повторять пункты 3-4, пока <tex>Q(a,X^l) > \varepsilon</tex> (то есть пока процесс не стабилизируется): <br />
+.  Выбрать очередной объект <tex>x_i</tex> из выборки <tex>X^l</tex>;<br />
+.  Если <tex>a(x_i) \not= y_i</tex>, то <tex>\gamma_i:=\gamma_i+1</tex>;<br />
+. Вернуть значения <tex>\gamma_i</tex> для всех <tex>i=\overline{1,l}</tex>.
 == Преимущества и недостатки ==
@@ Строка 72: / Строка 82: @@
 == Замечания ==
-Полученные в результате работы алгоритма значения параметров <tex>(\gamma_1,\dots,\gamma_l)</tex> позволяют выделить из обучающей выборки подмножество [[эталон|эталонов]] – наиболее значимых с точки зрения классификации объектов. Как нетрудно видеть, теоретически на роль эталона подходит любой объект <tex>x_i</tex> с ненулевой «значимостью» <tex>\left(\gamma_i>0 \right)</tex>.
+Полученные в результате работы алгоритма значения параметров <tex>(\gamma_1,\dots,\gamma_l)</tex> позволяют выделить из обучающей выборки подмножество [[эталон|эталонов]] — наиболее значимых с точки зрения классификации объектов. Как нетрудно видеть, теоретически на роль эталона подходит любой объект <tex>x_i</tex> с ненулевой «значимостью» <tex>\left(\gamma_i>0 \right)</tex>.
 == См. также ==
@@ Строка 79: / Строка 89: @@
 * [[Метрический классификатор]]
 * [[Метод ближайших соседей]]
 * [[Метод парзеновского окна]]
+* [[Сеть радиальных базисных функций]]
+* [[Метод потенциального бустинга]]
+* [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|Константин Воронцов|25 января 2010}}
+[[Категория:Метрические алгоритмы классификации]]
+{{Задание|osa|Константин Воронцов|27 января 2010}}