Методы решения задач распознавания образов комбинированного типа

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

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

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

Упоминание о первом из них — группировке встречается еще у Демокрита в «Письме к ученому соседу». Он пишет: «Если тебе, мой друг, нужно разобраться в сложном нагромождении фактов или вещей, ты сначала разложи их на небольшое число куч по похожести. Картина прояснится, и ты поймешь природу этих вещей». Этот способ познания — создание классификационных структур на множестве объектов схожей природы широко используется наукой и в наши дни. Его формализация и развитие делается в рамках научного направления, которое называется большим количеством синонимов: таксономия, группировка, кластерный анализ, автоматическая классификация, обучение без учителя, самообучение и т. д. В задаче таксономии упрощение информации происходит за счет сокращения числа рассматриваемых объектов. Вместо изучения каждого отдельного представителя выборки появляется возможность сосредоточить внимание на изучении классов сходных объектов. Похожесть в рамках класса позволяет заменять множества объектов из этого класса неким эталонным (идеальным) образцом.

Этой задачей занимались такие известные российские и зарубежные ученые как Воронин Ю. А., Загоруйко Н. Г., Ивахненко А. Г., Шлезингер М. И., Ватанабе М. С., Себестиан Г. С, Фукунага К. и другие. Далее мы будем обозначать задачу таксономии символом S.

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

Исследованиям задачи построения решающего правило посвящено огромное количество работ. Значительный вклад в развитие этой области внесли Журавлев Ю. И., Лбов Г. С., Вапник В. Н, Червоненкис А. Я, Мазуров В. Д, Симон, Фу К., Михальский Р. С. и многие другие исследователи. Задачу построения решающего правила далее мы будем обозначать символом D.

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

Методики выбора информативной системы признаков активно разрабатывались в рамках ИАД такими исследователями как Айвазяном С. А., Барабашом, Мерилом, Грином и рядом других. Далее эту задачу мы будем обозначать символом X.

Все описанные выше методы упрощения информации и соответствующие им задачи распознавания образов могут использоваться по отдельности. Однако самая совершенная система анализа информации — человеческий мозг — обычно решает их одновременно. То есть выбор системы информативных признаков, построение некоторой классификации объектов и решающего правила для различения созданных классов происходит параллельно и взаимосвязано. Аналогом реализации такого комплексного подхода в ИАД является задача комбинированного типа SDX [16].

Объект исследований. Задача SDX считается сложной и общего подхода к ее решению не существует. Прежде чем приступить к решению этой задачи, мы рассмотрим более простые задач комбинированного типа SX, DX, SD, в каждой из которых одновременно используются два из трех описанных выше приема упрощения информации [16]. Это позволит нам создать необходимый фундамент для решения задачи SDX непосредственно. Именно задачи распознавания образов комбинированного типа являются основными объектами исследования в данной работе. Комбинированные задачи хорошо согласуются с механизмами анализа информации, используемыми человеком, и S открывают новые возможности для решения сложных плохо обусловленных прикладных задач.

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

Основные направления исследований. Требование согласованности алгоритмов здесь оказывается очень важным. Для его выполнения необходимо иметь единый базис для решения всех задач. В этой работе таким базисом стали функции конкурентного сходства (FRiS-функции) [68]. Выбор функций конкурентного сходства в качестве основы для большинства представленных алгоритмов решения задач комбинированного типа объясняется еще и тем, что основным методом исследования для нас является моделирование интеллектуальной деятельности человека при решении комбинированных задач. FRiS-функция оказывается при этом особенно эффективной, так как она моделирует психофизиологические особенности человеческого восприятия при оценке близости между объектами.

Методы исследований Помимо имитационного моделирования для решения задач распознавания образов комбинированного типа привлекается аппарат методов оптимизации и математическая статистика.

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

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

На защиту выносятся следующие основные результаты:

• В рамках исследования применимости FRiS-функций показана их эффективность в качестве критерия информативности при решении задачи одновременного построения решающего правила и выбора наиболее информативного подпространства признаков. Предложена методика оценки надежности получаемых информативных систем признаков, их «неслучайности». Также предложена методика оценки надежности распознавания каждого нового объекта при использовании решающих правил, полученных с помощью алгоритма FRiS-Stolp.

• Разработан алгоритм FRiS-Tax для решения задачи комбинированного типа — одновременного построения таксономии и решающего правила, ее описывающего. Этот алгоритм не только достаточно точно воспроизводит действия человека эксперта при решении задач таксономии в пространствах малых размерностей, но и позволяет автоматически определять оптимальное число таксонов из заданного диапазона.

• Сформулированы основные требования, предъявляемые к «естественным» классификациям. Установлена связь между задачей построения «естественной» классификации и одной из задач распознавания образов комбинированного типа — задачей построения таксономии с одновременным выбором наиболее информативного подпространства признаков. Для решения данной задачи разработан алгоритм NatClass.

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

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

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

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

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

