Кластеризация K-средних с помощью Scikit-Learn в Python
Кластеризация K-средних – один из наиболее широко используемых алгоритмов неконтролируемого машинного обучения, который формирует кластеры данных на основе сходства между экземплярами данных. Для работы этого конкретного алгоритма необходимо заранее определить количество кластеров. K в K-средних означает количество кластеров.
- (i) Найти евклидово расстояние между каждым экземпляром данных и центроидами всех кластеров.
- (ii) Назначьте экземпляры данных кластеру центроида с ближайшим расстоянием.
- (iii) Вычислить новые значения центроидов на основе средних значений координат всех экземпляров данных из соответствующего кластера.
Пример
Давайте попробуем увидеть, как работает алгоритм K-средних, на собственном примере, прежде чем реализовывать алгоритм в Scikit-Learn. Для реализации алгоритма кластеризации K-средних в Scikit-Learn требуется три строки кода. Однако, чтобы понять, как это работает на самом деле, давайте сначала решим проблему с помощью K-средних «на бумаге».
Предположим, у нас есть набор следующих двухмерных экземпляров данных с именем D.
Мы хотим разделить эти данные на два кластера, C1 и C2, на основе сходства между точками данных.
Первым шагом является случайная инициализация значений центроидов обоих кластеров. Назовем центроиды кластеров C1 и C2 c1 и c2 и инициализируем их значениями первых двух точек данных, то есть (5, 3) и (10, 15).
Теперь нужно приступить к итерациям.
Итерация 1
| S.No | Точки данных | Евклидово расстояние от центроида скопления c1 = (5,3) | Евклидово расстояние от центроида скопления c2 = (10,15) | Назначенный кластер |
|---|---|---|---|---|
| 1 | (5,3) | 0 | 13 | C1 |
| 2 | (10,15) | 13 | 0 | C2 |
| 3 | (15,12) | 13,45 | 5,83 | C2 |
| 4 | (24,10) | 20,24 | 14,86 | C2 |
| 5 | (30,45) | 48,87 | 36 | C2 |
| 6 | (85,70) | 104,35 | 93 | C2 |
| 7 | (71,80) | 101,41 | 89 | C2 |
| 8 | (60,78) | 93 | 80 | C2 |
| 9 | (55,52) | 70 | 58 | C2 |
| 10 | (80,91) | 115,52 | 103,32 | C2 |
В приведенной выше таблице второй столбец содержит все точки данных. Третий столбец содержит евклидово расстояние между всеми точками данных и центроидом 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 теперь будет .
Для следующей итерации будут использоваться новые значения центроидов для c1 и c2, и весь процесс будет повторен. Итерации продолжаются до тех пор, пока значения центроидов не перестанут обновляться. Следующие итерации выглядят следующим образом.
Итерация 2
| S.No | Точки данных | Евклидово расстояние от центроида скопления c1 = (5,3) | Евклидово расстояние от центра скопления c2 = (47,77,50,33) | Назначенный кластер |
|---|---|---|---|---|
| 1 | (5,3) | 0 | 63,79 | C1 |
| 2 | (10,15) | 13 | 51,71 | C1 |
| 3 | (15,12) | 13,45 | 50,42 | C1 |
| 4 | (24,10) | 20,24 | 46,81 | C1 |
| 5 | (30,45) | 48,87 | 18,55 | C2 |
| 6 | (85,70) | 104,35 | 42,10 | C2 |
| 7 | (71,80) | 101,41 | 37,68 | C2 |
| 8 | (60,78) | 93 | 30,25 | C2 |
| 9 | (55,52) | 70 | 7,42 | C2 |
| 10 | (80,91) | 115,52 | 51,89 | C2 |
c1(x) = (5, 10, 15, 24) / 4 = 13.5 c1(y) = (3, 15, 12, 10) / 4 = 10.0
c2(x) = (30 + 85 + 71 + 60 + 55 + 80) / 6 = 63.5 c2(y) = (45 + 70 + 80 + 78 + 52 +91) / 6 = 69.33
Итерация 3
| S.No | Точки данных | Евклидово расстояние от центра скопления c1 = (13,5,10) | Евклидово расстояние от центра скопления c2 = (63,5,69,33) | Назначенный кластер |
|---|---|---|---|---|
| 1 | (5,3) | 11.01 | 88,44 | C1 |
| 2 | (10,15) | 6.10 | 76,24 | C1 |
| 3 | (15,12) | 2,5 | 75,09 | C1 |
| 4 | (24,10) | 10,5 | 71,27 | C1 |
| 5 | (30,45) | 38,69 | 41,40 | C1 |
| 6 | (85,70) | 93,33 | 21,51 | C2 |
| 7 | (71,80) | 90,58 | 13.04 | C2 |
| 8 | (60,78) | 82,37 | 9,34 | C2 |
| 9 | (55,52) | 59,04 | 19.30 | C2 |
| 10 | (80,91) | 104,80 | 27,23 | C2 |
c1(x) = (5, 10, 15, 24, 30) / 5 = 16.8 c1(y) = (3, 15, 12, 10, 45) / 5 = 17.0
c2(x) = (85 + 71 + 60 + 55 + 80) / 5 = 70.2 c2(y) = (70 + 80 + 78 + 52 + 91) / 5 = 74.2
Итерация 4
| S.No | Точки данных | Евклидово расстояние от центра скопления c1 = (16,8,17) | Евклидово расстояние от центра скопления c2 = (70,2,74,2) | Назначенный кластер |
|---|---|---|---|---|
| 1 | (5,3) | 18.30 | 96,54 | C1 |
| 2 | (10,15) | 7,08 | 84,43 | C1 |
| 3 | (15,12) | 5,31 | 83,16 | C1 |
| 4 | (24,10) | 10.04 | 79,09 | C1 |
| 5 | (30,45) | 30,95 | 49,68 | C1 |
| 6 | (85,70) | 86,37 | 15,38 | C2 |
| 7 | (71,80) | 83,10 | 5,85 | C2 |
| 8 | (60,78) | 74,74 | 10,88 | C2 |
| 9 | (55,52) | 51,80 | 26,90 | C2 |
| 10 | (80,91) | 97,31 | 19,44 | C2 |
c1(x) = (5, 10, 15, 24, 30) / 5 = 16.8 c1(y) = (3, 15, 12, 10, 45) / 5 = 17.0
c2(x) = (85 + 71 + 60 + 55 + 80) / 5 = 70.2 c2(y) = (70 + 80 + 78 + 52 + 91) / 5 = 74.2
В конце четвертой итерации обновленные значения C1 и C2 такие же, как и в конце третьей итерации. Это означает, что данные больше не могут быть кластеризованы. c1 и c2 – центроиды для C1 и C2. Чтобы классифицировать новую точку данных, вычисляется расстояние между точкой данных и центроидами кластеров. Точка данных назначается кластеру, центроид которого находится ближе всего к точке данных.
Кластеризация с помощью Scikit-Learn
Теперь, когда мы знаем, как на самом деле работает алгоритм кластеризации K-средних, давайте посмотрим, как мы можем реализовать его с помощью Scikit-Learn.
Начнем наш скрипт с импорта необходимых библиотек:
import matplotlib.pyplot as plt %matplotlib inline import numpy as np from sklearn.cluster import KMeans
Подготовка данных
Следующим шагом является подготовка данных, которые мы хотим кластеризовать. Давайте создадим массив из 10 строк и 2 столбцов. Строка содержит те же точки данных, которые мы использовали в нашем примере ручной кластеризации K-средних в последнем разделе. Мы создаем массив точек данных, потому что библиотека Scikit-Learn может работать с входными данными типа массивов без предварительной обработки.
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-средних то же самое или нет.
Создание кластеров
Чтобы создать кластер K-средних из двух кластеров, просто введите следующий скрипт:
kmeans = KMeans(n_clusters=2) kmeans.fit(X)
Да, это всего лишь две строчки кода. В первой строке вы создаете объект KMeans и передаете ему 2 в качестве значения параметра n_clusters. Затем вам просто нужно вызвать метод fit для kmeans и передать данные, которые вы хотите кластеризовать, в данном случае это массив X, который мы создали ранее.
Теперь посмотрим, какие значения центроидов алгоритм сгенерировал для конечных кластеров.
print(kmeans.cluster_centers_)
На выходе будет двумерный массив формы 2 x 2.
Здесь первая строка содержит значения для координат первого центроида, т.е. (16.8, 17), а вторая строка содержит значения для координат другого центроида, то есть (70.2, 74.2). Вы можете видеть, что эти значения аналогичны тем, которые мы вычислили вручную для центроидов c1 и c2 в предыдущем разделе.
Чтобы увидеть метки для точки данных, выполните следующий скрипт.
Результатом является одномерный массив из 10 элементов, соответствующих кластерам, назначенным нашим 10 точкам данных.
Здесь первые и последние пять точек сгруппированы вместе. Здесь 0 и 1 используются только для представления идентификаторов кластера и не имеют математического значения. Если бы кластеров было три, третий кластер был бы представлен цифрой 2.
Давайте снова нанесем точки данных на график и визуализируем, как данные были сгруппированы. На этот раз мы построим график данных вместе с присвоенной им меткой, чтобы мы могли различать кластеры. Выполните следующий скрипт:
plt.scatter(X[:,0],X[:,1], c=kmeans.labels_, cmap='rainbow')
Здесь мы сопоставляем первый столбец массива X со вторым столбцом, однако в этом случае мы также передаем kmeans.labels_ в качестве значения для параметра c, соответствующего меткам. Параметр cmap = ‘rainbow’ передается для выбора типа цвета для различных точек данных. Выходной график должен выглядеть так:
Как и ожидалось, первые пять точек в левом нижнем углу были сгруппированы вместе (отображаются синим цветом), а остальные точки в правом верхнем углу были сгруппированы вместе (отображаются красным цветом).
Теперь давайте выполним алгоритм K-средних с тремя кластерами и посмотрим на выходной график.
Вы можете видеть, что близкие друг к другу точки снова сгруппированы вместе.
Теперь давайте нанесем точки вместе с координатами центроида каждого кластера, чтобы увидеть, как положение центроида влияет на кластеризацию. Снова мы будем использовать три кластера, чтобы увидеть эффект центроидов. Выполните следующий скрипт, чтобы нарисовать график:
plt.scatter(X[:,0], X[:,1], c=kmeans.labels_, cmap='rainbow') plt.scatter(kmeans.cluster_centers_[:,0] ,kmeans.cluster_centers_[:,1], color='black')
В этом случае мы наносим точки данных в цвета радуги, а центроиды – в черный цвет. Результат выглядит так:
В случае трех кластеров две точки в середине (отображаются красным цветом) имеют расстояние ближе к центроиду в середине (отображается черным цветом между двумя красными) по сравнению с центроидами в нижнем левом или верхнем правом углу. Однако, если бы было два кластера, не было бы центроида в центре, поэтому красные точки должны были бы быть сгруппированы вместе с точками в нижнем левом или верхнем правом кластерах.
Заключение
Кластеризация K-средних – это простой, но очень эффективный алгоритм неконтролируемого машинного обучения для кластеризации данных. Он группирует данные на основе евклидова расстояния между точками данных. Алгоритм кластеризации K-средних имеет множество применений для группировки текстовых документов, изображений, видео и многого другого.