Метод К-средних (K-means), исходник на C++ (Builder)

Народ, не хочу никого пугать, но сейчас пост будет о кластеризации методом K-средних. Помогал знакомой с заданием из универа, родилась прога. Решил поделиться. Может вам никому и не надо, а кому-то где-то точно будет нужно (я сам пока гуглил, чуть пальцы не сломал; даже описание алгоритма еле нашел).

Внимание, рассказывает профан; все объяснения даются приближенные, «чтобы понять». За подробным описанием алгоритмов и точными определениями – в энциклопедию. Что такое кластеризация? Грубо говоря – это деление по группам некоторого количества объектов. Например, у нас в огромной куче смешались чебурашки, велосипеды и роботы-убийцы-детей. Если производить кластеризацию по признаку, то чебурашек мы отнесем в одну группу, велосипеды – в другу, а роботов-убийц-детей в третью (ту, что рядом с детским садиком у меня под окном). Признак, по которому мы относим один предмет в одну группу, а другой в другую называется метрикой. Грубо говоря, метрика – это просто способ отделить один предмет от другого, используя какие-то точные рассчеты. Самый простой вариант – это когда метрикой является расстояние.

Кластеризация (деление на кластеры) может быть и немного другой. Если в первом примере с 3 кучами вещей нам сказано разделить их на четыре кластера, то наверняка велосипеды попадут в кучу с чебурашками, а для каких-то детей не найдутся их роботы-убийцы.

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

В данном случае мы будем работать с точками на плоскости. Чтобы сразу можно было наглядно все представить, выложу скриншот программы на C++ Builder (скачать можно по ссылке в конце статьи).

Итак. Все точки, обозначенные… точками – это… точки… те, которые на плоскости. Во сказал. Кстати, почему-то точки тут немного похожи на маленькие ромбики – в общем, это они и есть. Квадратики – это центры кластеров. Линии от точек до центров нужны просто для наглядности, чтобы сразу видеть к какому центру принадлежит точка (их можно убрать, сняв галку «линии»). Хотя они и одного цвета, а центр обведен ченым и квадратный, я решил добавить линии.

Так вот. Хотя для многих студентов достаточно только программы, я расскажу как работает сам алгоритм кластеризации. Он интеративный. То есть он повторяется несколько раз, пока не «сойдется». Сходимость в данном случае значит, что с каждоый итерацией (повторением вычислений) мы все точнее приближаемся к правильному ответу. А «сошелся» в данном случае значит, что мы нашли правильный ответ или мы очень близко к нему (то есть нашлось число с небольшой погрешностью, на которую мы плюем и топчем ногами).

Дано. 50 точек, расположенных случайным образом на плоскости 20 на 20 (не важно даже каких единиц). Нужно распределить эти точки по кластерам алгоритмом К-средних (или K-means). Алгоритм действует так:

1) Сначала случайным образом выставляем на этой же плоскости k центров кластеров. Центр кластера называется центроидом. Просто рандомом, от балды, наплевательски, кое-какерски. Без начального положения центроидов не удастся запустить алгоритм (увидите почему). Как их расставить – дело ваше, можно самостоятельно вводить координаты, можно применить еще какой-нибудь алгоритм.

2) Начинается вычисление кластеров в цикле. Он простой как… куча дерьма.

2.1) Сначала мы «привязываем» каждую точку к тому центроиду, к которому она ближе. Т.к. центроид является центром кластера, то можно сказать, что мы относим каждую точку к тому кластеру, к центру которого она ближе.

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

2.3) Повторяем с шага 2.1 до тех пор, пока центроиды не перестанут менять своего положения. Если они перестали менять положение, значит алгоритм сошелся, мы крутые перцы и все надрали зад. Кстати, как правило алгоритм сходится где-то за 2-6 итераций. Но в теории возможно, что алгоритм не сойдется вообще, поэтому я на всякий случай включил в него «защиту» – сделал максимальное число итераций 30. Это гарантирует, что программа не зависнет.

Исходник потерян за давностью лет, простите. Хотя с точки зрения программирования – ничего сложного.

Постовые: обратные ссылки, реклама в Twitter

Отзывов (20) на «Метод К-средних (K-means), исходник на C++ (Builder)»

пишет:
23.06.2009 в 7:50 пп


класс!)) ниче не понял, но прикольно =))) совмещение профессионального и разговорного языка =))

---

пишет:
24.06.2009 в 7:56 пп


Забавно.))) продолжайте в том же духе!!!

---

пишет:
26.06.2009 в 11:55 дп


Почти поняла, мой брат этим занимается.

---

пишет:
28.06.2009 в 1:16 дп


Интересно. Хорошо объяснил. И вероятно автору надоел детский сад под окном
Вот только не понимаю зачем оно надо, как применить в жизни.
Ну вот про велосипеды и роботов_убийц_детей всё ясно. Каждый день сортирую )

---

пишет:
29.06.2009 в 3:38 пп


супер!!!!

---

пишет:
08.07.2009 в 11:44 дп


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

---

пишет:
15.09.2009 в 5:56 пп


Не загружается файлик… на главную сразу кидает… Жаль. Как раз такой метод задали делать…Хотела глянуть хоть что он из себя представляет.

---

пишет:
20.09.2009 в 7:23 дп



Ксю ты и тут уже побывала))))
ссылка не пашет, а ооооооочень нужно….

---

пишет:
11.12.2009 в 11:48 пп


респект)
очень живой стиль изложения. меня уже задрала сухая математика, а автор молодец) успехов!

---

пишет:
19.12.2009 в 1:04 дп


Я не знаю, что тебе сделала знакомая, чтоб ты это все наваял, но ты все равно молодец! Алгоритм, на самом деле, простейший, но его действительно хер найдешь. Благодарю за объяснение)

---

пишет:
19.12.2009 в 10:31 дп


Совсем ничего не сделала. А надо было просить, да? )))

---

пишет:
19.12.2009 в 11:42 дп


А исходников нет?=)

---

пишет:
24.12.2009 в 4:35 пп


Перезалейте пожалуйста исходник, очень нужен!

---

пишет:
04.01.2010 в 10:57 пп


Ссылка исходника не работает, если не сложно, то запиши ещё разок его, очень нужно

---

пишет:
11.03.2010 в 1:56 дп


Автору сенкс, всё понятно и без научной лабуды

---

пишет:
24.03.2010 в 6:58 пп


Дайте пожалуйста исходничек, очень-очень нужен.

---

пишет:
05.04.2010 в 9:34 пп


Люди,не вижу ссылку на исходник,если не трудно,у кого имеется в наличии выкиньте код,очччень надо

---

пишет:
19.04.2010 в 10:55 пп


Спасибо автору! =)
Блин, гуглил и яшил, что только не делал … везде срань какая-то, точнее вроде и понятно, но как-то по мелочи непонятно и в итоге, алгоритм не поддавался полному пониманию =)
А тут всё норм, просто, свободно и легко объясняется, так что мистер автор пиши статьи в том же духе =) полезны!
Респект и ещё раз спасибо!

---

пишет:
12.05.2010 в 10:40 дп


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

---

пишет:
30.08.2010 в 6:46 пп


2.2 – самый «приятный» пункт особенно в многомерном пространстве

---

Оставьте свой комментарий