Алгоритмы вычисления оценок

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

(Различия между версиями)
Перейти к: навигация, поиск
м («Алгоритмов вычисления оценок» переименована в «Алгоритмы вычисления оценок»: именительный падеж)
м (категория)
 
(3 промежуточные версии не показаны)
Строка 1: Строка 1:
-
<tex>\input graphicx
+
== '''''Алгоритмы вычисления оценок ''''' ==
-
\font\Large = cmr10 scaled \magstep 2
+
-
\font\tiny = cmr10 scaled \magstep 0
+
-
\font\small = cmr10 scaled \magstep 0
+
-
\def\mbox{\hbox}
+
-
\def\textbackslash{$\backslash$}
+
-
\noindent Алгоритмы вычисления оценок
+
----
-
\noindent Алгоритмы вычисления оценок (АВО) были предложены академиком РАН {\bf Ю.И. Журавлевым} в начале 70х годов прошлого века. В их описании были отражены передовые концепции решения задач распознавания.
+
Алгоритмы вычисления оценок (АВО) были предложены академиком РАН Ю.И. Журавлевым в начале 70х годов прошлого века. В их описании были отражены передовые концепции решения задач распознавания.
-
\noindent \underbar{Принципы, использованные в модели АВО:}
+
----
-
\underbar{ }Решение о классификации объекта принимается с помощью анализа оценок близости объекта к классам. За какой класс оценка близости выше -- к тому классу и относят объект. Оценки вычисляет {\bf распознающий оператор}. Классифицирует объекты на основе оценок их близостей к классам {\bf решающее правило}.
+
=== '''''Принципы, использованные в модели АВО.''''' ===
-
При вычислении оценок близости к классам учитывают близость/дальность объекта к эталонным объектам. Близость -- схожесть описаний, малое расстояние между значениями признаков. При этом оценка близости объекта к классу тем выше, чем ближе он к эталонным объектам данного класса и дальше от эталонных объектов других классов.
 
-
Близость распознаваемого объекта S к эталонному $S^t$ определяется на основе расстояний ${\rho }_i\left(a_i\left(S\right),a_i\left(S^t\right)\right),\ \ i=1,2,\dots ,n,$ и формализуется понятием {\bf функция близости}.
+
*Решение о классификации объекта принимается с помощью анализа оценок близости объекта к классам. За какой класс оценка близости выше -- к тому классу и относят объект. Оценки вычисляет распознающий оператор. Классифицирует объекты на основе оценок их близостей к классам решающее правило.
-
\noindent \underbar{Определение модели АВО.}
+
*При вычислении оценок близости к классам учитывают близость/дальность объекта к эталонным объектам. Близость -- схожесть описаний, малое расстояние между значениями признаков. При этом оценка близости объекта к классу тем выше, чем ближе он к эталонным объектам данного класса и дальше от эталонных объектов других классов.
-
\noindent В этой модели алгоритм распознавания представляется в виде суперпозиции распознающего оператора (РО) B и решающего правила (РП) C: $A=B\cdot C.$ Пусть необходимо классифицировать набор $\widetilde{S_q.}\ $Распознающий оператор B вычисляет {\bf оценки принадлежности объекта }$S_i${\bf к классу }$K_i$ по формуле
+
*Близость распознаваемого объекта S к эталонному <tex>$S^t$</tex> определяется на основе расстояний <tex>${\rho }_i\left(a_i\left(S\right),a_i\left(S^t\right)\right),\ \ i=1,2,\dots ,n,$</tex> и формализуется понятием функция близости.
-
$$Г_{ij}\left[B\right]={{x_1}\over {N_1(j)}}\sum_{\Omega \in {\Omega }_A}{\sum_{S^t\in \widetilde{K^1_j}}{w^tw\left(\Omega \right)B^{\tilde{e}}_{\Omega }\left(S^t,S_i\right)+}}{{x_0}\over {N_0(j)}}\sum_{\Omega \in {\Omega }_A}{\sum_{S^t\in \widetilde{K^0_j}}{w^tw\left(\Omega \right){[1-B}^{\tilde{e}}_{\Omega }\left(S^t,S_i\right)],}}$$
+
----
-
где $x_0,x_1\in \left\{0,1\right\};;\ \ $
+
-
$$N_0\left(j\right),N_1\left(j\right)-некоторые\ нормирующие\ множители,$$
 
