Кластерный анализ | Вводный курс ML

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

Все курсы > Вводный курс > Занятие 16

Основная идея кластерного анализа (clustering, cluster analysis) заключается в том, чтобы разбить объекты на группы или кластеры таким образом, чтобы внутри группы эти наблюдения были более похожи друг на друга, чем на объекты другого кластера.

При этом мы заранее не знаем на какие кластеры необходимо разбить наши данные. Это связано с тем, что мы обучаем модель на неразмеченных данных (unlabeled data), то есть без целевой переменной, компонента y. Именно поэтому в данном случае говорят по машинное обучение без учителя (Unsupervised Learning).

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

Как же разбить данные на кластеры?

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

В рамках этого занятия мы поговорим про алгоритм, который называется методом k-средних (k-means clustering method).

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

Давайте пошагово разберемся в том, как работает этот алгоритм.

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

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

В частности, T1 будет отнесена к C2.

Шаг 3. Таким образом, каждая точка будет отнесена к определенному центроиду (кластеру).

Шаг 4. Сместим наши центроиды в центр получившихся кластеров.

Шаг 5. Вновь отнесем точки к каждому из центроидов. Некоторые наблюдения «переметнутся» к другому центроиду.

Мы будем повторять шаги 4 и 5 до тех пор, пока алгоритм не стабилизируется, то есть до тех пор, пока наблюдения не перестанут переходить от одного центроида (кластера) к другому.

Говоря более формально, цель алгоритма — минимизировать сумму квадратов внутрикластерных расстояний до центра кластера (within-cluster sum of squares, WCSS, наша функция потерь):

Остается нерешенным важный вопрос.

Сколько кластеров выбрать?

Есть два способа выбора количества кластеров:

  1. Экспертный метод. Выбор количества кластеров будет зависеть от знания о предметной области (domain knowledge)
  2. Метод локтя (elbow method). Мы также можем (1) обучить модель используя несколько вариантов количества кластеров, (2) измерить сумму квадратов внутрикластерных расстояний и (3) выбрать тот вариант, при котором данное расстояние перестанет существенно уменьшаться.

На графике метод локтя выглядит следующим образом.

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

О важности нормализации данных

Алгоритм очень чувствителен к масштабу признаков. В связи с этим нормализация данных (feature scaling) приобретает особое значение. Так как при формировании кластеров мы измеряем расстояние (в частности, Евклидово расстояние), то признаки с большим масштабом будут иметь больший вес. Приведу пример.

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

Нам нужно определить насколько человек 1 отличается (насколько велико расстояние) от человека 2 и 3. В зависимости от этого мы будем формировать наши кластеры.

Вначале давайте обратимся к здравому смыслу. Мы видим, что респонденты 1 и 2 схожи, потому что им обоим около 20-ти и расходы у них примерно одинаковы. Респондент 3, имея схожие расходы, сильно отличается из-за своего возраста. Он в два раза старше. Это особенно легко увидеть на графике ниже:

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

Напомню формулу Евклидова расстояния.

$$ D = \sqrt {\left( {x_1-x_2 } \right)^2 + \left( {y_1-y_2 } \right)^2} $$

В данном случае x1 и x2 — это возраст двух сравниваемых нами людей, а y1 и y2 — их расходы. Подставим значения в формулу.

$$ D_1 = \sqrt {\left( {23-20 } \right)^2 + \left( {55000-50000 } \right)^2 } \approx 5000 $$

$$ D_2 = \sqrt {\left( {40-20 } \right)^2 + \left( {50500-50000 } \right)^2 } \approx 500 $$

Как мы видим, расстояние от человека 1 до человека 2 целых 5000 единиц (лет и рублей), в то время как до человека 3 только 500. Результат обратный тому, на который мы рассчитывали исходя из здравого смысла.

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

Практический пример — цветы ириса

Для иллюстрации работы алгоритма кластеризации мы возьмем еще один классический датасет из библиотеки sklearn, а именно данные о цветах ириса.

По традиции вначале откроем ноутбук к этому занятию

Этап 1. Загрузка данных

