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

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

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

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

Усов Алексей Евгеньевич,

Варламов Александр Александрович,

старший архитектор

старший архитектор, системный интегратор «Li9 Technology Solutions»

г. Райли

Аннотация

база шаблон алгоритм

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

Ключевые слова: информационные системы, методы классификации, обнаружение знаний в базах данных, дерево принятия решений, C4.5, ID3, FTree.

Abstract

Application of decision trees at defining information system patterns

Usov Aleksey Yevgenyevich - Lead Systems Architect;

Varlamov Aleksandr Aleksandrovich - Senior Solution Architect;

Babkin Oleg Vyacheslavovich - Senior System Architect;

Dos Evgeniy Vladimirovich - System Architect;

Mostovshchikov Dmitriy Nikolayevich - Senior System Architect,

IT integrator «LI9 technology solutions», Raleigh, United States of America

Methods for the development of knowledge discovery algorithms in databases are considered as a basic approach of significant samples detection at big data sets. Within the framework of the developed methodology, two groups of knowledge detection algorithms are distinguished: clustering objects with undefined classes and methods of inductive learning for determined objects by given set of classes. An original approach in the field of knowledge discovery at databases is proposed, which is based on classification methods based on a decision support tool such as a decision tree. The developed technique allows analyzing both on the basis of predetermined data classification patterns and highlighting new features of information objects of the data set and its classes, including patterns of a higher order, such as the similarity between classes, characteristics of classes and potential errors of the presented data set.

Keywords: information systems, classification methods, databases' knowledge discovery, decision tree, C4.5, ID3, FTree.

Основная часть

Методика обнаружения знаний в базах данных (KD: Knowledge Discovery) может быть определена как процесс выделения актуальных шаблонов при нейросетевом анализе больших наборов данных [1]. На сегодняшний день KD лежит в основе построения методов управления с прогнозирующими моделями, как наиболее продуктивного метода работы с базами данных, полученными в результате широкомасштабного исследования. В рамках данной работы, тем не менее, предлагается разделять задачи анализа данных и прогнозирования, и в соответствии с данным подходом строить математические модели KD. Это позволит увеличить эффективность анализа через соотнесение исполняемого алгоритма и класса задачи, что обуславливает актуальность исследования проведенного в рамках данной работы.

Анализ последних исследований и публикаций в данной области показал приоритет использования при кластеризации алгоритмов обучения без учителя (unsupervised learning), которые группируют объекты предметной области (domain objects) по признаку их сходства [2], что соответствует парадигме индуктивного обучения. Кроме того были рассмотрены методы подразумевающие наличие предварительной информации об оптимальной стратегии кластеризации, например, заданное количество кластеров на основе которых нейросетевые алгоритмы определяют их центроиды и границы [3].

Наиболее широко используемым методом индуктивного обучения является средство поддержки принятия решений, известное как дерево принятия решений (decision tree). Данный подход можно разделить на две базовые группы:

• деревья классификации (classification trees), где прогнозируемым результатом работы алгоритма (например, ID3 [4] или его расширенная версия C4.5 [5], где выбор атрибута происходит на основании нормализованного прироста информации) является выделение классов данных;

• деревья регрессии, где прогнозируемый результат работы алгоритма (алгоритм CART [6]) может быть представлен в числовой форме.

При этом построение деревьев классификации рассматривается как более сложная и значимая задача индуктивного обучения [7]. Большая часть работ в этой области посвящена построению прогностических моделей, в то время как более важным является выделение ключевых атрибутов объектов набора данных [8, 9]. Процесс классификации может быть рассмотрен прохождение пути от корня дерева принятия решений к листьям [10], которое содержит значения атрибутов. В работе [11], тем не менее, предлагается данный подход предлагается расширить в рамках KD, таким образом, все узлы дерева помимо листьев содержат наборы примеров классов. Соответственно, прохождение от корня к узлу определяет уровень сходства классов. Предложенная методология анализа

FTree (Filtered Tree) берет за основу алгоритм для роста дерева принятия решений (ID3, C4.5 или др.) с помощью которого производится анализ формы дерева. При этом остается возможность заложить в модель предварительный набор знаний.

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

Методология построения дерева принятия решений при построении моделей мониторинга информационных систем

Дерево принятия решений в общем случае может быть представлен как ориентированный ациклический граф (DAG: Directed Acyclic Graph). Что касается структуры данного графа, следует отметить, что все его узлы, помимо корня имеют одно входящее ребро, а у корня, соответственно нет входящего ребра [1]. Аналогично, узлы без исходящих ребер называются листьями, а все остальные узлы - внутренними узлами. Эффективность алгоритма дерева принятия решений определяется через эффективность проведения классификации на основе данной структуры в отношении объектов, которые не входят в обучающий набор.

Пример построения алгоритма дерева принятия решений показан на рис. 1 и рис. 2. В качестве объекта моделирования была выбрана базовая схема системы выявления кибер-угроз (IDS: Intrusion Detection System) распределенной информационной системы (рис. 1).

