Добро пожаловать в седьмую часть нашего открытого курса машинного обучения!

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

Краткое содержание статьи

  1. Вступление
  2. Анализ главных компонентов
  • Интуиция, теории и прикладные проблемы
  • Примеры применения

3. Кластерный анализ

  • K-означает
  • Распространение сродства
  • Спектральная кластеризация
  • Агломеративная кластеризация
  • Метрики точности

4. Задание №7.

5. Полезные ссылки

1. Введение

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

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

2. Анализ главных компонентов (PCA)

Интуиция, теории и прикладные проблемы

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

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

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

Давайте посмотрим на математическую формулировку этого процесса:

Чтобы уменьшить размерность наших данных с n до k при k ≤ n, мы сортируем наш список осей в порядке уменьшения дисперсии и берем верхние k из них.

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

где µ - математическое ожидание i-го признака. Стоит отметить, что ковариация симметрична, а ковариация вектора сама с собой равна его дисперсии.

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

Краткое резюме: матрицы, как линейные операторы, имеют собственные значения и собственные векторы. Они очень удобны, потому что описывают части нашего пространства, которые не вращаются и растягиваются только тогда, когда мы применяем к ним линейные операторы; собственные векторы остаются в том же направлении, но растягиваются на соответствующее собственное значение. Формально матрица M с собственным вектором w и собственным значением λ удовлетворяет этому уравнению:

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

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

Примеры

Набор данных по радужной оболочке Фишера

Начнем с загрузки всех основных модулей и опробуем пример iris из scikit-learn документации.

Теперь давайте посмотрим, как PCA улучшит результаты простой модели, которая не может правильно соответствовать всем обучающим данным:

Accuracy: 0.88889

Давайте попробуем еще раз, но на этот раз уменьшим размерность до двух измерений:

Accuracy: 0.91111

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

Теперь давайте посмотрим, какой процент отклонения можно объяснить каждым из выбранных компонентов.

1 component: 92.46% of initial variance 0.362 x sepal length (cm) + -0.082 x sepal width (cm) + 0.857 x petal length (cm) + 0.359 x petal width (cm) 
2 component: 5.3% of initial variance 0.657 x sepal length (cm) + 0.730 x sepal width (cm) + -0.176 x petal length (cm) + -0.075 x petal width (cm)

Набор данных рукописных чисел

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

Начнем с визуализации наших данных. Получите первые 10 чисел. Цифры представлены матрицами 8 x 8 с интенсивностью цвета для каждого пикселя. Каждая матрица сведена в вектор из 64 чисел, поэтому мы получаем функциональную версию данных.

Наши данные имеют 64 измерения, но мы собираемся уменьшить их до двух и увидеть, что даже с двумя измерениями мы можем ясно видеть, что цифры разделяются на кластеры.

Projecting 64-dimensional data to 2D

Действительно, с t-SNE картина выглядит лучше, поскольку PCA имеет линейное ограничение, а t-SNE - нет. Однако даже с таким небольшим набором данных алгоритм t-SNE требует значительно больше времени для выполнения, чем PCA.

CPU times: user 29.3 s, sys: 2.97 s, total: 32.3 s Wall time: 32.3 s

На практике мы бы выбрали такое количество главных компонентов, чтобы можно было объяснить 90% разброса исходных данных (через explained_variance_ratio). Здесь это означает сохранение 21 главного компонента; поэтому мы уменьшаем размерность с 64 до 21.

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

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

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

K-означает

Алгоритм K-средних - самый популярный и в то же время самый простой из всех алгоритмов кластеризации. Вот как это работает:

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

Этот алгоритм легко описать и визуализировать. Давайте взглянем.

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

Еще одна «особенность» этого алгоритма - его чувствительность к начальному положению центроидов кластера. Вы можете запустить алгоритм несколько раз, а затем усреднить все результаты центроидов.

Выбор количества кластеров для K-средних

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

где C - множество кластеров со степенью K, µ - центроид кластера.

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

Чтобы избежать этого случая, мы должны выбрать количество кластеров, после которого функция J (C) убывает менее быстро. Более формально