Давайте сразу загрузим данные и преобразуем их в формат датафрейма из библиотеки Pandas.

В данном случае речь идет о наборе данных, который состоит из 150 образцов цветов ириса, разделенных на три вида (Iris setosa, Iris virginica и Iris versicolor) по 50 растений в каждом. Каждый образец описан четырьмя атрибутами (длиной и шириной чашелистика и длиной и шириной лепестка).

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

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

Этап 2. Предварительная обработка данных

Для начала посмотрим, присутствуют ли пропущенные значения.

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

Категорийных переменных у нас также нет. Это становится понятно из результата функции head().

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

Этап 3 и 4. EDA и отбор признаков

Для целей кластерного анализа мы возьмем все имеющиеся у нас данные.

Этап 5.1. Обучение модели

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

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

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

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

Давайте создадим объект класса нашей модели, используя три кластера в качестве гипепараметра модели.

Подробнее рассмотрим параметры модели:

  • n_clusters: это количество кластеров, на которые мы хотим разбить наши наблюдения
  • init: определяет, как мы выберем первоначальное расположение (инициализацию) центроидов; есть два варианта, (1) выбрать центроиды случайно init = ‘random’ или (2) выбрать их так, чтобы центроиды с самого начала располагались максимально далеко друг от друга init = ‘k-means++’; второй вариант оптимальнее
  • n_init: сколько раз алгоритм будет инициализирован, т.е. сколько раз будут выбраны центроиды до начала оптимизации; на выходе будет выбран тот вариант, где ошибка была минимальна
  • max_iter: максимальное количество итераций алгоритма после первоначального выбора центроидов
  • random_state: воспроизводимость результата, с этим мы уже знакомы

Обучим модель и сделаем прогноз:

Этап 5.2. Оценка качества модели

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

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

На настоящих данных такое конечно невозможно.

Вначале преобразуем нашу целелевую переменную (iris.target) и наш прогноз (y_pred) в датафрейм (предварительно слегка их изменив, подробности в ноутбуке⧉).

С помощью функции where() создадим массив Numpy, в котором сравним каждую строчку датафрейма, и если целевая переменная и прогноз совпадают, зададим значение True, в противном случае — False.

Добавим этот массив в качестве столбца в датафрейм.

Выведем долю совпавших (True) и не совпавших (False) значений. Для этого используем функцию value_counts(), которая подсчитает, сколько раз встречается каждое значение. Параметр normalize=True вернет относительное значение или процент. Ровно это нам и нужно.

Как мы видим, модель была права в 83% случаев. Теперь давайте визуально оценим результат.

В исходном датафрейме четыре признака, а значит четыре измерения, столько мы представить графически не можем. Давайте возьмем первый (sepal length) и второй (sepal width) столбец исходного датафрейма.

Вначале построим точечную диаграмму целевой переменной.

Теперь посмотим на результат алгоритма кластеризации.

Выводы. Как мы видим, алгоритм идеально справился с кластером 0 (светлоголубой), однако допустил ошибки при разделение кластеров 1 и 2 (желтый и коричневый цвета). Почему?

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

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

Вопросы для закрепления

Почему кластеризация называется машинным обучением без учителя?

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

Как выбирается гиперпараметр модели (количество кластеров)?

Ответ: существует два способа: (1) экспертное мнение и (2) метод локтя

В чем заключаются основные ограничения модели k-средних?

Ответ: модель (1) очень чувствительна к масштабу признаков, и кроме того алгоритм предполагает (2) выпуклость и (3) разделенность данных

Дополнительные упражнения⧉ вы найдете в конце ноутбука.

Подведем итог

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

Мы закончили третий раздел классических алгоритмов машинного обучения. Пора переходить к более продвинутым задачам. Начнем с рекомендательных систем.

guest
3 комментариев
Межтекстовые Отзывы
Посмотреть все комментарии
Maxim

Здравствуйте! Скажите, а чем init = ‘k-means++’ лучше, чем init = ‘random’? Можете чуть подробнее объяснить. Спасибо!

Maxim

Большое спасибо!