Оценки надежности работы классификаторов на основании функции неподобия
Запропоновано підходи до обчислення верхніх оцінок вірогідності розпізнавання, що сприяють їх використанню для більш широкого класу моделей. Одна з оцінок стосується визначення стійкості покриття об’єктів класифікуючими алгоритмами на підставі розподілу відстаней між об’єктами, а інша — змінного кон...
Збережено в:
| Дата: | 2012 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/84132 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Оценки надежности работы классификаторов на основании функции неподобия / Б.П. Русын, В.А. Таянов, А.А. Луцык // Кибернетика и системный анализ. — 2012. — Т. 48, № 4. — С. 132-141. — Бібліогр.: 15 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-84132 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-841322015-07-04T03:01:41Z Оценки надежности работы классификаторов на основании функции неподобия Русын, Б.П. Таянов, В.А. Луцык, А.А. Системный анализ Запропоновано підходи до обчислення верхніх оцінок вірогідності розпізнавання, що сприяють їх використанню для більш широкого класу моделей. Одна з оцінок стосується визначення стійкості покриття об’єктів класифікуючими алгоритмами на підставі розподілу відстаней між об’єктами, а інша — змінного контролю з виключенням по одному, що дає можливість значно простіше і швидше будувати оцінки. The approaches to calculating the upper-bound estimates of the recognition probability are proposed. This allows using them for a more general class of models. One of the estimates determines the stability of the object coverage by classification algorithms based on the distribution of the distances between objects. The second estimate is concerned with leave-one-out cross-validation. This makes the estimation much faster and easier. 2012 Article Оценки надежности работы классификаторов на основании функции неподобия / Б.П. Русын, В.А. Таянов, А.А. Луцык // Кибернетика и системный анализ. — 2012. — Т. 48, № 4. — С. 132-141. — Бібліогр.: 15 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/84132 004.93+519.2 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Системный анализ Системный анализ |
| spellingShingle |
Системный анализ Системный анализ Русын, Б.П. Таянов, В.А. Луцык, А.А. Оценки надежности работы классификаторов на основании функции неподобия Кибернетика и системный анализ |
| description |
Запропоновано підходи до обчислення верхніх оцінок вірогідності розпізнавання, що сприяють їх використанню для більш широкого класу моделей. Одна з оцінок стосується визначення стійкості покриття об’єктів класифікуючими алгоритмами на підставі розподілу відстаней між об’єктами, а інша — змінного контролю з виключенням по одному, що дає можливість значно простіше і швидше будувати оцінки. |
| format |
Article |
| author |
Русын, Б.П. Таянов, В.А. Луцык, А.А. |
| author_facet |
Русын, Б.П. Таянов, В.А. Луцык, А.А. |
| author_sort |
Русын, Б.П. |
| title |
Оценки надежности работы классификаторов на основании функции неподобия |
| title_short |
Оценки надежности работы классификаторов на основании функции неподобия |
| title_full |
Оценки надежности работы классификаторов на основании функции неподобия |
| title_fullStr |
Оценки надежности работы классификаторов на основании функции неподобия |
| title_full_unstemmed |
Оценки надежности работы классификаторов на основании функции неподобия |
| title_sort |
оценки надежности работы классификаторов на основании функции неподобия |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2012 |
| topic_facet |
Системный анализ |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/84132 |
| citation_txt |
Оценки надежности работы классификаторов на основании функции неподобия / Б.П. Русын, В.А. Таянов, А.А. Луцык // Кибернетика и системный анализ. — 2012. — Т. 48, № 4. — С. 132-141. — Бібліогр.: 15 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT rusynbp ocenkinadežnostirabotyklassifikatorovnaosnovaniifunkciinepodobiâ AT taânovva ocenkinadežnostirabotyklassifikatorovnaosnovaniifunkciinepodobiâ AT lucykaa ocenkinadežnostirabotyklassifikatorovnaosnovaniifunkciinepodobiâ |
| first_indexed |
2025-07-06T11:05:11Z |
| last_indexed |
2025-07-06T11:05:11Z |
| _version_ |
1836895344193961984 |
| fulltext |
ÓÄÊ 004.93+519.2
Á.Ï. ÐÓÑÛÍ, Â.À. ÒÀßÍÎÂ, À.À. ËÓÖÛÊ
ÎÖÅÍÊÈ ÍÀÄÅÆÍÎÑÒÈ ÐÀÁÎÒÛ ÊËÀÑÑÈÔÈÊÀÒÎÐÎÂ
ÍÀ ÎÑÍÎÂÀÍÈÈ ÔÓÍÊÖÈÈ ÍÅÏÎÄÎÁÈß
Êëþ÷åâûå ñëîâà: âåðõíÿÿ îöåíêà âåðîÿòíîñòè ðàñïîçíàâàíèÿ, ñêîëüçÿùèé êîíò-
ðîëü, óñòîé÷èâîñòü ïîêðûòèÿ îáúåêòîâ êëàññèôèöèðóþùèìè àëãîðèòìàìè, ðàñ-
ïðåäåëåíèå ðàññòîÿíèé, ïðàâàÿ (ëåâàÿ) àñèììåòðèÿ, ìåòðèêà, êëàññ îáúåêòîâ.
ÂÂÅÄÅÍÈÅ
 íàñòîÿùåå âðåìÿ îöåíêè âåðîÿòíîñòè ïðàâèëüíîãî ðàñïîçíàâàíèÿ áàçèðóþò-
ñÿ íà àëãîðèòìàõ ñêîëüçÿùåãî êîíòðîëÿ (cross validation) [1]. Îäíàêî òàêèå àë-
ãîðèòìû (èñêëþ÷åíèå ïî îäíîìó è äðóãèå) òðóäîåìêèå ñ òî÷êè çðåíèÿ âû÷èñ-
ëåíèé è êîìáèíàòîðíûõ ïåðåãðóïïèðîâîê âûáîðêè. Ïîýòîìó íåîáõîäèìî ðàç-
ðàáîòàòü ïîäõîäû ê ïîñòðîåíèþ âåðõíèõ îöåíîê íàèáîëüøåãî çíà÷åíèÿ
ñðåäíåé âåðîÿòíîñòè ïðàâèëüíîãî ðàñïîçíàâàíèÿ äëÿ çíà÷èòåëüíî ìåíüøåãî
÷èñëà êîìáèíàòîðíûõ ïåðåãðóïïèðîâîê. Ýòî âîçìîæíî, ïîñêîëüêó îáó÷àþùèå
äàííûå ïðàêòè÷åñêè âñåãäà ñîäåðæàò èçáûòîê èíôîðìàöèè, ÷òî ïðîÿâëÿåòñÿ
â åå ÷àñòè÷íîì äóáëèðîâàíèè. Ñ òî÷êè çðåíèÿ ïåðåîáó÷åíèÿ, ïîñòðîåíèå âåðõ-
íèõ îöåíîê îçíà÷àåò, ÷òî ïåðåä àëãîðèòìîì êëàññèôèêàöèè ïîñòàâëåíî íàèáî-
ëåå ñëîæíóþ çàäà÷ó (ðàññìàòðèâàåòñÿ âûáîðêà, íà êîòîðîé äàííûé àëãîðèòì
áóäåò îøèáàòüñÿ ÷àùå, ÷åì íà îñòàëüíûõ âûáîðêàõ èç ãåíåðàëüíîé ñîâîêóï-
íîñòè), âêëþ÷àþùóþ â ñåáÿ ïðîèçâîëüíûå áîëåå ïðîñòûå ïîäâûáîðêè [1, 2],
ò.å. îöåíêè íàèáîëüøåãî çíà÷åíèÿ ñðåäíåé âåðîÿòíîñòè ïðàâèëüíîãî ðàñïîçíàâà-
íèÿ ìîäåëèðóþò êëàññèôèêàöèþ íàèáîëåå ñëîæíûõ ïîäâûáîðîê îáó÷àþùåé
âûáîðêè. ×åì ìåíüøå âåðîÿòíîñòü ïîïàäàíèÿ â êîíòðîëüíóþ âûáîðêó áîëåå
ñëîæíûõ ïîäâûáîðîê ïî ñðàâíåíèþ ñ òåìè, êîòîðûå âõîäèëè â îáó÷àþùóþ âû-
áîðêó, òåì íàäåæíåå áóäåò îöåíêà. Âìåñòå ñ òåì ïðè ïîñòðîåíèè îöåíîê äëÿ
ìàêñèìàëüíîãî çíà÷åíèÿ ñðåäíåé âåðîÿòíîñòè ïðàâèëüíîãî ðàñïîçíàâàíèÿ âñåé
âûáîðêè, ñîâîêóïíîñòè ïîäâûáîðîê, à òàêæå ãðóïïû àëãîðèòìîâ îöåíèâàåòñÿ
íàèáîëüøàÿ âåðîÿòíîñòü óñòîé÷èâîãî ïîêðûòèÿ êàæäîãî îáúåêòà â îòäåëüíîñ-
òè. Ïîä âåðîÿòíîñòüþ óñòîé÷èâîãî ïîêðûòèÿ êàæäîãî îáúåêòà â îòäåëüíîñòè
ïîíèìàåòñÿ âåðîÿòíîñòü åãî ïðàâèëüíîé êëàññèôèêàöèè ïðè èñïîëüçîâàíèè â
ðÿäå ïîäâûáîðîê èç ãåíåðàëüíîé ñîâîêóïíîñòè îáúåêòîâ. Â êàæäîì èç ýòèõ
ñëó÷àåâ âåðîÿòíîñòü âû÷èñëÿåòñÿ êàê ñðåäíåâçâåøåííîå çíà÷åíèå âåðîÿòíîñòåé
ïî îáúåêòàì ñ ó÷åòîì âåðîÿòíîñòè èõ ïîÿâëåíèÿ, à òàêæå èõ âàæíîñòè ëèáî
ïî àëãîðèòìàì (â àëãîðèòìàõ ãîëîñîâàíèÿ âåñà ïðèñâàèâàþòñÿ àëãîðèòìàì
â çàâèñèìîñòè îò íàäåæíîñòè èõ ýêñïåðòèçû [3]), ëèáî ïî îáîèì ôàêòîðàì.
Òàêèì îáðàçîì, ïîëó÷àåòñÿ áîëåå òî÷íàÿ ïîëíàÿ îöåíêà ñâåðõó äëÿ ñðåäíåé
âåðîÿòíîñòè ïðàâèëüíîãî ðàñïîçíàâàíèÿ.
 òåîðèè ðàñïîçíàâàíèÿ îáðàçîâ òàêæå ïðèíÿòî îöåíèâàòü ñëîæíîñòü äàííûõ
