Лабораторна робота 3 - Кластеризація даних

27 вересня 2019 р. 16:20

Тема: кластеризація, розбиття об'єктів на класи у системах розпізнавання образів "без вчителя"

Завдання:

  1. Розробити алгоритм кластеризації масиву об'єктів на N кількість класів.
  2. Написати програму мовою Python розробленого алгоритму.
  3. Порівняти ефективність кластеризації з різних заходів розрахунку приналежності до класу.

Додаткове завдання:

  1. Замінити двовимірні масиви даних на тривимірні масиви. Побудувати 3Д модель.
  2. Розрахувати оптимальну кількість кластерів для рандомного масиву.
  3. Побудувати другий алгоритм кластеризації

Теорія

На відміну від завдання класифікації або регресії, у разі кластеризації складніше вибрати критерій, за допомогою якого було б просто уявити задачу кластеризації як задачу оптимізації.

У випадку kMeans поширений такий критерій - сума квадратів відстаней від точок до центроїдів кластерів, до яких вони відносяться.

тут C – безліч кластерів потужності K, μk – центроїд кластера Ck.

Саме собою вирішення завдання K-means NP-трудное (NP-hard), й у розмірності d, числа кластерів k і числа точок n вирішується за .  Для вирішення такого болю часто використовуються евристики, наприклад MiniBatch K-means, який для навчання використовує не весь датасет цілком, а лише маленькі його порції (batch) і оновлює центроїди використовуючи середнє за всю історію оновлень центроїду від усіх точок, що до нього відносяться.

Алгоритм та блок-схема

Алгоритм К-середніх, напевно, найпопулярніший і найпростіший алгоритм кластеризації і дуже легко представляється у вигляді простого псевдокоду:

  1. Вибрати кількість кластерів k, яка нам здається оптимальною для наших даних.
  2. Висипати випадковим чином простір наших даних k точок (центроїдів).
  3. Для кожної точки нашого набору даних порахувати, до якого центроїду вона ближча.
  4. Перемістити кожен центроїд до центру вибірки, яку ми віднесли до цього центроїду.
  5. Повторювати останні два кроки фіксоване число разів, або до тих пір, поки центроїди не "зійдуть". Коли різниця значень центроїдів класів з попереднім значенням буде меншою за задану величину K

Блок-схема алгоритму

Приклад реалізованої функції кластеризації k-means. Вхідні параметри – число класів k = 3, число ітерацій i = 6