Разработка метода определения информативных признаков биометрической идентификации пользователей

Размещено на http://www.allbest.ru/

Федеральное агентство связи

Федеральное государственное бюджетное образовательное учреждение высшего образования «Поволжский государственный университет телекоммуникаций и информатики»

Факультет Заочного обучения

Направление (специальность) Информационные системы и технологии

Кафедра Информационных систем и технологии

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА

(БАКАЛАВРСКАЯ РАБОТА)

Разработка метода определения информативных признаков биометрической идентификации пользователей

Руководитель

доцент к.п.н., доцент

Е.И. Ряполова

Разработал БИСТу-30

И.А. Родимцев

Самара 2017



Федеральное агентство связи

Федеральное государственное бюджетное образовательное учреждение

Высшего образования «Поволжский государственный университет телекоммуникаций и информатики»

ЗАДАНИЕ

по подготовке выпускной квалификационной работы

Студента Родимцева Ивана Андреевича

1 Тема ВКР

Разработка метода определения информативных признаков биометрической идентификации пользователей

Утверждена приказом по университету от

25.11.2016 № 219-2

2 Срок сдачи студентом законченной ВКР 25.01.2017

3 Исходные данные и постановка задачи

1) провести анализ задачи определения информативных признаков в теории и практики распознания образов;

2) обзор и определение требований к методам сокращения признакового пространства;

3) исследовать законы распределения значений признаков;

4) разработать алгоритм сокращения признакового пространства;

5) разработать программный продукт.

4 Перечень подлежащих разработке в ВКР вопросов или краткое содержание ВКР.

Сроки исполнения 20.01.2017

1) Провести анализ задачи определения информативных признаков в теории и практики распознания образов

2) Обзор и определение требований к методам сокращения признакового пространства

3) Исследовать законы распределения значений признаков

4) Разработать алгоритм сокращения признакового пространства

5) Разработать программный продукт

5 Перечень графического материала. Сроки исполнения 20.01.2017

1) Постановка задач на ВКР

2) Общая структура системы распознавания и этапы в процессе ее разработки

3) Типы задач распознавания

4)Обзор современных методов сокращения признакового пространства

5) Классификация биометрических информативных признаков

6)Исследование законов распределения информативных признаков

7) Исследование законов распределения информативных признаков

8) Схема алгоритма сокращения признакового пространства

9) Экранная форма программного продукта

10) График плотностей распределения

6 Дата выдачи задания « 12 » декабря 2016 г.

Кафедра Информационных систем и технологий

Утверждаю зав.кафедрой д.т.н., доцент 12.12.16 Н.И. Лиманова

Руководитель доент. к.п.н. 12.12.16 Е.И.Ряполова

Задание принял БИСТу-30 12.12.16 И.А. Родимцев



Федеральное агентство связи

Федеральное государственное бюджетное образовательное учреждение высшего образования

«Поволжский государственный университет телекоммуникаций и информатики»

ОТЗЫВ РУКОВОДИТЕЛЯ

Тип ВКР бакалаврская работа

Студента(ки) Родимцев Иван Андреевич

Специальность/ направление Информационные системы и технологии

Разработка метода определения информативных призна-

Тема ВКР ков биометрической идентификации пользователей

Руководитель Ряполова Елена Ивановна

Ученая степень, звание к.п.н доцент

Место работы (должность) доцент МиЕНД

АКТУАЛЬНОСТЬ ТЕМЫ

________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

ОЦЕНКА СОДЕРЖАНИЯ РАБОТЫ

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

_____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

СТЕПЕНЬ ДОСТИЖЕНИЯ ЦЕЛИ И ПРАКТИЧЕСКАЯ ЗНАЧИМОСТЬ

(Полнота раскрытия исследуемой темы, практическая ценность и возможность внедрения)

__________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

ЗАКЛЮЧЕНИЯ ПО ПРЕДСТАВЛЕННОЙ РАБОТЕ

(Степень самостоятельной работы студента; совокупная оценка труда студента и его квалификация)

