Решение задачи классификации с использованием ε-сетей
Предложен новый метод решения задачи классификации, основанный на разделении двух множеств в пространстве Rd путем построения и разделения ε-сетей этих множеств в ранжированном пространстве относительно гиперплоскостей. Введено понятие области разделения — тех значений ε, при которых возможно разд...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2016 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2016
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/142005 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Решение задачи классификации с использованием ε-сетей / М.А. Иванчук, И.В. Малык // Кибернетика и системный анализ. — 2016. — Т. 52, № 4. — С. 134-144. — Бібліогр.: 24 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860128445895278592 |
|---|---|
| author | Иванчук, М.А. Малык, И.В. |
| author_facet | Иванчук, М.А. Малык, И.В. |
| citation_txt | Решение задачи классификации с использованием ε-сетей / М.А. Иванчук, И.В. Малык // Кибернетика и системный анализ. — 2016. — Т. 52, № 4. — С. 134-144. — Бібліогр.: 24 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Предложен новый метод решения задачи классификации, основанный на разделении двух множеств в пространстве Rd путем построения и разделения ε-сетей этих множеств в ранжированном пространстве относительно гиперплоскостей. Введено понятие области разделения — тех значений ε, при которых возможно разделить множества. Приведены примеры области разделения для случайных величин с разными распределениями и доказана теорема о ее сходимости. Введено понятие совокупности всех возможных ε-сетей некоторого множества и доказаны ее свойства. Доказана слабая сходимость нормированной разности эмпирической и теоретической кривых разделения к нормальному распределению, что позволяет проверять гипотезы о местонахождении теоретической кривой разделения в конкретной точке.
Запропоновано новий метод розв’язання задачі класифікації, що базується на відокремленні двох множин в просторі Rd шляхом побудови та відокремлення ε-сіток цих множин в ранжованому просторі відносно гіперплощин. Введено поняття області поділу — тих значень ε, при яких можливо відокремити множини. Наведено приклади області поділу для випадкових величин, розподілених за найбільш вживаними законами розподілу, та доведено теорему про її збіжність. Введено поняття сукупності всіх можливих ε-сіток деякої множини та доведено деякі її властивості. Доведена слабка збіжність нормованої різниці емпіричної та теоретичної кривих відокремлення до нормального розподілу, що дозволяє перевіряти гіпотези про місцезнаходження теоретичної кривої відокремлення в конкретній точці.
The new method of the solution the classification problem is proposed in the paper. The method is based on separating two sets in the space Rd by constructing and separating ε-nets of these sets in a ranked space with respect to hyperplanes. The concept of the set of possible values of ε for ε-nets of both sets is introduced in the paper. The properties of this set and the theorem of its convergence are proved. The paper contains examples of the set of possible values for the most useful distributions. The concept of the set of all possible ε-nets of the set is introduced in the paper. Weak convergence of the normalized difference of the empiric and theoretic separation curves to the normal distribution is proved. It makes possible to check the hypothesis of the place of theoretic separation curve at a specific point.
|
| first_indexed | 2025-12-07T17:43:29Z |
| format | Article |
| fulltext |
ÓÄÊ [519.245+519.214]: 519.237.8
Ì.À. ÈÂÀÍ×ÓÊ, È.Â. ÌÀËÛÊ
ÐÅØÅÍÈÅ ÇÀÄÀ×È ÊËÀÑÑÈÔÈÊÀÖÈÈ
Ñ ÈÑÏÎËÜÇÎÂÀÍÈÅÌ �-ÑÅÒÅÉ
Àííîòàöèÿ. Ïðåäëîæåí íîâûé ìåòîä ðåøåíèÿ çàäà÷è êëàññèôèêàöèè, îñíî-
âàííûé íà ðàçäåëåíèè äâóõ ìíîæåñòâ â ïðîñòðàíñòâå Rd ïóòåì ïîñòðîåíèÿ
è ðàçäåëåíèÿ �-ñåòåé ýòèõ ìíîæåñòâ â ðàíæèðîâàííîì ïðîñòðàíñòâå îòíîñè-
òåëüíî ãèïåðïëîñêîñòåé. Ââåäåíî ïîíÿòèå îáëàñòè ðàçäåëåíèÿ — òåõ çíà÷å-
íèé �, ïðè êîòîðûõ âîçìîæíî ðàçäåëèòü ìíîæåñòâà. Ïðèâåäåíû ïðèìåðû
îáëàñòè ðàçäåëåíèÿ äëÿ ñëó÷àéíûõ âåëè÷èí ñ ðàçíûìè ðàñïðåäåëåíèÿìè è
äîêàçàíà òåîðåìà î åå ñõîäèìîñòè. Ââåäåíî ïîíÿòèå ñîâîêóïíîñòè âñåõ âîç-
ìîæíûõ �-ñåòåé íåêîòîðîãî ìíîæåñòâà è äîêàçàíû åå ñâîéñòâà. Äîêàçàíà
ñëàáàÿ ñõîäèìîñòü íîðìèðîâàííîé ðàçíîñòè ýìïèðè÷åñêîé è òåîðåòè÷åñêîé
êðèâûõ ðàçäåëåíèÿ ê íîðìàëüíîìó ðàñïðåäåëåíèþ, ÷òî ïîçâîëÿåò ïðîâåðÿòü
ãèïîòåçû î ìåñòîíàõîæäåíèè òåîðåòè÷åñêîé êðèâîé ðàçäåëåíèÿ â êîíêðåò-
íîé òî÷êå.
Êëþ÷åâûå ñëîâà: �-ñåòè, ðàçäåëåíèå ìíîæåñòâ, ðàçìåðíîñòü Âàïíèêà–
×åðâîíåíêèñà, êëàññèôèêàöèÿ.
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È
 1987 ã. D. Haussler è E. Welzl [1] ââåëè ïîíÿòèå �-ñåòåé. Ñ ýòîãî âðåìåíè
