ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Journal influence

Higher Attestation Commission (VAK) - К1 quartile
Russian Science Citation Index (RSCI)

Bookmark

Next issue

4
Publication date:
09 September 2024

Fuzzy set approach to classifier combination

The article was published in issue no. № 4, 2010
Abstract:Fuzzy set approach for combining of multiple classifiers is introduced. Proposed algorithms are evaluated on the optical character recognition task. Advices on usage of considered algorithms are given.
Аннотация:В статье рассматривается применение методов теории нечетких множеств для решения задачи комбинирования простых классификаторов с целью улучшения качества классификации и расширения вида классифицируемых объ-ектов. Эффективность предложенных алгоритмов оценивается на задаче распознавания текста. Даются рекомендации по применимости рассмотренных алгоритмов.
Authors: (sytnik@complexsys.ru) - , (sytnik@complexsys.ru) - , Russia, (sergey@tversu.ru) - , Russia, (sytnik@complexsys.ru) - , Ph.D
Keywords: optical character recognition, fuzzy sets, classification
Page views: 15034
Print version
Full issue in PDF (6.26Mb)
Download the cover in PDF (1.28Мб)

Font size:       Font:

При разработке системы распознавания печатных кириллических символов авторы столкнулись с необходимостью создания специального классификатора, который должен распознавать множество начертаний символов, различающихся шрифтом, размером и стилем. Создание и обучение подобного классификатора в виде одной монолитной системы, скажем, одной искусственной нейронной сети, весьма сложно. Популярным подходом при решении сложных задач классификации является применение принципа «разделяй и властвуй», который получил распространение как в системах распознавания [1], так и в других задачах анализа данных, например, в алгоритме Matrixnet, применяемом поисковой системой Яндекс.

Этот подход предполагает создание и обучение набора простых классификаторов, распознающих определенные типы объектов, и последующее комбинирование результатов их работы.

Одной из наиболее распространенных технологий создания простых классификаторов являются искусственные нейронные сети. Классификаторы такого типа имеют по одному выходу на каждый распознаваемый класс, при этом одновременно несколько выходов могут иметь ненулевые значения. Интерпретация этих значений часто проводится в рамках теории вероятности, однако сложность в данном случае состоит в том, что выходы нейронных сетей не соответствуют базовому положению теории вероятности о том, что сумма вероятностей должна равняться 1. Для решения этой проблемы применялись различные способы, позволяющие по выходу сети определить вероятность принадлежности объекта тому или иному классу [2].

В статье рассматривается альтернативный подход к интерпретации результатов работы такого классификатора. Авторы предлагают опираться не на теорию вероятностей, а на теорию нечетких множеств, введенную Заде [3]. В этом случае выход нейронной сети может быть непосредственно интерпретирован как нечеткое подмножество множества распознаваемых классов, где каждый выход сети указывает степень принадлежности каждого конкретного объекта данному классу, представляемую числом в диапазоне [0, 1].

Определение 1. Нечетким подмножеством (множеством) A (в) X называется совокупность упорядоченных пар вида

,

где μA(x) представляет собой степень принадлежности x к A.

Отметим, что, в отличие от вероятностной интерпретации, в данном случае не требуется, чтобы сумма выходных значений классификатора равнялась 1. Неопределенность, моделируемая в рамках теории нечетких множеств, позволяет рассматривать значение каждого выхода как степень близости классифицируемого изображения к эталону соответствующей буквы, использованному при обучении нейронной сети. Такая интерпретация является более естественной, чем предлагаемая в рамках теории вероятностей.

Таким образом, выходом каждого классификатора является нечеткое подмножество множества распознаваемых символов. Результаты вычислений отдельных классификаторов могут комбинироваться с использованием тех или иных операций с нечеткими множествами. Это приводит к архитектуре сложного классификатора в виде дерева, листьями которого являются простые классификаторы, а внутренние узлы соответствуют операциям комбинирования.

  Алгоритмы комбинирования, основанные на теории нечетких множеств

Рассмотрим результаты применения некоторых механизмов теории нечетких множеств для комбинирования выходов классификаторов, в частности t- и s-нормы.

