О специальных представлениях метрических конфигураций тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Майсурадзе, Арчил Ивериевич

• Майсурадзе, Арчил Ивериевич
• кандидат физико-математических наук
• 2005

Оглавление диссертации кандидат физико-математических наук Майсурадзе, Арчил Ивериевич

Введение

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 Благодарности

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

Заключение диссертации по теме «Теоретические основы информатики», Майсурадзе, Арчил Ивериевич

Заключение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Майсурадзе, Арчил Ивериевич, 2005 год

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.