Доставка любой диссертации в формате PDF и WORD за 499 руб. на e-mail - 20 мин. 800 000 наименований диссертаций и авторефератов. Все авторефераты диссертаций - БЕСПЛАТНО
Вальков, Антон Сергеевич
01.01.09
Кандидатская
2005
Москва
62 с. : ил.
Стоимость:
499 руб.
СОДЕРЖАНИЕ РАБОТЫ ПО ГЛАВАМ
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
Название работы | Автор | Дата защиты |
---|---|---|
Ньютоновские методы решения смешанных комплементарных задач | Дарьина, Анна Николаевна | 2005 |
Алгоритмические исследования комбинаторных чисел и полиномов | Баранчук, Антон Леонидович | 2005 |
Сложностные параметры двоичных пороговых функций | Шабанин, Олег Васильевич | 2000 |