äàííîå íàïðàâëåíèå ñòàëî îäíèì èç ïåðñïåêòèâíûõ â âû÷èñëèòåëüíîé è êîì-
áèíàòîðíîé ãåîìåòðèè è ïîëó÷èëî øèðîêîå ïðèìåíåíèå [2–6]. Ðàññìîòðèì
ðàíæèðîâàííîå ïðîñòðàíñòâî ( , )X R , ãäå X — íåêîòîðîå ìíîæåñòâî, R — ñî-
âîêóïíîñòü ïîäìíîæåñòâ ìíîæåñòâà X .  ãåîìåòðè÷åñêîì êîíòåêñòå â êà÷åñò-
âå ìíîæåñòâà X ïðèíèìàþò åâêëèäîâî ïðîñòðàíñòâî R d , ïðè ýòîì ñîâîêóï-
íîñòüþ ïîäìíîæåñòâ R â òàêîì ïðîñòðàíñòâå ìîæåò áûòü, íàïðèìåð, H d —
ñîâîêóïíîñòü âñåõ ïîäïðîñòðàíñòâ; ñîâîêóïíîñòü âñåõ øàðîâ; ñîâîêóïíîñòü
âñåõ âûïóêëûõ îáîëî÷åê; ñîâîêóïíîñòü âñåõ d-ìåðíûõ ñèìïëåêñîâ [2]; ñîâî-
êóïíîñòü âñåõ ïðÿìîóãîëüíèêîâ, ïàðàëëåëüíûõ îñÿì êîîðäèíàò; ñîâîêóïíîñòü âñåõ
òðåóãîëüíèêîâ [3]; ñîâîêóïíîñòü âñåõ êëèíîâ, îáðàçîâàííûõ ïåðåñå÷åíèåì äâóõ íå-
ïàðàëëåëüíûõ ïîëóïðîñòðàíñòâ, óãîë ìåæäó êîòîðûìè íå ìåíüøå � ðàäèàí [4].
Òåîðèÿ �-ñåòåé äëÿ îäíîãî ìíîæåñòâà íà äàííûé ìîìåíò õîðîøî ðàçâèòà. Òàê,
íàïðèìåð, B. Aronov ñ ñîàâòîðàìè [5] ïîêàçàëè, ÷òî äëÿ ïðÿìîóãîëüíèêîâ, ïàðàë-
ëåëüíûõ îñÿì êîîðäèíàò, ðàçìåð �-ñåòè â R 2 îöåíèâàåòñÿ êàê O
1 1
� �
log log
�
�
�
�
�
� .
J. Kulkarni ñ ñîàâòîðàìè [4] äîêàçàëè, ÷òî äëÿ êëèíîâ òîëùèíîé � â R 2 ñóùåñòâó-
þò �-ñåòè ðàçìåða O
�
��
�
�
�
�
�
� . B. G��artner [2] äîêàçàë ñóùåñòâîâàíèå �-ñåòåé ìîùíîñ-
òüþ íå áîëåå
d nln
�
�
�
� , ãäå d — ðàçìåðíîñòü Âàïíèêà–×åðâîíåíêèñà [3].
J. Matousek [6] â 2000 ã. äîêàçàë, ÷òî åñëè äëÿ êàæäîãî êîíå÷íîãî ìíîæåñòâà
T R� 3 â âûïóêëîé ïîçèöèè ñóùåñòâóåò �-ñåòü äëÿ ïîëóïðîñòðàíñòâ ðàçìåðà
s( )� , òî äëÿ ëþáîãî êîíå÷íîãî ìíîæåñòâà â R 3 ñóùåñòâóåò �-ñåòü â ðàíæèðîâàí-
íîì ïðîñòðàíñòâå ( , )R Hd d ðàçìåðà 3 1s( )�
.
134 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 4
© Ì.À. Èâàí÷óê, È.Â. Ìàëûê, 2016
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 4 135
 íàñòîÿùåé ñòàòüå ðàññìàòðèâàåòñÿ çàäà÷à êëàññèôèêàöèè äâóõ ìíîæåñòâ,
êîòîðûå ñãåíåðèðîâàíû íåçàâèñèìûìè ñëó÷àéíûìè âåëè÷èíàìè. Ïóñòü èç ãåíå-
ðàëüíûõ ñîâîêóïíîñòåé, ñãåíåðèðîâàííûõ ñëó÷àéíûìè âåëè÷èíàìè � è � , ïîëó-
÷åíû âûáîðêè A è B îáúåìàìè nA , nB . Çàäà÷à ñîñòîèò â íàõîæäåíèè ðàçäåëÿþ-
ùåé ãèïåðïëîñêîñòè L , äëÿ êîòîðîé ñïðàâåäëèâî ñîîòíîøåíèå
P L L P l l
l H d
{ } sup { }� � � �� � � � �
�
�
�, ,
è îöåíêè âåðîÿòíîñòè P L Ln n n n{ }� �� �
�, , ãäå Ln — ãèïåðïëîñêîñòü, ðàçäå-
ëÿþùàÿ ìíîæåñòâà �n A� , � n B� .
Çàäà÷è êëàññèôèêàöèè øèðîêî èñïîëüçóþòñÿ âî ìíîãèõ îòðàñëÿõ, â òîì ÷èñ-
ëå â ýêîíîìèêå [7, 8], ìåäèöèíå [9–13], ïîëèòîëîãèè [14–16] . Äëÿ ðåøåíèÿ ýòîãî
êëàññà çàäà÷ ñóùåñòâóåò áîëüøîå êîëè÷åñòâî ìåòîäèê. Ñðàâíèòåëüíûé àíàëèç
èñïîëüçîâàíèÿ äèñïåðñèîííîãî àíàëèçà, êëàñòåðíîãî àíàëèçà, âàëüäîâñêîé êëàñ-
ñèôèêàöèè äëÿ ðåøåíèÿ çàäà÷ êëàññèôèêàöèè ïðè ïðîãíîçèðîâàíèè â ìåäèöèíå
ïðèâåäåí â [17].
 íàñòîÿùåé ñòàòüå äëÿ ðåøåíèÿ çàäà÷è êëàññèôèêàöèè èñïîëüçóåòñÿ òåîðèÿ
�-ñåòåé.  îòëè÷èå îò ðàáîò [1–6], êàñàþùèõñÿ ïîñòðîåíèÿ �-ñåòåé îäíîãî ìíî-
æåñòâà, â äàííîé ñòàòüå ðàññìàòðèâàþòñÿ �-ñåòè äâóõ ìíîæåñòâ â ðàíæèðîâàííîì
ïðîñòðàíñòâå ( , )R Hd d . Îïèñàíî ìíîæåñòâî âîçìîæíûõ çíà÷åíèé � äëÿ äâóõ
ðàçäåëèìûõ �-ñåòåé, äîêàçàíû åãî ñâîéñòâà. Ïðèâåäåíû ïðèìåðû ìíîæåñòâà âîç-
ìîæíûõ çíà÷åíèé � äëÿ íîðìàëüíîãî, ýêñïîíåíöèàëüíîãî, ðàâíîìåðíîãî
è ïóàññîíîâñêîãî çàêîíîâ ðàñïðåäåëåíèÿ.
�-ÐÀÇÄÅËÈÌÎÑÒÜ ÄÂÓÕ ÌÍÎÆÅÑÒÂ Â ÏÐÎÑÒÐÀÍÑÒÂÅ R
d
Îïðåäåëåíèå 1. Ìíîæåñòâà A è B îáúåìàìè n nA B, íàçûâàþòñÿ �-ðàçäåëèìû-
ìè, åñëè ñóùåñòâóþò A A1 � , B B1 � , äëÿ êîòîðûõ conv( \ )A A1 �
� ��conv( \ )B B1 è | | | | ( )A B n nA B1 1
�
� .
Îïðåäåëåíèå 2. Ãèïåðïëîñêîñòü L íàçûâàåòñÿ ðàçäåëÿþùåé äëÿ ìíîæåñòâ
A è B, åñëè conv A L�
, conv B L� � .
Îïðåäåëåíèå 3. Ãèïåðïëîñêîñòü L� íàçûâàåòñÿ �-ðàçäåëÿþùåé äëÿ ìíî-
æåñòâ A è B, åñëè
| | | |
| | | |
A L B L
A B
�
�
� �
�
� � �1 .
 [18] áûëè äîêàçàíû íåîáõîäèìûå è äîñòàòî÷íûå óñëîâèÿ ñóùåñòâîâàíèÿ
