ВУЗ:
Составители:
Рубрика:
7
3. Доказать, что метрика Канберра удовлетворяет всем аксиомам мет-
рики.
Лабораторная часть.
1.
Написать программу построения клеток Вороного для двухточеч-
ных множеств в разных метриках.
2.
Написать программу построения клеток Вороного для n-точечных
множеств в разных метриках.
3.
Написать программу распознавания «конвертных» цифр с помощью
функций расстояния, вычислив расстояния между эталонами и образом (об-
раз – двухмерный вектор относительных длин горизонтальных и вертикаль-
ных черточек).
4. АЛГОРИТМЫ КЛАСТЕРИЗАЦИИ
Идея векторного квантования состоит в разбиении пространства при-
знаков (или обучающей выборки) на непересекающиеся области-кластеры
таким образом, чтобы все точки кластера были неразличимы для решаемой
задачи распознавания. Количество кластеров, как правило, значительно
больше числа классов.
Под задачей разбиения класса на кластеры будем понимать задачу вы-
деления таких подмножеств
1
,...,
p
SS
из обучающей выборки
1
{ ,..., }
n
µ
=xx
,
что будут выполняться следующие условия:
1
...
p
SS
µ
∪∪ =;
ij
SS∩=∅ для всех ij≠ .
Эти подмножества обладают некоторым оптимальным свойством, в ка-
честве которого часто используется, например, минимальность дисперсии
кластеров, т.е. характеристика, описывающая степень разброса элементов
кластера вокруг его центра (эталонного образа). В любом кластере эталонный
образ – центр кластера:
1
ki
ik
i
S
S
∈
=
∑
x
cx.
Величина разброса элементов вокруг центра кластера (
дисперсия кластера)
может быть вычислена по формуле
2
1
i
k
iki
i
S
S
∈
∆= −
∑
x
xc
,
где
i
N
– число элементов в i -м кластере.
Разбиение множества элементов на кластеры можно считать успешным,
если функционал
1
p
i
i
Q
=
=∆
∑
будет минимальным.
4.1. Алгоритм k-внутригрупповых средних (k-means)
Этот алгоритм представляет собой пошаговое (итерационное) нахожде-
ние центров кластеров и разбиение обучающей выборки на кластеры до тех
пор, пока функционал
Q не перестанет уменьшаться.
Страницы
- « первая
- ‹ предыдущая
- …
- 5
- 6
- 7
- 8
- 9
- …
- следующая ›
- последняя »
