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

• Автор: Иофина, Галина Владимировна
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 105 с.

Введение

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 Структура АВО
1.3.2 Эквивалентность метрических характеристик.
1.3.3 Критерий минимизации ошибки АВО
1.4 Функции расстояния с суммой по модулю .
1.4.1 Общие утверждения
1.4.2 Случаи iV 1,2,.,5
1.4.3 Случай 6
1.4.4 Случай 7.
2 Выбор функций расстояния в задачах распознавания со смешанными признаками
2.1 Преобразование порядковых признаков в евклидовы.
2.1.1 Случай существования точного решения.
2.1.2 Общий вид матриц расстояний с выполненными условием порядка и неравенством треугольника.
2.1.3 Необходимое и достаточное условие существования точного решения .
2.2 Оценка размерности евклидова пространства, в которое можно поместить объекты задачи распознавания.
3 Выбор метрик в алгебраических замыканиях модели АВО
3.1 Алгебраический подход к задаче распознавания
3.2 Условие регулярности задачи распознавания с порядковыми признаками
3.2.1 Регулярность задачи распознавания при выборе метрик на признаках .
3.2.2 Регулярность задачи распознавания при выполнении условия
порядка
3.3 Корректность алгебраического замыкания в случае выбора метрик на признаках из ограниченного множества метрик.
3.4 Корректность линейного замыкания в случае выбора метрик на признаках .
3.4.1 Корректность линейного замыкания АВО в задачах распознавания с непересекающимися классами
3.4.2 Корректность линейного замыкания АВО.в задачах.распознавания с пересекающимися классами
3.4.3 Корректность линейного замыкания АВО в задачах распозна
вания с порядковыми признаками при выполнении условия порядка
3.5 Оценка минимальной степени корректного алгебраического замыкания АВО.
4 Эксперименты
4.1 Модельные задачи.
4.1.1 Выводы.
4.2 Эксперименты на реальных данных
4.2.1 Выбор коэффициента Л.
4.2.2 Выбор коэффициентов в АВО
4.2.3 Результаты.
4.2.4 Выводы.
Заключение
Введение


В случае порядковых признаков множество определения функции р на 1м признаке Ек х Едг ограничено, поэтому функцию рх, у можно представить как матрицу попарных расстояний элементов х, у Е Ед, х д, со значениями из ограниченного множества Ем 0,1,. У х Л. Занумеруем элементы х,у данной матрицы или значения функции ,т,у, удовлетворяющей свойствам 1 и 2 определения 0. Видно, что данная функция определяется ЛГЛГ, числами. Поэтому ее можно представить также вектором размерности ЛдЛГ, . М 1,1,. М 2,. Таким образом, задача оптимизации функций на порядковых признаках, играющих роль расстояний, сводится к выбору функций расстояния из ограниченного множества матриц, удовлетворяющих определенным условиям. В работе наиболее полно рассмотрен случай замены неравенства треугольника условием порядка. В случае перехода в условии неравенства треугольника к сумме но модулю было описано множество матриц при небольших . Выбор функций расстояния, отражающих внутреннюю структуру данных задачи классификации, при выполнении условия порядка В работе считается, что на данных принята гипотеза компактности. Определение 0. Гипотеза компактности задачах классификации объекты из одного класса находятся друг от друга на расстояниях друг от друга небольших, чем объекты из разных классов упрощенный вариант гипотезы Э. Поэтому естественно ставить задачу поиска функции расстояния, которая наилучшим образом отражала бы внутреннюю структуру задачи, то есть для объектов из одного класса функция давала бы малые значения, а для объектов из разных классов большие. М2 М 3 М 2 . Для формализации критериев оптимальности функции расстояния вводятся понятия внутриклассовых и межклассовых расстояний как средние арифметические всех попарных расстояний внутри классов и между элементами из разных классов соответственно. Рассматривается критерий максимизации взвешенной разницы межклассового и среднего внутриклассового расстояний линейный критерий. Вначале рассматривается задача классификации с двумя классами гл. Каждый объект принадлежит признаковому пространству размерности п, значение каждого признака конечному множеству Е 0,1,. Лг 1. На каждом признаке задана своя функция расстояния рх, у Едг х ЕА у Ем, которая удовлетворяет всем аксиомам метрики кроме неравенства треугольника, которое заменено на условие порядка. Так как область определения функции В1 х Еы ограничена, функция расстояния представляется в виде матрицы попарных расстояний элементов множества Еи. Признаки считаются попарно независимыми, поэтому вначале ищется функция расстояния на одном признаке гл. Показано, что в случае линейного критерия рассматриваемая задача сводится к задаче целочисленного линейного программирования ЗЦЛП. Оказалось, что для нахождения оптимальных функций расстояния достаточно рассматривать только матрицы, у которых недиагональные элементы принимают значения из множества 1, М 1 теорема 1. Поэтому вместо решения ЗЦЛП целесообразно решать задачу линейного программирования ЗЛП, что значительно уменьшает сложность. Далее было получено обобщение основных результатов для задачи распознавания с двумя классами на случай I классов гл. Для наибольшей наглядности описание алгоритма поиска функций расстояний было дано в матричных обозначениях. Как и прежде, считалось, что все признаки имеют одинаковую размерность, и на каждом признаке задана своя функция расстояния. Отдельно рассматривался случай, когда для некоторого множества признаков функции расстояния совпадали. Однако при решении реальных задач качество отражения внутренней структуры данных не всегда поддается измерению. Поэтому имеет смысл изучать го, насколько хорошо работает тот или иной алгоритм в рассматриваемом случае. Для того чтобы понять насколько решение оптимально, принято измерять число ошибок. Поэтому в 1. ЛЕЮ. Дополнительным критерием оптимальности была взята минимизация числа ошибок. Оптимизация проходила по метрикам при фиксировании остальных параметров. Введенное понятие эквивалентности метрических характеристик относительно задач распознавания позволило, без ограничения общности, использовать только метрики, принимающие значения из множества 0,1,2. При некоторых допущениях задача была сведена к оптимизации непрерывных функций. В 1.