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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Выбор параметров)
м (См. также)
 
(25 промежуточных версий не показаны.)
Строка 1: Строка 1:
-
{{Задание|osa|Константин Воронцов|25 января 2010}}
+
'''Метод потенциальных функций''' - [[метрический классификатор]], частный случай [[Метод ближайших соседей|метода ближайших соседей]]. Позволяет с помощью простого алгоритма оценивать вес («важность») объектов [[Выборка|обучающей выборки]] при решении задачи [[классификация|классификации]].
-
'''Метод потенциальных функций''' - [[метрический классификатор]], частный случай [[Метод ближайших соседей|метода ближайших соседей]]. Позволяет с помощью простого алгоритма оценивать вес («важность») объектов [[Выборка|обучающей выборки]] при решении задачи классификации.
+
-
== Введение ==
+
== Постановка задачи классификации ==
-
Общая идея метода иллюстрируется на примере электростатического взаимодействия элементарных частиц. Известно, что потенциал («мера воздействия») электрического поля элементарной заряженной частицы в некоторой точке пространства пропорционален отношению ''заряда'' частицы (Q) к расстоянию до частицы (r): <tex>\varphi(r) \sim \frac{Q}{r}</tex>.
+
Приведём краткую [[задача классификации|постановку задачи классификации]] в общем виде.
 +
Пусть имеется пространство объектов <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>.
-
== Основная формула ==
 
-
Пусть имеется пространство объектов <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>u \in X</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>.
+
Общая идея метода иллюстрируется на примере электростатического взаимодействия элементарных частиц. Известно, что потенциал («мера воздействия») электрического поля элементарной заряженной частицы в некоторой точке пространства пропорционален отношению ''заряда'' частицы (Q) к расстоянию до частицы (r): <tex>\varphi(r) \sim \frac{Q}{r}</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)</tex> весовой функции следующего вида:
:: <tex>w(i,u)=\gamma(x_u^{(i)}) K \left(\frac{\rho(u,x_u{(i)})}{h(x_u{(i)})}\right)</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>\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>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>i=\overline{1,l}</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_i)\}</tex> и <tex>\{h(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>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>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 />
 
-
1. Начало. Инициализация: <tex>\gamma_i:=0</tex> для всех <tex>i=\overline{1,l}</tex>; <br />
 
-
2. Повторять {<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>Q(a,X^l) > \varepsilon</tex> (то есть пока процесс не стабилизируется).<br />
 
== Преимущества и недостатки ==
== Преимущества и недостатки ==
Строка 61: Строка 79:
* Параметры <tex>\{\gamma_i\}</tex> и <tex>\{h_i\}</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^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}}

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

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


Содержание

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

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

Пусть имеется пространство объектов 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)}.
  • \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. Инициализация: \gamma_i:=0 для всех i=\overline{1,l}; 
2. Повторять пункты 3-4, пока Q(a,X^l) > \varepsilon (то есть пока процесс не стабилизируется):
3. Выбрать очередной объект x_i из выборки X^l;
4. Если a(x_i) \not= y_i, то \gamma_i:=\gamma_i+1;
5. Вернуть значения \gamma_i для всех i=\overline{1,l}.


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

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

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

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

  • Порождаемый алгоритм медленно сходится;
  • Параметры \{\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 в учебном процессе.


Личные инструменты