Статья:

ПРИМЕНЕНИЕ ТАБЛИЦЫ РЕШЕНИЙ ДЛЯ АВТОМАТИЗАЦИИ СЕЛЕКЦИИ ПО МНОЖЕСТВУ НЕЗАВИСИМЫХ ПРИЗНАКОВ

Конференция: XXIII Студенческая международная заочная научно-практическая конференция «Молодежный научный форум: технические и математические науки»

Секция: 3. Информационные технологии

Выходные данные
Курлов В.В. ПРИМЕНЕНИЕ ТАБЛИЦЫ РЕШЕНИЙ ДЛЯ АВТОМАТИЗАЦИИ СЕЛЕКЦИИ ПО МНОЖЕСТВУ НЕЗАВИСИМЫХ ПРИЗНАКОВ // Молодежный научный форум: Технические и математические науки: электр. сб. ст. по мат. XXIII междунар. студ. науч.-практ. конф. № 4(23). URL: https://nauchforum.ru/archive/MNF_tech/4(23).pdf (дата обращения: 12.10.2024)
Лауреаты определены. Конференция завершена
Эта статья набрала 1 голос
Мне нравится
Дипломы
лауреатов
Сертификаты
участников
Дипломы
лауреатов
Сертификаты
участников
на печатьскачать .pdfподелиться

ПРИМЕНЕНИЕ ТАБЛИЦЫ РЕШЕНИЙ ДЛЯ АВТОМАТИЗАЦИИ СЕЛЕКЦИИ ПО МНОЖЕСТВУ НЕЗАВИСИМЫХ ПРИЗНАКОВ

Курлов Василий Васильевич
студент НИУ «Белгородский государственный университет», РФ, г. Белгород
Бурданова Екатерина Васильевна
научный руководитель, доц. НИУ «Белгородский государственный университет», РФ, г. Белгород

 

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

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

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

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

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

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

Таблица 1.

Таблица решений


Признаки


1


2


3


4


5


6


7


8


9


10


Признак A


ДА


ДА


ДА


ДА


ДА


ДА


НЕТ


НЕТ


НЕТ


НЕТ


Признак B


ДА


ДА


*


НЕТ


НЕТ


НЕТ


ДА


ДА


ДА


НЕТ


Признак C


*


ДА


НЕТ


ДА


ДА


НЕТ


ДА


НЕТ


НЕТ


*


Признак D


ДА


НЕТ


НЕТ


ДА


НЕТ


ДА


*


ДА


НЕТ


*


Категории


 


 


 


 


 


 


 


 


 


 


Категория 1


 


X


 


 


X


 


 


 


 


X


Категория 2


 


X


 


X


 


 


X


 


 


X


Категория 3


 


 


 


 


 


 


 


X


 


X


Категория 4


 


 


 


X


 


X


 


 


 


X


Категория 5


X


 


X


 


 


 


X


X


 


 


Категория 6


X


 


X


X


X


X


 


 


X


 

 

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

Одним из способов обработки таблиц решений, является построение эквивалентного ей дерева решений (ДР). Для этого на основе таблицы решений строится система логических функций , где m — число признаков в таблице решений. Логическая функция представляется следующим образом:

                                                       (1)

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

При этом , если наличие признака ; , если состояние условия  и буква  отсутствует в формуле, если состояние условия не имеет значения. Подробно алгоритм получения системы логических функций описан в [1].

Таблица решений является обобщённым представлением всех возможных деревьев решений, следует отметить, что уже при семи условиях, число возможных деревьев решений будет равно 19*1026. Таким образом, поиск оптимального ДР путем полного перебора невозможен.

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

Таблица 2.

Характеристики системы


Переменная


Число вхождений


A


10


B


9


C


8


D


8

 

ДР построенная согласно полученному порядку проверки переменных представлена на рис. 1. Число условных вершин: 11.

 

Рисунок 1. ДР с порядком проверки A> B> C> D

 

Как можно было заметить из таблицы 2, переменные C и D обладают равным числом вхождений. Поэтому, меняя местами эти переменные в порядке проверки состояний условий, можно получить ДР с большим числом вершин чем в диаграмме, представленной на рисунке 1. ДР с порядком проверки A> B> D> C представлена на рис. 2.

 

Рисунок 2. ДР с порядком проверки A> B> D> C

 

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

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

                                                                (2)

где: i — число переменных;

j — число функций.

Элемент  принимает следующие значения:

·     1, если в функции , для переменной , ;

·     0, если в функции , для переменной , ;

·     -1, если в функции , переменная отсутствует.

Матрица характеристик для таблицы решений процесса селекции представлена в табл. 3.

Таблица 3.

Структурные характеристики


 


F1


F2


F3


F4


F5


F6


F7


F8


F9


F10


C1


1


1


1


1


1


1


0


0


0


0


C2


1


1


-1


0


0


0


1


1


1


0


C3


-1


1


0


1


1


0


1


0


0


-1


C4


1


0


0


1


0


1


-1


1


0


-1

 

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

1.  Первой выбирается переменная, номер которой соответствует строке с наибольшей суммой числом неотрицательных элементов:

                                                                     (3)

где:  — сумма элементов строки

Если для двух переменных с номерами k и r, = то выбирается переменная с номером k, если k <r; r, если r<k

2.  Далее из исходной строятся левая и правая подматрицы:

·     Левая подматрица состоит из тех столбцов где , при этом k-ая строка вычеркивается.

·     Правая подматрица состоит из тех столбцов где , при этом k-ая строка вычеркивается.

·     После этого пункты 1 и 2 выполняются для каждой подматрицы.

Дерево решений, полученное в соответствии с определенным выше порядком проверки, будет выглядеть как на рис. 4

 

Рисунок 3. Асимметричное дерево решений

 

Как можно заметить, число вершин в дереве решений равно 9. Что позволит уменьшить количество логических проверок.

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

Так же на основе дерева решений легко строится программная реализация алгоритма, что позволяет создавать программы для автоматизации селекции.

 

Список литературы:
1.    Муромцев В.В. Методы синтеза логических схем: Учебное пособие. — 2-е изд., перераб. и доп. — Белгород: Изд-во БелГТАСМ, 2001. — 78 с.
2.    Хайнби Э. Программирование таблиц решений. — М.: Мир, 1976. — 89 с.