Автореферат (1137290)
Текст из файла
На правах рукописиСавченко Андрей ВладимировичРАЗРАБОТКА МЕТОДА НАПРАВЛЕННОГО ПЕРЕБОРА АЛЬТЕРНАТИВВ ЗАДАЧАХ КЛАССИФИКАЦИИ ОБЪЕКТОВНА ОСНОВЕ ТЕОРЕТИКО-ИНФОРМАЦИОННОГО ПОДХОДАСпециальность 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. На основе метода направленного перебора предложен новый алгоритм распознавания речи, позволяющий в несколько раз сократить объем выполняемыхвычислений по сравнению с современными методами полного перебора.Практическая ценность работы состоит в том, что метод направленного перебора и его модификации предназначены для решения задач классификации в условиях больших баз данных эталонов, когда известные методы характеризуются недостаточным быстродействием.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
