Это серия быстрых и четких учебных заметок, которые можно использовать в качестве шпаргалки перед собеседованием или при работе с новым алгоритмом.

Если мы ничего не знаем о наших данных, кроме самих данных, т. е. в наборе данных не определены метки, кластеризация K-средних может помочь нам разобраться в этом.

Постановка проблемы: нас наняла компания FishBowl, приложение, которое предоставляет анонимный форум и сообщество для проверенных сотрудников для обсуждения проблем. Они хотят знать, как помочь им расширить свою пользовательскую базу.

Мы ничего не знаем об их текущей пользовательской базе или о том, какими они стали. Единственные данные, которые у нас есть для каждого пользователя, — это то, как они взаимодействуют с приложением. Мы получили эту информацию, отслеживая поведение пользователя в сети.

Функции (взаимодействия):

  • отдано/получено лайков в день
  • среднее время сеанса
  • количество размещенного контента в месяц
  • среднее время прокрутки фида за сеанс
  • прямых сообщений, отправленных/полученных за день

Цель K-средних состоит в том, чтобы организовать наши данные в K отдельных групп.

Пример сценария

Для лучшего визуального понимания предположим, что у нас есть только 2 функции, и после сопоставления векторов график выглядит следующим образом:

Теперь, если K=2, алгоритм разделит данные на две группы.

Шаг 1. Алгоритм выбирает K случайных точек и присваивает им разные метки.

Эти точки называются cэнтроиды.

Шаг 2. После этого мы находим расстояние между этими точками центроида и всеми остальными точками.

Шаг 3.В зависимости от того, какой центроид находится ближе всего к нему, каждая точка получит метку этого центроида.

Шаг 4. Затем мы обновляем центроиды, чтобы они были средними данными заданных точек в соответствующих кластерах.

Шаг 5.Процесс повторяется, и на каждой итерации мы проверяем расстояние нового центроида от остальных точек в его кластере. Впоследствии положение центроида изменяется на среднее значение кластера.

Если координаты центроида не меняются после нескольких итераций, то мы можем сказать, что K-средние сошлись.

Как проверить качество сходимости К-средних?

Получим евклидово расстояние между центроидом и всеми точками его кластера.

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

Цель состоит в том, чтобы минимизировать инерцию для формирования наиболее однородных кластеров.

Один из способов добиться наименьшей возможной инерции — буквально попробовать каждую комбинацию кластеров для K=2. Это приводит к нашему следующему вопросу:

Как минимизировать инерцию?

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

Временная сложность для вычисления K-средних всех возможных комбинаций кластеров для значения K составляет:

k= количество кластеров

d= количество параметров

n= количество d-мерных векторов

Некоторые более эффективные способы минимизации инерции:

(a) Алгоритм Ллойда

i= количество итераций, необходимых для сходимости.

Алгоритм Ллойда помогает снизить сложность до n*K*d*i. Однако здесь есть некоторые ограничения.

При использовании алгоритма Ллойда мы, по сути, аппроксимируем наилучшую конфигурацию кластера для определенного значения K. Давайте создадим двухмерную диаграмму с инерцией по оси Y, конфигурацией кластера по оси X (количество векторов в 1-м кластере), и постройте алгоритм Ллойда.

Мы видим, что это не выпуклая диаграмма, т. е. в диаграмме есть несколько минимумов. Следовательно, оптимизация этого может привести к неоптимальным результатам, если мы застрянем на локальных минимумах. Есть способы обойти это (K-means++), но ни один из них не идеален.

(b) Разделенные пополам K-средние

Алгоритм K-средних пополам является модификацией алгоритма K-средних. Он может производить секционированную/иерархическую кластеризацию и распознавать кластеры любой формы и размера.

Он превосходит K-Means в измерении энтропии.

Процесс разделения K-средних пополам

Шаг 1: независимо от значения K мы делим кластеры на две части, например, K=2.

Шаг 2. Мы делим кластер с более высокой инерцией из двух, полученных на шаге 1, на два кластера.

Шаг 3: через несколько итераций, когда мы достигнем желаемого значения K. В этом случае мы предполагаем, что оно равно K=3.

Bisected K-means можно использовать, если мы хотим избежать застревания в локальных минимумах (при этом получая наилучшую конфигурацию кластера). Загвоздка в том, что нам нужно знать правильное значение K-средних, чтобы остановиться. Это можно сделать методом локтя и методом силуэта.

Спасибо, что прочитали!