Учебное пособие для студентов всех специальностей Москва 2003 ббк 22. 17я7 удк 519. 22 (075. 8) 6Н1 к 60



страница8/10
Дата08.10.2012
Размер0.71 Mb.
ТипУчебное пособие
1   2   3   4   5   6   7   8   9   10

3.1.4Параллельные кластер-процедуры.
Методы, связанные с функционалами качества разбиения


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

Замечание. В рассмотренных выше иерархических методах реализованы схемы объединения объектов на основе эвристических соображений. Однако, например, для методов «ближнего соседа» и «дальнего соседа» можно указать функционалы качества разбиения .

«Ближний сосед»: (30)

«Дальний сосед»: (31)

Докажем, что (30) соответствует расстоянию (21). Обозначим качество разбиения , полученного из после объединения в нем кластеров и ; тогда

Поскольку для начального разбиения качество , то величиной (21) определяется качество нового разбиения с точки зрения критерия (30), что и требовалось доказать.

gif" align=left hspace=12>


l l l l l (r)
49
373/18

27

20,6

20

16,5 16,25
13

10 10 10 10 10,22 (0,17)

8

4,12 (0,33)

1 1 1 1 1 (0,95)
3 4 1 2 5 3 4 1 2 5 3 4 1 2 5 3 4 1 2 5 3 4 1 5 2

а) б) в) г) д)
Рис. 2
Наиболее распространенными являются при заданном числе кластеров следующие функционалы качества разбиения:

  • сумма внутриклассовых дисперсий

, (32)

  • сумма попарных внутриклассовых расстояний

, (33)

а при неизвестном числе кластеров функционалы:



или



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

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

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

Пусть некоторое разбиение совокупности элементов с матрицей связи , а некоторое пороговое значение связи. Связь кластеров и определяем так:

(34)

а критерий оптимальности разбиения

(35)

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

  1. , максимизируя сумму связей между элементами внутри образующих его кластеров, минимизирует сумму связей между элементами разных кластеров:

(36)

  1. Средняя связь между элементами, образующими кластер разбиение не меньше средней связи элементов этого кластера с элементами любого другого кластера разбиения :

(37)

  1. Средняя связь между элементами, образующими кластер разбиения не меньше средней связи этих элементов с элементами, не вошедшими в :

(38)

Каков смысл порога ? Проведя тождественные преобразования (35), получим



т. е. максимизация достигает за счет максимизации суммы связей внутри кластеров (без учета порога ) и минимизации (при условии ). Но минимум достигается при , т. е. при равномерном распределении элементов по кластерам. Поэтому порог это вес требования равномерности распределения элементов по кластерам в сравнении с требованием максимизации суммы связей внутри кластеров.

Алгоритм «объединение» является субоптимальным алгоритмом, использующим необходимое условие оптимальности разбиения по критерию (35): для оптимального разбиения

(39)

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





1

2

3

4

5






1

2

3

4

5

1

1

0.67

0.61

0.72

0.55

1

0

0.17

0.11

0.22

0.05

2

0.67

1

0.33

0.38

0.30

2

0.17

0

-0.17

-.012

-0.20

3

0.61

0.33

1

0.95

0.51

3

0.11

-0.17

0

0.45

0.01

4

0.72

0.38

0.95

1

0.61

4

0.22

-0.12

0.45

0

0.11

5

0.55

0.30

0.51

0.61

1

5

0.05

-0.20

0.01

0.11

0










1

2



5








2

5

1

0

0.17

0.33

0.05



1.56

-0.12

0.17

2

0.17

0

-0.29

-0.20

2

-0.12

0

-0.20



0.33

-0.29

0.9

0.12

5

0.17

-0.20

0

5

0.05

-0.20

0.12

0
















2



1.9

-0.32

2

-0.32

0


Последовательность разбиений: 1, 2, 3, 4, 51, 2, 34, 5 12345, 2 (см. рис 2. д).

Рассмотрим задачу оптимизации структуры некоторой производственной системы. Пусть имеется элементарных систем. Требуется найти такое разбиение , которое минимизировано бы сумму затрат на управление внутри кластеров (они пропорциональны количеству «внутренних связей») и затрат на управление «внешними» связями (они пропорциональны объему «внешних связей», равному ):

(40)

Но так как , а , где уменьшаемое — не зависящая от разбиения величина, то критерий (40) равносилен критерию:

идентичному (35) при

3.1.5Последовательные кластер-процедуры. Метод K-средних


Иерархические и параллельные кластер-процедуры практически реализуемы лишь в задачах классификации не более нескольких десятков наблюдений. К решению задач с большим числом наблюдений применяют последовательные кластер-процедуры - это итерационные алгоритмы, на каждом шаге которых используется одно наблюдение (или небольшая часть исходных наблюдений) и результаты разбиения на предыдущем шаге. Идею этих процедур поясним на представленном в ППП «STASTICA» методе среднихK-Means Clustering») с заранее заданным числом классов.

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

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

