Рубрики
Без рубрики

K-Означает Кластеризацию с помощью Scikit-Learn

Автор оригинала: Scott Robinson.

K-Означает Кластеризацию с помощью Scikit-Learn

Вступление

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

Алгоритм K-средних начинается с случайного выбора значения центроида для каждого кластера. После этого алгоритм итеративно выполняет три шага: (i) Находит евклидово расстояние между каждым экземпляром данных и центроидами всех кластеров; (ii) Присваивает экземпляры данных кластеру центроида с ближайшим расстоянием; (iii) Вычисляет новые значения центроида на основе средних значений координат всех экземпляров данных из соответствующего кластера.

Простой Пример

Давайте попробуем посмотреть, как работает алгоритм K-means на примере ручной работы, прежде чем реализовывать его в Scikit-Learn. Для реализации алгоритма кластеризации K-means в Scikit-Learn требуется три строки кода. Однако, чтобы понять, как это на самом деле работает, давайте сначала решим проблему кластеризации с помощью кластеризации K-средних “на бумаге”.

Предположим, что у нас есть набор следующих двумерных экземпляров данных с именем D .

D = { (5,3), (10,15), (15,12), (24,10), (30,45), (85,70), (71,80), (60,78), (55,52), (80,91) }

Мы хотим разделить эти данные на два кластера, C1 и C2, основываясь на сходстве между точками данных.

Первым шагом является случайная инициализация значений центроидов обоих кластеров. Назовем центроиды кластеров C1 и C2 как c1 и c2 и инициализируем их значениями первых двух точек данных, т. е. (5, 3) и (10, 15).

Теперь мы должны начать итерации.

Итерация 1

1 (5,3) С1 0.00 13.00
2 (10,15) С2 13.00 0.00
3 (15,12) С2 13.45 5.83
4 (24,10) С2 20.24 14.86
5 (30,45) С2 48.87 36.00
6 (85,70) С2 104.35 93.00
7 (71,80) С2 101.41 89.00
8 (60,78) С2 93.00 80.00
9 (55,52) С2 70.00 58.00
10 (80,91) С2 115.52 103.32

В приведенной выше таблице второй столбец содержит все точки данных. Третий столбец содержит евклидово расстояние между всеми точками данных и центроидом c1 . Точно так же четвертый столбец содержит расстояние между центроидом c2 и точками данных. Наконец, в пятом столбце мы показываем, какому кластеру назначена точка данных на основе евклидова расстояния между двумя центроидами кластера. Например, посмотрите на третью точку данных (15, 12). Он имеет расстояние 13,45 единицы от c1 в то время как расстояние 5,83 единицы от c2 ; поэтому он был сгруппирован в C2.

После назначения точек данных соответствующим кластерам следующим шагом является вычисление новых значений центроидов. Эти значения вычисляются путем нахождения средних значений координат точек данных, принадлежащих определенному кластеру.

Для кластера C1 в настоящее время существует только одна точка, т. е. (5,3), поэтому среднее значение координат остается прежним, и новое значение центроида для c1 также будет (5,3).

Для C2 в настоящее время существует 9 точек данных. Мы называем координаты точек данных как x и y . Новое значение для x координаты центроида c2 может быть вычислено путем определения среднего значения x координат всех 9 точек, принадлежащих кластеру C2, как указано ниже:

c2(x) = (10 + 15 + 24 + 30 + 85 + 71 + 60 + 55 + 80) / 9 = 47.77

Новое значение для y координаты центроида c2 может быть вычислено путем определения среднего значения всех y координат всех 9 точек, принадлежащих кластеру C2.

c2(y) = (15 + 12 + 10 + 45 + 70 + 80 + 78 + 52 + 91) / 9 = 50.33

Обновленное значение центроида для c2 теперь будет равно {47.77, 50.33}.

Для следующей итерации будут использоваться новые значения центроида для c1 и c2 , и весь процесс будет повторен. Итерации продолжаются до тех пор, пока значения центроида не перестанут обновляться. Следующие итерации следующие:

Итерация 2

