автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:О специальных представлениях метрических конфигураций

На правах рукописи

Майсурадзе Арчил Ивериевич

О специальных представлениях метрических конфигураций

Специальность 05.13.17 — теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических паук

Москва - 2005

(

Работа выполнена в Вычислительном центре им. А. А. Дородницына РАН.

Научный руководитель: Официальные оппоненты:

Ведущая организация:

член-корреспондент РАН, профессор, доктор физико-математических наук К. В. Рудаков профессор, доктор физико-математических наук Л. Н. Столяров

доктор физико-математических наук Ю. Г. Сметанин

Институт системного анализа РАН

Защита состоится «_»_ 2006 г. в_часов на заседании диссертационного совета Д002.017.02 Вычислительного центра им. А. А. Дородницына РАН по адресу: 119991, Москва, ул. Вавилова, 40.

С диссертацией можно ознакомиться в библиотеке Вычислительного центра им. А. А. Дородницына РАН.

Автореферат разослан «_»_2005 г.

Ученый секретарь диссертационного совета, д.ф.-м.н. '^с^У** в. В. Рязанов

М&6А

Общая характеристика работы

Актуальность темы. В последние десятилетия в распознавании образов, прогнозировании и интеллектуальном анализе данных получило широкое распространение использование мер сходства, когда описание объектов распознавания оказывается связанным с попарным сравнением этих объектов между собой. Практика решения задач распознавания показала, что во многих случаях указанные описания представляются гораздо более адекватными, чем признаковые. Попарные оценки сходства или различия объектов эффективно используются как в теории распознавания и прогнозирования, так и при решении конкретных прикладных задач.

Во многих задачах меры сходства вычисляются и используются только для конечного множества объектов. В практике интеллектуального анализа данных указанные задачи встречаются настолько часто, что возникла своя собственная терминология. В таком случае принято говорить о конфигурациях сходства. Если результатом попарного сравнения объектов является числовая оценка, которая интерпретируется как расстояние между этими объектами, то соответствующую конфигурацию сходства называют метрической конфигурацией (МК).

Не во всех задачах интеллектуального анализа данных существует некоторый единственный «объективный» способ наделить пространство объектов метрикой. Справедливо утверждать, что во многих задачах сами МК могут быть объектами исследования и обработки. И в настоящее время уже можно говорить о появлении в распознавании образов и интеллектуальном анализе данных комплекса технических приемов, предназначенных для работы с МК. В частности, интенсивно развиваются методы их синтеза и преобразования, позволяющие проявить скрытые структуры и закономерности, присутствующие в исходных данных.

Среди разделов математики, изучающих свойства метрик на конечных множествах, в первую очередь следует упомянуть геометрию расстояний. В частности, в работах по геометрии расстояний можно встретить упоминания о пространствах полуметрик. При этом среди стандартных конструкций исследования МК в основном упоминаются только различные конусы таких конфигураций. Однако развитие методов работы с МК в интеллектуальном

I РОС. НАЦИОНАЛЬНАЯ / 1 I БИБЛИОТЕКА I

анализе данных показало, что сами МК и различные их совокупности до сих пор остаются недостаточно изученными. Указанное состояние дел затрудняет создание и теоретическое обоснование новых методов, способных глубже раскрыть метрические свойства исходных данных.

Целью настоящей диссертационной работы является создание и исследование новых методов обработки и преобразования метрической информации, имеющих низкую вычислительную сложность и позволяющих работать с представлениями МК, учитывающими различные требования, дополнительные к метрическим. Для достижения данной цели выделяются два направления исследований.

Целью первого направления является исследование некоторых свойств разложений МК но различным конечным системам МК. Особое внимание при этом уделяется линейным разложениям как по полным, так и по неполным системам МК.

Целью второго направления является исследование некоторых свойств решений задачи представления МК точками конечномерного евклидова пространства, в частности, поведение ошибки представления в зависимости от размерности представления. При этом исследуются характеристики МК, позволяющие обоснованно выбирать размерность указанного представления.

Предметом исследования настоящей диссертационной работы являются сами МК, специальные совокупности МК и различные способы их представления. Во-первых, рассматриваются специальные пространства МК, возникающие при наделении множества всех МК некоторой фиксированной мощности свойствами линейного векторного пространства; рассматриваются специальные представления МК в указанных пространствах, базирующиеся на линейном разложении исходной МК по системе МК; исследуются методы эффективного преобразования данных представлений. Во-вторых, рассматривается задача построения в конечномерном евклидовом пространстве множества точек (точечной конфигурации), расстояния между которыми наилучшим образом приближают заданную МК; при этом предметом исследования оказывается последовательность ошибок представления заданной конфигурации в зависимости от размерности представления.

Методика исследования. В работе для решения поставленных задач используется аппарат линейной алгебры, теории аппроксимации и оптимизаг

ции. При этом следует отметить, что постановки большинства задач можно отнести к теории распознавания, геометрии расстояний и многомерному статистическому анализу.

Научная новизна. Тот факт, что к метрикам на конечном множестве объектов могут применяться операции сложения и умножения на скаляр, был известен ранее. В данной диссертационной работе, по-видимому, впервые МК рассматриваются одновременно как элементы специального линейного векторного пространства и конструкции интеллектуального анализа данных, удовлетворяющие каким-либо дополнительным проблемно-ориентированным требованиям.

Предложены и исследованы новые способы представления МК, при использовании которых требования полуметрики и дополнительные проблемно-ориентированные требования выполнены по построению. Рассмотрены требования, соответствующие задачам, в которых индивидуальные объекты отделены от остальных объектов, пары объектов отделены от остальных объектов, задан ранг МК.

Введено и исследовано понятие ортогональных МК. Введены понятия полных и неполных систем МК. При рассмотрении неполных систем предложены и исследованы понятия оптимального разложения и оптимального приближения заданной МК по системе МК. При рассмотрении полных систем предложены и исследованы некоторые семейства базисов в пространствах МК, соответствующие различным дополнительным проблемно-ориентированным требованиям.

Введено и исследовано новое семейство функционалов сравнения МК. При рассмотрении задачи представления МК точками конечномерного евклидова пространства для указанного семейства функционалов получены новые результаты о поведении ошибки представления для тех МК, которые не могут быть точно представлены ни в каком конечномерном евклидовом пространстве. Предложена и исследована новая характеристика МК — «эффективная размерность», — позволяющая обоснованно выбирать размерность представления.

Теоретическая и практическая ценность. Результаты, полученные в диссертационной работе, ориентированы как на непосредственное практическое применение, так и на разработку и теоретическое обоснование новых

методов преобразования метрической информации в распознавании образов и интеллектуальном анализе данных. В частности, предлагаемые в работе способы представления МК позволяют разработать вычислительно эффективные реализации широкого круга методов распознавания образов и кластерного анализа. Эффективность предложенных процедур подтверждена решением модельных задач и практических задач из области финансового анализа.

Апробация работы. Результаты, изложенные в диссертации, докладывались на Всероссийских конференциях «Математические методы распознавания образов VIII, IX, X, XII» (Москва, ВЦ РАН, 1997, 1999, 2001, 2005 гг.); Международных конференциях «Интеллектуализация обработки информации — 2000, 2002, 2004» (Симферополь, ТНУ); Международной конференции студентов и аспирантов по фундаментальным наукам «Ломоносов — 2001» (Москва, МГУ); семинарах отделов «Математических проблем распознавания и методов комбинаторного анализа» и «Вычислительных методов прогнозирования» ВЦ РАН.

Публикации. По теме диссертации опубликовано 10 работ [1 -10], в том числе 2 в ЖВМ и МФ и 1 в журнале «Искусственный Интеллект». Описания отдельных результатов, полученных в диссертации, включались в научные отчеты по проектам РФФИ 99-01-00562, 02-01-00326, НШ №1721.2003.1.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка иллюстраций (11 пунктов) и списка литературы (86 наименований). Общий объем работы составляет 122 страницы.

Содержание работы

Во «Введении» дается краткий исторический обзор теории и практики распознавания и интеллектуального анализа данных, в указанном контексте рассматриваются основные области применения мер сходства. Обосновывается актуальность темы, приводится краткое изложение содержания диссертационной работы.

В главе 1 даются основные определения, формулируются и доказываются утверждения, используемые во всей работе. В разделе 1.1 приводятся основные определения и обозначения, используемые в работе для метрик и

метрических конфигураций. Кроме того, приводится ряд вспомогательных определений и формул.

В работе используется стандартное определение метрики. Под полуметрикой понимается такое ослабление понятия метрики, для которого равенство расстояния нулю не обязательно влечет равенство объектов. Через [1 , то] обозначается множество натуральных чисел 1,..., т.

Определение 2. Метрической конфигурацией (МК) называется функция /5:[l,m]x[l,m]—»R, которая удовлетворяет условиям

1)Vt€[l,m] p(i,i) = 0\

2) Vix, h G [ 1, m ] p(iu i2) = p{i2, h).

В разделе 1.2 описан способ погружения множества МК в специальное линейное векторное пространство и приведены некоторые свойства операций в этом пространстве.

Введем множество неупорядоченных пар индексов Ет = { {ч) I M € [ 1, тг ], г ф j }. Пользуясь введенным обозначением и определением 2, МК р можно представить как вектор размерности t = \Ет\. Компоненты такого вектора индексируются неупорядоченными парами индексов (ij) и равны pi}. Обратно, по каждому такому вектору можно однозначно восстановить МК.

