В этом выпуске серии из 3 частей мы шаг за шагом рассмотрим все, что вам нужно знать, чтобы понять кластеризацию K-средних:
Часть 1: Основы
- Основы: понимание кластеризации, евклидовых расстояний и т. д.
- Интуиция: визуальное пошаговое руководство по K-средним в действии
Часть 2: Кодирование алгоритма с нуля
- Алгоритм: формальный обзор
- Реализация кода: реализация Python с нуля
Часть 3: Реальная реализация
- Вывод: использование K-Means от scikit для сжатия изображений
Не стесняйтесь переходить к определенному разделу. К концу вы будете иметь четкое представление о K-Means и сможете применять его к своим собственным наборам данных.
Во второй части мы исследуем, что такое K-средства, как они работают алгоритмически и технические аспекты, которые нужно знать, прежде чем внедрять собственные K-средства.
K-Means: формальный обзор
В этом разделе мы рассмотрим, что такое кластеризация K-средних, формально поймем алгоритм и рассмотрим некоторые предостережения, на которые следует обратить внимание.
Что такое кластеризация K-средних?
Кластеризация K-средних – это итеративный алгоритм, целью которого является разбиение данного набора данных на K отдельных кластеров. «K» в K-Means относится к количеству кластеров, которые мы хотим создать. Алгоритм работает, назначая каждую точку данных ближайшему центроиду, который представляет центр кластера, а затем пересчитывает центроиды на основе вновь назначенных точек данных. Этот процесс продолжается до сходимости, когда центроиды стабилизируются, а точки данных эффективно группируются в кластеры.
"Основная цель алгоритма K-средних — минимизировать сумму расстояний между точками и центроидами соответствующих кластеров".
Понимание алгоритма K-средних
- Выберите K:Начните. Определите количество кластеров. Обычно 3–4 — хороший выбор для большого разнообразия данных. Подробнее об этом позже.
- Инициализация: начните со случайного выбора K точек данных из набора данных в качестве начальных центроидов.
- Назначение. Для каждой точки данных рассчитайте расстояние до каждого центроида и назначьте его кластеру, представленному ближайшим центроидом.
- Обновление: пересчитайте центроиды, взяв среднее значение всех точек данных, назначенных каждому кластеру.
- Итерация: повторяйте шаги назначения и обновления до сходимости (когда центроиды больше не изменяются существенно).
Выбор количества кластеров (K)
Не существует определенного правила для магического значения K. Мы кратко коснемся некоторых общих подходов. Я рекомендую вам ознакомиться с ресурсами ближе к концу статьи, чтобы узнать больше о каждом из них:
- Знание предметной области. Предварительное знание набора данных может помочь вам принять решение об оптимальном K. Например, при сегментации клиентов вы можете иметь представление о том, сколько существует различных групп клиентов на основе определенных характеристик.
- Метод локтя. Метод локтя — популярный метод выбора K на основе суммы квадратов расстояний (SSE) внутри кластеров. Постройте график SSE в зависимости от различных значений K и найдите точку «локтя», где SSE уменьшается значительно меньше для последующих значений K. Точка локтя предполагает подходящее значение для K.
- Оценка силуэта. Оценка силуэта измеряет качество кластеризации, учитывая как сплоченность внутри кластеров, так и разделение между кластерами. Вычислите оценку силуэта для различных значений K и выберите ту, которая имеет наивысшую оценку, указывающую на хорошо разделенные и компактные кластеры.
- Метод проб и ошибок. Иногда необходимо поэкспериментировать с разными значениями K и наблюдать за результирующими кластерами. Визуализируйте кластеры и оцените, имеют ли они интуитивный смысл и дают ли они значимую информацию. Настраивайте K до тех пор, пока кластеры не станут разумными и полезными.
Критерии прекращения
Как мы узнаем, что «конвергенция» достигнута? Как и в нашем визуальном примере, у нас есть три простых идеи:
- Точки данных остаются назначенными тем же кластерам, что и раньше.
- Центроиды кластеров остаются неизменными по сравнению с их предыдущими позициями.
- Алгоритм выполнил указанное общее количество итераций.
Теперь, когда мы знаем, что такое K-Means, давайте реализуем его с нуля на Python!
Реализация кода с нуля на Python
В этом разделе давайте реализуем класс K-Means в Python. Я пройдусь по методам класса один за другим, объясняя, как это работает. В этой конкретной реализации мы будем рассматривать критерии остановки сходимости как относительное изменение потерь со значением допуска, предоставленным нашей функции. Если вы впервые используете K-Means, я настоятельно рекомендую вам просто определить и использовать метод и попытаться написать свой собственный код, прежде чем смотреть на мою реализацию. Помните, что правильных способов может быть несколько.
Сначала мы импортируем библиотеку NumPy и определим наш класс K-Means с помощью метода __init__, который принимает точки входных данных, количество кластеров (k), метод инициализации (init), максимальное количество итераций (max_iters) и критерии сходимости (rel_tol) в качестве аргументов.
def __init__(self, points, k, init='random', max_iters=10000, rel_tol=1e-5):
"""
Args:
points: NxD numpy array, where N is the number of points and D is the dimensionality
k: number of clusters
init: how to initialize the centers ('random' or 'kmpp')
max_iters: maximum number of iterations
rel_tol: convergence criteria w.r.t relative change of loss
"""
self.points = points
self.k = k
self.init = init
self.max_iters = max_iters
self.rel_tol = rel_tol
self.centers = None
self.assignments = None
self.loss = None
Во-вторых, давайте определим метод init_centers, который инициализирует центры кластера случайным образом, выбирая K случайных индексов из точек данных. Вместо случайного создания новых точек данных, как мы делали в визуальном примере, обычно выбирают случайные точки из самих данных, которые действуют как наши начальные точки.
def init_centers(self):
"""
Initialize the centers randomly.
"""
center_indices = np.random.choice(self.points.shape[0], self.k, replace=False)
self.centers = self.points[center_indices]
return self.centers
Теперь, когда у нас есть начальные центроиды, нам нужен метод для назначения точек каждому кластеру. Помните, что это было сделано путем проверки евклидова расстояния каждой точки до каждого центроида. Лучше всего, если мы реализуем это в обобщенной вспомогательной функции. Давайте назовем это pairwise_dist, которое будет вычислять попарные расстояния между двумя наборами точек, используя евклидову метрику расстояния. Помните, что мы постараемся максимально избежать использования циклов while/for и вместо этого будем использовать массивное вещание. Я настоятельно рекомендую этот ресурс, чтобы посмотреть на различные способы вычисления матрицы расстояний в Python.
def pairwise_dist(x, y):
"""
Args:
x: N x D numpy array
y: M x D numpy array
Return:
dist: N x M array, where dist2[i, j] is the euclidean distance between
x[i, :] and y[j, :]
"""
#construct x's dot product matrix:
n = x.shape[0]
m = y.shape[0]
#construct x's dot product matrix:
x_dot = np.sum(x*x , axis = 1, keepdims= True) # shape of n, 1
y_dot = np.sum(y*y, axis = 1, keepdims= True) # shape of m, 1
#construct 2ab matrix
xy_dot = x.dot(y.T)
dist = np.sqrt(np.abs(x_dot + y_dot.T - (2*xy_dot)))
return dist
Теперь мы, наконец, реализуем метод, который будет назначать кластер каждой точке в итерации. Метод update_assignment присваивает каждой точке данных ближайший центр кластера на основе попарных расстояний, рассчитанных с помощью функции pairwise_dist.
def update_assignment(self):
"""
Update the membership of each point based on the closest center
Return:
self.assignments : numpy array of length N, the cluster assignment for each point
"""
dist_matrix = pairwise_dist(self.points, self.centers)
self.assignments = np.argmin(dist_matrix, axis = 1)
return self.assignments
Помните следующий шаг? Теперь мы обновляем наши центры на основе центроидов каждого кластера. Метод update_centers обновляет центры кластеров, вычисляя среднее значение всех точек данных, назначенных каждому кластеру.
def update_centers(self):
"""
update the cluster centers
Return:
self.centers: new centers, a new K x D numpy array of float dtype, where K is the number of clusters, and D is the dimension.
"""
for i in range(self.K):
if self.points[self.assignments == i].size == 0: # no points assigned
continue
self.centers[i] = np.mean(self.points[self.assignments == i], axis= 0)
Эти два метода теперь можно вызывать на каждой итерации, пока мы не достигнем критерия остановки. Для наших критериев остановки давайте реализуем метод get_loss, который будет вычислять потери (целевую функцию) K-средних. Это сумма квадратов расстояний между каждой точкой данных и ее соответствующим центром.
def get_loss(self):
"""
The loss will be defined as the sum of the squared distances between each point and it's respective center.
Return:
self.loss: a single float number, which is the objective function of KMeans.
"""
self.loss = np.sum(np.square((self.points - self.centers[self.assignments]))
return self.loss
Объединим все в методе train! Это будет обучать модель K-средних, повторяя шаги назначения и обновления, пока не будет достигнута сходимость или максимальное количество итераций. Мы также будем обрабатывать пустые кластеры, случайным образом выбирая новую точку данных в качестве нового центра. Мы будем считать KMeans сходящимся, когда изменение убытка упадет ниже порогового значения. Потери будут определяться как сумма квадратов расстояний между каждой точкой и ее соответствующим центром.
def train(self):
"""
Return:
self.centers: K x D numpy array, the centers
self.assignments: Nx1 int numpy array
self.loss: final loss value of the objective function of KMeans.
"""
loss_prev_iter = pow(2, 60) #initial cluster
for i in range(0, self.max_iters):
self.update_assignment()
self.update_centers()
#account for cluster center with no points
for j in range(self.K):
if self.points[self.assignments == j].size == 0:
self.centers[i] = self.points[np.random.randint(0, self.points.size)]
loss_curr = self.get_loss()
if (i == 0):
loss_prev_iter = loss_curr
continue
percent_diff = np.abs(loss_curr - loss_prev_iter) / loss_prev_iter
loss_prev_iter = loss_curr
if percent_diff < self.rel_tol:
break
return self.centers, self.assignments, self.loss
To reiterate, here is how train works:
Recall that centers have already been initialized in __init__
1. Update the cluster assignment for each point
2. Update the cluster centers based on the new assignments from Step 1
3. Check to make sure there is no mean without a cluster,
i.e. no cluster center without any points assigned to it.
- In the event of a cluster with no points assigned,
pick a random point in the dataset to be the new center and
update your cluster assignment accordingly.
4. Calculate the loss and check if the model has converged to break the loop early.
- The convergence criteria is measured by whether the percentage difference
in loss compared to the previous iteration is less than the given
relative tolerance threshold (self.rel_tol).
5. Iterate through steps 1 to 4 max_iters times.
И с этим мы закончили! В качестве бонуса рассмотрим еще один метод инициализации. Как мы обсуждали ранее, K-Means очень чувствителен к исходным положениям центроида. Если они будут слишком близко, мы можем не получить хороших результатов. Используя эту интуицию, вот базовая версия знаменитого KMeans++.
def kmpp_init(self):
"""
Use the intuition that points further away from each other will probably be better initial centers
Return:
self.centers : K x D numpy array, the centers.
"""
#1. Sample 1% of the points from the dataset, uniformly at random (UAR) and without replacement. This sample will be the dataset the remainder of the algorithm uses to minimize initialization overhead.
# 2. From the above sample, select only one random point to be the first cluster center.
# 3. For each point in the sampled dataset, find the nearest currently established cluster center and record the squared distance to get there.
# 4. Examine all the squared distances and take the point with the maximum squared distance as a new cluster center. In other words, we will choose the next center based on the maximum of the minimum calculated distance instead of sampling randomly like in step 2. You may break ties arbitrarily.
# 5. Repeat 3-4 until all k-centers have been assigned. You may use a loop over K to keep track of the data in each cluster.
center_indices = np.random.choice(self.points.shape[0], int(0.01 * self.points.shape[0]), replace= False) #choose random indices
sample_dataset = self.points[center_indices]
cluster_center_index = np.random.choice(center_indices, 1, replace= False)
k_centers = self.points[cluster_center_index]
for i in range(0, self.K - 1):
dist_matrix = pairwise_dist(sample_dataset, k_centers)
dist_matrix = np.min(dist_matrix, axis = 1)
max_dist_index = np.argmax(dist_matrix)
k_centers = np.vstack([k_centers, sample_dataset[max_dist_index]])
self.centers = k_centers
return self.centers
Хотя инициализация в K-средних++ требует больших вычислительных ресурсов, чем стандартный алгоритм K-средних, время выполнения для сходимости к оптимальному для K-средних++ резко сокращается. Это связано с тем, что изначально выбранные центроиды, скорее всего, уже лежат в разных кластерах.
Ресурсы
Вы можете найти полный код на GitHub здесь:
https://github.com/TechTushaar/K-Means-Guide
