Кластеризация — это форма неконтролируемого машинного обучения, означающая, что агрегация, полученная в результате алгоритма, не имеет предопределенных меток. K-Means, или KNN, является типичным алгоритмом кластеризации, см. эту ссылку, если вы хотите познакомиться с алгоритмом. Цель этой статьи — более подробно изучить, как работает этот алгоритм, и предоставить основу для анимации графиков любого типа.

Анимация алгоритма — хороший визуальный инструмент для понимания того, как он работает внутри. Этот алгоритм особенно подходит для этого, потому что это итерационный алгоритм. Другие алгоритмы кластеризации более мощные, но их не так легко анимировать. Одно предостережение, о котором следует помнить, заключается в том, что механика 2D-алгоритма не может быть напрямую переведена в n-мерное пространство.

В этой статье для реализации кода используется Python и библиотека scikit-learn. Библиотека предоставляет реализация k-средних, которая принимает в качестве параметра схему инициализации центроида. Возможные варианты: случайный и k-means++. На следующих графиках показана анимация k-средних для каждой схемы инициализации и для одного и того же набора данных.

На этом графике показано, что говорится в документации scikit-learn о различиях в схеме инициализации. То есть «k-средних++» лучше, чем «случайный», потому что он выбирает лучшие начальные точки, что приводит к более быстрой сходимости алгоритма. Тем не менее, если честно, я запустил блокнот Jupyter с несколькими начальными значениями, чтобы найти тот, который лучше всего подходит для отображения. Что было странным, так это то, что меньшинство прогонов на самом деле приводило к «случайной» инициализации, что приводило к более высокой точности.

Следующий блок представляет собой псевдокод всего процесса со следующими ссылками для справки:

# create dataset
dataset = sklearn.datasets.make_blobs
# plot the dataset
define a function: plot_animation_frame()
   this function plots each frame with seaborn scatterplot 
   and saves the plot as a file with savefig()
call plot_animation_frame() with the data set only
   the goal is to plot only the dataset, no clustering
   this creates the first frame of the animation
# iterate over algorithm
initialize current-centroids as empty
run one iteration of KMeans, with max_iter=1
   this iteration uses the current-centroids
   after running, update current-centroids with the new result
   output current cluster predictions with plot_animation_frame()
   keep going in iterations until the algorithm converges
# create animated gif
   with all frames available as files, 
   join them into the animated gif with ImageMagick.convert
   note that each frame file needs to be named with 
   left-zero-padding so they come out in order

Ниже приведена команда ImageMagick, используемая для создания анимированного gif.

convert -delay 200 -loop 0 'kmeans_centroid/*.png' 'kmeans.gif'

На этом создание анимированного образца k-means завершено. Команду анимации можно использовать для любого набора изображений внутри папки, независимо от того, как эти изображения созданы.