Запустите алгоритм кластеризации

В машинном обучении вы иногда сталкиваетесь с наборами данных, которые могут содержать миллионы примеров. Алгоритмы машинного обучения должны эффективно масштабироваться для этих больших наборов данных. Однако многие алгоритмы кластеризации не масштабируются, поскольку им необходимо вычислять сходство между всеми парами точек. Это означает, что их время выполнения увеличивается пропорционально квадрату числа точек, обозначаемому как \(O(n^2)\). Например, агломеративные или разделительные алгоритмы иерархической кластеризации рассматривают все пары точек и имеют сложность \(O(n^2 log(n))\) и \(O(n^2)\)соответственно.

Этот курс фокусируется на k-средних, потому что он масштабируется как \(O(nk)\), где \(k\)— это количество кластеров. k-means группирует точки в кластеры \(k\) путем минимизации расстояний между точками и центроидом их кластера (как показано на рисунке 1 ниже). Центроид кластера - это среднее значение всех точек в кластере.

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

Перед запуском k-средних необходимо выбрать количество кластеров \(k\). Сначала начните с предположения для \(k\). Позже мы обсудим, как уточнить это число.

Алгоритм кластеризации k-средних

Чтобы сгруппировать данные в кластеры \(k\) , k-means выполняет следующие шаги:

Рисунок 1: k-средние при инициализации.

Шаг первый

Алгоритм случайным образом выбирает центр тяжести для каждого кластера. В нашем примере мы выбираем \(k\) из 3, и поэтому алгоритм случайным образом выбирает 3 центроида.

Рисунок 2: Начальные кластеры.

Шаг второй

Алгоритм присваивает каждой точке ближайший центр тяжести, чтобы получить начальные кластеры \(k\) .

Рисунок 3: Пересчет центроидов.

Шаг третий

Для каждого кластера алгоритм повторно вычисляет центр тяжести, взяв среднее значение всех точек в кластере. Изменения центроидов показаны на рисунке 3 стрелками. Поскольку центроиды меняются, алгоритм переназначает точки ближайшему центроиду. На рис. 4 показаны новые кластеры после переназначения.

Рисунок 4: Кластеры после переназначения.

Шаг четвертый

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

Вам не нужно понимать математику k-средних для этого курса. Однако, если вам интересно, см. ниже математическое доказательство.

Щелкните значок плюса для математического доказательства

Учитывая \(n\) примеров, назначенных \(k\) кластерам, минимизируйте сумму расстояний примеров до их центроидов. Где:

• \(A_{nk} = 1\) , когда пример \(n\)присваивается кластеру \(k\), и 0 в противном случае
• \(\theta_k\) — центр тяжести кластера \(k\).

Мы хотим минимизировать следующее выражение:$$\min_{A,\theta} \sum_{n=1}^N \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n ||^2$$с учетом:$$A_{nk} \in \{0,1\} \forall n,k$$и$$\sum^{K}_{k=1}A_{nk}=1 \forall n$$Чтобы минимизировать выражение относительно центроидов кластера \(\theta_k\), возьмите производную относительно \(\theta_k\) и приравняйте ее к 0.$$f(\theta) = \sum^{N}_{n=1} \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n||^2$$$$\frac{\partial f}{\partial \theta_k} = 2 \sum_{n=1}^{N} A_{nk}(\theta_k - x_n) = 0$$$$\implies \sum_{n=1}^{N} A_{nk}\theta_{k} = \sum^N_{n=1} A_{nk}x_{n}$$$$\theta_k \sum_{n=1}^{N} A_{nk} = \sum_{n=1}^{N} A_{nk} x_n$$$$\theta_k = \frac{\sum^N_{n=1} A_{nk} x_n}{\sum^N_{n=1} A_{nk}}$$Числитель представляет собой сумму всех расстояний пример-центроид в кластере. Знаменатель — это количество примеров в кластере. Таким образом, центр тяжести кластера\(\theta_k\) представляет собой среднее значение расстояний пример-центроид в кластере. Значит доказано.

Поскольку положения центроидов изначально выбираются случайным образом, k-средние могут возвращать значительно отличающиеся результаты при последовательных запусках. Чтобы решить эту проблему, запустите k-means несколько раз и выберите результат с метриками наилучшего качества. (Мы опишем метрики качества позже в этом курсе.) Вам понадобится расширенная версия k-средних, чтобы выбрать лучшие начальные положения центроидов.

Эксперимент: используя этот симулятор k-средних из Стэнфорда, попробуйте запустить k-means несколько раз и посмотрите, получите ли вы разные результаты.

Основные условия:

• центр тяжести