Введение в алгоритмы
Кластеризация заключается в группировании определенных выборок в несколько «классов» или «кластеров» в соответствии со сходством или расстоянием их признаков.
Эта статья кратко представляет процесс алгоритма кластеризации KMeans и имитирует sklean для реализации упрощенной версии алгоритма KMeans.
Диаграмма процесса алгоритма
Чтобы продемонстрировать процесс, давайте воспользуемся легендой, чтобы более интуитивно прочувствовать процесс вычисления KMeans.
Во-первых, здесь 8 пунктов. Разделим эти 8 пунктов на 2 категории.
Предположим, мы хотим разделить на 2 категории. Затем мы сначала предполагаем, что 2 центральные точки. Как показано ниже:
Перпендикулярно по 2 центральным точкам. Разделите точки на 2 категории, одна слева от линии и одна справа:
Пересчитайте центральную точку 2 классов, как показано на рисунке:
По 2-м центральным точкам все точки снова делятся на 2 категории:
Снова вычислите центральную точку:
Таким образом, очень просто обнаружить, что центральная точка больше не изменилась.
Весь процесс повторяет 2 вещи:
(1) Рассчитать классификацию всех точек в соответствии с центральной точкой
(2) Рассчитать новую центральную точку каждого класса
до сходимости.
В этой статье представлен только простой для понимания процесс и код, реализованный самостоятельно.Что касается модели алгоритма и шагов алгоритма, вы можете прочитать книги самостоятельно или проверить другие блоги. Рекомендуется «Статистические методы обучения» доктора Ли Ханга.
Реализуйте алгоритм KMeans самостоятельно
В этой статье реализована упрощенная версия алгоритма KMeans на основе приведенного выше кода, имитирующего sklean, который можно сохранить как KMeans.py и указать ссылку:
import numpy as np
from math import sqrt
from collections import Counter
from sklearn.metrics import accuracy_score
import random
class KMeans:
def __init__(self, n_clusters=3, random_state=0):
assert n_clusters >=1, " must be valid"
self._n_clusters = n_clusters
self._random_state = random_state
self._X = None
self._center = None
self.cluster_centers_ = None
def distance(self, M, N):
return (np.sum((M - N) ** 2, axis = 1))** 0.5
def _generate_labels(self, center, X):
return np.array([np.argmin(self.distance(center, item)) for item in X])
def _generate_centers(self, labels, X):
return np.array([np.average(X[labels == i], axis=0) for i in np.arange(self._n_clusters)])
def fit_predict(self, X):
k = self._n_clusters
# 设置随机数
if self._random_state:
random.seed(self._random_state)
# 生成随机中心点的索引
center_index = [random.randint(0, X.shape[0]) for i in np.arange(k)]
center = X[center_index]
# print('init center: ', center)
n_iters = 1e3
while n_iters > 0:
# 记录上一个迭代的中心点坐标
last_center = center
# 根据上一批中心点，计算各个点所属的类
labels = self._generate_labels(last_center, X)
self.labels_ = labels
# 新的中心点坐标
center = self._generate_centers(labels, X)
# print('n center: ', center)
# 暴露给外头的参数
# 中心点
self.cluster_centers_ = center
# 返回节点对应的分类 {0, 1, ..., n}
# 如果新计算得到的中心点，和上一次计算得到的点相同，说明迭代已经稳定了。
if (last_center == center).all():
self.labels_ = self._generate_labels(center, X)
break
n_iters = n_iters - 1
return self
Давайте посмотрим на реальный эффект, здесь я нарисовал очень плотную решетку. чтобы увидеть, есть ли какие-либо упущения в классификации.
import numpy as np
import matplotlib.pyplot as plt
from KMeans import KMeans
from sklearn.datasets import load_iris
t1 = np.linspace(-1, 1.5, 100)
t2 = np.linspace(-1, 1.5, 100)
X = np.array([(x, y) for x in t1 for y in t2])
plt.figure(figsize=(10, 10))
clf = KMeans(n_clusters=6, random_state=None)
clf.fit_predict(X)
plt.scatter(X[:, 0], X[:, 1], c=clf.labels_)
center = clf.cluster_centers_
plt.scatter(center[:, 0], center[:, 1],marker="*",s=200)
Фактический эффект выглядит следующим образом:
Примечание. Цветовые блоки здесь на самом деле представляют собой плотные решетки, и их классификация по каждому центру также полностью соответствует нашим ожиданиям.
Далее давайте воспользуемся этим алгоритмом для реализации классификации следующего набора данных по радужной оболочке.
Во-первых, давайте импортируем набор данных, чтобы увидеть влияние фактических точек на график:
import numpy as np
import matplotlib.pyplot as plt
from KMeans import KMeans
from sklearn.datasets import load_iris
iris = load_iris()
X = iris.data
X = X[:, 2:]
y = iris.target
plt.figure(figsize=(12, 12))
plt.scatter(X[:, 0], X[:, 1])
plt.grid()
plt.xlim(0, 7)
plt.ylim(0, 7)
center = clf.cluster_centers_
Распределение выборки выглядит следующим образом:
Затем мы вызываем написанный нами алгоритм KMeans для классификации образцов.Поскольку набор данных радужной оболочки изначально разделен на 3 категории, мы устанавливаем k = 3.
import numpy as np
import matplotlib.pyplot as plt
from KMeans import KMeans
from sklearn.datasets import load_iris
iris = load_iris()
X = iris.data
X = X[:, 2:]
y = iris.target
clf = KMeans(n_clusters=3)
s = clf.fit_predict(X)
plt.figure(figsize=(12, 12))
plt.scatter(X[:, 0], X[:, 1], c=clf.labels_)
plt.grid()
plt.xlim(0, 7)
plt.ylim(0, 7)
center = clf.cluster_centers_
plt.scatter(center[:, 0], center[:, 1],marker="*",s=200)
Результат выглядит следующим образом:
Как и ожидалось.
Суммировать
Алгоритм KMeans является итеративным алгоритмом и не может гарантировать глобальную оптимальность, конкретная производительность связана с параметрами инициализации. Выбор начальной центральной точки окажет определенное влияние на результаты.
Значение k алгоритма k-средних необходимо указывать заранее, и в практических приложениях максимальное количество категорий K является неопределенным. Один из способов решить эту проблему — попробовать кластеры с разными значениями k и изучить производительность каждого кластера, чтобы определить оптимальное значение k. Вообще говоря, когда количество категорий становится меньше, средний диаметр увеличивается; когда количество категорий становится больше определенного значения, средний диаметр существенно не изменяется. Это значение и есть значение k, которое мы ищем.