K-means — это алгоритм для назначения кластеров в разные точки. Одним из его приложений является предоставление автоматизированного метода сегментации и микросегментации на основе поведенческих данных. Затем эти сегменты можно использовать для предоставления рекомендаций или целевых предложений различным пользователям в сегментах, как описано ранее в предыдущем сообщении в блоге.

Алгоритм принимает два основных входа, список точек и фиксированное количество кластеров, и предоставляет два разных выхода: назначение кластера для каждой точки, центр кластера для каждого из вычисленных кластеров. В этом сообщении в блоге показано, как реализовать этот алгоритм с нуля, используя vanilla python.

Скелерн API

Если мы посмотрим на API Sklearn с точки зрения того, как он настраивает входные данные для K-средних:

K-Means создается путем предоставления входного количества кластеров для вычисления, а обучение вычисляется при вызове метода подгонки для списка точек, массива numpy или кадра данных pandas.

Результатом K-средних с sklearn является метод прогнозирования для назначения кластера и переменная cluster_centers_ для получения центральной точки каждого вычисляемого кластера.

Скелет класса

если бы мы повторно применили эти вызовы API в качестве основы для нашей реализации vanilla python, у нас был бы скелет класса как:

Классы и функции очков

Выше представлен потенциальный класс точек, он используется для хранения методов и данных каждой точки, предназначенных для включения в вычисление k-средних. Класс широко использует операторы Python для упрощения некоторых операций, которые будут выполняться ниже по течению, таких как вычисление средних значений, расстояний или равенства между двумя точками.

Точка кластера определяется как точка, назначаемая данному кластеру.

Алгоритмы k-средних основаны на понятии расстояния, чтобы связать каждую точку с ближайшей средней точкой. Показанная выше функция расстояния вычисляет евклидово расстояние между двумя точками 2D. В то время как ближайшая функция возвращает индекс первой точки в списке точек, которая является точкой, ближайшей к заданной точке p.

Подходящий метод

Давайте сначала сосредоточимся на том, что должен делать метод fit, если мы посмотрим, как должен вести себя алгоритм k-средних:

  • Этап назначения: случайным образом берется новая точка для каждого из n кластеров, определенных в k-средних, и назначается этому кластеру.
  • Этап обновления: для каждой точки присваивается точка кластеру на основании того, что он является ближайшим кластером, и до тех пор, пока не будет выполнен определенный критерий остановки, обычно количество итераций или условие сходимости ( кластер означает, что не меняются)

Давайте посмотрим, как реализовать шаг присваивания в методе fit:

Что делает код, так это то, что пока мы не назначим необходимое количество начальных точек кластера, мы назначаем кластеру одну точку случайным образом в качестве его центра. В конечном итоге они помещаются в переменную cluster_centers_ для дальнейшего использования. Затем мы инициализируем каждую точку, назначая ее ближайшей точке кластера.

Для всех точек в наборе данных выполните инициализацию первого прохода и назначьте точку данному кластеру.

  • Назначить каждой точке ближайшее среднее значение кластера (lcp)
  • Пересчитать среднее значение для каждого кластера (cluster_centers_), в приведенной выше функции среднее значение вычисляется с использованием фильтрации спискового понимания и операторов класса точек
  • Прервать, если условие остановки выполнено, в противном случае перейти к следующему раунду цикла. Условие остановки — это либо 100 итераций, либо постоянное среднее значение и 1 или более итераций.

Настройка всего вместе дает описанный выше метод подгонки.

Предсказать метод

Функции прогнозирования повторно используют часть кода, которая использовалась в процессе подбора/обучения. Он преобразует каждую точку в списке точек в точку кластера, назначенную ближайшему среднему значению кластера.

Подведение итогов

Настройка K-средних, как описано выше, позволяет нам запустить метод fit для списка точек и вычислить различные центры кластеров.

API прогнозирования при наличии списка входных точек возвращает список точек кластера с присвоением их ближайшим k-средним.

Нам удалось создать реализацию k-means с использованием vanilla python, смоделированного по образцу API sklearn, хотя он может не демонстрировать производительность реализации, основанной на numpy или pandas, и неоптимизирован, он позволяет понять различные шаги, необходимые для реализовать алгоритм K-средних.

Еще от меня на Hacking Analytics: