Автореферат (Исследование и разработка методов и алгоритмов обобщения знаний для систем поддержки принятия решений реального времени), страница 3

Внутренние вершины дерева взвешены (помечены) названием параметра и временной меткой, определяющей, в какоймомент времени проводится проверка значения данного параметра. Вершинылистья взвешены (помечены) названием класса ситуации, в более сложном случае – названием восстановительного действия, которое необходимопроизвести при обнаружении ситуации. Каждая дуга темпорального дереварешений взвешена результатом проверки значения параметра в определенныймомент времени, проводимой в вершине, из которой она исходит.Таблица 5 — Псевдокод алгоритма «Темпоральный ID3»Алгоритм «Темпоральный_ID3» (S: таблица с ситуациями,O: наблюдения)Результат: Темпоральное дерево решений НАЧАЛОЕсли для всех ситуаций из S классы ситуаций совпадают,то вернуть Лист(S)Если множество наблюдений O пусто, то вернуть Лист(S)Пусть D – минимальный крайний срок для ситуаций из SЕсли ситуации из S неразличимы на основе показаний датчиковс меткой времени ≤ , то вернуть Лист(S)< * , ′ >= Выбор_наблюдения_для_разбиения_темпоральный_ID3(S, O)Пусть *1 , *2 ,.., * – различающиеся показания параметра * в моментвремени t’, а * , = 1, 2, .., – подмножества ситуаций из S, состоящиеиз ситуаций с показанием * параметра * в момент времени t’.Вернуть дерево с корнем, помеченным выбранным наблюдением< * ,′ >, и дугами, помеченными *1 , *2 , .., * , соединяющимикорень соответственно с деревьями«Темпоральный_ID3»(1* , ∖{< * ,′ >})«Темпоральный_ID3»(2* , ∖{< * ,′ >})...«Темпоральный_ID3»(* , ∖{< * ,′ >})КОНЕЦВ работе предложен алгоритм «Темпоральный ID3» («TID3»), который является расширением алгоритма «ID3»3 , учитывающим фактор времени.

Данныйалгоритм представлен в табл. 5. При выборе параметра и момента времени дляразбиения набора ситуаций используется критерий «прирост информативности» Куинлана3 . Величина Gain(<s,t>, S) = Info(S)-Info(<s,t>, S) показывает3Quinlan J. R. Induction of decision trees // Machine learning. — 1986. — Vol. 1. — Pp.

81–106.13количество информации, которое мы получаем благодаря наблюдению <s, t>.В алгоритме «Темпоральный ID3» данная величина используется для оценкиинформативности наблюдения при построении дерева решений, что позволяет получать деревья минимальной высоты. Процедура выбора наблюдения сиспользованием данного критерия представлена в табл. 6. Алгоритм строиттакое дерево, в котором с каждым узлом ассоциирован параметр и метка времени, являющиеся наиболее информативными среди еще не рассмотренных напути от корня дерева. Вычислительная сложность алгоритма «ТемпоральныйID3» – (( * )2 * ), где q – число параметров, r – длина рассматриваемоговременного интервала, n – число примеров в обучающей выборке.Таблица 6 — Выбор наблюдения для разбиения, «Темпоральный ID3»Алгоритм Выбор_наблюдения_для_разбиения_Темпоральный_ID3(S: Таблица с ситуациями,O: Наблюдения)Результат: o* - наиболее информативное наблюдениеНАЧАЛОДля всех наблюдений <s,t> из O, для которых временная метка t непревосходит крайний срок для ситуаций из S, вычисляем количествоинформации, которое получаем благодаря этим наблюдениям:Gain(<s,t>, S) = Info(S) – Info(<s,t>, S), гдеInfo(S) – энтропия для ситуаций из S (распределение восстановительныхдействий)Info(<s,t>, S) – взвешенное среднее информации, необходимой дляидентификации класса ситуации в каждом подмножестве, полученномпри разбиении множества ситуаций из S на основе значений <s,t>Вернуть <s*, t’> - наблюдение с наибольшим значением Gain(<s, t>, S)КОНЕЦВ четвертой главе представлена архитектура разработанного программного комплекса (рис.

1), реализующего предложенные в работе методы и алгоритмы, и приведено описание функционала входящих в комплекс программ.Проверка работы алгоритмов проводилась на наборах данных из UC IrvineRepository, UCR Time Series Classification Archive, а также на данных, собранных с помощью специальных систем анализа трафика: для получения такихданных был собран специальный стенд, на котором осуществлялась передачаданных по сети в различных условиях: передача по протоколу FTP (эталон);одновременная передача по протоколам FTP и ping, FTP и UDP (анализировался FTP-трафик). Располагая информацией о передаче данных по сети, необходимо было определить, не является ли передача данных «подозрительной»,что могло свидетельствовать о возможной компрометации сетевой инфрастуктуры, наличии программных и/или аппаратных закладок.14Рис.

