Построение алгоритма и программная реализация интеллектуальной обработки данных при помощи переменнозначных логических функций

Димитриченко Дмитрий Петрович кандидат технических наук научный сотрудник, ФГБНУ "Институт прикладной математики и автоматизации" 360000, Россия, г. Нальчик, ул. Шортанова, 89а Dimitrichenko Dmitriy Petrovich PhD in Technical Science Researcher, "Institute of Applied Mathematics and Automation" 360000, Russia, g. Nal'chik, ul. Shortanova, 89a dimdp@rambler.ru Другие публикации этого автора

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

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

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

Актуальность решения указанной задачи возрастает в условиях противоположного влияния рассматриваемых характеристик на результирующий выбор. Например, требование надежности сопряжено с наличием дублирующих или резервных каналов связи, дополнительного оборудования и специализированного программного обеспечения, компенсирующего ошибки передачи данных, что приводит к возрастанию суммарной стоимости оборудования и технического обслуживания искомой ТКС. Требование дешевизны, наоборот, приводит к минимально возможному числу передающих линий, способному обеспечить связность всех, входящих в результирующую топологию узлов, что приводит к уменьшению общей стоимости установки и обслуживания результирующей топологии, но понижает общую надежность системы в целом.

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

Пусть t – количество узлов, входящих в произвольную топологию ТКС.

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

