Алгоритмы решения задач классификации на основе аппроксимации относительной глубины данных и взвешенного среднего значения
Розглянуто актуальну проблему вибору оптимальної гіпотези в задачах класифікації з використанням концепції зваженого середнього значення та функцій глибини. Розроблено та досліджено модифіковані алгоритми для апроксимації відносної глибини даних та відносного зваженого середнього значення розподілу....
Saved in:
| Published in: | Проблемы управления и информатики |
|---|---|
| Date: | 2016 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2016
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/208263 |
| 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. — № 5. — С. 144-155. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860243220738342912 |
|---|---|
| author | Галкин, А.А. |
| author_facet | Галкин, А.А. |
| citation_txt | Алгоритмы решения задач классификации на основе аппроксимации относительной глубины данных и взвешенного среднего значения / А.А. Галкин // Проблемы управления и информатики. — 2016. — № 5. — С. 144-155. — Бібліогр.: 10 назв. — рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Розглянуто актуальну проблему вибору оптимальної гіпотези в задачах класифікації з використанням концепції зваженого середнього значення та функцій глибини. Розроблено та досліджено модифіковані алгоритми для апроксимації відносної глибини даних та відносного зваженого середнього значення розподілу. Запропоновані алгоритми забезпечують поліноміальні наближення до напівпросторової глибини даних та напівпросторового зваженого середнього значення розподілу, що є окремим випадком сімейства зважених середніх значень.
An actual problem of choosing the optimal hypothesis in classification problems using the concept of weighted average value and depth functions are considered. The modified algorithms are constructed and studied to approximate the relative data depth and relative weighted average value of distribution. The proposed algorithms provide polynomial approximations to the half-space data depth and half-space weighted average value which is a special case of the weighted averages family.
|
| first_indexed | 2025-12-07T18:32:55Z |
| format | Article |
| fulltext |
© А.А. ГАЛКИН, 2016
144 ISSN 0572-2691
РОБОТЫ И СИСТЕМЫ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА
УДК 519.7
А.А. Галкин
АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ
КЛАССИФИКАЦИИ НА ОСНОВЕ
АППРОКСИМАЦИИ ОТНОСИТЕЛЬНОЙ ГЛУБИНЫ
ДАННЫХ И ВЗВЕШЕННОГО СРЕДНЕГО ЗНАЧЕНИЯ
Как известно, одной из актуальных задач многомерной классификации явля-
ется проблема выбора оптимальной гипотезы. Критерием выбора такой гипотезы
может выступать концепция глубины, где для нахождения наиболее глубокой фу-
нкции применяются соответствующие методы аппроксимации. В данной работе
исследуем алгоритмические аспекты определения глубины функций, в результате
чего будут построены алгоритмы для равномерной аппроксимации глубины на
общем классе функций, а также алгоритмы для аппроксимации взвешенного сре-
днего значения.
Постановка задачи
Для определения глубины функции предлагаем эффективный алгоритм
оценки глубины, который принимает на входе две выборки }...,,{ 1 gzzW и
},...,,{ 1 mhhQ первая из которых является выборкой точек из генеральной со-
вокупности , а вторая — выборкой функций из класса функций . На первом
этапе предложенный алгоритм оценивает глубину заданной функции h на элеме-
нтах ,...,,1 gzz после чего использует минимальное значение как оценку общей
глубины. Отметим, что глубина элемента iz оценивается путем подсчета компонент
функций ....,,1 mhh Итак, приведем алгоритм оценки глубины, на вход которого по-
дается выборка },...,,{ 1 gzzW где ,iz выборка },...,,{ 1 mhhQ где ,lh и
функция ,h а на выходе — функция ),(hEW
Q которая является приближением для
глубины :h 1) для gi ...,,1 вычислить ;1
1
)|( )()(
l zhzhiQ iilm
zhE 2) возвра-
тить ).|(min)( ii
W
Q zhEhE Отметим, что эмпирической глубиной h является
значение ),(hEW
Q возвращаемое алгоритмом оценки глубины. Кроме того, дан-
ный алгоритм позволяет получить эффективные оценки истинной глубины [1].
Предположим, что C — некоторое множество подмножеств в , а — ве-
роятностная мера, определенная на генеральной совокупности . Итак, опреде-
лим -сеть как такое конечное подмножество ,G что для ,Cd если
,)( d .dG
Международный научно-технический журнал
«Проблемы управления и информатики», 2016, № 5 145
Лемма показывает, что если размерность Вапника–Червоненкиса C является
конечной, то случайное множество точек образует -сеть с высокой вероятностью.
Лемма 1. Пусть C — множество подмножеств в генеральной
совокупности с конечной размерностью Вапника–Червоненкиса ,r а — ве-
роятностная мера, определенная на . Также предположим, что 0 и
./8 g Случайная выборка
g
iizW 1}{ из g является -сетью для C с веро-
ятностью не менее .2)2,(1 2/1 ggrf
Далее приведем теорему о равномерной сходимости глубины, что является
важным элементом нахождения взвешенного среднего значения. Из данной тео-
ремы следует, что эмпирическая глубина — эффективная оценка истинной глуби-
ны, если lh отбираются из вероятностной меры , а iz — из распределения
по . Кроме того, данная оценка является равномерно эффективной для всех
функций .h
Теорема 1. Пусть — вероятностная мера на , ,0, а — вероятностная
мера на . Пусть функция h )( h такова, что ,1)( zh если )|( zhE
,)(
,
hE
и 1)( zh — в противном случае. Определим ,),(
0
i
t
trf
r
i
если
,tr и
ttrf 2),( — в противном случае. Также предположим, при условии что
имеет конечную размерность Вапника–Червоненкиса ,r .}{ hh
Если W и Q выбраны случайным образом из g и m соответственно, где
,/8 g то с вероятностью
2/)(12 2)2,()2(exp1 ggrfmg (1)
имеет место неравенство
,)()()()(,
,,0
hEhEhEhEh W
Q (2)
где )(hEW
Q — эмпирическая глубина, которая вычисляется с помощью алгоритма
измерения глубины.
Доказательство. Из леммы 1 следует, что с вероятностью, большей или рав-
ной ,2)2,(1 2/)(1 ggrf случайная выборка
g
iizW 1}{ является -сетью для
.}{ hh Обозначим h как функцию, так и подмножество , которое включает
все ,z для которых ).()|(
,
hEzhE
Можно утверждать, что для h имеет место выражение ]...,,1[ gi
, .. hzts i поскольку для h выполняется неравенство .)( h Посколь-
ку ),()|( , hEzhE i
что следует из того, что ,hzi имеем, что ,h
)()|(min)( , hEzhEhE i
i
(3)
с вероятностью 2/)(12)2,(1 ggrf при случайном выборе ....,,1 gzz
Далее, используя неравенство Хефдинга для фиксированных ,iz имеем
),2(exp2}1)(:{1)(:
1 2
...,,1
mzhhzhh
m
P iill
hh m
(4)
где mhh ...,,1 — независимая одинаково распределенная выборка из .
146 ISSN 0572-2691
Итак, для i
}1)(:{1)(:
1
iill zhhzhh
m
(5)
с вероятностью ).2(exp1 2 mg
Кроме того, для i имеет место неравенство
.}1)(:{1)(:
1
iill zhhzhh
m
(6)
Учитывая полученные результаты, можно утверждать, что h
)()(
,
hEhEW
Q (7)
с вероятностью не менее
2/)(12 2)2,()2(exp1 ggrfmg при случайном вы-
боре gzz ...,,1 и ....,,1 mhh
Следует заметить, что с вероятностью 1 не существует в выборке такого ,i
что ).()|(
,0
hEzhE i
Отсюда следует, что для ,h ),()(
,0
hEhE W
Q
а
также выполняется неравенство ).()(
,0
hEhE
Теорема доказана.
Исходя из теоремы 1, можно сделать вывод, что расчетная глубина равно-
мерно сходится к истинной глубине.
Теорема 2. Пусть h является таким, что ,1)( zh если ,)|( EzhE и
1)( zh — в противном случае для .h Также предположим, что
)(sup hEE h и .}{
)(:
,
EhEh
h
Тогда размерность Вапника–Червонен-
киса ограничена сверху размерностью Вапника–Червоненкиса [2].
Доказательство. Для каждой последовательности ,}1{ nx ,xh где
xh
генерирует метки x на nzz ...,,1 при условии, что nzz ...,,1 модифициро-
ваны . Необходимо показать, что выборка данных модифицирована , пос-
кольку функции xh и xh
генерируют различные метки на nzz ...,,1 для .xx
Предположим, что ,xx 1ix и .1ix Отсюда следует, что iz такое, что
).|()|( i
x
i
x zhEEzhE
(8)
При условии, когда ),()( i
x
i
x zhzh
имеем ).|()|( i
x
i
x zhEzhE
Заме-
тим, что данный вывод следует из определения глубины в точке .iz
Итак, выборка nzz ...,,1 является модифицированной исходя из ее моди-
фикации . Поэтому можно сделать вывод, что размерность Вапника–Черво-
ненкиса ограничена размерностью Вапника–Червоненкиса .
Теорема доказана.
Отметим, что поскольку объектом нашего исследования являются глубинные
гипотезы, достаточно получить точные оценки для них [3]. Для достижения этого
приведем следующую теорему.
Теорема 3. Пусть имеет конечную размерность Вапника–Червоненкиса
,r ,0, ),(sup hEE h величина является вероятностной мерой на
, а величина — вероятностной мерой на . Если W и Q выбраны случай-
Международный научно-технический журнал
«Проблемы управления и информатики», 2016, № 5 147
ным образом из g и m соответственно, где ,/8 g тогда с вероятностью
2/)(12 2)2,()2(exp1 ggrfmg имеют место такие утверждения: а) )(hE
Q
W
,)(
,
hE ,h где ;)(, EhE
б)
)()()(
,0
hEhEhE
Q
W , ,h где
)(hEW
Q — эмпирическая глубина, вычисленная с помощью алгоритма измерения
глубины.
Доказательство. Используя результаты леммы 1 и теоремы 2 относи-
тельно функционирования -сетей, можно утверждать, что для ,h где
,)(
,
EhE
существует такое ,iz что с вероятностью
/2)(12)2,(1 ggrf на
выборке W имеет место неравенство
.)()|(
,
EhEzhE i
(9)
Отсюда следует, что для ,h таких, что ,)(
,
EhE
имеет место неравенс-
тво
)()( , hEhE
Q
W с вероятностью больше .2)2,(1 /2)(1 ggrf
Для доказательства второго утверждения следует отметить, что для z и ,h
)()|(
,0
hEzhE
с вероятностью 1. Поэтому неравенство )|()( zhEhE
Q
W мо-
жет быть следствием неопределенности в оценке .1
1
)|( )()( iili zhzh
l
Q
m
zhE
Отметим, что hi, выполняется неравенство
)|(1
1
)()( zhE
m l
zhzh iil
(10)
с вероятностью )2(exp1 2 mg на выборке ,Q что следует из доказательства
теоремы 1. В результате получаем, что
)()(
,0
hEhE
Q
W для .h
Теорема доказана.
Процедура нахождения взвешенного среднего значения
Анализируя методы определения глубины, установили, что расчетная глуби-
на принимает точные значения равномерно для всех функций h с достаточно
большой вероятностью при условии, что выборки W и Q достаточно боль-
шие [4]. Кроме того, имеем, что ),(argmax hEh h отсюда следует, что отно-
сительное взвешенное среднее значение является функцией ,h которая максими-
зирует глубину.
На основе полученных результатов строим алгоритм приближения относитель-
ного взвешенного среднего значения, а также алгоритм нахождения функции ,h ко-
торая максимизирует эмпирическую глубину, т.е. ).(argmax hEh W
Qh
Итак, предположим, что .}{ 1
g
iizW Отметим, что функция с большой
эмпирической глубиной будет согласовываться с большинством характеристик
данных точек. Однако когда такой функции не существует, возникает необходи-
мость нахождения гипотезы, которая не согласовывается с большинством харак-
теристик на соответствующих моделях. В таких случаях эмпирическая глубина
будет принимать большее значение, если большинство характеристик на таких
элементах данных доминирует с небольшим отрывом. Для решения данной про-
148 ISSN 0572-2691
блемы используем выборку функций
m
llhQ 1}{ для вычисления большинства ха-
рактеристик каждого iz и часть is -функций, которые не согласовываются с
большинством характеристик [5].
Предложенный подход базируется на нахождении функции, которая согласу-
ется с большинством характеристик всех элементов в .W При условии, если дан-
ной функции не существует, удаляем элемент данных, для которого is принимает
наибольшее значение, и находим функцию, которая согласуется с большинством
характеристик других элементов данных. Данная процедура выполняется до тех
пор, пока не будет найдена согласованная функция. Заметим, что данная функция
является максимизирующей оценкой ),(hEW
Q поэтому в алгоритме приближения
взвешенного среднего значения данная процедура ускоряется с помощью двоич-
ного поиска.
Отметим, что метод двоичного поиска уменьшает сложность алгоритма до
)),(log)(log( ggggmgO q в то время как линейный поиск требует mgO (
))(log 1 qggg операций. Указанная сложность обеспечивается при условии,
что алгоритм согласованности требует )( qgO операций для некоторого q при
работе на выборке размером .g
Далее представлен алгоритм приближения взвешенного среднего значения,
преимуществом которого является использование модели согласованности вместо
модели минимизации эмпирической ошибки [6]. Отметим, что условием выпол-
нения алгоритма приближения взвешенного среднего значения является лишь до-
ступ к модели, которая способна находить согласованную гипотезу, если таковая
существует. Указанная особенность алгоритма позволяет уменьшить сложность
минимизации и аппроксимации эмпирической ошибки.
Алгоритм приближения взвешенного среднего значения можно представить
следующим образом. На вход алгоритма подаются выборки
g
gzzW }...,,{ 1
и ,}...,,{ 1
m
mhhQ где .lh Также имеет место алгоритм , который воз-
вращает согласованную функцию, если такая функция существует. На выходе по-
лучаем функцию ,h приближающую относительное взвешенное среднее зна-
чение с его оценкой глубины ).(hEW
Q Итак, алгоритм состоит из следующих
шагов: 1) gi ...,,1 вычисляем }1)(:{
1
ili zhl
m
и };1,{min iiis
2) классифицируем gzz ...,,1 таким образом, что ;...21 nsss 3) gi ...,,1
пусть ,1ix если ,5,0i и 1ix — в противном случае; 4) используем дво-
ичный поиск для нахождения ,i что является наименьшим ,i для которого
может найти согласованную функцию h на выборке ;)},{(
g
ittt
i xzW 5) если
,1i возвращаем h и глубину ,1 1sE иначе — h и глубину .1 i
sE
Отметим, что процедура определения гипотезы, аппроксимирующая гипотезу
с минимальной эмпирической ошибкой, является NP-сложной задачей [7]. Однако
согласованная гипотеза может быть найдена за полиномиальное время на основе
линейного программирования с использованием линейного классификатора [8].
Анализ алгоритма приближения взвешенного среднего значения
Лемма 2. Гипотеза h и глубина E всегда будут возвращаться алгоритмом
приближения взвешенного среднего значения.
Международный научно-технический журнал
«Проблемы управления и информатики», 2016, № 5 149
Доказательство. Необходимо показать, что i такое, что алгоритм будет
возвращать функцию согласованности h относительно .iW Иными словами, не-
обходимо установить, что двоичный поиск будет всегда находить .gi
Можно утверждать, что поскольку )},,{( gg
g xzW выборка будет содер-
жать только один элемент данных gz с такой меткой ,gx что, по крайней мере,
половина функций в Q являются таковыми, что .)( ggl xzh Отсюда следует, что
существует функция ,h которая является согласованной с данной выборкой.
Лемма доказана.
Далее приводим теорему, которая доказывает корректность глубины, вычис-
ленной с помощью алгоритма приближения взвешенного среднего значения.
Теорема 4. Пусть гипотеза h и глубина E возвращаются алгоритмом приб-
лижения взвешенного среднего значения. Тогда ).(hEE W
Q
Доказательство. Предположим, что })(:{)( ii xzcicX является множест-
вом образов, на котором функция согласуется с меткой. Расчетная глубина функ-
ции определяется следующим образом:
.min),1(minmin)(
)()(
i
cXi
i
cXi
W
Q sscE (11)
Можно предположить, что )}(:{min cXiii и )}.(:{max cXiii
В результате определение расчетной глубины можно представить в форме
),),1((min)(
ii
W
Q sscE (12)
учитывая упорядоченность .is Заметим, что ,1
i
s если )(cX включает все ,i и
,0
i
s если )(cX является пустым.
Далее предположим, что гипотеза h и вычислительная глубина E возвра-
щаются алгоритмом приближения взвешенного среднего значения. В случае, ког-
да 1i и i является индексом, который возвращается двоичным поиском, ве-
личины ]...,,1[)( ghX и 11)( shEW
Q принимают точные значения, возвра-
щенные алгоритмом приближения взвешенного среднего значения. Иначе, если
,1i то ),(1 hXi при условии что ).(]...,,[ hXgi
В результате, поскольку для i имеет место неравенство 5,01 is
(учитывая, что ),5,0
1
i
s точным значением, возвращенным алгоритмом приб-
лижения взвешенного среднего значения, является .)(
1
i
W
Q shE
Теорема доказана.
Как уже было показано, эмпирическая глубина функции является функцией
множества точек, на которых она согласуется с большинством образов. Для доказате-
льства, что максимальная оценка эмпирической глубины возвращается алгоритмом
приближения взвешенного среднего значения, имеет место следующая теорема.
Теорема 5. Пусть h — функция, возвращенная алгоритмом приближения
взвешенного среднего значения. Тогда
).(maxarg hEh W
Q
h
(13)
150 ISSN 0572-2691
Доказательство. При условии, если ,1i эмпирическая глубина h являе-
тся максимальной. Отсюда следует, что 1i и ,)(
1
i
W
Q shE где i является
значением, которое возвращено двоичным поиском, а h — функцией, возвра-
щенной моделью согласованности. В случае, когда ii такое, что ,)( ii xzc
выполняется неравенство
),()(
11 hEsscE W
Qii
W
Q
(14)
где .c Учитывая тот факт, что этап двоичного поиска в алгоритме приближе-
ния взвешенного среднего значения может сгенерировать 1i или большее
множество, необходимо, чтобы
11
)(
ii
xzc для , ii где .)( ii xzc В ре-
зультате ).()(
1
hEscE W
Qi
W
Q
Теорема доказана.
Следующая теорема является основным результатом оценки приближения
взвешенного среднего значения.
Теорема 6. Имеют место следующие свойства алгоритма приближения взве-
шенного среднего значения: а) предположим, что .0, Можно утверждать,
что с вероятностью не менее
)2/(12 2)2,()2(exp1 ggrfmg (15)
функция ,h которая возвращена алгоритмом приближения взвешенного среднего
значения, такова, что
,2)(sup2)(sup)(
,0,
cEcEhE
HcHc
(16)
где r — минимум между размерностью Вапника–Червоненкиса и Вапника–
Червоненкиса ; выборка W взята из ,g так что ,/8 g а выборка Q —
из ;m б) если h является функцией, которая вовращена алгоритмом приближе-
ния взвешенного среднего значения, то );(argmax hEh W
Qh в) если h и E —
выходы алгоритма приближения взвешенного среднего значения, то );(hEE W
Q
г) алгоритм всегда будет останавливаться и возвращать функцию h и эмпи-
рическую глубину .E
Доказательство. Для доказательства свойства а) предположим, что
),(sup
,0
hEE h
где h — максимальная оценка ).(hEW
Q Как уже было показа-
но, с вероятностью
2/)(12 2)2,()2(exp1 ggrfmg (17)
имеем, что
EcEcEhE
c
W
Q
c
W
Q )(sup)(max)( ,0
(18)
при условии, если ,r как минимум, меньше размерностей Вапника–Червоненки-
са и . Кроме того, очевидно, что ,)()( ,
hEhEW
Q если .)(, EhE
Международный научно-технический журнал
«Проблемы управления и информатики», 2016, № 5 151
Отсюда следует, что справедливо неравенство EhE
)(
,
или
)(
,
hE
.2)( EhEW
Q
Доказательство свойств б)–г) следует из результатов теорем 5, 4 и леммы 2
соответственно.
Теорема доказана.
Реализация алгоритма приближения взвешенного среднего значения
Итак, реализация может быть обеспечена при условии соответствия та-
ким трем системам: алгоритму обучения , который возвращает гипотезу
(при условии ее существования), согласованную с выборкой образов; сис-
теме, способной классифицировать непомеченнные образы ;...,,1 gzz системе,
способной классифицировать гипотезы mhh ...,,1 из доверительного распре-
деления . Первая система не имеет слишком ограничительный характер, по-
скольку большинство алгоритмов может быть существенно упрощено на ос-
нове гипотезы, которая согласуется со всей выборкой, в отличие от гипотезы,
которая минимизирует количество ошибок. Вторая система является также
элементарной, поскольку алгоритм приближения взвешенного среднего зна-
чения превращает алгоритм согласованности в алгоритм обучения с части-
чным привлечением учителя [9]. Нахождение выборочных гипотез, что являе-
тся требованием для третьей системы, требует проведения более глубоких
исследований.
Отметим, что несмотря на наложение жестких ограничений процедура полу-
чения данных из непрерывных классов гипотез очень проблематична. В частнос-
ти, теоретически возможно получение данных из , что является одномерным на
выпуклом теле, однако на практике это требует значительных ресурсов. Поэтому
для оценки предельной величины ]1)([]|1[ zcPzZX c алгоритм оцен-
ки глубины и алгоритм приближения взвешенного среднего значения исполь-
зуют соответствующую выборку функций. Заметим, что существует также воз-
можность непосредственной оценки данной величины, где указанные алгори-
тмы могут выводить действительное значение, знак выхода которого является
амплитудой предельной величины и предусмотренной меткой. В данном слу-
чае можно рассматривать оценку ]|1[ zZX на основе сигмоиды.
Кроме того, применяя 0 к результатам теорем 1 и 6, алгоритм вычисле-
ния вероятностей можем использовать в процессе поиска взвешенного среднего
значения.
Альтернативный подход состоит в получении данных из распределе-
ния , аппроксимирующего . В данном случае применяется повторное
взвешивание функций при вычислении ).|( zhEQ Заметим, что для нахожде-
ния приближенного взвешенного среднего значения с использованием алгори-
тма приближения взвешенного среднего значения и для оценки глубины с
применением алгоритма измерения глубины вычисление )|( zhEQ является
таким, что близко к ).|( zhE
Учитывая приведенные предположения, вычислим только эмпирическую
условную глубину ).|( zhEQ Для этого необходимо получить оценку для
)|( zhE на заданной выборке ,Q взятой из :
152 ISSN 0572-2691
Поскольку имеют место равенства )]()([)|( zhzcPzhE c и )|( zhEQ
,1
1
)()( zhzh
l
lm
можно утверждать, что
)()(
,
1
)(
)(1
)( zhzh
l l
l
d
d
Q lhd
hd
m
hE
(19)
при заданной функции относительной плотности
d
d
и выборке ,Q где .}{ 1
m
llhQ
Итак, имеем, что
),|()]()([
1
]1[
1
)]|([ )()( zhEzhzhP
mm
zhE
l
l
l
zhzhQQ l
m
(20)
при условии если Q выбрано из .m
Далее покажем, что )(
,
hE
d
d
Q
концентрируется вокруг своего математиче-
ского ожидания и является несмещенной оценкой ).|( zhE
Теорема 7. Пусть и — вероятностные меры на . Тогда h
)|()(
,
zhEhE
d
d
QQ m
и ,
2
exp2)|()(
2
2
,
u
m
zhEhEP
d
d
QQ m
если
d
d
ограничена таким образом, что .u
d
d
Доказательство. Для того чтобы показать, что h
)(
,
hE
d
d
QQ m
),|( zhE отметим, что
)()(,
1
)(
)(1)(
zhzh
l l
l
Q
d
d
QQ l
mm
hd
hd
m
hE
)(1
)(
)(
1
)(
)(
)()()()( cd
cd
cd
cd
cd
zhzc
c
zhzcc
).|()(1 )()( zhEcdzhzc
c
(21)
Если
d
d
ограничена таким образом, что ,u
d
d
то доказательство не-
равенства
2
2
,
2
exp2)|()(
u
mzhEhEP
d
d
Q
Q m
следует с объеди-
нения равенства (21) с пределом Хефдинга.
Теорема доказана.
Алгоритмы полупространственной глубины
и полупространственного взвешенного среднего значения
Заключительный этап исследования состоит в определении того, как
предложенные алгоримы могут быть применены к задачам вычисления функ-
ции полупространственной глубины и нахождения полупространственного
Международный научно-технический журнал
«Проблемы управления и информатики», 2016, № 5 153
взвешенного среднего значения. Поскольку полупространственная глубина
может рассматриваться как частный случай относительной глубины, алго-
ритм оценки глубины и алгоритм приближения взвешенного среднего значе-
ния могут использоваться для вычисления полупространственной глубины и
аппроксимации полупространственного взвешенного среднего значения соо-
тветственно.
Предположим, что имеет место выборка mhh ...,,1 элементов данных в R r
, а
также выборка направлений и смещений интереса. Иными словами, имеет место
выборка таких ,iz что R,Wiz где W — единичная сфера. В данном случае
элементы iz представлены в виде комбинации r -мерного единичного вектора
b
iz
и смещения .iz
Алгоритм оценки полупространственной глубины позволяет использовать
данные выборки для оценки полупространственной глубины элемента .R rh
Алгоритм приближения полупространственного взвешенного среднего значения
показывает, как использовать данные выборки для приближения полупростран-
ственного взвешенного среднего значения [10]. Следует заметить, что размер-
ность Вапника–Червоненкиса для данных задач равна .r
Поскольку задача вычисления полупространственной глубины требует
нахождения инфимума по всем возможным направлениям, предложенный ал-
горитм приближения находит минимум на множестве всех возможных напра-
влений в выборке .W В данном случае выбор
b
iz проводится равномерно с
единичной сферы при генерации выборки. Заметим, что выбор
iz
в предло-
женных алгоритмах следует проводить случайным образом. Однако когда
b
iz
является фиксированным, нахождение минимальной глубины по всем возмо-
жным направлениям
iz возможно для случая линейных функций. Данная
процедура может быть выполнена путем подсчета числа lh таким образом,
что
b
i
b
il zhzh (или ),b
i
b
il zhzh после чего необходимо выбрать мини-
мальное значение.
Итак, на вход алгоритма оценки полупространственной глубины подаются
выборка },...,,{ 1 gzzW такая что W;iz выборка },...,,{ 1 mhhQ такая что
;R r
lh и элемент данных .R rh На выходе получаем ),(hEW
Q что является
приближением для глубины .h Алгоритм оценки полупространственной глубины
состоит из следующих шагов: 1) для gi ...,,1 вычислить )|( iQ zhE
);:,:(min
1
iilliill zhzhhzhzhh
m
2) возвратить ).|(min)( ii
W
Q zhEhE
Алгоритм приближения полупространственного взвешенного среднего
значения позволяет определить множество случайных направлений ....,,1 gzz
При этом взвешенное среднее значение h должно занимать центральное мес-
то в каждом направлении. Кроме того, проекция h должна иметь большую
одномерную глубину, т.е. она должна быть близкой к взвешенному среднему
значению проекции при проектировании mhh ...,,1 и h на .iz Поэтому первый
154 ISSN 0572-2691
шаг заключается в нахождении h с максимально возможной глубиной в каж-
дом направлении. Когда такое h не существует, необходимо уменьшить тре-
бование глубины в каждом направлении и повторить процедуру нахождения
соответствующего .h
Алгоритм приближения полупространственного взвешенного среднего зна-
чения принимает на входе выборку },...,,{ 1 gzzW такую, что W;iz и выбор-
ку },...,,{ 1 mhhQ такую, что .R r
lh Кроме того, имеем линейный програ-
ммный алгоритм , который находит элемент данных (если таковой существует),
что согласовывается с ограничениями на заданном множестве линейных ограни-
чений. На выходе алгоритма получаем элемент данных
rh R и его оценку глу-
бины ).(hEW
Q Алгоритм приближения полупространственного взвешенного сред-
него значения состоит из следующих шагов: 1) для gi ...,,1 и ml ...,,1 вычис-
лить ;il zh 2) пусть
m
ii ww ...,,1
— классифицированные значения ;il zh
3) использовать двоичный поиск для нахождения наименьшего ,2/...,,0 mt для
которого может найти такое ,h что ;,
]2/[]2/[ tm
ii
tm
i wzhwi
4) возвра-
тить значение ,]2/[ hm которое алгоритм нашел для наименьшего t на шаге 3.
Напоследок отметим, что алгоритм приближения полупространственного
взвешенного среднего значения позволяет ускорить данную процедуру с по-
мощью двоичного поиска. Поскольку указанные процессы используют только
скалярные произведения, перспективным остается исследование их ядерных
модификаций.
В данной работе представлены эффективные алгоритмы равномерного
измерения относительной глубины данных и нахождения относительного
взвешенного среднего значения в рамках исследования проблемы выбора оп-
тимальной гипотезы в задачах многомерной классификации. Предложенные
алгоритмы позволяют аппроксимировать за полиномиальное время значение
полупространственной глубины, а также полупространственное взвешенное
среднее значение, которые яляются частным случаем относительной глубины
данных.
О.А. Галкін
АЛГОРИТМИ РОЗВ’ЯЗАННЯ ЗАДАЧ
КЛАСИФІКАЦІЇ НА ОСНОВІ АПРОКСИМАЦІЇ
ВІДНОСНОЇ ГЛИБИНИ ДАНИХ
ТА ЗВАЖЕНОГО СЕРЕДНЬОГО ЗНАЧЕННЯ
Розглянуто актуальну проблему вибору оптимальної гіпотези в задачах
класифікації з використанням концепції зваженого середнього значення та
функцій глибини. Розроблено та досліджено модифіковані алгоритми для
апроксимації відносної глибини даних та відносного зваженого середнього
значення розподілу. Запропоновані алгоритми забезпечують поліноміальні
наближення до напівпросторової глибини даних та напівпросторового зва-
женого середнього значення розподілу, що є окремим випадком сімейства
зважених середніх значень.
Международный научно-технический журнал
«Проблемы управления и информатики», 2016, № 5 155
A.A. Galkin
THE ALGORITHMS FOR SOLVING
CLASSIFICATION PROBLEMS BASED
ON THE APPROXIMATION OF RELATIVE DATA
DEPTH AND WEIGHTED AVERAGE VALUE
An actual problem of choosing the optimal hypothesis in classification problems us-
ing the concept of weighted average value and depth functions are considered. The
modified algorithms are constructed and studied to approximate the relative data
depth and relative weighted average value of distribution. The proposed algorithms
provide polynomial approximations to the half-space data depth and half-space
weighted average value which is a special case of the weighted averages family.
1. Godtliebsen F., Marron J.S., Chaudhuri P. Significance in scale space for bivariate density esti-
mation // Journal of Computational and Graphical Statistics. — 2002. — 11. — P. 1–22.
2. Herbrich R., Graepel T., Campbell C. Bayes point machines // The Journal of Machine Learning
Research. — 2001. — 1. — P. 247–271.
3. Seeger M. PAC-Bayesian generalisation error bounds for gaussian process classification //
Ibid. — 2003. — 3. — P. 237–268.
4. Holmes C.C., Adams N.M. A probabilistic nearest neighbor method for statistical pattern recogni-
tion // Journal of the Royal Statistical Society. — 2002. — 64. — P. 295–306.
5. Davies P.L., Gather U. Breakdown and groups // The Annals of Statistics. — 2005. — 33(3). —
P. 981–1027.
6. Zuo Y., Serfling R. General notions of statistical depth function // Ibid. — 2000. — 28(2). —
P. 464–480.
7. Billor N., Abebe A., Turkmen A., Nudurupati S.V. Classification based on depth transvariations //
Journal of classification. — 2008. — 25(2). — P. 253–259.
8. Fine S., Gilad-Bachrach R., Shamir E. Query by committee, linear separation and random walks //
Theoretical Computer Science. — 2002. — 284(1). — P. 27–49.
9. Ben-David S., Eiron N., Long P.M. On the difficulty of approximately maximizing agreements //
Journal of Computer and System Sciences. — 2003. — 66(3). — P. 499–511.
10. Lange T., Mosler K., Mozharovskyi P. Fast nonparametric classification based on data depth //
Statistical Papers. — 2014. — 55. — P. 53–67.
Получено 07.04.2016
Статья представлена к публикации чл.-корр. НАН Украины А.В. Анисимовым.
|
| id | nasplib_isofts_kiev_ua-123456789-208263 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2025-12-07T18:32:55Z |
| publishDate | 2016 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Галкин, А.А. 2025-10-23T17:56:27Z 2016 Алгоритмы решения задач классификации на основе аппроксимации относительной глубины данных и взвешенного среднего значения / А.А. Галкин // Проблемы управления и информатики. — 2016. — № 5. — С. 144-155. — Бібліогр.: 10 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/208263 519.7 10.1615/JAutomatInfScien.v48.i10.80 Розглянуто актуальну проблему вибору оптимальної гіпотези в задачах класифікації з використанням концепції зваженого середнього значення та функцій глибини. Розроблено та досліджено модифіковані алгоритми для апроксимації відносної глибини даних та відносного зваженого середнього значення розподілу. Запропоновані алгоритми забезпечують поліноміальні наближення до напівпросторової глибини даних та напівпросторового зваженого середнього значення розподілу, що є окремим випадком сімейства зважених середніх значень. An actual problem of choosing the optimal hypothesis in classification problems using the concept of weighted average value and depth functions are considered. The modified algorithms are constructed and studied to approximate the relative data depth and relative weighted average value of distribution. The proposed algorithms provide polynomial approximations to the half-space data depth and half-space weighted average value which is a special case of the weighted averages family. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Роботы и системы искусственного интеллекта Алгоритмы решения задач классификации на основе аппроксимации относительной глубины данных и взвешенного среднего значения Алгоритми розв’язання задач класифікації на основі апроксимації відносної глибини даних та зваженого середнього значення The algorithms for solving classification problems based on the approximation of relative data depth and weighted average value Article published earlier |
| spellingShingle | Алгоритмы решения задач классификации на основе аппроксимации относительной глубины данных и взвешенного среднего значения Галкин, А.А. Роботы и системы искусственного интеллекта |
| title | Алгоритмы решения задач классификации на основе аппроксимации относительной глубины данных и взвешенного среднего значения |
| title_alt | Алгоритми розв’язання задач класифікації на основі апроксимації відносної глибини даних та зваженого середнього значення The algorithms for solving classification problems based on the approximation of relative data depth and weighted average value |
| title_full | Алгоритмы решения задач классификации на основе аппроксимации относительной глубины данных и взвешенного среднего значения |
| title_fullStr | Алгоритмы решения задач классификации на основе аппроксимации относительной глубины данных и взвешенного среднего значения |
| title_full_unstemmed | Алгоритмы решения задач классификации на основе аппроксимации относительной глубины данных и взвешенного среднего значения |
| title_short | Алгоритмы решения задач классификации на основе аппроксимации относительной глубины данных и взвешенного среднего значения |
| title_sort | алгоритмы решения задач классификации на основе аппроксимации относительной глубины данных и взвешенного среднего значения |
| topic | Роботы и системы искусственного интеллекта |
| topic_facet | Роботы и системы искусственного интеллекта |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/208263 |
| work_keys_str_mv | AT galkinaa algoritmyrešeniâzadačklassifikaciinaosnoveapproksimaciiotnositelʹnoiglubinydannyhivzvešennogosrednegoznačeniâ AT galkinaa algoritmirozvâzannâzadačklasifíkacíínaosnovíaproksimacíívídnosnoíglibinidanihtazvaženogoserednʹogoznačennâ AT galkinaa thealgorithmsforsolvingclassificationproblemsbasedontheapproximationofrelativedatadepthandweightedaveragevalue |