Содержание к диссертации
Введение
Глава 1. Системы распознавания и методы кластеризации 12
1.1. Распознавание объектов 12
1.1.1. Классификация систем распознавания образов 12
1.1.2. Классификация и кластеризация образов 16
1.2. Методы кластерного анализа данных 17
1.2.1. Общая схема работы методов кластеризации 17
1.2.2. Иерархические методы 20
1.2.3. Неиерархические методы 24
1.2.4. Сравнительный анализ методов кластеризации 33
Выводы по главе 1 37
Глава 2. Разработка нечеткого обобщения метода COBWEB 39
2.1. Метод концептуального кластерного анализа COBWEB 39
2.1.1. Общая характеристика метода COBWEB 39
2.1.2. Формальное представление метода COBWEB 44
2.1.3. Модель концептуального кластерного анализа COBWEB47
2.2. Разработка нечеткого обобщения метода COBWEB 48
Выводы по главе 2 56
Глава 3. Формирование функций принадлежности параметров кластеризуемых объектов 58
3.1. Функции принадлежности 58
3.2. Численный метод формирования функций принадлежности 60
3.3. Сравнение функций принадлежности 69
Выводы по главе 3 74
Глава 4. Решение практических задач кластеризации объектов с нечеткими значениями параметров 75
4.1. Программный комплекс, реализующий разработанный метод кластеризации данных 75
4.2. Автоматизация процесса формирования пользовательских ролей 82
4.3. Выявление вредоносного программного обеспечения 95
4.4. Сравнительный анализ точности кластеризации 99
4.5. Оценка производительности разработанного программного комплекса 100
Выводы по главе 4 104
Заключение 105
Список используемых источников
- Классификация и кластеризация образов
- Общая характеристика метода COBWEB
- Численный метод формирования функций принадлежности
- Автоматизация процесса формирования пользовательских ролей
Классификация и кластеризация образов
Выделяют агломеративные, дивизимные и концептуальные иерархические методы кластеризации [19]. В алгомеративных методах [64] каждый объект сначала заносится в отдельный кластер, по мере выполнения алгоритма кластеры объединяются, пока не получается единственный кластер, который включает в себя все исходные объекты. Примером данных методов является метод ближайшего соседа, метод одиночной связи, метод Ward, метод CURE [5, 7, 26, 73]. В дивизимных методах [8] на начальном этапе все рассматриваемые объекты определяются в один единственный кластер. После этого выполняется разделение кластера на основании выбранной меры сходства. Разделение продолжается до тех пор, пока каждый объект не будет определен в отдельный кластер. Примером данных методов является минимальное покрывающее дерево (Minimum Spanning Trees), метод BIRCH [5, 74, 67].
В концептуальных методах [28] каждый кластер представляется в виде концепта, а на выходе формируется иерархическое дерево. Примером данных методов является метод COBWEB, метод UNIMEM, метод ITERATE [58, 64, 69].
Результат работы иерархического метода можно представить в виде дендрограммы (Рис. 1.4) или классификационного дерева. Дендограмма показывает, в каком направлении происходит кластеризация объектов [64]. Поэтому можно понять с помощью какого из методов были получены данные результаты.
Одним из самых известных методов, относящихся к иерархическим агломеративным методам, является метод ближайшего соседа [5]. В данном методе кластеры объединяются на основе информации о расстоянии между ближними, дальними и центральными объектами кластеров. На рисунке 1.5 представлена блок-схема выполнения метода ближайшего соседа [5].
Интерпретация результатов данного метода происходит путем проведения перпендикулярной линии по направлению распространения дендограммы. Минимальное покрывающее дерево Данный метод относится к иерархическим дивизимным методам и описан в [19]. Он выполняет кластеризацию объектов «сверху вниз». Для данного метода характерно в начале определение всех объектов в единственный кластер. В ходе выполнения алгоритма кластеры разбиваются на два, пока каждый объект не окажется в отдельном кластере. При этом происходит оценка расстояния между ними. Расстояние между двумя кластерами должно быть максимальным.
В этом методе, описанном в [64] реализуется вероятностное представление кластеров. Объект, принадлежащий кластеру, определяется не множеством значений каждого параметра объекта, а с помощью вероятности появления конкретных значений параметра у объекта. Обозначим условную вероятность, с которой параметр Aj, принимает значение vp, в случае, когда объект относится к кластеру Q, как P(Aj =У .\ск). Для всех кластеров в иерархии хранятся вероятности появления того или иного значения для каждого параметра объекта. При появлении очередного объекта метод COBWEB начинает оценивать качество отнесения этого объекта к существующему кластеру. После этого происходит модификация иерархии кластеров в соответствии с новым объектом. Основной критерий или функция оценки качества кластеризации получила название полезность кластеризации. Эта функция находит и производит максимизацию вероятности того, что объекты, которые были определены в один кластер, будут иметь значения параметров максимально схожих друг с другом. А для объектов из различных кластеров значения параметров максимально отличаются. Полезность кластеризации представлена в [64] и определяется следующей формулой: Оно определяет вероятность того, что если значение Vv параметра Aj принимает определенное значение, то объект относится к кластеру Q [64]. При максимальной величине данного значения, параметры объектов, отнесенных к одному кластеру, будут иметь максимально одинаковые значения.
Общая характеристика метода COBWEB
Проведен сравнительный анализ методов кластеризации по следующим основным параметрам: автоматическое определение кластеров, высокая производительность при работе с большими массивами данных, чувствительность к выбросам, необходимость предварительного задания полного множества объектов кластеризации.
Отмечено, что методы концептуальной кластеризации данных, в том числе и метод COBWEB по сравнению с другими методами обладают следующими свойствами:
Данные свойства, а также способность к автоматическому определению кластеров, позволяют эффективно применять методы концептуальной кластеризации данных при решении многих практических задач, требующих обработки исходных данных в реальном режиме времени, с непрерывным сбором и обработкой больших объемов информации. Кроме этого данные методы можно эффективно использовать для решения задач выявления аномалий.
Отмечено, что основным недостатком классических (традиционных) методов кластеризации является то, что они работают с объектами, параметры которых заданы исключительно в четком виде, что затрудняет их практическое использование при работе с объектами нечеткой природы. С другой стороны большинство нечетких методов кластеризации работают с четкими значениями параметров объектов, формируя нечеткие кластеры, например, на основе оценки расстояний между объектами и центром кластера. Такой подход не позволяет эффективно осуществлять кластеризацию объектов с нечетко заданными значениями параметров. В связи с этим, актуальной задачей является разработка методов кластерного анализа, способных учитывать нечеткую природу объектов, то есть работать с параметрами, заданными в нечеткой форме в виде функций принадлежности. В том числе данная задача является актуальной для метода концептуальной кластеризации данных COBWEB. Глава 2. Разработка нечеткого обобщения метода COBWEB
Данная глава посвящена исследованию метода концептуальной кластеризации COBWEB, разработке модели концептуальной кластеризации объектов с нечеткими значениями параметров, разработке нового метода концептуальной кластеризации, обобщающего метод COBWEB, для работы с объектами с нечеткими значениями параметров.
Метод COBWEB был предложен в работе [64] Дугласом Фишером. Метод COBWEB относится к иерархическим концептуальным методам кластеризации. COBWEB работает пошагово, обновляя кластеры от объекта к объекту, тогда как некоторые итеративные методы кластеризации, такие как k-means, проходят через вс множество данных. Кластеры, которые создает COBWEB, формируют дерево классификации, в котором каждый лист представляет кластер. Корневой узел представляет весь набор данных, а ветви дерева представляют собой иерархические кластеры. Общее число кластеров может достигать общего количества рассматриваемых объектов.
Каждый кластер содержит объекты со значениями параметров. Каждый параметр объекта определяется бинарным значением (0 или 1). Если 1, то данный параметр присутствует у объекта, если 0, то параметр отсутствует.
На рисунке 2.1 представлен пример дерева классификации. Пусть кластер С1 содержит следующие три объекта:
Каждый объект описывается параметрами [а, Ъ, с]. В кластере хранится сумма по каждому параметру [2,2,3], показывающая, что у двух объектов присутствует параметр а, еще у двух объектов присутствует параметр Ъ и все три объекта имеют параметр с. Каждый кластер так же хранит условную вероятность появления параметров для этого кластера. Например, если объект является членом кластера С, то вероятность, что у него присутствует параметр а - 2/3. Аналогично, вероятность, что у объекта присутствует параметр Ъ - 2/3 и вероятность, что у объекта присутствует параметр с - 3/3. Тогда условная вероятность появления параметров может быть представлен как [2/3, 2/3, 3/3], что соответствует функции вероятности появления у объектов, относящихся к кластеру С, параметров
Численный метод формирования функций принадлежности
В данной главе рассмотрены основные типы функций принадлежности, используемые для описания параметров кластеризуемых объектов: кусочно-линейные и П-образные. Представлены их аналитические выражения.
Предложен численный метод формирования кусочно-линейных и П-образных функций принадлежности для параметров кластеризуемых объектов на основе анализа исходных данных. Функция принадлежности нечеткого числа строится в два этапа:
Получены выражения (3.36), (3.38) для определения точек пересечения двух П-образных и (3.40) для определения точек пересечения двух кусочно-линейных функций принадлежности. Глава 4. Решение практических задач кластеризации объектов с нечеткими значениями параметров
В данной главе представлено описание программного комплекса, реализующего разработанный метод кластеризации объектов, описанных параметрами нечеткой природы. Представлена архитектура программного комплекса. Решен ряд практических задач по кластеризации объектов и проведены экспериментальные исследования для сравнительной оценки точности кластеризации. Показано, что использование кусочно-линейных функций принадлежности для задания значений параметров нечетких объектов позволяет увеличить разделяющую способность кластеров в разработанном методе по сравнению П-образными функциями. Проведена оценка производительности разработанного программного комплекса.
Для практического решения задач с применением теоретических результатов, полученных ранее, был разработан программный комплекс в среде С# [13, 45, 49, 53]. Данный комплекс позволяет проводить численно-параметрические исследования модели и метода концептуальной кластеризации объектов с нечеткими значениями параметров, а также решать практические задачи. На разработанный программный комплекс получено свидетельство о государственной регистрации программы для ЭВМ (№ 2013614934).
Программный комплекс может быть эффективно использован для решения многих практических задач, связанных с кластеризацией данных в реальном режиме времени, когда исходное множество объектов и количество кластеров неизвестны, а объекты имеют нечеткую природу.
В структуру комплекса входят, как штатные средства администрирования ОС Windows [31] и пакет Microsoft Office Excel, так и программная реализация «КНЗ-1», на основе объектно-ориентированного языка программирования C#, разработанного метода кластеризации объектов, описанных параметрами нечеткой природы. Архитектура комплекса представлена на рисунке 4.1.
Архитектура программного комплекса Модуль сбора данных предназначен для сбора статистических данных о действиях пользователей в КИС. Сбор данных осуществляется на основе средств администрирования ОС Windows – системный монитор, представленного на рисунке 4.2. Рис. 4.2. Средство администрирования ОС Windows – системный монитор
Системный монитор используется для диагностики проблем производительности и сбора данных о производительности системы. Приложение позволяет вести сбор данных по конкретным системным счетчикам, как на локальном, так и на компьютерах входящих в КИС. Статистические данные сохраняются на жестком диске в виде текстового файла с разделителями табуляции, пример представлен на рисунке 4.3. Так же для регистрации действий пользователей в КИС возможно использовать коммерческие программные продукты Spector CNE, LanAgent 1.2 и др. Рис. 4.3. Представление статистических данных
Модуль подготовки данных на основе полученных статистических данных, и предложенного численного метода формирования функций принадлежности, строит функции принадлежности для каждого пользователя по каждому заданному параметру. Интерфейс этого модуля представлен на рисунке 4.4. Формально это таблица, ячейками которой являются кусочно-линейные функции принадлежности в виде выражения 3.1. А строки и столбцы – это пользователи и конкретные параметры, по которым производился сбор данных. Рис. 4.4. Графическое представление модуля подготовки данных
Выбрав в правой части окна конкретный параметр, получим графическое представление функций принадлежности пользователей относительно данного параметра. Модуль обработки данных выполняет программу «КНЗ-1», написанную для реализации разработанного метода кластеризации. Основным используемым компонентом является модифицированная формула (2.3) для оценки полезности конкретного варианта кластеризации. В приложении А приведены текстовые коды основных блоков программы «КНЗ-1».
В блок-схеме, на рисунке 4.5, представлено выполнение метода кластеризации в программе «КНЗ-1». В начале, происходит проверка, добавляется ли новый объект в алгоритм. Далее над объектом выполняются четыре операции, которые описаны в разделе 2.1.1 диссертации (добавление в существующий кластер, создание нового кластера, слияние двух кластеров, разделение кластера на два). После выполнения каждой операции происходит вычисление полезности кластеризации согласно формуле (2.3). В итоге выполняется та операция, при которой полезность кластеризации будет наивысшей.
Автоматизация процесса формирования пользовательских ролей
В данной главе разработан программный комплекс нечеткой концептуальной кластеризации объектов в среде С#, позволяющий осуществлять концептуальную кластеризацию объектов с нечеткими значениями параметров. Решен ряд практических задач по кластеризации объектов с нечеткими значениями параметров – задача автоматизации формирования пользовательских ролей, выявления вредоносного ПО, кластеризации животных.
На примере задачи автоматизации формирования пользовательских ролей, экспериментальным путем показано, что использование кусочно-линейных функций принадлежности для задания нечетких значений параметров объекта позволяет увеличить разделяющую способность кластеров в разработанном методе по сравнению c П-образными функциями.
При решении задачи выявления узлов, зараженных вредоносным программным обеспечением, разработанный метод кластеризации позволил осуществить верную классификацию зараженных узлов в 95% случаев.
На примере задачи кластеризации животных была сравнена точность разработанного метода кластеризации с другими известными методами. Разработанный метод, в отличие от других, показал 100% точность распознавания. На тех же данных точность известных методов кластеризации EM и g-means составила, соответственно, 80,9% и 76,1%.
Разработана модель концептуальной кластеризации объектов с нечеткими значениями параметров в виде взвешенного графа (дерева), на основании которого происходит разбиение объектов по кластерам.
Разработан новый метод концептуальной кластеризации, основанный на методе COBWEB, который, в отличие от существующих методов, позволяет строить модель концептуальной кластеризации для объектов нечеткой природы, а также повышать точность кластеризации по сравнению с известными четкими методами. Основу метода составляет предложенная в работе модифицированная формула оценки полезности концептуальной кластеризации для объектов с нечеткими значениями параметров. Кроме этого, сформулирован ряд утверждений, определяющих качество разбиения объектов по кластерам. Результаты, полученные в ходе экспериментальных исследований, показали, что точность кластеризации объектов с нечеткими значениями параметров, получаемая с помощью разработанного метода, превосходит точность других существующих методов кластеризации. На примере решения задачи кластеризации, разработанный метод показал 100% точность. На тех же данных точность известных методов кластеризации EM и g-means составила, соответственно, 80,9% и 76,1%.
Разработан программный комплекс нечеткой концептуальной кластеризации объектов в среде С#, позволяющий осуществлять концептуальную кластеризацию объектов с нечеткими значениями параметров, проводить исследования разработанного метода концептуальной кластеризации, решать практические задачи по кластеризации объектов, описанных в нечетком виде. На разработанный программный комплекс получено свидетельство о государственной регистрации программы для ЭВМ (№ 2013614934).
Предложен эффективный численный метод формирования кусочно-линейных и П-образных функций принадлежности для параметров кластеризуемых объектов на основе анализа исходных данных. При этом с помощью метода градиентного спуска минимизируется функция ошибки, определяемая в виде отклонения аналитически заданной функции принадлежности от реальных данных. На примере задачи автоматизации формирования пользовательских ролей, экспериментальным путем показано, что использование кусочно-линейных функций принадлежности для задания нечетких значений параметров объекта позволяет увеличить разделяющую способность кластеров в разработанном методе по сравнению c П-образными функциями.
Решен ряд практических задач по кластеризации объектов с нечеткими значениями параметров. Проведены исследования и эксперименты для оценки точности разработанного метода кластеризации. Полученные в работе теоретические результаты были использованы для решения задачи автоматизации формирования пользовательских ролей в корпоративной информационной сети, включающей в себя 22 пользователя, каждый из которых описывался 18 параметрами. Полученные результаты позволили выделить пользователей, характеризующихся аномальным поведением в компьютерной сети. Вторая практическая задача заключалась в выявлении узлов, зараженных вредоносным программным обеспечением.
Разработанный метод кластеризации позволил осуществить верную классификацию зараженных узлов в 95% случаев. На примере задачи кластеризации животных была сравнена точность разработанного метода кластеризации с другими известными методами. Разработанный метод, в отличие от других, показал 100% точность распознавания.
