Кластеризация: модуль кластерный анализ

Кластерный анализ объединяет различные процедуры, используемые для проведе­ния кластеризации. В результате применения этих процедур исходная совокупность неоднородных объектов разделяется на кластеры или группы схожих между собой объектов. Если вы взглянете на ночное небо и увидите скопления звезд, то ясно поймете, что такое кластеры.

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

В целом методы кластеризации делятся на агломеративные (лат. agglomeratus - скопление) и итеративные (лат. iterativus - часто повторяемый) дивизивные (фр. division - деление, разделение).

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

Процесс такого последовательного объединения можно показать на графике в виде дендрограммы или дерева объединения. Это удобное представление позволяет наглядно отобразить процесс кластеризации.

Исходными данными для анализа могут быть собственно объекты и их параметры, например, в рассматриваемой далее задаче с автомобилями разных марок в файле STATISTICA в наблюдениях (строках таблицы) записаны марки машин, в переменных (столбцах) характеристики: price - цена, acceler - время в секундах, необходимое для то­го, чтобы разогнаться с места до скорости 60 миль в час и др.

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

Если расстояния не даны сразу, то агломеративные алгоритмы начинаются с вычис­ления расстояний между объектами. Переход от объектов к расстояниям между объек­тами - важный момент исследования.

Расстояние между объектами - одна из мер сходства. Интуитивно понятно, что чем меньше расстояние между объектами, тем они более схожи. Но как выбрать естествен­ную метрику, т. е. как естественно для данной задачи измерить расстояние между объек­тами?

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

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

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

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

Упражнение. Представьте, что метрика имеет следующий вид р (х,у) = 1, если х А у (объект х отличается от объекта у), р (х,у) = 0, если х = у (объект х не отличает­ся от объекта у). Как вы думаете, подходит ли эта метрика для кластеризации данных?

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

В этих задачах используется понятие меры сходства объектов (расстояние - одна из возможных мер сходства). В социологии часто эта мера сходства является эмпириче­ской, сходство измеряется непосредственно. Например, проводится массовый опрос: сходно ли ваше отношение к двум явлениям политической жизни? или к двум товарам? к двум актерам? к двум цветам? определенным напиткам?

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

Для бинарных данных часто просто вычисляют количество параметров, которые совпадают у объектов. Далее это число делят на общее число параметров и получают меру сходства. Таким образом, построенные меры называют коэффициентами ассоциа­тивности. Описанный выше коэффициент называют простым коэффициентом совстре- чаемосги. Из других коэффициентов популярны коэффициент Жаккара и коэффициент Гауэра [10].

В программе STATISTICA доступны следующие меры сходства объектов: евклидова метрика, квадрат евклидовой метрики, манхэттенское расстояние, или «расстояние го­родских кварталов», метрика Чебышева, метрика Минковского, пирсоновский коэффи­циент корреляции (точнее, 1 - пирсоновский коэффициент корреляции), коэффициент совстречаемости (точнее, 1 - коэффициент совстречаемости).

Итак, программа предлагает несколько мер сходства. Естественно, возникает во­прос: какую из них выбрать? Однозначного ответа не существует. Это можно сделать, только «вжившись» в стоящую перед вами задачу.

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

Некоторые из возможных способов объединения мы опишем ниже.

В программе STATISTICA все эти исследования проводятся в естественной сре­де в диалоговом режиме.

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

Обычно перед началом классификации данные стандартизируются (вычитается среднее и производится деление на корень квадратный из дисперсии). Полученные в ре­зультате стандартизации переменные имеют нулевое среднее и единичную дисперсию. Рассматриваемые нами далее данные уже стандартизованы.

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

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

• метод одиночной связи,

• метод полной связи,

• невзвешенное попарное среднее,

• взвешенное попарное среднее,

• невзвешенный центроидный метод,

• взвешенный центроидный метод,

• метод Варда.

Данные алгоритмы различаются правилами объединения объектов в кластеры.

В методе одиночной связи на первом шаге объединяются два объекта, имеющие ме­жду собой максимальную меру сходства. На следующем шаге к ним присоединяется объект с максимальной мерой сходства с одним из объектов кластера. Таким образом процесс продолжается далее. Итак, для включения объекта в кластер требуется макси­мальное сходство лишь с одним членом кластера. Отсюда и название метода одиночной связи, нужна только одна связь, чтобы присоединить объект к кластеру: связь нового элемента с кластером определяется только по одному из элементов кластера. Недостат­ком этого метода является образование слишком больших «продолговатых» кластеров.

Метод полных связей позволяет устранить указанный недостаток. Здесь мера сход­ства между объектом-кандидатом на включение в кластер и всеми членами кластера не может быть меньше некоторого порогового значения.

В методе средней связи мера сходства между кандидатом и членами кластера ус­редняется, например, берется просто среднее арифметическое мер сходства.

Идея еще одного агломеративного метода - метода Уорда состоит в том, чтобы про­водить объединение, дающее минимальное приращение внутригрупповой суммы квад­ратов отклонений. Замечено, что метод Уорда приводит к образованию кластеров при­мерно равных размеров и имеющих форму гиперсфер.

Рассмотрим еще итеративный метод группировки к средних. Данный метод работа­ет непосредственно с объектами, а не с матрицей сходства.

В методе к средних объект относится к тому классу, расстояние до которого мини­мально. Расстояние понимается как евклидово расстояние, т. е. объекты рассматривают­ся как точки евклидова пространства.

Как определить евклидово расстояние, мы уже знаем. Но как определить расстояние от объекта до совокупности объектов? Оказывается, это можно сделать следующим способом: каждый класс объектов имеет центр тяжести (рассмотрите, как и ранее, про­стейший случай - представьте, что объект имеет только два параметра, тогда его можно изобразить точкой на плоскости, а группа объектов - это просто группа точек).

Расстояние между объектом и классом есть расстояние между объектом и центром класса. «Но как вычислить центр класса?» - спросите вы. Например, взять средние по каждому параметру. Тогда расстояние между объектом и группой объектов вполне оп­ределено и алгоритм может работать.

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

Принципиально метод к средних «работает» таким образом:

1. вначале задается некоторое разбиение данных на кластеры (число кластеров оп­ределяется пользователем); вычисляются центры тяжести кластеров;

2. происходит перемещение точек: каждая точка помещается в ближайший к ней кластер;

3. вычисляются центры тяжести новых кластеров;

4. шаги 2, 3 повторяются, пока не будет найдена стабильная конфигурация (т. е. кла­стеры перестанут изменяться) или число итераций не превысит заданное пользователем.

Итоговая конфигурация и является искомой.

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

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

1. Обзор метода

Стандартным образом, нажав кнопку Открыть папку примеров, откроем окно вы­бора файла (рис. 5.1).

Рис. 5.1. Выбор файла с данными об автомобилях

Выберем в этом окне файл cars.sta. как показано на рисунке, и нажмем кнопку ОК. Файл выбран, вы вернетесь обратно в стартовую панель модуля. В рабочем окне вы ви­дите открытый файл с данными (рис. 5.2).

Рис. 5.2. Файл cars.sta с данными автомобилей разных марок

Всего в файле содержатся данные о 22-х машинах разных марок. Марки машин - это наблюдения. Переменные в этом файле: PRICE - цена автомобиля, ACCELERATION - HANDLING - технические характеристики, MILEAGE - расход горючего (количество миль, пройденных на одном галлоне бензина).

Все характеристики машин уже стандартизированы, например, из значений пере­менной PRICE вычтена средняя цена и разность поделена на корень квадратный из дис­персии.

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

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

Конечно, подобных задач на практике возникает множество: от продажи недвижи­мости до конкурсов красоты!

Если бы машины сравнивались по одному параметру, например, по расходу горюче­го, мы выбрали бы машину с меньшим расходом топлива на одну милю. Все машиныбыли бы упорядочены в одну линию, и задача не представляла бы проблем. Однако па­раметров несколько, и ситуация существенно усложняется. Обратите внимание на отли­чие файла данных cars.sta от рассмотренного в предыдущей главе файла iris.sta. В файле нет зависимой переменной, аналогичной переменной iristype, иными словами, мы про­водим классификацию без обучения. В этом существенное отличие кластерного анализа от дискриминантного анализа

1. Постановка задачи, обзор методов

В верхнем меню рабочего окна STATISTICA щелкнем на пункт Анализ, выберем пункт Многомерный разведочный анализ.

Многомерный разведочный анализ включает большую группу методов для проведе­ния разведочного анализа: факторный анализ, канонический анализ, метод главных ком­понент, многомерное шкалирование, деревья классификации и др. В выпадающем меню выберем Кластерный анализ (рис. 5.3).

Рис. 5.3. Запуск модуля Кластерный анализ

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

В списке методов высветим Кластеризация методом К средних (рис. 5.4) и на­жмем кнопку ОК в правом верхнем углу панели.

Рис. 5.4. Стартовая панель модуля Кластерный анализ

Диалоговое окно метода Кластеризация методом К средних появится на экране

(рис. 5.5).

Рис. 5.5. Диалоговое окно метода К средних

1. Модуль Кластерный анализ - технология, пошаговый

   разбор примера

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

Так как мы будем разбивать машины на группы и учитывать все параметры, то на­жмем вначале кнопку Выбрать все, а затем кнопку ОК.

