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

Актуальность темы

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

Теория и практика распознавания особенно успешно развивались в последние 40−50 лет. В теоретических работах исследовались, в том числе, методы распознавания, применяемые человеком. На основе результатов этих исследований разрабатывались математические модели, имитирующие процессы распознавания человеком.

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

Это объясняется тем, что основные работы по построению общих моделей распознавания и решающих правил проводились, в первую очередь, в предметных областях, где опыт распознавания сравнительно невелик в связи с редкими актами распознавания, а эффект (в первую очередь, экономический) от получения новых усовершенствованных правил распознавания, достаточно велик, в первую очередь, за счет более точного распознавания. Этот эффект не только покрывает затраты на научно-исследовательские и опытно-конструкторские работы, но и приносит прибыль. К таким предметным областям относятся, в первую очередь, геология (в частности поиск и исследование рудных месторождений). Теоретические и прикладные работы в предметных областях, где накоплен многовековой опыт распознавания (однако, велики финансовые ограничения): в микробиологии, медицине, ветеринарии — велись в меньших объемах и с меньшим успехом. В этих предметных областях традиционно велика интенсивность работ по распознаванию (идентификации, диагностике, прогнозированию). Возможны резкие колебания интенсивности потока требований на распознавание, в частности, увеличение интенсивности этого потока в экстремальных ситуациях (например, в медицине, микробиологии — при эпидемиях, военных конфликтах). Насколько доля работ по распознаванию среди всех работ в предметной области велика в медицине, можно судить по характеру и структуре курса обучения в медицинских ВУЗах в сравнении с курсами обучения, например, в машиностроительных ВУЗах. Так, в медицинском ВУЗе из двух основных задач врача: диагностирование заболевания и назначение лечения, большая часть времени в курсе обучения (теоретического и, особенно, практического) занимает задача обучения диагностированию заболеваний. В машиностроительном ВУЗе диагностированию причин нарушения технологии производства и сбоев производственного процесса уделяется, в лучшем случае, очень мало внимания: считается, что редко встречающиеся в работе инженера задачи анализа причин нарушения технологических процессов или процессов организационного управления можно изучить и усвоить в процессе выполнения работ. Одной из причин меньшего успеха в разработке и внедрении методов распознавания в вышеуказанных трех предметных областях, в частности в медицине, является то, что усилия направлялись, в первую очередь, на разработку проблем построения решающих правил в этих предметных областях, а не на другие, более актуальные, проблемы [17,57].

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

Косвенно задача уменьшения затрат ресурсов (и, возможно, времени) решается при уменьшении количества используемых признаков для распознавания [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] рассматриваются способы формирования множеств признаков для распознавания («рабочих словарей признаков»), являющихся подмножествами «априорного словаря признаков» — множества признаков, описывающих объекты. Рабочий словарь признаков формируется и используется, если возникают ограничения в финансовых затратах на оборудование, приборы, предназначенные для измерения (оценки) значений признаков при распознавании. Такие задачи решаются при проектировании системы распознавания или при выполнении процесса распознавания после выбора и измерения значения очередного, r-го признака, когда или принимается решение о принадлежности распознаваемого объекта к одному из классов и, соответственно, об окончании процесса распознавания, или о выборе и измерении значения r+1-го признака. К существенным недостаткам предложенного способа следует отнести: 1) последовательное выполнение всех работ [67] по измерению значений признаков, что не позволяет существенно уменьшать затраты времени (продолжительность) работ в тех случаях, когда работы можно было бы вести параллельно- 2) анализ решений о результатах распознавания, принимаемых на промежуточных стадиях процесса распознавания, также может создавать неоправданные дополнительные затраты времени, увеличивающие общую продолжительность работ, что неблагоприятно может сказаться на вышеописанных экстремальных ситуациях- 3) большинство решений, которые согласно [20] принимаются при распознавании неизвестного объекта, могут быть подготовлены и приняты с достаточно высоким качеством заранее — на стадии ОРО, а корректировки этих решений при распознавании могут быть достаточно редкими. Количество таких корректировочных решений может быть уменьшено путем увеличения обучающей выборки [14,57] и улучшения решающего правила, например, [15,29,30,45,57].

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

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

Возможностям успешного решения вышеуказанных проблем могут способствовать результаты теоретических и прикладных научных работ в технической диагностике, в первую очередь, с использованием достижений теории автоматов [6,7,18,64,66]. Так, одной из основных областей приложения теории экспериментов с конечными детерминированными автоматами (КДА) является распознавание (диагностика) таких свойств функционирующих систем, которые могут быть представлены наблюдаемым поведением конечных автоматов. Средствами теории экспериментов с автоматами могут быть построены оптимальные эксперименты по выбранному критерию оптимальности. В ряде случаев в качестве предмета для оптимизации эксперимента является время. Актуальной задачей минимизации времени эксперимента по распознаванию свойств объектов является задача идентификации болезнетворных микроорганизмов в медицине и ветеринарии в связи с зависимостью эффективности лечения от сроков принятия решения. Задача идентификации в автоматной интерпретации определяется как перевод автомата из начального состояния, соответствующего принадлежности идентифицируемого объекта множеству всех классов в состояния, соответствующее только одному классу.

