Шалымов Д.С. - Алгоритмы устойчивой кластеризации на основе индексных функций и функций устойчивости

Алгоритмы устойчивой кластеризациина основе индексных функцийи функций устойчивости1Д. С. ШалымовСанкт-Петербургский государственный университетКластеризация активно изучается в таких областях, как статистика, распознавание образов, машинное обучение и др. В работе дается определениепонятий кластеризации и устойчивости кластеризации, описывается актуальность и основные проблемы кластеризации, предлагается обзор существующих алгоритмов устойчивой кластеризации на основе индексов и на основефункций устойчивости.Ключевые слова: кластеризация, устойчивость кластеризации.1.ВведениеКластеризацией является разбиение множества данных на группы по схожим признакам. Кластеризация используется при решении многообразных задач обработки данных, в том числе при распознавании образов, машинном обучении, автоматической классификации, выработке стратегий управления и т.

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

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

Также большинство из них недостаточно математически обоснованы. В статье рассматривается несколько помехоустойчивых алгоритмов, которые могут работать на множествах произвольной структуры.2.Задача кластеризацииКластеризацию можно определить как процесс объединения данных в группы по схожим признакам. Эта задача является одной изфундаментальных в области анализа данных и Data Mining. Список областей, в которых применяется кластеризация, очень широк: сегментация изображений, прогнозирование, анализ текстов,сжатие данных и многие др.

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

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

Имеется обучающая последовательность (набор данных){x1 , . . . , xn } ∈ X и функция расстояния между объектами ρ(x, x0).Требуется разбить последовательность на непересекающиеся подмножества (называемые кластерами) так, чтобы каждый кластерсостоял из объектов, близких по метрике ρ , а объекты разных кластеров существенно отличались. Алгоритм кластеризации — этофункция a : X → Y , которая любому объекту x ∈ X ставит всоответствие метку кластера yi ∈ Y . Множество меток Y заранеенеизвестно.На сегодняшний момент число методов разбиения групп объектов на кластеры довольно велико - несколько десятков алгоритмови еще больше их модификаций.В кластеризации выделяют два основных подхода: декомпозиция (неиерархический), когда каждый объект связан только с однойгруппой, и кластеризация на основе иерархий (иерархический), когда каждая группа большего размера состоит из групп меньшегоразмера.Классические иерархические алгоритмы работают только с категорийными атрибутами, когда строится полное дерево вложенных кластеров.

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

Большинство из них имеютсложность O(n2 ).Неиерархические алгоритмы основаны на оптимизации некоторой целевой функции, определяющей оптимальное в определенномсмысле разбиение множества объектов на кластеры. В этой группе популярны алгоритмы семейства k-средних (k-means), которые вкачестве целевой функции используют сумму квадратов взвешенных отклонений координат объектов от центров искомых кластеров. Кластеры ищутся сферической либо эллипсоидной формы.Решение задачи кластеризации принципиально неоднозначно,поскольку не существует однозначно наилучшего критерия качества кластеризации, число кластеров, как правило, неизвестно заранее и устанавливается в соответствии с некоторым субъективнымкритерием, а также результат кластеризации во многих алгоритмахсущественно зависит от метрики, выбор которой чаще всего субъективен и определяется экспертом.Таким образом, не существует единого универсального алгоритма кластеризации.

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

Количество кластеров, которое максимизирует кластерную устойчивость,может служить хорошей оценкой для реального количества кластеров. Проблема определения устойчивой кластеризации являетсяодной из наиболее сложных проблем кластерного анализа.Большая часть работ, посвященных устойчивой кластеризации,нацелены на конкретные прикладные проблемы. Известные алго239ритмы устойчивой кластеризации требуют определенных предположений о своих параметрах и недостаточно математически обоснованы. Также их вычислительная сложность существенно растетпри увеличении мощности исследуемого множества данных.Еще одной существенной трудностью кластерного анализа является нахождение первоначальных центров предполагаемых кластеров, т. е.

данных, с которых начинают работу алгоритмы. С теоретической точки зрения это могут быть любые точки пространства. Однако на практике выбор начальных центров значительносказывается как на скорости сходимости алгоритмов, так и на качестве результатов.Существует несколько базовых подходов к определению количества кластеров в множестве данных. Они основаны на:1) определяемых с помощью индексов, сравнивающих степени“разброса” данных внутри кластеров и между кластерами;2) расчете значений характеристик (функций устойчивости),показывающих соответствие назначенных кластеров для выборочных элементов множества;3) статистиках, определяющих наиболее вероятное решение;4) оценивании плотностей распределений.Рассмотрим наиболее известные алгоритмы устойчивой кластеризации на основе индексов.Первый подход (Calinski-Harabasz) [1] выбирает количество кластеров как значение аргумента, максимизирующего функцию CH(K),CH(K) =B(K)/(K − 1),W (K)/(n − K)где B(K) и W (K), соответственно, внешняя и внутренняя суммыквадратов элементов данных с K кластерами.

Это один из самыхпервых предложенных методов. Он оказывается эффективным приданных небольших размерностей.Подход Krzanowski and Lai [2] максимизирует функцию KL(K): DIF F (K) ,KL(K) = DIF F (K + 1)240где DIF F (K) = (K −1)2/p W (K −1)−(K)2/pW (K), p — размерностьпространства.Основная идея заключается в измерении порядка изменчивостивнутренних дисперсий.Hartigan [3] предлагает выбирать такое наименьшее значение K,что H(K) меньше либо равно 10H(K) = (n − K − 1)[W (K)− 1].W (K + 1)Еще один метод был предложен Kaufman and Rousseeuw [4], вкотором измеряется, насколько i-я точка была хорошо кластеризована.