Кластеризация данных в группы, часть 2

СТАТЬЯ

Кластеризация данных в группы, часть 2

Из Data Science Bookcamp Леонарда Апельцина

Эта серия статей из трех частей охватывает:

Кластеризация данных по централизации
Кластеризация данных по плотности
Компромиссы между алгоритмами кластеризации
Выполнение кластеризации с помощью библиотеки scikit-learn
Перебор кластеров с помощью Pandas

Получите скидку 35% на Data Science Bookcamp, введя fccapeltsin в поле кода скидки при оформлении заказа на manning.com.

Если вы пропустили это, вы можете проверить часть 1 здесь.

K-средних: алгоритм кластеризации для группировки данных в K центральных групп

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

Мы инициализируем K-means, сначала выбрав K — количество центральных координат, которые мы будем искать. В нашем анализе мишени K было установлено равным 2, хотя обычно K может равняться любому целому числу. Алгоритм случайным образом выбирает K точек данных. Эти точки данных рассматриваются как настоящие центры. Затем алгоритм выполняет итерации, обновляя выбранные центральные местоположения, которые специалисты по данным называют центроидами. Во время одной итерации каждая точка данных присваивается своему ближайшему центру, что приводит к формированию групп K. Далее обновляется центр каждой группы. Новый центр равен среднему значению координат группы. Если мы будем повторять процесс достаточно долго, групповые средние сойдутся в K репрезентативных центрах (рис. 6). Сходимость математически гарантирована. Однако мы не можем знать заранее количество итераций, необходимых для сходимости. Обычная уловка состоит в том, чтобы остановить итерации, когда ни один из вновь вычисленных центров не отличается значительно от своих предшественников.

K-средние не без ограничений. Алгоритм основан на нашем знании K: количества кластеров для поиска. Часто таких знаний нет. Кроме того, хотя K-средние обычно находят разумные центры, математически не гарантируется нахождение наилучших возможных центров в данных. Иногда K-средние возвращают неинтуитивные или субоптимальные группы из-за плохого выбора случайных центроидов на этапе инициализации алгоритма. Наконец, метод K-средних предполагает, что кластеры данных на самом деле вращаются вокруг K центральных местоположений. Но, как мы узнаем позже в этом разделе, это предположение не всегда выполняется.

Кластеризация K-средних с использованием scikit-learn

Алгоритм K-средних работает за разумное время, если он реализован эффективно. Быстрая реализация алгоритма доступна через внешнюю библиотеку scikit-learn. Scikit-learn — чрезвычайно популярный набор инструментов для машинного обучения, созданный на основе NumPy и SciPy. Он включает в себя множество основных алгоритмов классификации, регрессии и кластеризации, включая, конечно же, K-средних. Давайте установим библиотеку. Затем мы импортируем класс кластеризации scikit-learn KMeans.

Вызовите pip install scikit-learn из терминала командной строки, чтобы установить библиотеку scikit-learn.

Листинг 8. Импорт KMeans из scikit-learn

from sklearn.cluster import Kmeans

Применить KMeans к нашим darts данным очень просто. Сначала нам нужно запустить KMeans(n_clusters=2), который создаст объект cluster_model, способный находить два центра "бычьего глаза". Затем мы можем выполнить K-means, запустив cluster_model.fit_predict(darts). Вызов этого метода вернет массив assigned_bulls_eyes, в котором хранится индекс «бычьего глаза» каждого дротика.

Листинг 9. Кластеризация K-средних с использованием scikit-learn

cluster_model = KMeans(n_clusters=2) ❶
 assigned_bulls_eyes = cluster_model.fit_predict(darts) ❷
  
 print("Bull's-eye assignments:")
 print(assigned_bulls_eyes)
 Bull's-eye assignments:
 [0 0 0 ... 1 1 1]

❶ Создает объект cluster_model, в котором число центров равно 2.

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

Давайте раскрасим наши дротики в соответствии с их назначениями кластеризации, чтобы проверить результаты (рис. 7).

Листинг 10. График назначений кластеров K-средних

for bs_index in range(len(bulls_eyes)):
     selected_darts = [darts[i] for i in range(len(darts))
                       if bs_index == assigned_bulls_eyes[i]]
     x_coordinates, y_coordinates = np.array(selected_darts).T
     plt.scatter(x_coordinates, y_coordinates,
                 color=['g', 'k'][bs_index])
 plt.show()