Треугольные нормы, или t-нормы, являются известным механизмом агрегирования информации, применяющимся для вычисления пересечения нечетких множеств.

Определение 2. Отображение T: [0, 1]´[0, 1]→ →[0, 1] называется t-нормой, если для любых x, y, z, wÎ[0, 1] выполняется следующее:

·     граничные условия: T(0, 0)=0, T(1, x)=T(x, 1)=x;

·     симметричность: T(x, y)=T(y, x);

·     ассоциативность: T(x, T(y, z))=T(T(x, y), z);

·     монотонность: T(w, y)≤T(x, z), если w≤x и y≤z.

В качестве примеров t-норм рассмотрены операции произведения TP(x, y)=xy и взятия минимума TM(x, y)=min{x, y}. Соответствующие алгоритмы комбинирования состоят в вычислении t-нор­мы над входными нечеткими множествами и в дальнейшем будут обозначаться TP и TM соответственно.

Объединение нечетких множеств вычисляется с помощью s-норм (или t-конорм).

Определение 3. Треугольной t-конормой (t-ко­нормой, s-нормой) называется отображение S: [0,1]´[0,1]→[0,1], удовлетворяющее следующим условиям:

·     граничные условия: S(1, 1)=1, S(0, x)=S(x, 0)=x;

·     симметричность: S(x, y)=S(y, x);

·     ассоциативность: S(x, S(y, z))=S(S(x, y), z);

·     монотонность: S(w, y)≤S(x, z), если w≤x и y≤z.

В качестве примера s-нормы рассмотрена операция взятия максимума SM(x, y)=max{x, y}. Алгоритм комбинирования SM  состоит в вычислении этой s-нормы над входами.

Наряду с операциями объединения и пересечения нечетких множеств рассмотрены еще две операции.

В работе [4] предлагается другой способ нечеткой интерпретации выхода двух нейронных сетей. Если выход одной из сетей есть x1, а другой x2 (считаем, что x1≤x2), то авторы предлагают рассматривать результат комбинации как нечеткий интервал [x1, x2], к которому затем применяется центроидный метод дефаззификации, что дает значение (x1+ x2)/2. Чтобы расширить эту технику на большее число комбинируемых классификаторов, воспользуемся результатами [5], согласно которым модальное значение несимметричного нечеткого множества, построенного на основе ряда наблюдаемых значений x1, …, xn, есть их среднее арифметическое (x1+…+xn)/n. Данный алгоритм обозначим Avg.

Кроме того, авторами предложен алгоритм выбора наиболее уверенного эксперта. Последняя операция осуществляется путем выбора эксперта с минимальной энтропией функции принадлежности:

где x – элемент; X – множество элементов; μ(x) – уровень принадлежности элемента x множеству, .

Этот алгоритм обозначим Entropy.

  Методика тестирования

Изучение алгоритмов классификации проводилось в рамках системы распознавания печатного текста. Для оценки эффективности предлагаемых методов было создано по 18 простых классификаторов, обученных распознавать следующие начертания шрифтов: Arial 14 и 18 pt, Times New Roman 14 и 18 pt.

Системе распознавания текста, классификатор которой был построен путем той или иной комбинации указанных простых классификаторов, предлагалось распознать набор из 300 случайно выбранных из словаря слов средней длины 8,65 символа. Изображение каждого слова генерировалось с помощью функции печати текста операционной системы заданным шрифтом (который мог быть одним из приведенных выше плюс Arial 16 pt и Times New Roman 16 pt). Оценивалось число правильно распознанных слов.

Работа использованного простого классификатора осуществляется в два шага (см. рис.). Сначала по исходному изображению вычисляются признаки. Значение каждого признака является функцией от яркостей некоторого подмножества пикселей изображения. В результате получается вектор значений признаков, который поступает на вход нейронной сети. Каждый выход сети соответствует одной из букв алфавита, а получаемое на выходе значение рассматривается как уровень принадлежности буквы нечеткому множеству. В данном случае использовались классификаторы, у которых число признаков равнялось 50, а нейронная сеть не содержала скрытых слоев. Как показали практические эксперименты, такая архитектура позволяет решать задачу распознавания символов одного начертания.

