Определение значений порогов

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

Допустим, что х и х обозначают соответственно значения признака до и после квантования. Предполагается, что х — случайная величина с плотностью вероятности р(х) . Кроме того, предполагается, что х не выходит за пределы некоторого интервала: a_fи, где а,и а_и — нижняя и верхняя границы интервала.

При решении задачи о квантовании необходимо выбрать такой набор пороговых уровней dj и уровней квантования г, что если d_}<х < d_j+x, то исходное значение признака заменяется на число, равное уровню квантования г-

^Ximin

Xi тах^Хгтт

Хгтах Xsmin

X зтах¹

Х₁ = 0010,Р₁ =4; Х₂=01,Р₂ = 2;

N = Z Р, = 4 + 2 + 3 = 9;

Y= 001001100.

Х₃ = 100, Р₃ = 3.

Рис. 4. Формирование признакового слова объекта

Решение задачи выбора значений порогов признаков возможно на основе анализа всего заданного алфавита объектов распознавания S относительно распределения значений его признаков по классам объектов. Такой анализ проводится по обучающей выборке, характеризующей различные возможные состояния объектов всех L классов алфавита 5. Множество объектов, из которых производится выборка, составляет генеральную совокупность. Число объектов выборки определяет её объём. Будем использовать бес-повторную выборку, когда отобранный объект в генеральную совокупность не возвращается.

Наблюдаемое значение, характеризующее признаки объектов выборки, называют вариантой, а последовательность вариант в возрастающем порядке — вариационным рядом. Если в выборке объема п варианта х,- наблюдается n_t раз, относительная частота варианты выражается как i = п,/п. Перечень вариант и соответствующих им частот образует статистическое распределение значений признаков выборки.

Статистическое распределение выборки можно представить также в виде последовательности интервалов и соответствующих им частот, что особенно удобно, если признак принимает множество близко отстоящих значений, а объём выборки небольшой. Интервал а_к, в котором заключены все варианты некоторого признака а_к ^{= Х}ктах ~ ^хк min’ разбиваем на несколько ча-стичных интервалов А, и находим для каждого из них сумму частот «, вариант, попавших в /'-й интервал. Если все частичные интервалы одинаковы (А, = А), то соответствующие варианты называют равноотстоящими, причем их численные значения определяются точками, лежащими посредине частичных интервалов.

Отложив по оси абсцисс частичные интервалы и построив на них как на основаниях прямоугольники высотой и,/hj (или ,/hj), получим гистограмму частот (или относительных частот). Величина л,/Л, называется плотностью частоты, a j/hj — плотностью относительной частоты.

Если через п_х обозначить число наблюдений, при которых значение признака меньше х, то F*(x) = п_х/п представляет собой эмпирическую функцию распределения. В соответствии с теоремой Бернулли при увеличении числа испытаний относительная частота события по вероятности стремится к вероятности этого события. Поэтому Г*(х) приближается к интегральной (теоретической) функции распределения Т(х).

Выбор порогов является первым этапом обучения системы распознавания по обучающей выборке . При этом в память ЭВМ вводятся значения всех признаков для всех L классов объектов. На основании этих данных решается задача выбора значений порогов dj по каждому признаку X/.

Для этого диапазон значений a_t признаков x_z разбиваем на С интервалов величиной h_t = a_t/C. При выборе С необходимо исходить из того, что размер частичного интервала А/должен быть не меньше дискретности х, получения значения рассматриваемого признаках/, т. е. h_l>x_b и больше удвоенной ошибки, возникающей при измерении значения признака х_/5 h_t>2 _ь Число интервалов С не должно быть меньше числа классов L заданного алфавита объектов, С > L. Выполнение последнего условия позволяет сохранить максимальное значение информативности признаков после их квантования в случае полной разделимости всех L классов объектов по значениям одного кодируемого признака.

В общем случае, чем больше число С интервалов первоначального разбиения области значений /—го признака будет выбрано, тем точнее, в смысле информативности представления признака в признаковое слово объекта, могут быть выбраны пороги позиционного кодирования признаков. Однако, как уже отмечалось, увеличение числа С ведет к линейному увеличению требуемого для реализации алгоритма объема памяти и времени вычислений. Таким образом, при выборе С нужно исходить из вычислительных возможностей СР и условия L < С < max(a_t/

Разбиение области значения признака x_z на С интервалов осуществляется при помощи С — 1 границы d_r, г = 1, 2,..., С — 1.

^dr ^{= x}emin + ^rai/C, Г = 1, 2, ..., С- 1.

На установленных интервалах значений признака X/, I = 1, 2,..., q на одной оси абсцисс строятся гистограммы относительных частот или эмпирические функции распределения F_k(xj) значений признака для всех классов к = 1,2,..., L.

Численное значение F_k(xfr на r-м интервале равно числу объектов обучающей выборки класса к, имеющих значение признака х_/з лежащего в интервале (d_r__{, d_r), d_r__x t< d_r.

По совокупности эмпирических функций F_k(xj), к = 1, 2,..., L определяются пороги двоичного позиционного кодирования значений признака x_z из априорного словаря. Для этого просматривается вариационный ряд, начиная с первого интервала, соответствующего минимальному значению /-го признака, и на каждом интервале г = 1, 2,..., С определяется характеристическое множество V[ ^е 5 классов объектов обучающей выборки , для которых на данном г-м интервале значение F_k(xfr_r* 0.

Для оперирования с подмножеством V множества S в компьютеру удобно принять следующий подход [3]. Предположим, что все рассматриваемые множества являются подмножествами некоторого конечного множества S (множество классов объектов). Пусть S содержит L различных элементов, помеченных как 1,

2,..., L (каждый элемент помечен определенным целым числом — номером класса). Мы можем представить любое подмножество V множества 5 цепочкой или последовательностью нулей и единиц. Если /-я позиция или бит этой цепочки есть 1, тогда элемент под номером i и обозначаемый V, находится в V; если же там 0, то V, не принадлежит V, например, если в S шесть элементов, то V = (0,0,1,0,1,1) представляет множество V, состоящее из элементов И₃, И₅ и К₆, а = (0,0,0,0,0,0) представляет пустое множество (всегда обозначаемое ), не содержащее ни одного элемента, в то время как S = (1,1,1,1,1,1). Любая такая последовательность, представляющая множество V, известна как характеристический вектор V (по отношению к S). Если |5| меньше, чем число битов в слове ЭВМ, то можно представить любое V < S одним словом памяти.

Порог Н, устанавливается на границе d_r в том случае, если при переходе через границу d_rB сторону увеличения варианты x_h начиная с первого интервала г = 1, происходит изменение характеристического множества Vf, т.е. V[K/⁺¹. При этом необходимо, чтобы выполнялось условие Vf* и .