Ю.И. Журавлёв - Математические основы теории прогнозирования (курс лекций) (1162168), страница 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ω̃S1a2u1ω̃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 ) ≤ u11, если · · ·N (ω̃S, ω̃Si ) =ρ(auk , aiuk ) ≤ uk0, если хотя бы одно из этих неравенств не выполнено.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.

Пусть система {Ω}A состоит из всех k-элементных подмножеств множества {1, 2, . . . , n}.Функция близости определяется только параметрами 1 , 2 , . . . , n . Пусть такжеSi = (ai1 , . . . , aik , . . . , ain ), S = (a1 , . . . , ak , . . . , an ). Выпишем неравенстваρ1 (a1 , ai1 ) ≤ 1···ρk (ak , aik ) ≤ k···ρn (an , ain ) ≤ nСовокупность номеров признаков, для которых выполнены или, соответственно, невыполнены неравенства, обозначим через M + , M − , а мощности соответствующихмножеств через |M + |, |M − |.+Легко видеть, что R(N = 1, t) равно |Mk−1|−1 для t ∈ M + , и равно 0 для t ∈ M − .

Таккак число подмножеств, содержаших t в {Ω}A , равно n−1, тоk−1(R(N = 0, t) =Из последнего видно, чтоnPn−1−k−1 n−1,k−1|M + |−1k−1wt · R(N = 1, t),t=1, для t ∈ M +для t ∈ M − .nPwt · R(N = 0, t) в рассматривае-t=1мом случае заменится более “простыми” суммами, так как величины R(N = 1, t),R(N = 0, t) для каждой строки Si принимают только два различных значения. Так,! nXX|M + | − 1wt · R(N = 1, t) =Pt ·.k−1+t=1t∈MАналогично упрощаются и другие введенные ранее формулы.2.

Рассмотрим ту же, что и в 1, систему опорных множеств и функцию близости с параметрами 1 , . . . , n , ν, ν < [ k2 ]−1. Аналогично предыдущему пункту, при сравнениистрок S и Si образуем подмножества признаков-координат M + и M − .Пусть t ∈ M + . Тогда функция близости равна 1, если она содержит 0, 1, 2, . . .

,min(ν, |M − |) признаков из M − и, соответственно, k − 1, k − 2, . . . , k − min(ν, |M − |) −− 1 признаков из M + (для упрощения выкладок мы рассматриваем только случайk ≥ min(ν, |M − |) + 1). Тогда число опорных подмножеств, содержащих t и таких, чтоN (ω̃S, ω̃Si ) = 1, очевидно, равно + − + − + −|M | − 1|M ||M | − 1|M ||M | − r|M |·+·+ ...

Характеристики

Список файлов лекций