Что такое k means
Перейти к содержимому

Что такое k means

  • автор:

Кластеризация: алгоритмы k-means и c-means

Как и обещал, продолжаю серию публикаций о технологии Data Mining. Сегодня хочу рассказать о двух алгоритмах кластеризации (k-means и c-means), описать преимущества и недостатки, дать некоторые рекомендации по их использованию. Итак, поехали…

Кластеризация — это разделение множества входных векторов на группы (кластеры) по степени «схожести» друг на друга.

Кластеризация в Data Mining приобретает ценность тогда, когда она выступает одним из этапов анализа данных, построения законченного аналитического решения. Аналитику часто легче выделить группы схожих объектов, изучить их особенности и построить для каждой группы отдельную модель, чем создавать одну общую модель для всех данных. Таким приемом постоянно пользуются в маркетинге, выделяя группы клиентов, покупателей, товаров и разрабатывая для каждой из них отдельную стратегию (Википедия).

Меры расстояний

Для того, чтобы сравнивать два объекта, необходимо иметь критерий, на основании которого будет происходить сравнение. Как правило, таким критерием является расстояние между объектами.

Есть множество мер расстояния, рассмотрим несколько из них:

Евклидово расстояние — наиболее распространенное расстояние. Оно является геометрическим расстоянием в многомерном пространстве.

Квадрат евклидова расстояния. Иногда может возникнуть желание возвести в квадрат стандартное евклидово расстояние, чтобы придать большие веса более отдаленным друг от друга объектам.

Расстояние городских кварталов (манхэттенское расстояние). Это расстояние является просто средним разностей по координатам. В большинстве случаев эта мера расстояния приводит к таким же результатам, как и для обычного расстояния Евклида. Однако отметим, что для этой меры влияние отдельных больших разностей (выбросов) уменьшается (так как они не возводятся в квадрат).

Расстояние Чебышева. Это расстояние может оказаться полезным, когда желают определить два объекта как «различные», если они различаются по какой-либо одной координате (каким-либо одним измерением).

Степенное расстояние. Иногда желают прогрессивно увеличить или уменьшить вес, относящийся к размерности, для которой соответствующие объекты сильно отличаются. Это может быть достигнуто с использованием степенного расстояния.

Выбор расстояния (критерия схожести) лежит полностью на исследователе. При выборе различных мер результаты кластеризации могут существенно отличаться.

Алгоритм k-means (k-средних)

Наиболее простой, но в то же время достаточно неточный метод кластеризации в классической реализации. Он разбивает множество элементов векторного пространства на заранее известное число кластеров k. Действие алгоритма таково, что он стремится минимизировать среднеквадратичное отклонение на точках каждого кластера. Основная идея заключается в том, что на каждой итерации перевычисляется центр масс для каждого кластера, полученного на предыдущем шаге, затем векторы разбиваются на кластеры вновь в соответствии с тем, какой из новых центров оказался ближе по выбранной метрике. Алгоритм завершается, когда на какой-то итерации не происходит изменения кластеров.

Проблемы алгоритма k-means:
* необходимо заранее знать количество кластеров. Мной было предложено метод определения количества кластеров, который основывался на нахождении кластеров, распределенных по некоему закону (в моем случае все сводилось к нормальному закону). После этого выполнялся классический алгоритм k-means, который давал более точные результаты.
* алгоритм очень чувствителен к выбору начальных центров кластеров. Классический вариант подразумевает случайный выбор класторов, что очень часто являлось источником погрешности. Как вариант решения, необходимо проводить исследования объекта для более точного определения центров начальных кластеров. В моем случае на начальном этапе предлагается принимать в качестве центов самые отдаленные точки кластеров.
* не справляется с задачей, когда объект принадлежит к разным кластерам в равной степени или не принадлежит ни одному.

Нечеткий алгоритм кластеризации с-means

С последней проблемой k-means успешно справляется алгоритм с-means. Вместо однозначного ответа на вопрос к какому кластеру относится объект, он определяет вероятность того, что объект принадлежит к тому или иному кластеру. Таким образом, утверждение «объект А принадлежит к кластеру 1 с вероятностью 90%, к кластеру 2 — 10% » верно и более удобно.

Классический пример с-means — т.н. «бабочка» (butterfly):

