Формирование ассоциативных темпоральных правил в базах данных временных рядов на основе темпоральных сетевых моделей

Размещено на http://www.allbest.ru/

ФОРМИРОВАНИЕ АССОЦИАТИВНЫХ ТЕМПОРАЛЬНЫХ ПРАВИЛ В БАЗАХ ДАННЫХ ВРЕМЕННЫХ РЯДОВ НА ОСНОВЕ ТЕМПОРАЛЬНЫХ СЕТЕВЫХ МОДЕЛЕЙ

С.М. Ковалев (ksm@real36.com)

Ростовский университет путей сообщения, Ростов на Дону

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

1. Постановка задачи

Основными объектами рассмотрения статьи являются символьные временные ряды (ВР), и темпоральные ассоциативные правила (ТМП).

Под символьным ВР понимается упорядоченная последовательность символов из конечного множества Q, соотнесенных с фиксированными моментами временина дискретной временной шкалеT:

.

ТМПCописывает причинно-следственные зависимости между темпоральными образами во ВР и заявляется в форме продукционного правила:

где q - целевой символ, G - описание темпорального образа, предшествующего символу q.

ТМП, как элементы знаний, должны удовлетворять ряду требований и, в первую очередь, требованиям полноты, непротиворечивости и интерпретационной пригодности. Непротиворечивость ТМП означает, что каждое вхождение темпорального образа, указанного в антецеденте ТМП, во ВР однозначно обуславливает следование за ним символа q. Полнота системы ТМП означает, что для любого вхождения символаво ВРS в системе ТМП найдется правило, обуславливающее появление данного символа. Интерпретационная пригодность ТМП характеризует возможность представления ТМП в виде компактного вербализованного описания с минимальным числом переменных и логических связок.

Рассмотрим общую структуру и детали организации ТМП, удовлетворяющего выше приведенным требованиям. Предлагаемый подход к организации ТМП базируется на идеях работы [Гладун, 1987], в которых процедуры обобщения осуществляются на основе аппарата растущих пирамидальных сетей (РПС) с использованием двух типов прямых и инверсных признаков.

Семантику ТМП определяет темпоральная логическая формула, представленная в антецеденте правила и описывающая обобщенный образ одного или нескольких временных сценариев, предшествующих появлению символа qво ВР S. Переменными темпоральной формулы являются темпорально-метрические отношения, имеющие смысл выражения “В предшествии k тактов присутствовал символ g”, и определяемые для каждого момента :

(1.1)

темпоральный сетевой модель

Темпоральная формула, описывающая антецедент ТМП, имеет вид выражения:

(1.2)

где - темпоральные отношения типа (1.1).

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

Задача состоит в том, чтобы для заданного целевого символа на основе анализа ВР S сформировать полную систему непротиворечивых ТМП, удовлетворяющих критерию интерпретационной пригодности.

Приведенная постановка относится к классу задач индуктивного обобщения данных по их признаковым представлениям. Для решения подобного рода задач существует множество подходов, например [Вагин, 2004], [Nguyenetal., 1997], среди которых авторы хотели бы выделить методы признаковых обобщений на основе аппарата РПС [Гладун, 1987], положенные в основу разрабатываемого подхода.

2. Темпоральная сетевая модель

ТМПС [Ковалев, 2005] является видоизмененным вариантом РПС [Гладун, 1987] и ориентирована на формирование обобщенных описаний для темпоральных данных. ТМПСопределяется для заданногоцелевого символа ВР Sи представляет собой трехслойный сетевой граф, каждый слой вершин которого соответствует определенному уровню обобщения темпоральных данных. Первый слой ТМПС соответствуют первичным признакам - отношениям , а вершины второго и третьего слоев соответствуют коньюнктивным группам обобщаюших и детализирующихпризнаков. Описания обобщенных классов явным образом отображаются в структуре ТМПС и записываются в виде логических формул(1.2).

Формальному представлению ТМПС предпошлем ряд определений,

Пусть S - ВР и-целевой символ ВР, относящийся к некоторому моменту времени. Введем в рассмотрение параметр L, обозначающего ширину окна, в пределах которого выявляется причинная связь между символамиВР S, и зададимся некоторым конкретным его значением. Для символавыпишем l предшествующих ему символов и представим временной сценарий, предшествующий вхождению символа qво ВР Sмомент, в виде множества, состоящего изl отношений типа (1.1),

.

которое назовемВР относительно символа .

Обозначим черезмножествовсех временных сценариев, предшествующих целевому символу q,представленному в виде множества всех -окон ВР S. Разобьем E на две группы положительных и отрицательныхпримеров:

.

Модель ТМПС задается в виде сетевого ациклического графа , множество вершин которого разбито на три слоя так, что слой T соответствует входному множеству первичных признаков , слой G - множеству обобщающих признаков, а слой D - множеству детализирующих признаков. Отображение Г задает структуру межслойных связей таким образом, что вершины входного слоя T связаны исходящими дугами с вершинами второго и третьего слоя, образуя соответственно коньюнктивные группы обобщающих и детализирующих признаков. Вершины второгослоя связаны с вершинами третьего слоя, устанавливая соответствие между обобщающими и детализирующими признаками.