1 (5,3) С1 0.00 63.79
2 (10,15) С1 13.00 51.71
3 (15,12) С1 13.45 50.42
4 (24,10) С1 20.24 46.81
5 (30,45) С2 48.87 18.55
6 (85,70) С2 104.35 42.10
7 (71,80) С2 101.41 37.68
8 (60,78) С2 93.00 30.25
9 (55,52) С2 70.00 7.42
10 (80,91) С2 115.52 51.89
c1(x) = (5, 10, 15, 24) / 4 = 13.5
c1(y) = (3, 15, 12, 10) / 4 = 10.0

Обновлено c1 будет (13.5, 10.0).

c2(x) = (30 + 85 + 71 + 60 + 55 + 80) / 6 = 63.5
c2(y) = (45 + 70 + 80 + 78 + 52 +91) / 6 = 69.33

Обновлено c2 будет (63.5, 69.33).

Итерация 3

1 (5,3) С1 11.01 88.44
2 (10,15) С1 6.10 76.24
3 (15,12) С1 2.50 75.09
4 (24,10) С1 10.50 71.27
5 (30,45) С1 38.69 41.40
6 (85,70) С2 93.33 21.51
7 (71,80) С2 90.58 13.04
8 (60,78) С2 82.37 9.34
9 (55,52) С2 59.04 19.30
10 (80,91) С2 104.80 27.23
c1(x) = (5, 10, 15, 24, 30) / 5 = 16.8
c1(y) = (3, 15, 12, 10, 45) / 5 = 17.0

Обновлено c1 будет (16.8, 17.0).

c2(x) = (85 + 71 + 60 + 55 + 80) / 5 = 70.2
c2(y) = (70 + 80 + 78 + 52 + 91) / 5 = 74.2

Обновлено c2 будет (70.2, 74.2).

Итерация 4

1 (5,3) С1 18.30 96.54
2 (10,15) С1 7.08 84.43
3 (15,12) С1 5.31 83.16
4 (24,10) С1 10.04 79.09
5 (30,45) С1 30.95 49.68
6 (85,70) С2 86.37 15.38
7 (71,80) С2 83.10 5.85
8 (60,78) С2 74.74 10.88
9 (55,52) С2 51.80 26.90
10 (80,91) С2 97.31 19.44
c1(x) = (5, 10, 15, 24, 30) / 5 = 16.8
c1(y) = (3, 15, 12, 10, 45) / 5 = 17.0

Обновлено c1 будет (16.8, 17.0).

c2(x) = (85 + 71 + 60 + 55 + 80) / 5 = 70.2
c2(y) = (70 + 80 + 78 + 52 + 91) / 5 = 74.2

Обновлено c2 будет (70.2, 74.2).

В конце четвертой итерации обновленные значения C1 и C2 остаются такими же, как и в конце третьей итерации. Это означает, что данные больше не могут быть кластеризованы. c1 и c2 являются центроидами для C1 и C2. Для классификации новой точки данных вычисляется расстояние между точкой данных и центроидами кластеров. Точка данных назначается кластеру, центроид которого находится ближе всего к точке данных.

K-означает кластеризацию с помощью Scikit-Learn

Теперь, когда мы знаем, как на самом деле работает алгоритм кластеризации K-средних, давайте посмотрим, как мы можем реализовать его с помощью Scikit-Learn.

Для запуска следующего скрипта вам понадобятся библиотеки matplotlib, numpy и scikit-learn. Инструкции по загрузке и установке этих библиотек см. по следующим ссылкам.

Импорт библиотек

Давайте начнем наш скрипт с первого импорта необходимых библиотек:

import matplotlib.pyplot as plt
%matplotlib inline
import numpy as np
from sklearn.cluster import KMeans

Подготовка Данных

Следующим шагом является подготовка данных, которые мы хотим сгруппировать. Давайте создадим массив numpy из 10 строк и 2 столбцов. Эта строка содержит те же точки данных, которые мы использовали для нашего ручного примера кластеризации K-средних в предыдущем разделе. Мы создаем массив точек данных numpy , потому что библиотека Scikit-Learn может работать с входными данными типа numpy array, не требуя предварительной обработки.

X = np.array([[5,3],
     [10,15],
     [15,12],
     [24,10],
     [30,45],
     [85,70],
     [71,80],
     [60,78],
     [55,52],
     [80,91],])

Визуализируйте данные

