Обзор алгоритмов кластеризации данных
В своей дипломной работе я проводил обзор и сравнительный анализ алгоритмов кластеризации данных. Подумал, что уже собранный и проработанный материал может оказаться кому-то интересен и полезен.
О том, что такое кластеризация, рассказал sashaeve в статье «Кластеризация: алгоритмы k-means и c-means». Я частично повторю слова Александра, частично дополню. Также в конце этой статьи интересующиеся могут почитать материалы по ссылкам в списке литературы.
Так же я постарался привести сухой «дипломный» стиль изложения к более публицистическому.
Понятие кластеризации
Кластеризация (или кластерный анализ) — это задача разбиения множества объектов на группы, называемые кластерами. Внутри каждой группы должны оказаться «похожие» объекты, а объекты разных группы должны быть как можно более отличны. Главное отличие кластеризации от классификации состоит в том, что перечень групп четко не задан и определяется в процессе работы алгоритма.
- Отбор выборки объектов для кластеризации.
- Определение множества переменных, по которым будут оцениваться объекты в выборке. При необходимости – нормализация значений переменных.
- Вычисление значений меры сходства между объектами.
- Применение метода кластерного анализа для создания групп сходных объектов (кластеров).
- Представление результатов анализа.
Меры расстояний
Итак, как же определять «похожесть» объектов? Для начала нужно составить вектор характеристик для каждого объекта — как правило, это набор числовых значений, например, рост-вес человека. Однако существуют также алгоритмы, работающие с качественными (т.н. категорийными) характеристиками.
После того, как мы определили вектор характеристик, можно провести нормализацию, чтобы все компоненты давали одинаковый вклад при расчете «расстояния». В процессе нормализации все значения приводятся к некоторому диапазону, например, [-1, -1] или [0, 1].
- Евклидово расстояние
Наиболее распространенная функция расстояния. Представляет собой геометрическим расстоянием в многомерном пространстве:
- Квадрат евклидова расстояния
Применяется для придания большего веса более отдаленным друг от друга объектам. Это расстояние вычисляется следующим образом:
- Расстояние городских кварталов (манхэттенское расстояние)
Это расстояние является средним разностей по координатам. В большинстве случаев эта мера расстояния приводит к таким же результатам, как и для обычного расстояния Евклида. Однако для этой меры влияние отдельных больших разностей (выбросов) уменьшается (т.к. они не возводятся в квадрат). Формула для расчета манхэттенского расстояния:
- Расстояние Чебышева
Это расстояние может оказаться полезным, когда нужно определить два объекта как «различные», если они различаются по какой-либо одной координате. Расстояние Чебышева вычисляется по формуле:
- Степенное расстояние
Применяется в случае, когда необходимо увеличить или уменьшить вес, относящийся к размерности, для которой соответствующие объекты сильно отличаются. Степенное расстояние вычисляется по следующей формуле:
,
где r и p – параметры, определяемые пользователем. Параметр p ответственен за постепенное взвешивание разностей по отдельным координатам, параметр r ответственен за прогрессивное взвешивание больших расстояний между объектами. Если оба параметра – r и p — равны двум, то это расстояние совпадает с расстоянием Евклида.
Классификация алгоритмов
- Иерархические и плоские.
Иерархические алгоритмы (также называемые алгоритмами таксономии) строят не одно разбиение выборки на непересекающиеся кластеры, а систему вложенных разбиений. Т.о. на выходе мы получаем дерево кластеров, корнем которого является вся выборка, а листьями — наиболее мелкие кластера.
Плоские алгоритмы строят одно разбиение объектов на кластеры. - Четкие и нечеткие.
Четкие (или непересекающиеся) алгоритмы каждому объекту выборки ставят в соответствие номер кластера, т.е. каждый объект принадлежит только одному кластеру. Нечеткие (или пересекающиеся) алгоритмы каждому объекту ставят в соответствие набор вещественных значений, показывающих степень отношения объекта к кластерам. Т.е. каждый объект относится к каждому кластеру с некоторой вероятностью.
Объединение кластеров
- Одиночная связь (расстояния ближайшего соседа)
В этом методе расстояние между двумя кластерами определяется расстоянием между двумя наиболее близкими объектами (ближайшими соседями) в различных кластерах. Результирующие кластеры имеют тенденцию объединяться в цепочки. - Полная связь (расстояние наиболее удаленных соседей)
В этом методе расстояния между кластерами определяются наибольшим расстоянием между любыми двумя объектами в различных кластерах (т.е. наиболее удаленными соседями). Этот метод обычно работает очень хорошо, когда объекты происходят из отдельных групп. Если же кластеры имеют удлиненную форму или их естественный тип является «цепочечным», то этот метод непригоден. - Невзвешенное попарное среднее
В этом методе расстояние между двумя различными кластерами вычисляется как среднее расстояние между всеми парами объектов в них. Метод эффективен, когда объекты формируют различные группы, однако он работает одинаково хорошо и в случаях протяженных («цепочечного» типа) кластеров. - Взвешенное попарное среднее
Метод идентичен методу невзвешенного попарного среднего, за исключением того, что при вычислениях размер соответствующих кластеров (т.е. число объектов, содержащихся в них) используется в качестве весового коэффициента. Поэтому данный метод должен быть использован, когда предполагаются неравные размеры кластеров. - Невзвешенный центроидный метод
В этом методе расстояние между двумя кластерами определяется как расстояние между их центрами тяжести. - Взвешенный центроидный метод (медиана)
Этот метод идентичен предыдущему, за исключением того, что при вычислениях используются веса для учета разницы между размерами кластеров. Поэтому, если имеются или подозреваются значительные отличия в размерах кластеров, этот метод оказывается предпочтительнее предыдущего.
Обзор алгоритмов
Алгоритмы иерархической кластеризации
Среди алгоритмов иерархической кластеризации выделяются два основных типа: восходящие и нисходящие алгоритмы. Нисходящие алгоритмы работают по принципу «сверху-вниз»: в начале все объекты помещаются в один кластер, который затем разбивается на все более мелкие кластеры. Более распространены восходящие алгоритмы, которые в начале работы помещают каждый объект в отдельный кластер, а затем объединяют кластеры во все более крупные, пока все объекты выборки не будут содержаться в одном кластере. Таким образом строится система вложенных разбиений. Результаты таких алгоритмов обычно представляют в виде дерева – дендрограммы. Классический пример такого дерева – классификация животных и растений.
Для вычисления расстояний между кластерами чаще все пользуются двумя расстояниями: одиночной связью или полной связью (см. обзор мер расстояний между кластерами).
К недостатку иерархических алгоритмов можно отнести систему полных разбиений, которая может являться излишней в контексте решаемой задачи.
Алгоритмы квадратичной ошибки
Задачу кластеризации можно рассматривать как построение оптимального разбиения объектов на группы. При этом оптимальность может быть определена как требование минимизации среднеквадратической ошибки разбиения:
где cj — «центр масс» кластера j (точка со средними значениями характеристик для данного кластера).
- Случайно выбрать k точек, являющихся начальными «центрами масс» кластеров.
- Отнести каждый объект к кластеру с ближайшим «центром масс».
- Пересчитать «центры масс» кластеров согласно их текущему составу.
- Если критерий остановки алгоритма не удовлетворен, вернуться к п. 2.
К недостаткам данного алгоритма можно отнести необходимость задавать количество кластеров для разбиения.
Нечеткие алгоритмы
- Выбрать начальное нечеткое разбиение n объектов на k кластеров путем выбора матрицы принадлежности U размера n x k.
- Используя матрицу U, найти значение критерия нечеткой ошибки:
,
где ck — «центр масс» нечеткого кластера k:
. - Перегруппировать объекты с целью уменьшения этого значения критерия нечеткой ошибки.
- Возвращаться в п. 2 до тех пор, пока изменения матрицы U не станут незначительными.
Алгоритмы, основанные на теории графов
Суть таких алгоритмов заключается в том, что выборка объектов представляется в виде графа G=(V, E), вершинам которого соответствуют объекты, а ребра имеют вес, равный «расстоянию» между объектами. Достоинством графовых алгоритмов кластеризации являются наглядность, относительная простота реализации и возможность вносения различных усовершенствований, основанные на геометрических соображениях. Основными алгоритмам являются алгоритм выделения связных компонент, алгоритм построения минимального покрывающего (остовного) дерева и алгоритм послойной кластеризации.
Алгоритм выделения связных компонент
В алгоритме выделения связных компонент задается входной параметр R и в графе удаляются все ребра, для которых «расстояния» больше R. Соединенными остаются только наиболее близкие пары объектов. Смысл алгоритма заключается в том, чтобы подобрать такое значение R, лежащее в диапазон всех «расстояний», при котором граф «развалится» на несколько связных компонент. Полученные компоненты и есть кластеры.
Для подбора параметра R обычно строится гистограмма распределений попарных расстояний. В задачах с хорошо выраженной кластерной структурой данных на гистограмме будет два пика – один соответствует внутрикластерным расстояниям, второй – межкластерным расстояния. Параметр R подбирается из зоны минимума между этими пиками. При этом управлять количеством кластеров при помощи порога расстояния довольно затруднительно.
Алгоритм минимального покрывающего дерева
Алгоритм минимального покрывающего дерева сначала строит на графе минимальное покрывающее дерево, а затем последовательно удаляет ребра с наибольшим весом. На рисунке изображено минимальное покрывающее дерево, полученное для девяти объектов.
Путём удаления связи, помеченной CD, с длиной равной 6 единицам (ребро с максимальным расстоянием), получаем два кластера:
Послойная кластеризация
Алгоритм послойной кластеризации основан на выделении связных компонент графа на некотором уровне расстояний между объектами (вершинами). Уровень расстояния задается порогом расстояния c. Например, если расстояние между объектами 
, то 
.
Алгоритм послойной кластеризации формирует последовательность подграфов графа G, которые отражают иерархические связи между кластерами:
,
где G t = (V, E t ) — граф на уровне с t , 
,
с t – t-ый порог расстояния,
m – количество уровней иерархии,
G 0 = (V, o), o – пустое множество ребер графа, получаемое при t 0 = 1,
G m = G, то есть граф объектов без ограничений на расстояние (длину ребер графа), поскольку t m = 1.
Посредством изменения порогов расстояния <с 0 , …, с m >, где 0 = с 0 < с 1 < …< с m = 1, возможно контролировать глубину иерархии получаемых кластеров. Таким образом, алгоритм послойной кластеризации способен создавать как плоское разбиение данных, так и иерархическое.
Сравнение алгоритмов
Вычислительная сложность алгоритмов
| Алгоритм кластеризации | Вычислительная сложность |
| Иерархический | O(n 2 ) |
| k-средних | O(nkl), где k – число кластеров, l – число итераций |
|---|---|
| c-средних | |
| Выделение связных компонент | зависит от алгоритма |
| Минимальное покрывающее дерево | O(n 2 log n) |
| Послойная кластеризация | O(max(n, m)), где m < n(n-1)/2 |
Сравнительная таблица алгоритмов
| Алгоритм кластеризации | Форма кластеров | Входные данные | Результаты |
| Иерархический | Произвольная | Число кластеров или порог расстояния для усечения иерархии | Бинарное дерево кластеров |
| k-средних | Гиперсфера | Число кластеров | Центры кластеров |
| c-средних | Гиперсфера | Число кластеров, степень нечеткости | Центры кластеров, матрица принадлежности |
| Выделение связных компонент | Произвольная | Порог расстояния R | Древовидная структура кластеров |
| Минимальное покрывающее дерево | Произвольная | Число кластеров или порог расстояния для удаления ребер | Древовидная структура кластеров |
| Послойная кластеризация | Произвольная | Последовательность порогов расстояния | Древовидная структура кластеров с разными уровнями иерархии |
Немного о применении
В своей работе мне нужно было из иерархических структур (деревьев) выделять отдельные области. Т.е. по сути необходимо было разрезать исходное дерево на несколько более мелких деревьев. Поскольку ориентированное дерево – это частный случай графа, то естественным образом подходят алгоритмы, основанными на теории графов.
В отличие от полносвязного графа, в ориентированном дереве не все вершины соединены ребрами, при этом общее количество ребер равно n–1, где n – число вершин. Т.е. применительно к узлам дерева, работа алгоритма выделения связных компонент упростится, поскольку удаление любого количества ребер «развалит» дерево на связные компоненты (отдельные деревья). Алгоритм минимального покрывающего дерева в данном случае будет совпадать с алгоритмом выделения связных компонент – путем удаления самых длинных ребер исходное дерево разбивается на несколько деревьев. При этом очевидно, что фаза построения самого минимального покрывающего дерева пропускается.
В случае использования других алгоритмов в них пришлось бы отдельно учитывать наличие связей между объектами, что усложняет алгоритм.
Отдельно хочу сказать, что для достижения наилучшего результата необходимо экспериментировать с выбором мер расстояний, а иногда даже менять алгоритм. Никакого единого решения не существует.
Все о кластерах
Кластер – это форма представления информации в виде некоторого изображения, предполагающая отбор смысловых компонентов. Обозначается своеобразной схемой с обязательным отображением связей между элементами всей системы. В конечном итоге получается объект, помогающий систематизировать и обобщать новые и ранее известные данные по задаваемым вопросам.
В данной статье будет рассказано о том, в чем заключается суть метода кластеров. Предстоит изучить, как происходит его создание, а также работа в той или иной мере. Также интересно будет рассмотреть кластерный анализ и его принципы.
Принципы и правила формирования
Разбираясь, в чем суть метода кластеров, сначала нужно определить сферу, в которой он применяется. В качестве примера рассмотрим работу в классе.
Кластер нужно оформлять в виде модели планеты со спутниками или своеобразной грозди. Здесь требуется запомнить следующие особенности:
- в центре размещается ключевая задача, мысль или понятие;
- ответвлениям представляют собой смысловые единицы, связанные с главным «термином»;
- область вокруг выстроенной модели – менее значительные элементы и факты.
Последние нужны для того, чтобы расширить логическую цепочку в кластере. Они позволяют более полно раскрыть ту или иную тему. Главная мысль и ее смысловые единицы соединяются при помощи прямых отрезков.
На уроке
Составлять кластеры на самом деле не так трудно, если грамотно подойти к этому вопросу. Во время работы на уроке место, на котором будет располагаться «мысль», зависит от способа организации занятия.
Он может быть размещен на:
- доске;
- листе бумаги;
- непосредственно в тетрадке.
Чтобы нагляднее выделить составляющие, а также главную мысль, во время оформления рекомендуется пользоваться карандашами, фломастерами, а также мелками разных цветов. Этот прием поможет лучше и быстрее понять, что написано на том или ином пространстве.
Рекомендации
Составить кластер и воспользоваться им сможет любой из учащихся. Данная затея является основой критического мышления. Она в наглядном виде позволит проанализировать ту или иную мысль, после чего можно сделать логический вывод. Подобные принципы используются в маркетинге, а также информационных технологиях, но на примере их работы на уроке рассматривать соответствующий компонент проще всего.
Вот рекомендации, которые помогут составлению кластера на занятии:
- Если детей много, привлечь к работе нужно каждого. Это позволит записать больше мыслей, идей, фактов и выводов.
- Нужно делать конспект всего, что приходит в голову. Ошибиться в соответствующем вопросе нельзя. Ненужные записи в ходе анализа той или иной темы возможно удалить или стереть.
- Большое количество смысловых единиц – не проблема для дальнейшей работы. Чем больше гипотез, тем лучше. Такая концепция создает более полную картину происходящего.
- Оформите кластер на ту или иную тему так, чтобы он выглядел понятно: схемой или графиком. Стоит использовать различные формы и цвета для выделения составляющих модели.
Эти советы помогут сформировать кластер во время работы на уроке с любым количеством учеников, но они могут использоваться и в других сферах жизни человека. Пример – в аналитике.
Применение
Изучаемый прием часто встречается в начальной и старшей школе. Он актуален для всех предметов и позволяет лучше усвоить учебный материал. Форма организации зависит от того, что предполагает сделать учитель – работать с одним человеком или несколькими. Один вариант может плавно переходить в другой.
Сначала ученикам предлагается структурировать багаж имеющихся знаний, затем – поработать в небольших группах с предоставленной информацией, составить конспект и дополнить кластерные составляющие. Завершается процедура организацией общей деятельности всего класса. Она направлена на систематизацию полученных знаний и составление общей схемы.
Когда дети освоили принцип кластеризации, оформите им в соответствующей форме домашнее задание. Это также отличный вариант для проверки знаний данной темы: в соответствующей ситуации типом кластера на уроке выступит самостоятельная/проверочная работа.
Наглядный пример
Использование cluster method на конкретном примере поможет лучше освоить соответствующий принцип. В качестве основы возьмем урок биологии и работу с темой «Клетка». Здесь:
- Центральная смысловая единица – слово, одноименное с тематикой.
- На первом этапе дети должны вспомнить все, что знают по соответствующему направлению.
- После того, как соответствующие записи внесены в схему (на график), учитель просит учеников прочесть тот или иной текст, сделать конспект и внести новые единицы.
- Как только дети справились с задачей, учитель дописывает «недостающие элементы».
Заключение (выводы) в конце работы на уроке предполагает анализ кластера на соответствующую тему. Вместе с учениками нужно обсудить изученный материал и выдвинутые теории, а затем обговорить достоверность изначально приведенных данных.
Преимущества
Прием Кластер – это метод критического мышления, который:
- вовлекает в работу всех учеников/участников процесса;
- позволяет охватить и прийти к сути достаточно большого объема информации;
- создает ассоциации через образы.
Данная концепция оказывает благоприятное влияние на развитие учеников. Они не боятся выдвигать свои теории, ошибаться, анализироваться информацию.
Кластерный анализ
Составить cluster не так трудно, особенно если делать это постепенно. Соответствующая концепция мышления применяется почти во всех сферах жизни человека. Есть такое понятие как «кластерный анализ» или «кластеризация».
Это – разделение большой группы объектов на несколько мелких компонентов. Каждая группа – это и есть кластер. Он формируется на основе тех или иных критериев. Внутри объекты могут различаться, но хотя бы «одно общее» у них должно быть.
Сферы применения
После того как стало понятно, как составить кластер, можно применить его на практике. Соответствующая концепция встречается везде, где что-то подлежит классификации/разделению. Главное – наличие хотя бы одного общего признака у всех элементов. В противном случае составление кластера не будет иметь места.
На соответствующие «блоки» можно разделить:
- клиентов;
- конкурентов бизнеса для рыночного исследования;
- заболевания;
- респондентов опросов;
- ключи для формирования тематик веб-страниц;
- файлы различных форматов.
Это – только начало. Делать кластеры можно практически везде, где элементы структурируются и систематизируются.
Разбираясь, в чем суть метода кластеров, нужно усвоить цели кластеризации:
- Понимание. Деление информации на группы позволяет понять ее суть. Пока информация не систематизирована, она практически не подлежит обработке.
- Выявление аномалий. После кластеризации возможно появление данных, которые не относятся ни к одному из «блоков». Их рекомендуется изучить, чтобы понять – это следствие ошибки или интересный феномен.
- Расширение.
- Сжатие. Если информации очень много, ее можно разделить на кластеры, а затем усреднить и оставить на каждый «смысловой блок» всего один объект. На выходе получаем меньшие требования для дальнейшего анализа имеющихся сведений.
Часто это – предварительная работа перед масштабным анализом. Она упрощает использование иных методик изучения информации.
Алгоритмы и методы
Создать кластер в виде схемы или иной формы представления – не самая трудная задача, если выбрана концепция систематизации информации. Кластеризация проводится при помощи различных алгоритмов и инструментов. Они напрямую зависят от того, с какими материалами предстоит работать, а также от цели итогового результата.
При кластеризации данных используют:
- Нисходящие алгоритмы. Сначала объекты объединяются в один «блок», затем дробятся на более мелкие составляющие.
- Восходящие алгоритмы. Каждый объект – это отдельный cluster. Постепенно они объединяются до достижения желаемой степени разделения.
- Метод квадратичной ошибки. В основе заложена формула среднеквадратичной ошибки. Самый распространенный вариант – это метод k-средних. Он создает нужное количество «блоков», которые максимально удалены друг от друга.
- Системы искусственного интеллекта. Здесь используются нейронные сети. Применяется прием тогда, когда количество кластеров неизвестно.
Есть еще логический подход. Данные тут делятся по смыслу. Оформите соответствующую схему в виде дерева решений. Это лучший вариант для небольшого объема информации.
Соответствующей темой должны владеть системные администраторы, DevOps-специалисты, Data-инженеры, специалисты по машинному обучению, системные аналитики. Подобрать курс по интересующему IT-направлению вы всегда сможете в Otus.
Кластеризация
Кластеризация (англ. cluster analysis) — задача группировки множества объектов на подмножества (кластеры) таким образом, чтобы объекты из одного кластера были более похожи друг на друга, чем на объекты из других кластеров по какому-либо критерию.
Задача кластеризации относится к классу задач обучения без учителя.
Содержание
Постановка задачи кластеризации
Пусть [math]X[/math] — множество объектов, [math]Y[/math] — множество идентификаторов (меток) кластеров. На множестве [math]X[/math] задана функция расстояния между объектами [math]\rho(x,x’)[/math] . Дана конечная обучающая выборка объектов [math]X^m = \ < x_1, \dots, x_m \>\subset X[/math] . Необходимо разбить выборку на подмножества (кластеры), то есть каждому объекту [math]x_i \in X^m[/math] сопоставить метку [math]y_i \in Y[/math] , таким образом чтобы объекты внутри каждого кластера были близки относительно метрики [math]\rho[/math] , а объекты из разных кластеров значительно различались.
| Определение: |
| Алгоритм кластеризации — функция [math]a\colon X\to Y[/math] , которая любому объекту [math]x\in X[/math] ставит в соответствие идентификатор кластера [math]y\in Y[/math] . |
Множество [math]Y[/math] в некоторых случаях известно заранее, однако чаще ставится задача определить оптимальное число кластеров, с точки зрения того или иного критерия качества кластеризации.
Кластеризация (обучение без учителя) отличается от классификации (обучения с учителем) тем, что метки объектов из обучающей выборки [math]y_i[/math] изначально не заданы, и даже может быть неизвестно само множество [math]Y[/math] .
Решение задачи кластеризации объективно неоднозначно по ряду причин:
- Не существует однозначного критерия качества кластеризации. Известен ряд алгоритмов, осуществляющих разумную кластеризацию «по построению», однако все они могут давать разные результаты. Следовательно, для определения качества кластеризации и оценки выделенных кластеров необходим эксперт предметной области;
- Число кластеров, как правило, заранее не известно и выбирается по субъективным критериям. Даже если алгоритм не требует изначального знания о числе классов, конкретные реализации зачастую требуют указать этот параметр [1] ;
- Результат кластеризации существенно зависит от метрики. Однако существует ряд рекомендаций по выбору метрик для определенных классов задач. [2] .
Число кластеров фактически является гиперпараметром для алгоритмов кластеризации. Подробнее про другие гиперпараметры и их настройку можно прочитать в статье [3] .
Теорема невозможности Клейнберга
Для формализации алгоритмов кластеризации была использована аксиоматическая теория. Клейнберг постулировал три простых свойства в качестве аксиом кластеризации и доказал теорему, связывающую эти свойства.
| Определение: |
| Алгоритм кластеризации [math]a[/math] является масштабно инвариантным (англ. scale-invariant), если для любой функции расстояния [math]\rho[/math] и любой константы [math]\alpha \gt 0[/math] результаты кластеризации с использованием расстояний [math]\rho[/math] и [math]\alpha\cdot\rho[/math] совпадают. |
Первая аксиома интуитивно понятна. Она требует, чтобы функция кластеризации не зависела от системы счисления функции расстояния и была нечувствительна к линейному растяжению и сжатию метрического пространства обучающей выборки.
| Определение: |
| Полнота (англ. Richness). Множество результатов кластеризации алгоритма [math]a[/math] в зависимости от изменения функции расстояния [math]\rho[/math] должно совпадать со множеством всех возможных разбиений множества объектов [math]X[/math] . |
Вторая аксиома утверждает, что алгоритм кластеризации должен уметь кластеризовать обучающую выборку на любое фиксированное разбиение для какой-то функции расстояния [math]\rho[/math] .
| Определение: |
| Алгоритм кластеризации является согласованным (англ. consistent), если результат кластеризации не изменяется после допустимого преобразования функции расстояния. |
Третья аксиома требует сохранения кластеров при уменьшении внутрикластерного расстояния и увеличении межкластерного расстояния.
| Примеры преобразований с сохранением кластеров | ||
 |
 |
 |
