Построение линейных классификаторов на основе использования опорных функций
Предложен алгоритм построения линейных бинарных классификаторов. Объекты распознавания представляются выпуклыми компактами евклидового пространства. Алгоритм основан на использовании опорных функций выпуклых компактов и методов негладкой оптимизации. Запропоновано алгоритм побудови лінійних бінарних...
Gespeichert in:
| Veröffentlicht in: | Теорія оптимальних рішень |
|---|---|
| Datum: | 2016 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2016
|
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/113030 |
| 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: | Построение линейных классификаторов на основе использования опорных функций / Н.Г. Журбенко // Теорія оптимальних рішень: Зб. наук. пр. — 2016. — № 2016. — С. 137-141. — Бібліогр.: 7 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-113030 |
|---|---|
| record_format |
dspace |
| spelling |
Журбенко, Н.Г. 2017-01-31T16:55:19Z 2017-01-31T16:55:19Z 2016 Построение линейных классификаторов на основе использования опорных функций / Н.Г. Журбенко // Теорія оптимальних рішень: Зб. наук. пр. — 2016. — № 2016. — С. 137-141. — Бібліогр.: 7 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/113030 519.8 Предложен алгоритм построения линейных бинарных классификаторов. Объекты распознавания представляются выпуклыми компактами евклидового пространства. Алгоритм основан на использовании опорных функций выпуклых компактов и методов негладкой оптимизации. Запропоновано алгоритм побудови лінійних бінарних класифікаторів. Об’єкти розпізнавання представляються опуклими компактами евклідового простору. Алгоритм заснований на використанні опорних функцій опуклих компактів і методів негладкої оптимізації. An algorithm for construction of linear binary classifiers is proposed. The objects of recognition are presented by convex compacts of Euclidean space. The algorithm is based on the use of support functions of convex compacts and nonsmooth optimization methods. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Построение линейных классификаторов на основе использования опорных функций Побудова лінійних класифікаторів на основі використання опорних функцій The construction of linear classifiers on the basis of support functions Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Построение линейных классификаторов на основе использования опорных функций |
| spellingShingle |
Построение линейных классификаторов на основе использования опорных функций Журбенко, Н.Г. |
| title_short |
Построение линейных классификаторов на основе использования опорных функций |
| title_full |
Построение линейных классификаторов на основе использования опорных функций |
| title_fullStr |
Построение линейных классификаторов на основе использования опорных функций |
| title_full_unstemmed |
Построение линейных классификаторов на основе использования опорных функций |
| title_sort |
построение линейных классификаторов на основе использования опорных функций |
| author |
Журбенко, Н.Г. |
| author_facet |
Журбенко, Н.Г. |
| publishDate |
2016 |
| language |
Russian |
| container_title |
Теорія оптимальних рішень |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Побудова лінійних класифікаторів на основі використання опорних функцій The construction of linear classifiers on the basis of support functions |
| description |
Предложен алгоритм построения линейных бинарных классификаторов. Объекты распознавания представляются выпуклыми компактами евклидового пространства. Алгоритм основан на использовании опорных функций выпуклых компактов и методов негладкой оптимизации.
Запропоновано алгоритм побудови лінійних бінарних класифікаторів. Об’єкти розпізнавання представляються опуклими компактами евклідового простору. Алгоритм заснований на використанні опорних функцій опуклих компактів і методів негладкої оптимізації.
An algorithm for construction of linear binary classifiers is proposed. The objects of recognition are presented by convex compacts of Euclidean space. The algorithm is based on the use of support functions of convex compacts and nonsmooth optimization methods.
|
| issn |
XXXX-0013 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/113030 |
| citation_txt |
Построение линейных классификаторов на основе использования опорных функций / Н.Г. Журбенко // Теорія оптимальних рішень: Зб. наук. пр. — 2016. — № 2016. — С. 137-141. — Бібліогр.: 7 назв. — рос. |
| work_keys_str_mv |
AT žurbenkong postroenielineinyhklassifikatorovnaosnoveispolʹzovaniâopornyhfunkcii AT žurbenkong pobudovalíníinihklasifíkatorívnaosnovívikoristannâopornihfunkcíi AT žurbenkong theconstructionoflinearclassifiersonthebasisofsupportfunctions |
| first_indexed |
2025-11-26T00:08:23Z |
| last_indexed |
2025-11-26T00:08:23Z |
| _version_ |
1850592100541792256 |
| fulltext |
Теорія оптимальних рішень. 2016 137
ТЕОРІЯ
ОПТИМАЛЬНИХ
РІШЕНЬ
Предложен алгоритм построения
линейных бинарных классифи-
каторов. Объекты распознавания
представляются выпуклыми ком-
пактами евклидового простран-
ства. Алгоритм основан на ис-
пользовании опорных функций
выпуклых компактов и методов
негладкой оптимизации.
Н.Г. Журбенко, 2016
УДК 519.8
Н.Г. ЖУРБЕНКО
ПОСТРОЕНИЕ ЛИНЕЙНЫХ
КЛАССИФИКАТОРОВ
НА ОСНОВЕ ИСПОЛЬЗОВАНИЯ
ОПОРНЫХ ФУНКЦИЙ
Введение. Обычно объект распознавания для
линейного классификатора представляется
точкой в n -мерном евклидовом простран-
стве .nR Однако возникают задачи, когда
объект распознавания представляется более
сложным образом. Это может быть связано
с погрешностями измерения параметров
объекта или для параметра объекта задается
диапазон его значений. Последнее харак-
терно для задач медицинской диагностики.
В работе [1] объект распознавания опреде-
лялся эллипсоидом в .nR В данной работе
предполагается, что объект распознавания
определялся выпуклым компактом в .nR
В работе представляется описание алго-
ритма построения линейных бинарных клас-
сификаторов для такого достаточно широко-
го класса задач. Приводится также краткое
описание разработанного программного
обеспечения.
Линейный классификатор и опорная
функция. Линейный бинарный классифи-
катор ),( cbL задается ненулевым вектором
0, bRb n и константой .1Rc Классифи-
катор ),( cbL определяет открытые полу-
пространства в
nR :
};0),(|{ cbxRxR n
{ | ( , ) 0}.nR x R x b c
Объект распознавания представляется
выпуклым компактом W в .nR Объект
распознается классификатором, если RW
(«объект класса 1») или RW («объект
класса 2»). В противном случае говорим, что
Н.Г. ЖУРБЕНКО
138 Теорія оптимальних рішень. 2016
объект W не распознается классификатором ( , ).L b c Объект распознается
классификатором, если RW («объект класса 1») или RW («объект
класса 2»). В противном случае говорим, что объект W не распознается
классификатором ),( cbL .
Пусть )(uh опорная функция [2], выпуклого компакта :W
( ) max{( , ) | }.h u x u x W (1)
)(uh – выпуклая функция, )(uh – положительно однородна и субаддитивна
на nR : ( ) ( ) при 0;h u h u ).()()( vhuhvuh
Пусть )(ux – некоторое (возможно не единственное) решение задачи (1):
).),(()( uuxuh Из задачи (1) следует, что )(ux – субградиент опорной функции
).(uh Таким образом )(ux определяет не только значение опорной функции, но
и ее субградиент в точке u .
Приведем примеры опорной функции.
1. W – точка в : { }.n nR W z R ).,()(;)( uzuhzux
2. W – эллипсоид в },)(,(|{: 2rzxDzxRxWR nn где
nRz –
центр эллипсоида; D – положительно определенная матрица nn ; .0r
1
1
, 0;
( ) ( ,
0, 0.
r
D u u
x u z u D u
u
1( ) ( , ) ( , .h u z u r u D u
Нетрудно показать справедливость следующих отношений экви-
валентности:
RW ( ( ), ) 0;x b b c (2)
RW .0)),(( cbbx (3)
Из )()),(()),(( bhbbxbbx следует:
RW ;0)( cbh (4)
RW ( ) 0.h b c (5)
Отметим также следующее свойство опорных функций ([2], теорема 12.4).
Пусть iW – непустые выпуклые компакты в nR с опорными функциями
, 1, .ih i m
1
m
i
i
W conv W
(W – выпуклая оболочка множеств iW ).
Тогда )(max)(
1
uhuh i
mi
– опорная функция компакта .W
ПОСТРОЕНИЕ ЛИНЕЙНЫХ КЛАССИФИКАТОРОВ НА ОСНОВЕ ИСПОЛЬЗОВАНИЯ ...
Теорія оптимальних рішень. 2016 139
Заметим, что отсюда следует достаточно очевидный факт: если линейный
классификатор разделяет два множества компактов ,, 21 II то этот клас-
сификатор разделяет и множества
1 2( ), ( ).conv I conv I
Задача определения классификатора ),( cbL состоит в следующем. Задана
«обучающая выборка»: множество 1I (
1 1| |m I ) объектов класса 1; множество
2I (
2 2| |m I ) объектов класса 2. Необходимо определить классификатор ),( cbL
«правильно» определяющий класс этих объектов (в этом случае плоскость
}0),(|{ cbxRx n «разделяет» множества 21, II ). То есть необходимо
определить классификатор ),( cbL , для которого справедливы соотношения:
;,0)( 1Iicbhi .,0)( 2Iicbhi (6)
Система (6) эквивалентна системе
;0}|)(max{ 1 Iicbhi .0}|)(max{ 2 Iicbhi
Таким образом, формально определение классификатора ),( cbL сводится
к решению системы (6). Однако решение этой системы может быть не
единственно или система несовместна. Поэтому возникает достаточно сложная
проблема определения «хорошего» классификатора как для случая совме-
стности, так и несовместности (6). Этой проблеме посвящено множество
публикаций [3]. Разумеется, предлагаемый далее алгоритм построения клас-
сификатора не претендует на решение этой проблемы.
Алгоритм определения классификатора. В данном пункте приводится
краткое описание предлагаемого алгоритма определения классификатора.
Фактически этот алгоритм является обобщением алгоритма работы [1] на
случай представления объектов распознавания выпуклыми компактами .nR
В работе [4] был предложен робастный алгоритм решения задачи
построения разделяющей гиперплоскости для двух множеств точек. В работе [5]
для ее решения использовался алгоритм негладкой оптимизации – r-алгоритм
[6]. По аналогии работы [1] построим двухэтапный алгоритм для рассматри-
ваемой задачи, в которой объектами выборок являются компакты.
На первом этапе определяются параметры *b и *c путем решения задачи
минимизации выпуклой негладкой функции :),( cbF
1 2
,
1 2
1 1
min ( , ) max{0; ( ) 1} max{0; ( ) 1} .i i
b c
i I i I
F b c h b c h b c
m m
(7)
На втором этапе проводится процедура улучшения разделяющей гипер-
плоскости по переменной .c Эта процедура состоит в решении следующей
задачи минимизации выпуклой одномерной кусочно-линейной выпуклой
функции:
Н.Г. ЖУРБЕНКО
140 Теорія оптимальних рішень. 2016
1 2
* *
1 2
1 1
min max{0; ( ) } max{0; ( ) } .i i
c
i I i I
h b c h b c
m m
Основная численная трудоемкость описанной модели состоит в решении задачи
первого этапа (6).
Модель (7) в основном отражает интуитивные представления разделения
двух классов объектов. Так, например, если классы разделимы, то так
определяемый классификатор также их разделяет. При этом значение целевой
функции в задаче (7) равно нулю.
Недостатком модели (7) является то, что она не обеспечивает построение
разделяющей полосы максимальной ширины. Поэтому решение задачи
проводится по следующей схеме. Если в результате решения задачи (7)
определено, что классы разделимы, то решается следующая задача (задача
определения классификатора с максимальным «зазором» [1]):
* * 2
1 2
,
1
( , ) min max ( ) , ; ( ) , ; | 1 .
n
i i i
b c
i
F b c h b c i I h b c i I b
(8)
Алгоритмы решения задач (7), (8) основаны на использовании методов
негладкой оптимизации.
Замечание. Если классификатор правильно распознает не все объекты
обучающей выборки (ситуация неразделимости множеств
1 2,I I ), то это не
означает его непригодность. Это может быть связано с ошибками самой
обучающей выборки. Однако более реалистично, что поставленная задача
классификации не может быть точно формализована в рамках принятой модели.
Качество линейного классификатора может определяться лишь на основе
статистического анализа результатов для представительного множества
обучающих выборок.
Программное обеспечение. Программная реализация описанных алго-
ритмов представлена классами в объектно-ориентированном стиле на языке
С++. Разработанные классы отображают концепции объектов рассматриваемых
задач (линейный классификатор, объект распознавания, обучающая выборка).
Программное обеспечение может использоваться для построения линейного
классификатора любых объектов, определяемых выпуклыми компактами в .nR
Для этого пользователю достаточно определить опорную функцию распо-
знавательных объектов его задачи. Опорная функция объекта определяется
функцией-членом определяемого пользователем класса объекта. Эта функция
объявлена как чисто виртуальная функция абстрактного класса
CObjectRecognition (класс CObjectRecognition реализует концепцию «объект
распознавания»).
Кроме абстрактных классов программное обеспечение содержит
конкретные классы (порожденные от соответствующих абстрактных классов). В
частности, имеются классы представления таких объектов распознавания как
точка, шар, эллипс.
ПОСТРОЕНИЕ ЛИНЕЙНЫХ КЛАССИФИКАТОРОВ НА ОСНОВЕ ИСПОЛЬЗОВАНИЯ ...
Теорія оптимальних рішень. 2016 141
Программная реализация решения задач (7), (8) основана на модификациях
r-алгоритма [7].
М.Г. Журбенко
ПОБУДОВА ЛІНІЙНИХ КЛАСИФІКАТОРІВ НА ОСНОВІ ВИКОРИСТАННЯ ОПОРНИХ
ФУНКЦІЙ
Запропоновано алгоритм побудови лінійних бінарних класифікаторів. Об’єкти розпізнавання
представляються опуклими компактами евклідового простору. Алгоритм заснований на
використанні опорних функцій опуклих компактів і методів негладкої оптимізації.
N.G. Zhurbenko
THE CONSTRUCTION OF LINEAR CLASSIFIERS ON THE BASIS OF SUPPORT
FUNCTIONS
An algorithm for construction of linear binary classifiers is proposed. The objects of recognition are
presented by convex compacts of Euclidean space. The algorithm is based on the use of support
functions of convex compacts and nonsmooth optimization methods.
1. Березовский О.А., Журбенко Н.Г., Стецюк П.И. Алгоритмы построения линейных
бинарных классификаторов при неточных измерениях // Компьютерная математика. –
Киев: Ин-т кибернетики имени В.М. Глушкова НАН Украины, 2014. – № 2. –
С. 133 – 138.
2. Лейхтвейс К. Выпуклые множества. – М.: Наука, 1985. – 336 с.
3. Шлезингер М., Главач В. Десять лекций по статистическому и структурному распо-
знаванию. – Киев: Наук. думка, 2004. – 545 с.
4. Bennett K.P., Mangasarian O.L. Robust Linear Programming Discrimination of Two Linearly
Inseparable Sets // Optimization Methods and Software. – 1992. – 5 (1). – P. 23 – 34.
5. Журбенко Н.Г., Саимбетов Д.Х. К численному решению одного класса задач робастного
разделения двух множеств // Методы исследования экстремальных задач. – Киев: Ин-т
кибернетики имени В.М. Глушкова НАН Украины, 1994. – С. 52 – 55.
6. Шор Н.З., Журбенко Н.Г. Метод минимизации, использующий операцию растяжения
пространства в направлении разности двух последовательных градиентов // Кибернетика.
– 1971. – № 3. – С. 51 – 59.
7. Шор Н.З., Журбенко Н.Г., Лиховид А.П. и др. Развитие алгоритмов недифференцируемой
оптимизации и их приложения // Кибернетика и системный анализ. – 2003. – № 4. –
С. 80 – 94.
Получено 19.04.2016
|