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

2
СОДЕРЖАНИЕ
Введение.................................................................5
Глава I. Распознавание образов в пространстве признаков. Задачи и проблемы................................................................18
1.1. Задачи распознавания...............................................18
1.2. Проблемы распознавания.............................................25
Глава II. Постановка задачи.............................................32
2.1.Содержательная постановка задачи распознавания
микробиологических объектов........................................... 32
2.2. Формальная постановка задачи.......................................40
2.2.1 .Множество объектов предметной области и множество эталонных объектов................................................................40
2.2.2. Параметры множества эталонных объектов...........................43
2.2.3. Виды описаний множества эталонных объектов.......................44
2.2.4. Задачи распознавания.............................................52
2.2.5. Особенности решения задач........................................53
Глава III. Бинарные отношения на множестве эталонных
объектов................................................................55
3.1. Структура, характеристики н виды описаний отношений на
множестве эталонных объектов М..........................................57
3.1.1. Подмножества множества 1.........................................58
3.1.2. Характеристики множества !.......................................64
3.1.3. Характеристики множества Г.......................................79
3.1.4. Виды описаний отношений на множестве М...........................87
3.2. Некоторые свойства матриц различий и их столбцовых покрытий........91
Глава IV. Методы формирования тестов с минимальными затратами ресурсов и времени.....................................................100
4.1. Методы формирования минимальных тестов на основе первичного описания множества эталонных объектов..................................110
4.2. Методы формирования минимальных тестов на основе
3
количественной или частотной идентификационной матрицы..................127
4.3. Методы формирования тестов с минимальными затратами ресурсов и времени при измерении значений признаков с различными затратами для различных признаков..............................................134
4.4. Метод формирования тестов с заданными признака!ии..................141
Глава У.Методы формирования семейства рабочих словарей признаков..143
5.1. Методы формирования рабочих словарей признаков.....................147
5.2. Некоторые особенности распознавания объектов автоматными
методами...............................................................161
Заключение.............................................................167
Приложении.............................................................170
Приложение 1. Частотная матрица для идентификации бацилл................171
Приложение 2. Биохимическая характеристика энтеробактерий...............173
Приложение 3. Примеры формирования минимальных тестов
в соответствии с методом 4.1.1..........................................174
Приложение 4. Примеры формирования минимальных тестов
в соответствии с методом 4.1.2.........................................185
Приложение 5. Примеры формирования минимальных тестов
в соответствии с методом 4.1.3.........................................1 88
Приложение 6. Примеры формирования минимальных тестов
в соответствии с методом 4.1.4..........................................193
Приложение 7. Примеры формирования минимальных тестов
в соответствии с методом 4.1.5..........................................201
\
Приложение 8. Пример формирования теста в соответствии с методом 4.2.1 на основе частотной идентификационной матрицы, представленной в
таблице 2.2.3.5 (глава II)..............................................209
Приложение 9. Пример формирования теста в соответствии с методом 4.2.2 на основе частотной идентификационной матрицы, представленной в таблице 2.2.3.5 (глава II)...............................................217
4
Приложение 10. Примеры формирования теста с минимальными затратами ресурсов при измерении значений признаков в соответствии с
методом 4.3.1.............................................................220
Приложение 11 Пример формирования теста с минимальными затратами времени при измерении значений признаков в соответствии с
методом 4.3.2.............................................................229
Приложение 12. Задачи распознавания в микробиологии.......................233
Список литерату ры........................................................251
*
5
ВВЕДЕНИЕ
Актуал ьность темы. В настоящее время успешно развивается теория распознавания образов. Расширяются области ее применения. Получены полезные результаты не только в предметных областях, где задачи распознавания ранее решались, в значительной степени, интуитивно, но и там, где давно и успешно используются формализованные методы. Задачи распознавания предметов, явлений, процессов - одни из наиболее важных, часто решаемых задач человека в его научной, производственной деятельности.
Теория и практика распознавания особенно успешно развивались в последние 40-50 лет. В теоретических работах исследовались, в том числе, методы распознавания, применяемые человеком. На основе результатов этих исследований разрабатывались математические модели, имитирующие процессы распознавайия человеком.
В теоретических прикладных работах основные усилия направлялись на разработку общих и частных моделей для построения и совершенствования решающих правил - методов отнесения распознаваемых объектов к классам заданной или создаваемой классификации. Значительно меньше усилий прилагалось к решению других задач, которые также относятся к задачам распознавания: в частности, формированию множеств признаков,
обеспечивающих минимальные затраты ресурсов и времени при приемлемой точности распознавания.
Это объясняется тем, что основные работы по построению общих моделей распознавания и решающих правил проводились, в первую очередь, в предметных областях, где опыт распознавания сравнительно невелик в связи с редкими актами распознавания, а эффект (в первую очередь, экономический) от получения новых усовершенствованных правил распознавания, достаточно велик, в первую очередь, за счет более точного распознавания. Этот эффект не только покрывает затраты на научно-исследовательские и опытно-конструкторские работы, но и
6
приносит прибыль. К таким предметным областям относятся, в первую очередь, геология (в частности поиск и исследование рудных месторождений). Теоретические и прикладные работы в предметных областях, где накоплен многовековой опыт распознавания (однако, велики финансовые ограничения): в микробиологии, медицине, ветеринарии - велись в меньших объемах и с меньшим успехом. В этих предметных областях традиционно велика интенсивность работ по распознаванию (идентификации, диагностике, прогнозированию). Возможны резкие колебания интенсивности потока требований на распознавание, в частности, увеличение интенсивности этого потока в экстремальных ситуациях (например, в медицине, микробиологии - при эпидемиях, военных конфликтах). Насколько доля работ по распознаванию среди всех работ в предметной области велика в медицине, можно судить по характеру и структуре курса обучения в медицинских ВУЗах в сравнении с курсами обучения, например, в машиностроительных ВУЗах. Так, в медицинском ВУЗе из двух основных задач врача: диагностирование заболевания и назначение лечения, большая часть времени в курсе обучения (теоретического и, особенно, практического) занимает задача обучения диагностированию заболеваний. В машиностроительном ВУЗе диагностированию причин нарушения технологии производства и сбоев производственного процесса уделяется, в лучшем случае, очень мало внимания: считается, что редко встречающиеся в работе инженера задачи анализа причин нарушения технологических процессов или процессов организационного управления можно изучить и усвоить в процессе выполнения работ. Одной из причин меньшего успеха в разработке и внедрении методов распознавания в вышеуказанных грех предметных областях, в частности в медицине, является то, что усилия направлялись, в первую очередь, на разработку проблем построения решающих правил в этих предметных областях, а не на другие, более актуальные, проблемы [17,57].
Представляется, что недостаточные успехи прикладных исследований в вышеуказанных предметных областях (медицина, микробиология, ветеринария)
7
связаны, в том числе и с тем, что задачам минимизации затрат ресурсов и времени при распознавании и, особенно, при измерении (оценке) значений признаков, уделяется незаслуженно мало внимания.
Косвенно задача уменьшения затрат ресурсов (и, возможно, времени) решается при уменьшении количества используемых признаков для распознавания [15,27,30.32-34,40,45,48,50,54,59.62,71,73] с целью устранения малоинформативных признаков. При этом затраты ресурсов и времени не учитываются. Задачи уменьшения затрат ресурсов и времени мри уменьшении количества распознающих признаков усложняются, если обучение распознаванию образов (ОРО) выполняется на малых выборках из генеральной совокупности предметной области [14-16,54,57,69,70]. Рекомендуется ориентироваться на специалистов (экспертов) предметной области при формировании множества признаков для описания объектов и для распознавания [14,16,17,33,57]. Повысить точность и надежность распознавания при малом количестве эталонных объектов можно, если использовать методы статистического моделирования с применением датчика псевдослучайных чисел [46]. Непосредственно вопросам определения потерь при распознавании и затрат ресурсов при измерении значений признаков уделено внимание в работах Н.Г.Загоруйко, например, в [33].
В работах А.Г.Горелика [22-24] рассматриваются способы формирования множеств признаков для распознавания («рабочих словарей признаков»), являющихся подмножествами «априорного словаря признаков» - множества признаков, описывающих объекты. Рабочий словарь признаков формируется и используется, если возникают ограничения в финансовых затратах на оборудование, приборы, предназначенные для измерения (оценки) значений признаков при распознавании. Такие задачи решаются при проектировании системы распознавания или при выполнении процесса распознавания после выбора и измерения значения очередного, г-го признака, когда или принимается решение о принадлежности распознаваемого объекта к одному из классов и, соответственно, об окончании процесса распознавания, или о выборе и измерении
8
значения г+1-го признака. К существенным недостаткам предложенного способа следует отнести: I) последовательное выполнение всех работ [67] по измерению значений признаков, что не позволяет существенно уменьшать затраты времени (продолжительность) работ в тех случаях, когда работы можно было бы вести параллельно; 2) анализ решений о результатах распознавания, принимаемых на промежуточных стадиях процесса распознавания, также может создавать неоправданные дополнительные затраты времени, увеличивающие общую продолжительность работ, что неблагоприятно может сказаться на вышеописанных экстремальных ситуациях; 3) большинство решений, которые согласно [20] принимаются при распознавании неизвестного объекта, могут быть подготовлены и приняты с достаточно высоким качеством заранее - на стадии ОРО, а корректировки этих решений при распознавании могут быть достаточно редкими. Количество таких корректировочных решений может быть уменьшено путем увеличения обучающей выборки [14,57) и улучшения решающего правила, например, [15,29,30,45,57].
Обеспечить уменьшение затрат ресурсов и времени можно выбором минимального количества признаков, обеспечивающих минимальные затраты и приемлему ю точность распознавания.
Необходимо при этом учитывать ограничения, возникающие при уменьшении количества используемых признаков для распознавания:
а) уменьшение статистической устойчивости результатов распознавания;
б) зависимость продолжительности работ по измерению значений признаков (зазрат времени) от технологии работ по распознаванию.
Возможностям успешного решения вышеуказанных проблем могут способствовать результаты теоретических и прикладных научных работ в технической диагностике, в первую очередь, с использованием достижений теории автоматов [6,7,18,64,66]. Так, одной из основных областей приложения теории экспериментов с конечными детерминированными автоматами (КДЛ) является распознавание (диагностика) таких свойств функционирующих систем,
9
которые могут быть представлены наблюдаемым поведением конечных автоматов. Средствами теории экспериментов с автоматами могут быть построены оптимальные эксперименты по выбранному критерию оптимальности. В ряде случаев в качестве предмета для оптимизации эксперимента является время. Актуальной задачей минимизации времени эксперимента по распознаванию свойств объектов является задача идентификации болезнетворных микроорганизмов в медицине и ветеринарии в связи с зависимостью эффективности лечения от сроков принятия решения. Задача идентификации в автоматной интерпретации определяется как перевод автомата из начального состояния, соответствующего принадлежности идентифицируемого объекта множеству всех классов в состояния, соответствующее только одному классу.
Методы, основанные на распознавании объектов, описанных как последовательности значений признаков, сформировались па протяжении последних 20-30 лет и сформулированы в ряде работ [14,21,23,25,26,2729,45,69-71]. Наиболее закончено в концептуальном и практическом плане эти методы сформулированы в [21,29]. В этих и подобных им работах, задача распознавания формулируется, в той числе, и как задача определения набора наиболее информативных признаков для описания объектов, выявления связей между этими признаками и информацией о классах объектов и описания методов распознавания.
Разработаны различные способы определения важных для распознавания признаков в различных предметных областях [21,30,31,41,48,59,62,71]. В этих работах предлагаются различные методы для отбора информативных признаков, в том числе, с помощью так называемых тупиковых тестов (неизбыточных ключевых наборов признаков). В ряде перечисленных работ, посвященных тестам, в частности [59,62,71], рассматриваются алгоритмы получения всего множества ‘‘тупиковых тестов”.
В данной работе на основе проведенных исследований и экспериментального моделирования на ЭВМ разработаны методы формирования
10
множеств распознающих признаков, в значительной степени, лишенные указанных недостатков.
В работе описаны способы формирования множеств признаков, обеспечивающих минимальные затраты ресурсов и времени при измерении значений признаков распознаваемых объектов.
Поскольку в процессе выполнения работы выяснилось, что поставленная задача, имеет важное значение не только для вышеупомянутых предметных областей, но и для других предметных областей, например, криминалистики, то работа проведена таким образом, чтобы ее результаты были применимы везде, где возникают задачи подобного рода.
Цель работы Целыо данной работы является разработка методов формирования семейства рабочих словарей признаков, обеспечивающих оптимальное соотношение между затратами ресурсов и/или времени при измерении значений признаков и точностью распознавания при различных ограничениях на затраты и точность распознавания в различных производственных ситуациях.
Для достижения указанной цели поставлены и решены следующие Задачи работы.
]. Разработка методов формирования минимальных тестов на выборке
эталонных объектов, описанных кортежами значений признаков.
2. Разработка методов формирования минимальных тестов на выборке эталонных объектов, описанных частотами или относительными частотами появления объектов с заданным значением заданного признака в заданном классе - для всех значений, всех признаков, всех классов разбиения множества эталонных объектов.
3. Разработка методов формирования тестов с минимальными затратами ресурсов и/или времени на выборке эталонных объектов, описанных или кортежами значений признаков, или частотами, или относительными
II
частотами появления объектов с заданными различными значениями признаков в разных классах.
4. Разработка методов формирования представительной (репрезентативной) выборки абстрактных эталонных объектов для формирования тестов по пунктам 1,2,3.
5. Разработка методов формирования семейства рабочих словарей признаков, обеспечивающих суболтимальное соотношение между затратами ресурсов и/или времени и точностью распознавания.
Методологическая и теоретическая основа исследования.
Методологическую и теоретическую основу проведенного исследования и разработанных методов составили научные труды отечественных и зарубежных авторов в области распознавания образов, теории абстрактных автоматов, дискретной математики, математической статистики, алгебраической топологии, исследования операций.
Выполненные исследования и разработки опираются, в первую очередь, на груды специалистов в списке литературы в диссертации, а также на труды этих и других специалистов, которые не вошли в список литературы. Среди специалистов, работы которых оказали решающее влияние на формирование взглядов автора и выполнение данного диссертационного исследования, необходимо упомянуть, в первую очередь, таких ученых (представленных в алфавитном порядке), как А.М.Богомолов [4-8], В.Н.Вапник [14], В.И.Васильев [15], И.М.Гельфанд [17], А.Гилл [18], А.Л.Горелик [20-22], У.Гренандер [23],
A.Н.Дмитриев [25-27], Ю.И.Журавяев [25,27,29-31], Г.А.Заварзин [32],
Н.Г.Загоруйко [33], А.Д.Закревский [34], Дж.Келли [36], А.Н.Колмогоров [38], Р.М.Константинов [40,41], В.Б.Кудрявцев [41], Г.С.Лбов [46], В.В.Розен [57],
B.Н.Салий [4], Г.Л.Слупкая [59], Е.С.Смирнов [60], Н.А.Соловьев [62], Д.В.Сперанский [5], А.А.Сытник [6.63-65], В.А.Твердохлебов [7,66], Я.З.Цыпкин [69-70], С.В.Яблонский [71], Ю.А.Шрейдер 172,73].
12
Научная новизна
1. Разработаны новые методы формирования минимальных тестов на
множествах объектов, описанных как кортежи значений Узнанных (к>2) признаков с использованием или без использования матрицы различий.
2. Разработаны новые методы формирования минимальных тестов на
множествах объектов, описанных в таблицах с частотами или относительными частотами появления объектов с различными значениями А-значных
признаков.
3. Разработаны методы формирования тестов с минимальными затратами ресурсов и/или времени.
4. Предложены: способ оценки представительности выборки эталонных
объектов для теста и метод создания представительной выборки абстрактных эталонных объектов, описанных кортежами значений признаков.
5. Разработаны методы формирования подмножеств тестов, обеспечивающих субоптимальное соотношение между затратами ресурсов и/или времени и точностью распознавания для различных конкретных ситуаций распознавания.
Теоретическая и практическая значимость работы заключается в том, что разработаны методы, позволяющие повысить эффективность и качество решения задач распознавания в предметных областях (например, таких, как микробиология, медицина, ветеринария), где существенны ограничения ресурсов и времени.
Структура и объем работы. Работа состоит из 5 глав, введения, заключения, приложений, списка литературы и содержит 260 страниц маш инописного текста.
Глава 1 посвящена задачам распознавания в пространстве признаков по литературным источникам. Здесь также раскрываются проблемы
13
распознавания, решаемые в работе. Показано, что в таких предметных областях как микробиология, медицина, ветеринария, криминалистика, одна из наиболее значимых проблем распознавания - это проблема создания условий, обеспечивающих минимальные затраты ресурсов и/или времени и при приемлемой точности распознавания в конкретных ситуациях распознавания на практике. При этом следует учесть, что множество признаков распознавания, подготовленное для некоторой заданной ситуации, может оказаться мало пригодным для другой ситуации, в связи с различными ограничениями на затраты ресурсов и времени. Для успешного решения задач распознавания при различных ограничениях необходимо иметь, по возможности, необходимое и достаточное количество вариантов множеств признаков с различными ограничениями. Показано, что наилучших результатов можно добиться, если произвести отбор оптимальных множеств признаков при полном их переборе. Однако, полный перебор неприемлем, так как количество подмножеств признаков, из которых должен быть произведен
выбор, очень велико и равно 2п — 2, где п - число признаков априорного множества (словаря) признаков, пт1П - минимальное количество признаков в рабочем подмножестве (словаре) признаков, при котором обеспечивается минимально допустимая точность распознавания.
Рассмотрен вариант решения проблемы с применением теории экспериментов с автоматами по А.Гиллу, показаны особенности решения задачи построения решающего правила на языке теории автоматов для распознавания неизвестных экспериментальных объектов.
Во // главе дана постановка задачи распознавания, рассмотренной в работе. Представлена содержательная постановка задачи; формальная постановка задачи. В содержательной постановке изложены особенности микробиологии с точки зрения задач распознавания. Рассмотрены особенности микроорганизмов и их описаний. Описаны трудности, возникающие при распознавании
14
микроорганизмов, в отличие от других объектов материального мира. Отмечено, что эти трудности связаны с весьма малыми размерами этих объектов, их вариабельностью, необходимостью применения специальных сред выращивания микроорганизмов, необходимостью использования достаточно большого количества признаков для распознавания, трудностью их однозначного упорядочения по степени важности. Сообщены особенности “Определителей бактерий”, предназначенных для идентификации (распознанная) микроорганизмов - на примере “Определителя Берджи” [43,561 В формальной постановке задачи сообщены особенности множества объектов предметной области и его подмножества известных объектов (объектов, принадлежность которых к классам известна), названных, как в ряде других работ по распознаванию, “эталонными”; особенности словарей признаков, а также параметров множеств эталонных объектов, используемых при решении задач распознавания, рассматриваемых в работе. Описаны формально задачи распознавания для решения сформулированных проблем. Даны определения множеств эталонных объектов и четырех видов их описаний: а) “первичного” описания - описания объектов в виде кортежей значений признаков и классов, к которым принадлежат объекты; б) производных описаний: количественной, частотной идентификационной матрицы и матрицы “дифференциальных описаний”. В матрице дифференциальных описаний частоты появления эталонных объектов разделены на некоторое количество градаций частот. Матрицы дифференциальных описаний используются в “Определителях бактерий”, например, [43,56,68], частотные идентификационные матрицы - для описания коллекций микроорганизмов в микробиологии, статистических данных о заболеваниях в медицине и ветеринарии [3]. Дано формализованное описание основных решаемых задач.
В 111 главе даны математические основы для формирования разработанных методов.
15
В разделе 3.1 описано отношение между подмножеств множества М 1-го вида и отношение подмножеств множества М 2-го вида, их подмножества, параметры, виды представления. Даны определения соотвествующих понятий и необходимые утверждения. Понятия отношений 1-го и 2-го видов есть расширенные понятия матрицы различий.
В разделе 3.2 главы III изложены некоторые свойства матрицы различий и их столбцовых покрытий, так как тесты, как известно, могут рассматриваться как покрытия матриц различия. Даны определения и утверждения с учетом которых сформированы методы и алгоритмы формирования минимальных тестов и тупиковых тестов.
В главе IV представлены 11 методов формирования тестов с минимальными затратами ресурсов и времени, в том числе, 7 методов формирования тестов с равными затратами ресурсов и времени при измерении значений признаков и при последовательно выполняемых работах, 3 метода формирования тестов с различающимися затратами ресурсов и/или времени при любом порядке выполнения работ при измерении значений признаков и метод формирования тестов, если некоторые признаки теста заданы пользователем (например, экспертом). Первые семь методов - это новые методы формирования минимальных тестов или усовершенствованные известные: а) на основе матриц различий, созданных на множествах первичных описаний эталонных объектов или непосредственно на основе самих первичных описаний множеств эталонных объектов без использования матриц различий; б) на основе матриц различий, созданных с использованием количественных и частотных идентификационных матриц и матриц дифференциальных описаний. Три метода формирования тестов с различающимися затратами ресурсов основаны на использовании первых 7 методов с коррективами. Таким образом, используя первые 7 методов или 3 метода с каждым из 7 первых методов можно реализовать 28 методов, различающихся качеством результатов и комбинацией офаничений.
16
В V главе описаны: 1) способы проверки представительности множества эталонных объектов и его увеличения за счет абстрактных объектов; 2) 2-ой этап формирования множеств распознающих признаков, на котором составляются подмножества тестов, созданных на 1-ом этапе путем их “усечения” - по правилам, позволяющим уменьшить объем перебора. Для каждого подмножества теста определяются затраты ресурсов и времени и точность распознавания как доля точности распознавания с помощью исходного априорного словаря признаков. Списки тестов и их подмножеств упорядочиваются: по затратам ресурсов, затратам времени, точности распознавания, после чего они могут быть использованы для распознавания на практике в конкретных ситуациях.
В Заключении приводятся основные результаты, полученные в диссертационной работе.
Список литературы представлен 90 литературными источниками.
В приложении даны примеры реализации методов формирования тестов и некоторые вспомогательные материалы.
Публикации и апробация работы. Результаты работы докладывались: на конференции в Саратовском филиале НИИ генетики и селекции промышленных микроорганизмов РАН по проблемам систематики микроорганизмов (Саратов, 1995г.), на XI международной конференции «Проблемы теоретической кибернетики» (Ульяновск, 1996 г.), на международной конференции
«Компьютерные науки и информационные технологии», посвященной памяти проф. А.М.Богомолова (Саратов, 2002 г.) и на научных семинарах Саратовского государственного университета 1999-2002 гг.
Автор выражает глубокую признательность научному руководителю
17
работы - действительному члену РАЕН, доктору технических наук, профессору Александру Александровичу Сытнику, а также действительному члену РАЕН, доктору технических наук, профессору Владимиру Александровичу 1 вердохлсбову за постоянное внимание и поддержку в работе.
18
Глава I. РАСПОЗНАВАНИЕ ОБРАЗОВ В ПРОСТРАНСТВЕ ПРИЗНАКОВ. ЗАДАЧИ И ПРОБЛЕМЫ
В этой главе даны сведения из литературных источников по вопросам, связанным с распознаванием (идентификацией, диагностированием, прогнозированием), а также проблемами распознавания. Дано описание проблемы, решаемой в диссертации.
1.1. ЗАДАЧИ РАСПОЗНАВАНИЯ
Распознавание образов (РО) - есть определение принадлежности объекта к одному из классов (если классы не пересекаются) или к нескольким классам (если классы пересекаются).
К задачам распознавания относят задачи идентификации, диагностирования, прогнозирования - при заданной классификации (классификационной схеме), а также задачи формирования (уточнения) классификации (таксономии). К сожа-лению, до сих пор существует много различных определений понятия диагностирования [34,42,44,54].
По нашему мнению, под диагностированием (как разновидностью распознавания) объектов, с точки зрения автора, в отличие от [34], понимается процесс распознавания объектов, относимых к одному из двух классов (двух множеств классов): к классу (множеству классов) объектов, принятых в качестве эталонных и классу (множеству классов) объектов, отличающихся от эталонных и, затем, определения подкласса объектов, обладающих свойствами, отличающимися от свойств эталонных объектов. Так, например, в медицине диагностирование - эго исследование, предназначенное для определения пациента как здорового или больного, а затем, если исследуемый пациент - болен, определение его заболевания. В технике - диагностирование: а) при эксплуатации технических устройств -определение исправности технического устройства или узла (узлов); если диагностируемое устройство (иди его узел) неисправно - определение вида неисправности (неисправностей) устройства (узла); 6) при производстве технических устройств (узлов, деталей) - выявление годных (бездефектных) и негодных (брако-
19
ванных) продуктов производства (готовых устройств, узлов, деталей) и, затем, определение вида брака и его причин. Первую задачу диагностирования - отнесения диагностируемою объекта к одному из двух классов (множеств классов) -эталонных объектов и объектов, отличающихся от эталонных - часто называют контрольной задачей. Например, контрольная задача в медицине - задача профилактики заболеваний населения. Вторую задачу - задачу отнесения неэталонного объекта к конкретному классу объектов в зависимости от вида отличий свойств неэталонного объекта от эталонного - называют собственно диагностической задачей. В данной работе диагностирование (в том числе, контрольная задача) специально как вид распознавания не рассматривается. Все, что в данной работе рассматривается как решение задач распознавания в полной мере относится и к диагностированию.
Если необходимо расклассифицировать предъявленные объекты по классам (образам) только на основе их описаний (классификация не известна), то выполняется - задача таксономии (кластерного анализа, обучения без учителя, самообучения).
Под классификацией понимается система, структура которой предусматривает упорядоченное расположение множества каких-либо классифицируемых объектов на основе установленных связей и зависимостей между признаками этих объектов. Наглядное выражение классификационные системы получают в виде классификационных таблиц или схем [28]. В микробиологии, в основном, используются естественные классификации.
Естественная классификация — классификация, построенная на основе объективных признаков и свойств предметов (явлений) и связей между ними [28,37,49,72,73].
Естественные классификации отличаются от искусственных классификаций тем, что они опираются на существенные признаки объектов, и существенность их не связана с какими-либо целями людей. Классификация называется существенной системой, если положение каждого объекта в классификационной схеме
20
позволяет определить его важные (существенные) свойства [72,73]. Задача разбиения многомерных данных на классы связана непосредственно с задачей снижения размерности исследуемых данных [1]. Необходимость снижения размерности описаний вызвана не только необходимостью уменьшения затрат на определение значений признаков, но и:
а) уменьшением “засоренности” излишними признаками, которая возникает, если объем исследуемой совокупности объектов лишь незначительно превосходит размерность признанного пространства [15];
б) естественным и целесообразным стремлением исследователя к возможно большей простоте окончательной математической модели: чем меньшим числом признаков можно обойтись, тем проще объяснить механизм изучаемого явления.
При решении задачи таксономии специалистам в некоторых случаях некоторые объекты приходится относить к определенному таксону, несмотря на го что у них отсутствуют один - два признака, считающихся для объектов таксона обязательными. Различают монотетические и пояитетические группы - группы, имеющие либо одинаковые, либо различные наборы признаков [37]. Монотетиче-скую группу получают путем последовательности логических операций деления множества объектов. При этом образуются классы условной эквивалентности: обладание определенным комплексом признаков - необходимое и достаточное условие принадлежности объекта к группе. Построение монотстических групп в биологии при анализе фонетических данных всегда сопряжено с большими трудностями: организм, отклоняющийся от нормы по одному признаку, входящему в группу, будет исключен из нее. Более того, если этот признак используется для составления 1-го уровня иерархической классификации, то организм может попасть в группу, далекую от той, с которой он в действительности имеет наибольшее сходство. Авторитетные микробиологические определители, такие как [43,56] основаны на монотетичсской классификационной схеме. Политетическис группы определяются на основании большого числа обшцх признаков, ни один из которых не является необходимым или достаточным условием принадлежности к дан-
2)
ной группе, что согласуется с интуитивными представлениями о естественных таксонах. При этом образуются классы толерантности, группы могут пересекаться друг с другом.
Совокупность описаний объектов, для которых известны классы (образы), к которым они принадлежат, образует обучающую последовательность (набор эталонов). Основная задача обучения распознаванию образов (ОРО) заключается в том, чтобы на основе обучающей последовательности определить функцию (решающее правило), с помощью которой можно выполнить распознавание объекта. К такой схеме приводится любая задача принятия решения, если процесс принятия решения основан на изучении ранее накопленного опыта. Прикладные задачи, решаемые методами РО, возникают, в медицинской диагностике, при геологическом прогнозировании, идентификации фотоизображений, оценке экономических и производственных ситуаций. Для решения этих задач накоплено большое число эвристических алгоритмов распознавания.
Наиболее употребительны следующие модели РО: 1) модели, построенные с использованием принципа разделения, задающие класс гиперплоскостей, разделяющих образы; 2) модели, построенные на принципе потенциалов; 3) модели вычисления оценок (голосования); 4) структурные модели; 5) статистические модели.
На уровне модели ставится задача отыскания экстремального по качеству алгоритма распознавания. О качестве работы распознающего алгоритма судят по результатам работы алгоритма па экзаменационном множестве объектов (контрольной последовательности), для которых априори известна достоверная классификация. При построении общей теории распознающих алгоритмов наиболее полные результаты получены в рамках алгебраического подхода [29]. Распознающий алгоритм представляется в виде распознающего оператора и решающего правила. Введение над распознающими операторами операций сложения, умножения, умножения на скаляр позволяет доказать существование в рамках алгебраического расширения исходного набора распознающих операторов распознаю-
22
щего алгоритма, обладающего экстремальным качеством распознавания на любой контрольной последовательности. К задачам ОРО относятся и задачи минимизации описания исходных объектов путем выделения информативных признаков [35,50].
Известны следующие типы задач распознавания [35].
1. Отнесение предъявленного объекта (ситуации) по его формализованному описанию к одному из заданных классов - задача распознавания.
2. Разбиение множества ситуаций (объектов) по их формализованным описаниям на систему неиересекающихся подмножеств (классов) - задача автоматической классификации (таксономия, кластер-анализ, обучение без учителя).
3. Определение информативного набора признаков для построения формальных признаков и их сочетаний - задача выбора информативного набора признаков при распознавании.
4. Построение формализованного описания объекта - задача приведения исходных данных к виду, удобному для распознавания.
5. Задача 1 с учетом динамичности объекта (ситуации).
6. Задача 2 с учетом динамичности объекта (ситуации).
7. Задачи 5,6, в которых решение должно относиться к некоторому моменту времени в будущем, - задача прогнозирования.
Одной из важнейших задач является задача конструирования признакового пространства. В [15,17,33], а также в работах по проблеме обучения распознаванию образов, в которых значительное внимание в процессе обучения обращено на формирование описания объектов, сама проблема рассматривается как некая процедура конструирования пространства, в котором возможно простое разделение образов. Под конструированием пространства в [15] понимается некоторый механизм отбора таких свойств объектов, которые действительно являются признаками, относительно тех образов, которые нужно разделить. Не каждое свойство объектов, согласно [15], есть признак, а значит не всякое свойство должно участвовать в распознавании. Б распознавании должны участвовать только такие свой-
23
ства, которые сами по себе хотя и не разделяют образы, но в совокупности с себе подобными к этому разделению приводят. Существуют несколько способов выбора признаков для признакового пространства. Так, согласно [40,41,48] из набора (множества) известных признаков, отбирают признаки с наименьшим количеством на эталонной (обучающей) последовательности неопределенных значений. Оставшиеся признаки упорядочивают по уменьшению информативности признака, например, с с помощью информационного веса. Из ранжированного списка отбирают для описания обучающей последовательности наиболее информативные признаки. В работах [15,34,59,62] отбор признаков производится по их разделяющим свойствам.
Согласно [20-22], в общем случае, информативность признака зависит от того, какие признаки определены на предыдущих стадиях процесса распознавания и какие при этом они приняли значения. Однако, это не исключает целесообразности при построении системы распознавания определение априорной оценки информативности каждого признака (в предположении, что он определен первым). При этом окончательное решение, связанное с построением рабочего множества признаков системы распознавания, требует учета затрат на разработку (или приобретение) измерительной аппаратуры, предназначенной для определения признаков распознаваемых объектов, учета естественных ограничений на общую величину затрат. В [15] при диагностировании (распознавании) объектов одна из важнейших задач есть задача определения минимального набора наиболее существенных признаков. Минимизация набора диагностических признаков необходима не только с целью уменьшения затрат на проведение диагностических исследований, но и для уменьшения количества ошибок, возникающих вследствие использования для диагностирования мало существенных признаков, а также признаков с неустойчивыми (изменяющимися на объектах за достаточно малый период времени) и неопределенными (неизвестными) значениями признаков.
Известны различные способы выделения информативных для распознавания признаков в различных предметных областях
24
[15,16,25,27,32,38,40,48,50,59,62]. В этих работах предлагаются различные методы для отбора информативных признаков, в том числе с помощью множества так называемых тупиковых тестов. Тупиковый тест это - неизбыточный ключевой набор признаков, являющийся подмножеством заданного на таблице (или множестве таблиц) множества признаков. В ряде работ, посвященных тестам, в частности, [30,40,41,59,62,71] рассматриваются алгоритмы получения всего множества тупиковых тестов. С помощью всего множества тупиковых тестов определяются важнейшие характеристики признаков, определяющие их информативность для распознавания, - "информационные веса". Информационные веса используются: а) для создания списка признаков (для конкретной выборки объектов из генеральной совокупности), с целью использования этого списка при формировании диагностического набора признаков; б) для использования в качестве одного из сомножителей в весовых коэффициентах объектов, используемых в качестве эталонных при распознавании или при обучении распознаванию образов. Значение этих весовых коэффициентов особенно велико при решении задач распознавания (и обучения распознаванию) на множестве эталонных объектов в таких задачах, как диагностика неисправностей технических устройств [6,7,34,63-65], задачи определения рудоносности исследуемых месторождений.
Для геологии в [27] описываются основные правила отбора информации. 1) Формирование цели; 2) отбор эталонов; 3) отбор признаков; 4) построение таблицы эталонных объектов - вся имеющаяся информация об эталонах сводится в таблицу (для булевых признаков: выполнен - 1, не выполнен - 0, неизвестен для - _). Принцип отбора признаков: из двух различающихся признаков, входящих в допустимую таблицу, более существенным для характеристик объектов (месторождений, интрузивов, геологических районов, и т.п.) является тот, для которого информационный вес больше. В работе [40] уделено внимание методам определения информационныых весов геологических признаков. Авторы [27] рекомендуют, последовательно отбирая геологические признаки для исследования, также составить список всех признаков, существенное влияние которых на образование