bigpo.ru
добавить свой файл
1
Исследование и рандомизация алгоритмов устойчивой кластеризации на основе индексов

О. Н. Граничин, профессор, доктор физ.-мат. наук, мат.-мех. факультет СПбГУ, oleg_granichin@mail.ru

Д. С. Шалымов, аспирант мат.-мех. факультета СПбГУ, shalydim@mail.ru


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

1. Введение

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

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

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

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

2. Задача кластеризации

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

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

Цели кластеризации могут быть различными в зависимости от особенностей конкретной прикладной задачи:

  • определить структуру множества данных, разбив его на группы схожих объектов, упростив дальнейшую обработку данных при работе уже с каждым кластером в отдельности;

  • сократить объём хранимых данных, оставив по одному наиболее типичному представителю от каждого кластера;

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

Основная суть алгоритмов кластеризации заключается в следующем. Имеется последовательность (набор из n>0 данных) {x1,...,xn}X и функция расстояния между объектами ρ(x, x′). Требуется разбить последовательность на непересекающиеся подмножества (называемые кластерами) так, чтобы каждый кластер состоял из объектов, близких по метрике ρ, а объекты разных кластеров существенно отличались. Алгоритм кластеризации – это функция a: X → Y , которая любому объекту xX ставит в соответствие метку кластера yi Y . Множество меток Y заранее неизвестно.

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

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

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

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

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

3. Устойчивая кластеризация. Индексные методы

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

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

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

Существует несколько базовых подходов к определению количества кластеров в множестве данных. Они основаны на:

1) индексах, сравнивающих степени «разброса» данных внутри кластеров и между кластерами;

2) расчете значений эвристических характеристик (функций устойчивости), показывающих соответствие назначенных кластеров для выборочных элементов множества;

3) статистиках, определяющих наиболее вероятное решение;

4) оценивании плотностей распределений.

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

Первый подход (Calinski-Harabasz) [1] выбирает количество кластеров как значение аргумента, максимизирующего функцию

,

где B(K) и W(K) − внешняя и внутренняя суммы квадратов элементов данных с K кластерами соответственно. Это один из самых первых предложенных методов. Он оказывается эффективным при данных небольших размерностей.

Подход Krzanowski and Lai [2] максимизирует функцию

,

где

.

Основная идея заключается в измерении порядка изменчивости внутренних дисперсий.

Hartigan [3] предлагает выбирать наименьшее значение K, такое что соответствующее значение функции



меньше либо равно 10.

Еще один метод был предложен Kaufman and Rousseeuw [4], в котором измеряется, насколько i-я точка была хорошо кластеризована. Для этого определяют функцию

,

где a(i) – среднее расстояние между i-ой точкой и всеми остальными наблюдениями, попавшими в тот же кластер, b(i) – среднее расстояние до точек в ближайшем кластере, где под ближайшим кластером понимается тот, который минимизирует b(i). Количество кластеров считается верным, если оно максимизирует среднее значение s(i).

Другой, более редкий, метод использует статистику расхождений [5], вычисляя



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

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

Известен эффективный непараметрический метод, предложенный Sugar and James [7]. Он основан на использовании «искажений», которые по своей сути являются оценками дисперсии внутри класса. Для иллюстрации эффективности алгоритма строится специальный функционал зависимости минимального «искажения» от количества кластеров, который убывает с ростом количества кластеров. Минимальное «искажение» определяется следующим образом: на множестве данных с учетом текущего количества кластеров запускается какой-либо алгоритм кластеризации. Как правило, это k-means. Множество разбивается на отдельные кластеры, для каждого из которых подсчитывается внутренняя дисперсия. Из множества значений дисперсий выбирается наименьшее, которое принимается за минимальное «искажение» и становится значением функционала при данном количестве кластеров. Теоретически и эмпирически доказывается, что, при определенном выборе параметра Y (степень трансформации), построенная для функционала кривая будет иметь резкий скачок в том месте, которое соответствует действительному количеству кластеров.

Процедура определения количества кластеров состоит из следующих шагов:

1. Запускается k-means алгоритм для K кластеров и определяется соответствующее «искажение» . Для различных значений K строится набор .

2. Выбирается степень трансформации Y>0 (обычно принимается Y=p/2).

3. Вычисляются скачки по формуле

4. За итоговое количество кластеров выбирается то, которое соответствует наибольшему скачку .



Рис.1. a) Набор из девяти кластеров (Гауссово распределение) b) Кривая функционала (внутренняя дисперсия – количество кластеров) c) Преобразованная кривая, показывыающая количество кластеров, равное девяти. d) Кривая скачков

На Рис. 1 изображены зависимости «искажений» от количества кластеров. В данном случае использовано Гауссово распределение, однако метод был апробирован также на негауссовых данных.

4. Рандомизированные алгоритмы в задаче устойчивой кластеризации

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

Известно, что в других приложениях снять эти трудности удается при использовании рандомизированных алгоритмов, сложность которых, как правило, не сильно растет с ростом размерности исходной задачи [8]. Кроме того, эффективность процесса кластеризации может быть улучшена при использовании рандомизированных алгоритмов стохастической аппроксимаци с возмущением на входе (типа SPSA - simultaneously perturbation stochastic approximation) [9] за счет того, что они при небольших вычислительных затратах на каждой итерации обеспечивают сходимость при почти произвольных помехах.

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

В настоящий момент ведутся исследования, связанные с использованием этих алгоритмов в методах устойчивой кластеризации на основе индексов. В описанном выше методе Sugar and James была использована кривая функционала (внутренняя дисперсия – количество кластеров), которая может быть изменена за счет варьирования степени трансформации Y и функции скачков .

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

Оценив количество кластеров, можно далее использовать как широко известные методы кластеризации (например, k-means), так и достаточно новые рандомизированные алгоритмы.

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

5. Заключение

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

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

Литература

  1. Calinski, R. B. and Harabasz, J. (1974). A denrite method for cluster analysis. Communications in Statistics 3, 1–27.

  2. Hartigan, J. A. (1975). Clustering Algorithms. Wiley.

  3. Kaufman, L. and Rousseeuw, P. (1990). Finding Groups in Data: An Introduction to Cluster Analysis. New York: Wiley.

  4. Krzanowski, W. J. and Lai, Y. T. (1985). A criterion for determining the number of clusters in a data set. Biometrics 44, 23–34.

  5. Tibshirani, R., Walther, G., and Hastie, T. (2001). Estimating the number of clusters in a data set via the gap statistic. Journal of the Royal Statistical Society, Series B 63, 411–423.

  6. Z. Volkovich, Z. Barzily and L. Morozensky, A statistical model of cluster stability, Pattern Recognition (2008).

  7. C. Sugar and G. James. Finding the number of clusters in a data set : An information theoretic approach. J of the American Statistical Association, 98:750–763, 2003.

  8. Граничин О. Н., Поляк Б. Т. Рандомизированные алгоритмы оптимизации и оценивания при почти произвольных помехах. М., Наука, 2003.

  9. Spall J.C. (2003) Introduction to Stochastic Search and Optimization. Estimation, Simulation and Control. Wiley, London.

  10. Граничин О. Н., Измакова О. А. Рандомизированный алгоритм стохастической аппроксимации в задаче самообучения. Автоматика и телемеханика. 2005. No 8. C. 52 - 63.

_____________________________________________________________________

Работа посвящена исследованию алгоритмов устойчивой кластеризации на основе индексов с использованием методов стохастической аппроксимации