2. КЛАССИФИКАТОР СКРЫТЫЕ МОДЕЛИ МАРКОВА

3. КЛАССИФИКАТОР ДЕРЕВЬЯ РЕШЕНИЙ

Для того чтобы обеспечить дополнительную классификацию, надеемся дающую некоррелированные ошибки, должен быть извлечен другой тип признаков и классифицирован методом деревья решений. Такое решение, деревья, построенные при использовании методов, основанных Amit и др. [20]. Эти авторы брались за решение множества проблем, включая то же самое цифровое опознавание – классифицировали образы на цифры "0" - "9."

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

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

3.1 Выделение признаков

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

Рисунок 4. Одиночный выступ, показывающий извлеченные характеристики для дерева решения: максимум кривизны и, левая, правая, нижняя и верхняя точки поворота.

Используемая начальная предварительная обработка идентична используемой в классификаторе СММ, вплоть до извлечения выступов (Раздел 2.1), но, вместо извлечения признаков на пересечениях с опорными линиями, признаки генерируются в точках излома кривой выступа (выступающие точки). Признаки состоят из максимальной кривизны и четырех параллельных осям критических точек поворота (dx/ds = 0 или dy/ds = 0 для выступа представленного как параметрическая кривая (x(s),y(s)) и отличенного признаком второй производной). Некоторые примеры признаков показаны на рисунке 4. Для каждого признака записывается его тип и позиция (на пикселях в 500 dpi). Эти признаки полностью основаны на локальных вычислениях в выступах и, опять, избегается извлечение глобальных характеристик, таких как ядро (основная) и дельта точки. Кроме того, они неизменные при перемещении и при небольших вращениях.

3.2 Деревья решений

Двоичное дерево решения создано как иерархия двоичных вопросов [21]. Вопросы являются логическими суждениями (утверждениями) о признаках, которые могут присутствовать на отпечатке пальца и об отношениях между этими признаками; для предоставленного отпечатка пальца, вопрос – это или истина или ложь. На «верхнем» уровне, каждому тестовому образцу задается первый вопрос. Согласно данным тестового образца, вопрос возвращает истину или ложь и определяется ветка второго уровня. Какая бы ветка второго уровня ни была выбрана, задается вопрос второго уровня и порождается дальнейшее разветвление. Таким образом, каждый тестовый образец проходит дерево маршрутом, зависящим от его признаков, и достигает краевой узел (конечную вершину). Конечные вершины помечены согласно классам тестовых данных, которые проходят по дереву. В простой проблеме классификации, конечные вершины будут правильными - то есть, принимается только проверочная выборка из единственного класса и однозначной классификацией любого испытательного образца (контрольной выборки), прибывающих там, должен быть класс тренировочных данных в этом узле. Для более сложных проблем, конечные вершины содержат смешанные данные и тестовые данные помечаются стохастическим распределением (распределением вероятностей) через классы.

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

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

3.3 Вопросы

Вопрос состоит из списка необходимых признаков и набора отношений между ними. Каждый признак определен как один из пяти признаков, описанных выше (четыре критические точки поворота и максимум кривизны). Отношения – это форма "x - направление y", где направление - одно из Север, Юг, Восток, Запад. Дополнительно, вопрос может также наложить предельное расстояние, так как признак должен быть в пределах определенного расстояния. Экспериментирование привело нас к использованию двух групп расстояния: характеристики в пределах 0.1" и характеристик в пределах 0.2". Например, вопрос может определить, что максимум кривизны восточнее более низкой критической точки поворота, которая сама является восточной, и в пределах 0.2" от максимума кривизны. Другие вопросы показаны в узлах на рисунке 5. Вопросы созданы таким образом, чтобы каждый признак, связанный, по крайней мере, с одним признаком в списке признаков и так, чтобы каждая пара признаков могла иметь как минимум одно отношение.

Каждый новый отпечаток может быть протестирован поиском, который определяет, может ли вопрос быть совершен на основании признаков отпечатка.

3.4 Построение вопросов

При создании дерева, вопросы создаются произвольно следующим образом:

1. Выберите любой класс признаков как первый признак;
2. Протестируйте разделение данных. Если более чем 2/3 данных обучающей выборки в этом узле - ответили «да», уточните вопрос и повторите этот шаг. Если менее чем 1/3 ответов «да», отвергните этот вопрос и создайте новый вопрос. В противном случае, оцените вопрос.

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

1. Добавление признака. В этом случае, выбирается произвольный тип признаков и добавляется к списку. Произвольное отношение выбирается для связи этого признака с произвольно выбранным признаком, который уже имеется в списке;
2. Если в вопросе содержится два или более признаков и некоторая пара не имеет отношения (связи) между ними, тогда дополнительное отношение может быть добавлено к вопросу между любой парой признаков, которая пока еще не имеет отношения.

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

Достижение в вопросе, чьи каналы приблизительно составляют половину данных для каждой из сторон (ветвей) "да" и "нет", вопрос оценен. Мера эффективности вопроса - это изменение энтропии (неопределённости) в распределениях перед и после применения вопроса. Классы в корневом узле имеют высокую энтропию, но корневые узлы должны иметь очень низкую энтропию (быть "чисто"). Относительная энтропия выходных распределений для узла вычисляется для многих произвольно сконструированных вопросов и вопросов с самым верхним изменением энтропии из выбранных.

Дерево рекурсивно создается, пока листы не будут чисты или до достижения максимальной глубины (обычно 7).