Рус Eng Cn Перевести страницу на:  
Please select your language to translate the article


You can just close the window to don't translate
Библиотека
ваш профиль

Вернуться к содержанию

Кибернетика и программирование
Правильная ссылка на статью:

Применение операций булевого дифференцирования для минимизации баз знаний

Лютикова Лариса Адольфовна

кандидат физико-математических наук

заведующий отделом, ИПМА КБНЦ РАН

360000, Россия, Республика Кабардино-Балкария, г. Нальчик, ул. Шортанова, 89а

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
Другие публикации этого автора
 

 

DOI:

10.25136/2644-5522.2017.6.24746

Дата направления статьи в редакцию:

16-11-2017


Дата публикации:

11-01-2018


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


Ключевые слова:

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

Abstract: The object of the research is the subject area, which is a precedent relationship between objects and their characteristics used in solving image recognition problems.Intellectual analysis of data is one of the necessary stages in the solution of poorly formalized problems; therefore, in many cases the accuracy of the solution of the task depends on the method of building knowledge bases, analyzing them and minimizing them. The development of common formal methods for revealing logical patterns in any given subject area seems to be a very pressing problem, as it provides the opportunity to form optimal knowledge bases, which greatly simplifies the solution and improves its quality. In this paper, the author use the apparatus for differentiating Boolean functions to analyze and minimize knowledge bases, which are the directions of modern discrete mathematics and find their application in problems of dynamic analysis and synthesis of discrete digital structures. The main results of the study are a constructed logical function that analyzes the relationship between objects and characteristics that characterize them, which is an opportunity to reveal all the laws of a given subject area; as well as the method of minimizing knowledge bases obtained on the basis of logical data analysis, revealing a minimal set of decision rules, sufficient for solving the task.


Keywords:

Boolean function, logical operation, knowledge base, decisive rule, subject area, Boolean derivative, axioms, conjuction, disjunction, complex function

Введение

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

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

Пусть , где –множество признаков. – множество объектов, каждый объект характеризуется соответствующим набором признаков . Или , где – обрабатываемые входные данные – выходные данные:

Вид функции не задан. Требуется восстановить данную функцию по наблюдениям. А также найти , где , B- минимальное множество правил, задающих анализируемую предметною область. Для объяснения логической связи между понятиями предметной области будем использовать правило продукции, предложенное Э. Постом [2]. В нашем случае правило продукции представляет собой подстановку следующего вида:

, где ,

конечное число признаков, характеризующих элемент .

Это позволяет выразительно представить зависимости между объектом и его признаками.

где предикат принимает значение истина, т.е. в случае если и , если . Или в виде:

Решающей функций назовем конъюнкцию всех решающих правил:

или (1)

Эту функцию можно проинтерпретировать следующим образом:

Если обучающую выборку, состоящую из k элементов описать булевой функцией

, где ,

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

Все свойства функции (1) подробно рассмотрены в работe [1,3].

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

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

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

Пример

Пусть задана следующая предметная область:

x1 x2 x3 y

0

0

1

2

0

1

0

4

0

1

1

8

1

1

1

128

Множество признаков X представлено следующими значениями:

а множество объектов .

Решающая функция для примера 1 будет иметь следующий вид:

Объектная часть функции представима следующими дизъюнктами

Некоторые свойства операций логического дифференцирования и интегрирования дискретных k – значных функций

Логическое дифференциальное и интегральное исчисления являются направлениями современной дискретной математики и находят свое применение в задачах динамического анализа и синтеза дискретных цифровых структур. Основным понятием логического дифференциального исчисления является производная булевой функции, представление о которой в виде булевой разности было получено еще в работах [2, 4].

Булева производная по некоторым своим свойствам является аналогом производной в классическом дифференциальном исчислении

Определение 1. Производная первого порядка от булевой функции f(x1,…,xn) по переменной xi есть сумма по модулю 2 соответствующих остаточных функций:

(2)

Определение 2 .Весом производной от булевой функции называется число конституент («1») этой производной.

Утверждение 1. Чем больше вес производной, тем больше функция f(x1,…,xn) зависит от переменной `x_(i)` .

Определение 3. Смешанной производной k-го порядка от булевой функции f(x1,…,xn) называется выражение вид:

.

