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

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

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

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-оценки.

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

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

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

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

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

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

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