Тема: кластеризація, розбиття об'єктів на класи у системах розпізнавання образів "без вчителя"
Завдання:
- Розробити алгоритм кластеризації масиву об'єктів на N кількість класів.
- Написати програму мовою Python розробленого алгоритму.
- Порівняти ефективність кластеризації з різних заходів розрахунку приналежності до класу.
Додаткове завдання:
- Замінити двовимірні масиви даних на тривимірні масиви. Побудувати 3Д модель.
- Розрахувати оптимальну кількість кластерів для рандомного масиву.
- Побудувати другий алгоритм кластеризації
Теорія
На відміну від завдання класифікації або регресії, у разі кластеризації складніше вибрати критерій, за допомогою якого було б просто уявити задачу кластеризації як задачу оптимізації.
У випадку kMeans поширений такий критерій - сума квадратів відстаней від точок до центроїдів кластерів, до яких вони відносяться.
тут C – безліч кластерів потужності K, μk – центроїд кластера Ck.
Саме собою вирішення завдання K-means NP-трудное (NP-hard), й у розмірності d, числа кластерів k і числа точок n вирішується за . Для вирішення такого болю часто використовуються евристики, наприклад MiniBatch K-means, який для навчання використовує не весь датасет цілком, а лише маленькі його порції (batch) і оновлює центроїди використовуючи середнє за всю історію оновлень центроїду від усіх точок, що до нього відносяться.
Алгоритм та блок-схема
Алгоритм К-середніх, напевно, найпопулярніший і найпростіший алгоритм кластеризації і дуже легко представляється у вигляді простого псевдокоду:
- Вибрати кількість кластерів k, яка нам здається оптимальною для наших даних.
- Висипати випадковим чином простір наших даних k точок (центроїдів).
- Для кожної точки нашого набору даних порахувати, до якого центроїду вона ближча.
- Перемістити кожен центроїд до центру вибірки, яку ми віднесли до цього центроїду.
- Повторювати останні два кроки фіксоване число разів, або до тих пір, поки центроїди не "зійдуть". Коли різниця значень центроїдів класів з попереднім значенням буде меншою за задану величину K
Блок-схема алгоритму
Приклад реалізованої функції кластеризації k-means. Вхідні параметри – число класів k = 3, число ітерацій i = 6