_____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Руководитель ВКР Е.И. Ряполова



Федеральное агентство связи

Федеральное государственное бюджетное образовательное учреждение высшего образования

«Поволжский государственный университет телекоммуникаций и информатики»

РЕФЕРАТ

Название Разработка метода определения информативных при-знаков биометрической идентификации пользова-телей

Автор Родимцев Иван Андреевич

Научный руководитель Ряполова Елена Ивановна

Ключевые слова Метод определения, информативные признаки, био-метрическая идентификация, пользователи

Дата публикации 2017

Библиографическое описание Родимцев, И.А. Разработка метода определения ин-формативных признаков биометрической идентификации пользователей: [Текст]: бакалаврская работа / И.А. Родимцев. Поволжский государственный университет телекоммуникаций и информатики (ПГУТИ). Факультет заочного обучения (ФЗО). Кафедра информационных систем и технологий (ИСТ): науч. рук. Е.И. Ряполова - Самара. 2017. - 93 с.

Аннотация В ВКР разработан метод выбора информативных признаков для биометрической идентификации пользователей. Целью является разработка метода выбора информативных признаков для биометрической идентификации пользователей на основе вычислительной техники.

Руководитель ВКР Е.И. Ряполова



Федеральное агентство связи

Федеральное государственное бюджетное образовательное учреждение высшего образования

«Поволжский государственный университет телекоммуникаций и информатики»

ПОКАЗАТЕЛИ КАЧЕСТВА ВКР

По ВКР студента Родимцева Ивана Андреевича

На тему Разработка метода определения информативных признаков биометрической идентификации пользователей

1 Работа выполнена :

- по теме, предложенной студентом

- по заявке предприятия наименование предприятия

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

2 Результаты ВКР:

- рекомендованы к опубликованию указать где

- рекомендованы к внедрении указать где

- внедрены акт внедрения

3 ВКР имеет практическую ценность

Проект разработки программы определения информативных признаков для биометриче-ской идентификации в чем заключается практическая ценность

4 Использование ЭВМ при выполннии ВКР: (ПО, компьютерное моделирование, компьютерная обработка данных и др.)

Компьютерное моделирование, программирование

5 ВКР прошла проверку на объем % заимствований

Студент БИСТу-30 И.А. Родимцев

Руководитель

ВКР доцент к.п.н., доцент Е.И. Ряполова



Введение

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

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

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

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

Целью дипломного проекта (работы) является разработать метод выбора информативных признаков для биометрической идентификации пользователей на основе вычислительной техники.

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

? провести анализ задачи определения информативных признаков в теории и практики распознания образов;

? обзор и определение требований к методам сокращения признакового пространства;

? исследовать законы распределения значений признаков;

? разработать алгоритм сокращения признакового пространства;

? разработать программный продукт.

Объектом исследования выступает (является) совокупность биометрических признаков пользователей.

Предметом исследования является методы выбора информативных признаков для биометрической идентификации пользователей на основе вычислительной техники.

Основными источниками информации для написания работы послужили справочная литература и литература по теме ВКР

Цель и задачи написания работы определили ее структуру, которая состоит из введения, 3 глав и заключения.

Во введении обосновывается актуальность работы, цель, задачи, объект и предмет исследования.

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

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

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

В заключении сделаны основные выводы и результаты по проделанной работе.



1. Задача определения информативных признаков в теории и практике распознавания образов

1.1 Характеристика задачи распознавания образов

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

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

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

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

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

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

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

Общая структура системы распознавания и этапы в процессе ее разработки показаны на рисунке 1.1.



Рисунок 1.1 - Структура системы распознавания

Задачи распознавания имеют следующие характерные черты.

Это информационные задачи, состоящие из двух этапов:

преобразование исходных данных к виду, удобному для распознавания;

собственно распознавание (указание принадлежности объекта определенному классу).

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

Для этих задач трудно строить формальные теории и применять классические математические методы (часто недоступна информация для точной математической модели или выигрыш от использования модели и математических методов несоизмерим с затратами).

