Построение классификаторов на основе разделяющих поверхностей
В статье рассматривается проблема построения полиномиальной разделяющей гиперповерхности для задачи классификации двух классов изображений. Предлагается итерационный метод, позволяющий получать разделяющие гиперповерхности с учетом особенностей расположения обучающих объектов на границе между кла...
Saved in:
| Date: | 2008 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем штучного інтелекту МОН України та НАН України
2008
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/6712 |
| 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: | Построение классификаторов на основе разделяющих поверхностей / К.В. Мурыгин // Штучний інтелект. — 2008. — № 2. — С. 65-69. — Бібліогр.: 5 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859645356140134400 |
|---|---|
| author | Мурыгин, К.В. |
| author_facet | Мурыгин, К.В. |
| citation_txt | Построение классификаторов на основе разделяющих поверхностей / К.В. Мурыгин // Штучний інтелект. — 2008. — № 2. — С. 65-69. — Бібліогр.: 5 назв. — рос. |
| collection | DSpace DC |
| description | В статье рассматривается проблема построения полиномиальной разделяющей гиперповерхности для
задачи классификации двух классов изображений. Предлагается итерационный метод, позволяющий
получать разделяющие гиперповерхности с учетом особенностей расположения обучающих объектов
на границе между классами. Метод основан на взвешивании обучающих объектов в зависимости от
их удалённости от межклассовой границы.
У статті розглядається проблема побудови поліноміальної поділяючої гіперповерхні для задачі
класифікації двох класів зображень. Пропонується ітераційний метод, що дозволяє одержувати
поділяючі гіперповерхні з урахуванням особливостей розташування навчальних об’єктів на границі
між класами. Метод заснований на зважуванні навчальних об’єктів у залежності від віддалення від
границі між класами.
The paper is devoted to the problem of construction of polynomial separate surfaces for the task of two-class
images classification. It is proposed an iteration method that provide to get the coefficients of separate hyper
surfaces based on taking into account of peculiarity of the location of learning examples on the boundary
between classes. The method is based on the weighting of learning examples depending on its distance from
the boundary between classes.
|
| first_indexed | 2025-12-07T13:27:06Z |
| format | Article |
| fulltext |
«Штучний інтелект» 2’2008 65
3М
УДК 004.89, 004.93
К.В. Мурыгин
Институт проблем искусственного интеллекта МОН и НАН Украины, г. Донецк
kir@iai.donetsk.ua
Построение классификаторов на основе
разделяющих поверхностей
В статье рассматривается проблема построения полиномиальной разделяющей гиперповерхности для
задачи классификации двух классов изображений. Предлагается итерационный метод, позволяющий
получать разделяющие гиперповерхности с учетом особенностей расположения обучающих объектов
на границе между классами. Метод основан на взвешивании обучающих объектов в зависимости от
их удалённости от межклассовой границы.
Введение
Почти все объекты, которые в практических задачах необходимо обнаружить
на изображениях, обладают внутриклассовой изменчивостью. Такая изменчивость
может быть связана с различными факторами как собственными свойствами
объекта, так и факторами среды, в которой происходило получение его изображения
[1-4]. Среди последних два основных фактора находят отражение в таких харак-
теристиках изображения, как яркость и контрастность.
Яркость характеризуется средней яркостью изображения, а контрастность –
средним квадратическим разбросом яркости. Вследствие необходимости инвариантной
к ним классификации обычно прибегают к нормированию сопоставляемых
изображений таким образом, чтобы средняя яркость равнялась нулю, а модуль –
единице. В этом пространстве все изображения фиксированных размеров hwN ×=
лежат на N-мерной сфере с центром в точке (0,0,…,0). Причем изображения,
принадлежащие объектам, занимают некоторую компактную область, которую и
необходимо отделить от всех остальных изображений.
Для описанного вида расположения объектов в пространстве признаков удобно
использовать полиномиальные разделяющие функции 2-го порядка и выше. Так как
пространство признаков имеет большую размерность, равную размеру самого изоб-
ражения объекта, и даже при переходе в пространство главных компонент
размерность пространства, как правило, больше 20, то для качественного описания
положения объектов в пространстве признаков обучающей последовательности
объемом даже в несколько сотен тысяч недостаточно. В этом случае велика вероят-
ность при использовании, например, градиентных методов нахождения минимума
функции ошибки прийти к локальному минимуму, что затрудняет получение
точного решения задачи классификации. Кроме этого, решение зависит от начально-
го приближения классифицирующей функции. В описанных условиях целесообразно
получить приближенный вид классифицирующей функции, основываясь на ее значе-
нии, например, в виде решающего правила, рассчитанного методом наименьших
Мурыгин К.В.
«Искусственный интеллект» 2’2008 66
3М
квадратов. После этого уже с помощью градиентных методов выполнить подстройку
коэффициентов разделяющей функции минимизацией ошибки ложной тревоги при
заданном ограничении на ошибку пропуска цели.
Целью данной работы является разработка метода получения приближенной
разделяющей поверхности для классификации двух классов, основанного на взвешен-
ном учете объектов в зависимости от их положения относительно межклассовой
границы.
Приближенная классифицирующая функция
Расчет приближенной классифицирующей функции в пространстве признаков
размерности n для двух классов, обозначенных индексами «o» и «n» по обучающей
последовательности, содержащей oN -образов 1-го класса и nN -образов 2-го класса,
основан на минимизации следующего функционала:
( )( ) ( )( )∑∑
==
+χ+−χ=Ψ
no N
1i
2ni
n
N
1i
2oi
o
m1 1a,f
N
11a,f
N
1)a,...,a( , (1)
где ( )
( )
∑
>
=
=
nmm
k
i
kk
i aaf
1
, χχ – классифицирующая функция, такая, что для первого клас-
са ( ) 1a,f oi ≈χ , а для второго – ( ) 1a,f ni −≈χ . Таким образом, геометрическое место
точек ( ) 0a,f i =χ определяет границу между классами. Приведенный функционал
соответствует методу наименьших квадратов для определения функции предпоч-
тения [5]; i
kχ – координаты образа i в спрямляющем пространстве размерности
nm > , равной числу коэффициентов разделяющей функции. Если классифици-
рующая функция ( )a,f iχ имеет k-й порядок относительно исходных признаков
n1 x,...,x и представляет собой полный полином, то размер спрямляющего прост-
ранства m будет равен
!k
)in(
m
k
1i
∏
=
+
= .
Минимизируя функционал )a,...,a( m1Ψ из условия 0
a
)a,...,a(
j
m1 =
∂
Ψ∂ , получим
систему линейных уравнений
∑∑∑ ∑∑
=== ==
χ−χ=
χχ+χχ
nono N
1i
ni
j
n
N
1i
oi
j
o
m
1k
N
1i
ni
j
ni
k
n
N
1i
oi
j
oi
k
o
k N
1
N
1
N
1
N
1a , mj ...1= ,
или в матричном виде gaA = .
Найденный с помощью такой минимизации приблизительный вид разделяющей
функции обладает существенным недостатком, который заключается в зависимости
формы классифицирующей гиперповерхности от плотности распределения обучаю-
щих объектов вдали от границы между классами. Практически всегда плотность
объектов классов вдали от границы значительно больше, чем на границе, как
правило, разреженной, что и приводит к несоответствию полученной разделяющей
функции действительной границе между классами. Такое несоответствие кроме
Построение классификаторов на основе разделяющих поверхностей
«Штучний інтелект» 2’2008 67
3M
ухудшения показателей системы обнаружения относительно ошибок первого и
второго рода на практике часто приводит к зависимости качества решения задачи
классификации от условий применения системы. Последнее может быть вызвано
неравномерным составом обучающих объектов, что почти всегда имеет место при
рассмотрении базы данных изображений.
Классифицирующая функция на основе взвешивания
обучающих объектов
Для повышения качества нахождения границы в виде разделяющей гиперпо-
верхности необходимо учитывать объекты, близкие к границе в большей степени,
чем отдаленные от нее. Для этого удобно выполнить взвешивание объектов в
обучающей последовательности. Учитывая, что в рассматриваемой постановке гра-
ница задается выражением ( ) 0a,f i =χ , для обеспечения быстрого спада влияния
объектов при удалении от границы можно воспользоваться экспоненциальной
весовой функцией вида:
( ) α
−
=
nf
efW или ( ) α
−
=
n2f
efW ,
где α и n – параметры, регулирующие скорость спада функции при отдалении от
нулевого значения.
С учетом введения весовых функций и соответствующей перенормировки
функционал (1) примет вид:
( )
( ) ( )( )
( )
( ) ( )( )∑
∑
∑
∑ =
=
=
=
+χ+−χ=Ψ
n
n
o
o
N
1i
2nii
N
1i
i
N
1i
2oii
N
1i
i
m1 1a,ffW
fW
11a,ffW
fW
1)a,...,a( . (2)
Полученный функционал при переходе к системе уравнений
0
a
)a,...,a(
j
m1 =
∂
Ψ∂
приводит уже не к линейной системе, как в предыдущем случае, а к более сложной
нелинейной зависимости, которая в матричной форме имеет вид
( ) ( )agaaA = .
Для получения решения системы можно воспользоваться итеративной процедурой
( ) ( )tt
1
1t agaAa −
+ = ,
используя в качестве нулевого приближения 0a решение, дающее минимум
исходного функционала (1), полученного для невзвешенного случая. Теоретический
вопрос о сходимости приведенной итеративной процедуры к точному решению пока
еще остается открытым, однако на практике выявлено, что получаемые решения
сходятся достаточно быстро. Как правило, проведя 10 – 20 итераций можно
гарантировать получение
( ) 001,0
1
21 =<−∑
=
+
m
i
t
i
t
i aa ε .
Результаты работы метода для двумерного случая приведены на рис. 1.
Мурыгин К.В.
«Искусственный интеллект» 2’2008 68
3М
а) б)
в) г)
Рисунок 1 – Результаты определения границы между классами в двумерном случае:
а) и в) – решения, полученные с помощью минимизации функционала (1);
б) и г) – решения, полученные на основе взвешенного функционала (2)
Полученные описанным методом решения позволяют сформировать разделяющую
функцию
( ) ( )
( )
Ω∈<
Ω∈>
=
,,0,
,,0,
,
n
ii
o
ii
i
af
af
aR
χχ
χχ
χ
не удовлетворяющую пока выдвинутым требованиям допустимой ошибки пропуска цели.
Построение классификаторов на основе разделяющих поверхностей
«Штучний інтелект» 2’2008 69
3M
Если максимальная допустимая ошибка пропуска цели задана параметром oP ,
то удовлетворить требованиям можно установкой некоторого порога oΠ на значение
разделяющей функции:
( ) ( )
( )
Ω∈Π<
Ω∈Π>
=
n
ioi
o
ioi
i
af
af
aR
χχ
χχ
χ
,,
,,
, ,
при котором доля пропусков объекта классификации по обучающей выборке будет
меньше либо равна oP . В этом случае разделяющая функция ( )a,f iχ , задаваемая
параметрами a , просто подвергается пространственному сдвигу. Более качествен-
ным методом учета требуемого ограничения на ошибку пропуска цели является
рассмотрение полученной разделяющей функции как начальной при проведении
итеративной процедуры минимизации ошибок ложной тревоги при заданном
ограничении на ошибку пропуска цели. Такая процедура может быть выполнена
любым численным методом поиска экстремума функций.
Выводы
Предложенный итерационный метод дает возможность получать разделяющие
гиперповерхности с учетом особенностей расположения обучающих объектов на
границе между классами. Это позволяет более точно определять границу между
классами в случае, если вблизи точной границы содержится относительно
небольшое число обучающих объектов. Метод может использоваться как метод
предварительного обучения, если в качестве исходной ставится задача минимизации
ошибки ложной тревоги при заданном ограничении на ошибку пропуска цели, что
часто необходимо при решении задач обнаружения объектов.
Литература
1. Мурыгин К.В. Поиск области лица на изображении методом сопоставления с эталоном с исполь-
зованием нескольких шаблонов // Проблемы бионики. – 2003. – № 59. – С. 55-59.
2. Мурыгин К.В., Нюнькин К.М. Компьютерное обнаружение лиц людей на изображении //
Программные продукты и системы. – 2001. – № 2. – C. 25-29.
3. Мурыгин К.В., Нюнькин К.М. Локализация на изображении лица человека // Труды Междунар.
конф. «Знание – Диалог – Решение». – CПб. – 2001. – С. 490-495.
4. Мурыгин К.В. Автоматический анализ цифровых изображений с целью обнаружения лиц с
боковыми поворотами // Искусственный интеллект. – 2005. – № 3. – С. 649-657.
5. Васильев В.И. Распознающие системы: Справочник. – К.: Наукова думка, 1983. – 423 с.
К.В. Муригін
Побудова класифікаторів на основі поділяючих поверхонь
У статті розглядається проблема побудови поліноміальної поділяючої гіперповерхні для задачі
класифікації двох класів зображень. Пропонується ітераційний метод, що дозволяє одержувати
поділяючі гіперповерхні з урахуванням особливостей розташування навчальних об’єктів на границі
між класами. Метод заснований на зважуванні навчальних об’єктів у залежності від віддалення від
границі між класами.
K.V. Murygin
Classifiers Construсtion Based on Separate Hyper Surfaces
The paper is devoted to the problem of construction of polynomial separate surfaces for the task of two-class
images classification. It is proposed an iteration method that provide to get the coefficients of separate hyper
surfaces based on taking into account of peculiarity of the location of learning examples on the boundary
between classes. The method is based on the weighting of learning examples depending on its distance from
the boundary between classes.
Статья поступила в редакцию 21.04.2008.
|
| id | nasplib_isofts_kiev_ua-123456789-6712 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Russian |
| last_indexed | 2025-12-07T13:27:06Z |
| publishDate | 2008 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Мурыгин, К.В. 2010-03-15T13:43:09Z 2010-03-15T13:43:09Z 2008 Построение классификаторов на основе разделяющих поверхностей / К.В. Мурыгин // Штучний інтелект. — 2008. — № 2. — С. 65-69. — Бібліогр.: 5 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/6712 004.89, 004.93 В статье рассматривается проблема построения полиномиальной разделяющей гиперповерхности для задачи классификации двух классов изображений. Предлагается итерационный метод, позволяющий получать разделяющие гиперповерхности с учетом особенностей расположения обучающих объектов на границе между классами. Метод основан на взвешивании обучающих объектов в зависимости от их удалённости от межклассовой границы. У статті розглядається проблема побудови поліноміальної поділяючої гіперповерхні для задачі класифікації двох класів зображень. Пропонується ітераційний метод, що дозволяє одержувати поділяючі гіперповерхні з урахуванням особливостей розташування навчальних об’єктів на границі між класами. Метод заснований на зважуванні навчальних об’єктів у залежності від віддалення від границі між класами. The paper is devoted to the problem of construction of polynomial separate surfaces for the task of two-class images classification. It is proposed an iteration method that provide to get the coefficients of separate hyper surfaces based on taking into account of peculiarity of the location of learning examples on the boundary between classes. The method is based on the weighting of learning examples depending on its distance from the boundary between classes. ru Інститут проблем штучного інтелекту МОН України та НАН України Системы и методы искусственного интеллекта Построение классификаторов на основе разделяющих поверхностей Побудова класифікаторів на основі поділяючих поверхонь Classifiers Construсtion Based on Separate Hyper Surfaces Article published earlier |
| spellingShingle | Построение классификаторов на основе разделяющих поверхностей Мурыгин, К.В. Системы и методы искусственного интеллекта |
| title | Построение классификаторов на основе разделяющих поверхностей |
| title_alt | Побудова класифікаторів на основі поділяючих поверхонь Classifiers Construсtion Based on Separate Hyper Surfaces |
| title_full | Построение классификаторов на основе разделяющих поверхностей |
| title_fullStr | Построение классификаторов на основе разделяющих поверхностей |
| title_full_unstemmed | Построение классификаторов на основе разделяющих поверхностей |
| title_short | Построение классификаторов на основе разделяющих поверхностей |
| title_sort | построение классификаторов на основе разделяющих поверхностей |
| topic | Системы и методы искусственного интеллекта |
| topic_facet | Системы и методы искусственного интеллекта |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/6712 |
| work_keys_str_mv | AT muryginkv postroenieklassifikatorovnaosnoverazdelâûŝihpoverhnostei AT muryginkv pobudovaklasifíkatorívnaosnovípodílâûčihpoverhonʹ AT muryginkv classifiersconstrustionbasedonseparatehypersurfaces |