Комбинирование бинарных свойств в виде МКВ-классификатора
В статье рассматривается алгоритм объединения бинарных свойств, широко используемых на практике при разработке систем автоматического анализа визуальной информации, в виде МКВ-классификатора. Предложенный алгоритм позволяет генерировать более эффективные решающие правила по сравнению с известным...
Saved in:
| Published in: | Штучний інтелект |
|---|---|
| Date: | 2010 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем штучного інтелекту МОН України та НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/56130 |
| 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: | Комбинирование бинарных свойств в виде МКВ-классификатора / К.В. Мурыгин // Штучний інтелект. — 2010. — № 1. — С. 108-113. — Бібліогр.: 4 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-56130 |
|---|---|
| record_format |
dspace |
| spelling |
Мурыгин, К.В. 2014-02-12T00:23:28Z 2014-02-12T00:23:28Z 2010 Комбинирование бинарных свойств в виде МКВ-классификатора / К.В. Мурыгин // Штучний інтелект. — 2010. — № 1. — С. 108-113. — Бібліогр.: 4 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/56130 004.89, 004.93 В статье рассматривается алгоритм объединения бинарных свойств, широко используемых на практике при разработке систем автоматического анализа визуальной информации, в виде МКВ-классификатора. Предложенный алгоритм позволяет генерировать более эффективные решающие правила по сравнению с известным алгоритмом AdaBoost, а также существенно сократить число используемых свойств при одинаковой классифицирующей способности, за счет более точного описания положения объектов в пространстве признаков. У статті розглядається алгоритм об’єднання бінарних властивостей, широко використовуваних на практиці при розробці систем автоматичного аналізу візуальної інформації, у виді МКВ-класифікатора. Запропонований алгоритм дозволяє генерувати більш ефективні вирішуючи правила в порівнянні з відомим алгоритмом AdaBoost, а також істотно скоротити число використовуваних ознак при однаковій якості класифікації, за рахунок більш точного опису положення об’єктів у просторі ознак. In the article the algorithm of association of the binary properties widely used in practice at system engineering of the automatic analysis of the visual information, in the form of the MKV-classifier is considered. The offered algorithm allows to generate more effective solving rules in comparison with known algorithm AdaBoost, and also it is essential to reduce number of used properties at identical classifying ability, at the expense of more exact description of position of objects in feature space. ru Інститут проблем штучного інтелекту МОН України та НАН України Штучний інтелект Моделирование объектов и процессов Комбинирование бинарных свойств в виде МКВ-классификатора Комбінування бінарних ознак у вигляді МКВ-класифікатора Combination of Binary Properties in the Form of the MKV-classifier 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 |
Мурыгин, К.В. |
| topic |
Моделирование объектов и процессов |
| topic_facet |
Моделирование объектов и процессов |
| publishDate |
2010 |
| language |
Russian |
| container_title |
Штучний інтелект |
| publisher |
Інститут проблем штучного інтелекту МОН України та НАН України |
| format |
Article |
| title_alt |
Комбінування бінарних ознак у вигляді МКВ-класифікатора Combination of Binary Properties in the Form of the MKV-classifier |
| description |
В статье рассматривается алгоритм объединения бинарных свойств, широко используемых на практике при разработке систем автоматического анализа визуальной информации, в виде МКВ-классификатора. Предложенный алгоритм позволяет генерировать более эффективные решающие правила по сравнению с известным алгоритмом AdaBoost, а также существенно сократить число используемых свойств при одинаковой классифицирующей способности, за счет более точного описания положения объектов в пространстве признаков.
У статті розглядається алгоритм об’єднання бінарних властивостей, широко використовуваних на практиці при розробці систем автоматичного аналізу візуальної інформації, у виді МКВ-класифікатора. Запропонований алгоритм дозволяє генерувати більш ефективні вирішуючи правила в порівнянні з відомим алгоритмом AdaBoost, а також істотно скоротити число використовуваних ознак при однаковій якості класифікації, за рахунок більш точного опису положення об’єктів у просторі ознак.
In the article the algorithm of association of the binary properties widely used in practice at system engineering of the automatic analysis of the visual information, in the form of the MKV-classifier is considered. The offered algorithm allows to generate more effective solving rules in comparison with known algorithm AdaBoost, and also it is essential to reduce number of used properties at identical classifying ability, at the expense of more exact description of position of objects in feature space.
|
| issn |
1561-5359 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/56130 |
| citation_txt |
Комбинирование бинарных свойств в виде МКВ-классификатора / К.В. Мурыгин // Штучний інтелект. — 2010. — № 1. — С. 108-113. — Бібліогр.: 4 назв. — рос. |
| work_keys_str_mv |
AT muryginkv kombinirovaniebinarnyhsvoistvvvidemkvklassifikatora AT muryginkv kombínuvannâbínarnihoznakuviglâdímkvklasifíkatora AT muryginkv combinationofbinarypropertiesintheformofthemkvclassifier |
| first_indexed |
2025-11-27T08:13:32Z |
| last_indexed |
2025-11-27T08:13:32Z |
| _version_ |
1850804991132958720 |
| fulltext |
«Искусственный интеллект» 1’2010 108
2М
УДК 004.89, 004.93
Мурыгин К.В.
Институт проблем искусственного интеллекта МОН Украины и НАН Украины,
г. Донецк
kir@iai.donetsk.ua
Комбинирование бинарных свойств
в виде МКВ-классификатора
В статье рассматривается алгоритм объединения бинарных свойств, широко используемых на практике
при разработке систем автоматического анализа визуальной информации, в виде МКВ-классификатора.
Предложенный алгоритм позволяет генерировать более эффективные решающие правила по сравнению
с известным алгоритмом AdaBoost, а также существенно сократить число используемых свойств при
одинаковой классифицирующей способности, за счет более точного описания положения объектов в
пространстве признаков.
Введение
Одним из способов решения задач распознавания является построение классифи-
каторов на основе объединения простых, но недостаточно эффективных по отдельнос-
ти признаков, согласно некоторому алгоритму обучения, цель которого минимизиро-
вать ошибку классификации. К таким алгоритмам относится достаточно популярный и
часто используемый для решения задач распознавания зрительных образов алгоритм
AdaBoost. Алгоритм AdaBoost использует подход к обучению классификации, осно-
ванный на объединении некоторого количества малоэффективных элементарных клас-
сификаторов (ЭК) в один, более качественный, на основе их линейной комбинации.
Если такие классификаторы бинарные (возвращают два значения, например, 1 и 0),
то для их объединения используется классический подход, предложенный Шапиро и
др. [1-3]. В случае использования бинарных классификаторов положение объектов в
пространстве их представления в виде возвращаемых классификаторами значений ог-
раничивается вершинами куба, размерности, равной числу используемых классифика-
торов. При таком расположении объектов разделение их плоскостью является достаточ-
но грубым, особенно если число классификаторов невелико. Для более качественного
описания положения объектов в пространстве целесообразно использовать данные о
расположении обучающих объектов в вершинах многомерного куба. Назовем такой
классификатор – МКВ-классификатор. При таком подходе каждая из ограниченного
множества вершин наделяется атрибутом принадлежности к определенному классу.
При классификации объект попадает согласно принятым значениям набора элемен-
тарных классификаторов в одну из вершин куба, и относится к классу в соответствии
с атрибутом данной вершины. При решении двух классовых задач распознавания до-
статочным является пометить вершины, принадлежащие одному из классов, а все ос-
тальные автоматически будут относиться к объектам второго класса. Последнее в
полной мере относится к задаче поиска объектов, где необходима классификация объект/
все остальное. Так как количество вершин очень быстро увеличивается с ростом
Комбинирование бинарных свойств в виде МКВ-классификатора
«Штучний інтелект» 1’2010 109
2М
числа классификаторов ( n2 ), при бинарной классификации удобно использовать пред-
ставление классификатора в виде дерева решений.
Рисунок 1 – Схема представления МКВ-классификатора, составленного из набора
элементарных бинарных классификаторов, в виде дерева решений
При больших количествах используемых элементарных классификаторов число
вершин многомерного куба может быть достаточно большим, однако в силу того, что
число обучающих объектов, как правило, не настолько велико, то число используемых
вершин ограничивается сверху объемом обучающей выборки.
Обучение МКВ-классификатора
Качественное обучение МКВ-классификатора предполагает комбинирование не-
которого количества ЭК таким образом, чтобы пересечение обучающих объектов раз-
ных классов в вершинах многомерного куба было минимальным. Произвольный объект,
подаваемый на вход МКВ-классификатора, согласно принятым значениям ЭК попа-
дает в одну из вершин многомерного куба. Таким образом, имея определенный обуча-
ющий набор объектов и зная их классовую принадлежность, можно оценить частоты
попадания объектов разных классов в вершины куба. Назначение атрибута классовой
принадлежности вершины осуществляется путем выбора класса, которому соответству-
ет максимальная вероятность попадания в данную вершину. Если обозначить функцию
МКВ-классификатора, возвращающую атрибут класса для произвольного входного
объекта xr как ( )xh r , а его истинную принадлежность (правильный атрибут) как y , то для
ошибки классификации будем иметь:
∑
=
=
N
1i
iS
N
1E , где
( )
≠
=
.иначе,0
,yxh,1
S ii
i
r
Здесь N – число обучающих объектов. В ходе обучения ЭК выбираются таким обра-
зом, чтобы минимизировать ошибку классификации E .
ЭК 1
0 1
ЭК 2
0 1
ЭК 2
0 1
ЭК 3
0 1
ЭК 3
0 1
ЭК 3
0 1
ЭК 3
0 1
Атрибуты классов
Распознаваемый объект
Мурыгин К.В.
«Искусственный интеллект» 1’2010 110
2М
Процесс комбинирования элементарных классификаторов может иметь значи-
тельную вычислительную сложность в силу необходимости решения задачи полного
перебора, особенно при большом числе ЭК. Вместе с тем процесс обучения можно зна-
чительно упростить, применив по аналогии с AdaBoost последовательный отбор ЭК в
ходе формирования МКВ-классификатора. Общая схема процесса обучения приведе-
на на рис. 2.
1) Выбирается наилучший ЭК с точки зрения минимиза-
ции ошибки классификации.
2) Для каждого цикла обучения T,...,2t = :
2.1) организовывается цикл добавления ЭК к уже вклю-
ченным в МКВ-классификатор;
2.2) считается ошибка классификации после добавле-
ния текущего ЭК в МКВ-классификатор;
2.3) выбирается ЭК, который при добавлении в МКВ-
классификатор дает максимальное уменьшение ошиб-
ки, и включается в МКВ-классификатор.
3) После достижения требуемой ошибки классификации
процесс обучения заканчивается.
Рисунок 2 – Алгоритм обучения МКВ-классификатора
Самым вычислительно сложным этапом приведенного алгоритма является оцен-
ка ошибки МКВ-классификатора с добавлением нового ЭК. Для ускорения выполне-
ния вычислений на этом этапе удобно заполнять таблицу принятых элементарными
классификаторами значений:
Таблица 1 – Принятые элементарными классификаторами значения
№ ЭК Объект 1 Объект 2 Объект 3 Объект 4 … Объект N
1 0 1 0 0 … 0
2 1 1 0 1 … 0
3 0 0 0 0 … 0
…
…
…
…
…
…
…
T-1 1 1 0 1 … 0
T - новый 0 0 1 0 … 1
Номер впервые
встретившегося
такого же
вектора
1 2 3 1 … 3
Последняя строка таблицы содержит номер объекта, который имеет меньший
или равный текущему порядковый номер в списке обучающих объектов и для кото-
рого значения всех ЭК совпадают с соответствующими значениями ЭК для текущего
объекта. Она позволяет определить количество вершин куба, в которые попадают все
объекты обучающего набора, и оценить частоты попадания в каждую вершину объек-
тов каждого класса. Это позволяет назначить вершинам атрибуты классов из условия
минимизации ошибок классификации.
Последняя строка позволяет быстро находить впервые встретившийся вектор в
таблице, равный текущему вектору. Действительно, зная значения последней строки
Комбинирование бинарных свойств в виде МКВ-классификатора
«Штучний інтелект» 1’2010 111
2М
без добавления очередного ЭК и значение этого ЭК для данного объекта достаточно
ввести дополнительные две строки в таблицу выше:
Объект 1 Объект 2 Объект 3 … Объект
N
Номер впервые
встретившегося такого
же вектора без
добавления последнего
ЭК
1 2 3 … 3
Номер впервые
встретившегося такого
же вектора при условии,
что добавленный ЭК
возвращает 0
1 2 10 … 28
Номер впервые
встретившегося такого
же вектора при условии,
что добавленный ЭК
возвращает 1
23 45 3 … 3
Вычисляя значение добавленного ЭК для текущего объекта и зная первый, со-
впадающий с ним объект в списке обучающих объектов без добавления последнего
ЭК, можно получить номер впервые встретившегося такого же объекта, или назначить
текущий объект первым найденным в последовательности, что и занести в одну из
добавленных строк таблицы. Описанный подход позволяет вычислять ошибку класси-
фикации после добавления очередного классификатора с меньшими вычислительны-
ми затратами, близкими к выполнению аналогичной операции в алгоритме AdaBoost.
Тестирование МКВ-классификатора
Для тестирования предложенного МКВ-классификатора использовалась задача
обнаружения области губ на изображении лица. В качестве ЭК использовались пря-
моугольные логические свойства, предложенные в [4]. В качестве области поиска рас-
сматривалась область предварительно найденного лица, содержащая губы. Использо-
валась база изображений губ, произносящих различные звуки, положение которых
было размечено вручную. В качестве обучающего набора изображений губ использо-
вались вырезанные изображения областей губ из базы изображений лиц и изображения,
полученные их горизонтальным зеркальным отражением, – всего 5616 изображений.
Все обучающие изображения приведены к рабочему масштабу 16×16 пикселей. В ка-
честве изображений класса «Фон» из базы изображений лиц и их горизонтальных зер-
кальных отражений случайным образом извлечены 5348 изображений. Всего вариантов
изображений фона, содержащихся в изображениях базы изображений лиц, было около
461 000 000. Примеры изображений обучающего набора приведены на рис.3.
а)
Мурыгин К.В.
«Искусственный интеллект» 1’2010 112
2М
б)
Рисунок 3 – Примеры изображений обучающего набора:
а) обучающие объекты класса «Губы»,
б) обучающие объекты класса «Фон»
В процессе обучения на одном обучающем наборе изображений получены зави-
симости средней ошибки классификации 1 и 2 рода от числа используемых элементар-
ных классификаторов для МКВ-классификатора и классификатора в виде линейной
комбинации ЭК, полученного методом AdaBoost (рис. 4).
0
0,05
0,1
0,15
0,2
0,25
0 50 100 150 200
Количество используемых ЭК
С
ре
дн
яя
о
ш
иб
ка
к
ла
сс
иф
ик
ац
ии
МКВ-классификатор AdaBoost
Рисунок 4 – Сравнительная характеристика качества классификаторов МКВ
и AdaBoost по результатам обучения
Анализ полученных зависимостей показывает, что использование МКВ-класси-
фикатора по сравнению с классификатором, получаемым в результате работы алго-
ритма AdaBoost, позволяет существенно сократить число используемых ЭК при дости-
жении одинаковой средней ошибки классификации, что дает возможность значительно
ускорить процесс выполнения операции классификации. Для МКВ-классификатора
характерна большая скорость уменьшения ошибки обучения с увеличением числа ЭК.
Согласно приведенным зависимостям при использовании 25 элементарных классифи-
каторов ошибка МКВ-классификатора приблизительно в 10 раз меньше, чем ошибка
обучения алгоритма AdaBoost. Для достижения такого значения ошибки алгоритмом
AdaBoost необходимо использовать комбинацию более 200 классификаторов.
Комбинирование бинарных свойств в виде МКВ-классификатора
«Штучний інтелект» 1’2010 113
2М
Выводы
Рассмотренный в статье подход к объединению простых свойств в МКВ-клас-
сификатор позволяет проводить эффективное обучение распознаванию образов. По ско-
рости обучения предложенный подход не уступает алгоритму обучения AdaBoost, а
по эффективности получаемых решений позволяет значительно уменьшить число ис-
пользуемых свойств при сохранении требуемого качества классификации. Последняя
особенность МКВ-классификатора, а также возможность его представления в виде
дерева решений определяет высокую скорость работы классификатора, по сравнению
с линейной комбинацией значений свойств, получаемой при использовании алгорит-
ма обучения AdaBoost. Основным направлением дальнейших исследований является
исследование возможностей использования описанного подхода для решения задачи
обнаружения более широкого круга целевых объектов, в частности номерных знаков
автомобилей, лиц людей и т.п., что позволит определить степень его инвариантности
к свойствам объектов поиска.
Литература
1. Robert E. Schapire. Boosting the margin: A new explanation for the effectiveness of voting methods / Robert E.
Schapire, Freund Y. Bartlett P., Lee W.S. // Of the Fourteenth International Conference on Machine Learning. –
1997.
2. Schapire R.E. Improved Boosting Algorithms Using Confidence-rated Predictions / Schapire R.E. and Singer Y. //
Machine Learning. – 1999. – Р. 297-336.
3. Robert E. Schapire. The boosting approach to machine learning: An overview / Robert E. Schapire // In MSRI
Workshop on Nonlinear Estimation and Classification. – 2002.
4. Мурыгин К.В. Особенности реализации алгоритма AdaBoost для обнаружения объектов на изобра-
жениях / К.В. Мурыгин // Искусственный интеллект. – 2009. – № 3. – С. 573-581.
К.В. Муригін
Комбінування бінарних ознак у вигляді МКВ-класифікатора
У статті розглядається алгоритм об’єднання бінарних властивостей, широко використовуваних на практиці
при розробці систем автоматичного аналізу візуальної інформації, у виді МКВ-класифікатора. Запропонований
алгоритм дозволяє генерувати більш ефективні вирішуючи правила в порівнянні з відомим алгоритмом
AdaBoost, а також істотно скоротити число використовуваних ознак при однаковій якості класифікації,
за рахунок більш точного опису положення об’єктів у просторі ознак.
K.V. Murygin
Combination of Binary Properties in the Form of the MKV-classifier
In the article the algorithm of association of the binary properties widely used in practice at system engineering
of the automatic analysis of the visual information, in the form of the MKV-classifier is considered. The offered
algorithm allows to generate more effective solving rules in comparison with known algorithm AdaBoost,
and also it is essential to reduce number of used properties at identical classifying ability, at the expense of
more exact description of position of objects in feature space.
Статья поступила в редакцию 06.01.2010.
|