Выделяют следующие типы задач распознавания:

задача распознавания - отнесение предъявленного объекта по его описанию к одному из заданных классов (обучение с учителем);

задача автоматической классификации - разбиение множества объектов, ситуаций, явлений по их описаниям на систему непересекающихся классов (таксономия, кластерный анализ, самообучение);

задача выбора информативного набора признаков при распознавании;

задача приведения исходных данных к виду, удобному для распознавания;

динамическое распознавание и динамическая классификация - задачи 1 и 2 для динамических объектов;

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

1.2 Биометрические системы распознавания внешности

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

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

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

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

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

По сравнению с традиционными биометрические методы идентификации личности имеют ряд преимуществ, а именно:

биометрические признаки очень трудно фальсифицировать;

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

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

1.2.1 Характеристики биометрических систем

Наиболее важный фактор успеха биометрической системы - это ее одобрение пользователями. Оно, в свою очередь, зависит от нескольких факторов. Во-первых, устройство не должно вызывать у пользователя чувства тревоги или дискомфорта. Возможно, это субъективный показатель, но он весьма важен для понимания проблем пользователей. Если люди боятся использовать устройство, то, скорее всего, они будут обращаться с ним неправильно и в результате не получат доступа. Во-вторых, биометрическое устройство должно быть простым в использовании. Клиентам нравятся устройства, с которыми просто работать. В-третьих, биометрическое устройство должно функционировать четко и точно. Если биометрическая система работает так, как надо, она делает две вещи: не позволяет войти "плохим" и разрешает вход "хорошим". Однако ни одно устройство не может быть абсолютно совершенным, и биометрические системы - не исключение, они могут допустить ошибку: впустить "плохих" или закрыть вход для "хороших". Возможность таких ошибок выражается уровнем ложных приемов и ложных отказов.

Показателями надежности биометрических систем могут служить вероятности ошибок первого и второго рода. Ошибки первого рода определяют вероятность ложного отказа (FRR, False Rejection Rate) и возникают при отказе в доступе легальному пользователю системы. Ошибки же второго рода показывают вероятность ложного допуска (FAR, False Acceptance Rate) и появляются при предоставлении доступа постороннему лицу. FRR и FAR связаны обратной зависимостью. Современные биометрические системы имеют очень большой разброс этих характеристик.

Биометрическую систему также можно характеризовать уровнем равной вероятности ошибок первого и второго рода (EER, Equal Error Rates) -- точкой, в которой вероятность ошибки первого рода равна вероятности ошибки второго рода. На основании EER можно делать выводы об относительных достоинствах и недостатках разных биометрических методов. Чем ниже уровень EER, тем лучше. Например, уровень в один процент означает, что из 100 попыток опознания человек будет ошибочно отвергнут или ошибочно узнан один раз.

Еще один параметр, о котором стоит задуматься при выборе и установке биометрической системы, - ее пропускная способность. По сути, это время, которое требуется человеку для взаимодействия с данным устройством.

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

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

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

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

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

1.3 Обзор методов сокращения признакового пространства

Достаточно детально исследовались лишь линейные преобразования пространства признаков. Ограничение на линейность позволяет значительно упростить задачу, как с вычислительной, так и с концептуальной точки зрения. И действительно, в этом направлении уже достигнуты значительные успехи и разработаны такие методы, как анализ главных компонент (АГК), факторный анализ (ФА), анализ независимых компонент (АНК) и ряд других методов.

1.3.1 Постановка задачи

Пусть имеется набор данных x1, x2,…,xM, где xk € Rm - это m-мерный вектор xk=(xk,1,xk,2,…,xk,N)T, который также часто интерпретируется, как реализация некоторого случайного вектора X. Тогда задача заключается в том, чтобы найти функцию f: Rm > Rn, преобразующую исходный массив данных sx=f(xk) таким образом, чтобы результирующие вектора признаков sx обладали некоторыми желаемыми свойствами. Можно также рассматривать новый случайный вектор S= f(X), который определяется по формуле 1.1.

