To the Problem of Formalizing the Operation of Complex Pattern Recognition Systems

Full Text

Введение

В настоящее время имеется тенденция к созданию универсальных многопрофильных междисциплинарных центров распознавания образов, функционирующих как в экспресс-режиме, так и режиме углубленного анализа, что связано с экономией аппаратных и программных ресурсов, поскольку современные информационные системы и технологии включают в себя большое количество типовых процедур, моделирующих или поддерживающих процесс интеллектуального анализа данных.

К простейшим процедурам такого типа относится любая классификация количественных данных по заданным пользователем критериям. Более сложные обеспечивают анализ сцен, процессов, явлений в целях выделения объектов с заданными характеристиками или свойствами, присутствуют не только в задачах анализа изображений, но и при обработке сигналов в технических системах, медицинской диагностике, биологии, социологии и других областях человеческой деятельности.

Декомпозиция системы распознавания образов

В многоуровневых сложных системах распознавания важен способ декомпозиции, который обычно связан с моментами включения в процесс распознавания специалиста-аналитика данных, то есть с интерактивным режимом обработки из-за неполноты исходной информации или трудностей ее формального описания на этапе синтеза образов [1, 2].

В одноуровневых системах распознавание осуществляется на основе одного словаря признаков одним алгоритмом распознавания, что фактически приводит к поиску на тезаурусе, результатом может служить документ с вектором признаков.

Рассмотрим модель распределенной информационной системы на тезаурусе.

Тезаурус – словарь, отражающий смысловые связи между словами и иными смысловыми элементами и, следовательно, предназначенный для поиска слов по их смыслу. Тезаурусом называется непустое множество V слов υ, отвечающих условиям:

– имеется непустое подмножество V₀ ⊂ V, называемое множеством дескрипторов;

– имеется симметричное транзитивное рефлексивное отношение R ⊂ V × V, такое, что:

${\upsilon }_1\ne {\upsilon }_2\cap {\upsilon }_{1}R {\upsilon }_2\Rightarrow \left({\upsilon }_1\in V\backslash V_0\right)\cup \left({\upsilon }_1\in V\backslash V_0\right)$;

${\upsilon }_1\in V\backslash V_0\Rightarrow \left(\exists \upsilon \in V_0\right)\left(\upsilon R {\upsilon }_1\right)$;

– имеется транзитивное и несимметричное отношение K ⊂ V₀ × V₀, называемое обобщающим отношением.

Отношение R называется синонимическим отношением, слова υ₁ и υ₂, отвечающие этому отношению, называются синонимическими дескрипторами.

В случае, если два дескриптора υ₁ и υ₂ удовлетворяют отношению υ₁Kυ₂, полагается, что дескриптор υ₁ более общий, чем дескриптор υ₂.

Элементы множества V \ V₀ называются множеством аскрипторов.

Информационно-поисковый тезаурус позволяет находить нужные дескрипторы для адекватного выражения информационной потребности.

Дескриптор служит для описания основного содержания документа или формулировки информационного запроса при поиске документов в информационно-поисковой системе. Дескриптор ставится в однозначное соответствие группе ключевых слов естественного языка, отобранных из текста определенной области знания для построения дескрипторного языка [3].

Информационной системой с тезаурусом называется четверка (V, D, M, δ), где V – тезаурус с дескриптовым множеством V₀; D – коллекция документов; M – множество вопросов; δ:М → 2D – отображение, сопоставляющее каждому вопросу множество документов.

Пусть описание любого документа d ∈ D может быть представлено в виде υ(d) = {υ₁, υ₂, ..., υ_k} и удовлетворяет условию: никакие два дескриптора не встречаются в одном υ(d), если они удовлетворяют отношению K.

Можно также считать, что каждый вопрос m ∈ M представлен в форме, аналогичной описанию документов. Множество описаний вопросов и документов частично упорядочено отношением включения ≤ следующим образом ∇d₁, d₂ ∈ D:

