Лабораторная работа 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