5.6. Древовидные решающие структуры систем классификации и распознавания.
5.6.1. Класс автоматных моделей (конечные автоматы Мили)
Рассмотрим класс детерминированных конечно-автоматных моделей в классе детерминированных конечных автоматов Мили. Как известно, детерминированный конечный автомат Мили задан входным алфавитом
, выходным алфавитом
, множеством состояний
, функцией выходов
, функц
ией переходов
, где
,
и
- соответственно входной символ, выходной символ и состояние автомата в момент времени t, t = 1,2,...,T. Таким образом, конечный автомат реализует автоматное отображение символов (слов), составленных из символов входного алфавита, в сигналы, составленные из символов выходного алфавита, характер отображения зависит от начального состояния
, в котором подается первый символ сигнала
, где k - длина слова.
Задача идентификации в виде автоматного отображения предполагает наличие обучающей выборки входных и выходных сигналов, находящихся в отображении F, которое неизвестно, и приближает отображение
, где
- класс автоматных отображений. Ориентируясь на применение эволюционного синтеза будем рассматривать в качестве
класс СМ - связанных конечных автоматов с числом состояний не более N как СМ - модель автомат А и определяется функциональным базисом. и структурой
. Последняя задается графом G = (V,D) , где V- совокупность n вершин, D - совокупность дуг, соединяющих вершины.
Функции f совокупности реализуют частные отображения входного символа
, в выходной
и расположены в вершинах графа,
- число различных функций f. При табличном представлении структура задается s-подтаблицей, а каждой функции f соответствует строка у подтаблицы.
Используя определение эволюционного синтеза, сформируем список базовых изменений конечного детерминированного автомата.
Для этого необходимо установить простые элементы, функциональные элементы - это функции набора , преобразующие символ алфавита
в символ алфавита
, в данном случае это переключательные функции. При заданных p и q – размерностях соответственно входного и выходного алфавитов, множество переключательных функций имеет мощность pq.
Функция изменения заключается в добавлении или устранении простых элементов совокупности {f, J}, которые не меняют структуры автомата и не выводят его за пределы данного класса. Фиксируя уровень детализации рассматриваемого класса моделей, предполагаем далее, что функции являются простыми элементами. Простое функциональное изменение автомата сводится по определению к устранению некоторого элемента
из суперпозиции
. Ясно, что такое изменение может происходить без изменения структуры лишь в случае замены
на
(
).
По определению простое структурно-функциональное изменение - это добавление функции в указанную выше суперпозицию. Оно реализуется без изменения структуры элементов лишь в том случае, когда осуществляется замена
на
.
Структурные простые элементы автоматных моделей - это элементы множества и
графа G = (V, D).
Поэтому простые структурные изменения - это устранение вершины из множества V, а так же устранение дуги из множества D. Соответствующим образом формируются функционально-структурные изменения, которые сводятся к добавлению вершины либо дуги в соответствующие множества.
Как известно, в связном автомате для любого входного символа существует переход в следующее состояние. С учетом этого структурные и функционально-структурные изменения на дугах не реализуемы в отдельности. Однако, реализуемыми являются изменения, заключающиеся в изменении структурного элемента “вершина + переход”. В результате получаем список базовых изменений, приведенных в таблице 5.1, называемый далее "классическим".
Результатам выполнения A1 является замена в суперпозиции и символов выходных функций, формируемых в вершине
. При выполнении A2 меняется часть суперпозиции и той совокупности выходных функций, в формировании которых участвовала устраненная вершина
, начиная с первого появления
в суперпозиции.
Неизменной остается часть суперпозиции и выходных функций до первого попадания в в случаях A3 и A4. При необходимости список РИ увеличивается путем реализации составных изменений, получаемых многократным использованием базовых РИ. С этой целью вероятным выбором осуществляется задание g>1 кратности исполнения базового РИ. В целом это приводит к увеличению мощности изменения, выходных функций конечного автомата за одну реализацию РИ. Список РИ является классическим, но при реализации выбранного РИ допускается его g-кратное исполнение, что приводит к составному изменению. Такой список P и называется "полуклассическим".
Если при реализации полуклассического списка РИ учитываются топологические характеристики автомата, то такой список РИ отличается обязательностью фрагментального изменения автомата. В качестве топологической характеристики, отражающей структурные особенности автомата используется "связность", как конкретно выражается в степенях вершин графа – структуры ( - число входящих и
- число исходящих дуг вершины v)
Соответствующий список РИ приведен в таблице 5.2.
Таблица 5.1
РИ |
Тип изменения |
Реализация |
Формализованное выражение |
Результат |
А1 |
Функциональное: устранение функционального элемента |
В суперпозиции ( |
|
Заменена переключательная функция состояния |
А2 |
Структурно-функциональное: добавление функционального элемента |
В суперпозиции ( |
|
Заменена переключательная функция состояния |
А3 |
Структурное: устранение структурного элемента |
В маршруте |
|
Устранены |
А4 |
Функционально- структурное: добавление структурного элемента |
В маршруте |
|
Добавлена вершина v |
Таблица 5.2
РИ |
Тип изменения |
Реализация |
Формализованное выражение |
Результат |
А5 |
Составное функционально-структурное: добавление связного фрагмента из g вершин |
В совокупность вершин V добавляется g вершин с переходами, связных между собой, и с вершинами V с учетом топологических характеристик связности |
![]() ![]() так что ![]() j=n+1,..,n+g; ![]() ![]() |
Добавлен подграф из вершин |
А6 |
Составное структурное: устранение связного фрагмента, состоящего из g вершин |
В совокупности вершин V, участвующих в суперпозиции, выбирается g связных вершин, которые устраняются с учетом их топологических характеристик. |
![]() ![]() ![]() |
Устранен подграф из вершин |
А7 |
Составное из структурного и функционально-структурного |
В совокупности D переходов устранены концевые вершины и добавлены другие | ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
Изменены концевые вершины у переходов с выполнением связности по топологическим характеристикам |
5.6.2. Древовидные решающие структуры систем классификации и распознавания
В последнее время с развитием программных технологий древовидные решающие модели получают широкое распространение в задачах генерации формальных описаний классов, организации структур данных и т.п.
Совокупность структур данного класса С-моделей составляют множества конечных связных орграфов Д = {V, D}, где - множество вершин,
- множество дуг (ориентированных ребер); как обычно, орграф считаем ордеревом, растущим из корня
, если он связан, не имеет контуров, и единственный маршрут из
к любой
, i=2..n. является путем
.
Число вершин, составляющих маршрут , равно
и совпадает с номером уровня
вершины
.
Любое дерево характеризуется следующими параметрами:
Максимальный уровень дерева называют его высотой .
Равномерное дерево с точностью до изоморфизма определяется конечной последовательностью натуральных чисел , где h - высота дерева.
Вершины решающего дерева , j=1..n отличаются реализуемыми преобразователями
, входящими в функциональный базис {f, J}.
В качестве преобразователей в различных решающих древовидных структурах используются k-местные предикаты, описания объектов, булевы переменные, лингвистические переменные.
В результате древовидные С-модели представляют собой те или иные решающие функции.
При этом задача построения булевых решающих деревьев сводится:
Эффективной считается модель с минимальной вероятностью ошибки обучающей выборки. Такой подход рассматривается далее в эволюционном распознающем алгоритме.
Пусть на множестве Х допустимых символов заданно конечное число подмножеств (классов) таких, что
Нетрудно заметить, что в древовидной решающей структуре любой маршрут l задает совокупность xарактеристик сигнала, составляющих некоторое описание .
Доопределим структуру D следующим образом: сопоставим каждой дуге, выходящей из концевой вершины метку с номером k=1..K класса, к которому относится описание
сигнала по
и
, где
- обучающая выборка, известная априорно.
В результате совокупность маршрутов дерева, заканчивающаяся метками k, определяет описание класса сигналов
, а совокупность маршрутов дерева в целом определяет совокупность
описаний всех K классов, и т.о. дерево доопределяет разбиение
допустимых сигналов Х на множества
.
Поскольку описания формируются по априорной информации
, заведомо не являющейся исчерпывающей, то возможны
для которых
. Тогда разбиение
характеризуется вероятностью ошибки классификации сигнала Х, имеющего вероятностное распределение P(Х) :
(1)
где (2)
Отсюда следует задача синтеза такого дерева , для которого совокупность
обеспечивает вероятность ошибочной классификации не более
с заданной вероятностью или минимизирует вероятность ошибочной классификации
или
.
Нетрудно заметить, что совокупность конечных маршрутов есть подмножество суперпозиций функциональных преобразователей принятого базиса {f, J}. Каждая суперпозиция определяется конкретным набором
, примененным к вершинам маршрута
, их очередностью и длинной
маршрута. Все эти факторы определяются указанными выше параметрами Д- структуры, поэтому синтез требуемого дерева
и соответственно разбиения
целесообразно проводить путем структурных изменений некоторого дерева
на основе списка РИ.
Переходя к формированию списка РИ древовидной структуры отметим ее специфику, в частности иерархичность. Она приводит к тому, что ФП, приписываемая вершинам с меньшим номером уровня участвуют в большей части маршрутов дерева и поэтому более существенны для классификации реализуемой деревом.
Таким образом, уровень дерева, на котором реализуется РИ, является параметром, характеризующим степень изменения дерева, и поэтому учитывается при составлении списка РИ.
В соответствии с определением эволюционного синтеза сформируем список базовых изменений Д-структуры. Функциональные элементы древовидной С-модели - это функции набора {f, J}, являющиеся характеристиками сигналов (то есть признаками).
Эти признаки могут быть как логическими, так и вещественными функциями различной сложности, что является принципиальным отличием древовидных моделей от конечно-автоматных, порождая множество классов, отличающихся функциональным базисом.
Простые функции этих базисов определяются, как функции не декомпозируемые далее без нарушения класса моделей. Тогда простое функциональное изменение древовидной модели сводится по определению к устранению некоторого элемента
, j=1..l из суперпозиций
, реализуемой маршрутом
.
Простое структурно-функциональное изменение древовидной модели сводится к добавлению в суперпозицию
.
Положение элементов в суперпозиции в обоих случаях определяется случайно.
Структура равномерного дерева, в отличие от структуры конечного автомата состоит из одного типа простого элемента: вершины v с выходящими ребрами. В результате имеем следующее структурное изменение - устранить вершину, и функционально-структурное - добавить вершину в дерево.
Так, как каждая вершина древовидной решающей структуры является одновременно и функциональным элементом , то очевидно любое структурное изменение дерева является его функциональным изменением . С другой стороны, функциональные и структурно – функциональные изменения (Д1, Д2) дерева, включая устранение элемента
из суперпозиции (маршрута), могут приводить к изменению маршрутов и вовлечению других функциональных элементов, то есть на ином элементарном материале.
Список базовых РИ состоит из изменений, приведенных в таблице 5.3.
Список базовых изменений привлекателен тем, что его реализация наиболее проста, однако, как показывает анализ, РИ Д5 однократная реализация Д1-Д4 практически никогда не приведет к такому функциональному изменению дерева
Более направленным, как и более сложным в реализации, является список РИ на составных элементах Д-структур, то есть на фрагментах того или иного размера. При этом размер фрагмента и его конкретное местоположение достаточно определить степень изменения дерева. Соответствующие составные РИ приведены в таблице 5.4.
5.6.3. Методика синтеза конечно-автоматных предсказывающих моделей
Согласно результатам исследований в условиях максимальной априорной неопределенности целесообразно начинать синтез в классе графовых С-моделей с простейшим функциональным базисом, состоящим из переключательных функций, то есть в классе конечно-автоматных моделей.
Опишем методику эволюционного синтеза эффективных -приближений, в данном классе С-моделей при решении задач прогнозной оценки параметра.
Эволюционный синтез начинается с задания конкретного класса конечных автоматов и осуществляется при конкретизации параметров и частных алгоритмов формирования автоматов в процессе СП и выработки предсказаний относительно ожидаемого значения параметра.
При отсутствии информации относительно максимального числа состояний n и значимостей p – выходного алфавита определение этих параметров типа списка РИ, а также параметров, регламентирующих процессы синтеза конечных автоматов и фактические предсказания, базирующиеся на предварительных вычислительных экспериментах с пакетом программ прогнозной оценки (ПППО) в диалоговом режиме.
Основная стратегия диалога предполагает постепенное усложнение алгоритма эволюционного синтеза и его программных реализаций. Поэтому при отработке параметров p, q, и n целесообразно максимально упрощать алгоритм синтеза. Это достигается при следующих исходных параметрах и процедурах:
Рис.1
,
Номер |
Цель предсказания |
Элементы матрицы С |
1 |
Минимизация модуля ошибки предсказания |
|
2 |
Минимизация СКО |
|
3 |
Минимизация СКО при равноценном предсказании |
|
4 |
Минимизация СКО при неравноценном предсказании |
|
, l=1,2,3
где - показатель эффективности автомата
по функционалу
;
параметры многократности использования С-модели и РИ при первичных отладочных экспериментах предполают равными 1. В дальнейшем возможна обработка других кратностей: 2,3 и т.д.
В противном случае число допустимых ошибочных предсказаний за время T оценивается по зависимости , в которой определяется число предсказаний
за время T, а желаемое число правильных предсказаний
.
По истечении времени T осуществляется сброс накопленного и процесс контролируется по новым накапливаемым значениям
и
.