кластеризация это что такое

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

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

Задача кластеризации относится к статистической обработке, а также к широкому классу задач обучения без учителя.

Содержание

Типология задач кластеризации

Типы входных данных

Цели кластеризации

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

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

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

Классическим примером таксономии на основе сходства является биноминальная номенклатура живых существ, предложенная Карлом Линнеем в середине XVIII века. Аналогичные систематизации строятся во многих областях знания, чтобы упорядочить информацию о большом количестве объектов.

Методы кластеризации

Формальная постановка задачи кластеризации

Пусть — множество объектов, — множество номеров (имён, меток) кластеров. Задана функция расстояния между объектами . Имеется конечная обучающая выборка объектов . Требуется разбить выборку на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из объектов, близких по метрике , а объекты разных кластеров существенно отличались. При этом каждому объекту приписывается номер кластера .

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

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

Решение задачи кластеризации принципиально неоднозначно, и тому есть несколько причин:

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

Применение

В биологии

В социологии

В информатике

См. также

Литература

Внешние ссылки

На русском языке

На английском языке

Полезное

Смотреть что такое «Кластеризация» в других словарях:

кластеризация — — [Интент] Тематики автоматизированные системы EN clustering … Справочник технического переводчика

кластеризация — кластериз ация, и … Русский орфографический словарь

КЛАСТЕРИЗАЦИЯ — выделение различных групп объектов с общими признаками [63, c. 83] … Современный образовательный процесс: основные понятия и термины

кластеризация записей — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN record clustering … Справочник технического переводчика

Кластеризация рекламы — подача новостей или рекламной информации блоками, в которых объединяющую роль играет или общая тема, или общая фирма, рекламирующая свои товары … Реклама и полиграфия

Кластеризация генов — * кластарызацыя генаў * gene clustering задача разбиения заданной выборки генов на подмножества, называемые кластерами (), так, чтобы каждый кластер состоял из схожих генов, а гены разных кластеров существенно отличались. Задача К. г. относится к … Генетика. Энциклопедический словарь

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

кластеризация диполя — dipolio klasterizacija statusas T sritis chemija apibrėžtis Dipolio susiskaidymas į kelis mažesnius dipolius. atitikmenys: angl. dipole clustering rus. кластеризация диполя … Chemijos terminų aiškinamasis žodynas

Кластеризация документов — Для улучшения этой статьи желательно?: Дополнить статью (статья слишком короткая либо содержит лишь словарное определение). Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждаю … Википедия

Иерархическая кластеризация — (также графовые алгоритмы кластеризации) совокупность алгоритмов упорядочивания данных, визуализация которых обеспечивается с помощью графов. Алгоритмы упорядочивания данных указанного типа исходят из того, что некое множество объектов… … Википедия

Источник

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

Кластеризация (англ. cluster analysis) — задача группировки множества объектов на подмножества (кластеры) таким образом, чтобы объекты из одного кластера были более похожи друг на друга, чем на объекты из других кластеров по какому-либо критерию.

Задача кластеризации относится к классу задач обучения без учителя.

Содержание

Постановка задачи кластеризации [ править ]

Множество [math]Y[/math] в некоторых случаях известно заранее, однако чаще ставится задача определить оптимальное число кластеров, с точки зрения того или иного критерия качества кластеризации.

Решение задачи кластеризации объективно неоднозначно по ряду причин:

Теорема невозможности Клейнберга [ править ]

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

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

Третья аксиома требует сохранения кластеров при уменьшении внутрикластерного расстояния и увеличении межкластерного расстояния.

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

Исходя из этих аксиом Клейнберг сформулировал и доказал теорему:

Типология задач кластеризации [ править ]

Типы входных данных [ править ]

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

Цели кластеризации [ править ]

Методы кластеризации [ править ]

Меры качества кластеризации [ править ]

Подробнее про меры качества можно прочитать в статье оценка качества в задаче кластеризации.

Применение [ править ]

Биология и биоинформатика [ править ]

Медицина [ править ]

Маркетинг [ править ]

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

Интернет [ править ]

Компьютерные науки [ править ]

Псевдокод некоторых алгоритмов кластеризации [ править ]

Метод K-средних (Алгоритм Ллойда) [ править ]

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

DBSCAN [ править ]

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

На вход алгоритму подаётся набор точек, параметры [math]\epsilon[/math] (радиус окружности) и [math]m[/math] (минимальное число точек в окрестности). Для выполнения кластеризации потребуется поделить точки на четыре вида: основные точки, прямо достижимые, достижимые и шумовые.

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

На выходе получаем разбиение на кластеры и шумовые объекты. Каждый из полученных кластеров [math]C_j[/math] является непустым множеством точек и удовлетворяет двум условиям:

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

Пример кода [ править ]

Пример на языке R [ править ]

Источник

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

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

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

Кластерный анализ применяют в разных сферах:

Типы входных данных

Признаковое описание объектов

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

