Logical correction algorithms for qualitative analysis of the subject area in pattern recognition problems

Lyutikova Larisa Adol'fovna PhD in Physics and Mathematics Head of department, Institute of Applied Mathematics and Automation 360000, Russia, respublika Kabardino-Balkariya, g. Nal'chik, ul. Shortanova, 89a lylarisa@yandex.ru Other publications by this author

Shmatova Elena Vital'evna graduate student, Department of Intellectualization of Information and Control Systems, Institute of Applied Mathematics and Automation 360000, Russia, Kabardino-Balkariya, g. Nal'chik, ul. Shortanova, 89a lenavsh@yandex.ru Other publications by this author

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

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

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

Описание объекта представляет собой m-мерный вектор X={x₁,x₂,...,x_m}, где m - число признаков, используемых для характеристики объекта, причем j-я координата этого вектора равна значению j-го признака, j=1,...,m. В описании объекта допустимо отсутствие информации о значении того или иного признака. Совокупность некоторого числа объектов и их признаков представляют собой выборку, на которой проработало n алгоритмов. Качество работы каждого алгоритма оценивается булевой функцией a_j(X_i,y_i). Ни один из рассматриваемых алгоритмов не распознает все множество заданных объектов. Предлагается логический метод построения нового алгоритма, являющийся корректным на всем множестве распознаваемых объектов, на основе существующих алгоритмов и решающих правил, составленных для исследуемой области. ` `

На предметной области, состоящей из объектов и их признаков, рассматривается ряд алгоритмов A₁,A₂,...,A_n , дающих некоторые решения задачи распознавания.

Пусть X={x₁,x₂,...,x_m}, x_i `in` {0,1,...,k_i-1}– множество признаков рассматриваемых в рамках переменнозначной логической системы; Y={y₁,y₂,...,y_l}– множество объектов; – A={A₁,A₂,...,An} множество алгоритмов, a_j(X_i,y_i) `in`{0,1}, i=1,2,...,l, j=1,2,...,n - качество работы алгоритма на заданном наборе признаков X_i={x₁(y_i),x₂(y_i),...,x_m(y_i)}, i=1,2,...,l :

т.е. результат работы алгоритма на заданном наборе признаков оценивается в рамках булевой алгебры: 1 – алгоритм A_j распознал объект y_j по заданным признакам X_i; 0 - алгоритм A_j не распознал объект y_j по заданным признакам X_i.

Таблица 1.

Некоторые из заданных в обучающей выборке объектов не распознаются не одним из рассматриваемых алгоритмов, т.е.

Найти

Для анализа предметной области будем использовать алгебру переменнозначной логики ^[4,5,6], которая дает возможность для выразительного кодирования разнородной информации, т.к. каждый отдельный признак x_i `in` ` ` {0,1,...,k_i-1} может быть закодирован предикатом любой значности удобной именно для данного признака.

Решающим правилом для заданной предметной области назовем следующее высказывание:

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

Пусть имеется n алгоритмов {A₁,A₂,...,A_n} частично распознающих заданную область. Для каждой заданной строки признаков

cтроим функции качества работы этого алгоритма. Получаем столбец значений качества работы алгоритма на каждой заданной строке, соответствующей объекту , этому же объекту соответствует продукционное правило

(признак-объект). Полученный столбец можно рассматривать, как частично заданную булеву функцию на множестве переменных {X,Y}.

При обработке данных целесообразным является выбор алгоритма имеющего свойства:

В случае если хотя бы один алгоритм нашел решение вида:

Если ни один из рассматриваемых алгоритмов не распознает объект y_i, то .

Представим все обучающую выборку в виде решающих правил:

Для каждого алгоритма выберем решающие правила, на которых алгоритмы распознают объекты

, то , .

Составим функцию, являющуюся конъюнкцией таких решающих правил для данного алгоритма. Руководствуясь следующими логическими рассуждениями: алгоритм A_j распознает объект y_i и алгоритм распознает объект y_p и все остальные объекты распознаваемые этим алгоритмом:

Далее можно применить алгоритм сокращения в адаптированном для многозначных логик варианте:

- Если некоторая переменная входит в ДНФ с одним знаком во всех дизъюнктах, то удаляем все дизъюнкты, содержащие эту переменную; (данная переменная неинформативна).

- Если в ДНФ имеется какой-то однолитерный дизъюнкт x_i^j, то выполняем следующие действие:удаляем все дизъюнкты по правилу поглощения.

В результате для заданного алгоритма A_j, получаем функцию F_j, соответствующую тем решающим правилам, которые распознал заданный алгоритм. Данная функция обладает рядом свойств ^[2] и практически строит базу знаний данного алгоритма, разбивая область решения на все возможные для данной области классы.

Теорема Необходимым и достаточным условием, характеризуемого набором признаков {X_j} к классу К_r является равенство: F_i(X_j)=K_r.

Доказательство:

Пусть F₁(X)= K_{r ,}так как тогда и f (X_j)= K_r. f(X ) - однозначно характеризует заданную БД. Можно утверждать, что конкретный набор признаков {X_j}, используя представленные данные в БД, характеризует класс K_r .

Предположим, набор признаков {X_j}, характеризует объект класса K_r и это не противоречит исходным данным, тогда функция f (X ) примет значение

f ( X)= K_r. Так как f₂(X_j) - не содержит дизъюнкты, содержащие классы, то можно утверждать, что f₁( X)= K_r.

Построив для каждого алгоритма соответствующие функции F_i, i=1,2,...,n получаем множество функций F₁,F₂,...,F_n. Продолжая наши рассуждения построим обобщающую функцию являющуюся конъюкцией функций F₁,F₂,...,F_n: . Проведя вычисления и преобразования получим функцию:

где f₁(X)– функция, содержащая только переменныее x_j, и назовем ее функцией настройки, а дизъюнкты этой функции – элементами настройки, которые не имеют значения для идентификации объекта, но имеют значение в случае построения нового алгоритма на ранее нераспознанных объектов;

f₂(X,Y)– функция, содержащая конъюнкцию признаков и объектов, являющаяся функцией для определения индивидуальных признаков заданных объектов.

Для построения нового корректного алгоритма на наборах данных нераспознаваемых прежними алгоритмами достаточно использовать функцию f₁(X). Новый алгоритм является конъюнкцией f₁(X) и решающего правила объекта нераспознанного другими алгоритмами. В результате получаем уникальную характеристику объекта и сочетания его признаков, которые не относятся ни к одному из ранее распознанных объектов.

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