Наиболее часто используемый неконтролируемый алгоритм кластеризации

Фон

Каждый день мы генерируем примерно 2,5 квинтиллиона байт данных. Эти данные принимают форму символов, чисел, текста, изображений, голоса и т. д. Неудивительно, что большинство этих данных не имеют меток, а полезные идеи скрыты под горой данных. Кластеризация – это метод обучения без учителя, который широко используется для поиска групп точек данных (называемых кластерами) со схожими характеристиками без необходимости использования существующих размеченных данных. .

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

# 1: Что такое K-средние?

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

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

  • Внутрикластерная дисперсия (также известная как функция квадрата ошибки или сумма квадратов в пределах (SSW) или ошибка суммы квадратов (SSE)) используется для количественной оценки внутренней согласованности. Он определяется как сумма квадратов расстояний между средней точкой (называемой Centroid) и каждой точкой кластера. Чем меньше значение, тем лучше кластеризация.

  • Межкластерная дисперсия (также известная как сумма квадратов между (SSB)) используется для количественной оценки внешнего разделения. Он определяется как сумма квадратов расстояний между глобальной средней точкой и каждым центроидом. Чем больше значение, тем лучше кластеризация.

На практике нам нужно только минимизировать внутрикластерную дисперсию, потому что минимизация SSW (суммы квадратов внутри кластера) обязательно максимизирует SSB (сумма квадратов между кластерами)

Давайте использовать простой пример, чтобы доказать это. В следующем примере мы хотели бы создать кластеры на основе значений баллов. Если мы просто сгруппируем первые три наблюдения в группу 1, а последние три наблюдения в группу 2. Мы получим средний балл 25 для группы 1 и 16 для группы 2. Мы знаем, что глобальное среднее значение (20,5) всегда остается одним и тем же независимо от того, как создаются кластеры. Таким образом, SST (сумма квадратов расстояния между каждой точкой и глобальной средней точкой) также всегда будет оставаться неизменной. Математически нетрудно доказать SST = SSW + SSB. Таким образом, нахождение кластеров, которые минимизируют SSW, будет косвенно максимизировать SSB.

# 2: Как работает кластеризация K-средних?

Шаг 1. Инициализируйте центроиды кластера, случайным образом выбрав K начальных точек.

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

Шаг 3: Обновите центроиды кластера. Центроид вычисляется как среднее значение точек данных в кластере. Обновленные центроиды могут быть или не быть фактическими точками данных. Это было бы совпадением, если бы это было так.

Шаг 4: Повторяйте шаги 2–3 (назначение каждой точки данных новым центроидам и обновление центроидов кластера), пока не будет выполнено одно из условий остановки.

  • Обновленные центроиды остаются такими же, как и в предыдущей итерации (это идеальная ситуация, но на практике это может занять слишком много времени)
  • SSE не улучшился как минимум на x %
  • Достигнуто максимальное количество итераций (выбирайте максимальное количество итераций с умом, иначе у нас будут плохие кластеры).

# 3: Как предварительно обработать необработанные данные для K-средних?

K-Means использует измерения на основе расстояния (например, евклидово расстояние), чтобы вычислить, насколько каждая точка данных похожа на центроиды, используя значения всех функций. Эти функции обычно принимают значения в несопоставимых единицах (например, валюта в долларах, вес в кг, температура в градусах Фаренгейта). Для получения достоверного результата рекомендуется стандартизировать исходные данные. Мы можем преобразовать необработанные данные так, чтобы они имели среднее значение, равное нулю, и стандартное отклонение, равное единице, чтобы все функции имели равные веса.

№ 4: Как выбрать значение K в K-Means?

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

Метод локтя: он использует SSE (также известный как инерция кластера) для оценки качества разделения. Затем мы создаем локтевой график SSE для значений K в диапазоне от 2 до N (вы можете установить значение N для своего исследования). По мере увеличения K соответствующий SSE будет уменьшаться. Мы будем наблюдать компромисс между K и SSE (мы хотим, чтобы SSE был низким, сохраняя при этом разумное значение K). Обычно мы выбираем оптимальное значение K, когда видим, что SSE начинает сглаживаться и принимает форму локтя.

Анализ силуэта. Он использует Коэффициент силуэта для оценки качества разделения. Коэффициент силуэта рассчитывается как

S(i) — коэффициент силуэта для заданной точки данных. a(i) — среднее расстояние между данной точкой данных и всеми другими точками данных в том же кластере. b(i) — среднее расстояние между данной заданной точкой данных и всеми точками данных из ближайшего кластера. S(i) может варьироваться от -1 до 1.

  • если S(i) = 1, это означает, что эта точка данных находится близко к точкам в том же кластере и далеко от соседнего кластера.
  • если S(i) = 0, это означает, что эта точка данных находится вблизи границы своего кластера.
  • если S(i) = -1, это означает, что эта точка данных назначена неправильному кластеру.

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

