Исследование в области сложности алгебро-логического анализа данных и синтеза распознающих процедур

• Автор: Сотнезов, Роман Михайлович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Москва
• Количество страниц: 112 с.

Оглавление
Введение
Глава 1. Синтез процедур распознавания с использованием алгебро-логического
подхода
1.1. Основные определения
1.2. Модель голосования по корректным наборам эл.кл. класса
1.3. Построение корректных наборов эл.кл. класса
1.4. Модели голосования по монотонным и антимонотонным корректным
наборам эл.кл. класса
1.5. Связь алгебро-логического подхода с классическими логическими
процедурами распознавания
1.6. Обобщение алгебро-логического подхода на случай произвольного набора распознающих алгоритмов
1.7. Сложность задачи перечисления корректных наборов эл.кл
1.8. Тестирование моделей голосования по (монотонным) корректным наборам
эл.кл. классов
Глава 2,Корректное понижение значности информации в задачах распознавания
2.1. Основные определения
2.2. Алгоритмы поиска оптимальной корректной перекодировки КОД1
2.3. Однокритериальные генетические алгоритмы поиска оптимальной
корректной перекодировки КОД2, КОДЗ, КОД4
2.4. Двухкритериальный генетический алгоритм поиска оптимальной
корректной перекодировки КОД5
2.5. Результаты тестирования
Глава 3.Генетические алгоритмы в задачах дискретной оптимизации
3.1. Постановка задачи
3.2. Представление особей в генетическом алгоритме
3.3. Формирование начальной популяции
3.4. Функция приспособленности и выбор родительских особей
3.5. Операторы скрещивания и мутации
3.6. Восстановление допустимости решения
3.7. Обновление популяции
3.8. Описание алгоритмов ОАВтагу и ОА№тВшагу
3.9. Результаты вычислений на тестовых задачах
3.10. Адаптация алгоритмов ОаВтагу и ОаМопВтагу для многопроцессорных комплексов

Глава 4. Метрические свойства множества тупиковых покрытий булевых и целочисленных матриц
4.1. Основные понятия и результаты, полученные ранее
4.2. Метрические свойства множества покрытий булевых и целочисленных матриц в случае п <т
4.3. Метрические свойства множества максимальных конъюнкций двузначной логической функции в случае п < т
4.4.0 сложности алгоритмов построения тупиковых покрытий булевых и целочисленных матриц, основанных на перечислении совместимых наборов столбцов
Заключение
Список литературы

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

Паре объектов Б' и Б" ставится в соответствие строка £)"(£', 5") = (й"
= |1, если 5((5') = 0 и Я(Н;><Г/)(5") = 1,
; 1о, иначе.
у = 1,2
0"(Б',Б") таких, что 5' £ Я(Т,К), Б" £ Я(Т,К).
По построению каждому столбцу в матрицах ЬА/ к, ЬА" к соответствует некоторый эл.кл. из множеств СА’(К), САч(К) соответственно. Пусть набору столбцов Я'(Я") матрицы 1А/ к (ЬА" к) соответствует набор эл.кл. 1/Н'(Пн"). Из утверждений 1.2.2 - 1.2.4 следуют утверждения
Утверждение 1.4.2 Набор эл.кл. инг(ини) является монотонным (антимонотонным) корректным для класса К тогда и только тогда, когда Я'(Я") - покрытие матрицы ЬА' к (ЬА"К).
Утверждение 1.4.3 Набор эл.кл. Ян/(Нн") является тупиковым монотонным (антимонотонным) корректным набором для класса К тогда и только тогда, когда Я'(Я") - тупиковое покрытие матрицы 1А< к {ЬА" к).
Утверждение 1.4.4 Набор эл.кл. ЯН'(ЯН") является минимальным монотонным (антимонотонным) корректным набором для класса К тогда и только тогда, когда Я'(Я") - минимальное покрытие матрицы ЬА> к (ЬА" к).
1.5.Связь алгебро-логического подхода с классическими логическими процедурами распознавания.
Рассмотрим частный случай, когда множество СА(К) состоит только из одноэлементных эл.кл., то есть таких эл.кл., которые задаются парой (х),а), где 7 £ (1,2
Пусть набор эл.кл. I! = аг)
корректным для класса К, К Е {К1