_учебник_ Журавлёв Ю.И. Математические основы теории пронозирования (2008) (1185334), страница 4
Текст из файла (страница 4)
. αij . . . αil ) = α̃(Si ) указывает — каким из классов K1 , . . . , Kl принадлежит или не принадлежит объект Si , определенный строкой (ai1 . . . ain ) значений признаков 1, 2, . . . , n из таблицы обучения. Как иранее, полагаем, что области определения признаков — это метрические пространства Mtс метриками ρt , t = 1, . . . , n.Алгоритмы вычисления оценок определяются:I. Заданием системы опорных множеств признаков.Это могут быть любые множества, элементами которых являются непустые подмножества множества признаков 1, 2, .
. . , n. Такими могут быть:a) совокупность всех непустых подмножеств множества {1, 2, . . . , n},b) совокупность всех подмножеств из k элементов и т. д.В случаях a) и b) имеем, соответственно, 2n − 1 и nk , k = 1, 2, . . . , n − 1 подмножествпризнаков, по которым происходит сравнение эталонных и распознаваемого объекта.Вообще говоря, может быть задана любая совокупность {Ω}A опорных множеств,задающих распознающий алгоритм A.
Для удобства, в некоторых случаях, вместо16опорного множества Ω = {u1 , . . . uk } будем рассматривать характеристический вектор ω̃ = {σ1 , . . . σn }, где σu1 = . . . = σuk = 1, и остальные координаты равны 0.Очевидно: Ω ↔ ω̃, {Ω}A ↔ {ω̃}A .Введем понятия ω̃-части объекта S и таблицы kaij km×n :ω̃-часть строки S = (a1 , . . . an ) — обозначение ω̃S — это набор a1u1ω̃S1a2u1ω̃S = (au1 , .
. . , auk ), ω̃(kaij km×n ) = ... = ···ω̃Smamu1. . . a1uk. . . a2uk .··· ··· . . . amukБудем также использовать обозначение ω̃T1 , T1 — таблица обучения.II. Заданием функции близости N (ω̃S, ω̃Si ) между ω̃-частями распознаваемого объектаSi и эталонного объекта S. В дальнейшем рассматриваются только функции близости, принимающие значения 0, 1. Тогда корректно введение функции N (ω̃S, ω̃Si ),указывающей на отсутствие близости между ω̃S и ω̃Si .Обычно рассматриваются три вида функций близости:1) введем неотрицательные параметры 1 , . . . n .
Пусть ω̃S = (au1 , . . . , auk ),ω̃Si = (aiu1 , . . . , aiuk ). Тогдаρ(au1 , aiu1 ) ≤ u11, если · · ·N (ω̃S, ω̃Si ) =ρ(auk , aiuk ) ≤ uk0, если хотя бы одно из этих неравенств не выполнено.2) кроме параметров 1 , . . . n введем неотрицательный целочисленный параметрν: N (ω̃S, ω̃Si ) = 1, если среди приведенных выше неравенств не более ν невыполнены, и равна 0 в остальных случаях.Пусть |Ω| — число элементов в опорном множестве Ω ∈ {Ω}A ; пусть такжеmin |Ω| = q.Ω∈{Ω}AЛегко видеть, что следует рассматривать только значения ν, удовлетворяющиенеравенствуhq i− 1.0≤ν≤23) вместо параметра ν можно рассмотреть параметр ν ∗ и определить функциюблизости следующим образом: N (ω̃S, ω̃Si ) = 1 тогда и только тогда, когда из kнеравенствρ(au1 , aiu1 ) ≤ u1···ρ(auk , aiuk ) ≤ ukне выполнены r неравенств, и kr < ν ∗ .В практических системах распознавания, в основном, применяется функцияблизости, зависящая только от параметров 1 , .
. . n .17III. Признакам 1, 2, . . . , n, описывающим объекты, присваиваются веса w1 , w2 , . . . , wn .Как правило, wi ≥ 0, i = 1 . . . n. Но последнее ограничение не является обязательным. Объектам из исходной таблицы T1 : S1 , . . . , Sm приписываются веса w(S1 ) == w1 , . . . , w(Sm ) = wm .
Здесь wi ≥ 0, i = 1 . . . m. Множеству ω̃Si = (aiu1 , . . . , aiuk )приписывается вес (число голосов) Γ(ω̃Si ) = wi · (wu1 + . . . + wuk ).IV. При сравнении ω̃S и ω̃Si возможны следующие случаи, сведенные в таблицу и оцененные параметрами xij , i = 0, 1, j = 0, 1.HHH NSi KjHHHS i ∈ KjSi ∈/ KjN (ω̃S, ω̃Si ) = 1N (ω̃S, ω̃Si ) = 0x11x01x10x00При формировании оценки принадлежности S классу Kj , 1 ≤ j ≤ l (величиныΓj (ω̃S, ω̃Si )) учитываются оценка Γ(ω̃S, ω̃Si ) и то, какой из четырех указанных случаев имеет место: оценка Γ(ω̃S, ω̃Si ) умножается на соответствующий параметр. Так,если Si ∈ Kj , N (ω̃S, ω̃Si ) = 1, тоΓj (ω̃S, ω̃Si ) = x11 · Γ(ω̃S, ω̃Si ).Аналогично формируются оценки в остальных трех случаях.
Заметим, что естественно полагатьx11 ≥ 0, x00 ≥ 0, x01 ≤ 0, x10 ≤ 0, x00 < x11 .Действительно, близость к объекту из Kj или отсутствие близости с объектом, непринадлежащим Kj , благоприятны для оценки вхождения S в Kj , причем второйслучай не более благоприятен, чем первый.
Два других случая: Si ∈/ Kj , N (ω̃S, ω̃Si ) == 1 и Si ∈ Kj , N (ω̃S, ω̃Si ) = 1 не должны повышать оценку вхождения S в Kj .Заметим, что приведенные здесь объяснения не являются строгими доказательствами, но лишь эвристическими правдоподобными рассуждениями, оправдывающими(в некоторой степени) даваемое нами определение класса алгоритмов вычисленияоценок.V. Оценка Γj (S) вхождения объекта S в класс Kj задается следующей формулойm1 X XΓj (S) =Γj (ω̃S, ω̃Si ),Q i=1(3.1)ω̃∈{ω̃}AQ — нормирующий множитель. Его величина не влияет на дальнейшие преобразования Γj (S). Поэтому достаточно рассмотреть случай Q = 1.VI. Решающее правило определяется числовыми параметрами c1 , c2 , 0 < c1 < c2 .Алгоритм A формирует для S информационный (квази-информационный) вектор(β1 (S), .
. . , βj (S), . . . , βl (S)) следующим образом:βj (S) = 1 → S ∈ Kj , если Γj (S) > c2 ;βj (S) = 0 → S ∈/ Kj , если Γj (S) < c1 ;в остальных случаях βj (S) = ∆, что означает: алгоритм A отказался распознаватьвхождение S в класс Kj .Отметим, что алгоритм вычисления оценок (АВО) подразделяется на две части. Послевыполнения этапа V формируется числовой вектор оценок (Γ1 (S), . . . , Γj (S), . .
. , Γl (S)) =→−= Γl (S). Эту часть алгоритма принято называть распознающим оператором B:→−B(I, S) = (Γ1 (S), . . . , Γj (S), . . . , Γl (S)) = Γl (S).18→−Вторая часть алгоритма (этап VI) переводит Γl (S) в квази-информационный вектор.Это — решающее правило C:→−C( Γl (S)) = C(Γ1 (S), . . . , Γj (S), . . . , Γl (S)) = (C(Γ1 (S)), . . . , C(Γj (S)), . . .
, C(Γl (S))) == (β1 , . . . , βj , . . . , βl ).Резюме. Алгоритм A определяется заданием системы {Ω}A опорных множеств, параметров 1 , . . . n (возможно и ν или ν ∗ ), определяющих функцию близости, весов признаковw1 , . . . , wn , весов эталонных объектов w1 , . . . , wm , параметров x11 , x00 , “поощряющих” благоприятные ситуации, x01 , x10 , “штрафующих” за неблагоприятные ситуации, параметровc1 , c2 порогового решающего правила, с помощью которых принимается окончательное решение о вхождении, невхождении распознаваемого объекта S в классы K1 , .
. . Kl или, длянекоторых классов (может быть, для всех), — об отказе от распознавания.Пример 3S1S2S31001201133144241|S560.7 0.80.6 0.70.5 0.6{zI11230.6K1101K2011}0.8Алгоритм определяется следующими множествами и параметрами:{Ω}A = {(1, 2), (3, 4), (5, 6)};1 = 2 = 0, 3 = 4 = 1, 5 = 6 = 0.1;w1 = w2 = 2, w3 = 1;w1 = w2 = 1, w3 = w4 = 2, w5 = w6 = 3;x11 = 3, x00 = 1, x01 = x10 = −1.Таблица значений функции близостиΩ1 Ω2 Ω3S1 011S2 101S3 000Таблица использования параметровxij , i = 0, 1; j = 0, 1x10 x11 x11x01 x00 x01x01 x01 x01Таблица TΩ оценок Γ1 (ω̃S, ω̃Si )Ω1 Ω2 Ω3S1 48 12S2 48 12S3 246Таблица Txij значений параметров xij-1 3 3-1 1 -1-1 -1 -1Умножим поэлементно матрицу TΩ на матрицу Txij и сложим все элементы матрицыTΩ · Txij .
Получим число 36. При c2 < 36 алгоритм зачислит объект S в класс K1 .Аналогично вычисляется оценка Γ2 (S). Вычисление предоставляется выполнить читателю.193.2Эффективные формулы вычисления оценокПрямое использование формулы (3.1) для вычисления оценок Γj (S), j = 1, . . . l затруднительно при большом числе множеств. Так, если {Ω}A состоит из всех непустыхподмножеств множества {1, 2, . . . , n}, то потребовалось бы вычислить m · (2n − 1) слагаемых.
Поэтому рассмотрим пути сокращения вычислений. Рассмотрим вычисления прификсированной строке Si :XΓj (ω̃S, ω̃Si ).ω̃∈{ω̃}AРазберем два различных случая: 1◦ Si ∈ Kj и 2◦ Si ∈/ Kj . В случае 1◦ имеем два подслучая 1◦ 1 и 1◦ 0: N (ω̃S, ω̃Si ) = 1 и N (ω̃S, ω̃Si ) = 0.X1◦ 1 : x11 · wj ·P (Ω), P (Ω) = wi1 + .
. . + wik , если Ω = {i1 , . . . , ik }.Ω: N (ω̃S,ω̃Si )=1Ω∈{Ω}AОбозначим через R(N = 1, t) число опорных множеств, содержащих t и участвующихв суммировании. Очевидно, величина wt встретится при суммировании R(N = 1, t) раз,t = 1, . . . , n. Поэтому формулу для 1◦ 1 можно переписать:jx11 · w ·nXwt · R(N = 1, t).t=1В подслучае 1◦ 0 вместо множителя x11 появится x10 , а величина R(N = 1, t) заменится наR(N = 0, t), где R(N = 0, t) — число опорных подмножеств Ω, содержащих t и таких, чтоN (ω̃S, ω̃Si ) = 0. Окончательно при Si ∈ Kj получаем:jw (x11 ·nXwt · R(N = 1, t) + x10 ·nXwt · R(N = 0, t)) = Γ1j (si ∈ Kj ).(3.2)wt · R(N = 1, t)) = Γ0j (si ∈/ Kj ).(3.3)t=1t=1При 2◦ , действуя в точности как в 1◦ , выводим:jw (x00 ·nXwt · R(N = 0, t) + x10 ·t=1nXt=1Окончательно в формулеXΓj (ω̃S, ω̃Si )Ω∈{Ω}Aсуммирование по опорным множествам заменяется на два суммирования n слагаемых ивычисление значений R(N = 1, t), R(N = 0, t).Нами доказанаТеорема 3Γj (S) =1 Γ1 (Si ∈ Kj ) +Q S ∈K jXijXΓ0j (Si ∈/ Kj ) ,Si ∈K/ jгде величины Γ1j , Γ0j определяются по формулам (3.2),(3.3).20Вычисление R(N = 1, t), R(N = 0, t) для некоторых семейств опорных множеств.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