-
$$\ {\Omega }_A-\ множество\ подмножеств\ множества\ \left\{1,2,\dots ,n\right\}\ \left(система\ опорных\ множеств,\ СОМ\right),$$
+
=== '''''Определение модели АВО.''''' ===
-
$$\ \widetilde{K^1_j}=\widetilde{S^m}\cap K_j,\widetilde{{\ \ K}^0_j}=\widetilde{S^m}\backslash K_j,\ w^t\in Q^+\ при\ t\in \left\{1,2,\dots ,m\right\}\ \left(вес\ t-го\ объекта\right),\ \ \ $$
 
-
$$w\left(\Omega \right)\in Q^+\ \ при\ \Omega ?{\Omega }_A\left(вес\ опорного\ множества\right),$$
+
В этой модели алгоритм распознавания представляется в виде суперпозиции распознающего оператора (РО) B и решающего правила (РП) C: <tex>$A=B\cdot C.$</tex> Пусть необходимо классифицировать набор <tex>$\widetilde{S_q.}\ $</tex>Распознающий оператор B вычисляет оценки принадлежности объекта <tex>$S_i$</tex> к классу <tex>$K_i$</tex> по формуле
-
$$\ {\ Q^+-множество\ неотрицательных\ рациональных\ чисел,\ \ B}^{\widetilde{??}}_{\Omega }\left(S^t,S_i\right)-бинарная\ функция\ с\ параметрами\ \tilde{e},\ которая\ зависит\ от\ значений\ признаков\ из\ \Omega {\rm \ }{\rm на\ объектах\ }S^{{\rm t}},S_i.$$
+
<tex>$$G_{ij}\left[B\right]={{x_1}\over {N_1(j)}}\sum_{\Omega \in {\Omega }_A}{\sum_{S^t\in \widetilde{K^1_j}}{w^tw\left(\Omega \right)B^{\tilde{e}}_{\Omega }\left(S^t,S_i\right)+}}{{x_0}\over {N_0(j)}}\sum_{\Omega \in {\Omega }_A}{\sum_{S^t\in \widetilde{K^0_j}}{w^tw\left(\Omega \right){[1-B}^{\tilde{e}}_{\Omega }\left(S^t,S_i\right)],}}$$</tex>
-
$\ $Существуют параметры функции близости (задающие «чувствуемую» степень похожести описаний объектов) $\widetilde{e_1}=\widetilde{e_1}\left(\widetilde{S^m},\widetilde{S_q}\right)такие,\ что$
+
где <tex>$x_0,x_1\in \left\{0,1\right\};\ \ $</tex>
-
$$B^{\widetilde{e_1}}_{\Omega }\left(S^t,S_i\right)=1\ \forall S^t\in \widetilde{S^m}, \forall S_i\in \ \widetilde{S_q},\ \forall \Omega \in {\Omega }_A,$$
+
<tex>$$N_0\left(j\right),N_1\left(j\right)$$</tex>-некоторые нормирующие множители,
-
и параметры $\widetilde{e_0}=\widetilde{e_0}\left(\widetilde{S^m},\widetilde{S_q}\right)\ при\ \widetilde{S^m}\cap \widetilde{S_q}=\emptyset \ такие,\ что\ $
+
-
$$B^{\widetilde{e_0}}_{\Omega }\left(S^t,S_i\right)=0\ \forall S^t\in \widetilde{S^m},\forall S_i\in \ \widetilde{S_q},\ \forall \Omega \in {\Omega }_A.{\rm \ }$$
+
<tex>$$\ {\Omega }_A$$</tex> - множество подмножеств множества <tex>\left\{1,2,\dots ,n\right\}\ \left</tex>(система опорных множеств, СОМ),
-
Ссылки:
+
<tex>$$\widetilde{K^1_j}=\widetilde{S^m}\cap K_j,\widetilde{{\ \ K}^0_j}=\widetilde{S^m}\backslash K_j,\ w^t\in Q^+\$$</tex> при <tex>t\in \left\{1,2,\dots ,m\right\}\ \left</tex>(вес t-го объекта),
-
Журавлёв, Ю. И.~Об алгебраическом подходе к решению задач распознавания или классификации~//~Проблемы кибернетики: Вып.33.~--- 1978.~--- С.~5--68.
+
<tex>$$w\left(\Omega \right)\in Q^+\$$</tex> при <tex>$\Omega \in{\Omega }_A\left$</tex>(вес опорного множества),
-
Журавлев Ю.И., Никифоров В.В.~Алгоритмы распознавания, основанные на вычислении оценок // Кибернетика. 1971. № 3. С. 1--11.
+
<tex>$$ Q^+$$</tex>-множество неотрицательных рациональных чисел, <tex>{B}^{\widetilde{e}}_{\Omega }\left(S^t,S_i\right)</tex>-бинарная функция с параметрами <tex>\tilde{e}</tex>, которая зависит от значений признаков из <tex>\Omega</tex> на объектах <tex>S^{{\rm t}},S_i.</tex>
 +
