Это серия быстрых и четких учебных заметок, которые можно использовать в качестве шпаргалки перед собеседованием или при работе с новым алгоритмом.
Если мы ничего не знаем о наших данных, кроме самих данных, т. е. в наборе данных не определены метки, кластеризация 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-средних, чтобы остановиться. Это можно сделать методом локтя и методом силуэта.
Спасибо, что прочитали!