image

Как видно, точка с координатами (3,2) в равной степени принадлежит как первому так и второму кластеру.

Остальные проблемы у с-means такие же, как у k-means, но они нивелируются благодаря нечеткости разбиения.

P.S. Я не описывал математические принципы алгоритмов, с ними легко можно ознакомиться по представленным ссылкам.

Кластеризация пространственных данных – k-means и иерархические алгоритмы

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

Для иллюстрации каждого алгоритма рассмотрим пример кластеризации пациентов, выделенных по одной болезни. Наша цель – определить, какой метод лучше подходит, чтобы кластеризовать точки и выделить места скопления заболевших.

Что есть в этой статье:

  • Пара слов о кластеризации
  • Разделительные алгоритмы и их типы
  • Алгоритм кластеризации k-means
  • Работа с k-means с примерами кода на Python
  • Иерархические алгоритмы и их типы
  • Агломеративная кластеризация с примерами кода на Python

Пара слов о кластеризации

Кластеризация — это задача группировки данных таким образом, чтобы данные в одной группе (называемой кластером) были более похожи друг на друга, чем данные из других кластеров.

Алгоритмы кластеризации и заданные входные параметры отвечают за то, как именно данные будут разбиты на кластеры, а значит и за правильность кластеризации.

Три основных типа алгоритмов кластеризации:
  • разделительные – основаны на поэтапном улучшении разбиения исходного набора данных;
  • иерархические – создают иерархию вложенных разбиений;
  • алгоритмы на основе плотности – разбивают объекты на кластеры на основе оценки плотности распределения.

Поговорим подробнее о разделительных и иерархических алгоритмах.

Разделительные алгоритмы и их типы

Разделительные алгоритмы (partition clustering) делят объекты данных на непересекающиеся группы. Ни один объект не может находится в более чем одном кластере, и в каждом кластере должен быть хотя бы один объект.

Разделительные алгоритмы чаще всего используются при работе с большими наборами данных, так как они основаны на несложных вычислениях.

Примеры разделительных алгоритмов:
  • K-means (ниже рассмотрим, как он работает)
  • CLARANS (кластеризация больших приложений на основе рандомизированного поиска)
Где используются разделительные алгоритмы:

В рекомендательных системах, для кластеризации пользователей по группам интересов.

Алгоритм кластеризации k-means

K-means (или метод k-средних) – один из наиболее популярных методов кластеризации. Он не сильно подходит для пространственных данных, но является простым и важным для понимания.

Например, если данных очень много, использовать другие алгоритмы будет затруднительно, и даже в случае геоданных удобнее применить k-means.

Основная идея метода — итеративное повторение двух шагов:
  • распределение объектов выборки по кластерам;
  • пересчет центров кластеров.
Шаги работы алгоритма кластеризации K-means
  1. В начале работы алгоритма выбираются K случайных центров.
  2. Каждый объект выборки относят к тому кластеру, к центру которого объект оказался ближе.
  3. Далее центры кластеров подсчитывают как среднее арифметическое векторов признаков всех вошедших в этот кластер объектов (то есть центр масс кластера). Центры кластеров обновляются.
  4. Объекты заново перераспределяются по кластерам, а затем можно снова уточнить положение центров.
  5. Процесс продолжается до тех пор, пока центры кластеров не перестанут меняться.

Преимущества алгоритма K-means
  1. Алгоритм k-средних хорошо справляется с задачей кластеризации в случае, когда кластеры линейно разделимы и представляют собой отдельные скопления точек.
  2. Быстрая работа алгоритма.
Недостатки алгоритма K-means
  1. Не гарантируется достижение глобального минимума суммарного квадратичного отклонения V, а только одного из локальных минимумов.
  2. Результат зависит от выбора исходных центров кластеров, их оптимальный выбор неизвестен.
  3. Число кластеров надо знать заранее.

Реализация k-means на примере

Все расчеты проводились в Python с библиотекой sk-learn.

На вход алгоритму k-means необходимо задать гиперпараметр – количество кластеров, на которое будут разбиты данные. Первым шагом необходимо определить это значение. Для этого итерационно запускаем алгоритм с количеством кластеров от 1 до 100 и при этом оптимизируем четыре основные метрики кластеризации (о метриках качества поговорим в следующих статьях).

На выходе функции получаем датасет с количеством кластеров и значением метрик кластеризации. Берем пять первых значений.

В результате мы получили, что оптимальным количеством будет 10, 40, 55, 45, 30 кластеров.

Далее переходим к запуску алгоритма.
Для каждого алгоритма кластеризации были написаны функции:

  • Функция, которая принимает на вход данные и список с наилучшим количеством кластеров.
  • В ходе работы функции ко всем точкам из датасета добавляется поле с номером кластера, к которому они были отнесены.
  • Для более понятной визуализации точки с одинаковым значением кластера объединяются в альфа-форму – полигон, который объединяет самые выпуклые точки. Подсчитывается количество точек в каждой альфе-форме. Файлы с альфа-формами сохраняются в формате geojson.

Давайте посмотрим, какие кластеры у нас получились. На выходе получаем столько видов кластеризации, сколько различных гиперапараметров было задано – в нашем случае получили 5 вариаций.

На картах цветовая шкала кластеров зависит от количества точек. Поверх отображены сами точки.

Результат – с k-means точки довольно четко группируются на кластеры. Заметно, что при 10 кластерах в одном кластере может быть до двух-трех скоплений точек, что в нашем случае не является правильным. При 20 кластерах таких случаев меньше, и кластеры довольно четко разделены.

Если мы берем еще меньшее деление, видно, что некоторые скопления делятся на два и более частей, что неправильно для нашей задачи. Поэтому лучший вариант, основанный на визуальной составляющей – это 20 кластеров.

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

Иерархические алгоритмы кластеризации

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

Типы иерархических алгоритмов кластеризации:
  • Агломеративные (от меньшего к большему) – одиночные объекты постепенно объединяются в кластер.
  • Разделительная кластеризация (от большего к меньшему): все данные собираются в один кластер и далее происходит деление на два, четыре и так далее кластеров.

Источник: https://quantdare.com/hierarchical-clustering/

Принцип работы алгоритма

Для работы этих алгоритмов определяется матрица близости, которая содержит попарные расстояния между всеми объектами. На основании нее происходит объединение или разделение объектов.

Когда в одном кластере более одного объекта, берется среднее расстояние.
После каждой итерации заново рассчитывается матрица близости.

Условия окончания работы алгоритма

Для завершения работы алгоритма можно выбрать одно из условий:

  1. Получено нужное количество кластеров.
  2. Достигнуто определенное условие, связанное с расстоянием между кластерами – например, если оно сильно изменилось с прошлой итерации.
  3. Анализ по дендрограмме. На практике обычно кластеризацию проводят вплоть до одного кластера, включающего в себя всю выборку, а затем анализируют получившуюся иерархическую структуру с помощью дендрограммы.

Пример агломеративной кластеризации

Проведем агломеративную кластеризацию, используя в качестве точки остановки заданное количество кластеров.

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

Оптимальное количество кластеров: 40, 25, 45, 20 и 35.

Следующий шаг – написать функцию, которая производит кластеризацию с нужными гиперпараметрами.

Как и в k-means, на вход этой функции подается датасет с точками. Далее производится кластеризация. В итоге мы получаем альфа-формы и датасет с точками, которые имеет значение кластеров.

Посмотрим на кластеры, которые у нас получились.

В случае алгомеративной кластеризации наиболее оптимальным числом кластеров мне показалось 30. В этом случае четче всего выделяются скопления точек. Однако, как и в алгоритме k-means, мы видим, что кластеры объединяют даже те точки, которые можно было считать выбросами.

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

K-means и иерархическая кластеризация отлично справляются с задачей кластеризации компактных и хорошо разделенных кластеров.

В следующем тексте этой серии рассмотрим плотностные алгоритмы, наиболее подходящие для кластеризации пространственных данных. И если вы хотите узнать больше, мы всегда готовы научить вас работе с геоданными в Python и QGIS.

Материал подготовила Анна Пикулева

А еще у нас есть рассылка с лучшими статьями и новостями мира геотехнологий. Собираем все лучшее и отправляем в письме раз в две недели ⭐

Реализация алгоритма k-means (k-средних) на примере работы с пикселями