<tex>$\ $</tex>Существуют параметры функции близости (задающие «чувствуемую» степень похожести описаний объектов) <tex>$\widetilde{e_1}=\widetilde{e_1}\left(\widetilde{S^m},\widetilde{S_q}\right)$</tex>такие, что
-
Дьяконов А.Г.~Алгебра над алгоритмами вычисления оценок: Учебное пособие. М.: Издательский отдел ф-та ВМиК МГУ, 2006.
+
<tex>$$B^{\widetilde{e_1}}_{\Omega }\left(S^t,S_i\right)=1\ \forall S^t\in \widetilde{S^m}, \forall S_i\in \ \widetilde{S_q},\ \forall \Omega \in {\Omega }_A,$$</tex>
 +
и параметры <tex>$\widetilde{e_0}=\widetilde{e_0}\left(\widetilde{S^m},\widetilde{S_q}\right)\$</tex> при <tex>$\widetilde{S^m}\cap \widetilde{S_q}=\emptyset$</tex> такие, что
 +
<tex>$$B^{\widetilde{e_0}}_{\Omega }\left(S^t,S_i\right)=0\ \forall S^t\in \widetilde{S^m},\forall S_i\in \ \widetilde{S_q},\ \forall \Omega \in {\Omega }_A.{\rm \ }$$</tex>
-
Ю.И. Журавлев, Математические методы прогнозирования и распознавания на~базе неполной, частично противоречивой, разнородной информации, доклад на общеинститутском семинаре "Математика и ее приложения" Математического института им.~В.~А.~Стеклова~РАН~ 27 декабря 2007 г.~16:00
+
==='''''Ссылки'''''===
-
\noindent
+
*{{книга
 +
|автор = Журавлев Ю.И.
 +
|заглавие = Об алгебраическом подходе к решению задач распознавания или классификации//Проблемы кибернетики: Вып.33.
 +
|год = 1978
 +
|страниц = 5-68
 +
}}
-
\bye
+
 
-
</tex>
+
*{{книга
 +
|автор = Журавлев Ю.И., Никифоров В.В.
 +
|заглавие = Алгоритмы распознавания, основанные на вычислении оценок // Кибернетика.
 +
|год = 1971
 +
|страниц = 1-11
 +
}}
 +
 
 +
 
 +
*{{книга
 +
|автор = Дьяконов А.Г.
 +
|заглавие = Алгебра над алгоритмами вычисления оценок: Учебное пособие.
 +
|место = М.
 +
|издательство = Издательский отдел ф-та ВМиК МГУ
 +
|год = 2006
 +
}}
 +
 
 +
*Ю.И. Журавлев, Математические методы прогнозирования и распознавания на~базе неполной, частично противоречивой, разнородной информации, доклад на общеинститутском семинаре "Математика и ее приложения" Математического института им.~В.~А.~Стеклова~РАН~ 27 декабря 2007 г.~16:00
 +
 
 +
{{Задание|Bondarenko|Константин Воронцов|06 января 2009}}
 +
 
 +
[[Категория:Логические алгоритмы классификации]]
 +
[[Категория:Метрические алгоритмы классификации]]
 +
[[Категория:Методы отбора признаков]]
 +
[[Категория:Методы голосования]]

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

Содержание

Алгоритмы вычисления оценок

Алгоритмы вычисления оценок (АВО) были предложены академиком РАН Ю.И. Журавлевым в начале 70х годов прошлого века. В их описании были отражены передовые концепции решения задач распознавания.

Принципы, использованные в модели АВО.

  • Решение о классификации объекта принимается с помощью анализа оценок близости объекта к классам. За какой класс оценка близости выше -- к тому классу и относят объект. Оценки вычисляет распознающий оператор. Классифицирует объекты на основе оценок их близостей к классам решающее правило.
  • При вычислении оценок близости к классам учитывают близость/дальность объекта к эталонным объектам. Близость -- схожесть описаний, малое расстояние между значениями признаков. При этом оценка близости объекта к классу тем выше, чем ближе он к эталонным объектам данного класса и дальше от эталонных объектов других классов.
  • Близость распознаваемого объекта S к эталонному $S^t$ определяется на основе расстояний ${\rho }_i\left(a_i\left(S\right),a_i\left(S^t\right)\right),\ \ i=1,2,\dots ,n,$ и формализуется понятием функция близости.


