Содержание к диссертации
Введение
1 Анализ коллективов решающих правил в задачах распознавания образов 10
1.1 Классификация статистических алгоритмов распознавания образов коллективного типа 10
1.2 Традиционные методы построения коллективов решающих правил 13
1.3 Метод комитетов Вл.Д. Мазурова 14
1.4 Алгебраический подход Ю.И. Журавлёва 17
1.5 Метод группового учёта аргументов в задаче распознавания образов 19
1.6 Непараметрические алгоритмы обучения распознаванию образов 20
1.7 Многоуровневые системы распознавания образов 23
1.8 Линейные непараметрические коллективы решающих правил 28
Выводы 31
2 Нелинейные непараметрические коллективы в двуальтернативной задаче распознавания образов 32
2.1 Нелинейные непараметрические коллективы решающих правил, основанные на оценках частных решающих функций 32
2.2 Нелинейные непараметрические коллективы решающих правил, основанные на оценках частных решений 38
2.3 Нелинейные непараметрические коллективы решающих правил, основанные на оценках частных плотностей вероятности 40
2.4 Исследование свойств нелинейных непараметрических коллективов решающих правил 42
Выводы 49
3 Синтез и анализ непараметрических систем распознавания для многоальтернативной задачи классификации 50
3.1 Постановка задачи распознавания образов 50
3.2 Методика синтеза многоуровневых непараметрических систем распознавания образов, основанная на методе дихотомии 51
3.3 Синтез непараметрических систем распознавания образов, основанных на декомпозиции обучающей выборки с учётом статистической независимости наборов признаков 59
3.4 Модификация непараметрической системы классификации, основанная на методе дихотомии 62
3.5 Исследование свойств многоуровневых непараметрических систем распознавания образов 65
Выводы 83
4 Программное обеспечение, реализующее многоуровневые непараметрические системы распознавания образов, и его применение 86
4.1 Назначение и функциональные возможности программного обеспечения 86
4.2 Структура программного обеспечения
4.3 Инструкции пользователю программного обеспечения для проведения вычислительных экспериментов 95
4.4 Применение программного обеспечения при выборе режимов функционирования хранилища материалов 98
Выводы 104
Заключение 105
Список литературы 107
- Классификация статистических алгоритмов распознавания образов коллективного типа
- Нелинейные непараметрические коллективы решающих правил, основанные на оценках частных решающих функций
- Методика синтеза многоуровневых непараметрических систем распознавания образов, основанная на методе дихотомии
- Назначение и функциональные возможности программного обеспечения
Введение к работе
Актуальность работы. Большинство статистических методов распознавания образов ориентировано на представительные обучающие выборки. Однако при решении прикладных задач часто располагают ограниченным объемом наблюдений — короткой либо малой выборкой, что обусловливается нестационарностью объекта исследования, высокой стоимостью и сложностью получения дополнительной информации. Получаемые на их основе решающие правила не всегда обеспечивают приемлемые результаты классификации, так как информация малых обучающих выборок недостаточна для оценивания вероятностных характеристик изучаемых закономерностей.
Для "обхода" проблем малых выборок широко использовались принципы декомпозиции систем и последовательные процедуры формирования решений. Множества ранее разработанных методов, представленные в работах Растригина Л.А., Розенблатта Ф., Нильсона Н., Патрика Э., Айзермана М.А. были обобщены и развиты в работах Мазурова Журавлёва Ю.И., Вл.Д., Ивахненко А.Г.
В соответствии с подходом Вл.Д. Мазурова (метод комитетов, 1990), для увеличения отношения "объем/размерность" (п/к) обучающей выборки формируются наборы признаков классифицируемых объектов, в пространстве которых строятся частные решающие правила. Для получения обобщенного решения используются методы коллективного оценивания на основе вторичных факторов, соответствующих количеству наборов исходных признаков. Недостатком метода комитетов является потеря информации при переходе от исходного вектора описания классифицируемых объектов к его булевому представлению при формировании обобщённого уравнения разделяющей поверхности.
Идея алгебраического подхода, предложенного Журавлёвым Ю.И в 1989 году, состоит в представлении алгоритма распознавания образов в виде двух операторов: распознающего и решающего правила. Распознающий оператор определяет меру близости контрольного объекта с каждым классом, а решающее правило относит ситуацию к конкретному классу. С распознающими операторами различных алгоритмов распознавания образов
можно производить алгебраические операции (сложения, умножения и умножения на число). Априорные сведения составляют обучающая выборка и конечное множество алгоритмов распознавания образов, имеющих самостоятельное значение. Необходимость определения вводимых порогов, констант, коллективов алгоритмов и порядок алгебраического замыкания создают вычислительные трудности в реализации предлагаемого подхода.
Метод группового учета аргументов (МГУ А) предложенный Ивахненко А.Г (1990). Данный алгоритм реализует последовательную процедуру усложнения решающего правила путем целенаправленного отбора (селекции) пар, состоящих из первичных и промежуточных признаков. Каждый этап синтеза алгоритма характеризуется отношением п/к = п/2. Алгоритмы МГУА отличаются друг от друга критерием селекции, количеством промежуточных моделей и их сложностью. Недостатком МГУА является резкое повышение вычислительных затрат при увеличении размерности признакового пространства.
В работе с позиции последовательных процедур принятия решений и принципов коллективного оценивания предлагаются статистические модели распознавания образов, представляющие собой семейство частных решающих функций, организация которых в нелинейном решающем правиле осуществляется с помощью методов непараметрической статистики. Частные решающие функции формируются на основе однородных частей обучающей выборки, которые удовлетворяют одному или нескольким требованиям, например, наличие однотипных признаков, возможность декомпозиции исходных признаков на группы в соответствии со спецификой решаемой задачи. Это порождает широкий круг постановок задач синтеза непараметрических систем распознавания образов. При интеграции частных решающих функций используются непараметрические оценки оптимальных байесовских решающих правил.
Исследования выполнены в рамках гранта РФФИ №07-01-00006 и поддержке Совета по грантам Президента РФ (гранты МД-2130.2005.9, НШ-3428.2006.9).
Объектом исследований являются многоуровневые системы распознавания образов.
Предметом исследований являются методы синтеза и анализа
многоуровневых непараметрических системы распознавания образов, основанных на декомпозиции обучающей выборки по её размерности.
Цель диссертационной работы состоит в разработке методических, алгоритмических и информационных средств построения многоуровневых непараметрических систем распознавания образов, основанных на принципах декомпозиции систем и последовательных процедурах формирования решений, обеспечивающих эффективное использование информации обучающих выборок большой размерности, включая априорные сведения о виде решающих функций.
Цель достигается путём решения следующих задач:
Систематизация существующих наиболее известных методов классификации, определение условий их применимости.
Развитие методов синтеза и анализа многоуровневых непараметрических систем в задачах распознавания образов, обеспечивающих эффективное использование информации обучающих выборок большой размерности.
Исследование свойств многоуровневых непараметрических систем распознавания образов в многоальтернативной задаче распознавания образов, при конечных объёмах обучающих выборок и их сравнение с традиционными непараметрическими классификаторами, определение области их компетентности.
Разработка и внедрение результатов теоретических исследований и программных средств, реализующих многоуровневые непараметрические систем распознавания образов, при выборе режимов функционирования неопределенных систем.
Методы исследования. Основные теоретические и прикладные результаты работы были получены на основе теории обучающихся систем, аппарата теории вероятности и математической статистики, методов коллективного оценивания и статистического моделирования.
Научная новизна результатов исследований 1. Предложена и обоснована оригинальная методика построения непараметрических систем распознавания образов в условиях обучающих выборок большой размерности на основе декомпозиции признаков классифицируемых объектов, построении частных уравнений
Классификация статистических алгоритмов распознавания образов коллективного типа
Большинство статистических методов распознавания образов ориентировано на представительные обучающие выборки. Однако при решении прикладных задач часто располагают ограниченным объемом наблюдений — короткой либо малой выборкой, что обусловливается нестационарностью объекта исследования, высокой стоимостью и сложностью получения дополнительной информации. Получаемые на их основе решающие правила не всегда обеспечивают приемлемые результаты классификации, так как информация малых обучающих выборок недостаточна для оценивания вероятностных характеристик изучаемых закономерностей.
Для "обхода" проблем малых выборок широко использовались принципы декомпозиции систем и последовательные процедуры формирования решений. Множества ранее разработанных методов, представленные в работах Растригина Л.А., Розенблатта Ф., Нильсона Н., Патрика Э., Айзермана М.А. были обобщены и развиты в работах Мазурова Журавлёва Ю.И., Вл.Д., Ивахненко А.Г.
В соответствии с подходом Вл.Д. Мазурова (метод комитетов, 1990), для увеличения отношения "объем/размерность" (п/к) обучающей выборки формируются наборы признаков классифицируемых объектов, в пространстве которых строятся частные решающие правила. Для получения обобщенного решения используются методы коллективного оценивания на основе вторичных факторов, соответствующих количеству наборов исходных признаков. Недостатком метода комитетов является потеря информации при переходе от исходного вектора описания классифицируемых объектов к его булевому представлению при формировании обобщённого уравнения разделяющей поверхности.
Идея алгебраического подхода, предложенного Журавлёвым Ю.И в 1989 году, состоит в представлении алгоритма распознавания образов в виде двух операторов: распознающего и решающего правила. Распознающий оператор определяет меру близости контрольного объекта с каждым классом, а решающее правило относит ситуацию к конкретному классу. С распознающими операторами различных алгоритмов распознавания образов можно производить алгебраические операции (сложения, умножения и умножения на число). Априорные сведения составляют обучающая выборка и конечное множество алгоритмов распознавания образов, имеющих самостоятельное значение. Необходимость определения вводимых порогов, констант, коллективов алгоритмов и порядок алгебраического замыкания создают вычислительные трудности в реализации предлагаемого подхода.
Метод группового учета аргументов (МГУ А) предложенный Ивахненко А.Г (1990). Данный алгоритм реализует последовательную процедуру усложнения решающего правила путем целенаправленного отбора (селекции) пар, состоящих из первичных и промежуточных признаков. Каждый этап синтеза алгоритма характеризуется отношением п/к = п/2. Алгоритмы МГУА отличаются друг от друга критерием селекции, количеством промежуточных моделей и их сложностью. Недостатком МГУА является резкое повышение вычислительных затрат при увеличении размерности признакового пространства.
В работе с позиции последовательных процедур принятия решений и принципов коллективного оценивания предлагаются статистические модели распознавания образов, представляющие собой семейство частных решающих функций, организация которых в нелинейном решающем правиле осуществляется с помощью методов непараметрической статистики. Частные решающие функции формируются на основе однородных частей обучающей выборки, которые удовлетворяют одному или нескольким требованиям, например, наличие однотипных признаков, возможность декомпозиции исходных признаков на группы в соответствии со спецификой решаемой задачи. Это порождает широкий круг постановок задач синтеза непараметрических систем распознавания образов. При интеграции частных решающих функций используются непараметрические оценки оптимальных байесовских решающих правил.
Исследования выполнены в рамках гранта РФФИ №07-01-00006 и поддержке Совета по грантам Президента РФ (гранты МД-2130.2005.9, НШ-3428.2006.9).
Объектом исследований являются многоуровневые системы распознавания образов. Предметом исследований являются методы синтеза и анализа многоуровневых непараметрических системы распознавания образов, основанных на декомпозиции обучающей выборки по её размерности. Цель диссертационной работы состоит в разработке методических, алгоритмических и информационных средств построения многоуровневых непараметрических систем распознавания образов, основанных на принципах декомпозиции систем и последовательных процедурах формирования решений, обеспечивающих эффективное использование информации обучающих выборок большой размерности, включая априорные сведения о виде решающих функций. Цель достигается путём решения следующих задач: 1. Систематизация существующих наиболее известных методов классификации, определение условий их применимости. 2. Развитие методов синтеза и анализа многоуровневых непараметрических систем в задачах распознавания образов, обеспечивающих эффективное использование информации обучающих выборок большой размерности. 3. Исследование свойств многоуровневых непараметрических систем распознавания образов в многоальтернативной задаче распознавания образов, при конечных объёмах обучающих выборок и их сравнение с традиционными непараметрическими классификаторами, определение области их компетентности. 4. Разработка и внедрение результатов теоретических исследований и программных средств, реализующих многоуровневые непараметрические систем распознавания образов, при выборе режимов функционирования неопределенных систем.
Нелинейные непараметрические коллективы решающих правил, основанные на оценках частных решающих функций
С позиции принципов декомпозиции исходной задачи и коллективного оценивания разработаны оригинальные нелинейные непараметрические классификаторы с двухуровневой структурой для двуальтернативной задачи распознавания образов в условиях обучающих выборок большой размерности. Их применение обеспечивает значительное снижение ошибки распознавания образов на контрольных выборках в (1.5-3) раза и на порядок с использованием обучающих выборок по сравнению с традиционным непараметрическим классификатором. С ростом размерности признаков классифицируемых объектов преимущество предлагаемых систем распознавания образов при оптимальном количестве частных решающих правил возрастает.
Обнаружен экстремальный характер зависимости показателей эффективности нелинейного непараметрического классификатора от количества частных решающих правил первого уровня его структуры. Положение экстремума зависит от объёма исходной выборки и размерности признаков классифицируемых объектов. Перспективы развития предлагаемого подхода связаны с его применением в задачах классификации в условиях разнотипной информации и неоднородных выборок, получаемых в результате заполнения пропусков данных.
Методика синтеза непараметрических систем распознавания образов для двуальтернативной задачи классификации с использованием принципов декомпозиции была предложена в разделе 2. Полученные многоуровневые непараметрические системы, обеспечивают эффективное решение двуальтернативных задач распознавания образов в условиях обучающих выборок значительной размерности на основе принципов коллективного оценивания и декомпозиции задачи классификации. Однако в многоальтернативной задачи классификации переход в пространстве вторичных признаков (значения частных решающих функций) сопряжён с увеличением размерности задачи распознавания образов, что затрудняет её реализацию при ограниченных объёмах обучающих выборок. Применение в этом случае последовательных процедур классификации методом дихотомии приводит к снижению вычислительной эффективности непараметрических алгоритмов распознавания образов. В данном разделе предлагается методика построение непараметрических классификаторов для многоальтернативной задачи распознавания образов, основанной на декомпозиции обучающей выборки по её размерности и технологии параллельных вычислений [26, 68]. Исследуются свойства показателей эффективности многоуровневых непараметрических систем распознавания образов с помощью методов статистического моделирования. Пусть обучающая выборка, составленная из признаков классифицируемых объектов х = (х[,..,х к) и «указаний учителя» об их принадлежности к одному из классов Qj,j = \,M. Априорные вероятности классов и условные плотности вероятности распределения классов xeQj неизвестны. При этом отношение относительно мало. В этих условиях использование традиционных непараметрических алгоритмов затруднено. Для обхода возникшей проблемы используем принципы декомпозиции задачи классификации на ряд более простых задач с последующей интеграцией их решений в обобщённом алгоритме классификации. 1. Проведём ранжирование классов обучающей выборки по значениям показателя разброса их признаков. Этот шаг позволяет задать порядок принадлежности классов обучающей выборки к уровням многоуровневой непараметрической системы.
Методика синтеза многоуровневых непараметрических систем распознавания образов, основанная на методе дихотомии
Из приведённого рисунка 3.16 графикам видно, что с увеличением объёма обучающей выборки класса, зависимость от качества работы подсистем первых подуровней многоуровневой непараметрической системы остаётся постоянной. При увеличении параметров размытости подсистем первых подуровней многоуровневой непараметрической системы на 25% и 50% происходит линейное увеличение величины оценки вероятности ошибки распознавания. При уменьшении параметров размытости подсистем первых подуровней многоуровневой непараметрической системы на 25% и 50% происходит быстрое увеличение величины оценки вероятности ошибки распознавания, которое с ростом объёма обучающей выборки уменьшается.
При анализе всех рисунков 3.13, 3.14, 3.15, 3.16 можно выделить следующие закономерности: 1) При объёме выборки п=24, для любого способа формирования группы признаков, оценка вероятности ошибки распознавания колеблется в диапазоне от 28 до 32%. Это объясняется недостаточной представительностью обучающей выборки (2 точки на класс при 12 мерном признаковом пространстве). 2) При объёме выборки n=36 , п=48, п=96 для различных способов формирования групп, многоуровневая непараметрическая система реагирует резкими увеличениями оценки вероятности ошибки распознавания на ухудшение качества работы первых подуровней всех уровней алгоритма. Это объясняется недостаточной представительностью обучающей выборки (3,4,6 точки на класс при 12 мерном признаковом пространстве), но при этом свойства каждого распознаваемого класса уже видны. Также, исходя из графиков рисунка 3.10, именно при указанных значениях п система показывает наибольшую эффективность, по сравнению с традиционным непараметрическом алгоритмом (в 1.3-1.7 раза). 3) При объёме выборки n=144 , п=168, п=192 для различных способов формирования группы, алгоритм реагирует плавным увеличениями величины ошибки распознавания на ухудшение качества работы подсистем первых подуровней многоуровневой непараметрической системы. Это объясняется достаточной представительностью обучающей выборки (12, 14, 16 точки на класс при 12 мерном признаковом пространстве). Исходя из рисунков 3.10, именно при указанных значениях п алгоритм показывает постоянное преимущество, по сравнению с традиционным непараметрическом алгоритмом (в 1.1-1.4 раза). 1. На основе метода дихотомии и его модификаций предложен подход синтеза непараметрических систем распознавания образов обобщён на многоальтернативную задачу классификации, обеспечивающий значительное сокращение времени формирования решения на основе использования технологии параллельных вычислений. Вычисления, проводимые традиционным непараметрическими алгоритмами не могут быть разделены на ряд задач одинаковой сложности, для их выполнения в разных вычислительных потоках. Разделение классов и признаков в многоуровневых моделях распознавания образов способствует распараллеливанию вычислений и обеспечивает продуктивное использование мульти-ядерных (мультипроцессорных) вычислительных систем. 2. Обоснована методика синтеза двухуровневых непараметрйческих систем распознавания образов для многоальтернативных задач классификации,v основанная на формировании независимых групп признаков исследуемых объектов, построении на этой основе частных и обобщённых решающих правил. При этом вычислительная эффективность решения двух и многоальтернативных задач распознавания образов мало отличаются 3. Определена зависимость оценки вероятности ошибки распознавания образов от параметров структуры многоуровневых непараметрических классификаторов и особенностей обучающей выборки. Для эффективной работы предлагаемой иепараметрической системы необходимо на первых подуровнях структуры формировать независимые наборы признаков, а их размерность должна быть равна количеству групп признаков. 4. По результатам анализа данных вычислительного эксперимента, установлено достоверное преимущество предлагаемых многоуровневых непараметрических систем классификации над традиционным непараметрическим алгоритмом распознавания образов парзеновского типа, которые особо проявляются при относительно малых значениях отношения «обьелі выборки/(количество классов х размерность выборки)». При этом оценка вероятности ошибки исследуемой системы.
Назначение и функциональные возможности программного обеспечения
Программное обеспечение, реализующее методику построения многоуровневой непараметрической системы классификации выборок в условиях малых выборок, создано в визуальной среде Inprise Borland C++ Builder 6.0 [56].
Программа генерации обучающей и контрольной выборок. Для задания параметров генерации обучающих и контрольной выборок необходимо запустить исполняемый файл cCreator.exe. На экране плявляется окно пользовательского интерфейса, представленное на рисунке 4.2. В этом окне задаются параметры проведения вычислительных экспериментов и запускается процедура генерации выборок.
Параметр «Используемый файл БД» задаёт файл БД, в который будут сохранятся параметры классов и обучающие выборки. Группа параметров «Условия нового эксперимента»: «Повторений» - задаёт количество повторений одного и того же вычислительного эксперимента при одинаковых условиях. Для каждого повторения генерируется отдельная обучающая выборка. «Кол-во классов» - задаёт количество классов для которых будет генерироваться выборки. «Размерность» - задаёт размерность признакового пространства контрольной и обучающей выборок. Кнопка «Создать запись эксперимента» вносит параметры повторений, количества классов, размерности в базу данных и получает идентификатор серии вычислительных экспериментов. Параметр «ID» эксперимента отображает идентификатор эксперимента. Параметр «Тип параметра» выполнен в виде выпадающего списка, позволяет задать параметр для которого вносится значение. Доступные варианты типов параметра: «Матожидание», «Среднеквадратическое отклонение», «Объём выборки класса контрольной выборки», «Объём выборки класса обучающей выборки», «Задание коэффициента к1»,«3адание коэффициента 1 2» (для проверки качества работы многоуровневого алгоритма при различной эффективности функционирования первых подуровней системы), «Значение ситуации для определения принадлежности». Параметр «Номер класса» выполнен в виде выпадающего списка, позволяет задать класс, для которого вносится значение с параметром определённым в выпадающем списке «Тип параметра». Параметр «Номер признака» выполнен в виде выпадающего списка, позволяет задать номер признака в одной из выборок, для которого вносится значение с параметром определённым в выпадающем списке «Тип параметра». Параметр «Значение» позволяет указать значение для, класса. . определённого в выпадающем списке «Номер класса» и с типом определённым в выпадающем списке «Тип параметра». Кнопка «Задать значение» вносит значение параметра указанного в поле «Значение». Группа параметров «Сгенерированные эксперименты» содержит кнопку «Считать доступные эксперименты» и выпадающий список. Кнопка «Считать доступные эксперименты» считывает из базы данных данные о экспериментах, внесённых в БД ранее. Краткое описание эксперимента выводится в выпадающем списке ниже. Выпадающий список группы параметров «Сгенерированные эксперименты» позволяет выбрать уже сформированные записи экспериментов. При выборе в текстом окне справа выводится данные о корректности записей выбранного эксперимента. Кнопка «Сгенерировать данные» запускает процедуру формирования обучающих и контрольной выборок для выбранного эксперимента. В случае некорректности записей описывающих эксперимент в текстовое окно справа выводятся сообщения с результатами диагностики. Программа проведения серии вычислительных экспериментов. После запуска исполняемого файла cRecogn.exe, на экране появляется главное окно программы, представленное на рисунке 4.3. Параметр «Используемый файл» позволяет задать файл базы данных, из которого буду считываться обучающие и контрольные выборки и заноситься данные о результатах вычислительного эксперимента. Группа параметров «Загрузка параметров». Кнопка «Загрузить доступные эксперименты» считывает записи вычислительных экспериментов из указанной базы данных и вносит их в выпадающий список «Эксперименты». Параметр «Эксперименты» выполнен как выпадающий список. Им задаётся выполняемая серия экспериментов и запускается проверка целостности контрольной и обучающих выборок для данной серии. Параметр «Точки для определения принадлежности» выполнен как выпадающий список. Им задаётся выполняемая серия экспериментов и запускается проверка целостности контрольной и обучающих выборок для данной серии. Текстовое окно «Текущее состояние серии экспериментов» выводит результаты контроля целостности обучающих и контрольной выборок выбранной серии экспериментов, а во время расчёта серии вычислительных экспериментов отображает состояние и результаты выполнения.
