Обучение без присмотра
До сих пор я говорил об алгоритмах обучения с учителем (в частности, о бинарной классификации и регрессии). Сегодня я хотел бы поговорить о другом важном алгоритме базового машинного обучения, который работает совершенно по-другому, используя обучение без учителя.
Как я объяснял в других постах, обучение с учителем — это процесс обучения маркировке новых примеров на основе предварительного обучения на тщательно размеченных и классифицированных данных. При обучении без учителя наши данные состоят только из немаркированных примеров, и цель состоит в том, чтобы разобраться в данных, даже если никто не предоставил нам правильные метки. «Осмысление данных» в этом случае будет включать в себя понятие кластеризация.
Рассмотрим следующий график некоторых данных:
......... ........
......... ......
......... ......
..........
........
.......
Поскольку это обучение без учителя и меток нет, данные представлены в виде простых черных точек. Теперь цель состоит в том, чтобы разделить данные на три кластера. В этом случае совершенно очевидно, что следует делать. Вероятно, вы сгруппировали все данные в левом углу в один кластер A, данные справа — в другой кластер B, а точки внизу — в третий кластер C. Алгоритм кластеризации K-средних — простой, но мощный способ для создания кластеров на основе таких данных, как показано на графике выше.
Кластеризация K-средних — это метод группировки n наблюдений в K кластеров. Он использует векторное квантование и стремится отнести каждое наблюдение к кластеру с ближайшим средним значением или центроидом, который служит прототипом кластера. Первоначально разработанная для обработки сигналов, кластеризация K-средних теперь широко используется в машинном обучении для разделения точек данных на K-кластеры на основе их сходства. Цель состоит в том, чтобы минимизировать сумму квадратов (евклидовых) расстояний между точками данных и соответствующими центроидами кластера, в результате чего кластеры будут внутренне однородными и отличными друг от друга.
Проще говоря, идея состоит в том, чтобы представить каждый кластер его центром или центроидом. Учитывая центры кластеров, мы можем назначить каждую точку ее ближайшему центру. Аналогично, если мы знаем назначение точек кластерам, мы можем легко вычислить центры. Это порождает своего рода проблему курицы и яйца. Если мы знаем кластеры, мы можем вычислить центры. Если мы знаем центры, мы можем компьютеризировать кластеры. Но на самом деле мы тоже этого не знаем.
Общий ответ информатики на проблемы курицы и яйца — это итерация. Мы можем начать с предположения о центрах кластеров. Основываясь на этом предположении, мы можем присвоить каждой точке ее ближайший центр. Учитывая эти новые назначения, мы можем пересчитать центры. Мы повторяем это в цикле до тех пор, пока центры не перестанут двигаться или не будет достигнуто максимальное количество итераций.
В приведенном выше примере кластеризация сходится очень быстро.
Алгоритм
Псевдокод для алгоритмов кластеризации K означает следующее:
for k = 1 to K do
μ_k ← some random location // randomly initialize mean for kth cluster
end for
repeat
for n = 1 to N do
z_n ← argmin_k || μ_k − x_n || //assign example n to closest center
end for
for k = 1 to K do
X_k ← { x_n : z_n = k } // points assigned to cluster k
μ_ k ← mean(X_k ) // re-estimate mean of cluster k
end for
until μs stop changing
return z // return cluster assignments
Центры кластеров инициализируются случайным образом. В строке 6 точка данных x_n сравнивается с центром каждого кластера μ_k. Он присваивается кластеру k, если k — центр с наименьшим расстоянием. Переменная z_n хранит назначение примера n. В строках 8–12 пересчитываются центры кластеров. Сначала X_k хранит все примеры, которые были назначены кластеру k. Затем центр кластера k вычисляется как среднее значение (следовательно, K-среднее) назначенной ему точки. Этот процесс продолжается до тех пор, пока средства не сойдутся.
Очевидный вопрос об этом алгоритме: сходится ли он? Другой вопрос: сколько времени нужно, чтобы сойтись? Ответ на первый ответ – да, и это можно продемонстрировать математически. Ответ на второй вопрос заключается в том, что обычно он сходится очень быстро.
Важно отметить, что хотя K-средние гарантированно сходятся быстро, они не гарантированно сходятся к «правильному ответу». Ключевая проблема обучения без учителя заключается в том, что мы понятия не имеем, каков «правильный ответ». Сходимость к плохому решению обычно происходит из-за плохой инициализации.
Применение кластеризации в реальных сценариях
Кластеризация — широко используемый метод в отрасли. Он используется практически во всех сферах: от банковского дела и рекомендательных систем до кластеризации документов и сегментации изображений.
Сегментация клиентов
Мы уже говорили об этом ранее: одним из наиболее распространенных применений кластеризации является сегментация клиентов. И дело не ограничивается только банковским делом. Эта стратегия охватывает все функции, включая телекоммуникации, электронную коммерцию, спорт, рекламу, продажи и т. д.
Кластеризация документов
Это еще одно распространенное применение кластеризации. Допустим, у вас есть несколько документов, и вам нужно сгруппировать похожие документы вместе. Кластеризация помогает нам группировать эти документы таким образом, чтобы похожие документы находились в одних и тех же кластерах.
Выполнение
Реализация алгоритма K-средних на языке Python показана ниже. Программа использует евклидово расстояние между точками и пытается минимизировать квадрат расстояния между ними, тем самым формируя внутренне однородные кластеры, отличные друг от друга.
import numpy as np
import matplotlib.pyplot as plt
class KMeans:
def __init__(self, k=2, max_iters=100):
self.k = k
self.max_iters = max_iters
def fit(self, X):
self.centroids = X[np.random.choice(range(len(X)), self.k, replace=False)]
for _ in range(self.max_iters):
clusters = [[] for _ in range(self.k)]
for point in X:
distances = [np.linalg.norm(point - centroid) for centroid in self.centroids]
closest_centroid = np.argmin(distances)
clusters[closest_centroid].append(point)
prev_centroids = self.centroids.copy()
for i in range(self.k):
if clusters[i]:
self.centroids[i] = np.mean(clusters[i], axis=0)
if np.all(prev_centroids == self.centroids):
break
def predict(self, X):
return [np.argmin([np.linalg.norm(x - centroid) for centroid in self.centroids]) for x in X]
# Example usage
X = np.array([[1, 2], [2, 1], [2, 4], [3, 2], [7, 2], [6, 4], [7, 3], [8, 4], [9, 5]])
kmeans = KMeans(k=2, max_iters=100)
kmeans.fit(X)
labels = kmeans.predict(X)
plt.scatter(X[:, 0], X[:, 1], c=labels)
plt.scatter(kmeans.centroids[:, 0], kmeans.centroids[:, 1], marker='X', color='red')
plt.show()
Заключение
В этой статье мы обсудили основы алгоритма K-средних в машинном обучении и других приложениях. Был описан основной или наивный алгоритм и представлена реализация Python с примером использования с использованием matplotlib. Для получения более подробной информации и изучения кластеризации K-средних см. эту статью в Википедии.