Программой «K-Means Clustering» предусмотрена возможность вывода на печать результатов дисперсионного анализа (Analysis of Variance) полученного разбиения по каждому признаку: межклассовой и внутриклассовой вариации, числа степеней свободы, F-статистики и рассчитанного уровня значимости при проверке гипотезы о равенстве межклассовой и внутриклассовой дисперсий.

3.1.6Реализация методов кластерного анализа
в пакете SPSS

3.1.7Примеры решения задач

3.1.7.1Кластерный анализ: простой пример




3.1.7.2Кластерный анализ мировой демографической статистики




3.1.7.3Кластерный анализ финансовых показателей




3.1.7.4Кластерный анализ результатов аттестации персонала компании



1   2   3   4   5   6   7   8   9   10

Похожие:

Учебное пособие для студентов всех специальностей Москва 2003 ббк 22. 17я7 удк 519. 22 (075. 8) 6Н1 к 60 iconКонспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32
Учебное пособие предназначено для студентов факультета Кибернетики, изучающих на пятом семестре математическую лингвистику и основы...
Учебное пособие для студентов всех специальностей Москва 2003 ббк 22. 17я7 удк 519. 22 (075. 8) 6Н1 к 60 iconУчебное пособие для студентов всех специальностей Саратов 2009 удк 519. 17 Ббк 22. 174 С 32 Рецензенты
С32 Ведение в теорию графов: учеб пособие. Саратов: Сарат гос техн ун-т, 2009. 36с
Учебное пособие для студентов всех специальностей Москва 2003 ббк 22. 17я7 удк 519. 22 (075. 8) 6Н1 к 60 iconУчебное пособие Москва 2002 ббк 63. 3 /2/ я 73 Рецензент: Иванова А. А
Учебное пособие предназначено для студентов I курса всех направлений и всех специальностей дневной формы обучения
Учебное пособие для студентов всех специальностей Москва 2003 ббк 22. 17я7 удк 519. 22 (075. 8) 6Н1 к 60 iconУчебное пособие Москва, 2009 удк 811. 111 Ббк 81. 2Англ к 893 к 893
Учебное пособие предназначено для студентов продвинутого этапа обучения гуманитарных специальностей. Пособие базируется на оригинальном...
Учебное пособие для студентов всех специальностей Москва 2003 ббк 22. 17я7 удк 519. 22 (075. 8) 6Н1 к 60 iconУчебное пособие для студентов гумманитарных специальностей Павлодар удк 811. 124 (075. 8) Ббк 81. 2 Латиня 75 И87
Г. Х демисинова кандидат филологических наук, доцент, зав кафедрой теории и практики перевода пгу
Учебное пособие для студентов всех специальностей Москва 2003 ббк 22. 17я7 удк 519. 22 (075. 8) 6Н1 к 60 iconУчебное пособие Москва 2006 удк 341. 645: 347. 922(075) ббк 67. 412. 2 О 23

Учебное пособие для студентов всех специальностей Москва 2003 ббк 22. 17я7 удк 519. 22 (075. 8) 6Н1 к 60 iconУчебное пособие для студентов всех специальностей Саратов 2011 удк 510. 6 Ббк 22. 12 С 32 Рецензенты
С 32 Элементарный курс математической логики. Логические функции: учеб пособие. Саратов: Сарат гос техн ун-т, 2011. 32 с
Учебное пособие для студентов всех специальностей Москва 2003 ббк 22. 17я7 удк 519. 22 (075. 8) 6Н1 к 60 iconУчебное пособие Оренбург, 2007 удк 811. 131. 1(075) ббк 81. 2Фр-923 а 23 Рецензенты
Данное учебное пособие предназначено для студентов, занимающихся изучением древних языков и античной культуры и имеет целью помочь...
Учебное пособие для студентов всех специальностей Москва 2003 ббк 22. 17я7 удк 519. 22 (075. 8) 6Н1 к 60 iconУчебное пособие для самостоятельной работы обучающихся Сызрань 2007 Составители: П. П. Гавриш, Ю. А. Мелешкин удк 621. 375 Ббк 32. 85
Учебное пособие предназначено для обучающихся всех специальностей, изучающих теорию электрических цепей
Учебное пособие для студентов всех специальностей Москва 2003 ббк 22. 17я7 удк 519. 22 (075. 8) 6Н1 к 60 iconУчебное пособие для студентов всех специальностей ч луганск 2003 удк 01 Рябова С. В. Основы информационного поиска: Учеб пособие для студ всех специальностей. Ч /С. В. Рябова. Луганск: Изд-во вну им. В. Даля, 2003. 44с
Рябова С. В. Основы информационного поиска: Учеб пособие для студ всех специальностей. Ч /С. В. Рябова.– Луганск: Изд-во вну им....
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org