Автор работы: Пользователь скрыл имя, 07 Мая 2015 в 14:15, реферат
При анализе и прогнозировании социально-экономических явлений исследователь довольно часто сталкивается с многомерностью их описания.
Это происходит при решении задачи сегментирования рынка, построении типологии стран по достаточно большому числу показателей, прогнозирования конъюнктуры рынка отдельных товаров, изучении и прогнозировании экономической депрессии и многих других проблем.
Введение 2
1. Понятие кластерного анализа 3
1.2. Кластерный анализ с примерами на R 4
2. Алгоритмы кластерного анализа 6
2.1. Межгрупповые связи (Between-groups linkage) 9
Заключение 11
Список используемой литературы 12
Содержание
При анализе и прогнозировании социально-экономических явлений исследователь довольно часто сталкивается с многомерностью их описания.
Это происходит при решении задачи сегментирования рынка, построении типологии стран по достаточно большому числу показателей, прогнозирования конъюнктуры рынка отдельных товаров, изучении и прогнозировании экономической депрессии и многих других проблем.
Методы многомерного анализа - наиболее действенный количественный инструмент исследования социально-экономических процессов, описываемых большим числом характеристик. К ним относятся кластерный анализ, таксономия, распознавание образов, факторный анализ.
Кластерный анализ наиболее ярко отражает черты многомерного анализа в классификации, факторный анализ – в исследовании связи.
Иногда подход кластерного анализа называют в литературе численной таксономией, численной классификацией, распознаванием с самообучением и т.д.
Кластерный анализ – это совокупность методов, позволяющих классифицировать многомерные наблюдения. Термин кластерный анализ, впервые введенный Трионом (Tryon) в 1939 году, включает в себя более 100 различных алгоритмов.
КЛАСТЕР — Класс родственных элементов статистической совокупности.
В результате кластерного анализа при помощи предварительно заданных переменных формируются группы наблюдений — отдельные личности (респонденты) или любые другие объекты. Члены одной группы (одного кластера) должны обладать схожими проявлениями переменных, а члены разных групп различными.
Наряду с кластеризацией наблюдений в SPSS предусмотрена кластеризация переменных. Здесь на основе заданных наблюдений образовываются группы переменных.
Задачи кластерного анализа можно объединить в следующие группы:
1. Разработка типологии или
2. Исследование полезных
3. Представление гипотез на
4. Проверка гипотез или
Как правило, при практическом использовании кластерного анализа одновременно решается несколько из указанных задач.
Рассмотрим кластерный анализ на примере. У каждого элемента данных есть набор характеристик (например, если речь идет о людях: возраст, пол, образование и т.п.).
Задача кластерного анализа состоит в том, чтобы разбить объекты на группы (кластеры) так чтобы объекты в каждой группе были некоторым образом похожи. Тем самым раскрывается внутренняя структура данных. При этом, нам не требуются тренировочные данные.
Рассмотрим, к примеру, набор данных:
Имя |
Возраст |
Город |
Доход |
Петя |
25 |
Москва |
120000 |
Вася |
34 |
Киров |
45000 |
Маша |
27 |
Самара |
15000 |
Света |
36 |
Нью-Йорк |
150000 |
Катя |
24 |
Москва |
30000 |
Каким образом можно разбить эти данные на кластеры?
Можно по зарплате:
Можно по возрасту:
Можно еще разбить по месту жительства или полу.
Всякий раз результат будет получаться разный. Какой результат лучше? Ответить можно только зная задачу, для чего именно проводится анализ. Данные сами по себе никак не определяют возможные группировки. Чтобы получить однозначный результат нам необходимо ввести понятие расстояния. Причем, мы можем использовать сразу несколько характеристик объектов для определения расстояния между ними, например зарплату, возраст и пол.
Существуют различные меры расстояний, но для нас интуитивно понятным является классическое Евклидово. Важно лишь правильно нормализовать данные. Как в нашем примере: зарплаты измеряются в тысячах, а возраст в годах. Непосредственно сравнивать эти две величины нельзя. А вот если предварительно привести их к диапазону от 0 до 1 то они станут вполне сравнимыми.
Таким образом, кластерный анализ, в первую очередь состоит из работы над данными. Требуется выбрать интересующие нас характеристики, нормализовать их и выбрать подходящую меру расстояний. И только после этого можно переходить к алгоритмам кластерного анализа.
Известно множество алгоритмов кластерного анализа. Далеко не полная и не единственная возможная классификация представлена на рисунке ниже.
Итак, первым делом, все алгоритмы кластерного анализа делятся на две группы: иерархические и неиерархические. Первые строят не просто разбиение на классы, а иерархию разбиений. Результатом их работы, как правило, является дендрограмма, на основе которой, пользователь может сам выбрать желаемое разбиение. Неиерархические алгоритмы, напротив, в результате работы выдают некоторое конкретное разбиение и имеют ряд параметров, позволяющих настраивать алгоритм для имеющихся данных. Естественно, вторые работают быстрее, чем первые.
Все методы кластеризации работают с данными в виде векторов в многомерном пространстве. Каждый вектор определяется значениями нескольких направлений, а направления и есть известные нам характеристики (пол, возраст, образование). Характеристики могут быть как количественные, так и качественные и искусство специалиста по data mining состоит в том, чтобы правильно отобрать и нормализовать эти характеристики, а потом выбрать подходящую меру расстояний. И только после этого в игру вступают алгоритмы кластеризации.
К числу наиболее популярных, неиерархических алгоритмов относится алгоритм k-средних. Он особенно популярен в силу простоты реализации и скорости работы.
Главным его недостатком является сходимость к локальному минимуму и зависимость результата от начального распределения. Кроме того, требуется заранее знать предполагаемое число кластеров k.
Итак, сам алгоритм:
1) Выбрать
k случайных центров в
2) Приписать
каждый объект из множества
исходных данных кластеру
3) Пересчитать центры кластеров используя полученное распределение объектов
4) Если алгоритм не сошелся, то перейти к п. 2.
Типичные критерии схождения алгоритма это либо среднеквадратичная
ошибка, либо отсутствие перемещений объектов из кластера в кластер.
Существует множество вариаций этого алгоритма, некоторые из них пытаются выбирать наилучшее начальное распределение, другие позволяют кластерам разбиваться на части и объединяться.
По своему подходу, все алгоритмы иерархической кластеризации делятся на два типа: сверху-вниз и снизу-вверх. Первые начинают с одного большого кластера состоящего из всех элементов, а за тем, шаг за шагом разбивают его на все более и более мелкие кластеры. Вторые, напротив, начинают с отдельных элементов постепенно объединяя их в более и более крупные кластеры.
Для пользователя, принципиальной разницы между этими двумя подходами нет, куда более значимо то, каким способом алгоритм пользуется для вычисления расстояний между кластерами. По этому признаку иерархические алгоритмы делятся на алгоритмы с одиночной связью и с полной связью (существуют и другие подходы, но они менее популярны). В алгоритмах с одиночной связью расстоянием между двумя кластерами считается минимальное расстояние между всеми парами элементов из этих двух кластеров. В алгоритмах с полной связью расстоянием считается максимальное расстояние между всеми парами элементов из двух кластеров.
Алгоритмы основанные на теории графов
На практике, в чистом виде, применяются редко, т.к. их вычислительная сложность не позволяет обрабатывать большие графы. Чаще используются в сочетании с другими алгоритмами, такими как k-средних.
Классический пример, это алгоритм минимального покрывающего дерева. Идея состоит в том, чтобы представить весь набор данных в виде графа, вершины которого это наши элементы данных, а вес каждого ребра равен расстоянию между соответствующими элементами.
Тогда, мы можем построить минимальное покрывающее дерево на данном графе, а затем последовательно удалять ребра с наибольшим весом.
Кластером считается множество элементов, соединенных "остатком" дерева. С каждым убранным ребром, количество кластеров увеличивается.
Этот подход очень популярен в области распознавания изображений. Идея такая: предположим, что каждый кластер в наших данных, подчиняется некоторому распределению, как правило предполагается Гаусовское распределение. Далее, методами статистики, мы определяем параметры допустимых распределений и их центры.
Методы объединения (кластеризации)
SPSS предлагает, в общей сложности, 7 методов объединения. Из них метод Межгрупповые связи (Between-groups linkage) устанавливается по умолчанию.
Дистанция между кластерами равна среднему значению дистанций между всеми возможными парами наблюдений, причём один наблюдения берётся из одного кластера, а другой из другого. Информация, необходимая для расчёта дистанции, находится на основании всех теоретически возможных пар наблюдений. По этой причине данный метод и устанавливается по умолчанию.
Это вариант связи между группами, а именно, здесь дистанция между двумя кластерами рассчитывается на основании всех возможных пар наблюдений, принадлежащих обоим кластеров, причём учитываются также и пары наблюдений, образующиеся внутри кластеров.
Дистанция между двумя кластерами определяется, как расстояние между парой значений наблюдений, расположенных друг к другу ближе всего, причём каждое наблюдение берётся из своего кластера.
Дистанция между двумя кластерами определяется как расстояние между самыми удалёнными друг от друга значениями наблюдений, причём каждое наблюдение берётся из своего кластера.
В обоих кластерах рассчитываются средние значения переменных относящихся к ним наблюдений. Затем расстояние между двумя кластерами рассчитывается как дистанция между двумя осредненными наблюдениями.
Этот метод похож на центроидную кластеризацию. Однако в предидущем методе центроид нового кластера получается как взвешенное среднее центроидов обоих исходных кластеров, причём количества наблюдений исходных кластеров образовывают весовой коэффициент. В медианном же методе оба исходных кластера берутся с одинаковым весом.
Сначала в обоих кластерах для всех имеющихся наблюдений производится расчёт средних значений отдельных переменных. Затем вычисляются квадраты евклидовых расстояний от отдельных наблюдений каждого кластера до этого кластерного среднего значения. Эти дистанции суммируются. Потом в один новый кластер объединяются те кластера, при объединении которых получается наименьший прирост общей суммы дистанций.
Так как некоторые из предлагаемых методов имеют явные недостатки (Близлежащий сосед, Дальний сосед), а другие очень мало наглядны и плохо поддаются последующему анализу, рекомендуется применять устанавливаемый по умолчанию и наиболее понятный метод Between-groups linkage (Межгрупповые связи).
Большое достоинство кластерного анализа в том, что он позволяет производить разбиение объектов не по одному параметру, а по целому набору признаков. Кроме того, кластерный анализ в отличие от большинства математико-статистических методов не накладывает никаких ограничений на вид рассматриваемых объектов, и позволяет рассматривать множество исходных данных практически произвольной природы. Это имеет большое значение, например, для прогнозирования конъюнктуры, когда показатели имеют разнообразный вид, затрудняющий применение традиционных эконометрических подходов.