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

  • Примеры внутри кластера аналогичны (в данном случае мы говорим о высоком внутриклассовом сходстве).
  • Примеры в разных кластерах разные (в данном случае мы говорим о низком межклассовом сходстве)

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

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

Цели

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

Здесь мы будем работать с одним из простейших, но мощных методов кластеризации, методом K-средних. Помимо описания того, что делает K-means, мы собираемся построить модель, используя язык программирования Python с библиотекой Scikit-Learn. Сказав это, с этого момента я попытаюсь ответить на следующие вопросы, касающиеся кластеризации с помощью K-средних:

  1. Как выполнить кластерный анализ с использованием метода K-средних?
  2. Как найти оптимальное количество кластеров?
  3. Как определить подходящие функции?
  4. Зачем и когда нам нужно стандартизировать данные?
  5. Какие плюсы и минусы использования K-means?

Метод K-средних

Метод K-средних основан на двух важных математических концепциях: Расстояние и Центроид.

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

Алгоритм

Алгоритм K-средних делит набор из n выборок X на k непересекающихся кластеров cᵢ, i = 1, 2,…, k, каждый из которых описывается средним значением (центроид) μᵢ выборок в кластере. K-средство предполагает, что все k групп имеют одинаковую дисперсию.

Грубо говоря, алгоритм выполняет следующие шаги:

