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

результатів, як і для звичайної відстані Евкліда. Проте при його застосуванні вплив окремих великих різниць (викидів) зменшується (оскільки вони не зводяться в квадрат). Формула для розрахунку манхеттенскої відстані:

 ;                                     (2.3)

- відстань Чебишева. Ця відстань може виявитися корисною, коли треба визначити два об'єкти як «різні», якщо вони розрізняються по будь - якій одній координаті. Відстань Чебишева обчислюється за формулою:

 ;                                     (2.4)

- степенева відстань. Застосовується у разі, коли необхідно збільшити або зменшити вагу, що відноситься до розмірності, для якої відповідні об’єкти сильно відрізняються. Степенева відстань обчислюється за наступною формулою:

 ,                                     (2.5)

де r і p – параметри, що визначаються користувачем. Параметр p відповідальний за поступове зважування різниць по окремих координатах, параметр r відповідальний за прогресивне зважування великих відстаней між об’єктами. Якщо обидва параметри – r і p – рівні 2, то ця відстань співпадає з відстанню Евкліда.

Вибір метрики повністю лежить на досліднику, оскільки результати кластеризації можуть істотно відрізнятися при використанні різних метрик [19].

Для даного випадку найбільш доцільна метрика — Евклідова [5], так як дана міра ідеально підходить для розрахунку географічних відстаней та бойових порядків. Решта метрик менш доцільніші, так як вони застосовуються для вирішення інших специфічних завдань, і не придатні для здійснення кластеризації просторових даних. Основні характеристики бойових порядків засобів ППО і ознаки по яких можливо здійснювати кластеризацію представлені у табл. 2.1.

Таблиця 2.1

Основні характеристики бойових порядків засобів ППО і ознаки по яких можливо здійснювати кластеризацію

Назва дивізіонуКількість бойових батарей, шт.Відстань між бойовими батареями, кмВіддаленість від переднього краю, кмДальність зв’язку, км

“Чапарел - Вулкан”38-15>158-30

“Петріот”630-50>4030-100

“Удосконалений Хок”3-415-40>3515-80

Ознаки, по яким здійснюється кластеризація:

- кількість бойових батарей - N;

- відстань між бойовими батареями  ;

- віддаленість від переднього краю  ;

- дальність зв’язку  .

2.2 Вибір доцільного алгоритму  кластеризації складних об’єктів моніторингу

Проаналізувавши відомі алгоритми кластеризації [4] , для вирішення задачі ідентифікації, найбільш доцільними є нечіткі алгоритми. Нечіткі методи кластеризації, на відміну від чітких, дозволяють одному і тому ж об’єкту належати одночасно кільком кластерам з різним ступенем приналежності. Нечітка кластеризація в багатьох ситуаціях переважає чітку, зокрема для об’єктів, розташованих на грані кластерів.

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

- вибір початкового нечіткого розбиття n об’єктів k кластерів шляхом вибору матриці приналежності U розміру n x k;

- пошук значення критерію нечіткої помилки, використовуючи матрицю U:

 ,                         (2.6)

де   – «центр мас» нечіткого кластера k :

 ;                                         (2.7)

- кожне спостереження «приписується» до одного з n кластерів – того, відстань до якого найкоротша;

- розраховується новий центр кожного кластера як елемент, ознаки якого розраховуються як середнє арифметичне ознак об’єктів, що входять у цей кластер.

Відбувається така кількість ітерацій (повторюються кроки 3-4), поки кластерні центри не стануть стійкими (тобто при кожній ітерації в кожному кластері виявлятимуться одні й ті самі об’єкти). Це повторення грунтоване на мінімізації цільової функції, яка представляє собою відстань від будь-якого елемента кластера у центрі самого кластеру, зважених щодо членства класу, відносно іншого елемента кластера. Дисперсія всередині кластера буде мінімізована, а між кластерами – максимізована. Цей алгоритм може не підійти, якщо заздалегідь невідоме число кластерів, або необхідно однозначно віднести кожен об'єкт до одного кластера.

Переваги:

- простота та швидкість виконання.

Недоліки:

- результат кластеризації у найбільшій мірі залежить від випадкових початкових позицій кластерних центрів;

- алгоритм чутливий до аномальних вимірів (викидів), які можуть викривлювати середнє.

Існують наступні алгоритми нечіткого кластерного аналізу:

- FCM (Fuzzy c-means – нечітких c-середніх); 

- гірської кластеризації;

- поступово зростаючого розбиття.

Алгоритм FCM

Алгоритм нечіткої кластеризації називають FCM - алгоритмом (Fuzzy Classifier Means, Fuzzy C-Means). Метою FCM - алгоритму кластеризації є автоматична класифікація безлічі об'єктів, які задаються векторами ознак в просторі ознак. Іншими словами, такий алгоритм визначає кластери і відповідно класифікує об'єкти. Кластери представляються нечіткими множинами, і, крім того, межі між кластерами також є нечіткими. 

FCM-алгоритм кластеризації припускає, що об'єкти належать усім кластерам з певним ступенем приналежності. Ступінь приналежності визначається відстанню від об'єкта до відповідних кластерних центрів. Даний алгоритм ітераційно обчислює центри кластерів і нові ступені приналежності об'єктів.

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

а) ініціалізація.

Вибираються наступні параметри: 

- необхідна кількість кластерів N, 2 <N <К;

- міра відстаней (Евклідова);