Неконтролируемое обучение и интуиция, лежащая в основе кластеризации K-средних

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

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

Давайте приступим к делу.

Алгоритмы неконтролируемого обучения

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

где все {x^(1), x^(2),...x^(m)} (обучающий ввод) имели соответствующее значение {y^(1),y^(2),...y^(m)} (обучающая метка), указывающее, какое фактическое значение. Обладая этой информацией, мы смогли обучить нашу модель, используя обучающие входные данные, и сравнить наше прогнозируемое значение с фактической обучающей меткой. Мы назвали это контролируемым обучением. При обучении без учителя наши данные теперь выглядят примерно так:

Все, что у нас есть, - это обучающий ввод {x^(1), x^(2),...x^(m)}, и мы не понимаем ярлыков этих вводов, т.е. нет {y^(1),y^(2),...y^(m)}. Цель алгоритма обучения без учителя - найти некоторый порядок в этих данных путем создания различных групп на основе сходства между точками. Эти группы называются кластерами. Вот пример того, как алгоритм обучения без учителя может создавать различные кластеры из данных обучения, показанных на рисунке 2:

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

К-средние

Интуиция

Лучше всего понять этот алгоритм на примере. Поэтому рассмотрим следующий график:

Мы хотим сгруппировать похожие точки данных в кластеры. Первое, что сделает K-Means, это выберет k произвольных точек. Мы называем эти точки центроидами. В нашем примере мы выберем k = 3, отмеченный красным, синим и черным крестиками:

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

Теперь мы перемещаем наши центроиды, вычисляя среднее значение всех назначенных им тренировочных точек, используя следующую формулу:

В уравнении 1 выше m^K представляет количество обучающих примеров, назначенных кластеру K. И, наконец, мы повторяем процесс до тех пор, пока не перестанем видеть изменение положения наших центроидов (пока мы не сойдемся), то есть среднее расстояние от обучающих точек до назначенных им центроидов будет минимальным:

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

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

Где m сейчас - общее количество тренировочных очков. Итак, это уравнение, которое мы пытаемся минимизировать, это наша функция стоимости для K-средних.

Что нужно учитывать

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

Всегда ли мы приближаемся к глобальному оптимуму?

Ответ - нет. Рассмотрим следующий график:

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

Хотя график на рисунке 10, очевидно, является правильным решением, вполне возможно, что K-среднее значение сходится к локальному оптимуму вместо глобального, оставляя нам неточные результаты, подобные тем, что показаны на рисунках 11. и 12. Математически доказать это сложно, но есть отличный способ визуализировать это. Учтите эти два момента:

.     .
.     .

Решение вроде следующего (где c - кластер):

.  c  .
.  c  .

Действительно, но лучшим решением будет:

.     .
c     c
.     .

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

Как случайно инициализировать центроиды?

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

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

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

Обратите внимание, что это все еще не гарантирует, что мы не достигнем локального оптимума, но снижает шансы.

Как выбрать K?

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

Из немногих доступных техник наиболее широко используется метод локтя. Он работает путем сравнения стоимости и количества кластеров K:

В этом случае мы видим значительное снижение стоимости между K=1 и K=2 и между K=2 и K=3, но впоследствии оно начинает уменьшаться гораздо медленнее, поэтому мы можем сделать вывод, что K=3 - правильное количество центроидов. Но, хотя всегда стоит попробовать этот метод, чаще всего ваш график будет выглядеть примерно так:

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

Опять же, лучший на данный момент метод - это просто просмотреть ваши данные вручную.

Заключение

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

В следующей статье мы обсудим уменьшение размерности.

Прошлые статьи

  1. Часть первая: Предварительная обработка данных
  2. Часть вторая: Линейная регрессия с использованием градиентного спуска: интуиция и реализация
  3. Часть третья: Логистическая регрессия с использованием градиентного спуска: интуиция и реализация
  4. Часть четвертая - 1: Нейронные сети. Часть 1: Терминология, мотивация и интуиция
  5. Часть четвертая - 2: Нейронные сети. Часть 2: обратное распространение и проверка градиента
  6. Часть шестая: Оценка вашей гипотезы и понимание систематической ошибки в сравнении с дисперсией
  7. Часть седьмая: Опорные векторные машины и ядра

Бесстыдный штекер

использованная литература

  1. Курс Coursera по машинному обучению Эндрю Нг
  2. Переполнение стека: почему К-средние не дают глобальных минимумов?