èìåííî ñ òî÷êè çðåíèÿ èõ êëàññèôèêàöèè.  ýòîì ñëó÷àå ñëîæíîñòü äàííûõ îöå-
íèâàåòñÿ íà îñíîâàíèè áëèçîñòè êëàññîâ, ê êîòîðûì ýòè äàííûå ïðèíàäëåæàò,
ôîðìû ãèïåðïîâåðõíîñòè èõ ïåðåñå÷åíèÿ, à òàêæå ôîðì èõ ñîáñòâåííûõ ïîâåð-
õíîñòåé, êîëè÷åñòâà äàííûõ êëàññîâ, íàõîäÿùèõñÿ äîñòàòî÷íî áëèçêî ê ðàçäåëÿþ-
ùåé ãèïåðïîâåðõíîñòè, è òåõ, êîòîðûå íàõîäÿòñÿ ïî äðóãóþ ñòîðîíó ðàçäåëÿþùåé
ãèïåðïîâåðõíîñòè, ò.å. èìåþò îòðèöàòåëüíûé îòñòóï [4].
132 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
© Á.Ï. Ðóñûí, Â.À. Òàÿíîâ, À.À. Ëóöûê, 2012
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È
 íàñòîÿùåé ðàáîòå ñòàâèòñÿ îáùàÿ ïðîáëåìà ïîñòðîåíèÿ îöåíîê âåðîÿòíîñòè
ïðàâèëüíîé êëàññèôèêàöèè îáúåêòîâ âûáîðîê, êîòîðàÿ õàðàêòåðèçóåò íàäåæ-
íîñòü êëàññèôèêàöèè. Âíà÷àëå ðàññìàòðèâàåòñÿ çàäà÷à ïîñòðîåíèÿ îöåíîê âå-
ðîÿòíîñòè ïðàâèëüíîé êëàññèôèêàöèè êàæäîãî îáúåêòà â îòäåëüíîñòè. Äàííàÿ
âåðîÿòíîñòü îöåíèâàåòñÿ ïðè óñëîâèè, ÷òî èçâåñòíà ïðèíàäëåæíîñòü êàæäîãî
ðàññìàòðèâàåìîãî îáúåêòà ê òîìó ëèáî èíîìó êëàññó, ò.å. ðàññìàòðèâàåòñÿ îáó-
÷àþùàÿ âûáîðêà. Ýòà âåðîÿòíîñòü ìîæåò áûòü îöåíåíà íà îñíîâàíèè ðàñïðåäå-
ëåíèÿ îòñòóïîâ äëÿ ñîîòâåòñòâóþùèõ ìîäåëåé ëèáî ðàñïðåäåëåíèåì ðàññòîÿíèé
ìåæäó îáúåêòàìè, â îáùåì ñëó÷àå ýòî îäíî è òî æå. Ïîäðîáíî äàííûå âîïðîñû
ðàññìàòðèâàþòñÿ íèæå. Ñðåäíÿÿ âåðîÿòíîñòü ïðàâèëüíîé êëàññèôèêàöèè âñåé
âûáîðêè îïðåäåëÿåòñÿ êàê ìàòåìàòè÷åñêîå îæèäàíèå îò óæå èçâåñòíûõ âåðîÿò-
íîñòåé ïðàâèëüíîé êëàññèôèêàöèè êàæäîãî îáúåêòà â îòäåëüíîñòè. Ïðè ýòîì
íå îáÿçàòåëüíî çíàòü àïðèîðíûå âåðîÿòíîñòè, êîòîðûå çà÷àñòóþ íåèçâåñòíû.
Äàëåå, îñíîâûâàÿñü íà ïîëóêîëüöå èç îïåðàöèé ( , )min � [5], ìîæíî ïîêàçàòü,
÷òî ñðåäíåå îò âåðõíèõ îöåíîê ïðàâèëüíîé êëàññèôèêàöèè êàæäîãî îáúåêòà â
îòäåëüíîñòè áóäåò âåðõíåé îöåíêîé ñðåäíåé âåðîÿòíîñòè ïðàâèëüíîé êëàññè-
ôèêàöèè âñåõ îáúåêòîâ àíàëèçèðóåìîé âûáîðêè.
Çàòåì ðàññìàòðèâàåòñÿ çàäà÷à âû÷èñëåíèÿ îöåíêè ïðàâèëüíîé êëàññèôèêàöèè
â óñëîâèÿõ ñêîëüçÿùåãî êîíòðîëÿ. Â [1] àíàëèçèðóåòñÿ ïîëíûé ñêîëüçÿùèé êîí-
òðîëü. Îäíàêî ïðîâîäèòü åãî â óñëîâèÿõ áîëüøèõ âûáîðîê î÷åíü òðóäîåìêàÿ çàäà-
÷à ñ òî÷êè çðåíèÿ âû÷èñëåíèé. Ïîëíûé ñêîëüçÿùèé êîíòðîëü âêëþ÷àåò â ñåáÿ
ìíîãîêðàòíóþ ïåðåãðóïïèðîâêó âûáîðêè ìåòîäàìè ñêîëüçÿùåãî êîíòðîëÿ ñ âîç-
âðàòîì ïî îäíîìó, ñ âîçâðàòîì ïî k , îöåíèâàíèåì ïî áëîêàì ðàçìåðíîñòüþ q,
à òàêæå èõ ïåðåãðóïïèðîâêîé [4].  ñâÿçè ñ ýòèì öåëü çàäà÷è — ðàçðàáîòàòü ìåòîä
ïîñòðîåíèÿ âåðõíèõ îöåíîê äëÿ îöåíêè ïîëíîãî ñêîëüçÿùåãî êîíòðîëÿ, èñïîëüçóÿ
ñêîëüçÿùèé êîíòðîëü ñ íåáîëüøèì ÷èñëîì ïåðåãðóïïèðîâîê âûáîðêè.  îáùåì
ñëó÷àå èäåÿ, çàëîæåííàÿ â îñíîâó ïðåäëàãàåìîãî ïîäõîäà, ïðåäñòàâëÿåò ñîáîé
îöåíêó çàâèñèìîñòè f x x( , )2 3 , åñëè çàäàíû çàâèñèìîñòè f x x( , )1 2 è f x x( , )1 3 .
Êàê ïðàâèëî, ðåøèòü ýòó çàäà÷ó íå ïðåäñòàâëÿåòñÿ âîçìîæíûì, ïîýòîìó çäåñü
îïèñàíû ðåøåíèÿ ëèøü äëÿ ÷àñòíûõ ñëó÷àåâ. Ïîñêîëüêó â äàííîé ðàáîòå ðàñ-
ñìàòðèâàþòñÿ ìåòðè÷åñêèå êëàññèôèêàòîðû, ïðåäëîæåí âàðèàíò ðåøåíèÿ çàäà÷è
ñ ïîìîùüþ íåðàâåíñòâà òðåóãîëüíèêà, ÷òî â îáùåì ñëó÷àå ïðåäñòàâëÿåò ñîáîé
íåðàâåíñòâî Êîøè–Øâàðöà [6].
ÂÀÆÍÛÅ ÇÀÄÀ×È ÒÅÎÐÈÈ ÌÀØÈÍÍÎÃÎ ÎÁÓ×ÅÍÈß
 ñîâðåìåííîé òåîðèè ìàøèííîãî îáó÷åíèÿ ñóùåñòâóåò äâå ñåðüåçíûå ïðîáëåìû:
ïîëó÷åíèå òî÷íûõ âåðõíèõ îöåíîê âåðîÿòíîñòè íåæåëàòåëüíîãî ïåðåîáó÷åíèÿ è
ñïîñîáîâ åãî óñòðàíåíèÿ. Ïîä ïåðåîáó÷åíèåì àëãîðèòìà ðàñïîçíàâàíèÿ ïîäðàçó-
ìåâàåòñÿ ðàçíîñòü ìåæäó âåðîÿòíîñòÿìè ïðàâèëüíîãî ðàñïîçíàâàíèÿ ïðè êîíòðîëå
è îáó÷åíèè. Îöåíèâàåòñÿ âåðîÿòíîñòü òîãî, ÷òî ïåðåîáó÷åíèå íå ïðåâûñèò çàäàí-
íûé âåðîÿòíîñòíûé ïîðîã �. Íà äàííûé ìîìåíò íàèáîëåå òî÷íûå îöåíêè ñèëü-
íî çàâûøåíû. Ýêñïåðèìåíòàëüíî óäàëîñü óñòàíîâèòü ïðè÷èíû ýòîãî.  ïîðÿäêå
óìåíüøåíèÿ âëèÿíèÿ íàèáîëåå ñóùåñòâåííûìè èç íèõ ÿâëÿþòñÿ ñëåäóþùèå [1].
� Ïðåíåáðåæåíèå ýôôåêòîì ðàññëîåíèÿ èëè ëîêàëèçàöèè ñåìåéñòâà àë-
ãîðèòìîâ. Äàííàÿ ïðîáëåìà îáóñëàâëèâàåòñÿ òåì, ÷òî ðåàëüíî ðàáîòàåò íå âñå
ìíîæåñòâî àëãîðèòìîâ, à òîëüêî îïðåäåëåííàÿ åãî ÷àñòü, çàâèñÿùàÿ îò çàäà÷è.
Êîýôôèöèåíò çàâûøåííîñòè — îò íåñêîëüêèõ äåñÿòêîâ äî ñîòåí òûñÿ÷.
� Ïðåíåáðåæåíèå ñõîäñòâîì àëãîðèòìîâ. Êîýôôèöèåíò çàâûøåííîñòè —
îò íåñêîëüêèõ ñîòåí äî äåñÿòêîâ òûñÿ÷ ðàç. Ýòîò ôàêòîð âñåãäà ñóùåñòâåíåí è
ìåíüøå çàâèñèò îò çàäà÷è, ÷åì ïåðâûé.
� Ýêñïîíåíöèàëüíàÿ àïïðîêñèìàöèÿ «õâîñòà» ãèïåðãåîìåòðè÷åñêîãî ðàñ-
ïðåäåëåíèÿ. Êîýôôèöèåíò çàâûøåííîñòè ìîæåò ñîñòàâëÿòü íåñêîëüêî äåñÿòêîâ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 133
� Ïðåäñòàâëåíèå âåðõíåé îöåíêè ïðîôèëÿ ðàçíîîáðàçèÿ îäíèì ñêàëÿð-
íûì êîýôôèöèåíòîì ðàçíîîáðàçèÿ. Êîýôôèöèåíò çàâûøåííîñòè ÷àñòî ïîðÿä-
êà åäèíèöû, îäíàêî â íåêîòîðûõ ñëó÷àÿõ ìîæåò äîñòèãàòü íåñêîëüêèõ äåñÿòêîâ.
Ýôôåêò ïåðåîáó÷åíèÿ ñîñòîèò â òîì, ÷òî èñïîëüçóåòñÿ àëãîðèòì ñ ìèíè-
ìàëüíûì ÷èñëîì îøèáîê íà îáó÷àþùåé âûáîðêå, ò.å. ïðîâîäèòñÿ îäíîñòîðîííÿÿ
íàñòðîéêà àëãîðèòìîâ. Ïåðåîáó÷åíèå òåì áîëüøå, ÷åì áîëüøàÿ êîìïîçèöèÿ àë-
ãîðèòìîâ èñïîëüçóåòñÿ. Ýòî ñïðàâåäëèâî äëÿ àëãîðèòìîâ, âçÿòûõ èç ðàñïðåäåëå-
íèÿ ñëó÷àéíî è íåçàâèñèìî.  ñëó÷àå çàâèñèìîñòè àëãîðèòìîâ (â ðåàëüíîé ñèòóà-
öèè îíè, êàê ïðàâèëî, òàêèìè è ÿâëÿþòñÿ) äîïóñêàåòñÿ óìåíüøåíèå ïåðåîáó÷å-
íèÿ. Îíî ìîæåò âîçíèêíóòü äàæå ïðè âûáîðå âñåãî îäíîãî èç äâóõ àëãîðèòìîâ.
Ðàññëîåíèå àëãîðèòìîâ ïî ÷èñëó îøèáîê è óâåëè÷åíèå èõ ïîäîáèÿ óìåíüøàþò
âåðîÿòíîñòü ïåðåîáó÷åíèÿ.
Ðàññìîòðèì äóïëåò âûáîðêà–àëãîðèòì. Êàæäûé àëãîðèòì ïîêðûâàåò îïðå-
äåëåííîå ÷èñëî îáúåêòîâ îáó÷àþùåé âûáîðêè. Åñëè èñïîëüçîâàòü âíóòðåííèå
êðèòåðèè [7] (íàïðèìåð, â ñëó÷àå ìåòðè÷åñêèõ êëàññèôèêàòîðîâ), òî ìîæíî îöå-
íèòü óñòîé÷èâîñòü ýòîãî ïîêðûòèÿ è ñóçèòü ÷èñëî ïîêðûòûõ îáúåêòîâ ñîãëàñíî
çàäàííîìó óðîâíþ óñòîé÷èâîñòè. Òàêèì îáðàçîì, äëÿ òîãî ÷òîáû ïîêðûòü áîëü-
øåå ÷èñëî îáúåêòîâ, íåîáõîäèìî ïðèìåíèòü áîëüøåå ÷èñëî àëãîðèòìîâ. Ýòè àë-
ãîðèòìû äîëæíû áûòü ïîõîæèìè è èìåòü ðàçíûé óðîâåíü îøèáîê. Ýòî íàèëó÷-
øèå ñîâðåìåííûå ñòðàòåãèè ïîñòðîåíèÿ êîìïîçèöèè àëãîðèòìîâ [1]. Îäíàêî ïðè
èñïîëüçîâàíèè òåñòîâûõ äàííûõ, ê êîòîðûì êîìïîçèöèÿ àëãîðèòìîâ íåàäàïòè-
ðîâàíà, îøèáêà êëàññèôèêàöèè ìîæåò ñèëüíî îòëè÷àòüñÿ îò ìèíèìàëüíîé, ïîëó-
÷åííîé íà îáó÷àþùèõ äàííûõ.
ÏÎÑÒÐÎÅÍÈÅ ÎÖÅÍÎÊ ÂÅÐÎßÒÍÎÑÒÍÎÉ ÓÑÒÎÉ×ÈÂÎÑÒÈ ÏÎÊÐÛÒÈß ÎÁÚÅÊÒÎÂ
ÀËÃÎÐÈÒÌÀÌÈ ÒÈÏÀ kNN ÄËß ÎÄÈÍÎ×ÍÛÕ ÈÑÏÛÒÀÍÈÉ
Êà÷åñòâî ðàáîòû êëàññèôèêàòîðîâ, ïîñòðîåííûõ íà îñíîâàíèè ðàíãîâîãî ãîëîñî-
âàíèÿ è ñ èñïîëüçîâàíèåì ðàçäåëÿþùèõ ãèïåðïëîñêîñòåé (R-ìîäåëåé [3, c. 13]),
ïðèíÿòî õàðàêòåðèçîâàòü ïîíÿòèåì îòñòóïà (margin), ïðåäñòàâëÿþùåì ðàññòîÿ-
íèå îáúåêòà îò ðàçäåëÿþùåé ãèïåðïëîñêîñòè [4]. ×åì áîëüøèé îòñòóï, òåì
ëó÷øèì ñ÷èòàåòñÿ êëàññèôèêàòîð. Ïîíÿòèå îòñòóïà ïðèìåíèìî ê êëàññèôèêà-
òîðàì, ïîñòðîåííûì ñ ïîìîùüþ R-ìîäåëåé, à òàêæå íà îñíîâàíèè ôóíêöèè
ïîäîáèÿ. Ê ïîñëåäíèì îòíîñÿòñÿ âñå ìåòðè÷åñêèå êëàññèôèêàòîðû. Îäíàêî
åñëè âñå îáúåêòû èëè ïîäàâëÿþùåå èõ áîëüøèíñòâî èìåþò ïðèáëèçèòåëüíî
îäèíàêîâûé îòñòóï è ãðóïïèðóþòñÿ îäèí âîçëå äðóãîãî, òî â ýòîì ñëó÷àå ðåç-
êî ïàäàåò èõ èíôîðìàòèâíîñòü. Ýòî çíà÷èò, ÷òî âìåñòî âñåõ îáúåêòîâ ìîæíî
îñòàâèòü îäèí èëè íåñêîëüêî, èñïîëüçóåìûõ äëÿ îáó÷åíèÿ. Òàêîé ïîäõîä ïî-
ðîæäàåò îäíó èç ãëàâíûõ ïðè÷èí, îáóñëàâëèâàþùèõ ïåðåîáó÷åíèå. Îäíîñòî-
ðîííÿÿ íàñòðîéêà àëãîðèòìà íà îñíîâàíèè áëèçêîé ïî ñóùíîñòè îáó÷àþùåé
èíôîðìàöèè ïðèâîäèò ê òîìó, ÷òî íà êîíòðîëüíîé âûáîðêå îí ìîæåò ÷àñòî
îøèáàòüñÿ, äàæå åñëè íå îøèáàëñÿ íà îáó÷àþùåé âûáîðêå. Äåéñòâèòåëüíî,
âåðîÿòíîñòü òîãî, ÷òî â óñëîâèÿõ îáó÷àþùåé âûáîðêè âîçìîæíà òàêàÿ æå ñè-
òóàöèÿ, áëèçêà ê íóëþ.
Ïîýòîìó äëÿ îáó÷åíèÿ ïðèíÿòî èñïîëüçîâàòü íåïîõîæèå è «òðóäíûå» äëÿ
àëãîðèòìà îáúåêòû ñ ìàëûìè çíà÷åíèÿìè îòñòóïà. Ýòà èäåÿ ïðèìåíÿåòñÿ, â ÷àñò-
íîñòè, â ìåòîäå îïîðíûõ âåêòîðîâ (Support Vector Machine) èëè ìåòîäå âçâåøåí-
íîãî ãîëîñîâàíèÿ [3]. Èñïîëüçóåì îáîáùåííûé ïîäõîä äëÿ õàðàêòåðèñòèêè êëàñ-
ñèôèêàòîðîâ íà îñíîâàíèè ïîíÿòèÿ îòñòóïà. Ðåçóëüòàòîì ðàáîòû ìåòðè÷åñêèõ
êëàññèôèêàòîðîâ ÿâëÿþòñÿ ðàíæèðîâàííûå äàííûå (îáúåêòû áàçû äàííûõ, ñîð-
òèðîâàííûå ïî ñòåïåíè ïîäîáèÿ òåñòîâîìó îáúåêòó ). Äëÿ òàêèõ êëàññèôèêàòî-
ðîâ ïîíÿòèå îòñòóïà ïðåäñòàâëÿåòñÿ ñëåäóþùèì îáðàçîì. Ââîäèòñÿ ýêâèâàëåíò-
íàÿ êëàññè÷åñêîìó îòñòóïó õàðàêòåðèñòèêà, êîòîðàÿ ìîæåò áûòü ïðåäñòàâëåíà
êàê íîðìèðîâàííîå ðàññòîÿíèå îò òåñòîâîãî îáúåêòà äî óñðåäíåííîãî îáúåêòà
134 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
áàçû äàííûõ èëè ïîñëåäíåãî îáúåêòà èç îäíîðîäíîé (ñòðàòåãè÷åñêîé) [8] ïîñëå-
äîâàòåëüíîñòè «ñâîèõ» îáúåêòîâ. Äîïóñêàåòñÿ, ÷òî õîòÿ áû ÷àñòü «ñâîèõ» îáúåê-
òîâ ðàçìåùàåòñÿ â íà÷àëå ñïèñêà âîçìîæíûõ ïðåòåíäåíòîâ. Òàêèì îáðàçîì, ãà-
ðàíòèðóåòñÿ êîððåêòíîñòü äîïóùåíèÿ.
Äëÿ áîëåå ñòðîãîãî îïðåäåëåíèÿ äàííîé õàðàêòåðèñòèêè íåîáõîäèìî ââåñòè
ïîíÿòèå ðàñïðåäåëåíèÿ ðàññòîÿíèé ìåæäó îáúåêòàìè. Èçâåñòíî, ÷òî ïðîöåññ ñ íå-
çàâèñèìûìè ïðèðàùåíèÿìè [9] èìååò íîðìàëüíîå ðàñïðåäåëåíèå ñ íóëåâûì ñðåä-
íèì è ëèíåéíî èçìåíÿþùåéñÿ äèñïåðñèåé. Êàæäîå ñëåäóþùåå ïðèðàùåíèå áóäåò
èìåòü áîëüøóþ äèñïåðñèþ, ÷åì ïðåäûäóùåå. Ñîâîêóïíîñòü ðàññòîÿíèé â ïðèçíà-
êîâîì ïðîñòðàíñòâå îò ïðîèçâîëüíîãî îáúåêòà äî âñåõ îñòàëüíûõ ÿâëÿåòñÿ àíàëî-
ãîì ïðîöåññà ñ íåçàâèñèìûìè ïðèðàùåíèÿìè, åñëè ðàññìàòðèâàòü ïîïàðíûå ðàñ-
ñòîÿíèÿ ìåæäó îáúåêòàìè âûáîðêè, äèñïåðñèÿ êîòîðîãî îãðàíè÷èâàåòñÿ çàìêíó-
òîñòüþ ïðèçíàêîâîãî ïðîñòðàíñòâà. Ðàñïðåäåëåíèå ðàññòîÿíèé ñóùåñòâóåò,
ïîñêîëüêó ñóùåñòâóåò ðàñïðåäåëåíèå íåçàâèñèìûõ ïðèðàùåíèé [9]. Ïîñêîëüêó
ïðîèçâîëüíîå ðàññòîÿíèå — ýòî âñåãäà ïîëîæèòåëüíàÿ âåëè÷èíà, òî åå ìàòåìàòè-
÷åñêîå îæèäàíèå áîëüøå íóëÿ, åñëè îíî íå ðàâíî íóëþ.
×òîáû ïåðåéòè ê íîðìàëüíîìó ðàñïðåäåëåíèþ ñ íóëåâûì ìàòåìàòè÷åñêèì
îæèäàíèåì, íåîáõîäèìî ñäåëàòü ñäâèã âëåâî âñåãî ðàñïðåäåëåíèÿ íà âåëè÷èíó,
ðàâíóþ ìàòåìàòè÷åñêîìó îæèäàíèþ. Çàêîí ðàñïðåäåëåíèÿ ñîâîêóïíîñòè ðàññòî-
ÿíèé îïðåäåëÿåòñÿ ñîãëàñíî öåíòðàëüíîé ïðåäåëüíîé òåîðåìå, èç êîòîðîé
ñëåäóåò, ÷òî ñóììà ïðîèçâîëüíûõ ñëó÷àéíûõ âåëè÷èí áóäåò èìåòü àñèìïòîòè-
÷åñêè íîðìàëüíîå ðàñïðåäåëåíèå [10]. Ìàòåìàòè÷åñêîå îæèäàíèå è äèñïåðñèþ
ïëîòíîñòè ðàñïðåäåëåíèÿ âåðîÿòíîñòåé ìîæíî îöåíèòü, íàïðèìåð, ìåòîäîì
ìàêñèìàëüíîãî ïðàâäîïîäîáèÿ [11].
Ïîñêîëüêó çíà÷åíèÿ ðàññòîÿíèé ìîãóò áûòü ïðîèçâîëüíûìè ïî ìîäóëþ, òî
ïðîöåäóðà íåïàðàìåòðè÷åñêîãî îöåíèâàíèÿ ôîðìû çàêîíà ðàñïðåäåëåíèÿ íåóñå-
÷åííûìè ÿäåðíûìè ôóíêöèÿìè áóäåò êîððåêòíîé.
Ïóñòü íåïàðàìåòðè÷åñêè îöåíåíà ïëîòíîñòü ðàñïðåäåëåíèÿ ðàññòîÿíèé ìåæ-
äó îáúåêòàìè, çàäàííûìè âåêòîðàìè x è y : ( )p x , x d� ( , )x y . Ñîãëàñíî íåðàâåí-
ñòâó ×åáûøåâà [12] âåðîÿòíîñòü òîãî, ÷òî íàéäåòñÿ ðàññòîÿíèå, ïðåâûøàþùåå
íåêîòîðîå ïîðîãîâîå çíà÷åíèå ðàññòîÿíèé � , ðàâíà p x dx
x
( )
| |�
� �
�
�
�
2
2
.
Ðàññìîòðèì ñëó÷àé ðàâåíñòâà ìàòåìàòè÷åñêîãî îæèäàíèÿ è ìîäû ðàñïðåäå-
ëåíèÿ p x( ). Âåðõíèé ïðåäåë îäíîìîäàëüíîãî ðàñïðåäåëåíèÿ ñ ìîäîé � � 0 íåðà-
âåíñòâîì Ãàóññà [13] ïðåäñòàâëÿåòñÿ â âèäå
P x(| | ) � �� ��
�
4
9 2
, (1)
ãäå � � � �2 2
0
2
� ( ) .
Ïóñòü � �� �0 0 è � �
. Òîãäà ïîðîã � �� ��� � , à � � �� / . Èòàê, íåðàâåí-
ñòâî Ãàóññà äëÿ ïîðîãà � ìîæåò áûòü ïðåäñòàâëåíî â âèäå
p x dx
x
( )
| |�
� �
�
�
�
4
9
2
2
. (2)
Òàêèì îáðàçîì, ñîãëàñíî íåðàâåíñòâó Ãàóññà äëÿ îäíîìîäàëüíûõ ðàñïðåäåëåíèé
ñ ìîäîé, ðàâíîé ìàòåìàòè÷åñêîìó îæèäàíèþ, îöåíêà â 2,25 ðàçà ëó÷øå òîé, êî-
òîðàÿ ïîëó÷àåòñÿ ñîãëàñíî íåðàâåíñòâó ×åáûøåâà. Ýòî ìàêñèìàëüíî õîðîøàÿ
îöåíêà ïðè óñëîâèè, ÷òî íåèçâåñòåí êîíêðåòíûé âèä ðàñïðåäåëåíèÿ, à èçâåñòíû
ëèøü îïðåäåëåííûå åãî ñâîéñòâà. Ïðè ñèììåòðè÷íîñòè îäíîìîäàëüíîãî ðàñïðå-
äåëåíèÿ ìîäà ðàâíà ìàòåìàòè÷åñêîìó îæèäàíèþ, à â ÷àñòíîì ñëó÷àå íîðìèðî-
âàííîñòè îáà ïàðàìåòðà ðàâíû íóëþ. Îäíàêî â îáùåì ñëó÷àå èíîãäà ðåàëüíûé
çàêîí ðàñïðåäåëåíèÿ íå ÿâëÿåòñÿ ñèììåòðè÷íûì. Ïðè ýòîì âîçìîæíà ëåâàÿ ëèáî
ïðàâàÿ àñèììåòðèÿ ôóíêöèè ïëîòíîñòè ðàñïðåäåëåíèÿ âåðîÿòíîñòåé (ÔÏÐÂ).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 135
ÏÎÑÒÐÎÅÍÈÅ ÎÖÅÍÎÊ ÂÅÐÎßÒÍÎÑÒÈ ÓÑÒÎÉ×ÈÂÎÃÎ ÏÎÊÐÛÒÈß
ÎÁÚÅÊÒÎÂ ÀËÃÎÐÈÒÌÀÌÈ ÒÈÏÀ kNN ÄËß ÎÏÐÅÄÅËÅÍÍÛÕ ÊËÀÑÑÎÂ
ÐÀÑÏÐÅÄÅËÅÍÈÉ ÐÀÑÑÒÎßÍÈÉ ÌÅÆÄÓ ÎÁÚÅÊÒÀÌÈ
Ðàçäåëèì ÔÏРíà äâå ÷àñòè: íàõîäÿùèåñÿ ñïðàâà è ñëåâà îò ìàêñèìóìà.
Åñëè ïëîùàäü ïîä ïðàâîé ÷àñòüþ ÔÏРáîëüøå ëåâîé, òî ñ÷èòàåòñÿ, ÷òî ýòî
ïðàâàÿ àñèììåòðèÿ, à åñëè íàîáîðîò, òî ëåâàÿ (ðèñ. 1, à è á ñîîòâåòñòâåííî).
Ðàññìîòðèì îöåíêè, ïîëó÷åííûå ñ ïîìîùüþ íåðàâåíñòâà Ãàóññà äëÿ îáîèõ
ñëó÷àåâ. Äëÿ ïðàâîé àñèììåòðèè ñäåëàåì ðàñïðåäåëåíèå ñèììåòðè÷íûì îòíî-
ñèòåëüíî ëåâîé ÷àñòè, ò.å. ëåâóþ ÷àñòü îñòàâëÿåì áåç èçìåíåíèé è îòîáðàæàåì
åå ñèììåòðè÷íî âìåñòî èñõîäíîé ïðàâîé ÷àñòè. Ïóñòü íåêîòîðàÿ òî÷êà x0
ïðèíàäëåæèò ëåâîé ÷àñòè ðàñïðåäåëåíèÿ. Òîãäà ôóíêöèÿ ðàñïðåäåëåíèÿ âåðî-
ÿòíîñòåé (ÔÐÂ) P X x( )� 0 äëÿ ñèììåòðè÷íîãî ñëó÷àÿ âñåãäà áîëüøå äëÿ êàæ-
äîé òî÷êè â ëåâîé ÷àñòè ÔÐÂ, íåæåëè â èñõîäíîì ñëó÷àå. Íàñ èíòåðåñóþò
ïåðâûå îáúåêòû â ñïèñêå âîçìîæíûõ ïðåòåíäåíòîâ, ñîîòâåòñòâóþùèå ëåâîé
÷àñòè ðàñïðåäåëåíèÿ. Èìåííî ýòî äàåò îñíîâàíèå äëÿ èñêóññòâåííîé ñèììåò-
ðèçàöèè çàêîíà ðàñïðåäåëåíèÿ, ÿâëÿþùåãîñÿ â îáùåì ñëó÷àå àñèììåòðè÷íûì.
Ïðè ýòîì ÔÐÂ áóäåò âåðõíåé îöåíêîé äëÿ îøèáêè ðàñïîçíàâàíèÿ.
Ïðîàíàëèçèðóåì ïîëó÷åííûé ðåçóëüòàò. Ïðåäâàðèòåëüíî îòìåòèì, ÷òî äëÿ
ëó÷øåãî ïîíèìàíèÿ ïðåäëîæåííîãî ïðèåìà, à òàêæå îáëåã÷åííîé èíòåðïðåòàöèè
ðåçóëüòàòîâ íåò íåîáõîäèìîñòè â íîðìèðîâêå ÔÏРê åäèíè÷íîé ïëîùàäè.
Îòìåòèì, ÷òî îöåíêà äèñïåðñèè ìîæåò áûòü ïðîâåäåíà òîëüêî ïî îäíîé ÷àñòè
ðàñïðåäåëåíèÿ (â äàííîì ñëó÷àå — ëåâîé). Ýòî ñâÿçàíî ñ òåì, ÷òî îáúåêòû ÷àñòè
ðàñïðåäåëåíèÿ, êîòîðûå íå ó÷àñòâóþò â îïðåäåëåíèè îöåíêè äèñïåðñèè, çíà÷è-
òåëüíî óäàëåíû îò çîíû ïðèíÿòèÿ ðåøåíèé (â äàííîì ñëó÷àå — ïåðâûõ îáúåêòîâ
â ñïèñêå âîçìîæíûõ ïðåòåíäåíòîâ) è íå îêàçûâàþò ñóùåñòâåííîãî âëèÿíèÿ íà
ïðèíèìàåìîå ðåøåíèå. Óìåíüøåíèå åäèíè÷íîé ïëîùàäè ñâèäåòåëüñòâóåò î òîì,
÷òî ìû ïîëó÷àåì áîëåå òî÷íóþ îöåíêó, íåæåëè ïî âñåìó ðàñïðåäåëåíèþ. Óâåëè-
÷åíèå ïëîùàäè, íàîáîðîò, ñâèäåòåëüñòâóåò îá óõóäøåíèè îöåíêè.
Îñîáûé èíòåðåñ ïðåäñòàâëÿþò îòêëîíåíèÿ ðàññòîÿíèé âëåâî îò ìàòåìàòè÷åñ-
êîãî îæèäàíèÿ ïðè èñïîëüçîâàíèè k NN êëàññèôèêàòîðîâ ñ íåáîëüøèìè çíà÷åíèÿ-
ìè k. Ïîñêîëüêó îöåíêà äèñïåðñèè ÔÏÐÂ äëÿ ïîñòðîåíèÿ îöåíêè Ãàóññà ïðîâîäè-
ëàñü ïî ëåâîé ÷àñòè ðàñïðåäåëåíèÿ, òî î÷åâèäíî, ÷òî ýòà îöåíêà â ñëó÷àå ñèììåò-
ðè÷íîé ÔÏРìåíüøå èñõîäíîé, ÷òî äåëàåò îöåíêó áîëåå òî÷íîé. Ê òîìó æå
ñèììåòðèÿ ïîçâîëÿåò ñäåëàòü îöåíêó Ãàóññà ìàêñèìàëüíî òî÷íîé ñîãëàñíî íåðàâåí-
ñòâó (2), à âñå âìåñòå ïîçâîëÿåò ñóùåñòâåííî óëó÷øèòü îáùóþ âåðõíþþ îöåíêó.
136 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
Ðèñ. 1
x0 �0 �
x0
p x( ) p x( )
x
x0 � �0
à á
Ðàññìîòðèì ÔÏРâ ñëó÷àå ëåâîé àñèììåòðèè. Òåïåðü äèñïåðñèÿ ñèììåòðè-
çèðîâàííîé ÔÏÐÂ áóäåò áîëüøå èñõîäíîé, à åäèíñòâåííûì ïðåèìóùåñòâîì òàêî-
ãî ïðåîáðàçîâàíèÿ áóäåò ñèììåòðèÿ âíîâü ïîëó÷åííîãî çàêîíà ðàñïðåäåëåíèÿ.
 äàííîì ñëó÷àå òàêæå íåò íåîáõîäèìîñòè â íîðìèðîâêå ÔÏÐÂ. Óâåëè÷åíèå ïëî-