Посмотрите далее на поле Объекты, находящееся ниже кнопки Переменные. На­жав на стрелку в этом поле, выберем Наблюдения (Строки). Если нужно кластеризиро- вать переменные - Переменные (Столбцы).

Рис. 5.6. Выбор переменных для кластерного анализа

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

В поле Число кластеров нужно определить число групп, на которые мы хотим раз­бить автомобили. Запишем в это поле число 3. Таким образом, мы хотим разбивать ма­шины, представленные в файле, на 3 кластера.

В строке Число итераций задается максимальное число итераций, используемых при построении классов. Задайте, например, число 11.

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

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

Сделайте такие же установки, которые показаны на рис. 5.5.

Упражнение. Как вы думаете, изменятся ли результаты классификации, если выбраны другие опции в группе Начальные центры классов? Проверьте это эксперимен­тально, после того как разберете данный пример.

После того как все установки сделаны, нажмем кнопку ОК в верхнем правом углу окна Кластеризация методом К средних и запустим вычислительную процедуру. Через несколько секунд на экране появится окно результатов (рис. 5.7).

Рис. 5.7. Окно результатов кластеризации машин по методу средних

В верхней части окна представлено: число переменных - 5; число наблюдений - 22; метод кластеризации - k-средних; число кластеров - 3 и количество итераций, после ко­торых найдено решение - 3.

Кнопки в нижней части окна позволяют провести подробный анализ результатов.

Кнопка Средние кластеров и евклидовы расстояния позволяет вывести две таб­лицы, в первой из которых указаны средние для каждого кластера (усреднение произво­дится внутри кластера), во второй таблице указаны евклидовы расстояния и квадраты евклидовых расстояний между кластерами.

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

Кнопка График средних позволяет посмотреть средние значения для каждого кла­стера на линейном графике.

Кнопка Статистики для каждого кластера открывает электронную таблицу с опи­сательными статистиками для каждого кластера (среднее, дисперсия и т. д ).

Кнопка Сохранить классификацию и расстояния позволяет сохранить результаты классификации в файле STATISTICA для дальнейшего исследования.

Нам, конечно, интересно посмотреть, как распределились машины по кластерам. Для этого нажмем кнопку Элементы кластеров и расстояния. На экране появятся таб­лицы с названиями машин, отнесенных к определенным кластерам (рис. 5.8-5.10).

Рис. 5.8. Первый кластер

Рис. 5.9. Второй кластер

Рис. 5.10. Третий кластер

В строках таблиц указано расстояние от каждой машины до центра кластера.

Нажмем на кнопку Средние кластеров и евклидовы расстояния. На экране поя­вится таблица, в которой даны евклидовы расстояния между средними кластеров (по каждому из параметров внутри кластера вычисляется среднее, получается 3 точки в пя­тимерном пространстве, и между ними находится расстояние) (рис. 5.11).

Рис. 5.11. Расстояния между кластерами

Из таблицы видно, что расстояние между первым и вторым кластером 0,969, а между вторым и третьим - 1,876. Над диагональю в таблице даны квадраты расстояний между кластерами.

С помощью кнопки График средних строятся следующие графики средних значе­ний характеристик машин для каждого кластера (рис. 5.12).

График сред них для кажд.

Перемен Кластер 3

Л, О ■ J • J о— Й

Рис. 5.12. График средних для каждого кластера

Закроем окно результатов и вернемся в начальное окно метода к-средних.

Покажем, какие еще возможности для интерактивного анализа предоставляет мо­дуль.

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

Сделайте установки, как показано на рис. 5.13 (теперь выбираем только 3 параметра, характеризующие машины):

Рис. 5.13. Выбор части переменных для кластерного анализа методом К средних

Повторим действия, описанные ранее. Нажмем кнопку График средних, построим графики средних значений характеристик машин для каждого кластера (рис. 5.14).

График средних для кажд. кл.

Перемен. -*Э- Кластер 3

EWSB J ’ J f

Рис. 5.14. График средних для новых кластеров

Заметьте, что состав групп изменился. Теперь машины более отчетливо группиру­ются. Мы пожертвовали размерностью, сократили число параметров и получили более отчетливо выраженные группы (сравните с рис. 5.12).

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

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

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

Рис. 5.15. Результат кластеризации машин методом двувходового объединения

Если вы воспользуетесь Иерархической кластеризации, то сможете увидеть дендрограмму или дерево объединения (рис. 5.16), о котором мы говорили вначале.

Дендрограмма для 22 набл.

Метод одиночной связи Евклидово расстояние

Рис. 5.16. Дерево объединения машин разных марок в кластер методом одиночной связи

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

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

Упражнение. Примените иерархическую классификацию и метод k-средних к данным Фишера iris.sta, сравните полученные результаты с результатами, полученными с помощью дискриминантного анализа.