Unsupervised learning

import pandas as pd
import numpy as np

import matplotlib.pyplot as plt
import seaborn as sns
%matplotlib inline
%config InlineBackend.figure_format = 'svg'

import warnings
warnings.filterwarnings("ignore")

Кластеризация и снижение размерности

Основное отличие методов обучения без учителя от привычных классификаций и регрессий машинного обучения в том, что разметки для данных в этом случае нет.

Плюсы: можно использовать на больших объёмах данных, поскольку их не нужно будет размечать руками для обучения

Минусы: неясность измерения качества методов, из-за отсутствия таких же прямолинейных и интуитивно понятных метрик, как в задачах обучения с учителем.

Снижение размерности

Одной из самых очевидных задач, которые возникают в голове в отсутствие явной разметки, является задача снижения размерности данных. С одной стороны её можно рассматривать как помощь в визуализации данных, c другой стороны подобное снижение размерности может убрать лишние сильно скоррелированные признаки у наблюдений и подготовить данные для дальнейшей обработки в режиме обучения с учителем, например сделать входные данные более "перевариваемыми" для деревьев решений.

Объемы и сложность данных постоянно растут. В результате, существенно увеличивается и их размерность. Для компьютеров это не проблема — в отличие от людей: мы ограничены всего тремя измерениями.

Структура, скрытая в данных, может быть восстановлена только с помощью специальных математических методов. К ним относится подраздел машинного обучения без учителя под названием множественное обучение (manifold learning) или нелинейное уменьшение размерности (nonlinear dimensionality reduction).

t-SNE

t-SNE (t-distributed stochastic neighbor embedding) — техника нелинейного снижения размерности и визуализации многомерных переменных. Этот алгоритм может свернуть сотни измерений к меньшему количеству, сохраняя при этом важные отношения между данными: чем ближе объекты располагаются в исходном пространстве, тем меньше расстояние между этими объектами в пространстве сокращенной размерности. t-SNE неплохо работает на маленьких и средних реальных наборах данных и не требует большого количества настроек гиперпараметров.

Алгоритм t-SNE, который также относят к методам множественного обучения признаков, был опубликован в 2008 году голландским исследователем Лоуренсом ван дер Маатеном (сейчас работает в Facebook AI Research) и Джеффри Хинтоном. Классический SNE был предложен Хинтоном и Ровейсом в 2002. В статье 2008 года описывается несколько «трюков», которые позволили упростить процесс поиска глобальных минимумов, и повысить качество визуализации.

Параметры t-SNA из sk-learn:

  1. n_components=2. Количество измерений, до которых надо редуцировать данные.
  2. perplexity=30.0. При помощи перплексии вы можете настраивать чувствительность модели к локальным или глобальным паттернам данных. Если перплексия маленькая (≈1-5), модель будет хорошо вычленять небольшие группы похожих объектов, если большая — большие группы. Параметр, в каком-то смысле, является аналогом о числа ближайших соседей. В оригинальной статье говорится, что «SNE достаточно устойчив к изменениям в перплексии, а её типичные значения лежат в диапазоне от 5 до 50».
  3. early_exaggeration=12.0.
  4. learning_rate=200.0.
  5. n_iter=1000.
  6. n_iter_without_progress=300.
  7. min_grad_norm=1e-07.
  8. metric=’euclidean’.

Изменение модели в зависимости от перплексии.

from IPython.display import display, IFrame
IFrame(src="https://distill.pub/2016/misread-tsne/", width=960, height=615)
from IPython.display import display, IFrame
IFrame(src="https://www.youtube.com/embed/NEaUSP4YerM", width=560, height=315)
from sklearn.manifold import TSNE
from sklearn.preprocessing import StandardScaler
from sklearn import datasets


iris = datasets.load_iris()
X = iris.data
y = iris.target

iris_full = X[:]
iris_full = np.column_stack([iris_full, y])

