Алгоритмы распознавания состояния объекта по экспериментальным данным

Существует несколько методов распознание данных. Далее приведены основные методы распознавания данных.

Основы статистической теории распознавания

Математически постановка задачи распознавания двух объектов и , измеряемые признаки которых являются случайными векторами , формулируется следующим образом. Известно, что частоты появления объектов характеризуются вероятностями и , и признаки описываются условными законами распределения:

, (2.3.1)

. (2.3.2)

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

1) принять решение «объект », если в действительности измерения признаков получены от объекта .

2) принять решение «объект », если предъявлен к распознаванию объект . Эти события являются случайными и описываются вероятностями и . Если стоимости ошибок обозначить и , то их математическое ожидание можно вычислить по формуле

. (2.3.3)

Выделим в гиперпространстве признаков область , точки которой принадлежат измерениям объекта . Тогда вероятность правильного распознавания объекта равна

(2.3.4)

т.е. вероятность того, что в область попадут измерения, характеризующие объект . Если в эту область попадут измерения объекта , то это будет ошибочное решение, вероятность которого равна

(2.3.5)

Так как вероятность ошибки , то, подставив в (2.3.3) выражение для и , получим после несложных преобразований

(2.3.6)

Условие минимума математического ожидания стоимости ошибок при принятии решения "объект " очевидно из анализа выражения (2.3.6): функция в квадратных скобках должна быть больше нуля

. (2.3.7)

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

(2.3.8)

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

. (2.3.9)

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

. (2.3.10)

Здесь , , , и – математические ожидания измерений и вероятности появления признаков.

Запишем ряд Тейлора с тремя членами окрестности вектора

. (2.3.11)

В этом выражении первая производная есть вектор-строка (градиент), вторая производная– матрица Гесса

, (2.3.12)

. (2.3.13)

Если выполнить все операции над векторами и матрицами, то логарифм отношения правдоподобия приближенно можно представить в виде ограниченного ряда Колмогорова-Габора

, (2.3.14)

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

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

 

 

Решающее правило распознавания на основе оценок параметров законов распределения

 

Предположим, что по результатам специально проведенного эксперимента для объектов класса и объектов класса получены измерения вектора признаков распознавания и результаты эксперимента сведены в таблицу 2.3.1

Таблица 2.3.1

Класс	Класс
		...				...
		...				...
		...				...
...	...	...	...	...	...	...
		...				...

 

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

, (2.3.15)

, (2.3.16)

, (2.3.17)

, (2.3.18)

, (2.3.19)

. (2.3.20)

 

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

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

Построение решающих правил методом группового учета аргументов

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

Таблица 2.3.2 Исходные данные

№
			...				...
			...				...
			...				...
...	...	...	...	...	...	...	...	...
n			...				...

 

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

(2.3.21)

и записать решающее правило распознавания объекта

. (2.3.22)

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

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

. (2.3.23)

(2.3.24)

Нормированные данные рассчитаем по формулам

(2.3.55)

(2.3.56) и составим таблицы и нормированных исходных данных.

Неизвестный логарифм отношения правдоподобия

(2.3.27)

представим в виде ряда Колмогорова-Габора. Ряд Колмогорова-Габора – это конечный ряд Тейлора степени . Например, при это полином вида

(2.3.28)

Здесь число неизвестных коэффициентов равно 5, при их 20, при их 75. Коэффициенты ряда модно определить по экспериментальным данным следующим образом. В соответствии с решающим правилом

(2.3.29)

если , т.е. измерения принадлежат объектам класса , и наоборот

(2.3.30)

если .

Можно составить систему уравнений вида

(2.3.31)

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

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

(2.3.32)

(2.3.33)

Запишем, используя нормированные данные таблиц и , уравнений для оценки коэффициентов и для оценки коэффициентов :

(2.3.34)

(2.3.35)

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

(2.3.36)

где , .

Умножив исходные уравнения на и и определив средние значения, составим второе уравнение:

, (2.3.37)

где

Третье уравнение запишется в виде:

(2.3.38)

где

Четвертое уравнение сформируем после умножения исходных уравнений на и и их усреднения:

, (2.3.39)

где .

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

