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

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

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

Версия 12:26, 6 января 2010

\noindent


\bye " alt= "\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х годов прошлого века. В их описании были отражены передовые концепции решения задач распознавания.

\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$ по формуле

$$Г_{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),$$

$$\ {\ Q^+-множество\ неотрицательных\ рациональных\ чисел,\ \ B}^{\widetilde{??}}_{\Omega }\left(S^t,S_i\right)-бинарная\ функция\ с\ параметрами\ \tilde{e},\ которая\ зависит\ от\ значений\ признаков\ из\ \Omega {\rm \ }{\rm на\ объектах\ }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. № 3. С. 1--11.
Дьяконов А.Г.~Алгебра над алгоритмами вычисления оценок: Учебное пособие. М.: Издательский отдел ф-та ВМиК МГУ, 2006.
Ю.И. Журавлев, Математические методы прогнозирования и распознавания на~базе неполной, частично противоречивой, разнородной информации, доклад на общеинститутском семинаре "Математика и ее приложения" Математического института им.~В.~А.~Стеклова~РАН~ 27 декабря 2007 г.~16:00

\noindent


\bye " />

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