Кластеризация множества объектов, алгоритм K-means++

Приветствую, друзья. Квалифицирую себя как джуна на языке GO, с анализом данных еще не сталкивался, поэтому после изучения вопроса, решил что выйдет классная статья из полученного опыта. Плюс разложу материал для себя по полочкам. Статья будет описываться поэтапно, т.к считаю это самым удобным восприятием алгоритмов.

Поступила задача выполнения кластеризации множества товаров, по их размерам. Значения распределения: ширина и высота.

После изучения вопроса, было найдено несколько подходящих алгоритмов, одним из самых распространенных оказался алгоритм под названием K-means, а так же его вариация K-means++.

Историческая сводка

Краткая история базового алгоритма, взятая из википедии: наиболее популярный метод кластеризации. Был изобретён в 1950-х годах математиком Гуго Штейнгаузом и почти одновременно Стюартом Ллойдом. Особую популярность приобрёл после работы Маккуина.

Далеко ходите не будем, оставлю здесь же: k-means++ — улучшенная версия алгоритма кластеризации k-means. Суть улучшения заключается в нахождении более «хороших» начальных значений центроидов кластеров. Оригинальный k-means не регламентирует то, как выполняется этот этап алгоритма, и поэтому является нестабильным.

Обозначения на рисунках

Точки — входные данные, имеющие какие-либо значения по координатным осям
x и y;

Крестики — формирующие центроиды кластеров;

Стрелка — вектор (отрезок, характеризующийся направлением и величиной);

K-means classic

Давайте начнем с классики, а позже перейдем к плюсам.

Этап 1. Итак, алгоритм нахождения кластеров, основан на дополнительных точках опоры, случайно распределенных на двумерной плоскости. В будущем, эти точки, станут центроидами наших кластеров. Необходимо рандомно сгенерировать константное количество центроид.

Проще: Инициализируйте необходиоме количество центроид, с рандомными значениями по оси X и Y. Предлагаю структуру Dot{X float; Y: float}.

Этап 2. Под каждую раставленную центроиду, вычисляем расстояния до входных точек, в данном случае, применима формула расстояния:

Этап 3. Теперь нам необходимо переместить центроиду ближе к входным точкам, а именно, центру их области. Вычисление новых координат центроиды, происходит по формуле

где складываемые значения x и y — это координаты точек на плоскости, а n — их количество.

Этап 4. Ключевой moment алгоритма! Далее, нам необходимо вычислить WCSS (within-cluster sum of squares) — кластерный показатель, представляющий сумму квадратов внутрикластерных растояний.

где i — номер кластера, k — их количество, C — множество кластеров, x — точки входящие в кластер выбранного центроида. (breakpoint)

Результаты вычислений отдельно сохраняем для каждого центроида.

Этап 5. Ooops! К сожалению, все предыдущие этапы, кроме первого, были для простоты объяснения обернуты в цикл ?. Здесь мы обязаны сверить на полную идентичность, новые показатели WCSS со старыми. Перепрыгиваем к этапу 2 и вычисляем все заново, пока условие не станет истинным. Как только это произошло, алгоритм считается выполненым и мы можем выводить данные пользователю.

В данном случае я нарисовал тестовые данные и центроиды, а теперь предлагаю визуализировать в анимации процесс выполнения K-means на рабочих данных.

K-means++

У алгоритмов отличается только этап number 1 (yore almost here?). Доработка классического алгоритма производилась из-за нестабильности выборки начальных отправных точек.

Опишем ход действий алгоритма:

Этап 1.1. Выбираем из всех точек на плоскости, случайный первый центроид;

Этап 1.2. Находим квадрат расстояния от каждой точки на плоскости до выбранного центроида. Параллельно считаем их общую сумму;

Этап 1.3. Далее случайно указываем на число из интервала [0; random(0.0, 1.0) * sum];

Этап 1.4. Начинаем снова подсчитывать сумму квадратов расстояний (этапа 1.2) точек, пока сумма не превысит границу выбранного интервала. Берем точку, на которой подсчет был приостановлен;

Этап 1.5. Повтор шагов 2-4, пока не будут найдены все центроиды.

Далее выполняется основной алгоритм K-means.

func SelectFirstCentroids(dots []Size, countCentroids int) []Size { var kDots []Size dotsCount := len(dots)  kDots = append(kDots, dots[RandInt(0, dotsCount)])  for len(kDots) < countCentroids { var sumAllDistance float64 minDistancesForDots := make([]float64, dotsCount)  for d := range dots { minDistance := FindMinDistance(dots[d], kDots) minDistancesForDots[d] = minDistance sumAllDistance += sumAllDistance }  var sumCenter float64 rnd := rand.Float64() * sumAllDistance for dot, distance := range minDistancesForDots { sumCenter += distance if sumCenter > rnd { kDots = append(kDots, dots[dot]) break } } } return kDots }

Определение оптимального количества кластеров

Вы могли заметить, что алгоритм ожидает передачи входного значения K (количества кластеров), необходим оптимальный подбор этого значения, для качества результирующих данных. Давайте автоматизируем этот процесс, с помощью метода визуализации, под название “плечо”.

Этап 1. Задаем константу K, определяющую интервал [1; K];

Этап 2. Для каждого значения в интервале, высчитываем сумму квадратов расстояния до его центроиды;

Этап 3. Выводим полученные значения на плоскость, где значение K — лежит на оси X, а полученную сумму — кладем на ось Y.

Z-score

В ходе работы над алгоритмом, были обнаружены дикие выбросы. Для того чтобы избавиться от них, был найден алгоритм Z-оценки.

Из википедии

Стандартизированная оценка (z-оценка, англ. : Standard score, z-score) — это мера относительного разброса наблюдаемого или измеренного значения, которая показывает, сколько стандартных отклонений составляет его разброс относительного среднего значения. Это безразмерный статистический показатель, используемый для сравнения значений разной размерности или шкалой измерений.

Итак, необходимо найти стандартное отклонение для всей выборки данных, для этого опишем следующий алгоритм:

Этап 1. Найдем дистанции от каждой точки выборки до средней точки, лежащей в основе выборки, в моем случае я просто проставляю нули для обеихз. 

Этап 2. Найдем среднее значение выбранных дистанций. 

Этап 3. Найдем дисперсию по формуле

Этап 4. Теперь стандартное отклонение

Этап 5. Проходим циклом по каждой точке и вычисляем для нее Z-оценку, которую применим для очистки данных.

В итоге мы получаем значение, которое выражает критерий отклонения точки от основного скополения точек. Терпимые значения данного отклонения необходимо определять самим, я задал [-4; 4]. Например 0, будет представлять среднее значение выборки.