_учебник_ Журавлев Ю.И. Распознавание. Математические методы. Программная система. Практические применения (2005) (_учебник_ Журавлев Ю.И. Распознавание. Математические методы. Программная система. Практические применения (2005).doc)

158

Ю.И.Журавлев, В.В.Рязанов, О.В.Сенько

РАСПОЗНАВАНИЕ

Математические методы. Программная система. Практические применения.

ИЗДАТЕЛЬСТВО ФАЗИС

МОСКВА 2005

Введение

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

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

• распознавание (классификация, диагностика) ситуаций, явлений, объектов или процессов с обоснованием решений;

• прогнозирование ситуаций, явлений, процессов или состояний по выборкам динамических данных;

• кластерный анализ и исследование структуры данных;

• выявление существенных признаков и нахождение простейших описаний;

• нахождение эмпирических закономерностей различного вида;

• построение аналитических описаний множеств (классов) объектов;

• нахождение нестандартных или критических случаев;

• формирование эталонных описаний образов.

Первые работы в области теории распознавания и классификации по прецедентам появились в 30-х годах прошлого столетия и были связаны с байесовской теорией принятия решений (работы Неймана, Пирсона /74/), применением разделяющих функций к задаче классификации (Фишер /63/), решением вопросов проверки гипотез (Вальд /85/). В 50-х годах появились первые нейросетевые модели распознавания (перцептрон Розенблата /48/), связанные с успехами в моделировании головного мозга. К концу 60-х годов уже были разработаны и детально исследованы различные подходы для решения задач распознавания в рамках статистических, перцептронных моделей, и моделей с разделяющими функциями. Итоги данных и последующих исследований были представлены в ряде монографий /1, 2, 8, 11, 25, 30, 31, 33, 41, 45, 48, 55, 57, 58, 64, 73, 75/. Большой вклад в развитие теории распознавания и классификации внесли советские и, в последующем, российские ученые: Айзерман, Браверман, Розоноэр (метод потенциальных функций /2/), Вапник, Червоненкис (статистическая теория распознавания, метод «обобщенный портрет» /11/), Мазуров (метод комитетов /42, 43, 45/), Ивахненко (метод группового учета аргументов /33/), Загоруйко (алгоритмы таксономии и анализа знаний /30, 31/), Лбов (логические методы распознавания и поиска зависимостей /41/). Интенсивные исследования проводились с конца 60-х годов в ВЦ АН СССР (в настоящее время ВЦ им А.А.Дородницына РАН). Еще в начале 60-х академиком РАН Журавлевым был предложен тестовый алгоритм распознавания – логический метод эффективного решения задач распознавания при малом числе обучающих прецедентов /15/. В дальнейшем на базе этого алгоритма Журавлевым был построен новый класс распознающих процедур – алгоритмы вычисления оценок /27/, а затем введена и исследована алгебраическая теория распознавания /26, 28/. В этом направлении фундаментальные результаты получили также чл.корр. РАН Рудаков (общая теория проблемно-ориентированного алгебраического синтеза корректных алгоритмов /49/, чл.корр. РАН Матросов (статистическое обоснование алгебраического подхода /44/), Рязанов (оптимизация моделей классификации /50/, коллективные решения задач кластерного анализа /51,52/), Дюкова (асимптотически-оптимальные логические алгоритмы /21,22/), Сенько (алгоритмы взвешенного статистического распознавания /56/), Асланян (логические алгоритмы распознавания) /60/, Донской (решающие деревья /16, 17/) и многие другие исследователи России, СНГ и дальнего зарубежья.

Разработки программных систем анализа данных и прогноза по прецедентам также активно ведутся в России и ведущих зарубежных странах. Прежде всего, это статистические пакеты обработки данных и визуализации (SPSS, STADIA, STATGRAPHICS, STATISTICA, SYSTAT, Олимп:СтатЭксперт Prof., Forecast Expert, и другие), в основе которых лежат методы различных разделов математической статистики – проверка статистических гипотез, регрессионный анализ, дисперсионный анализ, анализ временных рядов, и др. Использование статистических программных продуктов стало стандартным и эффективным инструментом анализа данных, и, прежде всего, начального этапа исследований, когда находятся значения различных усредненных показателей, проверяется статистическая достоверность различных гипотез, находятся регрессионные зависимости. Вместе с тем статистические подходы имеют и существенные недостатки. Они позволяют оценить (при выполнении некоторых условий) статистическую достоверность значения прогнозируемого параметра, гипотезы или зависимости, однако сами методы вычисления прогнозируемых величин, выдвижения гипотез или нахождения зависимостей имеют очевидные ограничения. Прежде всего находятся усредненные по выборке величины, что может быть достаточно грубым представлением об анализируемых или прогнозируемых параметрах. Любая статистическая модель использует понятия «случайных событий», «функций распределения случайных величин» и т.п., в то время как взаимосвязи между различными параметрами исследуемых объектов, ситуаций или явлений являются детерминированными. Само применение статистических методов подразумевает наличие определенного числа наблюдений для обоснованности конечного результата, в то время как данное число может быть существенно больше имеющегося или возможного. Т.е. в ситуациях анализа в принципе непредставительных данных, или на этапах начала накопления данных, статистические подходы становятся неэффективными как средство анализа и прогноза.

В последние годы появились узкоспециализированные пакеты интеллектуального анализа данных. Для данных пакетов часто характерна ориентация на узкий круг практических задач, а их алгоритмической основой является какая-либо одна из альтернативных моделей, использующая нейронную сеть, решающие деревья, ограниченный перебор, и т.п. /20/. Ясно, что подобные разработки существенно ограничены при практическом использовании. Во-первых, заложенные в них подходы не является универсальными относительно размерностей задач, типа, сложности и структурированности данных, величины шума, противоречивости данных, и т.п. Во-вторых, созданные и «настроенные» на решение определенных задач, они могут оказаться совершенно бесполезными для других. Наконец, множество задач, представляющих интерес практическому пользователю, обычно шире возможностей отдельного подхода. Например, пользователю может быть важно иметь численную характеристику надежности некоторого прогноза, но «решающее дерево» ее не вычисляет. «Нейронная сеть» выступает в роли «черного ящика», предлагающего некоторый прогноз без его обоснования. Логические методы распознавания позволяют выявлять логические закономерности в данных и использовать их при прогнозировании, но при наличии линейных зависимостей между признаками и прогнозируемой величиной точность прогноза, сделанного «линейной машиной», может быть заметно выше.

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

Теоретические основы практической реализации идеи решения задач анализа данных коллективами алгоритмов были разработаны в ВЦ РАН в рамках алгебраического подхода для решения задач распознавания (логическая и алгебраическая коррекция алгоритмов) в 1976-1980 /25, 26, 28/ и комитетного синтеза классификаций для задач кластерного анализа (автоматической классификации) в 1981-1982 годах /51,52/. Позднее появились исследования в данной области и в других странах.

В алгебраическом подходе новые алгоритмы распознавания строятся в виде полиномов над исходными алгоритмами (применение алгебраических корректоров) или в виде специальных булевских функций (логических корректоров). Теоретическим базисом является теорема о существовании для произвольного алгоритма распознавания ему эквивалентного стандартного алгоритма, представимого в виде произведения распознающего оператора и решающего правила /26/. Это позволяет описать основные результаты вычислений произвольных алгоритмов распознавания в стандартном виде с помощью числовых матриц оценок («мер принадлежности» объектов к классам) и информационных матриц окончательных ответов (классификаций). Матрицы оценок различных распознающих алгоритмов являются «исходным материалом» для синтеза в виде полиномов новых матриц оценок, которые задают основу нового скорректированного решения задачи распознавания. Алгебраический подход позволяет строить алгоритмы, безошибочные на «обучающем» материале или совершающие меньшее число ошибок, чем каждый из исходных алгоритмов.

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

В настоящей монографии представлено современное состояние в области практических методов распознавания, классификации и анализа данных, и приведено краткое описание программной системы «РАСПОЗНАВАНИЕ», включающей основные подходы.

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

В первой главе рассмотрена задача распознавания (классификации с учителем) и современное состояние в области практических методов для ее решения. Рассмотрены основные этапы в развитии теории и практики распознавания: создание эвристических алгоритмов, модели распознавания и оптимизация моделей, алгебраический подход к коррекции моделей. Приведены краткие описания основных подходов (основанных на построении разделяющих поверхностей, потенциальных функций, статистические и нейросетевые модели, решающие деревья, и другие). Расширенные описания методов, включенных в систему РАСПОЗНАВАНИЕ, приведены при необходимости в третьей главе. Более подробно описаны основные подходы и алгоритмы комбинаторно-логических методов распознавания (модели вычисления оценок или алгоритмы, основанные на принципе частичной прецедентности), разработанные в ВЦ РАН. В основе данных моделей лежит идея поиска важных частичных прецедентов в признаковых описаниях исходных данных (информативных фрагментов значений признаков, или представительных наборов). Для вещественных признаков находятся оптимальные окрестности информативных фрагментов. В другой терминологии, данные частичные прецеденты называют знаниями или логическими закономерностями, связывающими значения исходных признаков с распознаваемой или прогнозируемой величиной. Найденные знания являются важной информацией об исследуемых классах (образах) объектов. Они непосредственно используются при решении задач распознавания или прогноза, дают наглядное представление о существующих в данных взаимозависимостях, что имеет самостоятельную ценность для исследователей и может служить основой при последующем создании точных моделей исследуемых объектов, ситуаций, явлений или процессов. По найденной совокупности знаний вычисляются также значения таких практически полезных величин, как степень важности (информативности) признаков и объектов, логические корреляции признаков и логические описания классов объектов, и решается задача минимизации признакового пространства.