Индекс Дэвиса-Булдина. Он использует индекс Дэвиса-Булдина для оценки качества разделения. Индекс Дэвиса-Булдинавычисляется как

D(i, j) — это индекс Дэвиса-Булдина для данной пары кластеров (например, кластеров i и j). d(i) и d(j) — среднее расстояние между каждой точкой и ее центром тяжести в кластере i и кластере j соответственно. d(i, j) — расстояние между центроидами кластеров i и j.

Для данного кластера мы вычислим индекс Дэвиса-Булдина между ним и всеми другими кластерами. Затем мы берем максимальный индекс Дэвиса-Булдина для этого кластера. В конце мы вычисляем окончательный индекс Дэвиса-Булдина как среднее этих максимальных значений. Затем мы вычисляем индекс Дэвиса-Булдина для значений K в диапазоне от 2 до N. Чем меньше индекс Дэвиса-Булдина, чем дальше эти кластеры, тем лучше кластеризация.

# 5: Как выбрать отправную точку для K-средних?

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

Существует расширенный метод инициализации, такой как K-Means++, который позволяет преодолеть проблему застревания в плохом локальном оптимуме и улучшить качество кластеризации. Интуиция проста. Мы выберем начальные центроиды, которые находятся далеко друг от друга, чтобы с большей вероятностью выбрать точки из разных кластеров. K-Means++ можно реализовать, выполнив следующие шаги.

  • Шаг 1: мы случайным образом выбираем точку данных в качестве первого центроида.
  • Шаг 2: Мы вычисляем расстояние между оставшимися точками с ближайшим центром тяжести.
  • Шаг 3: Мы выбираем следующий центроид так, чтобы вероятность выбора данной точки в качестве центроида была пропорциональна расстоянию между этой данной точкой и ближайшим к ней выбранным центроидом. Другими словами, чем дальше точка находится от выбранных центроидов, тем больше вероятность того, что она будет выбрана в качестве следующего центроида.
  • Повторяйте шаги 2–3, пока не будут выбраны K центроидов.

# 6: Как реализовать кластеризацию K-средних в Python?

В следующем примере я реализую кластеризацию K-средних для набора данных Iris в Python. Набор данных Iris включает 4 характеристические переменные (например, «Длина чашелистика», «Ширина чашелистика», «Длина лепестка», «Ширина лепестка») и 1 переменную, описывающую вид цветка ириса (например, Setosa, Versicolor, Virginica) .

from sklearn.preprocessing import StandardScaler
import pandas as pd
import matplotlib.pyplot as plt
import matplotlib.cm as cm
import seaborn as sns
from sklearn.cluster import KMeans
from sklearn.metrics import davies_bouldin_score, silhouette_score, silhouette_samples
import numpy as np
df = pd.read_csv("https://archive.ics.uci.edu/ml/machine-learning-databases/iris/iris.data", names = ['SepalLength', 'SepalWidth', 'PetalLength', 'PetalWidth', 'Species'])
# standardize the data to have a mean of zero and a standard deviation of one
df.iloc[:,:4] = StandardScaler().fit_transform(df.iloc[:,:4])
# Exploratory Data Analysis
sns.pairplot(df, diag_kind= 'kde')
sns.pairplot(df, hue="Species", diag_kind= 'kde')

На рисунке 1 мы можем видеть разделение точек данных. Мы надеемся, что сможем получить результаты, максимально приближенные к рисунку 2, после применения кластеризации K-средних.

Мы будем использовать алгоритм «KMeans» из библиотеки «sklearn» на Python. «n_clusters» указывает количество кластеров, которые необходимо сформировать. «max_iter» указывает максимальное количество итераций, выполненных за один прогон. «n_init» указывает, сколько раз K-Means будет запускаться с разными наборами начальных точек. init = «random|k-means++» указывает, используется ли метод случайной инициализации или инициализация K-Means++. «random_state» используется для обеспечения воспроизводимости результата.

Чтобы вычислить SSE, мы можем использовать «.inertia_» из вывода K-Means. «davies_bouldin_score» и «silhouette_score» используются для расчета индекса Дэвиса-Булдина и оценки силуэта соответственно.

x = df.iloc[:,:4]
sse, db, slc = {}, {}, {}
for k in range(2, 10):
    kmeans = KMeans(n_clusters = k, max_iter = 1000, n_init = 10, init = 'k-means++', random_state=123).fit(x)
    clusters = kmeans.labels_
    sse[k] = kmeans.inertia_
    db[k] = davies_bouldin_score(x, clusters)
    slc[k] = silhouette_score(x, clusters)

Метод локтя. На рисунке 3 показан график SSE с количеством кластеров. Этот график предполагает, что локоть сформирован со значением K около 3–5. После K=5 SSE начинает медленно уменьшаться.

plt.figure(figsize=(8, 6))
plt.plot(list(sse.keys()), list(sse.values()), marker='o')
plt.xlabel('Number of Clusters', fontsize=24)
plt.ylabel('SSE', fontsize=24)
plt.show()