Методы, основанные на распознавании объектов, описанных как последовательности значений признаков, сформировались на протяжении последних 20−30 лет и сформулированы в ряде работ [14,21,23,25,26,2729,45,6971]. Наиболее закончено в концептуальном и практическом плане эти методы сформулированы в [21,29]. В этих и подобных им работах, задача распознавания формулируется, в той числе, и как задача определения набора наиболее информативных признаков для описания объектов, выявления связей между этими признаками и информацией о классах объектов и описания методов распознавания.

Разработаны различные способы определения важных для распознавания признаков в различных предметных областях [21,30,31,41,48,59,62,71]. В этих работах предлагаются различные методы для отбора информативных признаков, в том числе, с помощью так называемых тупиковых тестов (неизбыточных ключевых наборов признаков). В ряде перечисленных работ, посвященных тестам, в частности [59,62,71], рассматриваются алгоритмы получения всего множества «тупиковых тестов» .

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

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

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

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

Для достижения указанной цели поставлены и решены следующие Задачи работы.

1. Разработка методов формирования минимальных тестов на выборке эталонных объектов, описанных кортежами значений признаков.

2. Разработка методов формирования минимальных тестов на выборке эталонных объектов, описанных частотами или относительными частотами появления объектов с заданным значением заданного признака в заданном классе — для всех значений, всех признаков, всех классов разбиения множества эталонных объектов.

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

Методологическая и теоретическая основа исследования.

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

Выполненные исследования и разработки опираются, в первую очередь, на труды специалистов в списке литературы в диссертации, а также на труды этих и других специалистов, которые не вошли в список литературы. Среди специалистов, работы которых оказали решающее влияние на формирование взглядов автора и выполнение данного диссертационного исследования, необходимо упомянуть, в первую очередь, таких ученых (представленных в алфавитном порядке), как А. М. Богомолов [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], Ю. А. Шрейдер [72,73].

Научная новизна.

1. Разработаны новые методы формирования минимальных тестов на множествах объектов, описанных как кортежи значений &-~значных (к>2) признаков с использованием или без использования матрицы различий.

2. Разработаны новые методы формирования минимальных тестов на множествах объектов, описанных в таблицах с частотами или относительными частотами появления объектов с различными значениями А>значных признаков.

3. Разработаны методы формирования тестов с минимальными затратами ресурсов и/или времени.

4. Предложены: способ оценки представительности выборки эталонных объектов для теста и метод создания представительной выборки абстрактных эталонных объектов, описанных кортежами значений признаков.

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

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

Структура и объем работы. Работа состоит из 5 глав, введения, заключения, приложений, списка литературы и содержит 260 страниц машинописного текста.

ЗАКЛЮЧЕНИЕ

.

Результаты моделирования ситуаций распознавания позволили сделать выводы о важности и актуальности поставленной и решенной в диссертационной работе проблемы в рассмотренных предметных областях (медицине, микробиологии, ветеринарии) — проблемы минимизации затрат ресурсов и/или времени при распознавании (диагностике, идентификации, прогнозировании).

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

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

Работа посвящена методам формирования рабочих словарей признаков-подмножеств априорного словаря признаков. Априорный словарь признаков формируется экспертами предметной области. Рабочие словари признаков формируются как множества признаков, оптимальные по затратам ресурсов и/или времени и точности распознавания, используется один или несколько тестов с минимальными затратами ресурсов и/или времени. Если затраты ресурсов мало различаются для различных признаков теста, то формируется минимальный тестесли затраты ресурсов различны для различных признаков, то формируемый тест может оказаться большей длины, чем минимальный, однако он — тупиковый.

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

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

Созданы математические основы для разработки новых алгоритмов формирования минимальных тестов;

Созданы новые алгоритмы формирования тестов минимальной (или близкой к минимальной) длины на множествах объектов, описанных как кортежи значений Л-значных признаков {к>2), с использованием или без использования матриц различий;

Разработаны новые алгоритмы формирования тестов минимальной (близкой к минимальной) длины на множествах объектов, описанных количествами или частотами появления объектов с заданными значениями &—значных признаков {к> 2);

Разработаны методы формирования тестов с минимальными затратами ресурсов и/или времени;

Разработаны методы формирования подмножеств тестов, обеспечивающих оптимальное соотношение точности распознавания и затрат ресурсов.

Даны примеры реализации методов и алгоритмов формирования тестов с минимальными затратами ресурсов и/или времени.

Работа выполнена с ориентацией на медицину, микробиологию. Результаты исследований могут быть использованы в других предметных областях, например, химии, криминалистике.

Необходимо на основании результатов диссертационной работы провести следующие исследования:

1) исследование методов формирования минимальных тестов с целью выработки решений, повышающих точность и надежность распознавания при минимальных затратах;

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

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