1. Полноячеистая топология (каждая из t вершин связана с t-1 соседней вершиной отдельным ребром: полный граф);
2. Топология «t-вершинная звезда» (фиксированная вершина, называемая центром, связана с t-1 соседней вершиной: звездообразная структура);
3. Кольцевая t-вершинная топология (единственный контур (или цикл), включающий все t вершин: кольцевая структура);
4. Линейная топология (t-вершинный контур (или цикл), в котором удалено одно из t ребер: путь или цепь);
5. Смешанная топология (включает произвольную топологическую структуру, не относящуюся ни к какой из ранее описанных.

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

1. Полный граф позволит рассчитать верхнюю (или нижнюю) границу искомой оценки по соответствующему критерию;
2. Используя звездообразную структуру легко определить динамику изменения анализируемого параметра от текущей вершины до всех t-1 соседних вершин;
3. Кольцевая структура позволит вычислить важные характеристики контура (или информационного цикла), описывающего системы с обратной связью;
4. Линейная структура обеспечит вычисление характеристик, связывающих важнейшие узлы (вершины) путей (или цепей), например, структуры проводящих или передающих транспортных подсетей;
5. В случаях, когда смешанная (гетерогенная) информационная сеть не может быть описана с достаточной степенью формализации, в качестве первого приближения для анализа такой сети, характеризующейся смешанной топологией можно выбрать в качестве опорных средние значения характеристик ранее описанных топологических структур.

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

Расширяя подкласс смешанных топологий, за счет пополнения множества W новыми представителями топологических структур, мы получим актуальное для проектировщика (заказчика) множество анализируемых топологий.

Пусть на множестве топологических структур ТКС W определены n функций F_j(w_i), оценивающие каждую из m топологий w_i по критерию j, i=1, …, m, j=1, …, n.

При этом, совокупность вещественных значений любой из n оценочных функций всегда можно отобразить на шкалу с индивидуальной дискретной градуировкой с соответствующим числом элементов k_j, k_j>=2, j=1,…, n.

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

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

Другие экспертные оценки удобно представить виде трех состояний: «хорошо», «удовлетворительно», «плохо». В этом случае, речь может идти, например, об экспертной оценке эффективности работы определенного антивирусного решения.

В общем случае каждая из n экспертных оценок имеет самостоятельную градацию, состоящую из k_j четко различимых состояний, k_j>=2, j=1,…, n.

Формализованные таким образом n экспертных оценок m топологических структур по выделенным критериям могут быть представлены в виде таблицы размера mn, где m - число рассмотренных топологий, а n - количество актуальных критериев.

Сформированные подобным образом данные наиболее удобно представить при помощи системы переменнозначных предикатов, каждый из которых имеет соответствующую значность k_j, j=1,…, n.

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

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

Пусть задано конечное число объектов m из рассматриваемой предметной области W= {w_i}, i=1, …,m. Для каждого из m объектов w_i, принадлежащих множеству W, определены n актуальных критериев виде n заданных оценочных функций, совокупность значений которых можно представить в виде переменнозначных предикатов, таких что x_j=F_j(w_i), выражающихоценку топологии w_i по критерию, j, принимающую значения 0, ...,k_j-1.

Необходимо найти объект (или класс объектов) наиболее полно удовлетворяющий запросу X^*, где X^* - произвольный вектор характеристик, X^*=x₁, …, x_n.

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

Эффективным методом моделирования свойств объектов в слабо формализуемых областях знаний является метод описания объектов при помощи переменнозначных логических предикатов ^[1].

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

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

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

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

Описание объекта представляет собой n-компонентный вектор, где n - число признаков, используемых для характеристики анализируемого объекта, причем j-я координата этого вектора равна значению j-го предиката, характеризующего данный признак, j=1,..., n. Число таких векторов равно m в соответствии с количеством анализируемых объектов. В описании объекта допустимо отсутствие информации о значении того или иного признака. Требуется найти совокупность объектов w^*, наиболее полно удовлетворяющих фиксированному набору характеристик X*. При формировании эффективной системы интеллектуального описания объектов следует избегать двух крайностей: избыточности и недостаточности набора признаков. В первом случае важные результаты окажутся скрытыми в массе второстепенных или малозначительных признаков. Во втором – критерий для однозначного распознавания конкретных объектов останется не выявленным. Предложенный в ^[2] логический алгоритм построения переменнозначных функций, устраняющий избыточность в описании данных и выделяющий наиболее важные причинно-следственные связи в описании объектов, позволяет решить эту задачу.

Соответствие множества объектов и характеризующих их признаков представимо ниже следующей таблицей:

X_j={x₁(w_j), x₂(w_j),...,x_n(w_j)}, где X=(x₁, …, x_n) - вектор качественных признаков, каждый элемент которого – значение фиксированного признака характеризуемого объекта.

Каждый соответствующий признак x_j(w_i) является предикатом значности k_j, i=1, …, m, j=1, …, n.

Указанный вид функции следует из известного логического тождества:

,

где a конъюнкция характеристик (признаков), определяющих объект, а b - предикат, равный единице, когда w_i становится равным соответствующему определяемому объекту. Такие предикаты будем называть объектными предикатами, а дизъюнкты, содержащие такие предикаты- продукционными дизъюнктами.

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

(Конъюнкция_признаков_1 → Объект₁),

(Конъюнкция_признаков_2 → Объект₂),

…

(Коньюнкция_признаков_m → Объект_m).

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

При нахождении значения логической функции W_X=F(X,W) от n-компонентного вектора логических переменных X=x₁,…, x_n. в качестве итогового результата формируется дизъюнкция w_X только тех подклассов объектов из множества W, значения всех логических переменных при которых содержатся в векторе входных аргументов ^X. Чем большему числу компонентов вектора признаков X удовлетворяет искомый объект, тем большее число подклассов с участием этого объекта в результате будет найдено. В этом случае частотный анализ результирующих подклассов W_X укажет на те объекты, которые наиболее полно удовлетворяют запросу X.

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

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

Очевидно, что такая программа должна удовлетворять следующим требованиям:

1. Обладать универсальностью по отношению к свойствам исследуемых объектов;
2. Выполнять построение и оптимизацию переменнозначных логических функций, полученных на основе исходных данных, описывающих все известные (занесенные в обучающую выборку) объекты;
3. Анализировать структуру построенных логических функций (задача классификации);
4. Производить вычисления в рамках правил многозначных логик, построенных логических функций при заданных значениях параметров вектора X (задача логического поиска).

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

Пользователю необходимо ввести следующие данные:

1. количество переменных (критериев, по которым характеризуются анализируемые объекты);
2. Наименования критериев и значности k_j используемых логических переменных X=(x₁, …, x_n) для описания свойств объектов j=1,…, n;
3. Объекты и их характеристики.

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

После построения переменнозначной логической функции W_X=F(X,W) в соответствии с введенными данными, пользователю предлагается вычислить полученную логическую функцию при заданных значениях характеристик объектов X^*.

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

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

На разработанный программный продукт получено свидетельство о государственной регистрации программы для ЭВМ № 2011616751.

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

В приведенном ниже примере рассматриваются следующие топологии:

1. Полноячеистая – FULL;

2. Звезда – STAR;

3. Кольцевая – RING;

4. Линейная – LINE;

5. Смешанная – MIX.

Эти топологии исследуются по следующим трем критериям:

1. Топологическая надежность A, значностьk_A=4;

2. Стоимость B, значность k_B=3;

3. Быстродействие C, Значность k_C=5.

Будем предполагать, что экспертные оценки сетевых топологий получены, обработаны и преобразованы в соответствующие значения логических предикатов A, B, C с учетом предложенных в ^[3] оценочных функций для рассматриваемых топологий и объединены в начальные продукционные правила ниже приведенного вида.

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

X=(A, B, C).

W(FULL, STAR, RING, LINE, MIX).

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

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

Начало вычислений:

F(X,W)=(3A∨0B∨4C→FULL)∧(2A∨1B∨1C→STAR)∧(0A∨1B∨0C→RING)∧

(1A∨2B∨2C→LINE)∧(2A∨1B∨3C→MIX) =

(0A∨1A∨2A∨1B∨2B∨0C∨1C∨2C∨3C∨FULL)∧

(0A∨1A∨3A∨0B∨2B∨0C∨2C∨3C∨4C∨STAR)∧

(1A∨2A∨3A∨0B∨2B∨1C∨2C∨3C∨4C∨RING)∧

(0A∨2A∨3A∨0B∨1B∨0C∨1C∨3C∨4C∨LINE)∧

(0A∨1A∨3A∨0B∨2B∨0C∨1C∨2C∨4C∨MIX) =

(0A∧0B)∨(0A∧2B)∨(0A∧1C)∨(0A∧2C)∨(0A∧3C)∨(0A∧4C)∨(0A∧RING)∨

(1A∧0B)∨(1A∧1B)∨(1A∧0C)∨(1A∧1C)∨(1A∧3C)∨(1A∧4C)∨(1A∧LINE)∨

(2A∧0B)∨(2A∧2B)∨(2A∧0C)∨(2A∧2C)∨(2A∧4C)∨(2A∧STAR∧MIX)∨(3A∧1B)∨(3A∧2B)∨(3A∧0C)∨(3A∧1C)∨(3A∧2C)∨(3A∧3C)∨(3A∧FULL)∨(0B∧0C)∨

(0B∧1C)∨(0B∧2C)∨(0B∧3C)∨(0B∧FULL)∨(1B∧2C)∨(1B∧4C)∨

(1B∧STAR∧RING∧MIX)∨(2B∧0C)∨(2B∧1C)∨(2B∧3C)∨(2B∧4C)∨(2B∧LINE)∨

(0C∧RING)∨(1C∧STAR)∨(2C∧LINE)∨(3C∧MIX)∨

(4C∧FULL)∨(FULL∧STAR∧RING∧LINE∧MIX)

Анализ структуры функции

Свободные знания:

(0A∧0B),(0A∧2B),(0A∧1C),(0A∧2C),(0A∧3C),(0A∧4C),(1A∧0B),(1A∧1B),

(1A∧0C),(1A∧1C),(1A∧3C),(1A∧4C),(2A∧0B),(2A∧2B),(2A∧0C),(2A∧2C),

(2A∧4C),(3A∧1B),(3A∧2B),(3A∧0C),(3A∧1C),(3A∧2C),(3A∧3C),(0B∧0C),

(0B∧1C),(0B∧2C),(0B∧3C),(1B∧2C),(1B∧4C),(2B∧0C),(2B∧1C),(2B∧3C),

(2B∧4C)

Аксиомы: (0A∧RING),(1A∧LINE),(3A∧FULL),(0B∧FULL),(2B∧LINE),(0C∧RING),

(1C∧STAR),(2C∧LINE),(3C∧MIX),(4C∧FULL)

Разбиениянаклассы: (2A∧STAR∧MIX),(1B∧STAR∧RING∧MIX)

Остатокфункции: FULL∧STAR∧RING∧LINE∧MIX

Поиск топологических структур

Так как переменнозначная логическая функция W_XF(X,W) построена и содержит в логической форме как начальные, так и скрытые закономерности в виде совокупности соответствующих подклассов исследуемых объектов, то теперь мы можем произвести поиск сетевых топологий ТКС, наиболее полно удовлетворяющих сделанному запросу X.

Ниже приведенный запрос означает, что необходимо найти топологию, обладающую высокой топологической надежностью (3A), средней стоимостью (1B) и средней пропускной способностью (1C).

Текущие значения переменных X: 3A,1B,1C

Полученная функция: F(X,W)= (3A∧1B)∨(3A∧1C)∨(3A∧FULL)∨(1B∧STAR∧RING∧MIX)∨(1C∧STAR)∨

(FULL∧STAR∧RING∧LINE∧MIX)

Свободные знания: (3A∧1B),(3A∧1C)

Аксиомы: (3A∧FULL),(1C∧STAR)

Разбиения на классы: 1B∧STAR∧RING∧MIX

Остаток функции: FULL∧STAR∧RING∧LINE∧MIX

Частотный анализ:

FULL = 1/5. STAR = 2/5.

RING = 1/5. MIX = 1/5.

Лучше всего указанному запросу соответствует топология «звезда». ЕЕ вес в общем решении 2/5=0,4. Этот результат лучше, чем все остальные топологии 1/5=0,2.

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

Ослабим требование к топологической надежности (2A), стоимость оставим прежней (1B) и увеличим требование к пропускной способности (2C).

Текущие значения переменных X: 2A,1B,2C

Полученная функция:

F(X,W)=(2A∧2C)∨(2A∧STAR∧MIX)∨(1B∧2C)∨(1B∧STAR∧RING∧MIX)∨(2C∧LINE)∨

(FULL∧STAR∧RING∧LINE∧MIX)

Свободные знания: (2A∧2C),(1B∧2C)

Аксиомы: 2C∧LINE

Разбиения на классы: (2A∧STAR∧MIX),(1B∧STAR∧RING∧MIX)

Остаток функции: FULL∧STAR∧RING∧LINE∧MIX

Частотный анализ:

LINE =1/6 STAR = 2/6

RING = 1/6 MIX =2/6

В этом случае топология «звезда» является наиболее подходящим решением. Однако, ее вес в общем решении равен 2/6=1/3=0,3.

Среди прочих топологий такое решение является наилучшим, так как вес остальных решений равен 1/6=0,17. Но это решение хуже соответствует совокупности предъявленных требований.

Найдем топологию, отвечающую требованиям высокой надежности (3A) и повышенному требованию к быстродействию (4C) при игнорировании стоимости (0B).

Текущие значения переменных X: 3A,0B,4C

Полученная функция:

(3A∧FULL)∨(0B∧FULL)∨(4C∧FULL)∨(FULL∧STAR∧RING∧LINE∧MIX)

Свободные знания: нет

Аксиомы: (3A∧FULL),(0B∧FULL),(4C∧FULL)

Разбиения на классы: нет

Остаток функции: FULL∧STAR∧RING∧LINE∧MIX

Частотный анализ: FULL = 3/3.

Мы видим, что единственным наилучшим решением в этом случае является полноячеистая топология.

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

1. Совокупность знаний, описываемая переменнозначной логической функцией (или системой таких функций) обладает значительной степенью гибкости при добавлении новых знаний: ранее неизвестных типов объектов в рамках уже известных критериев (значений логических предикатов), или расширении знаний: появлении новых актуальных характеристик описывающих новые критерии, не известные на начальном этапе формирования этой базы знаний.
2. Предложенный способ интеллектуальной обработки данных в слабо формализованных областях знаний при неполной и нечеткой информации об анализируемых объектах в условиях противоположного влияния критериев на качество оптимальных решений, обеспечивает свойства адаптивности и самообучения.
3. Свойство переменной значности предикатов позволяет выработать гибкий подход к способу формализации соответствующих характеристик, описывающих актуальные качества анализируемых объектов.

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

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