�-ñåòåé ýòèõ ìíîæåñòâ.
Òåîðåìà 1. Äëÿ òîãî ÷òîáû ìíîæåñòâà A è B áûëè �-ðàçäåëèìûìè, íåîáõî-
äèìî è äîñòàòî÷íî, ÷òîáû ñóùåñòâîâàëè �A , �B è ñîîòâåòñòâóþùèå èì �-ñåòè
N
A
A�
, N
B
B�
ìíîæåñòâ A è B â ( , )R Hd d , äëÿ êîòîðûõ âûïîëíÿëèñü ñëåäóþùèå
ñîîòíîøåíèÿ:
� � �A A B B A Bn n n n
�
( ) , (1)
conv convN N
A B
A B� �� �� . (2)
ÎÁËÀÑÒÜ ÐÀÇÄÅËÅÍÈß È ÅÅ ÑÂÎÉÑÒÂÀ
Îïðåäåëåíèå 4. Ìíîæåñòâî
D N N N NA B A B A B, ( , ) ( , ) : , ,� � � � �{ conv conv� �
� � � �
1 2
20 1 1 2 1 2 �} (3)
íàçûâàåòñÿ îáëàñòüþ ðàçäåëåíèÿ.
Î÷åâèäíî, ÷òî äëÿ ëþáûõ � �A B A BD, ,� âûïîëíÿåòñÿ óñëîâèå (2) òåîðåìû 1.
Ñëåäîâàòåëüíî, äëÿ òîãî ÷òîáû ìíîæåñòâà A è B áûëè �-ðàçäåëèìûìè, íåîáõîäèìî
ïðîâåðèòü ñóùåñòâîâàíèå ( , ) ,� �A B A BD� , äëÿ êîòîðûõ âûïîëíÿåòñÿ óñëîâèþ (1).
Äëÿ ýòîãî äîñòàòî÷íî ïîêàçàòü, ÷òî ( , )
( , ) ,
� �
� �
� �
A B
D
A A B B
A BA B A B
n n
n n
0 0 �
�
argmin óäîâëåò-
âîðÿåò óñëîâèþ (1). Åñëè óñëîâèå (1) íå âûïîëíÿåòñÿ äëÿ ( , )� �
A B
0 0 , òî îíî íå áó-
äåò âûïîëíÿòüñÿ äëÿ âñåõ ( , ) ,� �A B A BD� , ò.å. ìíîæåñòâà A è B �-íåðàçäåëèìû.
Ïðåäïîëîæèì, ÷òî ñëó÷àéíûå âåëè÷èíû � �, �R 1 — íåïðåðûâíûå ñëó÷àé-
íûå âåëè÷èíû ñ ôóíêöèÿìè ðàñïðåäåëåíèÿ F F� �, .
Îïðåäåëåíèå 5. Ìíîæåñòâî Dl òàêîå, ÷òî
D x y h R P h x P h yl : ( , ) ( , ) : , { } , { }� � � � � � � �
�{ }0 1 2 1 � � , (4)
íàçûâàåòñÿ îáëàñòüþ ðàçäåëåíèÿ äëÿ � �, .
Äëÿ ìíîæåñòâà Dl èìååò ìåñòî ñëåäóþùåå óòâåðæäåíèå.
Ëåììà 1. Ïóñòü ñóùåñòâóåò îáðàòíàÿ ôóíêöèÿ ê F� . Òîãäà ìíîæåñòâà Dl è
D Dl : ( , ) \� 01 2 ðàçäåëåíû êðèâîé
y x F F x F F x( ) min ( ( ( )), ( ( )))� � �� �
� � � �
1 11 1 . (5)
Äîêàçàòåëüñòâî. Ðàññìîòðèì äâà âîçìîæíûõ ñëó÷àÿ.
1. Ïóñòü äëÿ íåêîòîðîãî h� �� �( , ): F h F h� �( ) ( )� , òîãäà ìíîæåñòâî Dl
ìîæíî îïèñàòü ñèñòåìîé íåðàâåíñòâ
x F h
y F h
� �
�
�
�
�
1 �
�
( ),
( ).
Òîãäà êðèâàÿ, ðàçäåëÿþùàÿ ìíîæåñòâà Dl è Dl , èìååò âèä
y x F F x( ) ( ( ))� ��
� �
1 1 .
2. Ïóñòü äëÿ íåêîòîðîãî h� �� �( , ): F h F h� �( ) ( )� , òîãäà ìíîæåñòâî Dl
ìîæíî îïèñàòü ñèñòåìîé íåðàâåíñòâ
x F h
y F h
�
� �
�
�
�
�
�
( ),
( ).1
 ýòîì ñëó÷àå êðèâàÿ, ðàçäåëÿþùàÿ ìíîæåñòâà Dl è Dl , èìååò âèä
y x F F x( ) ( ( ))� � �1 1
� �
.
Òàêèì îáðàçîì, â îáùåì ñëó÷àå ìíîæåñòâà Dl è Dl ðàçäåëÿþòñÿ êðèâîé
y x F F x F F x( ) min( ( ( )), ( ( )))� � �� �
� � � �
1 11 1 .
Ëåììà 1 äîêàçàíà.
Çàìå÷àíèå 1. Óñëîâèå ëåììû ìîæåò áûòü çàìåíåíî ñóùåñòâîâàíèåì îáðàò-
íîé ôóíêöèè F�
�1 . Òîãäà ðàçäåëÿþùàÿ êðèâàÿ áóäåò èìåòü âèä
x y F F y F F y( ) min ( ( ( )), ( ( )))� � �� �
� � � �
1 11 1 .
136 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 4
Ðàññìîòðèì îáùèé ñëó÷àé, êîãäà ôóíêöèè ðàñïðåäåëåíèÿ íå îáÿçàòåëüíî
èìåþò îáðàòíûå. Âîñïîëüçóåìñÿ ïîíÿòèåì îáîáùåííîé îáðàòíîé ôóíêöèè [19].
Îïðåäåëåíèå 6. Äëÿ âîçðàñòàþùåé ôóíêöèè T R R: � ïðè T T xx( ) lim ( )�� � ���
è T T xx( ) lim ( )� � �� îáîáùåííîé îáðàòíîé ôóíêöèåé íàçûâàåòñÿ
T y x R T x y y R
G
� � � � �1 ( ) : ( ) ,inf { } , (6)
ïðè óñëîâèè, ÷òî inf � � � . Åñëè T R: [ , ]� 0 1 — ôóíêöèÿ ðàñïðåäåëåíèÿ, òî
T R
G
� �1 0 1: [ , ] òàêæå íàçûâàåòñÿ êâàíòèëüíîé ôóíêöèåé T .
Òîãäà èìååò ìåñòî ñëåäóþùåå óòâåðæäåíèå.
Ëåììà 2. Ìíîæåñòâà Dl è D Dl : ( , ) \� 01 2 ðàçäåëåíû êðèâîé
y x F F x F F x
G G
( ) min ( (( ) ( )), (( ) ( )))� � �� �
� � � �
1 11 1 . (7)
Äîêàçàòåëüñòâî. Ïóñòü x�( ; )0 1 — íåêîòîðàÿ òî÷êà, äëÿ êîòîðîé íå ñóùåñòâóåò
F
�
�1 . Íàéäåì çíà÷åíèÿ ôóíêöèè y x( ) (ñì. (7)). Òîãäà ñîãëàñíî îïðåäåëåíèþ îáîáùåí-
íîé îáðàòíîé ôóíêöèè äëÿ ëþáîãî �� 0 ñïðàâåäëèâà ïðèíàäëåæíîñòü y x Dl( )
�� ,
y x Dl( ) � �� . Òàêèì îáðàçîì, ìíîæåñòâà Dl è Dl ðàçäåëåíû êðèâîé (6).
Ëåììà 2 äîêàçàíà.
ÏÐÈÌÅÐÛ ÏÎÑÒÐÎÅÍÈß ÎÁËÀÑÒÈ ÐÀÇÄÅËÅÍÈß
Ðàññìîòðèì ïðèìåðû îáëàñòè ðàçäåëåíèÿ äëÿ íàèáîëåå ÷àñòî èñïîëüçóåìûõ
ðàñïðåäåëåíèé.
Ïðèìåð 1. Ïóñòü ñëó÷àéíûå âåëè÷èíû � è � ðàñïðåäåëåíû ïî íîðìàëüíîìó
çàêîíó ñ ïàðàìåòðàìè � � �, è � � �, . Òîãäà îáëàñòü Dl îãðàíè÷åíà ôóíêöèåé
y x
x
G
( ) min�
� ��
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
�
�
�
�
�
�
��
�
�
� 1 1 �
�
�
�
�
�
, 1
1
�
��
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
�
�
�
�
�
�
��
�
�
�
�
�
�
�
�
�
�
G
x �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�, ( , )x 0 1 .
Íà ðèñ.1 èçîáðàæåí ãðàôèê ôóíêöèè y y x� ( ) äëÿ � � �� �3 1, è
� � �� �5 2, .
Ïðèìåð 2. Ïóñòü ñëó÷àéíûå âåëè÷èíû � è � ðàñïðåäåëåíû ïî ýêñïîíåíöè-
àëüíîìó çàêîíó ñ ïàðàìåòðàìè �� è �� . Îáëàñòü Dl îãðàíè÷åíà ñíèçó ôóíêöèåé
y x x x x( ) min ( , ( ) ), ( , )� � � �1 1 0 1
� � � �� � � � .
Íà ðèñ. 2 èçîáðàæåí ãðàôèê ôóíêöèè y y x� ( ) äëÿ �� �1 è �� � 5 .
Ïðèìåð 3. Ïóñòü ñëó÷àéíûå âåëè÷èíû � è � ðàñïðåäåëåíû ïî ðàâíîìåðíîìó
çàêîíó ñ ïàðàìåòðàìè a b� �, è a b� �, . Îáëàñòü Dl îãðàíè÷åíà ñíèçó ôóíêöèåé
y x
b x a x a
b a
a x b x a
b a
( ) min
( )
,
( )
�
�
�
�
�
�
�
�
� � � �
� �
� � �
� �
1
1
1
�
�
�
�
�
�
�
�, ( , )x 0 1 .
Íà ðèñ. 3 èçîáðàæåí ãðàôèê ôóíêöèè y y x� ( ) äëÿ a b� �� �1 5, è a b� �� �4 7, .
Ïðèìåð 4. Ïóñòü äèñêðåòíûå ñëó÷àéíûå âåëè÷èíû � �, ðàñïðåäåëåíû ïî çà-
êîíó Ïóàññîíà ñ ïàðàìåòðàìè
� �, . Íà ðèñ. 4 èçîáðàæåí ãðàôèê ôóíêöèè
y y x� ( ) äëÿ
� �1 ,
� � 2 ïðè x�( ; )0 1 .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 4 137
Ïðèìåð 5. Ïóñòü ñëó÷àéíàÿ âåëè-
÷èíà � ðàñïðåäåëåíà ïî ðàâíîìåðíîìó
çàêîíó ñ ïàðàìåòðàìè a b� �, , à ñëó÷àé-
íàÿ âåëè÷èíà � ðàñïðåäåëåíà ïî íîð-
ìàëüíîìó çàêîíó ñ ïàðàìåòðàìè � � �, .
Òîãäà îáëàñòü Dl îãðàíè÷åíà ôóíêöèåé
y x
b x a x
( ) min
( )
,�
�
��
�
�
�
�
�
�
�
�
�
�
�
�
� � �
�
�
1
1
1
0 1�
� ��
�
�
�
�
�
�
�
�
�
�
�
��
b x a x
x
� � �
�
�
( )
, ( , ) .
Íà ðèñ. 5 èçîáðàæåí ãðàôèê ôóíêöèè
y y x� ( ) äëÿ a b� �� �1 5, è �� � 7, � �1 .
ÑÎÂÎÊÓÏÍÎÑÒÈ �-ÑÅÒÅÉ È ÈÕ ÑÂÎÉÑÒÂÀ
Îáîçíà÷èì D N N N NA B A B A B, ( , ) ( , ) : , ,� � � !{ conv conv� �
� � � �
1 2
201 1 2 1 2 �} .
Îïðåäåëåíèå 7. Ìíîæåñòâî X íàçûâàåòñÿ çâåçäíûì, åñëè � �x X0 �x X ,
�� [ , ]0 1 : � �x0 1
�( ) x X� [20].
Òî÷êó x0 áóäåì íàçûâàòü öåíòðàëüíîé òî÷êîé çâåçäíîé îáëàñòè.
Äîêàæåì, ÷òî ìíîæåñòâà DA B, è DA B, ÿâëÿþòñÿ çâåçäíûìè. Äëÿ ýòîãî ââåäåì
ïîíÿòèå ñîâîêóïíîñòè âñåõ âîçìîæíûõ �-ñåòåé ìíîæåñòâà è ðàññìîòðèì åãî ñâîéñòâà.
138 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 4
Ðèñ. 1. Ãðàôèê ôóíêöèè y x( ) äëÿ íîðìàëüíîãî
ðàñïðåäåëåíèÿ
Ðèñ. 2. Ãðàôèê ôóíêöèè y x( ) äëÿ ýêñïîíåí-
öèàëüíîãî ðàñïðåäåëåíèÿ
Ðèñ. 4. Ãðàôèê ôóíêöèè y x( ) äëÿ ðàñïðåäåëåíèÿ
Ïóàññîíà
Ðèñ. 3. Ãðàôèê ôóíêöèè y x( ) äëÿ ðàâíîìåð-
íîãî ðàñïðåäåëåíèÿ
y y
y y
x x
x x
Ðèñ. 5. Ãðàôèê ôóíêöèè y x( ) äëÿ ðàâíîìåð-
íîãî è íîðìàëüíîãî ðàñïðåäåëåíèÿ
y
x
Îïðåäåëåíèå 8. Ìíîæåñòâî N
A
� , ñîäåðæàùåå âñå âîçìîæíûå �-ñåòè ìíîæå-
ñòâà A, íàçûâàåòñÿ ñîâîêóïíîñòüþ �-ñåòåé ìíîæåñòâà A .
Íàïðèìåð, äëÿ A � { }1 2 3, , ïðè � � 0 2, ìíîæåñòâî N
A
� ñîäåðæèò òîëüêî A ; äëÿ
� � 0 4, èìååì N
A
A� � { { } { } { }}, , , , , ,1 2 1 3 2 3 .
Ëåììà 3. N N
A A
� �1 2" , åñëè � �1 2� .
Äîêàçàòåëüñòâî. Ïóñòü H
— ïîëóïðîñòðàíñòâî, ïîðîæäàåìîå íåêîòîðîé
ãèïåðïëîñêîñòüþ H . Ñîãëàñíî îïðåäåëåíèþ �-ñåòåé � �
| | | |A H A�1
� � �
x A H : x N
A
� �1 . Ïóñòü � �2 1� , òîãäà åñëè | | | |A H A� �
�2 , òî
| | | |A H A� �
�1 , îòêóäà � # �x N x N
A A
� �1 2 , ò.å. N N
A A
� �1 2" .
Ëåììà 3 äîêàçàíà.
Ââåäåì ñëåäóþùèå îáîçíà÷åíèÿ: A Ai � — ïîäìíîæåñòâî ìíîæåñòâà A , êî-
òîðîå ñîäåðæèò i òî÷åê: A a a ai i� { }1 2, , ..., ; A Ai
�1 — ìíîæåñòâî, ñîäåðæà-
ùåå âñå òî÷êè ìíîæåñòâà Ai è åùå îäíó òî÷êó èç ìíîæåñòâà A:
A A ai i i
� $1 1{ }}{ . Òîãäà ñïðàâåäëèâà ñëåäóþùàÿ ëåììà.
Ëåììà 4. Äëÿ ëþáîãî N
A
j i
i
1
1 �j i1, ñóùåñòâóåò N
A
j i
i
, äëÿ êîòîðîãî âûïîë-
íÿåòñÿ ñîîòíîøåíèå
N N
A
j i
A
j i
i i
"
1
1
.
Äîêàçàòåëüñòâî. Ðàññìîòðèì ìíîæåñòâî N
A
j i
i
, êîòîðîå ÿâëÿåòñÿ ñîâîêóï-
íîñòüþ âñåõ âîçìîæíûõ êîìáèíàöèé òî÷åê èç ìíîæåñòâà Ai ïî i òî÷åê, ïî i�1òî-
÷åê, ..., ïî i j�
1 òî÷åê.  ñâîþ î÷åðåäü, ìíîæåñòâî N
A
j i
i
1
1
— ýòî ñîâîêóïíîñòü
âñåõ âîçìîæíûõ êîìáèíàöèé òî÷åê èç ìíîæåñòâà Ai
1 ïî i
1 òî÷åê, ïî i òî÷åê,
..., ïî i j� òî÷åê. Î÷åâèäíî, ÷òî ñðåäè ýòèõ êîìáèíàöèé òî÷åê íàéäåòñÿ òàêàÿ, ÷òî
íå ñîäåðæèò òî÷êó ai
1 è ïðèíàäëåæèò ìíîæåñòâó N
A
j i
A
j i
i i
�N .
Ëåììà 4 äîêàçàíà.
Ëåììà 5. Ìíîæåñòâà DA B, è DA B, — çâåçäíûå.
Äîêàçàòåëüñòâî.
1. Ðàññìîòðèì òî÷êè x DA B� �( , ) ,� �1 2 è x0 1 1� ( ; ) . Äîêàæåì, ÷òî
� �x x DA B0 1
� �( ) , . Ïóñòü � � � � � � � �x x0 1 1 2 21 1 1
� �
�
�( ) ( ( ), ( )) .
Ïîñêîëüêó � � � �1 1 11�
�( ) , òî ñîãëàñíî ëåììå 1 N N
A A
� � � �1 1 11"
�( )
.
Àíàëîãè÷íî N N
B B
� � � �2 2 21"
�( )
. Ïîñêîëüêó ïî îïðåäåëåíèþ � �N
A A
� �1 1N ,
N
B B
� �2 2�N : conv convN N
A B
� �1 2� �� , òî ñóùåñòâóþò òàêèå �-ñåòè N
A A
� �1 1� "N
"
�N
A
� � �1 11( )
, N
B B B
� � � � �2 2 2 21� "
�N N ( )
, äëÿ êîòîðûõ ñïðàâåäëèâî conv N
A
( )1 1� �� �
� ���
conv N
B
( )1 2� �
.
Òàêèì îáðàçîì, � �x x DA B0 1
� �( ) , , ò.å. ìíîæåñòâî DA B, — çâåçäíîå.
2. Ðàññìîòðèì òî÷êè x DA B� �( , ) ,� �1 2 è x0 0 0� ( ; ). Äîêàæåì, ÷òî
� �x x DA B0 1
� �( ) , . Ïóñòü òàêæå � � � � � �x x0 1 21 1 1
� � � �( ) (( ) , ( ) ).
Ïîñêîëüêó � � �1 11� �( ) , òî ñîãëàñíî ëåììå 1 N N
A A
� � �1 11% �( )
. Àíàëîãè÷íî
N N
B B
� � �2 21% �( )
. Ïîñêîëüêó ïî îïðåäåëåíèþ � �N N
A A B B
� � � �1 1 2 2N N, :
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 4 139
conv convN N
A B
� �1 2� !� , òî äëÿ ëþáûõ N
A A A
( ) ( )1 11 1 1� �� %� � � � �N N è
N
B B B
( ) ( )1 12 2 2� �� %� � � � �N N ñïðàâåäëèâî conv convN N
A B
( ) ( )1 11 2� �� !�� � � �
.
Òàêèì îáðàçîì, � �x x DA B0 1
� �( ) , , ò.å. ìíîæåñòâî DA B, — çâåçäíîå.
Ëåììà 5 äîêàçàíà.
ÀÑÈÌÏÒÎÒÈÊÀ ÐÀÇÄÅËßÞÙÈÕ ÊÐÈÂÛÕ
 ëåììàõ 1, 2 îïèñàíà êðèâàÿ, ðàçäåëÿþùàÿ ìíîæåñòâà D� �, è D� �, . Äîêàæåì
åå ñõîäèìîñòü ñ êðèâîé, ðàçäåëÿþùåé ìíîæåñòâà DA B, è DA B, .
Òåîðåìà 2. Ïóñòü:
1) ìíîæåñòâà A B, îáúåìîì n nA B, ñîîòâåòñòâåííî ãåíåðèðóþòñÿ íåçàâèñè-
ìûìè íåïðåðûâíûìè ñëó÷àéíûìè âåëè÷èíàìè � è � ;
2) ìíîæåñòâà DA B, è DA B, ðàçäåëåíû êðèâîé y xA B, ( ) .
Òîãäà �x ( , )0 1 èìååò ìåñòî ñîîòíîøåíèå
lim ( ) ( )
,
,
n n
A B
A B
y x y x
��
� ,
ãäå
y x F F x F F x
G G
( ) min ( (( ) ( )), (( ) ( )))� � �� �
� � � �
1 11 1 .
Äîêàçàòåëüñòâî. Äëÿ äîêàçàòåëüñòâà òåîðåìû äîñòàòî÷íî ïîêàçàòü, ÷òî èìå-
þò ìåñòî ñîîòíîøåíèÿ
F F y F F y yn nB A
( ( )) ( ( )), ( , )� �� �1 1 01� �
, (8)
F F y F F y yn nB A
( ( )) ( ( )), ( , )1 1 011 1� � � �� �
� �
. (9)
Ïîêàæåì ñïðàâåäëèâîñòü ñîîòíîøåíèÿ (8):
sup
y
n n
F F y F F y
B A�
� �� �
[ , ]
| ( ( )) ( ( )) |
0 1
1 1
� �
�
�
�
� � �sup
y
n n n n
F F y F F y F F y
B A A A[ , ]
| ( ( )) ( ( )) ( ( )
0 1
1 1 1
� � ) ( ( ))|� ��F F y� �
1
� �
�
� �
�
sup sup
y
n n n
y
F F y F F y
B A A[ , ] [ , ]
| ( ( )) ( ( )) |
0 1
1 1
0 1
� | ( ( )) ( ( )) |F F y F F y
nA
� � �
� �� �1 1
� �
�
� �
�sup sup
x R
n
y
n
F x F x F F y F
B A1 0 1
1| ( ) ( ) | | ( ( )) (
[ , ]
� � � F y
�
�1 ( )) | .
Ïî òåîðåìå Ãëèâåíêî–Êàíòåëëè [21] äëÿ ïåðâîãî ñëàãàåìîãî ñïðàâåäëèâî
sup
x R
n BF x F x n
B
�
� � � �
1
0| ( ) ( )| ,� .
Ïðåäïîëîæèì, ÷òî � èìååò ïëîòíîñòü f K� � . Òîãäà äëÿ âòîðîãî ñëàãàåìîãî
èìååì îöåíêó
sup sup
y
n
y
F F y F F y K F
A�
� �
�
� �
[ , ] [ , ]
| ( ( )) ( ( )) | |
0 1
1 1
0 1
� � � nA
y F y� ��1 1( ) ( )|
�
.
Ïîêàæåì, ÷òî sup
y
n
F y F y
A�
� �� �
[ , ]
| ( ) ( ) |
0 1
1 1 0
�
.
140 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 4
Ïðåäïîëîæèì, ÷òî F x y� ( ) ( , )0 0 0 1� � ôèêñèðîâàííîå è | ( )F y
nA
� �1
0
� ��F y
�
1
0 0( ) | / , òîãäà | ( ) ( ) | /F x F xnA� 0 0 0� � . Ïîëó÷àåì ïðîòèâîðå÷èå.
Òàêèì îáðàçîì, èìååò ìåñòî ñîîòíîøåíèå (8). Ïî àíàëîãèè ñîîòíîøåíèå (9)
òàêæå ñïðàâåäëèâî.
Òåîðåìà 2 äîêàçàíà.
Òåîðåìà 3. Ïóñòü:
1) � i i, � 1 , èìåþò ðàñïðåäåëåíèå F� ; � j j, � 1 , èìåþò ðàñïðåäåëåíèå F� ;
2) � �i j i j, , , � 1 , — íåçàâèñèìûå â ñîâîêóïíîñòè ñëó÷àéíûå âåëè÷èíû;
3) ôóíêöèè F� , F� èìåþò îáðàòíûå è ñóùåñòâóþò îãðàíè÷åííûå ïëîò-
íîñòè f f� �, .
Òîãäà íàáëþäàåòñÿ ñëàáàÿ ñõîäèìîñòü
� � � �n m n m n my n F F y F F y N, , ( ) ( ( ( )) ( ( ))) ( , )� � � �� �1 1 20 ,
ãäå
� � � �
2 1 11� �� �F F y F F y( ( ))( ( ( )))
ïðè n�� , m O n� �( ),� � 0.
Äîêàçàòåëüñòâî. Ðàññìîòðèì ìàòåìàòè÷åñêîå îæèäàíèå � n m, :
E n EF F y F F yn m n m� � �, ( ( ( )) ( ( )))� �� �1 1 .
Èñïîëüçóÿ îïðåäåëåíèå ýìïèðè÷åñêîé ôóíêöèè ðàñïðåäåëåíèÿ, ïîëó÷aeì
| | | ( ( ( ))) |, ( )
E n EI F F yn m F ym
�
� � �
� � �
�
�
�1
1
� � � � �� �| ( ( ) ( ) ) |n P F y P F ym{ } { }� �
�
1 1
| ( ( ) ( ) ( ) ( ) ) |n P F y F y P F y F ym m{ } { }
� �
� �� � � �� �
� �1 1 1 1 .
Òàêèì îáðàçîì, äëÿ ñõîäèìîñòè
E n m� , � 0
äîñòàòî÷íî ïîêàçàòü, ÷òî
nP F y F ym{ }| ( ) ( ) |
�
�� �� � �1 1 0
ïðè ëþáîì � .
Ñîãëàñíî îïðåäåëåíèþ îáîáùåííîé îáðàòíîé ôóíêöèè ïîëó÷èì ñîîòíîøåíèå
nP F y F ym{ }| ( ) ( )|
�
�� �� � �1 1
� � � � �� �nP F y F y n e em
m n m{ }| ( ) ( ) | ( ) ( ) , ln (
�
� � � �� � 2 22 0 5 22 )2
,
ãäå ïîñëåäíåå íåðàâåíñòâî áàçèðóåòñÿ íà íåðàâåíñòâå Äâîðåöêîãî–Êèôåðà–
Âîëüôîâèöà [22], � �( ) íå çàâèñèò îò n è m .
Òàêèì îáðàçîì, ïðè m O n� �( ),� � 0 , èìååì lim ,
n
n mE
��
�� 0 .
Ðàññìîòðèì äèñïåðñèþ � n m, :
D E En m n m n m� � �, , ,( )� �2 2 .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 4 141
Âòîðîå ñëàãàåìîå ñòðåìèòñÿ ê íóëþ, ïîýòîìó âàæíî ðàññìîòðåòü ïåðâîå ñëàãà-
åìîå ïðåäûäóùåãî ðàâåíñòâà
E nE F F y F F yn m n m� � �, ( ( ( )) ( ( )))2 1 1 2� � �� �
� �
�
�
�E I F F y
F ym
( ( ( )))
( )� � �1
1 2
� �
�
�
�
�
� �
1
1 1
1 1
n
I F F y I F F y
i m j mF y F y
( ( ( ))) ( ( (
( ) ( )� � � � � �
)))
i j!
& .
Ïðåíåáðåãàÿ âåëè÷èíàìè ïîðÿäêà ìàëîñòè O( )1 , ïîëó÷aeì ñîîòíîøåíèå
D n m� , �
� �
�
�
� �� � �E I F F y
n
EI I
F y F y Fm i m j m
( ( ( ))) (
( ) ( )� � � � �1 1
1 2 1
1
2
1 2( )
)
y
i j
p A A�
�
�
�
�
�
�
�
�
�
!
& ,
ãäå
p F F y� �
� �
( ( ))1 .
Ðàññìîòðèì êàæäîå ñëàãàåìîå îòäåëüíî. Èñïîëüçóÿ òåîðåìó Ëåáåãà î ìàæî-
ðàíòíîé ñõîäèìîñòè [23], ïîëó÷àåì
A E I F F y E I F F
F y F ym
1
1 2 1
1 1� � � �
�
�
�
�
� �( ( ( ))) ( (
( ) ( )� � � � � ��
( ))) ( )y p p2 1� �
ïðè m�� .
Äëÿ âòîðîãî ñëàãàåìîãî ñ ó÷åòîì íåçàâèñèìîñòè � i i, � 1 , ïîëó÷èì
A n EI I p
F y F ym m
2
21
1
1
2
1� � � �
� �� �( )( )
( ) ( )� �
� � � � � �� �( )( ( ), ( ) )n P F y F y pm m1 1
1
2
1 2{ }� �
� � � � � ' �� � �( )( ( ), ( ) ( ),n P F y F y p P F ym m m1 1
1
2
1 2
1
1
2{ } {� � � � � ��F y
�
1 ( ) )}
� � � � � � �� � �( )( ( ), ( ) ( ),n P F y F y P F y Fm m m1 1
1
2
1
1
1
2{ } {� � � �
�
�
1 ( ) )y }
� � � � �
� �( )( ( ), ( ) )n P F y F y p A Am1 1
1
2
1 2
21 22{ }� �
�
.
Äëÿ ïåðâîãî ñëàãàåìîãî ïîëó÷èì
| | ( )| ( ) | ( ) | ( )A n P F y P F y F ym m m21 1
1
2
1
1
11� � � � �� � �{ } { }� � � �
� � � �� �P F y F ym{ }� �
�2
1
1
1( )| ( ) |
� � � � � � �� � �( ) | ( ) | ( ) ( )|n P F y F y P F y Fm m m1 2
1
1
1
2
1
1{ } {� � � �
�
�1 ( ) |y } .
Àíàëîãè÷íî ïðåäûäóùèì ðàññóæäåíèÿì, èñïîëüçóÿ íåðàâåíñòâî Äâîðåöêî-
ãî–Êèôåðà–Âîëüôîâèöà, ïîëó÷aeì | |A21 0� .
Äëÿ âòîðîãî ñëàãàåìîãî èìååì A n p P F y pm22 1
11� � � ��( ) ( ( ) ){ }� , îòñþäà
ñëåäóåò | |A22 0� .
Òàêèì îáðàçîì, D p pn m� , ( )� �1 .
Ïîñëåäíèì øàãîì äîêàçàòåëüñòâà áóäåò èñïîëüçîâàíèå öåíòðàëüíîé ãðàíè÷-
íîé òåîðåìû äëÿ àñèìïòîòè÷åñêè íåçàâèñèìûõ ñëó÷àéíûõ âåëè÷èí [24]
u I ii m F y pi m
, ( )
,� �
� ��� 1 1 ,
142 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 4
ãäå àñèìïòîòè÷åñêóþ íåçàâèñèìîñòü ñëåäóåò ïîíèìàòü ïðè m�� â ñëåäóþ-
ùåì êîíòåêñòå:
lim ( , ), , , ,
m
i m j m i m j mP u A u B P u A P u B
��
� � � � � �{ } { } { } 0
äëÿ i j! , A B R, � � .
Òåîðåìà 3 äîêàçàíà.
ÇÀÊËÞ×ÅÍÈÅ
 ñòàòüå ââåäåíî ïîíÿòèå îáëàñòè ðàçäåëåíèÿ ìíîæåñòâà Dl , äîêàçàíà òåîðåìà