, (1.1)

где X- случайный вектор,

W -матрица линейного преобразования

Обычно преобразование f полагается линейным, а случайные вектора X и S - центрированными.

Цель заключается в поиске оптимальных коэффициентов матрицы. Очевидно, основной вопрос заключается в установлении критерия оптимальности преобразования. Оптимальность определяется по статистическим свойствам случайных векторов X и S.

1.3.2 Методы второго порядка

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

Это исторически первые и наиболее разработанные методы, среди которых наиболее известными являются классические методы АГК и ФА. Естественно, для общего решения задачи представления многомерных данных необходимо преодолеть эти два ограничения: ограничение на линейность преобразования и ограничение на рассмотрение моментов второго порядка. Рассмотрим, в чем заключается второе ограничение.

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

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

1.3.3 Анализ главных компонент

Наиболее часто анализ главных компонент используется для уменьшения размерности исходных данных, то есть размерности n выходного вектора S=(S1, S2,…,Sn)T фиксирована и n<m (часто n<<m). То, что из описания исключаются некоторые компоненты (после линейного преобразования), увеличивает среднюю ошибку описания, а поскольку минимизируется именно СКО, то в первую очередь должны исключаться компоненты, обладающие минимальной дисперсией. Иными словами, остаются компоненты, объясняющие максимальное количество вариативности данных.

При реализации АГК оказывается возможным вычислять главные компоненты последовательно. Пусть w1 - это направление первой главной компоненты (вектор w имеет ту же размерность m, что и случайный вектор данных X). Поскольку минимизируется средняя ошибка, вызванная неполнотой описания, то добавляемая в описание компонента должна иметь максимальную дисперсию, а значит, ее направление следует определить по формуле 1.2.

(1.2)

Следовательно, первая главная компонента - это проекция на данное направление S1=w1TX. Определив первые k-1 главных компонент, направление k-й главной компоненты определяется как направление главной компоненты остатков по формуле 1.3.

(1.3)

А сами главные компоненты вычисляются как Si=wiTX.

Оказывается, что подобные вычисления равносильны вычислению n собственных векторов ковариационной матрицы C = E{XXT}. Величины wi - это собственные вектора матрицы C, которые соответствуют n наибольшим ее собственным числам.

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

Рисунок 1.2 - Пример неадекватного выбора наиболее значимых направлений при применении методов второго порядка (в частности, анализа главных компонент)

Тем не менее, в определенных случаях этот метод может быть весьма полезен. Например, если исходные данные относятся к объектам одного типа (в пространстве признаков один класс), то данный метод может быть использован для уменьшения шумов. Он также может быть полезен и в целях распознавания образов, но при условии, что различные признаки равноправны, а расстояние между классами больше размеров классов, то есть метрика пространства признаков евклидова. Тогда уменьшение размерности пространства признаков с помощью АГК может существенно упростить дальнейший анализ. Как и другие подобные методы, АГК может использоваться в целях когнитивной графики (например, для простой визуализации данных, n=2).

1.3.4 Факторный анализ

Факторный анализ (ФА), также как и АГК, является методом второго порядка, работающим с линейными преобразованиями. В этом смысле он мало отличается от АГК. Однако, вместо поиска прямого преобразования от исходных данных к их оптимальному представлению, в ФА производится поиск факторов - скрытых переменных, которыми описывается источник информации. При этом используется следующая общая модель, представленная в формуле 1.4

, (1.4)

где X - это случайный вектор, соответствующий исходным данным;

S - вектор скрытых переменных (факторов), который не наблюдается напрямую;

A - постоянная mxn матрица;

N - шум

Предполагается, что случайные вектора S и N имеют многомерное гауссово распределение. Обычно рассматривается случай, когда S имеет более низкую размерность, чем X, то есть рассматривается задача уменьшения размерности данных.

Поскольку, не считая вырожденных случаев, всегда можно найти nxm матрицу W=A' такую, что A'A= En (En - единичная матрица размера nxn), то решение задачи поиска факторов равносильна задаче нахождения следующего вектора S, который определяется формулой 1.5.

