Практикум по прикладой статистике
.pdf
На основе расстояний между классами объектов вычисляется расстояние между классом Sl и классом S(m,q), являющимся в свою очередь объединением классов Sm и Sq:
pl , m,q p Sl , S m,q plm plq pmq plm plq ,
где α, β, γ, δ – числовые коэффициенты, значения которых определяют специфику кластер-процедуры. Значения коэффициентов приведены в таблице 4.1.
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 4.1 |
|||
Значения числовых коэффициентов |
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Метод |
|
|
|
|
|
|
Параметры |
|
|
|
|
|
|||
|
α |
|
|
|
|
β |
|
|
|
γ |
|
|
δ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
«Ближайшего соседа» |
0,5 |
|
|
|
0,5 |
|
|
|
0 |
|
|
-0,5 |
|
||
«Дальнего соседа» |
0,5 |
|
|
|
0,5 |
|
|
|
0 |
|
|
0,5 |
|
||
Центроидный |
|
nm |
|
|
|
nq |
|
|
nm |
. |
nm |
|
0 |
|
|
|
|
nm n1 |
|
|
|
|
|
|
|
nm n1 |
nm n1 |
|
|
||
|
|
|
|
n |
m |
n |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
Средней связи |
|
nm |
|
|
|
nq |
|
|
|
0 |
|
|
0 |
|
|
|
|
nm n1 |
|
|
nm n1 |
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Для выбора наилучшего способа разбиения совокупности на кластеры вводится понятие критерия качества разбиения.
Критерий качества представляет собой некоторый функционал, соответственно наилучшим считается разбиение, при котором
достигается экстремум функционала. |
|
|
|||
Наиболее |
распространенными |
критериями |
качества |
||
разбиения при заданном числе классов являются: |
|
||||
сумма |
|
|
внутриклассовых |
дисперсий |
|
k |
X i , |
|
l , где S=(S1,S2, |
|
|
Q S d 2 |
X |
… Sk) - |
некоторое |
||
l 1 X i Sl
фиксированное разбиение исходных объектов на заданное k классов;
сумма попарных внутриклассовых расстояний между
k |
X i , X j |
; |
объектами Q S d 2 |
||
l 1 X i , X j Sl |
|
|
|
70 |
|
обобщенная |
внутриклассовая |
дисперсия |
|||
|
k |
ˆ |
|
|
|
Q S det |
nl |
|
|
|
|
l . |
|
|
|||
l 1 |
|
|
|
|
|
Наиболее простым способом оценки (но не сравнения) качества разбиения является проверка статистической гипотезы о равенстве средних значений признаков в отдельных кластерах со средними значениями в целом по всей совокупности объектов. Статистическая значимость отличия групповых средних от общего среднего значения может служить признаком хорошего разбиения.
Приведенные способы оценки качества разбиения совокупности представляют собой формальный подход и являются лишь вспомогательным средством. Основная роль при решении задачи классификации принадлежит возможности содержательной интерпретации результатов кластеризации.
На следующем рисунке 4.4 представлена классификация методов кластерного анализа. Кластер-процедуры подразделяют на два основных типа:
иерархические (деревообразные). Принцип работы иерархических агломеративных (дивизимных) процедур состоит в последовательном объединении (разделении) групп объектов сначала самых близких (далеких), а затем все более отдаленных друг от друга (приближенных);
итеративные: параллельные и последовательные. Процесс классификации начинается с задания некоторых начальных условий (количество образуемых кластеров, порог завершения процесса классификации и т.д.).
В таблице 4.2 представлено описание наиболее распространенных методов иерархического кластерного анализа.
71
72
73
Алгоритм иерархического агломеративного кластерного анализа следующий:
1.Нормирование исходных переменных.
2.Расчет матрицы расстояний между объектами.
3.Объединение пары самых близких объектов (кластеров).
4.Процедуры 2 и 3 повторяются до тех пор, пока все объекты не будут объединены в один кластер или до достижения заданного порога сходства.
Рассмотрим алгоритм иерархического кластерного анализа на примере.
Пример 4.1. Провести классификацию пяти объектов, характеризующихся двумя признаками, с помощью иерархического агломеративного алгоритма. Значения переменных представлены в таблице 4.3.
|
|
Таблица 4.3 |
|
Матрица исходных данных |
|
|
|
|
|
|
|
Номер объекта |
х1 |
х2 |
|
1 |
3 |
0,9 |
|
2 |
2 |
1,5 |
|
3 |
5 |
0,6 |
|
4 |
7 |
0,3 |
|
5 |
4 |
0,8 |
|
Среднее значение x j |
4,20 |
0,82 |
|
Среднее квадратическое отклонение j |
1,72 |
0,40 |
|
Решение.
На первом шаге матрица исходных данных нормируется
методом статистической стандартизации z |
|
|
xij |
x j |
. |
ij |
|
|
|||
|
|
|
j |
||
|
|
|
|
||
Матрица нормированных значений переменных Z принимает
вид:
74
0,70 |
0,20 |
|
|
1,28 |
1,71 |
|
|
|
Z |
0,46 |
0,55 . |
|
1,63 |
1,31 |
|
|
|
|
0,12 |
|
|
0,05 |
|
На втором шаге вычисляется матрица расстояний между объектами. В качестве меры близости принимается обычное евклидово расстояние. Далее определяется расстояние между первым и вторым объектами:
d |
d X , X |
|
|
|
|
0,70 1,28 2 0,20 1,71 2 |
1,62. |
|
|
x k x k 2 |
|||||||
|
|
|
|
2 |
|
|
|
|
12 |
1 |
2 |
|
i |
j |
|
|
|
|
|
|
|
k 1 |
|
|
|
|
Таким образом строится матрица расстояний между отдельными объектами, каждый из которых на первом шаге представляет кластер.
|
|
|
|
|
|
Таблица 4.4 |
|
|
Матрица евклидовых расстояний |
|
|
|
|||
|
|
|
|
|
|
|
|
Номер объекта |
1 |
2 |
3 |
|
4 |
5 |
|
1 |
0,00 |
1,62 |
1,39 |
|
2,77 |
0,63 |
|
2 |
1,62 |
0,00 |
2,86 |
|
4,19 |
2,11 |
|
|
|
|
|
|
|
|
|
3 |
1,39 |
2,86 |
0,00 |
|
1,39 |
0,77 |
|
|
|
|
|
|
|
|
|
4 |
2,77 |
4,19 |
1,39 |
|
0,00 |
2,15 |
|
5 |
0,63 |
2,11 |
0,77 |
|
2,15 |
0,00 |
|
Из матрицы расстояний видно, что первый и пятый объекты находятся наиболее близко друг к другу p1,5 0,63 . Эти объекты
объединяются в один кластер под номером один (присваивается меньший порядковый номер объектов (кластеров)).
Далее определяется расстояние между кластером S(1,5) и вторым объектом по принципу «дальнего соседа»:
p2, 1,5 p S2 , S 1,5 0,5 p2,1 0,5 p2,5 0 p1,5 0,5 p2,1 p2,5
121,62 12 2,11 12 1,62 2,11 2,11.
75
Расстояние между кластером S(1,5) и остальными объектами пересчитывается, получается новая матрица расстояний (табл. 4.50.
|
|
|
|
|
|
Таблица 4.5 |
|
|
Матрица евклидовых расстояний |
|
|
|
|||
|
|
|
|
|
|
|
|
|
Номер кластера |
1 |
2 |
|
3 |
4 |
|
|
|
|
|
|
|
|
|
|
Состав кластера |
(1,5) |
2 |
|
3 |
4 |
|
1 |
(1,5) |
0,00 |
2,11 |
|
1,39 |
2,77 |
|
2 |
2 |
2,11 |
0,00 |
|
2,86 |
4,19 |
|
3 |
3 |
1,39 |
2,86 |
|
0,00 |
1,39 |
|
|
|
|
|
|
|
|
|
4 |
4 |
2,77 |
4,19 |
|
1,39 |
0,00 |
|
На этом шаге объединения самыми близкими объектами являются третий и четвертый p3,4 1,39 . Эти объекты объединяются в новый кластер, которому присваивается номер три.
Заново |
пересчитывается |
матрица |
расстояний |
по |
принципу |
|||||
«дальнего соседа» (табл. 4.6). |
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
Таблица 4.6 |
|
|
|
Матрица евклидовых расстояний |
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
Номер кластера |
|
1 |
|
2 |
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Состав кластера |
|
(1,5) |
|
2 |
|
|
(3,4) |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
(1,5) |
|
0,00 |
|
2,11 |
|
|
2,77 |
|
|
2 |
2 |
|
2,11 |
|
0,00 |
|
|
4,19 |
|
|
3 |
(3,4) |
|
2,77 |
|
4,19 |
|
|
0,00 |
|
|
|
|
|
|
|
|
||||
|
Здесь объединяются первый и второй кластеры, так как |
|||||||||
расстояние между ними минимально |
p1,2 2,11. |
Они |
образуют |
|||||||
новый кластер под номером один. После пересчета расстояний между кластерами по принципу «дальнего соседа» получается следующая матрица (табл. 4.7).
На последнем шаге иерархического агломеративного кластерного анализа все объекты объединяются в один кластер на расстоянии 4,19 (табл. 4.8).
76
Таблица 4.7
Матрица евклидовых расстояний
|
Номер кластера |
1 |
2 |
|
|
|
|
|
Состав кластера |
(1,2,5) |
(3,4) |
1 |
(1,2,5) |
0,00 |
4,19 |
2 |
(3,4) |
4,19 |
0,00 |
|
|
|
|
Таблица 4.8
Схема объединения объектов
|
Расстояние объединения |
|
|
|
Объекты |
|
|
|
|
||||
|
0,63 |
|
1 |
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1,39 |
|
3 |
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2,11 |
|
1 |
|
5 |
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4,19 |
|
1 |
|
5 |
|
2 |
|
|
3 |
|
4 |
|
|
|
|
|
|
|
|
|||||||
На основе представленных в таблице 4.8 данных построено графическое изображение процедуры кластерного анализа – дендрограмма (рис. 4.5).
Метод полных связей Евклидово расстояние
Расстояние объединения
4,5
4,0
3,5
3,0
2,5
2,0
1,5
1,0
0,5
0,0
4 |
3 |
2 |
5 |
1 |
Рис. 4.5. Дендрограмма классификации объектов
77
Наряду с описанными иерархическими процедурами широко используется итеративный метод k-средних. Метод k-средних не требует вычисления матрицы расстояний между объектами. Для начала процедуры классификации достаточно задать k случайно выбранных объектов, которые будут служить центрами кластеров. Далее алгоритм включает в состав кластера новые объекты таким образом, чтобы внутриклассовая дисперсия стремилась к минимуму.
Вычислительная процедура метода следующая:
1.Выбор числа кластеров, на которые должна быть разбита совокупность.
2.Задание первоначального разбиения объектов и определение центров тяжести кластеров.
3.В соответствии с выбранными мерами расстояний определение нового состава каждого кластера.
4.Пересчет центров тяжести кластеров.
5.Процедуры 3 и 4 продолжаются до тех пор, пока следующая итерация не даст такой же состав кластеров, что и предыдущая.
Рассмотрим пример реализации метода k-средних.
Пример 4.2. Даны четыре объекта, характеризующихся двумя признаками. Необходимо разбить объекты на два класса с помощью метода k-средних. Исходные данные представлены в таблице.
|
|
Таблица 4.5 |
|
Матрица исходных данных |
|
|
|
|
|
|
|
Номер объекта |
х1 |
х2 |
|
1 |
4 |
5,9 |
|
2 |
2 |
3,7 |
|
3 |
3 |
1,9 |
|
4 |
0,8 |
2,7 |
|
Среднее значение x j |
2,45 |
3,55 |
|
Среднее квадратическое отклонение j |
1,19 |
1,50 |
|
78 |
|
|
|
Решение:
Нулевая итерация. В качестве эталонов выступают первые два объекта: Е10=(4; 5,9), w10=1 и Е20=(2; 3,7) w20=1.
Первая итерация. Далее рассчитывается расстояние от третьего и четвертого объектов до эталонов. В качестве меры расстояния принята евклидова метрика.
|
2 |
|
|
|
|
|
d13 d Е10 , X 3 |
xi k x jk 2 |
|
4 3 2 |
5,9 1,9 2 |
4,12 ; |
|
|
|
k 1 |
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
d23 d Е20 , X 3 |
|
xi k x jk 2 |
|
2 3 2 |
3,7 1,9 2 |
2,06 . |
|
|
k 1 |
|
|
|
|
Расстояние от третьего объекта до второго эталона меньше, чем до первого эталона, следовательно, объект включается в состав второго эталона. Первый эталон остается без изменений: Е11= Е10,
w11=w10. Второй |
эталон |
|
пересчитывается |
по |
формуле |
||||||||
E21 |
w |
E |
20 |
X |
3 |
|
2 3 |
|
3,7 1,9 |
2,5; 2,8 , |
|
|
|
20 |
|
|
|
|
; |
|
|
вес |
эталона |
||||
|
|
w20 1 |
|
|
2 |
|
2 |
|
|
|
|||
приравнивается к величине w21=w20+1=1+1=2.
Вторая итерация. Определяется расстояние от четвертого объекта до эталонов, затем объект присоединяется к тому эталону, к которому он ближе всего расположен:
|
d14 d Е11, X 4 |
|
|
|
|
|
|
||||||||
|
|
4 0,8 2 5,9 2,7 2 |
4,53; |
||||||||||||
|
d24 d Е21, X 4 |
|
|
|
|
|
1,70 . |
||||||||
|
|
|
2,5 0,8 2 |
2,8 2,7 2 |
|||||||||||
Четвертый объект присоединяется ко второму эталону и |
|||||||||||||||
эталон пересчитывается: |
|
|
|
|
|
|
|
|
|||||||
|
|
w |
E |
21 |
X |
4 |
|
2 2,5 0,8 |
|
2 2,8 2,7 |
|||||
E22 |
21 |
|
|
|
|
|
|
; |
|
|
1,93; 2,77 , |
||||
|
|
w21 1 |
|
|
|
2 1 |
2 1 |
|
|||||||
|
|
|
|
|
|
|
|
|
|
||||||
w22=w21+1=2+1=3.
Первый эталон остается без изменений: Е12= Е11, w12=w11. После того как рассмотрены все объекты, кроме объектов
принятых за эталон на нулевом шаге, начинается новый цикл, т.е. по тому же правилу осуществляется расчет расстояния и присоединение к ближайшему эталону каждого из четырех
79