scaler = StandardScaler()
iris_scaled = scaler.fit_transform(iris_full)

tsne = TSNE(random_state=17)
tsne_representation = tsne.fit_transform(iris_scaled)

plt.scatter(tsne_representation[:, 0], tsne_representation[:, 1])
plt.figure(figsize=(12, 12))
iris_full_df = pd.DataFrame(iris_full)

plt.scatter(
    tsne_representation[:, 0],
    tsne_representation[:, 1],
    c=iris_full_df[4].map({
        0: 'red',
        1: 'green',
        2: "blue"
    }))
from sklearn.manifold import TSNE
from sklearn.preprocessing import StandardScaler
from sklearn.impute import SimpleImputer

titanic = pd.read_csv(
    "https://github.com/agconti/kaggle-titanic/raw/master/data/train.csv")
    
for c in titanic.select_dtypes(include=[object]).columns:
    titanic[c] = pd.factorize(titanic[c])[0]
tsne = TSNE(n_components=2, perplexity=50, random_state=17)
tsne_representation = tsne.fit_transform(titanic_scaled)

plt.scatter(tsne_representation[:, 0], tsne_representation[:, 1])
plt.figure(figsize=(12, 12))
tsne = TSNE(n_components=2, perplexity=5, random_state=17)
tsne_representation = tsne.fit_transform(titanic_scaled)

plt.scatter(tsne_representation[:, 0], tsne_representation[:, 1])
plt.figure(figsize=(12, 12))
titanic.fillna({"Age": titanic["Age"].mean()}, inplace=True)

scaler = StandardScaler()
titanic_scaled = scaler.fit_transform(titanic)

tsne = TSNE(n_components=2, perplexity=30, random_state=17)
tsne_representation = tsne.fit_transform(titanic_scaled)

plt.scatter(tsne_representation[:, 0], tsne_representation[:, 1])
plt.figure(figsize=(12, 12))
plt.scatter(
    tsne_representation[:, 0],
    tsne_representation[:, 1],
    c=titanic["Pclass"].map({
        1: 'red',
        2: 'green',
        3: "blue"
    }))
plt.scatter(
    tsne_representation[:, 0],
    tsne_representation[:, 1],
    c=titanic["Sex"].map({
        0: "blue",
        1: "pink"
    }))

PCA

PCA помогает выразить несколько признаков через один, что позволяет работать с более простой моделью.

PCA аппроксимирует n-размерное облако наблюдений до эллипсоида (тоже n-мерного), полуоси которого и будут являться будущими главными компонентами. И при проекции на такие оси (снижении размерности) сохраняется наибольшее количество информации.

Вычисление главных компонент сводится к вычислению собственных векторов и собственных значений ковариационной матрицы исходных данных или к сингулярному разложению матрицы данных.

На PCA очень похож метод Многомерного шкалирование (Multi-dimensional scaling)

Pearson K., On lines and planes of closest fit to systems of points in space, Philosophical Magazine, (1901) 2, 559—572.

from IPython.display import display, IFrame
IFrame(src="https://www.youtube.com/embed/FgakZw6K1QQ", width=560, height=315)

Посмотрим, насколько PCA улучшит результаты для модели, которая в данном случае плохо справится с классификацией из-за того, что у неё не хватит сложности для описания данных:

from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score, roc_auc_score

iris = datasets.load_iris()
X, y = iris.data, iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=.3, 
                                                    stratify=y, # стратифицированная выборка
                                                    random_state=42)

# Для примера возьмём неглубокое дерево решений
clf = DecisionTreeClassifier(max_depth=2, random_state=42)
clf.fit(X_train, y_train)
preds = clf.predict_proba(X_test)
print('Accuracy: {:.5f}'.format(accuracy_score(y_test, 
                                                preds.argmax(axis=1))))
Accuracy: 0.88889

Теперь попробуем сделать то же самое, но с данными, для которых мы снизили размерность до 2D:

from sklearn import decomposition

pca = decomposition.PCA(n_components=2)
X_centered = X - X.mean(axis=0)
pca.fit(X_centered)
X_pca = pca.transform(X_centered)

plt.plot(X_pca[y == 0, 0], X_pca[y == 0, 1], 'bo', label='Setosa')
plt.plot(X_pca[y == 1, 0], X_pca[y == 1, 1], 'go', label='Versicolour')
plt.plot(X_pca[y == 2, 0], X_pca[y == 2, 1], 'ro', label='Virginica')
plt.legend(loc=0);
# Повторим то же самое разбиение на валидацию и тренировочную выборку.
X_train, X_test, y_train, y_test = train_test_split(X_pca, y, test_size=.3, 
                                                    stratify=y, 
                                                    random_state=42)

clf = DecisionTreeClassifier(max_depth=2, random_state=42)
clf.fit(X_train, y_train)
preds = clf.predict_proba(X_test)
print('Accuracy: {:.5f}'.format(accuracy_score(y_test, 
                                                preds.argmax(axis=1))))
Accuracy: 0.91111

Как правило, выбирают столько главных компонент, чтобы оставить 90% дисперсии исходных данных. У нас не так много признаков, так что даже один компонент даёт достаточно данных.

plt.figure(figsize=(10,7))
plt.plot(np.arange(1,3), np.cumsum(pca.explained_variance_ratio_), color='k', lw=2)
plt.xlabel('Number of components')
plt.ylabel('Total explained variance')
plt.xlim(1, 10)
plt.yticks(np.arange(0, 1.1, 0.1))
plt.axhline(0.9, c='r')
plt.show();

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

Кластерный анализ (Data clustering) — задача разбиения заданной выборки объектов (ситуаций) на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из схожих объектов, а объекты разных кластеров существенно отличались.

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

  1. Понимание данных путём выявления кластерной структуры. Разбиение выборки на группы схожих объектов позволяет упростить дальнейшую обработку данных и принятия решений, применяя к каждому кластеру свой метод анализа (стратегия «разделяй и властвуй»).
  2. Сжатие данных. Если исходная выборка избыточно большая, то можно сократить её, оставив по одному наиболее типичному представителю от каждого кластера.
  3. Обнаружение новизны (novelty detection). Выделяются нетипичные объекты, которые не удаётся присоединить ни к одному из кластеров.

Часто кластеризация используется как дополнительный метод: Clustering memes in social media

Виды кластеризации

По степени однозначности отнесения к кластерам.

  • Чёткая.
  • Нечёткая.

По подходу к образованию кластеров.

  • Плоская. Оптимизируем некоторую целевую функцию.
  • Иерархическая. Иерархические алгоритмы (также называемые алгоритмами таксономии) строят не одно разбиение выборки на непересекающиеся кластеры, а систему вложенных разбиений. Т.о. на выходе мы получаем дерево кластеров, корнем которого является вся выборка, а листьями — наиболее мелкие кластера.
    • Соединительная (Agglomerative).
    • Разделительная (Divisive).
  • Используемая для графов (Communities detection).

Метрики качества кластеризации

Задача оценки качества кластеризации является более сложной по сравнению с оценкой качества классификации. Во-первых, такие оценки не должны зависеть от самих значений меток, а только от самого разбиения выборки. Во-вторых, не всегда известны истинные метки объектов, поэтому также нужны оценки, позволяющие оценить качество кластеризации, используя только неразмеченную выборку.

Выделяют внешние и внутренние метрики качества. Внешние используют информацию об истинном разбиении на кластеры, в то время как внутренние метрики не используют никакой внешней информации и оценивают качество кластеризации, основываясь только на наборе данных. Оптимальное число кластеров обычно определяют с использованием внутренних метрик.

Все указанные ниже метрики реализованы в sklearn.metrics 1, 2.