• KDS-2001, 2007 (Knowledge-Dialog-Solutions),.

• PRIA-2004, 2007 (Pattern Recognition and Image Analysis),.

• PRIP-2005, 2007 (Pattern Recognition and Image Processing),.

• MMPO-12, 13 (Математические Методы Распознавания Образов),.

• ACIT-SE-2005 (Automation, Control and Information Technology),.

• BGRS-2006 (Bioinformatics of Genome Regulation and Structure),.

• 30HT-2007 (Знания, Онтологии, Теории).

Отдельные этапы работы прошли экспертизу в ходе выполнения проектов, поддержанных грантами РФФИ (проекты № 02−01−82-а, № 05−01−241-а).

Публикации. По теме диссертации опубликованы 16 работ, из них 2 научные статьи в журналах, входящих в перечень изданий, рекомендованных ВАК РФ, 2 научные статьи в ведущих рецензируемых журналах, 2 — в сборниках научных трудов, 10 — в сборниках трудов конференций.

Структура работы. Диссертационная работа изложена на 121 страницах и состоит из введения, обзора литературы (глава 1), четырех глав, содержащих основные результаты, и заключения. Иллюстративный материал представлен 24 рисунками и 1 таблицей.

Список литературы

включает 77 ссылок.

Выводы по пятой главе.

1.Задача SDX (одновременного выбора наилучшего разбиения множества объектов на классы, решающего правила для их распознавания и наиболее информативного подпространства признаков) может рассматриваться как задача систематизации и структуризации информации в самом общем виде [76].

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

Заключение

.

Разработка методов решения задач распознавания образов комбинированного типа является актуальным направлением исследований. Сами задачи такого вида лучше согласуются с общими механизмами анализа информации, используемыми человеком. Объясняется это тем, что в силу особенностей восприятия человеческий мозг обычно решает несколько базовых задач по систематизации и структуризации новых данных одновременно и согласованно. Таким образом, рассматривая возникающие прикладные задачи анализа данных как задачи комбинированного типа, мы можем имитировать действия человека-эксперта и в некоторых случаях заменять его. Кроме того, комбинированный подход позволяет минимизировать число дополнительных предположений относительно анализируемой выборки, а получаемые решения оказываются более устойчивыми к ошибкам и выбросам в исходных данных. В связи с этим особенно полезным комбинированный подход оказывается при решении задач Data Mining в условиях, которые не позволяют применить методы классической статистики. Ярким примером являются задачи, в которых число объектов М меньше числа описывающих их характеристик N и, кроме того, априорная информация о распределениях объектов, о зависимостях между объектами и между признаками отсутствует.

Наиболее общей задачей комбинированного типа, интересующей нас в данном исследовании, является задача SDX, когда одновременно решается задача таксономии (S), построения решающего правила для ее описания (D) и выбора информативного пространства признаков (X). Для корректного решения этой сложной задачи необходимо уметь решать все три основные задачи распознавания образов согласовано.

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

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

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

Было обнаружено, что в процессе решения задачи DX целесообразно опираться не на все объекты выборки, а лишь на некоторый набор эталонных образцов (столпов). Среднее значение функции конкурентного сходства, вычисленное с опорой на набор столпов, является наиболее эффективным критерием выбора информативной для распознавания системы признаков. Кроме того, величина функции конкурентного сходства контрольного объекта с образом, к которому он был отнесен, дает возможность сопроводить принятое решение оценкой уверенности в правильности этого решения.

2.

Введение

в рассмотрение «виртуального конкурента» позволило определить редуцированную функцию конкурентного сходства для неклассифицированной выборки. Предложенный алгоритм FRiS-Tax, опирающийся на редуцированную FRiS-функции, в процессе решения задачи SD позволяет строить разбиение выборки на адекватные с точки зрения человеческого восприятия кластеры и классы. При этом кластеры представляют из себя мелкие линейно разделимые группы объектов, имеющие простую форму, которые, объединяясь, образуют более сложные структуры «классы» произвольной формы. Использование среднего значения FRiS-функции для оценки качества таксономии позволило автоматизировать процесс выбора оптимального числа кластеров и классов в создаваемой таксономии.

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

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

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

5. Все предложенные в работе алгоритмы проверялись как на различных модельных задачах, так и на реальных данных. Такая проверка подтвердила их применимость и эффективность в процессе решения задач распознавания образов комбинированного типа. Кроме того, большая часть описанных здесь алгоритмов вошла в пакет программ «Спектран» для интеллектуального анализа спектральных характеристик химических веществ, созданного по заказу Института Криминалистики ФСБ. Данная разработка получила высокую оценку заказчика.