Задачи обучения без учителя

Машинное обучение без учителя (unsupervised learning, редко - неконтролируемое обучение) - это набор задач машинного обучения и анализа данных, при которых модель обучается выявлять внутренние паттерны и структуры в данных. При обучении без учителя в наборе данных (датасете) не выделяется явная целевая переменная.

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

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

Модели обучения без учителем отвечают на другие вопросы о данных. Конечно, так как они относятся к моделям машинного обучения, данные все равно обязательно должны быть, именно на них модель учится - то есть подбирвает свои параметры. Но сама модель формализует внутреннюю структуру в этих данных. Конкретная цель моделирования в задачах обучения без учителя разная. Есть несколько типов задач обучения без учителя, и они отвечают на совершенно разные вопросы о данных.

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

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

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

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

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

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

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

Определение количества кластеров - это одна из проблем при построении моделей. Обычно мы не знаем его заранее. Но можем пробовать разное количество и анализировать полученное рапределение объектов по кластерам.

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

После кластеризации модель выдает принадлежность объектов кластерам. При этом сами кластеры не имеют никакого общего смысла. Эту результирующую группировку необходимо анализировать вручную и интерпретировать кластеры судя по тому, какие объекты в них находятся. При этом некоторые алгоритмы могут дополнительно выделять “шум” - объкты, которые не отнесены ни к одному кластеру.

Метод K-средних

Метод К-средних (K means) - это один из самых популярных алгоритмов кластеризации. По аналогии с методом k ближайших соседей он основан на идее вычисления расстояний между точками выборки. Алгоритм строится на приципе минимизации внутрикластерного расстояния, то есть метрики WCSS (within-cluster sum of squares):

где k - число кластеров, $S_i$ - сами кластеры, $\mu_i$ - центр i-го кластера.

Для начала работы алгоритма необходимо задать необходимое количество кластеров. Затем в пространстве признаков выбираются случайные центры этих кластеров. Центры желательно выбирать так, чтобы к каждому кластеру принадлежала хотя бы одна точка. Есть несколько алгоритмов выбора

Затем алгоритм итеративно повторяет два шага:

На этапе распределения каждая точка относится к тому кластеру, центр которого к ней ближе. На этапе обновления центр каждого кластера заменяется на центр масс всех принадлежащих точек.

Рано или поздно на этапе обновления центры кластеров сместятся так, что ни одна точка не поменяет своего распределения. Это означает схождение алгоритма и завершение цикла. Итоговые центры кластеров и определяют результат кластеризации.

Алгоритм сходится всегда. Правда, иногда алгоритм “сваливается” в локальный оптимум:

Алгоритм имеет экспоненциальную сложность по количеству признаков. Поэтому в очень высокомерных пространствах он может быть неэффективен.

Большим недостатком метода является то, что для его инициализации нужно задать количество кластеров. Обычно оно не известно заранее. Для выбора лучшего количества применяют “метод локтя”. Для этого нужно построить кластеризацию с разным количеством кластеров и построить график зависимости метрики WCSS от количества кластеров. Чем больше количество, тем более равномерными они получатся. Поэтому мы увидим примерно такую картину:

Метод локтя заключается а том, что мы выбираем такое количество кластеров, которое сильно снижает метрику WCSS, а при большем количестве она снижается уже не так сильно. То есть мы ищем “локоть” на этом графике. В данном примере адекватное количество кластов - 2 или 3.

1
2
3
4
5
6
7
8
9
10
11
from sklearn import datasets
from sklearn.cluster import KMeans

iris_df = datasets.load_iris()

model = KMeans(n_clusters=3)

model.fit(iris_df.data)

predicted_label = model.predict([[7.2, 3.5, 0.8, 1.6]])
all_predictions = model.predict(iris_df.data)

Иерархическая кластеризация

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

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

Разделяющая кластеризация менее распространена. При таком алгоритме наоборот, происходит последовательное разделение кластеров так, чтобы минимизировать метрику WCSS или другую выбранную.

1
2
3
4
5
6
7
8
9
from sklearn.cluster import AgglomerativeClustering 
import numpy as np 
  
X = np.array([[1, 2], [1, 4], [1, 0], 
              [4, 2], [4, 4], [4, 0]]) 
 
