Рис. 2
Воспользуемся агломеративным иерархическим алгоритмом классификации. В качестве расстояния между объектами примем обычное евклидово расстояние. Тогда согласно (1) расстояние между объектами 1 и 2 равно 
,
а между объектами 1 и 3 -
,
очевидно, что 
Аналогично находим расстояния между всеми шестью объектами и строим матрицу расстояний
Из матрицы расстояний следует, что объекты 4 и 5 наиболее близки d4,5=l,00 и поэтому по методу «ближайшего соседа» объединяются в один кластер.
После объединения имеем пять кластеров
Номер кластера | 1 | 2 | 3 | 4 | 5 |
Состав кластера | (1) | (2) | (3) | (4,5) | (6) |
Расстояние между кластерами будем находить по принципу "ближайшего соседа", воспользовавшись формулой пересчета (15). Так, расстояние между объектом S1 и кластером S(4,5) равно 5.10
Мы видим, что расстояние ρ 1, (4,5) равно расстоянию от объекта 1 до ближайшего к нему объекта, входящего в кластер S(4,5), т. е. ρ 1,(45) = ρ 1,4 =5,10- Тогда матрица расстояний равна
Объединим объекты 2 и 3, имеющие наименьшее расстояние ρ2.3 =1,41. После объединения имеем четыре кластера: S(i), S(2,3), S(4,5), S(6).
Вновь найдем матрицу расстояний. Для этого необходимо рассчитать расстояние до кластера s(2,3)- Для этого воспользуемся матрицей расстояний D2. Например, расстояние между кластерами s(4,5) и S(2,3) равно:
Проведя аналогичные расчеты, получим
Объединим кластеры S(4,5) и S(6), расстояние между которыми согласно матрице D3 наименьшее.
В результате этого получим три кластера Si, S(2,3) И S(4,5,6)-
Матрица расстояний будет иметь вид
Объединим теперь кластеры S1 и S23, расстояние между которыми равно 2,24. В результате получим два кластера: S(i,2,3) S(4,5,6), расстояние между которыми, найденное по принципу "ближайшего соседа", равно 5
Результаты иерархической классификации объектов представлены на рис. 3 в виде дендрограммы.
Рис. 3. Дендрограмма
Слева на рисунке приводится расстояние между объединяемыми на данном этапе кластерами (объектами).
В задаче предпочтение следует отдать предпоследнему этапу классификации, когда все объекты объединены в два кластера
S(l,2,3) и S(4,5,6), что наглядно видно на рис. 2 и 3.
Задача №7
Пусть имеются шесть объектов, которые необходимо разбить на три класса (кластера) при помощи метода k-средних. Каждый из объектов описывается тремя переменными Х1, Х2 X3. Исходные значения этих переменных представлены в таблице
Исходные данные
Номер объекта | X1 | X2 | X3 |
1 | 0,10 | 10 | 5,0 |
2 | 0,80 | 14 | 2,0 |
3 | 0,40 | 12 | 3,0 |
4 | 0,18 | 11 | 4,0 |
5 | 0,25 | 13 | 3,2 |
6 | 0,67 | 15 | 2,4 |
В качестве эталонов возьмем первые три объекта (k = 3). Согласно выбранному правилу классификации запишем исходные значения эталонов и весов:
— нулевая итерация.
На первом шаге берем четвертый объект и определяем его расстояние до каждого из эталонов по евклидовой метрике:
d41 =1,416, d42 =3,222, d43 = =1,431.
Следовательно, рассматриваемый объект должен быть присоединен к первому эталону и первый эталон будет пересчитан, а второй и третий не меняются:
где Х4 — вектор значений переменных для четвертого объекта, Е\ — пересчитанное значение эталона;
На втором шаге проверяем, к какому эталону ближе всего находится пятый объект:
d5l =2.820, d52=1.656, d53=1.031
П ятый объект присоединяется к третьему эталону, этот эталон пересчитывается и вес его увеличивается:
На третьем шаге все рассуждения повторяем для шестого объекта:
d61 =4,994, d62=1.085, d63=2.619
Пересчитываем второй эталон и его вес:
После того как просмотрены все объекты, кроме первых трех, процесс «зацикливается», т. е. по тому же правилу осуществляются просмотр и присоединение к соответствующему эталону каждого из шести объектов. При этом происходит пересчет эталонов и продолжается наращивание их весов. Результаты расчетов, начиная с четвертой итерации, представлены в таблице.
Итак, на этом процесс завершается, так как последующее разбиение (интерации 16—21) дали такой же результат, как и предыдущее разбиение (итерации 10—15).
Образованы три кластера: S1 {1}, S2{2, 6}, S3 {3, 4, 5}. Вычисляем центры тяжести полученных кластеров, причем в общем случае эти центры не совпадают с эталонами:
С1= (0,10; 10; 5,0) — центр 1 кластера,
С2 = (0,735; 14,5; 2,2) — центр 2 кластера,
С3 = (0,277; 12,00; 3,4) - центр 3 кластера.
После этого строится окончательное разбиение: каждая многомерная точка относится к тому кластеру, центр которого ближе всех к этой точке.
Для нашего примера определяем поочередно расстояния всех точек (Х1, X2, X3, Х4, Х5, Х6) до центров трех кластеров.
Как видно из табл. 4, подтверждается полученное разбиение на три кластера: S1 {1}, S2{2, 6}, S3 {3, 4, 5}. На этом алгоритм завершается.
Параметрические данные кластеризации объектов методом k - средних
Номер итерации | Эталоны и их веса | ||
1 | 2 | 3 | |
4 | (0.127, 7, 4.7) 3 | (0.735, 14.5, 2.2) 2 | (0.325, 12.5, 3.1) 2 |
5 | (0.127, 7, 4.7) 3 | (0.757, 14.33, 2.133) 3 | (0.325, 12.5, 3.1) 2 |
6 | (0.127, 7 ,4.7) 3 | (0.757, 14.33, 2.133) 3 | (0.35, 12.33, 3.07) 3 |
7 | (0.140, 8, 4.3) 4 | (0.757, 14.33, 2.133) 3 | (0.35, 12.33, 3.07) 3 |
8 | (0.140, 8, 4.3) 4 | (0.735, 14.5, 2.2) 4 | (0.35, 12.33, 3.07) 3 |
9 | (0.132, 8.4, 4.44) 5 | (0.735, 14.5, 2.2) 4 | (0.35, 12.33, 3.07) 3 |
10 | (0.126, 5.72, 4.55) 6 | (0.735, 14.5, 2.2) 4 | (0.35, 12.33, 3.07) 3 |
11 | (0.126, 5.72, 4.55) 6 | (0.748, 14.4, 2.16) 5 | (0.35, 12.33, 3.07) 3 |
12 | (0.126, 5.72, 4.55) 6 | (0.748, 14.4, 2.16) 5 | (0.36, 12.25, 3.050 4 |
13 | (0.126, 5.72, 4.55) 6 | (0.748, 14.4, 2.16) 5 | (0.324, 12, 3.24) 5 |
14 | (0.126, 5.72, 4.55) 6 | (0.748, 14.4, 2.16) 5 | (0.312, 12.17, 3.23) 6 |
15 | (0.126, 5.72, 4.55) 6 | (0.735, 14.5, 2.2) 6 | (0.312, 12.17, 3.23) 6 |
16 | (0.122, 8.9, 4.61) 7 | (0.735, 14.5, 2.2) 6 | (0.312, 12.17, 3.23) 6 |
17 | (0.122, 8.9, 4.61) 7 | (0.744, 14.43, 2.17) 7 | (0.312, 12.17, 3.23) 6 |
18 | (0.122, 8.9, 4.61) 7 | (0.744, 14.43, 2.17) 7 | (0.324, 12.14, 3.20) 7 |
19 | (0.122, 8.9, 4.61) 7 | (0.744, 14.43, 2.17) 7 | (0.306, 12.00, 303) 8 |
20 | (0.122, 8.9, 4.61) 7 | (0.744, 14.43, 2.17) 7 | (0.3, ,12.11, 3.29) 9 |
21 | (0.122, 8.9, 4.61) 7 | (0.735, 14.5, 2.2) 8 | (0.3, ,12.11, 3.29) 9 |
Номер объекта | 1 | 2,6 | 3,4,5 |
Расстояния до центров классов
Центры кластеров | Объекты | |||||
1 | 2 | 3 | 4 | 5 | 6 | |
С1 С2 С3 | 0 5,338 5,920 | 5,049 0,542 2,497 | 2,844 2,646 0,418 | 1,416 3,939 1,169 | 3,502 1,867 1,020 | 5,664 0,542 3,187 |
Задача №8
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 |
