Статья будет описываться поэтапно, т.к считаю это самым удобным способом для восприятия алгоритмов.
Поступила задача выполнения кластеризации множества товаров, по их размерам. Значения распределения: ширина и высота.
После изучения вопроса, было найдено несколько подходящих алгоритмов, одним из самых распространенных оказался алгоритм под названием 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. Под каждую расставленную центроиду, вычисляем расстояния до входных точек, в данном случае, применима формула расстояния:
Каждой центроиде, необходимо присвоить точки, с наименьшими значениями d (расстояния), найденными на предыдущем этапе, т.е проводим кластеризацию.
Этап 3. Теперь нам необходимо переместить центроиду ближе к входным точкам, а именно, центру их области. Вычисление новых координат центроиды, происходит по формуле
где складываемые значения x и y - это координаты точек на плоскости, а n - их количество.
Этап 4. Ключевой moment алгоритма! Далее, нам необходимо вычислить WCSS (within-cluster sum of squares) - кластерный показатель, представляющий сумму квадратов внутрикластерных расстояний.
где i - номер кластера, k - их количество, C - множество кластеров, x - точки входящие в кластер выбранного центроида. (breakpoint)
Результаты вычислений отдельно сохраняем для каждого центроида.
Этап 5. Ooops! К сожалению, все предыдущие этапы, кроме первого, были для простоты объяснения обернуты в цикл 😔. Здесь мы обязаны сверить на полную идентичность, новые показатели WCSS со старыми. Перепрыгиваем к этапу 2 и вычисляем все заново, пока условие не станет истинным. Как только это произошло, алгоритм считается выполненым и мы можем выводить данные пользователю.
P.S Это происходит за конечное число итераций, так как количество возможных разбиений конечного множества конечно, а на каждом шаге отклонение WCSS уменьшается, поэтому зацикливание невозможно.
В данном случае я нарисовал тестовые данные и центроиды, а теперь предлагаю визуализировать в анимации процесс выполнения 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, будет представлять среднее значение выборки.
Github с кодом: https://github.com/krasov-rf/kmeans
