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

Сложности и проблемы, которые могут возникнуть при  применении кластерного анализа

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

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

Существует ряд сложностей, которые следует продумать перед  проведением кластеризации.

• Сложность выбора характеристик, на основе которых проводится кластеризация. Необдуманный выбор приводит к неадекватному разбиению на кластеры и, как следствие, - к неверному решению задачи.
• Сложность выбора метода кластеризации. Этот выбор требует неплохого знания методов и предпосылок их использования. Чтобы проверить эффективность конкретного метода в определенной предметной области, целесообразно применить следующую процедуру: рассматривают несколько априори различных между собой групп и перемешивают их представителей между собой случайным образом. Далее проводится кластеризация для восстановления исходного разбиения на кластеры. Доля совпадений объектов в выявленных и исходных группах является показателем эффективности работы метода.
• Проблема выбора числа кластеров. Если нет никаких сведений относительно возможного числа кластеров, необходимо провести ряд экспериментов и, в результате перебора различного числа кластеров, выбрать оптимальное их число.
• Проблема интерпретации результатов кластеризации. Форма кластеров в большинстве случаев определяется выбором метода объединения. Однако следует учитывать, что конкретные методы стремятся создавать кластеры определенных форм, даже если в исследуемом наборе данных кластеров на самом деле нет.

Сравнительный анализ иерархических и неиерархических  методов кластеризации

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

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

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

Иерархические методы, в отличие от неиерархических, отказываются от определения числа кластеров, а строят полное дерево вложенных кластеров.

Сложности иерархических  методов кластеризации: ограничение  объема набора данных; выбор меры близости; негибкость полученных классификаций.

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

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

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

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

Новые алгоритмы кластерного анализа и некоторые модификации алгоритмов кластерного анализа

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

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

Отметим также другие свойства, которым должен удовлетворять алгоритм кластеризации: независимость результатов  от порядка входных данных; независимость  параметров алгоритма от входных  данных.

В последнее время ведутся  активные разработки новых алгоритмов кластеризации, способных обрабатывать сверхбольшие базы данных. В них  основное внимание уделяется масштабируемости. К таким алгоритмам относятся  обобщенное представление кластеров (summarized cluster representation), а также выборка  и использование структур данных, поддерживаемых нижележащими СУБД [33].

Разработаны алгоритмы кластерного анализа, в которых методы иерархической кластеризации интегрированы с другими методами. К таким алгоритмам относятся:BIRCH, CURE, CHAMELEON, ROCK.

Алгоритм BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies)

Алгоритм предложен Тьян Зангом и его коллегами [55].

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

В этом алгоритме реализован двухэтапный процесс кластеризации.

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

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

Алгоритм WaveCluster

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

Главные особенности WaveCluster:

1. сложность реализации;
2. алгоритм может обнаруживать кластеры произвольных форм;
3. алгоритм не чувствителен к шумам;
4. алгоритм применим только к данным низкой размерности.

Алгоритм CLARA (Clustering LARge Applications)

Алгоритм CLARA был разработан Kaufmann и Rousseeuw в 1990 году для кластеризации  данных в больших базах данных. Данный алгоритм строится в статистических аналитических пакетах, например, таких  как S+.

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

Для больших баз данных этот алгоритм эффективнее, чем алгоритм PAM. Эффективность алгоритма зависит от выбранного в качестве образца набора данных. Хорошая кластеризация на выбранном наборе может не дать хорошую кластеризацию на всем множестве данных.

Алгоритмы кластерного анализа Clarans, CURE, DBScan

Алгоритм Clarans (Clustering Large Applications based upon RANdomized Search) [14] формулирует задачу кластеризации как случайный  поиск в графе. В результате работы этого алгоритма совокупность узлов  графа представляет собой разбиение множества данных на число кластеров, определенное пользователем. "Качество" полученных кластеров определяется при помощи критериальной функции. Алгоритм Clarans сортирует все возможные разбиения множества данных в поисках приемлемого решения. Поиск решения останавливается в том узле, где достигается минимум среди предопределенного числа локальных минимумов.

Среди новых масштабируемых алгоритмов также можно отметить алгоритм CURE [57] - алгоритм иерархической кластеризации, и алгоритм DBScan [58], где понятие кластера формулируется с использованием концепции плотности (density). 

 

Основным недостатком  алгоритмов BIRCH, Clarans, CURE, DBScan является то обстоятельство, что они требуют задания некоторых порогов плотности точек, а это не всегда приемлемо. Эти ограничения обусловлены тем, что описанные алгоритмыкластерного анализа ориентированы на сверхбольшие базы данных и не могут пользоваться большими вычислительными ресурсами [59].

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