clustering = AgglomerativeClustering(n_clusters=2).fit(X) 
  
print(clustering.labels_) 

При объединении двух кластеров необходимо проверять расстояние между ними в каждой паре кластеров и объединяем пару с наименьшим расстоянием/наибольшим сходством. Но вопрос в том, как определяется это расстояние. Существуют различные способы определения расстояния/сходства между кластерами. Самые распространенные:

Метод Уорда: Сходство двух кластеров основано на увеличении WCSS при объединении двух кластеров.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from scipy.cluster.hierarchy import linkage, dendrogram
import matplotlib.pyplot as plt
import pandas as pd

seeds_df = pd.read_csv("http://qps.ru/jNZUT")
varieties = list(seeds_df.pop('grain_variety'))

samples = seeds_df.values

mergings = linkage(samples, method='complete')

dendrogram(mergings,
           labels=varieties,
           leaf_rotation=90,
           leaf_font_size=6,
           )

plt.show()

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

Таким образом по дендрограмме можно определить относительную близость объектов. А выбрав определенный уровень метрики, то есть уровень на вертикальной шкале, можно определить нужные по задаче кластеры.

DBSCAN

DBSCAN (Density-Based Spatial Clustering of Applications with Noise, плотностный алгоритм пространственной кластеризации с присутствием шума) – популярный алгоритм кластеризации, используемый в анализе данных в качестве одной из замен метода k-средних.

Методы, основанные на разделении точек (K-средние, PAM-кластеризация) и иерархические методы кластеризации позволяют находить кластеры близкой к сферической формы и выпуклые кластеры. Другими словами, они подходят только для компактных и хорошо разделенных кластеров. Кроме того, на них также серьезно влияет наличие шума и выбросов в данных.

Реальные данные могут содержать проблемы, которые существенно осложняют применение таких классических методво кластеризации:

Алгоритм DBSCAN решает эти проблемы тем, что оперирует понятиями плотности, связности и достижимости точек. На концептуальном уровне он ближе к интуитивному пониманию понятия “кластер” человеком.

Для работы алгоритма DBSCAN необходимо выбрать значение двух параметров - радиус окрестности точки $\epsilon$ и минимальное количество точек в этом радиусе $m$. Основа алгоритма DBSCAN в том, что все точки выборки делятся на три категории.

Основные (центральыне) точки - это такие точки выборки, в окрестностях которых (радиусом, который задан перед началом работы алгоритма $\epsilon$) находятся не менее заданного количества точек $m$. Например на картинке ниже минимальное количество точек задано равным 4, а радиус окрестности показан окружностями:

Неосновная точка - это такая, в окрестностях которой меньше заданного количества точек $m$, но есть хотя бы одна основная. А точка шума - это та, в окрестностях которой мало точек, и нет ни одной основной.

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

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

Применение алгоритма в библиотеке sklearn ничем не отличается от других моделей кластеризации:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
X, y_true = make_blobs(n_samples=300, centers=4,
                       cluster_std=0.50, random_state=0)

db = sklearn.cluster.DBSCAN(eps=0.3, min_samples=10).fit(X)
core_samples_mask = np.zeros_like(db.labels_, dtype=bool)
core_samples_mask[db.core_sample_indices_] = True
labels = db.labels_

n_clusters_ = len(set(labels)) - (1 if -1 in labels else 0)

for k, col in zip(set(labels), ['y', 'b', 'g', 'r']):
    if k == -1:
        col = 'k' 
    class_member_mask = (labels == k)
 
    xy = X[class_member_mask & core_samples_mask]
    plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=col)
 
    xy = X[class_member_mask & ~core_samples_mask]
    plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=col)
 
plt.title('number of clusters: %d' % n_clusters_)

Обратите внимание на работу с полями обученной модели. В этом листинге основной объем занимает работа с организацией визуализации построенных кластеров. Этот код генерирует такой результат:

В сравнении с методом К-средних особенно ярко проявляются специфические черты алгоритма DBSCAN относительно распозначания формы кластеров и работы с шумом:

Алгоритм довольно чувствителен к выбору изначальных параметров $m$ и $\epsilon$:

Существуют эвристики для выбора $m$ и $\epsilon$. Чаще всего применяется такой метод и его вариации:

