Кластеризация методом k-средних

Наглядный разбор алгоритма кластеризации методом k-средних

Здравствуйте и вновь добро пожаловать на занятия по теме «Кластерный анализ и машинное обучение без учителя на языке Python».

В этой лекции мы поговорим о кластеризации методом k-средних. Метод k-средних – это специальный алгоритм кластеризации, подразумевающий, что у нас есть массив данных, которые мы хотим сгруппировать в кластеры, а точнее – в k кластеров.

Входными данными в методе k-средних является только матрица наших X. Как правило, мы формируем её так, чтобы каждая строка представляла отдельный пример (образец), а каждый столбец – отдельный признак или, пользуясь терминами из статистики, фактор. Обычно мы говорим, что есть N примеров и D признаков, так что X представляет собой матрицу размерности NxD.

В алгоритме метода k-средних есть два основных этапа. Сначала мы выбираем k разных центров кластеров – как правило, это просто случайные точки в наборе данных. Затем мы переходим к нашему основному циклу, который также состоит из двух этапов. Первый – это выбор, к какому из кластеров принадлежит каждая точка из X. Для этого мы берём каждый пример и выбираем кластер, чей центр ближе всего. Не забывайте, что вначале мы выбираем центры случайным образом. Второй этап – заново вычислить каждый центр кластера, основываясь на множестве точек, которые к нему приписаны. Для этого берутся все соответствующие примеры и вычисляется их среднее значение, отсюда и название метода – «метод k-средних». Всё это делается до тех пор, пока алгоритм не сойдётся, то есть пока не прекратится изменение в распределении точек по кластерам или в координатах центров кластеров. Как правило, это происходит очень быстро – в районе от 5 до 15 проходов цикла. Это сильно отличается от градиентного спуска в глубоком обучении, где могут пройти тысячи итераций, пока не произойдёт схождение.

Рассмотрим наглядный пример работы метода k-средних. На первом этапе мы приписываем центры кластеров m1 и m2 к случайным точкам X. На следующем этапе – являющемся первым этапом основного цикла – мы выбираем, к какому из кластеров принадлежит каждая точка. Так, на рисунке две точки слева принадлежат к кластеру 1, а две точки справа – к кластеру 2. На следующем этапе пересчитываем средние значения m1 и m2. Тогда m1 получается средним значением двух точек слева, поскольку они принадлежат этому кластеру – на рисунке m1 выделен зелёным кружочком. M2, выделенный другим зелёным кружочком справа, вычисляется точно так же. Всё, алгоритм сошёлся, поскольку больше не может быть изменений в присвоении данных к кластерам и, следовательно, в значениях m1 и m2.

Мягкий метод k-средних

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

О чём это говорит?

Это говорит, что функция затрат чувствительна к локальным минимумам. Один из способов преодолеть это препятствие – использование «нечёткого» членства в каждом классе. Это значит, что каждая точка наших данных не относится полностью к тому или иному классу, а составляет сумму принадлежностей к классам, например, может принадлежать на 60% кластеру 1 и на 40% кластеру 2. Вы увидите, что мы можем получить мягкий метод k-средних, лишь немного подправив алгоритм «обычного» метода k-средних.

Итак, первая часть в «мягком» варианте остаётся неизменной – мы инициируем k центров кластеров в случайных точках набора данных. Изменения начинаются в теле главного цикла. Так, первым этапом становится вычисление границ распределения кластеров:

r_k^{(n)}=\frac{e^{-\beta d}(m_kx^{(n)})}{\sum_j e^{-\beta d}(m_jx^{n})}.

Как вы можете убедиться, теперь наше всегда будет дробью, числом между 0 и 1, тогда как в «жёстком», или «обычном», методе k-средних всегда равен точно нулю или единице.

Второй этап очень похож – мы лишь пересчитываем средние значения, основываясь на границах распределениях кластеров:

m_k=\frac{\sum_n r_k^{(n)} x^{(n)}}{\sum_n r_k^{(n)}}.

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

Если вы изучали мои курсы по глубокому обучению, то могли заметить, что  в чём-то похож на функцию софтмакс.

Целевая функция метода k-средних

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

J=\sum_n \sum_k r_k^{(n)} || m_k-x^{(n)}||^2.

Таким образом, в действительности это лишь квадрат расстояния, взвешенный на величину принадлежности x, то есть если x(n) находится далеко от центра кластера k, то можно предполагать, что его влияние на кластер будет весьма малым.

Если вы проходили какой-либо из моих курсов по глубокому обучению, то знаете, что мы оптимизируем целевую функцию с помощью градиентного спуска. При этом в предыдущей лекции мы никаким градиентным спуском не пользовались. В действительности то, чем мы сейчас занимаемся, называется «координатным спуском». Это значит, что мы двигаемся в направлении уменьшения J относительно только одной переменной за раз. Вы можете легко убедиться, что это так, поскольку мы действительно обновляем лишь одну переменную за раз – либо , либо . Математически доказано, что при каждой итерации целевая функция будет уменьшаться и что она всегда сходится. Однако, как уже указывалось ранее, нет никакой гарантии что сойдётся она непременно к глобальному минимуму.

Код для мягкого метода k-средних на Python

Если вы не хотите писать код самостоятельно, а лишь запустить уже написанный, зайдите на Github по адресу https://github.com/lazyprogrammer/machine_learning_examples и найдите папку unsupervised_class. Нужный для данной лекции файл называется kmeans.py.

Итак, начнём с основных необходимых вещей – с импорта библиотек Numpy и Matplotlib и написания функции main. В данном примере мы создадим три гауссова облака. D будет равно 2, так чтобы можно было легко показать всё графически. Кроме того, введём переменную s, равную 4 и определяющую, насколько сильно разделены средние значения облаков. Первое из облаков будет в начале координат в точке (0, 0), второе – в точке с координатами (s, s), а третье – в точке (0, s). У нас будет 900 примеров (образцов) – по 300 примеров на облако. X будет матрицей размерностью NxD. И сразу выведем то, что получилось, на экран.

import numpy as np
import matplotlib.pyplot as plt

def main():
D = 2
s = 4
mu1 = np.array([0, 0])
mu2 = np.array([s, s])
mu3 = np.array([0, s])

N = 900
X = np.zeros((N, D))
X[:300, :] = np.random.randn(300, D) + mu1
X[300:600, :] = np.random.randn(300, D) + mu2
X[600:, :] = np.random.randn(300, D) + mu3

plt.scatter(X[:,0], X[:,1])
plt.show()

Далее используем функцию plot_k_means, хотя она ещё не написана – мы займёмся ею, когда закончим здесь. Значение переменной K установим равным 3, поскольку мы выбрали три кластера. Далее, чтобы посмотреть, что получится, установим K = 5. Сделаем это дважды, но во втором случае изменим значение параметра β.

K = 3
plot_k_means(X, K)

K = 5
plot_k_means(X, K, max_iter=30)

K = 5
plot_k_means(X, K, max_iter=30, beta=0.3)

if __name__ == ‘__main__’:
main()

Теперь вернёмся назад и напишем функцию plot_k_means. Прежде всего определим переменные и форму X – матрицу размерностью NxD. Далее инициируем случайные точки X в качестве центров кластеров. После этого вычисляем r_k^((n)).

def plot_k_means(X, K, max_iter=20, beta=1.0):
N, D = X.shape
M = np.zeros((K, D))
R = np.zeros((N, K))

for k in xrange(K):
M[k] = X[np.random.choice(N)]

costs = np.zeros(max_iter)
for i in xrange(max_iter):
for k in xrange(K):
for n in xrange(N):
R[n,k] = np.exp(-beta*d(M[k], X[n])) / np.sum( np.exp(-beta*d(M[j], X[n])) for j in xrange(K) )

Напишем также сразу функцию расстояния между двумя векторами u и v, возвращающую квадрат расстояния.

def d(u, v):
diff = u – v
return diff.dot(diff)

Вернёмся к функции plot_k_means. Теперь второй этап – перерасчёт средних значений. Это матричное умножение. N при этом исчезает, поскольку является внутренней размерностью.

for k in xrange(K):
M[k] = R[:,k].dot(X) / R[:,k].sum()

И дополнительный этап – расчёт и вывод на экран функции затрат, рассчитывающую ошибку X при данных значениях R и M. При этом функция будет прекращать работу, когда изменение ошибки станет малым между двумя итерациями.

costs[i] = cost(X, R, M)
if i > 0:
if np.abs(costs[i] – costs[i-1]) < 0.1:
break

Для этого напишем, не изощряясь, соответствующую функцию.

def cost(X, R, M):
cost = 0
for k in xrange(len(M)):
for n in xrange(len(X)):
cost += R[n,k]*d(M[k], X[n])
return cost

И последнее в функции plot_k_means – вывод на экран результатов. Сначала – функции затрат, а затем – данные с кластерами, раскрашенными разными цветами.

plt.plot(costs)
plt.title(“Costs”)
plt.show()

random_colors = np.random.random((K, 3))
colors = R.dot(random_colors)
plt.scatter(X[:,0], X[:,1], c=colors)
plt.show()

Запустим программу.

Сначала видим просто необработанные данные:

Кластеризация методом k-средних

Далее функцию затрат для K = 3.

Кластеризация методом k-средних

И, наконец, кластеры, найденные методом k-средних.

Кластеризация методом k-средних

Далее – функция затрат для K = 5 и кластеры для K = 5.

Кластеризация методом k-средних

Кластеризация методом k-средних

Затем – функция затрат для K = 5, но при другом значении β и соответствующие кластеры.

Кластеризация методом k-средних

Кластеризация методом k-средних

Трудно разглядеть, что здесь пять кластеров.

Понравилась статья? Поделить с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: