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

Содержание 

 

 

 

 

 

 

 

 

Введение

 

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

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

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

Кластерный анализ наиболее ярко отражает черты многомерного анализа в классификации, факторный анализ – в исследовании связи.

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

 

1. Понятие кластерного анализа

 

Кластерный анализ – это совокупность методов, позволяющих классифицировать многомерные наблюдения. Термин кластерный анализ, впервые введенный Трионом (Tryon) в 1939 году, включает в себя более 100 различных алгоритмов.

КЛАСТЕР — Класс родственных элементов статистической совокупности.

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

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

Задачи кластерного анализа можно объединить в следующие группы:

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

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

3. Представление гипотез на основе  исследования данных.

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

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

 

 

 

2. Кластерный анализ с примерами на R

 

Рассмотрим кластерный анализ на примере. У каждого элемента данных есть набор характеристик (например, если речь идет о людях: возраст, пол, образование и т.п.).

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

Предварительная работа

Рассмотрим, к примеру, набор данных:

Имя	Возраст	Город	Доход
Петя	25	Москва	120000
Вася	34	Киров	45000
Маша	27	Самара	15000
Света	36	Нью-Йорк	150000
Катя	24	Москва	30000

 

Каким образом можно разбить эти данные на кластеры?

Можно по зарплате:

• Петя и Света в один кластер,
• Вася и Катя во второй,
• Маша в третий.

Можно по возрасту:

• Петя, Маша и Катя в один,
• Вася и Света во второй.

Можно еще разбить по месту жительства или полу.

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

Существуют различные меры расстояний, но для нас интуитивно понятным является классическое Евклидово. Важно лишь правильно нормализовать данные. Как в нашем примере: зарплаты измеряются в тысячах, а возраст в годах. Непосредственно сравнивать эти две величины нельзя. А вот если предварительно привести их к диапазону от 0 до 1 то они станут вполне сравнимыми.

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

 

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

 

Известно множество алгоритмов кластерного анализа. Далеко не полная и не единственная возможная классификация представлена на рисунке ниже.

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

Все методы кластеризации работают с данными в виде векторов в многомерном пространстве. Каждый вектор определяется значениями нескольких направлений, а направления и есть известные нам характеристики (пол, возраст, образование). Характеристики могут быть как количественные, так и качественные и искусство специалиста по data mining состоит в том, чтобы правильно отобрать и нормализовать эти характеристики, а потом выбрать подходящую меру расстояний. И только после этого в игру вступают алгоритмы кластеризации.

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

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

Итак, сам алгоритм:

1) Выбрать k случайных центров в пространстве, содержащем исходные данные

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

3) Пересчитать  центры кластеров используя полученное распределение объектов

4) Если  алгоритм не сошелся, то перейти  к п. 2.

Типичные критерии схождения алгоритма это либо среднеквадратичная

ошибка, либо отсутствие перемещений объектов из кластера в кластер.

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

Иерархическая кластеризация

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

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

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

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

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

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

Кластером считается множество элементов, соединенных "остатком" дерева. С каждым убранным ребром, количество кластеров увеличивается. 

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

Этот подход очень популярен в области распознавания изображений. Идея такая: предположим, что каждый кластер в наших данных, подчиняется некоторому распределению, как правило предполагается Гаусовское распределение. Далее, методами статистики, мы определяем параметры допустимых распределений и их центры.

Методы объединения (кластеризации)

SPSS предлагает, в общей сложности, 7 методов объединения. Из них  метод Межгрупповые связи (Between-groups linkage) устанавливается по умолчанию.

1. Межгрупповые связи (Between-groups linkage)

 

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

• Связь внутри групп (Within-groups linkage)

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

• Близлежащий сосед (Nearest neighbor)

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

• Дальний сосед (Furthest neighbor)

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

• Центроидная кластеризация (Centroid clustering)

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

 

• Медианная кластеризация (Median clustering)

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

• Метод Варда (Ward's Method)

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

Так как некоторые из предлагаемых методов имеют явные недостатки (Близлежащий сосед, Дальний сосед), а другие очень мало наглядны и плохо поддаются последующему анализу, рекомендуется применять устанавливаемый по умолчанию и наиболее понятный метод Between-groups linkage (Межгрупповые связи).

 

Заключение

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