Всем привет! Недавно нужно было написать код для реализации сегментации изображения с помощью метода k – средних (англ. k-means). Ну, первым делом Google в помощь. Нашел много информации, как и с математической точки зрения (всякие там сложные математические каракули, хрен поймёшь, что там написано), так и некоторые программные реализации, которые есть в английском интернете. Эти коды конечно прекрасны – спору нет, но саму суть идеи сложно поймать. Как – то оно там все сложно, запутано, да и пока сам, ручками, не пропишешь код, ничего не поймешь. В этой статье хочу показать простую, не производительную, но, надеюсь, понятную реализацию этого чудесного алгоритма. Ладно, погнали!

Итак, что такое кластеризация с точки зрения нашего восприятия? Приведу пример, допустим, есть милое изображение с цветочками с дачи твоей бабушки.

Вопрос следующий: определить, сколько на данном фото участков, залитых приблизительно одним цветом. Ну это совсем не сложно: белые лепестки – раз, желтые центры – два (я не биолог, как они именуются, не знаю), зелень – три. Эти участки и называются кластерами. Кластер -объединение данных, имеющих общие признаки (цвет, положение и т.д.). Процесс определения и помещения каждой составляющей каких-либо данных в такие кластеры — участки и называется кластеризацией.

Есть много алгоритмов кластеризации, но самый простой из них — k – средних, о котором дальше и пойдет речь. K-средних – простой и эффективный алгоритм, который легко реализовать программным методом. Данные, которые мы будем распределять по кластерам — пиксели. Как известно, цветной пиксель имеет три составляющих — red, green и blue. Наложение этих составляющих и создает палитру существующих цветов.

В памяти компьютера каждая составляющая цвета характеризуется числом от 0 до 255. То есть комбинируя различные значения красного, зеленого и синего, получаем палитру цветов на экране.

На примере пикселей мы и реализуем наш алгоритм. K-средних – итерационный алгоритм, то есть он даст правильный результат, после энного количества повторов некоторых математических вычислений.

Алгоритм

  1. Нужно наперед знать в сколько кластеров нужно распределить данные. Это является существенным минусом данного метода, но эта проблема решается улучшенными реализациями алгоритма, но это, как говорят, совсем другая история.
  2. Нужно выбрать начальные центры наших кластеров. Как? Да наугад. Зачем? Чтобы можно было привязывать каждый пиксель к центру кластера. Центр – это как Король, вокруг которого собираются его подданные — пиксели. Именно «расстояние» от центра до пикселя определяет, кому будет подчиняться каждый пиксель.
  3. Посчитаем расстояние от каждого центра до каждого пикселя. Это расстояние считается как евклидово расстояние между точками в пространстве, а в нашем случае — как расстояние между тремя составляющими цвета: Считаем расстояние от первого пикселя до каждого центра и определяем наименьшее расстояние между этим пикселем и центрами. Для центра расстояние, до которого является наименьшим, пересчитываем координаты, как среднее арифметическое между каждой составляющей пикселя – короля и пикселя — подданного. Наш центр смещается в пространстве соответственно подсчетам.
  4. После пересчета всех центров, мы распределяем пиксели по кластерам, сравнивая расстояние от каждого пикселя до центров. Пиксель помещается в кластер, к центру которого он расположен ближе, чем к остальным центрам.
  5. Все начинается сначала, до тех пор, пока пиксели остаются в одних и тех же кластерах. Часто такого может и не случится, так как при большом количестве данных центры будут перемещаться в малом радиусе, и пиксели по краям кластеров будут прыгать то в один, то в другой кластер. Для этого нужно определить максимальное число итераций.

Реализация

Реализовывать данный проект я буду на С++. Первый файл – «k_means.h», в нем я определил основные типы данных, константы, и основной класс для работы — «K_means».
Для характеристики каждого пикселя создадим структуру, которая состоит из трех составляющих пикселя, для которых я выбрал тип double для более точных расчетов, а также определил некоторые константы для работы программы:

const int KK = 10; //количество кластеров const int max_iterations = 100; //максимальное количество итераций typedef struct < double r; double g; double b; >rgb;

Сам класс K_means:

class K_means < private: std::vectorpixcel; int q_klaster; int k_pixcel; std::vector centr; void identify_centers(); inline double compute(rgb k1, rgb k2) < return sqrt(pow((k1.r - k2.r),2) + pow((k1.g - k2.g), 2) + pow((k1.b - k2.b), 2)); >inline double compute_s(double a, double b) < return (a + b) / 2; >; public: K_means() : q_klaster(0), k_pixcel(0) <>; K_means(int n, rgb *mas, int n_klaster); K_means(int n_klaster, std::istream & os); void clustering(std::ostream & os); void print()const; ~K_means(); friend std::ostream & operator<<(std::ostream & os, const K_means & k); >; 

Пробежимся по составляющим класса:

vectorpixcel — вектор для пикселей;
q_klaster – количество кластеров;
k_pixcel – количество пикселей;
vectorcentr – вектор для центров кластеризации, количество элементов в нем определяется q_klaster;
identify_centers() – метод для случайного выбора начальных центров среди входных пикселей;
compute() и compute_s() встроенные методы для расчета расстояния между пикселями и пересчета центров соответственно;
три конструктора: первый по умолчанию, второй — для инициализации пикселей из массива, третий — для инициализации пикселей из текстового файла (в моей реализации сначала файл случайно заполняется данными, и потом с этого файла считываются пиксели для работы программы, почему не напрямую в вектор – просто так нужно в моем случае);
clustering(std::ostream & os) – метод кластеризации;
метод и перегрузка оператора вывода для публикации результатов.

void K_means::identify_centers() < srand((unsigned)time(NULL)); rgb temp; rgb *mas = new rgb[q_klaster]; for (int i = 0; i < q_klaster; i++) < temp = pixcel[0 + rand() % k_pixcel]; for (int j = i; j < q_klaster; j++) < if (temp.r != mas[j].r && temp.g != mas[j].g && temp.b != mas[j].b) < mas[j] = temp; >else < i--; break; >> > for (int i = 0; i < q_klaster; i++) < centr.push_back(mas[i]); >delete []mas; > 

Это метод для выбора начальных центров кластеризации и добавления их в вектор центров. Осуществляется проверка на повтор центров и замена их в этих случаях.

K_means::K_means(int n, rgb * mas, int n_klaster) < for (int i = 0; i < n; i++) < pixcel.push_back(*(mas + i)); >q_klaster = n_klaster; k_pixcel = n; identify_centers(); > 

Реализация конструктора для инициализации пикселей из массива.

K_means::K_means(int n_klaster, std::istream & os) : q_klaster(n_klaster) < rgb temp; while (os >> temp.r && os >> temp.g && os >> temp.b) < pixcel.push_back(temp); >k_pixcel = pixcel.size(); identify_centers(); > 

В этот конструктор мы передаем объект ввода для возможности ввода данных как из файла, так и из консоли.

void K_means::clustering(std::ostream & os) < os check_1(k_pixcel, -1); std::vector check_2(k_pixcel, -2); int iter = 0; /*Количество итераций.*/ while(true) < os /*Определяем минимальное расстояние и в m_k фиксируем номер центра для дальнейшего пересчета.*/ double min_dist = *mas; int m_k = 0; for (int i = 0; i < q_klaster; i++) < if (min_dist >*(mas + i)) < min_dist = *(mas + i); m_k = i; >> os /*Классифицируем пиксели по кластерам.*/ int *mass = new int[k_pixcel]; os /*Определяем минимальное расстояние.*/ double min_dist = *mas; int m_k = 0; for (int i = 0; i < q_klaster; i++) < if (min_dist >*(mas + i)) < min_dist = *(mas + i); m_k = i; >> mass[k] = m_k; os /*Выводим информацию о принадлежности пикселей к кластерам и заполняем вектор для сравнения итераций.*/ os os > > delete[] mass; /*Выводим информацию о новых центрах.*/ os > /*Если наши векторы равны или количество итераций больше допустимого – прекращаем процесс.*/ iter++; if (check_1 == check_2 || iter >= max_iterations) < break; >check_2 = check_1; > os

Основной метод кластеризации.

std::ostream & operator <<(std::ostream & os, const K_means & k) < os << "Начальные пиксели: " << std::endl; for (int i = 0; i < k.k_pixcel; i++) < os << k.pixcel[i].r << " " << k.pixcel[i].g << " " << k.pixcel[i].b << " - №" << i << std::endl; >os os

