fffffff - master - catmar_mrr/PatternRecognitionMethods

fffffff
230 строк10 KB
andrushka
create fffffff
16 сен 2025, 16:58
16 сен 2025, 16:5825c0ced
4.2. Алгоритм k-внутригрупповых средних (k-means) 
Рассмотрим один из популярных алгоритмов кластеризации, основан-
ный на минимизации функционала суммарной выборочной дисперсии раз-
броса элементов относительно центров тяжести кластеров Q Q=
(3)
. Этот ал-
горитм представляет собой пошаговое (итерационное) нахождение центров
тяжести кластеров и разбиение обучающей выборки на кластеры до тех пор, 
пока функционал Q не перестанет уменьшаться. 
Алгоритм k-means
1. Выделяются некоторые образы из обучающей выборки – начальные цен-
тры кластеров c c 1
(0) (0)
,..., m и полагается k = 0. 
2. Вся обучающая выборка разбивается на m кластеров (клеток Вороного) по
40 © А.Е. Лепский, А.Г. Броневич
методу ближайшего соседа – получаются некоторые кластеры X X 1
( ) ( ) k k
,..., m
. 
3. Рассчитываются новые центры – центры тяжести кластеров по формуле
( )
( 1) 1
( ) k k
i i
k
i X X
+
∈
= ∑x
c x . 
4. Проверяется выполнение условия останова: c c i i
( 1) ( ) k k +
= для всех k m =1,..., . 
В противном случае – переход к пункту 2. 
Теорема 4.1. Алгоритм k-means минимизирует функционал суммарной
выборочной дисперсии Q
(3)
и сходится за конечное число шагов. 
Доказательство. Покажем, что в процессе выполнения шагов алгоритма
минимизируется функционалQ Q=
(3)
. Действительно, сначала (пункт 2 алго-
ритма) он минимизируется при фиксированном положении центров тяжести
кластеров путем оптимизации разбиения обучающей выборки на кластеры
x∈ Xi
, если x c x c − ≤ − i j
( ) ( ) l l
для всех j i ≠ . 
Покажем, что в пункте 3 алгоритма осуществляется минимизация функцио-
нала Q за счет пересчета центров тяжести кластеров при фиксированном
разбиении обучающей выборки на кластеры
( )
( 1)
( )
1
i
l
l
i
Xi
l
X
+
∈
= ⋅ ∑x
c x . 
Для этого рассмотрим функцию разброса R( ) ci
выборочных значений в i -м
классе относительно некоторой точки ci
 (не обязательно центра класса): 
( )
2 2 2 ( ) 2
i i
i i j j X X
R ∈ ∈
= − = − ⋅ + ∑ ∑ x x
c x c x x c c . Исследуем на минимум эту
функцию методом дифференциального исчисления. Имеем
2
1
( ) 2 ( ) ( 1) 0
i i
n
k ik k ik
ik X k X
R
x c x c
c ∈ = ∈
′
  ∂
= − = − ⋅ − =   ∂
  ∑ ∑ ∑ x x
. 
Откуда 1
j i
ik k X X
c x
∈
= ∑x
. Следовательно, минимум функции R( ) ci
достигает-
ся при 1
i
i
i X ∈X
= ∑x
c x . 
Таким образом, на каждой итерации значение Q не увеличивается, т.е. 
Q Q (1) (2) ≥ ≥ .... Имеем невозрастающую последовательность Q( )l
, ограничен-
ную снизу нулем, поэтому эта последовательность имеет предел. Так как
число элементов обучающей выборки, а, следовательно, и число различных
разбиений, конечно, то этот предел достигается за конечное число итера-
ций.
Замечания. 
1. Алгоритм k-means осуществляет локальную, но не глобальную мини-
мизацию функционала Q . Поэтому гарантии «хорошей» кластеризации этот
алгоритм не дает. 
 © А.Е. Лепский, А.Г. Броневич 41
2. Существует много алгоритмов векторного квантования, похожих на k means, но обучающихся быстрее. Правда качество такого обучения может
быть хуже, чем в k-means. 
3. Процедура k-means относится к алгоритмам обучения без учителя (с
самообучением). 
4. Векторное квантование очень чувствительно к размерности простран-
ства признаков: требуемое количество центров кластеров экспоненциально
растет с ростом размерности. Поэтому, если удается избавиться от признака, 
мало влияющего на классификацию, то векторное квантование начинает ра-
ботать быстрее и лучше. 
5. Рассматриваются и невекторные методы квантования. В этих мето-
дах осуществляется квантование не образов – отдельных векторов, а орбит – 
образов относительно некоторой группы преобразований, не влияющих на
кластеризацию (например, сдвиги, растяжения, небольшие искажения букв, 
цифр). 
Пример. Предположим, что на плоскости R
2
за-
даны векторы-образы x1 = (1,1), x2 = (0,0), x3 = (2,0), 
x4 = (4,4), x5 = (5,5), x6 = (5,3) (рис. 4.1). Найдем
кластеризацию этих образов по двум классам. Для
этого выполним последовательно шаги рассмотрен-
ного алгоритма. 
1. В качестве начальных центров кластеров выберем
образы c x 1 1
(0)
= и c x (0)
2 2 = . Тогда, разбивая выборку
{ ,..., } x x 1 6 на два подмножества по методу ближайше-
го соседа, получим начальные кластеры
X1 1 3 4 5 6
(0)
={ , , , , } x x x x x и X2 2
(0)
={ } x . 
2. Вычисляем новые центры – центры тяжести кластеров
(1) 11 31 41 51 61
1
12 32 42 52 62
1
5
x x x x x
x x x x x
+ + + +  
= =   + + + +   c
1 2 4 5 5 17 5 1
1 0 4 5 3 13 5 5
+ + + +    
=     + + + +    , 
(1)
2 2
0
0
= =
      c x . 
3. Сравниваем: c c 1 1
(0) (1) ≠ и c c (0) (1)
2 2 = . Продолжаем выполнение алгоритма. 
4. Разбиваем выборку { ,..., } x x 1 6 на два подмножества с новыми центрами по
методу ближайшего соседа, получим кластеры X1 4 5 6
(1)
={ , , } x x x и
X2 1 2 3
(1)
={ , , } x x x . 
5. Вновь вычисляем центры тяжести кластеров
(2) 41 51 61
1
42 52 62
4 5 5 14 3 1 1
4 5 3 4 3 3
x x x
x x x
+ + + +      
= = =       + + + +       c , 
(2) 11 21 31
2
12 22 32
1 0 2 1 1 1
1 0 0 1 3 3 3
x x x
x x x
+ + + +      
= = =       + + + +       c . 
6. Сравниваем: c c 1 1
(1) (2) ≠ и c c (1) (2)
2 2 ≠ . Продолжаем выполнение алгоритма. 
42 © А.Е. Лепский, А.Г. Броневич
7. Разбиваем выборку { ,..., } x x 1 6 на два подмножества с новыми центрами по
методу ближайшего соседа, получим кластеры X1 4 5 6
(2)
={ , , } x x x и
X2 1 2 3
(2)
={ , , } x x x . 
8. Вновь вычисляем центры тяжести кластеров c c 1 1
(3) (2)
= , c c (3) (2)
2 2 = . Остановка
алгоритма. 
При практической реализации алгоритма возникают следующие про-
блемы: 
1) необходимо задать число кластеров; 
2) качество работы алгоритма зависит от начальной расстановки центров
кластеров. 
Для решения этих проблем рекомендуется осуществить несколько кла-
стеризаций при разных начальных расстановках центров кластеров и различ-
ных значений числа кластеров. После чего необходимо выбрать ту кластери-
зацию, которая доставляет минимум функционалу Q
(3)
.