Подпись:  
Простой классификатор

Комбинирование классификаторов, обученных распознавать одинаковые символы

Рассмотрим задачу комбинирования результатов работы нескольких классификаторов, обученных распознавать символы одинакового начертания. Для проверки использовались группы классификаторов, обученных распознавать определенный шрифт, выходы которых комбинировались с помощью одного из 5 алгоритмов, описанных выше. Системе распознавания предлагалось прочитать текст, написанный тем же шрифтом, что использовался для обучения простых классификаторов. Результаты тестирования приведены в таблице 1.

Таблица 1

Число распознанных слов при использовании классификаторов, обученных распознаванию символов одного начертания

Шрифт

Алгоритм комбинирования

TP

TM

SM

Avg

Entropy

Arial, 14 pt

179

202

199

197

211

Arial, 18 pt

222

222

219

244

226

Times New Roman, 14 pt

20

150

93

154

190

Times New Roman, 18 pt

5

75

74

74

66

Уже первые тесты показали низкую надежность использования произведения для комбинирования результатов классификации. В случае шрифта Times New Roman в результате работы классификатора с умножением в большинстве случаев для всех букв получались уровни принадлежности, очень близкие к 0, что не позволяло в дальнейшем получить корректное прочтение слова. Этот эффект также зависит от числа комбинируемых классификаторов: если их несколько, проблема стоит не так остро.

Лучшие результаты показали алгоритмы выбора классификатора с наименьшей энтропией и наименьшего среднего.

Комбинирование классификаторов, обученных распознавать символы разного размера

Несмотря на то, что изображение буквы перед классификацией масштабируется до фиксированного размера (в данном случае 15´15 пикселей), начертания одних и тех же букв при использовании шрифтов разных размеров могут отличаться. На это влияют и погрешности, возникающие при масштабировании, и различия в самих шрифтах.

В рассматриваемом примере использовалась двухуровневая схема построения классификатора. На первом уровне комбинировалось по 18 простых классификаторов, распознающих шрифты Arial 14 pt и Arial 18 pt. Два полученных в результате нечетких множества комбинировались алгоритмом второго уровня.

В данном случае на примере шрифта Arial 18 pt выяснялось, насколько полученная система в целом сохраняет свои возможности по распознаванию шрифтов первого уровня (табл. 2). Кроме того, на шрифте Arial 16 pt проверялось, сможет ли она читать шрифт промежуточного размера, который не использовался при обучении простых классификаторов (табл. 3).

Таблица 2

Число распознанных слов, написанных шрифтом Arial 18 pt

Алгоритм второго уровня

Алгоритм первого уровня

TP

TM

SM

Avg

Entropy

TP

2 (-220)

253 (+31)

90 (-129)

90 (-154)

88 (-138)

TM

2 (-220)

252 (+30)

263 (+44)

263 (+19)

255 (+29)

SM

243 (+21)

252 (+30)

258 (+39)

263 (+19)

253 (+27)

Avg

243 (+21)

252 (+30)

263 (+44)

263 (+19)

254 (+28)

Entropy

228 (+6)

244 (+22)

239 (+20)

264 (+20)

256 (+30)

 

Примечание: в скобках дано изменение по сравнению с результатами из таблицы 1.

Таблица 3

Число распознанных слов, написанных шрифтом Arial 16 pt

Алгоритм второго уровня

Алгоритм первого уровня

TP

TM

SM

Avg

Entropy

TP

0

206

190

205

87

TM

0

86

191

206

85

SM

195

201

225

209

203

Avg

8

201

212

205

204

Entropy

0

72

64

84

48

Таблица 4

Общее число слов, распознанных в данной группе тестов (из 600 слов теста)

Алгоритм второго уровня

Алгоритм первого уровня

TP

TM

SM

Avg

Entropy

TP

2

459

280

295

175

TM

2

338

454

469