1 — Архитектура программного комплексаПриведены результаты использования программного комплекса для решения задачи обнаружения аномалий в наборах временных рядов, относящихсяк одному классу. На наборе данных «трафик» алгоритм «TS-ADEEP» показалточность обнаружения аномалий в 100%.Для сравнения будем использовать классические алгоритмы: метод K ближайших соседей (Knn); алгоритм C4_5; байесовские сети (NB); многослойныйперсептрон и логистическая регрессия (MLP); алгоритм Random Forest(RF);логистическая регрессия и деревья решений (LMT); метод опорных векторов(SVM).Результаты сравнения точности обнаружения аномалий предложенным алгоритмом «TS-ADEEP» с классическими алгоритмами приведены в таблице 7.Как видно из таблицы, на двух из пяти рассмотренных наборах данных предложенный алгоритм «TS-ADEEP» показал результаты лучше, чем остальныеалгоритмы.

В среднем по точности «TS-ADEEP» лучше, чем 4 из 7 сравниваемых с ним алгоритмов. В связи с этим можно говорить об эффективностиалгоритма «TS-ADEEP» обнаружения аномалий в наборах временных рядов,относящихся к одному классу.Приведены результаты использования программного комплекса для решения задачи обнаружения аномалий в таких наборах временных рядов, где временные ряды относятся к нескольким различным, но допустимым классам.На наборе данных «трафик» алгоритм «TS-ADEEP-Multi» показал точностьобнаружения аномалий в 100%. Результаты сравнения точности обнаруженияаномалий предложенным алгоритмом «TS-ADEEP-Multi» с классическими алгоритмами приведены в таблице 8.

Алгоритм «TS-ADEEP-Multi» обнаружения15Таблица 7 — Сравнение точности обнаружения аномалий алгоритмом«TS-ADEEP» (%) с классическими алгоритмамиCoffeeCBFOlive oilCCBeefСреднееKnnNBC4_5MLPRFLMTSVM75.0085.0076.6788.0060.0076.93(5)67.8689.6776.6796.0050.0076.04(7)57.1467.3373.3381.0056.6767.09(8)96.4385.3386.6791.3373.3386.61(1)75.0083.5686.6786.0050.0076.25(6)100.0077.0083.3392.0080.0086.47(2)96.4387.6786.6792.3366.6785.95(3)TS-ADEEP(среднее)82.1478.8981.6798.0381.3384.41(4)аномалий в наборах временных рядов с несколькими классами показываетудовлетворительные результаты по сравнению с вышеперечисленными алгоритмами классификации, что позволяет говорить о его эффективности.Таблица 8 — Сравнение точности обнаружения аномалий алгоритмом«TS-ADEEP-Multi» с классическими алгоритмамиKnnCBF85.00CC88.00Face(Four) 87.5086.83Среднее(4)NBC4_5MLPRFLMT89.6796.0084.0989.92(1)67.3381.0071.5973.31(8)85.3391.3387.5088.05(3)83.5686.0078.4182.66(6)77.0092.0077.2782.09(7)SVM TS-ADEEP-Multi(среднее)87.6777.8992.3391.4988.6480.4089.5583.26(2)(5)Приведены результаты моделирования процесса диагностики с использованием темпоральных деревьев решений для частного случая, когда динамические объекты обобщения представляют собой временные ряды, и проведеносравнение предложенного алгоритма «Темпоральный ID3» с другими алгоритмами, решающими аналогичные задачи.

Результаты моделирования и сравнение со специализированными алгоритмами классификации временных рядов приведены в таблице 9. Cреди специализированных алгоритмов выделимметод ближайшего соседа (1-NN ED), алгоритмы 1-NN Best Warping WindowDynamic Time Warping (r) (1-NN BWW DTW (r))4 и 1-NN Dynamic Time Warping,no Warping Window(1-NN DTW no WW)4 . Сравнение показывает, что на рассмотренных наборах данных точность классификации с использованием алгоритма «Темпоральный ID3» в среднем на 5.18-6.68% ниже, чем точностьклассификации специализированными алгоритмами, созданными для работыс временными рядами, но чуть выше (на 0.07%), чем точность классификации4Fast Time Series Classification Using Numerosity Reduction / Xi, Xiaopeng, Keogh, Eamonn, Shelton, Christianet al. // Proceedings of the 23rd International Conference on Machine Learning. — ICML ’06.