| Исходное расположение объектов и их кластеризация | Пример масштабной инвариантности. Уменьшен масштаб по оси ординат в два раза. | Пример допустимого преобразования. Каждый объект в два раза приближен к центроиду своего класса. Внутриклассовое расстояние уменьшилось, межклассовое увеличилось. |
Исходя из этих аксиом Клейнберг сформулировал и доказал теорему:
Несмотря на эту теорему Клейнберг показал [4] , что иерархическая кластеризация по методу одиночной связи с различными критериями останова удовлетворяет любым двум из трех аксиом.
Типология задач кластеризации
Типы входных данных
- Признаковое описание объектов. Каждый объект описывается набором своих характеристик, называемых признаками (англ. features). Признаки могут быть как числовыми, так и категориальными;
- Матрица расстояний между объектами. Каждый объект описывается расстоянием до всех объектов из обучающей выборки.
Вычисление матрицы расстояний по признаковому описанию объектов может быть выполнено бесконечным числом способов в зависимости от определения метрики между объектами. Выбор метрики зависит от обучающей выборки и поставленной задачи.
Цели кластеризации
- Классификация объектов. Попытка понять зависимости между объектами путем выявления их кластерной структуры. Разбиение выборки на группы схожих объектов упрощает дальнейшую обработку данных и принятие решений, позволяет применить к каждому кластеру свой метод анализа (стратегия «разделяй и властвуй»). В данном случае стремятся уменьшить число кластеров для выявления наиболее общих закономерностей;
- Сжатие данных. Можно сократить размер исходной выборки, взяв один или несколько наиболее типичных представителей каждого кластера. Здесь важно наиболее точно очертить границы каждого кластера, их количество не является важным критерием;
- Обнаружение новизны (обнаружение шума). Выделение объектов, которые не подходят по критериям ни в один кластер. Обнаруженные объекты в дальнейшем обрабатывают отдельно.
Методы кластеризации
- Графовые алгоритмы кластеризации. Наиболее примитивный класс алгоритмов. В настоящее время практически не применяется на практике;
- Вероятностные алгоритмы кластеризации. Каждый объект из обучающей выборки относится к каждому из кластеров с определенной степенью вероятности:
- EM-алгоритм;
Меры качества кластеризации
Для оценки качества кластеризации задачу можно переформулировать в терминах задачи дискретной оптимизации. Необходимо так сопоставить объектам из множества [math]X[/math] метки кластеров, чтобы значение выбранного функционала качества приняло наилучшее значение. В качестве примера, стремятся достичь минимума среднего внутрикластерного расстояния [math]F_0 = \dfrac<\sum_
Подробнее про меры качества можно прочитать в статье оценка качества в задаче кластеризации.
Применение
Биология и биоинформатика
- В области экологии кластеризация используется для выделения пространственных и временных сообществ организмов в однородных условиях;
- Кластерный анализ используется для группировки схожих геномных последовательностей в семейство генов, которые являются консервативными структурами для многих организмов и могут выполнять схожие функции;
- Кластеризация помогает автоматически определять генотипы по различным частям хромосом;
- Алгоритмы применяются для выделения небольшого числа групп генетических вариации человеческого генома.
Медицина
- Используется в позитронно-эмиссионной томографии для автоматического выделения различных типов тканей на трехмерном изображении;
- Применяется для выявления шаблонов устойчивости к антибиотикам; для классификации антибиотиков по типу антибактериальной активности.
Маркетинг
Кластеризация широко используется при изучении рынка для обработки данных, полученных из различных опросов. Может применяться для выделения типичных групп покупателей, разделения рынка для создания персонализированных предложений, разработки новых линий продукции.
Интернет
- Выделение групп людей на основе графа связей в социальных сетях;
- Повышение релевантности ответов на поисковые запросы путем группировки веб-сайтов по смысловым значениям поискового запроса.
Компьютерные науки
- Кластеризация используется в сегментации изображений для определения границ и распознавания объектов;
- Кластерный анализ применяется для определения образовавшихся популяционных ниш в ходе работы эволюционных алгоритмов для улучшения параметров эволюции;
- Подбор рекомендаций для пользователя на основе предпочтений других пользователей в данном кластере;
- Определение аномалий путем построения кластеров и выявления неклассифицированных объектов.
Псевдокод некоторых алгоритмов кластеризации
Метод K-средних (Алгоритм Ллойда)
Основная идея заключается в том, что на каждой итерации перевычисляется центр масс для каждого кластера, полученного на предыдущем шаге, затем объекты снова разбиваются на кластеры в соответствии с тем, какой из новых центров оказался ближе по выбранной метрике. Алгоритм завершается, когда на какой-то итерации не происходит изменения внутрикластерного расстояния.
Алгоритм минимизирует сумму квадратов внутрикластерных расстояний: [math] \sum_^
||x_i — \mu_ ||^2 \: \to \: \min_< \ ^ (f_j(x_i) — \mu_ )^2[/math] На вход алгоритму подаётся выборка [math]X^m = \< x_1, \dots, x_m \>[/math] и количество кластеров [math]K = |Y|[/math] .
На выходе получаем центры кластеров [math]\mu_a[/math] для кластеров [math]a \in Y[/math] .
DBSCAN
Основная идея метода заключается в том, что алгоритм разделит заданный набор точек в некотором пространстве на группы точек, которые лежат друг от друга на большом расстоянии. Объекты, которые лежат отдельно от скоплений с большой плотностью, будут помечены как шумовые.
На вход алгоритму подаётся набор точек, параметры [math]\epsilon[/math] (радиус окружности) и [math]m[/math] (минимальное число точек в окрестности). Для выполнения кластеризации потребуется поделить точки на четыре вида: основные точки, прямо достижимые, достижимые и шумовые.
- Точка является основной, если в окружности с центром в этой точке и радиусом [math]\epsilon[/math] находится как минимум [math]m[/math] точек.
- Точка [math]a[/math] является прямо достижимой из основной точки [math]b[/math] , если [math]a[/math] находится на расстоянии, не большем [math]<\epsilon>[/math] от точки [math]b[/math] .
- Точка [math]a[/math] является достижимой из [math]b[/math] , если существует путь [math]p_1, \dots, p_n[/math] с [math]p_1 = a[/math] и [math]p_n = b[/math] , где каждая точка [math]p_
- Все остальные точки, которые не достижимы из основных точек, считаются шумовыми.
Основная точка вместе со всеми достижимыми из нее точками формирует кластер. В кластер будут входить как основные, так и неосновные точки. Таким образом, каждый кластер содержит по меньшей мере одну основную точку.
Алгоритм начинается с произвольной точки из набора, которая еще не просматривалась. Для точки ищется [math]<\epsilon>[/math] -окрестность. Если она не содержит как минимум [math]m[/math] точек, то помечается как шумовая, иначе образуется кластер [math]K[/math] , который включает все точки из окрестности. Если точка из окрестности уже является частью другого кластера [math]C_j[/math] , то все точки данного кластера добавляются в кластер [math]K[/math] . Затем выбирается и обрабатывается новая, не посещённая ранее точка, что ведёт к обнаружению следующего кластера или шума.
На выходе получаем разбиение на кластеры и шумовые объекты. Каждый из полученных кластеров [math]C_j[/math] является непустым множеством точек и удовлетворяет двум условиям:
- Любые две точки в кластере попарно связаны (то есть найдется такая точка в кластере, из которой достижимы обе этих точки).
- Если точка достижима из какой-либо точки кластера, то она принадлежит кластеру.
Пусть для каждого [math]x \in X^m[/math] имеем посчитанной его [math]\epsilon[/math] -окрестность [math]U_<\epsilon>(x) = \
DBSCAN находит практическое применение во многих реальных задачах, например, в маркетинге: необходимо предложить покупателю релевантный товар, который подойдет под его заказ. Выбрать такой товар можно, если посмотреть на похожие заказы других покупателей — в таком случае похожие заказы образуют кластер вещей, которые часто берут вместе. Похожим образом с помощью DBSCAN можно исследовать и находить общие интересы людей, делить их на социальные группы, моделировать поведение посетителей сайта. Алгоритм также может использоваться для сегментации изображений.
Пример кода
Пример на языке R
Для реализации алгоритма k-средних используется пакет ClusterR . В нем реализовано 2 функции: KMeans_arma() и KMeans_rcpp() . В примере далее рассмотрена реализация с использованием функции KMeans_arma() .
Алгоритмы кластеризации на службе Data Mining
Данный материал — попытка систематизировать и дать целостный взгляд на последние достижения в области разработки эффективных подходов к кластеризации данных. Целью материала не являлось подробное описание всех алгоритмов кластеризации. Наоборот, обзорный характер статьи и затронутая проблематика помогут сориентироваться в огромном количестве алгоритмов кластеризации.
Введение
Кластеризация – объединение в группы схожих объектов – является одной из фундаментальных задач в области анализа данных и Data Mining. Список прикладных областей, где она применяется, широк: сегментация изображений, маркетинг, борьба с мошенничеством, прогнозирование, анализ текстов и многие другие. На современном этапе кластеризация часто выступает первым шагом при анализе данных. После выделения схожих групп применяются другие методы, для каждой группы строится отдельная модель.
Задачу кластеризации в том или ином виде формулировали в таких научных направлениях, как статистика, распознавание образов, оптимизация, машинное обучение. Отсюда многообразие синонимов понятию кластер – класс, таксон, сгущение.
На сегодняшний момент число методов разбиения групп объектов на кластеры довольно велико – несколько десятков алгоритмов и еще больше их модификаций. Однако нас интересуют алгоритмы кластеризации с точки зрения их применения в Data Mining.
Кластеризация в Data Mining
Кластеризация в Data Mining приобретает ценность тогда, когда она выступает одним из этапов анализа данных, построения законченного аналитического решения. Аналитику часто легче выделить группы схожих объектов, изучить их особенности и построить для каждой группы отдельную модель, чем создавать одну общую модель на всех данных. Таким приемом постоянно пользуются в маркетинге, выделяя группы клиентов, покупателей, товаров и разрабатывая для каждой из них отдельную стратегию.
Очень часто данные, с которыми сталкивается технология Data Mining, имеют следующие важные особенности:
- высокая размерность (тысячи полей) и большой объем (сотни тысяч и миллионы записей) таблиц баз данных и хранилищ данных (сверхбольшие базы данных);
- наборы данных содержат большое количество числовых и категорийных атрибутов.
Все атрибуты или признаки объектов делятся на числовые (numerical) и категорийные (categorical). Числовые атрибуты – это такие, которые могут быть упорядочены в пространстве, соответственно категорийные – которое не могут быть упорядочены. Например, атрибут «возраст» – числовой, а «цвет» – категорийный. Приписывание атрибутам значений происходит во время измерений выбранным типом шкалы, а это, вообще говоря, представляет собой отдельную задачу.
Большинство алгоритмов кластеризации предполагают сравнение объектов между собой на основе некоторой меры близости (сходства). Мерой близости называется величина, имеющая предел и возрастающая с увеличением близости объектов. Меры сходства «изобретаются» по специальным правилам, а выбор конкретных мер зависит от задачи, а также от шкалы измерений. В качестве меры близости для числовых атрибутов очень часто используется евклидово расстояние, вычисляемое по формуле:
Для категорийных атрибутов распространена мера сходства Чекановского-Серенсена и Жаккара ( \mid t_1 \cap t_2\mid/\mid t_1\cup t_2 \mid) .
Потребность в обработке больших массивов данных в Data Mining привела к формулированию требований, которым, по возможности, должен удовлетворять алгоритм кластеризации. Рассмотрим их:
- Минимально возможное количество проходов по базе данных;
- Работа в ограниченном объеме оперативной памяти компьютера;
- Работу алгоритма можно прервать с сохранением промежуточных результатов, чтобы продолжить вычисления позже;
- Алгоритм должен работать, когда объекты из базы данных могут извлекаться только в режиме однонаправленного курсора (т.е. в режиме навигации по записям).
Алгоритм, удовлетворяющий данным требованиям (особенно второму), будем называть масштабируемым (scalable). Масштабируемость – важнейшее свойство алгоритма, зависящее от его вычислительной сложности и программной реализации. Имеется и более емкое определение. Алгоритм называют масштабируемым, если при неизменной емкости оперативной памяти с увеличением числа записей в базе данных время его работы растет линейно.
Но далеко не всегда требуется обрабатывать сверхбольшие массивы данных. Поэтому на заре становления теории кластерного анализа вопросам масштабируемости алгоритмов внимания практически не уделялось. Предполагалось, что все обрабатываемые данные будут умещаться в оперативной памяти, главный упор всегда делался на улучшение качества кластеризации.
Трудно соблюсти баланс между высоким качеством кластеризации и масштабируемостью. Поэтому в идеале в арсенале Data Mining должны присутствовать как эффективные алгоритмы кластеризации микромассивов (microarrays), так и масштабируемые для обработки сверхбольших баз данных (large databases).
Алгоритмы кластеризации: блеск и нищета
Итак, уже можно классифицировать кластерные алгоритмы на масштабируемые и немасштабируемые. Продолжим классификацию.
По способу разбиения на кластеры алгоритмы бывают двух типов: иерархические и неиерархические. Классические иерархические алгоритмы работают только с категорийными атрибутами, когда строится полное дерево вложенных кластеров. Здесь распространены агломеративные методы построения иерархий кластеров – в них производится последовательное объединение исходных объектов и соответствующее уменьшение числа кластеров. Иерархические алгоритмы обеспечивают сравнительно высокое качество кластеризации и не требуют предварительного задания количества кластеров. Большинство из них имеют сложность O(n^2) .
Неиерархические алгоритмы основаны на оптимизации некоторой целевой функции, определяющей оптимальное в определенном смысле разбиение множества объектов на кластеры. В этой группе популярны алгоритмы семейства k-средних (k-means, fuzzy c-means, Густафсон-Кесселя), которые в качестве целевой функции используют сумму квадратов взвешенных отклонений координат объектов от центров искомых кластеров.
Кластеры ищутся сферической либо эллипсоидной формы. В канонической реализации минимизация функции производится на основе метода множителей Лагранжа и позволяет найти только ближайший локальный минимум. Использование методов глобального поиска (генетические алгоритмы) значительно увеличит вычислительную сложность алгоритма.
Рисунок 1. Гистограммы двух разбиений
Среди неиерархических алгоритмов, не основанных на расстоянии, следует выделить EM-алгоритм (Expectation-Maximization). В нем вместо центров кластеров предполагается наличие функции плотности вероятности для каждого кластера с соответствующим значением математического ожидания и дисперсией. В смеси распределений (рис. 2) ведется поиск их параметров (средние и стандартные отклонения) по принципу максимума правдоподобия. Алгоритм EM и есть одна из реализаций такого поиска. Проблема заключается в том, что перед стартом алгоритма выдвигается гипотеза о виде распределений, которые оценить в общей совокупности данных сложно.
Рисунок 2. Распределения и их смесь
Еще одна проблема появляется тогда, когда атрибуты объекта смешанные – одна часть имеет числовой тип, а другая часть – категорийный. Например, пусть требуется вычислить расстояние между следующими объектами с атрибутами (Возраст, Пол, Образование):
Первый атрибут является числовым, остальные – категорийными. Если мы захотим воспользоваться классическим иерархическим алгоритмом с какой-либо мерой сходства, нам придется каким-то образом произвести дискредитацию атрибута «Возраст». Например, так:
При этом часть информации, мы, безусловно, потеряем. Если же мы будем определять расстояние в евклидовом пространстве, то возникнут вопросы с категорийными атрибутами. Понятно, что расстояние между «Пол муж» и «Пол жен» равно 0, т.к. значения этого признака находятся в шкале наименований. А атрибут «Образование» можно измерить как в шкале наименований, так и в шкале порядка, присвоив каждому значению определенные балл.
Какой вариант выбрать? А что делать, если категорийные атрибуты важнее числовых? Решение этих проблем ложится на плечи аналитика. Кроме того, при использовании алгоритма k-средних и ему подобных возникают трудности с пониманием центров кластеров у категорийных атрибутов, априорным заданием количества кластеров.
Алгоритм оптимизации целевой функции в неиерархических алгоритмах, основанных на расстояниях, носит итеративный характер, и на каждой итерации требуется рассчитывать матрицу расстояний между объектами. При большом числе объектов это неэффективно и требует серьезных вычислительных ресурсов. Вычислительная сложность 1-й итерации алгоритма k-means оценивается как O(kmn) , где k,m,n — количество кластеров, атрибутов и объектов соответственно. Но итераций может быть очень много! Придется делать много проходов по набору данных.
Имеет массу недостатков в k-means сам подход с идеей поиска кластеров сферической или эллипсоидной формы. Подход хорошо работает, когда данные в пространстве образуют компактные сгустки, хорошо отличимые друг от друга. А если данные имеют вложенную форму, то ни один из алгоритмов семейства k-means никогда не справится с такой задачей. Также алгоритм плохо работает в случае, когда один кластер значительно больше остальных, и они находятся близко друг от друга – возникает эффект «расщепления» большого кластера (рис. 3).
Рисунок 3. Эффект расщепления большого кластера
Впрочем, исследования в области совершенствования алгоритмов кластеризации идут постоянно. Разработаны интересные расширения алгоритма k-means для работы с категорийными атрибутами (k-modes) и смешанными атрибутами (k-prototypes). Например, в k-prototypes расчет расстояний между объектами осуществляется по-разному в зависимости от типа атрибута.
На рынке масштабируемых алгоритмов кластеризации борьба идет за снижение каждого «дополнительного» прохода по набору данных во время работы алгоритма. Разработаны масштабируемые аналоги k-means и EM (scalable k-means и scalable EM), масштабируемые агломеративные методы (CURE, CACTUS). Эти современные алгоритмы требуют всего несколько (от двух до десяти) сканирований базы данных до получения финальной кластеризации.
Получение масштабируемых алгоритмов основано на идее отказа от локальной функции оптимизации. Парное сравнение объектов между собой в алгоритме k-means есть не что иное, как локальная оптимизация, т.к. на каждой итерации необходимо рассчитывать расстояние от центра кластера до каждого объекта. Это ведет к большим вычислительным затратам.
При задании глобальной функции оптимизации добавление новой точки в кластер не требует больших вычислений: оно рассчитывается на основе старого значения, нового объекта и так называемых кластерных характеристик (clusters features). Конкретные кластерные характеристики зависят от того или иного алгоритма. Так появились алгоритмы BIRCH, LargeItem, CLOPE и многие другие.
Таким образом, не существует единого универсального алгоритма кластеризации. При использовании любого алгоритма важно понимать его достоинства и недостатки, учитывать природу данных, с которыми он лучше работает и способность к масштабируемости.