340

SM

438

453

483

472

456

Avg

251

453

475

468

458

Entropy

228

316

303

348

304

Отметим, что во многих случаях добавление дополнительных классификаторов, обученных распознаванию шрифта Arial 14 pt, улучшило распознавание шрифта Arial 18 pt.

В случае одноуровнего классификатора алгоритм выбора по лучшей энтропии показывал хорошие результаты, но его эффективность в качестве алгоритма для второго уровня оказалась низкой, особенно при распознавании шрифта, не использовавшегося для обучения сетей.

Алгоритм вычисления среднего уровня принадлежности сохранил достаточно высокие позиции в качестве алгоритма как для первого, так и для второго уровня. Однако в обобщении на неизвестный шрифт и, как следствие, в общем итоге он уступил s-норме максимум, использованной на обоих уровнях.

Комбинирование классификаторов, обученных распознавать различные начертания символов

Для третьей группы тестов использовались шрифты одинакового размера, но разных начертаний, а именно шрифты Arial 14 pt и Times New Roman 14 pt.

В этом случае также применялась двухуровневая схема, при которой на первом уровне обобщались классификаторы для одинаковых шрифтов, а второй уровень объединял полученные для двух шрифтов оценки. При этом оценивалось, сможет ли классификатор выбрать правильный шрифт из двух возможных. Результаты представлены в таблицах 5–7.

Таблица 5

Число распознанных слов, написанных шрифтом Arial 14 pt

Алгоритм второго уровня

Алгоритм первого уровня

TP

TM

SM

Avg

Entropy

TP

39 (-140)

161 (-41)

160 (-39)

161 (-38)

122 (-89)

TM

39 (-140)

97 (-105)

160 (-39)

160 (-39)

108 (-103)

SM

81 (-98)

90 (-112)

56 (-143)

82 (-117)

56 (-155)

Avg

81 (-98)

171 (-31)

161 (-38)

154 (-45)

96 (-115)

Entropy

26 (-153)

31 (-171)

32 (-167)

26 (-173)

18 (-193)

Примечание: в скобках дано изменение по сравнению с результатами одноуровнего классификатора соответствующего типа (таблица 1).

Таблица 6

Число распознанных слов, написанных шрифтом Times New Roman 14 pt

Алгоритм второго уровня

Алгоритм первого уровня

TP

TM

SM

Avg

Entropy

TP

0 (-20)

15 (-135)

15 (-78)

26 (-128)

8 (-182)

TM

0 (-20)

0 (-150)

2 (-91)

1 (-153)

0 (-190)

SM

20 (0)

100 (-50)

64 (-29)

87 (-67)

39 (-151)

Avg

18 (-2)

83 (-67)

48 (-45)

62 (-92)

41 (-149)

Entropy

20 (0)

150 (0)

93 (0)

154 (0)

190 (0)

Примечание: в скобках дано изменение по сравнению с результатами из таблицы 1.

Таблица 7

Общее число распознанных слов (из 600 слов теста)

Алгоритм второго уровня

Алгоритм первого уровня

TP

TM

SM

Avg

Entropy

TP

39 (-160)

176 (-175)

175 (-117)

187 (-166)

130 (-271)

TM

39 (-160)

97 (-255)

162 (-130)

161 (-192)

108 (-293)

SM

61 (-98)

190 (-162)

120 (-172)

169 (-184)

95 (-306)

Avg

99 (-100)

254 (-98)

209 (-83)

216 (-137)

137 (-264)

Entropy

46 (-153)

181 (-171)

125 (-167)

180 (-173)

208 (-193)

Примечание: в скобках дана разница по сравнению с гипотетическим классификатором, всегда выбирающим набор сетей, соответствующий использованному шрифту, и комбинирующим их соответствующим алгоритмом.

Очевидно, что строка, соответствующая использованию алгоритма Entropy для шрифта Times New Roman, в точности повторяет результаты распознавания этого шрифта алгоритмами первого уровня, тогда как для шрифта Arial его результаты оказались плохими. При попытке применить Arial для комбинирования классификаторов, предназначенных для распознавания все более и более различающихся символов, эффективность этого алгоритма снижалась.

Лучшей в данном случае оказалась комбинация, в которой на первом уровне использовалась t-норма минимум, а на втором производилось усреднение  уровня возможности. Такая структура классификатора обеспечила максимальное суммарное число распознанных слов и сравнительно небольшие потери по сравнению с идеальным классификатором, не ошибающимся при выборе шрифта.

Эта же конфигурация обеспечила и минимальное среднее число ошибок (то есть минимальное число удалений, вставок или замен, необходимых для получения правильного слова из предложенного системой распознавания варианта) для слов, которые не были найдены классификатором. Оно составило 1,22 для Arial и 1,99 для Times New Roman (без учета алгоритма Entropy, который показал более высокий результат на шрифте Times New Roman). Такой результат позволяет надеяться, что большинство ошибок может быть исправлено при использовании информации о частоте сочетаний букв и проверке по словарю.

Использование на первом уровне минимума может показаться нелогичным, однако стоит вспомнить, что в рамках теории нечетких множеств эта операция используется для вычисления пересечения нечетких множеств. В данном случае получено обобщенное мнение экспертов, высокий результат в котором может быть только у альтернативы, достаточно высоко оцененной всеми. В то же время при использовании максимума ставшая лучшей альтернатива может иметь низкие оценки части экспертов. Это может говорить о том, что классифицируемый образ далек от образов обучающей последовательности для данной группы экспертов и вынесенное заключение является плохо обоснованным.

Использование одного классификатора в пределах слова

Таким образом, задача комбинирования классификаторов, распознающих схожие начертания символов, может быть успешно решена с помощью рассмотренных простых алгоритмов комбинирования. Однако результаты объединения с их помощью классификаторов, распознающих символы различных начертаний, нельзя признать удовлетворительными.

Для улучшения работы было решено использовать информацию о распознавании других букв слова. Исходя из предположения о том, что слово, как правило, пишется символами одного шрифта, предложим следующий алгоритм.

1.   Выполнить распознавание всех букв слова, запоминая на верхнем уровне классификатора, какому из классификаторов второго уровня отдавалось предпочтение при прочтении каждой буквы.

2.   Определить классификатор второго уровня, который был выбран наибольшее число раз.

3.   Выполнить повторное распознавание слова, используя определенный в п. 2 классификатор; использовать полученный вариант прочтения как окончательный.

Указанный алгоритм имеет смысл при использовании на верхнем уровне такого алгоритма комбинирования, который выбирает один из нескольких входных векторов. В данном случае это алгоритмы TM, SM и Entropy.

В таблицах 8–10 приведены результаты тестирования эффективности этого алгоритма при выборе между классификаторами, обученными распознавать шрифты Arial и Times New Roman. Методика тестирования полностью соответствует использованной ранее.

Таблица 8

Число распознанных слов, написанных шрифтом Arial 14 pt

Алгоритм второго уровня

Алгоритм первого уровня

TP

TM

SM

Avg

Entropy

TM

177 (-2)

188 (-14)

197 (-2)

195 (-2)

176, (-35)

SM

40 (-139)

98 (-104)

32 (-167)

40 (-157)

31 (-180)

Entropy

177 (-2)

200 (-2)

197 (-2)

195 (-2)

209 (-2)

Примечание: в скобках дано изменение по сравнению с результатами из таблицы 1.

Таблица 9

Число распознанных слов, написанных шрифтом Times New Roman 14 pt

Алгоритм второго уровня

Алгоритм первого уровня

TP

TM

SM

Avg

Entropy

TM

0 (-20)

0 (-150)

2 (-91)

1 (-153)

0 (-190)

SM

20 (0)

150 (0)

93 (0)

154 (0)

174 (-16)

Entropy

0 (-20)

150 (0)

93 (0)

154 (0)

174 (-16)

Примечание: в скобках дано изменение по сравнению с результатами из таблицы 1.

Таблица 10

Общее число распознанных слов для шрифтов размера 14 pt (из 600 слов теста)

