Лабораторная работа №3 Кластеризация данных
Цель работы: изучить алгоритмы и методы кластерного анализа на практике.
Краткий теоретический материал
Кластеризация — разделение объектов на группы, при этом «правильные» ответы, то есть заранее заданных классы отсутсвуют.
Скажем, задача классификации — определение жанра музыкального трека на основании анализа его звуковой дорожки из известного перечня: джаз, пост-панк, классическая музыка, регги. А вот пример кластеризации — тематическое моделирование статей и выделение схожих. В кластеризации заранее заданных классов нет. Их формирует алгоритм, а не вы.
В целом задачи обучения без учителя сводятся к вычислению схожести между объектами. Когда модель её обнаружила, можно группировать сами объекты — решать задачу кластеризации.
Например, кластеризацию применяют:
• Для сегментации клиентов
Скажем, вы работаете в сервисе индивидуального медицинского страхования. Клиенты не однородны: есть молодые предприниматели и разработчики, которым нравится идея нестандартных обследований. Есть и более взрослые страхователи, разочарованные в ДМС своих компаний и нуждающиеся в традиционных продуктах и высоком сервисе. Вы также подозреваете, что существуют и другие, неочевидные группы клиентов. Кластеризация поможет их выделить и предложить каждому сегменту подходящий вариант продукта и точную коммуникацию.
• Для сегментации продуктов
Вы начали работать аналитиком в сети кофеен. Задача — разработка стратегии дистрибуции. Вы предполагаете, что можно выделить несколько типов кофеен в зависимости от расстояния до метро и центра, наличия туристических мест поблизости и размеров точки продаж. Для каждого типа можно устанавливать свои цели, KPI; по-разному оформлять интерьер и наружную рекламу. Кластеризация позволит выделить такие типы кофеен.
• Для тематического моделирования
Например, вы разрабатываете сервис по подборке красивых визуализаций данных. Собрали огромное количество примеров и хотите систематизировать их для удобства пользователей. Кластеризация поможет проанализировать код визуализаций и в зависимости от методов, функций и подписей к графикам сформировать темы. Так посетители ресурса будут гораздо быстрее находить примеры в вашей визуальной энциклопедии.
Обучение модели в Python. Библиотека sklearn
Модель — система взаимосвязей между признаками и целевой переменной или между наблюдениями, которая максимально близко отражает действительность.
Модель обучают на основе уже имеющихся наблюдений. Строят такие модели разными методами, или алгоритмами.
В Python есть библиотека sklearn, которая помогает обучать модели.
Стандартизация и нормализация
Бывает, что в наборе данных много признаков, диапазоны значений который отличаются (удаленность от метро, стоимость, категориальные признаки, возраст, параметры давления и тд).
Чтобы веса можно было сравнивать, признаки приводят к единому масштабу. Для этого применяют нормализацию — перевод значений признаков в диапазон от 0 до 1. Однако чаще масштабируют другим способом
— стандартизацией. И вот почему. Минимизировать среднеквадратичную ошибку уместно, только если данные имеют вид стандартного нормального распределения. Математическое ожидание равно нулю, а стандартное отклонение — 1.
Стандартизация приводит значение признака именно к такому виду: для каждого наблюдения из исходного значения признака вычитается среднее, а полученная разность делится на стандартное отклонение. На практике необязательно знать, по какой формуле исходные признаки получают значение из этих интервалов. Тем не менее, для решения задач методами линейной регрессии и кластеризации данные обязательно стандартизируют
В sklearn для |
нормализации |
и |
стандартизации |
данных |
в |
модуле preprocessing есть |
|
|
готовые |
||
классы MinMaxScaler() и StandardScaler() соответственно.
Они напоминают модели: их также нужно обучать — показывать, какие значения принимает признак на примере обучающей выборки, — и только после этого применять к любым новым наблюдениям. Синтаксис работы нормализации и стандартизации одинаковый:
from sklearn.preprocessing import StandardScaler
scaler = StandardScaler() # создаём объект класса scaler scaler.fit(X) # обучаем стандартизатор
X_sc = scaler.transform(X) # преобразуем набор данных
K-Means и агломеративная иерархическая кластеризация
Первый метод быстрый и понятный, однако чувствительный к заданному числу кластеров. Второй посложнее, зато не требует заданного заранее числа кластеров и позволяет визуализировать соотношения между объектами.
K-Means (англ. «К средних»)
K-Means группирует объекты пошагово. Алгоритм основан на предположении, что число кластеров (групп) заранее известно. Это довольно сильное допущение, и часто выбор оптимального количества кластеров заслуживает решения отдельных задач.
Вот принцип работы пошагового алгоритма K-means:
1)Есть K кластеров. Алгоритм пошагово подбирает их центры и относит объекты к тому кластеру, чей центр ближе.
2)Центры корректируются (меняют своё положение) до тех пор, пока это позволяет минимизировать среднее расстояние от объектов каждого кластера до его центра.
3)Когда расстояние от объектов до центра перестаёт снижаться или сокращается несущественно, алгоритм останавливается и фиксирует разбиение, считая его оптимальным.
Разобравшись в устройстве алгоритма, запустим его в Python. Алгоритм под названием KMeans реализован в модуле sklearn.cluster.
Вот его синтаксис:
from sklearn.cluster import KMeans
# обязательная стандартизация данных перед работой с алгоритмами
sc = StandardScaler() X_sc = sc.fit_transform(X)
km = KMeans(n_clusters=5, random_state=0) # задаём число кластеров, равное 5, и фиксируем значение random_state для воспроизводимости результата
labels = km.fit_predict(X_sc) # применяем алгоритм к данным и формируем вектор кластеров
В переменной labels сохраняются индексы предложенных алгоритмом групп. Алгоритм случайно назначает номер определённой группе, поэтому искать в этой цифре какой-то смысл не нужно: группа с индексом 2 не «ближе» к группе с индексом 3, чем группа 1. Важно, что объекты, которым модель присвоила один и тот же индекс, относятся к одному кластеру.
Чтобы не потерять удачный вариант кластеризации, нужно зафиксировать случайное состояние алгоритма. Для этого параметру random_state передают любое значение, например 0. Так результат работы алгоритма получится воспроизвести при перезапуске.
Агломеративная иерархическая кластеризация
Суть иерархической кластеризации проста. Когда мы задали функцию расстояния, можно вычислить матрицу расстояний между всеми объектами, в ячейках которой будет попарное расстояние между двумя объектами. А ещё учтены все признаки объектов, а не только два.
На основе этой матрицы можно последовательно объединять близкие кластеры. По ней оценить близость отдельных стран, быстро найти самые близкие или самые удалённые друг от друга на глаз сложно. Однако расстояния между объектами и сама агломеративная иерархическая кластеризация хорошо визуализируются на специальных графиках
— дендрограммах:
По вертикали расстояние между кластерами, а по горизонтали — объекты. Каждая горизонтальная «связка» соответствует расстоянию между объединяемыми объектами. Если двигаться по этому графику снизу вверх, сначала идут связки, которые соединяют отдельные объекты; потом связки, которые соединяют объекты с группами или одни группы объектов с другими. Если этот процесс не останавливать специально, он прекратится, когда
останется только один гигантский кластер. |
|
|||
Именно |
так |
и |
работает |
сама иерархическая |
агломеративная кластеризация. Разберём это на примере дендрограммы для стран.
Видно, что Канада наиболее близка к Австрии (внезапно это самые «похожие» страны в пространстве наших признаков) — объединим их в один кластер. Для него можно задать центр и пересчитать матрицу расстояний, но теперь уже с учётом расстояния от других объектов до нового сводного центра.
Дальше можно объединить другие близкие пары стран. Например, Францию и Италию, Таиланд и Грецию. Каждый раз будем получать новый кластер, его сводный центр и пересчитанные матрицы расстояний.
В какой-то момент ближайшими кластерами станут «парные» кластеры «Канада-Австрия» и «США-Австралия» — их объединим в сводный кластер из 4 стран.
Этот способ кластеризации интуитивно понятный и наглядный. На каждом шаге алгоритм наращивает кластеры, присоединяя соседние. Потому он и называется агломеративным, ведь превращает кластеры в агломерации — так называют объединение соседствующих населённых пунктов. Важно понять — в какой именно момент процесс объединения следует остановить.
По дендрограмме можно визуально оценить, сколько кластеров должно быть. А также прикинуть расстояние, после которого мы перестаём объединять объекты. Вот пример того, как для большого количества объектов можно подбирать разные пороги расстояний:
Значение K — это число линий, пересечённых пунктирной линией. Нарисуем дендограмму в Python. Сперва из модуля для иерархической
кластеризации hierarchy импортируем классы модели кластеризации linkage() и dendrogram():
from scipy.cluster.hierarchy import dendrogram, linkage
После этого выполним стандартизацию и передадим получившуюся стандартизированную таблицу в качестве параметра функции linkage(). Чтобы диаграмма получилась показательной, лучше передать параметру method значение 'ward':
# обязательная стандартизация данных перед работой с алгоритмами
sc = StandardScaler() X_sc = sc.fit_transform(X)
linked = linkage(X_sc, method = 'ward')
В переменной linked сохранена таблица «связок» между объектами. Её можно визуализировать как дендрограмму:
plt.figure(figsize=(15, 10)) dendrogram(linked, orientation='top') plt.title('Hierarchial clustering for GYM') plt.show()
В результате получаем график:
Предложенное оптимальное число кластеров 5 — пять разных цветов на графике.
Сложность агломеративной кластеризации заключается не в устройстве самого алгоритма, а в вычислениях, которые машина совершает для построения дендрограммы. Расчёты попарных расстояний могут занять очень много времени. Потому при решении задачи кластеризации полезно строить дендрограмму на случайной подвыборке, а после оценки оптимального числа кластеров запустить более быстрый алгоритм K-Means.
Метрики для задач обучения без учителя Забавный факт: существует теорема невозможности Клейнберга,
которая гласит, что оптимального алгоритма кластеризации не существует.
Это значит, что в силу отсутствия разметки, нет единственно верного способа оценить результат работы алгоритма. Все подходы к определению того, насколько хорошо разделили объекты, основаны на привлечении экспертов или эвристических оценках. Тем не менее, оценивать качество их решения както нужно.
Метрика силуэта показывает, насколько объект своего кластера похож на свой кластер больше, чем на чужой. Вот её формула:
где n — количество наблюдений; c_k — конкретный кластер;
x_i — конкретный объект кластера c_k;
a(x_i, c_k) — среднее расстояние от объекта x_i до других объектов кластера. Характеризует компактность (кучность) кластера;
b(x_i, c_k) — среднее расстояние от объекта x_i до объектов другого кластера. Характеризует отделимость кластера от других.
Синтаксис метода:
from sklearn.metrics import silhouette_score
silhouette_score(x_sc, labels)
На вход передаём нормализованную или стандартизованную матрицу признаков и метки, которые спрогнозировал алгоритм кластеризации, в виде списка.
Значение метрики силуэта принимает значения от -1 до 1. Чем ближе к 1, тем качественнее кластеризация.
Более подробно можно почитать тут - https://habr.com/ru/company/ods/blog/325654/
Порядок выполнения
1.Получить у преподавателя набор данных для проведения кластерного анализа, при необходимости провести нормализацию и кодирование данных.
2.Провести предварительную обработку данных, как в 1 ЛР.
3.Выполнить кластеризацию объектов
3.1иерархическим агломеративным методом
−выбрать подходящую метрику расстояния;
−построить дендрограмму;
−определить три признака (характеристики), оказавших наибольшее влияние на выделение кластеров используя оценку средних значений признаков на основе визуального анализа построенного графика выдвинуть гипотезу о числе кластеров;
−рассчитать оптимальное число кластеров.
3.2методом k-средних.
−задать число кластеров;
−рассчитать евклидово расстояние между кластерами;
−определить три признака (характеристики), оказавших наибольшее влияние на выделение кластеров используя оценку средних значений признаков;
−определить объекты, относящиеся к каждому кластеру;
−рассчитать оптимальное число кластеров
На оценку 5 – выполнять оба метода. На оценку 4 можно выполнить один метод.
4.Опишите полученные кластеры в терминах предметной области, дайте каждому кластеру условное наименование с учетом значимости признаков, повлиявших на выделение кластеров.
5.Сделать выводы по работе
Содержание отчета
1.Титульный лист
2.Цель работы
3.Вариант задания с кратким описанием набора данных
4.Пояснения и скриншоты по каждому пункту выполнения лабораторной работы
5.Ссылка на ваш Jupyter-ноутбук
6.Расширенный вывод по вашему исследованию