Одна из ключевых проблем информатики — разработка, исследование и реализация методов синтеза при помощи обучения алгоритмических процедур преобразования и анализа информации, предназначенных для решения задач, для которых соответствующие алгоритмы неизвестны. Эти методы составляют сердцевину математической теории алгоритмов, кибернетики и информатики. Задачи, требующие использования таких методов, возникают в связи с обработкой и преобразованием на ЭВМ структур, образованных из символов, т. е. структур, представляющих в программах искусственного интеллекта знания о проблемной области в целом и знания, относящиеся к конкретной задаче. Несмотря на универсальность задач, эти методы стали предметом интенсивных исследований, развивались и в конце концов получили оформление в виде нескольких общих математических моделей лишь в рамках одного, хотя и весьма обширного класса задач преобразования и анализа информациизадач распознавания образов.
Во второй половине 50-х годов XX в. начало формироваться новое научное направление, связанное с разработкой теоретических основ и практической реализацией устройств и систем, предназначенных для распознавания объектов, явлений и процессов. Оно получило название «распознавание образов». Название возникло в связи с тем, что процесс распознавания отождествлялся с выяснением вопроса об отнесении распознаваемого объекта к определенному классу объектов (образу), олицетворяющему совокупность (подмножество) объектов, обладающих близкими свойствами.
Таким образом, распознавание представляет собой задачу преобразования входной информации, в качестве которой уместно рассматривать некоторые параметры, признаки распознаваемых образов, в выходную, представляющую собой заключение о том, к какому классу относится распознаваемый образ.
Формально задача распознавания образов может быть представлена в следующей форме.
Пусть х — описание объекта, т. е. совокупность доступной информации об объекте, набор признаков, описывающих объект (в дальнейшем для простоты будем отождествлять объект и его описание), а Г={У1,., 1Ут} -конечное множество классов, на которые разбито все множество объектов.
Требуется классифицировать объект с описанием х, т. е. отнести объект к одному из взаимоисключающих классов множества Г на основе анализа его описания.
К середине 1970;х годов распознавание образов как самостоятельное научное направление достигло такой стадии развития, что возникла возможность создания математической теории распознавания. Одной из предпосылок явилось выделение и отработка ряда моделей распознавания.
Ключевым моментом при решении задачи распознавания явилось определение признаков, характеризующих объект или явление. Признаки объектов могут быть подразделены на детерминированные, вероятностные, логические и структурные [4].
Детерминированные признаки — признаки, принимающие конкретные числовые значения (например, размах крыла самолета 1=25 м, масса самолета в=70 тит. д.), которые могут рассматриваться в качестве координат точки в признаковом пространстве, соответствующей данному объекту. При рассмотрении признаков в качестве детерминированных ошибками измерений пренебрегают.
Вероятностные признаки — признаки, случайные значения которых распределены по всем классам объектов, при этом решение о принадлежности распознаваемого объекта к тому или другому классу может приниматься только на основании конкретных значений признаков данного объекта, определенных в результате проведения соответствующих опытов. Признаки распознаваемых объектов следует рассматривать как вероятностные и в случае, если измерение их числовых значений производится с такими ошибками, что по результатам измерений невозможно с полной определенностью сказать, какое числовое значение приняла данная величина.
Логические признаки распознаваемых объектов можно рассматривать как элементарные высказывания, принимающие два значения истинности (<да>, <нет> или <истина>, <ложь>) с полной определенностью. К логическим признакам относятся прежде всего признаки, не имеющие количественного выражения. Эти признаки представляют собой суждения качественного характера типа наличия или отсутствия некоторых свойств или некоторых элементов у распознаваемых объектов или явлений. В качестве логических признаков можно рассматривать, например, такие симптомы, используемые при медицинской диагностике, как боль в горле, кашель, насморк и т. д., такие свойства объектов геологической разведки, как растворимость или нерастворимость в определенных кислотах или в некоторых смесях кислот, наличие или отсутствие запаха, цвета и т. д. К логическим можно отнести также признаки, у которых важна не величина признака у распознаваемого объекта, а лишь факт попадания или непопадания ее в заданный интервал. На практике логические признаки подобного рода используются в таких ситуациях, когда-либо ошибками измерений можно пренебречь, либо интервалы значений признаков выбраны таким образом, что ошибки измерений практически не оказывают влияния на достоверность принимаемых решений относительно попадания измеряемой величины в заданный интервал. Например, в области технической диагностики решение о выходе из строя технических устройств принимается лишь тогда, когда фактические значения некоторых параметров (признаков) превышают заданные пределы. Отклонение же значений параметров от номинала, не сопровождающееся выходом за пределы соответствующих интервалов, является информацией о том, что устройство функционирует нормально.
Структурные (лингвистические, синтаксические) признаки представляют собой непроизводные элементы (символы) структуры объекта. Иначе эти элементы (константы) называют терминалами. Каждый объект может рассматриваться как цепочка терминалов или как предложение. Эти предложения и описывают объекты. При этом, если предложение, описывающее неизвестный распознаваемый объект, относится к языку данного класса, то этот объект и принимается принадлежащим к этому классу. Например, при распознавании букв русского алфавита терминалами являются вертикальная, горизонтальная, наклонная черточка, наличие угла и т. д.
Как правило, модели распознавания образов ориентированы и используют только один вид признаков и игнорируют то, что в описании могут быть признаки разных видов. В зависимости от того, на языке каких признаков производится описание объектов, выделяются следующие модели алгоритмов распознавания.
Детерминистские модели используют «геометрическую» меру близости, основанную на измерении расстояний между распознаваемым объектом и эталонами классов. В общем случае применение детерминистских методов распознавания предусматривает наличие координат эталонов классов в признаковом пространстве либо координат объектов, принадлежащих соответствующим классам. Детерминистские модели можно разделить на следующие два вида.
Модели, основанные на использовании принципа разделения (Я-модели), различаются главным образом заданием класса поверхностей, среди которых выбирается поверхность (или набор поверхностей), в некотором смысле наилучшим образом разделяющая элементы разных классов [7, 12].
Модели, построенные на основе так называемого «метода потенциальных функций» (П-модели), базируются на заимствованной из физики идее потенциала, определенного для любой точки пространства и зависящего от расположения источника потенциала. В качестве функции принадлежности объекта классу используется потенциальная функциявсюду положительная и монотонно убывающая функция расстояния [1].
Вероятностно-статистические модели основаны на использовании аппарата теории вероятностей и математической статистики и применяются в основном в тех случаях, когда известны или могут быть определены вероятностные характеристики классов, например, соответствующие функции распределения [2, 3, 12].
Логические модели основаны на использовании логики высказываний, в частности, на аппарате алгебры логики (Л-модели). В них классы и признаки объектов рассматриваются как логические переменные, а описание классов на языке признаков представляется в форме булевых соотношений [3, 11].
Структурные модели используются при лингвистическом подходе к распознаванию образов, когда описание объекта рассматривается как цепочка терминальных символов, образующих предложение. Каждому классу соответствует грамматика. Язык, порождаемый грамматикой, состоит из описаний объектов заданного класса. Задача классификации в этом случае сводится к определению принадлежности объекта с заданным описанием одному из языков, порождаемых грамматиками [14].
Использование той или иной группы моделей определяется некоторой априорной информацией, с помощью которой делается вывод о состоятельности тех допущений, которые принимаются при построении модели.
Большинство реальных задач распознавания образов в той или иной степени удовлетворяют допущениям сразу нескольких моделей, и описание объекта может быть получено в виде набора признаков различного вида.
Несколько более общий подход реализован в моделях вычисления оценок (голосования) (Г-модели), которые основаны на принципе частичной прецедентное&trade-. Анализируется «близость» между частями описаний ранее классифицированных объектов и объекта, который надо распознать. Наличие близости служит частичным прецедентом и оценивается по заданному правилу посредством числовой оценкив качестве такого правила может служить и любое правило для классификации, построенное на основе одной из ранее названных моделей. По набору оценок близости вырабатывается общая оценка распознаваемого объекта для класса, которая и является значением функции принадлежности объекта классу [3,5,8,9]. Таким образом, эти модели являются в некотором виде голосованием различных алгоритмов по поводу принадлежности объекта к классу. Наиболее простым примером моделей данного типа является перцептрон [31].
В данной работе используется вероятностно-статистический подход к распознаванию образов, который является, пожалуй, одним из наиболее хорошо изученных и наиболее популярных для решения прикладных задач. Причины этой популярности кроются в том, что.
• практически любое достаточно сложное явление или процесс в природе содержит в себе некий элемент случайности и, следовательно, вероятностное описание бывает вполне уместно;
• для алгоритмов, построенных в рамках вероятностно-статистического подхода, теоретические оценки качества классификации получить легче, в частности и по критерию вероятности ошибки классификации.
До настоящего момента в литературе вопрос о классификации объектов, описываемых вероятностными признаками, в случае, когда информация о вероятностных характеристиках для части классов может быть получена, а для другой части классов недоступна, не затрагивался. Однако традиционные статистические методы принятия решений требуют в обязательном порядке знания вероятностных законов распределения объектов внутри всех классов или их оценок и применение традиционных вероятностно-статистических алгоритмов в этом случае невозможно. На практике в этом случае используются методы, основанные на детерминистских моделях, не учитывающие вероятностный характер признаков описывающих объект и игнорирующие имеющуюся информацию о вероятностных характеристиках для части классов.
Особый интерес в связи с этим возникает к правилу ближайшего соседа, для которого удалось построить вероятностно-статистическую модель для оценки асимптотической вероятности ошибки классификации при неограниченном объеме обучающей выборки [6,15,16]. Хотя правило ближайшего соседа не предусматривает использования знаний о законах распределения (или виде этих законов распределения) для части классов, тем не менее, созданная вероятностно-статистическая модель может служить предпосылкой для использования этой информации. При этом встает проблема поиска возможных путей применения знаний о законах распределения для части классов в правиле ближайшего соседа.
В данной работе предлагаются подходы к использованию имеющихся знаний о законах распределения (или виде этих законов распределения) для части классов в правиле ближайшего соседа. На основе предложенных подходов формируются схемы решающих правил, которые определяют класс алгоритмов, среди которых затем выбирается наилучший.
Так как к настоящему времени разработано большое количество алгоритмов классификации в различных группах моделей, то встает вопрос о выборе наилучшего алгоритма. Поэтому при выборе алгоритма важно оценить его эффективность. Па практике применяются несколько критериев оценки эффективности алгоритма классификации. Одним из наиболее важных критериев эффективности алгоритма классификации является вероятность ошибки классификации.
В данной работе за критерий качества классификации примем вероятность ошибки классификации при применении алгоритма.
Для удобства восприятия при изложении материала будем считать, что случайный вектор X — система дискретных случайных величин. Однако, все выводы, сделанные в данной работе, легко могут быть обобщены на случаи, когда X — система непрерывных случайных величин, или когда X содержит одновременно как дискретные, так и непрерывные случайные величины.
Вначале рассмотрим вероятностно-статистические модели, некоторые элементы которых будут использованы при построении новых правил для классификации. Необходимо отметить следующие моменты.
Байесовское решающее правило обеспечивает минимум вероятности ошибки классификации, однако для его применения необходима полная информация о вероятностных характеристиках классов, и для решения поставленной задачи оно непригодно.
Правило ближайшего соседа применимо для решения рассматриваемой задачи, но при его использовании информация об известных вероятностных характеристиках классов игнорируется. Кроме того, для правила ближайшего соседа найдена асимптотическая вероятность ошибки классификации при неограниченном объеме обучающей выборки.
В качестве подходов к решению проблемы классификации при доступности информации о вероятностных характеристиках только для части классов предлагаются модификации правила ближайшего соседа с целью использования знаний об известных законах распределения (или виде этих законов распределения) для части классов. В качестве модификаций правила ближайшего соседа, использующих информацию об известных вероятностных характеристиках классов, предлагаются и анализируются три схемы классификации. Для них найдены асимптотические оценки вероятности ошибки классификации и показано, что они более эффективны, чем правило ближайшего соседа. Предлагаемые схемы классификации также сравниваются между собой.
В конце работы приведены примеры практических задач, сводимых к классификации при неполной информации о вероятностных характеристиках классов. -" «Д.
Таким образом, целью работы является разработка, теоретическая оценка эффективности и сравнительный анализ методов классификации при доступности информации о вероятностных характеристиках лишь для части классов на основе вероятностно-статистического подхода к распознаванию образов.
На защиту выносятся следующие основные результаты, полученные в диссертации:
1. Два подхода к решению задачи классификации при неполной информации о вероятностных характеристиках классов, основанные на использовании имеющейся информации о вероятностных характеристиках для части классов до и после классификации по правилу ближайшего соседа.
2. Три схемы классификации с использованием предложенных подходов.
3. Асимптотические оценки вероятностей ошибочной классификации по каждой из трех схем в случае неограниченного объема обучающей выборки.
4. Алгоритм выбора подмножества классов, минимизирующий асимптотическую оценку вероятности ошибочной классификации в рамках схемы 2.
Основные материалы диссертации опубликованы в работах автора [33 — 37,40] и в соавторстве [38−39]. В работе [38] диссертантом написаны заключение, подразделы. 2.2, 3.1 и приложение. В работе [39] постановка задачи и определение общих подходов к ее решению и к получению асимптотических оценок вероятности ошибки классификации выполнена совместно с научным руководителем Ю. В. Ореховым, диссертанту принадлежат разработанные схемы классификации, асимптотические оценки вероятности ошибки классификации при применении разработанных схем классификации, алгоритмы формования подмножеств в рамках схемы 2, доказательство их оптимальности, сравнительный анализ разработанных схем классификации и правила ближайшего соседа с точки зрения эффективности классификации и требуемых вычислительных ресурсов.
Основные результаты диссертации докладывались на.
• 2-ой Всероссийской с участием стран СНГ конференции «Распознавание образов и анализ изображений: новые информационные технологии» (1995, г. Ульяновск),.
• конференции «Проблемы экологического мониторинга» (1995, г. Уфа),.
• Всероссийской конференции «Повышение эффективности средств обработки информации на базе математического и машинного моделирования» (Тамбов, 1995),.
• Всероссийской молодежной научно-технической конференции «Информационные и кибернетические системы управления и их элементы» (1995, г. Уфа),.
• общегородском семинаре по математическому моделированию (1996, г. Уфа),.
• семинарах «Модели искусственного интеллекта» кафедры ВМиК УГАТУ (1994;1996, г. Уфа).
Результаты исследований применялись при выполнении научно-исследовательской работы «Разработка и внедрение математических, программных и аппаратных средств дистанционного мониторинга» (№ гос. регистрации 01.9.60 003 774) и включены в спецкурс УГАТУ «Распознавание образов» .
Основные результаты диссертации можно сформулировать следующим образом.
1. Предложено два подхода к решению задачи классификации при неполной информации о вероятностных характеристиках классов, основанных на использовании имеющейся информации о вероятностных характеристиках для части классов до и после классификации по правилу ближайшего соседа.
2. На основе предложенных подходов сформулированы три общие схемы классификации. Первая схема классификации реализует подход, основанный на использовании имеющейся информации о вероятностных характеристиках для части классов после классификации по правилу ближайшего соседа. Вторая схема классификации реализует подход, основанные на использовании имеющейся информации о вероятностных характеристиках для части классов до классификации по правилу ближайшего соседа. В рамках третьей схемы сделана попытка объединить оба данных подхода.
3. Для всех трех схем получены асимптотические оценки вероятностей ошибочной классификации в случае неограниченного объема обучающей выборки.
4. Для всех трех схем классификации показано, что их использование более эффективно в смысле минимизации вероятности ошибки классификации, чем использование правила ближайшего соседа.
5. Предлагаемые схемы классификации и правило ближайшего соседа сравнены с точки зрения требуемых вычислительных затрат.
6. Предложен алгоритм А0рт выбора подмножества классов О в рамках схемы классификации 2. Доказано, что алгоритм А0рт минимизирует асимптотическую оценку вероятности ошибочной классификации в рамках схем 2.
7. В связи с невозможностью практического применения алгоритма А0рт, в силу неизвестности вероятностных характеристик для всех классов, предложен алгоритм, использующий вместо неравенств (1) и (2) достаточные условия для этих неравенств.
8. Найдено достаточное условие для того, чтобы классификация по схеме 1 обладала не большей вероятностью ошибки, чем классификация по схеме 2 и показано, что достаточное условие имеющее практическую ценность для того, чтобы классификация по схеме 2 обладала не большей вероятностью ошибки, чем классификация по схеме 1, не может быть найдено.
9. Показано, что при одинаковом формировании группы О классификация по схеме 3 обладает меньшей вероятностью ошибки, чем классификация по схеме 2.
10. Отмечено, что классификация по схеме 1 является частным случаем классификации по схеме 3, когда П=Г1.
11. Приведены примеры практических задач решение которых возможно сведением к задаче классификации при неполной информации о вероятностных характеристиках классов.
Полученные в диссертации результаты могут быть полезными для решения задач классификации в случае доступности информации о вероятностных характеристиках для части классов.
Кроме того, предложенные в диссертации схемы классификации могут служить удобным «мостом» при постепенном исследовании проблемы и переходе от классификации по правилу ближайшего соседа (в случае доступности практического минимума информации о классахобучающей выборки) к классификации по байесовскому решающему правилу (в случае доступности максимума информации о классах — полной информации о вероятностных характеристиках для всех классов). Таким образом, перспективность использования предложенных схем классификации определяется также и тем, что оно обладает свойством использовать всю имеющуюся на момент принятия решения информацию, что позволяет использовать его в развивающихся системах искусственного интеллекта.
Несомненно, что предложенные в диссертации подходы будут служить предметом дальнейших исследований в данной области. Особенно актуальна задача формирования группы О в схеме классификации 3.
Результаты исследований применялись при выполнении научно-исследовательской работы «Разработка и внедрение математических, программных и аппаратных средств дистанционного мониторинга» (№ гос. регистрации 01.9.60 003 774) и включены в спецкурс УГАТУ «Распознавания образов» .
Заключение
.
