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

Неявное задание критериев качества в алгоритме кластеризации.

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

Выделяется как минимум три цели кластеризации [Воронцов 2015]:

• 5. описать структуру пространства объектов, разбивая его на классы похожих объектов и исследуя области сгущения (выделить темы),
• 6. сократить объем данных, выделяя наиболее типичных представителей каждого кластера,
• 7. выделить специфические объекты, не относящиеся ни к одному из кластеров.

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

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

Существует немало работ, посвященных описанию алгоритмов кластеризации [Jain A. и др. 1999]. Мы не ставим перед собой задачу повторить эти труды и описать все возможные алгоритмы, но лишь описываем наиболее стандартные и используемые, для того чтобы оправдать выбор методов, предпринятый нами в практической части работы.

Алгоритм выделения связных компонент.

Выделение связанных компонент [Лагутин 2003] - один из простейших методов кластеризации. Пространство представляется в виде графа: вершинами являются объекты, а каждому ребру соответствует число — длина пути между соответствующими объектами. Фиксируется некоторый параметр и перекрываются все те ребра, длина которых больше параметра. Граф распадается на компоненты связности (между вершинами различных компонент не может быть пути, проходящего по ребрам графа). Каждая компонента и будет искомым кластером.

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

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

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

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

Алгоритм ФОРЭЛ (Формальный элемент).

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

Этот алгоритм имеет множество вариаций и модификаций [Загоруйко 1999], которые отличаются способом объединения окрестностей формальных элементов в кластеры, способами изменения параметра, способами выбора начального положения формальных элементов, однако построены на одном и том же принципе. Значительно усложняется процедура кластеризации, если пространство нелинейно. Доказано, что он сходится за конечное число шагов.

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

Во-первых, среднее внутрикластерное расстояние должно быть как можно меньше:

С другой стороны, среднее межкластерное расстояние должно быть как можно больше:

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

Для поиска минимума функционала можно использовать один из оптимизационных алгоритмов, например, EM-алгоритм и др.

Разделение смеси распределений.

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

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

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

Метод k-средних Один из самых используемых алгоритмов кластеризации [Мандель 1988], метод k-средних, делит пространство объектов на кластеры близкого объема, минимизируя разброс — среднеквадратическое отклонение объектов кластера от соответствующего центра масс. Для его работы требуется задание числа кластеров.

Более формально, если — выборка пространства объектов, подбирается такой классификатор, что если — центры масс кластеров, то величина.

достигает минимума.

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

• · Во-первых, при такой постановке предполагается, что кластеры выпуклы и изотропны, т. е. распределение значений внутри кластера не зависит от координат. Некоторые модификации позволяют ослабить это требование.
• · Во-вторых, среднеквадратический разброс — ненормированная метрика. Известно лишь, что эталонным значением является нуль, а меньшее значение разброса предпочтительнее.
• · Отдельной проблемой представляется работа с пространствами очень больших размерностей, тогда зачастую векторы сильно разрежены. Применение алгоритмов понижения размерностей (например, PCA) существенно сокращает скорость вычисления, зачастую при этом понижая шум.

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

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

Метод k-средних по сути представляет собой упрощенную версию EM-алгоритма при разделении смеси: в первом случае каждому объекту однозначно соответствует единственный кластер, тогда как во втором случае каждому объекту соответствует некоторое вероятностное распределение на всем множестве кластеров.

Этот метод — один из самых используемых в прикладных задачах, существует немало модификаций, позволяющих учесть тонкие настройки оптимизации или формы кластеров. Он крайне чувствителен к начальным приближениям центров кластеров вплоть до того, что разные стартовые позиции могут привести к разным локальным минимумам функционала качества. С этой проблемой есть разные способы борьбы, один из которых — параллельный запуск нескольких случайных приближений. Иной метод, предназначенный для решения проблемы поиска глобального минимума, называют схемой инициализации k-means++. В качестве априорного приближения выбираются наиболее удаленные друг от друга точки. Доказано, что таким путем получается заведомо лучшая кластеризация, чем при генерации случайных центров.

Метод сигнала родства (Affinity Propagation).

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

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

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

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

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

где — степень близости, а характерность, в свою очередь:

Начальные значения, считаются нулями, параметры пересчитываются до сходимости.

Сдвиг среднего (Mean Shift).

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

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

Новое приближение центроида есть сдвиг прежней величины на функцию :

Спектральная кластеризация (Spectral clustering).

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

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

Спектральный метод особенно распространен при обработке изображений.

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

Иерархические алгоритмы бывают двух видов — нисходящие и восходящие. Первые делят пространство на всё более мелкие части.

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

На первом шаге каждый объект считается одним кластером, между которыми естественным образом задана функция расстояния:. Объединение происходит следующим образом. На каждом шаге два самых близких кластера и объединяются в единый кластер. Расстояние между и прочими кластерами пересчитывается по формуле, в самом общем виде предложенной Лансом и Уильямосом []:

где, , и — числовые параметры. Через это представление выражаются почти все разумные метрики пространства кластеров.

Чаще всего используются следующие способы вычисления расстояний :

(1) Расстояние ближнего соседа:

(2) Расстояние дальнего соседа:

(3) Среднее расстояние:

(4) Расстояние между центрами:

(5) Расстояние Уорда:

DBSCAN.

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

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

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