Субквадратичные алгоритмы метрического анализа данных

• Автор: Вальков, Антон Сергеевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Москва
• Количество страниц: 62 с. : ил.

СОДЕРЖАНИЕ РАБОТЫ ПО ГЛАВАМ

1 е -КЛАСТЕРНЫЕ СТРУКТУРЫ

1.1 Определения

1.2 Свойства є -кластерных структур

1.3 Описание алгоритма V для выделения є -кластерной структуры

1.4 Параллельная реализация алгоритма V

1.5 Обоснование алгоритма V

1.6 Анализ сложности алгоритма V

2 ЧАСТИЧНО ОПРЕДЕЛЕННЫЕ МЕТРИКИ

2.1 Определения

2.2 Свойства частично определенных метрик

2.3 О множествах допустимых значений локализации
3 СИНТЕЗ ПЛОСКИХ ПРЕДСТАВЛЕНИЙ МЕТРИЧЕСКИХ КОНФИГУРАЦИЙ
3.1 Описание алгоритма IV для синтеза плоского представления на
основе выделения множества скелетных объектов
3.2 Сложность алгоритма

3.3 Иерархический вариант алгоритма IV
3.4 Параллельная реализация алгоритма IV
3.5 Обоснование алгоритма IV
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ

Использование метрической информации является основой решения многих задач распознавания образов, прогнозирования и Data Mining. В частности, на обработке информации такого рода основаны алгоритмы вычисления оценок [21], [22], алгоритмы типа потенциальных функций [1], метод ближайшего соседа [50], метод к ближайших соседей [48], алгоритмы кластеризации [5,7] и многие другие.
В теории распознавания [2, 9, 11-13, 18-23, 34-41], статистическим обоснованием которой служат [25-33], наряду с логическими конструкциями [15-17] разработаны метрические методы, например, [43,44], использующие матрицу расстояний до объектов обучения.
Дискретным аналогом метрики на множестве объектов является отношение соседства [3,4].
Введение метрики возможно и на самих задачах. В этом случае решается вопрос о получении оценок для так называемых радиусов регулярности и разрешимости, понимаемых как расстояния от данной регулярной (разрешимой) задачи до ближайшей нерегулярной (неразрешимой) [45,46].
Трудности работы с большими метрическими конфигурациями в значительной степени обусловлены квадратичным ростом числа расстояний между объектами с ростом числа объектов. В связи с этим большинство известных алгоритмов анализа метрических конфигураций применимы лишь для конфигураций, насчитывающих до нескольких тысяч объектов.
В то же время, в последние годы растет число практических задач, в которых метрические конфигурации имеют сотни тысяч или миллионы

Арв(Л’В) = min [pn(A,S) + pn(B,S)]- ma.xpn(A,S)-pn(B,S) |<
oEÜ J€w
.Pn(A,S A) + I Pn(Л,SA) — pn(B,SA) |= [pn(A,SA) + Pn(B,SA)]
[pn(B,SA)-pa(A,SA)] = 2pn(A,SA) = 2 pn({A,B},0). Отсюда получаем
требуемое äpa(A,B)<2pa({A,B},Ci).
Теперь докажем, что 2pm(.{A,B},Cl)~ р(А,В)<, АРп(А,В). Выполнены следующие соотношения:
Др„ (А,В) = min[pn(^,S') + pn(S,B)] - по следствию из теоремы 7; min[pn(^,S) + pn(S,5)]£p„(>i,Q) + p„(fi,5), так как S efi, и,

следовательно, pn(A,S)Zpn(A, П) и pn (S, В) > р0 (П, В);
рп(А,П) + рп(П,В)>2рп({А,В},П), так как рп(А,П) > рп({А,В},П) и рп(П,В)>Рп({А,В}, П);
рп({А,В},С2) = р({А,В},С2), так как рп является локализацией метрики р на Q.
Получаем цепочку неравенств:
ДРп (А,В) = min[pn(Л,£) + рп(S,В)] >рп(А,П) + рп(Q,5) > 2ра{{А,В),П)

Таким образом, для верхней границы значения ра(А,В) имеем оценку:
ДРп(Л0^2рп({Д,г},П).
В то же время, выполнены следующие соотношения:
Д (А,В) = тах | р„ (А, S) -pn(S,3) | - по следствию из теоремы 7;
- ра Se£l
max| pn(A,S)~ pn(S,B) < p(P,Q) - по лемме 10;

Поэтому для нижней границы того же значения рп(А,В) имеем оценку:
Д (А, В) = тах | рп {А, S) - ра (S, В) |< р(А, В)
- Рп Sen