close

Вход

Забыли?

вход по аккаунту

?

Модель и метод кластеризации объектов с нечеткими значениями параметров

код для вставкиСкачать
2
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность. Задача кластеризации является одной из важнейших задач
интеллектуального анализа данных в различных проблемных областях – технических, естественнонаучных, социальных. Кластеризация является примером задачи
обучения без учителя и сводится к разбиению исходного множества объектов на
подмножества классов таким образом, чтобы элементы одного класса были максимально схожи между собой, а элементы различных классов – отличались.
Традиционные методы кластерного анализа работают с объектами, параметры которых заданы исключительно в четком виде, что затрудняет их практическое использование при работе с объектами нечеткой природы. В настоящее время для кластеризации подобных объектов активно развиваются методы, основанные на нечеткой логике. Исследованиям в данной области посвящены работы известных зарубежных и российских ученых: Bezdek J.C., Pedrycz W., Zadeh L.A.,
Аверкина А.Н., Батыршина И.З., Вагина В.Н., Васильева В.И., Вятченина Д.А.,
Елизарова С.И. Куприянова М.С., Холода И.И., Ярушкиной Н.Г. и др.
Существует множество методов нечеткой кластеризации, таких как Fuzzy CMeans, Гюстафсона-Кесселя, FOPTICS и др. Данные методы формируют кластеры, границы которых размыты, а объект может одновременно относиться к нескольким из них с различными степенями принадлежности. Однако следует отметить, что известные методы нечеткой кластеризации работают с четко заданными
значениями параметров объектов, формируя кластерные решения, например, на
основе оценки расстояний между объектами и центрами кластеров. Такой подход
не позволяет эффективно осуществлять кластеризацию объектов с нечетко заданными значениями параметров. В связи с этим, актуальной задачей является разработка методов кластеризации, способных учитывать нечеткую природу объектов,
то есть работать с параметрами, заданными в виде функций принадлежности.
Кроме этого, для решения ряда практических задач, требующих обработки
исходных данных в реальном режиме времени, актуально использование методов
концептуальной кластеризации, таких как COBWEB. Основным преимуществом
подобных методов является отсутствие необходимости предварительного задания
полного множества объектов и числа кластеров. Классический вариант реализации метода COBWEB не предполагает работу с нечеткими значениями параметров, что актуализирует решение поставленной выше задачи для данного метода.
Объект исследования: кластеризация объектов с нечеткими значениями параметров.
Предмет исследования: модели и методы концептуальной кластеризации
объектов нечеткой природы.
Цель работы: повышение эффективности концептуальной кластеризации
путем разработки модели, метода и реализующего их программного комплекса
для кластеризации объектов с нечеткими значениями параметров на основе метода COBWEB. Эффективность определяется способностью предложенного метода
находить кластерное решение для объектов с нечеткими значениями параметров и
достигаемой точностью кластеризации.
Достижение поставленной цели потребовало решения следующих задач:
 разработки модели концептуальной кластеризации объектов с нечеткими
значениями параметров;
3
 разработки нового метода концептуальной кластеризации, обобщающего
метод COBWEB, для работы с объектами с нечеткими значениями параметров;
 разработки эффективного численного метода формирования функций
принадлежности параметров кластеризуемых объектов;
 разработки программного комплекса нечеткой концептуальной кластеризации объектов;
 проведения исследований и экспериментов для оценки точности разработанного метода кластеризации;
 решения практических задач концептуальной кластеризации объектов с
