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

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

- Разработка топологии и классификации.

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

- Выдвижение гипотез  на основе исследуемых данных.

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

Кластерный анализ предполагает следующие этапы:

- Отбор выборки  для кластеризации.

- Определить множество  критериев (переменных), по которым  будут оцениваться объекты в выборке.

- Вычисление значения того или иного сходства между объектами.

- Применение метода кластерного анализа для создания групп схожих объектов.

- Проверка достоверности результатов кластерного решения.

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

- Показатели не должны быть связаны между собой.

- Показатели не должны быть безразмерными.

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

- Отсутствие влияния  на значение показателей случайных факторов.

- Выборка должна быть однородна.

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

Меры  расстояний

 
Как же отбирать похожие объекты? В первую очередь необходимо вектор характеристик для каждого объекта — обычно, это набор числовых значений, как например, месяц и год человека. Так же существуют алгоритмы, работающие категорийными характеристиками. 
 
После определения вектора характеристик, нужно провести нормализацию, для того чтобы все составляющие давали одинаковый вклад при расчете «расстояния». В процессе нормализации все значения приводятся к некоторому диапазону, например, [-1, 0] или [-1, 1]. 
 
Следующий шаг, это измерение степень похожести объектов в каждом кластере. Существует множество метрик, например: 

1. Евклидова метрика 
   Самая распространенная функция расстояния, это геометрическое расстояние между двумя точками в многомерном пространстве

 где  p = (p₁, p₂,…, p_n) и q = (q₁, q₂,…, q_n)

2. Квадрат евклидовой метрики 
   Применяется для придания большего веса более отдаленным друг от друга объектам. Это расстояние вычисляется следующим образом: 
   
3. Манхэттенское расстояние (расстояние городских кварталов) 
   Это расстояние является средним разностей по координатам. Чаще случаев эта мера расстояния приводит к таким же результатам, как и для обычного расстояния Евклида, но надо учитывать, что для этой меры влияние отдельных больших разностей (выбросов) уменьшается (т.к. они не возводятся в квадрат). Формула для расчета манхэттенского расстояния: 
   
4. Расстояние Чебышева 
   Это расстояние может оказаться нужным, когда необходимо определить два объекта как «различные», есть ли у них различия какой-либо одной координате. Расстояние Чебышева вычисляется по формуле: 
   
5. Степенное расстояние 
   Используется когда есть необходимость увеличить или уменьшить вес, относящийся к размерности, для которой соответствующие объекты сильно отличаются. Степенное расстояние вычисляется по следующей формуле: 
   , 
   где r и p – параметры, определяемые пользователем. Параметр p ответственен за постепенное взвешивание разностей по отдельным координатам, параметр r ответственен за прогрессивное взвешивание больших расстояний между объектами. Если оба параметра – r и p — равны двум, то это расстояние совпадает с расстоянием Евклида.

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

Классификация алгоритмов

 
Алгоритм классифицируется как: 

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

Объединение кластеров

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

1. Одиночная связь (расстояния ближайшего соседа) 
   В этом методе расстояние между двумя кластерами определяется расстоянием между двумя наиболее близкими объектами (ближайшими соседями) в различных кластерах. При этом результирующие кластеры объединяются в цепочки.
2. Полная связь (расстояние наиболее удаленных соседей) 
   В этом методе расстояния между кластерами определяются наибольшим расстоянием между любыми двумя объектами в различных кластерах (т.е. наиболее удаленными соседями). Этот метод обычно работает отлично, если объекты берутся из отдельных групп. Если же кластеры имеют удлиненную форму или естественный тип является «цепочечным», то этот метод не годится.
3. Невзвешенное попарное среднее 
   В этом методе расстояние между двумя различными кластерами вычисляется как среднее расстояние между всеми парами объектов в них. Метод эффективен, когда объекты объединяют разные группы, однако он так же хорошо работает и в случаях протяженных («цепочечного» типа) кластеров.