Давайте посмотрим на пример.

Мы видим, что J (C) значительно уменьшается, пока количество кластеров не станет 3, а затем больше не меняется. Это означает, что оптимальное количество кластеров - 3.

Проблемы

По сути, K-means NP-сложен. Для d измерений, k кластеров и n наблюдений мы найдем решение за O (n ^ (dk + 1)) во времени. Есть некоторые эвристики, чтобы справиться с этим; Примером является MiniBatch K-means, который берет части (пакеты) данных вместо того, чтобы соответствовать всему набору данных, а затем перемещает центроиды, принимая среднее значение из предыдущих шагов. Сравните реализацию K-means и MiniBatch K-means в документации sckit-learn.

Реализация алгоритма с использованием scikit-learn имеет свои преимущества, такие как возможность указывать количество инициализаций с помощью параметра функции n_init, что позволяет нам идентифицировать более устойчивые центроиды. Более того, эти прогоны можно выполнять параллельно, чтобы сократить время вычислений.

Распространение сродства

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

Давайте определим метрику подобия так, что s (x, y) ›s (x, z), если наблюдение x больше похоже на наблюдение y и меньше похоже на наблюдение z. Простым примером такой метрики подобия является отрицательный квадрат расстояния s (x, y) = - || x - y || ².

Теперь давайте опишем «соответствие», составив две нулевые матрицы. Один из них, r, определяет, насколько хорошо k-е наблюдение является «образцом для подражания» для i-го наблюдения по отношению ко всем другим возможным «образцам для подражания». Другая матрица, a, определяет, насколько целесообразно для i-го наблюдения использовать k-е наблюдение в качестве «ролевой модели». Это может показаться запутанным, но это станет более понятным после некоторой практики.

Матрицы обновляются последовательно по следующим правилам:

Спектральная кластеризация

Спектральная кластеризация объединяет некоторые из описанных выше подходов для создания более сильного метода кластеризации.

Прежде всего, этот алгоритм требует от нас определения матрицы подобия для наблюдений, называемой матрицей смежности. Это можно сделать аналогично алгоритму Affinity Propagation, так что матрица A содержит отрицательный квадрат расстояний между соответствующими точками. Эта матрица описывает полный граф с наблюдениями как вершинами и оцененным значением сходства между парой наблюдений как весами ребер для этой пары вершин. Для определенной выше метрики и двумерных наблюдений это довольно интуитивно понятно - два наблюдения похожи, если граница между ними короче. Мы хотим разбить график на два подграфа таким образом, чтобы каждое наблюдение в каждом подграфе было похоже на другое наблюдение в этом подграфе. Формально это задача нормализованных разрезов; для более подробной информации рекомендуем прочитать эту статью.

Агломеративная кластеризация

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

Алгоритм довольно простой:

  1. Мы начинаем с присвоения каждому наблюдению отдельного кластера.
  2. Затем отсортируйте попарные расстояния между центрами кластеров в порядке убывания.
  3. Возьмите два ближайших соседних кластера и объедините их вместе и пересчитайте центры.
  4. Повторяйте шаги 2 и 3, пока все данные не будут объединены в один кластер.

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

  1. Одиночная связь - расстояние между центроидами - это минимальное расстояние между всеми парами точек, где одна от первого кластера, а вторая от другого.
  2. Полная связь - расстояние между центроидами - это максимальное расстояние между всеми парами точек, где одна находится от первого кластера, а вторая - от другого.
  3. Среднее сцепление - расстояние между центроидами - это скорректированная сумма всех расстояний между всеми парами точек, где одна от первого кластера, а вторая от другого.
  4. Связь центроидов - расстояние между центроидами - это расстояние между их геометрическими центрами кластеров.

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

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

Давайте рассмотрим пример с кластерами, которые мы получили от K-means:

Метрики точности

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

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

Все описанные ниже показатели реализованы в sklearn.metrics.

Скорректированный индекс ранда (ARI)

Здесь мы предполагаем, что истинные названия объектов известны. Этот показатель зависит не от значений меток, а от разбивки кластера данных. Пусть N будет количеством наблюдений в выборке. Пусть a - количество пар наблюдений с одинаковыми метками и расположенных в одном кластере, а b - количество наблюдений с разными метками и расположенных в разных кластерах. Индекс Rand можно рассчитать по следующей формуле: RI = 2 (a + b) / n (n - 1) Другими словами, он оценивает долю наблюдений, для которых эти разбиения (исходный результат и результат кластеризации) согласованы. Индекс Рэнда (RI) оценивает сходство двух разбиений одного и того же образца. Чтобы этот индекс был близок к нулю для любых результатов кластеризации с любым n и любым количеством кластеров, необходимо его масштабировать, следовательно, Скорректированный индекс ранда: ARI = (RI - E (RI)) / (max (RI) ) - E (RI)).

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

Скорректированная взаимная информация (AMI)

Эта метрика похожа на ARI. Он также симметричен и не зависит от значений и перестановки меток. Он определяется функцией [энтропия] (https://en.wikipedia.org/wiki/Entropy_(information_theory) и интерпретирует разбиение выборки как дискретное распределение (вероятность отнесения к кластеру равна проценту от объектов в нем). Индекс MI определяется как взаимная информация для двух распределений, соответствующая выборке, разбитой на кластеры. Интуитивно, взаимная информация измеряет долю информации, общей для обоих кластерных разбиений, т.е. уменьшает неопределенность другого.

AMI определяется аналогично ARI. Это позволяет нам избавиться от увеличения индекса MI с увеличением количества кластеров. AMI находится в диапазоне [0, 1]. Значения, близкие к нулю, означают, что разделения независимы, а значения, близкие к 1, означают, что они похожи (с полным совпадением при AMI = 1).

Однородность, полнота, V-мера

Формально эти метрики также определяются на основе функции энтропии и функции условной энтропии, интерпретируя разбиения выборки как дискретные распределения:

где K - результат кластеризации, а C - начальное разбиение. Следовательно, h оценивает, состоит ли каждый кластер из одних и тех же объектов класса, а c измеряет, насколько хорошо одни и те же объекты класса подходят кластерам. Эти показатели не симметричны. Оба лежат в диапазоне [0, 1], а значения, близкие к 1, указывают на более точные результаты кластеризации. Значения этих показателей не масштабируются, как показатели ARI или AMI, и поэтому зависят от количества кластеров. Результат случайной кластеризации не будет иметь значений метрик, близких к нулю, когда количество кластеров достаточно велико, а количество объектов мало. В таком случае разумнее было бы использовать ARI. Однако при большом количестве наблюдений (более 100) и количестве кластеров менее 10 этот вопрос менее критичен, и его можно игнорировать.

V-мера - это комбинация h и c и их среднее гармоническое значение: v = (2hc) / (h + c). Он симметричен и измеряет, насколько согласованы два результата кластеризации.

Силуэт

В отличие от метрики, описанной выше, этот коэффициент не подразумевает знания об истинных названиях объектов. Это позволяет нам оценить качество кластеризации, используя только исходную, немеченую выборку и результат кластеризации. Для начала для каждого наблюдения вычисляется коэффициент силуэта. Пусть a будет средним расстоянием между объектом и другими объектами в одном кластере, а b будет средним расстоянием от объекта до объекта из ближайшего кластера (отличного от того, к которому объект принадлежит). Тогда мера силуэта этого объекта равна s = (b - a) / max (a, b).

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

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

В заключение давайте посмотрим, как эти показатели работают с набором данных рукописных чисел MNIST:

4. Задание №7.

Полные версии заданий объявляются каждую неделю при новом запуске курса (1 октября 2018 г.). А пока вы можете потренироваться с демо-версией: Kaggle Kernel, nbviewer.

5. Полезные ссылки

Автор: Сергей Королев, инженер-программист Snap Inc. Перевод и редактирование: Анна Головченко, Юрий Кашницкий и Юаньюань Пао.