нечеткими значениями параметров.
Методы исследования: математическое моделирование, кластерный анализ,
теория нечетких множеств, численные методы, объектно-ориентированное программирование.
Научная новизна работы
1. Разработан новый метод кластеризации, который, в отличие от существующих методов, позволяет строить модель концептуальной кластеризации для
объектов нечеткой природы, а также повышать точность кластеризации по сравнению с известными четкими методами.
2. Предложена модифицированная формула оценки полезности концептуальной кластеризации для объектов с нечеткими значениями параметров.
3. Разработан численный метод формирования кусочно-линейных и Побразных функций принадлежности для параметров кластеризуемых объектов на
основе анализа исходных данных.
4. Экспериментальным путем показано, что использование кусочнолинейных функций принадлежности для задания нечетких значений параметров
объектов позволяет увеличить разделяющую способность кластеров по сравнению с использованием П-образных функций принадлежности.
5. Теоретически доказан ряд утверждений, определяющих качество разбиения объектов по кластерам для разработанного метода кластеризации.
Достоверность результатов работы. Предложенные в диссертации
оригинальные модель и методы теоретически обоснованы и не противоречат
известным положениям других авторов. Достоверность полученных результатов
обеспечена математически строгим выполнением расчетов, подтверждена
вычислительными экспериментами и результатами практического использования.
Теоретическая значимость диссертационной работы заключается в
разработке модели и метода концептуальной кластеризации объектов с нечеткими
значениями параметров и эффективного численного метода формирования
кусочно-линейных и П-образных функций принадлежности.
Практическая значимость диссертации заключается в разработке программного комплекса в среде С#, позволяющего осуществлять концептуальную
кластеризацию объектов с нечеткими значениями параметров, проводить исследования разработанного метода концептуальной кластеризации, решать практические задачи по кластеризации объектов, описанных в нечетком виде.
Публикации по теме диссертации. Основные результаты диссертационного
исследования опубликованы в 15 печатных работах, в том числе 7 статей в российских рецензируемых научных журналах, 7 публикаций в материалах научных
4
семинаров и конференций; получено 1 свидетельство о регистрации программы
для ЭВМ.
Апробация работы. Основные положения и результаты диссертационной
работы докладывались и обсуждались на Международной молодежной научной
конференции «Туполевские чтения» (Казань, 2009, 2010), Всероссийской научной
конференции «Информационные технологии в системе социально-экономической
безопасности России и ее регионов» (Казань, 2010, 2012), региональном научном
семинаре «Методы моделирования» (Казань, 2013).
Реализация результатов работы. Результаты исследования:
 использованы в Министерстве внутренних дел по Республике Татарстан
для выявления вредоносного программного обеспечения на рабочих станциях информационных систем;
 использованы в ОАО «Таттелеком» для решения задачи автоматизации
формирования пользовательских ролей и выявления несанкционированных действий пользователей;
 внедрены в учебный процесс ФГБОУ ВПО «Казанский национальный исследовательский технический университет им. А.Н. Туполева-КАИ» и используются при изучении дисциплин «Интеллектуальные информационные системы»,
«Технологии интеллектуального анализа данных».
Положения, выносимые на защиту:
 модель и метод концептуальной кластеризации объектов с нечеткими значениями параметров;
 формула оценки полезности концептуальной кластеризации объектов нечеткой природы;
 численный метод формирования кусочно-линейных и П-образных функций принадлежности параметров кластеризуемых объектов;
 программный комплекс нечеткой концептуальной кластеризации.
Структура и объем работы. Диссертация изложена на 131 страницах машинописного текста, содержит 36 рисунков, 15 таблиц, состоит из введения, четырех
глав, заключения, списка использованной литературы из 76 наименований на 8
страницах и 6 приложений на 16 страницах.
Сведения о личном вкладе автора. Личный вклад автора состоит в разработке модели и метода концептуальной кластеризации для работы с объектами с
нечеткими значениями параметров. Автором лично предложена формула оценки
полезности концептуальной кластеризации объектов с нечеткими значениями параметров, сформулированы и доказаны утверждения, определяющие качество
разбиения объектов по кластерам. Предложен численный метод формирования
функций принадлежности для нечетких параметров на основе анализа исходных
данных. Лично разработан программный комплекс нечеткой концептуальной кластеризации.
5
СОДЕРЖАНИЕ РАБОТЫ
Во введении отражена актуальность темы исследования, сформулированы
цель и задачи диссертации, показаны научная новизна, практическая ценность,
достоверность и обоснованность результатов диссертации, приведены основные
положения, выносимые на защиту, указана степень апробации и реализации результатов диссертационного исследования, кратко раскрыто содержание глав диссертации.
Первая глава посвящена анализу систем распознавания объектов, методов
кластеризации данных и формулировке целей исследования.
Задача кластеризации - пример задачи обучения без учителя, которая сводится к разбиению исходного множества объектов данных O  Oi i1,r на подмножества в виде классов C  Ck k 1,n таким образом, что элементы одного класса существенно отличались друг от друга по заданному набору параметров A  A j j 1,m от
элементов других классов, и были максимально схожи с элементами своего класса.
Отмечено, что кластеризацию объектов с нечеткими значениями параметров
сложно провести с помощью классических (четких) методов кластеризации.
Большинство методов нечеткой кластеризации (Fuzzy C-Means, FOPTICS) работают с четко описанными параметрами.
Актуализирована необходимость решения задачи разработки метода концептуальной кластеризации, обобщающего метод COBWEB, для работы с объектами
с нечеткими значениями параметров.
Вторая глава посвящена исследованию метода концептуальной кластеризации COBWEB, разработке модели и метода концептуальной кластеризации,
обобщающих COBWEB, для объектов с нечеткими значениями параметров.
Для формализации метода кластеризации COBWEB обозначим через
O  Oi i1,r множество распознаваемых объектов, характеризуемое бинарными параметрами A  A j j 1,m , принимаемыми одно из возможных значений Vij  0;1.
C0 ,C1 ,...,Cn  – множество формируемых кластеров, где n – заранее неизвестно.
Полезность кластеризации в методе COBWEB рассматривается как функция
CU, определяющая сходство объектов в рамках одного кластера и их различие по
отношению к объектам из других кластеров. Внутриклассовое сходство определяется условной вероятностью PA j  Vij | Ck , а межклассовое сходство – условной
вероятностью PCk | A j  Vij .
Функция полезности кластеризации определяется в виде:
CU