4. Взвешенное попарное среднее 
   Метод идентичен методу невзвешенного попарного среднего, за исключением того, что при вычислениях размер соответствующих кластеров (т.е. число объектов, содержащихся в них) используется в качестве весового коэффициента. Поэтому данный метод должен быть использован, когда предполагаются неравные размеры кластеров.
5. Невзвешенный центроидный метод 
   В этом методе расстояние между двумя кластерами определяется как расстояние между их центрами тяжести.
6. Взвешенный центроидный метод (медиана) 
   Этот метод идентичен предыдущему, за исключением того, что при вычислениях используется вес как разница между размерами кластеров. Поэтому, если имеются или подразумеваются значительные отличия в размерах кластеров, этот метод оказывается предпочтительнее предыдущего.

Обзор алгоритмов

Алгоритмы иерархической кластеризации

 
Среди алгоритмов иерархической кластеризации можно выделить два основных типа: восходящие и нисходящие. Нисходящие алгоритмы работают по принципу «сверху-вниз»: в начале все объекты помещаются в один кластер, который затем разбивается на все более мелкие кластеры. Более распространены восходящие алгоритмы, которые являются зеркальным отражением нисходящих. Результаты таких алгоритмов обычно представляют в виде дерева – дендрограммы. Классический пример такого дерева – классификация животных и растений. 
 
Для вычисления расстояний между кластерами чаще все пользуются двумя расстояниями: одиночной связью или полной связью (см. обзор мер расстояний между кластерами). 
 
Недостатком иерархических алгоритмов можно считать систему полных разбиений. Она может быть лишней для решения задачи. 
 

Алгоритмы квадратичной ошибки

 
Необходимость кластеризации можно рассматривать как построение оптимального разбиения объектов на группы. При этом оптимальность может быть определена как требование минимизации среднеквадратической ошибки разбиения: 
 
 
 
где c_j — «центр масс» кластера j (точка со средними значениями характеристик для данного кластера). 
 
Алгоритмы квадратичной ошибки относятся к типу плоских алгоритмов. Самым распространенным алгоритмом этой категории является метод k-средних, который строит заданное число кластеров, расположенных как можно дальше друг от друга. Работа алгоритма делится на несколько этапов: 

1. Случайно выбрать k точек, являющихся начальными «центрами масс» кластеров.
2. Отнести каждый объект к кластеру с ближайшим «центром масс».
3. Пересчитать «центры масс» кластеров согласно их текущему составу.
4. Если критерий остановки алгоритма не удовлетворен, вернуться к п. 2.

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

Нечеткие  алгоритмы

 
Наиболее популярным алгоритмом нечеткой кластеризации является алгоритм c-meаns (c-средних). Он представляет собой модификацию метода k-средних. Шаги работы алгоритма: 

1. Выбрать начальное нечеткое разбиение n объектов на k кластеров путем выбора матрицы принадлежности U размера n x k.
2. Используя матрицу U, найти значение критерия нечеткой ошибки: 
   , 
   где c_k — «центр масс» нечеткого кластера k: 
   .
3. Перегруппировать объекты с целью уменьшения этого значения критерия нечеткой ошибки.
4. Возвращаться в п. 2 до тех пор, пока изменения матрицы U не станут незначительными.

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

Алгоритмы, основанные на теории графов

 
Основа таких алгоритмов заключается в том, что выборка объектов представляется в виде графа G=(V, E), вершинам которого соответствуют объекты, а ребра имеют вес, равный «расстоянию» между объектами. Достоинством графовых алгоритмов кластеризации являются наглядность, простота реализации и возможность внесения разных усовершенствований, основанных на геометрических соображениях. Основными алгоритмам являются алгоритм выделения связных компонент, алгоритм построения минимального остовного (покрывающего) дерева и алгоритм послойной кластеризации. 
 

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

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