$\upsilon \left(d_1\right)<\upsilon \left(d_2\right)\iff \left(\nabla {\upsilon }^{\text{'}}\in \upsilon \left(d_1\right)\right)\times \left(\exists {\upsilon }^{\text{'}\text{'}}\in \upsilon \left(d_2\right)\right)\left({\upsilon }^{\text{'}}K{\upsilon }^{\text{'}\text{'}}\right)\vee \left(d^{\text{'}}=d^{\text{'}\text{'}}\right)$,

то есть каждый дескриптор из υ(d₁) представляет собой обобщение дескриптора из υ(d₂) или идентичен дескриптору из υ(d₂). Отношение ≤ позволяет сформулировать ответ Q на вопрос m ∈ M в виде Q = d(m) = {d : d ∈ D ∧ m ≤ x(d)}.

Пусть S₁, S₂, ..., S_n – локальные информационные системы, где S_j = (V_j, D_j, M_j, δ_j), $j=\overline{\mathrm{1,}n}$. Соединим системы S₁, S₂, ..., S_n в одну систему S, которую будем называть распределенной информационной системой, базирующейся на глобальном тезаурусе $V=\cup V_j$.

Пусть имеется распределенная информационная система S = (V, D, M, d) с синонимическим отношением R_n, обобщающим отношение K. Тогда последовательность информационных систем можно определить следующим образом: S_j = (V_j, D_j, M_j, d_j), где V_j ⊂ V; D_j ⊂ D; M_j ⊂ M; d_j – сужение d на M_j; $j=\overline{\mathrm{1,}n}$.

Кроме того, отношения $R_j=R\cap \left(V_j\times V_j\right)$ и $K_j=K\cap \left(V_{0j}\times V_{0j}\right)$; V_0j – множество дескрипторов системы S_j; отношение предпочтения j ≤ (M_j × M_j); $\forall m\in M_j\delta \left(m\right)=\left\{d:d\in D_j\wedge m\le j_v\left(d\right)\right\}$.

Определим понятие подсистемы, которое позволит формализовать отношение включения одной системы в другую. Пусть S₁ = (V₁, D₁, M₁, δ₁) и S₂ = (V₂, D₂, M₂, δ₂) – информационные системы. Система S₁ является подсистемой S₂, S₁ ⊂ S₂, если:

$$\begin{gathered} \left(V_1\subset V_2\right)\wedge \left(K_1=K_2\cap \left(V_{01}\times V_{02}\right)\right)\wedge \left(R_1=R_2\cap \left(V_{01}\times V_{02}\right)\right); \\ {D}_1\subset D_2; \left(V_1\subset V_2\right)\wedge \le 2\cap \left(M_j\times M_j\right) \\ {\delta }_1\left(m\right)={\delta }_2\left(m_2\right)\cap D_1; m\in M_1 \end{gathered}$$

Локальные информационные системы – подсистемы распределенной информационной системы.

Ввиду того что множество документов распределенной системы – это объединение множеств документов локальных систем, можно выразить ответ на вопрос к распределенной системе как результат некоторых операций над ответами от локальных систем. Пусть $\overline{m}=\left\{m\right\}$ – вопрос, содержащий один дескриптор, $\delta \left(\overline{m}\right)$ – ответ на вопрос m. В подсистеме S_i ответ на локальный вопрос $\overline{m}=\left\{m\right\}$ описывается в следующей форме

${\delta }_j\left(m\right)=\left\{d:d\in D_j\wedge j_v\left(d\right)\right\}$.

В свою очередь, в распределенной системе S глобальный ответ на вопрос $\overline{m}=\left\{m\right\}$ будет объединением локальных ответов $\delta \left(\overline{m}\right)=\underset{j}{\cup }{\delta }_j\left(\overline{m}\right)$.

Ответ на произвольный вопрос $\overline{m}=\left\{m_1,\mathrm{...,}{m}_k\right\}$ в распределенной системе выражается формулой $\delta \left(\overline{m}\right)=\underset{i=1}{\overset{k}{\cap }}\delta \left({\overline{m}}_i\right), {\overline{m}}_i=\left\{m_i\right\}$.

Распределенная информационная система обладает свойством включения, если множество вопросов частично упорядочено отношением ≤ и выполняется условие

$\left\{{\overline{m}}_1,{\overline{m}}_2\right\}\subset M\wedge {\overline{m}}_1\le {\overline{m}}_2\Rightarrow \delta \left({\overline{m}}_1\right)\supset \delta \left({\overline{m}}_2\right)$.

Свойства включения позволяют формулировать цепь ответов на цепь вопросов, уточняя ответы более специализированными вопросами. В некоторых случаях при выполнении свойства аддитивности операции над ответами локальных систем могут быть упрощены.

Если множества документов локальных информационных систем не пересекаются, то глобальный ответ распределенной системы представляется как объединение локальных ответов

$\left(\vee D_k\underset{1\le k\ne \le n}{\cap }{D}_l=0\right)\wedge \left(\overline{m}=\left\{m_1\mathrm{,...,}{m}_s\right\}\right)\Rightarrow \delta \left(m\right)=\underset{j=1}{\overset{n}{\cup }}{\delta }_j\left(\overline{m}\right)$.

Если все локальные информационные системы заданы на одном тезаурусе S_j = (V_j, D_j, M_j, δ_j), $j=\overline{\mathrm{1,}n}$, а множество документов разнесены, то ответ на глобальный вопрос будет объединением локальных ответов, то есть если $\overline{m}=\left\{m_1,\mathrm{...,}{m}_k\right\}$ – вопрос $\underset{1\le i\le n}{\forall }{V}_i=V$, тогда $\delta \left(\overline{m}\right)=\underset{j=1}{\overset{n}{\cup }}{\delta }_j\left(\overline{m}\right)$.

Введем веса, которые будут описывать распределение информации на каждом слове. Информацию, заложенную в описании документов, будем рассматривать в виде единицы, следовательно, вес w_i соответствует объему информации, падаю́щей на дескриптор v_i, то есть v(d) = {<v₁, w₁>, <v₂, w₂>, …, <v_k, w_k>} и выполняются условия:

$v_i\ne v_j\wedge v_{i}K{v}_j\Rightarrow \left(\forall w_i\in \left[\mathrm{0,1}\right]\right)\left(v_i,w_i\right)\in \vee \left(\forall w_j\in \left(v_j,w_j\right)\in v\left(d\right)\right), \sum _{i=1}^k{w}_i=1$.

Описание документов удовлетворяют свойству включения. Дадим определение понятию подобия вопросов и описаний документов.

Пусть v(d₁), v(d₂) – описания документов:

$v\left(d_1\right)=<v_{11},w_{11}>,<v_{12},w_{12}>,\dots ,<v_{1k1},w_{1k1}>$;

$v\left(d_2\right)=<v_{21},w_{21}>,<v_{22},w_{22}>,\dots ,<v_{2k2},w_{2k2}>$.

Описание v(d₁) подобно описанию v(d₂) с точностью r(0 ≤ r ≤ 1), если v(d₁) ≤ v(d₂) ∧ w_1i, r ≤ Σw_2j, <v₁₁, w₁₁> ∈ v(d₁) j : [v_2j ∈ J(v_1j)], где J(v_1j) = {v_2j :v_1jKv_2j ∧ (1 ≤ j ≤ K₂) при 1 ≤ i ≤ K₁}.

Если v(d₁) и v(d₂) удовлетворяют условию, то пишется v(d₁)$⊲$ρv(d₂).

Представляет интерес и другая величина, характеризующая коэффициент подобия или меру корреляции пар векторов, удовлетворяющих отношению ≤.

Для векторов

$\mu \left(v\right(d_1),v(d_2\left)\right)=\sum _{i\left(v_{1i},w_{1i}\right)\subset v\left(d_1\right)}\min \left(w_{1i},\sum w_{1i}\right), j:\left[v_{2j}\in J\left(v_{1i}\right)\right]$,

где $J\left(v_{1i}\right)=\left\{v_{2s}:v_{1i}K{v}_{2s}\wedge 1\le s\le k_2\right\}$ при 1 ≤ i ≤ k₁. Мера m, по сути дела, оценивает информацию, заключенную в описании документов v(d₁), v(d₂).

Информационной системой на тезаурусе с весами называется четверка (V, D, M, δ), где V – тезаурус с дескрипторным множеством V₀ ⊂ V; D – корреляция документов; M – множество вопросов; δ – отображение δ : M × [0, 1] →  2D × [0, 1], сопоставляющее каждой паре (вопрос, точность подобия) множество пар (документ мера корреляции).

Ответом системы на вопрос $\overline{m}$ с требуемой точностью ρ = c называется множество

$Q=\delta \left(\overline{m},\overline{c}\right)=\left\{\left(d,\alpha \right):d\in D\wedge \overline{m}cv\left(d\right)\wedge \alpha =\mu \left(\overline{m},v\left(d\right)\right)\right\}\subseteq D\times \left[\mathrm{0,1}\right]$.

В определении ответа $N=\delta \left(\overline{m},c\right)$ отношение подобия осуществляет выбор документов, точность подобия которых не менее с. Мера корреляции $\mu \left(\overline{m},v\left(d\right)\right)$ показывает, какая часть информации в документе соответствует ответу на вопрос.

Одно из фундаментальных свойств ответа связано с точностью ρ и мерой корреляции m вопроса к описанию документа, включенного в ответ.

Если документ d ∈ D с мерой корреляции α включен в ответ, то есть $\left(d,\alpha \right)\in \delta \left(\overline{m},c\right)$, то верно неравенство α ≥ с. Обратное утверждение неверно.

Если ρ₁ ≥ ρ₂, то $\delta \left(\overline{m},{\rho }_1\right)\subset \delta \left(\overline{m},{\rho }_2\right)$.

В многоуровневых системах распознавания важной функцией аналитика данных является оценка качества распознавания на текущем этапе и возникающей из-за этого потери информации на следующем.

При разработке алгоритмов формализации в условиях неопределенности по характеристикам объекта аналитик может использовать модели, критерии и показатели R₁, …, R_i.

Имеем в виду, что значения показателей получаем на основании алгоритмов оценивания эффективности распознавания. Предположим аддитивность критериев [4, 5]. Учитывая возможные неточности значений показателей из-за вероятностного характера величин, входящих в показатели, наличия значений показателей, представляется целесообразным использование лингвистического подхода. Проранжируем рассматриваемые варианты на основе аддитивной свертки показателей при нечеткой исходной информации [6, 7].

Нечеткие оценки вариантов и коэффициенты важности показателей зададим функциями принадлежности в треугольной форме. Причем коэффициенты важности определяются исходя из предпочтений исследователя на основе аппарата теории одномерной полезности (лингвистического подхода) [8].

Определим методику получения коэффициентов важности показателей оценивания эффективности. Задано множество показателей важности R = {R₁, …, R_i}. Каждый из показателей может принимать конкретные значения x₁, x₂, …, x_m, которые наступают с нечеткими (лингвистическим) вероятностями p₁, p₂, …, p_n.

Предпочитаемая величина значений показателей (в дальнейшем полезность) определяется в ходе диалога с исследователем и задается в виде нечеткой функции принадлежности w₁, w₂, w₃, …, w_n. Определим нечеткую ожидаемую важность (полезность) каждого из показателей. Смысл диалога с исследователем по определению предпочитаемых значений показателей оценивания заключается в следующем. В ходе такого диалога исследуется поведение в условиях риска. Для этого исследователь:

– в соответствии со своими предпочтениями упорядочивает значения показателей: $x_1\prec x_2\prec \mathrm{...}\prec x_n$, где х₁ и х_n – соответственно наименее и наиболее предпочтительные значения;

– обозначая предпочитаемую величину показателя (полезность) w₁ для наихудшего значения, w_n для наилучшего, для каждого значения показателя х_j (j = 1, 2, …, n) назначают вероятность p_j такую, что ему будут безразличны следующие ситуации:

– получить значение х_j;

– получить значение x_n с вероятностью p_j;

– получить значение х₁ с вероятностью 1 – р_j.

Получаем тройку (x_n; p_j; x₁), то есть лотерею, полезность (важность) которой находится с помощью выражения $w_j=w_n{p}_j+w_1(1-p_j)$. Для вычисления нечеткой ожидаемой важности каждого показателя будем использовать a-сечение нечеткого множества R (множество уровня a) [4]: $R_{\alpha }=\left\{x\in X; {\mu }_k\left(x\right)\ge \alpha \right\}$, где Х – базовое множество, a ∈ [0; 1], m_k(x) – функция принадлежности, a – сечение нечеткой вероятности и нечеткой важности значения показателя оценивания x_j.

Представим в форме треугольных функций принадлежности m(p_j) и m(w_j) (рис. 1, 2). Если функции принадлежности нечеткой вероятности и нечеткой важности выпуклые и непрерывные, то a-сечение есть замкнутый интервал. Функцию принадлежности каждого показателя будем строить для тех же a, и a-сечения важности каждого показателя есть замкнутый интервал с границами [9, 10]:

$\inf \omega =\sum _{j=1}^{k-1}{M}_j{w}_j+\left(1-\sum _{j=1}^{k-1}{M}_j-\sum _{j=k+1}^n{m}_j\right)w_k+\sum _{j=k+1}^n{m}_j{w}_j$

при k = k^– и w_j = a_j;

$\sup \omega =\sum _{j=1}^{k+1}{m}_j{w}_j+\left(1-\sum _{j=1}^{k+1}{m}_j-\sum _{j=k+1}^n{M}_j\right)w_k+\sum _{j=k+1}^n{M}_j{w}_j$

при k = k⁺ и w_j = b_j.

 

Рис. 1. Функция принадлежности

 

Рис. 2. α-сечение функции принадлежности

 

Индексы k^– и k⁺ находим из условий:

$\left\{1-\sum _{j=1}^{k^{-}-1}{M}_j-\sum _{j=k^{-}+1}^n{m}_j\right\}\in \left[m_k;M_{k^{+}}\right]$;

$\left\{1-\sum _{j=1}^{k^{+}+1}{m}_j+\sum _{j=k^{+}+1}^n{M}_j\right\}\in \left[m_{k^{+}};M_{k^{+}}\right]$.

Формулы имеют место для данного показателя i и данного уровня a, поэтому индексы i и a в них отсутствуют (для удобства их восприятия). Так как значения показателей x₁, x₂, …, x_n, а также их важности (полезности) необходимо предварительно упорядочить, то необходимо упорядочить и границы a_j; b_j : $a_1\prec a_2\prec \mathrm{...}\prec a_n$; $b_1\prec b_2\prec \mathrm{...}\prec b_n$.

Полученные функции принадлежности нечеткой ожидаемой важности показателей изображены графически на рис. 3. По треугольным функциям определяем значения коэффициентов важности показателей

$p_{j\alpha }=\left[m_j\right(\alpha ); M_j(\alpha \left)\right], w_{j\alpha }=\left[a_j\right(\alpha ); b_j(\alpha \left)\right]; \forall \alpha [0;1]$.

 

Рис. 3. Правые и левые границы функции принадлежности

 

Так как функции принадлежности нечетких вероятностей и нечетких важностей значений показателей алгоритмов формализации в условиях неопределенности элементов моделей объектов распознавания известны, то задаваясь различными значениями a, получаем тот материал, обработав который и найдем функции принадлежности важности показателей алгоритмов формализации в условиях неопределенности элементов моделей (рис. 4).

 

Рис. 4. Выбор наилучшего варианта. Бинарное сравнение

 

Проведем аддитивную свертку показателей. Варианты S = {S₁, S₂, …, S_n}, оцениваемые по n = i показателям, имеющим коэффициенты важности W₁, W₂, ..., W_n, необходимо упорядочить. Через R_ij обозначим оценку i-го варианта (S_i) по j-у показателю (i = 1, 2, …, m; j = 1, 2, …, n) и через R_i – оценку i-го варианта по всем показателям (взвешенную оценку). Оценки R_ij по показателям и коэффициенты относительной важности показателей W_ij задаем функциями принадлежности, соответственно m_Rij(r_ij) и m_Wj(w_j). Взвешенная оценка i-го варианта вычисляется по формуле $R_i=\sum _{j=1}^n{W}_j{R}_{ij}$ при условии, что оценки – нормированы. Будем пользоваться треугольным представлением нечетных оценок и коэффициентов относительной важности показателей. Если функции принадлежности двух нечетких множеств X и Y имеют треугольное представление (см. рис. 1 – 4), то нечетное множество Z = X*Y также определяется функцией принадлежности треугольного вида, а границы и вершина находятся следующим образом: $z^{\text{'}}=x^{\text{'}}\ast y^{\text{'}}, z^{\text{'}\text{'}}=x^{\text{'}\text{'}}\ast y^{\text{'}\text{'}}, z=x\ast y$, где x', y', x'', y'', x, y – соответственно левая, правая границы и вершины функций принадлежности нечетких множеств X и Y, * – бинарная операция над функциями принадлежности нечетких множеств X и Y [11].

После того как взвешенные оценки получены, необходимо сравнить варианты на их основе. Для этого вводится нечеткое множество I, заданное на множестве индексов вариантов {1, 2, …, n}, и значение соответствующей функции принадлежности интерпретируется как характеристика того, насколько вариант x_i является лучшим. Значение m_I(i) вычисляется по формуле ${\mu }_I\left(i\right)=\mathrm{supmin}{\mu }_{j=Ri/\mathrm{1,}n}\left(r_i\right)$ [12, 13].

Графически значение m_I(i) равно ординате точки пересечения взвешенной оценки i-го варианта и взвешенной оценки наилучшего варианта (то есть того варианта, вершина функции принадлежности которого расположена справа от всех остальных). В простейшем случае для обнаружения контурных и полутоновых объектов на цветных и полутоновых изображениях система может иметь вид, показанный на рис. 5.

 

Рис. 5. Структура системы выбора алгоритмов распознавания изображений

 

Заключение

Таким образом, при проектировании и системном анализе процесса функционирования универсальных многопрофильных междисциплинарных центров распознавания образов, функционирующих как в экспресс-режиме, так и в режиме углубленного анализа, возможно рассматривать поиск вектора признаков как модель распределенной информационной системы на тезаурусе, методы лингвистической лотереи для свертки показателей при нечеткой исходной информации.

About the authors

I. A. Glazkova

Tambov State Technical University

Email: ivanovskiy_62@mail.ru

магистрант кафедры «Информационные системы и защита информации»

Russian Federation, Tambov

M. A. Ivanovsky

Tambov State Technical University

Author for correspondence.
Email: ivanovskiy_62@mail.ru

кандидат технических наук, доцент кафедры «Информационные системы и защита информации»

Russian Federation, Tambov

Badr Khalil Mahmud El Eissawi

Tambov State Technical University

Email: ivanovskiy_62@mail.ru

аспирант кафедры «Информационные системы и защита информации»

Russian Federation, Tambov

References

Supplementary files