î ñõîäèìîñòè ìíîæåñòâ DA B, è Dl , à òàêæå äîêàçàíî, ÷òî ìíîæåñòâà Dl è Dl
ÿâëÿþòñÿ çâåçäíûìè; ïðåäëîæåí àíàëèòè÷åñêèé âèä ôóíêöèè, ðàçäåëÿþùåé
ýòè ìíîæåñòâà. Ïðèâåäåíû ïðèìåðû ïîñòðîåíèÿ äàííîé ôóíêöèè äëÿ íîð-
ìàëüíîãî, ýêñïîíåíöèàëüíîãî, ðàâíîìåðíîãî è ïóàññîíîâñêîãî ðàñïðåäåëåíèé.
Íåñîìíåíííî, ÷òî ýòà æå ìåòîäèêà ìîæåò áûòü ðàññìîòðåíà è äëÿ ìíîãîìåð-
íîãî ñëó÷àÿ.  òåîðåìå 3 äîêàçàíà ñëàáàÿ ñõîäèìîñòü íîðìèðîâàííîé ðàçíî-
ñòè ýìïèðè÷åñêîé è òåîðåòè÷åñêîé êðèâûõ ðàçäåëåíèÿ ê íîðìàëüíîìó ðàñïðå-
äåëåíèþ, ÷òî ïîçâîëÿåò ïðîâåðÿòü ãèïîòåçû î ìåñòîíàõîæäåíèè òåîðåòè÷åñêîé
êðèâîé ðàçäåëåíèÿ â êîíêðåòíîé òî÷êå.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. H a u s s l e r D . , W e l z l E . Epsilon-nets and simplex range queries // Discrete Comput. Geom. —
1987. — N 2. — P. 127–151.
2. G ��ar t n e r B . , H o f f m a n n M . Computational Geometry. — http://www.ti.inf.ethz.ch/ew/lehre/
CG12/lecture/CG%20lecture%20notes.pdf.
3. H a u s l e r S . VC Dimension. A tutorial for the course computational intelligence. —
http://www.igi.tugraz.at/lehre/CI.
4. K u l k a r n i J . , G o v i n d a r a j a n S . New �-net constructions // Canadian Conference on Compu-
tational Geometry — CCCG, 2010. — P. 159–162.
5. A r o n o v B . , E z r a E . , S h a r i r M . Small-size epsilon-nets for axis-parallel rectangles and boxes
// Symposium on Theory of Computing, 2009. — P. 639–648.
6. M a t o u s e k J . , S e i d e l R . , W e l z l E . How to net a lot with little: small �-nets for disks and
halfspaces // Sixth Annual Symposium on Computational Geometry, Berkley, CA, USA,
June 07–09, 1990. — P. 16–22.
7. V e s e l y' A . Economic classification and regression problems and neural networks // Agricultural
Economics — CZECH. — 2011. — N 57. — P. 150–157.
8. P r i c e D . , P o l l o c k A . M . , B r h l i k o v a P . Classification problems and the dividing line
between government and the market: An examination of NHS foundation trust classification in the
UK // Annals of Public and Cooperative Economics. — 2011. — 82, Issue 4. — P. 455–473.
9. S c h a u b e l D . E . , C a i J . Analysis of clustered recurrent event data with application to
hospitalization rates among renal failure patients // Biostatistics. — 2005. — N 6. — Ð. 404–419.
10. W e a t h e r a l l M . , S h i r t c l i f f e P . , T r a v e r s J . , B e a s l e y R . Use of cluster analysis to
define COPD phenotypes // Eur. Respir. J. — 2010. — 36. — P. 472–474.
11. M a h r A . , K a t s a h i a n S . , V a r e t H . Revisiting the classification of clinical phenotypes of
anti-neutrophil cytoplasmic antibody-associated vasculitis: A cluster analysis // Annals of the
Rheumatic Diseases. — 2012. — 72. — P. 1003–1010.
12. M a n g a s a r i a n O . L . , S t r e e t W . N . , W o l b e r g W . H . Breast cancer diagnosis and prognosis
via linear programming // Operation Research. — 1995. — 43, N 4.
13. M a n g a s a r i a n O . L . A simple characterization of solution sets of convex programs // Computer
Sciences Technical Report #685, 1987. — P. 21–26.
14. C a r d D . , K r u e g e r A . B . Minimum wages and employment: A case study of the fast-food industry
in New Jersey and Pennsylvania // American Economic Review. — 1994. — 84, N 4. — P. 772–793.
15. A n g r i s t J . , V i c t o r y L . Using maimonides’ rule to estimate the effect of class size on student
achievement // Quarterly Journal of Economics. — 1999. — 114. — P. 533–575.
16. L e e D . , M o r e t t i E . , B u t l e r M . J . Do voters affect or elect policies? Evidence from the U.S.
House // Quarterly Journal of Economics. — 2004. — 119. — P. 807–859.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 4 143
17. I v a n c h u k M . A . , M a l y k I . V . Comparison of the methods for classification of observations in
predicting complications in critically ill patients // Cybernetics and Systems Analysis. — 2015. —
51, N 2. — P. 303–312.
18. I v a n c h u k M . A . , M a l y k I . V . Using �-nets for linear separation of two sets in a euclidean
space Rd // Cybernetics and Systems Analysis. — 2015. — 51, N 6. — P. 965–968.
19. E m b r e c h t s P . , H o f e r t M . A note on generalized inverses // Mathematical Methods of
Operations Research. — 2013. — 77, N 5. — P. 423–432.
20. S m i t h C . R . A characterization of star-shaped sets // American Mathematical Monthly. —
1968. — 75, N 4. — P. 386.
21. T u c k e r H . G . A generalization of the Glivenko–Cantelli theorem // The Annals of Mathematical
Statistics. — 1959. — 30, N 3. — P. 828–830.
22. D v o r e t z k y A . , K i e f e r J . , W o l f o w i t z J . Asymptotic minimax character of the sample
distribution function and of the classical multinomial estimator // Annals of Mathematical
Statistics. — 1956. — 27, N 3. — P. 642–669.
23. D u r r e t t R . Probability: Theory and examples. — Forth Edition, 2013. — 386 p.
24. Ó ñ î ë ü ö å â Ë . Ï . Îá àñèìïòîòèêå è áîëüøèõ óêëîíåíèÿõ â öåíòðàëüíîé ïðåäåëüíîé òåîðåìå
äëÿ ñóìì âèäà f q tn( )& // Âåñòíèê ÑàìÃÓ. Åñòåñòâåííîíàó÷íàÿ ñåðèÿ. — 2009. —
Âûï. 4 (70) — Ñ. 52–84.
Íàä³éøëà äî ðåäàêö³¿ 03.12.2015
Ì.À. ²âàí÷óê, ².Â. Ìàëèê
ÐÎÇÂ’ßÇÀÍÍß ÇÀÄÀײ ÊËÀÑÈÔ²ÊÀÖ²¯ Ç ÂÈÊÎÐÈÑÒÀÍÍßÌ �-ѲÒÎÊ
Àíîòàö³ÿ. Çàïðîïîíîâàíî íîâèé ìåòîä ðîçâ’ÿçàííÿ çàäà÷³ êëàñèô³êàö³¿, ùî
áàçóºòüñÿ íà â³äîêðåìëåíí³ äâîõ ìíîæèí â ïðîñòîð³ Rd øëÿõîì ïîáóäîâè òà
â³äîêðåìëåííÿ �-ñ³òîê öèõ ìíîæèí â ðàíæîâàíîìó ïðîñòîð³ â³äíîñíî ã³ïåð-
ïëîùèí. Ââåäåíî ïîíÿòòÿ îáëàñò³ ïîä³ëó — òèõ çíà÷åíü � , ïðè ÿêèõ ìîæëè-
âî â³äîêðåìèòè ìíîæèíè. Íàâåäåíî ïðèêëàäè îáëàñò³ ïîä³ëó äëÿ âèïàäêîâèõ
âåëè÷èí, ðîçïîä³ëåíèõ çà íàéá³ëüø âæèâàíèìè çàêîíàìè ðîçïîä³ëó, òà äîâå-
äåíî òåîðåìó ïðî ¿¿ çá³æí³ñòü. Ââåäåíî ïîíÿòòÿ ñóêóïíîñò³ âñ³õ ìîæëèâèõ
�-ñ³òîê äåÿêî¿ ìíîæèíè òà äîâåäåíî äåÿê³ ¿¿ âëàñòèâîñò³. Äîâåäåíà ñëàáêà
çá³æí³ñòü íîðìîâàíî¿ ð³çíèö³ åìï³ðè÷íî¿ òà òåîðåòè÷íî¿ êðèâèõ â³äîêðåìëåí-
íÿ äî íîðìàëüíîãî ðîçïîä³ëó, ùî äîçâîëÿº ïåðåâ³ðÿòè ã³ïîòåçè ïðî ì³ñöåçíà-
õîäæåííÿ òåîðåòè÷íî¿ êðèâî¿ â³äîêðåìëåííÿ â êîíêðåòí³é òî÷ö³.
Êëþ÷îâ³ ñëîâà: �-ñ³òêè, â³äîêðåìëåííÿ ìíîæèí, ðîçì³ðí³ñòü Âàïí³êà–×åðâî-
íåíê³ñà, êëàñèô³êàö³ÿ.
M.A. Ivanchuk, I.V. Malyk
SOLVING THE CLASSIFICATION PROBLEM USING �-NETS
Abstract. The new method of the solution the classification problem is proposed
in the paper. The method is based on separating two sets in the space Rd by
constructing and separating �-nets of these sets in a ranked space with respect to
hyperplanes. The concept of the set of possible values of � for �-nets of both
sets is introduced in the paper. The properties of this set and the theorem of its
convergence are proved. The paper contains examples of the set of possible
values for the most useful distributions. The concept of the set of all possible
�-nets of the set is introduced in the paper. Weak convergence of the normalized
difference of the empiric and theoretic separation curves to the normal
distribution is proved. It makes possible to check the hypothesis of the place of
theoretic separation curve at a specific point.
Keywords: �-nets, sets’ separation, VC-dimension, classification.
Èâàí÷óê Ìàðèÿ Àíàòîëüåâíà,
àññèñòåíò êàôåäðû Áóêîâèíñêîãî ãîñóäàðñòâåííîãî ìåäèöèíñêîãî óíèâåðñèòåòà, ×åðíîâöû,
e-mail: mgracia@ukr.net.
Ìàëûê Èãîðü Âëàäèìèðîâè÷,
êàíäèäàò ôèç.-ìàò. íàóê, äîöåíò êàôåäðû ×åðíîâèöêîãî íàöèîíàëüíîãî óíèâåðñèòåòà
èìåíè Þðèÿ Ôåäüêîâè÷à, e-mail: malyk.igor.v@gmail.com.
144 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 4
|
| id | nasplib_isofts_kiev_ua-123456789-142005 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T17:43:29Z |
| publishDate | 2016 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Иванчук, М.А. Малык, И.В. 2018-09-19T19:28:45Z 2018-09-19T19:28:45Z 2016 Решение задачи классификации с использованием ε-сетей / М.А. Иванчук, И.В. Малык // Кибернетика и системный анализ. — 2016. — Т. 52, № 4. — С. 134-144. — Бібліогр.: 24 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/142005 [519.245+519.214]: 519.237.8 Предложен новый метод решения задачи классификации, основанный на разделении двух множеств в пространстве Rd путем построения и разделения ε-сетей этих множеств в ранжированном пространстве относительно гиперплоскостей. Введено понятие области разделения — тех значений ε, при которых возможно разделить множества. Приведены примеры области разделения для случайных величин с разными распределениями и доказана теорема о ее сходимости. Введено понятие совокупности всех возможных ε-сетей некоторого множества и доказаны ее свойства. Доказана слабая сходимость нормированной разности эмпирической и теоретической кривых разделения к нормальному распределению, что позволяет проверять гипотезы о местонахождении теоретической кривой разделения в конкретной точке. Запропоновано новий метод розв’язання задачі класифікації, що базується на відокремленні двох множин в просторі Rd шляхом побудови та відокремлення ε-сіток цих множин в ранжованому просторі відносно гіперплощин. Введено поняття області поділу — тих значень ε, при яких можливо відокремити множини. Наведено приклади області поділу для випадкових величин, розподілених за найбільш вживаними законами розподілу, та доведено теорему про її збіжність. Введено поняття сукупності всіх можливих ε-сіток деякої множини та доведено деякі її властивості. Доведена слабка збіжність нормованої різниці емпіричної та теоретичної кривих відокремлення до нормального розподілу, що дозволяє перевіряти гіпотези про місцезнаходження теоретичної кривої відокремлення в конкретній точці. The new method of the solution the classification problem is proposed in the paper. The method is based on separating two sets in the space Rd by constructing and separating ε-nets of these sets in a ranked space with respect to hyperplanes. The concept of the set of possible values of ε for ε-nets of both sets is introduced in the paper. The properties of this set and the theorem of its convergence are proved. The paper contains examples of the set of possible values for the most useful distributions. The concept of the set of all possible ε-nets of the set is introduced in the paper. Weak convergence of the normalized difference of the empiric and theoretic separation curves to the normal distribution is proved. It makes possible to check the hypothesis of the place of theoretic separation curve at a specific point. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Решение задачи классификации с использованием ε-сетей Розв’язання задачі класифікації з використанням ε-сіток Solving the classification problem using ε-nets Article published earlier |
| spellingShingle | Решение задачи классификации с использованием ε-сетей Иванчук, М.А. Малык, И.В. Системный анализ |
| title | Решение задачи классификации с использованием ε-сетей |
| title_alt | Розв’язання задачі класифікації з використанням ε-сіток Solving the classification problem using ε-nets |
| title_full | Решение задачи классификации с использованием ε-сетей |
| title_fullStr | Решение задачи классификации с использованием ε-сетей |
| title_full_unstemmed | Решение задачи классификации с использованием ε-сетей |
| title_short | Решение задачи классификации с использованием ε-сетей |
| title_sort | решение задачи классификации с использованием ε-сетей |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/142005 |
| work_keys_str_mv | AT ivančukma rešeniezadačiklassifikaciisispolʹzovaniemεsetei AT malykiv rešeniezadačiklassifikaciisispolʹzovaniemεsetei AT ivančukma rozvâzannâzadačíklasifíkacíízvikoristannâmεsítok AT malykiv rozvâzannâzadačíklasifíkacíízvikoristannâmεsítok AT ivančukma solvingtheclassificationproblemusingεnets AT malykiv solvingtheclassificationproblemusingεnets |