1. Выберите $m$. Обычно используются значения от 3 до 9, чем более неоднородный ожидается датасет, и чем больше уровень шума, тем большим следует взять $m$.
2. Вычислите среднее расстояние по $m$ ближайшим соседям для каждой точки. Т.е. если $m=3$, нужно выбрать трёх ближайших соседей, сложить расстояния до них и поделить на три.
3. Сортируем полученные значения по возрастанию и выводим на экран.
4. Видим что-то вроде такого резко возрастающего графика. Следует взять $\epsilon$ где-нибудь в полосе, где происходит самый сильный перегиб. Чем больше $\epsilon$, тем больше получатся кластеры, и тем меньше их будет.

HDBSCAN

OPTICS

Метод нечетких C-средних

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

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

Большое количество признаков может доставлять следующие сложности в процессе проведения анализа данных и машинного обучения:

Совокупность этих факторов приводит к тому, что эффективность моделей машинного обучения может снижаться с ростом количества признаков:

Понижение размерности стремится представить данные с меньшим количеством признаков. Во многом это работает как проекция исходного многообразия точек. Естественно, выбор проекции оказывает существенное влияние на результат:

При этом для проекции можно выбирать не только оси исходного пространства, но и произвольные вектора:

При этом некоторые проекции оказываются хуже или лучше других. Например, проекция, которая “перемешивает” точки исходного распределения не очень эффективна:

Искусство понижения размерности как раз состоит в том, чтобы выбрать такие проекции исходного датасета, чтобы максимально сохранить информацию об исходном распределении или разделение данных по классам:

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

При этом надо помнить, что понижение размерности как правило свзано с потерей информации об исходном датасете. Чем большее сокращение произвести, тем больше информации теряется. Поэтому выбор количества измерений тоже представляет собой нетривиальную задачу. Как правило, для методов понижения размерности мы сами задаем желаемое количество измерений.

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

PCA

Наиболее популярным алгоритмом сокращения размерности является метод главных компонент (principal component analysis, PCA). В этом методе переменные преобразуются в новый набор переменных, которые являются линейной комбинацией исходных переменных. Эти новые переменные известны как основные или главные компоненты. Они получаются таким образом, что первая компонента учитывает большую часть возможного изменения исходных данных, после чего каждая последуюая компонента имеет максимально возможную дисперсию.

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

Учитывая две функции: $x_1$ и $x_2$, мы хотим найти одну такую переменную, которая эффективно описывает обе функции одновременно. Затем мы сопоставляем наши старые функции с этой новой строкой, чтобы получить новую отдельную функцию. То же самое можно сделать с тремя функциями, где мы сопоставляем их с плоскостью.

Цель PCA - уменьшить среднее значение всех расстояний каждой функции до линии проецирования. Это называется ошибка проецирования. Либо можно анализировать процент исходной дисперсии данных, который сохранился после уменьшения размерности:

Векторы главных компонент могут быть найдены как решения однотипных задач оптимизации:

Централизуются данные (вычитанием среднего): $x_i := x_i - \bar{X}$. Теперь $\sum_{i=1}^m = 0$;

Отыскивается первая главная компонента как решение задачи: $a_1 = argmin (\sum_{i=1}^m || x_i - a_1(a_1, x_i) ||^2)$. если решение не единственно, то осуществляется выбор одного из них.

Из данных вычитается проекция на первую главную компоненту: $x_i := x_i - a_1(a_1, x_i)$.

Отыскивается вторая главная компонента как решение задачи: $a_2 = argmin (\sum_{i=1}^m || x_i - a_2(a_2, x_i) ||^2)$. Если решение не единственно, то выбирается одно из них.

Далее процесс продолжается итеративно.

Смысл первой главной компоненты в том, что это такое направление, вдоль которого дисперсия исходного датасета максимальна:

Поэтому если спроецировать точки данных на это направление, это максимально сохранит информацию о взаимном их расположении.

После окончания работы метода PCA можно выбрать столько компонент, сколько необходимо. Берутся последовательно компоненты, начиная с главной. Таким образом можно получить проекцию исходного датасета на любое количество измерений:

Иногда нужное количество измерений естественно следует из постановки задачи. В остальных случаях требуется выбрать количество измрений. Нужно понимать компромисс - чем больше измерений оставить, тем больше информации сохранится, но тем меньше смысла в преобразовании. Чем сильнее понизить размерность, тем больше информации теряется, но датасет становится компактнее. Можно воспользоваться

PCA не является линейной регрессией. В линейной регрессии мы минимизируем квадрат ошибки от каждой точки до нашей линии предиктора. Это вертикальные расстояния. В PCA мы минимизируем кратчайшее расстояние или кратчайшие ортогональные расстояния до наших точек данных. В более общем плане, в линейной регрессии, мы берем все наши примеры в x и применяем параметры в $b_i$ для предсказания y. В PCA мы берем ряд функций и находим среди них наиболее близкий общий набор данных. Мы не пытаемся предсказать какой-либо результат, и мы не применяем к ним веса.

Рассмотрим применение метода PCA в Python на примере сгенерированного датасета:

1
2
3
4
5
6
7
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons
 
X, y = make_moons(n_samples=500, noise=0.02, random_state=417)
 
plt.scatter(X[:, 0], X[:, 1], c=y)
plt.show()

Так выглядит исходный датасет:

Создадим и обучим простой метод главных компонент:

1
2
3
4
5
6
7
8
9
from sklearn.decomposition import PCA
pca = PCA(n_components=2)
X_pca = pca.fit_transform(X)
 
plt.title("PCA")
plt.scatter(X_pca[:, 0], X_pca[:, 1], c=y)
plt.xlabel("Component 1")
plt.ylabel("Component 2")
plt.show()

После преобразования мало что изменяется. Немного смещаются вектора проекции, что ведет к “наклону” исходного распределения:

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

1
2
3
4
5
6
7
from sklearn.decomposition import KernelPCA
kpca = KernelPCA(kernel='rbf', gamma=15)
X_kpca = kpca.fit_transform(X)
 
plt.title("Kernel PCA")
plt.scatter(X_kpca[:, 0], X_kpca[:, 1], c=y)
plt.show()

Это уже приводит к совершенно другому проеобразованию:

ICA

Случайная проекция

NMF

T-SNE

UMAP

Обнаружение аномалий

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

Под аномалией понимается некий объект, который сильно отличается от “нормы”, отклонение, исключение, редкое событие, которое не вписывается в общую зависимость, паттерн. Аномальные объекты часто свидетельствуют о нарушении каких-то зависимостей, подозрительных объектах.

Различают следующие типы аномалий:

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

Контекстуальный выброс, это такой у которого значение не соответствует тому, что ожидается для аналогичной точки данных в том же контексте. Контексты обычно являются временЫыми, и одна и та же ситуация, наблюдаемая в разное время, может не быть выбросом. Например, для магазинов вполне нормально наблюдать увеличение числа покупателей в праздничный сезон. Однако, если внезапный всплеск происходит вне праздничных дней или распродаж, это можно рассматривать как контекстуальное отклонение.

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

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

Ключевой характеристикой аномалий является их редкость. Если аномальное поведение объектов встречается часто, это уже не может считаться аномалией. Поэтому при использовании алгоритмов обучения с учителем (классификации) существенная проблема дисбаланса классов. Аномальный объект вполне может встретиться на 10 000 или даже миллион нормальных объектов.

Поэтому хотя классические методы классификации, такие как KNN или SVM могут применяться для обнаружения аномалий, они не очень эффективны.

Нахождение аномалий в датасете с произвольным количеством признаков может быть не так тривиально, как могло бы показаться. Ведь большое количество признаков соответствует большому числу измерений. А объект может быть выборосом не по значению одного или пары признаков в отдельности, а по совокупности харкактеристик:

Алгоритм DBSCAN, который применяется для определения кластеров может также указать на аномалии. В этом алгоритме - это точки шума, которые не попали ни в один кластер:

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

Вот пример применения этого метода в бибилиотеке sklearn в Python:

1
2
3
4
5
6
from sklearn.neighbors import LocalOutlierFactor

clf = LocalOutlierFactor(n_neighbors=20, contamination=0.1)
y_pred = clf.fit_predict(X)
n_errors = (y_pred != ground_truth).sum()
X_scores = clf.negative_outlier_factor_