1. Choose the number (k) of clusters;
2. Specify the cluster seeds (define the initial position of the centroids);
3. Assign each point to a centroid based on its proximity (if the centroid α is the nearest centroid to the point p, then assign p to α, do this for all points;
4. Adjust the centroid (recalculate the position of each centroid based on the points assigned to them);
5. Repeat step 3 and 4, until achieving a stop criterion;
6. After achieve a stop criteria (commonly the pre-defined maximum number of iterations), end execution.

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

Центроиды представлены желтыми точками. Фиолетовые, красные и зеленые точки - это точки данных, и каждый цвет относится к одному из трех кластеров.

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

Каковы истинные намерения K-means?

Алгоритм K-средних решает следующую задачу минимизации:

Где k - количество кластеров, cᵢ - это набор точек, принадлежащих кластеру i, а μᵢ - это центроид класса, представленного cᵢ.

НЕ ПАНИКА!

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

Недостаток №1: количество кластеров.

Целевая функция кластеризации K-средних использует квадрат евклидова расстояния d (x, μⱼ). Его также называют инерцией или суммой квадратов внутри кластера. Основываясь на том, что вы читали выше, цель K-средних - минимизировать инерцию.

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

Этот удивительный результат должен нас порадовать, потому что мы достигли минимального нуля, другими словами, мы решили задачу минимизации!

Но нет смысла устанавливать количество кластеров равным количеству точек данных. Представьте себе тот же случай с тысячей точек данных!

Цель использования K-средних - выявить закономерности и разделить сходные данные, чтобы они соответствовали этим шаблонам. Итак, очевидно, что количество кластеров k всегда должно быть меньше количества выборок.

Математически, если k представляет количество кластеров, а n - количество точек данных, тогда k ‹n. Точно так же, если мы используем только один кластер, тогда все данные будут классифицироваться как принадлежащие этому уникальному классу, это еще одно бесполезное решение! Следовательно, 1 ‹k‹ n.

Недостаток 2: инициализация центроида.

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

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

Недостаток 3: нестандартизированные данные.

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

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

Следовательно, без какой-либо стандартизации алгоритм будет рассматривать только переменную цен. Например, возьмем два дома: А и Б.

  • Дом А стоит 280000 долларов США, имеет площадь 201 м² и 4 комнаты.
  • Дом B стоит 300000 долларов США, имеет площадь 250 м² и 4 комнаты.

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

Хорошо, теперь возникает проблема. Когда алгоритм вычисляет «расстояние» между элементами A и B до центроида, он понимает, что веса элементов для размера дома и количества комнат в нем значительно меньше, чем у характеристики стоимости.

Эта огромная разница в масштабе поставит под угрозу модель из-за вычисленного евклидова расстояния между объектами. Вам может быть интересно, будет ли ваша модель по-прежнему обеспечивать вывод. Да, это будет!

Что произойдет, так это то, что ваша модель покажет вам группы домов только на основе их цен. Например, такие кластеры можно назвать «дешевыми», «разумными» и «дорогими».

Реализация

Хорошо, теперь мы получили представление о том, как работает K-means. Давайте напишем код!

Получение данных

Перво-наперво. Перед кодированием K-средних нам нужны данные. В этом примере давайте создадим собственные искусственные образцы, похожие на точки, которые вы видели на анимации.

# Import the relevant packages
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
sns.set()
from sklearn.cluster import Kmeans
# Number of points of each cluster
MAXN = 40
# Normal distribution 
data = np.concatenate([1.25*np.random.randn(MAXN, 2), 
                   5 + 1.5*np.random.randn(MAXN, 2)])
data = np.concatenate([data, [8, 3] + 1.2*np.random.randn(MAXN, 2)])
df = pd.DataFrame(data={'x' : data[:,0], 'y' : data[:,1]})
plt.scatter(df['x'], df['y'])
plt.show()

Инициализация центроида

Теперь давайте разделим точки данных на три кластера (k = 3). Но перед этим мы должны инициализировать центроиды. Мы могли бы инициализировать их вручную, указав их координаты, но это повлияет на наши результаты. Давайте еще немного подумаем над этой проблемой.

Итак, как мы можем решить проблему инициализации?

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

Чтобы облегчить проблему локальных минимумов, вычисление K-средних, реализованное в библиотеке Scikit-Learn, часто выполняется несколько раз (метод Forgy) с разными инициализациями центроида.

Кроме того, одним из способов решения этой проблемы является схема инициализации k-means ++, реализованная в Scikit-Learn (используйте параметр init = ’kmeans ++’).

Этот параметр инициализирует центроиды (как правило) удаленными друг от друга, что, вероятно, приводит к лучшим результатам, чем случайная инициализация. Вам просто нужно позаботиться об инициализации, если вы используете другой пакет, отличный от Scikit-Learn.

Кластеризация

Наконец, мы можем реализовать код для K-means. Это так просто. См. Ниже:

kmeans = KMeans(init = 'k-means++', n_clusters = 3)
clusters = kmeans.fit_predict(df)
plt.scatter(df['x'],df['y'], c=clusters, cmap='rainbow')
plt.show()

Удивительный! Похоже, у нас получился хороший результат.

Здесь каждый кластер не имеет значения, но на реальных примерах вы сможете сказать, о чем каждый отдельный кластер.

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

Метод локтя

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

# drop the class column in order to have only the features in df
new_df = df.copy()
# empty list for inertia values
inertia = []
for i in range(1,10):
    # instantiating a kmeans model with i clusters
    # init=kmeans++ is default
    kmeans = KMeans(n_clusters=i)
    
    # fitting the model to the data
    kmeans.fit(new_df)
    
    # appending the inertia of the model to the list
    inertia.append(kmeans.inertia_)
    
    # Knowing from the data that we have three samples distributions
    # let's save the inertia for the case k=3
    if i == 3:
        elbow = kmeans.inertia_
# creating a list with the number of clusters
number_of_clusters = range(1,10)
plt.plot(number_of_clusters, inertia)
plt.plot(3, elbow, 'ro', label='Elbow')
plt.legend()
plt.xlabel('# of clusters')
plt.ylabel('Inertia')
plt.show()

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

Метод изгиба заключается в принятии количества кластеров, представляющих изгиб графа. Следовательно, идеальное количество кластеров для этой задачи - 3.

Говоря о стандартизации

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

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

Однако для случая, когда у нас много выбросов, лучше заменить стандартное отклонение межквартильного размаха, т.е. е. Q₃-Q₂. Таким образом мы избегаем существенного влияния выбросов на алгоритм.

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

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

K-means Плюсы и минусы

После всего, о чем мы до сих пор говорили, давайте подытожим плюсы и минусы использования K-means. Вы, наверное, уже догадались, кто они.

Плюсы

  1. Просто понять
  2. Быстро кластеризовать
  3. Широко доступен (есть несколько пакетов, реализующих K-means)
  4. Легко реализовать
  5. Всегда дает результат (тоже минус, так как может вводить в заблуждение)

Минусы

  1. Нам нужно выбрать количество кластеров (средство: метод локтя)
  2. он чувствителен к инициализации (средство: kmeans ++)
  3. Чувствительность к выбросам (способ устранения: удаление выбросов)
  4. Стандартизация

На данный момент это все :( Большое спасибо за чтение. Надеюсь, вам понравилось наше путешествие по пути метода кластеризации K-средних. Если вы хотите узнать больше по этой теме, я предоставил Jupyter Notebook с некоторая ценная дополнительная информация и другие примеры на моей странице GitHub по адресу https://github.com/alexandrehsd/Cluster-Analysis.

Буду признателен за ваши отзывы и советы по возможным улучшениям в следующих статьях. Пожалуйста, если есть, оставляйте их в комментариях! До свидания и удачной кластеризации! :)