n
k 1

P (C k )  j i P ( A j  Vij | C k ) 2   j i P ( A j  Vij ) 2

(1)
n
где n – количество кластеров.
Метод COBWEB строит дерево классификации с вероятностными описаниями концептов. Выбор возможного способа кластеризации объектов основан на
значениях функции полезности кластеризации (1). При построении дерева классификации используются следующие 4 операции:
 отнесение объекта к наилучшему из существующих кластеров;
 добавление нового кластера, содержащего единственный объект;
6
 слияние двух существующих кластеров в один новый с добавлением в него
этого объекта;
 разбиение существующего кластера на два и отнесение объекта к лучшему
из вновь созданных кластеров.
Предлагается модель концептуальной кластеризации объектов в виде дерева,
представленного на рисунке 1.
Рис. 1. Модель концептуальной кластеризации
j
где Сk – число раз, когда значение параметра Aj  1 для объектов в кластере Сk ,
rk – число объектов в кластере Сk .
Формально данная модель концептуальной кластеризации объектов представляется в виде взвешенного графа (дерева) (2)
(2)
G  D, F , H
где D  C0 , C1 ,...,Cn  – множество вершин графа, определяющих кластеры, F –
множество ребер графа, H  h0 ,....,hn  – веса вершин графа, определяющих внутриклассовое
сходство
на
основе
условных
вероятностей
1
m
hk  P x | C k   [C k / rk ,..., C k / rk ] .
Метод концептуальной кластеризации
1. Вводится корневой кластер С0, свойства которого совпадают со свойствами
первого объекта О1=[V11, …, V1m]. Для каждого последующего объекта
Оi=[Vi1,…,Vim] выполняется цикл, реализующий шаги 2-6, в рамках которых выполняются 4 выше представленные операции.
2. Объект Оi добавляется поочередно в кластеры С1, C2,…, Сk. После каждого
добавления вычисляется полезность кластеризации СU1,…, СUk.
3. Для объекта Оi создается новый кластер Сk+1, объект помещается в кластер
и вычисляется полезность кластеризации CUk+1.
4. Объединяются два кластера с максимальными значениями полезности кластеризации из СU1,…,СUk. Образуется новый кластер, в него добавляется объект
Оi. Вычисляется полезность кластеризации CUk+2.
7
5. Объект Оi добавляется в кластер с максимальным значением полезности
кластеризации из СU1,…, СUk. Образуется новый кластер с двумя кластерамипотомками. Вычисляется полезность кластеризации CUk+3.
6. Выбирается максимальное значение полезности кластеризации среди полезностей СU1,…,СUk,CUk+1,CUk+2,CUk+3, в соответствии с ним выбирается операция разбиения объектов по кластерам.
В диссертационной работе разработан метод концептуальной кластеризации,
основанный на методе COBWEB, позволяющий работать с объектами, характеризуемыми параметрами с нечеткими значениями. Данный метод предполагает реализацию классического метода концептуальной кластеризации в следующих
условиях:
1. Множество распознаваемых объектов O  Oi i1,r характеризуется параметрами, описанными в нечетком виде A  A j j 1,m ;
~
~
~
2. Значение параметра A j для объекта Oi определяется в виде функции принадлежности  А~  x   0 ;1;
ij
3. Степень сходства двух функций принадлежности  А~  x  и  А~  x  определяtj
ij
ется их наибольшей верхней границы в виде:
v jit  sup max  A~ x ,  A~ x   0 ,1,
x X

ij
tj

(3)
~
где  А~ij  x  – функция принадлежности параметра A j для объекта Oi , а  А~  x  –
tj
~
функция принадлежности параметра A j для объекта Ot ;
4. Основываясь на формуле полезности кластеризации (1) и положениях 1-3,
оценка полезности кластеризации осуществляется по модифицированной формуле (4)
CU
*
  

n
m
r
k 1
j 1
i 1 ,Oi Ck

r
t 1 ,Ot Ck
v jit / C k   j 1 i 1 t 1 v jit / r
m
r
r
n
,
(4)
где v jit – степень сходства двух функций принадлежности, Ck – количество объектов в кластере С k , r – общее количество рассматриваемых объектов, n – количество кластеров, j  1, m , i ,t  1, r .
m
r
r
 j 1 i 1,O C t 1,O C v jit / C k  0,1 – вычисляет среднее арифметическое значение
i
k
t
k
~
степеней сходства функций принадлежности по параметру A j для всех объектов
Oi , принадлежащих кластеру С k .
  
m
r
r
j 1
i 1
t 1
v jit / r  0,1 – вычисляет среднее арифметическое значение степе~
ней сходства функций принадлежности по параметру A j для всего множества
распознаваемых объектов Oi .
CU *  0 ,1 – полезность кластеризации для объектов, описанных нечеткими
параметрами.
8
Данный метод формирует модель концептуальной кластеризации объектов
(2), при этом значения hk формируются по модифицированным формулам с учетом нечеткого вида параметров объектов.
m
r
r
m
r
r
Утверждение 1. Если  j 1 i 1,O C t 1,O C v jit / C k  1 , а  j 1 i 1 t 1 v jit / r  0 ,
i
то CU  1 .
Утверждение 2. Выражение
k
t
k
*
 
m
r
j 1
i 1 ,Oi C k

r
t 1 ,Ot C k
v jit / C k  1 , когда объек-
ты, отнесенные в кластер С k , имеют идентичные функции принадлежности параметров.
m
r
r
Утверждение 3. Выражение  j 1 i 1 t 1 v jit / r  0 , когда все рассматриваемые объекты имеют различные функции принадлежности параметров (т.е. сравниваемые функции не имеют точек пересечения).
Третья глава посвящена разработке численного метода формирования кусочно-линейных и П-образных функций принадлежности параметров кластеризуемых объектов.
Кусочно-линейные функции принадлежности определены в виде (5)
0, x  a

x  a


, a  x  b
b  a

f  ( x; a, b, c)  

c  x ,b  c  x 
c  b

0, c  x



(5)
П-образные функции принадлежности определены в виде (6)
0 , x  a ;



2
 2 x  a  , a  x  a  b ; 
  b  a 

2


2


b

x
a

b


 x  b; 
 ,
1  2
2
ba




f П ( x; a ,b ,c ,d )  1, x  b , x  c;



2
1  2 x  c  ,c  x  c  d ;

2 
 d c


2
 d x cd

 2 d  c  , 2  x  d ; 

 



0 ,d  x.

(6)
В диссертационной работе предложен численный метод формирования кусочно-линейных и П-образных функций принадлежности для параметров, заданных в нечетком виде, на основе анализа статистических данных. При этом минимизируется функция ошибки, определяемая в виде отклонения аналитически заданной функции принадлежности от реальных данных. Для кусочно-линейных
функций принадлежности суммарная ошибка определяется в виде (7)
n
m
i 1
j 1
Eобщ ( a ,b ,c )   Еia   Е cj
9
(7)
где E ia , E cj – ошибки по левой и правой частям функции принадлежности. Минимизация функции ошибки осуществляется путем корректировки параметров
функции принадлежности с помощью метода градиентного спуска по следующим
формулам.
n
x a
 x b
a i 1  a i  2   i
 yi   i
(8)
2
 (b  a )
i 1  b  a
m
c  xj
 x b
c j 1  c j  2 
 y j   i
(9)
2
j 1  c  b
 (c b)
k
 k  c  xw
 x b
 xw  a
 x b 

bw1  bw  2  
 yw   w

 yw   w


(10)
2
2 
c

b
b

a
(
c

b
)
(
b

a
)




w

1
w

1


Для П-образных функций принадлежности суммарная ошибка определяется в
виде (11), а корректировка параметров функции принадлежности осуществляется
согласно формулам (12)-(15)
n
z
Eобщ ( a ,b ,c , d )   Е   Еvd
i 1
a
i
v 1
(11)
Уравнения (11) для П-образных функций можно представить в следующем
виде:
2
n 
  xi  b  xi  b
x

a


i

ai 1  ai  8   2

y


(12)
i 
2


b

a
b

a
(
b

a
)



i 1  

2
z 
  d  xv  d  xv
 d  xv 

d v 1  d v  8   2

y


(13)
v 
2


d

c
d

c
(
d

c
)



v 1  

2
k 
 ( d  x w )2 
 d  xw 



b w  1  b w  8  2
  yw  
3 



w 1   d  c 
 (d c) 

(14)
2
k 
 ( x w  b )2 
x

a


w

 8    2
  yw  
3 



b

a
(
b

a
)

w 1  



2
m 
 ( d  x j )2 
d

x


j



(15)
  y j  
