Розробки алгоритму ідентифікації складних об’єктів моніторингу на основі нечітких алгоритмів кластерного аналізу

style="text-align: justify;">- фіксований параметр q;

- початкова (на нульовій ітерації) матриця приналежності   об'єктів   з урахуванням заданих початкових центрів кластерів  .

б) регулювання позицій   центрів кластерів.

На t-му ітераційному кроці при відомій матриці   обчислюється   відповідно до викладеного вище рішенням системи диференціальних рівнянь.

в) корегування значень приналежності  .

Враховуючи відомі  , вираховуються  , якщо  , в іншому випадку:

 ;                             (2.8)

г) зупинка алгоритму.

Алгоритм нечіткої кластеризації зупиняється при виконанні наступної умови:

 ,                                       (2.9)

де  ||         || − матрична норма (Евклідова);

ε − заздалегідь заданий рівень точності.

Алгоритм гірської кластеризації

Алгоритм пікового групування (гірської кластеризації), запропонований Р. Ягером та Д. Фільовим, не вимагає задавання кількості кластерів. Кластеризація гірським алгоритмом не є нечіткою, однак, її часто використовують при синтезі нечітких правил з даних.

Ідея алгоритму полягає в тому, що спочатку визначають точки, які можуть бути центрами кластерів. Далі для кожної такої точки розраховується значення потенціалу, що показує можливість формування кластера в її околиці. Чим щільніше розташовані об’єкти в околиці потенційного центра кластера, тим вище значення його потенціалу. Після цього ітераційно вибираються центри кластерів серед точок з максимальними потенціалами. Алгоритм гірської кластеризації можна записати як послідовність таких кроків:

а) формування потенційних центрів кластерів, число яких Q повинно бути кінцевим. Центрами кластерів можуть бути об'єкти кластеризації - екземпляри вибірки х. Тоді Q = S, де S - кількість екземплярів у вибірці x. Другий спосіб вибору потенційних центрів кластерів полягає в дискретизації простору вхідних ознак. Для цього діапазони зміни вхідних ознак розбивають на кілька інтервалів. Проводячи через точки розбиття прямі, паралельні координатним осям, одержуємо «сітковий» гіперкуб. Вузли цієї сітки і будуть відповідати центрам потенційних кластерів. Позначимо через   - кількість значень, що можуть приймати центри кластерів за r-ою координатою, r = 1,2,...N. Тоді кількість можливих кластерів буде дорівнювати:

 ;                                           (2.10)

б) розрахунок потенціалу центрів кластерів за формулою:

 ,                   (2.11)

де   - потенційний центр q-го кластера;

  − значення j-ої ознаки для q-го кластера;

α − додатня константа;

  − відстань (Евклідова) між потенційним центром кластера   та об’єктом кластеризації  .

У випадку, коли об’єкти кластеризації задані двома ознаками (N = 2), графічне зображення розподілу потенціалу буде являти собою поверхню, що нагадує гірський рельєф (рис. 2.1). Звідси і назва – гірський алгоритм кластеризації.

Рисунок 2.1 − Розподіл потенціалу при кластеризації гірським алгоритмом

в) вибір центрами кластерів координати «гірських» вершин. Для цього, центром першого кластера призначають точку з найбільшим потенціалом. Звичайно, найвища вершина оточена декількома досить високими піками. Тому призначення центром наступного кластера точки з максимальним потенціалом серед вершин, що залишилися, призвело б до виділення великого числа близько розташованих центрів кластерів.

Щоб вибрати наступний центр кластера необхідно спочатку виключити вплив щойно знайденого кластера. Для цього значення потенціалу для можливих центрів кластерів, що залишилися, перераховується в такий спосіб: від поточних значень потенціалу віднімають внесок центра щойно знайденого кластера (тому кластеризацію за цим алгоритмом іноді називають субтрактивною). Перерахунок потенціалу відбувається за формулою: 

 ,                     (2.12)

де    − потенціал на першій ітерації;

  − потенціал на другій ітерації;

β − додатня константа;

  − номер першого знайденого центра кластера:

 .                             (2.13)

Номер центра другого кластера визначається за максимальним значенням оновленого потенціалу:

 .                             (2.14)

Потім знову перераховуються значення потенціалів:

 .                   (2.15)

д) якщо максимальне значення потенціалу перевищує деякий поріг, то здійснюється перехід до пункту б), у іншому випадку – зупинка. Алгоритм гірської кластеризації є ефективним, якщо розмірність вхідного вектора не є занадто великою. У іншому випадку (при великій кількості ознак) число потенційних центрів наростає лавиноподібно, і процес розрахунку чергових пікових функцій стає занадто тривалим, а процедура кластеризації – малоефективною.

Алгоритм гірської кластеризації можна використовуватись для синтезу нечіткої бази знань. Нехай ми маємо   – центри кластерів, знайдені в результаті гірської кластеризації, кожному з яких зіставлене значення цільової ознаки  . Тоді кожному центру кластера   ставиться у відповідність правило: якщо  , то  , де нечіткі терми   та   характеризуються гаусівськими функціями приналежності:

 .                 (2.16)

Алгоритм поступово зростаючого розбиття IDA

Алгоритм