Кластерный анализ (Data clustering) — задача разбиения заданной выборки объектов (ситуаций) на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из схожих объектов, а объекты разных кластеров существенно отличались.
Задача кластеризации относится к широкому классу задач обучения без учителя.
Содержание
Типология задач кластеризации
Типы входных данных
Матрица расстояний может быть вычислена по матрице признаковых описаний объектов бесконечным числом способов, в зависимости от того, как ввести функцию расстояния (метрику) между признаковыми описаниями. Часто используется евклидова метрика, однако этот выбор в большинстве случаев является эвристикой и обусловлен лишь соображениями удобства.
Обратная задача — восстановление признаковых описаний по матрице попарных расстояний между объектами — в общем случае не имеет решения, а приближённое решение не единственно и может иметь существенную погрешность. Эта задача решается методами многомерного шкалирования.
Таким образом, постановка задачи кластеризации по матрице расстояний является более общей. С другой стороны, при наличии признаковых описаний часто удаётся строить более эффективные методы кластеризации.
Цели кластеризации
В первом случае число кластеров стараются сделать поменьше. Во втором случае важнее обеспечить высокую (или фиксированную) степень сходства объектов внутри каждого кластера, а кластеров может быть сколько угодно. В третьем случае наибольший интерес представляют отдельные объекты, не вписывающиеся ни в один из кластеров.
Во всех этих случаях может применяться иерархическая кластеризация, когда крупные кластеры дробятся на более мелкие, те в свою очередь дробятся ещё мельче, и т. д. Такие задачи называются задачами таксономии.
Результатом таксономии является древообразная иерархическая структура. При этом каждый объект характеризуется перечислением всех кластеров, которым он принадлежит, обычно от крупного к мелкому. Визуально таксономия представляется в виде графика, называемого дендрограммой.
Классическим примером таксономии на основе сходства является биноминальная номенклатура живых существ, предложенная Карлом Линнеем в середине XVIII века. Аналогичные систематизации строятся во многих областях знания, чтобы упорядочить информацию о большом количестве объектов.
Функции расстояния
Методы кластеризации
Формальная постановка задачи кластеризации
Решение задачи кластеризации принципиально неоднозначно, и тому есть несколько причин:
Кластеризация (англ. cluster analysis) — задача группировки множества объектов на подмножества (кластеры) таким образом, чтобы объекты из одного кластера были более похожи друг на друга, чем на объекты из других кластеров по какому-либо критерию.
Задача кластеризации относится к классу задач обучения без учителя.
Содержание
Постановка задачи кластеризации [ править ]
Множество [math]Y[/math] в некоторых случаях известно заранее, однако чаще ставится задача определить оптимальное число кластеров, с точки зрения того или иного критерия качества кластеризации.
Решение задачи кластеризации объективно неоднозначно по ряду причин:
Теорема невозможности Клейнберга [ править ]
Для формализации алгоритмов кластеризации была использована аксиоматическая теория. Клейнберг постулировал три простых свойства в качестве аксиом кластеризации и доказал теорему, связывающую эти свойства.
Определение:
Алгоритм кластеризации [math]a[/math] является масштабно инвариантным (англ. scale-invariant), если для любой функции расстояния [math]\rho[/math] и любой константы [math]\alpha \gt 0[/math] результаты кластеризации с использованием расстояний [math]\rho[/math] и [math]\alpha\cdot\rho[/math] совпадают.
Первая аксиома интуитивно понятна. Она требует, чтобы функция кластеризации не зависела от системы счисления функции расстояния и была нечувствительна к линейному растяжению и сжатию метрического пространства обучающей выборки.
Определение:
Алгоритм кластеризации является согласованным (англ. consistent), если результат кластеризации не изменяется после допустимого преобразования функции расстояния.
Третья аксиома требует сохранения кластеров при уменьшении внутрикластерного расстояния и увеличении межкластерного расстояния.
Примеры преобразований с сохранением кластеров
Исходное расположение объектов и их кластеризация
Пример масштабной инвариантности. Уменьшен масштаб по оси ординат в два раза.
Пример допустимого преобразования. Каждый объект в два раза приближен к центроиду своего класса. Внутриклассовое расстояние уменьшилось, межклассовое увеличилось.
Исходя из этих аксиом Клейнберг сформулировал и доказал теорему:
Теорема (Клейнберга, о невозможности):
Типология задач кластеризации [ править ]
Типы входных данных [ править ]
Вычисление матрицы расстояний по признаковому описанию объектов может быть выполнено бесконечным числом способов в зависимости от определения метрики между объектами. Выбор метрики зависит от обучающей выборки и поставленной задачи.
Цели кластеризации [ править ]
Методы кластеризации [ править ]
Меры качества кластеризации [ править ]
Подробнее про меры качества можно прочитать в статье оценка качества в задаче кластеризации.
Применение [ править ]
Биология и биоинформатика [ править ]
Медицина [ править ]
Маркетинг [ править ]
Кластеризация широко используется при изучении рынка для обработки данных, полученных из различных опросов. Может применяться для выделения типичных групп покупателей, разделения рынка для создания персонализированных предложений, разработки новых линий продукции.
Интернет [ править ]
Компьютерные науки [ править ]
Псевдокод некоторых алгоритмов кластеризации [ править ]
Метод K-средних (Алгоритм Ллойда) [ править ]
Основная идея заключается в том, что на каждой итерации перевычисляется центр масс для каждого кластера, полученного на предыдущем шаге, затем объекты снова разбиваются на кластеры в соответствии с тем, какой из новых центров оказался ближе по выбранной метрике. Алгоритм завершается, когда на какой-то итерации не происходит изменения внутрикластерного расстояния.
DBSCAN [ править ]
Основная идея метода заключается в том, что алгоритм разделит заданный набор точек в некотором пространстве на группы точек, которые лежат друг от друга на большом расстоянии. Объекты, которые лежат отдельно от скоплений с большой плотностью, будут помечены как шумовые.
На вход алгоритму подаётся набор точек, параметры [math]\epsilon[/math] (радиус окружности) и [math]m[/math] (минимальное число точек в окрестности). Для выполнения кластеризации потребуется поделить точки на четыре вида: основные точки, прямо достижимые, достижимые и шумовые.
Основная точка вместе со всеми достижимыми из нее точками формирует кластер. В кластер будут входить как основные, так и неосновные точки. Таким образом, каждый кластер содержит по меньшей мере одну основную точку.
На выходе получаем разбиение на кластеры и шумовые объекты. Каждый из полученных кластеров [math]C_j[/math] является непустым множеством точек и удовлетворяет двум условиям:
DBSCAN находит практическое применение во многих реальных задачах, например, в маркетинге: необходимо предложить покупателю релевантный товар, который подойдет под его заказ. Выбрать такой товар можно, если посмотреть на похожие заказы других покупателей — в таком случае похожие заказы образуют кластер вещей, которые часто берут вместе. Похожим образом с помощью DBSCAN можно исследовать и находить общие интересы людей, делить их на социальные группы, моделировать поведение посетителей сайта. Алгоритм также может использоваться для сегментации изображений.
Кластеризация — это разбиение множества объектов на подмножества (кластеры) по заданному критерию. Каждый кластер включает максимально схожие между собой объекты. Представим переезд: нужно разложить по коробкам вещи по категориям (кластерам) — например одежда, посуда, декор, канцелярия, книги. Так удобнее перевозить и раскладывать предметы в новом жилье. Процесс сбора вещей по коробкам и будет кластеризацией.
Критерии кластеризации определяет человек, а не алгоритм, — этим она отличается от классификации. Этот метод машинного обучения (Machine Learning) часто применяют в различных неструктурированных данных — например если нужно автоматически разбить коллекцию изображений на мини-группы по цветам.
Кластерный анализ применяют в разных сферах:
Типы входных данных
Признаковое описание объектов
Объект описывается при помощи набора характеристик. Признаки бывают числовые и категориальные. Например, можно кластеризовать группу покупателей на основе их покупок в интернет-магазине. В качестве входных данных будут средний чек, возраст, количество покупок в месяц, любимая категория покупок и другие критерии.
Матрица расстояний между выделенными объектами
Это симметричная таблица, где по строкам и столбцам расположены объекты, а на пересечении — расстояние между ними: например, таблица с расстояниями между отелями в разных городах. Такой способ может помочь выделить кластеры отелей, которые сгруппированы в одной и той же локации.
Кластеризация актуальна, если исходная выборка слишком большая. В результате от каждого кластера остается по одному типичному представителю. Количество кластеров может быть любым — здесь важно обеспечить максимальное сходство объектов внутри каждой группы.
Поиск паттернов внутри данных
Разбиение объектов на кластеры позволяет добавить дополнительный признак каждому объекту. Так, если в результате кластерного анализа выявилось, что определенный покупатель относится к первому кластеру, и мы знаем, что первый кластер — это кластер людей, которые тратят большое количество денег на покупки по средам, то можно сказать, что это покупатель приобретает продукты в основном по средам.
Поиск аномалий
В этом случае выделяют нетипичные объекты, не подходящие ни к одному сформированному кластеру. Интересны отдельные объекты, которые не вписываются ни в одну из сформированных групп.
Методы кластеризации
Общепринятой классификации методов нет, но есть несколько групп подходов.
1. Вероятностный подход. В рамках него предполагается, что каждый из объектов относится к одному из классов.
2. Подходы с учетом систем искусственного интеллекта. Большая условная группа методов, разнится с методической точки зрения.
4. Иерархический подход. Предполагает наличие вложенных групп — кластеров разного порядка. Выделяются агломеративные и дивизионные (объединительные и разделяющие) алгоритмы. В зависимости от количества признаков могут выделяться политетические (используют при сравнении нескольких признаков одновременно) и монотетические (используют при применении одного признака) методы классификации.
Как описать кластеризацию формально?
В кластеризации имеют дело с множеством объектов (X) и множеством номеров кластеров (Y). Задана функция расстояния между объектами ( p). Нужно разбить обучающую выборку на кластеры, так чтобы каждый кластер состоял из объектов, близких по метрике p, а объекты разных кластеров существенно отличались. При этом каждому объекту приписывается номер кластера y(i).
Алгоритм кластеризации — это функция, которая любому объекту X ставит в соответствие номер кластера Y.
Data Science с нуля
Вы получите достаточную математическую подготовку и опыт программирования на Python, чтобы решать задачи машинного обучения.
Обзор алгоритмов кластеризации числовых пространств данных
Задача кластеризации – частный случай задачи обучения без учителя, которая сводится к разбиению имеющегося множества объектов данных на подмножества таким образом, что элементы одного подмножества существенно отличались по некоторому набору свойств от элементов всех других подмножеств. Объект данных обычно рассматривается как точка в многомерном метрическом пространстве, каждому измерению которого соответствует некоторое свойство (атрибут) объекта, а метрика – есть функция от значений данных свойств. От типов измерений этого пространства, которые могут быть как числовыми, так и категориальными, зависит выбор алгоритма кластеризации данных и используемая метрика. Этот выбор продиктован различиями в природе разных типов атрибутов.
В этой статье приведён краткий обзор методов кластеризации числовых пространств данных. Она будет полезна тем, кто только начинает изучать Data Mining и кластерный анализ и поможет сориентироваться в многообразии современных алгоритмов кластеризации и получить о них общее представление. Статья не претендует на полноту изложения материала, напротив, описание алгоритмов в ней максимально упрощено. Для более подробного изучения того или иного алгоритма рекомендуется использовать научную работу, в которой он был представлен (см. список литературы в конце статьи).
Методы разбиения
Наиболее известные представители этого семейства методов – алгоритмы k-means[1] и k-medoids[2]. Они принимают входной параметр k и разбивают пространство данных на k кластеров таких, что между объектами одного кластера сходство максимально, а между объектами разных кластеров минимально. Сходство измеряется по отношению к некоторому центру кластера как дистанция от рассматриваемого объекта до центра. Основное различие между этими методами заключается в способе определения центра кластера.
В алгоритме k-means сходство рассматривается по отношению к центру масс кластера – среднему значению координат объектов кластера в пространстве данных. Сначала произвольно выбираются k объектов, каждый из которых является прототипом кластера и представляет его центр масс. Затем для каждого из оставшихся объектов выполняется присоединение к тому кластеру, с которым сходство больше. После этого центр масс каждого кластера вычисляется заново. Для каждого полученного разбиения рассчитывается некоторая оценочная функция, значения которой на каждом шаге образуют сходящейся ряд. Процесс продолжается до тех пор, пока указанный ряд не сойдётся к своему предельному значению. Иными словами, перемещение объектов из кластера в кластер заканчивается тогда, когда с каждой итерацией кластеры будут оставаться неизменными. Минимизация оценочной функции позволяет сделать результирующие кластеры настолько компактными и раздельными, насколько это возможно. Метод k-means хорошо работает, когда кластеры представляют собой значительно разделённые между собой компактные «облака». Он эффективен для обработки больших объёмов данных, однако не применим для обнаружения кластеров невыпуклой формы или сильно различающегося размера. Более того, метод очень чувствителен к шуму и обособленным точкам пространства, поскольку даже малое количество таких точек может существенно влиять на вычисление центра масс кластера.
Чтобы сократить влияние шума и обособленных точек пространства на результат кластеризации, алгоритм k-medoids, в отличие от k-means, использует для представления центра кластера не центр масс, а представительный объект – один из объектов кластера. Как и в методе k-means, сначала произвольным образом выбирается k представительных объектов. Каждый из оставшихся объектов объединяется в кластер с ближайшим представительным объектом. Затем итеративно для каждого представительного объекта производится его замена произвольным непредставительным объектом пространства данных. Процесс замены продолжается до тех пор, пока улучшается качество результирующих кластеров. Качество кластеризации определяется суммой отклонений между каждым объектом и представительным объектом соответствующего кластера, которую метод стремится минимизировать.То есть, итерации продолжаются до тех пор, пока в каждом кластере его представительный объект не станет медоидом – наиболее близким к центру кластера объектом. Алгоритм плохо масштабируем для обработки больших объёмов данных, но эту проблему решает дополняющий метод k-medoids алгоритм CLARANS [3]. Для кластеризации многомерных пространств на основе CLARANS построен алгоритм PROCLUS [4].
Иерархические методы
Общая идея методов данной группы заключается в последовательной иерархической декомпозиции множества объектов. В зависимости от направления построения иерархии различают дивизимный и агломеративный методы. В случае агломеративного метода (снизу вверх) процесс декомпозиции начитается с того, что каждый объект представляет собой самостоятельный кластер. Затем на каждой итерации пары близлежащих кластеров последовательно объединяются в общий кластер. Итерации продолжаются до тех пор, пока все объекты не будут объединены в один кластер или пока не выполнится некоторое условие остановки. Дивизимный метод (сверху вниз) напротив, подразумевает, что на начальном этапе все объекты объединены в единый кластер. На каждой итерации он разделяется на более мелкие до тех пор, пока каждый объект не окажется в отдельном кластере или не будет выполнено условие остановки. В качестве условия остановки можно использовать пороговое число кластеров, которое необходимо получить, однако обычно используется пороговое значение расстояния между кластерами.
Основная проблема иерархических методов заключается в сложности определения условия остановки таким образом, чтобы выделить «естественные» кластеры и в то же время не допустить их разбиения. Еще одна проблема иерархических методов кластеризации заключается в выборе точки разделения или слияния кластеров. Этот выбор критичен, поскольку после разделения или слияния кластеров на каждом последующем шаге метод будет оперировать только вновь образованными кластерами, поэтому неверный выбор точки слияния или разделения на каком-либо шаге может привести к некачественной кластеризации. Кроме того, иерархические методы не могут быть применены к большим наборам данных, потому как решение о разделении или слиянии кластеров требует анализа большого количества объектов и кластеров, что ведёт к большой вычислительной сложности метода. Примерами алгоритмов, основанных на иерархическом методе являются BIRCH[5] и CHAMELEON[6].
Плотностные методы
Кластеры рассматриваются как регионы пространства данных с высокой плотностью объектов, которые разделены регионами с низкой плотностью объектов.
Алгоритм DBSCAN [7] – один из первых алгоритмов кластеризации плотностным методом. В основе этого алгоритма лежит несколько определений:
Хотя, в отличие от методов разбиения, DBSCAN не требует заранее указывать число получаемых кластеров, требуется указание значений параметров ε и MinPts, которые непосредственно влияют на результат кластеризации. Оптимальные значения этих параметров сложно определить, особенно для многомерных пространств данных. Кроме того, распределение данных в таких пространствах часто несимметрично, что не позволяет использовать для их кластеризации глобальные параметры плотности. Для кластеризации многомерных пространств данных на базе DBSCAN был создан алгоритм SUBCLU [8].
Сетевые методы
Общая идея методов заключается в том, что пространство объектов разбивается на конечное число ячеек, образующих сетевую структуру, в рамках которой выполняются все операции кластеризации. Главное достоинство методов этой группы в малом времени выполнения, которое обычно не зависит от количества объектов данных, а зависит только от количества ячеек в каждом измерении пространства.
Алгоритм CLIQUE [9], адаптированный под кластеризацию данных высокой размерности, является одним из классических сетевых алгоритмов. Метод основан на том предположении, что если в многомерном пространстве данных распределение объектов не равномерно – встречаются регионы плотности и разрежения, то проекция региона плотности в подпространство с меньшей размерностью будет частью региона плотности в этом подпространстве. Алгоритм CLIQUE производит кластеризацию многомерного пространства данных следующим образом: пространство данных разбивается на не пересекающиеся ячейки фиксированного размера, среди них идентифицируются плотные ячейки – такие, плотность объектов данных в которых превышает заданное пороговое значение. Далее из найденных ячеек формируется пространство, в котором могут существовать плотные ячейки большей размерности. Процесс начинается с одномерных пространств (описанная процедура выполняется для каждого измерения) с последующим переходом к подпространствам более высокой размерности.
Этот алгоритм масштабируем для обработки большого количества данных, однако при большом количестве измерений число рассматриваемых комбинаций растёт нелинейно, следовательно, требуется использовать эвристики для сокращения количества рассматриваемых комбинаций. Кроме того, получаемый результат очень сильно зависит от выбора размера ячейки и порогового значения плотности объектов в ячейке. Это является большой проблемой, поскольку одни и те же значения этих параметров используются при рассмотрении всех комбинаций измерений. Эту проблему решает алгоритм MAFIA [10], работающий по схожему принципу, но использующий адаптивный размер ячеек при разбиении подпространств.
Модельные методы
Методы этого семейства предполагают, что имеется некоторая математическая модель кластера в пространстве данных и стремятся максимизировать сходство этой модели и имеющихся данных. Часто при этом используется аппарат математической статистики.
Алгоритм EM [11] основан на предположении, что исследуемое множество данных может быть смоделировано с помощью линейной комбинации многомерных нормальных распределений. Его целью является оценка параметров распределения, которые максимизируют функцию правдоподобия, используемую в качестве меры качества модели. Иными словами, предполагается, что данные в каждом кластере подчиняются определенному закону распределения, а именно, нормальному распределению. С учетом этого предположения можно определить оптимальные параметры закона распределения – математическое ожидание и дисперсию, при которых функция правдоподобия максимальна. Таким образом, мы предполагаем, что любой объект принадлежит ко всем кластерам, но с разной вероятностью. Тогда задача будет заключаться в «подгонке» совокупности распределений к данным, а затем в определении вероятностей принадлежности объекта к каждому кластеру. Очевидно, что объект должен быть отнесен к тому кластеру, для которого данная вероятность выше.
Алгоритм EM прост и лёгок в реализации, не чувствителен к изолированным объектам и быстро сходится при удачной инициализации. Однако он требует для инициализации указания количества кластеров k, что подразумевает наличие априорных знаний о данных. Кроме того, при неудачной инициализации сходимость алгоритма может оказаться медленной или может быть получен некачественный результат. Очевидно, что подобные алгоритмы не применимы к пространствам с высокой размерностью, поскольку в этом случае крайне сложно предположить математическую модель распределения данных в этом пространстве.
Концептуальная кластеризация
В отличие от традиционной кластеризации, которая обнаруживает группы схожих объектов на основе меры сходства между ними, концептуальная кластеризация определяет кластеры как группы объектов, относящейся к одному классу или концепту – определённому набору пар атрибут-значение.
Алгоритм COBWEB [12] – классический метод инкрементальной концептуальной кластеризации. Он создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт и содержит вероятностное описание этого концепта, которое включает в себя вероятность принадлежности концепта к данному узлу и условные вероятности вида: P(Ai = vij|Ck), где Ai = vij – пара атрибут-значение, Ck – класс концепта. Узлы, находящейся на определённом уровне дерева классификации, называют срезом. Алгоритм использует для построения дерева классификации эвристическую меру оценки, называемую полезностью категории – прирост ожидаемого числа корректных предположений о значениях атрибутов при знании об их принадлежности к определённой категории относительно ожидаемого числа корректных предположений о значениях атрибутов без этого знания. Чтобы встроить новый объект в дерево классификации, алгоритм COBWEB итеративно проходит всё дерево в поисках «лучшего» узла, к которому отнести этот объект. Выбор узла осуществляется на основе помещения объекта в каждый узел и вычисления полезности категории получившегося среза. Также вычисляется полезность категории для случая, когда объект относится к вновь создаваемому узлу. В итоге объект относится к тому узлу, для которого полезность категории больше. Однако COBWEB имеет ряд ограничений. Во-первых, он предполагает, что распределения вероятностей значений различных атрибутов статистически независимы друг от друга. Однако это предположение не всегда верно, потому как часто между значениями атрибутов существует корреляция. Во-вторых, вероятностное представление кластеров делает очень сложным их обновление, особенно в том случае, когда атрибуты имеют большое число возможных значений. Это вызвано тем, что сложность алгоритма зависит не только от количества атрибутов, но и от количества их возможных значений.