. (2.3.40)

Совершенно аналогично определяются коэффициенты второго полинома. Его оценку запишем в виде

. (2.3.41)

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

Таблица 2.3.3 Промежуточные данные

№
...	...	...	...	...

 

Сформируем теперь третий полином Колмогорова-Габора относительно и

. (2.3.42)

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

. (2.3.43)

Если теперь вместо и в (2.3.73)подставить выражения (2.3.70) и (2.3.71), то получим формулу для оценки логарифма отношения правдоподобия

(2.3.44)

где определяется через оценки коэффициентов , , .

Решающее правило распознавания объекта имеет вид:

(2.3.45)

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

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

, (2.3.63)

, (2.3.63)

(2.3.63)

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

Первая таблица промежуточных данных

№
			...				...
			...				...
			...				...
...	...	...	...	...	...	...	...	...
			...				...

 

Каждому полиному соответствует вероятность распознавания

. (4.3.8)

Для оценки вероятностей воспользуемся восстановленными непосредственно по экспериментальным данным функциями распределения

.

В результате получим формулы для оценки и :

, (4.3.9)

.

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

Таблица эффективностей

	-
	-	-
	-	-	-
	-	-	-	-

 

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

Предположим, что для распознавания используются два параметра:

, ,

, ,

где -нормальные ошибки измерений.

Если , , то по методу минимума средней вероятности ошибки эффективность решающих правил равна:

, , (4.3.10)

.

Из анализа (4.3.10) можно сделать следующие выводы:

1) если примерно равно , то ;

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

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

, ,

, ,

где - ошибки оценивания.

Вероятность распознавания по двум параметрам будет равна

. (4.3.11)

Рассмотрим числитель под знаком интеграла вероятности. Подкоренное выражение преобразуем к виду:

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

. (4.3.12)

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

,

где - нормальные случайные величины с нулевым средним и дисперсией .

Закон распределения -это закон Райса (обобщенный закон Релея)

.

Вероятность выполнения условия (4.3.12) равна

, (4.3.13)

где .

Известен табличный интеграл

.

Для определения вероятности получим формулу

, (4.3.14)

где - размер выборки, по которой оценивались неизвестные параметры.

При больших значениях аргумента функция Бесселя равна

.

Следовательно, приближенно вероятность можно оценить по формуле

. (4.3.15)

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

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

.

Важным достоинством метода группового учёта аргументов является то, что на каждом этапе отбора используются одни и те же алгоритмы.

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

1) для оценки неизвестных коэффициентов рядов Колмогорова-Габора;

2) для оценки вероятностей распознавания.

Как показали исследования, такие оценки завышены (занижены вероятности ошибок). Хотя это мало сказывается на правильности отбора пар признаков, но если исходные выборки данных большого размера (100 и более), то их следует разделить на две группы:

1) обучающие, используемые для оценки коэффициентов полиномов;

2) проверочные, используемые для оценки вероятностей и отбора параметров.

Для обучения отбирается примерно 2/3 измерений, для контроля - 1/3.

Гистограммный метод распознавания

Предположим, что контролируемый объект может находится в двух состояниях и известны выборки измерений, полученные при состоянии и состоянии :1) ; 2) .Размеры выборок достаточны, чтобы построить гистограммы: 1) ; 2) . Если бы были известны законы распределения и , то можно было бы определить теоретические гистограммные вероятности и и для случайных величин , где - число измерений выборки , попадающих в i-й интервал гистограммы, записать условные полиномиальные законы распределений

(4.4.1)

Заменим в (4.4.1) и их оценками и , составим отношение правдоподобия

(4.4.2)

и определим его логарифм

(4.4.3)

Для распознавания состояния объекта необходимо по измеренной выборке определить гистограммные числа , вычислить логарифмическую функцию отношение правдоподобия и сравнить её с порогом . Эффективность алгоритма можно оценить, определив вероятности ошибок и , полагая порог . Логарифм отношения правдоподобия (4.4.3) как сумма биномиальных случайных величин имеет распределение, близкое к нормальному. Его математическое ожидание равно

Дисперсию вычислим, учитывая, что случайные величины и коррелированы и . В этом случае