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

• Иофина, Галина Владимировна
• кандидат физико-математических наук
• 2010

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

Введение

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 при возможности выбора функций расстояния на признаках. В случае метрик она равняется единице, в случае функций расстояния, удовлетворяющих условию порядка, — не может превышать двух.

Список литературы диссертационного исследования кандидат физико-математических наук Иофина, Галина Владимировна, 2010 год

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.