Анализ силуэта. На рисунке 4 показан график индекса силуэта с количеством кластеров. Этот график предполагает, что высокий индекс силуэта появляется при более низком значении K (например, 2, 3).

plt.figure(figsize=(8, 6))
plt.plot(list(slc.keys()), list(slc.values()), marker='o')
plt.xlabel('Number of Clusters', fontsize=24)
plt.ylabel('Silhouette Score', fontsize=24)
plt.show()

Индекс Дэвиса-Булдина. На рисунке 5 показан график индекса Дэвиса-Булдина с количеством кластеров. Этот график также предполагает, что низкий индекс Дэвиса-Булдина появляется при более низком значении K (например, 2, 3).

plt.figure(figsize=(8, 6))
plt.plot(list(db.keys()), list(db.values()), marker='o')
plt.xlabel('Number of Clusters', fontsize=24)
plt.ylabel('Davies-Bouldin Values', fontsize=24)
plt.show()

Силуэтная диаграмма. Еще один информативный график, который мы можем создать для определения оптимального значения K, — силуэтная диаграмма. Он отображает коэффициенты силуэта для всех точек в разных кластерах. Диаграмма включает форму ножа для каждого кластера. Ширина представляет коэффициент силуэта для каждой точки. Высота представляет количество точек в данном кластере. Мы можем выбрать оптимальное K по следующим критериям.

  • Средний индекс силуэта высокий.
  • Кластеры примерно сбалансированы, т. Е. Кластеры имеют примерно одинаковое количество точек.
  • Большинство точек имеют более высокие коэффициенты силуэта, чем средний индекс силуэта.

На рисунке 6 K=2, 3 имеют относительно более высокий индекс силуэта. Но K=3 имеет более сбалансированные кластеры. Следовательно, 3, скорее всего, будет оптимальным значением K.

def make_Silhouette_plot(X, n_clusters):
    plt.xlim([-0.1, 1])
    plt.ylim([0, len(X) + (n_clusters + 1) * 10])
clusterer = KMeans(n_clusters=n_clusters, max_iter = 1000, n_init = 10, init = 'k-means++', random_state=10)
    cluster_labels = clusterer.fit_predict(X)
    silhouette_avg = silhouette_score(X, cluster_labels)
    print(
        "For n_clusters =", n_clusters,
        "The average silhouette_score is :", silhouette_avg,
    )
# Compute the silhouette scores for each sample
    sample_silhouette_values = silhouette_samples(X, cluster_labels)
y_lower = 10
    for i in range(n_clusters):
        ith_cluster_silhouette_values = sample_silhouette_values[cluster_labels == i]
        ith_cluster_silhouette_values.sort()
        size_cluster_i = ith_cluster_silhouette_values.shape[0]
        y_upper = y_lower + size_cluster_i
        color = cm.nipy_spectral(float(i) / n_clusters)
        plt.fill_betweenx(
            np.arange(y_lower, y_upper),
            0,
            ith_cluster_silhouette_values,
            facecolor=color,
            edgecolor=color,
            alpha=0.7,
        )
plt.text(-0.05, y_lower + 0.5 * size_cluster_i, str(i))
        y_lower = y_upper + 10
plt.title(f"The Silhouette Plot for n_cluster = {n_clusters}", fontsize=26)
    plt.xlabel("The silhouette coefficient values", fontsize=24)
    plt.ylabel("Cluster label", fontsize=24)
    plt.axvline(x=silhouette_avg, color="red", linestyle="--")
    plt.yticks([])  
    plt.xticks([-0.1, 0, 0.2, 0.4, 0.6, 0.8, 1])
    
range_n_clusters = [2, 3, 4, 5]
for n_clusters in range_n_clusters:
    make_Silhouette_plot(x, n_clusters)   
    plt.savefig('Silhouette_plot_{}.png'.format(n_clusters))
    plt.close()

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

kmeans = KMeans(n_clusters = 3, max_iter = 1000, n_init = 10, init = 'k-means++', random_state=123).fit(x)
clusters = kmeans.labels_
x['K-Means Predicted'] = clusters
sns.pairplot(x, hue="K-Means Predicted", diag_kind= 'kde')

# 7: Каковы преимущества и недостатки K-средних?

K-Means — наиболее часто используемый алгоритм кластеризации, потому что его очень легко реализовать и интерпретировать. Есть только один гиперпараметр (значение K) для настройки. Это эффективный инструмент, который можно применять практически ко всем типам данных.

Однако K-Means имеет ряд очевидных недостатков. Он предполагает

  • Различные кластеры имеют разные центроиды, которые находятся далеко друг от друга.
  • Если точка (A) находится дальше от данного центроида, чем точка (B), то точка (A) с меньшей вероятностью принадлежит к данному кластеру, чем точка (B)

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

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

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

Спасибо за чтение !!!

Если вам понравилась эта статья и вы хотите Купить мне кофе, нажмите нажмите здесь.

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