Алгоритм KMeans
Алгоритм кластеризации KMeans был открыт еще в 1950 году математиком Гуго Штенгаузом. У этого алгоритма есть множество применений, например:
- статистическая обработка данных в археологии, медицине, психологии, химии, биологии, государственном управлении, филологии, антропологии, маркетинге, социологии, геологии и других дисциплинах
Для начала немного терминов, которые помогут вам разобраться в работе этого алгоритма:
- кластер - некое множество, состоящее из точек и одного центроида
- центроид - абстрактный объект в кластере, к которому прикрепляются все соседние незакрепленные точки
- значение потери - сумма всех евклидовых расстояний точек до назначенного ей центроида
Этот алгоритм гениален в своей простоте - его основная цель это уменьшить значение потери перемещая центроиды и создавая новые кластеры. Его шаги таковы:
- Случайным образом создать некоторое количество центроидов
- У каждой точки найти ближайший цетроид при помощи евклидового расстояния и прикрепить эту точку к нему
- Переместить центроиды у образовавшихся кластеров в новое место - среднее всех точек определенного кластера
- Вычислить новое значение потерь
- Повторять шаги 2-4 пока значение потерь не перестанет заметно меняться
- для лучшего результата можно несколько раз инициализировать этот алгоритм с разным начальным положением центроидов (п.1), и выбрать из получившихся решений наиболее удачное
COLORSCHEME
На основе алгоритма KMeans я создал свой полностью автоматизированный паблик ВК, пример его работы:
Работает моя программа так:
- на вход подается изображение
- это изображение постеризуется (процесс уменьшения палитры цветов изображения) P.S. постеризованное изображение можно увидеть напротив диаграммы цветов
- цвета изображения подаются в алгоритм KMeans
- полученные кластеры из п.3 - и есть наиболее важные цвета на изображении
- некоторые процедуры по созданию графического интерфейса
В будущем планируется добавить еще больше информации о цветах изображения, придумать как сделать тегирование, и другое...
