Делим исходные данные на кластеры, опираясь на поняние "близости" в каком-то многомерном евклидовом пространстве
- Данных бывает очень много.
- Исходые данные могут быть шардированы по серверам (Distributed таблица)
- результатом должен быть массив ключей исходных строк для всех выявленных кластеров
Выгода делать это все не обычным образом (скажем через стандартную библиотеку питона), а внутри КХ на его SQL диалекте заключается в следующем:
- многопоточность по ядрам получается "сама", не нужно ничего специально программировать, КХ будет читать с диска данные в 8 потоков и там-же делать самые сложные вычислении - подсчет евклидовой дистанции и группировку.
- шардинг (если данные уже разложены по серверам) - ускоряет в N раз, так как точки будут обсчитываться параллельно и независимо отдельными серверами.
- хотя UDF на питоне решают задачу через множество библиотек с доступными и отлаженными реализациям k-means, но нужно учитывать, что будет запущено несколько копий питона, чтобы КХ кормил их данными в параллель. Важно чтобы скрипт это учитывал, и работал соответственно. Получаеся довольно сложная работа с shared memory (для хранения центроидов) и прочий непростой interprocess communications.
Идея SQL k-means взята из https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.109.5005&rep=rep1&type=pdf Но там сделано на классическом SQL и очень сложно. Clickhouse позволяет сделать изящнее и эффективнее.
- берем случайную точку как первый центроид
- вычисляем остальные центроиды случайным образом из остальных точек так, чтобы вероятность выбора точки была пропорциональна вычисленному для неё квадрату расстояния до предыдущего
- вычисляем расстояние от каждой точки до всех центроидов
- находим ближайший центроид для каждой точки, объединяем их в группу, назначаем центр этой группы новой позицией центроида
- повторяем пока движение не остановится
Все сделано в виде bash скрипта, который запускает в циклах два разных SQL insert (инициализация и пересчет центроидов).
Больше подробностей тут - https://habr.com/ru/post/645291/
- данные могут находиться в любой таблице, алгоритм работает через view YH, которое получает из исходной таблицы только ключ строки (i) и формирует tuple координат в пространстве.
- если данные шардированы, то view нужно создать на всех узлах кластера
- тип координат может быть любой числовой. По умолчанию Int32, можно заменить на Float. Указывается в исходном view YH, и в результирующей таблице WCR. В ней же надо указать количество измерений для Y
- количество кластеров данных определяется начальным количеством центроидов. Задается в bash скрипте.
- статистика для локтя и силуэта - https://www.helenkapatsa.ru/mietod-k-sriednikh/
- https://medium.com/analytics-vidhya/how-to-determine-the-optimal-k-for-k-means-708505d204eb
- пара запросов для вычисления необходимых метрик есть в OptimalK.sql
- строим графики, смотрим глазами, выбираем лучшее
В таблице WCR есть строка для каждого шага алгоритма и каждого центроида, с указанием таймстемпа. Для получения кластеров нужен ещё один полный проход по данным, с вычислением ближайшего центроида к каждой точке. Можно джойнить с исходными данными по ключу. Мой вариант для визуализации - в конце sql&bash файлов.
- считать не только центроиды (means), но и weights and variances
- Sufficient Statistics
- https://www.researchgate.net/publication/267202484_Fast_K-Means_Clustering_for_Very_Large_Datasets_Based_onMapReduce_Combined_with_a_New_Cutting_Method_httplinkspringercomchapter1010072F978-3-319-11680-8_23