Translate this page:
Please select your language to translate the article


You can just close the window to don't translate
Library
Your profile

Back to contents

Cybernetics and programming
Reference:

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
 

 

DOI:

10.7256/2306-4196.2015.5.16368

Received:

11-09-2015


Published:

27-11-2015


Abstract: The subject of the research are methods and algorithms aimed at practical solution of problems of pattern recognition in the weakly formalized fields of knowledge, such as medical field, technical field, geological reconnaissance diagnostics, forecasting and construction of expert systems. The solutions of such problems entered into use a large number of incorrect (heuristic) algorithms. The authors focus on such aspects as the need for the development of the theory of corrective operations, the necessity for the synthesis of correct algorithms minimum complexity, solving the stability issues by using mathematical methods. Special attention is paid to the construction of the algorithm, correct on the whole set of recognizable objects, based on existing algorithms and decision rules drawn up for the studied area. The logical approach may be a technology of constructing a theory of the synthesis of the correct recognition algorithms based on existing family of algorithms. The article shows that these methods allow creating algorithms that implement certain expert conclusion, despite the lack of adequate mathematical models of the relationships between image and its properties, incomplete and contradictory of data. The main conclusion of the research is in a logical analysis of a given subject area, in terms of variables valued logic. The authors propose approaches to the design of procedures for recognition of precedents on the basis of incorrect set of algorithms and constructed logical decision rules. The main contribution of the authors in the study of the topic is the proposed algorithm, expanding the area of the solutions obtained and correct on the whole set of recognizable objects. The novelty of the study is the use of variables valued logic that improves the correctness of encoded information and increase the expressiveness of the conclusions.


Keywords:

algorithm, training set, a set of data, knowledge base, the subject area, logic of varied values, clauses, the decision rule, operation logic of varied values, correct algorithm


Введение

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

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

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

Постановка задачи

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

Формальная постановка задачи

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

Пусть X={x1,x2,...,xm}, xi `in` {0,1,...,ki-1}– множество признаков рассматриваемых в рамках переменнозначной логической системы; Y={y1,y2,...,yl}– множество объектов; – A={A1,A2,...,An} множество алгоритмов, aj(Xi,yi) `in`{0,1}, i=1,2,...,l, j=1,2,...,n - качество работы алгоритма на заданном наборе признаков Xi={x1(yi),x2(yi),...,xm(yi)}, i=1,2,...,l :

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

Таблица 1.

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

Найти

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

Операции переменозначной логики

Высказывания строятся над множеством {B,0,1,...,ki-1}, где B — непустое множество, над элементами которого определены три операции: отрицание (унарная операция), конъюнкция (бинарная), дизъюнкция (бинарная), а также константы — логический ноль .

Пусть Xi – независимая многозначная переменная величина, Xi `` `in[`0,…,ki-1`]` , являющейся одной из характеристик объекта. Введем еще несколько функций и свойств многозначной логики.

Обобщенной инверсией является следующее выражение:

Заданная таким образом инверсия обеспечивает включение всех возможных интерпретаций отрицания в различных многозначных логических системах.

Будем утверждать, что дизъюнкцией двух элементов разной значности является следующая функция:

Конъюнкцией двух элементов разной значности

Импликацию для переменнозначной логики зададим следующим выражением:

Элементарная конъюнкция представляет характеристическую функцию некоторого интервала I, пространства М, а интервал - это простое произведение непустых подмножеств ai, взятых по одному из каждого

Тогда элементарная переменнозначная конъюнкция представляется выражением [5]:

Решающие правила и функция качества ответов

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

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

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

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

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

Построения алгоритма расширяющего область решений

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

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

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

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

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

, то , .

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

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

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

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

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

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

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

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

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

f ( X)= Kr. Так как f2(Xj) - не содержит дизъюнкты, содержащие классы, то можно утверждать, что f1( X)= Kr.

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

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

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

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

Заключение

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

References
1. Zhuravlev Yu. I. Ob algebraicheskom podkhode k resheniyu zadach raspoznavaniya ili klassifikatsii // Problemy kibernetiki. 1978. T. 33. S. 5–68.
2. Zhuravlev Yu. I., Rudakov K. V. Ob algebraicheskoi korrektsii protsedur obrabotki (preobrazovaniya) informatsii // Problemy prikladnoi matematiki i informatiki. 1987. S. 187–198.
3. Vorontsov K. V. Optimizatsionnye metody lineinoi i monotonnoi korrektsii v algebraicheskom podkhode k probleme raspoznavaniya // ZhVM i MF. 2000. T. 40, № 1. S. 166–176.
4. Lyutikova L.A. Ispol'zovanie matematicheskoi logiki s peremennoi znachnost'yupri modelirovanii sistem znanii // Vestnik Samarskogo gosudarstvennogo universiteta. Estestvennonauchnaya seriya. №6(65). 2008. S. 20-27. 2008.
5. Lyutikova L.A. Logicheskii podkhod k modeli predstavleniya znanii // Estestvennye i tekhnicheskie nauki. 2014. № 6 (74). S. 107-108.
6. Yablonskii S. V. Vvedenie v diskretnuyu matematiku. M.: Nauka, 2001. 384 c.
7. Shibzukhov Z.M. Correct Aggregation Operations with Algorithms // Pattern Recognition and Image Analysis. 2014, Vol. 24, No. 3, pp. 377–382
8. Giniyatullin V.M., Arslanov I.G., Bogdanova P.D., Gabitov R.N., Salikhova M.A. Sposoby realizatsii funktsii troichnoi logiki // Programmnye sistemy i vychislitel'nye metody. - 2014. - 2. - C. 239 - 254. DOI: 10.7256/2305-6061.2014.2.11820.
9. Komartsova L.G., Lavrenkov Yu.N., Antipova O.V. Kompleksnyi podkhod k issledovaniyu slozhnykh sistem // Programmnye sistemy i vychislitel'nye metody. - 2013. - 4. - C. 330 - 334. DOI: 10.7256/2305-6061.2013.4.10551.