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

Структурно-функциональное: добавление функционального элемента

В суперпозиции () выбирается элемент так, что ,при и заменяется на , ,

так, что , , j=1,..k , где k - число состояний автомата

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

А3

Структурное: устранение структурного элемента

В маршруте суперпозиции выбирается , переходы и заменяются на ,

Устранены автомата и суперпозиции

А4

Функционально- структурное: добавление структурного элемента

В маршруте суперпозиции выбирается , на переход добавляется вершина v с переходами и

Добавлена вершина v

 

Таблица 5.2

РИ

Тип изменения

Реализация

Формализованное выражение

Результат

А5

Составное функционально-структурное: добавление связного фрагмента из g вершин

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


,
так что ,
j=n+1,..,n+g;

Добавлен подграф из вершин ; условия на топологические характеристики обеспечивают связность автомата.

А6

Составное структурное: устранение связного фрагмента, состоящего из g вершин

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


так, что , j=1,..,n-g

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

А7

Составное из структурного и функционально-структурного

В совокупности D переходов устранены концевые вершины и добавлены другие так что:
, j= 1..L-g;
, где , , j= L-g ..L,
,

Изменены концевые вершины у переходов с выполнением связности по топологическим характеристикам

 

5.6.2. Древовидные решающие структуры систем классификации и распознавания

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

Совокупность структур данного класса С-моделей составляют множества конечных связных орграфов Д = {V, D}, где - множество вершин, - множество дуг (ориентированных ребер); как обычно, орграф считаем ордеревом, растущим из корня , если он связан, не имеет контуров, и единственный маршрут из к любой , i=2..n. является путем .

Число вершин, составляющих маршрут , равно и совпадает с номером уровня вершины .

Любое дерево характеризуется следующими параметрами:

- степенью исхода для каждой вершины

Максимальный уровень дерева называют его высотой .

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

Равномерное дерево с точностью до изоморфизма определяется конечной последовательностью натуральных чисел , где h - высота дерева.

Вершины решающего дерева , j=1..n отличаются реализуемыми преобразователями , входящими в функциональный базис {f, J}.

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

В результате древовидные С-модели представляют собой те или иные решающие функции.

При этом задача построения булевых решающих деревьев сводится:

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

Пусть на множестве Х допустимых символов заданно конечное число подмножеств (классов) таких, что

.
Каждый сигнал x определяется значениями характеристик т.о., что их совокупность дает описание J(x) сигнала x (характеристики , j=1..N, называются признаками).

Нетрудно заметить, что в древовидной решающей структуре любой маршрут 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

Минимизация СКО при неравноценном предсказании

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

По истечении времени T осуществляется сброс накопленного и процесс контролируется по новым накапливаемым значениям и .