Наша модель кластеризации определила центроиды в данных. Теперь мы можем повторно использовать эти центроиды для анализа новых точек данных, которые модель раньше не видела. При выполнении cluster_model.predict([x, y]) центроид назначается точке данных, определенной x и y. Мы используем метод predict для кластеризации двух новых точек данных.

Листинг 11. Использование cluster_model для кластеризации новых данных

new_darts = [[500, 500], [-500, -500]]
 new_bulls_eye_assignments = cluster_model.predict(new_darts)
 for i, dart in enumerate(new_darts):
     bulls_eye_index = new_bulls_eye_assignments[i]
     print(f"Dart at {dart} is closest to bull's-eye {bulls_eye_index}")
 Dart at [500, 500] is closest to bull's-eye 0
 Dart at [-500, -500] is closest to bull's-eye 1

Выбор оптимального K методом локтя

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

Метод локтя зависит от расчетного значения, называемого инерцией, которое представляет собой сумму квадратов расстояний между каждой точкой и ее ближайшим центром К-средних. Если K равно 1, то инерция равна сумме всех квадратов расстояний до среднего значения набора данных. Это значение, как обсуждалось в разделе 5, прямо пропорционально дисперсии. Дисперсия, в свою очередь, является мерой дисперсии. Таким образом, если K равно 1, инерция является оценкой дисперсии. Это свойство остается верным, даже если K больше 1. По сути, инерция оценивает общую дисперсию вокруг наших вычисленных значений K.

Оценивая дисперсию, мы можем определить, является ли наше значение K слишком высоким или слишком низким. Например, представьте, что мы установили для K значение 1. Потенциально многие из наших точек данных будут расположены слишком далеко от одного центра. Наша дисперсия будет большой, и наша инерция будет большой. По мере того, как мы увеличиваем K до более разумного значения, дополнительные центры вызывают уменьшение инерции. В конце концов, если мы переусердствуем и установим K равным общему количеству точек, каждая точка данных попадет в свой собственный частный кластер. Дисперсия будет устранена, а инерция упадет до нуля (рис. 8).

Некоторые значения инерции слишком велики. Другие слишком низкие. Где-то посередине может лежать значение, которое в самый раз. Как мы его находим?

Давайте выработаем решение. Начнем с построения графика инерции нашего набора данных мишени для большого диапазона значений K (рис. 9). Инерция автоматически вычисляется для каждого объекта scikit-learn KMeans. Мы можем получить доступ к этому сохраненному значению через атрибут модели _inertia.

Листинг 12. График инерции K-средних

k_values = range(1, 10)
 inertia_values = [KMeans(k).fit(darts).inertia_
                   for k in k_values]
  
 plt.plot(k_values, inertia_values)
 plt.xlabel('K')
 plt.ylabel('Inertia')
 plt.show()

Сгенерированный график напоминает руку, согнутую в локте, и локоть указывает на значение K, равное 2. Как мы уже знаем, это K точно отражает два центра, которые у нас есть. предварительно запрограммированы в наборе данных.

Сохранится ли этот подход, если количество существующих центров будет увеличено? Мы можем узнать это, добавив дополнительную мишень в нашу симуляцию метания дротиков. После того, как мы увеличим количество кластеров до трех, мы регенерируем наш график инерции (рис. 10).

Листинг 13. График инерции для моделирования с тремя мишенями

new_bulls_eye = [12, 0]
 for _ in range(5000):
     x = np.random.normal(new_bulls_eye[0], variance ** 0.5)
     y = np.random.normal(new_bulls_eye[1], variance ** 0.5)
     darts.append([x, y])
  
 inertia_values = [KMeans(k).fit(darts).inertia_
                   for k in k_values]
  
 plt.plot(k_values, inertia_values)
 plt.xlabel('K')
 plt.ylabel('Inertia')
 plt.show()

Добавление третьего центра приводит к новому изгибу, самый нижний угол наклона которого указывает на значение K, равное 3. По сути, наш график излома отслеживает дисперсию, захваченную каждым приращением K. Быстрое уменьшение инерции между последовательными значениями K означает, что разбросанные точки данных относятся к более тесному кластеру. Снижение инерции постепенно теряет свое влияние по мере того, как кривая инерции выравнивается. Этот переход от вертикального падения к более мягкому углу приводит к появлению на нашем графике формы локтя. Мы можем использовать положение локтя, чтобы выбрать правильный K в алгоритме K-средних.

