+3 8(066) 185-39-18
fкластеризації, що дозволить багато в чому покращити процес відображення просторових даних і полегшить роботу з ними.
1.1 Методи та алгоритми кластеризації
З аналізу літератури [2] визначено, що загальноприйнятої класифікації методів кластеризації не існує. Але якщо узагальнити різні методи кластеризації, то можна виділити ряд груп.
Об'єднання схожих об'єктів у групи може бути здійснене різними способами. Серед таких груп, згідно [18] виділяються наступні:
а) ієрархічні групи – будують не одне розбиття вибірки на кластери, що не перетинаються, а систему вкладеного розбиття. За допомогою таких груп можна виділити кластери, об’єднуючи менші кластери та розподіляючи більші. Тобто на виході створюється дерево кластерів, на різних рівнях якого можна отримати різне розподілення на кластери. Серед груп ієрархічної кластеризації виділяються два основні типи: висхідні і низхідні алгоритми.
- низхідні типи груп кластеризації працюють за принципом «згори-вниз»: на початку усі об'єкти поміщаються в один кластер, який потім розбивається на дрібніші кластери.
- висхідні типи, які на початку роботи поміщають кожен об'єкт в окремий кластер, а потім об'єднують кластери у більші, поки усі об'єкти вибірки не будуть міститись в одному кластері.
б) неієрархічні (плоскі) - будують одне розбиття об’єктів на кластери. Плоскі групи вважаються досить швидкими та простими в дії. До того ж одноразове розбиття дозволяє уникнути необхідності зберігати велику кількість проміжних даних. Серед таких груп кластеризації виділяються наступні типи:
- типи, які ґрунтовані на теорії графів. Суть їх полягає в тому, що вибірка об'єктів представляється у вигляді графа G= (V, E), вершинам (V) якого відповідають об'єкти, а ребра (E) мають вагу, яка дорівнює «відстані» між об'єктами. Перевагою даних типів кластеризації є наочність, відносна простота реалізації і можливість внесення різних удосконалень, які ґрунтовані на геометричних міркуваннях.
- EM – тип. Алгоритм EM – типу використовують в математичній статистиці для пошуку оцінок максимальної правдоподібності параметрів ймовірнісних моделей, коли модель залежить від деяких прихованих змінних. Кожна ітерація EM-типу алгоритму складається з двох кроків. На E-кроку (expectation) обчислюється очікуване значення функції правдоподібності, при цьому приховані змінні розглядаються як спостережувані. На M-кроку (maximization) обчислюється оцінка максимальної правдоподібності, таким чином збільшується очікувана правдоподібність, що обчислюється на E-кроці. Потім це значення використовується для E-кроку на наступній ітерації. Алгоритм виконується до збіжності.
- K – середніх (k – means) – тип. Алгоритм цього типу будує задане число кластерів, розташованих якнайдалі один від одного. Робота алгоритму ділиться на декілька етапів: випадковий вибір k точок, що є початковими «центрами мас» кластерів; віднесення кожного об'єкта до кластера з найближчим «центром мас»; перерахування «центрів мас» кластерів згідно з їх поточним складом; якщо критерій зупинки алгоритму не задоволений, то повернутися до віднесення кожного об'єкта до кластера з найближчим «центром мас». В якості критерію зупинки роботи алгоритму зазвичай вибирають мінімальну зміну середньоквадратичної похибки. Так само можливо зупиняти роботу алгоритму, якщо при спробі віднести об'єкт до кластера з найближчим «центром мас», не було об'єктів, що перемістилися з кластера в кластер. До недоліків цього алгоритму можна віднести необхідність задавати кількість кластерів для розбиття.
- C – середніх (c – means) - найбільш популярний тип нечіткої кластеризації. Він є модифікацією типу k- середніх. Кроки роботи алгоритму даного типу:
1) вибір початкового нечіткого розбиття n об'єктів k кластерів шляхом вибору матриці приналежності U розміру n * k;
2) використовуючи матрицю U, пошук значення критерію нечіткої помилки; кожне спостереження «приписується» до одного з n кластерів – того, відстань до якого найкоротша;
3)розрахунок нового центра кожного кластера як елемент, ознаки якого розраховуються як середнє арифметичне ознак об’єктів, що входять у цей кластер.
Відбувається стільки ітерацій (повторюються кроки 3-4), поки кластерні центри не стануть стійкими.
Не дивлячись на значні відмінності між перерахованими методами всі вони спираються на початкову « гіпотезу компактності»: у просторі об’єктів всі близькі об’єкти повинні відноситись до одного кластера, а всі різні (відмінні) об’єкти відповідно повинні знаходитись у різних кластерах відповідно. Для вирішення основної задачі, тобто ідентифікації ОМ за допомогою алгоритмів кластерного аналізу доцільним буде застосування алгоритму C – середніх – типу. Адже даний тип алгоритму має ряд особливостей та переваг, він дозволяє одному і тому ж об’єкту належати одночасно кільком кластерам з різним ступенем приналежності, а також він простий і швидкий та легко реалізується на практиці.
1.2 Постановка задачі дослідження
Процес прийняття рішення при веденні РМ характеризується частковою невизначеністю і недостовірністю інформації, малим резервом часу та динамічною зміною РЕО. Проаналізувавши теоретичний матеріал було встановлено, що на сучасному етапі існує велика кількість типів кластеризації, які використовують різні принципи та підходи. Але, незважаючи на це, проблема актуальна, розробляються нові алгоритми для вирішення тих чи інших завдань. Для роботи над кваліфікаційною роботою необхідно проаналізувати методи і алгоритми кластеризації, розібратися в області застосування кожного з них і вибрати найбільш доцільний для даного завдання алгоритм, який повинен забезпечувати: вибір найкращого рішення з множини можливих рішень ідентифікації складних ОМ, головним елементом якого є кластеризація.
Підвищення вимог до достовірності та оперативності прийнятих рішень в процесі