Вывод начальных данных.

Пример вывода

Пример вывода

Начальные пиксели:
255 140 50 — №0
100 70 1 — №1
150 20 200 — №2
251 141 51 — №3
104 69 3 — №4
153 22 210 — №5
252 138 54 — №6
101 74 4 — №7

Случайные начальные центры кластеризации:
150 20 200 — #0
104 69 3 — #1
100 70 1 — #2

Количество кластеров: 3
Количество пикселей: 8

Расстояние от пикселя 0 к центру #0: 218.918
Расстояние от пикселя 0 к центру #1: 173.352
Расстояние от пикселя 0 к центру #2: 176.992
Минимальное расстояние к центру #1
Пересчитываем центр #1: 179.5 104.5 26.5
Расстояние от пикселя 1 к центру #0: 211.189
Расстояние от пикселя 1 к центру #1: 90.3369
Расстояние от пикселя 1 к центру #2: 0
Минимальное расстояние к центру #2
Пересчитываем центр #2: 100 70 1
Расстояние от пикселя 2 к центру #0: 0
Расстояние от пикселя 2 к центру #1: 195.225
Расстояние от пикселя 2 к центру #2: 211.189
Минимальное расстояние к центру #0
Пересчитываем центр #0: 150 20 200
Расстояние от пикселя 3 к центру #0: 216.894
Расстояние от пикселя 3 к центру #1: 83.933
Расстояние от пикселя 3 к центру #2: 174.19
Минимальное расстояние к центру #1
Пересчитываем центр #1: 215.25 122.75 38.75
Расстояние от пикселя 4 к центру #0: 208.149
Расстояние от пикселя 4 к центру #1: 128.622
Расстояние от пикселя 4 к центру #2: 4.58258
Минимальное расстояние к центру #2
Пересчитываем центр #2: 102 69.5 2
Расстояние от пикселя 5 к центру #0: 10.6301
Расстояние от пикселя 5 к центру #1: 208.212
Расстояние от пикселя 5 к центру #2: 219.366
Минимальное расстояние к центру #0
Пересчитываем центр #0: 151.5 21 205
Расстояние от пикселя 6 к центру #0: 215.848
Расстояние от пикселя 6 к центру #1: 42.6109
Расстояние от пикселя 6 к центру #2: 172.905
Минимальное расстояние к центру #1
Пересчитываем центр #1: 233.625 130.375 46.375
Расстояние от пикселя 7 к центру #0: 213.916
Расстояние от пикселя 7 к центру #1: 150.21
Расстояние от пикселя 7 к центру #2: 5.02494
Минимальное расстояние к центру #2
Пересчитываем центр #2: 101.5 71.75 3

Проведем классификацию пикселей:
Расстояние от пикселя №0 к центру #0: 221.129
Расстояние от пикселя №0 к центру #1: 23.7207
Расстояние от пикселя №0 к центру #2: 174.44
Пиксель №0 ближе всего к центру #1
Расстояние от пикселя №1 к центру #0: 216.031
Расстояние от пикселя №1 к центру #1: 153.492
Расстояние от пикселя №1 к центру #2: 3.05164
Пиксель №1 ближе всего к центру #2
Расстояние от пикселя №2 к центру #0: 5.31507
Расстояние от пикселя №2 к центру #1: 206.825
Расстояние от пикселя №2 к центру #2: 209.378
Пиксель №2 ближе всего к центру #0
Расстояние от пикселя №3 к центру #0: 219.126
Расстояние от пикселя №3 к центру #1: 20.8847
Расстояние от пикселя №3 к центру #2: 171.609
Пиксель №3 ближе всего к центру #1
Расстояние от пикселя №4 к центру #0: 212.989
Расстояние от пикселя №4 к центру #1: 149.836
Расстояние от пикселя №4 к центру #2: 3.71652
Пиксель №4 ближе всего к центру #2
Расстояние от пикселя №5 к центру #0: 5.31507
Расстояние от пикселя №5 к центру #1: 212.176
Расстояние от пикселя №5 к центру #2: 219.035
Пиксель №5 ближе всего к центру #0
Расстояние от пикселя №6 к центру #0: 215.848
Расстояние от пикселя №6 к центру #1: 21.3054
Расстояние от пикселя №6 к центру #2: 172.164
Пиксель №6 ближе всего к центру #1
Расстояние от пикселя №7 к центру #0: 213.916
Расстояние от пикселя №7 к центру #1: 150.21
Расстояние от пикселя №7 к центру #2: 2.51247
Пиксель №7 ближе всего к центру #2

