Ng Enda Machine Learning-8-Знания о кластеризации

Продюсер: Ю Эр Хат
Автор: Питер
Редактор: Питер

Эндрю Нг Машинное обучение-8-Кластеризация

Главные выводы на этой неделе — два в неконтролируемом обучении:Кластеризация и уменьшение размерности. Впервые в этой статье представлен алгоритм K-средних в кластеризации, в том числе:

• Алгоритмическое мышление
• диаграммаK-Means
• sklearnвыполнить
• Pythonвыполнить

неконтролируемое обучение

Введение в неконтролируемое обучение

Кластеризация и уменьшение размерности — это неконтролируемые методы обучения, в которых данные не маркируются.

Например, в следующих данных горизонтальная и вертикальная оси$x$, без меток (вывод$y$). В неконтролируемом обучении нам нужно ввести ряд немаркированных обучающих данных в алгоритм, чтобы быстро найти его внутреннюю структуру данных в этих данных.

Приложения для неконтролируемого обучения

• сегментация рынка
• анализ социальных сетей
• Организация компьютерных кластеров
• Узнайте о формировании галактик

кластеризация

кластеризация

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

показатели эффективности

Метрики производительности кластеризации также известны как «метрики достоверности». Надеюсь «собраться». Результатом кластеризации является «высокое сходство внутри кластеров» и «низкое сходство между кластерами».

общийвнешние индикаторыДа:

1. Коэффициент Жаккара
2. коэффициент FM
3. Коэффициент ранда

Значения трех вышеуказанных коэффициентов все между [0,1], чем меньше, тем лучше

общийВнутренние показателиДа:

1. Индекс БД
2. Индекс Данна

Чем меньше значение DBI, тем лучше, а чем больше значение Dunn, тем лучше.

расчет расстояния

$x_i,x_j$из$L_p$Расстояние определяется как:

$L_p(x_i,x_j)=(\sum_{l=1}^{n}|x_i^{(l)}-x_j^{(l)}|^p)^\frac{1}{p}$

Регулирование:$p\geq1$, обычно используемая формула расчета расстояния:

• когда$p=2$когда欧式距离, чаще используется, а именно:

$L_2(x_i,x_j)=(\sum_{l=1}^{n}|x_i^{(l)}-x_j^{(l)}|^2)^\frac{1}{2}$

• когда$p=1$когда, то есть曼哈顿距离,который:

$L_1(x_i,x_j)=\sum_{l=1}^{n}(|x_i^{(l)}-x_j^{(l)}|)$

• когда$p$стремится к бесконечности, т.切比雪夫距离, что является максимальным значением каждого координатного расстояния:

$L_{\infty}(x_i,x_j)=\mathop {max}\limits_{l}|x_i^{(l)}-x_j^{(l)}|$

косинусное сходство

Формула косинусного подобия:

$\cos (\theta)=\frac{x^{T} y}{|x| \cdot|y|}=\frac{\sum_{i=1}^{n} x_{i} y_{i}}{\sqrt{\sum_{i=1}^{n} x_{i}^{2}} \sqrt{\sum_{i=1}^{n} y_{i}^{2}}}$

Коэффициент корреляции Пирсона

Формула для коэффициента корреляции Пирсона выглядит следующим образом:

$\rho_{X Y}=\frac{\operatorname{cov}(X, Y)}{\sigma_{X} \sigma_{Y}}=\frac{E\left[\left(X-\mu_{X}\right)\left(Y-\mu_{Y}\right)\right]}{\sigma_{X} \sigma_{Y}}=\frac{\sum_{i=1}^{n}\left(x-\mu_{X}\right)\left(y-\mu_{Y}\right)}{\sqrt{\sum_{i=1}^{n}\left(x-\mu_{X}\right)^{2}} \sqrt{\sum_{i=1}^{n}\left(y-\mu_{Y}\right)^{2}}}$

Алгоритм K-средних

Алгоритмическое мышление

K-均值,также называемыйk-meansАлгоритмы, наиболее распространенные алгоритмы кластеризации, берут немаркированный набор данных, а затем группируют данные в отдельные группы. Предположим, что данные разделены на n групп, метод таков:

• Произвольно выберите K точек, называемых «центрами кластеров».
• Для каждых данных в наборе данных, в соответствии с расстоянием от K центральных точек, они связаны с ближайшей центральной точкой, и все точки, связанные с одной и той же центральной точкой, группируются в класс.
• Вычислите среднее значение классов, сформированных на шагах выше, и переместите центральную точку, связанную с группой, в положение среднего значения.
• Повторяйте два вышеуказанных шага до тех пор, пока центральная точка не перестанет меняться.

Графическое K-среднее

1. Учитывая данные, которые нужно разделить, случайным образом определите две центральные точки кластера.
2. Вычислите расстояние между другими данными и этими двумя центральными точками и классифицируйте его в класс с небольшим расстоянием, предполагая, что два класса$C_1,C_2$
3. Убедитесь, что два класса в приведенных выше шагах$C_1,C_2$Среднее значение , это среднее значение является новым центром кластера
4. Повторение: рассчитайте расстояние между данными и этими двумя центральными точками, классифицируйте их в класс с небольшим расстоянием и сформируйте новый класс, затем определите новый центр кластера.
5. Пока центральная точка не перестанет меняться, завершите

Весь процесс

Процесс алгоритма K-средних

Псевдокод в видео Эндрю Нг

repeat {
  for i= to m
  #  计算每个样例属于的类
  c(i) := index (from 1 to K)  of cluster centroid closest to x(i)

 for k = 1 to K
  # 聚类中心的移动，重新计算该类的质心
 u(k) := average (mean) of points assigned to cluster K
}

Псевдокод в арбузной книге

Цель оптимизации

Задача минимизации K-средних состоит в том, чтобы минимизировать сумму расстояний между всеми точками данных и связанными с ними центральными точками кластера, поэтому функция стоимости K-средних (Функция искажения):

$J\left(c^{(1)}, \ldots, c^{(m)}, \mu_{1}, \ldots, \mu_{K}\right)=\frac{1}{m} \sum_{i=1}^{m}\left|X^{(i)}-\mu_{c^{(i)}}\right|^{2}$

в${u_{c^{(i)}}}$представляет собой${x^{(i)}}$Ближайшая точка центра кластера.

Цель оптимизации состоит в том, чтобы найти тот, который минимизирует функцию стоимости.${с^{(1)}},{с^{(2)}},…,{с^{(м)}}$и${\mu}_1,{\mu}_2,…,{\mu}_k$,который:

случайная инициализация

БегK-均值算法До этого сначала случайным образом инициализируйте все центральные точки кластера:

• выберите$K < m$, то есть количество центров кластеров меньше количества экземпляров обучающей выборки
• случайное обучение$K$обучающих примеров, а затем сделать K кластерных центров равными K обучающим примерам

Что касается проблемы локальных минимумов с K-средними:

Scikit Learn реализует K-средства

набор данных make_blobs

make_blobsГенератор кластерных данныхmake_blobsМетоды часто используются для генерации тестовых данных для алгоритмов кластеризации. Он будет основан на указанном пользователемКоличество объектов, количество центральных точек, экстенти т. д. для генерации нескольких типов данных.

Основные параметры

sklearn.datasets.make_blobs(n_samples=100, n_features=2,centers=3, cluster_std=1.0, center_box=(-10.0, 10.0), shuffle=True, random_state=None)[source]

• n_samplesобщее количество выборок, которые необходимо сгенерировать
• n_featuresколичество признаков на образец
• centersУказывает количество категорий
• cluster_stdпредставляет дисперсию каждого класса

import numpy as np
import matplotlib.pyplot as plt
# 导入 KMeans 模块和数据集
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs

# 定义画布
plt.figure(figsize=(12,12))

# 定义样本量和随机种子
n_samples = 1500
random_state = 170

# X是测试数据集，y是目标分类标签0，1，2
X, y = make_blobs(n_samples=n_samples, random_state=random_state)

X
array([[-5.19811282e+00,  6.41869316e-01],
       [-5.75229538e+00,  4.18627111e-01],
       [-1.08448984e+01, -7.55352273e+00],
       ...,
       [ 1.36105255e+00, -9.07491863e-01],
       [-3.54141108e-01,  7.12241630e-01],
       [ 1.88577252e+00,  1.41185693e-03]])

y
array([1, 1, 0, ..., 2, 2, 2])

# 预测值的簇类
y_pred = KMeans(n_clusters=2, random_state=random_state).fit_predict(X)
y_pred
array([0, 0, 1, ..., 0, 0, 0], dtype=int32)

X[:,0]  # 所有行的第1列数据
array([ -5.19811282,  -5.75229538, -10.84489837, ...,   1.36105255,
        -0.35414111,   1.88577252])

# 子图1的绘制
plt.subplot(221)
plt.scatter(X[:, 0], X[:, 1], c=y_pred)
plt.title("incorrrect Number of Blods")

transformation = [[0.60834549, -0.63667341],[-0.40887718, 0.85253229]]
X_aniso = np.dot(X, transformation)
y_pred = KMeans(n_clusters=3, random_state=random_state).fit_predict(X_aniso)
# 子图2的绘制
plt.subplot(222)
plt.scatter(X_aniso[:, 0], X_aniso[:, 1], c=y_pred)
plt.title("Anisotropicly Distributed Blobs")

X_varied, y_varied = make_blobs(n_samples=n_samples,
                               cluster_std=[1.0,2.5,0.5],random_state=random_state)
y_pred = KMeans(n_clusters=3, random_state=random_state).fit_predict(X_varied)
plt.subplot(223)
plt.scatter(X_varied[:, 0], X_varied[:, 1], c=y_pred)
plt.title("Unequal Variance")

X_filtered = np.vstack((X[y == 0][:500],
                      X[y == 1][:100],
                      X[y == 2][:10]))
y_pred = KMeans(n_clusters=3,random_state=random_state).fit_predict(X_filtered)
plt.subplot(224)
plt.scatter(X_filtered[:, 0],
           X_filtered[:, 1],
           c=y_pred)
plt.title("Unevenly Sized Blobs")
plt.show()

Python реализует алгоритм K-средних

Вот один из них, найденный в Интернете на основеPythonНайдите экспериментальный алгоритм K-средних, научитесь использовать