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

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

 
Рассмотрены итеративные методы на примере алгоритма k-средних. Изложена основа факторного анализа и итеративная  кластеризация . Описан процесс кластерного  анализа. Приведен сравнительный анализ иерархических и неиерархических  методов и некоторые новые  алгоритмы кластерного анализа.

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

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

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

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

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

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

Описание алгоритма

1. Первоначальное распределение объектов по кластерам.

Выбирается число k, и на первом шаге эти точки считаются "центрами" кластеров. Каждому  кластеру соответствует один центр.

Выбор начальных центроидов может осуществляться следующим  образом:

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

В результате каждый объект назначен определенному кластеру.

2. Итеративный процесс.

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

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

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

На рис. 14.1 приведен пример работы алгоритма k-средних для k, равного двум.

 
Рис. 14.1.  Пример работы алгоритма k-средних (k=2)

Выбор числа кластеров  является сложным вопросом. Если нет  предположений относительно этого  числа, рекомендуют создать 2 кластера, затем 3, 4, 5 и т.д., сравнивая полученные результаты.

Проверка качества кластеризации

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

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

• простота использования;
• быстрота использования;
• понятность и прозрачность алгоритма.

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

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

Алгоритм PAM ( partitioning around Medoids)

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

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

PAM эффективен для небольших баз данных, но его не следует использовать для больших наборов данных.

Предварительное сокращение размерности

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

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

Факторный анализ

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

Вообще, факторный анализ преследует две цели:

• сокращение числа переменных;
• классификацию переменных - определение структуры взаимосвязей между переменными.

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

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

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

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

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

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

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

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

Итеративная кластеризация  в SPSS

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

Для сокращения размерности  исходных данных воспользуемся факторным анализом. Для этого выберем в меню: Analyze (Анализ)/Data Reduction (Преобразование данных)/Factor (Факторный анализ):

При помощи кпопки Extraction:(Отбор) следует выбрать метод отбора. Мы оставим выбранный по умолчанию  анализ главных компонентов, который  упоминался выше. Таже следует выбрать  метод вращения - выберем один из наиболее популярных - метод варимакса. Для сохранения значений факторов в  виде переменных в закладке "Значения" необходимо поставить отметку "Save as variables" (Сохранить как переменные).

В результате этой процедуры  пользователь получает отчет "Объясненная  суммарная дисперсия", по которой  видно число отобранных факторов - это те компоненты, собственные  значения которых превосходят единицу.

Полученные значения факторов, которым обычно присваиваются названия fact1_1, fact1_2 и т.д., используем для проведения кластерного анализа методом k-средних. Для проведения быстрого кластерного  анализа выберем в меню:

Analyze (Анализ)/Classify(Классифицировать)/K-Means Cluster: (Кластерный анализ методом  k-средних).

В диалоговом окне K Means Cluster Analysis (Кластерный анализ методом k-средних) необходимо поместить факторные  переменные fact1_1, fact1_2 и т.д. в поле тестируемых переменных. Здесь же необходимо указать количество кластеров  и количество итераций.

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

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

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

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

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

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

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

Процесс кластерного  анализа. Рекомендуемые этапы

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

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

Выбор метрики и метода стандартизации исходных данных.

Определение количества кластеров (для итеративного кластерного анализа).

Определение метода кластеризации (правила объединения или связи).

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

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

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

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

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