Массив соответствия пикселей и центров:
1 2 0 1 2 0 1 2

Результат кластеризации:
Кластер #0
150 20 200
153 22 210
Кластер #1
255 140 50
251 141 51
252 138 54
Кластер #2
100 70 1
104 69 3
101 74 4
Новые центры:
151.5 21 205 — #0
233.625 130.375 46.375 — #1
101.5 71.75 3 — #2

Расстояние от пикселя 0 к центру #0: 221.129
Расстояние от пикселя 0 к центру #1: 23.7207
Расстояние от пикселя 0 к центру #2: 174.44
Минимальное расстояние к центру #1
Пересчитываем центр #1: 244.313 135.188 48.1875
Расстояние от пикселя 1 к центру #0: 216.031
Расстояние от пикселя 1 к центру #1: 165.234
Расстояние от пикселя 1 к центру #2: 3.05164
Минимальное расстояние к центру #2
Пересчитываем центр #2: 100.75 70.875 2
Расстояние от пикселя 2 к центру #0: 5.31507
Расстояние от пикселя 2 к центру #1: 212.627
Расстояние от пикселя 2 к центру #2: 210.28
Минимальное расстояние к центру #0
Пересчитываем центр #0: 150.75 20.5 202.5
Расстояние от пикселя 3 к центру #0: 217.997
Расстояние от пикселя 3 к центру #1: 9.29613
Расстояние от пикселя 3 к центру #2: 172.898
Минимальное расстояние к центру #1
Пересчитываем центр #1: 247.656 138.094 49.5938
Расстояние от пикселя 4 к центру #0: 210.566
Расстояние от пикселя 4 к центру #1: 166.078
Расстояние от пикселя 4 к центру #2: 3.88306
Минимальное расстояние к центру #2
Пересчитываем центр #2: 102.375 69.9375 2.5
Расстояние от пикселя 5 к центру #0: 7.97261
Расстояние от пикселя 5 к центру #1: 219.471
Расстояние от пикселя 5 к центру #2: 218.9
Минимальное расстояние к центру #0
Пересчитываем центр #0: 151.875 21.25 206.25
Расстояние от пикселя 6 к центру #0: 216.415
Расстояние от пикселя 6 к центру #1: 6.18805
Расстояние от пикселя 6 к центру #2: 172.257
Минимальное расстояние к центру #1
Пересчитываем центр #1: 249.828 138.047 51.7969
Расстояние от пикселя 7 к центру #0: 215.118
Расстояние от пикселя 7 к центру #1: 168.927
Расстояние от пикселя 7 к центру #2: 4.54363
Минимальное расстояние к центру #2
Пересчитываем центр #2: 101.688 71.9688 3.25

Проведем классификацию пикселей:
Расстояние от пикселя №0 к центру #0: 221.699
Расстояние от пикселя №0 к центру #1: 5.81307
Расстояние от пикселя №0 к центру #2: 174.122
Пиксель №0 ближе всего к центру #1
Расстояние от пикселя №1 к центру #0: 217.244
Расстояние от пикселя №1 к центру #1: 172.218
Расстояние от пикселя №1 к центру #2: 3.43309
Пиксель №1 ближе всего к центру #2
Расстояние от пикселя №2 к центру #0: 6.64384
Расстояние от пикселя №2 к центру #1: 214.161
Расстояние от пикселя №2 к центру #2: 209.154
Пиксель №2 ближе всего к центру #0
Расстояние от пикселя №3 к центру #0: 219.701
Расстояние от пикселя №3 к центру #1: 3.27555
Расстояние от пикселя №3 к центру #2: 171.288
Пиксель №3 ближе всего к центру #1
Расстояние от пикселя №4 к центру #0: 214.202
Расстояние от пикселя №4 к центру #1: 168.566
Расстояние от пикселя №4 к центру #2: 3.77142
Пиксель №4 ближе всего к центру #2
Расстояние от пикселя №5 к центру #0: 3.9863
Расстояние от пикселя №5 к центру #1: 218.794
Расстояние от пикселя №5 к центру #2: 218.805
Пиксель №5 ближе всего к центру #0
Расстояние от пикселя №6 к центру #0: 216.415
Расстояние от пикселя №6 к центру #1: 3.09403
Расстояние от пикселя №6 к центру #2: 171.842
Пиксель №6 ближе всего к центру #1
Расстояние от пикселя №7 к центру #0: 215.118
Расстояние от пикселя №7 к центру #1: 168.927
Расстояние от пикселя №7 к центру #2: 2.27181
Пиксель №7 ближе всего к центру #2