При этом порядок фиксированной переменной не имеет значения. Производная k-го порядка определяет условия, при которых эта функция изменяет свое значение при одновременном изменении значений x1,…,xk. Совершенные нормальные дизъюнктивные формы хотя и дают однозначные представления функции, но являются очень громоздкими. Реализация СДНФ программное или схемотехнически является избыточной, что ведет к увеличению программного кода, поэтому существуют методы упрощения логической записи – минимизации [5,6].

Теорема. Пусть , пусть , где l- конечное число, тогда функция представима в виде псевдополинома.

В системах k=6,10 и выше, если , где p -простое число существуют бесконечно дифференцируемые функции.

Свойство1. Пусть

булева функция от n переменных, , , тогда - существенные переменные.

Свойство 2. Для булевой функции .

Свойство 3.

Применение булевого дифференцирования для минимизации объектной части логической функции.

Воспользовавшись свойствами булевого дифференцирования, и формулами:

дифференцирования дизъюнкции,

дифференцирования конъюнкции, применяя их к объектной части построенной логической функции (1) получим

где -переменные ходящие в объектную часть функции (1).

Применяя к нашему к примеру:

получаем

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

Заключение.

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

Библиография
1. Лютикова Л. А., Шматова Е. В. Анализ и синтез алгоритмов распознавания образов с использованием переменно-значной логики // "Информационные технологии". Том 22. №4. 2016. С. 292—297.
2. Бохманн Д., Станкович Р.С., Тошич Ж., Шмерко В.П., Янушкевич С.Н. Логическое дифференциальное исчисление: достижения, тенденции и приложения Автоматика и телемеханика, 2000, № 6, С. 156–170; Autom. Remote Control, 61:6 (2000), Р. 1033–1047.
3. Дюкова Е.В., Журавлев Ю.И., Прокофьев П.А. Методы повышения эффективности логических корректоров // Машинное обучение и анализ данных. 2015. Т. 1. № 11. С. 1555-1583.
4. Лютикова Л. А. Исследование систем булевых функций логическими интегро-дифференциальными методами // Материали за 6 Международна научна практична конференция «Найновите постижения на европейской наука-2011». София. Т. 37. С. 31-38.
5. Чернов А. В. Развитие аппарата логического дифференциального исчисления в применении к задачам проектирования и диагностики телекоммуникационных систем // Научно-технические ведомости СпБГПУ. 2008. № 2. С. 118-126.
6. Спирина М.С. Логическое дифференциальное и интегральное исчисление Информационные системы и технологии: управление и безопасность. 2016. №4. С. 187-201.
References
1. Lyutikova L. A., Shmatova E. V. Analiz i sintez algoritmov raspoznavaniya obrazov s ispol'zovaniem peremenno-znachnoi logiki // "Informatsionnye tekhnologii". Tom 22. №4. 2016. S. 292—297.
2. Bokhmann D., Stankovich R.S., Toshich Zh., Shmerko V.P., Yanushkevich S.N. Logicheskoe differentsial'noe ischislenie: dostizheniya, tendentsii i prilozheniya Avtomatika i telemekhanika, 2000, № 6, S. 156–170; Autom. Remote Control, 61:6 (2000), R. 1033–1047.
3. Dyukova E.V., Zhuravlev Yu.I., Prokof'ev P.A. Metody povysheniya effektivnosti logicheskikh korrektorov // Mashinnoe obuchenie i analiz dannykh. 2015. T. 1. № 11. S. 1555-1583.
4. Lyutikova L. A. Issledovanie sistem bulevykh funktsii logicheskimi integro-differentsial'nymi metodami // Materiali za 6 Mezhdunarodna nauchna praktichna konferentsiya «Nainovite postizheniya na evropeiskoi nauka-2011». Sofiya. T. 37. S. 31-38.
5. Chernov A. V. Razvitie apparata logicheskogo differentsial'nogo ischisleniya v primenenii k zadacham proektirovaniya i diagnostiki telekommunikatsionnykh sistem // Nauchno-tekhnicheskie vedomosti SpBGPU. 2008. № 2. S. 118-126.
6. Spirina M.S. Logicheskoe differentsial'noe i integral'noe ischislenie Informatsionnye sistemy i tekhnologii: upravlenie i bezopasnost'. 2016. №4. S. 187-201.