ùàäè ïîä êðèâîé îçíà÷àåò, ÷òî âêëþ÷åíû äîïîëíèòåëüíûå îáúåêòû, êîòîðûå íå
ó÷àñòâóþò â ðàñïîçíàâàíèè. Ýòî óõóäøàåò îöåíêó Ãàóññà, ïîñêîëüêó âîçðîñëî çíà-
÷åíèå îöåíåííîé äèñïåðñèè. Ðåøåíèå î òîì, êàêóþ îöåíêó èñïîëüçîâàòü — ñ ïðå-
îáðàçîâàíèåì ñèììåòðèè èëè ïî èñõîäíîìó ðàñïðåäåëåíèþ, íåîáõîäèìî ïðèíè-
ìàòü, èìåÿ çíà÷åíèÿ ìàòåìàòè÷åñêîãî îæèäàíèÿ, ìîäû è äèñïåðñèè îáåèõ ÔÏÐÂ.
Ïðîàíàëèçèðóåì ñâÿçü îöåíêè Ãàóññà ñî çíà÷åíèÿìè ÔРP X x( )� 0 . Ïðà-
âàÿ ÷àñòü ðàñïðåäåëåíèÿ íå ïðåäñòàâëÿåò èíòåðåñà, ïîýòîìó åñëè âìåñòî îöåíêè
Ãàóññà âçÿòü ÔÐÂ, òî ýòî áóäåò âåðõíåé îöåíêîé ïî îòíîøåíèþ ê èñõîäíîé îöåí-
êå. Ïðè ýòîì íå èìåþò çíà÷åíèÿ íè âèä àñèììåòðèè, íè ñàìà àñèììåòðèÿ
â ÔÏÐÂ. Èòàê, âåðõíÿÿ îöåíêà çíà÷åíèÿìè ÔРïî îòíîøåíèþ ê îöåíêå Ãàóññà
êàñàåòñÿ êàê ñèììåòðè÷íûõ, òàê è àñèììåòðè÷íûõ ÔÏÐÂ. Çàâûøåííîñòü îöåíêè
Ãàóññà ïî îòíîøåíèþ ê çíà÷åíèÿì ÔÐÂ, áåçóñëîâíî, êîìïåíñèðóåòñÿ ëèøü
â ñëó÷àå ïðàâîé àñèììåòðèè.  ñëó÷àå ëåâîé àñèììåòðèè ñòåïåíü êîìïåíñàöèè
çàâèñèò îò ñîîòíîøåíèÿ ìåæäó çíà÷åíèÿìè äèñïåðñèè è ðàçíèöû | |� � 0 .
Åñëè ÔÏРíå èìååò ÷åòêî âûðàæåííîé ñòðóêòóðû (ñóùåñòâîâàíèå ýêñòðå-
ìóìà, ñèììåòðèÿ, ïðàâàÿ àñèììåòðèÿ), òî ìîæíî âîñïîëüçîâàòüñÿ íåïàðàìåòðè-
÷åñêèì îöåíèâàíèåì, â ðåçóëüòàòå êîòîðîãî ïîëó÷àåì íåïðåðûâíóþ ÔÏÐÂ. Ýòó
ôóíêöèþ ìîæíî èíòåãðèðîâàòü è äèôôåðåíöèðîâàòü ïî îïðåäåëåíèþ. Ïîñêîëü-
êó íîðìàëüíàÿ ÔÏÐÂ õàðàêòåðèçóåòñÿ ìèíèìàëüíîé îøèáêîé êëàññèôèêàöèè
äëÿ äàííîãî ïîðîãà � è íå ïðåâûøàåò
4
9
2
2
�
�
[13, 14] â ñëó÷àå îäíîìîäàëüíîé ñèì-
ìåòðè÷íîé ÔÏРëèáî ÔÏРñ ïðàâîé àñèììåòðèåé, äâóñòîðîííåå íåðàâåíñòâî
äëÿ äàííîé îøèáêè ðàñïîçíàâàíèÿ çàïèøåì
0 5 1
4
9
2
2
,
�
�
�
�
�
�
��
�
�
�� � �erf
�
�
�
�
�
, (3)
ãäå � � 0 .
Ïðîàíàëèçèðóåì îáùóþ âîçìîæíóþ ôîðìó ïîòåíöèàëüíî ïîëó÷àåìûõ
ÔÏÐÂ ðàññòîÿíèé ìåæäó îáúåêòàìè. Âñå ðàñïðåäåëåíèÿ áóäóò èìåòü ýêñòðåìó-
ìû, ïîñêîëüêó ÔÏÐÂ ñóùåñòâóåò íà èíòåðâàëå [ , )0 � , à ïëîòíîñòü â îêðåñòíîñòè
íóëÿ è äëÿ áîëüøèõ ðàññòîÿíèé íå ìîæåò áûòü âûñîêîé, òàê êàê ýòè ñîáûòèÿ ìà-
ëîâåðîÿòíû. Ïðàâàÿ àñèììåòðèÿ (ñì. ðèñ. 1, à) áîëåå âåðîÿòíàÿ, ïîñêîëüêó ÔÏÐÂ
ðàññòîÿíèé îãðàíè÷åíà íóëåì è íå èìååò ñòðîãèõ îãðàíè÷åíèé.
ÎÖÅÍÊÈ ÂÅÐÎßÒÍÎÑÒÍÎÉ ÓÑÒÎÉ×ÈÂÎÑÒÈ ÏÎÊÐÛÒÈß ÎÁÚÅÊÒÎÂ
ÀËÃÎÐÈÒÌÀÌÈ ÒÈÏÀ kNN Â ÓÑËÎÂÈßÕ ÄÂÓÕ ÊËÀÑÑÎÂ,
ÈÌÅÞÙÈÕ ÇÀÄÀÍÍÛÅ ÐÀÇÌÅÐÛ
Ðàññìîòðèì ðàñïðîñòðàíåííóþ çàäà÷ó êëàññèôèêàöèè â óñëîâèÿõ äâóõ êëàññîâ.
Îáîçíà÷èì ðàçìåðû êëàññîâ s1 è s2 . Òîãäà åñëè âåðîÿòíîñòü çàìåùåíèÿ îáúåêòà
èç êëàññà ðàçìåðîì s1 â ïðåäåëàõ äîâåðèòåëüíîãî èíòåðâàëà ðàâíà �1, òî âåðîÿò-
íîñòü íåçàìåùåíèÿ îáúåêòîâ èç ýòîãî æå êëàññà îáúåêòàìè èç êëàññà ðàçìåðîì
s2 ðàâíà ( )1 1
2 � s
ïðè óñëîâèè íåçàâèñèìîñòè îáúåêòîâ [15]. Äëÿ äðóãîãî êëàñ-
ñà ïðè ñîîòâåòñòâóþùèõ èçìåíåíèÿõ â îáîçíà÷åíèÿõ ýòà âåðîÿòíîñòü ðàâíà
( )1 2
1 � s
. Åñëè ââåñòè íåêîòîðûé âèðòóàëüíûé êëàññ è äîïóñòèòü, ÷òî çàìåùå-
íèå ïðîèçâîëüíîãî îáúåêòà ýòîãî êëàññà îáúåêòàìè èç óïîìÿíóòûõ äâóõ êëàññîâ
ÿâëÿåòñÿ äîñòîâåðíûì ñîáûòèåì, òî ìîæíî çàïèñàòü ñëåäóþùåå óðàâíåíèå:
� � �(( ) ( ) )1 1 11 2
2 1 � �s s
, (4)
îòêóäà ìíîæèòåëü ïðîïîðöèîíàëüíîñòè � âû÷èñëÿåòñÿ òðèâèàëüíî.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 137
Èíîãäà èìåþò ìåñòî ñèòóàöèè, êîãäà ðàññòîÿíèÿ ìåæäó îáúåêòàìè ðàâíû
íóëþ. Ïðè ýòîì íåïàðàìåòðè÷åñêè îöåíåííîå ðàñïðåäåëåíèå îäíîãî èç êëàññîâ
ìîæåò èìåòü ìàêñèìóì â òî÷êå, ñîîòâåòñòâóþùåé íóëåâîìó ðàññòîÿíèþ. Ïóñòü
ïëîòíîñòè ðàñïðåäåëåíèé â íóëåâîé òî÷êå ðàâíû p1 0( ) è p2 0( ). Îöåíêà ñîîòíî-
øåíèÿ ìåæäó âåðîÿòíîñòÿìè ìîæåò áûòü çàäàíà â âèäå p p
s s
1 20 02 1( ) / ( ) èëè
ln ( ( ) / ( ) )p p
s s
1 20 02 1 . Ïðè ýòîì íåîáõîäèìî ñäåëàòü ãðàíè÷íûé ïåðåõîä îò ÔÐÂ
ê ÔÏÐÂ, ïîñêîëüêó îíè ñâÿçàíû ìåæäó ñîáîé îïåðàöèåé äèôôåðåíöèðîâàíèÿ.
Ñîîòíîøåíèå ln ( ( ) / ( ) )p p
s s
1 20 02 1 ( ln ( ( ) / ( ) )p p
s s
2 10 01 2 èëè â îáùåì ñëó÷àå
ln ( ( ) / ( ) )p p
s s
1 2
2 1� � (ln ( ( ) / ( ) )p p
s s
2 1
1 2� � ) ìîæíî èñïîëüçîâàòü äëÿ ïîñòðîåíèÿ
êëàññèôèêàòîðà âèäà
ln
( )
( )
p
p
s
s
1
2
1
2
1
�
�
�� ; ln
( )
( )
p
p
s
s
1
2
1
2
1
�
�
�� èëè ln
( )
( )
p
p
s
s
2
1
2
1
2
�
�
�� ; ln
( )
( )
p
p
s
s
2
1
2
1
2
�
�
�� , (5)
ãäå çíà÷åíèå ln
( )
( )
p
p
s
s
1
2
2
1
0
�
�
� èëè ln
( )
( )
p
p
s
s
2
1
1
2
0
�
�
� íå âëèÿåò íà ðåçóëüòàòû êëàñ-
ñèôèêàöèè, à ðåøåíèå ìîæåò áûòü ïðèíÿòî â ïîëüçó ëþáîãî êëàññà.  ñëó÷àå íåïà-
ðàìåòðè÷åñêîãî îöåíèâàíèÿ âåðîÿòíîñòü òàêîãî çíà÷åíèÿ ïðàêòè÷åñêè ðàâíà íóëþ.
ÂÅÐÕÍßß ÎÖÅÍÊÀ ÄËß ÌÅÒÎÄÀ ÑÊÎËÜÇßÙÅÃÎ ÊÎÍÒÐÎËß ÌÅÒÐÈ×ÅÑÊÈÕ
ÀËÃÎÐÈÒÌÎÂ ÊËÀÑÑÈÔÈÊÀÖÈÈ
Ìåòîäû ñêîëüçÿùåãî êîíòðîëÿ íåðàçðûâíî ñâÿçàíû ñ òàêèì ïîíÿòèì, êàê îáîá-
ùàþùàÿ ñïîñîáíîñòü àëãîðèòìîâ êëàññèôèêàöèè. Ïîä îáîáùàþùåé ñïîñîáíîñ-
òüþ àëãîðèòìîâ ïîäðàçóìåâàåòñÿ èõ ñïîñîáíîñòü îòíîñèòü îáúåêòû ñî ñõîæè-
ìè ñâîéñòâàìè ê îäíîìó è òîìó æå êëàññó. Êà÷åñòâî àëãîðèòìîâ, ñ òî÷êè çðå-
íèÿ îáîáùàþùåé ñïîñîáíîñòè, ïðèíÿòî õàðàêòåðèçîâàòü íà îñíîâàíèè ÷àñòîòû
(âåðîÿòíîñòè) îøèáîê, êîòîðûå ñîâåðøàåò òîò èëè èíîé àëãîðèòì. Ïðè ýòîì
âàæíî òàêæå ïðåäâèäåòü ÷àñòîòó îøèáîê íà êîíòðîëüíîé âûáîðêå, ê êîòîðîé
àëãîðèòì êëàññèôèêàöèè íåàäàïòèðîâàí. ×àñòîòó îøèáîê íà êîíòðîëüíîé âû-
áîðêå ìîæíî ïðåäâèäåòü íà îñíîâàíèè ãèïîòåçû î íåçàâèñèìîñòè îáúåêòîâ
âûáîðêè (êîòîðàÿ îáû÷íî âñåãäà âûïîëíÿåòñÿ [1]), à òàêæå îáîáùàþùåé ñïî-
ñîáíîñòè àëãîðèòìîâ.
Åñëè ñóùåñòâóåò òåñíàÿ ñâÿçü ìåæäó ÷àñòîòîé îøèáîê ïðè îáó÷åíèè è íà
êîíòðîëå, òî, óìåíüøàÿ ÷àñòîòó îøèáîê ïðè îáó÷åíèè (÷àñòî îíà ïðàêòè÷åñêè
ðàâíà íóëþ), ìû ñìîæåì óìåíüøèòü åå òàêæå è íà êîíòðîëå èëè ïðåäâèäåòü åå ñ
áîëüøîé âåðîÿòíîñòüþ.
Ïóñòü X — ïðîñòðàíñòâî îáúåêòîâ (object space); Y — ìíîæåñòâî èìåí
êëàññîâ (class name set); y X Y* : � — öåëåâàÿ ôóíêöèÿ (target function), çíà÷åíèÿ
êîòîðîé èçâåñòíû ëèøü íà îáúåêòàõ êîíå÷íîé îáó÷àþùåé âûáîðêè äëèíû l :
X x y X Yl
i i i
l� � �
�
( , )
1
, y y xi i� * ( ) . Â áàçå äàííûõ ñóùåñòâóþò êëàññû ýòàëî-
íîâ (class patterns) Ci , i n�1, , ïðè÷åì s Ci i� | | — ðàçìåðû êëàññîâ. Ïðåäïîëàãàåò-
ñÿ, ÷òî ðàçìåðû si âñåõ êëàññîâ îäèíàêîâûå è ðàâíû s. Ïîñêîëüêó ñóùåñòâóåò âû-
áîðêà êîíòðîëüíûõ îáúåêòîâ U , ïîäàþùèõñÿ íà ðàñïîçíàâàíèå, òî îáùåå êîëè-
÷åñòâî îáúåêòîâ, ó÷àñòâóþùèõ â ïðîöåññå ðàñïîçíàâàíèÿ, ðàâíî n s U� � | | . Ïóñòü
îöåíåííàÿ ÷àñòîòà îøèáîê (error frequency) àëãîðèòìà êëàññèôèêàöèè a X l� �( )
íà îáó÷àþùåé âûáîðêå X Xl L� : ( , )
| |
[ ( ) ( )]*a U
U
a u y u
x U
� �
��
1
, ãäå çàïèñü
x U� îçíà÷àåò, ÷òî îáúåêò îòíîñèòñÿ ê êîíòðîëüíîé ïîñëåäîâàòåëüíîñòè, à çà-
ïèñü [ ( ) ( )]*a u y u� âîñïðèíèìàåòñÿ êàê ôóíêöèÿ èíäèêàöèè íåñîâïàäåíèÿ îòâåòà
àëãîðèòìà a u( ) è ïðàâèëüíîãî îòâåòà y u* ( ) äëÿ ýòîãî îáúåêòà.
138 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
Íà ïðàêòèêå îïòèìàëüíîå çíà÷åíèå k ïîäáèðàåòñÿ ïî êðèòåðèþ ñêîëüçÿùåãî
êîíòðîëÿ (cross-validation) ñ èñêëþ÷åíèåì îáúåêòîâ ïî îäíîìó (leave-one-out,
LOO). Äëÿ êàæäîãî îáúåêòà x Xi
l� ïðîâåðÿåòñÿ, ïðàâèëüíî ëè îí êëàññèôèöè-
ðóåòñÿ ïî ñâîèì k áëèæàéøèì ñîñåäÿì:
LOO( , ) [ ( ; \ , ) ] mink X a x X x k yl
i
l
i
l
i i
k
� � �
�
�
1
. (6)
Èäåÿ ïðåäëàãàåìîãî ïîäõîäà ñîñòîèò â ñëåäóþùåì. Àíàëèçèðóþòñÿ ðàññòîÿ-
íèÿ ìåæäó òåñòîâûì îáúåêòîì è îáúåêòàìè áàçû äàííûõ. Òîãäà íà îñíîâàíèè
ðàññòîÿíèé îò òåñòîâîãî îáúåêòà äî îáúåêòîâ áàçû äàííûõ íåîáõîäèìî ïðåäâè-
äåòü ðàññòîÿíèÿ ìåæäó îáúåêòàìè áàçû äàííûõ. Íà ïåðâûé âçãëÿä ìîæåò ïîêà-
çàòüñÿ, ÷òî òàêèå îöåíêè ìåíåå òî÷íû, íåæåëè ïîëó÷àåìûå íà îñíîâàíèè ïîëíîãî
ñêîëüçÿùåãî êîíòðîëÿ ïî âûáîðêå. Îäíàêî åñëè äîêàçàòü, ÷òî ýòè îöåíêè ïðåä-
ñòàâëÿþò ñîáîé âåðõíèå îöåíêè îòíîñèòåëüíî ÷àñòîòû (âåðîÿòíîñòè) îøèáîê, òî
îíè áóäóò ìåíåå ÷óâñòâèòåëüíû ê ôàêòîðàì, îáóñëàâëèâàþùèì ïåðåîáó÷åíèå.
Ïóñòü ñòåïåíü ïîäîáèÿ ìåæäó îáúåêòàìè õàðàêòåðèçóåòñÿ íà îñíîâàíèè ïî-
íÿòèÿ ðàññòîÿíèÿ. Ïî îïðåäåëåíèþ ðàññòîÿíèå ìåæäó äâóìÿ âåêòîðàìè ïðèçíà-
êîâ (x è y) ñîîòâåòñòâóþùèõ îáúåêòîâ äîëæíî óäîâëåòâîðÿòü ñëåäóþùèì
óñëîâèÿì:
1) d x x d y y( , ) ( , )� � 0 ;
2) d x y d y x( , ) ( , )�
(äëÿ òîãî ÷òîáû ðàññòîÿíèå áûëî ìåòðèêîé, íåîáõîäèìî âûïîëíåíèå åùå îä-
íîãî äîïîëíèòåëüíîãî óñëîâèÿ, íàçûâàåìîãî íåðàâåíñòâîì òðåóãîëüíèêà):
3) d x y d x z d y z( , ) ( , ) ( , )� � .
Ìåòðèêîé ÿâëÿåòñÿ îáîáùåííàÿ ìåòðèêà Ìèíêîâñêîãî ñ ïîêàçàòåëåì ñòåïå-
íè p � 1:
d x y x y a x yi i
p
i
n
p
i
i
n
i i( , ) | | | |
/
�
�
�
�
�
�
�
�
�
�
�
�
� �
� �
1
1
1
�
�
�
�
�
�
�
1
1
/
( ) | |
p
i
i
n
i iC p a x y , (7)
ãäå ìóëüòèïëèêàòèâíûé ìíîæèòåëü C p( ) ïðåäñòàâëÿåòñÿ â âèäå
C p a x yi
i
n
i i
p p
( ) | |
( )/
�
�
�
�
�
�
�
�
�
�
1
1
, a x yi i i
p� | | 1 , p � 0 . (8)
Ïðîàíàëèçèðóåì ðàññòîÿíèÿ ìåæäó îáúåêòàìè ñ òî÷êè çðåíèÿ àäåêâàòíîãî
îïèñàíèÿ ïîäîáèÿ ìåæäó îáúåêòàìè, à òàêæå ìåòðèêè Ìèíêîâñêîãî äëÿ ðàçëè÷-
íûõ ïîêàçàòåëåé p. Ââåäåì ïîíÿòèå ãëóáèíû ìåòðèêè M
d x z d y z
d x y
�
�( , ) ( , )
( , )
. Òà-
êèì îáðàçîì, ÷åì áîëüøå çíà÷åíèå ãëóáèíû ìåòðèêè, òåì ñòðîæå âûïîëíÿåòñÿ
óñëîâèå òðåóãîëüíèêà. Äëÿ ìåòðèêè Ìèíêîâñêîãî åå ãëóáèíà âîçðàñòàåò ñ ðîñòîì
ïîêàçàòåëÿ p. Ïî îïðåäåëåíèþ M � 1. Îñòàåòñÿ âûÿñíèòü, êàê âëèÿåò òà èëè èíàÿ
ìåòðèêà íà ïåðåðàñïðåäåëåíèå ðàññòîÿíèé ìåæäó îáúåêòàìè.
Ñíà÷àëà ðàññìîòðèì åâêëèäîâóþ ìåòðèêó (ïîêàçàòåëü â îáîáùåííîé ìåòðè-
êå Ìèíêîâñêîãî ðàâåí 2): d x y x yi i
i
n
( , ) | |
/
�
�
�
�
�
�
�
�
�
� 2
1
1 2
. Ïóñòü èçâåñòíû ðàññòîÿíèÿ
ìåæäó òåñòîâûì îáúåêòîì è îáúåêòàìè áàçû äàííûõ: d d x yi i� ( , ) è d d x yj j� ( , ).
Íåîáõîäèìî îöåíèòü ðàññòîÿíèå d y yij i j( , ) íà îñíîâàíèè äâóõ èçâåñòíûõ ðàñ-
ñòîÿíèé.  òåîðèè ðàñïîçíàâàíèÿ îáðàçîâ èëè òåîðèè ìàøèííîãî îáó÷åíèÿ ýòà
çàäà÷à ñâîäèòñÿ ê îöåíêå ðåçóëüòàòîâ íà êîíòðîëå, êîãäà èçâåñòíû ðåçóëüòàòû
ëèøü íà îáó÷àþùåé âûáîðêå. Êîëè÷åñòâî äàííûõ, èñïîëüçóåìûõ äëÿ îáó÷åíèÿ,
çíà÷èòåëüíî ìåíüøå òîãî êîëè÷åñòâà äàííûõ, êîòîðîå ìîæíî áûëî áû ïîëó÷èòü
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 139
êîìáèíàòîðíîé ïåðåãðóïïèðîâêîé âûáîðêè. Ýòî íóæíî äëÿ áûñòðîãî îïðåäåëå-
íèÿ ïàðàìåòðîâ áåç ó÷åòà ðåçóëüòàòîâ ðàñïîçíàâàíèÿ àëãîðèòìàìè ïîëíîãî
ñêîëüçÿùåãî êîíòðîëÿ, ò.å. ïðîâîäèòñÿ íåïîëíûé ñêîëüçÿùèé êîíòðîëü ñ ãëóáè-
íîé, çíà÷èòåëüíî ìåíüøå òîé, ÷òî ìîæåò áûòü ïîëó÷åíà ïåðåãðóïïèðîâêîé îá-
ùåé âûáîðêè íà òåñòîâóþ è îáó÷àþùóþ.
Ðàññìîòðèì â êà÷åñòâå ïðèìåðà òðè ðàññòîÿíèÿ: d d x y1 1� ( , ) , d d x y2 2� ( , )
è d d x y3 3� ( , ) äëÿ åâêëèäîâîé ìåòðèêè è ïðîñòðàíñòâà R 2 . Ñîîòâåòñòâåííî íå-
îáõîäèìî îöåíèòü ðàññòîÿíèÿ d d y y12 1 2� ( , ) , d d y y13 1 3� ( , ) è d d y y23 2 3� ( , ) .
Âû÷èñëèì èõ ñ ïîìîùüþ òåîðåìû êîñèíóñîâ:
d d d d d d d12 1
2
2
2
1 2 1 22� � cos ( , ) ,
d d d d d d d13 1
2
3
2
1 3 1 32� � cos ( , ) , (9)
d d d d d d d23 2
2
3
2
2 3 2 32� � cos ( , ) .
Äëÿ òîãî ÷òîáû îïðåäåëèòü ðàññòîÿíèÿ d12 , d13 è d23 , íåîáõîäèìî çíàòü ñî-
îòâåòñòâóþùèå óãëû ìåæäó âåêòîðàìè. Âîçìîæíû äâà âàðèàíòà:
1) ïðèìåíèòü ïàðàëëåëüíî åâêëèäîâîé êîñèíóñíóþ ìåòðèêó;
2) âû÷èñëèòü çàâûøåííóþ îöåíêó äëÿ ñîîòâåòñòâóþùèõ ðàññòîÿíèé, íàêëà-
äûâàÿ îïðåäåëåííûå óñëîâèÿ íà óãëû ìåæäó âåêòîðàìè.
Ïåðâûé ñïîñîá ãàðàíòèðóåò òî÷íîå âû÷èñëåíèå ðàññòîÿíèé ëèøü â ñëó÷àå
åâêëèäîâîé ìåòðèêè. Âòîðîé ñïîñîá èñïîëüçóåòñÿ ëèøü êàê áàçîâûé äëÿ åâêëè-
äîâîé ìåòðèêè, ÷òî â äàëüíåéøåì ïîçâîëèò îöåíèâàòü ñîîòíîøåíèÿ ìåæäó ðàñ-
ñòîÿíèÿìè ñ ïîìîùüþ äðóãèõ ìåòðèê. ×àñòî íåò íåîáõîäèìîñòè îïðåäåëÿòü ðàñ-
ñòîÿíèå àáñîëþòíî òî÷íî, ÷òîáû ðåçóëüòàòû ðàñïîçíàâàíèÿ áûëè èäåíòè÷íûìè;
êðîìå òîãî, òàêàÿ îöåíêà äàåò çàïàñ óñòîé÷èâîñòè ðåçóëüòàòîâ ðàñïîçíàâàíèÿ.
Ïîýòîìó ðàññìîòðèì âòîðîé âàðèàíò. Äîïóñòèì, ÷òî óãëû ìåæäó âåêòîðàìè d1,
d2 è d3 íàõîäÿòñÿ â ïðåäåëàõ [ ; / ]0
� . Ýòî âûòåêàåò èç òîãî, ÷òî åñëè óãîë ðàâåí
�/ , äîñòèãàåòñÿ ìàêñèìàëüíîå ðàçëè÷èå ìåæäó îáúåêòàìè, îïèñûâàåìûìè ñî-
îòâåòñòâóþùèìè âåêòîðàìè. Ïðè ýòîì äëÿ òîãî ÷òîáû áîëüøèé èç âîçìîæíûõ
óãëîâ ìåæäó âåêòîðàìè ðàññòîÿíèé áûë ðàâåí
�/ , õîòÿ áû îäèí èç óãëîâ, îáðà-
çîâàííûõ âåêòîðàìè ðàññòîÿíèé d1, d2 è d3 ñ ïîëîæèòåëüíîé ïîëóîñüþ, äîëæåí
áûòü íå ìåíüøå
�/ . Ïóñòü äëÿ êëàññèôèêàöèè çàäàííîé ïîñëåäîâàòåëüíîñòè
îáúåêòîâ âàæíûìè ÿâëÿþòñÿ k áëèæàéøèõ ñîñåäåé. Ïðîàíàëèçèðóåì ïðîöåññ
ïðèíÿòèÿ ðåøåíèÿ íà îñíîâàíèè àëãîðèòìà áëèæàéøèõ ñîñåäåé. Äëÿ íåãî ðàñ-
ñòîÿíèÿ d12 , d13 è d23 ìîãóò áûòü âû÷èñëåíû ñëåäóþùèì îáðàçîì:
d d d d d
l
12 1
2
2
2
1 22
2
� �
�
�
�
�
�cos
,
d d d d d
l
13 1
2
3
2
1 32
2
� �
�
�
�
�
�cos
, (10)
d d d d d
l
23 2
2
3
2
2 32
2
� �
�
�
�
�
�cos
.
Ýòîò ñïîñîá âû÷èñëåíèÿ ðàññòîÿíèé îñíîâàí íà äîïóùåíèè î ðàâíîìåðíîñ-
òè ðàñïðåäåëåíèÿ óãëîâ ìåæäó ñîîòâåòñòâóþùèìè âåêòîðàìè ðàññòîÿíèé. Äëÿ
çàäà÷è ðàñïîçíàâàíèÿ òàêîå äîïóùåíèå ñîîòâåòñòâóåò íàèõóäøåìó ñëó÷àþ.
Èòàê, íà îñíîâàíèè (10) ïîëó÷åíû âåðõíèå îöåíêè äëÿ ñîîòâåòñòâóþùèõ ðàññòî-
ÿíèé. Òåïåðü ýòè ðàññòîÿíèÿ äëÿ ïðîèçâîëüíîé ïîñëåäîâàòåëüíîñòè îáúåêòîâ è
âåêòîðîâ, êîòîðûå èì ñîîòâåòñòâóþò, çàïèøåì òàê:
d d d d d
j i
l
i j k j iij i j i j� �
�
�
�
�
� � �2 2 2
2
1cos
( )
, , , ;
{ } . (11)
140 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
Ðàññìîòðèì èçìåíåíèå ðàññòîÿíèé ìåæäó îáúåêòàìè ïðè ïðèìåíåíèè äðó-
ãèõ ìåòðèê, ó÷èòûâàÿ äâà âîçìîæíûõ ñëó÷àÿ ïî îòíîøåíèþ ê åâêëèäîâîé ìåòðè-
êå. Ïåðâûé êàñàåòñÿ ìåòðèê ñ ïîðÿäêîì p � 2, à âòîðîé — 1 2� �p . Ïðîàíàëèçè-
ðóåì èçìåíåíèå ñîîòíîøåíèÿ ìåæäó âåêòîðàìè ðàññòîÿíèé íà îñíîâàíèè ïîíÿ-
òèÿ ãëóáèíû ìåòðèêè M . Ñ ðîñòîì ïîêàçàòåëÿ p â îáîáùåííîé ìåòðèêå
Ìèíêîâñêîãî ãëóáèíà ìåòðèêè M ðàñòåò. Ïðè ýòîì äëÿ ñëó÷àÿ p � 2 ãëóáèíà ìåò-
ðèêè âñåãäà áîëüøå, ÷åì äëÿ p � 2, à äëÿ 1 2� �p — ñîîòâåòñòâåííî ìåíüøå. Òà-
êèì îáðàçîì, åâêëèäîâàÿ ìåòðèêà ÿâëÿåòñÿ íåêîòîðîé ãðàíèöåé ðàçäåëà â ïðî-
ñòðàíñòâå ìåòðèê, îòíîñèòåëüíî êîòîðîé ïðîâîäèòñÿ ñðàâíåíèå. Ïîýòîìó åâêëè-
äîâàÿ ìåòðèêà íàèáîëåå èñïîëüçóåìàÿ â ïðèêëàäíûõ çàäà÷àõ, à ðàññòîÿíèÿ,
âû÷èñëÿåìûå ñ åå ïîìîùüþ, ïîíÿòíû ñ òî÷êè çðåíèÿ èíòåðïðåòàöèè.
ÇÀÊËÞ×ÅÍÈÅ
 íàñòîÿùåé ðàáîòå ïîñòðîåíû è èññëåäîâàíû îöåíêè âåðîÿòíîñòè ïðàâèëüíîé
êëàññèôèêàöèè äëÿ êëàññèôèêàòîðîâ, èñïîëüçóþùèõ â êà÷åñòâå ìåðû ïîäîáèÿ
ôóíêöèþ ðàññòîÿíèé. Ðåçóëüòàòû îöåíèâàíèÿ ïîëó÷åíû íà îñíîâàíèè ôóíêöèè
ðàñïðåäåëåíèÿ ðàññòîÿíèé ìåæäó îáúåêòàìè. Ïðè ýòîì ðàññìîòðåíû ðàçíûå ÷àñ-
òè÷íûå ñëó÷àè ôîðìû ôóíêöèè ðàñïðåäåëåíèÿ. Ïîñòðîåíû äâóñòîðîííèå âåðõíèå
îöåíêè îäèíî÷íîãî ðàñïîçíàâàíèÿ è ðàñïîçíàâàíèÿ äëÿ äâóõ êëàññîâ çàäàííûõ
ðàçìåðîâ. Ïðåäëîæåí ìåòîä êëàññèôèêàöèè íà îñíîâàíèè ñîîòíîøåíèÿ ïëîòíîñ-
òåé ðàñïðåäåëåíèÿ âåðîÿòíîñòåé â íóëåâîé è ïðîèçâîëüíûõ òî÷êàõ. Ðàçðàáîòàí
ïîäõîä ê ïîñòðîåíèþ îöåíîê ìàêñèìàëüíîãî çíà÷åíèÿ âåðîÿòíîñòè ïðàâèëüíîãî
ðàñïîçíàâàíèÿ äëÿ êëàññèôèêàòîðîâ íà îñíîâàíèè ôóíêöèè ðàññòîÿíèé (êëàññè-
ôèêàòîðîâ òèïà k NN) ñ ïîìîùüþ íåãëóáîêîãî ñêîëüçÿùåãî êîíòðîëÿ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. V o r o n t s o v K . V . Combinatorial probability and the tightness of generalization bounds // Pattern
Recognition and Image Analysis. — 2008. — 18, N 2. — P.243–259.
2. V a p n i k V . The nature of statistical learning theory. — New York: Springer-Verlag, 2000. — 314 p.
3. Æ ó ð à â ë å â Þ . È . Îá àëãåáðàè÷åñêîì ïîäõîäå ê ðåøåíèþ çàäà÷ ðàñïîçíàâàíèÿ èëè êëàñ-
ñèôèêàöèè // Ïðîáëåìû êèáåðíåòèêè. — 1978. — 33. — Ñ. 5–68.
4.  î ð î í ö î â Ê .  . Ìàøèííîå îáó÷åíèå è àíàëèç äàííûõ // Êóðñ ëåêöèé «Ìàòåìàòè÷åñêèå
ìåòîäû îáó÷åíèÿ ïî ïðåöåäåíòàì». — http: // www.ccas.ru/voron/teaching.html.
5. Ø ë å ç è í ã å ð Ì . , à ë à â à ÷  . Äåñÿòü ëåêöèé ïî ñòàòèñòè÷åñêîìó è ñòðóêòóðíîìó
ðàñïîçíàâàíèþ. — Êèåâ: Íàóê. äóìêà, 2004. — 545 ñ.
6. M o o n T . K . , S t i r l i n g W . C . Mathematical methods and algorithms for signal processing. —
N.J.: Prentice-Hall, 2000. — 937 p.
7. K a p u s t i i B . E . , R u s y n B . P . , T a y a n o v V . A . Classifier optimization in small sample
size condition // Automatic Control and Computer Sci. — 2006. — 40, N 5. — P. 17–22.
8. Ê à ï ó ñ ò ³ é Á . Î . , Ð ó ñ è í Á . Ï . , Ò à ÿ í î â  . À . Êîìá³íàòîðíà îö³íêà âïëèâó çìåíøåí-
íÿ ³íôîðìàö³éíîãî ïîêðèòòÿ êëàñ³â íà óçàãàëüíþþ÷ó âëàñòèâ³ñòü 1NN àëãîðèòì³â
êëàñèô³êàö³¿ // Èñêóññòâåííûé èíòåëëåêò. — 2008. — ¹ 1. — Ñ. 49–54.
9. Ê à ð ë è í Ñ . Îñíîâû òåîðèè ñëó÷àéíûõ ïðîöåññîâ. — Ì.: Ìèp, 1971. — 576 ñ.
10. Ê î ð î ë þ ê  . Ñ . , Ï î ð ò å í ê î Í . È . , Ñ ê î ð î õ î ä À .  . , Ò ó ð á è í À . Ô . Ñïðàâî÷íèê
ïî òåîðèè âåðîÿòíîñòåé è ìàòåìàòè÷åñêîé ñòàòèñòèêå. — Ì.: Íàóêà, 1985. — 640 ñ.
11. B i s h o p C . M . Pattern recognition and machine learning (Information science and statistics). —
London: Springer, 2006. — 738 p.
12. W e i s s t e i n E . W . Chebyshev inequality. — http://mathworld.wolfram.com/Chebyshev
Inequality.html, 10.12.2008.
13. W e i s s t e i n E . W . Gauss inequality. — http://mathworld.wolfram.com/GaussInequality.html,
10.12.2008.
14. Ò ó Ä æ . , Ã î í ñ à ë å ñ Ð . Ïðèíöèïû ðàñïîçíàâàíèÿ îáðàçîâ. — Ì.: Ìèð, 1978. — 416 ñ.
15. Ê à ï ó ñ ò è é Á . Î . , Ð ó ñ û í Á . Ï . , Ò à ÿ í î â Â . À . Íîâûé ïîäõîä ê îïðåäåëåíèþ âåðîÿò-
íîñòè ïðàâèëüíîãî ðàñïîçíàâàíèÿ îáúåêòîâ ìíîæåñòâ // ÓÑèÌ. — 2005. — ¹ 2. — Ñ. 8–13.
Ïîñòóïèëà 07.12.2011
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 141
|