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

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

^^ГАДЖИЕВ Тажудин Сиражудинович

МЕТОДИКА ИЗУЧЕНИЯ ПРОЦЕДУР РАСПОЗНАВАНИЯ НА ОСНОВЕ СИНТЕЗА ПЛОСКИХ ПРЕДСТАВЛЕНИЙ МЕТРИЧЕСКИХ КОНФИГУРАЦИЙ

Специальность 05.13.17 - теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

юие

Москва 1996

Работа, выполнена на кэфедре информатики и дискретной математики в Московской педагогическом государственном университете им. В.И. Ленина.

Научные руководители:

академик РАО, доктор физико-математических наук, профессор МАТРОСОВ В.Л.,

академик РАЕН, доктор физико-математических наук, профессор РУДАКОВ К.В.

Официальные оппоненты:

доктор техических наук, профессор МЕСТЕЦКИЙ Л.М.,

кандидат физико-математических наук ИСАЕВ И.В.

Ведущая организация: Центральный научно-исследовательский институт экономики, информатики и систем управления (Москва).

Защита состоится .........1996 г. в 15 часов на

заседании Диссертационного совета К 053.01.16 в Московском педагогическом государственном университете им. В.И. Ленина по адресу: 107140, Москва, Краснопрудная ул., д. 14, математический факультет МПГУ им. В.И. Ленина, ауд. 301.

С диссертацией можно ознакомиться в библиотеке МПГУ им. В.И. Ленина по адресу: 119435, Москва, ул. Малая Пироговская, д. 1.

Автореферат разослан ..... 1996 года.

Ученый секретарь Диссертационного совета

КУЗНЕЦОВ Э.И.

9)Гг

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

-г-

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

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

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

- Э -

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

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

Приведенные положения являются основными в обосновании темы предлагаемой работы.

Из сказанного вытекают цели работы:

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

2. Разработка технологии построения плоских представлений разделяющих гиперповерхностей, порождаемых алгоритмами распознавания.

3. Проведение экспериментальной проверки разработанных методов на модельных и реальных данных.

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

Практическая значимость. Результаты ориентированы на использование при анализе слокной прецедентной информации, подборе адекватных алгоритмов распознавания и при обучении специалистов в области распознавания образов. Разработанные методы уже использовались при анализе медицинской (токсикологической) и социологической информации в Вычислительном центре РАН, Институте' проблем прогнозирования АЕН и в Ситуационном центре Президента РФ.

Апробация работы и публикации. Результаты работы докладывались и обсуждались на VIх-конференции "Математические методы распознавания образов" (Пущина, 1995 г.), на научных семинарах Вычислительного центра Р1Н, на научно-методическом семинаре кафедры информатики и дискретной математики МШУ им.В.И.Ленина (май 1ЭЭ5 г.).

Структура и объем работы. Диссертация состоит из введения, четырех глав и списка литературы (51 наименование) Объем работы - 92 страницы машинописного текста.

АЕтор выражает глубокую признательность Есем сотрудникам кафедры информатики и дискретной математики ЖГУ им. В.И.Ленина за их доброжелательное отношение к его работе в годы учебы в аспирантуре и на завершающем этапе. Чувстео глубочайшей благодарности автор выражает своим научным руководителям академику РАО Матросову Виктору ЛеонядоЕичу и академику РАЕН Рудакову Константину Владимировичу, которые с огромным вниманием и терпеливостью относились к написанию автором реферируемой диссертации. .

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

....., и значения целевого метрического функционала

), где I £ и .I € {т,...,ч}. Требуется

получить плоскую модель метрической конфигурации ,

т.е. сформировать набор пар действительных чисел

Нг= (х7.у?).....Нч = такой, что р(Н{,Н^) «

где р(Н{,К,) - евклидовы расстояния между точками на плоскости. Заметим, что таких соотношений будут и

содержат они 2д переменных. Следует также заметить, что

- ? -

поскольку нас интересуют относительные характеристики типа

) £ р(.Бк,Зг), где ъ € О.....а) и I € то

можно считать, что х^ = о и ¡/1 = о.

Ставится задача приближения в среднем:

Так как задача (1.4.1) нелинейна и содержит переменных, то она чрезвычайно сложна в смысле сложности вычислений. Задачу (1.4.1) предлагается решать последовательно: считая, что размещены п точек (ть < д), определяем положение только (п,+1 )-й точки. Таким образом, вместо задачи с 2Ч неизвестны?,® получаем последовательность задач с двумя

неизвестными: пусть известны (х ,у,).....(л^.у^); ищем

(»т1+г<г'п+7) ■ Итак, задача (1.4.1) сводится к виду (1.4.2)

(1.4.1 )

р<ЯгВр - —» аШ

<.3

После элементарных преобразований получаем:

Г = пх'

Ч-Т ~ + Й + ""п+Т ~ 2*тг+тХ}* + Х1^

2

п.

п

3 V-1 о

Приравнивая нулю частную производную от Р по ¡г , имеем:

г. п Р{.тг-!-7 (аГп+Г

(1 .4.3) пхп+т - V*, - У- = О

(жЛ+7~ + Чг+Г

Так как, уравнение (1.4.3) содержит радикал, поиск его решения оказывается достаточно сложной задачей. В силу этого предлагается в (1.4.2) вместо разности расстояний использовать разность квадратов расстояний. Тогда задача

(1.4.2) приобретает вид: п

(1.4.4) Р = г{)г + (Ул+Г у,)2 - Р2ип+1)г —> 1Г.1п

Приравнивая нулю частную производную от Р по г , имеем:

__п п

3

пх . п+

, - + - ^ + -

1=1 1=1 1=1

ТЬ 7 V 71/ 1 Ь

1=1 1=1 1=1 1=1

1=1 1=1 1=1

Отсюда, группируя члены содержащие и уп+г , получаем

следующее квадратное уравнение относительно уг+? :

(1.4.5)

+ + С - 0,

Tfc 7b 7fc

где F = - Yf^ D = ~ »«mI>4 и

i—i i=i i=j

n. n n

0 = ™n+i - ^n+f^

+ ч^ХЧ - +

i=i t=? i=T

i ть iu

+ Xv.+ lJ}2i - Y?*Vl ~ Xn+lEPt.n+i + XPl.n+l*i

t=i 1=1 i=7 t=T

Предполагая, что пробегает числовой отрезок

[г .г 1 ^ДЭ min -шах '

x»in = mln(li - Pt.n+i^ 8

»«и " mBX{xt - Pt.n+fb { е t

из (1.4.5) найдем соответствующие значения ,. Искомыми значениями «г+7 к являются те, при которых ¥ имеет

минимум.

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

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

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

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

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

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

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

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

Для анализа результатов работы алгоритмов распознавания предложена и реализована следующая схема: сначала проводится триангуляция (разбиение на треугольники) полученной в

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

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

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

- 1Э -

Наконец, предложенная методика была использована для анализа реальной информации. Предметом изучения были результаты декабрьских 1ЭЭ5 г. выборов е Государственную думу по партийны!,? спискам. В качестве объектов рассматривались 43 избирательных объединения, участвовавших в выборах. Каждый объект был описан вектором из 225 чисел -процентов голосов, набранных объединением в каждом избирательном округе. На множестве объектов была введена и вычислена для каждой пары мера близости, определенная как количество синхронных изменений процентов голосов при переходах от округа к округу. Обратная к оценке близости величина рассматривалась как целевое расстояние между объектами и соответствующая метрическая конфигурация была представлена на плоскости. Полученное представление (рис. I) использовалось аналитиками Ситуационного центра Президента РФ и получило их высокую оценку.

•4?

3£

э8 з3

Г 8

' я Зй*~т42

эт Эа 18 *43

•40

6 8 5

17 935

28

5т

* г?

Иа

Рис. I

Для справки приведем список кратких названий обозначенных на рис. I номерами избирательных объединений: I. "ЖЕНЩИНЫ РОССИИ"; 2. "ДЕРЖАВА"; 3. "ДУМА-ЗБ"; 4. "ПРЕОБРАЖЕНИЕ ОТЕЧЕСТВА"; 5. "ТИХОНОВ-ТУПОЛЕВ-ТИХОНОВ"; 6. "РОССИЙСКОЕ ОБЩЕНАРОДНОЕ ДВИЖЕНИЕ"; 7. "НУР"; 8. "ФВДЕРАЛШО-ДШОКРАТИЧЕСКОЕ ДВИЖЕНИЕ"; 5. "ЗЕЫЖ-МАТЭТПКА"; 10. "МЕЖНАЦИОНАЛЬНЫЙ СОЮЗ"; II. "СТАБИЛЬНАЯ РОССИЯ"; 12. "ПОКОЛЕНИЯ РУБЕЖА"; 13. "МОЕ ОТЕЧЕСТВО"; 14. "ЗА РОДИНУ!"; 15. "ОБЩЕЕ ДЕПО"; 16. "БЛОК НЕЗАВИСИМЫХ"; 17. "НАШ ДОМ - РОССИЯ"; 18. "ПАШЙПОВА-ГУРОВ-ЛЫСЕНКО"; 19. "ЯБЛОКО"; 20. "ВПЕРЕЩ, РОССИЯ!"; 21. "89"; 22. "КЕДР"; 23. "ДЕМОКРАТИЧЕСКИЙ ВЫБОР РОССИИ"; 24. "ПРЕС"; 25. "КПРФ"; 26. "БЛОК ГОВОРУХИНА"; 27. "АССОЦИАЦИЯ АДВОКАТОВ