— New York, NY, USA:ACM, 2006. — Pp. 1033–1040. http://doi.acm.org/10.1145/1143844.114397416с использованием метода ближайшего соседа. Тем не менее на одном из наборов данных – «Olive oil» – алгоритм «Темпоральный ID3» показал точностьклассификации выше (на 6.70-10.00%), чем рассмотренные специализированные алгоритмы.Таблица 9 — Сравнение точности классификации динамических объектов(временных рядов) алгоритмом «Темпоральный ID3» соспециализированными алгоритмамиwaferCoffeeCBFOlive oilTraceCCECG200Lightning2yogaLightning7BeefСреднее1-NN ED99.50100.0085.2086.6076.0088.0088.0075.4083.0057.5066.6082.35(4)1-NN BWW DTW (r)99.50100.0099.6086.6099.0098.3088.0086.9084.5071.2066.6089.11(1)1-NN DTW, no WW98.00100.0099.7083.30100.0099.3077.0086.9083.6072.6063.3087.61(2)TID398.6496.4395.6793.3088.0083.3379.0077.0569.5665.7560.0082.43(3)Сравнение предложенного алгоритма «Темпоральный ID3» с классическимиалгоритмами и алгоритмом построения темпоральных решений, предложенным в работе5 (обозначим его «CPD»), приведено в табл.

10. Алгоритм «CPD»был выбран для сравнения как алгоритм, наиболее близкий к «Темпоральному ID3», но использующий другие критерии для построения темпоральногодерева решений. Из таблицы видно, что «Темпоральный ID3» на рассмотренных наборах данных превосходит классические алгоритмы классификации всреднем на 0.34-12.76%; на трёх из одиннадцати использованных в работе наборов данных «Темпоральный ID3» по точности превосходит все классическиеалгоритмы.В таблице 11 приведены результаты моделирования процесса диагностикис использованием темпоральных деревьев решений для общего случая, когдадинамические объекты обобщения представляют собой наборы временных рядов, и проведено сравнение предложенного алгоритма «Темпоральный ID3» салгоритмом «CPD».

В большинстве случаев предложенный в работе алгоритм«Темпоральный ID3» на рассмотренных наборах данных показывает более высокую точность классификации, на 0.83-13.33% выше, чем алгоритм «CPD».5Luca Console, Claudia Picardi, Daniele Theseider Dupre. Temporal decision trees: model-based diagnosis ofdynamic systems on-board // Journal of Artificial Intelligence Research. — 2003.

— Vol. 19(1). — Pp. 469–512.17Таблица 10 — Сравнение точности классификации динамических объектов(временных рядов) алгоритмом «Темпоральный ID3» с классическимиалгоритмамиwaferCoffeeCBFOlive oilTraceCCECG200Lightning2yogaLightning7BeefСРЕДНЕЕKnn99.4075.0085.0076.6782.0088.0089.0080.3383.3063.0160.0080.16(5)NB70.8367.8689.6776.6780.0096.0077.0067.2154.2364.3850.0072.17(7)C4_598.2057.1467.3373.3374.0081.0072.0062.3069.9054.7956.6769.67(9)MLP96.2896.4385.3386.6777.0091.3384.0073.7774.5064.3873.3382.09(2)RF99.3275.0083.5686.6781.0086.0081.0078.6977.8756.1650.0077.75(6)LMT98.09100.0077.0083.3376.0092.0082.0063.9371.8764.3880.0080.78(3)SVM95.9696.4387.6786.6773.0092.3381.0072.1363.0771.2366.6780.56(4)CPD97.1296.4392.5556.6783.0060.6773.0075.4158.7647.9546.6771.66(8)TID398.6496.4395.6793.3088.0083.3379.0077.0569.5665.7560.0082.43(1)Таблица 11 — Точность классификации динамических объектов,представленных наборами временных рядов (%)Набор данныхЧисло параметровЧисло классовCBFCBFCCCC22253966АлгоритмCPD TID385.00 89.0058.11 71.4497.50 99.0098.17 99.00Таким образом, можно сделать вывод о том, что использование всех параметров (временных рядов) из описания ситуаций действительно позволяет свысокой точностью разделить имеющиеся объекты на соответствуюшие классы.

В случае, когда ситуации на сложных технических объектах описываются несколькими временными рядами и нет (или не выявлен) единственныйнаиболее информативный параметр, алгоритм «Темпоральный ID3», используя все доступные параметры, показывает точность классификации в среднемлучше, чем при использовании какого-либо одного параметра.В заключении приведены основные результаты, полученные в диссертационной работе.В приложении рассмотрены примеры работы с программным комплексом,приведены свидетельства о государственной регистрации программ для ЭВМи акты о внедрении.18Основные результаты диссертационной работы.1. Проведён обзор методов представления знаний в современных интеллектуальных системах и рассмотрена проблема работы с данными, явно зависящими от времени – темпоральными данными. Выделены основные категории таких данных, которые могут использоваться в ИСППР реальноговремени.