Adjusted Rand Index (ARI)

Предполагается, что известны истинные метки объектов. Данная мера не зависит от самих значений меток, а только от разбиения выборки на кластеры. Пусть $n$ — число объектов в выборке. Обозначим через $a$ — число пар объектов, имеющих одинаковые метки и находящихся в одном кластере, через $b$ — число пар объектов, имеющих различные метки и находящихся в разных кластерах. Тогда Rand Index это

$$\text{RI} = \frac{2(a + b)}{n(n-1)}.$$

То есть это доля объектов, для которых эти разбиения (исходное и полученное в результате кластеризации) "согласованы". Rand Index (RI) выражает схожесть двух разных кластеризаций одной и той же выборки.

Чтобы этот RI давал значения близкие к нулю для случайных кластеризаций при любом n и числе кластеров, необходимо нормировать его. Так определяется Adjusted Rand Index:

$$\text{ARI} = \frac{\text{RI} - Expected[\text{RI}]}{\max(\text{RI}) - Expected[\text{RI}]}.$$

Эта мера симметрична, не зависит от значений и перестановок меток. Таким образом, данный индекс является мерой расстояния между различными разбиениями выборки. $ARI$ принимает значения в диапазоне $[−1,1]$. Отрицательные значения соответствуют "независимым" разбиениям на кластеры, значения, близкие к нулю, — случайным разбиениям, и положительные значения говорят о том, что два разбиения схожи (совпадают при $ARI=1$).

Силуэт (Silhouette)

В отличие от описанных выше метрик, данный коэффициент не предполагает знания истинных меток объектов, и позволяет оценить качество кластеризации, используя только саму (неразмеченную) выборку и результат кластеризации. Сначала силуэт определяется отдельно для каждого объекта. Обозначим через a — среднее расстояние от данного объекта до объектов из того же кластера, через b — среднее расстояние от данного объекта до объектов из ближайшего кластера (отличного от того, в котором лежит сам объект). Тогда силуэтом данного объекта называется величина:

$$s = \frac{b - a}{\max(a, b)}.$$

Силуэтом выборки называется средняя величина силуэта объектов данной выборки. Таким образом, силуэт показывает, насколько среднее расстояние до объектов своего кластера отличается от среднего расстояния до объектов других кластеров. Данная величина лежит в диапазоне $[−1,1]$. Чем больше силуэт, тем более четко выделены кластеры. С помощью силуэта можно выбирать оптимальное число кластеров $k$ (если оно заранее неизвестно) — выбирается число кластеров, максимизирующее значение силуэта. В отличие от предыдущих метрик, силуэт зависит от формы кластеров, и достигает больших значений на более выпуклых кластерах, получаемых с помощью алгоритмов, основанных на восстановлении плотности распределения.

Про другие меры качества и примеры из использования можно почитать в статье Сергея Королева.

Методы кластеризации

Method name Parameters Scalability Usecase Geometry (metric used)
K-Means number of clusters Very large n_samples, medium n_clusters with MiniBatch code General-purpose, even cluster size, flat geometry, not too many clusters Distances between points
Affinity propagation damping, sample preference Not scalable with n_samples Many clusters, uneven cluster size, non-flat geometry Graph distance (e.g. nearest-neighbor graph)
Mean-shift bandwidth Not scalable with n_samples Many clusters, uneven cluster size, non-flat geometry Distances between points
Spectral clustering number of clusters Medium n_samples, small n_clusters Few clusters, even cluster size, non-flat geometry Graph distance (e.g. nearest-neighbor graph)
Ward hierarchical clustering number of clusters Large n_samples and n_clusters Many clusters, possibly connectivity constraints Distances between points
Agglomerative clustering number of clusters, linkage type, distance Large n_samples and n_clusters Many clusters, possibly connectivity constraints, non Euclidean distances Any pairwise distance
DBSCAN neighborhood size Very large n_samples, medium n_clusters Non-flat geometry, uneven cluster sizes Distances between nearest points
Gaussian mixtures many Not scalable Flat geometry, good for density estimation Mahalanobis distances to centers
Birch branching factor, threshold, optional global clusterer. Large n_clusters and n_samples Large dataset, outlier removal, data reduction. Euclidean distance between points