(1.5)

Таким образом, единственным принципиальным отличием ФА от АГК является добавление в модель данных шума N. Другое отличие, хотя и не принципиальное, заключается в том, что в ФА факторы определяются не однозначно, а с точностью до вращения. Однако и в АГК мы можем выбрать любой базис в АГК подпространстве, что аналогично неоднозначности выбора факторов. Выбор наиболее "интересного" базиса часто рассматривается в качестве отдельной задачи, что, опять же, говорит о том, что данные методы не решают проблему представления данных.

Обычно факторный анализ сводится к применению АГК с учетом шума, то есть к нахождению главных компонент для модифицированной ковариационной матрицы C-У , где C , как и ранее, - это ковариационная матрица X, а У=E(NNT) - это ковариационная матрица шума. Такой подход называется анализом главных факторов (АГФ). Есть методы, основанные на оценке максимального правдоподобия, которые напрямую не обращаются к АГК, однако также могут быть к нему сведены. Ковариационная матрица шума либо считается известной априори, либо дополнительно применяются какие-либо методы ее оценки.

1.3.5 Методы, основанные на статистиках высоких порядков

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

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

При использовании второго критерия стремятся выделить наиболее "интересные" направления. Под "интересностью", как правило, понимают то, насколько по данному направлению распределение отличается от нормального распределения. Можно показать, что при фиксированной ковариационной матрице максимум энтропии приходится именно на гауссово распределение. Для любого другого распределения, энтропия строго меньше. Поэтому обычно ищутся такие компоненты S=wTX, которые максимизируют энтропию H(wTX) при условии, что дисперсия E{(wTX)2} постоянна независимо от w.

1.3.6 Анализ независимых компонент

В этом методе предлагается искать такие направления, которые дают максимально статистически независимые компоненты. По определению, набор случайных величин Y1,Y2,…,Ym является (взаимно) статистически независимым, если для его плотности распределения вероятностей верно соотношение в формуле 1.6.

(1.6)

При этом вводится некоторая мера статистической независимости компонент, максимум которой и ищется.

Существуют различные определения АНК, различия между которыми примерно такие же, как и между АГК и ФА. То есть эти различия вызваны тем, производится поиск компонент или факторов и присутствует ли в модели шум. Существуют также различные меры, оценивающие статистическую независимость. При этом обычно перед применением АНК производится нормировка случайных величин (в дополнение к центрированию).

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

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

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

(1.7)

Как известно, взаимная информация равна нулю тогда и только тогда, когда случайные величины являются статистически независимыми.



1.3.7 Метод группового учета аргументов

Перед тем, как начинать рассмотрение МГУА, было бы полезно вспомнить или узнать впервые метод наименьших квадратов - наиболее распространенный метод подстройки линейно зависимых параметров.

Рассмотрим для примера МНК для трех аргументов:

Пусть функция T=T(U, V, W) задана таблицей, то есть из опыта известны числа U-i, Vi, Wi, Ti ( i = 1, : , n). Будем искать зависимость между этими данными по формуле 1.8.

, (1.8)

где a, b, c - неизвестные параметры.

Подберем значения этих параметров так, чтобы была наименьшей сумма квадратов уклонений опытных данных Ti и теоретических Ti = aUi + bVi + cWi, то есть сумма, представленная в формуле 1.9.

(1.9)

(1.10)

(1.11)

Величина s является функцией трех переменных a, b, c. Необходимым и достаточным условием существования минимума этой функции является равенство нулю частных производных функции s по всем переменным, то есть принимает вид представленный в формуле 1.10 и 1.11.

То система для нахождения a, b, c будет иметь вид представленный в формуле 1.12.

(1.12)

Данная система решается любым стандартным методом решения систем линейных уравнений (Гаусса, Жордана, Зейделя, Крамера).

Рассмотрим некоторые практические примеры нахождения приближающих функций. 1. y = ax2 + bx + g

