Математические методы искусственного интеллекта. Броневич А.Г - 8 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

8
Рис.3
2
x
1
x
0
1
x
2
x
4
x
5
x
6
x
3
x
1. Выделим некоторые образы из обучающей выборки и назовем их
эталонными образами – центрами кластеров
(0) (0)
1
,...,
p
cc.
2. Разобьем всю обучающую выборку на
p
кластеров (клеток Вороно-
го) по
методу ближайшего соседа. Получаются некоторые кластеры
(0) (0)
1
,...,
p
SS.
3. Вычислим значение функционала
(0)
Q
.
4. Вычислим новые центры кластеров по формуле
(0)
(1)
(0)
1
k
i
k
i
i
S
S
∈
=
∑
x
cx и
перейдем к пункту 2. Условием остановки этого алгоритма является выпол-
нение на
k -м шаге равенства
() ( 1)kk
QQ
−
=
.
Замечания.
1. Вместо условия остановки
() ( 1)kk
QQ
−
= можно использовать и другие
условия, например условие неизменности положения центров кластеров.
2.
Алгоритм k-means осуществляет локальную, но не глобальную ми-
нимизацию функционала
Q . Поэтому гарантии «хорошей» кластеризации
этот алгоритм не дает.
1.
Число разбиений n точек на k кластеров больше, чем !
k
nk и при
1
nk>> >> велико. Поэтому алгоритм k-means может сходиться очень мед-
ленно.
Пример. Предположим, что на плоскости
2
R
заданы образы-точки
1
(1; 1)=x
,
2
(0; 0)=x
,
3
(2; 0)=x
,
4
(4; 4)=x ,
5
(5; 5)=x ,
6
(5; 3)=x (рис. 3). Найдем кла-
стеризацию этих образов по двум классам. Для этого
выполним последовательно шаги рассмотренного ал-
горитма.
1.
В качестве начальных центров кластеров
выберем образы
(0)
1
1
=cx и
(0)
2
2
=cx. Тогда, разбивая
выборку
16
{ ,..., }xx на два подмножества по методу
ближайшего соседа, получим начальные кластеры
(0)
13456
1
{, , , , }S = xxxxx и
(0)
2
2
{}S = x .
2.
Вычисляем новые центры кластеров:
(1)
11 31 41 51 61
1
12 32 42 52 62
1
5
xxxxx
xxxxx
++++
⎡⎤
==
++++
⎢⎥
⎣⎦
c
12455 3.4
1
10453 2.6
5
++++
⎡
⎤⎡ ⎤
=
++++
⎢
⎥⎢ ⎥
⎣
⎦⎣ ⎦
;
(1)
2
2
0
0
⎡⎤
==
⎢⎥
⎣⎦
cx .
3.
Сравниваем
(0) (1)
11
≠cc и
(0) (1)
22
=cc. Продолжаем выполнение алгоритма.
4.
Разбиваем выборку
16
{ ,..., }xx на два подмножества с новыми цен-
трами по методу ближайшего соседа, получим кластеры
(1)
456
1
{, , }S = xxx и
(1)
123
2
{, , }S = xxx .
5.
Вновь вычисляем новые центры кластеров:
(2)
41 51 61
1
42 52 62
455 143
11
453 4
33
xxx
xxx
++ ++
⎡⎤⎡⎤⎡⎤
===
++ ++
⎢⎥⎢⎥⎢⎥
⎣⎦⎣⎦⎣⎦
c
,
(2)
11 21 31
2
12 22 32
102 1
11
100 13
33
xxx
xxx
++ ++
⎡
⎤⎡ ⎤⎡⎤
===
++ ++
⎢
⎥⎢ ⎥⎢⎥
⎣
⎦⎣ ⎦⎣⎦
c
.

Страницы