ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение

высшего профессионального образования

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

 
 
 
 
 
 
 
 
 
 
 

Методы  построения типологических групп

(основные  понятия кластерного анализа) 
 
 

 
 
 
 
 
 
 
 
 
 
 
 
 
 

ТОМСК – 2010 

Оглавление

Введение……………………………………………………………………………………….3 

1. Основные типы задач кластер-анализа и основные типы кластер-процедур…………..4 

2. Методы кластерного анализа………………………………………………………………5 

3. Меры близости и расстояния между объектами………………………………………….7 

4. Расстояния между классами объектов…………………………………………………….9 

5. Пример……………………………………………………………………………………….10 

Заключение…………………………………………………………………………………….18 

Список литературы……………………………………………………………………………19  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение 

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

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

    Первые публикации по кластерному анализу появились в конце 30-х годов.   Термин кластерный анализ, впервые введенный Трионом (Tryon) в 1939 году, включает в себя более 100 различных алгоритмов. Но активное развитие этих методов и их широкое использование началось в конце 60-х – 70-х годов. В дальнейшем это направление многомерного анализа очень интенсивно развивалось.

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

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

           Пункты 1-4 носят реферативный характер  и в них рассмотрены основные типы задач и иерархический метод кластерного анализа, а так же меры близости и расстояния между объектами. В пункте 5 рассмотрен пример.

   

  

    
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

1. Основные типы задач кластер-анализа и основные типы кластер-процедур

 

     Кластерный анализ – это совокупность методов, позволяющих классифицировать многомерные наблюдения, каждое из которых описывается набором исходных переменных Х₁, Х₂,…, Х_m (m – количество наблюдаемых переменных)_. Целью кластерного анализа является образование групп схожих между собой объектов, которые принято называть кластерами. Слово кластер английского происхождения (cluster), переводится как сгусток, пучок, группа. Родственные понятия, используемые в литературе, - класс, таксон, сгущение.

     Прежде всего целесообразно подразделение всех задач кластер-анализа на два основных типа: Б1 и Б2 в зависимости от объема n совокупности классифицируемых наблюдений Х₁, Х₂,…,Х_n.

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

      К типу Б2 будем относить задачи классификации достаточно больших массивов многомерных наблюдений (n – порядка нескольких сотен и тысяч; классификация индивидуумов, семей, изделий, некоторых промышленных и технических микрообъектов). Подобное разделение задач классификации на два типа и условно, но весьма необходимо, и в первую очередь с точки зрения принципиального различия идей и методов, на основании которых конструируются кластер-процедуры в том и в другом случае. Например, для задач типа Б2 целесообразно построение процедур последовательного типа, обладающих достаточно хорошими, хотя бы асимптотическими по n, свойствами.

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

(а) число  классов априорий задано;

(б) число  классов неизвестно и подлежит  определению (оценке);

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

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

• Процедуры иерархические. Предназначены в основном для решения задач типа (в). Что касается объема классифицируемой совокупности, то формально иерархические процедуры применимы и для задач Б1, и для задач Б2. Однако поскольку эти процедуры основаны на переборе элементов матрицы расстояний (или матрицы соответствующих мер близости), то конструктивно реализуемыми их можно признать лишь  в пределах задач типа Б1. Следует отметить, что иерархические процедуры применяют иногда и для решения задач типов Б1, (а) и Б2, (б);
• Процедуры параллельные. Предназначены для решения задач типов Б1, (а) и Б1, (б). Они реализуются с помощью итерационных алгоритмов, на каждом шаге которых одновременно (параллельно)  используются все имеющиеся наблюдения;
• Процедуры последовательные. Предназначены в основном для решения задач типов Б2, (а) и Б2, (б). Они реализуются с помощью итерационных алгоритмов, на каждом шаге которых используется лишь небольшая часть, например одно из исходных наблюдений, а так же результат разбиения на предыдущем шаге.

                          

2. Методы кластерного анализа

    

   Методы кластерного анализа можно разделить на две группы:

- иерархические;

- неиерархические. 

   Каждая из групп включает множество подходов и алгоритмов.

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

   Рассмотрим иерархические методы  подробно.

   Иерархические методы кластерного анализа

   Суть иерархической кластеризации  состоит в последовательном объединении  меньших кластеров в большие  или разделении больших кластеров  на меньшие.

   Иерархические агломеративные методы

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

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

   Иерархические дивизимные (делимые) методы

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

   Принцип работы описанных выше  групп методов в виде дендрограммы  показан на рис. 1. 

 

Рис. 1.  Дендрограмма агломеративных и дивизимных методов

  

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

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

   Преимуществом иерархических методов  кластеризации является их наглядность.

   Иерархические алгоритмы связаны с построением дендрограмм (от греческого dendron - "дерево"), которые являются результатом иерархического кластерного анализа. Дендрограмма описывает близость отдельных точек и кластеров друг к другу, представляет в графическом виде последовательность объединения (разделения) кластеров.

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

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

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

   Существует много способов построения  дендрограмм. В дендрограмме объекты могут располагаться вертикально или горизонтально. Пример вертикальной дендрограммы приведен на рис. 2. 

 

Рис. 2.  Пример дендрограммы

   

   Числа 11, 10, 3 и т.д. соответствуют номерам объектов или наблюдений исходной выборки. Мы видим, что на первом шаге каждое наблюдение представляет один кластер (вертикальная линия), на втором шаге наблюдаем объединение таких наблюдений: 11 и 10; 3, 4 и 5; 8 и 9; 2 и 6. На втором шаге продолжается объединение в кластеры: наблюдения 11, 10, 3, 4, 5 и 7, 8, 9. Данный процесс продолжается до тех пор, пока все наблюдения не объединятся в один кластер. 

3. Меры близости и расстояния между объектами

  

     Для проведения классификации необходимо ввести понятие сходства или однородности объектов по наблюдаемым переменным. В каждый кластер (класс, таксон) должны попасть объекты, имеющие сходные характеристики.

     В общем случае понятие однородности объектов определяется заданием правила вычисления , характеризующей либо расстояние d(O_i, O_j) между объектами О_i и O_j из исследуемой совокупности O(i, j=1,2,…,n), либо степень близости (сходства) r(O_i, O_j) тех же объектов. В кластерном анализе для количественной оценки сходства вводится понятие метрики. Сходство или различие между классифицируемыми объектами устанавливается в зависимости от метрического расстояния между ними. Если задана функция d(O_i, O_j), то близкие в смысле этой метрики объекты считаются однородными, принадлежащими к одному классу. Естественно, при этом необходимо сопоставление d(O_i, O_j) с некоторым пороговым значением, определяемым в каждом конкретном случае по-своему.