Рис. 1. Базовая схема системы выявления кибер-угроз распределенной информационной системы

На рис. 1 наглядно представлены фундаментальные основы работы комплекса IDS, схема включает в себя весь набор ключевых элементов, которые отвечают за мониторинг и блокировку потенциальных кибер-угроз инфраструктуры распределенной информационной системы, как внутренних, так и внешних. Тем не менее, такая схема не является интуитивно понятной для неспециалиста в данной области, например, научного сотрудника, который на основе математического моделирования хочет определить эффективность работы комплекса и подготовить рекомендации для его усовершенствования или масштабирования. Для решения поставленной задачи может быть предложено построить алгоритм дерева принятия решений (рис. 2).

Рис. 2. Алгоритм дерева принятия решений системы выявления кибер-угроз

Корнем дерева принятия решений, представленного на рис. 2, является «канал передачи данных» а листьями - «регистрация» и «блокировка». Как можно видеть, построение дерева принятия решений происходит через разделения базового набора элементов на подмножества атрибутов, которые далее рекурсивно разделяются на меньшие подмножества-домены до тех пор, пока анализ не позволит выйти на листья дерева принятия решений. Все доменные объекты должны быть представлены с помощью пар атрибут-значение (на уровне классификации или числовой оценки). Наиболее репрезентативный атрибут представленного алгоритма «скрытый канал», он позволяет провести однозначную классификацию программного кода как кибер-угрозы для информационного ресурса. Во всех остальных случаях, соответственно, подмножество должно быть разбито на меньшие подмножества. Такой подход в значительной мере упрощает схему IDS, но при этом он может быть положен в основу алгоритмов моделирования широкого спектра задач по оценке мониторинга и защиты распределенных информационных систем

1. Оптимизация методов математического моделирования алгоритмов дерева принятия решений

Как было показано в предыдущем разделе, ключевая задача, которая решается при построении алгоритмом деревьев принятия решений - это выбор оптимального атрибута для разделения узла. Эффективность решения данной задачи определяет эффективность дерева принятия решений, равно как и его структуру. На сегодняшний день в данной области широко используется универсальный подход [12], который базируется на оценке уровня беспримесности узла (NID: node impurity degree).

Так, например, соотнесение уровня беспримесности узла Т_п по отношению к уровню беспримесности его дочерних узлов Т_{п k} Є (Т_{п 1}; Т_пЛ) относительно атрибута а_ь который для узла Т_п, соответственно, может принимать К значений, что позволяет определить эффективность разбиения узла на подмножество, рассчитывается как:

где TV/.D () - функция оценки уровня беспримесности узла, а N U М () определяет количество примеров, связанных с узлом.

Как можно видеть, в рамках данного подхода есть возможность построить алгоритмы деревьев регрессии на основе коэффициента Джини G (Т_п, С), который определяет разницу между распределением вероятности значений атрибутов Р_пс Ј [Р_п^ Р_пС}.

где С, таким образом, определяет полный набор меток класса.

Аналогичным образом при построении деревьев классификации в качестве функции оценки уровня беспримесности узла при соотнесении уровня беспримесности отдельного узла по отношению к уровню беспримесности его дочерних узлов можно использовать показатель энтропии С (Т_п):

Как можно видеть, в рамках данного определения 8 (ai) может быть описана, как прирост информации (information gain).

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

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

Рассмотрим разбиение, описываемое через R Е {R₁,… R…R,} конечного множества элементов базы данных D. В таком случае энтропия Н () множества разбиений R, которое определяется через мощность | R_i | (соответственно, мощность множества элементов базы данных равна | D |) может быть рассчитана на основе следующей системы уравнений:

При этом расстояние между двумя разбиениями (например, Д 6 {Д _г,… Д;,… Д_;} и 5 6 {5!,… 5 j,… 5у} в данном случае определяется как:

причем Н (Д | 5), Н (5 | Д) и Н (Д П 5) определяются через систему уравнений:

Данный математический аппарат может быть положен в основу построения дерева решений (рис. 3):

• работа с заданным набором базы знаний;

• работа с атрибутами, значения которых не заданы;

• масштабируемость структуры дерева знаний.

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

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

Рис. 3. Схема разработки деревьев классификации на основе оценки уровня беспримесности узла и показателя энтропии

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

• методики SPRINT и CART [14], которые включают в себя создание списков атрибутов на этапе предварительной обработки всего множества информационных объектов при работе с деревьями регрессии;

• алгоритмы фреймворка RainForest, где используются как AVC-наборы, связывающие каждую пару атрибут-значение с меткой класса, так и AVC-группы, которые являются группами AVC-наборов, связанных с узлами дерева принятия решений [15].

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

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

1. обобщенная схема построения деревьев классификации;

2. математический аппарат классификации на основе оценки уровня беспримесности узла и показателя энтропии;

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

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

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