Using Boolean differentiation operations to minimize knowledge bases

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

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

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

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

, где ,

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

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

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

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

или (1)

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

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

, где ,

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

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

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

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

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

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

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

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

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

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

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

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

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

(2)

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

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

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

.

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

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

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

Свойство 3.

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

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

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

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

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

получаем

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

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