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

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

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

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

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

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

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

Читать полностью »

Комментариев (14)