Матрица расстояний между выделенными объектами

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

Освойте самую востребованную технологию искусственного интеллекта. Дополнительная скидка 5% по промокоду BLOG.

Цели кластеризации

Сжатие данных

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

Поиск паттернов внутри данных

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

Поиск аномалий

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

Методы кластеризации

Общепринятой классификации методов нет, но есть несколько групп подходов.

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

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

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

Как описать кластеризацию формально?

В кластеризации имеют дело с множеством объектов (X) и множеством номеров кластеров (Y). Задана функция расстояния между объектами ( p). Нужно разбить обучающую выборку на кластеры, так чтобы каждый кластер состоял из объектов, близких по метрике p, а объекты разных кластеров существенно отличались. При этом каждому объекту приписывается номер кластера y(i).

Алгоритм кластеризации — это функция, которая любому объекту X ставит в соответствие номер кластера Y.

Data Science с нуля

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

Источник

Зачем нужен этот метод

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

Сферы применения

Алгоритмы кластеризации

Последовательность команд в общем виде выглядит следующим образом:

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

Иерархические алгоритмы

Иерархические алгоритмы бывают:

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

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

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

Объединение кластеров

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

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

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

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

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

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

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

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

Неиерархические алгоритмы

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

Наиболее популярный алгоритм K-средних. Метод также именуют быстрым кластерным анализом.

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

Описание алгоритма K-средних

Таким способом все объекты распределяются по конкретным группам.

Итеративный процесс

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

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

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

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

Источник

Открытый курс машинного обучения. Тема 7. Обучение без учителя: PCA и кластеризация

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

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

UPD: теперь курс — на английском языке под брендом mlcourse.ai со статьями на Medium, а материалами — на Kaggle (Dataset) и на GitHub.

Видеозапись лекции по мотивам этой статьи в рамках второго запуска открытого курса (сентябрь-ноябрь 2017).

План этой статьи

0. Введение

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

Одной из самых очевидных задач, которые возникают в голове в отсутствие явной разметки, является задача снижения размерности данных. С одной стороны её можно рассматривать как помощь в визуализации данных, для этого часто используется метод t-SNE, который мы рассмотрели во второй статье курса. С другой стороны подобное снижение размерности может убрать лишние сильно скоррелированные признаки у наблюдений и подготовить данные для дальнейшей обработки в режиме обучения с учителем, например сделать входные данные более «перевариваемыми» для деревьев решений.

1. Метод главных компонент (PCA)

Интуиция, теория и особенности применения

Метод главных компонент (Principal Component Analysis) — один из самых интуитивно простых и часто используемых методов для снижения размерности данных и проекции их на ортогональное подпространство признаков.

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

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

«To deal with hyper-planes in a 14 dimensional space, visualize a 3D space and say ‘fourteen’ very loudly. Everyone does it.» — Geoffrey Hinton

Рассмотрим как это делается математически:

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

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

где — матожидание -ого признака.
При этом отметим, что ковариация симметрична и ковариация вектора с самим собой будет равна его дисперсии.

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

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

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

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

Примеры использования

Набор данных по цветкам ириса

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

Теперь посмотрим, насколько PCA улучшит результаты для модели, которая в данном случае плохо справится с классификацией из-за того, что у неё не хватит сложности для описания данных:

Теперь попробуем сделать то же самое, но с данными, для которых мы снизили размерность до 2D:

Смотрим на возросшую точность классификации:

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

Посмотрим на 2 главные компоненты в последнем PCA-представлении данных и на тот процент исходной дисперсии в даных, который они «объясняют».

Набор данных по рукописным цифрам

Теперь возьмем набор данных по рукописным цифрам. Мы с ним уже работали в 3 статье про деревья решений и метод ближайших соседей.

Вспомним, как выглядят эти цифры – посмотрим на первые десять. Картинки здесь представляются матрицей 8 x 8 (интенсивности белого цвета для каждого пикселя). Далее эта матрица «разворачивается» в вектор длины 64, получается признаковое описание объекта.

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

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

На практике, как правило, выбирают столько главных компонент, чтобы оставить 90% дисперсии исходных данных. В данном случае для этого достаточно выделить 21 главную компоненту, то есть снизить размерность с 64 признаков до 21.

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

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

K-means

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

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

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

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

Выбор числа кластеров для kMeans

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

здесь – множество кластеров мощности , – центроид кластера .

Понятно, что здравый смысл в этом есть: мы хотим, чтобы точки располагались кучно возле центров своих кластеров. Но вот незадача: минимум такого функционала будет достигаться тогда, когда кластеров столько же, сколько и точек (то есть каждая точка – это кластер из одного элемента).
Для решения этого вопроса (выбора числа кластеров) часто пользуются такой эвристикой: выбирают то число кластеров, начиная с которого описанный функционал падает «уже не так быстро». Или более формально:

Видим, что падает сильно при увеличении числа кластеров с 1 до 2 и с 2 до 3 и уже не так сильно – при изменении с 3 до 4. Значит, в данной задаче оптимально задать 3 кластера.

Сложности

Само по себе решение задачи K-means NP-трудное (NP-hard), и для размерности , числа кластеров и числа точек решается за . Для решения такой боли часто используются эвристики, например MiniBatch K-means, который для обучения использует не весь датасет целиком, а лишь маленькие его порции (batch) и обновляет центроиды используя среднее за всю историю обновлений центроида от всех относящихся к нему точек. Сравнение обычного K-means и его MiniBatch имплементации можно посмотреть в документации scikit-learn.

Affinity Propagation

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

Заведём для этого какую-нибудь метрику «похожести», определяющуюся тем, что s(x_i, x_k)$» data-tex=»inline»/> если наблюдение больше похоже на наблюдение , чем на . Простым примером такой похожести будет отрицательный квадрат расстояния .

Теперь опишем сам процесс «общения». Для этого заведём две матрицы, инициализируемые нулями, одна из которых будет описывать, насколько хорошо -тое наблюдение подходит для того, чтобы быть «примером для подражания» для -того наблюдения относительно всех остальных потенциальных «примеров», а вторая — будет описывать, насколько правильным было бы для -того наблюдения выбрать -тое в качестве такого «примера». Звучит немного запутанно, но чуть дальше увидим пример «на пальцах».

После этого данные матрицы обновляются по очереди по правилам:

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

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

Для работы этого алгоритма нам потребуется определить матрицу похожести наблюдений (adjacency matrix). Можно это сделать таким же образом, как и для Affinity Propagation выше: . Эта матрица также описывает полный граф с вершинами в наших наблюдениях и рёбрами между каждой парой наблюдений с весом, соответствующим степени похожести этих вершин. Для нашей выше выбранной метрики и точек, лежащих на плоскости, эта штука будет интуитивной и простой — две точки более похожи, если ребро между ними короче. Теперь нам бы хотелось разделить наш получившийся граф на две части так, чтобы получившиеся точки в двух графах были в общем больше похожи на другие точки внутри получившейся «своей» половины графа, чем на точки в «другой» половине. Формальное название такой задачи называется Normalized cuts problem и подробнее про это можно почитать тут.

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

Наверное самый простой и понятный алгоритм кластеризации без фиксированного числа кластеров — агломеративная кластеризация. Интуиция у алгоритма очень простая:

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

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

По итогам выполнения такого алгоритма можно также построить замечательное дерево склеивания кластеров и глядя на него определить, на каком этапе нам было бы оптимальнее всего остановить алгоритм. Либо воспользоваться тем же правилом локтя, что и в k-means.

К счастью для нас в питоне уже есть замечательные инструменты для построения таких дендрограмм для агломеративной кластеризации. Рассмотрим на примере наших кластеров из K-means:

Метрики качества кластеризации

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

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

Adjusted Rand Index (ARI)

Предполагается, что известны истинные метки объектов. Данная мера не зависит от самих значений меток, а только от разбиения выборки на кластеры. Пусть — число объектов в выборке. Обозначим через — число пар объектов, имеющих одинаковые метки и находящихся в одном кластере, через — число пар объектов, имеющих различные метки и находящихся в разных кластерах. Тогда Rand Index это

То есть это доля объектов, для которых эти разбиения (исходное и полученное в результате кластеризации) «согласованы». Rand Index (RI) выражает схожесть двух разных кластеризаций одной и той же выборки. Чтобы этот индекс давал значения близкие к нулю для случайных кластеризаций при любом и числе кластеров, необходимо нормировать его. Так определяется Adjusted Rand Index:

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

Adjusted Mutual Information (AMI)

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

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

Гомогенность, полнота, V-мера

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

здесь — результат кластеризации, — истинное разбиение выборки на классы. Таким образом, измеряет, насколько каждый кластер состоит из объектов одного класса, а — насколько объекты одного класса относятся к одному кластеру. Эти меры не являются симметричными. Обе величины принимают значения в диапазоне , и большие значения соответствуют более точной кластеризации. Эти меры не являются нормализованными, как или , и поэтому зависят от числа кластеров. Случайная кластеризация не будет давать нулевые показатели при большом числе классов и малом числе объектов. В этих случаях предпочтительнее использовать . Однако при числе объектов более 1000 и числе кластеров менее 10 данная проблема не так явно выражена и может быть проигнорирована.

Для учёта обеих величин и одновременно вводится -мера, как их среднее гармоническое:

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

Силуэт

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

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

И напоследок давайте посмотрим на эти метрики для наших алгоритмов, запущенных на данных рукописных цифр MNIST:

3. Домашнее задание

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

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

4. Полезные источники

Статья написана в соавторстве с yorko (Юрием Кашницким). Материал статьи доступен в виде тетрадки Jupyter в GitHub-репозитории курса.

Источник