Исследование и разработка алгоритмов поиска исключений в системах интеллектуального анализа данных

• Автор: Петровский, Михаил Игоревич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Москва
• Количество страниц: 145 с. : ил

содержание работы.

ГЛАВА I. СУЩЕСТВУЮЩИЕ МЕТОДЫ ПОИСКА ИСКЛЮЧЕНИЙ

1.1. Статистический подход.

1.1.1. Методы традиционного статистического подхода

1.1.2. Методы робастной нечеткой кластеризации.

1.1.3. Методы обнаружение исключений, строящие вероятностную модель данных

1.2. Метрический подход

1.2.1. Глобальные метрические алгоритмы

1.2.2. Локальные метрические алгоритмы.

1.3. Методы анализа отклонений .

1.3.1. Алгоритмы последовательного поиска исключений.

1.3.2. Репликаторные нейронные сети
1.3.3. Подходы на основе кластеризации.
1.4. ВЫВОДЫ
ГЛАВА II. МЕРА СХОДСТВА ДЛЯ РАЗНОРОДНЫХ
СТРУКТУРИРОВАННЫХ ДАННЫХ.
2.1. Представление данных в системах ИАД.
2.1.1. Типы источников данных
2.1.2. Реляционная модель с вложенными отношениями.
2.2 МЕРА СХОДСТВА ДЛЯ ВЛОЖЕННЫХ РЕЛЯЦИОННЫХ ОТНОШЕНИЙ
2.2.1. Потенциальная функция как мера сходства.
2.2.2. Определение потенциальной функции для вложенных реляционных отношений.
2.3. Основные свойства предложенной меры сходства
2.3.1. Семантика параметров
2.3.3. Вычислительная сложность
2.3.3. Предположение о независимости атрибутов.
2.3.4. Пример использования предложенной меры сходства для поиска исключений в реляционных данных.
2.4. ВЫВОДЫ
ГЛАВА III. НЕЧЕТКИЙ МЕТОД ПОИСКА ИСКЛЮЧЕНИЙ С ИСПОЛЬЗОВАНИЕМ ПОТЕНЦИАЛЬНЫХ ФУНКЦИЙ.
3.1. Обоснование и формулировка метода.
3.1.1. Потенциальные функции в задачах поиска исключений.
3.1.2. Идея метода, определение исключения.
3.1.3. Алгоритм поиска исключений на основе блочного покоординатного спуска
3.1.4. Исследование сходимости.
3.2. Повышение вычислительной эффективности метода для больших объемов данных.
3.2.1. Оценка сложности алгоритма и применение методов случайной выборки.
3.2.2. Проблема упрощения решающего правила в методах, использующих потенциальные функции.
3.2.3. Алгоритм упрощения решающего правила на основе алгоритма кластеризации Руспини.
3.3. Экспериментальное исследование метода на эталонных наборах
данных.
3.3.1. Данные с числовыми атрибутами. Тестовый набор данных НВК
3.3.2. Данные с бинарными и номинальными атрибутами. Тестовые наборы данных из архива 1.
к 3.3.3 Реляционные данные. База данных i
3.5. ВЫВОДЫ.
ГЛАВА IV. АПРОБАЦИЯ НА ПРИКЛАДНОЙ ЗАДАЧЕ ОБНАРУЖЕНИЯ КОМПЬЮТЕРНЫХ АТАК.
4.1. Задача обнаружения атак
4.1.1. Методы И АД в системах обнаружения атак.
4.1.2. Методика верификации алгоритмов выявления сетевых атак
4.2. Экспериментальное исследование метода для задачи выявления СЕТЕВЫХ АТАК
4.2.1. Постановка эксперимента
4.2.2. Результаты эксперимента
4.2.3. Сравнительный анализ.
4.3. Программная реализация.
4.3.1. Реализация модуля поиска исключений, поддерживающего стандарт О В ii.
. 4.3.2. Архитектура и функциональность экспериментальной системы обнаружения атак
4.4.Вывод ы.
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


Очевидно, что такая постановка задачи остается интуитивной, поскольку не накладывает никаких условий на множество анализируемых объектов X, не определяет понятие «сходства» на множестве X, и, вообще говоря, не дает формального определения самого понятия исключения. Разработать эффективный метод поиска таких исключений в исходном множестве анализируемых объектов. При решении данных подзадач используется доступная информация о структуре и свойствах множества анализируемых объектов. Но даже для одного и того же исходного множества X могут быть применены различные подходы для формализации понятия исключения, что приводит к различным постановкам задачи поиска исключений и, соответственно, объекты, определенные как исключения в рамках одного подхода могут не являться таковыми в рамках другого. D от данного объекта о». К данной группе относятся методы поиска исключений на основе нейронных сетей [,,,], методы последовательного поиска исключений (Sequential Exception Mining) [], методы на основе кластеризации [,] и другие [,]. Следует заметить, что попытки ввести универсальное определение исключения предпринимались в работе []. Но, к сожалению, предложенное понятие универсального исключения не соответствовало определениям исключения, используемым в методах анализа отклонений. Кроме того, даже для статистического и метрического подхода удалось доказать эквивалентность определений исключения только для простейших случаев. Большинство методов поиска исключений в системах интеллектуального анализа данных были заимствованы из смежных областей, таких как математическая статистика и искуственный интеллект. Поэтому они накладывают ряд жестких ограничений на структуру и размер множества анализируемых объектов. Например, некоторые методы рассматривают анализируемый объект как числовой вектор фиксированной длины; другие подразумевают, что вероятностная модель данных должна быть задана априори, хотя бы параметрически; третьи имеют сложность выше квадратичной, что не позволяет их применять для больших объемов данных. Данные ограничения делают эти методы мало применимыми в системах НАД в общем случае, хотя на отдельных прикладных задачах они могут показывать хорошие результаты. Сформулируем особенности анализируемых данных в системах НАД, которые отличают такие системы от статистических, нейросетевых и других специализированных программных систем анализа данных. В свою очередь каждая из этих особенностей имеет ряд аспектов с точки зрения требований к методу поиска исключений. Во-вторых, у нас нет информации о том, каким классам могут принадлежать анализируемые объекты, в частности, мы не можем заранее сказать какой объект является исключением, а какой нет. Используя терминологию теории распознавания образов, это условие заставляет нас использовать только методы автоматической классификации, так называемые методы обучения без учителя или неконтролируемого обучения (unsupervised learning methods) [7]. Анализируемый объект может иметь сложную разнородную структуру. Данная особенность следует из требования глубокой интеграции системы ИАД с хранилищами и базами данных [,,]. Это означает, что множество анализируемых объектов формируется непосредственно выборкой из хранилища или базы данных, то есть анализируемый объект может быть представлен не вектором признаков, а срезом n-мерного информационного куба [,4,5], для многомерной модели, или набором взаимосвязанных записей из различных таблиц, для реляционной модели [,]. И наконец, третья важная особенность, это большой объем и размерность анализируемых данных. Во-вторых, не могут иметь высокую вычислительную сложность. Согласно [] сложность выше 0(Ь'2) уже не позволяет применять такой алгоритм в системах НАД. В связи с перечисленными выше особенностями систем ИАД, а также важностью прикладных задач, решаемых с помощью таких систем, становится актуальной проблема разработки новых эффективных алгоритмов поиска исключений для применения их в системах интеллектуального анализа данных. Диссертационная работа состоит'из четырех глав, каждая из которых содержит по три параграфа. Первая глава посвящена обзору существующих алгоритмов поиска исключений, представляющих три основных подхода: статистический, метрический и анализ отклонений.