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

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

004616949

ИОФИНА ГАЛИНА ВЛАДИМИРОВНА

ВЫБОР ОПТИМАЛЬНЫХ МЕТРИК

В ЗАДАЧАХ РАСПОЗНАВАНИЯ С ПОРЯДКОВЫМИ ПРИЗНАКАМИ

05.13.17 — теоретические основы информатики

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

- 9 ДЕК 2010

Москва, 2010

004616940

Работа выполнена в Московском физико-техническом институте (государственном университете)

Научный руководитель: доктор физико-математических наук,

академик РАН

Юрий Иванович Журавлёв

Официальные оппоненты: доктор физико-математических наук

Олег Валентинович Сенько

кандидат физико-математических наук Андрей Сергеевич Инякин

Ведущая организация: Научно-исследовательский институт

системных исследований РАН

Защита диссертации состоится « » 2010 г. в

на заседании диссертационного совета Д 002.017.02 в Учреждении Российской академии наук Вычислительный центр им. А. А. Дородницына РАН по адресу: 119333, г. Москва, ул. Вавилова, д. 40.

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

Автореферат разослан « 2010 г.

Учёный секретарь диссертационного совета Д002.017.02, д.ф.-м.н., профессор

В. В. Рязанов

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

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

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

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

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

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

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

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

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

ча поиска метрики, которая обеспечила бы регулярность задачи распознавания с порядковыми признаками (т. е. в задаче распознавания должны были выполняться три естественных условия:

1) множества эталонов каждого из классов попарно различны,

2) в контрольной выборке нет ни одной пары объектов, неразличимых относительно эталонов, 3) обучающая и контрольная выборки не пересекаются).

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

Методы исследования. В исследовании использовались комбинаторные рассуждения, методы теории графов, линейной алгебры, оптимизации, теории сложности. При изучении корректности моделей ABO использовались методы и подходы алгебраического подхода к решению задач распознавания, разработанные Ю.И. Журавлёвым, К. В. Рудаковым, B.JI. Матросовым, А. Г. Дьяконовым и др. Эксперименты проводились с использованием программного продукта Matlab.

На защиту выносятся следующие результаты, полученные для задачи распознавания с порядковыми признаками:

1. Представлен метод поиска наилучшей функции расстояния,

удовлетворяющей условию порядка и не удовлетворяющей неравенству треугольника.

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

3. Найдены всевозможные полуметрики в пространстве с суммой по модулю N для N = 1,2,..., 7, и сформулирован ряд теорем, справедливых для произвольных N.

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

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

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

Апробация работы. Результаты работы неоднократно докладывались на научных семинарах К. В. Рудакова и на конферен-

циях:

— научные конференции МФТИ, 2006-2009 гг. [1,3,8,12];

— всероссийских конференциях «Математические методы распознавания образов» ММРО-13 (2007) и ММРО-14 (2009) [2,11];

— международная конференция «Интеллектуализация обработки информации» ИОИ-7 (2008) [6].

— международные конференции студентов, аспирантов и молодых ученых «Ломоносов-2008», «Ломоносов-2010» [4,14];

Публикации. Результаты работы изложены в статье «Журнала вычислительной математики и математической физики» [13], двух статьях журнала «Pattern Recognition and Image Analysis» [10,15], двух статьях сборника «Моделирование процессов обработки информации» [5, 9], статье журнала «Таврический вестник» [7], а также в трудах конференций [1-4,6,8,11,12,14] (всего 15 публикаций, из которых три из списка ВАК). Описания отдельных результатов работы включались в научные отчеты по проектам РФФИ, № 08-01-00636 и №08-01-00405.

Структура и объём работы. Работа состоит из оглавления, введения, четырёх глав, заключения и списка литературы (82 пункта).

Общий объём работы —105 стр.

Краткое содержание работы по главам

В автореферате сохранена нумерация основных утверждений (определений, лемм, теорем и их следствий), принятая в тексте работы. Нумерация формул сквозная.

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

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

В §1.1 рассмотрена задача классификации с двумя классами. Дано множество объектов {S1,... , S™1} из класса Кг , и ..., Smi+m2} из класса Каждый объект принадлежит признаковому пространству размерности п. Значения признаков принадлежат конечному множеству EN= {0,1,..., N—1}, в котором задано отношение порядка 1.

На каждом признаке задана своя функция расстояния, которая удовлетворяет всем аксиомам метрики кроме неравенства треугольника. То есть функция р(х, у) : EN х EN -» Ем удовлетворяет следующим условиям:

1. р(х,у) = 0&х = у,

2. р(х,у)=р(у,х),

3. х^у^ р(х, z) ^ р(у, z), р{х, z) ^ р{х, у), Vz eEN,z^ у.

Последнее условие будем называть условием порядка.

Так как множество определения функции EN х EN ограничено, то функцию р{х,у) можно представить как матрицу попарных расстояний элементов множества Ем. Занумеруем зна-

чения функции расстояния на парах (г, ¿) следующим образом:

/ о

XI

Хг

О

Х2

XX

Хз

1

Хм-1 Х2ЛГ-4 Хзы-Ь \xjv-l Ж2ЛГ-3 ^ЗЛГ-б Я-Ш-Ю

^ЛГ-1 \

О )

причем условие порядка записывается в виде:

XI ^ ... ^

глг ^ ■ ■ • < £2лг-з,

£2 ^ Ждг,

хз ^ ^ Ж2лг-2,

2

АГ(]У-1)

хк Е Ем\{0}, /с = 1,..., —2"

Видно, что функция расстояния определяется ЛГ(ЛГ — 1)/2 числами. Поэтому она представляется вектором размерности ]\Г(ЛГ — 1)/2. Признаки считаются попарно независимыми, поэтому в этом параграфе ищется функция расстояния на одном признаке.

Если обозначить количество нулей, единиц, двоек, троек и так далее среди значений признака объектов из первого класса через • • )£лг-1 соответственно, то количество сравнивае-

мых пар при попарном сравнении объектов из первого класса (г, можно представить в виде матрицы:

Ах

&& €1&

£лг-1(Слг-1-1)

\Sofrv-i £14лг-1 1

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

Аналогично, если количество нулей, единиц, двоек, троек и так далее среди значений признака объектов из второго класса обозначить через щ, щ,..., ?7лг_1 соответственно, то матрицу А2 можно записать как:

¿2 =

/ 40(40-1) 2

пот

ПО Ц2

пот 2

тп2

т/042

тп2 (>12-1)

2

тчдг-1

Ч2ЧЛГ-1

г

\mw-i тчат- 1 тпы-г • •• у-' -у

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

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

Аналогично можно записать матрицу коэффициентов межклассовых расстояний:

/ *)оСо 40С1 + С01 т)о?2 + Ьт ■ ■ ■ + Сочлг-Л

тю&+€от т(1 т& + £т2 ■■■

П0& + С0Ч2 тЬ + &П2 П2& ■ ■ ■ Т12&-1 +

+ ш£лг-1 + ?1»7АГ-1 П2Ы-1 + ?2??ЛГ-1 •■• ЧЛГ-1?ЛГ-1 У

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

«1 = 1М £

,■5*4

а2 = 1/Н2 £

ХтМгЛи

.....N-1

где N1 и Л<2 — нормировочные множители.

Для межклассового расстояния, аналогично имеем

¡3 = 1/ N0 £ + Г]г&),

где N0 — нормировочный множитель.

Рассматривается критерий максимизации взвешенной разницы межклассового и среднего внутриклассового расстояний, т. е. максимизируется величина /3 — 0.5А(а!1 + аг)-

Таким образом, исходная задача может быть представлена в виде

в — 0.5Л(а! + а2) -> шах

1 ^ хк < М - 1, к = 1,..., N(N - 1)/2 хь — удовлетворяют условию порядка хь — целое

Здесь Л можно рассматривать как отношение весов межклассового и среднего внутриклассового расстояний соответственно, а Хк = хТ1, где

к = • -+(ЛГ-г)+*-г = №-1-г)г/2+г-г,Чг ^ г.

Так как а^, а2, и /3 линейны по хти по которым происходит оптимизация, то имеем задачу целочисленного линейного программирования :

N(N-1)/2

У] 7кХк Шах

^ хьЬ=1.....N{N-1)12

1 ^ Хк ^ м - 1, к = 1,..., ДГ(ЛГ - 1)/2 — удовлетворяют условию порядка Хк— целое

где 7fc = 1/NoterVt + VrZt) ~ 0-5X/N^S - 0.5\/N2Vr7]t, к = (2N ~ 1 — r)r/2 + t — r, Vr ^ t — соответствующие коэффициенты.

Для данного критерия доказано, что для нахождения оптимальных функций расстояния достаточно рассматривать только матрицы, состоящие из чисел 1 и М — 1 и решать задачу линейного программирования (вместо задачи целочисленного программирования), т.е. справедлива

Теорема 1.1. Решением оптимизационной задачи

' N(N-1)/2

min ^ Хк ^ max, к = 1,.. .,N(N — 1)/2, хк — удовлетворяют условию порядка для действительных ж* могут являться только векторы 6 =

(bi,..., Ьлг(лг_1)/2), в которых Ьк = min или bк — max, Vfc =

, N(N-l) I, ... , 2

Для оценки сложности задачи получено число матриц расстояний размерности N:

Теорема 1.2. Число матриц функций расстояний размерности N, удовлетворяющих условию порядка, можно представить следующей рекуррентной формулой (через числа Каталана):

f(N) =f(0)f(N - l)+f(l)f(N - 2)+. ..+f(N - l)/(0) =

к—0

/(0) = 1~ /(1) = 1. Или в явной форме данную величину можно представить как:

т =

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

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

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

В ABO расстояния между объектами определяются с помощью функций близости. В работе используется следующая функция близости для объектов Su и St.

(1, если число невыполненных неравенств в системе {pi(SÍ, S¡) < e¿, i = 1,..., /} не больше е;

О, в противном случае,

где ¿D — характеристический вектор, соответствующий опорному множеству (подмножеству множества признаков), — метрика в множестве значений г-го признака, — точность измерения i-го признака, е — минимальное число невыполненных неравенств.

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

Определение 1.13. Метрической характеристикой признака i алгоритма ABO называется пара {/л, £{} (функция расстояния на признаке и соответствующий порог).

Определение 1.14. Будем говорить, что метрические характеристики признаков s и г эквивалентны относительно задачи распознавания Z, если при их использовании в ABO алгоритмы APsí£s и ЛРг^Т дают одинаковые результаты для всех

объектов контрольной выборки, то есть для всех Su, и = 1,..., q выполняются равенства APs¡£s(Su) = APr¿r(Su).

Если es — £r — ё, то будем говорить об эквивалентности метрик.

Было показано, что справедлива следующая

Теорема 1.4. Пусть для решения задачи распознавания с порядковыми признаками Z при использовании ABO с фиксированными параметрами метрические характеристики {/9¿,e¿}, i = 1,..., в также фиксированы. Тогда справедливы следующие утверждения:

1. Если £i = 0 или £i ^ Mi - 1, то все метрики p¿ эквивалентны относительно задачи распознавания Z.

2. Если 0 < £i < Mi - 1, то существует метрика р*: ENi х ENi —> {0,1,2} такая, что метрические характеристики {Pí,£í} и {р*, 1} эквивалентны относительно задачи Z.

Таким образом, без ограничения общности, можно использовать только метрики, принимающие значения из множества {0,1,2}.

В §1.4 рассмотрен случай, когда в задаче классификации признаки заданы на множестве EN = {0,1,... ,N — 1} с естественным отношением порядка — 1 и, кроме того, в пространстве EN задана операция © — сложение по модулю N. Рассмотрена задача поиска всех полуметрик, то есть функций от двух аргументов, удовлетворяющих всем аксиомам полуметрик с операцией сумма по модулю N в неравенстве треугольника.

В начале параграфа дана постановка задачи, и получены утверждения, верные для случаев произвольных размерностей N. Далее по-отдельности рассмотрены случаи размерностей t =

1,2,3,4,5,6,7. Для каждого случая доказывалась теорема о том, что все матрицы, удовлетворяющие некоторым условиям, являются полу метриками; либо, что полуметрик, удовлетворяющих данным условиям, нет; либо давался метод определения является ли рассматриваемая матрица полуметрикой в данном пространстве.

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

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

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

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

парных расстояний задает в евклидовом пространстве несколько правильных симплексов с единичными ребрами. Все вершины двух разных симплексов находятся на расстояниях М — 1 друг от друга. Получено, что число таких матриц размерности N при М ^ 4 равно ¡(И) = 6 • 2мпри М ^ 3 равно

т = Ш

В §2.2 рассмотрена задача вложения найденных матриц расстояния А = {а^} размером N х N в евклидово пространство размерности Ь. То есть решена задача поиска точек (векторов) в евклидовом пространстве размерности ¿, которые дают те же расстояния, что и значения порядковых признаков в матрице расстояний. На основе модели Торгенсона был сформулирован критерий возможности погружения.

В §2.3 рассмотрена задача оценки размерности евклидова пространства, в которое можно поместить объекты задачи распознавания, располагающиеся на заданных матрицей А = {а^} расстояниях. Таким образом, объекты помещались в евклидово пространство на расстояниях равных единице либо М — 1 друг от друга, и так, чтобы они образовывали кластерную структуру.

Для случаев малых размерностей £ = 1,2,3 были построены все возможные конфигурации. Для случая евклидова пространства произвольной размерности £ было найдено максимальное число объектов, которые можно в него поместить при выполнении всех условий на расстояния.

Теорема 2.4. Пусть в матрице попарных расстояний А недиагональные элементы принимают значения из множества {1, М— 1}, и выполнены все аксиомы метрики и условие порядка. Тогда, если точки можно поместить в пространство размерности I согласно матрице попарных расстояний А, то число точек не может превышать 21

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

Следствие 2.1. Размерность пространства t, требуемая для размещения N произвольных точек на расстояниях, удовлетворяющих условию порядка, находится в интервале (N/2], N - 1].

Глава 3. Выбор метрик в алгебраических замыканиях модели ABO

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

В §3.1 дана постановка задачи и основные определения, введённые Ю.И. Журавлёвым, B.JI. Матросовым, А.Г. Дьяконовым и другими исследователями. Приведены некоторые результаты, полученные ранее другими авторами и используемые в дальнейшем.

В §3.2 найдены условия регулярности задачи распознавания с порядковыми признаками при выборе фиксированных метрик на признаках. Рассуждения построены на понятии полной разделимости объектов по признаку, т.е. возможности каждому значению признака взаимнооднозначно сопоставить строку подматрицы R = ((pi(Sj, Si),.. .,pn(Sj, 5¿)))Lii=i' соответствующую этому признаку. Была получена

Теорема 3.3. Пусть в задаче осуществлено деление на подгруппы по полностью делящимся признакам. Тогда задача регулярна (а модель U(В*) корректна) тогда и только тогда, когда на множествах Si х ti,... ,sr х tr неполностью делящихся при-

знаков можно задать метрику так, чтобы в каждой подгруппе были различные векторы (здесь Sj, tj — числа различных значений j-то признака в объектах из обучающей и контрольной выборок).

Рассмотрены как случай произвольных метрик на признаках, так и случай функций расстояния, удовлетворяющих условию порядка (являющихся также метриками из-за ограниченности множеством {0,1,2} её значений). Условия регулярности согласно критерию корректности были эквивалентны условию корректности задач распознавания.

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

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

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

В § 3.4 рассмотрен частный случай алгебраического замыкания — алгебраическое замыкание наименьшей степени — линейное замыкание модели ABO. Получены критерии корректности линейного замыкания ABO при возможности выбора функций расстояния на порядковых признаках. Отдельно рассмотрены случаи задач распознавания с непересекающимися и пересекающимися классами, а также при выборе метрик из произвольного множества допустимых метрик (со значениями из ограниченного множества {0,1,2}) и при выборе метрик из множества функций расстояния, удовлетворяющих условию порядка.

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

Глава 4. Эксперименты

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

В § 4.1 представлена серия модельных примеров, сравнива-

ющих качество работы алгоритма ближайшего соседа при использовании различных функций расстояния. В § 4.2 показаны результаты экспериментов с реальными задачами из репозито-рия UCI: breast cancer Wisconsin, саг, iris, wine, glass, ionosphere.

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

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

[1] Иофина Г. В. Выбор наилучшей метрики в алгоритме распознавания по ближайшему соседу // Сборник трудов 49-й научной конференции МФТИ. -М.: МФТИ, 2006.-С. 266-267.

[2] Иофина Г. В., Кропотов Д. А. Поиск оптимальной метрики в задачах классификации с порядковыми признаками // Докл. всеросс. конф. Математические методы распознавания образов-13.-М.: МАКС Пресс, 2007.-С. 137-140.

[3] Иофина Г. В. Оптимизация метрик для порядковых признаков в задачах распознавания // Сборник трудов 50-й научной конференции МФТИ. — М.: МФТИ, 2007.-С. 98-100.

[4] Иофина Г. В., Ветров Д. П., Кропотов Д. А. Восстановление объектов в евклидовом пространстве по оптимальной метрике в задаче распознавания образов с порядковыми признаками // Ломоносов-2008: Материалы конф. — М.: Издательский отдел факультета ВмиК МГУ, 2008. — С. 38.

[5] Иофина Г. В., Ветров Д. П., Кропотов Д. А. Восстановление объектов в евклидовом пространстве по оптимальным матрицам близости // Моделирование процессов обработки информации.-М.: МФТИ, 2008.-С. 110-114.

[6] Иофина Г. В. Многомерное шкалирование в случае матриц попарных расстояний с элементами из конечного множества //

Интеллектуализация обработки информации: Тезисы докл.— Симферополь, 2008.-С. 112-113.

[7] Иофина Г. В. Многомерное шкалирование в случае матриц попарных расстояний с элементами из конечного множества // Таврический вестник информатики и математики. — 2008. — № 1.-С. 223-230.

[8] Иофина Г. В. Оптимизация алгоритмов вычисления оценок по метрикам на признаковых описаниях объектов // Сборник трудов 51-й научной конференции МФТИ. — М.: МФТИ, 2008. — С. 39-42.

[9] Иофина Г. В. Эквивалентные метрики в алгоритмах вычисления оценок в задачах с порядковыми признаками // Моделирование процессов обработки информации. — М.: МФТИ, 2009.— С. 65-69.

[10] G. V. Iofina Optimal Metrics in Classification Problems with Ordered Features and an Arbitrary Number of Classes // Pattern Recognition and Image Analysis.— 2009.— Vol. 19, no. 2.— Pp. 284-288.

[11] Иофина Г. В. Критерии корректности алгебраического замыкания модели ABO в задачах с порядковыми признаками //Докл. всеросс. конф. Математические методы распознавания образов-14.-М.: МАКС Пресс, 2009.-С. 37-41.

[12] Иофина Г. В. Критерии корректности алгебраического замыкания модели ABO при варьировании метрик на признаках // Сборник трудов 52-й научной конференции МФТИ. — М.: МФТИ, 2009.-С. 67-70.

[13] Иофина Г. В. Поиск оптимальной метрики в задачах классификации с порядковыми признаками // ЖВМ и МФ.— 2010. — Т. 50, № 3. - С. 585-592.

[14] Иофина Г. В. Условия корректности линейного замыкания модели ABO // Ломоносов-2010: Материалы конф. — М.: Издатель-

ский отдел факультета ВмиК МГУ, 2010. —С. 85-86. [15] G. V. Iofina A Study of Metrics in Finite Sets for Application in Classification and Recognition Problems // Pattern Recognition and Image Analysis.-2010.-Vol. 20, no. 4.-Pp. 238-246.

Подписано в печать:

18.11.2010

Заказ № 4569 Тираж - 100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

Введение

0.1 Роль метрик в задачах анализа данных.

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

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

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

1.1.1 Обозначения.

1.1.2 Некоторые свойства функций расстояния

1.1.3 Критерии оптимальности.

1.1.4 Линейный критерий.

1.2 Линейный критерий выбора функций расстояния в задаче классификации с I классами.

1.2.1 Обозначения.

1.2.2 Некоторые операции над матрицами.

1.2.3 Линейный критерий для случая I классов.

1.2.4 Объединение различных метрик по признакам.

1.3 Минимизация ошибки в алгоритмах вычисления оценок.

1.3.1 Структура ABO.

1.3.2 Эквивалентность метрических характеристик.

1.3.3 Критерий минимизации ошибки ABO.

1.4 Функции расстояния с суммой по модулю N.

1.4.1 Общие утверждения.

1.4.2 Случаи N = 1,2,., 5.

1.4.3 Случай N =

1.4.4 Случай N = 7.

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

2.1 Преобразование порядковых признаков в евклидовы.

2.1.1 Случай существования точного решения.

2.1.2 Общий вид матриц расстояний с выполненными условием порядка и неравенством треугольника.

2.1.3 Необходимое и достаточное условие существования точного решения

2.2 Оценка размерности евклидова пространства, в которое можно поместить объекты задачи распознавания.

3 Выбор метрик в алгебраических замыканиях модели ABO

3.1 Алгебраический подход к задаче распознавания.

3.2 "Условие регулярности задачи распознавания с порядковыми признаками

3.2.1 Регулярность задачи распознавания при выборе метрик на признаках

3.2.2 Регулярность задачи распознавания при выполнении условия порядка.

3.3 Корректность алгебраического замыкания в случае выбора метрик на признаках из ограниченного множества метрик.

3.4 Корректность линейного замыкания в случае выбора метрик на признаках

3.4.1 Корректность линейного замыкания ABO в задачах распознавания с непересекающимися классами

3.4.2 Корректность линейного замыкания ABO в задачах распознавания с пересекающимися классами.

3.4.3 Корректность линейного замыкания ABO в задачах распознавания с порядковыми признаками при выполнении условия порядка

3.5 Оценка минимальной степени корректного алгебраического замыкания ABO.

4 Эксперименты

4.1 Модельные задачи.

4.1.1 Выводы.

4.2 Эксперименты на реальных данных.

4.2.1 Выбор коэффициента А.

4.2.2 Выбор коэффициентов в ABO.

4.2.3 Результаты.

4.2.4 Выводы.

0.1 Роль метрик в задачах анализа данных

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

Наиболее активно использование математического определения метрики (т. е. функции р(х,у), действующей в пространстве X х X и принимающей значения во множество действительных чисел, неотрицательной, причем р(х,у) = 0 выполняется тогда и только тогда, когда х = у, симметричной, и удовлетворяющей неравенству треугольника р(х, у) < р(х, z) + p(z, у)) и метрического пространства (X, р) началось столетие назад М. Фрехетом и Ф. Хаусдорфом как частного случая ограниченного топологического пространства. Условие «неравенства треугольника» возникло еще раньше, у Евклида. Бесконечные метрические пространства рассматриваются обычно как обобщения метрики \х — у\ над действительными числами. Pix основные классы это измеримые пространства (добавляется мера) и Банаховы пространства (добавляется норма и полнота) [47, 65].

Начиная с К. Менгера и, главным образом, JL М. Блюменталя, особый интерес привлекли к себе конечные метрические пространства. В настоящее время конечные метрики стали главным инструментом во многих областях математики и ее приложений, включая геометрию, теорию вероятности, статистику, криптографию и теорию графов, кластеризацию, распознавание образов, информационные сети, инженерию, компьютерную графику и компьютерное зрение, астрономию, космологию, молекулярную биологию, и многие другие области науки [70, 63]. Часто одни и те же метрики возникают независимо в нескольких различных областях, например, метрика редактирования между словами, эволюционное расстояние в биологии, метрика Левенстейна в теории кодирования [70].

Метрики часто используются в задачах интеллектуального анализа данных (англ. Data Mining) — выявлении скрытых закономерностей или взаимосвязей между переменными в больших массивах необработанных данных. В литературе приводятся различные множества решаемых задач интеллектуального анализа данных [46, 49, 27], однако наиболее часто рассматриваются задачи классификации (отнесение входного вектора (объекта, события, наблюдения) к одному из заранее известных классов) и кластеризации (разделение множества входных векторов на группы похожих объектов).

Задачи классификации и кластеризации встречаются в различных областях человеческой деятельности: геологии, экономике, медицине, химии, финансах и т.д. Для задач классификации характерно «обучение с учителем», при котором построение алгоритма (отнесение объектов к классам) производится по обучающей выборке. Для задач кластеризации применяется «обучение без учителя», при котором построение модели производится по выборке, в которой нет выходного параметра [8].

Для решения данных задач существует множество различных алгоритмов [13, 25, 28]. Например, для решения задач классификации (или распознавания) используются алгоритмы, основанные на принципе разделяющих плоскостей [25], статистические алгоритмы [13], нейронные сети [58], метрические алгоритмы. [6], [51] алгоритмы вычисления оценок [20], алгоритмы, основанные на поиске закономерностей [7] и другие. Для решения задач кластеризации (или таксономии) это иерархическая кластеризация [6], метод ¿-средних [25], нейронные сети Кохонена [58], алгоритмы класса РСЖЕЬ, динамическая таксономия [27] и другие.

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

В метрических алгоритмах «мера сходства» («расстояние») определяет величину близости пары объектов либо определяет сам факт близости. Определения и свойства функции расстояния для объектов могут сильно различаться [70, 63, 79]. Обычно берут такие функции р на парах значений (х,у), что они удовлетворяют аксиомам метрики либо их модификациям.

Результат работы алгоритмов классификации и кластеризации сильно зависит от метрик, заданных на объектах. Особо важно выбрать правильную функцию близости в задачах кластеризации [27, 49]. Поэтому обычно проводят предобработку данных существующими или специально разрабатываемыми методами [29, 82]. Часто решаются задачи выбора пли построения оптимальных метрик (или их параметров) на объектах [45, 79, 76, 69, 81]. В работах по оптимизации метрик часто используются методы, разработанные для решения других задач оптимизации. Например, часто используются методы, разработанные для решения задач линейного,' квадратичного или целочисленного программирования [9, 64, 3], методы исследования структуры пространства [51, 11, 19, 73], методы исследования сложности задач [48] и другие.

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

В зависимости от свойств множеств значений говорят, главным образом, о номинальных, порядковых (или ранговых) и действительных (непрерывных или интервальных) признаках [27, 49, 75]. В случае номинальных и порядковых признаков число различных значений ограничено. В случае ранговых признаков на значениях задано отношение порядка. Таким образом, отношение «равно»/«не равно» заменено на отношение «не болыне»/«не меньше». Значения действительных признаков принадлежат множеству действительных чисел, и с ними можно выполнять всевозможные арифметические операции.

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

Похожая идея применяется в алгебраическом подходе к решению задач распознавания, предложенном Ю.И.Журавлевым в конце 1970-х годов [20, 22, 24, 14]. Здесь на основе «плохих» алгоритмов проводится построение «хороших» алгоритмов с помощью устранения недостатков одного конкретного алгоритма достоинствами остальных. Также данную идею используют такие современные алгоритмы, как комитеты [50], бустинг (boosting [72]), нелинейные монотонные корректирующие операции [5], смешение мнений экспертов (mixture of experts) [74] и другие.

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

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

В работе рассматривается задача классификации с порядковыми признаками с I классами. Пусть даны множества объектов {5*,., S™q} из классов Кq, где q = 1,., I. Каждый объект принадлежит признаковому пространству размерности п. Значения признаков принадлежат конечным множествам ENx = {0,1,. ,Nt — 1}, в которых заданы естественные отношения порядка: 0 < 1 < 2 < • ■ • < Аг, (где г — номер признака). Описания объектов можно представить как где а^) Е = 1,., п, Ь = 1,., тпд, д = 1,.,

На признаках принято задавать метрики, то есть функции, удовлетворяющие всем аксиомам.

Определение 0.1 Пусть X — произвольное множество. Функция р : X х X —» М называется метрикой на X, если удовлетворяет следующим условиям:

1. р{х, у) = 0 & х = у Ух, у е X;

2. р{х, у) = р(у, х) Ух, у Е X;

3. р(х, у) + р(у, г) > р(х, г), Ух, у, г е X (неравенство треугольника).

Если первое условие заменено на условие р{х, х) = 0 Ух € X, то р{х, у) называется полуметрикой.

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

Sq = (а^),.--,^)) S?" = (ai(S'qn%.,an(S?')) ближними, то есть для всех х, у, г £ X таких, что г < у < х выполняются условия р{г,у) < р{г,х) и р(у,ж) < р(г, ж) (условие порядка), и второй способ — замена операции обычной суммы в неравенстве треугольника на сумму по модулю натурального числа N € {1,2, 3, 4,5,6,7}.

В случае порядковых признаков множество определения функции р* на г-м признаке ЕМх х ЕМг ограничено, поэтому функцию р%{х, у) можно представить как матрицу попарных расстояний элементов (х, у) 6 Е1^1 х ЕМг со значениями из ограниченного множества ЕМг = {0,1,., М* — 1} размерности А^ х Л^.

Занумеруем элементы (х,у) данной матрицы (или значения функции р;(х, у)), удовлетворяющей свойствам 1) и 2) определения 0.1, следующим образом: 0 Х1 Х2 х3 -1 \

XI 0 372ЛГ,- -3

Хз ЛГ.-5 • жлг.см- -1)/2

XN.~ 1 ЖЗЛГ.-6 0 /

Видно, что данная функция определяется Л^(АГ,- — 1)/2 числами. Поэтому ее можно представить также вектором размерности АГ1(7У{ — 1)/2. Например, в случае евклидовой метрики данная метрика принимает вид

0 1 2 3 . АГ-1\ 1 0 1 2 . N,-2

N>-2 Л^-З К-А . 1

Ai-l А^-2 Щ- 3 Щ-2 . 0 / и соответствующий ей вектор равен (1,., А^ — 1,1,., — 2,., 1).

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

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

В работе считается, что на данных принята гипотеза компактности.

Определение 0.2 (Гипотеза компактности ) В задачах классификации объекты из одного класса находятся друг от друга на расстояниях друг от друга небольших, чем объекты из разных классов (упрощенный вариант гипотезы Э. М. Браверма-на [1]).

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

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

Вначале рассматривается задача классификации с двумя классами (гл. 1, §1.1). Каждый объект принадлежит признаковому пространству размерности п, значение каждого признака — конечному множеству EN = {0,1,. ,N — 1} с-отношением порядка 0<1<2<---<JV — 1.

На каждом признаке задана своя функция расстояния р(х, у) : EN х EN —> Ем, которая удовлетворяет всем аксиомам метрики кроме неравенства треугольника, которое заменено на условие порядка.

Так как область определения функции EN х Еы ограничена, функция расстояния представляется в виде матрицы попарных расстояний элементов множества Ем. Признаки считаются попарно независимыми, поэтому вначале ищется функция расстояния на одном признаке (гл. 1, §1.1).

Показано, что в случае линейного критерия рассматриваемая задача сводится к задаче целочисленного линейного программирования (ЗЦЛП). Оказалось, что для нахождения оптимальных функций расстояния достаточно рассматривать только матрицы, у которых недиагональные элементы принимают значения из множества {1, М — 1} (теорема 1.1). Поэтому вместо решения ЗЦЛП целесообразно решать задачу линейного программирования (ЗЛП), что значительно уменьшает сложность.

Было найдено число матриц расстояний размерности N ^f(N) =

Далее было получено обобщение основных результатов для задачи распознавания с двумя классами на случай I классов (гл. 1, §1.2). Для наибольшей наглядности описание алгоритма поиска функций расстояний было дано в матричных обозначениях. Как и прежде, считалось, что все признаки имеют одинаковую размерно'сть, и на каждом признаке задана своя функция расстояния. Отдельно рассматривался случай, когда для некоторого множества признаков функции расстояния совпадали.

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

Поэтому в §1.3 показан вариант применения найденных функций расстояния для решения задач распознавания с порядковыми признаками с помощью алгоритма вычисления оценок (ABO). Дополнительным критерием оптимальности была взята минимизация числа ошибок. Оптимизация проходила по метрикам при фиксировании остальных параметров. Введенное понятие эквивалентности метрических характеристик относительно задач распознавания позволило, без ограничения общности, использовать только метрики, принимающие значения из множества {0,1,2}. При некоторых допущениях задача была сведена к оптимизации непрерывных функций.

Описание множества функций расстояния с суммой по модулю N

В §1.4 был рассмотрен случай, когда на значениях порядковых признаков задана функция, удовлетворяющая всем аксиомам полуметрики с операцией сложения по модулю N вместо обычной операции сложения, используемой в аксиоме неравенства треугольника. В работе были описаны все возможные полуметрики при Л/ = N = 1,2,3,4,5, 6,7. Для каждого случая доказывалась теорема о том, что все матрицы, удовлетворяющие некоторым условиям, являются полуметриками; либо, что полуметрик, удовлетворяющих данным условиям, нет; либо давался метод определения является ли рассматриваемая матрица полуметрикой в данном пространстве. Кроме того, был получен ряд утверждений, верных для случаев произвольных И, и помогающих значительно сократить перебор.

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

На практике также встречаются задачи с признаками различных типов (или, в терминах Н. Г. Загоруйко, измеренными в различных шкалах [27]). Известно, что номинальные шкалы являются наиболее слабыми, далее идут порядковые шкалы, наиболее мощные — количественные или интервальные шкалы. Ясно, что работа с математическими операциями в более слабых шкалах может оказаться некорректной или даже невозможной. Поэтому для использования стандартных алгоритмов анализа данных в задачах со смешанными признаками иногда имеет смысл усилить одни типы признаков или ослабить другие.

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

Методы перехода от одних числовых типов признаков к другим рассматривались, например, в [66, 27, 10, 82]. Кроме того, связанной с преобразованиями метрик задачей является классическая задача изометрического вложения, которая состоит в ответе на вопрос, может ли данное пространство расстояний (X, с1) быть изометрически вложено в некоторое «объемлющее» пространство [11]. Работы в этом направлении велись многими исследователями: Кэли [68], Менгером [77], Шенбергом [80] и Блюменталем [67]. Задачу вложения в евклидово пространство принято называть «задачей многомерного шкалирования» [19, 8].

Ряд работ посвящен исследованию вложений в ¿^-пространства при выполнении гиперметричесих неравенств ( Ь^х^ < 0, где ¿>1,.,Ьп — такие числа,

1<1 <з<п что ^ = 1) 11 их частного случая неравенства треугольника (все компоненты Ь равны нулю, за исключением двух компонент, равных 1, и одной компоненты, равной —1). Здесь возникают такие задачи, как определение возможности вложения в пространство заданной размерности, поиск минимальной необходимой размерности пространства вложения, определение достаточного числа объектов, при вложении которых в пространство, можно сказать, можно ли вложить в это пространство все объекты данной природы и т.д. [11].

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

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

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

Рассматриваемые матрицы имеют структуру, состоящую из единичных подматриц с нулевыми диагоналями и строк с элементами, равными М — 1 (кроме нулевых диагональных элементов). Единичные подматрицы расположены вдоль диагонали. Такая структура матрицы попарных расстояний задает в евклидовом пространстве несколько правильных симплексов с единичными ребрами. Все вершины двух разных симплексов находятся на расстояниях М — 1 друг от друга. Получено, что число таких матриц размерности N при М > 4 равно /(№) = 6 • 2ЛГ~3; при М < 3 равно = %

В §2.2 рассматривалась задача погружения объектов, расположенных на расстояниях, определяемых найденными матрицами расстояний А = {а^} размером N х N, в евклидово пространство размерности Другими словами, решалась задача поиска точек (векторов) в евклидовом пространстве размерности t, которые дают те же расстояния, что и значения порядковых признаков в матрице расстояний. На основе модели Торгенсона был сформулирован критерий возможности погружения.

В §2.3 рассматривалась задача оценки размерности евклидова пространства, в которое можно поместить объекты задачи распознавания, располагающиеся на заданных матрицей А = {а^} расстояниях. Таким образом, рассматривались объекты, расположенные друг относительно друга на расстояниях либо равных 1, либо М — 1. а также образующих кластерную структуру.

Для случаев малых размерностей £ = 1,2,3 были построены все возможные конфигурации. Для случая евклидова пространства произвольной размерности 4 была найдена оценка максимального числа объектов, которые можно в него поместить при выполнении всех условий на расстояния.

Оказалось, что если точки можно поместить в пространство размерности ¿ согласно матрице попарных расстояний А, в которой недиагональные элементы принимают значения из множества {1,М — 1}, и выполнены все аксиомы метрики и условие порядка, то число точек не может превышать 2£. Причем случай 2Ь точек соответствует конфигурации пересечения 2í единичных отрезков в одной точке — середине всех отрезков. В данном случае М — 1 = \/2/2 < 1, то есть имеется не близость, а «антиблизость» единичных симплексов. Следовательно, для случая М — 1 > 1 данная нижняя оценка для максимального числа объектов не является точной и может быть улучшена в дальнейшем.

Выбор метрик в алгебраических замыканиях модели ABO

С точностью работы алгоритмов на контрольной или обучающей выборках связан такой раздел области интеллектуального анализа данных как алгебраический подход к решению задач распознавания образов, предложенный Ю. И. Журавлевым в конце 1970-х годов [20]. Одним из ключевых в разделе является понятие корректного алгоритма, т. е. алгоритма, который не делает ошибок на контрольной выборке [22, 23, 24]. Идея алгебраического подхода состоит в синтезе корректного алгоритма с помощью алгебраического выражения над некорректными (эвристическими) алгоритмами.

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

Обзор литературы по алгебраическому подходу выявил, что выбор метрик на признаках как механизм образования новых алгоритмов ABO в замыканиях ранее не рассматривался [25, 21, 14, 53].

Действительно, в рамках алгебраического подхода развивались такие направления, как теория локальных и универсальных ограничений К. В. Рудакова (направленная на создание универсального языка, пригодного для описания и исследования задач преобразования информации) [59], совершенствование техники анализа алгебраических конструкций (в рамках классической теории она была построена B.JT. Матросовым [53, 55, 56], более наглядно и полно ее удалось описать и разработать А.,Г. Дьяконову [17, 15, 16, 14], поиск оптимальных в том или ином смысле алгоритмов модели [60, 61, 12] и алгебраических выражений над ними [4, 5, 54, 55] и т.д.

В частности, изучались линейные и алгебраические замыкания алгоритмов, получаемых путем изменения параметров. Для алгоритмов ABO выбираемыми параметрами были веса объектов из обучающей выборки, нормировочные коэффициенты. В основной части работ метрика на объектах (или признаках) была фиксирована и не являлась параметром алгоритма. Выбор метрики использовался только как способ получения описания алгебраических замыканий и их преобразования. Так, А. Г. Дьяконовым в работе [18] было показано, что в задаче с двумя непересекающимися классами при фиксированных метриках на объектах матрицы оценок близости объектов можно описать некоторой метрикой.

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

В §3.1 даны ключевые понятия и методы алгебраического подхода, сформулирован критерий корректности алгебраического замыкания модели ABO, впервые сформулированный Ю.И.Журавлевым в 1977 году [23]. Корректность алгебраического замыкания модели ABO базируется на понятии регулярности задачи распознавания, т.е. факте удовлетворения задачи распознавания трем естественным условиям: 1) множества эталонов каждого из классов попарно различны, 2) в контрольной выборке нет ни одной пары объектов, неразличимых относительно эталонов, 3) обучающая и контрольная выборки не пересекаются. Критерий состоит в том, что алгебраическое замыкание модели ABO корректно тогда и только тогда, когда задача распознавания, регулярна. В [14] было показано, что для корректности алгебраического замыкания необходимо и достаточно выполнение первых двух условий регулярности задачи.

В §3.2 были найдены условия регулярности задачи распознавания с порядковыми признаками при выборе фиксированных метрик на признаках. Были рассмотрены как случай произвольных метрик на признаках, так и случай функций расстояния, удовлетворяющих условию порядка (являющихся также метриками из-за ограниченности ее значений множеством {0,1,2}). Условия регулярности согласно критерию корректности были эквивалентны условию корректности задач распознавания.

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

В § 3.4 был рассмотрен важный частный случай алгебраического замыкания — линейное замыкание модели ABO. Ранее изучались теоретические основы линейного замыкания ABO для общих случаев [20, 53, 59, 14, 16, 52], поэтому рассмотрение более конкретной задачи поиска критериев корректности при возможности выбирать функции расстояния из всевозможных метрик и из множества функций, удовлетворяющих первым двум аксиомам метрики и условию порядка, представляло определенный интерес. В работе получены критерии корректности линейного замыкания ABO при возможности выбора функций расстояния на порядковых признаках. Отдельно рассматриваются случаи задачи распознавания с непересекающимися и пересекающимися классами, а также при выборе метрик из произвольного множества допустимых метрик (со значениями из ограниченного множества {0,1,2}) и при выборе метрик из множества функций расстояния, удовлетворяющих условию порядка.

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

Эксперименты

Для определения целесообразности использования новых функций расстояния на признаках был проведен ряд экспериментов с задачами из репозитория UCI [78]. Результаты работы алгоритмов с использованием полученных функций расстояния сравнивались с результатами тех же алгоритмов с использованием манхэттенского расстояния или Хэмминговой метрики. Было показано, что в некоторых случаях имеет смысл настраивать функции расстояния, а не брать стандартные метрики.

4.2.4 Выводы

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

Опыты показали, что имеет смысл оптимизировать Л, а не брать просто Л = 1. Кроме того, из рассмотренных примеров дискретизации выборок видно, что увеличение количества различных значений признаков для дискретизации в большинстве случаев улучшает точность распознавания. Однако иногда (задачи Ionosphere и Wine) при увеличении размерности N точность падает. Поэтому для увеличения точности распознавания имеет смысл проводить оптимизацию по N. Также можно сделать вывод, что использование дискретизации с помощью деления на одинаковые группы чаще дает лучшую точность, чем дискретизации в помощью деления на равные интервалы, особенно при использовании алгоритма вычисления оценок. Использование расстояния Хэмминга в рассматриваемых задачах чаще дает худшие результаты, чем использование какой-либо другой функции расстояния.

Заключение

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

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

Также рассмотрен случай использования функций расстояния, когда в определении полуметрики в неравенстве треугольника обычная сумма заменена на сумму по модулю N. Были получены утверждения, верные для случаев произвольных размерностей N. Подробно рассмотрены случаи размерностей Ь = N = 1,2,3,4,5,6,7. Для каждого случая доказаны теоремы о том, что все матрицы, удовлетворяющие некоторым условиям, являются полуметриками; либо, что полуметрпк, удовлетворяющих данным условиям, нет; либо давался метод определения является ли рассматриваемая матрица полуметрикой в данном пространстве.

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

Проведенные эксперименты на реальных задачах из репозитория иС1 и примеры показали, что в некоторых случаях, при определенных параметрах алгоритмов использование рассматриваемых функций расстояния приводит к лучшим результатам, чем использование стандартной метрики (обычно это манхэттенское расстояние или евклидова метрика).

Для возможности представления исходных порядковых признаков непрерывными признаками с евклидовой метрикой получен общий вид матриц расстояний, соответствующих функциям расстояния с выполненным условием порядка, при условии, что также выполнено неравенство треугольника. Оказалось, что матрицы должны иметь структуру, состояп^ую из единичных блоков, расположенных по диагонали, и строк, состоящих из элементов, равных М — 1 (кроме нулевых диагональных элементов). Такая структура дает в евклидовом пространстве кластеры близких точек. Точки из различных групп должны находиться на расстояниях равных М — 1 друг от друга. Также найдено число матриц размерности N.

Решена задача погружения найденных матриц расстояний А = {<kj} размером N х N в евклидово пространство размерности t. То есть решена задача поиска точек (векторов) в евклидовом пространстве размерности t, которые дают те же расстояния, что и значения порядковых признаков в матрице попарных расстояний. На основе модели Торгенсона был сформулирован критерий возможности погружения.

Получена оценка размерности евклидова пространства, в которое можно поместить объекты задачи распознавания, располагающиеся на заданных матрицей А = {аг]} расстояниях. Для случаев малых размерностей пространств t = 1,2,3 были построены все возможные конфигурации точек. Для случая евклидова пространства произвольной размерности i было найдено максимальное число объектов, которые можно в него поместить при выполнении всех условий на расстояния.

Рассмотрен случай возможности использования полученных функций расстояния в алгебраическом подходе к решению задач распознавания. Были найдены условия регулярности задачи распознавания с порядковыми признаками при выборе фиксированных метрик на признаках. Были рассмотрены как случай произвольных метрик на признаках, так и случай функций расстояния, удовлетворяющих условию порядка (являющихся также метриками из-за ограниченности множеством {0,1,2} ее значений). Условия регулярности согласно критерию корректности были эквивалентны условию корректности задач распознавания.

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

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

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

1. Аркадьев А.Г., Э.М. Браверман Обучение машин распознаванию образов. — М.: Наука, 1964. 110 с.

2. Беклемишев Д.В. Курс аналитической геометрии и линейной алгебры. — М.: Наука. 1971. 328 с.

3. Васильев Ф.П. Численные методы решения экстремальных задач. — М.: Наука,1988. 550 с.

4. Воронцов К. В. Локальные базисы в алгебраическом подходе к проблеме распознавания: Дис. канд. физ.-матем. наук./ ВЦ РАН. — М. 1999. —107 с.

5. Воронцов К. В. Оптимизационные методы линейной и монотонной коррекции в алгебраическом подходе к проблеме распознавания // ЖВМ и МФ. — 2000. — Т. 40, № 1. — С. 166-176.

6. Воронцов К.В. Курс лекций «Математические методы обучения по прецедентам». «Метрические алгоритмы классификации», http://www.ccas.ru/voron/download/MetricAlgs.pdf

7. Воронцов К.В. Курс лекций «Математические методы обучения по прецедентам». «Логические алгоритмы классификации», http://www.ccas.ru/voron/download/LogicAlgs.pdf

8. Воронцов К.В. Курс лекций «Математические методы обучения по прецедентам». «Лекции по алгоритмам кластеризации и многомерного шкалирования», http://www.ccas.ru/voron/download/Clustering.pdf

9. Галеев Э.М., Тихомиров В.М. Краткий курс теории экстремальных задач.— М.: Изд. Московского университета, 1989.— 204 с.

10. Двоенко С.Д. Согласование измерений в разнотипных шкалах. Аналитические материалы. — Информационные Бизнес-Технологии (Компания IBTech) — http: / / www.ib-tech.ru/papers/scaling.htm

11. Деза М. М., Лоран М. Геометрия разрезов и метрик — М.: МЦНМО, 2001. — 736 с.

12. Докукин А. А. Об одном методе построения оптимального алгоритма вычисления оценок // ЖВМ и МФ. 2006. - Т. 46, № 4. — С. 763-768.

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

14. Дьяконов А. Г. Алгебры над алгоритмами вычисления оценок: Учебное пособие. — М.: Издат. отд. ф-та ВМиК МГУ, 2006. —70 с.

15. Дьяконов А. Г. Критерии корректности алгебраических замыканий модели алгоритмов вычисления оценок // ДАН. — 2008. — Т. 420, № 6. — С. 732-735.

16. Дьяконов А. Г. Алгебра над алгоритмами вычисления оценок: нормировка и деление // ЖВМиМФ. 2007.-Т. 47, №6, —С. 1099-1109.

17. Дьяконов А. Г. Алгебраические замыкания обобщенной модели алгоритмов распознавания, основанных на вычислении оценок: Дис. докт. физ.-матем. наук. — М. 2009.-292 с.

18. Дьяконов А. Г. Метрики алгебраических замыканий в задачах распознавания образов с двумы непересекающимися классами // ЖВМиМФ. — 2008.—Т.48, №5. — С. 916-927.

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

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

21. Журавлев Ю.И. Избранные научные труды.— М.: Магистр. 1998. —420 с.

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

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

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

25. Журавлев Ю.И., Рязанов В.В., Сенько О.В. «Распознавание». Математические методы. Программная система. Практические применения. — М.: Фазис, 2006. — 159 с.

26. Журавлев Ю. И., Флеров Ю. А. Дискретный анализ. Часть I: Учебное пособие. — М.: МФТИ, 1999.-136 с.

27. Загоруйко Н.Г. Прикладные методы анализа данных и знаний. — Новосибирск: Изд. Института математики СО РАН, 1999. — 270 с.

28. Зайченко Ю. П. Основы проектирования интеллектуальных систем. — К.: Издательский Дом «Слово», 2004. — 352 с.

29. Зиновьев А.Ю. Визуальзация многомерных данных — Издательство Красноярского государственного технического университета, 2000. — 180 с.

30. Иофина Г. В. Выбор наилучшей метрики в алгоритме распознавания по ближайшему соседу // Сборник трудов 49-й научной конференции МФТИ.— М.: МФТИ, 2006.-С. 266-267.

31. Иофина Г. В., Кропотов Д. А. Поиск оптимальной метрики в задачах классификации с порядковыми признаками // Докл. всеросс. конф. Математические методы распознавания образов-13. —М.: МАКС Пресс, 2007.— С. 137-140.

32. Иофина Г. В. Оптимизация метрик для порядковых признаков в задачах распознавания // Сборник трудов 50-й научной конференции МФТИ. —М.: МФТИ, 2007. —С. 98-100.

33. Иофина Г. В., Ветров Д. П., Кропотов Д. А. Восстановление объектов в евклидовом пространстве по оптимальным матрицам близости // Моделирование процессов обработки информации. — М.: МФТИ, 2008.— С. 110-114.

34. Иофина Г. В. Многомерное шкалирование в случае матриц попарных расстояний с элементами из конечного множества // Интеллектуализация обработки информации: Тезисы докл.— Симферополь, 2008.— С. 112-113.

35. Иофина Г. В. Многомерное шкалирование в случае матриц попарных расстояний с элементами из конечного множества // Таврический вестник информатики и математики. — 2008. — № 1. — С. 223-230.

36. Иофина Г. В. Оптимизация алгоритмов вычисления оценок по метрикам на признаковых описаниях объектов // Сборник трудов 51-й научной конференции МФТИ. М.: МФТИ, 2008. - С. 39-42.

37. Иофина Г. В. Эквивалентные метрики в алгоритмах вычисления оценок в задачах с порядковыми признаками // Моделирование процессов обработки информации. — М.: МФТИ, 2009. —С. 65-69.

38. G. V. Iofma Optimal Metrics in Classification Problems with Ordered Features and an Arbitrary Number of Classes // Pattern Recognition and Image Analysis.— 2009.-Vol. 19, no. 2.-Pp. 284-288.

39. Иофина Г. В. Критерии корректности алгебраического замыкания модели ABO в задачах с порядковыми признаками // Докл. всеросс. конф. Математические методы распознавания образов-14. — М.: МАКС Пресс, 2009. — С. 37-41.

40. Иофина Г. В. Критерии корректности алгебраического замыкания модели ABO при варьировании метрик на признаках // Сборник трудов 52-й научной конференции МФТИ. —М.: МФТИ, 2009.-С. 67-70.

41. Иофина Г. В. Поиск оптимальной метрики в задачах классификации с порядковыми признаками // ЖВМ и МФ. 2010. - Т. 50, № 3. — С. 585-592.

42. Иофина Г. В. Условия корректности линейного замыкаеия модели ABO // Ломоносов-2010: Материалы конф. — М.: Издательский отдел факультета ВмиК МГУ, 2010.-С. 85-86.

43. G. V. Iofina A Study of Metrics in Finite Sets for Application in Classification and Recognition Problems // Pattern Recognition and Image Analysis. — 2010. — Vol. 20, no. 4.-Pp. 238-246.45 4647 48 [49 [50 [51 [525354 555657 58

44. Казарян М.Э. Лекционные курсы НОЦ, вып. 3. Введение в теорию гомологий. — М.: МИАН, 2006. 106 с.

45. Карпов JI.E., Юдин В.Н. Методы добычи данных при построении локальной метрики в системах вывода по прецедентам // Препринт ИСП РАН. — М.: ИСП РАН, 2007.-4 с.

46. Колмогоров А.Н., Фомин C.B. Элементы теории функций и функционального анализа. — М.: Физматлит, 2004. — 572 с.

47. Томас X. Кормен, Чарльз И. Лейзерсон, Рональд Л. Р. Алгоритмы: построение и анализ, 2-е издание. — М.-Спб.-Киев, 2005. — 955 с.

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

49. Мазуров В.Д. Метод комитетов в задачах оптимизации и классификации. — М.: Наука, 1990.-248 с.

50. Майсурадзе А.И. О специальных представлениях метрических конфигураций: Дисс. к.ф.-м.н. ВЦ РАН, 2005. - 122 с.

51. Максимов Ю. В. Корректные алгебры над алгоритмами вычисления оценок в множестве регулярных задач распознавания с непересекающимися классами // ЖВМиМФ. 2009. - Т. 49, № 7. - С. 1327-1339.

52. Матросов В. Л. Корректные алгебры ограниченной емкости над множеством регулярных задач: Дис. докт. физ.-матем. наук./ Гос. пед. инст-т им. В. И Ленина. — М. 1985. 220 с.

53. Матросов В. Л. Оптимальные алгебры в алгебраических замыканиях операторов вычисления оценок // Докл. АН СССР. 1982.-Т. 262, №4.-С.818-822.

54. Матросов В. Л. Синтез оптимальных алгоритмов в алгебраических замыканиях моделей алгоритмов распознавания // Распознавание, классификация, прогноз. Математические методы и их применение. — М.: Наука,1989. — Вып. 1. — С. 149176.

55. Матросов В. Л. Корректные алгебры ограниченной емкости над множествами некорректных алгоритмов // Докл. АН СССР. — 1980. — Т. 253, № 1. — С. 25-30.

56. Понтрягин Л. С., Основы комбинаторной топологии, М. — Л., 1947.—С. 23-31.

57. Розенблатт Ф. Принципы нейродинамики: Перцептроны и теория механизмов мозга = Principles of Neurodynainic: Perceptions and the Theory of Brain Mechanisms. — M.: Мир, 1965. — 480 с.

58. Рудаков К. В. Алгебраическая теория универсальных и локальных ограничений для алгоритмов распознавания: Дис. докт. физ.-матем. наук. — М.: ВЦ РАН, 1992.-146 с.

59. Рязанов В. В. Оптимизация алгоритмов вычисления оценок по параметрам, характеризующим представительность эталонных строк // ЖВМ и МФ.— 1976. Т. 16, № 6. - С. 1559-1570.

60. Рязанов В. В. О построении оптимальных алгоритмов распознавания и таксономии (классификации) при решении прикладных задач // Распознавание, классификация, прогноз. Математические методы и их применение. — М.: Наука,1988. Вып. 1. —С. 229-279.

61. Садовничий В., Григорьян А., Конягин С. Задачи студенческих математических олимпиад. —М.: Изд-во МГУ, 1987.— 308 с.

62. Скворцов В. А. Примеры метрических пространств. — М.: МЦНМО, 2002,— 24 с.

63. Соболев В.А. Решаем несовместные системы // Соросовский образовательный журнал. Т. № 4, 2000. - 16-119 с.

64. Тер-Крикоров A.M., Шабунин М.И. Курс математического анализа: Учеб. по-соб. для вузов. — М.: МФТИ, 2000. — 720 с.

65. Bana е Costa and J. Vansnick, The MacBeth approach: basic ideas, software and an application. — Dordrecht: Kluwer Academic Publishers, 1999.— Pp. 131-157.

66. L.H. Blumental Theory and Application of Distance Geometry // Oxford University Press. — 1953.

67. A. Cayley On a theorem in the Geometry of Position // Cambridge Mathematical Journal. Vol. 2, 1841.-Pp. 267-271.

68. Jason V.Davis, Brian Kulis, Prateek Jain, Suvrit Sra, Inderjit S. Dhillon Information-Theoretic Metric Learning.// In Proceedings of the 24-th International Conference on Machine Learning, 2007.

69. Elena Deza Dictionary of distances — Elsevier, 2006. — 391 p.

70. Dietterich T.G. Approximate statistical tests for comparing supervised classification learning algorithms. Neural Computation, 10, 1998, Pp. 1895-1924.

71. Freund Y., Schapire R.E. A decision-theoretic generalization of on-line learning and an application to boosting // European Conference on Computational Learning Theory. 1995. - Pp. 23-37.

72. Hallard T. Croft, K. J. Falconer , Richard K. Guy Unsolved problems in Geometry. — Springer-Verlang, 1991. —198 p.

73. Jacobs R.A., Jordan M.I., Nowlan S.J., Hinton G.E. Adaptive mixtures of local experts // Neural Computation. — 1991. — № 3. — Pp. 79-87.

74. Kim Cao-Van. Supervised ranking from semantics to algorithms: Dissertation in fulfillment of the requirements for the degree of Doctor of Philosophy (Ph.D.).— Faculty of Sciences, Universiteit Geut, 2003.

75. Lebanon, G. Learning Riemannian Metrics.// In Proceedings of the 19th UAI, 2003.

76. K. Menger New Foundation of Euclidean Geometry. // American Journal of Mathematics. Vol. 53, № 4. (Oct., 1931).-Pp. 721-745.

77. Newman D.J., Hettich S., Blake C.L., Merz C.J. UCI repository of machine learning databases, 1998. http://www.ics.uci.edu/ mlearn/MLRepository.html

78. Rubner, Y., Tomasi, C., Guibas, L. J. The Earth Mover's Distance as a Metric for Image Retrieval.// International Journal of computer Vision, 40(2), 2007. — Pp. 99121.

79. I.J. Schoenberg On Certain Metric Spaces Arising Prom Euclidean Spaces by a Change of Metric and Their Imbedding in Hilbert Space // The Annals of Mathematics, Second Series. Vol. 38, № 4. (Oct., 1937).-Pp. 787-793.

80. Wei Zhang, Xiangyang Xue, Ziehen Sun, Yue-Fei Guo, Hong Lu Optimal Dimensionality of Metric Space for Classification //In Proceedings of the 24-th International Conference on Machine Learning", 2007.

81. Yan Li, Simon Chi-Keung Shiu, Sankar Kumar Pal and James Nga-Kwok Liu. Learning Similarity Measure of Nominal Features in CBR Classifiers // Pattern Recognition and Machine Intelligence. — Springer Berlin/Heidelberg, 2005.