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


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

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


Пусть имеется матрица расстоянии между объектами и некоторое их разбиение на кластеров. Основным понятием кластер-процедур является расстояние между кластерами и . Программой «Cluster Analysis» пакета «STATISTICA» предусмотрены следующие виды расстояний:

расстояние, измеряемое по принципу «ближнего соседа»,

(21)

Метод, использующий это расстояние, получил в отечественной литературе название метода «ближнего соседа», а в зарубежной — метода «одиночной связи» — «Single linkage»*);

расстояние, измеряемое по принципу «дальнего соседа», (метод «дальнего соседа», или «полных связей» — «Complete linkage»*))

; (22)

расстояние по принципу «средней связи» (метод «средней связи» — «Pair group average»)

; (23)

где и — числа объектов в кластерах и ;

расстояние, измеряемое между «центрами тяжести» кластеров («центроидный метод»),

(24)

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

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

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


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

(25)

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



Метод










Ближний сосед (Одиночной связи)
0.5
0.5
0
-0.5
(26)

Дальний сосед (Полных связей)
0.5
0.5
0
0.5
(27)

Средней связи




0
0
(28)

Центроидный






0
(29)


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

Проиллюстрируем методы на примере классификации пяти точек: (1,2), (4,3), (-1, — 1), (-1,0), (-3,3):

(5)                                            (2) (1)
(4)
(3)

Рис. 1

За метрику расстояний примем квадратичное евклидово расстояний. Матрица расстояний:
1
2
3
4
5

1
0
10
13
8
17

2
10
0
41
34
49

3
13
41
0
1
20

4
8
34
1
0
13

5
17
49
20
13
0


Начальное разбиение: 1, 2, 3, 4, 5. Минимальное расстояние , переходим к разбиению: 1, 2, , 5.


Ближний сосед
1
2


5







2
5







5

1
0
10
8
17


0
10
13


0
13

2
10
0
34
49
2
10
0
49



13
0



8
34
0
13
5
13



0



5
17
49
13
0




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

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


4









5









1
0
10
13
17


0
41
49


0
49

2
10
0
41
49


41
0
20


49
0



13
41
0
20
5
49
20
0



5
17
49
20
0




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

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

Средняя связь
1
2


5









5









1
0
10
10.5
17


0
24
33


0
27

2
10
0
37.5
49


24
0
16.5


27
0



10.5
37.5
0
16.5
5
33
16.5
0



5
17
49
16.5
0




В последней таблице .

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


5









5









1
0
10
10.25
17


0
21.25
30.5


0


2
10
0
37.25
49


21.25
0
16.25




0



10.25
37.25
0
16.25
5
30.5
16.25
0



5
17
49
16.25
0







Дадим пояснение к расчетам некоторых расстояний. Расчеты проведем по тождественным формулам (29):





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

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

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
    Главная страница
Сочинения
Лекции
Рассказы
Справочники
Уроки
Доклады
Рефераты
Курсовые работы
Документы