Определение модели АВО.

В этой модели алгоритм распознавания представляется в виде суперпозиции распознающего оператора (РО) B и решающего правила (РП) C: $A=B\cdot C.$ Пусть необходимо классифицировать набор $\widetilde{S_q.}\ $Распознающий оператор B вычисляет оценки принадлежности объекта $S_i$ к классу $K_i$ по формуле

$$G_{ij}\left[B\right]={{x_1}\over {N_1(j)}}\sum_{\Omega \in {\Omega }_A}{\sum_{S^t\in \widetilde{K^1_j}}{w^tw\left(\Omega \right)B^{\tilde{e}}_{\Omega }\left(S^t,S_i\right)+}}{{x_0}\over {N_0(j)}}\sum_{\Omega \in {\Omega }_A}{\sum_{S^t\in \widetilde{K^0_j}}{w^tw\left(\Omega \right){[1-B}^{\tilde{e}}_{\Omega }\left(S^t,S_i\right)],}}$$ где $x_0,x_1\in \left\{0,1\right\};\ \ $

$$N_0\left(j\right),N_1\left(j\right)$$-некоторые нормирующие множители,

$$\ {\Omega }_A$$ - множество подмножеств множества \left\{1,2,\dots ,n\right\}\ \left(система опорных множеств, СОМ), $$\widetilde{K^1_j}=\widetilde{S^m}\cap K_j,\widetilde{{\ \ K}^0_j}=\widetilde{S^m}\backslash K_j,\ w^t\in Q^+\$$ при t\in \left\{1,2,\dots ,m\right\}\ \left(вес t-го объекта),

$$w\left(\Omega \right)\in Q^+\$$ при $\Omega \in{\Omega }_A\left$(вес опорного множества),

$$ Q^+$$-множество неотрицательных рациональных чисел, {B}^{\widetilde{e}}_{\Omega }\left(S^t,S_i\right)-бинарная функция с параметрами \tilde{e}, которая зависит от значений признаков из \Omega на объектах S^{{\rm t}},S_i. $\ $Существуют параметры функции близости (задающие «чувствуемую» степень похожести описаний объектов) $\widetilde{e_1}=\widetilde{e_1}\left(\widetilde{S^m},\widetilde{S_q}\right)$такие, что

$$B^{\widetilde{e_1}}_{\Omega }\left(S^t,S_i\right)=1\ \forall S^t\in \widetilde{S^m}, \forall S_i\in \ \widetilde{S_q},\ \forall \Omega \in {\Omega }_A,$$ и параметры $\widetilde{e_0}=\widetilde{e_0}\left(\widetilde{S^m},\widetilde{S_q}\right)\$ при $\widetilde{S^m}\cap \widetilde{S_q}=\emptyset$ такие, что $$B^{\widetilde{e_0}}_{\Omega }\left(S^t,S_i\right)=0\ \forall S^t\in \widetilde{S^m},\forall S_i\in \ \widetilde{S_q},\ \forall \Omega \in {\Omega }_A.{\rm \ }$$

Ссылки

  • Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации//Проблемы кибернетики: Вып.33.. — 1978. — 5-68 с.


  • Журавлев Ю.И., Никифоров В.В. Алгоритмы распознавания, основанные на вычислении оценок // Кибернетика.. — 1971. — 1-11 с.


  • Дьяконов А.Г. Алгебра над алгоритмами вычисления оценок: Учебное пособие.. — М.: Издательский отдел ф-та ВМиК МГУ, 2006.
  • Ю.И. Журавлев, Математические методы прогнозирования и распознавания на~базе неполной, частично противоречивой, разнородной информации, доклад на общеинститутском семинаре "Математика и ее приложения" Математического института им.~В.~А.~Стеклова~РАН~ 27 декабря 2007 г.~16:00


Данная статья является непроверенным учебным заданием.
Студент: Участник:Bondarenko
Преподаватель: Участник:Константин Воронцов
Срок: 06 января 2009

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

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

Источник — «http://poligon.machinelearning.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BE%D1%86%D0%B5%D0%BD%D0%BE%D0%BA»