Критерий выбора метода локтя является полезной эвристикой, но не гарантируется, что он будет работать во всех случаях. При определенных условиях изгиб медленно выравнивается по нескольким значениям K, что затрудняет выбор единственного допустимого числа кластеров.

Существуют более мощные методы K-отбора, такие как оценка силуэта, которая фиксирует расстояние от каждой точки до соседних кластеров. Подробное обсуждение оценки силуэта выходит за рамки этой книги. Тем не менее, вам рекомендуется изучить партитуру самостоятельно, используя метод sklearn.metrics.silhouette_score.

Методы кластеризации K-средних

k_means_model = KMeans(n_clusters=K) — создает модель K-средних для поиска K различных центроидов. Нам нужно подогнать эти центроиды к введенным данным.
clusters = k_means_model.fit_predict(data) — выполняет K-средние для введенных данных, используя инициализированный объект KMeans. Возвращенный массив clusters содержит идентификаторы кластеров в диапазоне от 0 до K. Идентификатор кластера data[i] равен clusters[i].
clusters = KMeans(n_clusters=K).fit_predict(data) — выполняет K-средних в одной строке кода и возвращает результирующие кластеры.
new_clusters = k_means_model.predict(new_data) — находит ближайшие центроиды к ранее невидимым данным, используя существующие центроиды в оптимизированном для данных объекте KMeans.
inertia = k_means_model.inertia_ — возвращает инерцию, связанную с оптимизированным для данных объектом KMeans.
inertia = KMeans(n_clusters=K).fit(data).inertia_ — выполняет K-средних в одной строке кода и возвращает результирующую инерцию.

Метод локтя не идеален, но он работает достаточно хорошо, если данные сосредоточены на K различных средних значениях. Конечно, это предполагает, что наши кластеры данных различаются из-за центральности. Однако во многих случаях кластеры данных различаются из-за плотности точек данных в пространстве. Давайте рассмотрим концепцию кластеров, управляемых плотностью, которые не зависят от центральности.

Использование плотности для обнаружения кластеров

Предположим, астроном обнаружил новую планету на дальнем краю Солнечной системы. Планета, как и Сатурн, имеет несколько колец, вращающихся по постоянным орбитам вокруг своего центра. Каждое кольцо сформировано из тысяч камней. Мы смоделируем эти породы как отдельные точки, определяемые координатами x и y. Давайте создадим три каменных кольца, состоящих из множества камней, используя функцию scikit-learn makes_circles (рис. 11).

Листинг 14. Моделирование колец вокруг планеты

from sklearn.datasets import make_circles
  
 x_coordinates = []
 y_coordinates = []
 for factor in [.3, .6, 0.99]:
     rock_ring, _ = make_circles(n_samples=800, factor=factor, ❶
                                 noise=.03, random_state=1)
     for rock in rock_ring:
         x_coordinates.append(rock[0])
         y_coordinates.append(rock[1])
  
 plt.scatter(x_coordinates, y_coordinates)
 plt.show()

❶ Функция make_circles создает две концентрические окружности в 2D. Масштаб радиуса меньшего круга относительно большего круга определяется параметром factor.

На графике отчетливо присутствуют три кольцевые группы. Давайте найдем эти три кластера, используя метод К-средних, установив для K значение 3 (рис. 12).

Листинг 15. Использование K-средних для кластеризации колец

rocks = [[x_coordinates[i], y_coordinates[i]]
           for i in range(len(x_coordinates))]
 rock_clusters = KMeans(3).fit_predict(rocks)
  
 colors = [['g', 'y', 'k'][cluster] for cluster in  rock_clusters]
 plt.scatter(x_coordinates, y_coordinates, color=colors)
 plt.show()

Выход - полный провал! K-средние разбивают данные на три симметричных сегмента, и каждый сегмент охватывает несколько колец. Решение не согласуется с нашим интуитивным ожиданием того, что каждое кольцо должно попадать в свою отдельную группу. Что пошло не так? Ну, K-средние предполагали, что три кластера были определены тремя уникальными центрами, но на самом деле кольца вращаются вокруг одной центральной точки. Разница между кластерами обусловлена не центральностью, а плотностью. Каждое кольцо строится из плотного набора точек, а пустые области малонаселенного пространства служат границами между кольцами.

