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

С.М. Ковалев¹

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

Введение

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

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

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

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

1. Представление темпоральных образов в БД ВР

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

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

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

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

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

Лежащие в основе второго направления поиска знаний идеи заключаются в символьной или лингвистической аппроксимации фрагментов ВР типовыми шейпами с последующим объединением их в структуры, допускающие простую текстовую или смысловую интерпретацию. Наиболее яркими представителями данного направления являются методы Порождения Естественного Языка (NLG) [13], формирующие представления, отличающиеся высокой степенью интерпретационной пригодности, перцептивные модели [20] и гибридные нечетко-трендовые описания ВР [14].

К третьему направлению в области представления темпоральных знаний относятся специализированные языки правил, предназначенные для описания темпоральных образов и явлений. К ним относятся Унификационная Темпоральная Грамматика [15], представляющая собой иерархический язык правил, разработанный для описания сложных темпоральных образов в многомерных ВР, а также TSKR – методология [16], представляющая собой абстрактный иерархический язык правил, способный отражать все основные темпоральные концепты знаний.

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

Временным рядом называется множество упорядоченных временных отсчетов вместе с соответствующими им числовыми или символьными значениями:

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

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

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

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

Нечетким темпоральным образом СОБЫТИЯ называется двойка

, (1)

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

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

где - степень близости значения ВР номинальному значению C.

Второй уровень иерархической модели представлен типом образа нечеткого темпорального ОТНОШЕНИЯ, в основу определения которого положено обобщение понятия темпорального отношения Аллена на случай нечетких событий [17]

Пусть RT - семейство отношений Аллена, включающее 13 базовых зависимостей.

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

Характеристическая функция нечетко-темпорального отношения определяется на основе выражения

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

где - характеристическая функция ДФ-образа, определяемая как

Третий верхний уровень иерархической модели представлен нечетким темпоральным образом СТРУКТУРА, характеризующим наличие нескольких нечетко-темпоральных отношений на заданном временном интервале.

где – название структуры, - нечеткая характеристическая функция, определяемая на основе выражения

.где - нечеткие характеристические функции образов ОТНОШЕНИЙ, входящих в структуру.

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

где - НТП, Р – подмножество тепморальных отношений Алена, включающее три отношения: СТЫК, СЛЕДОВАНИЕ), СОВПАДЕНИЕ.

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

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

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

Ниже на рис. 1 приведен заимствованный из [19] пример графика функции ошибки Е-сети, работающей в режиме предсказания результатов логической операции ИЛИ. Сеть предсказывает каждый последующий символ как результат операции ИЛИ над двумя предыдущими.

Рис. 1. График ошибки предсказания результата операции ИЛИ. Ошибка падает на тех отсчетах, для которых оказывается возможным корректное предсказание; на других отсчетах ошибка высокая.

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

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

Рис. 2. Гибридная Е-сеть для выявления темпоральной структуры ВР

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

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

1. 
   А.П. Еремеев, В.В. Троицкий. Модели представления временных зависимостей в интеллектуальных системах поддержки принятия решений // Известия РАН. Теория и системы управления. 2003. №5, с. 75-88.
   
2. 
   C. Mooney and J. F. Roddick. Mining relationships between interacting episodes. In M. W. Berry, U. Dayal, C. Kamath, and D. B. Skillicorn, editors, Proceedings of the 4th SIAM International Conference on Data Mining (SDM'04). SIAM, 2004.
   
3. 
   J. F. Roddick and C. H. Mooney. Linear temporal sequences and their interpretation using midpoint relationships. IEEE Transactions on Knowledge and Data Engineering, 17(1):133-135, 2005.
   
4. 
   J. Wang and J. Han. BIDE: E_cient mining of frequent closed sequences. In Proceedings of the 20th International Conference on Data Engineering (ICDE'04), pages 79-90. IEEE Press, 2004.
   
5. 
   P. Tzvetkov, X. Yan, and J. Han. TSP: Mining Top-K closed sequential patterns. In Proceedings of the 3rd IEEE International Conference on Data Mining (ICDM'03), pages 347-354. IEEE Press, 2003.
   
6. 
   Hoppner. Discovery of temporal patterns - learning rules about the qualitative behaviour of time series. In L. D. Raedt and A. Siebes, editors, Proceedings of the 5th European Conference on Principles of Data Mining and Knowledge Discovery (PKDD'01), pages 192-203. Springer, 2001.
   
7. 
   J. F. Allen. Maintaining knowledge about temporal intervals. Communications of the ACM, 26 (11):832-843, 1983.
   
8. 
   Y. Shahar. A framework for knowledge-based temporal abstraction. Arti_cial Intelligence, 90 (1-2):79-133, 1997.
   
9. 
   P. R. Cohen, C. Sutton, and B. Burns. Learning effects of robot actions using temporal associations. In Proceedings of the 2nd International Conference on Development and Learning, pages 96-101. IEEE Press, 2002.
   
10. 
    P.-S. Kam and A. W.-C. Fu. Discovering temporal patterns for interval-based events. In Y. Kambayashi, M. K. Mohania, and A. M. Tjoa, editors, Proceedings of the 2nd International Conference on Data Warehousing and Knowledge Discovery (DaWaK'00), pages 317-326. Springer, 2000.
    
11. 
    D. DuBois and H. Prade. Processing fuzzy temporal knowledge. IEEE Transactions on Systems, Man and Cybernetics, 19(4):729-744, 1989.
    
12. 
    S. Badaloni and M. Giacomin. A fuzzy extension of Allen's interval algebra. In E. Lamma and P. Mello, editors, AI*IA99: Advances in Artificial Intelligence, pages 155-165. Springer, 2000.
    
13. 
    S. G. Sripada, E. Reiter, and J. Hunter. Generating English summaries of time series data using the Gricean maxims. In L. Getoor, T. E. Senator, P. Domingos, and C. Faloutsos, editors, Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'03), pages 187-196. ACM Press, 2003b.
    
14. 
    Ярушкина Н.Г. Нечеткие нейронные сети – когнитивный и прикладной потенциал // Интегрированные модели и мягкие вычисления в искусственном интеллекте. Сб. научн. тр. III Международного научно-практического семинара. – М.: Физматлит, 2005. С. 57-62.
    
15. 
    G. Guimaraes and A. Ultsch. A symbolic representation for pattern in time series using definitive clause grammars. In R. Klar and O. Opitz, editors, Proceedings of the 20th Annual Conference of the German Classi_cation Society (GfKl'96), pages 105-111. Springer, 1997.
    
16. 
    F. Morchen Time Series Knowledge Mining Dissertation Marburg/Lahn 2006
    
17. 
    Л.С. Берштейн, С.М. Ковалев. Нечеткие темпоральные модели акустических процессов в интеллектуальных системах автоматического распознавания речи // Известия РАН. ТиСУ, 2004. №6, С. 74-79.
    
18. 
    Ковалев С.М. Формирование темпоральных баз знаний на основе аппарата растущих пирамидальных сетей // Интегрированные модели и мягкие вычисления в искусственном интеллекте. Сб. научн. тр. III Международного научно-практического семинара. – М.: Физматлит, 2005. С. 351-357.
    
19. 
    J. Elman. Finding Structure in Time. COGNITIVE SCIENCE, University of California, San Diego. 14, 179-211 (1990).
    
20. 
    [Batyrshin I.Z., Sheremetov L.B. Perception based associations in time series data bases. In: NAFIPS 2006, Canada, Montreal, 2006.
    

RGU PS, Rostov-on-Don, Lenina st. 44