2. Меры близости между объектами в пространстве разнотипных шкал.

В реальных задачах часто приходиться работать с объектами характеристики которых, измерялись в разных шкалах. В этом случае возникает непростая проблема оценки меры расстояния, близости, похожести как между объектами (строками), так и между свойствами (столбцами). Как правило, ищутся такие меры, которые удовлетворяли бы обычным аксиомам метрического пространства (непрерывности, симметричности и т. п.), были инвариантны к допустимым преобразованиям для данного типа шкалы и не зависели от состава изучаемых объектов. Итоги этих рассмотрений сводятся к тому, что меры, инвариантные к допустимым преобразованиям для многих шкал, можно указать, а мер, которые не зависели бы от состава выборки, не существует. Добавление к конечной выборке А или изъятие из неё какого-нибудь объекта может изменить прежние порядковые номера объектов i и l (для шкал порядка) или нормировку (для более сильных шкал), что приводит к изменению расстояния d(i, l) между i-м и l-м объектами.

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

Исследователь должен либо знать, что выборка A включает полный набор изучаемых объектов, и тогда трудности, описанные выше, возникнуть не могут. Либо он должен верить в то, что выборка А представляет лишь часть генеральной совокупности G, но достаточно хорошо отражает её закономерности, т. е. что выборка представительна. Тогда меры d(i, l) будут одинаковыми для объектов i и l независимо от того, рассматриваем ли мы их на фоне выборки A или на фоне генеральной совокупности G. Выводы (т. е. таксономия, решающие правила, регрессионные уравнения и т. д.), сделанные на основании такой выборки, будут сохраняться и на генеральной совокупности. Некоторые отклонения от идеальной представительности можно частично компенсировать применением процедур, повышающих устойчивость d(i, l) к случайным возмущениям. Например, нормировку делать не по крайним значениям характеристик, а по их дисперсии или медиане.

А если выборка A непредставительна, то никакие формальные ухищрения, в том числе и гарантии инвариантности d(i, l) к допустимым преобразованиям шкал, не имеют смысла: из-за не представительности A индуктивные выводы для G все равно будут ложными.

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

5. Статистическая постановка задачи распознавания. Байесово решающее правило.

Статистический подход к задаче распознавания.

Генеральная совокупность изучаемых объектов Г.

Данное множество объектов (явлений, ситуаций) разбито на ряд подмножеств (классов, образов) Г1,…,Гt,…,Гk,

где k – число образов, k>1;

каждый объект из Г описывается набором характеристик Х={X1,…,Xj,…,Xn};

Ωj – множество возможных значений признака Xj,

Ω= Ω1х…хΩjх… n задает многомерное пространство переменных;

Произвольному объекту аГ может быть поставлен в соответствие вектор Х(а)=( X1(a),…,Xj(a),…,Xn(a)), Х(а) будем обозначать через х, Xj(a) – через xj;

Номинальная переменная Y c множеством значений ΩY={1, 2, … , t, …, k} соответствует имени класса.

Основные обозначения и определения

Задача распознавания образов состоит в том, чтобы для произвольного а ΩГ по значениям x1,…,xj,…xn предсказать y.

Отображение d: Ω-->ΩY назовём решающей функцией. Ей соответствует разбиение множества Ω на k непересекающихся подмножеств Ω1,…, Ωt,… Ωk покрывающих Ω, где Ωt={x | d(x)=t}. Через D0 обозначим множество всевозможных отображений Ω->ΩY.

Объект а из генеральной совокупности Г выбирается случайным образом. Поэтому величины X1,…,Xj,…,XN являются случайными величинами.

Под стратегией природы понимается совместное распределение Р(у, х) случайной величины Y и n-мерной случайной величины Х=( X1,…,Xj,…,XN), у принадлежит ΩY , х принадлежит Ω. В дальнейшем стратегию природы будем обозначать через с.

P(y, x)=P(y)P(x|y)=P(x)P(y|x)

P(s) – априорная вероятность образа s.

P(x|y)=Ps(x)

P(y|x)=Px(s)

Байесовская решающая функция

Вероятность ошибки для фиксированной стратегии природы с в случае использования решающего правила d обозначим P(d, c);

P(d, c)=P(1)*P1+…+P(s)*Ps+…+P(k)*Pk, где Ps – вероятность ошибки s-го образа, т.е. вероятность того, что объект другого образа будет ошибочно распознан как объект s-го образа;

Оптимальной решающей функцией в случае произвольной стратегии природы с называется такая функция d0, при которой выполняется соотношение: P(d0, c)= inf{P(d, c)| d D0};

Байесовской решающей функцией в случае произвольной стратегии природы с называется такая функция d*, которая при эмпирическом факте Х(а)=х объект а относит к тому образу w, при котором условная вероятность Px(w)=P{Y(a)=w|X(a)=x} максимальна, то есть Px(w)=max {Px(s)| s=1..k}. Когда максимальное значение достигается на нескольких образах, объект а относится к любому из них.;

Оптимальной решающей функцией является Байесовская решающая функция d*

d*: w=argmax {PsPs(x)| s=1..k}

НО:

Стратегия природы с, определяющая значения Ps и Ps(x)(s=1..k) на практике неизвестна

Дана обучающая выборка А, представленная таблицей {xi(aj),y(aj)|i=1,..,N, j=1,..,M}

Требуется получить эмпирические оценки s и s(x) по выборке

При подстановке эмпирических оценок Байесов классификатор перестаёт быть оптимальным