ВУЗ:
Составители:
Рубрика:
X
X X
s > 2 {X
t
}, t = 1, s
X
x
1
, x
2
, . . . , x
m
, x
m+1
, . . . , x
m+l
X
x
1
, x
2
, . . . , x
m
x
m+1
, . . . , x
m+l
L = m + l
Y {K
1
, . . . , K
s
}
f
∗
: X → Y
X n
Ââåäåíèå
Ðàñïîçíàâàíèå îáðàçîâ íå ñâîäèòñÿ ê ìåòîäàì ðàçäåëåíèÿ íàáîðîâ ïîäìíîæåñòâ â
ïðèçíàêîâîì ïðîñòðàíñòâå. Âàæíî íå òîëüêî ïîëó÷èòü àëãîðèòì, ðåàëèçóþùèé (âîçìîæíî
ñ íåêîòîðûìè îøèáêàìè) òðåáóåìîå ðàçäåëåíèå êëàññîâ, íî è èìåòü îöåíêó íàäåæíîñòè
ðåøåíèÿ ïîñòàâëåííîé çàäà÷è, ò.å. çíàòü, êàê ÷àñòî äàííûé àëãîðèòì áóäåò îøèáàòüñÿ ïðè
êëàññèôèêàöèè âíîâü ïðåäúÿâëÿåìûõ îáúåêòîâ. ßñíî, ÷òî óêàçàííàÿ îöåíêà íàïðÿìóþ
îïðåäåëÿåò êà÷åñòâî ðåøåíèÿ ïîñòàâëåííîé çàäà÷è. Íà ïðàêòèêå æå äàòü òàêóþ
îáîñíîâàííóþ îöåíêó àïðèîðè ÷àñòî îêàçûâàåòñÿ çàòðóäíèòåëüíûì.
Íåñìîòðÿ íà óêàçàííóþ âàæíîñòü, ìåòîäû îöåíêè íàäåæíîñòè âûáðàííîãî ðåøàþùåãî
ïðàâèëà ðàçâèòû çíà÷èòåëüíî ñëàáåå, ÷åì òåîðèÿ ïîñòðîåíèÿ ðàñïîçíàþùèõ àëãîðèòìîâ.
Ïðîáëåìà óñóãóáëÿåòñÿ åù¼ è òåì, ÷òî ïðè ðåøåíèè ïðàêòè÷åñêèõ çàäà÷ ðàñïîçíàâàíèÿ
îáðàçîâ ÷àñòî ïðèõîäèòüñÿ äîâîëüñòâîâàòüñÿ ìàëûì ÷èñëîì èìåþùèõñÿ â íàëè÷èè
ïðåöåäåíòîâ.  ýòîì ñëó÷àå òèïè÷íîé ÿâëÿåòñÿ ñèòóàöèÿ, êîãäà ëèáî ïàðàìåòðû
ôîðìóë îöåíêè îøèáîê ðàñïîçíàâàíèÿ íàõîäÿòñÿ âíå ãðàíèö ïðèìåíèìîñòè ìåòîäà, ëèáî
ïîëó÷åííûå îöåíêè îêàçûâàþòñÿ ñèëüíî çàíèæåííûìè èëè çàâûøåííûìè è èíòóèòèâíî
íåïðèåìëåìûìè, êàê, íàïðèìåð, íóëåâàÿ òî÷å÷íàÿ îöåíêà îøèáêè ïðè êîððåêòíîì
àëãîðèòìå ðàñïîçíàâàíèÿ.
Âûøåñêàçàííîå ñâèäåòåëüñòâóåò î íåîáõîäèìîñòè ïðåäëîæèòü íîâûå ïîäõîäû ê
ïîñòðîåíèþ îöåíîê àëãîðèòìîâ ðàñïîçíàâàíèÿ, ñïîñîáíûõ îõâàòèòü âàæíûé ñëó÷àé
ìàëîãî ÷èñëà ïðåöåäåíòîâ. Ýòîé ïðîáëåìå è ïîñâÿùåíà íàñòîÿùàÿ ðàáîòà.
1 Îñíîâíûå ïîíÿòèÿ è îïðåäåëåíèÿ
Ïîä ïðîñòðàíñòâîì îáðàçîâ X áóäåì ïîíèìàòü ïðîèçâîëüíûé íåïóñòîé êîìïàêò1 .
Ýëåìåíòû X íàçûâàþòñÿ îáðàçàìè. Ìíîæåñòâî X ïîëàãàåòñÿ ðàçáèòûì íà êîíå÷íîå ÷èñëî
s > 2 ïîïàðíî íåïåðåñåêàþùèõñÿ îáëàñòåé {Xt }, t = 1, s , íàçûâàåìûõ êëàññàìè.
Ñóùåñòâåííûì ÿâëÿåòñÿ òî, ÷òî èíôîðìàöèÿ î ðàçáèåíèè X íà êëàññû
îãðàíè÷èâàåòñÿ çíàíèåì î ïðèíàäëåæíîñòè ê òîìó èëè èíîìó êëàññó êîíå÷íîãî
÷èñëà x1 , x2 , . . . , xm , xm+1 , . . . , xm+l ýëåìåíòîâ X . Òàêèå îáðàçû ñ èçâåñòíîé
êëàññèôèêàöèåé íàçûâàþò ïðåöåäåíòàìè. Ìû ðàçáèâàåì ñïèñîê ïðåöåäåíòîâ íà äâå
ïîäïîñëåäîâàòåëüíîñòè: íà÷àëüíóþ x1 , x2 , . . . , xm è çàêëþ÷èòåëüíóþ xm+1 , . . . , xm+l , è
ñ÷èòàåì ïðè ýòîì, ÷òî ïîñëåäíÿÿ èñïîëüçóåòñÿ äëÿ ïîñòðîåíèÿ àëãîðèòìà êëàññèôèêàöèè,
à ïåðâàÿ äëÿ îöåíêè êà÷åñòâà ïîñòðîåííîãî àëãîðèòìà. Ýòè ïîäïîñëåäîâàòåëüíîñòè
îáðàçóþò îáó÷àþùóþ è ýêçàìåíàöèîííóþ âûáîðêè. Ïîëàãàåì, ÷òî âñå ýëåìåíòû âíóòðè
êàæäîé âûáîðêè ðàçëè÷íû. Áóäåì îáîçíà÷àòü L = m + l.
Çäåñü ñëåäóåò ñäåëàòü âàæíîå çàìå÷àíèå2 . Äàëåå ìû ñ÷èòàåì, ÷òî óêàçàííûå âûáîðêè
íå èìåþò îáùèõ ýëåìåíòîâ. Ýòî òðåáîâàíèå (ïðè óñëîâèè âûïîëíåíèÿ ñôîðìóëèðîâàííîé
íèæå ãèïîòåçû ïðåäñòàâèòåëüíîñòè) ãàðàíòèðóåò êîððåêòíîñòü ïðèìåíåíèÿ ðåçóëüòàòîâ
êëàññèôèêàöèè íà ýêçàìåíàöèîííîé ïîñëåäîâàòåëüíîñòè ê çàäà÷å îöåíêè êà÷åñòâà
îáó÷åíèÿ.
Îáîçíà÷èâ ÷åðåç Y ìíîæåñòâî ñèìâîëîâ êëàññîâ {K1 , . . . , Ks } ìîæíî ñêàçàòü, ÷òî
ñóùåñòâóåò ôóíêöèÿ f ∗ : X → Y , î êîòîðîé èçâåñòåí ëèøü íàáîð åå çíà÷åíèé
1 Îáû÷íî òàêæå ñ÷èòàþò, ÷òî X åñòü ïîäìíîæåñòâî ïðÿìîãî ïðîèçâåäåíèÿ êîíå÷íîãî ÷èñëà n
ìåòðè÷åñêèõ ïðîñòðàíñòâ, ñîîòâåòñòâóþùèõ ïðèçíàêàì, è íàçûâàþò åãî ïðèçíàêîâûì ïðîñòðàíñòâîì.
Îäíàêî ýòî ïðåäïîëîæåíèå, ñóùåñòâåííîå ïðè ïîñòðîåíèè êëàññèôèêàòîðîâ, íå áóäåò èñïîëüçîâàòüñÿ íàìè
ïðè îöåíêå íàäåæíîñòè ïîñòðîåííûõ ðåøàþùèõ ïðàâèë.
2 íà íåãî óêàçàë àâòîðó Ê.Â. Âîðîíöîâ