Нам нужно разработать алгоритм, который группирует данные в плотных областях пространства. Для этого необходимо определить, является ли данная область плотной или разреженной. Одно простое определение плотности звучит следующим образом: точка находится в области плотности только в том случае, если она расположена на расстоянии X от Y других точек. Мы будем ссылаться на X и Y как epsilon и min_points соответственно. Следующий код устанавливает epsilon равным 0,1, а min_points равным 10. Таким образом, наши камни присутствуют в плотной области пространства, если они находятся в радиусе 0,1 по крайней мере от 10 других камней.

Листинг 16. Задание параметров плотности

epsilon = 0.1
 min_points = 10

Давайте проанализируем плотность первой породы в нашем списке rocks. Начнем с поиска всех других камней в пределах epsilon единиц от rocks[0]. Мы сохраняем индексы этих соседних камней в списке neighbor_indices.

Листинг 17. Поиск соседей rocks[0]

neighbor_indices = [i for i, rock in enumerate(rocks[1:])
                     if euclidean(rocks[0], rock) <= epsilon]

Теперь мы сравниваем количество соседей с min_points, чтобы определить, находится ли rocks[0] в плотной области пространства.

Листинг 18. Проверка плотности rocks[0]

num_neighbors = len(neighbor_indices)
 print(f"The rock at index 0 has {num_neighbors} neighbors.")
  
 if num_neighbors >= min_points:
     print("It lies in a dense region.")
 else:
     print("It does not lie in a dense region.")
 The rock at index 0 has 40 neighbors.
 It lies in a dense region.

Камень с индексом 0 находится в плотной области пространства. Соседи rocks[0] также разделяют эту плотную область космоса? Это сложный вопрос. В конце концов, возможно, что каждый сосед имеет менее min_points собственных соседей. Согласно нашему строгому определению плотности, мы не будем считать этих соседей плотными точками. Однако это привело бы к нелепой ситуации, когда плотная область состоит только из одной точки: rocks[0]. Мы можем избежать таких абсурдных результатов, обновив наше определение плотности. Формально определим плотность следующим образом:

Если точка находится на расстоянии epsilon от min_point соседей, то эта точка находится в плотной области пространства.
Каждый сосед точки в плотной области пространства также группируется в этом пространстве.

Основываясь на нашем обновленном определении, мы можем объединить rocks[0] и его соседей в один плотный кластер.

Листинг 19. Создание плотного кластера

dense_region_indices = [0] + neighbor_indices
 dense_region_cluster = [rocks[i] for i in dense_region_indices]
 dense_cluster_size = len(dense_region_cluster)
 print(f"We found a dense cluster containing {dense_cluster_size} rocks")
 We found a dense cluster containing 41 rocks

Камень с индексом 0 и его соседи образуют единый плотный кластер из 41 элемента. Принадлежат ли какие-либо соседи соседей к плотной области пространства? Если да, то по нашему обновленному определению эти породы также относятся к плотному скоплению. Таким образом, анализируя дополнительные соседние точки, мы можем расширить размер dense_region_cluster.

Листинг 20. Расширение плотного кластера

dense_region_indices = set(dense_region_indices) ❶
 for index in neighbor_indices:
     point = rocks[index]
     neighbors_of_neighbors = [i for i, rock in enumerate(rocks)
                               if euclidean(point, rock) <= epsilon]
     if len(neighbors_of_neighbors) >= min_points:
         dense_region_indices.update(neighbors_of_neighbors)
  
 dense_region_cluster = [rocks[i] for i in dense_region_indices]
 dense_cluster_size = len(dense_region_cluster)
 print(f"We expanded our cluster to include {dense_cluster_size} rocks")
 We expanded our cluster to include 781 rocks

❶ Преобразует индексы плотности_региона в набор. Это позволяет нам обновлять набор с помощью дополнительных индексов, не беспокоясь о дубликатах.

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

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

Посмотрите часть 3 здесь. Спасибо за прочтение.

Кластеризация данных в группы, часть 2

СТАТЬЯ