Кластерный анализ

(n-2) строки для последней матрицы взяты из предыдущей, а первая строка вычислена заново. Вычисления могут быть сведены к минимуму, если удастся выразить di j2k,k = 1, 2,…, n; (k ¹ i ¹ j) через элементы первоначальной матрицы.

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

di+j,k = ½ (di k + dj k).

Но можно также определить di+j,k как минимальное из этих двух расстояний:

di+j,k  = min (di k + dj k).

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

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

di+j,k = A(w) min(dik djk) + B(w) max(dik djk), где

A(w) = , если dik £ djk

A(w) = , если dik > djk

B(w) = , если dik £ djk

B(w) = , если dik >  djk

где ni  и nj - число элементов в кластерах i и j, а w – свободный параметр, выбор которого определяет конкретный алгоритм. Например, при w = 1 мы получаем, так называемый, алгоритм «средней связи», для которого формула перерасчета расстояний принимает вид:

di+j,k =

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

Наглядный смысл параметра w становится понятным, если положить w ® ¥. Формула пересчета расстояний принимает вид:

di+j,k = min (di,k djk)

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

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

В случае кластер анализа  объектов наиболее часто мерой различия служит либо квадрат евклидова расстояния

(где xih, xjh - значения h-го  признака для i-го и j-го объектов, а m - число характеристик), либо  само евклидово расстояние. Если  признакам приписывается разный  вес, то эти веса можно учесть при вычислении расстояния

Иногда в качестве меры различия  используется расстояние, вычисляемое по формуле:

которые называют: «хэмминговым», «манхэттенским» или «сити-блок» расстоянием.

Естественной  мерой сходства характеристик объектов во многих задачах является коэффициент корреляции между ними

где mi ,mj ,di  ,dj - соответственно средние и среднеквадратичные отклонения для характеристик i и j. Мерой различия между характеристиками может служить величина  1 - r. В некоторых задачах  знак коэффициента корреляции несуществен и зависит лишь от  выбора единицы измерения. В этом случае в качестве меры различия  между характеристиками используется ô1 - ri j ô.

2.2 Итеративные методы

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

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

• Алгоритм k-средних (k-means)

Наиболее распространен  среди неиерархических методов  алгоритм k-средних, также называемый быстрым кластерным анализом. Полное описание алгоритма можно найти  в работе Хартигана и Вонга (Hartigan and Wong, 1978). В отличие от иерархических  методов, которые не требуют предварительных предположений относительно числа кластеров, для возможности использования этого метода необходимо иметь гипотезу о наиболее вероятном количестве кластеров.

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

Общая идея алгоритма: заданное фиксированное число k кластеров  наблюдения сопоставляются кластерам  так, что средние в кластере (для  всех переменных) максимально возможно отличаются друг от друга.

К достоинствам алгоритма k-средних относятся простота и бысторота использования ,а так же понятность и прозрачность алгоритма.

Недостатки алгоритма k-средних:

• алгоритм слишком чувствителен к выбросам, которые могут искажать среднее. Возможным решением этой проблемы является использование модификации алгоритма - алгоритм k-медианы;
• алгоритм может медленно работать на больших базах данных. Возможным решением данной проблемы является использование выборки данных.
• Алгоритм PAM ( partitioning around Medoids)

PAM является модификацией алгоритма k-средних, алгоритмом k-медианы (k-medoids).

Алгоритм менее чувствителен к шумам и выбросам данных, чем  алгоритм k-means, поскольку медиана  меньше подвержена влияниям выбросов. Он ффективен для небольших баз данных, но его не следует использовать для больших наборов данных.

Итеративные методы кластеризации  различаются выбором следующих  параметров:

• начальной точки;
• правилом формирования новых кластеров;
• правилом остановки.

Выбор метода кластеризации  зависит от количества данных и от того, есть ли необходимость работать одновременно с несколькими типами данных.

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

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

 

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

2. Алгоритм WaveCluster

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

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

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

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

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

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