Автореферат (Разработка метода направленного перебора альтернатив в задачах классификации объектов на основе теоретико-информационного подхода)

На правах рукописиСавченко Андрей ВладимировичРАЗРАБОТКА МЕТОДА НАПРАВЛЕННОГО ПЕРЕБОРА АЛЬТЕРНАТИВВ ЗАДАЧАХ КЛАССИФИКАЦИИ ОБЪЕКТОВНА ОСНОВЕ ТЕОРЕТИКО-ИНФОРМАЦИОННОГО ПОДХОДАСпециальность 05.13.18 – «Математическое моделирование,численные методы и комплексы программ»АВТОРЕФЕРАТдиссертации на соискание ученой степеникандидата технических наукМосква – 2010Работа выполнена на кафедре информационных систем и технологий Нижегородского филиала Государственного университета – Высшей школы экономикиНаучный руководитель:кандидат технических наук,доцент Бабкин Эдуард АлександровичОфициальные оппоненты:доктор технических наук,доктор экономических наукпрофессор Орлов Александр Иванович,кандидат технических наук,доцент Акатьев Дмитрий ЮрьевичВедущая организация:Институт прикладной физики РоссийскойАкадемии НаукЗащита состоится “ 25 ” ноября 2010 г.

в 12.00 часов на заседании диссертационного совета Д 212.048.09 при Государственном университете – Высшей школеэкономики по адресу: 105679, Москва, ул. Кирпичная, д. 33, ауд. 503.С диссертацией можно ознакомиться в библиотеке Государственного университета – Высшей школы экономики по адресу: 101990, Москва, ул. Мясницкая, д. 20.Автореферат разослан “____” октября 2010 г.Ученый секретарь диссертационного советадоктор технических наук2В.А.

ФомичевОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫАктуальность темы. Классификация объектов как направление исследований иодновременно теоретическая база для решения прикладных задач распознаванияобразов активно развивается с середины XX века. Большой вклад в его развитиевнесли отечественные ученые В.Н. Вапник, В.М.

Глушков, А.Л. Горелик, Ю.И.Журавлёв, Н.Г. Загоруйко, А.А. Харкевич, Я.З. Цыпкин, А.Я. Червоненкис и др.За рубежом одними из основоположников классификации применительно к распознаванию образов считаются Ф. Розенблатт и Б. Уидроу. В дальнейшем их идеибыли развиты Л. Рабинером, К.

Фукунагой, П. Хартом, Дж. Хопфилдом и др.Среди систем классификации особенно широкое распространение в настоящее время получили системы автоматического распознавания изображений.Действительно, цифровые изображения являются одним из основных способовпредставления информации в промышленности, медицине, и, конечно, в экономическом анализе (диаграммы, таблицы, графики и т.п.). Одной из наиболее актуальных прикладных задач в этой области считается ([Eickeler et al, 2000]1) распознавание людей по фотографиям их лиц.

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

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

Проблема точностиособенно усиливается, если объем базы эталонных данных составляет тысячиединиц, что приводит, к усложнению методов распознавания и, как следствие, невозможности реализации существующих алгоритмов ([Cover, Hart, 1968]2) в ре-1Eickeler S., Jabs M., Rigoll G. Comparison of Confidence Measures for Face Recognition // Fourth IEEE InternationalConference on Automatic Face and Gesture Recognition (FG'00). 2000. P.257-263.2Cover T.M., Hart P.E. Nearest Neighbor Pattern Classification. IEEE Trans. Information Theory. 1968.

Vol. 13. P.21-27.3жиме реального времени. Без применения современных моделей изображений иновых вычислительных методов их классификации данная проблема большихбаз эталонов ([Tse, Lam, 2008]3) не может быть преодолена.Общепринятой моделью здесь служит понятие образа ([Цыпкин, 1968]4) изображения группируются по принципу их близости (в некотором смысле) в набор кластеров. Система распознавания тогда решает задачу классификации изображений на наборе наиболее информативных эталонов из каждого кластера([Орлов, 2009]5). К сожалению, такая редукция базы эталонов к центрам кластеровзачастую не позволяет преодолеть отмеченную проблему, т.к.

число выделенныхкластеров может быть велико. А многочисленные методы, основанные на математическом аппарате деревьев решений ([Zhang, Srihari, 2004]6), оказываются эффективными лишь в тех редких случаях, когда группы однородных изображенийв пределах каждого кластера сходны между собой, но резко отличаются от объектов из других кластеров. Поэтому на практике классификация в реальном времениосуществляется за счет потерь в точности классификации ([Hastie et al, 2009]7).Со всех перечисленных точек зрения несомненный интерес представляетмоделированиераспознаванияизображенийнаосноветеоретико-информационного подхода ([Zhao, Chellappa, 2005]8) и общесистемного принципаминимума информационного рассогласования (МИР) в метрике КульбакаЛейблера ([Кульбак, 1967]9).

Основанная на этом принципе информационная теория восприятия речи показала высокие результаты ([Савченко, 2007]10) в задаче3Tse S.-H., Lam K.-M. Efficient face recognition with a large database // 10th IEEE International Conference on Control,Automation, Robotics and Vision. 2008. P.944-9494Цыпкин Я.З. Адаптация и обучение в автоматических системах. - М: Наука, 1968.

- 400 с.5Орлов А.И.О развитии математических методов теории классификации//Заводская лаборатория. - 2009. - №75(7).-С.51-636Zhang B., Srihari S.N. Fast k-Nearest Neighbor Classification Using Cluster-Based Trees. IEEE Trans. on Pattern Analy-sis and Machine Intelligence. 2004. Vol.26. №4. P.

525-528.7Hastie, T., Tibshirani R., Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. 2nded. Springer-Verlag, 2009. 746 p.8Zhao W., Chellappa R. ed. Face Processing: Advanced Modeling and Methods. Elsevier/Academic Press, 2005.

768 p.9Кульбак С. Теория информации и статистика / Пер. С англ. М.: Наука, 1967. - 408 с.10Савченко В.В. Информационная теория восприятия речи//Известия вузов. Радиоэлектроника.-2007. - №6. - с.3-9.4автоматического распознавания речи. Между тем, не все преимущества принципаМИР получили необходимое освещение и развитие.

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

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

Реализация предложенного вычислительного метода в виде комплекса программ для проведения экспериментальных исследований его эффективности в реальных задачах распознавания изображений с базой эталонов большого объёма.5. Исследование возможностей и перспектив применения метода направленного перебора в других актуальных задачах классификации.Методы исследования. В работе использовались современные методы теориираспознавания образов, теории вероятностей и математической статистики, имитационного моделирования, теории информации, теории сигналов.Научная новизна работы состоит в следующем1. Предложена новая теоретико-вероятностная модель полутонового изображения с целью применения к задаче распознавания на основе принципа минимума5информационного рассогласования в метрике Кульбака-Лейблера.2.

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