70K Method

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

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

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

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

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

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

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

Алгоритм

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

Реализация

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

Сам класс K_means:

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

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

70K Method

Feed The topics in Internet Marketing that you should be reading right now

New Threads with the newest replies

Top Threads voted as the best by the Warrior Forum Community

Exclusive products and services available only at Warrior Forum

Get great deals on Internet Marketing Products, Services, Trainings and other Offers at the world’s largest Internet marketing marketplace

Метод k-средних

Продолжаем описывать популярные алгоритмы из data mining, сегодня остановимся на методе к-средних (k-means).

Метод к-средних создает к-групп из набора объектов таким образом, чтобы члены группы были наиболее однородными. Это популярная техника кластерного анализа для исследования набора данных.

А что такое кластерный анализ? Кластерный анализ – это семейство алгоритмов, разработанных для формирования групп таким образом, чтобы члены группы были наиболее похожими друг на друга и не похожими на элементы, не выходящие в группу. Кластер и группа – это синонимы в мире кластерного анализа.

Есть какой-нибудь пример? Определенно. Предположим, что у нас есть данные о пациентах. В кластерном анализе это называется наблюдениями. Мы кое-что знаем о каждом пациенте, например, его возраст, пульс, кровяное давление, максимальное потребление кислорода, холестерин и так далее. Это вектор, представляющий пациента.

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

Может возникнуть вопрос:

Как нам сгруппировать вместе пациентов по возрасту, пульсу, давлению с помощью этих векторов?
Хотите узнать хорошую новость?

Вы говорите методу к-средних, сколько кластеров вам нужно, а он сделает все остальное.

Как это происходит? Метод к-средних имеет множество вариантов работы для различных типов данных.

В общем случае все они делают примерно следующее:

1. Метод к-средних выбирает точки многомерного пространства, которые будут представлять к-кластеры. Эти точки называются центрами тяжести.
2. Каждый пациент будет располагаться наиболее близко к одной из точек. Надеемся, что не все они будут стремиться к одному центру тяжести, поэтому образуется несколько кластеров.
3. Теперь у нас есть к-кластеров, и каждый пациент – это член какого-то из них.
4. Метод к-средних, учитывая положение членов кластера, находит центр каждого из к-кластеров (именно здесь используются векторы пациентов!).
5. Вычисленный центр становится новым центром тяжести кластера.
6. Поскольку центр тяжести переместился, пациенты могли оказаться ближе к другим центрам тяжести. Другими словами, они могли сменить членство.
7. Шаги 2-6 повторяются до тех пор, пока центр тяжести не перестанут изменяться и членство не стабилизируется. Это называется сходимостью.

Требует ли этот метод обучения или он самообучающийся? Бывает по-разному. Но большинство расценивает метод к-средних как самообучающийся. Вместо того, чтобы уточнять количество кластеров, метод к-средних «изучает» кластеры самостоятельно, не требуя информации о том, к какому кластеру относятся данные наблюдения. Метод к-средних может быть полуобучаемым.

Почему стоит использовать метод к-средних? Не думаю, что многие возьмутся спорить:

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

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

Но не все так гладко:

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

Где он используется? Огромное количество реализаций метода к-средних доступны онлайн: