Субквадратичные алгоритмы метрического анализа данных тема автореферата и диссертации по математике, 01.01.09 ВАК РФ
|
Вальков, Антон Сергеевич
АВТОР
|
||||
|
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Москва
МЕСТО ЗАЩИТЫ
|
||||
|
2005
ГОД ЗАЩИТЫ
|
|
01.01.09
КОД ВАК РФ
|
||
|
|
||||
На правах рукописи
ВАЛЬКОВ Антон Сергеевич
Субквадратичные алгоритмы метрического анализа данных
01.01.09. - дискретная математика и математическая кибернетика
АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук
Москва - 2005
Работа выполнена в отделе Вычислительных методов прогнозирования Вычислительного центра им. A.A. Дородницына Российской академии наук
Научный руководитель:
член-корреспондент РАН, доктор физико-математических наук Рудаков Константин Владимирович
Официальные оппоненты:
доктор физико-математических наук Сметанин Юрий Геннадиевич
доктор технических наук, профессор Местецкий Леонид Моисеевич
Ведущая организация: Московский физико-технический
институт (государственный университет)
. Защита диссертации состоится CUQU^ 2005 г. в
^ 7 часов на заседании диссертационного совета Д002.017.02 в Вычислительном центре им. A.A. Дородницына Российской академии наук по адресу 119991 г. Москва, ул. Вавилова д.40
С диссертацией можно ознакомиться в библиотеке ВЦ
РАН
Автореферат разослан « 2005 г.
Ученый секретарь диссертационного совета д.ф.м.н.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Использование метрической информации является основой решения многих задач распознавания образов, прогнозирования и Data Mining.
Трудности работы с большими метрическими конфигурациями в значительной степени обусловлены квадратичным ростом числа расстояний между объектами с ростом числа объектов В связи с этим большинство известных алгоритмов анализа метрических конфигураций применимы лишь для конфигураций, насчитывающих до нескольких тысяч объектов.
В то же время, в последние годы растет число практических задач, в которых метрические конфигурации состоят из сотен тысяч или миллионов объектов. Для таких (больших) метрических конфигураций любой алгоритм, который хотя бы один раз использует каждое расстояние между объектами, становится практически бесполезным.
Этим обусловлена актуальность настоящей работы, которая посвящена разработке и обоснованию методов, позволяющих реально проводить анализ широкого точно описанного класса больших метрических конфигураций.
Цель работы.
1. Описание достаточно широких и содержательных классов метрических конфигураций, для которых задачи метрического анализа (в частности, задачи кластеризации и задачи синтеза представлений), допускают решение с помощью субквадратичных алгоритмов.
2. Разработка и обоснование субквадратичных алгоритмов анализа метрических конфигураций.
Научная новизна. Впервые исследованы свойства е -кластерных структур: показано, что задача выделения иерархической е -кластерной структуры, вообще говоря, имеет сложность 0(N2); выделены
содержательные классы метрических конфигураций, для которых эта задача имеет сложность 0(Ы 1п ЛО; для решения этой задачи предложен алгоритм V, выделяющий в метрической конфигурации е -кластерную структуру со сложностью от О(ЛЧпА0 до 0(Ы2) в зависимости от е и от свойств заданной метрической конфигурации; разработан основанный на алгоритме V метод выбора скелетных объектов в иерархическом алгоритме синтеза плоских представлений; доказана оптимальность алгоритма V.
Методика исследования. В работе использованы методы общей алгебры, теории множеств, теории функций, теории алгоритмов.
Практическая ценность. В последние годы растет число практических задач, в которых метрические конфигурации имеют сотни тысяч или миллионы объектов. Для таких (больших) метрических конфигураций классические алгоритмы анализа, которые хотя бы один раз использует каждое расстояние между объектами, становятся практически бесполезными.
Предложенные в работе алгоритмы выделения в метрической конфигурации иерархической с-кластерной структуры и синтеза плоских представлений позволяют обрабатывать широкий класс метрических конфигураций указанного масштаба за обозримое время.
Апробация работы. Материалы, изложенные в диссертации, докладывались на:
• Международной конференции "Интеллектуализация обработки информации - 2004" (г Алушта, Крым, Украина);
• 11-ой Всероссийской конференции "Математические методы распознавания образов" (2003 год, г. Пущино, Московская область);
• Международной конференции "Интеллектуализация обработки информации - 2002" (г. Алушта, Крым, Украина);
• 10-ой Всероссийской конференции "Математические методы распознавания образов" (2001 год, г. Звенигород, Московская область);
• семинаре отдела "Вычислительные методы прогнозирования" Вычислительного центра им. А А. Дородницына РАН.
Полученные результаты использовались в работах по проектам РФФИ (№№ 00-15-96064, 99-01-00562,02-01-00326,01-07-90242, 04-0790290, 05-01-00718), Миннауки "Перспективные информационные технологии", Программы фундаментальных исследований ОМН РАН "Алгебраические и комбинаторные методы математической кибернетики".
Личный вклад. Выносимые на защиту результаты получены соискателем лично.
Публикации. По теме диссертации опубликовано 7 работ [1-7], в том числе 2 в ЖВМиМФ. Описания отдельных результатов включались в научные отчеты по проектам РФФИ (№№ 00-15-96064, 99-01-00562, 02-01-00326, 01-07-90242, 04-07-90290, 05-01-00718), Миннауки "Перспективные информационные технологии", Программы фундаментальных исследований ОМН РАН "Алгебраические и комбинаторные методы математической кибернетики".
Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы (50 наименований). Нумерация теорем, лемм, замечаний, алгоритмов, формул сквозная. Текст диссертации занимает 63 страницы.
СОДЕРЖАНИЕ РАБОТЫ
Во введении обосновывается актуальность темы, описываются постановки задач, приводится краткое изложение содержания каждой главы работы.
В первой главе вводится понятие иерархической s-кластерной структуры, исследуются свойства таких структур Показывается, что во всякой метрической конфигурации для каждого £<1 существует единственная е -кластерная структура Исследуется задача выделения в метрической конфигурации г-кластерной структуры при заданном г Показывается, что эта задача имеет квадратичную сложность. В то же время указывается широкий класс метрических конфигураций, для которого сложность удается понизить. Описывается алгоритм V, восстанавливающий иерархическую с -кластерную структуру, и имеющий для задач из этого класса сложность 0(N In N) Указывается способ эффективного распараллеливания алгоритма V Показывается, что алгоритм V обладает свойством «представительного покрытия», состоящим в том, что сначала выбирается по одному объекту в каждом s -кластере, и лишь потом начинаются повторения
Метрической конфигурацией (S,/?) будем называть набор S из JV объектов с введенной на них метрикой р, вообще говоря, неевклидовой.
Будем рассматривать системы К = {АГ,, ,КС } подмножеств множества S. Введем следующие обозначения:
D(K:) = max р(st,s,) — диаметр подмножества;
0ш,СК)=ткД*-1) — максимальный диаметр системы подмножеств;
р{а,К) = папp(a,s) — расстояние от объекта aeS до подмножества icS;
р(К,М)= mm p(s,t) —расстояние между двумя подмножествами;
Imi„(K)= min (К,,К ) — минимальное расстояние между подмножествами системы К.
Разбиением на е-кластеры (при г >0) метрической конфигурации (в.р) будем называть такой набор к = {а:,, непустых
непересекающихся подмножеств К„ что выполнены следующие условия:
и при этом число подмножеств Ск минимально по всем наборам подмножеств, удовлетворяющим условиям (1) и (2).
Обозначим С(е) минимальное по всем наборам подмножеств К, удовлетворяющим условиям (1) и (2), значение Ск.
Подмножества К„...,КСМ, составляющие разбиение К метрической конфигурации на г-кластеры, будем называть е-кластерами.
Отметим, что из условия минимальности Ск следует, что число е-кластеров во всех разбиениях заданной метрической конфигурации на е -кластеры одинаково.
Метрическая конфигурация, число е -кластеров которой С(е) равно числу объектов N, называется е -неделимой, в противном случае - е-делимой.
Для метрической конфигурации (S,р) ее с-кластеры будем также называть б -кластерами первого уровня.
Каждый из £-кластеров первого уровня (которые также являются метрическими конфигурациями с той же метрикой р) либо е-неделим, либо, в свою очередь имеет в -кластерную структуру, и тогда делится на е-кластеры второго уровня и т.д. Так как по определению все кластеры -непустые непересекающиеся множества, то число уровней в этом процессе деления конечно. Назовем его числом уровней иерархической е -кластерной структуры.
АГ,и...и^С11 = S
D„(K)/I„(K)S£
0) (2)
Теорема 1 (критерий s-неделимости). Для произвольной метрической конфигурации при любом в>0 следующие утверждения эквивалентны:
1) Метрическая конфигурация в-неделима.
2) Существует разбиение метрической конфигурации К на в-кластеры такое, что каждый е -кластер А", содержит ровно по одному объекту из S.
3) Существует разбиение к метрической конфигурации на е-кластеры такое, что Dm„(K) = о.
Теорема 2 (о единственности разбиения). Для всякой метрической конфигурации (S,¿>) при любом заданном е < 1 существует единственное ее разбиение на в -кластеры.
Данная теорема доказывается на основе следующих двух лемм'
Лемма 1. Пусть задана в -делимая метрическая конфигурация, и имеются два ее разбиения K = {K,,...,Kcley) и М = {М,,...,МС(£)} на в-кластеры, е < 1 Если некоторые е -кластеры Кч е к и М h е М, 1 < itjJa < С(е) пересекаются, то один из них целиком содержится в другом.
Лемма 2. Пусть задана г-делимая метрическая конфигурация, и имеются два ее разбиения к = {лг,,...,лгс(0} и м = {А/,,...,мС(£)} на е-кластеры, е < 1. Тогда если некоторый е -кластер Кц одного разбиения к содержится строго внутри некоторого е -кластера М h разбиения м, 1<;0,у0 < С(е), то никакой е-кластер из разбиения М не может строго содержаться ни в каком в -кластере разбиения К .
Теорема 3. При в< 1 разбиение метрической конфигурации на иерархию в -кластеров однозначно.
Условие (*). Будем говорить, что при фиксированном е<1 метрическая конфигурация (S,p) удовлетворяет условию (*), если ее е-кластерная структура совпадает как набор подмножеств множества объектов с ее е' -кластерной структурой при s' = е /(1 - е).
Предлагаемый алгоритм V состоит в рекуррентном применении к каждому выделяемому кластеру К, который можно считать метрической конфигурацией (Sк,р), начиная со всей конфигурации (S,p) как одного кластера, следующей процедуры v, делящей этот кластер К на кластеры следующего уровня:
Шаг i = l. Выбирается произвольный объект 5, е S^ Вводится множество П, .= {5,}.
Шаги / = 2,...,/0 Выбирается очередной объект S, е (S,. \П,_,) такой, что p(S,,£},_,) ~> шах Вводится множество Q, ={St,S2,...,S,} Для каждого объекта <Г е (S \ П1Ч) определяются расстояния от него до двух ближайших узлов сети П,_,: = p(S,Cl:_,)= p(S,S,(S)), где
S.(S) = arg min p(S, Cl,,), r2 (S, ) = p(S, \ S. (S)). Для каждого объекта S e (S\ilw) запоминаются значение r2 (S, ) и объект S.(S). Проверяется условие останова, состоящее в том, что для всех Sе(S\fl,_,) верны неравенства p(S„il,_i)<E r1(S,n,,).
Момент останова /0 определяется как наименьшее при котором выполнено условие останова.
Поскольку на каждом шаге в П, добавляется новый объект из S^ с S, то процедура v конечна.
После останова процедуры v объекты 5,,...,5,(1 полагаются центрами «шаров» Остальные объекты приписываются к тому «шару», к центру которого они ближе. Полученные шары объявляются
кластерами следующего уровня. К тем из них, что содержат больше одного объекта, снова применяется процедура V
Лемма 3. Последовательность расстояний /)(5„П,_,) при ;' = 1,2,...,/0 монотонно невозрастает.
Лемма 4. Если объекты /< у находятся в одном е-кластере, то в каждом е -кластере есть хотя бы один объект из .
Лемма 5. При / < /0 ни в одном ^-кластере нет двух объектов из сети
П,
Лемма 6. Пусть г - минимальное такое, что для всех 5 выполнено />(£„ О,.)) < е г2(Я, Тогда вся конфигурация разделяется на
непересекающиеся шары радиуса Пм), при этом найдется к<1
такое, что точки 5„ & находятся в одном шаре, в остальных же шарах находится ровно по одной точке сети. Для шаров отношение Отах к Ьтт не превосходит е' = е /(1 - е) .
Теорема 4. Пусть е<\, и метрическая конфигурация удовлетворяет условию (*). Тогда предлагаемый алгоритм V выделяет (восстанавливает) в точности иерархическую е-кластерную структуру.
Лемма 7. При е<1/2 каждое г'-подмножество, выделенное алгоритмом V, является объединением некоторого числа е-кластеров.
Теорема 5. При любом заданном е<1 сложность задачи выделения е-кластерной структуры не меньше, чем О(ЬР).
Теорема 6. Предложенный алгоритм V, восстанавливающий иерархическую кластерную структуру, имеет сложность т^^к^к).
к
где сумма берется по всем е-кластерам К всех уровней иерархической е-кластерной структуры (по всем вершинам дерева е-кластеров).
Следствие 1. Пусть метрическая конфигурация является в-неделимой. Тогда алгоритм V имеет сложность 0(ЛР).
Следствие 2. Пусть метрическая конфигурация имеет иерархическую в-кластерную структуру с числом уровней (на каждом уровне «отделяется» по одному объекту). Тогда алгоритм V имеет сложность 0(Мг).
Следствие 3. Пусть метрическая конфигурация имеет такую иерархическую кластерную структуру, что каждый кластер каждого уровня (кроме последнего) делится на постоянное число ¿/>2 е-кластеров следующего уровня. Тогда алгоритм V имеет сложность <¡■N■10^ = 0(И\о%М).
Следствие 4. Пусть метрическая конфигурация имеет такую иерархическую кластерную структуру, что она делится на с1\ кластеров первого уровня, каждый кластер первого уровня делится на с12 кластеров второго уровня, и так далее каждый кластер /-го уровня делится на ¿/,+1 кластеров следующего уровня. При этом все ¿/,>2. Тогда если последовательность с^ ограничена сверху, то алгоритм V имеет сложность 0(ЫЛо%Ы).
Во второй главе вводятся понятия частично определенной метрики и локализации метрики, изучаются их свойства. Исследуется, к каким потерям информации (неопределенностям) приводит отказ от использования части расстояний. Приводится ряд точных оценок. Вводится понятие неопределенности значения частично определенной метрики на паре объектов. Обосновывается процедура, вычисляющая эту неопределенность. Доказывается верхняя и нижняя оценки неопределенности.
Пусть задано множество объектов в. Симметричную функцию двух переменных р, заданную на некотором подмножестве п . множества 8x8, назовем частично определенной метрикой, если ее можно доопределить до метрики на всем множестве в2.
Будем также рассматривать и произвольные продолжения частично определенной метрики р на все множество SxS, не требуя выполнения аксиом метрики.
Пусть заданы два объекта А и В из множества объектов S, и частично определенная метрика р такая, что ее значение на этой паре объектов не определено. Действительное число * будем называть допустимым значением частично определенной метрики р на паре объектов (А,В), если р, будучи доопределенной значением х на парах объектов (А,В) и (В,А) может быть доопределена на оставшихся парах объектов из S2 \{D¡¡ ^{(А,В\(В,А)}) так, что полученная функция окажется метрикой.
Пусть заданы два объекта А и В из множества объектов S, и частично определенная на S2 метрика р, причем (А, В) ч DJt Множество допустимых значений р на паре объектов (А,В) обозначим Рр(А,В)с:П*. Верхней (соответственно нижней) границей для неопределенного значения р{А,В) будем называть Д?(А,В)= sup х (соответственно
Д (А,В)= inf *) Неопределенностью значения р на паре объектов
- р хеР;(Л.В)
(А, В) назовем разность д ?(А,В) = - Д ¡¡(А,В).
Пусть задана метрическая конфигурация (S,р) и некоторое непустое ücS. Локализацией ра метрики р на множество fl, будем называть такую частично определенную на S2 метрику ра, что значение ра (А, В) определено тогда и только тогда, когда выполнено условие ((AeCi)v(Be íí)), и при этом ра(А,В) = р(А,В).
Лемма 8. Пусть задано множество объектов S, и функция р -S2-»R+, удовлетворяющая аксиомам 1 и 2. Тогда эквивалентны следующие утверждения:
1. р является метрикой.
2. Для любых a,b,ceS выполнены неравенства р(а, b) й р(а, с) + р(с, Ь). -
3. Для каждой пары объектов a,beS при всех ceS выполнены неравенства | р(а, с) - р(с, Ь) |< р(а, Ь) <, р(а, с) + р(с, Ь).
4. Для каждой пары объектов a,beS выполнены неравенства max | р(а,с)~ р(с, b) р(а, b) < min[ р(а, с) + р(с, 6)].
XS
Лемма 9. Пусть задано множество объектов S, и частично определенная метрика р. Тогда если объекты а,6,сеS таковы, что (a,b)еDfi, (b,c)eDp, (а,с)е£>?, то выполнены следующие неравенства: I р(а,с) - р(с,Ь) |< р(а,Ь) < р(а,с) + р(с,Ь)
Лемма 10. Пусть задана метрическая конфигурация (S,/=>), и локализация ра метрики р на некоторое непустое ficS Тогда для всех пар объектов a, be S\n выполнено неравенство' max | pQ(a,S)-pD(b,S)\i р(а, b) < mm[pQ(a, S) + ра (/>,S)].
Лемма 11. Пусть задана метрическая конфигурация (S,p), и локализация ра метрики р на некоторое непустое ficS. Пусть, кроме того, задано некоторое продолжение р частично определенной метрики ра такое, что на парах из заданных объектов a,b,ceS\Ci для продолжения р выполнены соотношения'
HP,с) = min[/>Q(6,S) + ра(с,5)];
Р(а,с) = mm[pa(a,S) i pa(c,S)];
Тогда для функции р, которая, вообще говоря, может не удовлетворять аксиомам метрики, выполнены следующие два неравенства: | р(а,с) - р(с,Ь) \< р(а,Ь) < р(а,с) + р(с,Ь).
Теорема 7. Пусть задана метрическая конфигурация (S,p), и локализация ра метрики р на некоторое непустое ficS. Тогда для каждой пары различных объектов (А,В)е S2 выполнено следующее равенство:
Рра (А,В) =[max \pa(A,S)- ра(В,S) |, тт(ра(A,S) + ра(В,S)) ]г.(0,+ ос)
Следствие. В условиях теоремы 7 выполнены следующие равенства:
1.ДЛ(ЛВ) = 1пк|/>0(Л^)-р0(в,5)|; А?АА,В) = (A,S) + ра{В,6')); Лд,(A,B)=min(pa(A,S) + pu(B,S))-max | pa(A,S)-pa(B,S) \.
2.РЛ(А,В)=[АЛ(4В), ~&pq(A,B)], если
и РЛ(ДВ)=СО, Д*KB)],если \Ро(А,В)=0,
Замечание, Теорема 7 не может быть расширена на случай произвольной частично определенной метрики заменой шт[р0(Л5) + /70(В,5)] на min [p(A,S) +p(B,S)] и max | pa(A,S)~ pa(B,S) |
на max \p(A,S)-p(B,S)\, где минимум и максимум берутся по
множеству Sp{A,B)={S е SMS е Dp,BS е Лэ}.
В третьей главе исследуются быстрые алгоритмы синтеза плоских представлений метрических конфигураций Описывается субквадратичный алгоритм W, совмещающий размещение точек на плоскости на основе широко известного метода Ньютона-Рафсона с построением иерархии «скелетных» объектов на основе выделяемой алгоритмом V иерархической е -кластерной структуры
Указывается способ распараллеливания алгоритма W. При помощи техники частично определенных метрик, описанной в главе 2, показывается, что для метрических конфигураций, имеющих
достаточно выраженную г-кластерную структуру (г <2/5), использование для выбора скелетных объектов алгоритма V, обладающего свойством представительного покрытия, является оптимальным по сравнению со всеми алгоритмами, не обладающими этим свойством. Алгоритм V, по сравнению с любым другим алгоритмом, не обладающим свойством представительного покрытия, оставляет меньшую неопределенность для расстояний между массовыми объектами. Это означает, что любой алгоритм синтеза плоских представлений метрических конфигураций, использующий для выбора скелетных объектов алгоритм V, имеет заведомо меньшие интервалы погрешностей при последующем «беглом» размещении массовых объектов.
Теорема 8. Пусть заданы метрическая конфигурация и
локализация ра метрики р на некоторое непустое Пев. Тогда для любых объектов Л, в ев выполнены неравенства" 2р{а)({А,В},0.)-р(А,В)<Ь^(А,В)<2рМА,В},0). Теорема 9. Пусть заданы:
- метрическая конфигурация (в,/?);
- О < е < 2/3;
- п - число е-кластеров конфигурации (в,/?);
- набор объектов Пев, П = {5,, причем объекты 5',, ,5„ выбраны таким образом, что в каждом е-кластере находится по одному объекту из £2;
-локализация ра метрики р на некоторое непустое Пев;
- набор объектов Пев, 0 = ,£„}, причем объекты 5,, ,5„ выбраны таким образом, что существует е-кластер К, состоящий по крайней мере из двух объектов, в котором нет ни одного объекта из О.. Тогда
тахД„ М,Я)<тахД„ (А,В)
АВеЗ ' 2-е А'в<* "о -1.я*3
Для доказательства данной теоремы используются следующие утверждения:
Лемма 12. В условиях теоремы 9 для П выполнено неравенство:
тахА {А,В) <, 2вЦ„ (в,/?)
Лемма 13. В условиях теоремы 9 для О выполнено неравенство'
шах А (А, В) >(2- е)Гтт (8,р) 2 (2/е - (В,р).
0
ЗАКЛЮЧЕНИЕ На защиту выносятся:
• Определения и результаты исследования понятия иерархической е -кластерной структуры в метрической конфигурации при заданном е, включающие:
о теорему существования для каждой метрической конфигурации единственной е -кластерной структуры при заданном е < 1;
о теорему о квадратичной сложности в общем случае задачи
выделения с-кластерной структуры; о алгоритм V, выделяющий в метрической конфигурации
иерархическую е -кластерную структуру при заданном е ; о описание классов метрических конфигураций, допускающих (в частности, при помощи алгоритма V) решение задачи со сложностью О(ЛПпЛГ); о теорему об обладании алгоритма V свойством представительного покрытия е -кластеров.
• Результаты исследования частично определенных метрик, включающие:
о теорему о множестве допустимых значений частично определенной метрики на паре объектов вне области ее определения;
о теорему о верхней и нижней оценках неопределенности значения локализации метрики на паре объектов. • Описание и обоснование субквадратичных алгоритмов синтеза плоских представлений метрических конфигураций, включающие:
о алгоритм W синтеза плоского представления метрической конфигурации, основанный на выборе скелетных объектов при помощи алгоритма V; о теорему об оптимальности алгоритма V как алгоритма выбора скелетных объектов в алгоритме W для достаточно выраженной е -кластерной структуры (е <2/3) по сравнению с алгоритмами, не обладающими свойством представительного покрытия е -кластеров.
ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ
1 Вальков ACO быстрых алгоритмах синтеза плоских представлений конечных метрических конфигураций // Ж вычисл матем и матем физ. 2005. Т.45. №2, с.357-368
2 Вальков А С. О быстром алгоритме восстановления иерархической е-кластерной структуры при £<1 // Ж. вычисл. матем. и матем физ. 2005. Т.45. №1,с.170-179.
3. Воронцов К.В, Вальков А.С О быстрых алгоритмах синтеза плоских представлений метрических конфигураций // Искусственный интеллект, Донецк, 2004. №2, с.43-48.
4. Вальков АС. О субквадратичном алгоритме восстановления иерархической е-кластерной структуры при е<1 // Тезисы докладов
международной конференции «Интеллектуализация обработки информации 2004», 14-19 июня 2004, Алушта.
5. Вальков A.C. О субквадратичных алгоритмах синтеза плоских представлений конечных метрических конфигураций // Доклады XI всероссийской конференции «Математические методы распознавания образов» (ММРО-11), Пущино, 23-29 ноября 2003,
6. Вальков A.C. Задачи распознавания с отношением соседства на множестве объектов // Тезисы докладов международной конференции «Интеллектуализация обработки информации 2002», 17-23 июня 2002, Алушта, с.20-21.
7. Вальков A.C. Задачи распознавания с отношением соседства на объектах. Критерии разрешимости и регулярности // Доклады X всероссийской конференции «Математические методы распознавания образов» (ММРО-Ю), Звенигород, 19-23 ноября 2001
Заказ № 636 Подписано в печать 25 04.05 Тираж 100 экз Уел п.л 0,67 ООО "Цифровичок", тел. 505-28-72. www.cfr.ni
РНБ Русский фонд
2005-4 42297
19 МАЙ 2005
ВВЕДЕНИЕ.
СОДЕРЖАНИЕ РАБОТЫ ПО
ГЛАВАМ.
1 s -КЛАСТЕРНЫЕ СТРУКТУРЫ.
1.1 Определения.
1.2 Свойства s -кластерных структур.
1.3 Описание алгоритма V для выделения е -кластерной структуры.
1.4 Параллельная реализация алгоритма V.
1.5 Обоснование алгоритма V.
1.6 Анализ сложности алгоритма V.
2 ЧАСТИЧНО ОПРЕДЕЛЕННЫЕ МЕТРИКИ.
2.1 Определения.
2.2 Свойства частично определенных метрик.
2.3 О множествах допустимых значений локализации.
3 СИНТЕЗ ПЛОСКИХ ПРЕДСТАВЛЕНИЙ МЕТРИЧЕСКИХ КОНФИГУРАЦИЙ.
3.1 Описание алгоритма W для синтеза плоского представления на основе выделения множества скелетных объектов.
3.2 Сложность алгоритма W.
3.3 Иерархический вариант алгоритма W.
3.4 Параллельная реализация алгоритма W.
3.5 Обоснование алгоритма W.
Использование метрической информации является основой решения многих задач распознавания образов, прогнозирования и 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].
Трудности работы с большими метрическими конфигурациями в значительной степени обусловлены квадратичным ростом числа расстояний между объектами с ростом числа объектов. В связи с этим большинство известных алгоритмов анализа метрических конфигураций применимы лишь для конфигураций, насчитывающих до нескольких тысяч объектов.
В то же время, в последние годы растет число практических задач, в которых метрические конфигурации имеют сотни тысяч или миллионы объектов. К таковым, в частности, относятся задачи анализа клиентских сред, где в качестве объектов рассматриваются клиенты некоторой компании (например, крупной розничной сети или сотового оператора), описаниями объектов служат протоколы действий клиентов, и вводятся различные метрики, характеризующие похожесть клиентов в том или ином смысле. Требуется, к примеру, сегментировать множество клиентов, руководствуясь заданной мерой сходства. Или, если задана метрика, отражающая совместную близость клиентов и предоставляемых им услуг, то требуется определить целевую аудиторию для заданной услуги, то есть группу клиентов, которыми эта услуга будет наиболее вероятно востребована.
Для больших метрических конфигураций любой алгоритм, который хотя бы один раз использует каждое расстояние между объектами, становится практически бесполезным. Поэтому поиск субквадратичных (имеющих сложность меньше 0(№) и, следовательно, использующих не все расстояния) алгоритмов решения проблем метрического анализа данных представляется весьма актуальным.
В качестве примера таких проблем можно указать хорошо известную в прикладном анализе данных задачу синтеза плоских представлений метрических конфигураций [6, 8, 12, 14, 47, 49]. Она важна для визуализации и разведочного анализа данных и состоит в следующем. Объектам метрической конфигурации требуется сопоставить точки на координатной плоскости таким образом, чтобы евклидовы расстояния между точками на плоскости в том или ином смысле мало отличались от заданных исходной метрикой расстояний между соответствующими объектами.
Эта задача, вообще говоря, имеет более чем квадратичную сложность, однако при дополнительном допущении о том, что объекты конфигурации могут быть расположены на евклидовой плоскости без искажения расстояний, имеется очевидное решение линейной сложности: в этом случае для точного размещения каждого объекта достаточно использовать лишь расстояния от него до трех других объектов.
Многомерное шкалирование часто используют как средство разведочного анализа данных для наглядного представления метрической конфигурации на плоском точечном графике. Такое представление, несмотря на возможные искажения, как правило, отражает существенные особенности исходной конфигурации, в частности, ее кластерную структуру, если таковая имеется.
Обычно задачу многомерного шкалирования решают путём минимизации функционала стресса ([14]). и где суммирование ведется по всем парам точек (i,j), для которых заданы исходные расстояния р0, wu = р" — веса объектов, dfj =YH=\(xik ~xjk)2 — евклидовы расстояния между м и 7-м объектами, х1к— искомые координаты z-й точки, представляющей /-й объект в евклидовом пространстве. Показатель степени а позволяет ориентировать процесс размещения точек на более точное отражение далеких (при а>-2) или близких (при а<-2) расстояний. Принято считать, что наиболее адекватный результат достигается при а = -2. В этом случае функционал стресса приобретает смысл потенциальной энергии в системе точек, связанных упругими связями, и задача минимизации имеет физический смысл поиска устойчивого равновесия.
Требование субквадратичности для алгоритмов метрического анализа данных означает, в частности, невозможность использования всех заданных расстояний между объектами. В то же время, имеется возможность выбирать те пары объектов, расстояния между которыми используются.
Поскольку значения метрики на различных парах объектов связаны неравенством треугольника, и задание части расстояний может накладывать различные ограничения на значения остальных расстояний, то предпочтительно, чтобы немногочисленные используемые расстояния оставляли по возможности меньшую неопределенность значений неиспользуемых расстояний, другими словами, чтобы отказ от использования значительной части расстояний приводил к малым потерям информации. Таким образом, возникает задача оптимального выбора используемых расстояний.
С решением задачи многомерного шкалирования (минимизации функционала стресса) связаны две проблемы. Во-первых, ни один из известных эффективных методов многомерного шкалирования не гарантирует достижения глобального минимума стресса. Предложенный в [12] описанный ниже алгоритм W не является исключением. В то же время, он ориентирован на поиск такого локального минимума, при котором сохраняются наиболее существенные структурные особенности исходной метрической конфигурации. Для разведочного анализа данных эта стратегия представляет даже больший интерес, чем борьба за глобальную минимизацию стресса. Во-вторых, большинство известных алгоритмов имеют квадратичную по числу объектов сложность, позволяя размещать до нескольких тысяч объектов за приемлемое время. Однако они практически бесполезны для сверхбольших конфигураций, насчитывающих сотни тысяч объектов ([49]). В [12] рассматриваются алгоритмы синтеза плоских представлений метрических конфигураций, имеющие субквадратичную сложность. Требование субквадратичности означает, в частности, что алгоритм уже «не имеет права» просматривать все попарные расстояния между объектами и должен обладать стратегией эффективного выбора используемых пар. Построение такой стратегии оказывается возможным за счет существенной эксплуатации важного свойства метрики — неравенства треугольника. Суть стратегии в том, что построение «проекции» сопровождается выявлением иерархической кластерной структуры метрической конфигурации. Заодно это решает проблему эффективной графической визуализации: вместо всего множества точек отображается только кластерная структура заданной глубины, и такая визуализация становится возможна еще до завершения размещения всех точек.
В алгоритме W использована та же, что и в [47], идея разделения всего множества объектов метрической конфигурации на «скелетные» и «массовые». Скелетные объекты как отдельная, существенно меньшая часть метрической конфигурации размещаются на плоскости с помощью трудоемкого, но обеспечивающего достаточное точное приближение к минимальному значению функционала стресса, алгоритма. Массовые же объекты затем размещаются более быстрым алгоритмом независимо друг от друга на основе информации об их удаленности лишь от «скелетных» объектов. Выигрыш в скорости такого комбинированного алгоритма достигается за счет того, что в качестве скелетных берется лишь малая часть всех объектов метрической конфигурации.
Первая попытка оптимизации выбора скелетных объектов была предпринята в работе [12], где в качестве алгоритма для выбора «скелетных» объектов использован быстрый алгоритм V, выделяющий е-кластерную структуру. Как показано в [5], этот алгоритм обладает свойством «представительного покрытия», то есть сначала выбирает по одному «скелетному» объекту (представителю) в каждом е-кластере, и лишь потом начинаются повторения.
Целью данного исследования, с одной стороны, является описание достаточно широких и содержательных классов задач метрического анализа (в частности, задач кластеризации и задач синтеза представлений), допускающих решение с помощью субквадратичных алгоритмов, с другой стороны - разработка и обоснование методов синтеза таких алгоритмов.
СОДЕРЖАНИЕ РАБОТЫ ПО ГЛАВАМ
В главе 1 вводится понятие иерархической s-кластерной структуры, исследуются свойства таких структур. Показывается, что во всякой метрической конфигурации для каждого е< 1 существует единственная е-кластерная структура. Исследуется задача выделения в метрической конфигурации е-кластерной структуры при заданном е. Показывается, что эта задача имеет квадратичную сложность. В то же время указывается широкий класс метрических конфигураций, для которого сложность удается понизить. Описывается алгоритм V, восстанавливающий иерархическую s -кластерную структуру, и имеющий для задач из этого класса сложность 0(N-\nN). Указывается способ эффективного распараллеливания алгоритма V. Показывается, что алгоритм V обладает свойством «представительного покрытия», состоящим в том, что сначала выбирается по одному объекту в каждом е -кластере, и лишь потом начинаются повторения ([5]).
В главе 2 вводятся понятия частично определенной метрики и локализации метрики, изучаются их свойства. Исследуется, к каким потерям информации (неопределенностям) приводит отказ от использования части расстояний. Приводится ряд точных оценок. В частности, показывается, что множество допустимых значений локализации на паре объектов, на которой она не определена, представляет собой отрезок [а, Ь] или (0,6], границы а, Ъ которого имеют простое выражение через известные значения локализации. Вводится понятие неопределенности значения частично определенной метрики на паре объектов. Обосновывается процедура, вычисляющая эту неопределенность. Доказывается верхняя и нижняя оценки неопределенности ([6]).
В главе 3 исследуются быстрые алгоритмы синтеза плоских представлений метрических конфигураций. Описывается субквадратичный алгоритм W, совмещающий размещение точек на плоскости на основе широко известного метода Ньютона-Рафсона с построением иерархии «скелетных» объектов на основе выделяемой алгоритмом V иерархической е -кластерной структуры ([12]).
Указывается способ распараллеливания алгоритма W. При помощи техники частично определенных метрик, описанной в главе 2, показывается, что для метрических конфигураций, имеющих достаточно выраженную е -кластерную структуру (е<2/3), использование для выбора скелетных объектов алгоритма V, обладающего свойством представительного покрытия, является оптимальным по сравнению со всеми алгоритмами, не обладающими этим свойством ([6]). Алгоритм V, по сравнению с любым другим алгоритмом, не обладающим свойством представительного покрытия, оставляет меньшую неопределенность для расстояний между «массовыми» объектами. Это означает, что любой алгоритм синтеза плоских представлений метрических конфигураций, использующий для выбора «скелетных» объектов алгоритм V, имеет заведомо меньше возможностей для ошибок при последующем «беглом» размещении «массовых» объектов.
Описанные результаты продолжаются и на иерархические варианты алгоритмов синтеза плоских представлений метрических конфигураций.
1 £ -КЛАСТЕРНЫЕ СТРУКТУРЫ 1.1 Определения
Для удобства ссылок приведем здесь аксиомы метрики. Функция p:S2->R+ называется метрикой([24]), если удовлетворяет следующим трем аксиомам:
Аксиома 1. Для всех а,Ъ е S выполнено [p(atb) = 0 а = b ]. Аксиома 2. Для всех a,be S выполнено р{а,Ь) = р(Ъ,а). Аксиома 3. Для всех а, Ь, с е S выполнено р(а,Ъ) < р(а,с) + р(с,Ъ). Метрической конфигурацией (S,р) будем называть набор S из N объектов с введенной на них метрикой р, вообще говоря, неевклидовой. Будем рассматривать системы К = {АГ,,.,л:Ск} подмножеств множества
S. Введем следующие обозначения:
D(Kt) = max p{sk,sl) —диаметр подмножества; sk,SieK, max(К) = шах D(K,) — максимальный диаметр системы подмножеств;
IS/SCK p(a,K) = mmp(a,s) — расстояние от объекта aeS до подмножества seK
К cS; р(К,М)= min p(s,t)—расстояние между двумя подмножествами;
Zmin(K)= min {KifKj) — минимальное расстояние между подмножествами системы К.
Разбиением на е-кластеры (при £>0) метрической конфигурации (S,p) будем называть такой набор К = {К1,.,КСк} непустых непересекающихся подмножеств К-и что выполнены следующие условия: seKjeM
U.U/:Ck =s
DmiX(K)fLmia(K)<£
1) (2) и при этом число подмножеств Ск минимально по всем наборам подмножеств, удовлетворяющим условиям (1) и (2).
Обозначим С(е) минимальное по всем наборам подмножеств К, удовлетворяющим условиям (1) и (2), значение Ск.
Подмножества Кх,.,Кс{е), составляющие разбиение К метрической конфигурации на е -кластеры, будем называть £-кластерами.
Отметим, что из условия минимальности Ск следует, что число е-кластеров во всех разбиениях заданной метрической конфигурации на е -кластеры одинаково.
Ниже в теореме 2 показано, что при е < 1 существует единственное разбиение заданной метрической конфигурации (S,p) на е -кластеры. Обозначим это разбиение K*(S,p). Тогда однозначно определены следующие величины: L*mia(S,p) = Lmia(K*(S,p)) и D*max(S,p) = Dmax(K*(S,/>)).
Метрическая конфигурация, число е -кластеров которой С(е) равно числу объектов N, называется е-неделимой, в противном случае — е-делимой.
Для метрической конфигурации (S,/?) ее £-кластеры будем также называть е -кластерами первого уровня.
Каждый из s -кластеров первого уровня (которые также являются метрическими конфигурациями с той же метрикой р) либо е-неделим, либо, в свою очередь имеет г--кластерную структуру, и тогда делится на s-кластеры второго уровня и т.д. Так как по определению все кластеры -непустые непересекающиеся множества, то число уровней в этом процессе деления конечно. Назовем его числом уровней иерархической е-кластерной структуры.
Каждой иерархической е -кластерной структуре соответствует дерево е-кластеров, вершинам которого соответствуют всевозможные £-кластеры различных уровней из этой иерархической £ -кластерной структуры. Корневой вершине дерева соответствует вся заданная метрическая конфигурация. Из вершины, соответствующей некоторому £ -кластеру К, выходят ребра в те и только те вершины, которые соответствуют £ -кластерам следующего уровня, на которые делится К. а е
Рис. 1 Пример £ -кластерной структуры
Пример Пусть задана метрическая конфигурация, состоящая из 6 объектов - точек на плоскости (рис.1). При £- = 1/2 £ -кластерами первого уровня будут {a}, {b,c,d} и {e,f}. При этом, Dmax = p(b,d), Lmm =p(d,c). £-кластерами второго уровня будут {Ь}, {с}, {d}, {<?} и {/}. Дерево £ -кластеров, соответствующее такой £ -кластерной структуре из двух уровней, изображено на рис.2. a,b,c,d,e,f}
ЗАКЛЮЧЕНИЕ
В данной работе описаны некоторые классы задач метрического анализа (задач кластеризации и задач синтеза плоских представлений), допускающие решение с помощью субквадратичных алгоритмов, а также предложен и обоснован ряд таких алгоритмов.
В частности, введено понятие иерархической е-кластерной структуры, исследованы свойства таких структур. Показано, что во всякой метрической конфигурации для каждого £-<1 существует единственная е-кластерная структура. Исследована задача выделения в метрической конфигурации е -кластерной структуры при заданном s. Показано, что эта задача имеет квадратичную сложность. В то же время указан широкий класс метрических конфигураций, для которого сложность удается понизить. Предложен алгоритм V, восстанавливающий иерархическую е -кластерную структуру, и имеющий для задач из этого класса сложность O(N-lnN). Указан способ эффективного распараллеливания алгоритма V. Показано, что алгоритм V обладает свойством «представительного покрытия», состоящим в том, что сначала он выбирает по одному объекту в каждом е -кластере, и лишь потом начинаются повторения.
Введены понятия частично определенной метрики, локализации метрики и неопределенности значения частично определенной метрики на паре объектов, изучены их свойства. Исследовано, к каким потерям информации приводит отказ от использования части расстояний. Приведен ряд точных оценок. В том числе, показано, что множество допустимых значений локализации на паре объектов, на которой она не определена, представляет собой отрезок [а, Ь] или (0,6], границы а, Ъ которого имеют простое выражение через известные значения локализации. Введено понятие неопределенности значения частично определенной метрики на паре объектов. Обоснована процедура, вычисляющая эту неопределенность. Получены верхняя и нижняя оценки неопределенности.
Исследованы быстрые алгоритмы синтеза плоских представлений метрических конфигураций. Предложен субквадратичный алгоритм tv, совмещающий размещение точек на плоскости на основе широко известного метода Ньютона-Рафсона с построением иерархии «скелетных» объектов на основе выделяемой алгоритмом V иерархической е-кластерной структуры. Указан способ распараллеливания алгоритма W. При помощи предложенной техники частично определенных метрик показано, что для метрических конфигураций, имеющих достаточно выраженную s -кластерную структуру (е <2/3), использование для выбора скелетных объектов алгоритма V, обладающего свойством представительного покрытия, является оптимальным по сравнению с алгоритмами, не обладающими этим свойством. Таким образом, решена задача оптимального выбора используемых расстояний.
Алгоритм V, по сравнению с любым другим алгоритмом, не обладающим свойством представительного покрытия, оставляет меньшую неопределенность для расстояний между «массовыми» объектами. Это означает, что любой алгоритм синтеза плоских представлений метрических конфигураций, использующий для выбора «скелетных» объектов алгоритм V, имеет заведомо меньше возможностей для ошибок при последующем «беглом» размещении «массовых» объектов.
Показано, что описанные результаты продолжаются и на иерархические варианты алгоритмов синтеза плоских представлений метрических конфигураций.
Выполнена программная реализация предложенных алгоритмов. Полученные теоретические выводы подтверждены серией экспериментов на модельных и реальных данных.
1. Айзерман М.А. Браверман Э.М., РозоноэрЛ.И. Метод потенциальных функций в теории обучения машин М.Наука, 1970.
2. Вапник В.Н. Восстановление зависимостей по эмпирическим данным М. Наука. 1979.
3. Вальков А.С. Задачи распознавания с отношением соседства на множестве объектов // Тезисы докладов международной конференции «Интеллектуализация обработки информации 2002», 17-23 июня 2002, Алушта, с.20-21.
4. Вальков А.С. Задачи распознавания с отношением соседства на объектах. Критерии разрешимости и регулярности // Доклады X всероссийской конференции «Математические методы распознавания образов» (ММРО-Ю), Подмосковье 19-23 ноября 2001
5. Вальков А.С. О быстром алгоритме восстановления иерархической е-кластерной структуры при г<1 // Ж. вычисл. матем. и матем. физ. 2005. Т.45. №1, с. 170-179.
6. Вальков А.С. О быстрых алгоритмах синтеза плоских представлений конечных метрических конфигураций // Ж. вычисл. матем. и матем. физ. 2005. Т.45. №2, с.357-368.
7. Вальков А.С. О субквадратичном алгоритме восстановления иерархической е-кластерной структуры при е<1 // Тезисы докладов международной конференции «Интеллектуализация обработки информации 2004», 14-19 июня 2004, Алушта.
8. Вальков А.С. О субквадратичных алгоритмах синтеза плоских представлений конечных метрических конфигураций // Доклады XIвсероссийской конференции «Математические методы распознавания образов» (ММРО-11), Пущино, 23-29 ноября 2003.
9. Васильев В.И. Распознающие системы. Справочник. Киев. Наукова думка. 1983.
10. Ю.Воронцов К.В. О проблемно-ориентированной оптимизации базисов задач распознавания // ЖВМ и МФ. 1998 Т. 38, № 5. с. 870-880
11. Воронцов К.В. Оптимизационные методы линейной и монотонной коррекции в алгебраическом подходе к проблеме распознавания // ЖВМ и МФ. 2000. Т. 40, №1.
12. Воронцов К.В., Вальков А.С. О быстрых алгоритмах синтеза плоских представлений метрических конфигураций // Искусственный интеллект, Донецк, 2004. №2, с.43-48.
13. З.Воронцов К.В., Рудаков К.В., ЧеховичЮ.В. Информационные методы анализа сложных систем // Тезисы докладов научной конференции "Математические модели сложных систем и междисциплинарные исследования", ВЦ РАН им. А.А. Дородницына, 2002 г., Москва, с. 9.
14. М.Дэйвисон М. Многомерное шкалирование: методы наглядного представления дан-ных. М.: Финансы и статистика, 1988. — 254 с.
15. Дюкова Е.В. Об асимптотически оптимальном алгоритме построения тупиковых тестов // ДАН СССР. 1977. 233. № 4. С. 527-530.
16. Дюкова Е.В., Журавлев Ю.И. Дискретный анализ признаковых описаний в задачах распознавания большой размерности // Ж. вычисл. матем. и матем. физ. 2000. Т. 40, №8. С. 1264-1278.
17. Дюкова Е.В., Песков Н.В. Поиск информативных фрагментов описаний объектов в дискретных процедурах распознавания // Ж. вычисл. матем. и матем. физ. 2002. Том 42, № 5. С. 741-753.
18. Журавлев Ю.И. Локальные алгоритмы вычисления информации I, II // Кибернетика 1965 г. № 1, 1966 г. №2.
19. Журавлев Ю.И. Об одном классе алгоритмов над конечными множествами, ДАН СССР, т 151, 5, М. 1963, с. 1025-1028.
20. Журавлев Ю.И., Лосев Г.Ф. Окрестности в задачах дискретной математики // Кибернетика и системный анализ, 1995 г., №2.
21. Журавлев Ю.И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. I-III // Кибернетика. 1977. № 4. С. 5-17, 1977. № 6. С. 21-27, 1978. № 2. С. 35-43.
22. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания и классификации // Проблемы кибернетики. Вып. 33 М.: Наука, 1978, С. 5-68.
23. Журавлев Ю.И. Рудаков К.В. Об алгебраической коррекции процедур обработки (преобразования) информации // Проблемы прикладной математики и информатики. М. Наука, 1987. С.187-198.
24. Колмогоров А.Н., Фомин С.В., Элементы теории функций и функционального анализа, 3 изд., М., 1972
25. Мазуров В.Д. Метод комитетов в задачах оптимизации и классификации. М. Наука. 1990.
26. Матросов В.Л. Нижние оценки емкости многомерных алгебр алгоритмов вычисления оценок // ЖВМ и МФ. 1984 Т. 24, № 12, с. 18811892.
27. Матросов В.Л. Емкость алгебраических расширений модели алгоритмов вычисления оценок // ЖВМ и МФ. 1984 Т. 11, № 5, с. 1719-1730.
28. Матросов B.JI. Емкость полиномиальных расширений множества алгоритмов вычисления оценок // ЖВМ и МФ. 1985 Т. 25, № 1, с. 122133.
29. Матросов В.Л. Корректные алгебры ограниченной емкости над множествами некорректных алгоритмов // ДАН СССР. 1980 Т. 253, № 1, с. 25-30.
30. Матросов В.Л. Корректные алгебры ограниченной емкости над множествами некорректных алгоритмов // ЖВМ и МФ. 1981 Т. 21, № 5, с. 1276-1291.
31. Матросов В.Л. О критериях полноты модели алгоритмов вычисления оценок и ее алгебраических замыканий // ДАН СССР. 1981 Т. 258, № 4, с. 791-796.
32. Матросов В.Л. Оптимальные алгебры в алгебраических замыканиях операторов вычисления оценок // ДАН СССР. 1982 Т. 262, № 4, с. 818822.
33. Матросов В.Л. Синтез оптимальных алгоритмов в алгебраических замыканиях моделей алгоритмов распознавания // Распознавание, классификация, прогноз. М.: Наука, 1989. с. 149-176.
34. Рудаков К.В. О некоторых универсальных ограничениях для алгоритмов классификации // ЖВМ и МФ. 1988. Т.26, № 11. с. 1719 -1729.
35. Рудаков К.В. О применении универсальных ограничений при исследовании алгоритмов классификации //Кибернетика. 1988. № 1. с. 1-5.
36. Рудаков К.В. О симметрических и функциональных ограничениях для алгоритмов классификации // ДАН СССР. 1987. Т. 297, № 1. с. 43- 46.
37. Рудаков К.В. Об алгебраической теории универсальных и локальных ограничений для задач классификации // Распознавание, классификация, прогноз. М.: Наука, 1989. С. 176-201.
38. Рудаков К.В. Полнота и универсальные ограничения в проблеме коррекции эвристических алгоритмов классификации // Кибернетика. 1987. №3. с. 106- 109.
39. Рудаков К.В. Построение проблемно-ориентированных теорий на основе алгебраического подхода к задачам распознавания образов // Доклады 10-й Всероссийской конференции "Математические методы распознавания образов", Москва, AJIEB-B, 2001, с. 113-115.
40. Рудаков К.В. Симметрические и функциональные ограничения для алгоритмов классификации // Кибернетика. 1987. № 4. с. 73 77.
41. Рудаков К.В. Универсальные и локальные ограничения в проблеме коррекции эвристических алгоритмов классификации // Кибернетика. 1987. №2. с. 30-35.
42. Рудаков К.В., Воронцов К.В. О методах оптимизации и монотонной коррекции в алгебраическом подходе к проблеме распознавания // ДАН. 1999. Т. 367 №3. С. 314-317
43. Рязанов В.В. Комитетный синтез алгоритмов распознавания и классификации//ЖВМ и МФ. 1981. Т. 21, № 6 с. 1533-1543.
44. Рязанов В.В. О построении оптимальных алгоритмов распознавания и таксономии (классификации) при решении прикладных задач // Распознавания, классификация, прогноз. Выпуск 1. М. Наука. 1989. с. 229-279.
45. Черепнин А.А. О радиусах разрешимости и регулярности задач распознавания // Доклады 11-й Всероссийской конференции
46. Математические методы распознавания образов", 2003 г. Пущино, с. 210-211.
47. Черепнин А.А. Об оценках регулярности задач распознавания и классификации // Журнал вычислительной математики и математической физики. 1993. №1, с. 155-159
48. Basalaj W. Incremental multidimentional scaling method for database visualization // Proc. of Visual Data Exploration and Analys. VI, SPIE V.3643, California, 1999.
49. Maneewongvatana S., Mount D.M., Analysis of Approximate Nearest Neighbor Searching with Clustered Point Sets //Workshop on Algorithm Engineering and Experiments (ALENEX 99), 1999.
50. TsogoL., BardotA. Multidimensional Scaling Methods For Many-Objects Sets: a Review, http://citeseer.ist.psu.edu/482931.html.
51. Volmer S. "Fast Approximate Nearest-Neighbor Queries in Metric Feature Spaces by Buoy Indexing" //Proc. of the 5th International Conference on Visual Information Systems, p. 36-49, Hsin Chu, Taiwan, March 2002.
