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

Основания для кластерных алгоритмов:

1. характер отношения, который отыскивается как результат классификации

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

• Разбиение с пересекающимися классами.

• Иерархическое дерево.

• Отношение произвольной структуры

2. степень участия человека в процедуре выделения кластеров

• машинный способ. Программист задает параметры классификации

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

3. характер априорных сведений для работы алгоритма

• сведений нет

• задано число искомых классов

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

• заданы комбинированные сведения

4. характер работы алгоритма классификации. В зависимости от порядка просмотра точек

• зависящие от порядка просмотра

• независящие

Плотность, дисперсия, форма, отдельность.

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

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

Кластер – непрерывные области пространства с относительно высокой плотностью точек, отделенные от других таких же областей. Методы одиночной, полной и средней связи.Метод Уорда позволяет создать кластеры приблизительно равных размеров. Сначала объединяет самые близкие объекты, затем к уже образованным присоединяются сходные с ними объекты. Мера сходства – 1, коэффициент корреляции Пирсона.

На основе анализа содержания переменных, входящих в отдельные кластеры, строится группировка респондентов по признакам, включенным в процесс кластеризации. Одиночная связь (метод ближайшего соседа). в этом методе расстояние между двумя кластерами определяется расстоянием между двумя наиболее близкими объектами (ближайшими соседями) в различных кластерах. Это правило должно, в известном смысле, нанизывать объекты вместе для формирования кластеров, и результирующие кластеры имеют тенденцию быть представленными длинными "цепочками". Полная связь (метод наиболее удаленных соседей). В этом методе расстояния между кластерами определяются наибольшим расстоянием между любыми двумя объектами в различных кластерах (т.е. "наиболее удаленными соседями"). Этот метод обычно работает очень хорошо, когда объекты происходят на самом деле из реально различных "рощ". Если же кластеры имеют в некотором роде удлиненную форму или их естественный тип является "цепочечным", то этот метод непригоден. Невзвешенное попарное среднее. В этом методе расстояние между двумя различными кластерами вычисляется как среднее расстояние между всеми парами объектов в них. Метод эффективен, когда объекты в действительности формируют различные "рощи", однако он работает одинаково хорошо и в случаях протяженных ("цепочного" типа) кластеров. Взвешенное попарное среднее. Метод идентичен методу невзвешенного попарного среднего, за исключением того, что при вычислениях размер соответствующих кластеров (т.е. число объектов, содержащихся в них) используется в качестве весового коэффициента. Поэтому предлагаемый метод должен быть использован (скорее даже, чем предыдущий), когда предполагаются неравные размеры кластеров. Невзвешенный центроидный метод. В этом методе расстояние между двумя кластерами определяется как расстояние между их центрами тяжести. Взвешенный центроидный метод (медиана). этот метод идентичен предыдущему, за исключением того, что при вычислениях используются веса для учёта разницы между размерами кластеров (т.е. числами объектов в них). Поэтому, если имеются (или подозреваются) значительные отличия в размерах кластеров, этот метод оказывается предпочтительнее предыдущего. Метод Варда. Этот метод отличается от всех других методов, поскольку он использует методы дисперсионного анализа для оценки расстояний между кластерами. Метод минимизирует сумму квадратов (SS) для любых двух (гипотетических) кластеров, которые могут быть сформированы на каждом шаге.

Иерархические алгоритмы.

рассмотрение каждого объекта как отдельного кластера.

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

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

Упорядочение матрицы расстояний и последовательного формирования кластеров.

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

Процедуры эталонного типа.

Выбираются случайным образом N-точек, объявляемых центрами классов. Стоятся окружности таким образом, чтобы не осталось свободных, неохваченных точек. Затем интерпретируются свойства объектов, объединенных в одной окружности.

Алгоритмы типа разрезанного графа.

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