Содержание к диссертации
Введение
ГЛАВА I. Существующие методы поиска исключений 17
1.1. Статистический подход 17
1.1.1. Методы традиционного статистического подхода 18
1.1.2. Методы робастной нечеткой кластеризации 19
1.1.3. Методы обнаружение исключений, строящие вероятностную модель данных 22
1.2. Метрический подход 26
1.2.1. Глобальные метрические алгоритмы 26
1.2.2. Локальные метрические алгоритмы ..29
1.3. Методы анализа отклонений... 31
1.3.1. Алгоритмы последовательного поиска исключений 32
1.3.2. Репликаторные нейронные сети 33
1.3.3. Подходы на основе кластеризации ...35
1.4. Выводы 37
ГЛАВА II. Мера сходства для разнородных структурированных данных 44
2.1. представление данных в системах ИАД 45
2.1.1. Типы источников данных 45
2.1.2. Реляционная модель с вложенными отношениями 47
2.2 Мера сходства для вложенных реляционных отношений 49
2.2.1. Потенциальная функция как мера сходства 49
2.2.2. Определение потенциальной функции для вложенных реляционных отношений 51
2.3. Основные свойства предложенной меры сходства 63
2.3.1. Семантика параметров 63
2.3.3. Вычислительная сложность 63
2.3.3. Предположение о независимости атрибутов 64
2.3.4. Пример использования предложенной меры сходства для поиска исключений в реляционных данных 66
2.4. Выводы 69
ГЛАВА III. Нечеткий метод поиска исключений с использованием потенциальных функций 71
3.1. Обоснование и формулировка метода 71
3.1.1. Потенциальные функции в задачах поиска исключений 71
3.1.2. Идея метода, определение исключения 74
3.1.3. Алгоритм поиска исключений на основе блочного покоординатного спуска 81
3.1.4. Исследование сходимости 85
3.2. Повышение вычислительной эффективности метода для больших объемов данных 87
3.2.1. Оценка сложности алгоритма и применение методов случайной выборки 87
3.2.2. Проблема упрощения решающего правила в методах, использующих потенциальные функции 90
3.2.3. Алгоритм упрощения решающего правила на основе алгоритма кластеризации Руспини 92
3.3. Экспериментальное исследование метода на эталонных наборах данных 95
3.3.1. Данные с числовыми атрибутами. Тестовый набор данных НВК 95
3.3.2. Данные с бинарными и номинальными атрибутами. Тестовые наборы
данных из архива UCI 98
3.3.3 Реляционные данные. База данных Northwind. 99
3.5. Выводы 100
ГЛАВА IV. Апробация на прикладной задаче обнаружения компьютерных атак 103
4.1. Задача обнаружения атак 103
4.1.1. Методы ИАД в системах обнаружения атак 103
4.1.2. Методика верификации алгоритмов выявления сетевых атак 108
4.2. Экспериментальное исследование метода для задачи выявления сетевых атак 112
4.2.1. Постановка эксперимента , 112
4.2.2. Результаты эксперимента 115
4.2.3. Сравнительный анализ 119
4.3. Программная реализация 122
4.3.1. Реализация модуля поиска исключений, поддерживающего стандарт OLEDB for Data Mining 122
4.3.2. Архитектура и функциональность экспериментальной системы обнаружения атак 127
4.4.Выводы 131
Заключение 134
Литература 135
- Методы обнаружение исключений, строящие вероятностную модель данных
- Определение потенциальной функции для вложенных реляционных отношений
- Алгоритм поиска исключений на основе блочного покоординатного спуска
- Реализация модуля поиска исключений, поддерживающего стандарт OLEDB for Data Mining
Введение к работе
ИНТЕЛЛЕКТУАЛЬНЫЙ АНАЛИЗ ДАННЫХ
С развитием информационных технологий увеличивается количество, размеры и сложность хранилищ и баз данных. Объем хранимой информации в таких системах может достигать миллионов и даже миллиардов записей. В связи с чем возникает необходимость разработки программных средств автоматизированного анализа данных большого объема с целью извлечения из них содержательной информации. Для этих целей используются системы интеллектуального анализа данных (НАД) [6,10,14,37,56,59,66].
Согласно подходу, представленному в работах [56,59,66], интеллектуальный анализ данных (Data Mining) рассматривается как один из этапов процесса, называемого обнаружение знаний в базах данных (Knowledge Discovery in Databases). Этот термин был впервые введен в работе [59], где определялся следующим образом: «Обнаружение знаний в базах данных это нетривиальный процесс выявления скрытых, значимых, содержательных и потенциально полезных закономерностей в больших объемах данных». Найденные таким образом закономерности затем могут быть использованы экспертом или программными системами при решении задач поддержки принятия решений, информационного поиска, управлении производственными процессами и в других приложениях.
Объединение и предобработка данных. На данном этапе происходит консолидация данных из различных источников, удаление некорректных значений и вычисление агрегационных значений. Как правило, после этого этапа данные помещаются в хранилище, использующее либо реляционное представление [40], либо многомерное представление на основе п-мерного информационного куба [16,41].
Интеллектуальный анализ данных. Этот этап подразумевает применение к данным, находящимся в хранилище, специализированных методов ИАД с целью поиска закономерностей и выявления зависимостей. Для этого используется математический аппарат и методы математической статистики, искусственного интеллекта, распознавания образов и другие. Найденные закономерности обычно представляются в виде моделей анализа данных (Data Mining models), конкретный вид и содержание этих моделей зависит от используемого математического аппарата и решаемой задачи анализа данных. Например это может быть система правил или дерево решений для задачи классификации; нейронная сеть или регрессионная модель для задачи прогнозирования, прототипы и параметры кластеров для задачи кластеризации и так далее.
Проверка, интерпретация и визуализация результатов. Данный этап основан на интерактивном взаимодействии с экспертом, проводящим анализ данных. Эксперт должен иметь возможность просмотреть и проверить найденные закономерности. Возможно, заново произвести анализ данных, изменив параметры применяемых алгоритмов. Кроме того, на данном этапе могут применяться статистические методы [2] и методы теории возможностей [11] для проверки значимости найденных закономерностей и адекватности построенных моделей.
Традиционно выделяют следующие основные задачи интеллектуального анализа данных (Data Mining tasks) [37,66]: поиск ассоциативных правил; классификация; прогнозирование; кластеризация; анализ временных рядов; поиск исключений.
2. ЗАДАЧА ПОИСКА ИСКЛЮЧЕНИЙ
Настоящая работа посвящена задаче поиска исключений (англ. Outlier Mining, Exception Mining). В ИАД под исключением (Outlier, Exception) обычно понимают «объекты, которые не соответствуют или сильно отличаются от остальных объектов в хранилище или базе данных» [66]. Большинство методов интеллектуального анализа данных чувствительны к наличию исключений в анализируемых данных. Поэтому одна из областей применения методов поиска исключений это подготовка данных для последующего применения других методов ИАД. Но существует ряд прикладных задач, где исключения играют важную роль и собственно поиск исключений является основной целью. К таким прикладным задачам можно отнести:
• обеспечение компьютерной безопасности (например, системы обнаружения атак, работающие в режиме выявления аномалий [18,47,49,53 ,55,77]);
• предоставление банковских и телекоммуникационных услуг (в частности, предотвращение мошенничеств при использовании кредитных [28] и телефонных карт [33]); • медицина (например, поиск данных в базе данных историй болезни
информации о необычных реакциях на проведенный курс лечения [79]). Неформально постановка задачи поиска исключений в ИАД может быть сформулирована двумя способами [66]:
1) Дано множество из п объектов, требуется выбрать к из них, которые наиболее отличаются от остальных.
2) Дано множество из п объектов, требуется упорядочить их по степени непохожести друг на друга.
Более формально: дано некоторое множество Х = {xj,..., хп}, далее называемое исходным множеством или множеством анализируемых объектов. Требуется построить функцию F0j- :Х —»7, называемую решающей функцией,
такую, что каждому значению х из X ставится в соответствие значение фактора исключительности (Outlier Factor) у из Y, которое зависит от того, насколько объект х «похож» на остальные элементы множества X.
Если при этом решающая функция бинарная и принимает положительное значение ровно для к элементов из X, где к заданно априори, мы получаем
неформальную постановку задачи поиска исключений типа (1). В случае Гс 9? J мы получаем неформальную постановку задачи поиска исключений типа (2), и в этом случае говорят, что F0f определяет степень исключительности.
Очевидно, что такая постановка задачи остается интуитивной, поскольку не накладывает никаких условий на множество анализируемых объектов X, не определяет понятие «сходства» на множестве X, и, вообще говоря, не дает формального определения самого понятия исключения. Таким образом для решения задачи поиска исключений требуется решить две подзадачи [66]:
• Формально определить понятие исключение, то есть задать критерии по которым объект из исходного множества может быть определен как исключение. • Разработать эффективный метод поиска таких исключений в исходном множестве анализируемых объектов.
При решении данных подзадач используется доступная информация о структуре и свойствах множества анализируемых объектов. Но даже для одного и того же исходного множества X могут быть применены различные подходы для формализации понятия исключения, что приводит к различным постановкам задачи поиска исключений и, соответственно, объекты, определенные как исключения в рамках одного подхода могут не являться таковыми в рамках другого.
Выделяют три основных подхода к формализации понятия исключения, и соответственно, все методы поиска исключений разбиваются на три группы [66]: статистические (statistical-based); метрические (distance-based); методы, основанные на анализе отклонений (deviation-based).
Статистический подход, представленный, в частности, в работах [12,20,45,45,53,58,70,75,76,81,101], является традиционным подходом к решению задачи поиска исключений. Он использует вероятностную интерпретацию понятия исключения как резко выделяющегося наблюдения (или выброса) и привлекает математический аппарат статистики и теории вероятностей.
Метрический подход к задаче поиска исключений [31,32,67,71,72,73,74,96] использует геометрическую интерпретацию исключения. Он основан на вычислении расстояния между объектами в базе данных и в общем случае использует следующее определение исключения [71,72,73]: «Объект о считается исключением, если как минимум р-ая часть всех объектов базы находится на расстоянии большем D от данного объекта о».
Все остальные методы, не использующие ни вероятностную ни геометрическую интерпретацию понятия исключения объединены в третью группу: методы, основанные на анализе отклонений. Как правило, каждый метод из данной группы использует собственное определение исключения. К данной группе относятся методы поиска исключений на основе нейронных сетей [21,22,38,69], методы последовательного поиска исключений (Sequential Exception Mining) [15], методы на основе кластеризации [46,55] и другие [17,66].
Следует заметить, что попытки ввести универсальное определение исключения предпринимались в работе [72]. Но, к сожалению, предложенное понятие универсального исключения не соответствовало определениям исключения, используемым в методах анализа отклонений. Кроме того, даже для статистического и метрического подхода удалось доказать эквивалентность определений исключения только для простейших случаев.
3. АКТУАЛЬНОСТЬ
Большинство методов поиска исключений в системах интеллектуального анализа данных были заимствованы из смежных областей, таких как математическая статистика и искуственный интеллект. Поэтому они накладывают ряд жестких ограничений на структуру и размер множества анализируемых объектов. Например, некоторые методы рассматривают анализируемый объект как числовой вектор фиксированной длины; другие подразумевают, что вероятностная модель данных должна быть задана априори, хотя бы параметрически; третьи имеют сложность выше квадратичной, что не позволяет их применять для больших объемов данных. Данные ограничения делают эти методы мало применимыми в системах НАД в общем случае, хотя на отдельных прикладных задачах они могут показывать хорошие результаты. Сформулируем особенности анализируемых данных в системах ИАД, которые отличают такие системы от статистических, нейросетевых и других специализированных программных систем анализа данных.
Основные особенности данных в системах ИАД [37,66]: отсутствие априорной информации; анализируемый объект может иметь сложную разнородную структуру; большой объем и размерность анализируемых данных.
В свою очередь каждая из этих особенностей имеет ряд аспектов с точки зрения требований к методу поиска исключений.
Отсутствие априорной информации означает что, во-первых, мы не можем делать априори никаких предположений о законах распределения на множестве анализируемых объектов, что сразу заставляет отказаться от параметрических методов математической статистики. Во-вторых, у нас нет информации о том, каким классам могут принадлежать анализируемые объекты, в частности, мы не можем заранее сказать какой объект является исключением, а какой нет. Используя терминологию теории распознавания образов, это условие заставляет нас использовать только методы автоматической классификации, так называемые методы обучения без учителя или неконтролируемого обучения (unsupervised learning methods) [7].
Анализируемый объект может иметь сложную разнородную структуру. Это одна из основных особенностей данных в системах ИАД, которая отличает такие системы от других программных систем анализа данных. Данная особенность следует из требования глубокой интеграции системы ИАД с хранилищами и базами данных [56,59,66]. Это означает, что множество анализируемых объектов формируется непосредственно выборкой из хранилища или базы данных, то есть анализируемый объект может быть представлен не вектором признаков, а срезом n-мерного информационного куба [65,104,105], для многомерной модели, или набором взаимосвязанных записей из различных таблиц, для реляционной модели [51,62].
И наконец, третья важная особенность, это большой объем и размерность анализируемых данных. Данная особенность, во-первых, накладывает ограничения на реализацию алгоритмов поиска исключений - они не могут хранить в памяти весь анализируемый набор объектов, равно как и другие вспомогательные структуры данных (индексы, хэш-таблицы), чей объем соизмерим с объемом множества анализируемых объектов. Во-вторых, не могут иметь высокую вычислительную сложность. Согласно [97] сложность выше 0(N2) уже не позволяет применять такой алгоритм в системах ИАД.
В связи с перечисленными выше особенностями систем НАД, а также важностью прикладных задач, решаемых с помощью таких систем, становится актуальной проблема разработки новых эффективных алгоритмов поиска исключений для применения их в системах интеллектуального анализа данных.
4. ЦЕЛЬ РАБОТЫ
Цель работы состоит в исследовании, разработке и реализации эффективных алгоритмов поиска исключений для разнородных структурированных данных большого объема, что предполагает решение следующих подзадач:
• предложить метод вычисления меры сходства для разнородных структурированных данных, структура которых определяется реляционным или многомерным представлением, и исследовать возможность ее применения в задачах поиска исключений;
• предложить определение исключения и разработать эффективный метод поиска исключений, основанный на предложенной мере сходства и имеющий сложность по времени не выше квадратичной;
• реализовать предложенный метод в рамках экспериментальной компоненты интеллектуального анализа данных и провести ее апробацию на прикладной задаче обнаружения сетевых атак.
5. СТРУКТУРА И КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ
Диссертационная работа состоит из четырех глав, каждая из которых содержит по три параграфа. Первая глава посвящена обзору существующих алгоритмов поиска исключений, представляющих три основных подхода: статистический, метрический и анализ отклонений. Первый параграф посвящен статистическим методам, второй - метрическим, последний — методам анализа отклонений. Для каждого из них описываются основные принципы и особенности, приводятся наиболее показательные алгоритмы, обсуждается вопрос их применимости в системах интеллектуального анализа данных. В результате, формулируются требования, которым должен удовлетворять алгоритм поиска исключений, применимый в системах ИАД и показывается, что полностью отвечающего данным требованием метода, на настоящий момент не предложено.
Вторая глава посвящена задаче определения меры сходства для разнородных структурированных данных. В первом параграфе рассматриваются различные типы источников данных, используемых в системах НАД. Выбирается представление на основе реляционной модели с вложенными отношениями [82,91], что позволяет единообразно представлять транзакционные, реляционные и многомерные данные. Во втором параграфе ставится задача определения меры сходства для разнородных структурированных данных, структура которых задана реляционной схемой с вложенными отношениями. В результате предлагается метод определения меры сходства для вложенных реляционных отношений. В данном методе мера сходства определяется как R-свертка потенциальных функций [68], заданных для атомарных атрибутов вложенного реляционного отношения. Доказывается, что определенная таким образом мера сходства также является потенциальной функцией. С помощью данного метода строится мера сходства, являющаяся R-сверткой радиально-базисных (RBF) потенциальных функций, определенных для числовых и номинальных атрибутов реляционной схемы с вложенными отношениями. В третьем параграфе рассматриваются свойства предложенной меры сходства, такие как семантика параметров и вычислительная сложность, обсуждается случай коррелированных атрибутов и приводится пример применения метрики расстояния, основанной на предложенной мере сходства, для поиска исключений в реляционных данных с помощью метрического алгоритма поиска исключений. В третьей главе формулируется новый нечеткий метод поиска исключений, использующий потенциальные функции. В первом параграфе обсуждается применение потенциальных функций в методах поиска исключений, особое внимание уделяется методам, использующим гипотезу о компактности [3]. В частности рассматриваются методы опорных векторов Single-Class SVM [94,95] и SVC [23,95]. Данные методы неявно, с помощью потенциальной функции, отображают объекты исходного из исходного пространства X в векторное пространство характеристик большой или бесконечной размерности. В пространстве характеристик строятся гиперсфера (SVC) или гиперплоскость (Single-Class SVM), описывающие компактное множество образов «основной части» объектов, а остальные объекты определяются как исключения. Эти методы доказали свою эффективность для большого числа прикладных задач, но они имеют ряд недостатков, затрудняющих их применение в системах ИАД. Для преодоления таких недостатков и развивая идею этих методов, в настоящей работе предлагается метод поиска исключений, который вместо гиперсферы ищет нечеткий кластер, такой что, образы «основной части» объектов в пространстве характеристик имеют высокую степень принадлежности. Таким образом, данный нечеткий кластер содержит компактное множество образов объектов в пространстве характеристик, а объекты, образы которых находятся относительно далеко от центра кластера и поэтому имеют низкую степень принадлежности рассматриваются как возможные исключения. Для определения исключения вводится понятие нечеткой степени «типичности» и(х), которое соответствует степени принадлежности образа объекта х нечеткому кластеру, а исключением считаются объекты, чья степень типичности ниже заданного порога а. Процесс поиска исключений можно представить следующим образом: в пространстве характеристик ищется нечеткий кластер, включающий с высокой степенью принадлежности «основную часть» образов исходного множества X; на основе найденного нечеткого кластера определяется функция и(х), вычисляющая нечеткую степень «типичности» х для всех объектов из Ху и задающая таким образом на X нечеткое множество U; множество исключений в результате формируется как множество а-уровня U [1], то есть множество объектов, чья степень типичности меньше а.
Основным этапом решения задачи поиска исключений в предложенной постановке является решение задачи робастной нечеткой кластеризации в пространстве характеристик. Главным отличием от обычной задачи робастной нечеткой кластеризации является то, что центр кластера принадлежит не исходному пространству, а, вообще говоря, неизвестному векторному пространству характеристик большой, возможно бесконечной размерности. В работе доказывается, что задача нечеткой робастной кластеризации в пространстве характеристик может быть сведена к задаче условной оптимизации с 2N вещественными переменными, где N число объектов в X. Для данной задачи формулируются необходимые условия существования решения и предлагается алгоритм поиска решения, являющийся одним из вариантов метода блочного покоординатного спуска [5,26,27]. Для предложенного алгоритма доказывается, что он линейно сходится при любом начальном приближении.
Во втором параграфе оценивается вычислительная сложность предложенного алгоритма, показывается что она квадратичная, и рассматривается вопрос применения предложенного метода поиска исключений вместе с методами случайной выборки (sampling) [66,97], что позволяет сократить вычислительную сложность до линейной. Кроме того в данном параграфе рассматривается проблема упрощения решающего правила (решающей функции) [34,35,95], характерная для большинства методов анализа данных, использующих потенциальные функции. В результате предлагается эвристический жадный алгоритм упрощения решающего правила, основанный на модификации алгоритма кластеризации Руспини [99]. Данный алгоритм позволяет применять предложенный метод поиска исключений с упрощенным решающим правилом в режиме реального времени.
Третий параграф посвящен экспериментальному исследованию предложенного метода поиска исключений на эталонных наборах данных. Рассматриваются эталонные наборы данных с числовыми, бинарными и номинальными атрибутами, а также реляционные данные. Производится сравнительный анализ результатов, полученных на рассмотренных эталонных наборах данных [84,89] предложенным нами методом, с результатами существующих статистических, метрических методов, а также методов анализа отклонений.
Четвертая глава посвящена апробации предложенного метода поиска исключений для прикладной задачи обеспечения компьютерной безопасности — задачи выявления сетевых вторжений [8,80,88]. В первом параграфе данной главы вводятся основные понятия и описывается задача выявления вторжений. Рассматриваются подходы к применению методов интеллектуального анализа данных для решения данной задачи и методика верификации алгоритмов выявления вторжений DARPA Intrusion Evaluation Program. Второй параграф посвящен экспериментальному исследованию предложенного метода поиска исключений с использованием методики DARPA на эталонном тестовом наборе данных KDD Сир 99 [85]. Производится сравнительный анализ полученных результатов эксперимента с результатами, полученными ведущими алгоритмами выявления вторжений. В заключительном параграфе данной главы описывается экспериментальная программная реализация предложенного метода поиска исключений в виде компоненты анализа данных, поддерживающей промышленный стандарт OLEDB for Data Mining [91], а также рассматривается архитектура экспериментальной системы выявления вторжения, построенной на базе данной компоненты. В заключении формулируются основные результаты.
Методы обнаружение исключений, строящие вероятностную модель данных
Приведенные алгоритмы робастной нечеткой кластеризации базируются на статистических методах вычисления устойчивых оценок и обладают тем свойством, что, во-первых, позволяют находить прототипы кластеров и соответственно решать задачу кластеризации в «зашумленных» данных. Во-вторых, данные алгоритмы позволяют выявлять исключения. В отличии от алгоритмов нечеткой кластеризации типа нечетких к средних Fuzzy C-means с (FCM) [7,24,25], эти алгоритмы не используют условия муї=1» поэтому исключения можно определить как те объекты, чья степень принадлежности кластерам меньше заданного порога [70]. Таким образом максимум по всем кластерам степени принадлежности можно рассматривать как функцию обратную степени исключительности F0s и определить решающую функцию, например как F0f(xi) = l-max(Uji). Кроме того, важным свойством этих алгоритмов является то, что они могут работать с данными большой размерности, не требуют задания вероятностной модели. Но у них есть один серьезный недостаток, они существенно зависят от параметра С - количества кластеров, задаваемого априори. Для оценки этого параметра, как правило, используются итерационные методы, последовательно решающие задачу кластеризации для различных С и выбирающие в результате то решение, для которого максимизируется некоторый критерий качества [19]. Но такой подход создает ряд проблем при применении в системах ИАД. Во-первых, методы перебора С являются эвристическими и не гарантируют сходимость процесса к глобальному минимуму критерия качества [19], во-вторых, по очевидным причинам, такой подход не применим для больших объемов данных.
Данная группа статистических методов наиболее часто используется в системах ИАД, поскольку требует минимальное количество априорных знаний о множестве анализируемых объектов и обладает достаточной вычислительной эффективностью. Суть этих методов заключается в автоматическом построении вероятностной модели данных, которой соответствует большинство объектов из анализируемого множества. После чего все объекты проверяются на соответствие этой модели, а не соответствующие объекты объявляются исключениями. Также, помимо вероятностной модели «нормальных» данных может строиться еще и вероятностная модель исключений, в этом случае для каждого из объектов проверяется какой из моделей он принадлежит. Прежде чем рассмотреть данные два подхода более подробно сделаем несколько замечаний о методах построения вероятностной модели данных, применяемых в системах ИАД.
Существует широкий спектр алгоритмов, позволяющих по выборочным данным определить предполагаемое распределение, то есть вероятностную модель. В системах ИАД часто приходится работать с данными, имеющими как непрерывные так и номинальные (дискретные) атрибуты. В простейшем случае анализируемый объект представим в виде вектора (х,у), где х-дискретные атрибуты, а -непрерывные. Некоторые алгоритмы [101] рассматривают дискретные атрибуты как пространство ячеек, определенное произведением доменов этих атрибутов Dom(A1)xDom(A2) i... xDom(Ad). В рамках этого пространства строится гистограмма распределения вероятности р(х). Далее в каждом элементе этого пространства (ячейке) строится вероятностная модель непрерывных атрибутов. Таким образом, р{х, у) = р(х)р(у \ х). Для построения вероятностной модели непрерывных атрибутов для заданной дискретной ячейки р(у х) используют, как правило, либо конечную смесь нормальных распределений (finite Gaussian mixture model) [39, 101], параметры которой динамически вычисляются с помощью ЕМ алгоритма (Expectation-Maximization Algorithm) [29,86]; либо используют оценку плотности вероятности с помощью гистограммных методов, базирующуюся, например, на работах Парзена [92] и Розенблатта [98]. Следует отметить, что в последнее время появились работы рассматривающие вопросы построения вероятностных моделей не только для объектов содержащих фиксированное число дискретных и вещественных атрибутов, но и для сложных структурированных объектов. В частности, большой интерес представляет работа [62], в которой исследуется вопрос построения вероятностных моделей для реляционных данных. В этом случае структура анализируемых объектов определяется реляционной схемой, а сам объект состоит из нескольких взаимосвязанных записей из различных таблиц. Для оценки параметров модели авторы [62] также используют модификацию ЕМ алгоритма.
Вернемся к рассмотрению методов поиска исключений, использующих построенную вероятностную модель. Для данного рассмотрения не существенно, какой из методов построения вероятностной модели используется, важно, что можно построить некоторое приближение функции распределения на множестве XS czX, применяя один из таких алгоритмов, обозначим его S. Будем обозначать Pxs (х) = S(XS)(x) есть вероятность х, для вероятностной модели построенной методом S на данных Леї.
Рассмотрим подход при котором строится как вероятностная модель «нормальных» данных F, так и модель исключений G [53]. Предположим, что каждый объект в анализируемом наборе с вероятностью Я является исключением. Я = к/п параметр метода, где к - ожидаемое число исключений, а п - число анализируемых объектов. На каждом шаге t алгоритм генерирует пару множеств At и Mt. К первому относятся объекты, которые считаются уже выявленными исключениями, ко второму все остальные. В начале Ао=0, М0 = X. Всего алгоритм делает п шагов, по числу элементов в X, каждый раз один из элементов проверяется на возможную принадлежность к исключениям и каждый элемент проверяется только один раз. Для этого считается правдоподобие.
Определение потенциальной функции для вложенных реляционных отношений
. В этом случае для построения модели используется только часть данных, как правило, случайная выборка размера и1 т, таким образом суммарное время построения можно свести к 0(п ). В задаче поиска исключений на этапе применения модели улучшить скорость алгоритма уже не удастся, поскольку должны быть проанализированы все данные. В метрических же подходах применение методов случайной выборки проблематично, потому что не строится модель, а значит оценку 0(п ), справедливую для большинства метрических алгоритмов, можно улучшить только за счет применения алгоритма ячеек [71,72], экспоненциального по размерности данных, и требующего хранения в памяти больших вспомогательных структур. Поэтому перспективным направлением в рамках метрического подходя является развитие методов в сторону понижения точности вычисляемых оценок, за счет увеличения вычислительной эффективности, например применяя методы кластеризации, как это сделано в работе [32] для вычисления приближенной оценки LOF в сочетании с алгоритмом кластеризации OPTICS.
Методы анализа отклонений настолько сильно отличаются друг от друга, как в смысле применяемого математического аппарата, так и в смысле определения исключения, что достаточно тяжело выделить общие характеристики, за исключением одной главной. Во всех методах анализа отклонений производится разбиение множества анализируемых объектов на группы или выделение одной общей группы, после чего исключением считаются объекты, чьи характеристики сильно отклоняются от характеристик группы. Среди методов анализа отклонений необходимо выделить метод последовательного анализа исключений, как наиболее отвечающий требованиям ИАД. Он не требует, чтобы анализируемые объекты были элементами метрического или вероятностного пространства, линеен, и легко модифицируется под специфику задачи за счет определения соответствующих функций различия и мощности. Основной проблемой является зависимость результата от последовательности рассмотрения анализируемых объектов. Нейросетевые методы анализа отклонений в задачах поиска исключения в системах ИАД имеют скорее больше недостатков, чем достоинств, поскольку не отвечают ни требованиям эффективности вычислений, ни четкости используемого понятия исключения, и не имеют возможности работать с дискретными значениями, не говоря об анализируемых объектах сложной структуры. Их применение скорее всего оправдано традиционной популярностью нейросетевых методов в задачах машинного обучения и распознования образов, а также большим числом специалистов, владеющих данной технологией. Методы на основе четкой робастной кластеризации, несмотря на вычислительную эффективность так же можно подвергнуть критике за неточность, наличие эвристических предположений о плотности распределения и неформальность в определении исключения. Кроме того, эти методы также зависят от подбора априорных параметров, таких как ширина кластера или количество кластеров.
Подводя итог данной главе, на основе анализа представленного материала сформулируем основные требования, которым должен отвечать эффективный метод поиска исключений, применимый в системах интеллектуального анализа данных. Мотивированное интуитивно понятное определение исключение. Как видно из представленного обзора существующих методов поиска исключений, не существует единого определения исключения даже в рамках одного подхода. И попытки точного решения задачи поиска исключений, когда понятие исключения формально определено с использованием строгого математического аппарата, взятого из смежных областей, как правило, либо приводят к необходимости решения NP-полных задач, либо вообще не применимо в системах ИАД для разнородных структурированных данных высокой размерности и большого объема. Но это не означает, что не нужно использовать формальные определения исключения и подходы из смежных областей. Наоборот, определение исключения в ИАД должно базироваться на формальных определениях, но быть интуитивно понятным и учитывать специфику задачи поиска исключений в ИАД. Как сказано в работе [97], посвященной анализу применимости методов математической статистики в ИАД: «Статистический подход в интеллектуальном анализе данных может принести пользу, если особенности интеллектуального анализа данных учитывались при разработке соответствующих статистических методов».
Вычислительная эффективность. Вычислительно эффективным в ИАД считаются линейные методы [15,66,97]. Либо методы, использующие построение модели (model-based) и методы случайной выборки (sampling). При этом процесс построения модели должен быть полиномиальным с невысокой степенью, 0(п ) или 0(п ), а процесс применения построенной модели, то есть собственно поиск исключений - линейным. Это позволяет находить приближенное решение за приемлемое время.
Минимальное использование априорных параметров. Это требование означает, что желательно, чтобы метод вообще не имел критических параметров, и во всяком случае не делал явных предположений о законе распределения, возможном количестве кластеров в данных, их форме и так далее. Единственный априорный параметр, который методу необходимо учитывать это ожидаемое экспертом отношение числа исключений к общему объему данных.
Работа с разнородными структурированными данными. Поскольку в системах ИАД исходное множество анализируемых объектов формируется непосредственно выборкой из базы данных или многомерного хранилища, этот вопрос становится особенно актуальным. В процессе изложения материала первой главы на нем не акцентировалось особого внимание, за исключением рассмотренных в 1.1.3 методов. Большинство методов поиска исключений изначально разрабатывалось и исследовалось в предположении, что анализируемые объекты принадлежат к - мерному метрическому пространству, например X с ЧЯк, но в системах ИАД анализируемый объект быть разнородным, то есть иметь как числовые так и номинальные атрибуты, а также может иметь сложную структуру, определенную реляционной или многомерной схемой представления данных.
Рассмотрев основные подходы и методы поиска исключений, сформулировав требования, которым должен отвечать эффективный метод поиска исключений в системе интеллектуального анализа данных, можно заключить, что методов в точности отвечающих данным требованиям на данный момент не предложено, поэтому дальнейшие исследования в этой области необходимы и актуальны.
Алгоритм поиска исключений на основе блочного покоординатного спуска
Если на множестве анализируемых объектов задана мера сходства на основе потенциальной функции, то очевидно могут использоваться методы метрического подхода и некоторые методы анализа отклонений, рассмотренные в первой главе. Для этого достаточно на множестве анализируемых объектов ввести метрику расстояния типа (2.2) или (2.13), как это было проиллюстрировано во второй главе на примере поиска DB(p,D) исключений в реляционной базе данных. Однако, как обсуждалось выше, эти методы имеют ряд недостатков. А именно, наличие критичных параметров, таких как р и D для методов DB(p,D), число или размер кластеров для методов анализа отклонений на основе кластеризации. Эти параметры необходимо устанавливать априори, а чаще всего в реальных прикладных задачах, итеративно искать переборными методами. Кроме того, для большинства таких методов решающая функция F0f бинарная, то есть невозможно сравнить и упорядочить объекты по степени исключительности. И наконец, для метрических методов проблематично использовать методы случайной выборки.
Помимо метрических методов, могут быть использованы и статистические методы, строящие вероятностную модель данных. В этом случае потенциальные функции могут применяться для аппроксимации функции плотности распределения, например, с использованием метода Парзена (Parzen Window) [92], или методов опорных векторов аппроксимации плотности распределения (SV Density Estimation) [61] или метода Ченцова [3,13]. Основной их проблемой также является высокая вычислительная сложность, а также дополнительные условия, накладываемые на используемую потенциальную функцию. В связи с перечисленными проблемами, наибольшее распространение получили методы, опирающиеся на гипотезу о компактности (ГП) [3]. К наиболее эффективным с точки зрения многих авторов [18] методам поиска исключений, использующим ГП, относится ряд методов опорных векторов SVM (Support Vector Machines). В частности, метод построения оптимальной разделяющей гиперплоскости для одного класса Single-Class SVM [94,95], и метод кластеризации на основе опорных векторов SVC (Support Vectors Clustering) [23,95]. Неформально идею этих методов можно описать следующим образом. Объекты из исходного множества неявно отображаются с помощью потенциальной функции в пространство характеристик высокой размерности, где SVC щет гиперсферу минимального радиуса, содержащую внутри «основную часть» образов объектов из исходного множества, a Single-Class SVM находит гиперплоскость, отделяющую «основную часть» образов объектов от начала координат. Размер этой «основной части» контролируется специальным параметром у, характеризующим отношения ожидаемого числа исключений к общему числу объектов. Объекты, чей образ лежит за пределами найденной гиперсферы для SVC считаются исключениями, а лежащие на границе гиперсферы — опорными векторами. Аналогично для Single-Class SVM, объекты, чьи образы лежат ближе, чем построенная разделяющая гиперплоскость к началу координат, являются исключениями, а лежащие на гиперплоскости - опорными векторами. Таким образом, основная идея обоих методов опирается на ГП и заключается в построении в пространстве характеристик некоторой геометрической структуры (гиперсферы или гиперплоскости), позволяющей описать компактное множество образов «основной части» объектов, а v-ая часть объектов, чьи образы не попадают в данное компактное множество определяются как исключения. В случае, если используется RBF потенциальная функция, может быть показано, что оба метода находят одинаковое решение [95]. Рассмотрим более подробно метод SVC. Его математическая формулировка выглядит следующим образом: где R это радиус, а это центр гиперсферы в пространстве характеристик; N -число объектов в X; О v 1 параметр, контролирующий число исключений; ,- дополнительные переменные. Эта задача решается методом множителей Лагранжа [9]. В результате бинарная решающая функция будет иметь вид: где Д- множители Лагранжа. Они равны (1 / vN) для исключений, больше нуля и меньше чем (1/vN) для объектов на границе, и равны нулю для остальных объектов из X. Таким образом алгоритм находит решающую функцию, которая в X, где плотность распределения, порождающего исходное множество объектов, относительно велика, принимает значение большее нуля, а в остальных меньше нуля. При дополнительных ограничениях, а именно, в предположении, что Ы исходное множество порождено некоторым неизвестным распределением Р, не имеющим дискретных компонент, может быть доказано [95], что алгоритм решает задачу оценки квантиля распределения Р, то есть находит области, в которых Р(лс) 1-а. Таким образом, хотя в общем случае метод является эвристическим и имеет геометрическую интерпретацию, он тесно связан со статистическими методами выявления исключений. В реальных прикладных задачах приходится иметь дело с дискретными данными и различными видами потенциальных функций, но не смотря на то, что в этом случае методы SVC и Single-Class SVM не имеют строгого математического обоснования, они успешно применяются для таких задач [18]. Данные методы показывают хорошие Н результаты для различных приложений, но имеют несколько недостатков, 1 затрудняющих их применение в системах интеллектуального анализа данных. Основной недостаток это то, что решающая функция - бинарная. Кроме того, как было показано в работах [23,94,95], результат работы алгоритма зависит от параметра v. Один из путей решения данной проблемы, предложенный в работе [23], приводит к необходимости несколько раз применять метод, каждый раз увеличивая параметр v, начиная со значения v = l/N пока не будет получено подходящее значение. Критерий остановки, равно как и шаг увеличения v выбираются эвристически.
Реализация модуля поиска исключений, поддерживающего стандарт OLEDB for Data Mining
Поскольку основной объем публикаций по методам выявления исключений был посвящен статистическим и метрическим методам, то большую часть эталонных наборов данных, используемых в литературе, составляют наборы только с числовыми атрибутами. Поэтому для исследования предложенного метода на эталонных наборах данных с номинальными и бинарными атрибутами будем использовать данные из архива Калифорнийского Университета Ирвин (UCI) [84], которые собирались в основном для исследования алгоритмов кластеризации и классификации.
В качестве тестового набора данных с бинарными атрибутами используется набор данных Zoo. Эталонный набор данных Zoo содержит 101 объект, представляющий описания животных, каждое из которых представлено 15 бинарными признаками. Каждый из объектов принадлежит одному из семи типов, например «змеи», «млекопитающие» и так далее. В качестве тестового набора данных с номинальными атрибутами будем использовать эталонный набор данных Mushrooms. Он содержит описание 8124 объектов, представляющих собой описание различных видов грибов, каждый из которых представлен 22 номинальными признаками и принадлежит к одной из двух групп: «съедобных» или «ядовитых». Эксперимент для обоих наборов данных будем проводить следующим образом. Выбирается один из типов объектов, в частности «млекопитающие» для Zoo (всего 42 объекта) и «съедобные» для Mushrooms (всего использовалось 1000 объектов), и к множеству объектов этого типа добавляется некоторое число исключений, то есть объектов других типов из того же набора данных выбранных случайным образом. В результате задачей метода является при известной пропорции исключений найти их в сформированном таким образом наборе данных. Поскольку число ожидаемых исключений известно заранее, то исключением считаются объекты, чья степень «типичности» меньше 0.5. Параметры алгоритма 3.1 и потенциальной функции (2.15) взяты по умолчанию: т=1.2 и q=l. Результаты метода приводятся в таблице и сравниваются с результатами DB(p,D) метода с расстоянием Хэмминга и оптимально подобранными параметрами.
Как видно из представленных результатов эксперимента, предложенный метод на рассмотренных эталонных наборах данных обладает большей точность чем DB(p,D) метод. Кроме того, предложенный метод не требовалось применять несколько раз для оценки критических параметров, как метод DB(p,D) для подбора D при фиксированном р.
Для исследования предложенного метода на реляционных данных использовалась база данных Northwind [89]. Задача поиска в ней исключений рассматривалась во второй главе. Таким образом, работоспособность предложенного метода так же как и метода DB(p,D) в предыдущей главе будет определяться способностью обнаружить специально добавленные в базу «искусственные» исключения #1, #2, #3, #4, описанные в пункте 2.3.4. Параметры для алгоритма 3.1 и потенциальной функции (2.15) установлены по умолчанию: т=1.2 и q=l. Метод применялся при установках v = 0.1, v = 0.3, v = 0.5. Для заданных параметров определяется число исключений и найденные «искусственные» исключения при различных значениях порога. Результаты Из приведенных результатов видно, что производительность нашего метода на данном тестовом примере близка к производительности метода DB(p,D), рассмотренного во второй главе. Кроме того, необходимо заметить, что независимо от параметра v, степень «типичности» искусственных исключений относительно остальных данных практически не меняется, так исключения #3 во всех тестах было выявлено как наиболее не «типичный» объект, исключения #1, #4 при любых значениях v и соответствующем выборе порога попадают в 2-6% наиболее не «типичных» объектов, а исключение #2 в 30-40%.
В настоящей главе был предложен новый нечеткий метод поиска исключений, применимый в системах интеллектуального анализа данных. Данный метод является гибридным и сочетает методы нечеткой кластеризации с методами потенциальных функций. Рассмотрим определение и свойства предложенного метода с точки зрения требований к методам поиска исключений, сформулированным в заключении первой главы.
Мотивированное интуитивно понятное определение исключения. Предложенный метод опирается на гипотезу о компактности (ГК) и идеи, используемые в методах поиска исключений на основе опорных векторов (SVM). Как и методы SVM предлагаемый метод неявно, с помощью потенциальной функции, отображает объекты исходного множества X в векторное пространство характеристик большой (или бесконечной) размерности, структура которого не уточняется, но скалярное произведение в этом пространстве задается потенциальной функцией К, определенной на Ххх. Методы SVM строят в J пространстве характеристик простые геометрические структуры: гиперсферы h (SVC) или гиперплоскости (Single-Class SVM), описывающие компактное множество образов «основной части» объектов, а остальные объекты определяются как исключения. Причем решающее правило, является ли объект исключением, в SVM есть бинарная функция. Предложенный в настоящей работе метод ищет вместо гиперсферы нечеткий кластер, такой что, образы «основной части» объектов имеют высокую степень принадлежности выше 0.5. Таким образом этот нечеткий кластер содержит компактное множество образов объектов в пространстве характеристик, а объекты, образы которых находятся относительно далеко от центра кластера и поэтому имеют низкую степень принадлежности рассматриваются как возможные исключения.
