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

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

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

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

. , для СА ресурсов и сроков выполнения работ его реализация возможна в опреде-

, . многоаспектности СА и применимости его практически в любой сфере деятельно, ,

, .

В ходе проделанной работы была предложена методика проведения СА, представлен пример ее реализации. Показано, что разработка математических моделей и их реализация в ИС является необходимыми компонентами СА.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Системный анализ и принятие решений. Словарь-справочник. - М: Высшая школа, 2005. - 616 с.

2. Орловский П.Н. Системный Анализ (основные понятия, принципы, методология). Том 1 / Учебное пособие. - Киев: Минобразования Украины, 1996. - 360 с.

3. Ант оное А.В. Проектирование систем. - Обнинск: Изд-во ИАТЭ, 1996. - 157 с.

4. Моисеев Н.Н. Математические задачи системного анализа. - М.: Наука, 1981. - 488 с.

5. Ант оное Л.В. Системный анализ / Учебник для вузов. - М: Высшая школа, 2006. - 470 с.

6. Дагаее А.В., Антонов А.В, Чепурко В.А. Модель анализа надежности подсистем ЯЭУ со

// . . - : -ИАТЭ, 2001, №2. - С. 3-9.

УДК 519.007

А.Н. Шабельников, В.А. Шабельников

ПОИСК АНОМАЛИЙ В ТЕХНИЧЕСКИХ БАЗАХ ДАННЫХ ВРЕМЕННЫХ

РЯДОВ*

Введение. Базы данных временных рядов (БДВР) отличаются от статических , ,

. -

* Работа выполнена при поддержке РФФИ, проекты № 07-01-00075 и № 07-07-00010

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

[1].

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

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

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

7 = {(yt,11)/ie N, yt e R, ti eT],

где T - дискретная временная шкала; R - множество действительных чисел yi = y(tj), характеризующих числовые значения ВР в i-e моменты времени.

Определение 2. Временным интервалом или темпором называется пара [ts, te ] e T2, в которой S < e .

Будем обозначать через I = ([s, e] e N2 / s < e] конечное множество

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

Определение 3. БДВР называется множество записей {ri = (y1, y 2 ,•••, ym, tj)}, в котором каждая запись содержит определенный набор

числовых либо символьных атрибутов и определенное значение времени, задаваемое на временном масштабе в определенном разрешении.

Определение 4. Функцией j-ro атрибута называется функция времени yj (t), значениями которой являются значения j-ro атрибута в записях rt Е БДВР .

Определение 5. Признаком функции атрибута y(t) на интервале [t1, t2] называется некоторая функция Q(t), аппроксимирующая функцию y (t) на интервале [ti, t2 ] , т^.

y(t) ^ Q(t) Vt Е [tl, t2].

Термин “аппроксимирует” может быть интерпретирован различными способами относительно конкретной предметной области, например:

I y(t) - Q(t)\<£ Vt Е [tl, t2].

Иногда под признаком функции атрибута будем понимать параметры ап. ,

у^) = а  t + в, то можно сказать, что на этом интервале функция обладает уклоном а , значение которого является признаком, извлеченным из ВР у^) .

Определение 6. Темпоральным паттерном (образом) ВР Ж(7) будем называть последовательность признаков, сопоставленных строго упорядоченной последовательности непересекающихся темпоров:

ад=аж,^]),а2(к,£],...,отас,4] ^ ^=1,2,...т.

Определение 7. Темпоральным правилом ассоциации называется правило вида

^(7) ^ Я2(7),

где (7), (7) - темпоральные образы ВР У.

С учетом приведенных выше определений задача поиска знаний в БДВР сводится к препроцессингу данных в БДВР; извлечению системы признаков р и формированию правил ассоциаций.

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

( ).

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

. , , [2] многошкальной вейвлет сегментации и представления каждого интервала одним из семи примитивов. В [3] используется расширенное множество из 13 примити-

.

основе методов кусочно-агрегированной аппроксимации (РАА) [4].

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

. -

работку сырых данных с целью удаления в них аддитивного шума. Положим, что сырые данные yi = y(ti) получены из долгосрочных трендов сигнала j>(ti) и

аддитивного шума e(ti) , т.е.

y(ti) = № )+e(ti).

Целью препроцессинга является получение оценок длительного сигнала j>(ti). Для этого необходимо описать сигналы y(t) и e(t) .

Шум является случайным по своей природе и подвергается влиянию различ-.

сравнительно малого числа факторов. Поэтому для очистки данных можно использовать оператор низкочастотного фильтра (LPF), устраняющий высокочастотные компоненты. Один из простейших типов оператора LPF является конечный фильтр (FIR), определяемый как:

N-1

y(t) = Z y(ti- j+N /2 c(j),

j=0

где y(ti) - начальная функция атрибута; y(t) - очищенная функция атрибута;

c( j ) - .

Фильтр принимает на вход N сэмплов и вычисляет скалярное произведение с вектором весовых коэффициентов. Размер и значения коэффициентов формируются с учетом полосы пропускания и требуемой точности.

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

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

a«,) = y(t+1)-y(t);

t г +1 - t i

в(Ь) = y(ti); n(tiy) =[ y (ti) - y(tt-i, tr+i)] / y (ti),

где y(t-1, tt+1) - аппроксимированное значение BP в точке tt, вычисленное на основе прямой, проходящей через ТОЧКИ y(ti-1), y(ti+1)) .

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

Переход от числовых значений признаков к символьным осуществляется с использованием лингвистической сегментации на основе величины переменной с использованием таких термов как «ВЫСОКОЕ», «НИЗКОЕ» и т.п. В качестве метода сегментации используется метод дискретизации числовых признаков на основе гистограмм распределения числовых значений [6]. Выделенные на гистограммах сегменты характеризуются минимальными значениями энтропии на границах и соответствуют столбцам гистограммы, имеющим примерно равные площади.