Таким образом, в данной работе МК мощности m отождествляются с векторами размерности t = т(т — 1)/2. Для обозначения векторного представления МК р будет использоваться тот же самый символ р. В результате такого отождествления на множестве МК одной мощности оказываются заданы операции сложения и умножения на действительное число, фактически соответствующие традиционным операциям в R4. Это позволяет говорить о МК как об элементах специального линейного векторного пространства R£m.

В качестве стандартных (известных) конструкций исследования МК в работе рассматриваются полуметрический конус МЕТт, разрезный конус CUTm, гиперметрический конус HYPm В частности, полуметрическим конусом МЕТт называется множество всех векторов пространства RBm. которые соответствуют МК, удовлетворяющим аксиомам полуметрики.

МК являются элементами линейного векторного пространства. Это означает, что компоненты векторного представления произвольной МК являются коэффициентами разложения этой МК по некоторому базису пространства

К-®™. В частности, если каждая компонента векторного представления МК равна исходному расстоянию между соответствующей парой объектов, то это означает, что разложение производится по так называемому тривиальному базису. В работе предлагается рассмотреть разложения МК по некоторым нетривиальным базисам или неполным системам МК.

В разделе 1.3 исследуется случай, когда каждая компонента некоторой МК одним и тем же образом зависит от соответствующих компонент некоторого набора вообще говоря других МК той же мощности. При этом рассматривается задача поиска таких покомпонентных отображений набора МК в новую МК, которые гарантируют выполнение аксиом полуметрики для получаемой МК при выполнении этих аксиом для каждой МК набора. В разделе для искомых отображений получены некоторые достаточные условия.

Теорема 1. Пусть дана функция /: Ж9 —► К, которая на множестве К' неотрицательна, монотонна и удовлетворяет неравенству треугольника (для функций). Тогда индуцируемое функцией / покомпонентное преобразование набора МК удовлетворяет условию сохранения свойств полуметрики.

Утверждение 4. Пусть Я С И?Вт — множество метрических конфигураций. Если все элементы множества Я удовлетворяют условиям полуметрики, то все элементы выпуклой оболочки Сопу(Д) и неотрицательного конуса К+(Д) также удовлетворяют условиям полуметрики Если все элементы множества Я удовлетворяют условиям метрики, то все элементы Сопу(Я) и К+(Д), кроме нулевого, также удовлетворяют условиям метрики

Приведенные выше утверждения в данной работе используются для получения достаточных условий гарантированного выполнения для некоторой заданной МК условий полуметрики или метрики Указанные достаточные условия получаются по общей схеме, опирающейся на факт принадлежности заданной МК выпуклой оболочке Сопу(Я) или неотрицательному конусу образующими которых является некоторая система МК Я, удовлетворяющих аксиомам полуметрики или метрики. Другими словами, указанные достаточные условия эквивалентны существованию неотрицательного разложения заданной МК по некоторой системе МК, удовлетворяющих аксиомам полуметрики или метрики.

В линейной алгебре наибольшее предпочтение традиционно отдается разложению по ортогональным системам. В разделе 1.4 рассматриваются орто-

тональные системы в пространствах МК.

Теорема 2. Пусть дана пара МК, удовлетворяющих аксиомам полуметрики. Пусть эти МК ортогональны. Тогда по крайней мере одна из данных МК является нулевой.

Из теоремы следует, что в наборе ненулевых МК, удовлетворяющих аксиомам полуметрики, никакие две МК не являются ортогональными. Таким образом, не существует никаких наборов ортогональных МК, которые позволили бы воспользоваться полученными в разделе 1.3 достаточными условиями гарантированного сохранения свойств полуметрики или метрики.

В главе 2 исследуются разложения МК по неполным системам МК. Для того чтобы для неполных систем появилась возможность говорить о разложении произвольной МК, в разделе 2.1 стандартным для теории аппроксимации способом вводятся следующие понятия.

Определение 13. Оптимальным разложением р"^ метрической конфигурации р из пространства по системе метрических конфигураций К с матрицей перехода S называется решение задачи оптимизации

|| р - Sp\\ min, peR«

где ||-|| обозначает некоторую норму в Rßm. Метрическая конфигурация ßopt _ Sß°pt называется оптимальным приближением метрической конфигурации р по системе метрических конфигураций К.

Из определения оптимального приближения можно получить следующее свойство, которое является одним из решающих оснований для использования оптимальных разложений в прикладных задачах:

^ 0 £ К+(АГ).

Далее в работе рассматривается ситуация, когда верны соотношения Ург, р2 € K£m Vc*i, с*2 е К р = аЛрх + а2р2 = a\vT + , Vpi,ß2 е Уаиа2 G R р = щрх + а2р2 => р0** = oupf + а2р^.

Хотя указанные соотношения выполнены не всегда, они, например, всегда имеют силу для очень важного случая норм, обобщающих понятие евклидовой нормы. Если соотношения выполнены, то справедливы следующие утверждения, которые могут найти существенное применение при разработке и обосновании процедур обработки МК.

Утверждение 13. Для любой системы метрических конфигураций К и любого подмножества X множества R£m выполнены соотношения

X С { р | > 0 } М+ (X) С { р | f* > 0 } , ХС{р\рР>* ^ 0} «=►»+(*) XQ{p\p*e METm } ^ R+РО Я{р\рР*е МЕТт } , хс {р\рР*е CUTm} с {р| р^ € CUTm}.

Утверждение 14. Для любой системы метрических конфигураций К и произвольной метрической конфигурации р выполнены соотношения

реж+({рг\р? р € М+({ pi I pf € METm METm,

р е R+({ h\p?e CUTm }) => p°* e CUTm.

Таким образом, при выполнении ряда ограничений на исходную МК может быть получен спектр условий как на неотрицательность оптимального разложения, так и на сохранение или усиление указанных ограничений для оптимальных приближений [8]

В разделе 2.2 свойства оптимального разложения МК исследуются для неполной системы, элементы которой могут быть интерпретированы как отделение одного объекта распознавания от всех остальных [7]. Данная система содержит т МК и имеет вид

#={5({г})|ге[1,т]}, (2.4)

где <5({г})у = 1, i({t})/y = 0 при k,j <£ {г}.

Пусть некоторая МК р может быть точно разложена по системе (2.4), пусть р — ее разложение. Тогда векторное представление и разложение связаны следующим образом:

т

Р = О) = £ Pj)iij ИЛИ V(tj) £ Ет р13 =Рг+ рг

»=1 to)e£m

Если для некоторой МК р такое разложение существует, то оно может быть использовано для описания или интерпретации отдельных объектов в сравнении со всеми остальными. При этом компоненты разложения показывают удаленность каждого объекта от остальных объектов в совокупности.

В работе получены выражения для оптимального разложения и оптимального приближения произвольной МК по рассматриваемой системе (2.4), причем показано, что процедуру их вычисления можно организовать таким образом, что потребуется порядка 0(т2) арифметических операций. Неотрицательные оптимальные разложения по системе (2.4) и только они соответствуют оптимальным приближениям, удовлетворяющим условиям полуметрики.

Утверждение 17. Оптимальное приближение МК по системе (2.4) лежит на фасете полуметрического конуса тогда и только тогда, когда минимум по вектору оптимального разложения равен нулю:

р°*едМЕТт 4=^ = 0.

Утверждение 19. Если МК удовлетворяет условиям полуметрики, то ее оптимальное разложение по системе (2.4) неотрицательно.

р € МЕТт =» р01* > 0

Аналогичные утверждения выполнены для МК, принадлежащих С11Тт или НУРт.

В главе 3 исследуются разложения МК по полным системам МК.

Векторы, из которых состоит тривиальный базис, не соответствуют МК, удовлетворяющим аксиомам метрики. Указанное несоответствие существенным образом влияет на эффективность реализации процедур обработки МК, особенно в тех случаях, когда множество используемых МК ограничено какими-либо условиями. Поэтому может быть поставлена задача выбора в пространстве МК некоторого иного, нетривиального базиса [4, б], учитывающего условия, предъявляемые к используемым МК. В качестве таких условий в данной работе рассматриваются аксиомы метрики, «равноправие» всех пар объектов, соответствие МК заданному рангу, а также сочетания указанных условий.

В качестве формального эквивалента равноправия всех пар объектов распознавания в разделе 3.1 вводится понятие гомогенной системы МК НМв(а,Р, т)-

Определение 14. Гомогенной системой МК с параметрами (а, /3,7) называется такая система МК | | (г?) € Ет |, что для каждой неупорядоченной пары [г]) соответствующая МК р13 строится по следующему набору

правил:

(Ру)у = (&;)«* = & & е [ 1, т] \ {.7" };

(РиЬк = 0, ке [1,т]\{г}; (й,-)и = 7> М € [1,т] \ {»,.7 }.

Таким образом, введено трехпараметрическое семейство систем МК. Тривиальный базис является гомогенной системой ЯМ(7(1,0,0).

Устанавливаются необходимые и достаточные условия выполнения аксиом полуметрики и метрики для элементов гомогенных систем, а также условия их линейной независимости. Доказывается, что формулы перехода от разложения по некоторому базису к разложению по тривиальному базису имеют вид линейной комбинации усреднения расстояний по объектам и парам объектов тогда и только тогда, когда базис является гомогенной системой. При этом сложность как прямого, так и обратного перехода составляет 0(т2), что меньше, чем сложность перехода к разложению по произвольному базису. Для гомогенных систем дается интерпретация как коэффициентов указанного перехода, так и коэффициентов разложения произвольной МК.

Введем обозначения р = (Е^^Ж,)/*; рг.= (Т,кф,т],к&Р*к)/(т -1), *€[1 ,т].

Теорема 4. Формулы перехода от представления р к представлению р имеют вид р%] = ,32ргз + Эх^рг + р3) 4- зр с произвольными числовыми параметрами (в2, я) тогда и только тогда, когда р составляют коэффициенты разложения по некоторой гомогенной системе МК.

Кроме того, ставится и решается задача поиска такой гомогенной системы, которой соответствует в некотором смысле наибольшее множество МК, все коэффициенты разложения которых по искомой системе неотрицательны.

Теорема 5. Если ЯМС?(а,/?,7) С МЕТт, то конус И+(ЯМ(?(а,А7)) имеет наибольший «объем» при значениях параметров а = 0, /0 = 1,7 = 0.

В разделе 3.2 вводятся ранговые базисы, в которых МК имеет неотрицательное разложение тогда и только тогда, когда она имеет заданный ранг

Определение 15. Рангом МК р называется такой линейный порядок на множестве неупорядоченных пар индексов Ет, что порядок на парах индексов совпадает с нестрогим порядком значений соответствующих компонент МК в том смысле, что для порядка на парах выполнены соотношения

(у) < (Ы) р{] < ры и (у) < (Ы) Ф= ру < ры-

Следует отметить, что если некоторые компоненты МК равны, то ей со-

ответствует сразу несколько рангов. В соответствии с линейным порядком неупорядоченные пары из Ет можно занумеровать числами от 1 до t = С^. Далее для ранговых базисов вместо пар (ij) из Ет будут использоваться одинарные индексы из [ 1, í ].

Рассмотрим представление р МК р последовательными приращениями. Пусть pi = pi, а для г — 2,3,..., t выполнено рг — рг - рг. Соответственно, ранговым базисом называется такой набор МК р\,... ,pt, в котором представлением МК р будет вектор р.

Все элементы рангового базиса сами имеют заданный ранг По аналогии с разделом 1.3 выясняется связь между неотрицательносью разложения некоторой МК по ранговому базису и наличием соответствующего ранга у этой МК.

Утверждение 33. Пусть по заданному рангу построен ранговый базис. Представление р некоторой МК по этому ранговому базису неотрицательно тогда и только тогда, когда эта МК имеет заданный ранг и ее представление в тривиальном базисе неотрицательно.

Сложность перехода от разложения по тривиальному базису к разложению по ранговому базису и обратно составляет 0(т2), что меньше, чем сложность перехода к разложению по произвольному базису. Доказывается, что если некоторый элемент некоторого рангового базиса удовлетворяет аксиомам полуметрики, то либо он совпадает с конфигурацией, соответствующей пространству изолированных точек, либо лежит на границе множества метрических конфигураций, удовлетворяющих аксиомам полуметрики. Если же элемент рангового базиса не удовлетворяет аксиомам полуметрики, то на границе множества метрических конфигураций, удовлетворяющих аксиомам полуметрики, лежит середина отрезка, соединяющего этот элемент и конфигурацию j, соответствующую пространству изолированных точек

Утверждение 34. Для произвольного i € [l,t] выполнено соотношение

Pi G METm 3METm V Pi = j.

Утверждение 35. Для произвольного г £ [ 1, t ] если p¿ € <9METm, то pi лежит на экстремальном луче МЕТт.

Теорема 6. Для произвольного i е [l,t] выполнено соотношение

Pi <¿ METm ¡(I, + j) <E <9METm.

Пусть дан ранговый базис рг,р2, Тогда в разделе 3.3 полуметриче-

ский ранговый базис 9ъ <72, ■ ■ ■, <7г строится по правилу

¿¿МЕТт;

Теорема 7. Пусть задал некоторый ранг и по нему построен полуметрический ранговый базис. Пусть д —представление некоторой МК в этом базисе. Тогда если д > 0, то МК имеет заданный ранг и удовлетворяет аксиомам полуметрики.

В теореме 8 доказывается, что среди всех базисов, обладающих только что указанным свойством, полуметрические ранговые базисы характеризуют в некотором смысле наибольшие множества МК.

В главе 4 рассматривается задача представления МК в конечномерном евклидовом пространстве, которая в разделе 4.1 формулируется следующим образом. Пусть х: х ® — заданный функционал сравнения МК. Пусть заданы набор объектов распознавания мощности тп и соответствующая ему МК р*, а также желаемая размерность представления п. Для точечной конфигурации (хг | х, е Е", г £ [ 1, т]} соответствующую ей МК обозначим рп. Среди всех возможных точечных конфигураций {хг | х, € К", г € [ 1, га]} требуется найти такую, что соответствующая ей МК рп доставляла бы минимум заданному функционалу х при сравнении с исходной МК р*, т.е. величине х(/5*, р")-

Для любого числа объектов, большего трех, существуют МК, которые не могут быть изометрически вложены ни в какое конечномерное евклидово пространство В задачах распознавания такие МК возникают достаточно часто и представляют существенный интерес. Результаты глав 4 и 5 ориентированы как раз па такие МК.

В разделе 4.2 предлагается алгоритм, который проверяет возможность точного представления заданной МК точками конечномерного евклидова пространства и, в случае успеха, строит соответствующую точечную конфигурацию наименьшей необходимой размерности В отличие от распространенных методов многомерного шкалирования, алгоритм рассматривает объекты распознавания последовательно, что позволяет наращивать множество объектов или выбирать порядок их рассмотрения.

В разделе 4 3 рассматривается задача поиска оптимальной проекции точечной конфигурации для конкретного функционала ошибки представления МК. Предлагается процедура построения оптимального представления заг данного набора векторов с помощью линейного ортогонального преобразования и одновременного упорядочивания компонент Приведенная процедура допускает итеративное пополнение набора объектов распознавания.

В главе 5 для одного семейства функционалов сравнения МК исследуется поведение ошибки представления МК в конечномерном евклидовом пространстве с ростом размерности представления. Рассматриваются свойства получаемых при этом оптимальных точечных конфигураций [10}.

В разделе 5 1 для МК вводится семейство функционалов сравнения х(р, г), на которые наложены следующие требования:

1) равенство нулю только при совпадении МК;

2) при изменении некоторого выделенного расстояния гу и фиксации всех остальных расстояний единственной точкой экстремума будет точка минимума, которой является соответствующее исходное расстояние ру (таг ким образом, «плато» тоже недопустимы).

Отметим, что из указанных требований вытекает неотрицательность функционалов. Неформально можно сказать, что функционалы данного семейства сохраняют информацию обо всех элементах исходной МК, как бы далеко от нее ни была другая МК. Предложенное семейство функционалов сравнения достаточно широко. Частным, но распространенным случаем таких функционалов являются функционалы сравнения вида «потенциальной функции»

та—1 т

х(р,г) = £ /(/ty.ro), ¿=1 >=й-1

где неотрицательная числовая функция /х(у) = /(х, у) (при любом параметре х) равна нулю при у = х и только там, строго монотонно возрастает при у > х и убывает при у < х.

Теорема 10. Пусть дана МК для т объектов. Если эта МК точно предста-вима точечной конфигурацией в некотором конечномерном евклидовом пространстве, то непрерывно дифференцируемый функционал сравнения, удовлетворяющий свойству (2), достигает экстремальных значений на точечных

конфигурациях размерности не более m — 1, иначе он достигает экстремальных значений на точечных конфигурациях размерности не более m — 2

В разделе 5.2 для рассматриваемого семейства функционалов сравнения МК формулируется и доказывается теорема об асимптотическом поведении ошибки представления с ростом размерности.

Теорема 11. Пусть дана МК мощности то и по этой МК и непрерывно дифференцируемому функционалу сравнения, удовлетворяющему требованиям (1) и (2), построена последовательность Р(п) минимумов ошибки представления. Тогда эта последовательность неотрицательная, монотонно невоз-растающая. Кроме того, если исходная МК точно представима точечной конфигурацией в некотором конечномерном евклидовом пространстве, то Р(п) достигает минимального (а именно, нулевого) значения при размерности не более п = т — 1, иначе Р(п) достигает минимального (причем строго положительного) значения при размерности не более п = тп — 2.

В разделе 5.3 вводится функционал эффективности размерности и на модельных задачах раскрывается его смысл.

Определение 20. Назовем эффективностью размерности к, к £ N, для данной последовательности ошибок представления { Р(п) | п = 0,1,2... } величину

Эффективными будем называть размерности, при которых на графике эффективности наблюдается пик, т.е. размерность к эффективна, если е(к) > е(к - 1) и е(к) > е(к + 1). Эффективная размерность является характеристикой метрических свойств набора объектов. Как показывают исследования и модельные задачи, превышение пика е(к) над «соседями», представляющее практический интерес, составляет один-два порядка и более.

Приводятся исследования и численные эксперименты, иллюстрирующие понятие эффективной размерности и подтверждающие возможность при поиске такой размерности использовать приближенные алгоритмы, существенно более быстрые, чем точные алгоритмы оптимизации [5].

при АР(к +1) > 0; 1, при АР{к) = 0 и АР(к + 1) = 0; +ос, при АР(к) > 0 и АР{к + 1) = 0;

\

где АР{к) = Р(к - 1) - Р(к).

В разделе 5.4 приводится пример выявления эффективных размерностей для данных реального прикладного исследования, которое проводилось в рамках решения одной задачи финансового анализа.

В «Заключении» перечислены основные результаты, полученные в диссертационной работе.

Публикации по теме диссертации

[1] Майсурадзе А. И. Эффективная размерность контрольных выборок в задачах распознавания // Матем. методы распознавания образов. Тезисы докл. VIII Всеросс. конф. Пущино: ОНТИ ПНЦ РАН, 1997. С. 81-83.

[2] Майсурадзе А. И. О выборе размерностей евклидовых представлений метрических описаний прецедентов // Матем. методы распознавания образов. Докл. IX Всеросс. конф. М.: AJIEB-B, 1999. С. 74-75.

[3] Майсурадзе А. И. Об эффективном выборе размерностей представлений метрических конфигураций в евклидовых пространствах // Интеллектуализация обработки информации. Тезисы докл. Междунар. науч. конф. Симферополь: Крымский науч. центр НАН Украины, 2000. С. 48.

[4] Майсурадзе А. И. О некоторых нетривиальных базисах в пространствах метрических конфигураций // Матем. методы распознавания образов. Докл. X Всеросс. конф. М.: AJIEB-B, 2001. С. 87-90.

[5] Майсурадзе А. И. О некоторых проблемах вычисления эффективной размерности в задачах распознавания образов // Материалы Междунар. конф. студентов и аспирантов по фундаментальным наукам «Ломоносов 2001». М.: Изд. отдел ф-та ВМиК МГУ, 2001. С. 20.

[6] Майсурадзе А. И. Об использовании нетривиальных базисов пространств метрических конфигураций в задачах распознавания // Интеллектуализация обработки информации. Тезисы докл. Междунар. науч. конф. Симферополь: Крымский науч. центр НАН Украины, 2002. С. 58 60.

[7] Майсурадзе А. И. Об оптимальном разложении по одной системе метрических конфигураций // Искусственный Интеллект. 2004. № 2. С. 129-133.

[8] Майсурадзе А. И. Об оптимальных разложениях конечных метрических конфигураций в задачах распознавания образов // Ж. вычисл. матем. и матем. физ. 2004. Т. 44, № 9. С. 1697-1707.

[9] Майсурадзе А. И. Об оптимальных разложениях метрических конфигураций в задачах распознавания // Интеллектуализация обработки информации. Тезисы докл. Междунар. науч. конф. Симферополь. Крымский науч. центр НАН Украины, 2004. С. 109-110.

[10] Майсурадзе А. И. О свойствах оптимальных точечных конфигураций для одного семейства функционалов сравнения метрических конфигураций // Ж. вычисл. матем. и матем. физ. 2005. Т. 45, № 9. С. 1741-1748.

/

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. Подписано к печати 19.12.2005 г. Формат 60x90 1/16. Усл.печ.л, 1,0. Тираж 100 экз. Заказ 890. Тел. 939-3890. Тел /Факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.

Введение

0.1 Теория распознавания.

0.2 Меры сходства в распознавании

0.3 Содержание работы.

0.4 Благодарности.

1 Специальные пространства метрических конфигураций

1.1 Метрики и метрические конфигурации

1.2 Метрические конфигурации как элементы линейного векторного пространства

1.3 Достаточные условия выполнения аксиом метрики.

1.4 Ортогональные системы и аксиомы метрики.

2 Неполные системы метрических конфигураций

2.1 Понятие оптимального разложения метрической конфигурации

2.2 Пример оптимального разложения по системе метрических конфигураций.

3 Полные системы метрических конфигураций

3.1 Гомогенные системы и гомогенные базисы

3.2 Ранг метрической конфигурации и ранговые базисы

3.3 Полуметрические ранговые базисы.

4 Представление метрических конфигураций в конечномерных евклидовых пространствах

4.1 Задача оптимального представления метрической конфигурации в конечномерном евклидовом пространстве

4.2 Построение точечной конфигурации в конечномерном евклидовом пространстве по матрице попарных расстояний

4.3 Ортогональное проектирование, оптимальные свойства разложения по системе ортогональных векторов.

5 Оптимальные точечные конфигурации: связь качества и размерности представления

5.1 Функционалы сравнения метрических конфигураций и свойства оптимальной точечной конфигурации.

5.2 Об асимптотическом поведении ошибки представления

5.3 Понятие эффективности размерности.

5.4 Об одной задаче финансового анализа.

Целью настоящей диссертационной работы является исследование множеств метрических конфигураций и создание специальных методов работы с метрическими конфигурациями. Во-первых, исследуются специальные пространства метрических конфигураций, возникающие при наделении множества всех метрических конфигураций некоторой фиксированной мощности свойствами линейного векторного пространства; предлагаются новые методы эффективного преобразования представлений метрических конфигураций в указанных пространствах. Во-вторых, рассматривается задача поиска в конечномерном евклидовом пространстве оптимальной точечной конфигурации, т.е. множества точек, расстояния между которыми наилучшим образом приближают заданную метрическую конфигурацию; предлагаются новые критерии выбора размерности оптимальной точечной конфигурации. Указанные исследования ориентированы как на непосредственное практическое применение, так и на разработку и теоретическое обоснование новых методов преобразования информации в распознавании образов и интеллектуальном анализе данных.

0.1 Теория распознавания

Настоящая диссертационная работа посвящена исследованию свойств и разработке новых методов преобразования метрической информации. Так как излагаемые в работе результаты в первую очередь направлены на применение в распознавании образов и интеллектуальном анализе данных, представляется целесообразным кратко рассмотреть историю и современное состояние этих разделов прикладной математики. Отметим, что нижеследующий обзор в основном базируется на идеях академика РАН Ю.И. Журавлева и члена-корреспондента РАН К.В. Рудакова.

Теория распознавания образов начала формироваться как самостоятельный раздел математики в середине 50-х годов XX века. На первом этане ученые и разработчики руководствовались тезисом: «Никакая строгая математика не может решить сложных задач». До начала 70-х годов шло бурное строительство эвристических методов классификации и алгоритмов анализа сложных описаний. Для различных прикладных задач были созданы свои собственные более или менее удачные эвристики. Одновременно шел «естественный отбор» таких алгоритмов, наилучшим образом зарекомендовавших себя при решении прикладных задач. Результатом этого этапа накопления в 50-е и 60-е годы стало создание по сути большой библиотеки эвристических алгоритмов [3, 12, 28, 31, 54], некоторые из которых были в некотором смысле теоретически обоснованы [11, 45, 46, 85].

Начало следующего этапа развития теории распознавания образов связано с идеей исследовать отдельный алгоритм как математический объект. Варьируя параметры эвристических алгоритмов, можно было получить описание, их охватывающее. Регулярное описание алгоритмов и соответствующее построение моделей алгоритмов позволило поставить строгую задачу максимизации в моделях меры качества алгоритма, показывающей, например, долю правильно распознанных контрольных точек.

Среди возникших на втором этапе моделей алгоритмов наибольшую известность имеют алгоритмы, основанные на принципе комитетных решений [32, 33], алгоритмы вычисления оценок [18, 19, 20], статистические [4, 5,10, 27, 73, 72], логические [14,15, 68] и структурные [9,10] семейства. Отметим, что модели вычисления оценок вобрали в себя большинство используемых эвристических принципов.

Дальнейшим этапом на этом пути стало появление в конце 70-х годов методов суперпозиции алгоритмов. Наиболее известное выражение идея совместного использования нескольких алгоритмов при решении отдельных задач нашла в конструкциях голосования [53, 62] и взвешенного голосования [71, 81].

Среди подходов, использующих сразу некоторый набор распознающих алгоритмов, выделяется алгебраический подход, исходно предложенный Ю.И. Журавлевым и развиваемый его учениками [22, 17, 21,

- 749, 50, 51]. В алгебраическом подходе целенаправленно строятся оптимальные суперпозиции алгоритмов для конкретных задач при помощи корректирующих операций, при определенном выборе исходных алгоритмов из имеющихся [8, 47, 52]. Первоначально в качестве корректирующих операций применялись операции над действительными матрицами, а в качестве исходных семейств алгоритмов рассматривались алгоритмы вычисления оценок и алгоритмы, основанные на принципе разделения [23, 24, 25, 26]. В алгебраическом подходе возможно достраивать алгоритмический базис и применять корректирующие операции для синтеза алгоритмов, превосходящих по качеству любой из исходных.

Быстрое совершенствование измерительной техники стимулирует непрерывный рост сложности задач обработки данных, связанный с увеличением размерностей информационных массивов и повышением структурной сложности регистрируемых сигналов. Одновременно накладываются все более жесткие ограничения на время обработки. Основной метод преодоления возникающих при этом проблем — увеличение быстродействия и памяти вычислительных устройств. Современное развитие архитектуры ЭВМ подчинено увеличению скорости выполнения элементарных операций (увеличение частоты центрального процессора и распараллеливания процедуры вычислений). Необходимо отметить, что в рамках теории распознавания и интеллектуального анализа данных развиваются универсальные вычислительные методы, позволяющие лучше использовать уже существующий парк вычислительной техники [6].

0.2 Меры сходства в распознавании

В последние десятилетия в распознавании образов, прогнозировании и интеллектуальном анализе данных использование метрической информации или мер сходства (см. [7]), когда описание объектов распознавания оказывается связанным с попарным сравнением этих объектов между собой, получило широкое распространение.

Описания указанного вида в задачах распознавания могут возникать естественным путем. Например, такие меры сходства известны в ряде областей химии, геологии, медицины, финансового анализа. В других случаях объективное представление о сходстве объектов может отсутствовать. Практика решения задач распознавания показала, что во многих случаях указанные описания представляются гораздо более адекватными, чем признаковые. Попарные оценки сходства или различия объектов эффективно используются как в теории распознавания и прогнозирования (см. цикл [23, 24, 25], а также [21]), так и при решении конкретных прикладных задач.

Во многих задачах меры сходства вычисляются и используются только для конечного множества объектов. В практике интеллектуального анализа данных указанные задачи встречаются настолько часто, что возникла своя собственная терминология. В таком случае принято говорить о конфигурациях сходства. Если результатом попарного сравнения объектов является числовая оценка, которая интерпретируется как расстояние между этими объектами, то соответствующую конфигурацию сходства называют метрической конфигурацией.

Метрическая информация об исследуемых объектах или ситуациях распознавания может отражать важнейшие их характеристики, от выявления и использования которых зависит сам успех решения стоящих перед исследователем задач. Особо хотелось бы подчеркнуть тот факт, что далеко не во всех задачах интеллектуального анализа данных существует некоторый единственный «объективный» способ наделить пространство объектов метрикой. Справедливо утверждать, что во многих задачах сами метрические конфигурации могут быть объектами исследования и обработки. И в настоящее время уже можно говорить о появлении в распознавании образов и интеллектуальном анализе данных комплекса технических приемов, предназначенных для работы с метрическими конфигурациями. В частности, интенсивно развиваются методы их синтеза и преобразования, позволяющие проявить скрытые структуры и закономерности, присутствующие в исходных данных.

Меры сходства играют существенную роль в современной теории распознавания. Но их применение для систем классификации начиналось (как один из эвристических подходов) с самого зарождения теории распознавания. Одной из первых идей автоматического распознавания образов была классификация объектов с помощью расстояний до эталонов, или критерию минимума расстояния. В этом случае некоторое множество образцов, по одному для каждого класса, хранится в памяти машины. Распознаваемый (входной) объект сравнивается с эталоном каждого класса. Классификация основывается на заранее выбранной мере сходства — критерии соответствия или критерии подобия. Если входной объект по выбранному критерию лучше соответствует эталону некоторого класса, чем эталонам остальных классов, то этот объект классифицируется как принадлежащий этому классу. Такой подход давно используется в устройствах чтения печатных букв, банковских чеков, индексов на конвертах.

Следующей идеей стала классификация по методу ближайшего соседа [64, 79], которая заключалась в том, что анализируемый объект относился к тому классу, к одному из эталонов которого он находился ближе, чем к любому другому эталону любого класса. Такие алгоритмы обычно можно было привести к алгоритмам, основанным на принципе разделения, которые различаются главным образом заданием класса поверхностей, среди которых выбирается поверхность (или набор поверхностей), разделяющая элементы разных классов.

При построении алгоритмов, использующих информацию о расстояниях между объектами, также заслуживает особого упоминания метод потенциальных функций [2, 48]. В его основе лежит аналогия с известным физическим принципом: сила взаимодействия зависит от потенциала, создаваемого всеми объектами. На объектах различными способами вводится понятие «веса», а в качестве значения функции принадлежности объекта классу используют величину, являющуюся монотонно возрастающей функцией «веса» и монотонно убывающей функцией расстояния.

В теории распознавания важную роль играет модель алгоритмов вычисления оценок [18,19, 20], определение которой существенно опирается на понятие меры сходства. Кроме того, отметим аксиоматический подход к пострению функций близости в теории распознавания [29, 30].

Существенным разделом интеллектуального анализа данных является кластерный анализ (обучение без учителя) [84]. Подавляющее большинство используемых сегодня методов кластерного анализа тем или иным способом используют меры сходства. Необходимо отметить, что для получения хорошо интерпретируемого результата чаще всего приходиться настраивать именно меру сходства, а не метод кластеризации.

На получение удовлетворительных практических результатов при классификации с использованием мер сходства можно рассчитывать только в тех случаях, когда классы обнаруживают тенденцию к проявлению кластеризационных свойств. Примером подобного свойства может служить следующее («оптимистическое») утверждение: «для всех кластеров наибольшее расстояние между объектами внутри одного кластера меньше минимального расстояния между объектами из разных кластеров». Кластеризация необходима для точного понимания того, сколько и какие именно классы присутствуют в исходных описаниях. Но при нарушении неравенства треугольника анализ кластеризационных свойств оказывается затруднительным, а результаты их применения не оправдывают ожиданий. Например, попытка объединять в один кластер близко лежащие объекты может войти в противоречие с тем фактом, что в некоторой тройке объектов имеется две пары близких точек и одна пара далеких, что конфликтует с транзитивным отношением эквивалентности «быть в одном кластере». Неравенство треугольника нередко используется и при обосновании различных предлагаемых алгоритмов классификации и кластеризации. Эти аргументы заставляют решать не всегда простую задачу перехода от некоторых оценок близости к полноценным метрическим конфигурациям.

Среди разделов математики, изучающих свойства метрик на конечных множествах, в первую очередь следует упомянуть геометрию расстояний [60, 61]. В частности, в работах по геометрии расстояний можно встретить упоминания о пространствах нолуметрик [59]. При этом среди стандартных конструкций исследования метрических конфигураций в основном упоминаются только различные конусы таких конфигураций [55, 56, 65]. Однако развитие методов работы с метрическими конфигурациями в интеллектуальном анализе данных показало, что сами метрические конфигурации до сих пор остаются недостаточно изученными. Указанное состояние дел препятствует созданию и теоретическому обоснованию новых методов, способных глубже раскрыть метрические свойства исходных данных.

Данная работа направлена на исследование свойств метрических конфигураций, пространств метрических конфигураций и методов их представления и преобразования. Известно, что сложность решения, казалось бы, одной и той же задачи может существенно зависеть от способа представления исходных данных. В данной работе как раз и предлагаются некоторые из возможных способов представления метрических конфигураций, которые позволяют упростить процедуры их исследования и обработки.

В теории распознавании образов метрики нередко пытаются построить для пространства описаний. Но даже интуитивно не всегда понятно, какие из исходных объектов находятся ближе или дальше друг от друга. Сначала обычно легче предложить расстояния между значениями отдельных признаков. После этого, с привлечением дополнительной информации об объектах, синтезируются проблемно-ориентированные метрики на пространствах описаний объектов. Предварительным этапом таких построений часто бывает создание функций близости (мер сходства), которые строятся как приблизительные показатели сходства объектов, но не удовлетворяют всем аксиомам метрического пространства. Именно на этом шаге наиболее существенно участие специалистов-экспертов в проблемной области решаемой задачи.

Отметим, что любой набор близостей можно монотонным образом перевести в расстояния разместив последние, например, на отрезке [1,2], что автоматически гарантирует выполнение неравенства треугольника, но практически малоинтересно, т.к. уничтожает существенные для методов классификации и кластеризации метрические свойства исходной конфигурации. В данной работе предлагаются некоторые методы построения функций близости, гарантирующие выполнение аксиом метрики и допускающие содержательную интерпретацию получаемых величин сходства. При этом особое внимание уделяется вычислительной эффективности предлагаемых процедур и хорошей интерпретируемости получаемых результатов.

Особое место при обработке данных занимает построение их представления в конечномерных евклидовых пространствах. Для этих хорошо знакомых пространств разработан обширный парк различных алгоритмов. У них есть многочисленные удобные свойства, в том числе связывающие (через скалярное произведение) линейные и метрические характеристики. Понятно, что переход к таким представлениям, особенно когда на пространстве описаний построена проблемно-ориентированная метрика, нужно проводить с учетом метрических свойств исходного пространства описаний. Некоторым аспектам такого перехода и посвящена существенная часть предлагаемой работы.

В работе рассматриваются некоторые аспекты перехода к описаниям меньшей размерности. Актуальность указанного перехода обусловлена тем, что при постановке практических задач распознавания исходные описания объектов обычно включают в себя все доступные наблюдению и измерению параметры, а иногда и их комбинации. Это приводит к большим размерам описаний объектов, которые могут задаваться несколькими десятками, а то и сотнями величин. В частности, подобная ситуация часто возникает при постановке задач медицинской диагностики, геологического, технического, социологического прогнозирования и т.д. Именно это обстоятельство — большая размерность описаний — в значительной степени исключает возможность непосредственного применения методов традиционной вычислительной математики для задач распознавания и приводит к необходимости обоснованного уменьшения размерности и создания соответствующих математических конструкций.

На этапе предварительной подготовки исходных данных нередко проводят настройку метрики. Это служит не только оптимизации процедур кластеризации и классификации, но и лучшему пониманию строения пространства описаний исходных объектов. При этом над метрикой производят различные операции. Например, суперпозиция выпуклой вверх функции с функцией расстояния снова даст функцию расстояния. Для конечных метрических пространств, т.е. пространств, содержащих конечное число элементов (а именно такие нередко рассматриваются при решении задач распознавания образов), возможны операции над метриками, «подчеркивающие» те или иные метрические свойства, например, приведение метрики к состоянию, когда в ней есть вырожденные треугольники, т.е. для некоторых троек объектов неравенство треугольника переходит в равенство. Интересен и синтез метрики сразу по нескольким другим метрикам.

Результаты данной работы позволяют предложить эффективную реализацию целого ряда методов настройки метрических конфигураций.

0.3 Содержание работы

Работа состоит из введения, пяти глав и заключения.

В главе 1 даются основные определения, формулируются и доказываются утверждения, используемые во всей работе.

Основные определения и обозначения, используемые в работе для метрик и метрических конфигураций, приводятся в разделе 1.1. В разделе 1.2 описан способ погружения множества метрических конфигураций в специальное линейное векторное пространство и приведены некоторые свойства операций в этом пространстве.

В разделе 1.3 исследуется случай, когда каждая компонента некоторой метрической конфигурации одним и тем же образом зависит от соответствующих компонент некоторого набора вообще говоря других метрических конфигураций. При этом рассматривается задача поиска таких покомпонентных отображений набора метрических конфигураций в новую метрическую конфигурацию, которые гарантируют выполнение аксиом метрики для получаемой метрической конфигурации при выполнении этих аксиом для каждой метрической конфигурации набора. В разделе получены некоторые достаточные условия на искомые отображения. В частности, для того чтобы указанные условия можно было использовать при исследовании полных и неполных систем метрических конфигураций, они переформулируются в терминах неотрицательности коэффициентов линейного разложения метрической конфигурации по набору конфигураций.

Хорошо известно, что в линейной алгебре наибольшее предпочтение традиционно отдается разложению по ортогональным системам. В разделе 1.4 рассматриваются ортогональные системы в пространствах метрических конфигураций. Для того чтобы можно было использовать условия, полученные в разделе 1.3, элементы рассматриваемых базисов должны удовлетворять аксиомам метрики или полуметрики. Результаты раздела 1.4 показывают, что требования ортогональности и выполнения аксиом полуметрики в определенном смысле являются несовместимыми.

В главе 2 исследуются разложения метрических конфигураций по неполным системам метрических конфигураций.

Для того чтобы для неполных систем метрических конфигураций появилась возможность говорить о разложении произвольной метрической конфигурации, в разделе 2.1 стандартным для теории аппроксимации способом вводится понятие оптимального разложения метрической конфигурации, которое искажает заданную метрическую конфигурацию наименьшим образом [42]. Для выбора оптимального разложения пространство метрических конфигураций наделяется нормой. При этом оптимальным приближением метрической конфигурации называется метрическая конфигурация, которая имеет точное разложение по используемой системе конфигураций и это разложение совпадает с оптимальным разложением для исходной метрической конфигурации.

Особое внимание в работе уделяется исследованию оптимальных разложений метрических конфигураций, когда исходные конфигурации удовлетворяют аксиомам полуметрики или более строгим ограничениям, например, гиперметрическим неравенствам, входящим в стандартный аппарат исследования метрических конфигураций [55]. Показано, что при выполнении этих ограничений может быть получен спектр достаточных условий и критериев как па неотрицательность оптимального разложения, играющую важную роль в методах анализа метрических конфигураций, так и на сохранение или усиление указанных ограничений для оптимальных приближений [41].

В разделе 2.2 свойства оптимального разложения метрической конфигурации исследуются для системы, элементы которой могут быть ин-териретированы как отделение одного объекта распознавания от всех остальных [40]. Показано, что рассматриваемое оптимальное разложение может быть удобно интерпретировано в терминах коэффициентов разложения для отдельных объектов. Оно эффективно вычисляется и гарантировано неотрицательно для метрических конфигураций, удовлетворяющих условиям полуметрики. Неотрицательные оптимальные разложения по этой системе конфигураций и только они соответствуют оптимальным приближениям, удовлетворяющим условиям полуметрики.

В главе 3 исследуются разложения метрических конфигураций по полным системам метрических конфигураций.

При работе с метрическими конфигурациями, как элементами линейного векторного пространства, может быть поставлен вопрос о выборе базиса в этом пространстве [37, 39]. В настоящее время в подавляющем числе работ традиционно используется только «тривиальный» базис, т.е. такой базис, в котором каждая компонента представления метрической конфигурации равна расстоянию между соответствующей парой объектов. Указанный тривиальный базис состоит из единичных ортов, если компоненты метрических конфигураций рассматривать как расстояния.

Необходимо отметить, что векторы, из которых состоит тривиальный базис, не соответствуют метрическим конфигурациям, удовлетворяющим аксиомам метрики. Оказывается, указанное несоответствие существенным образом влияет на эффективность реализации процедур обработки метрических конфигураций, особенно в тех случаях, когда множество используемых метрических конфигураций ограничено какими-либо условиями. Поэтому может быть поставлена задача выбора в пространстве метрических конфигураций некоторого иного, нетривиального базиса, учитывающего условия, предъявляемые к используемым метрическим конфигурациям. В качестве таких условий в данной работе рассматриваются аксиомы метрики, равноправие всех пар объектов, соответствие конфигурации заданному рангу, а также сочетания указанных условий [44].

В качестве формального эквивалента равноправия всех пар объектов распознавания в разделе 3.1 вводится понятие гомогенной системы метрических конфигураций, каждый элемент которой по одному и тому же правилу сопоставляется каждой паре объектов распознавания. Устанавливаются необходимые и достаточные условия выполнения аксиом полуметрики и метрики для элементов гомогенных систем, а также условия их линейной независимости. Доказывается, что формулы перехода от разложения по некоторому базису к разложению по тривиальному базису имеют вид линейной комбинации усреднения расстояний по объектам и парам объектов тогда и только тогда, когда базис является гомогенной системой. При этом сложность такого перехода меньше, чем сложность перехода к разложению по произвольному базису. Для гомогенных систем дается интерпретация как коэффициентов указанного перехода, так и коэффициентов разложения произвольной метрической конфигурации. Кроме того, ставится и решается задача поиска такой гомогенной системы, которой соответствует в некотором смысле наибольшее множество метрических конфигураций, все коэффициенты разложения которых по искомой системе неотрицательны.

В разделе 3.2 вводятся ранговые базисы, в которых метрическая конфигурация имеет неотрицательное разложение тогда и только тогда, когда она имеет некоторый заданный ранг. При этом сложность перехода от разложения по тривиальному базису к разложению по ранговому базису и обратно меньше, чем сложность перехода к разложению по произвольному базису. Доказывается, что если некоторый элемент некоторого рангового базиса удовлетворяет аксиомам полуметрики, то либо он совпадает с конфигурацией, соответствующей пространству изолированных точек, либо лежит на границе множества метрических конфигураций, удовлетворяющих аксиомам полуметрики. Если же элемент рангового базиса не удовлетворяет аксиомам полуметрики, то на границе множества метрических конфигураций, удовлетворяющих аксиомам полуметрики, лежит середина отрезка, соединяющего этот элемент и конфигурацию, соответствующую пространству изолированных точек.

Полученные в разделе 3.2 результаты позволяют в разделе 3.3 перейти к иолуметрическим ранговым базисам, в которых неотрицательность разложения произвольной метрической конфигурации является достаточным условием того, что эта конфигурация одновременно удовлетворяет аксиомам полуметрики и имеет заданный ранг. Доказывается, что среди всех базисов, обладающих только что указанным свойством, иолу-метрические ранговые базисы характеризуют в некотором смысле наибольшие множества метрических конфигураций.

В главе 4 рассматривается задача представления метрической конфигурации в конечномерном евклидовом пространстве.

Среди приемов работы с метрическими конфигурациями выделяются методы их приближенного к изометрическому вложения в конечномерные евклидовы пространства. Другими словами, ставится задача поиска в конечномерном евклидовом пространстве множества точек, попарные расстояния между которыми наилучшим образом представляют исходную метрическую конфигурацию. Такое множество точек, сопоставленных объектам распознавания, можно назвать точечной конфигурацией.

В проблемах распознавания указанная задача возникает в разных контекстах. Например, данное представление позволяет при наличии метрической информации привлекать весь арсенал методов, накопленных для работы с признаковыми описаниями. Кроме того, нередко требуется получить визуальное представление, обычно двумерное, объектов, имеющих сложные метрические описания или описания в пространстве разнородных признаков большой размерности. Решение поставленной задачи позволяет получить визуальное представление, отражающее метрические свойства исходного набора объектов. Отметим, что решение задачи представления метрической конфигурации можно получить лишь с точностью до изометрического преобразования.

В разделе 4.1 задача поиска точечной конфигурации формулируется как задача минимизации функционала сравнения метрических конфигураций.

В разделе 4.2 предлагается алгоритм, который проверяет возможность точного представления заданной метрической конфигурации точками конечномерного евклидова пространства и, в случае успеха, строит соответствующую точечную конфигурацию наименьшей необходимой размерности.

В разделе 4.3 рассматривается задача поиска оптимальной проекции точечной конфигурации для конкретного функционала ошибки представления метрической конфигурации. Предлагается процедура построения оптимального представления заданного набора векторов с помощью линейного ортогонального преобразования и одновременного упорядочивания компонент.

В главе 5 рассматривается поведение ошибки представления метрической конфигурации в конечномерном евклидовом пространстве с ростом размерности представления.

Методы поиска представления метрической конфигурации в конечномерном евклидовом пространстве в литературе иногда объединяют термином многомерное шкалирование (см. [13]). Эти методы отличаются друг от друга требованиями, накладываемыми на исходную метрическую конфигурацию и получаемые представления. Существенной особенностью подавляющего большинства таких методов является то, что размерность пространства, в котором ищется представление, должна быть задана самим исследователем. И если в некоторых случаях размерность представления известна заранее (например, в случае визуализации метрической конфигурации — два или три), то в общем случае проблема выбора размерности представления требует отдельного исследования. Одним из путей такого выбора является анализ поведения ошибки представления с ростом его размерности.

В данной работе указанный анализ поведения ошибки представления проводится для одного семейства функционалов сравнения метрических конфигураций. Кроме того, проводится исследование свойств оптимальных точечных конфигураций при представлении исходных описаиий [43].

В разделе 5.1 дается определение рассматриваемого семейства функционалов сравнения метрических конфигураций. Неформально можно сказать, что функционалы данного семейства сохраняют информацию обо всех элементах исходной метрической конфигурации, как бы далеко от нее ни была другая конфигурация. В этом же разделе получены результаты о предельных размерностях оптимальных точечных конфигураций.

В разделе 5.2 формулируется и доказывается теорема об асимптотическом поведении ошибки представления с ростом размерности для рассматриваемого семейства функционалов сравнения метрических конфигураций.

В разделе 5.3 вводится функционал эффективности размерности и на модельных задачах раскрывается его смысл. Предлагается понятие эффективной размерности, которая является характеристикой метрических свойств набора объектов. Приводятся исследования и численные эксперименты, иллюстрирующие понятие эффективной размерности и подтверждающие возможность при поиске такой размерности использовать приближенные алгоритмы, более быстрые, чем алгоритмы оптимизации [38].

В разделе 5.4 приводится пример выявления эффективных размерностей для данных реального прикладного исследования.

В «Заключении» перечислены основные результаты, полученные в работе.

0.4 Благодарности

Автор выражает глубокую признательность члену-корреспонденту РАН Константину Владимировичу Рудакову за предложенную тематику и постоянное внимание к работе; академику РАН Юрию Ивановичу Журавлеву за неослабевающую поддержку на всех этапах выполнения данной работы.

Заключение

В работе рассматриваются специальные пространства метрических конфигураций, возникающие при наделении множества всех метрических конфигураций некоторой фиксированной мощности свойствами линейного векторного пространства. Исследованы методы преобразования представлений метрических конфигураций в указанных пространствах, а также методы и свойства перехода к представлениям в конечномерных евклидовых пространствах.

Основным приемом, использованным в работе, является разложение произвольной метрической конфигурации по некоторой системе метрических конфигураций. В частности, особое внимание уделено линейному разложению. Предложено перейти к представлениям метрических конфигураций коэффициентами указанного разложения.

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

Рассмотрены ортогональные системы в пространствах метрических конфигураций. Показано, что требования ортогональности и выполнения аксиом полуметрики в определенном смысле являются несовместимыми.

В работе отдельно рассмотрены полные и неполные системы метрических конфигураций.

Для работы с неполными системами метрических конфигураций введено понятие оптимального разложения метрической конфигурации. Рассмотрены свойства указанного оптимального разложения и связь такого разложения с некоторыми стандартными конструкциями исследования метрических конфигураций. Получены условия неотрицательности такого разложения.

Рассмотрены свойства указанного оптимального разложения для системы, элементы которой могут интерпретироваться как отделение одного объекта от всех остальных. При этом показана тесная связь неотрицательности такого разложения с некоторыми стандартными конструкциями исследования метрических конфигураций.

При исследовании полных систем метрических конфигураций рассмотрены три специальных параметрических семейства наборов метрических конфигураций: гомогенные, ранговые и полуметрические ранговые семейства. Установлены условия, при которых наборы из рассматриваемых семейств являются базисами в специальном линейном пространстве метрических конфигураций. Показано, что переход из представления метрической конфигурации в тривиальном базисе в ее представление в любом из рассматриваемых базисов и обратно может быть вычислен за существенно меньшее число арифметических операций, чем при работе с базисами в общем случае. Показано, что неотрицательность разложения произвольной метрической конфигурации по гомогенным и полуметрическим ранговым базисам является достаточным условием выполнения аксиом полуметрики для данной метрической конфигурации, а неотрицательность разложения по ранговому базису является необходимым и достаточным условием того, что метрическая конфигурация имеет заданный ранг. Для гомогенных базисов дана интерпретация коэффициентов перехода и компонент разложения. В рассматриваемых семействах указаны наборы, которые характеризуют конусы метрических конфигураций наибольшего объема.

Рассмотрена задача поиска в конечномерном евклидовом пространстве оптимальной точечной конфигурации, т.е. множества точек, расстояния между которыми наилучшим образом приближают заданную метрическую конфигурацию. Показано, что методы и свойства решения указанной задачи существенно зависят от того, существует ли точечная конфигурация, точно представляющая заданную метрическую конфигурацию.

Задача поиска оптимальной точечной конфигурации сформулирована как задачи минимизации функционала сравнения метрических конфигураций, использующаяся как для анализа свойств исходных описаний, так и для получения визуального представления объектов, имеющих сложные описания в пространстве разнородных признаков большой размерности.

Предложен алгоритм, который проверяет возможность точного представления заданной метрической конфигурации точками конечномерного евклидова пространства и, в случае успеха, строит соответствующую точечную конфигурацию наименьшей необходимой размерности.

Найдено оптимальное представление набора векторов в евклидовом пространстве при использовании для сравнения метрических конфигураций функционала среднеквадратичной ошибки. Показано, что оптимальная проекция исходного набора векторов на подпространство любой меньшей размерности п может быть получена, если взять только первые п компонент оптимального представления исходного набора векторов. При этом оптимальная проекция заданных векторов на подпространство любой меньшей размерности при сравнении метрических конфигураций будет давать наименьшую среднеквадратичную ошибку среди всех проекций исходного набора векторов на подпространства той же размерности. Предложена процедура построения оптимального представления заданного набора векторов с помощью линейного ортогонального преобразования и одновременного упорядочивания компонент.

Для одного естественного семейства функционалов сравнения метрических конфигураций получен верхний предел размерности пространства, в котором для любой метрической конфигурации фиксированной мощности может быть найдена оптимальная точечная конфигурация, точно или приближенно представляющая исходную метрическую конфигурацию. Показано, что если не существует точечной конфигурации, точно представляющей заданную метрическую конфигурацию, то для указанного семейства функционалов сравнения метрических конфигураций размерность пространства, в котором существует оптимальная точечная конфигурация, будет меньше размерности, необходимой в общем случае для представления метрической конфигурации заданной мощности.

Предложено понятие эффективной размерности, которая является характеристикой метрических свойств набора объектов. Проведены исследования и численные эксперименты, иллюстрирующие понятие эффективной размерности и подтверждающие возможность при поиске такой размерности использовать приближенные алгоритмы, более быстрые, чем алгоритмы оптимизации.

Выполнена программная реализация предложенных методов. Полученные теоретические выводы подтверждены серией экспериментов на модельных и реальных данных.

1. Абрамов JI. М., Капустин В. Ф. Матемтаическое программирование: Теория выпуклого программирования.— СПб.: Издательство С.-Петербургского государственного университета, 2001.— 264 с.

2. Айзерман М. А., Браверман Э. М., Розоноэр Л. И. Метод потенциальных функций в теории обучения машин. — М.: Наука, 1970. — 320 с.

3. Бонгард М. М. Проблема узнавания. — М.: Наука, 1967. — 320 с.

4. Вапник В. Н., Червоненкис А. Я. Теория распознавания образов.— М.: Наука, 1974.-418 с.

5. Васильев В. И. Распознающие системы.— Киев: Наукова думка, 1983.-466 с.

6. Воронин Ю. А. Теория классифицирования и её приложения. — Новосибирск: Наука, Сиб. отд-ние, 1985. — 232 с.

7. Воронин Ю. А. Начала теории сходства. — Новосибирск: Наука, Сиб. отд-ние, 1991. 128 с.

8. Воронцов К. В. О проблемно-ориентированной оптимизации базисов задач распознавания // ЖВМ и МФ. 1998. - Т. 38, № 5. - С. 870880.

9. Глаз А. Б. Параметрическая и структурная адаптация решающих правил в задачах распознавания. — Рига: Зинатне, 1988. — 172 с.

10. Гренадер У. Лекции по теории образов. — М.: Мир, 1979. — Т.1. 1979. 384 с.Т.2. 1981. 448 с. Т.З. 1983. 432 с.

11. Дмитриев А. И., Журавлев Ю. И., Кренделев Ф. П. О математических принципах классификации предметов и явлений // Дискретный анализ. — Новосибирск: СО РАН, 1966. — Vol. 7. — Pp. 3-17.

12. Дуда Р., Харт П. Распознавание образов и анализ сцен. — М.: Мир, 1976.-511 с.

13. Дэйвисон М. Многомерное шкалирование. — М.: Финансы и статистика, 1988. 254 с.

14. Дюкова Е. В., Песков Н. В. Поиск информативных фрагментов описаний объектов в дискретных процедурах распознавания // ЖВ-МиМФ. 2002. - Т. 42, № 5. - С. 741-753.

15. Дюкова Е. В. Дискретные (логические) процедуры распознавания: принципы конструирования, сложность реализации и основные модели. — М.: Прометей, 2003. — 29 с. — Учебное пособие для студентов математических факультетов педвузов.

16. Емеличев В. А., Ковалев М. М., Кравцов М. К. Многогранники, графы, оптимизация. — М.: Наука, 1981. — 344 с.

17. Журавлев Ю. И., Гуревич И. Б. Распознавание образов и распознавание изображений // Распознавание, классификация, прогноз. — 1989. Т. 2. - С. 5-73.

18. Журавлев Ю. И., Камилов М. М., Туляганов Ш. Е. Алгоритмы вычисления оценок и их применение. — Ташкент: ФАН, 1974. — 119 с.

19. Журавлев Ю. И., Мирошник С. Н., Швартин С. М. Об одном подходе к оптимизации в классе параметрических алгоритмов распознавания // ЖВМ и МФ. 1976. - Т. 16, № 1. — С. 209-218.

20. Журавлев Ю. И., Никифоров В. В. Алгоритмы распознавания, основанные на вычислении оценок // Кибернетика. — 1971.— К2 3.— С. 1-11.

21. Журавлев Ю. И., Рудаков К. В. Об алгебраической коррекции процедур обработки (преобразования) информации // Проблемы прикладной математики и информатики. Сб. статей. / Под ред. О. Бе-лоцерковский и др. — М.: Наука, 1987.— С. 187-198.

22. Журавлев Ю. И. Об алгебраических методах в задачах распознавания и классификации // Распознавание, классификация, прогноз. — 1988.-Т. 1.-С. 9-16.

23. Журавлёв Ю. И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. Часть I // Кибернетика. — 1977. — № 4. С. 5-17.

24. Журавлёв Ю. И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. Часть II // Кибернетика.— 1977. — № 6.-С. 21-27.

25. Журавлёв Ю. И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. Часть III // Кибернетика. — 1978. № 2. - С. 35-43.

26. Журавлёв Ю. И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики. Выи. 33. — М.: Наука, 1978.-С. 5-68.

27. Загоруйко Н. Г., Елкина В. Н., Лбов Г. С. Алгоритмы обнаружения эмпирических закономерностей. — Новосибирск: Наука, 1985. — 110 с.

28. Загоруйко Н. Г. Методы распознавания и их применение. — М.: Советское радио, 1972.— 119 с.

29. Кочетков Д. В. О функциях близости: Сообщение по прикладной математике: Вычислительный центр АН СССР, 1978.

30. Кочетков Д. В. Построение алгоритма вычисления расстояний для одного класса метрических пространств: Сообщение по прикладной математике: Вычислительный центр АН СССР, 1978.

31. Лбов Г. С. Методы обработки разнотипных экспериментальных данных. — Новосибирск: Наука, 1981.— 160 с.

32. Мазуров В. Д. Об одном методе обучения узнаванию // Кибернетика. 1970. - № 2. - С. 92-94.

33. Мазуров В. Д. Комитеты систем неравенств и задача распознавания // Кибернетика. — 1971. — № 3. — С. 140-146.

34. Майсурадзе А. И. О выборе размерностей евклидовых представлений метрических описаний прецедентов // Математические методы распознавания образов: доклады IX Всероссийской конференции. — М.: Вычислительный центр РАН, 1999. — С. 74-75.

35. Майсурадзе А. И. Об эффективном выборе размерностей представлений метрических конфигураций в евклидовых пространствах //

36. Интеллектуализация обработки информации: тезисы докладов Международной научной конференции. — Симферополь: Крымский научный центр НАН Украины, Таврический национальный университет, 2000. С. 48.

37. Майсурадзе А. И. О некоторых нетривиальных базисах в пространствах метрических конфигураций // Математические методы распознавания образов: доклады X Всероссийской конференции.— М.: Вычислительный центр РАН, 2001.- С. 87-90.

38. Майсурадзе А. И. Об оптимальном разложении по одной системе метрических конфигураций // Искусственный Интеллект.— 2004. № 2. - С. 129-133.

39. Майсурадзе А. И. Об оптимальных разложениях конечных метрических конфигураций в задачах распознавания образов // ЖВМ и МФ. 2004. - Т. 44, № 9. - С. 1697-1707.

40. Майсурадзе А. И. О свойствах оптимальных точечных конфигураций для одного семейства функционалов сравнения метрических конфигураций // ЖВМ и МФ. 2005. - Т. 45, № 9. - С. 1741-1748.

41. Майсурадзе А. И. Гомогенные и рагновые базисы в пространствах метрических конфигураций // ЖВМ и МФ. — 2006. — Т. 46, № 2. — С. 344-361.

42. Нильсон Н. Искусственный интеллект. Методы поиска решений.— М.: Мир, 1973.-272 с.

43. Патрик Э. Основы теории распознавания образов. — М.: Советское радио, 1980. 408 с.

44. Рудаков К. В. Полнота и универсальные ограничения в проблеме коррекции эвристических алгоритмов классификации // Кибернетика. 1987. - № 3. - С. 106-109.

45. Рудаков К. В. Симметрические и функциональные ограничения в проблеме коррекции эвристических алгоритмов классификации // Кибернетика. 1987. - № 4. - С. 73-77.

46. Рудаков К. В. Универсальные и локальные ограничения в проблеме коррекции эвристических алгоритмов // Кибернетика. — 1987. — № 2. С. 30-35.

47. Себастьян Г. С. Процессы принятия решений при распознавании образов. — Киев: Техника, 1965. — 151 с.

48. Тылкин М. Е. О геометрии Хэминга единичных кубов // Доклады АН СССР. 1960. - Т. 134. - С. 1037-1040.

49. Blumenthal L. M. Theory and Applications of Distance Geometry (Second Edition). New York: Chelsea, 1970. - 347 pp. Breiman L. Bagging predictors // Machine Learning. — 1996. — Vol. 24, no. 2. - Pp. 123-140.

50. Cayley On a theorem in the geometry of position // Cambridge

51. Mathematical Journal. 1841. — Vol. II. — Pp. 267-271.

52. Devroye L., Gyorfi L., Krzyzak A., Lugosi G. On the strong universalconsistency of nearest neighbor regression function estimates // Annalsof Statistics. 1994. - no. 22. - Pp. 1371-1385.

53. Deza M., Dutour M. Data mining for cones of metrics, quasi-metrics,hemi-metrics, and super-metrics. — Paris: ENS, 2002.

54. Deza M., Laurent M. Geometry of Cuts and Metrics. — Berlin: Springer

55. Verlag, 1997.— 736 pp.— Имеется перевод: M. Деза и М. Лоран,

56. Геометрия разрезов и метрик, М.: МЦНМО, 2001.

57. De Leeuw J., Heiser W. Theory of multidimensional scaling //

58. Handbook of Statistics 2: Classification, Pattern Recognition and

59. Reduction of Dimensionality / Ed. by P. R. Krishnaiah, L. N. Kanal. —

60. Amsterdam: North-Holland, 1982. Vol. 2. - Pp. 285-316.

61. Djukova E. V., Inyakin A. S., Peskov N. V. Methods of combinatorialanalysis in synthesis of efficient recognition algorithms // Pattern

62. Recognition and Image Analysis. — 2003. — Vol. 13, no. 3. — Pp. 426432.

63. Draper N. R., Smith H. Applied Regression Analysis.— New York: Wiley, 1981.— Имеется перевод: Дрейпер H., Смит Г., Прикладной регрессионный анализ (кн. 1,2), М.: Финансы и статистика,1986.

64. Fichet В. The role played by L\ in data analysis // Statistical Data Analysis Based on the Li-Norm and Related Methods / Ed. by Y. Dodge. — North-Holland, Amsterdam: Elsevier Science Publishers,1987.-Pp. 185-193.

65. Freund Y. Boosting a weak learning algorithm by majority // COLT: Proceedings of the Workshop on Computational Learning Theory.— Morgan Kaufmann Publishers, 1990.

66. Fukunaga K. Introduction to Statistical Pattern Recognition (Second Edition). — New York: Academic Press, 1990.

67. Fu K. S. Sequential Methods in Pattern Recognition and Machine Learning. — New York: Academic Press, 1968. — Имеется перевод: Фу К., Последовательные методы в распознавании образов и обучении машин, М.: Наука, 1971, 256 с.

68. Golub G., Loan С. V. Matrix Computations.— London: The John Hopkins University Press, 1989.— 548 pp.— Имеется перевод: Голуб Дж., Ван Лоун Ч., Матричные вычисления, М.: Мир, 1999.

69. Kahaner D., Moler С., Nash S. Numerical Methods and Software.— Prentice-Hall International, Inc., 1989.— 575 pp. — Имеется перевод: Каханер Д., Моулер К., Нэш С., Численные методы и программное обеспечение, М.: Мир, 2001.

70. Lawley D. N., Maxwell А. Е. Factor Analysis as a Statistical Method.— London: Butterworths, 1963.— 145 pp. — Имеется перевод: Лоули Д., Максвелл А., Факторный анализ как статистический метод, М.: Мир, 1967.

71. Мепдег К. Untersuchungen iiber allgmeine metrik // Mathematische Annalen. 1928. - Vol. 100. - Pp. 75-163.

72. Menger К. New foundation of euclidean geometry // American Journal of Mathematics. 1931. - Vol. 53. - Pp. 721-745.

73. Mullin M., Sukthankar R. Complete cross-validation for nearest neighbor classifiers // Proceedings of International Conference on Machine Learning. 2000.

74. Nagata J. Modern dimension theory.— New York: Interscience Publishers, 1965.— 259 pp.— Bibliotheca mathematica, a series of monographs on pure and applied mathematics, v. 6.

75. Schapire R. E. Theoretical views of boosting and applications // Algorithmic Learning Theory, 10th International Conference, ALT '99, Tokyo, Japan, December 1999, Proceedings.— Vol. 1720.— Springer, 1999.-Pp. 13-25.

76. Schoenberg I. J. Remarks to Maurice Frechet article «Sur la definition axiomatique d'une classe d'espace distancies vectoriellement applicable sur l'espace de Hilbert» // Annals of Mathematics. — 1935. — Vol. 36. — Pp. 724-732.

77. Schoenberg I. J. On certain metric spaces arising from Euclidean spaces by a change of metric and their imbedding in Hilbert space // Annals of Mathematics. 1937. - Vol. 38. - Pp. 787-793.

78. Teodoridis S., Koutroumbas K. Pattern Recognition (Second Edition). — USA: Elsevier Academic Press, 2003. 707 pp.

79. Той J. Т., Gonzalez R. C. Pattern Recognition Principles.— New York: Addison-Wesley, 1974.— Имеется перевод: Ту Дж., Гонсалес Р., Принципы распознавания образов, М.: Мир, 1978, 416 с.

80. Wells J. Н., Williams L. R. Embeddings and Extensions in Analysis. — Berlin: Springer-Verlag, 1975. — 108 pp.