Вы можете видеть, что это те же самые точки данных, которые мы использовали в предыдущем примере. Давайте построим эти точки и проверим, можем ли мы наблюдать какие-либо кластеры. Для этого выполните следующую строку:

plt.scatter(X[:,0],X[:,1], label='True Position')

Приведенный выше код просто строит все значения в первом столбце массива X против всех значений во втором столбце. График будет выглядеть так:

k-означает участок 1

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

Создание Кластеров

Чтобы создать кластер K-means с двумя кластерами, просто введите следующий сценарий:

kmeans = KMeans(n_clusters=2)
kmeans.fit(X)

Да, это всего лишь две строки кода. В первой строке вы создаете объект KMeans и передаете ему 2 в качестве значения параметра n_clusters . Далее вам просто нужно вызвать метод fit на k means и передать данные, которые вы хотите кластеризировать, что в данном случае является массивом X , который мы создали ранее.

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

print(kmeans.cluster_centers_)

Выход будет представлять собой двумерный массив формы 2 х 2.

[[ 16.8  17. ]
 [ 70.2  74.2]]

Здесь первая строка содержит значения координат первого центроида , т. е. (16.8, 17), а вторая строка содержит значения координат другого центроида, т. е. (70.2, 74.2). Вы можете видеть, что эти значения аналогичны тем, которые мы рассчитали вручную для центроидов c1 и c2 в последнем разделе. Короче говоря, наш алгоритм работает отлично.

Чтобы просмотреть метки для точки данных, выполните следующий сценарий.

print(kmeans.labels_)

Выход представляет собой одномерный массив из 10 элементов, соответствующих кластерам, назначенным нашим 10 точкам данных.

[0 0 0 0 0 1 1 1 1 1]

Здесь первые пять точек были сгруппированы вместе, и последние пять точек были сгруппированы. Здесь 0 и 1 просто используются для представления идентификаторов кластеров и не имеют никакого математического значения. Если бы было три кластера, то третий кластер был бы представлен цифрой 2 .

Давайте снова построим точки данных на графике и визуализируем, как данные были сгруппированы. На этот раз мы построим данные вместе с их назначенной меткой, чтобы мы могли различать кластеры. Выполните следующий сценарий:

plt.scatter(X[:,0],X[:,1], c=kmeans.labels_, cmap='rainbow')

Здесь мы строим первый столбец массива X против второго столбца, однако в этом случае мы также передаем kmeans.labels_ в качестве значения для параметра c , соответствующего меткам. Параметр cmap='rainbow' передается для выбора типа цвета для различных точек данных. Выходной график должен выглядеть следующим образом:

k-означает участок 2

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

Теперь давайте выполним алгоритм K-средних с тремя кластерами и посмотрим выходной график.

k-означает участок 3

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

Теперь давайте построим точки вместе с координатами центроида каждого кластера, чтобы увидеть, как положение центроида влияет на кластеризацию. Снова мы будем использовать три кластера, чтобы увидеть эффект центроидов. Выполните следующий сценарий, чтобы нарисовать график:

plt.scatter(X[:,0], X[:,1], c=kmeans.labels_, cmap='rainbow')
plt.scatter(kmeans.cluster_centers_[:,0] ,kmeans.cluster_centers_[:,1], color='black')

Здесь, в этом случае, мы строим точки данных в цветах радуги, а центроиды-в черном. Вывод выглядит следующим образом:

k-означает участок 4

В случае трех кластеров две точки посередине (отображаются красным цветом) имеют расстояние ближе к центроиду посередине (отображается черным цветом между двумя красными) по сравнению с центроидами внизу слева или вверху справа. Однако если бы было два кластера, то в центре не было бы центроида, поэтому красные точки должны были бы быть сгруппированы вместе с точками в нижнем левом или верхнем правом кластерах.

Ресурсы

Хотите узнать больше о Scikit-Learn и других полезных алгоритмах машинного обучения? Я бы порекомендовал проверить некоторые более подробные ресурсы, например онлайн-курс:

Хотя изучение сообщений в блогах, подобных этому, – отличное начало, лично я склонен лучше учиться с помощью визуальных эффектов, ресурсов и объяснений из видеокурсов, подобных тем, что приведены выше.

Вывод

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

Вы когда-нибудь использовали кластеризацию K-средних в приложении? Если да, то зачем? Дайте нам знать в комментариях!