Использование ε-сетей для линейного разделения двух множеств в пространстве Rd

Использование ε-сетей для линейного разделения двух множеств в пространстве Rd

Введено понятие ε-разделимости двух множеств. Доказаны необходимые и достаточные условия ε-разделимости, а также сведение задачи ε-разделения двух множеств к задаче разделения их ε-сетей, которые не пересекаются....

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Datum:2015
Hauptverfasser: Иванчук, М.А., Малык, И.В.
Format: Artikel
Sprache:Russian
Veröffentlicht: Інститут кібернетики ім. В.М. Глушкова НАН України 2015
Schriftenreihe:Кибернетика и системный анализ
Schlagworte:
Системный анализ
Online Zugang:http://dspace.nbuv.gov.ua/handle/123456789/124936
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Использование ε-сетей для линейного разделения двух множеств в пространстве Rd / М.А. Иванчук, И.В. Малык // Кибернетика и системный анализ. — 2015. — Т. 51, № 6. — С. 147-150. — Бібліогр.: 14 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-124936
record_format dspace
spelling irk-123456789-1249362017-10-13T03:03:26Z Использование ε-сетей для линейного разделения двух множеств в пространстве Rd Иванчук, М.А. Малык, И.В. Системный анализ Введено понятие ε-разделимости двух множеств. Доказаны необходимые и достаточные условия ε-разделимости, а также сведение задачи ε-разделения двух множеств к задаче разделения их ε-сетей, которые не пересекаются. У роботі введено поняття ε-відокремлюваності двох множин. Доведено необхідні та достатні умови ε-відокремлюваності. Доведено, що задачу ε-відокремлення двох множин можна звести до задачі відокремлення їх ε-сіток, що не перетинаються. The concept of ε-separability is introduced in the paper. The necessary and sufficient conditions of ε-separability are proved. It is proved that the problem of ε-separability of two sets can be reduced to the trivial problem of separability of their disjoint ε-nets. 2015 Article Использование ε-сетей для линейного разделения двух множеств в пространстве Rd / М.А. Иванчук, И.В. Малык // Кибернетика и системный анализ. — 2015. — Т. 51, № 6. — С. 147-150. — Бібліогр.: 14 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/124936 519.673+519.674: 519.234.6 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Russian
topic Системный анализ
Системный анализ
spellingShingle Системный анализ
Системный анализ
Иванчук, М.А.
Малык, И.В.
Использование ε-сетей для линейного разделения двух множеств в пространстве Rd
Кибернетика и системный анализ
description Введено понятие ε-разделимости двух множеств. Доказаны необходимые и достаточные условия ε-разделимости, а также сведение задачи ε-разделения двух множеств к задаче разделения их ε-сетей, которые не пересекаются.
format Article
author Иванчук, М.А.
Малык, И.В.
author_facet Иванчук, М.А.
Малык, И.В.
author_sort Иванчук, М.А.
title Использование ε-сетей для линейного разделения двух множеств в пространстве Rd
title_short Использование ε-сетей для линейного разделения двух множеств в пространстве Rd
title_full Использование ε-сетей для линейного разделения двух множеств в пространстве Rd
title_fullStr Использование ε-сетей для линейного разделения двух множеств в пространстве Rd
title_full_unstemmed Использование ε-сетей для линейного разделения двух множеств в пространстве Rd
title_sort использование ε-сетей для линейного разделения двух множеств в пространстве rd
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate 2015
topic_facet Системный анализ
url http://dspace.nbuv.gov.ua/handle/123456789/124936
citation_txt Использование ε-сетей для линейного разделения двух множеств в пространстве Rd / М.А. Иванчук, И.В. Малык // Кибернетика и системный анализ. — 2015. — Т. 51, № 6. — С. 147-150. — Бібліогр.: 14 назв. — рос.
series Кибернетика и системный анализ
work_keys_str_mv AT ivančukma ispolʹzovanieesetejdlâlinejnogorazdeleniâdvuhmnožestvvprostranstverd
AT malykiv ispolʹzovanieesetejdlâlinejnogorazdeleniâdvuhmnožestvvprostranstverd
first_indexed 2025-07-09T02:17:19Z
last_indexed 2025-07-09T02:17:19Z
_version_ 1837133929188950016
fulltext ÓÄÊ 519.673+519.674: 519.234.6 Ì.À. ÈÂÀÍ×ÓÊ, È.Â. ÌÀËÛÊ ÈÑÏÎËÜÇÎÂÀÍÈÅ e-ÑÅÒÅÉ ÄËß ËÈÍÅÉÍÎÃÎ ÐÀÇÄÅËÅÍÈß ÄÂÓÕ ÌÍÎÆÅÑÒ  ÏÐÎÑÒÐÀÍÑÒÂÅ R d Àííîòàöèÿ. Ââåäåíî ïîíÿòèå e-ðàçäåëèìîñòè äâóõ ìíîæåñòâ. Äîêàçàíû íåîáõîäèìûå è äîñòàòî÷íûå óñëîâèÿ e-ðàçäåëèìîñòè, à òàêæå ñâåäåíèå çàäà÷è e-ðàçäåëåíèÿ äâóõ ìíî- æåñòâ ê çàäà÷å ðàçäåëåíèÿ èõ e-ñåòåé, êîòîðûå íå ïåðåñåêàþòñÿ. Êëþ÷åâûå ñëîâà: ýïñèëîí-ñåòè, ðàçäåëåíèå ìíîæåñòâ, ðàçìåðíîñòü Âàïíèêà–×åðâîíåíêèñà. ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È Ïóñòü çàäàíû äâà êîíå÷íûõ ìíîæåñòâà: A R d Ì è B R d Ì , ìîùíîñòè êîòîðûõ | |A nA= , | |B nB= . Ïðåäïîëîæèì, ÷òî A BË conv , B AË conv .  ïðîñòåéøåì ñëó÷àå, åñëè âûïóêëûå îáîëî÷êè ìíîæåñòâ A R d Ì è B R d Ì íå ïåðåñåêàþò- ñÿ, èõ ìîæíî ðàçäåëèòü, ò.å. íàéòè ãèïåðïëîñêîñòü, îòíîñèòåëüíî êîòîðîé äàí- íûå ìíîæåñòâà áóäóò íàõîäèòüñÿ ïî ðàçíûå ñòîðîíû. Ïðåäïîëîæèì, ÷òî ìíî- æåñòâà íåðàçäåëèìû, ò.å. conv conv( ) ( )A BÇ ¹ Æ . Âîçíèêàåò âîïðîñ, â êàêîì ñëó÷àå äàííûå ìíîæåñòâà ìîæíî ðàçäåëèòü, èñêëþ÷èâ èç íèõ íåáîëüøîå êî- ëè÷åñòâî òî÷åê, íàïðèìåð e Î( , )0 1 ÷àñòåé îò îáùåãî êîëè÷åñòâà. Íà äàííûé ìîìåíò ñóùåñòâóåò áîëüøîå êîëè÷åñòâî ìåòîäîâ êëàññèôèêà- öèè, êàæäûé èç êîòîðûõ èìååò ïðåèìóùåñòâà è íåäîñòàòêè. Íàèáîëåå ïîïóëÿð- íûé èç íèõ — äèñêðèìèíàíòíûé àíàëèç Ôèøåðà [1]. Îí øèðîêî èñïîëüçóåòñÿ â òàêèõ îòðàñëÿõ èíôîðìàòèêè, êàê ìàøèííîå îáó÷åíèå, ïîèñê èíôîðìàöèè è ðàñïîçíàâàíèå îáðàçîâ. Ñëîæíîñòü àëãîðèòìà ëèíåéíîãî äèñêðèìèíàíòíîãî àíà- ëèçà îöåíèâàåòñÿ êàê O ndt t( )+ 3 , ãäå n — êîëè÷åñòâî íàáëþäåíèé â îáó÷àþùåé âûáîðêå, d — êîëè÷åñòâî ïðèçíàêîâ, t n d= min( , ) [2]. Ïîýòîìó ïðè áîëüøèõ çíà- ÷åíèÿõ n è d àëãîðèòì èñïîëüçîâàòü íåâîçìîæíî. Áàéåñîâñêèé êëàññèôèêàòîð [3] îïòèìàëüíûé, ëåãêî ðåàëèçóåòñÿ ïðîãðàì- ìíî, íà åãî îñíîâå ïîñòðîåíî ìíîãî ìåòîäîâ êëàññèôèêàöèè. Îäíàêî ïîñêîëüêó íà ïðàêòèêå ôóíêöèè ïðàâäîïîäîáèÿ êëàññîâ âîññòàíàâëèâàþò ïî êîíå÷íûì âû- áîðêàì äàííûõ, áàéåñîâñêèé êëàññèôèêàòîð ïåðåñòàåò áûòü îïòèìàëüíûì [4]. Åãî ñëîæíîñòü àëãîðèòìà îöåíèâàåòñÿ êàê O nd( ) [5]. Ñðàâíèòåëüíî íîâûé ìåòîä îïîðíûõ âåêòîðîâ, èçâåñòíûé â ëèòåðàòóðå êàê SVM [6] áëàãîäàðÿ ïðèíöèïó îïòèìàëüíîé ðàçäåëÿþùåé ãèïåðïëîñêî- ñòè, ïðèâîäèò ê ìàêñèìèçàöèè øèðèíû ðàçäåëÿþùåé ïîëîñû ìåæäó êëàññà- ìè. Òàêèì îáðàçîì, ýòîò ìåòîä ñïîñîáñòâóåò áîëåå óâåðåííîé êëàññèôèêà- öèè. Îäíàêî íàðÿäó ñ ýòèì îí íåñòîéêèé ê øóìó â èñõîäíûõ äàííûõ. Ñóùåñ- òâåííûì íåäîñòàòêîì ìåòîäà ÿâëÿåòñÿ îòñóòñòâèå ðàçðàáîòàííûõ îáùèõ ìåòîäîâ ïîñòðîåíèÿ âûïðÿìëÿþùèõ ïðîñòðàíñòâ è ÿäåð, êîòîðûå íàèëó÷- øèì îáðàçîì ïîäõîäÿò ê êîíêðåòíîé çàäà÷å [7]. Ñëîæíîñòü àëãîðèòìà ìåòî- äà îïîðíûõ âåêòîðîâ îöåíèâàåòñÿ êàê O n( )3 [8]. Êëàññèôèêàöèÿ ñ ïîìîùüþ êëàñòåðíîãî àíàëèçà, à òàêæå âàëüäîâñêèé ïîñëåäîâàòåëüíûé àíàëèç ñ ïðè- ìåíåíèåì èíôîðìàöèîííîé ìåðû Êóëüáàêà îïèñàíû â ðàáîòå [9]. ÎÑÍÎÂÍÛÅ ÎÏÐÅÄÅËÅÍÈß Îïðåäåëåíèå 1. Ìíîæåñòâà A è B íàçûâàþòñÿ e-ðàçäåëèìûìè, åñëè ñóùåñòâó- þò A A1 Ì , B B1 Ì , äëÿ êîòîðûõ conv conv( \ ) ( \ )A A B B1 1Ç = Æ , (1) | | | | ( )A B n nA B1 1+ < +e . (2) ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5 147 © Ì.À. Èâàí÷óê, È.Â. Ìàëûê, 2015 Îïðåäåëåíèå 2. Ãèïåðïëîñêîñòü L íàçûâàåòñÿ ðàçäåëÿþùåé äëÿ ìíîæåñòâ A è B, åñëè conv A LÌ + , conv B LÌ - . Îïðåäåëåíèå 3. Ãèïåðïëîñêîñòü Le íàçûâàåòñÿ e-ðàçäåëÿþùåé äëÿ ìíî- æåñòâ A è B, åñëè | | | |A L B L n nA B Ç + Ç + ³ - + - e e e1 . Äëÿ ðåøåíèÿ çàäà÷è íàõîæäåíèÿ e-ðàçäåëÿþùåé ãèïåðïëîñêîñòè äâóõ ìíî- æåñòâ áóäåì èñïîëüçîâàòü e-ñåòè. Ðàññìîòðèì ðàíæèðîâàííîå ïðîñòðàíñòâî ( , )X u , ãäå X — íåêîòîðîå ìíîæåñòâî, u — ñîâîêóïíîñòü ïîäìíîæåñòâ ìíî- æåñòâà X [10]. Îïðåäåëåíèå 4. Ïðîåêöèåé u íà A íàçûâàåòñÿ ìíîæåñòâî PrA r A r( ) { : }u u= Ç Î . Îïðåäåëåíèå 5. Ñ÷èòàþò, ÷òî A äðîáèòñÿ ñ ïîìîùüþ u, åñëè PrA A( )u = 2 . Îïðåäåëåíèå 6. Ðàçìåðíîñòüþ Âàïíèêà–×åðâîíåíêèñà äëÿ ðàíæèðîâàííîãî ïðîñòðàíñòâà ( , )X u íàçûâàåòñÿ ìîùíîñòü (âîçìîæíî, áåñêîíå÷íàÿ) íàèáîëüøå- ãî ïîäìíîæåñòâà èç X , êîòîðîå äðîáèòñÿ ñ ïîìîùüþ u : VC X m A X( , ) : max{ :u = $ Ì , A äðîáèòñÿ ñ ïîìîùüþ u} . Òåîðåìà Ðàäîíà. Êàæäîå ìíîæåñòâî èç d +2 èëè áîëåå òî÷åê â R d ìîæåò áûòü ïðåäñòàâëåíî êàê îáúåäèíåíèå äâóõ íåïåðåñåêàþùèõñÿ ìíîæåñòâ, âûïóê- ëûå îáîëî÷êè êîòîðûõ èìåþò îáùóþ òî÷êó [11]. Ñëåäñòâèå [10]. Ðàçìåðíîñòü Âàïíèêà–×åðâîíåíêèñà äëÿ ðàíæèðîâàííîãî ïðîñòðàíñòâà ( , )R H d d , ãäå H d — ñîâîêóïíîñòü âñåõ ïîëóïðîñòðàíñòâ â R d , îïðåäåëÿåòñÿ êàê VC R H d d d( , ) = +1 . Îïðåäåëåíèå 7. Ïóñòü çàäàíû ðàíæèðîâàííîå ïðîñòðàíñòâî ( , )X u , ìíî- æåñòâî A XÌ è e ÎR , 0 1< <e , òîãäà ïîäìíîæåñòâî N AÌ íàçûâàåòñÿ e-ñåòüþ äëÿ ìíîæåñòâà A , åñëè " Î Ç ³ Þ Ç Ç ¹ Ær r A A N r Au: | | | | ( )e . Òåîðåìà Âåëüöëÿ–Õàóññëåðà [12]. Ïóñòü VC X( , )u = < ¥d , òîãäà " ÌA X , | |A n= , " Îe ( , )0 1 ñóùåñòâóåò e-ñåòü N ìíîæåñòâà A, ìîùíîñòü êîòîðîé íå çàâèñèò îò ìîùíîñòè ìíîæåñòâà A , êðîìå òîãî | | logN £ 8 8 2 d e d e . e-ÐÀÇÄÅËÅÍÈÅ ÌÍÎÆÅÑÒ  ÏÐÎÑÒÐÀÍÑÒÂÅ R d Ðàññìîòðèì ðàíæèðîâàííîå ïðîñòðàíñòâî ( , )R H d d , ãäå H d — ñîâîêóïíîñòü âñåõ ïîëóïðîñòðàíñòâ â R d .  ( , )R H d d áóäåì ñòðîèòü e-ñåòè ìíîæåñòâ A è B. Ïîêàæåì, ÷òî çàäà÷ó e-ðàçäåëåíèÿ ìíîæåñòâ A è B ìîæíî ñâåñòè ê çàäà÷å ðàç- äåëåíèÿ âûïóêëûõ îáîëî÷åê èõ íåïåðåñåêàþùèõñÿ e-ñåòåé. Ñôîðìóëèðóåì îñíîâíóþ òåîðåìó äàííîé ñòàòüè. Òåîðåìà 1. ×òîáû ìíîæåñòâà A è B áûëè e-ðàçäåëèìûìè, íåîáõîäèìî è äîñòà- òî÷íî ñóùåñòâîâàíèÿ e eA B, è ñîîòâåòñòâóþùèõ èì e-ñåòîê N A A e , N B B e â ( , )R H d d , äëÿ êîòîðûõ âûïîëíÿþòñÿ ñîîòíîøåíèÿ e e eA A B B A Bn n n n+ < +( ) , (3) conv convN N A B A B e e Ç = Æ . (4) 148 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5 Äîêàçàòåëüñòâî. Íåîáõîäèìîñòü. Ïðåäïîëîæèì, ÷òî ìíîæåñòâà A è B e-ðàçäåëèìû. Îáîçíà÷èì | |A nA1 1 = , | |B nB1 1 = . Ïóñòü e dA A A n n = + 1 , e dB B B n n = + 1 , ãäå d âûáðàíî èç óñëîâèÿ ( ) ( )n n n nA B A B1 1 2+ + < +d e . Òîãäà â êà÷åñòâå ñåòåé ìîæíî èñïîëüçîâàòü N A A A A e = \ 1, N B B B B e = \ 1. Ñîãëàñíî (1) âûïîëíÿåòñÿ ñîîò- íîøåíèå (4), ñîãëàñíî (2) — íåðàâåíñòâî (3). Äîñòàòî÷íîñòü. Ïðåäïîëîæèì, ÷òî âûïîëíÿþòñÿ óñëîâèÿ (3), (4) òåîðåìû 1. Äîêàæåì, ÷òî ìíîæåñòâà A è B ÿâëÿþòñÿ e-ðàçäåëèìûìè. Ïóñòü ìíîæåñòâà A è B íå ÿâëÿþòñÿ e-ðàçäåëèìûìè. Ýòî çíà÷èò, ÷òî óñëîâèå (1) ìîæåò âûïîëíÿòüñÿ òîëüêî â òîì ñëó÷àå, êîãäà n n n nA B A B1 1 + ³ +e( ) . (5) Ïîñêîëüêó âûïîëíÿåòñÿ ñîîòíîøåíèå (4), òî äëÿ conv N A A e è conv N B B e ñóùå- ñòâóåò ðàçäåëÿþùàÿ ãèïåðïëîñêîñòü. Ïðåäïîëîæèì, ÷òî conv N L A A e Î + è conv N L B B e Î - . Îáîçíà÷èì A x A x L N = Î Î +{ : } , B x B x L N = Î Î -{ : } . Ìíîæåñò- âà A A N\ è B B N\ ñîãëàñíî îïðåäåëåíèþ e-ñåòåé óäîâëåòâîðÿþò ñîîòíîøåíèÿì | \ |A A n N A A< e , | \ |B B n N B B< e . Ðàññìîòðèì ìíîæåñòâà, êîòîðûå èñêëþ÷àåì: A A A B B B N N 1 1= =\ , \ . Òîãäà äëÿ ýòèõ ìíîæåñòâ ñîãëàñíî óñëîâèþ (3) n n n nA B A B1 1 + < +e ( ) . Òàêèì îáðàçîì, íåðàâåíñòâî (5) äëÿ äàííûõ ìíîæåñòâ íå âûïîëíÿåòñÿ. Ïîëó÷àåì ïðîòèâîðå÷èå. Äîñòàòî÷íîñòü äîêàçàíà. Òåîðåìà 1 äîêàçàíà. Ââåäåì îáîçíà÷åíèÿ h A B A A n = Ç| |conv , h B A B B n = Ç| |conv è e hA A An = + 1 , e hB B Bn = + 1 . Òåîðåìà 2. Ïóñòü e h h > + + A A B B A B n n n n , òîãäà äëÿ ëþáîé e-ðàçäåëÿþùåé ãèïåðïëîñêîñòè Le ìíîæåñòâ A è B ñóùåñòâó- þò e-ñåòè N A A e è N B B e , äëÿ êîòîðûõ Le — ðàçäåëÿþùàÿ ãèïåðïëîñêîñòü. Äîêàçàòåëüñòâî. Áóäåì ñòðîèòü e-ñåòü N A A e òàêèì îáðàçîì, ÷òîáû â íåå íå ïîïàëè òå òî÷êè ìíîæåñòâà A , êîòîðûå ïðèíàäëåæàò âûïóêëîé îáîëî÷êå conv B . Ïîñêîëüêó e hA A> , òî " Ç ³r r A nA A: | | e ñóùåñòâóåò òî÷êà x òàêàÿ, ÷òî x r AÎ Ç( ) , íî x BÏconv . Ïðè ïîñòðîåíèè e-ñåòè N A A e â êà÷åñòâå ïðåäñòàâèòåëÿ ìíîæåñòâà r áóäåì èñïîëüçîâàòü òî÷êó x òàêóþ, ÷òî x BÏconv . Áëàãîäàðÿ ïîëó- ïðîñòðàíñòâàì r, äëÿ êîòîðûõ | |r A nA AÇ = +h 1 è | ( ) |r A nB A AÇ Ç =conv h , e-ñåòü N A A e ñîäåðæèò âñå òå òî÷êè ìíîæåñòâà A , êîòîðûå ÿâëÿþòñÿ áëèæàéøèìè ñîñåäÿìè ê ïåðåñå÷åíèþ A BÇconv . Ïîñêîëüêó e-ñåòè N A A e è N B B e ñîäåðæàò âñåõ áëèæàéøèõ ñîñåäåé ê ïåðåñå÷å- íèÿì A BÇconv è B AÇconv è íå ñîäåðæàò òî÷åê, ïðèíàäëåæàùèõ ýòèì ïåðåñå÷å- íèÿì, ìîæíî óòâåðæäàòü, ÷òî ñðåäè ðàçäåëÿþùèõ ãèïåðïëîñêîñòåé äëÿ ìíîæåñòâ N A A e è N B B e íàéäåòñÿ ãèïåðïëîñêîñòü, êîòîðàÿ e-ðàçäåëÿåò ìíîæåñòâà A è B. Òåîðåìà 2 äîêàçàíà. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5 149 Èòàê, çàäà÷ó e-ðàçäåëåíèÿ äâóõ ïåðåñåêàþùèõñÿ ìíîæåñòâ (A è B) ìîæíî ñâåñòè ê òðèâèàëüíîé çàäà÷å ðàçäåëåíèÿ äâóõ âûïóêëûõ íåïåðåñåêàþùèõñÿ ìíî- æåñòâ (convN A A e è convN B B e ). Îáîçíà÷èì n N A A A e e = | | , n N B B B e e = | | . Ïîñêîëüêó ñëîæíîñòü àëãîðèòìà ïîèñ- êà e-ñåòè ëèíåéíàÿ [13], à ïîñòðîåíèå âûïóêëûõ îáîëî÷åê äëÿ e-ñåòåé N A A e è N B B e , íàïðèìåð, ìåòîäîì Äæàðâèñà îöåíèâàåòñÿ êàê O n A ( ) e 2 è O n B ( ) e 2 [14], òî îáùóþ ñëîæíîñòü àëãîðèòìà e-ðàçäåëåíèÿ ìíîæåñòâ A è B ñ èñïîëüçîâàíèåì e-ñåòåé ìîæíî îöåíèòü êàê O m m( )+ e 2 , ãäå m n nA B= max( , ) , m n n A Be e e= max( , ). Òàêèì îáðàçîì, äîêàçàíî, ÷òî äëÿ e-ðàçäåëèìîñòè äâóõ ìíîæåñòâ íåîáõîäè- ìî è äîñòàòî÷íî ñóùåñòâîâàíèÿ íåêîòîðûõ ðàçäåëèìûõ e-ñåòåé ýòèõ ìíîæåñòâ. Ïðåäëîæåí ìåòîä ïîñòðîåíèÿ ðàçäåëèìûõ e-ñåòåé è ïîêàçàíî, ÷òî çàäà÷ó ðàçäå- ëåíèÿ äâóõ ïåðåñåêàþùèõñÿ ìíîæåñòâ ìîæíî ñâåñòè ê çàäà÷å ðàçäåëåíèÿ äâóõ íåïåðåñåêàþùèõñÿ âûïóêëûõ ìíîæåñòâ. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. F i s h e r R . A . The use of multiple measurements in taxonomic problems // Annals of Eugenics. — 1936. — N 7. — P. 179–188. 2. D e n g C a i , X i a o f e i H e , J i a w e i H a n . Training linear discriminant analysis in linear time. — http://researchweb.iiit.ac.in/~nataraj.j/poseSearchReports/icde08_dengcai.pdf. 3. À é â à ç ÿ í Ñ . À . , Á ó õ ø ò à á å ð  . Ì . , Å í þ ê î â È . Ñ . , Ì å ø à ë ê è í Ë . Ä . Ïðèêëàäíàÿ ñòàòèñòèêà: êëàññèôèêàöèÿ è ñíèæåíèå ðàçìåðíîñòè. — Ì.: Ôèíàíñû è ñòàòèñòèêà, 1989. — 607 ñ. 4.  î ð î í ö î â Ê .  . Ëåêöèè ïî ñòàòèñòè÷åñêèì (áàéåñîâñêèì) àëãîðèòìàì êëàññèôèêàöèè: http:www.ccas.ru/voron/download/Bayes.pdf. 5. C h r i s F l e i z a c h , S a t o r u F u k u s h i m a . A naive Bayes classifier on 1998 KDD Cup. — http://sysnet.ucsd.edu/~cfleizac/cse250b/project1.pdf. 6. V a p n i k V . N . The nature of statistical learning theory. — 2nd ed. — New York: Springer, 2000. — 314 p. 7.  î ð î í ö î â  . Ê . Ëåêöèè ïî ìåòîäó îïîðíûõ âåêòîðîâ. — http://www.ccas.ru/voron/download/ SVM.pdf. 8. I v o r W . T s a n g , J a m e s T . K w o k , P a k - M i n g C h e u n g . Core vector machines: fast SVM training on very large data sets // Journal of Machine Learning Research. — 2005. — N 6. — Ð. 363–392. 9. È â à í ÷ ó ê Ì . À . , Ì à ë û ê È .  . Ñðàâíåíèå ìåòîäîâ ðàñïðåäåëåíèÿ íàáëþäåíèé íà êëàññû ïðè ïðîãíîçèðîâàíèè íàëè÷èÿ îñëîæíåíèé ó òÿæåëîáîëüíûõ // Êèáåðåíòèêà è ñèñòåìíûé àíà- ëèç. — 2015. — 51, ¹ 2. — Ñ. 164–174. 10. Ð à é ã î ð î ä ñ ê è é À . Ì . Ñèñòåìû îáùèõ ïðåäñòàâèòåëåé â êîìáèíàòîðèêå è èõ ïðèëîæåíèÿ â ãåîìåòðèè. — Ì.: ÌÖÍÌÎ, 2009. — 136 ñ. 11. Ä à í ö å ð Ë . , à ð þ í á à ó ì Á . , Ê ë è  . Òåîðåìà Õåëëè. — Ì.: Ìèð, 1968. — 162 ñ. 12. H a u s s l e r D . , W e l z l E . e-nets and simplex range queries // Discrete & Computational Geometry. — 1987. — N 2. — P. 127–151. 13. I C S Theory Group. Computational Statistics. — https://www.ics.uci.edu/~eppstein/280/cluster.html. 14. Ï ð å ï à ð à ò à Ô . , Ø å é ì î ñ Ì . Âû÷èñëèòåëüíàÿ ãåîìåòðèÿ: Ââåäåíèå.  — Ì.: Ìèð, 1989.  — Ñ.  478. Ïîñòóïèëà 27.04.2015 150 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5

Ähnliche Einträge