Следует отметить, что первый (входной) слой сетевого графа H для заданного ВР Sи ширины окна l определяется однозначно, в то время как вершины второго и третьего слоя вместе с отображением Г могут быть сформированы различными способами, однако, должны удовлетворять ряду условий, вытекающим из постановки задачи обобщения.

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

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

то есть, для каждого положительного примера e+ в обобщающем слое ТМПС должна найтись вершина g, входящая своим признаковым подмножеством в этот пример.

Вершины детализирующего слоя должны удовлетворять отсекающему условию

(2.1)

Последнее условие, фактически, является переформулировкой предложенного в [Гладун, 1987] одного из правилвыделения контрольных вершин в РПС.

Заметим, что сетевой граф ТМПС Hорганизован таким образом, что каждому из его подграфов, образованному обобщающей вершиной g и связанным с ней подмножеством детализирующих вершин, вместе с соответствующими признаковыми подмножествами и однозначно отвечает формула (1.2), описывающая некоторое множество темпоральных сценариев, предшествующих символу q. Обобщающая вершина своим признаковым подмножеством соответствует обобщающему коньюнкту темпоральной формулы, а связанные с ней детализирующие вершины своими признаковыми подмножествами характеризуют инверсные коньюнкты.

3. Пример ТМПС

Ниже приведен пример ТМПС для ВР целевого символа x и окна анализа .

Рис. 1. Структура ТМПС для рассматриваемого примера.

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

Выше описанная модель ТМПС является сетевой моделью, в структуре которой объединены образы всех сценариев, предшествующих вхождению символа xво ВР S.В частности, приведенная на рис. 1 структура реализует темпоральное ассоциативное правило вывода:

Система ТМП для БЗ формируется путем извлечения темпоральных образов из структуры ТМПС и сопоставления им соответствующих темпоральных формул в качестве антецедентов ТМП.

4. Оптимизация ТМПС

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

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

,(4.1)

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

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

,

имеющего смысл выражения “В предшествии k тактов в течение nтактов наблюдался символ g”.

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

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

Пусть g - обобщающий признак.множество отрицательных, а множество положительных примеров относительно g. В силу отсекающего условия (2.1) для любого i-го отрицательного примера должен найтись детализирующий признак , который своим признаковым множеством включается в и не включается ни в один из положительных примеров. Это требование удовлетворяется тогда и только тогда, когда для каждого из положительных примеров в детализирующем признаке d найдется отношение , входящее ви не входящее в , то есть принадлежащее разности множеств. Данному условию отвечает следующий дизьюнкт

. (4.2)

Условие (4.2) должно выполняться для всех положительных примеров , чему отвечает коньюнкт:

. (4.3)

Очевидно, что любая из импликант выражения (4.3) удовлетворяет отсекающему условию (2.1) относительно отрицательного примера, а, следовательно, может быть использована в качестве детализирующего признака для i-го отрицательного примера . Раскрыв скобки в (4.3) и, используя закон поглощения, получаем выражение, характеризующее множество всех минимальных импликант(признакам, с минимальным числом входящих в них отношений):

,

где j-я импликанта выражения (4.3).

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

, (4.4)

где z - количество отрицательных примеров.

Раскрыв скобки в (4.4) ииспользуя закон поглощения, приходим к выражению, характеризующему все минимальные подмножества детализирующих признаков:

(4.5)

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

Выше приведенные рассуждения положены в основу алгоритма формирования оптимальных множеств детализирующих признаков для ТМПС. Исходные данные для алгоритма представляются в виде прямоугольной матрицы, строки которой соответствуют темпоральным отношениям . Столбцы матрицы объединены в z групп, соответствующих отрицательным примерам, каждая из которых содержит по m столбцов, соответствующих положительным примерам. На пересечении n-й строки и j-го столбца i-й группы проставляется 1, если n-й признак входит в подмножество . Алгоритм формирования детализирующих признаков сводится к процедуре поиска оптимального строкового покрытия объединенной матрицы.детализирующем слоях.

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

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

Список литературы

[Вагин и др., 2004] В.Н. Вагин и др. Методы теории приближенных множеств в решении задач обобщения понятий. Известия РАН. ТиСУ, 2004, №6.

[Гладун, 1987]Гладун В.П. Планирование решений. - Киев: Наукова думка. 1987.

[Ковалев, 2005]Ковалев С.М. Формирование темпоральных баз знаний на основе аппарата растущих пирамидальных сетей // Интегрированные модели и мягкие вычисления в искусственном интеллекте. Сб. научн. тр. III Международного научно-практического семинара. - М.: Физматлит, 2005.

[Nguyen et al., 1996]Nguyen S.N., Nguyen H.S. Some efficient algorithms for rough set methods // Bouchon-Meunier, Delgado, Verdegay, Vila, and Yager, 1996.

Размещено на Allbest.ru