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

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

---

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

Алгоритмы вычисления оценок Алгоритмы вычисления оценок (АВО) были предложены академиком РАН Ю.И. Журавлевым в начале 70х годов прошлого века. В их описании были отражены передовые концепции решения задач распознавания. Принципы, использованные в модели АВО: Решение о классификации объекта принимается с помощью анализа оценок близости объекта к классам. За какой класс оценка близости выше – к тому классу и относят объект. Оценки вычисляет распознающий оператор. Классифицирует объекты на основе оценок их близостей к классам решающее правило. При вычислении оценок близости к классам учитывают близость/дальность объекта к эталонным объектам. Близость – схожесть описаний, малое расстояние между значениями признаков. При этом оценка близости объекта к классу тем выше, чем ближе он к эталонным объектам данного класса и дальше от эталонных объектов других классов. Близость распознаваемого объекта S к эталонному S^t определяется на основе расстояний ρ_i (a_i (S),a_i (S^t ) ),i=1,2,…,n, и формализуется понятием функция близости. Определение модели АВО. В этой модели алгоритм распознавания представляется в виде суперпозиции распознающего оператора (РО) B и решающего правила (РП) C: A=B∙C. Пусть необходимо классифицировать набор (S_q.) ̃ Распознающий оператор B вычисляет оценки принадлежности объекта S_i к классу K_i по формуле Г_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}; N_0 (j),N_1 (j)-некоторые нормирующие множители,

Ω_A- множество подмножеств множества {1,2,…,n}  (система опорных множеств,СОМ),
(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 (вес опорного множества),

〖 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 ) ̃=∅ такие,что B_Ω^(e_0 ) ̃ (S^t,S_i )=0 ∀S^t∈(S^m ) ̃,∀S_i∈ (S_q ) ̃,∀Ω∈Ω_A. Ссылки: Журавлёв, Ю. И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики: Вып.33. — 1978. — С. 5–68. Журавлев Ю.И., Никифоров В.В. Алгоритмы распознавания, основанные на вычислении оценок // Кибернетика. 1971. № 3. С. 1–11. Дьяконов А.Г. Алгебра над алгоритмами вычисления оценок: Учебное пособие. М.: Издательский отдел ф-та ВМиК МГУ, 2006. Ю.И. Журавлев, Математические методы прогнозирования и распознавания на базе неполной, частично противоречивой, разнородной информации, доклад на общеинститутском семинаре "Математика и ее приложения" Математического института им. В. А. Стеклова РАН 27 декабря 2007 г. 16:00