Принцип KMeans, реализация и анализ

Резюме

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

1. Введение

Идея алгоритма KMeans уже давно переплетена исследователями во многих междисциплинарных областях, но первое его использование было предложено Ллойдом (1957, 1982) для кодирования импульсов модуляции.Более подробную информацию о KMeans можно найти в [ 2].В начале предложения KMeans это была NP-сложная задача, потому что ее наивный алгоритм включал проблемы комбинаторного взрыва, но Грей и Нойхофф [3] предложили очень эффективный эвристический алгоритм поиска, который может быстро сходиться к локальному оптимуму.

Во втором разделе этой статьи будут подробно описаны математические принципы KMeans (что необходимо) и реализовано на Python в соответствии с его основными принципами; в третьем разделе scikit-learn будет использоваться для создания набора тестовых наборов данных. , которые состоят из трех различных распределений Гаусса, а затем алгоритм KMeans, реализованный в разделе 2, будет применен к этому набору данных и сравнен с алгоритмом KMeans, представленным в scikit-learn, Наконец, будут обсуждаться недостатки KMeans и будут обсуждаться популярные в отрасли методы Улучшения Раздел IV представляет собой краткое изложение этой статьи.

2 Принцип и реализация

KMeans — это, по сути, метод кластеризации на основе центроида [5], целью которого являетсяВсе объекты в присвоеныкластеры $C_1, \cdot \cdot \cdot , C_k$ , так что для $1 \leqslant i , j \leqslant k , C_i \subseteq D$ и $C_i \cap C_j = \varnothing$ . Качество раздела оценивается с помощью метрики расстояния, т.е.

E = \sum^{k}_{j=1} \sum_{x \in C_j} dist(x, \mu_j) \qquad \qquad (2.1)

в $dist(\cdot,\cdot)$ - оцениваемая метрическая функция расстояния, и $\mu$ - центроид (средняя точка) кластера $\mu_j=\frac{1}{|C_j|} \sum_{x \in C_j} x$ , обычно метрикой расстояния, используемой традиционными KMeans, является евклидово расстояние (евклидово расстояние), тогдаВизуально это можно понять как все точки в наборе данных и $\mu$ Сумма квадратов ошибок, т.е.

E = \sum^{k}_{j=1} \sum_{x \in C_j} ||x-\mu_j||^2 \qquad \qquad (2.2)

Цель оптимизации состоит в том, чтобы сделать как можно меньше E. Было доказано, что перечисление всех делений в общем евклидовом пространстве может быть NP-трудной задачей, поэтому метод оптимизации изменен на эвристический поиск, Эта эвристика состоит из данных Назначение и обновление.

$DataAssignment(\cdot)$ ответственность за всеПо расчету $dist(\cdot,\cdot)的结果$ назначается ближайшему кластеру, возвращая каждыйкластерные маркеры.