c j 1  c j  8  2
3
 d  c
 (d c) 
j 1





2
m 
 ( x j  b )2 
 xj  a 



  y j  
 8  2
3

 ba 
 (b  a ) 
j 1

 

Степень сходства двух функций принадлежности  x  и t x  определяется согласно формуле (3). На основании функции (3) определяется наибольшая верхняя
граница пересечения графиков функций принадлежности  x  и t  x  (рисунок 2).
10
Рис. 2. Наибольшая верхняя граница пересечения графиков функций принадлежности
Исходя из способа задания П-образных функций принадлежности (6), точку
их пересечения можно представить как:
(16)
at  x c  x   bt  x d   x 
x
,
c  x   d   x   bt  x   at  x 
Подставляя значение х в (6), получим степень сходства функций принадлежности f  ( x ) ( x; a ( x ) ,b ( x ) ,c ( x ) ,d  ( x ) ) и f t ( x ) ( x; at ( x ) ,bt ( x ) ,ct ( x ) ,d t ( x ) ) .
Пересечение двух кусочно-линейных функций принадлежности, определяется согласно (17)
bt  x c  x   b  x at  x 
x
(17)
c b b a
 x
 x
t x
t x
Подставляя значение х в (5), получим степень сходства функций принадлежности.
В четвертой главе представлено описание программного комплекса, реализующего разработанный метод кластеризации объектов с нечеткими значениями
параметров. Представлена архитектура программного комплекса. Решен ряд
практических задач по кластеризации объектов и проведены экспериментальные
исследования для сравнительной оценки точности кластеризации.
Для практического решения задач с применением теоретических результатов,
полученных ранее, был разработан программный комплекс в среде С#. Данный
комплекс позволяет проводить численно-параметрические исследования разработанной модели и метода концептуальной кластеризации объектов, решать практические задачи по кластеризации объектов с нечеткими значениями параметров. На
разработанный комплекс программ получено свидетельство о государственной
регистрации программы для ЭВМ (№ 2013614934).
С помощью разработанного программного комплекса решена практическая
задача по автоматизации построения пользовательских ролей в корпоративной
информационной системе (КИС). Решение данной задачи позволяет с одной стороны значительно упростить работу администратора информационной безопасности по формированию пользовательских ролей в КИС, с другой стороны позволяет обнаруживать аномальное поведение пользователей в КИС, выявляя недобросовестных сотрудников, использующих информационные ресурсы организации
не только для выполнения своих функциональных обязанностей, но и в личных
целях.
Архитектура системы, предназначенной для автоматизации построения пользовательских ролей, представлена на рисунке 4 и состоит из 4 модулей:
11
Модуль обработки данных
Модуль подготовки данных
Программная реализация нечеткого
обобщения метода кластеризации
Функции принадлежности
Метод построения ФП
Microsoft Office Excel
Модуль интерпретации результатов
Данные
Группы сборщиков данных
Операционная
система
Параметры сбора данных
Системный монитор
Диск
База данных
Модуль сбора данных
Рис. 4. Архитектура системы, предназначенной для автоматизации построения
пользовательских ролей
1. Модуль сбора данных, предназначенный для сбора статистических данных
об объектах. Для решения задачи кластеризации пользователей в КИС сбор данных осуществляется на основе анализа журналов событий. Статистические данные сохраняются на жестком диске в виде текстового файла с разделителями.
2. Модуль подготовки данных позволяет построить функции принадлежности для каждого объекта по каждому из параметров. Выходом данного модуля являются сформированные нечеткие описания объектов в виде функций принадлежности их параметров.
3. Модуль обработки данных реализует разработанный метод концептуальной кластеризации объектов с нечеткими значениями параметров.
4. Модуль интерпретации результатов. Результаты работы метода можно
увидеть в отдельном окне, в котором представляются результаты кластеризации и
полученная иерархия кластеров.
В качестве примера решена задача автоматизации формирования пользовательских ролей для тестовой зоны информационной системы ОАО «Таттелеком».
Структура информационной системы представлена на рисунке 5. Она включает в
себя четыре отдела: Администрация, Бухгалтерия, Отдел продаж, Технический
отдел. В состав локальной вычислительной сети (ЛВС) входит один почтовый и
два файловых сервера, коммутатор, сетевой принтер, 3 МФУ. Осуществляется
выход во внешнюю сеть через прокси-сервер.
12
Рис. 5. Структура информационной системы организации
Осуществлялась кластеризация 22 пользователей: O  Oi i 1 , представленных в таблице 1.
Таблица 1. Пользователи КИС
22
Пользователь
Должность
Отдел
O1
Генеральный директор
O2
Финансовый директор
O3
Технический директор
Администрация
O4
Секретарь
O5
Офис-менеджер
O6
Главный бухгалтер
O7
Зам. главного бухгалтера
Бухгалтерия
O8
Бухгалтер
O9
Начальник отдела продаж
O10
Зам. начальника отдела продаж
Отдел продаж
O11– O13
Менеджеры
O14
Начальник технического отдела
O15
Зам. начальника технического отдела
Технический отдел
O16 – O21
Технические специалисты
O22
Администратор ЛВС
Отдел ИТ
Для описания поведения пользователей было выделено 18 параметров
18
A  A j  j 1 , представленных в таблице 2.
13
Параметр
А1
А2
А3
А4
А5
А6
А7
А8
А9
А10
А11
А12
А13
А14
А15
А16
Таблица 2. Параметры пользователей
Описание параметра
Количество обращений к почтовому серверу в сутки
Количество обращений к файловому серверу H в сутки
Количество обращений к файловому серверу Z в сутки
Количество обращений к коммутатору в сутки
Количество обращений к сетевому принтеру «Бухгалтерия» в сутки
Количество обращений к сетевому МФУ «Секретариат» в сутки
Количество обращений к сетевому МФУ «Менеджеры» в сутки
Количество обращений к сетевому МФУ «Тех.отдел» в сутки
Количество обращений к прокси-серверу в сутки
Количество принятых, отправленных писем через Microsoft Office
Outlook в сутки
Количество обращений к «1С:Бухгалтерия 8» в сутки
Количество обращений к «1С:Документооборот» в сутки
Количество обращений к «1С:Предприятие 8» в сутки
Количество обращений к «Microsoft Navision 3.60» в сутки
Количество обращений к «1С:Зарплата и управление персоналом 8» в
сутки
Количество обращений к модулю «Монитор сопровождения» в сутки
А17
Объем внешнего сетевого трафика в сутки
А18
Средний процент загруженности центрального процессора в сутки
На основании анализа поведения пользователей по выше перечисленным параметрам осуществлялось распределение пользователей по кластерам. Результаты
кластеризации представлены в таблице 3.
Таблица 3. Результаты проведенной кластеризации
Кластер Объект (Пользователь)
С1
O1
С2
O2
С3
O3
С4
O4, O5
С5
O6, O7, O8
С6
O9, O10, O11, O13
С7
С8
O12
O14, O15, O16, O18, O19, O20, O21
С9
O17
С10
O22
Анализируя таблицу 3, можно сделать вывод, что программа сформировала
10 кластеров. Первые три кластера описывают действия пользователей руководящего состава: генерального директора, финансового директора и технического
директора соответственно. Кластер С4 описывает поведение объектов O4 и O5 –
пользователи секретарь и офис-менеджер.
14
В связи с функциональными обязанностями администратора ЛВС его действия в ИС отличны от действий других пользователей. Поэтому для администратора ЛВС (O22) был создан отдельный кластер.
Так же были выделены кластеры, характеризующие поведение пользователей, входящих в различные структурные подразделения организации:
Бухгалтерия – С5;
Отдел продаж – С6;
Технический отдел – С8.
Пользователи, относящиеся к кластерам С7 и С9 были выделены в отдельные
кластеры, что свидетельствует об их аномальном поведении. Проведя детальный
анализ, было выявлено, что объем внешнего сетевого трафика объекта O12 превышает показатели использованного трафика других пользователей отдела продаж, что и формирует подобную аномалию. А пользователь O17 обращался к программам, использование которых не является необходимым при выполнении
функциональных обязанностей сотрудника технического отдела, что также сформировало соответствующую аномалию. Выявление подобных инцидентов позволяет администратору безопасности своевременно отреагировать на них.
На примере задачи автоматизации формирования пользовательских ролей
экспериментальным путем показано, что использование кусочно-линейных функций принадлежности для задания нечетких значений параметров объекта позволяет увеличить разделяющую способность кластеров в разработанном методе по
сравнению с использованием П-образных функций.
Также с помощью разработанного метода решена задача определения вредоносного программного обеспечения (ПО) в компьютерных системах на основе
анализа параметров, отражаемых в журналах событий. Были отобраны 20 виртуальных машин VMware Workstation, некоторые из которых были заражены вредоносным ПО. В качестве вредоносного ПО использовалось Trojan-PSW, TrojanSpy, Trojan-Downloader, IM-Worm, Email-Worm, IRC-Worm. Разработанный метод
кластеризации позволил осуществить верную классификацию зараженных узлов в
95% случаев.
Также был рассмотрен пример решения задачи распределения животных по
кластерам на основе их параметров, заданных в нечетком виде. Для каждого семейства животных (медвежьи, зайцевые, кошачьи) взята выборка по 7 видов 21
O  Oi i 1 . Каждое животное было описано 3 параметрами, описанными в нечет3
ком виде (длина тела, вес, скорость) - A  A j j 1 . В таблице 4 представлены рас-
сматриваемые объекты.
O1
Большая панда
O8
O2 Очковый медведь O9
O3 Бурый медведь O10
O4 Чёрный медведь O11
O5
Белый медведь
O12
Таблица 4. Рассматриваемые объекты
Лазающий заяц
O15
Гепард
Обыкновенная
Бушменов заяц
O16
рысь
Полосатый заяц
O17
Пума
Заяц-русак
O18 Канадская рысь
Дымчатый леоЗаяц-беляк
O19
пард
15
Гималайский медКалифорнийский
O6
ведь
O13
кролик
O20
Леопард
O7
Губач
O14
Дикий кролик
O21
Ирбис
Разработанный метод концептуальной кластеризации распределил объекты
по 3 кластерам в соответствии с семействами животных. На примере решения
данной задачи, разработанный метод кластеризации показал 100% точность кластеризации.
Для сравнительного анализа, данная задача также была решена с помощью
известных методов кластеризации EM и g-means. При этом выполнялась дефаззификация параметров объектов, заданных в нечетком виде. Результаты сравнительного анализа точности кластеризации методов представлены на рисунке 6.
Рис. 6. Сравнительный анализ методов кластеризации
Таким образом, видим, что точность решения задачи кластеризации методами EM и g-means составила, соответственно, 80,9% и 76,1%, что меньше точности, полученной в результате работы разработанного метода.
Проведена оценка производительности разработанного программного комплекса. Для ПЭВМ, построенной на базе процессора Intel Core i3-330M 2,13 ГГц,
метод выполнил кластеризацию 5000 объектов, характеризуемых 48 параметрами,
за 12 секунд. Затрачиваемая производительность составила ≈10,3 GFlops. Полученный результат не является существенным для производительности современных компьютеров.
В заключении приведены основные результаты исследований, представленные в диссертации.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ И ВЫВОДЫ
1. Разработана модель концептуальной кластеризации объектов с нечеткими
значениями параметров в виде взвешенного графа (дерева), на основании которого происходит разбиение объектов по кластерам.
16
2. Разработан новый метод концептуальной кластеризации, основанный на
методе COBWEB, который, в отличие от существующих методов, позволяет
строить модель концептуальной кластеризации для объектов нечеткой природы, а
также повышать точность кластеризации по сравнению с известными четкими методами. Основу метода составляет предложенная в работе модифицированная
формула оценки полезности концептуальной кластеризации для объектов с нечеткими значениями параметров. Кроме этого, сформулирован ряд утверждений,
определяющих качество разбиения объектов по кластерам.
3. Разработан программный комплекс нечеткой концептуальной кластеризации объектов в среде С#, позволяющий осуществлять концептуальную кластеризацию объектов с нечеткими значениями параметров, проводить исследования
разработанного метода концептуальной кластеризации, решать практические задачи по кластеризации объектов, описанных в нечетком виде. На разработанный
программный комплекс получено свидетельство о государственной регистрации
программы для ЭВМ (№ 2013614934).
4. Предложен эффективный численный метод формирования кусочнолинейных и П-образных функций принадлежности для параметров кластеризуемых объектов на основе анализа исходных данных. При этом с помощью метода
градиентного спуска минимизируется функция ошибки, определяемая в виде отклонения аналитически заданной функции принадлежности от реальных данных.
На примере задачи автоматизации формирования пользовательских ролей, экспериментальным путем показано, что использование кусочно-линейных функций
принадлежности для задания нечетких значений параметров объекта позволяет
увеличить разделяющую способность кластеров в разработанном методе по сравнению c П-образными функциями.
5. Решен ряд практических задач по кластеризации объектов с нечеткими
значениями параметров. Проведены исследования и эксперименты для оценки
точности разработанного метода кластеризации. Полученные в работе теоретические результаты были использованы для решения задачи автоматизации формирования пользовательских ролей в корпоративной информационной сети и выделения пользователей, характеризующихся аномальным поведением. Вторая практическая задача заключалась в выявлении узлов, зараженных вредоносным программным обеспечением. Разработанный метод кластеризации позволил осуществить верную классификацию зараженных узлов в 95% случаев. На примере задачи кластеризации животных была сравнена точность разработанного метода
кластеризации с другими известными методами, EM и g-means, точность составила 80,9% и 76,1% соответственно. Разработанный метод показал 100% точность
распознавания.
ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ
Основное содержание диссертации опубликовано в следующих работах:
в российских рецензируемых научных журналах
1. Назаров, А.О. Выбор вида функции принадлежности в нечеткой
модификации
алгоритма
Cobweb
для
задачи
формирования
пользовательских ролей
/ А.О. Назаров, И.В. Аникин // Вестник
Казанского государственного технического университета им. А.Н.
Туполева, 2014. – № 2. – С. 214-219.
17
2. Назаров, А.О. Практическое применение метода концептуальной
кластеризации объектов, характеризуемых нечеткими параметрами / И.В.
Аникин, А.П. Кирпичников, А.О. Назаров // Вестник Казанского
технологического университета. – 2014. – Т.17. – С. 203-207.
3. Назаров, А.О. Модель и метод концептуальной кластеризации объектов,
характеризуемых нечеткими параметрами
/
А.О.
Назаров
//
Фундаментальные исследования. – 2014. – №9 (5). – С. 993-997.
4. Назаров, А.О. Кластеризация пользователей информационной системы на
основе их действий в компьютерной сети [Электронный ресурс] / А.О.
Назаров // Современные проблемы науки и образования. – 2014. – №4. –
URL: http://www.science-education.ru/118-13961
5. Назаров, А.О. Автоматизация процесса формирования пользовательских
ролей на основе метода концептуальной кластеризации данных / А.О.
Назаров, С.В. Суханов, Д.А. Токарев // Известия Института инженерной
физики. – 2014. – № 3. – С. 2-6.
6. Назаров,
А.О.
Формирование
эталонных
профилей
поведения
пользователей в корпоративных информационных системах / А.О. Назаров,
И.В. Аникин // Вестник Казанского государственного технического
университета им. А.Н. Туполева. – 2012. – №3. – С. 138-142.
7. Назаров, А.О. Распознавание поведения объектов методом нечеткой
кластеризации данных / А.О. Назаров, И.В. Аникин // Вестник Казанского
государственного технического университета им. А.Н. Туполева. – 2012. –
№ 4(1). – С. 222-228.
в материалах научных семинаров и конференций:
8. Назаров, А.О. Метод формирования эталонных профилей поведения
пользователей в корпоративных информационных системах [Электронный
ресурс] / А.О. Назаров // Информационные технологии в системе соц.экономич. безопасности России и ее регионов: Электронная библиотека
Казанского (Приволжского) федерального университета – Казань, 2012. –
URL: http://diglib.kpfu.ru/xmlui/handle/123456789/792
9. Назаров, А.О. Сравнительный анализ методов кластеризации данных
относительно формирования элементов ролевого разграничения доступа
[Электронный ресурс] / А.О. Назаров // Информационные технологии в
системе соц.-экономич. безопасности России и ее регионов: Электронная
библиотека Казанского (Приволжского) Федерального Университета –
Казань, 2012. – URL: http://diglib.kpfu.ru/xmlui/handle/123456789/791
10.Назаров, А.О. Ролевая модель разграничения доступа в корпоративных
информационных системах / А.О. Назаров // Информационные технологии в
системе соц.-экономич. безопасности России и ее регионов: сб. трудов III
Всерос. научной конф. – Казань, 2010. – С. 304-307.
11.Назаров, А.О. Обеспечение безопасности информационной системы с
помощью алгоритма кластеризации и нечетких параметров пользователей /
А.О. Назаров // Информационные технологии в системе соц.-экономич.
безопасности России и ее регионов: сб. трудов III Всерос. научной конф. –
Казань, 2010. – С. 206-209.
18
12.Назаров, А.О. Сравнительный анализ алгоритмов кластеризации / А.О.
Назаров // XVIII Туполевские чтения. Междунар. молодежная научная
конф.: тез. докл. – Казань, 2010. – С. 220-222.
13.Назаров, А.О. Формирование пользовательских ролей с помощью
алгоритма кластеризации и нечетких методов / А.О. Назаров // XVIII
Туполевские чтения. Междунар. молодежная научная конф.: тез. докл. –
Казань, 2010. – С. 218-220.
14.Назаров, А.О. Оценка рисков информационной безопасности на базе
экспертных систем / А.О. Назаров // XVII Туполевские чтения. Междунар.
молодежная научная конф.: тез. докл. – Казань, 2009. – С. 81-82.
свидетельства:
15.Назаров, А.О. Свидетельство о государственной регистрации программы
для ЭВМ № 2013614934. КНЗ-1 / А.О. Назаров. – М.: Роспатент, 2013.
19
Документ
Категория
Без категории
Просмотров
24
Размер файла
1 340 Кб
Теги
значения, метод, нечеткими, объектов, модель, кластеризацию, параметры
1/--страниц
Пожаловаться на содержимое документа