Вопрос 35. Алгоритм вычисления оценок (аво).

Пусть множество объектов {ω} подразделено на классы Ω_i,,i=l,...,m, и для описания объектов используются признаки x_j, j=l,...,N. Все объекты описываются одним и тем же набором признаков. Алгоритм рас­познавания сравнивает описание распознаваемого объекта с описаниями всех объектов и прини­мает решение о том, к какому классу отнести объект. Класси­фикация основана на вычислении степени похожести (оценки) распознаваемого объекта на объекты, принадлежность которых к классам известна. Эта процедура включает в себя два этапа: сначала подсчитывается оценка для каждого объекта, а затем полученные оценки используются для получения суммарных оценок по каждому из классов Ω_i. Решающим правилом является отнесение распознаваемого объекта к классу, которому соответствует максимальная оценка, либо эта оценка превышает оценки всех остальных не менее чем на определенную пороговую величину, либо отношение соответствующей оценки к сумме оценок всех остальных классов не менее пороговой величины.

Вопрос 36. Основные идеи, лежащие в основе аво.

Рассмотрим полный набор признаков х = {x₁,...,x_N} и выде­лим систему подмножеств множества признаков (систему опор­ных множеств алгоритма) S₁,...,S_l. В АВО обычно рассматриваются либо все подмножества множества признаков фиксированной длины k, k=2,...,N—1, либо вообще все подмножества множе­ства признаков.

Удалим произвольный поднабор признаков из строк ω_1, ω_{2, ...,} ω_rm , ω’и обозначим полученные строки S_ω1, S_ω2,... ,S_ωrm, S_{ω’ .} Правило близости, позволяющее оценить похожесть стро­ки S_ω’, соответствующей распознаваемому объекту ω', и строки S_ωk, соответствующей произвольному объекту исходной таблицы, состоит в следующем.

Пусть «усеченные» строки содержат q первых признаков, т. е. S_wk = (α₁,..., α_q) и S_ω’ = (β₁,..., β_q), и заданы пороги ε₁, ε₂,... ,ε_q, δ . Строки S_ωи S_ωk считаются по­хожими, если выполняется не менее чем δ неравенств вида | α_j – β_j| < ε_j, j =1,..., q. Величины ε₁, ε₂,... ,ε_q, δ входят в качестве параметров в АВО.

Рассмотрим процедуру вычисления оценок по подмножеству Si . Проверяет­ся близость строки Si_ω’ строками Si_ω1, Si_ω2,... ,Si_ωr1,-,, принадлежа­щими объектам класса Ω₁. Число строк этого класса, близких по выбранному критерию классифицируемой строке Si_ω’, обоз­начается Γ_Si(ω’, Ω₁); последняя величина представляет собой оценку строки ω’ для класса Ω₁ по опорному множеству Si. Аналогичным образом вычисляются оценки для остальных клас­сов. Применение подобной процеду­ры ко всем остальным опорным множествам алгоритма позво­ляет получить систему оценок Γ_S1(ω’, Ω₁), ..., Γ_S1(ω’, Ω_m), ...,Γ_Sk(ω’, Ω₁), ...,Γ_Sk(ω’, Ω_m).

Γ(ω’, Ω₁) = Γ_S1(ω’, Ω₁) + Γ_S2(ω’, Ω₁) + ... + Γ_Sk(ω’, Ω₁) =

(1)Γ(ω’, Ωm) = Γ_S1(ω’, Ωm) + Γ_S2(ω’, Ωm) + ... + Γ_Sk(ω’, Ωm) =

Величины Γ(ω’, Ω₁),...,Γ(ω’, Ω_m) представляют собой оценки строки ω’ для соответствующих классов по системе опорных множеств алгоритма S_A. Решающее правило может прини­мать различные формы, в частности распознаваемый объект мо­жет быть отнесен к классу, которому соответствует максималь­ная оценка, либо эта оценка будет превышать оценки всех ос­тальных классов не меньше чем на определенную пороговую ве­личину n1, либо значение отношения соответствующей оценки к сумме оценок для всех остальных классов будет не менее значения порога n2 и т. д. Параметры типа n1 и n2 также включаются в АВО.