|
Народ, не хочу никого пугать, но сейчас пост будет о кластеризации методом K-средних. Помогал знакомой с заданием из универа, родилась прога. Решил поделиться. Может вам никому и не надо, а кому-то где-то точно будет нужно (я сам пока гуглил, чуть пальцы не сломал; даже описание алгоритма еле нашел).
Внимание, рассказывает профан; все объяснения даются приближенные, «чтобы понять». За подробным описанием алгоритмов и точными определениями – в энциклопедию. Что такое кластеризация? Грубо говоря – это деление по группам некоторого количества объектов. Например, у нас в огромной куче смешались чебурашки, велосипеды и роботы-убийцы-детей. Если производить кластеризацию по признаку, то чебурашек мы отнесем в одну группу, велосипеды – в другу, а роботов-убийц-детей в третью (ту, что рядом с детским садиком у меня под окном). Признак, по которому мы относим один предмет в одну группу, а другой в другую называется метрикой. Грубо говоря, метрика – это просто способ отделить один предмет от другого, используя какие-то точные рассчеты. Самый простой вариант – это когда метрикой является расстояние.
Кластеризация (деление на кластеры) может быть и немного другой. Если в первом примере с 3 кучами вещей нам сказано разделить их на четыре кластера, то наверняка велосипеды попадут в кучу с чебурашками, а для каких-то детей не найдутся их роботы-убийцы.
Есть метод, называется метод кластеризации К-средних, который позволяет «расфасовать» объекты как раз по второму принципу. То есть мы заранее задаем количество кластеров, а алгоритм сам разделяет объекты на это количетсво.
В данном случае мы будем работать с точками на плоскости. Чтобы сразу можно было наглядно все представить, выложу скриншот программы на C++ Builder (скачать можно по ссылке в конце статьи).
Итак. Все точки, обозначенные… точками – это… точки… те, которые на плоскости. Во сказал. Кстати, почему-то точки тут немного похожи на маленькие ромбики – в общем, это они и есть. Квадратики – это центры кластеров. Линии от точек до центров нужны просто для наглядности, чтобы сразу видеть к какому центру принадлежит точка (их можно убрать, сняв галку «линии»). Хотя они и одного цвета, а центр обведен ченым и квадратный, я решил добавить линии.
Так вот. Хотя для многих студентов достаточно только программы, я расскажу как работает сам алгоритм кластеризации. Он интеративный. То есть он повторяется несколько раз, пока не «сойдется». Сходимость в данном случае значит, что с каждоый итерацией (повторением вычислений) мы все точнее приближаемся к правильному ответу. А «сошелся» в данном случае значит, что мы нашли правильный ответ или мы очень близко к нему (то есть нашлось число с небольшой погрешностью, на которую мы плюем и топчем ногами).
Дано. 50 точек, расположенных случайным образом на плоскости 20 на 20 (не важно даже каких единиц). Нужно распределить эти точки по кластерам алгоритмом К-средних (или K-means). Алгоритм действует так:
1) Сначала случайным образом выставляем на этой же плоскости k центров кластеров. Центр кластера называется центроидом. Просто рандомом, от балды, наплевательски, кое-какерски. Без начального положения центроидов не удастся запустить алгоритм (увидите почему). Как их расставить – дело ваше, можно самостоятельно вводить координаты, можно применить еще какой-нибудь алгоритм.
2) Начинается вычисление кластеров в цикле. Он простой как… куча дерьма.
2.1) Сначала мы «привязываем» каждую точку к тому центроиду, к которому она ближе. Т.к. центроид является центром кластера, то можно сказать, что мы относим каждую точку к тому кластеру, к центру которого она ближе.
2.2) Когда все точки привязаны и ни одна от нас не убежала, нужно пересчитать координаты центроидов. Для этого мысленно вписываем весь кластер в прямоугольник и ставим центроид туда, где пересекутся его диагонали (в середину, короче). На скриншоте это очень хорошо видно. Обведите, например, синий кластер прямоугольником и вы увидите, что синий центроид стоит в его середине.
2.3) Повторяем с шага 2.1 до тех пор, пока центроиды не перестанут менять своего положения. Если они перестали менять положение, значит алгоритм сошелся, мы крутые перцы и все надрали зад. Кстати, как правило алгоритм сходится где-то за 2-6 итераций. Но в теории возможно, что алгоритм не сойдется вообще, поэтому я на всякий случай включил в него «защиту» – сделал максимальное число итераций 30. Это гарантирует, что программа не зависнет.
Исходник потерян за давностью лет, простите. Хотя с точки зрения программирования – ничего сложного.
Постовые: обратные ссылки, реклама в Twitter
Оставьте свой комментарий
|
|
Что здесь почитать?
1. Разработки.
1.1 Плагин "Я не робот"
1.2 Плагин "Код Adsense прямо в пост"
2. Заработай.
2.1 Блогун: 20$ в день
2.2 Уходим от налогов в Sape
2.3 Хватит думать, пора зарабатывать
3. Акции и конкурсы.
3.1 Ссылка за "Рабочий стол"
Показать весь список.
полный список в процессе наполнения ;) посмотрите чуть позже
-->
|
23.06 2023 в 7:50 пп
24.06 2023 в 7:56 пп
26.06 2023 в 11:55 дп
28.06 2023 в 1:16 дп
Вот только не понимаю зачем оно надо, как применить в жизни.
Ну вот про велосипеды и роботов_убийц_детей всё ясно. Каждый день сортирую
29.06 2023 в 3:38 пп
08.07 2023 в 11:44 дп
15.09 2023 в 5:56 пп
20.09 2023 в 7:23 дп
Ксю ты и тут уже побывала))))
ссылка не пашет, а ооооооочень нужно….
11.12 2023 в 11:48 пп
очень живой стиль изложения. меня уже задрала сухая математика, а автор молодец) успехов!
19.12 2023 в 1:04 дп
19.12 2023 в 10:31 дп
19.12 2023 в 11:42 дп
24.12 2023 в 4:35 пп
04.01 2024 в 10:57 пп
11.03 2024 в 1:56 дп
24.03 2024 в 6:58 пп
05.04 2024 в 9:34 пп
19.04 2024 в 10:55 пп
Блин, гуглил и яшил, что только не делал … везде срань какая-то, точнее вроде и понятно, но как-то по мелочи непонятно и в итоге, алгоритм не поддавался полному пониманию =)
А тут всё норм, просто, свободно и легко объясняется, так что мистер автор пиши статьи в том же духе =) полезны!
Респект и ещё раз спасибо!
12.05 2024 в 10:40 дп
Автору спасибо за пост.
30.08 2024 в 6:46 пп