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

 

С целью обеспечения высокой эффективности сложных, больших систем распознавания наряду с теоретическими исследованиями применяют математическое или (и) физико-математическое моделирование. Например, при построении локационных систем селекции и распознавания разрабатывается комплекс математических моделей, являющийся инструментом для организации исследований на основе выполнения математических экспериментов [7]. Физико-математическое моделирование предусматривает сочетание физических (лабораторных, натурных) и математических экспериментов. При этом, как отмечено в [7], роль математического эксперимента значительнее при лабораторных исследованиях, чем при натурных испытаниях. При разработке большой системы распознавания и ее элементов может реализовываться следующая цепочка: физико-математические исследования – натурные испытания.

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

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

В работе [1] рассматриваются следующие методы анализа данных:

· дискриминантный анализ – для построения разделяющих функций в признаковом пространстве;

· выделение и выбор признаков –для сужения избыточного множества признаков до подмножества «наилучших признаков» или их комбинаций;

· кластерный анализ – для разделения данных на подобные группы объектов.

В дискриминантном анализе формирование разделяющих функций основывается на одном из статистических или эвристических методов. Статистические методы нацелены на минимизацию ошибки классификации, представляющей собой вероятность неправильной классификации поступившего на распознавание k-мерного объекта X. К таким методам относят [1]:

· разделение с помощью квадратичной функции на основе использования плотностей нормального распределения;

· разделение с помощью линейных функций на основе использования плотностей нормального распределения;

· непараметрические методы, применяемые в случае отсутствия информации о виде кривой плотности распределения;

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

Эвристические методы ориентированы на критерии, непосредственно связанные с имеющимися исходными данными. К этим методам относят [1]:

· правило ближайшего соседа, в соответствии с которым, исследуемый объект относят к тому классу, к которому принадлежит его ближайший сосед из обучающей выборки;

· правило К ближайших соседей;

· оптимизация по какому-либо критерию ошибки выбранной разделяющей функции (линейной, квадратичной и т. д.), например, число неправильно классифицированных объектов из обучающей выборки, расстояние (среднее или «взвешенное») между обучающей выборкой и разделяющей функцией;

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

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

Кластерный анализ служит инструментом для выделения структур, классов, множеств подобных объектов из исходных неклассифицированных совокупностей. Ввиду многоаспектного характера применения кластерного анализа (социология, психология, биология, медицина, геология, астрономия и др.) в нем применяются разнообразные критерии, определяемые конкретными целями анализа в различных прикладных задачах. В литературе описано множество методов кластеризации, основанных на творческом подходе к использованию приемов кластерного анализа для создания «своего» метода кластеризации. Основы кластерного анализа изложены в работе [5].

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

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

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

В распознавании объектов, явлений, ситуаций и т. д. возможно применение идей теории нечетких множеств, в которых принадлежность элементов к таким множествам может принимать любые значения в диапазоне 0–1. Нечеткие множества можно применять в условиях неопределенности для квантифицирования и формализации различных неопределенных и интуитивных утверждений типа «теплый день», когда установлено всего лишь два класса дней: «жаркий день» и «холодный день». Тогда «теплый день» может принадлежать классу «жаркий день», например, со значением принадлежности 0,6 и к классу «холодный день» со значением принадлежности 0,15. Сумма указанных двух значений может быть отличной от единицы. В теории нечетких множеств вводятся понятия объединения и пересечения множеств. Например, принадлежность к объединению нечетких множеств А и В элемента ), имеющего значение принадлежности к множеству и к множеству , можно определить как:

 

 

а принадлежность к пересечению нечетких множеств А к В – как:

 

 

В распознавании, например, могут применяться нечеткие метки, нечеткие признаки и нечеткие классификации.

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

Введение понятия «нечеткие признаки» связано с искусственным «размыванием» значений признаков X, представляющих результаты объективных измерений и не содержащих нечеткостей, посредством отображения на интервале 0,1, например, в виде:

 

 

где αи β – положительные постоянные, подлежащие определению,

– «идеальное» значение признака для класса l.

 

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

 

 

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

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

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

NB

 

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

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

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

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

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

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

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

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

■ Детерминированные признаки – это признаки, характеризующиеся принимаемыми дискретными значениями на числовых осях в количественных шкалах измерения. Например, к ним относятся признаки, характеризующие весо-габаритные параметры элементов среды. Например, масса, вес, длина, ширина, высота и т. п., измеренные в шкале отношений.

■ Вероятностные признаки – это признаки имеющие по тем или иным причинам стохастический (случайный) характер.

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

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

■ Кластерный анализ служит инструментом для выделения структур, классов, множеств подобных объектов из исходных неклассифицированных совокупностей.

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

Литература

 

1. Верхаген К., Дейн Р., Грун Ф. и др. Распознавание образов: состояние и перспективы. – М.: Радио и связь, 1985.

2. Глушков В.М. Основы безбумажной информатики. – М.: Наука, 1987.

3. Горелик А.Л., Скрипкин В.А. Методы распознавания. – М.: Высшая школа, 1984.

4. Горелик А.Л., Гуревич И.Б., Скрипкин В.А. Современное состояние проблемы распознавания. – М.: Радио и связь, 1985.

5. Дуда Р., Харт П. Распознавание образов и анализ сцен. – М.:Мир, 1976.

6. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации. «Проблемы кибернетики». Вып. 33. – М.: Наука, 1978.

7. Селекция и распознавание на основе локационной информации / А.Л. Горелик, Ю.Л. Барабаш, О.В. Кривошеев и др.; Под ред. А.Л. Горелика. – М.: Радио и связь, 1990.

8. Харкевич А.А. Опознавание образов. –М.: Радиотехника, 1959. Т. 14,15.

9. Цыпкин Я.З. Основы теории обучающихся систем. – М.: Наука, 1970.

10. Энциклопедия кибернетики. – Киев: Главная редакция Украинской советской энциклопедии, 1975.

11. Rosenblatt F. Perception simulation experiments. – Proc. I.R.E., 1960.