$Update(\cdot)$ Затем он отвечает за все центроиды кластера в соответствии с меткой кластера текущего шага. $\mu_j$ Выполните внутрикластерное усреднение, возвращая обновленный $\mu_j^{'}$

Итерации непрерывно, пока $\mu_j$ Никаких изменений не происходит, т. е. сходится к локальному оптимуму.

Псевдокод показан на рисунке 1.

Рисунок 1: Псевдокод KMeans

Реализация Python выглядит следующим образом

def random_init_centroids(X, k):
    ids = np.random.choice(X.shape[0], k, replace=True)
    return X[ids]

def data_assignment(X, centroids):
    m = X.shape[0]
    ids = np.zeros((m, ))
    for i in range(m):
        V = X[i] - centroids
        V = np.dot(V, V.T)
        ids[i] = np.argmin(np.diag(V))
    return ids
    

def update(X, centroids, ids):
    K = centroids.shape[0]
    new_centroids = np.zeros(centroids.shape)
    for i in range(K):
        new_centroids[i] = np.sum(X[ids==i], axis=0) / \
                           np.size(np.where(ids==i))
    return new_centroids


def k_means(X, k, max_iter=500):
    # randomly initial centroids
    centroids = random_init_centroids(X, k)
    previous_centroids = centroids

    for i in range(max_iter):
        
        # data assignment
        ids = data_assignment(X, centroids)
        
        # plot each situation of iteration.
        plot_cluster(X, ids, ['o', 'x', '^'], ['r', 'g', 'b'],
                     centroids=centroids.tolist(),
                     title=f"Iteration {i+1}",
                     x_label="X1",
                     y_label="X2",
                     labels=['cluster 1', 'cluster 2', 'cluster 3'])
        plt.show()
        # update
        previous_centroids = centroids
        centroids = update(X, centroids, ids)
        
        if np.allclose(previous_centroids, centroids):
            print(f"k-mean finish at {i+1}")
            break
    
    return centroids

Для того, чтобы четко понимать изменения каждой итерации KMeans, добавлен код $plot\_cluster(\cdot)$ чтобы показать реальную кластеризацию.

Все примеры кода в этой статье находятся в приложении.

3 Анализ и улучшение

Чтобы проверить точность KMeans, реализованных в разделе 2, используйтеmake_blobsДля создания тестовых кластерных данных этот метод может генерировать изотропные гауссовские данные, что означает создание нескольких кластеров данных с одинаковым распределением.

from sklearn.datasets import make_blobs

real_centroids = [(-4, -4), (0, 0), (4, 4)]
X, y = make_blobs(n_samples=300, centers=real_centroids, n_features=2, random_state=42)

Примечание: разныеrandom_stateбудут производить разные точки данных.

Для облегчения проверки необходимо следующее (-4, -4), (0, 0), (4, 4) Для выборки данных центральной точки генерируются 100 для одной центральной точки. Пример ситуации для каждого кластера в исходном наборе данных показан на рисунке 2. Видно, что точка выброса, которая относительно близка к кластеру 3 (синий треугольник), создается в кластере 2 (зеленый x), поэтому эта точка очень мала. после запуска алгоритма KMeans можно отнести к кластеру 3.

Рисунок 2: Образец необработанных данных

3.1 Анализ результатов

Результат применения KMeans в исходном наборе данных показан на рисунке 3. Из-за нестабильности KMeans метки кластеров меняются местами, но все же видно, что выбросы исходного кластера 2 относятся к исходному кластеру 3 (это то есть текущий кластер 1, красные точки), результаты сходимости центроидов каждого кластера следующие:

array([[ 0.15868461,  0.0155145 ],
       [-4.10690785, -3.93685302],
       [ 3.92090405,  3.87351944]])

Можно видеть, что, хотя рассчитанные центроиды каждого кластера не могут сходиться к исходным центроидам (-4, -4), (0, 0), (4, 4) , но положения соответствующих центроидов очень близки. Причина такого явления в том, что KMeans будет сходиться к алгоритму локального минимума. При выборе начальной точки значение точки сходимости также будет другим, но оно будет быть бесконечно близким к действительному значению.

Рисунок 3: Результаты работы KMeans

Затем используйте предоставленный в scikit-learnKMeansЗапустите исходный набор данных и сравните его с алгоритмом KMeans, реализованным в этой статье.Код выглядит следующим образом:

from sklearn.cluster import KMeans

sk_kmeans = KMeans(n_clusters=3, random_state=42).fit(X)
print(sk_kmeans.cluster_centers_)

Результат выглядит следующим образом:

array([[ 0.15868461,  0.0155145 ],
       [ 3.92090405,  3.87351944],
       [-4.10690785, -3.93685302]])

Можно видеть, что это почти согласуется с результатами KMeans, полученными в этой статье.

3.2 Дефекты и улучшения KMeans

Хотя KMeans имеет простые математические принципы и очень широкий спектр приложений, вначале у него много недостатков.

нестабильный Результат работы KMeans очень зависит от выбора точки центроида инициализации.Один из хороших вариантов инициализации показан на рисунке 4, а плохой выбор инициализации показан на рисунке 5. близко, количество итераций будет больше, поэтому алгоритм станет очень нестабильным.Основным методом в отрасли является использованиеkmeans++Метод инициализации из [6], этот метод может ускорить сходимость KMeans с учетом глобальности, и KMeans, предоставленный в наборе инструментов scikit-learn, использует этот метод.

Рисунок 4: Хорошие результаты инициализации

Рисунок 5: Плохой результат инициализации

Ловушка локального оптимального решения В дополнение к тому, что KMeans зависит от выбора начальной точки, также очень легко попасть в локальную оптимальную точку.Например, центральные точки, возвращаемые двумя KMeans в 3.1 Анализ результатов после запуска, отличаются от установленных центральных точек. В реальном наборе данных влияние этого явления будет усиливаться, поэтому избавиться от локальной оптимальной точки можно двумя способами: один — постоянно заменять начальную центральную точку, чтобы она могла сходиться в разных направлениях, и затем взять лучший результат, а другой использовать коэффициент осцилляции, Когда он сходится к оптимальной точке, дополнительный коэффициент осцилляции позволяет избавиться от локальной оптимальной точки. Одна из схем является наиболее эффективной и широко используемой схемой.
meanэто хрупкая мера Сравнивая рисунок 2 и рисунок 3, видно, что KMeans, вне зависимости от стратегии инициализации, не имеет возможности устранить влияние выбросов, расположенных в среднем кластере, и относит их к кластеру 3 (кластер, расположенный в правом верхнем углу ), суть которого заключается в том, что из-за статистической ошибки, возникающей при выполнении операции среднего по всем точкам выборки в кластере, это явление чаще встречается в реальных наборах данных, и влияние может быть больше, поэтому перед запуском необходима предварительная обработка данных KMeans Да, удаление выбросов и нормализация данных могут повысить производительность KMeans.
Гауссов предел распределения KMeans по существу делит данные в евклидовом пространстве и хорошо работает для наборов данных с неявным гауссовым распределением, но для тех данных, которые могут не иметь неявного гауссовского распределения или не могут быть разделены в евклидовом пространстве, он будет вести себя как очень плохо, так что вы можете узнать из решения SVM используйте функцию ядра (функцию ядра), чтобы отобразить его в более многомерное (бесконечномерное) пространство, а затем разделите его. Благодаря простоте алгоритма KMeans и его сильной воспроизводимости для формулы 2.1 $dist(\cdot,\cdot)$ Переоснащение несложно.

4 Резюме

Эта статья завершает реализацию KMeans в Python и сравнивает экспериментальные результаты.Известно, что алгоритм KMeans может вычислять только бесконечно близкие к реальным центральным точкам кластера на большинстве наборов данных, и обсуждаются некоторые недостатки KMeans и предлагаются соответствующие методы улучшения были предложены. В большинстве случаев предварительная обработка данных перед запуском алгоритма KMeans может улучшить производительность кластеризации алгоритма KMeans. При работе с неразделимыми данными на более низких широтах можно использовать функцию ядра для сопоставления их с многомерным пространством. Разделите снова.

использованная литература

Wu, Xindong, et al. "Top 10 algorithms in data mining." Knowledge and information systems 14.1 (2008): 1-37.
Jain AK, Dubes RC (1988) Algorithms for clustering data. Prentice-Hall, Englewood Cliffs
Грей Р.М., Нойхофф Д.Л. (1998) Квантование, IEEE Trans Inform Theory 44(6):2325–2384.
Чжихуа Чжоу, Машинное обучение, 2012.
Цзявей Хан, Концепции и методы интеллектуального анализа данных, 2017.
Arthur, David, and Sergei Vassilvitskii. "How slow is the k-means method?." Proceedings of the twenty-second annual symposium on Computational geometry. 2006.

приложение

Загрузите экспериментальный код