Linux-Clickhouse k means: k-means on Clickhouse SQL

k-means on Clickhouse SQL

4clusters

Делим исходные данные на кластеры, опираясь на поняние "близости" в каком-то многомерном евклидовом пространстве

  • Данных бывает очень много.
  • Исходые данные могут быть шардированы по серверам (Distributed таблица)
  • результатом должен быть массив ключей исходных строк для всех выявленных кластеров

Почему clickhouse

Выгода делать это все не обычным образом (скажем через стандартную библиотеку питона), а внутри КХ на его 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 (инициализация и пересчет центроидов).

Исходные данные

  • данные могут находиться в любой таблице, алгоритм работает через view YH, которое получает из исходной таблицы только ключ строки (i) и формирует tuple координат в пространстве.
  • если данные шардированы, то view нужно создать на всех узлах кластера
  • тип координат может быть любой числовой. По умолчанию Int32, можно заменить на Float. Указывается в исходном view YH, и в результирующей таблице WCR. В ней же надо указать количество измерений для Y
  • количество кластеров данных определяется начальным количеством центроидов. Задается в bash скрипте.

Результат

В таблице WCR есть строка для каждого шага алгоритма и каждого центроида, с указанием таймстемпа. Для получения кластеров нужен ещё один полный проход по данным, с вычислением ближайшего центроида к каждой точке. Можно джойнить с исходными данными по ключу. Мой вариант для визуализации - в конце sql&bash файлов.

todo

Comments

  • исправления под step
    исправления под step

    Jan 20, 2022

    null

                                                                                                                                                                                                           
    Reply