Задача подбора коэффициентов a, b, g сводится к решению общей задачи при T=y, U=x2, V=x, W=1, a=a, b=b, g=c.

2. f(x, y) = asin(x) + bcos(y) + g/x

Задача подбора коэффициентов a, b, g сводится к решению общей задачи при T=f, U=sin(x), V=cos(y), W=1/x, a=a, b=b, g=c.

Если мы распространим МНК на случай с m параметрами, то путем рассуждений, аналогичных приведенным выше, получим следующую систему линейных уравнений, представленных в формуле 1.13.

, (1.13)

Заимствование алгоритмов переработки информации у природы является одной из основных идей кибернетики. "Гипотеза селекции" утверждает, что алгоритм массовой селекции растений или животных является оптимальным алгоритмом переработки информации в сложных задачах. При массовой селекции высевается некоторое количество семян. В результате опыления образуются сложные наследственные комбинации. Селекционеры выбирают некоторую часть растений, у которых интересующее их свойство выражено больше всего (эвристический критерий). Семена этих растений собирают и снова высевают для образования новых, еще более сложных комбинаций. Через несколько поколений селекция останавливается и ее результат является оптимальным Если чрезмерно продолжать селекцию, то наступит <инцухт> - вырождение растений. Существует оптимальное число поколений и оптимальное количество семян, отбираемых в каждом из них.

Алгоритмы МГУА воспроизводят схему массовой селекции , показанной на рисунке 1.3. В них есть генераторы усложняющихся из ряда в ряд комбинаций и пороговые самоотборы лучших из них. Так называемое <полное> описание объекта, в виде формулы 1.14.

j = f(x1,x2,x3,ј,xm), (1.14)



Рисунок 1.3 - Селекция самого черного тюльпана при расширяющемся опытном поле (эквивалент полного перебора), и при постоянном размере поля (эквивалент селекции при сохранении свободы выбора решений F = const)

Например степенной полином, заменяется несколькими рядами "частных" описаний формулы 1.15

y1= f(x1x2), y2= f(x1x3),..., ys= f(xm-1xm) (1.15)

z1= f(y1y2), z2= f(y1y2),..., zp= f(ys-1ys),

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

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

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

Рисунок 1.4 - МГУА как эквивалент массовой селекции

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

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



yi=a0+a1xi+a2xj+a3xixj; (1.16)

yk=a0+a1xi+a2xj+a3xixj+a4xi2+a5xj2.

Сложность модели увеличивается от ряда к ряду селекции как по числу учитываемых аргументов, так и по степени. Степень полного описания быстро растет. На первом ряду - квадратичные описания, на втором - четвертой степени, на третьем - восьмой и т. д. В связи с этим минимум критерия селекции находится быстро, но не совсем точно. Кроме того, имеется опасность потери существенного аргумента, особенно на первых рядах селекции (в случае отсутствия протекции). Специальные теоремы теории МГУА определяют условия, при которых результат селекции не отличается от результата полного перебора моделей.

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

1.4 Определение требований к методам определения информативных признаков для биометрической идентификации пользователей

Задача формирования признакового пространства является одним из ключевых в построении системы распознавания образов.

Метод определения информативных признаков должен удовлетворять следующим требованиям:

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

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

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

закон распределения значений признаков; все признаки пользователей должны подчиняться существующему закону распределения и иметь соответствующее математическое описание.

1.5 Постановка задачи

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

Основные решаемые задачи:

провести анализ задачи определения информативных признаков в теории и практики распознания образов;

обзор и определение требований к методам сокращения признакового пространства;

исследовать законы распределения значений признаков;

разработать алгоритм сокращения признакового пространства;

разработать программный продукт.



2. Разработка метода для сокращения признакового пространства для биометрической идентификации пользователя

2.1 Характеристика математической модели распознавания образов

2.1.1 Сущность моделирования и общая классификация моделей

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

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

Математические модели в свою очередь подразделяются на статистические (матричные), операциональные (алгоритмические) и аналитические.

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

...