Материал: Мясников В.В. Основы статистической
3 л и н е й н ы е к л а с с и ф и к а т о р ы
Цель работы - изучение теоретических основ и экспериментальное исследование методов построения линейных классификаторов для распознавания образов.
В лабораторной работе изучаются методы построения линейных классификаторов, основанные на критериях минимума суммарной вероятности ошибочной классификации, минимума среднеквадратической ошибки решения, максимума критерия Фишера. Также изучаются итерационные методы настройки классификаторов: алгоритм персептрона и алгоритмы, основанные на методе стохастической аппроксимации.
ЗЛ Теоретические основы лабораторной работы
3.1.1 Постановка задачи построения линейного классификатора
Классификатор называется линейньш, если его дискриминантная функция является линейной, то есть допускает представление в виде
d{x) = w'^x + W]^ , |
(3.1) |
где X = {XQ,...,XJP_I Y - вектор признаков, который определяет образ объекта, |
|
подлежащего классификации, W = {wQ,...,Wf^_Yf |
- вектор весовых |
коэффициентов классификатора, ттд? - пороговое значение. При этом процесс
принятия решения о номере класса текущего объекта производится в соответствии со следующим правилом:
N - \ |
|
|
(To |
< |
1^1 |
Задача синтеза линейного классификатора заключается в поиске вектора |
||
коэффициентов W и порогового значения |
оптимальным в каком-либо |
|
смысле образом.
Известно [3,5,6,8,9,11,12], что байесовский классификатор в случае нормальных распределений с равными корреляционными матрицами является линейным. Однако часто равенство корреляционных матриц является неприемлемым предположением и, более того, возникает
35
необходимость построения линейного классификатора вообще отказываясь от нормальности распределений.
3.1.2 Линейный классификатор, минимизирующий суммарную вероятность ошибочной классификации
Предположим, что случайная величина d{x^ (как функция случайного вектора X ) распределена по нормальному или близкому к нему закону
распределения в кащдом из классов Qg и Q j . В этом случае для вычисления вероятностей ошибок достаточно знать лишь математические ожидания и
дисперсии случайной величины |
в каждом из классов. |
||
Действительно, параметры одномерных нормальных распределений |
|||
случайной величины |
имеют вид |
|
|
ш/ = M ( d ^ ) / n i ) = w ' ^ M l +wj,f, |
|||
|
|
|
(3.3) |
a j = D [d^)lD .i ) = W ^ BiW, |
/ = 0Д, |
||
где |
|
|
|
Ml |
|
|
|
BI =M |
[{X - M iX^i-MiJInX |
/ = од |
|
|
V |
|
|
- вектор математических ожиданий и корреляционная матрица случайного вектора X соответственно. В силу же (2) вероятности ошибочной классификации первого ивторого рода [8,12,6] записываются следующим образом:
О |
00 |
Р\ = щ)\ f d |
(м/^1 |
. |
P o =щ)\ f d (м /^0 ) d u , |
(3.4) |
— 00 |
|
|
О |
|
где |
(/ = 0,l) |
- |
плотности вероятностей |
нормального |
закона распределения с соответствующими параметрами.
Зададим критерий оптимальности линейной дискриминантной функции в виде
A = P (Q g);?g+ P (Q l);?l ^ j n i n , |
(3.5) |
lV,Wjv |
|
36
где |
P (QO)A(I^I ) - априорные вероятности появления объектов классов Qg и |
Qj |
соответственно. Критерий (5), таким образом, определяет оптимальную |
линейную дискриминантную функцию, которая дает минимальное значение суммарной вероятности ошибочной классификации.
С учетом (4) показатель качества критерия (5) может быть переписан в
следующем виде: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
щ |
|
|
|
|
|
|
К = Р{По) |
ехр |
du +P{o.i) |
|
|
ехр |
|
du . |
(3.6) |
||
™о л/хтг |
|
|
42% |
|
|
|
|
|||
Необходимым условием минимума показателя (6), как известно, является |
||||||||||
равенство нулю его частных производных по W |
я |
: |
|
|
|
|
||||
|
|
1 2 4 . |
д |
f |
Щ) |
+ |
|
|
||
dW |
4 b i |
dW I ^0 |
|
|
||||||
|
|
|
||||||||
|
|
|
m l |
d |
< |
_гщ |
\ |
|
|
|
|
- 4 ( Q l) - ^ e x p |
|
|
|
|
|
||||
|
2а? J |
|
|
|
|
|
|
|
||
|
л12ж |
[ |
dW |
|
|
|
|
(3.7) |
||
|
|
( |
2 |
|
|
|
|
|
|
|
|
|
|
d |
f |
|
|
|
|
||
dwN |
|
|
MQ |
|
|
|
|
|
||
42% |
V |
dw x I |
^ o j |
|
|
|||||
|
|
|
m l |
d |
|
|
4 |
|
|
|
|
+ P { 0 .i) - ^ e ^ V |
|
|
|
|
|
||||
|
2a? J dwN |
, |
^ ly ' |
|
|
|||||
|
ф2% |
, |
|
|
||||||
Подставляя в (7) вьфажения для частных производных |
|
|
|
|||||||
|
т. |
M l ^ |
BiMi |
|
|
|
|
|
||
|
dW V |
а |
|
|
|
|
|
|
|
|
щ
dwN СТ/
окончательно получим следующую систему уравнении:
37
|
^ ( ^ l ) - T ^ e x p |
2a? |
|
|
|
|
|
|
|
|
V2Tia, |
|
|
|
|
|
|
||
|
|
= ^ 0 > |
V ^ a , |
-exp |
m l |
|
|
|
(3.8) |
|
|
|
2a? |
|
oo |
2 |
|
||
|
|
|
mf |
|
|
|
|
|
|
|
|
-exp |
= ^(f2o) |
|
-exp |
WQ |
|
||
|
|
2a? |
|
2ag J |
|
||||
|
|
Tca^ |
|
|
Tiag |
|
|||
|
При выполнении второго равенства в (8) первое уравнение системы |
||||||||
можно переписать в виде |
|
|
|
|
|
|
|
||
|
|
M i- M o = |
mi г. |
то |
Во |
W . |
|
(3.9) |
|
|
|
a i |
- — |
|
|||||
|
|
|
|
ад |
|
|
|
|
|
|
Решение уравнения (9) может быть получено с помощью следующей |
||||||||
итеративной процедуры (процедура Петерсона-Матсона): |
|
||||||||
|
|
W = [sBo+{\-s)Bi] |
1 ^ 1 -М о ), |
|
(3.10) |
||||
где |
|
|
|
|
|
|
|
|
|
|
|
.-2 ( ^ ..- 2 |
|
_-2 |
|
0 < 5 < 1 . |
|
||
|
5 = -Шдао |
te ja i |
-Шдад Г . |
|
|||||
Из |
вьфажения |
для |
|
следует |
|
справедливость |
равенства |
||
2 |
2 |
|
|
учитывая |
соотношения (3), |
получаем |
|||
5ag/wi + (1- 5)aj/Ид = О, откуда, |
|||||||||
вьфажение для |
! |
|
|
|
|
|
|
|
|
|
|
|
5 а?м [ +(1-5)ст?Мо — |
|
(3.11) |
||||
|
|
1Тл? = ----------- 9^ |
^ |
9 ^ |
■ |
|
|||
|
|
|
5ад + ( l- 5 ) a j |
|
|
|
|||
С использованием вьфажений (3.10) и (3.11) для W ж м>„ можно построить график зависимости суммарной вероятности ошибочной классификации R от единственного параметра 5 (о < 5< l) и в качестве окончательного ответа принять то значение параметра, при котором R{s)
имеет минимум. Пример подобного решения приведен на рис.3.1.
38