Сравнение методов кластеризации

K-means

Алгоритм К-средних, наверное, самый популярный и простой алгоритм кластеризации и очень легко представляется в виде простого псевдокода:

  1. Выбрать количество кластеров k, которое нам кажется оптимальным для наших данных.
  2. Высыпать случайным образом в пространство наших данных k точек (центроидов).
  3. Для каждой точки нашего набора данных посчитать, к какому центроиду она ближе.
  4. Переместить каждый центроид в центр выборки, которую мы отнесли к этому центроиду.
  5. Повторять последние два шага фиксированное число раз, либо до тех пор пока центроиды не "сойдутся" (обычно это значит, что их смещение относительно предыдущего положения не превышает какого-то заранее заданного небольшого значения).

$$\sum_{i=0}^{n}\min_{\mu_j \in C}(||x_i - \mu_j||^2)$$

В случае обычной евклидовой метрики для точек лежащих на плоскости, этот алгоритм очень просто расписывается аналитически и рисуется. Давайте посмотрим соответствующий пример:

# Код взят из https://habrahabr.ru/company/ods/blog/325654/
# Начнём с того, что насыпем на плоскость три кластера точек
X = np.zeros((150, 2))

np.random.seed(seed=42)
X[:50, 0] = np.random.normal(loc=0.0, scale=.3, size=50)
X[:50, 1] = np.random.normal(loc=0.0, scale=.3, size=50)

X[50:100, 0] = np.random.normal(loc=2.0, scale=.5, size=50)
X[50:100, 1] = np.random.normal(loc=-1.0, scale=.2, size=50)

X[100:150, 0] = np.random.normal(loc=-1.0, scale=.2, size=50)
X[100:150, 1] = np.random.normal(loc=2.0, scale=.5, size=50)

# В scipy есть замечательная функция, которая считает расстояния
# между парами точек из двух массивов, подающихся ей на вход
from scipy.spatial.distance import cdist

# Прибьём рандомность и насыпем три случайные центроиды для начала
np.random.seed(seed=42)
centroids = np.random.normal(loc=0.0, scale=1., size=6)
centroids = centroids.reshape((3, 2))

cent_history = []
cent_history.append(centroids)

for i in range(3):
    # Считаем расстояния от наблюдений до центроид
    distances = cdist(X, centroids)
    # Смотрим, до какой центроиде каждой точке ближе всего
    labels = distances.argmin(axis=1)

    # Положим в каждую новую центроиду геометрический центр её точек
    centroids = centroids.copy()
    centroids[0, :] = np.mean(X[labels == 0, :], axis=0)
    centroids[1, :] = np.mean(X[labels == 1, :], axis=0)
    centroids[2, :] = np.mean(X[labels == 2, :], axis=0)

    cent_history.append(centroids)
    
    
# А теперь нарисуем всю эту красоту
plt.figure(figsize=(8, 8))
for i in range(4):
    distances = cdist(X, cent_history[i])
    labels = distances.argmin(axis=1)

    plt.subplot(2, 2, i + 1)
    plt.plot(X[labels == 0, 0], X[labels == 0, 1], 'bo', label='cluster #1')
    plt.plot(X[labels == 1, 0], X[labels == 1, 1], 'co', label='cluster #2')
    plt.plot(X[labels == 2, 0], X[labels == 2, 1], 'mo', label='cluster #3')
    plt.plot(cent_history[i][:, 0], cent_history[i][:, 1], 'rX')
    plt.legend(loc=0)
    plt.title('Step {:}'.format(i + 1));