ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.04.2021
Просмотров: 1655
Скачиваний: 36
151
24
,
2
12
10
6
5
2
2
12
,
а между первым и третьим объектами
3
13
10
5
5
2
2
13
.
Очевидно, что
0
11
.
Аналогично находим расстояние между шестью
объектами и строим матрицу расстояний
0
24
.
2
2
81
.
7
40
.
6
83
.
5
24
.
2
0
1
21
.
7
83
.
5
08
.
6
2
1
0
40
.
6
5
10
.
5
81
.
7
21
.
7
40
.
6
0
41
.
1
3
40
.
6
83
.
5
5
41
.
1
0
24
.
2
83
.
5
08
.
6
10
.
5
3
24
.
2
0
,
1
j
x
i
x
R
.
Из матрицы расстояний следует, что четвертый и пятый
объекты наиболее близки
00
,
1
5
,
4
и поэтому объединяются
в один кластер. После объединения объектов имеем пять
кластеров:
Номер
кластера
1
2
3
4
5
Состав
кластера
(1)
(2)
(3)
(4,5)
(6)
Расстояние между кластерами определим по принципу
«ближайшего соседа», воспользовавшись формулой пересчета
(10.11). Расстояние между объектом
S
1
и кластером
S
(4,5)
будет
.
10
.
5
08
.
6
10
.
5
2
1
08
.
6
10
.
5
2
1
2
1
2
1
2
1
,
15
14
15
14
)
5
.
4
(
1
)
5
.
4
(
,
1
S
S
152
Таким образом, расстояние
)
5
.
4
(
,
1
равно расстоянию от
объекта 1 до ближайшего к нему объекта, входящего в кластер
S
(4,5)
, т.е.
10
,
5
4
,
1
)
5
.
4
(
,
1
. Тогда матрица расстояний
примет вид
0
2
81
.
7
40
.
6
83
.
5
2
0
40
.
6
5
10
.
5
81
.
7
40
.
6
0
41
.
1
3
40
.
6
5
41
.
1
0
24
.
2
83
.
5
10
.
5
3
24
.
2
0
2
R
.
Объединим второй и третий объекты, имеющие наименьшее
расстояние
41
.
1
3
,
2
. После объединения объектов имеем
четыре кластера:
)
6
(
)
5
,
4
(
)
3
,
2
(
)
1
(
;
;
;
S
S
S
S
.
Вновь найдем матрицу расстояний. Для того чтобы рассчитать
расстояние до кластера
S
(2,3)
воспользуемся матрицей
расстояний
R
2
.
Например, расстояние между кластерами
S
(4,5
)
и
S
(2,3)
равно
.
5
2
40
,
1
2
40
,
6
2
5
2
1
2
1
2
1
3
),
5
,
4
(
2
),
5
,
4
(
3
),
5
,
4
(
2
),
5
,
4
(
)
3
,
2
(
),
5
,
4
(
Проведя аналогичные расчеты, получим
0
2
40
.
6
83
.
5
2
0
5
10
.
5
40
.
6
5
0
24
.
2
83
.
5
10
.
5
24
.
2
0
3
R
.
Объединим кластеры
S
(4,5)
и
S
6
, расстояние между которыми,
согласно матрице
R
3
, наименьшее
2
6
),
5
,
4
(
. В результате
получим три кластера
)
3
,
2
(
)
1
(
;
S
S
и
)
6
,
5
,
4
(
S
.
153
Матрица расстояний будет иметь вид:
0
5
10
.
5
5
0
24
.
2
10
.
5
24
.
2
0
4
R
.
Объединим теперь кластеры
S
(1
)
и
S
(2,3)
, расстояние между
которыми
24
,
2
)
3
,
2
(
,
1
. В результате получим два кластера:
)
3
,
2
,
1
(
S
и.
S
(4,5,6)
Расстояние между ними, найденное по
принципу «ближайшего соседа», будет
5
)
6
,
5
,
4
)(
3
,
2
,
1
(
.
Результаты
иерархической
классификации
объектов
представлены на рис. 10.2 в виде дендрограммы: по
горизонтали откладываются номера объектов, а по вертикали –
значения мер близости, при которых происходили соединения
классов.
Рис. 10.2. Дендрограмма
На рис. 10.2 приводятся расстояния между кластерами,
которые объединяются на одном этапе. В этом примере
предпочтение
следует
отдать
предпоследнему
этапу
0
ρ
1
2
3
4
5
6
0.0
0
1.0
0
1.4
1
2.0
0
2.2
4
3.0
0
4.0
0
5.0
0
2.2
24
1.4
1
1.0
0
2.0
0
5.0
0
154
классификации, когда все объекты объединены в два кластера
)
3
,
2
,
1
(
S
и
S
(4,5,6)
.
10.6. Эвристические методы и алгоритмы
Подавляющая часть классификаций на практике
производится эвристическими методами. Это объясняется
относительной простотой и содержательной ясностью таких
алгоритмов. Эти алгоритмы допускают вмешательство в их
работу путем изменения одного или нескольких параметров,
кроме того, они обладают невысокой трудоемкостью.
Наиболее
распространенные
эвристические
алгоритмы
используют для своей реализации различные типы классов.
Разделение классов на типы впервые осуществил советский
ученый Миркин Б.Г. Какие множества называются группами
однородных объектов или классов можно уточнить на основе
заданного расстояния между объектами. Выделим некоторые
типы классов.
1. Класс типа ядра. Такой класс называется
сгущением
.
Все расстояния между объектами внутри класса меньше
любого из расстояний между объектами класса и остальной
частью множества объектов. На рис. 10.3 сгущениями
являются А и В. Остальные пары множеств не разделяются с
помощью этого определения.
2. Кластер (
сгущение в среднем
). Среднее расстояние
внутри класса меньше среднего расстояния от объектов класса
до всех остальных. Множества С и Д теперь разделяются, но у
Е(G) среднее внутреннее расстояние больше, чем среднее
расстояние между Е и F (G и H).
3. Класс типа ленты (
слабое сгущение
). Существует
пороговое значение
Т>0
такое, что для любого
i
x
из класса
S
найдется такой объект
S
j
x
, что
T
ij
, а для всех
S
k
x
справедливо неравенство
T
ik
. В смысле этого
155
определения на рис. 10.3 разделяются все пары множеств
кроме I и J, K и L.
4. Класс с центром. Существует порог R>0 и некоторая
точка x
*
в пространстве, занимаемом объектами класса
S
,
такие, что все объекты из S и только они содержатся в шаре
радиуса R с центром в x
*
. Часто в качестве x
*
выступает центр
масс класса
S
, т.е. координаты центра определяются как
средние значения признаков у объектов класса. Множества I и
J являются классами с центром, а E, F и G – нет.
Рис. 10.3. Типы классов
Рассмотрим наиболее часто используемые эвристические
алгоритмы.
1. Метод К-средних предназначен для выделения и
распознавания классов типа 4 («класс с центром»). Приведем
два варианта.
а) Алгоритм Г. Бола и Д. Холла был предложен в 1965
году. Суть алгоритма состоит в следующем. Случайно
выбираются
К
объектов (эталонов). Каждый объект
присоединяется к ближайшему эталону (тем самым
образуются
К
классов), в качестве новых эталонов
принимаются центры масс классов. Считается, что каждому
объекту приписана масса 1. После пересчета объекты снова
распределяются по ближайшим эталонам и т.д. Критерием
окончания алгоритма служит стабилизация центров масс всех
классов.
K
L
G
H
J
I
A
B
E
F
C
D