WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |   ...   | 58 |
РОССИЙСКАЯ АКАДЕМИЯ НАУК ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР при поддержке РОССИЙСКОГО ФОНДА ФУНДАМЕНТАЛЬНЫХ ИССЛЕДОВАНИЙ КОМПАНИИ FORECSYS МАТЕМАТИЧЕСКИЕ МЕТОДЫ РАСПОЗНАВАНИЯ ОБРАЗОВ ММРО-12 Доклады 12-й Всероссийской конференции Москва 2005 Аннотация В сборнике представлены доклады 12-й Всероссийской конференции «Математические методы распознавания образов», проводимой Вычислительным центром им. А.А. Дородницына Российской академии наук при финансовой и организационной поддержке РФФИ (грант № 05-01-10142) и компании Forecsys.

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

2 Оргкомитет Председатель: Журавлев Юрий Иванович, академик РАН Зам. председателя: Дюкова Елена Всеволодовна, д.ф.-м.н.

Ученый секретарь Воронцов Константин Вячеславович, к.ф.-м.н.

Члены: Донской Владимир Иосифович, д.ф.-м.н.

Дедус Флоренц Федорович, д.т.н.

Местецкий Леонид Моисеевич, д.т.н.

Немирко Анатолий Павлович, д.ф.-м.н.

Устинин Михаил Николаевич, к.ф.-м.н.

Песков Николай Владимирович, к.ф.-м.н.

Рейер Иван Александрович, к.т.н.

Программный оргкомитет Председатель: Рудаков Константин Владимирович, член-корр. РАН Зам. председателя: Матросов Виктор Леонидович, член-корр. РАН Ученый секретарь Чехович Юрий Викторович, к.ф.-м.н.

Члены: Микаэлян Андрей Леонович, академик РАН Сергиенко Иван Васильевич, академик НАН Украины Жижченко Алексей Борисович, член-корр. РАН Сойфер Виктор Александрович, член-корр. РАН Моттль Вадим Вячеславович, д.ф.-м.н.

Пытьев Юрий Петрович, д.ф.-м.н.

Рязанов Владимир Васильевич, д.ф.-м.н.

Сенько Олег Валентинович, к.ф.-м.н.

Технический оргкомитет Председатель: Громов Андрей Николаевич Члены: Вальков Антон Сергеевич, к.ф.-м.н.

Ефимов Александр Николаевич Ивахненко Андрей Александрович Инякин Андрей Сергеевич Кирсанов Антон Андреевич Кочедыков Денис Алексеевич Никитов Глеб Владимирович I. Математическая теория распознавания Cложность алгоритмов решения задачи синтеза групповых классификаций М.Б. Айдарханов, Е.Н. Амиргалиев (Алматы) Пусть задано конечное множество объектов M = {S1,..., Sn} из некоторого объектного множества D. Для каждого Si определено J (Si ) - описание объекта. Задача классификации Zk состоит в следующем. Для множества объектов M по информации J (M ) найти классы эквивалентных объектов K1(M ),...K2(M ) то есть классификацию K (M ).

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

Пусть A1,..., Am {A} - исходный набор алгоритмов решения задачи классификации Zk для множества объектов M = {S1,..., Sn}.

Результатом применения алгоритмов Ai к (M, J (M )) являются классификации Ki (M ) (M ), где (M ) - пространство классификаций конечного множества объектов M. Пусть определена метрика d (K ', K") в (M ) и m (K) = d(K, Ki ), Ki = Ki (M ), K (M ). (1) i=* Задача ZC : Найти K (M ) (M ), минимизирующую функционал * (K ) = min (K), K (M ). (2) Для построения алгоритмов решения задачи синтеза групповых классификаций будут использоваться решения следующих двух вспомогательных легко решаемых задач Z1 и Z2.

Задача Z1. Данная задача состоит в построении результирующего бинарного отношения R с использованием критерия большинства для представлений исходных классификаций K1,..., Km в виде матриц соответствующих им отношений эквивалентностей R1,..., Rm.

Задача Z2. Задача сводится к минимизации функционала m 1(Ki (li )) = (lv ), Ki (li )), (3) d(Kv v=в результате которой находится оптимальная классификация Kt (lt ) в пространстве классификации, удовлетворяющая условию 1(Kt (lt )) = min 1(Ki (li )). (4) ~ Ki (li )K (M ) Рассмотрим задачу Zc. Представляет интерес отдельный анализ этой задачи при l1 =... = lm = l и при произвольных lv, 1 lv n, v = 1,..., m.

Пусть l1 = l2 =... = lm = l. Требуется найти классификацию * l l Kn K (M ), где K (M ) множество всех классификаций М содержащих l классов, удовлетворяющую условию m * v (Kn ) = min (l), Kn ). (5) d(Kn l KnK (M ) v=Приведем локально-экстремальные алгоритмы решения этой задачи.

Алгоритм A1.

Шаг 0. (выбор начального приближения). Решается задача Z2.

Решение этой задачи – классификация K принимается за начальное 0 приближение. Запоминается значение 1(K ) = (K ).

l 0 Шаг 1. Строится 2-окрестность B2(K ) объекта K и для каждого l объекта Ki0 B2 (K ) вычисляется значение (Ki0).

0 1 Если (Ki0 (K ) для всех Ki0 B2(K ), то алгоритм заканчивает работу и K - искомое решение локально-экстремальной задачи. Если для Ki0, v = 1,...,r, (Ki0 ) < (K ), то находится v v min{(Ki0 ),...,(Ki0 )}= (K1), фиксируется классификация K1.

1 r Шаг 2. В силу теоремы 2.2 из [1] классификация K1 построена из классификации K переносом некоторого объекта S0 из класса с l l номером u в класс с номером w. Теперь построим B2(K ), начиная последовательный поочередный перенос объектов из класса с номером w, т.е. K1w, в классы с номерами 1,2,..., w -1, w +1,...,l. Очевидно, что при переносе S0 в K1u получится классификация K, а при переносе S0 в остальные классы Kl получаются некоторые классификации из l анализируемого множества B2(K ). Поэтому объект S0 фиксируется в классе K1w. В силу теорем 2.2 и 2.4 из [1, 2], l l l 0 l B2(K ) B2(K ) B1 (K ), т.е. осуществляется направленный поиск.

l Вычисляя (Kil ) для Ki1 B2 (K ) фиксируем классификацию. На p некотором шаге ( p +1) находится классификация K такая, что p l p (K ) (Kip ), для всех Kip B2(K ).



Алгоритм A2. Решаются задачи Z2 и Z1. Вычисляется значение 0 (K, R), где K - решение задачи Z2, R - результирующее бинарное отношение, соответствующее решению задачи Z1. Анализируется l 0 l окрестность B2(K ) и (Ki0, R) для всех Ki0 B2(K ).

Теорема 1. Сложность C(A1) алгоритма A1 есть O(n5m).

Теорема 2. Сложность C(A2) алгоритма A2 есть C(A2)= O(n2(n9 + m)).

Доказательства теорем рассмотрены в [3].

Таким образом, оценена сложность алгоритмов решения задачи синтеза групповой классификации. Для предложенных алгоритмов A1, A2, эта сложность полиномиальная. Максимальная степень полинома не превышает шестой степени, причем пятой степени по отношению к мощности множества M, равной n и первой степени по отношению к количеству исходных алгоритмов классификации, равному m. Этим подтверждается возможность реального использования алгоритмов при решении задачи синтеза групповой классификации Zc.

Литература 1. Айдарханов М.Б. Метрический и структурный подходы к построению групповых классификаций. – Алматы: Гылым, 1994. – 56 с.

2. Aidarkhanov M.B. Metric and Structural Approaches to the Construction of Group Classifications. – Pattern Recognition and Image Analysis, Vol.4, N 4, 1994, pp.372 – 389.

3. Айдарханов М.Б., Амиргалиев Е.Н. Исследование сложности решения синтеза групповых решении в пространстве классификаций // Известия НАН Азербайджана, Сер. физ.-мат.и техн. наук, 2004,Том XXIV, №3, стр.176-182.

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

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

Метрика Евклида, используемая для определения расстояния между точками, x1, x(1) RE (x1, x2 ) = (x1 - x2 )T (x1 - x2 ) удовлетворяет всем аксиомам расстояния, она удобна для определения расстояния между двумя точками, например, между точкой наблюдаемых параметров и центром (выборочным средним) класса. Она не учитывает распределение точек в классе.

Метрика Махаланобиса описывается, как 2 -(2) RM (x, X ) = (x - x)T C (x - x), где x – выборочное среднее класса Х. Она представляет собой квадратичную форму, где С-1 – матрица, обратная корреляционной для рассматриваемого класса.

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

lim RM (x, X ) =.

(3) Di Метрика Махаланобиса совпадает с Евклидовой в случае, если класс представляет собой вектор реализаций нормированных (дисперсии Di=1, i=1,…, n) независимых (ковариации Kij=0, i,j=1,…, n, ij) случайных величин. Если дисперсии больше 1, то расстояние Махаланобиса меньше 2 Евклидова, если меньше, то RM > RE. Проверка аксиом расстояния затруднена тем, что метрика используется для определения расстояния между разнородными объектами. Расстояние между двумя точками согласно (3) почти всегда бесконечно велико. Исключением является случай, рассмотренный в приложении, который можно считать доказательством, что RM (x, x) 0. Метрику Евклида можно, как и метрику Махаланобиса, представить в виде квадратичной формы, матрицей которой является единичная матрица:

(4) RE (x1, x2 ) = (x1 - x2 )T E(x1 - x2 ) Метрика Махаланобиса может также использоваться и для измерения расстояния между двумя классами Х1 и Х2. Для этого используют среднее взвешенное расстояний Махаланобиса от выборочных средних:

~2 (5) RM (X1, X ) = RM (x1, X ) + (1- )RM (x2, X1 ).

Такая метрика неудобна, т.к. если класс Х1 состоит из единственной точки ~х1, то RM (x1, X ) RM (x1, X ). Рассмотрим обобщенную метрику 2 Евклида - Махаланобиса, определяющую расстояние между двумя классами Х1 и Х2, в виде квадратичной формы (6) RG (X1, X ) = (x1 - x2 )T A-1(x1 - x2 ), где x1 и x – средние выборочные классов, матрица А-1 является обратной матрицей произведения (7) A=(C1+E)(C2+E), C1 и C2 – корреляционные матрицы для первого и второго классов соответственно. Для любых двух классов Х1 и Х2 у которых x1 = x2, расстояние RG (X1, X ) = 0. Если класс Х1 представляет собой точку, то соответствующая ему корреляционная матрица состоит из нулей и мы получаем расстояние, аналогичное расстоянию Махаланобиса, с той 2 разницей, что RG (x1, X ) = RE (x1, x2 ) в случае если дисперсия Di=0, (i=1, …, n). Если оба класса представляют собой точки, то 2 RG (x1, x2 ) = RE (x1, x2 ). Такая метрика удобна для решения задач распознавания образов, в которых некоторые параметры, описывающие наблюдаемые объекты, не изменяются. Рассмотрим, в качестве примера, задачу классификации летательных аппаратов [1]. В табл.1 приведены характерные размеры некоторых отечественных самолетов, взятые из открытых источников. Данные по размаху крыльев самолетов Су практически одинаковы. Из-за того, что дисперсия размаха крыльев мала, расстояние Махаланобиса от некоторой точки до класса Су очень велико.

В результате получаем неприемлемый ответ.

Табл. 1. Характерные размеры некоторых отечественных самолетов Модель самолета Длина самолета (м) Размах крыльев (м) Высота (м) Миг-23 16,7 13,46 5,Миг-25 19,75 14,015 5,Миг-27 17,1 14 Миг-29 17,32 11,36 4,Миг-31 22,69 13,46 5,Су-27 21,935 14,7 5,Су-30 21,94 14,7 6,Су-32 22 14,7 5,Су-33 21,19 14,7 5,Су-35 22,18 14,7 6,Су-37 22,183 14,698 6,Су-39 21,9 14,7 5,Расстояние Евклида не учитывает корреляционных зависимостей в классах, поэтому оно также приводит к ошибкам. Расстояние RG (x, X ) свободно от указанных выше недостатков, что позволяет правильно идентифицировать объект. Таким образом, методы измерения расстояния с использованием метрики Махаланобиса непригодны в случае, когда значение хотя бы одного элемента на главной диагонали корреляционной матрицы, описывающей класс, достаточно мало, то есть, когда дисперсия какого-либо показателя мала. При этом расстояние Махаланобиса оказывается неоправданно велико. Предложенная метрика, учитывает корреляционные свойства классов, таким образом, что расстояние между точкой и классом стремится к расстоянию Евклида когда дисперсии параметров класса стремятся к нулю.





Работа поддержана грантом РФФИ № 03-01-00808.

Литература 1. Пережигин А.А., Хачумов В.М. Обнаружение и автоматическое определение параметров летательного объекта на видео потоке. - Информационные технологии и вычислительные системы, № 1, 2005, с. 38-48.

Метод коротких корреляционных функций в задачах структурирования сигналов сложной природы В.Е. Анциперов (Москва) Институт радиотехники и электроники РАН (www.cplire.ru) В докладе излагаются результаты исследования динамики параметров коротких корреляционных функций случайных, хаотических сигналов. В центре внимания находится проблема определения участков квазипериодического поведения этих сигналов и моменты смены колебательных режимов. Определяются связанные с корреляционными функциями количественные характеристики типа степени корреляции, основной частоты и т.д. На основе временной зависимости боковых максимумов корреляционных функций построены инструментальные оценки параметров степени квазипериодичности, длительности участков квазипериодичности, периода основнго тона и т.д. Подобный анализ заданной реализации случайного процесса поволяет сформировать его целостный образ и на его основе судить о поведении источника сигнала в терминах его динамики – для динамических систем, в терминах текстурного состава для изображений, в терминах передаваемой информации в случае хаотического кодирования. В докладе приведены результаты экспериментального применения рассматриваемой методологии к сигналам биологической природы – речевым сигналам и балистокардиографическим данным.

Основы методологии Участки квазипериодического поведения сигнала определим таким образом, что в их пределах реализация S(t) может быть представлена (по аналогии с квазигармоническим сигналом) в форме:

t (1) S(t) = A(t)F( + (t)), T где F[…] – периодическое, с периодом 1, продолжение произвольной, заданной на интервале [0,1] формы колебаний F[x] :

(2) F(x + k) = F(x) k = 0, ±1,±2,..., Т –период, A(t) и (t) – медленно меняющиеся на периоде Т амплитуда и фаза, обуславливающие отличие сигнала от строго периодичесого.

Выделим при помощи взвешивающего окна (t) - симметричной функции длительности ~T, (±)=0 два близких фрагмента сигнала S1(t) и S2 (t) соответствующих моментам времени t1 иtсоответственно:

S1(t) = (t - t1)S(t), S2 (t) = (t - t2 )S(t).

Совместим оба фрагмента в начале координат и в качестве меры их подобия возьмем скалярное произведение нормированных версий:

S (t'+t1)S2 (t'+t2 )dt' (3) R(t, ) = 1 S 2 (t')dt' S 2 (t')dt' - где t = (t2 + t1) / 2 – анализируемый момент времени, = (t2 - t1).

Короткая корреляционная функция (ККФ) R(t,) (3) по структуре подобна нормированным автокорреляционным функциям (АКФ) стационарных сигналов, но в общем случае зависит от времени t. Легко показать, что как и АКФ она всегда имеет по в нуле единичный максимум. Если бы сигнал S(t) был строго периодичен, то, в силу (2) периодичной по была бы и R(t,), т.е. имела бы единичные боковые максимумы при =±T, ±2T и т.д. В случае нестрогой периодичности (квазипериодичности) боковые максимумы понижаются и, оказывается, что их величины (в особенности у первых максимумов при =±T) оказываются исключительно полезными для анализа поведения сигнала.

Подробный анализ зависимости R(t,) (3) от факторов A(t), (t) и (t) приводит к следующим результатам. В предположении T > TA > T, где TA –характерное время огибающей A(t), R(t,) факторизуется к виду:

(4) R(t, ) = R0 ( )(t, ), где R0 ( ) – АКФ строго периодического сигнала F(t) и (t,) - ККФ медленно меняющейся амплитуды A(t). Рис.1 иллюстрирует эффект уменьшения основных максимумов R0 ( ) засчет нестационарнности, обусловленной изменяющейся амплитудой:

Искажающий фактор (t,) (4) при небольших, например, ~T приобретает вид параболы:

1 n(t) (5) (t, ) 1-, 2 T где параметр n(t) связан с вариабельностью огибающей A(t) и имеет смысл числа ее «осциляций» на анализируемом участке длительностиT : его малые значения характеризуют фрагмент сигнала как периодический, большие ~T /T – как, с точки зрения периодичности, безструктурный.

Замечательной особенностью n(t) является то, что он легко находится по ККФ) R(t,) (3): в соответствии с (4) и (5) этот параметр равен величине первого бокового максимума (при =T):

T (6) n(t) 2[1- R(t,TM )], TM где TM - положение бокового максимума – основной период колебаний.

Экспериментальные результаты Динамика нормированного к единице параметра n(t) исследовалась применительно к сигналам сложной природы – речевым сигналам и балистокардиографическим записям. На Рис.2 и Рис.3 приведены соответствующие примеры:

Pages:     || 2 | 3 | 4 | 5 |   ...   | 58 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.