Кластеризация не является сложной концепцией для понимания. По сути, когда вы группируете группу объектов, вы делите их на набор подгрупп, в которых члены каждой подгруппы близки друг к другу в соответствии с некоторой мерой.
Одним из самых простых способов кластеризации является алгоритм кластеризации K-средних.
Представьте, что у вас есть набор точек, и вы хотите сгруппировать их в K=2 группы.
Первое, что вам нужно сделать, это выбрать случайным образом K=2 точки. Эти две точки будут служить начальными центроидами для двух кластеров. Подробнее о центроидах позже. Давайте представим наши два кластера зеленым треугольником и желтыми ромбами. Предположим, мы выбираем следующие две точки в качестве начальных центроидов наших кластеров.
Затем мы проходим по каждой точке и назначаем каждую кластеру центроида, к которому она ближе всего.
Как мы видим, каждая точка теперь принадлежит кластеру. Следующее, что мы делаем, это вычисляем центр тяжести каждого кластера. (Вот почему он называется алгоритмом K-средних.) Давайте пометим последующие центроиды кластера метками x.
Как и прежде, мы проходим по каждой точке и назначаем каждую кластеру, к центроиду которого она ближе всего.
Здесь мы видим, что один из зеленых треугольников становится желтым ромбом, поскольку он ближе к центроиду желтых ромбов, чем к центру зеленых треугольников.
Затем мы повторяем процесс
- вычисление центроида каждого кластера и
- присвоение каждой точки кластеру, к центроиду которого она ближе всего,
пока не будет выполнено условие остановки. Мы могли бы проверить, не изменяет ли ни одна точка кластер в следующей итерации или средняя межкластерная ошибка изменяется очень незначительно.
В двух словах, это алгоритм кластеризации K-средних.
Если мы продолжим наш пример и вычислим следующие центроиды,
Проходя по каждой точке и назначая кластеры,
Опять же, зеленый треугольник превращается в желтый ромб. Теперь, вычисляя центроиды,
Мы видим, что ни одна точка не переносит кластер в этой итерации. Таким образом, мы останавливаем алгоритм кластеризации K-средних и считаем полученные кластеры окончательными.
Сжатие изображения
Интересным применением алгоритма кластеризации K-средних является сжатие изображений. Предположим, у вас есть немного слишком большое изображение, и вы хотите уменьшить размер его файла. Как вы можете это сделать?
Один из способов сделать это — уменьшить набор цветов в изображении. Цвет пикселя обычно хранится в виде кортежа из 3 целых чисел — RGB — который описывает относительные уровни красного, зеленого и синего пикселя. Уровни могут быть от 0 до 255.
Поскольку каждый пиксель хранит 3 целых числа для описания цвета, в одном изображении может быть большой набор цветов. Теоретически для пикселя существует 16 777 216 возможных цветовых вариантов. Таким образом, очень красочное изображение содержит массу данных.
Применяя алгоритм K Means Clustering к цветовому пространству RGB изображения, мы можем уменьшить его размер, выбрав набор из K репрезентативных цветов (также известных как центроиды) для описания цветового пространства всего изображения. В частности, мы заменяем цвет каждого пикселя центроидом, к которому он ближе всего. Уменьшая набор цветов до K, мы, по сути, вносим ошибку в наше сжатие, и поэтому сжатие цветов не является типом сжатия без потерь.
В качестве примера мы можем применить алгоритм кластеризации K-средних к следующему изображению Копенгагена:
Если мы выберем 10 цветов,
или 40 цветов,
Чем больше K мы выбираем, тем ближе цвета нашего сжатого изображения к цветам исходного изображения. С другой стороны, чем меньше K, тем меньше размер файла изображения. Для K=5 размер изображения составляет 679 КБ, а для K=40 — 2,1 МБ. Итак, мы видим, что существует компромисс между точностью цветопередачи и размером файла.
В заключении
Алгоритм кластеризации K-средних — до смешного простой, но мощный инструмент машинного обучения, который нашел отличное применение во множестве областей. Как мы видели в нашем примере, кластеризацию можно использовать для сокращения цветового пространства изображения до набора K цветов.
Я использовал алгоритм кластеризации K-средних в своем анализе цвета Ла-Ла Ленд, чтобы уменьшить цветовое пространство каждого кадра фильма до набора из 50 цветов. Посмотрите мой пост в блоге!
Первоначально опубликовано на datameetsmedia.com