,

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

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

.

различных подхода к их поиску.

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

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

На рис. 1 приведен заимствованный из [7] пример двухслойной информаци-онно-коннекционисткой сети, построенной на основе двух атрибутов.

Слой №0 Слой №1 Слой №2 Целевой слой

атрибут) входной связей з значения

3 значения атрибут)

2 значения

Рис. 1. Информационно-теоретическая коннекционистская сеть

В приведенной сети первый входной атрибут соответствует трем значениям, представленными элементами 1, 2 и 3 в первом слое. По результатам теста статистической значимости в качестве значимых выделены только элементы 1 и 3. Второй слой содержит четыре узла, описывающих комбинацию двух значений второго входного атрибута с двумя элементами первого слоя. Целевой атрибут имеет , .

Описанию алгоритма построения сети предпошлем следующие рассуждения. Пусть в символьном ВР У выделен темпоральный образ Ас (А - темпоральный подобраз, с - символьный признак), имеющий поддержку (количество

вхождений образа во ВР У), равную | Ас |. Тогда величина --------- (| * с | - коли-

чество вхождений символа “с” во ВР У) характеризует условную вероятность появления целевого атрибута “с” после образа “А”, или, иными словами, возможность наличия причинной связи А => с. С другой стороны, для любого иного

целевого атрибута q величина -------- характеризует условную вероятность появ-

ления целевого атрибута “^’ после образа “А”, т.е. вероятность наличия причинной связи А ^ Ч. Тогда величина (1 — |——) характеризует вероятность <<не

появления» “чужого” атрибута “^’ после образа “АС'. Для всех иных т “чужих”

атрибутов Ч] величина (1 -| Ач‘ |) характеризует вероятность <<не появле-

ния>> ни одного из них после образа А. В результате величина „ | Ас | ” 1 | Аа, I

Р =-----------П (1-—) характеризует условную вероятность появления целе-

вого атрибута “с” после образа А при одновременном <<не появлении» ни одного из “чужих” атрибутов. Таким образом, величина Р может служить некой условной мерой полезности использования образа А в качестве причины появления целевого атрибута “с”, а, следовательно, и одновременно - неким информационнотеоретическим весом ассоциативного правила А => с.

Алгоритм построения сети сводится к последовательному установлению связей между нейронами в соответствии с правилами предсказания целевых атрибутов. Предварительно заметим, что в ниже описываемой инфонечеткой сети (ИНС) каждый путь между нейронами промежуточных слоев и целевым нейроном “с” целевого слоя характеризует некий темпоарльный образ, который, в свою очередь,

“<

<конъюнкция входных значений> то <целевое значение>”.

1. На первой итерации для заданного порога £ устанавливаются все связи

между атрибутами последнего внутреннего слоя а. и целевым атрибутом “с”, если они обеспечивают информационно теоретический вес правила а^ с не £.

2. Пусть уже установлены связи между к-ым и (к-1)-ым слоем ИНС. Тогда устанавливаются связи между (к+1)-ым и к-ым слоем следующим образом. Добав-

ляется связь между нейронами ak+1 и ak , если она увеличивает информационнотеоретический вес вновь создаваемого сетью образа, то есть, если P(ak+1 и Ak) >P(Ak) (Ak - подсеть, уже сформированная на k-ой итерации).

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

Правила определения аномалий часто еще называют правила поиска «новинок» или “сюрпризов” [8]. Идея выявления правил аномалий заключается в пред,

проявляют себя редко, во всяком случае, по сравнению с часто встречающимися (условно нормальными) темпоральными образами. Исходя из этого, предлагаемый способ определения аномалий заключается в создании модели нормального состояния ВР в виде правил предсказания. Входные данные, не соответствующие в достаточной мере модели, отмечаются как аномальные. Для этого используются модификация правил предсказания путем введения в них операторов отрицаний с использованием техники работы с отрицаниями [9].

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Батыршин ИЗ. Основные операции нечет кой логики и их обобщение. - Казань: Отечество, 2001. - 102 с.

2. A. Ultsch. Knowledge discovery, lecture notes, 2003a. German.

3. Bakshi B.R. and Stephanopoulos G. Representation of process trends - IV. Induction of realtime patterns from operating data for diagnosis and supervisory control. Computers & Chemical Engineering, 18(4):303-332, 1994.

4. Colomer J., Melendez J., and Gamero F. Pattern recognition based on episodes and DTW. Application to diagnosis of a level control system. In Proceedings 16th International Workshop on Qualitative Reasoning (QR'02), pages 37-43, 2002.

5. Keogh E., Chakrabarti K., Pazzani M. J., andMehrotra S.. Dimensionality reduction for fast similarity search in large time series databases. Knowledge and Information Systems, 3(3): 263-286, 2001b

6. AgrawalR. andSrikantR.. Fast algorithms for mining association rules. In Proceedings of the 20th VLDB Conference, pages 487 - 499, 1994.

7. Daw C.S., Finney C. E. A, and E. R. Tracy. A review of symbolic analysis of experimental data. Review of Scienti_c Instruments, 74(2):916-930, 2003.

8. Last M., Klein Y., and Kandel A. Knowledge discovery in time series databases. IEEE Transactions on Systems, Man, and Cybernetics, 31(1):160-169, 2001

9. Keogh E., Lonardi S., and Chiu B. Finding surprising patterns in a time series database in linear time and space. In D. Hand, D. Keim, and R. Ng, editors, Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'02), pages 550-556. ACM Press, 2002.