Алгоритм второго уровня

Алгоритм первого уровня

TP

TM

SM

Avg

Entropy

TM

177 (-22)

188  (-164)

199 (-93)

196 (-155)

176 (-225)

SM

60 (-139)

248 (-104)

125 (-167)

194 (-157)

205 (-196)

Entropy

177 (-20)

350 (-2)

290 (-2)

349 (-2)

383 (-18)

Примечание: в скобках дана разница по сравнению с гипотетическим классификатором, всегда выбирающим набор сетей, соответствующий использованному шрифту, и комбинирующим их соответствующим алгоритмом.

Можно видеть, что в данном случае алгоритм второго уровня TM, невзирая на распознаваемый шрифт, отдавал предпочтение классификатору для шрифта Arial, а SM – Times New Roman. В результате оба эти алгоритма не справились с поставленной задачей.

Лучший результат был показан алгоритмом Entropy – ему удалось правильно различить почти все предложенные примеры для обоих шрифтов.

Проведенные эксперименты показали, что подход, опирающийся на теорию нечетких множеств, наряду с другими методами может использоваться для комбинирования выходов нескольких классификаторов с целью улучшения их работы. При этом необходимо отметить следующее.

·     Использование t-нормы TP(x, y)=xy пред­ставляется нецелесообразным в связи с проблемами вычислительного характера.

·     Алгоритм вычисления среднего значения уровня принадлежности весьма эффективен в широком спектре возможных условий применения, но может быть превзойден алгоритмами, лучше адаптированными к конкретной задаче.

·     Алгоритм выбора нечеткого множества с минимальной энтропией может давать довольно хорошие результаты, но может оказаться и непригодным при комбинировании информации от разнородных классификаторов в отсутствие дополнительной информации.

·     Необязательно алгоритм, показавший высокие результаты в составе более простого классификатора, окажется лучшим выбором при комбинировании этого классификатора с другими. Выбор оптимальной архитектуры в значительной степени определяется рассматриваемой задачей и имеющимися простыми классификаторами.

Рассмотренные в статье несложные способы комбинирования позволяют достичь хороших результатов при объединении простых классификаторов, обученных распознавать достаточно похожие друг на друга объекты. В случае выбора классификаторов, распознающих существенно различающиеся объекты, эффективность рассмотренных методов может быть улучшена за счет использования контекстной информации. При отсутствии такой информации представляется целесообразной разработка более сложных методов. Возможными направлениями решения этой проблемы могут быть создание отдельного классификатора, определяющего тип классифицируемого образа, на основании заключения которого производится выбор из имеющихся классификаторов, а также анализ близости классифицируемых образов к образам обучающих последовательностей классификаторов, возможно, реализованный в виде дополнительного выхода классификатора, оценивающего принадлежность образа к группе неизвестных.

Литература

1. Ян Д.Е. Исследование, развитие и реализация методов автоматического распознавания рукописных текстов в компьютерных системах: дисс. … канд. физ.-мат. наук. М., 2003.

2. Denker J.S., leCun Y. Transforming Neural-Net Output Levels to Probability Distributions. AT&T Bell Labs Technical Memorandum, November, 1990.

3. Zadeh L.A., The concept of a linguistic variable and its application to approximate reasoning // Information Sciences, 1975, № 8, pp. 199–249; № 9, pp. 43–80.

4. Melin P., Urias J., Solano D., Soto M., Lopez M., Castillo O. Voice Recognition with Neural Networks, Type-2 Fuzzy Logic and Genetic Algorithms / Engineering Letters, 2006, 13:2.

5. Панфилов С.А. Методы и программный комплекс моделирования алгоритмов управления нелинейными динамическими системами на основе мягких вычислений. Дисс. … канд. технич. наук. Тверь, 2005.


Permanent link:
http://swsys.ru/index.php?page=article&id=2627&lang=en
Print version
Full issue in PDF (6.26Mb)
Download the cover in PDF (1.28Мб)
The article was published in issue no. № 4, 2010

Perhaps, you might be interested in the following articles of similar topics: