Послойная кластеризация


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
Послойная кластеризация
Выполнила: Шамсутдинова Лилия
Алгоритмы, основанные на теории
графов

Выборка объектов представляется в виде
графа
G=(V,E)
Алгоритм послойной кластеризации

Основан
на выделении связных компонент
графа на некотором уровне расстояний
между объектами (вершинами
)

С
-
порог расстояния

Формирует
последовательность подграфов
графа
G
, которые отражают иерархические
связи между кластерами
Алгоритм послойной кластеризации

G
t
= (
V
,
E
t
)

граф на уровне
с
t

с
t

t
-
ый
порог
расстояния

m

количество уровней
иерархии

G
0
= (
V
,
o
)
,
o

пустое множество ребер графа,
получаемое при
с
0
=
0

G
m
=
G
, то есть граф объектов без ограничений
на расстояние (длину ребер графа),
поскольку
с
m
= 1
Алгоритм послойной кластеризации

Посредством изменения порогов расстояния
{
с
0
, …, с
m
}, где 0 =
с
0

с
1
< …<
с
m
= 1, возможно
контролировать глубину
иерархии
получаемых
кластеров

Вычислительная сложность:
O(max(n, m)),
где
m n(n
-
1)/
2

Входные данные:
п
оследовательность
порогов
расстояния

Результат: древовидная
структура
кластеров с
разными уровнями иерархии
Практика

Даны объекты:

В качестве расстояния использовать
расстояние Чебышева:

С1= 4, С2=5

Представить решение в виде графа

Приложенные файлы

  • pdf 14693212
    Размер файла: 443 kB Загрузок: 1

Добавить комментарий