Полное руководство по алгоритмам кластеризации и тематическому моделированию
Часть 1: Руководство по K-means для начинающих
Кластеризация - один из наиболее часто используемых алгоритмов машинного обучения без учителя. Вы можете думать о кластеризации как о помещении неорганизованных точек данных в разные категории, чтобы вы могли больше узнать о структурах ваших данных. Кластеризация имеет множество приложений для извлечения информации из данных без меток. Например, компании объединяют клиентов в группы на основе их характеристик, таких как покупательское поведение, чтобы проводить более эффективные рыночные кампании, устанавливать стратегии ценообразования для получения большей прибыли и т. Д. Алгоритмы кластеризации также широко используются в обработке естественного языка (NLP) для извлечения информации из неструктурированных текстовые данные и тематическое моделирование являются одним из примеров.
Целью этой серии статей является предоставление читателям полного представления о двух общих, но очень разных алгоритмах кластеризации, K-средних и скрытом распределении Дирихле (LDA), и их приложениях в тематическое моделирование:
Часть 1. Руководство по K-средних для начинающих (эта статья)
Часть 3. Использование K-средних и LDA для моделирования тем (скоро)
В этой статье я подробно расскажу о применении алгоритма K-средних.
Что такое К-средние
K-Means - это один из простейших алгоритмов кластеризации для обнаружения общих закономерностей в неорганизованных точках данных. Алгоритм классифицирует все точки данных на K кластеров, определяя близкие точки данных на основе их сходства. K-среднее просто определяет сходство как евклидово расстояние, измеренное в пространстве признаков. В целях иллюстрации, используя приведенный ниже код, я генерирую три кластера нормально распределенных точек в двух измерениях:
import numpy as np import matplotlib.pyplot as plt #generate random data samples from known clusters x = np.random.normal(0, 0.5, (100, 2)) + np.array([0, 1.2]) y = np.random.normal(0, 0.5, (100, 2)) + np.array([-0.7, -0.7]) z = np.random.normal(0, 0.5, (100, 2)) + np.array([0.7, -0.7]) plt.scatter(*x.T) plt.scatter(*y.T) plt.scatter(*z.T) plt.title(‘Data Example with Only Two Features’) plt.xlabel(‘Feature 1’) plt.ylabel(‘Feature 2’);
На приведенном ниже графике показаны вручную три кластера данных. Поскольку у данных выборки есть только две особенности, мы можем ясно видеть, какие точки близки друг к другу на двумерном графике. Та же самая интуиция возникает, когда пространство функций увеличивается более чем в двух измерениях в реальных приложениях.
Чтобы применить K-Means, исследователям сначала необходимо определить количество кластеров. Затем алгоритм назначит каждую выборку кластеру, где ее расстояние от центра кластера будет минимальным. Код прост:
from sklearn.cluster import KMeans data = np.vstack((x,y,z)) km = KMeans(n_clusters=3) km.fit(data)
Здесь, поскольку мы сгенерировали данные, мы знаем, что существует три кластера. А как насчет реальных приложений, когда вы мало знаете о данных? В этой статье мы обсудим ответ на этот вопрос после знакомства с математическими деталями алгоритма K-средних.
Математика, лежащая в основе К-средних
Алгоритм K-средних заранее определяет количество кластеров K, а затем назначает набор кластеров C = {C1, C2,… Ck}, которые минимизируют:
где 𝜇𝑘 - центр точек кластера Ck:
Алгоритм работает следующим образом:
- Укажите количество кластеров K.
2. Инициализируйте центральную точку 𝜇𝑘 (k ∈ K) каждого кластера случайным значением.
3. Вычислите квадрат евклидова расстояния от каждой точки данных X_j до центральной точки каждого кластера.
4. Назначьте X_j ближайшему кластеру k, где квадрат евклидова расстояния минимален:
5. Обновите 𝜇𝑘, взяв среднее значение точек выборки, присвоенных кластеру k.
6. Повторите шаги с 3 по 5 до схождения.
Обратите внимание, что итерационные шаги понижают целевую функцию, и существует только конечное число возможных разбиений точек, поэтому алгоритм гарантированно сходится. Однако конвергентное решение не может быть оптимальным в глобальном масштабе. По умолчанию K-Means запускает алгоритм кластеризации десять раз с разными начальными числами центроидов и получает лучший результат в показателях.
Показатели K-среднего
Как определить степень соответствия для моделей кластеризации, таких как K-means? Ответ на этот вопрос важен для поиска наиболее подходящей модели на этапах итерации и играет важную роль в оказании помощи исследователям в выборе количества кластеров. Наиболее часто используемые показатели для алгоритмов кластеризации - это инерция и силуэт.
Инерция
Инерция измеряет расстояние от каждой точки данных до ее конечного центра кластера. Для каждого кластера инерция определяется средним квадратом расстояния между каждой точкой данных X_j ∈ Ck и центром 𝜇𝑘:
После суммирования инерции по всем кластерам, общая инерция используется для сравнения производительности различных моделей K-средних:
Из определения инерции ясно, что нам нужно выбрать модель, которая минимизирует общую инерцию.
Коэффициент силуэта
Коэффициент силуэта - еще один показатель, который можно использовать в алгоритмах кластеризации. Для каждой точки данных X_j вычисляется среднее расстояние между X_j и всеми другими точками в тех же кластерах. Определим его как a_j. Затем он ищет следующий ближайший кластер X_j (второй лучший кластер для классификации X_j) и вычисляет среднее расстояние между X_j и всеми точками в этом кластере как b_j. Коэффициент силуэта для точки X_j равен:
Из приведенного выше уравнения мы можем видеть, что коэффициент силуэта находится между -1 и 1 в зависимости от того, какой из них больше, a_j или b_j:
Если b_j больше, чем a_j, это означает, что модель сгруппировала X_j в лучший кластер. Чем больше b_j по сравнению с a_j, тем лучше кластер. В противном случае, когда a_j больше, это означает, что эта точка, вероятно, должна быть в другом кластере. Чем больше a_j по сравнению с b_j, тем ближе значение к -1.
Коэффициент силуэта дает информацию о том, насколько плотен каждый кластер при вычислении его среднего значения для всех точек данных в кластерах. Он измеряет производительность модели при вычислении среднего коэффициента силуэта для всех точек данных.
Как правильно выбрать количество кластеров?
К сожалению, мы не можем решить этот вопрос аналитически, но при решении K полезно руководствоваться некоторыми общими правилами. Число K определяется как математически, так и практически. Чтобы получить лучшую модель, мы можем рассчитать инерцию из различных вариантов K и выбрать наиболее эффективную. Вот тут-то и пригодится изгиб локтя. Кривая изгиба отображает инерцию для различных K. Обратите внимание, что инерция всегда будет уменьшаться с увеличением K. Если K равно количеству общих точек данных, инерция будет равна нулю (каждая точка данных является кластером). Мы можем использовать кривую изгиба, чтобы проверить убывающую скорость, и выбрать K в точке изгиба, когда после этой точки инерция уменьшается значительно медленнее.
Используя точки данных, сгенерированные выше, и код ниже, мы можем построить кривую локтя:
inertias = [] for n_clusters in range(2, 15): km = KMeans(n_clusters=n_clusters).fit(data) inertias.append(km.inertia_) plt.plot(range(2, 15), inertias, ‘k’) plt.title(“Inertia vs Number of Clusters”) plt.xlabel(“Number of clusters”) plt.ylabel(“Inertia”);
и это сюжет:
График показывает, что инерция продолжает уменьшаться с увеличением K. Когда K = 3, есть точка поворота с точки зрения скорости уменьшения инерции, и это точка изгиба, которую мы должны искать. Обратите внимание, что при генерации данных мы используем три нормальных распределения. Таким образом, он соответствует результату, основанному на кривой локтя.
Нам также необходимо подумать о целесообразности количества кластеров, которые мы определяем с помощью кривой локтя. Мы должны выбрать K, который легко интерпретировать и который практически осуществим. Например, если у вашей компании есть ресурсы (рабочая сила и капитал) только для того, чтобы сгруппировать клиентов по трем категориям, вам следует установить K равным трем независимо от предложений кривой Локтя.
Перед применением К-средних
Для повышения производительности модели и получения более надежных результатов необходимо выполнить предварительную обработку функций как минимум в два этапа: масштабирование и уменьшение размерности.
Функции масштабирования
Поскольку K-среднее использует евклидово расстояние между точками данных для определения кластеров, все функции должны быть масштабированы таким образом, чтобы их единицы были сопоставимы. В противном случае отклонение определенных характеристик от несопоставимых единиц может повлиять на результат. Мы можем масштабировать данные с помощью StandardScaler преобразователя scikit-learn. Он центрирует каждую функцию вокруг ее среднего значения и масштабирует его путем деления на стандартное отклонение этой функции.
Выполните уменьшение размерности
Как вы могли заметить, алгоритмы кластеризации сложны в вычислительном отношении, и сложность быстро увеличивается с увеличением количества функций. Таким образом, очень часто перед применением алгоритма кластеризации K-средних часто снижают размерность данных.
Анализ основных компонентов (PCA) - широко используемый алгоритм для сокращения количества функций в данных при сохранении как можно большего объема информации. Вы можете обратиться к этому документу для получения более подробной информации.
K-Means - это самый простой и популярный алгоритм кластеризации с множеством вариантов использования. В этой статье основное внимание уделяется его математическим деталям, используемым метрикам и предложениям по их применению. В следующих статьях я расскажу об альтернативном алгоритме кластеризации, LDA, и о применении K-Means и LDA в тематическом моделировании.
Спасибо за чтение! Вот список всех моих сообщений в блоге. Посмотрите их, если вам интересно.