Массив соответствия пикселей и центров:
1 2 0 1 2 0 1 2

Результат кластеризации:
Кластер #0
150 20 200
153 22 210
Кластер #1
255 140 50
251 141 51
252 138 54
Кластер #2
100 70 1
104 69 3
101 74 4
Новые центры:
151.875 21.25 206.25 — #0
249.828 138.047 51.7969 — #1
101.688 71.9688 3.25 — #2

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

Интереснее случаи при рандомной генерации пикселей. Сгенерировав 50 точек, которые нужно поделить на 10 кластеров, я получил 5 итераций. Сгенерировав 50 точек, которые нужно поделить на 3 кластера, я получил все 100 максимально допустимых итераций. Можно заметить, что чем больше кластеров, тем легче программе найти наиболее схожие пиксели и объединить их в меньшие группы, и наоборот — если кластеров мало, а точек много, часто алгоритм завершается только от превышения максимально допустимого количества итераций, так как некоторые пиксели постоянно прыгают из одного кластера в другой. Тем не менее, основная масса все равно определяются в свои кластеры окончательно.

Ну а теперь давайте проверим результат кластеризации. Взяв результат некоторых кластеров из примера 50 точек на 10 кластеров, я вбил результат этих данных в Illustrator и вот что получилось:

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

Допустим, у нас есть такое фото. Остров мы можем определить, как один кластер, но при увеличении мы видим, что он состоит из разных оттенков зеленого.

А это 8 кластер, но в уменьшенном варианте, результат аналогичен:

Полную версию программы можно посмотреть на моем GitHub.

Метод k-средних (K-means)

Метод k-средних используется для кластеризации данных на основе алгоритма разбиения векторного пространства на заранее определенное число кластеров k . Алгоритм представляет собой итерационную процедуру, в которой выполняются следующие шаги:

  1. Выбирается число кластеров k .
  2. Из исходного множества данных случайным образом выбираются k наблюдений, которые будут служить начальными центрами кластеров.
  3. Для каждого наблюдения исходного множества определяется ближайший к нему центр кластера (расстояния измеряются в метрике Евклида). При этом записи, «притянутые» определенным центром, образуют начальные кластеры.
  4. Вычисляются центроиды — центры тяжести кластеров. Каждый центроид — это вектор, элементы которого представляют собой средние значения соответствующих признаков, вычисленные по всем записям кластера.
  5. Центр кластера смещается в его центроид, после чего центроид становится центром нового кластера.
  6. 3-й и 4-й шаги итеративно повторяются. Очевидно, что на каждой итерации происходит изменение границ кластеров и смещение их центров. В результате минимизируется расстояние между элементами внутри кластеров и увеличиваются междукластерные расстояния.

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

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

Существуют методы кластеризации, которые можно рассматривать как происходящие от k-средних. Например, в методе k-медиан (k-medians) для вычисления центроидов используется не среднее, а медиана, что делает алгоритм более устойчивым к аномальным значениям в данных.

Алгоритм g-средних (от gaussian) строит кластеры, распределение данных в которых стремится к нормальному (гауссовскому) и снимает неопределенность выбора начальных кластеров. Алгоритм C-средних использует элементы нечеткой логики, учитывая при вычислении центроидов не только расстояния, но и степень принадлежности наблюдения к множеству объектов в кластере. Также известен алгоритм Ллойда, который в качестве начального разбиения использует не множества векторов, а области векторного пространства.

Идея метода k-средних была одновременно сформулирована Гуго Штейнгаузом и Стюартом Ллойдом в 1957 г. Сам термин «k-средних» был впервые введен Дж. Маккуинном в 1967 г.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *