Научные направления - Анализ данных и распознавание образов


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

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

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

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

Большинство математических проблем, возникающих в рамках анализа данных и распознавания образов, относится к классу труднорешаемых (NP-трудных) оптимизационных задач. Универсальный метод решения подобных задач – выбор наилучшего (оптимального) решения среди всех допустимых вариантов решения путем их прямого перебора. Однако этот универсальный метод оказывается малопригодным для практической реализации на компьютерах, так как число допустимых вариантов решения и вместе с ним время решения задачи растет экспоненциально с увеличением её размерности. Эта экспоненциальная зависимость стимулирует поиск таких приближенных алгоритмов с оценками точности решения, что время решения задачи с помощью этих алгоритмов является полиномом от размерности задачи.

Пример содержательной задачи.

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

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

Еще несколько примеров содержательных задач приведено ниже.

Задача 2. Идентифицировать (распознать) личность по результатам измерения каких-либо (физических, биологических и т.п.) характеристик человека (например, распознать личность по отпечаткам пальцев, голосу, радужке глаз и т.п.).

Задача 3. Построить алгоритм диагностики (распознавания) заболевания человека по результатам медицинских анализов.

Задача 4. Определить истинность (правда/ложь) высказываний человека по результатам измерения каких-либо косвенных характеристик (детектор лжи).

Задача 5. Определить благонадежность (платежеспособность) клиента банка по результатам ответов на анкетные вопросы.

Задача 6. По результатам «посещения» сайтов в Интернете охарактеризовать личность.

Задача 7. Распознать (классифицировать) тип объекта - военный или гражданский - по результатам космической съемки.

Задача 8. Построить алгоритм диагностики состояния технического устройства (например, исправно или неисправно) по результатам измерения каких-либо значимых характеристик.

Задача 9. Построить алгоритм определения перспективности месторождения полезных ископаемых по результатам геологоразведки.

Задача 10. По результатам геофизического мониторинга оценить вероятность возникновения землетрясения.

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

Преподаватели: