Содержание к диссертации
Введение
Глава 1. Обзор состояния проблемы исследования. Постановка задачи 12
1.1 Нечеткие системы 12
1.2 Идентификация нечетких систем 16
1.3 Критерии оптимизации нечетких систем 30
1.4 Постановка задачи 33
Выводы 36
Глава 2. Методика и алгоритмы построения Парето–оптимальных нечетких систем 37
2.1 Методика построения трехкритериальных Парето–оптимальных нечетких систем 37
2.1.1 Комплексный критерий интерпретируемости нечетких систем 38
2.1.2 Алгоритм усечения базы правил нечеткой системы 41
2.1.3 Алгоритм исключения терма из базы правил нечеткой системы 42
2.1.4 Алгоритм объединения термов 43
2.1.5 Алгоритм исключения пересечения наиболее лингвистически отдаленных термов 44
2.2 Гибридный численный метод структурной и параметрической оптимизации нечетких систем 45
2.2.1 Алгоритмы пчелиной колонии 45
2.2.2 Алгоритм адаптивной эволюционной стратегии 48
2.2.3. Гибридный численный метод идентификации структуры и параметров на основе островной модели 54
2.3 Алгоритм генерации нечетких классификаторов на основе экстремумов таблицы наблюдений 55
Выводы 57
Глава 3. Программный комплекс 57
3.1 Формализация предметной области 58
3.2 Проектирование программного комплекса 58
3.3 Выбор средств разработки 64
3.4 Описание и структура программного комплекса MixCore 65
3.5 Диспетчер параллельных вычислений 69
3.5.1 Схемы параллельного расчета ошибки нечеткой системы 70
3.5.2 Схемы параллельной реализации алгоритма пчелиной колонии для генерации правил нечеткой системы 74
3.5.3 Схемы параллельной реализации алгоритма пчелиной колонии для идентификации параметров нечеткой системы 81
3.5.4 Схемы параллельной реализации алгоритма адаптивной эволюционной стратегии для идентификации параметров нечеткой системы 83
3.5.5 Схемы параллельной реализации алгоритма, реализующего методику построения трехкритериальных Парето-оптимальных нечетких систем 85
3.5.6 Диспетчер многопоточных вычислений 87
3.6 Представление нечетких систем в стандарте PMML v4.2 87
3.6.1 Представление функций принадлежности в PMML 89
3.6.2 Представление нечетких правил в PMML 91
3.6.3 Представление нечетких систем в PMML 93
Выводы 95
Глава 4. Исследование методики, метода, алгоритма и программного комплекса 95
4.1 Апробация методики построения трехкритериальных Парето–оптимальных нечетких систем 97
4.1.1 Апробация методики при построении трехкритериальных Парето-оптимальных систем синглтон в задаче аппроксимации 97
4.1.2 Апробация методики при построении трехкритериальных Парето-оптимальных питтсбугских классификаторов 105
4.2 Исследование гибридного метода структурной и параметрической оптимизации нечетких систем 113
4.2.1 Исследование алгоритма пчелиной колонии для идентификации параметров нечеткой системы 113
4.2.2 Исследование алгоритма адаптивной эволюционной стратегии для идентификации параметров нечеткой системы 121
4.2.3 Исследование параметров гибридного метода структурной и параметрической оптимизации нечетких систем 127
4.3 Исследование алгоритма генерации нечетких классификаторов на основе экстремумов таблицы наблюдений 133
4.4 Исследование параллельной архитектуры разработанного программого комплекса 134
Выводы 139
Глава 5. Описание внедрения разработанных программных комплексов 140
5.1 Рекомендательная система для НИИКФ 140
5.1.1 Постановка задачи 140
5.1.2 Отбор информативных признаков 141
5.1.3 Рекомендательная система 144
5.2 Аутентификация пользователей по клавиатурному почерку 148
5.2.1 Задача повышения точности аутентификации 149
5.2.2 Программная реализация и оценка эффективности 150
Выводы 152
Заключение 153
Список сокращений и условных обозначений 155
Список литературы 157
- Идентификация нечетких систем
- Гибридный численный метод структурной и параметрической оптимизации нечетких систем
- Диспетчер параллельных вычислений
- Исследование алгоритма пчелиной колонии для идентификации параметров нечеткой системы
Введение к работе
Актуальность исследования. Нечеткие системы давно и успешно применяются в таких проблемных областях, как классификация, аппроксимация, интеллектуальный анализ данных, распознавание образов, прогнозирование и управление, в задачах принятия решений. Достоинствами нечетких систем являются невысокая стоимость разработки, гибкость, интуитивно понятная логика функционирования.
В последнее время нечеткие методы моделирования сконцентрированы на проблемах улучшения интерпретируемости нечетких систем без потери точности. Интерпретируемость является важным свойством модели, так как позволяет преобразовывать данные в знания. Поиск компромисса между точностью и интерпретируемостью является в настоящее время одним из наиболее актуальных направлений исследований в нечетком моделировании.
Основной вклад в исследование критериев интерпретируемости нечетких систем и методов ее достижения внесли R. Alcala, J.Alonso, J.M. Andjar, R. Cannone, G. Castellano, M. Gacto, A.M. Fanelli, Gan J.Q., G. Gonzalez–Rodriguez, S. Guillaume, F. Herrera, H. Ishibuchi, Y. Jin, H. Koivisto, L. Magdalena, Mencar C., D.D. Nauck, Y. Nojima, J. V. Oliveira, W. Pedrycz, P. Pulkkinen, S. Romero, O. Snchez, M.A. Vlez, H. Wang, T. Yamamoto, Y. Zhang, S. M. Zhou.
Целью диссертационной работы является разработка алгоритмов и программных средств идентификации Парето-оптимальных нечетких систем на основе метаэвристических методов для достижения компромисса между точностью, сложностью и интерпретируемостью нечетких систем.
Для достижения поставленной цели решены следующие основные задачи:
-
обзор существующих методик и методов построения многоцелевых Парето-оптимальных нечетких систем и критериев, используемых для оценки их интерпретируемости;
-
разработка методики построения многоцелевых Парето-оптимальных нечетких моделей на основе метаэвристических методов с применением оригинального комплексного критерия интерпретируемости нечетких систем;
-
разработка гибридного численного метода идентификации структуры и параметров нечеткой системы, основанного на группе алгоритмов пчелиной колонии и адаптивном алгоритме эволюционной стратегии;
-
разработка программных средств, реализующих предложенную методику и гибридный численный метод в многопоточном режиме, позволяющих экспортировать нечеткие системы в представление, совместимое с языком разметки прогнозного моделирования (PMML);
-
исследование разработанных алгоритмов, численных методов и предложенной методики на контрольных примерах в сравнении с аналогами.
Объектом исследований является процесс структурной и параметрической идентификации нечетких систем.
Предметом исследований являются гибридные алгоритмы и программы идентификации структуры и параметров Парето-оптимальных нечетких систем, а также критерий их интерпретируемости.
Методы исследования. В диссертационной работе применялись методы искусственного интеллекта, теории нечетких множеств, математической статистики, линейной алгебры, объектно-ориентированного и рефлексивно-ориентированного программирования.
Достоверность результатов обеспечивается строгостью применения математических методов, результатами проведенных численных экспериментов, которые сопоставимы с данными, полученными другими исследователями.
Научная новизна полученных результатов. В диссертации получены следующие новые научные результаты.
-
Разработана оригинальная трехкритериальная методика построения Парето-оптимальных нечетких моделей. Методика отличается от аналогов использованием элементарных гиперпараллепипедов задаваемых размеров, динамически изменяющихся во время работы по каждому из критериев, и использованием однокритериальных алгоритмов идентификации параметров и структуры нечеткой системы.
-
Впервые разработан гибридный численный метод идентификации структуры и параметров нечетких систем, основанный на группе алгоритмов пчелиной колонии и адаптивном алгоритме эволюционной стратегии с применением метода наименьших квадратов и схемы островов.
-
Разработан алгоритм генерации нечетких классификаторов на основе экстремумов таблицы наблюдений. Алгоритм отличается тем, что позволяет уменьшить количество правил нечеткого классификатора не менее чем в 2 раза по сравнению с методами равномерного разбиения при сравнимой точности и повысить точность классификации более чем на 10% по сравнению с методами, основанными на нечетких осредних, при сохранении сопоставимого количества правил.
Теоретическая значимость работы заключается в развитии технологии построения Парето-оптимальных нечетких моделей при апостериорном подходе. Разработанный гибридный метод может использоваться не только для идентификации параметров нечетких систем, но и как метод глобальной параметрической оптимизации.
Практическая значимость работы подтверждается использованием полученных в ней результатов для решения практических задач:
создание рекомендательной системы немедикаментозного восстановительного лечения участников вооруженных конфликтов и чрезвычайных ситуаций при назначении комплексов реабилитации пациентам с посттравматическими стрессовыми расстройствами, внедренной в НИИ курортологии и физиотерапии ФМБА России (НИИ КиФ);
разработка программного модуля, служащего для повышения качества распознавания клавиатурного почерка при двухфакторной аутентификации для предоставления доступа по протоколу RDP, внедренного в ОАО «Особая экономическая зона технико-внедренческого типа г. Томск» (ОАО ОЭЗ ТВТ).
Разработанные алгоритмы и программные средства использованы при выполнении следующих проектов:
грант РФФИ 09-07-99008 «Исследование и разработка технологии идентификации нечетких моделей на базе метаэвристик и методов, основанных на производных» 2009-2010г.;
грант РФФИ 12-07-00055 «Методы построения Парето-оптимальных нечетких систем на основе гибридного подхода» 2012-2014г.;
грант РГНФ 12-06-12008 «Программный комплекс для прогнозирования эффективности реабилитации лиц опасных профессий с наиболее распространенными социально значимыми неинфекционными заболеваниями» 2012-2013г.;
проект УМНИК 2014 «Разработка облачного менеджера паролей с двухфакторной аутентификацией на основе клавиатурного почерка».
На защиту выносятся приведенные ниже положения.
1. Трехкритериальная методика построения Парето-оптимальных нечет
ких моделей позволяет достичь равномерного распределения решений вдоль Па-
рето-фронта по каждому из трех критериев: интерпретируемость, сложность и
точность нечеткой системы. Кроме того, данная методика позволяет использо
вать однокритериальные алгоритмы идентификации параметров и структуры не
четкой системы без изменения самой методики и алгоритмов, а также позволяет
регулировать соотношение скорости поиска и дистанции приближения к гипоте
тическому (идеальному) Парето-фронту по каждому критерию.
Соответствует пункту 1 паспорта специальности: Разработка новых математических методов моделирования объектов и явлений.
2. Численный метод идентификации структуры и параметров нечеткой си
стемы, основанный на группе алгоритмов пчелиной колонии и адаптивном алго
ритме эволюционной стратегии с применением метода наименьших квадратов и
схемы островов, позволяет повысить точность вывода нечеткой системы не ме
нее чем в 1,36 раза на обучающих выборках по сравнению с численными мето
дами, применяемыми другими исследователями в аналогичных задачах.
Соответствует пункту 3 паспорта специальности: Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий.
3. Алгоритм генерации нечетких классификаторов на основе экстремумов
таблицы наблюдений.
Соответствует пункту 3 паспорта специальности: Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий.
4. Многопоточная архитектура программного комплекса для построения
Парето-оптимальных нечетких систем реализует предложенные алгоритмы и ме
тодику, использует оригинальное расширение формата PMML для экспорта-им
порта нечетких систем с глобально определенными термами.
Соответствует пункту 4 паспорта специальности: Реализация эффек-тивных численных методов и алгоритмов в виде комплексов проблемно-ориен-
тированных программ для проведения вычислительного эксперимента.
Внедрение результатов диссертационного исследования. Результаты исследовательской работы вошли в качестве программных компонентов в рекомендательную систему для немедикаментозного восстановительного лечения участников вооруженных конфликтов и чрезвычайных ситуаций при назначении комплексов реабилитации пациентам с посттравматическими стрессовыми расстройствами, используемую в НИР НИИ КиФ.
Результаты работы вошли в качестве программных компонентов в разработанный программный комплекс, предназначенный для повышения защищенности доступа по RDP с помощью внедрения дополнительного фактора аутентификации по клавиатурному почерку со сниженными по сравнению с аналогами ошибками первого и второго рода, используемый в ОАО ОЭЗ ТВТ.
Разработанные алгоритмы идентификации нечетких систем используются при изучении дисциплины «Базы данных и экспертные системы», а также в рамках группового проектного обучения на кафедре комплексной информационной безопасности электронно-вычислительных систем ТУСУР.
Апробация работы. Основные положения работы докладывались и обсуждались на следующих конференциях, семинарах, выставках: Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых «Научная сессия ТУСУР», г. Томск, 2009-2014 г.; Всероссийской конференции «Проведение научных исследований в области обработки, хранения, передачи и защиты информации», г. Ульяновск, 2009 г.; Международной научной конференции «Системный анализ в медицине» (CАМ 2011), г. Благовещенск, 2011 г.; Всероссийской конференции с международным участием “Знания – Онтологии – Теории” (ЗОНТ-2011), г. Новосибирск, 2011 г.; Международной заочной научно-практической конференции «Наука, образование, общество: тенденция и перспективы», г. Москва, 2013 г.; VII-ой Международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте», г. Коломна, 2013 г.; Всероссийской конференции с международным участием «Современные системы искусственного интеллекта и их приложения в науке», г. Казань, 2013 г.; Международной научно-практической конференции «Электронные средства и системы управления», г. Томск, 2013 г.; XII Всероссийском совещании по проблемам управления Россия, г. Москва, ИПУ РАН, 2014 г.; Открытой выставке научных достижений молодых ученых РОСТ UP-2013, г. Томск, 2013 г.; Всероссийском конкурсе-конференции по информационной безопасности SIBINFO 2014, г. Томск; Томском IEEE семинаре «Интеллектуальные системы моделирования, проектирования и управления» г. Томск, 2012-2014 г.
Публикации по теме диссертации. По результатам исследований опубликованы 24 печатные работы, из которых в рекомендованных ВАК РФ периодических изданиях – 7. Были получены 3 свидетельства о государственной регистрации программ для ЭВМ (номера свидетельств: №2013610783, № 2014610816, № 2014610817).
Личный вклад автора. Постановка цели научного исследования и подготовка материалов к печати велась совместно с научным руководителем. Основ-
ные научные результаты получены лично автором. Автором самостоятельно разработан численный метод, предложенные алгоритмы, оригинальная методика и оригинальная архитектура для программного комплекса построения Парето-оп-тимальных нечетких систем.
Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы из 140 наименований и шести приложений. Основная часть работы содержит 167 страниц, в том числе 75 рисунков и 31 таблицу.
Идентификация нечетких систем
Достоинством строгого нечеткого разделения является меньшая размерность входного вектора при его представлении в алгоритмах идентификации.
Идентификация параметров нечеткой системы может быть как однокритериальной, тогда рассматривают критерий точности вывода нечеткой системы, или многокритериальной, когда кроме точности рассматривают критерии сложности и/или интерпретируемости. Рассмотрим каждый из подходов идентификации параметров отдельно.
Одномерную идентификацию параметров нечеткой системы выполняют, используя методы нелинейной оптимизации, адаптированные к особенностям нечеткой системы. Методы бывают основанными на производных и метаэврическими.
Наиболее популярными методами и алгоритмами, основанными на производных, являются метод наименьших квадратов [40, 75, 124], Левенберга–Марквардта, фильтр Калмана [35, 57, 104, 117], градиентный метод [56, 81]. Основные проблемы при их применении – это высокие временные затраты, застрявание в локальных минимумах и резкое увеличение трудоемкости при увеличении числа входных переменных, называемое «проклятием размерности». Однако их использование позволяет добиться высокой скорости сходимости к экстремуму (локальному или глобальному) на одну итерацию. Кроме того, эти методы часто используют матричные вычисления, которые вводят дополнительные ограничения при реализации на вычислительных системах именно в задаче оптимизации параметров нечетких систем. Возникают эти ограничения при перемножении десятков–сотен значений меньших единицы, например, в задаче определения детерминанта матрицы, так как именно такими являются степени принадлежности значений входных переменных термам. Использование сингулярного разложения матриц или других методов позволяет снять эти ограничения, но лишает уверенности, что результаты такой оптимизации не ухудшат текущий результат.
Метаэвристические методы являются субоптимальными итеративными методами, основанными на простых правилах - эвристиках. Их использование позволяет устранить часть недостатков методов нелинейной оптимизации, основанных на производных.
На современном этапе метаэвристические методы можно разделить на два больших подтипа. Это методы, основанные на генетических, эволюционных алгоритмах и эволюционном программирования и методах роящегося интеллекта. Первый подтип является имитацией процесса эволюции и оценки приспособленности особей, второй подход основан на поведении стай животных при решении повседневных задач.
Генетические методы и алгоритм эволюционной стратегии возникли независимо друг от друга, они характеризуются рядом важных общих свойств. Для любого из них формируется исходная популяция особей, которая в последующем подвергается селекции и воздействию различных генетических операторов (чаще всего скрещиванию и/или мутации), что позволяет находить более хорошие решения [1, 34, 54, 82].
Существует особая категория, эволюционных методов - это методы с адаптацией параметров и статистическими операторами, такими как матрица ковариации, позволяющими добиться большей скорости сходимости, если гипотеза наличия взаимосвязей среди входных данных верна. Одним из наиболее ярких представителей этой группы алгоритмов является адаптивная эволюционная стратегия с матрицей ковариации. В отличие от классического генетического алгоритма в этом алгоритме используются два понятия фенотип и генотип. Параметры нечеткой системы представлены в виде хромосомы и существуют только на уровне генотипа, фенотип включает в себя генотип и характеристики алгоритма эволюционной стратегии такие как шаг мутации и угол ротации. Шаг мутации - это адаптивный коэффициент, изменяемый самим алгоритмом от итерации к итерации. Эти параметры характеризуют величину шага оптимизации для каждой входной переменной отдельно. Угол ротации исследует взаимосвязи между входными переменными на основе матрицы ковариации и рассчитывается после каждой итерации. Применение угла ротации позволяет избежать большинства промахов, связанных со слишком большим шагом мутации для группы входных переменных [73, 93, 105]
Использование этого алгоритма из-за сложной комбинации эвристик вычислительно затратнее аналогов, но позволяет добиться более устойчивых результатов и во многих случаях более точного вывода по сравнению как с генетическим алгоритмом, так и с классическим алгоритмом эволюционной стратегии.
Следующий подтип – алгоритмы, основанные на поведении роевого интеллекта. Алгоритмы муравьиной колонии [69, 70]– алгоритмы, изначально созданные для решения комбинаторных задач в дискретном пространстве, являются алгоритмами ограниченного перебора, впоследствии перенесенные на оптимизацию в непрерывном пространстве вводя отдельных ответственных муравьев на каждом признаке в алгоритме CACO [51] или используя гауссово ядро DACO [119]. В основе большинства алгоритмов данной группы лежит коммуникация муравьев с помощью ферамона, концентрация ферамона пропорциональна качеству решения [132].
Алгоритмы роящихся частиц [96]– это алгоритмы основанные, на обобщенной концепции поведения косяков рыб или стай птиц. Эти алгоритмы реализуют стохастический метод поиска, основанный на итеративном взаимодействии частиц, образующих рой. Перемещение частицы в пространстве поиска определяют три фактора: инерция, память, сотрудничество. Инерция подразумевает, что частица не может мгновенно изменить свое направление движения. Каждая частица имеет память и хранит свою лучшую позицию в пространстве поиска и позицию лучшей частицы в рое. Зная эти две позиции, частица динамически изменяет скорость согласно ее собственному опыту и опыту полета других частиц. Таким образом, движение каждой частицы задается ее лучшей позицией, ее текущей скоростью, ускорением, заданным предыдущей позицией, и ускорением, заданным лучшей частицей в рое. Существуют модификаций, детерминирующие или перерассчитывающие значение каждого из коэффициентов инерции, доверия своему лучшему решению (память), и коэффициента сотрудничества[96]. Если проводить аналогии с генетическими алгоритмами, то присутствует мутация в виде поиска прототипа в пространстве и элитарная селекция. Однако роль лучшей не так однозначна, как в эволюционных подходах, изменяя коэффициент доверия ее решению, можно выбирать между лучшим исследованием всего пространства поиска и эффективностью поиска точного значения локального экстремума на текущей итерации [132].
Алгоритмы пчелиной колонии [53, 94, 110, 122] – это группа алгоритмов оптимизации, использующая разное поведение пчел. Оптимизация выполняется различным образом для каждого вида пчел. Разведчики осуществляют глобальный поиск, рабочие пчелы оптимизируют лучшие решения на данной итерации, используя локальный поиск, и наблюдатели которые, оптимизируют лучшие решения за всю историю имитации. Если проводить параллели между этими и популяционными алгоритмами, то в пчелинных алгоритмах нет аналога кроссовера, для каждого вида пчел своя мутация и общий для всех пчел вероятностный процесс отбора решения [132].
Гибридный численный метод структурной и параметрической оптимизации нечетких систем
Ниже приведено описание каждого из представленных компонентов. Fuzzy_Abstract – набор абстрактных классов, определяющий систему вывода (Fuzzy_System), базу правил (Knowledge_base_Rules), правила (Rule) и множество термов (Term), а так же файлы-хранилища настроек алгоритма генерации правил и алгоритма оптимизации базы правил (Fuzzy_Abstract.conf).
Approx_Singletone представляет собой нечеткую систему типа синглтон. В нем определены интерфейсы алгоритмов инициализации правил (Approx_Singletone.init), алгоритмов генерации правил (Approx_Singletone.add_generators), а также алгоритмы параметрической оптимизации (Approx_Singletone.learn_algorithm); для хранения и передачи реализуется представление нечеткой системы в виде UFS.
PittsburghClassifierHybride_FrontEnd, соответственно. Эти интерфейсы позволяют нечетким системам взаимодействовать с графическим интерфейсом пользователя компонентом Mix_Core. Mix_Core позволяет получать алгоритмы добавления правил, структурной и параметрической инициализации из интерфейса пользователя, запускать и отслеживать процесс оптимизации.
FrontEnd_Construction – класс, который позволяет интерфейсу Mix_Core заранее определять реализованные типы нечетких систем и строить объекты, реализующие интерфейс Fuzzy_FrontEnd.
Member_Function – класс, позволяющий определить количество параметров каждой функции принадлежности, вычислить функцию принадлежности для конкретного терма в точке и получить название функции принадлежности.
Type_Term_Func_Enum содержит виды функций принадлежности, поддерживающихся текущей версией системы.
На рисунке 3.6 представлена диаграмма классов интерфейса пользователя Mix_Core. class Mix_Сore add_algorithm_B_list :List Button = new List Button () add_algorithm_CB_list :List ComboBox = new List ComboBox () all_algorithms_B_List :List Button = new List Button () all_algorithms_CB_List :List ComboBox = new List ComboBox () count_interation_complete :string current_section :int = 0
Program – основной класс взаимодействия с пользователем, отвечает за загрузку форм и блокировку парковки дисков и уход в спящий режим компьютера, пока происходит процесс обучения.
Forms:Start_F – главная форма, позволяет выбрать тип нечеткой системы, запрашивает через интерфейсы IFuzzy_FrontEnd доступные алгоритмы инициализации, обучения и их конфигурационные файлы для создания объектов Forms:universal_conf_form для конкретного алгоритма.
Forms:Result_F – форма для вывода результатов после выполнения всей заданной пользователем цепочки алгоритмов инициализации и обучения. Forms:universal_conf_form – форма для настройки параметров алгоритмов обучения, привязывается к объектам-наследникам классов Fuzzy_Abstract.conf, Approx_Singletone.init.conf, Approx_Singletone.add_generators, Approx_Singletone.learn_algorithm, публичные свойства которых доступны для задания пользователем.
Fuzzy_FrontEnd::Methods_init_loader – класс, позволяющий загружать дополнительные библиотеки ( .dll) алгоритмов, внешние к системе.
В настоящее время существуют архитектуры центрального процессора, которые снижают объем ручного распараллеливания программистом, например, VLIM [97], но для привычной архитектуры IBM PC требуется определение мест распараллеливания кода и исследования эффективности параллелизации. Поскольку готовые методики построения вариантов параллельной реализации, учитывающих особенности различных семейств современных процессоров x86, недостаточно проработаны, а производители процессоров говорят только о рекомендациях, которые для реальных приложений часто противоречивы, разработчику приходится производить поиск эффективных реализаций самому. В научных исследованиях известны пределы ускорения, благодаря таким законам как закон Амдала [48] и закон Гуфставсона [85]. Эти законы оперируют понятием доля последовательно выполняемого кода, она просто рассчитывается на ассемблере, но для высокоуровневых языков таких как C# не применима, ввиду сокрытия кода библиотек от разработчика, это приводит к трудоемкой оценке реальной доли последовательного и параллельного кода.
С другой стороны, научные исследования для конкретных алгоритмов обучения и видов нечетких систем являются перспективными и востребованными, что подтверджается публикацией научных статей по данной тематике, для напримера [2,3, 44, 95]
Поэтому были построены варианты реализации параллельных вычислений, проведена оценка их эффективности (подробнее в главе 4) и составлен управляющий модуль, переключающий варианты исполнения в зависимости от семейства процессора, автоматически проводящий тесты для ранее нетестированных процессоров. Именно этот модуль является главной архитектурной особенностью данного программного комплекса с точки зрения повышения производительности.
Распараллеливание программного обеспечения включает в себя поиск участков программного комплекса, которые можно было бы свести к одному из следующих шаблонов, предложенных Флинном (M. J. Flynn).
SIMD (Single Instruction-Multiple Data) - одинаковые преобразования выполняются на множестве несвязанных данных. Данный шаблон достаточно легко поддается параллельной реализации и в общем случае показывает наибольшую эффективность от параллельного исполнения.
MIMD (Multiple Instructions -Multiple Data) - различные данные подвергаются различным преобразованиям, наиболее обобщённый шаблон. При реализации требуется постоянный контроль наличия средств синхронизации, так как различные инструкции выполняются за разное время. Эффективность параллельного выполнения такого шаблона ниже, но именно этот шаблон рекомендуется использовать при медленной сети между вычислительными ресурсами.
MISD (Multiple Instructions -Single Data) - одни и те же данные подвергаются различным преобразованиям. Очень редко встречается в практике, наиболее эффективен при реализации на устройствах, сильно отличающихся по производительности, например, CPU - GPU. [29]
После нахождения шаблона в части алгоритма стоит проверить обязательное условие Бернстайна, смысл которого в том, что выходы и входы частей алгоритма, подлежащие распараллеливанию не пересекаются и выходы одной части не должны быть входом другой [126].
Диспетчер параллельных вычислений
Для методов кластеризации число кластеров менялось от количества классов до утроенного количества классов для каждого сочетания обучающей и тестовой выборки, а затем отбирались лучшие по точности результаты, именно поэтому в таблице 4.17 дробные значения количества правил и термов. Алгоритм равномерного нечеткого разделения использовался в таких сочетаниях разбиения, пока число генерируемых правил не превысило количества образцов в выборке.
По таблице 4.17 видно, что базы правил, получаемые алгоритмом при том же количестве правил, точнее по проценту классификации в сравнении с аналогами. Алгоритм равномерной инициализации дает сравнимые и превосходящие результаты по точности классификации на данных Iris, но различаются эти решения более чем на 100 правил.
Исследование параллельной архитектуры разработанного программого комплекса Результаты исследования представлены в таком же виде и последовательности, как выполняет диспетчер многопоточных вычислений, указанный в разделе 3.5.6, а соотвествующие схемы параллельного выполнения представлены в разделах 3.5.1-3.5.5.
Введем метрику оценки качества параллельной реализации алгоритма. Коэффициент Эксперименты проводились на трех процессорах с разным количествам ядер и разной архитектурой. Тестовый стенд №1: Процессор Intel І5-2410M (2.3 ГГц), вычислительных ядер два, вычислительных потоков 4, ОЗУ DDR3 8 ГБ частота 667 МГЦ, чипсет Sandy Bridge НМ65. Тестовый стенд №2: Процессор Intel І7-3770К (3.5 ГГц), вычислительных ядер четыре, вычислительных потоков восемь, ОЗУ DDR3 8 ГБ частота 667 МГЦ , чипсет Ivy Bridge Z77, Тестовый стенд №3: Процессор AMD Opteon 6272 (2.1 Ггц), доступно вычислительных ядер восемь (из шестнадцати), доступно вычислительных потоков восемь, ОЗУ DDR3 8 ГБ частота 667 МГЦ , чипсет G34.
Схема экспериментов построена на модели с выбыванием. То есть сначала проводится тест на алгоритме расчета ошибки, выбирается лучшая схема параллельного выполнения для каждого процессора, потом на каждом из алгоритмов идентификации структуры и параметров, выбирается лучшая схема параллельного выполнения, а затем проводится тест совместного использования лучших схем параллелизации для каждого алгоритма, с вариантами, когда какие-то из алгоритмов выполняются последовательно. Все тесты выполнялись 10 раз для нивелирования влияния фоновых процессов[25].
Из таблицы 4.21 видно, что лучшим вариантом параллельного выполнения для стендов №1 и №2 на процессорах Intel оказался PBS4, который распараллеливает выполнение полета рабочих пчел по пчелам и по правилам. А для стенда №3 лучшим оказался вариант PBS5 в котором распараллелино максимальное количество циклов. Также заметим, что для стенда №3 вариант PBS3 с внешним распараллеливанием рабочих пчел, оказался лучше, чем вариант PBS4, где это распараллеливание выполнено для внешнего и внутреннего цикла рабочих пчел.
Перейдем к оценке скорости оптимизации правил алгоритмом пчелиной колонии для идентификации параметров нечеткой системы. Эксперимент состоит в выполнении 100 итераций для базы правил из 256 правил на данных Ele-2 при последовательном вычислении ошибки вывода синглтона. Таблица 4.22 Сравнение временных затрат на оптимизацию правил 100 итерациями алгоритма пчелиной колонии для идентификации параметров
Из таблицы 4.23 видно, что лучшим вариантом параллельного выполнения на всех тестовых стендах, является схема параллельного выполнения PES1, то есть параллельное выполнение итеративного процесса эволюции, а допольнительное распареллеливание примененное в PES2 не окупает затрат на создание потоков, так как выполняется один раз.
Перейдем к оценке скорости выполнения 100 итераций алгоритма, реализующего методику построения трехкритериальных Парето-оптимальных нечетких систем на данных Ele-2 при варьируемом способе вычисления ошибки, и схеме параллельного выполнения каждого из алгоритмов структурной и параметрической оптимизации и вычисления ошибки. В виду того, что выполнение методики затратно по времени, эксперимент проводился по следующей схеме. Все алгоритмы выполняются последовательно, включая распараллеливание для самого времязатратного алгоритма. При уменьшении времени выполнения, делалась попытка распараллеливания для следующего по временным затратам алгоритма, и так пока время выполнения не начинает увеличиваться. Отдельно проверялся вариант, когда распараллелено вычисление ошибки вывода, а когда нет.
Из таблицы 4.24 видно, что лучшим вариантом параллельного выполнения для стендов №1 и №2 на процессорах Intel оказался вариант PF2+PBS0+PBP1+PES0, который распараллеливает выполнения алгоритма пчелиной колонии для идентификации параметров и распараллеливает вычисление ошибки вывода нечеткой системы. А для стенда №3 лучшим оказался вариант PF2+PBS0+PBP0+PES0 в котором параллельно выполняется только вычисление ошибки.
Эксперименты показали, что во многих случаях тестовые стенды одинаково положительно реагируют на одинаковые схемы паралелльного выполнения, но в двух случаях эффективность выполнения на стенде №3 отличается, ввиду отличия в процессоре количества ядер, архитектуры ядер и серверному назначению, которое отражается в дополнительной оптимизации микрокода предсказателя ветвлений.
Исследование показало, что применяя лучшие схемы параллельного исполнения, возможно уменьшить время выполнения алгоритмов идентификации параметров с 1,27 раз до 3,93 раз в зависимости от алгоритма и типа процессора, а временные затраты на алгоритм, реализующий методику построения трехкритериальных Парето-оптимальных нечетких систем, снизить с 1,67 раза до 4,05 раза.
В ходе исследования была показана актуальность диспетчера многопоточных вычислений способного настроить программный комплекс под производительность данного тестового стенда.
Исследование алгоритма пчелиной колонии для идентификации параметров нечеткой системы
Задача повышения точности аутентификации по клавиатурному почерку может быть сведена к задаче повышения точности классификации. В общем случае для каждого человека может быть построено от одного до трех шаблонов его клавиатурного почерка с целью минимизации ошибки классификации. Существуют два различных подхода к формированию шаблона клавиатурного почерка: анализ набора текстов и анализ набора ключевой фразы (от 9 до 30 символов). Основным недостатком первого подхода является длительная процедура обучения. Кроме того, если процедура аутентификации будет сопровождаться набором большого текста, не исключена возможность отвлечения и, соответственно, изменения проверяемых характеристик. Из многих способов сформировать шаблон клавиатурного почерка применен метод аутентификации на основе клавиатурного почерка по контрольной фразе. Несмотря на устойчивость клавиатурного почерка, он все же колеблется из–за состояния человека. При анализе клавиатурного почерка производят разделение на утро, день и вечер [30]. Сложно составить четкие границы каждого из понятий утро, день, вечер в данной задаче, так как в современном обществе используются различные графики работы, в том числе гибкие. В общем случае следует рассматривать понятия: до работы, во время работы, после работы. При этом необходимо учесть, что не у всех людей требуется различать все три состояния. Стоит учесть особенность задачи аутентификации, в которой множество классов состоит из зарегистрированных пользователей и идентификатора указывающего на неизвестного пользователя, которые могут попытаться пройти процедуру аутентификации. Далее будут представлены необходимые изменения в базе правил нечеткого питтсбурского классификатора, затем параметры и особенности применения гибридного метода идентификации структуры и параметров нечеткой системы на основе островной модели.
Модификация нечеткого питтсбургского классификатора. Питтсбугский классификатор работает на основе правил вида (1.2).
При данной структуре сформировать правило для идентификатора класса, указывающего на неизвестного пользователя, весьма затруднительно, поэтому предлагается переход к базе правил следующего вида: где сz– идентификатор класса незарегистрированных пользователей. Так же стоит учесть, что такое изменение правил снимает с нечеткого питтсбурского классификатора необходимость покрытия всей области определения каждой входной переменной термами, в данном случае ситуация неопределённости не возникает.
Программная реализация и оценка эффективности Используются следующие алгоритмы: АПКГП, модифицированный алгоритм пчелиной колонии для настройки весов (МАПКНВ)[43], ААЭС. Диаграмма деятельности использования алгоритмов при построении правил проверки для нового зарегистрированного пользователя, прошедшего семидневный процесс сбора данных, представлена на рисунке 5.7.
Было проведено два эксперимента, в которых проверялась точность классификации и расчет ошибки первого рода (отказ в доступе зарегистрированному пользователю, указавшему правильный логин и пароль) и ошибки второго рода (предоставление доступа пользователю, указавшему чужой логин и пароль).
Первый эксперимент проводился через неделю после начала использования программы в режиме обучения. В эксперименте участвовало 10 программистов, клавиатурный почерк у которых более усточивый на английском языке, поэтому для всех была установлена ключевая фраза “AstalaVista Password”. В процессе обучения в качестве входной выборки использовались варианты набора всех участников эксперимента. Эксперимент проводился по схеме кросс– валидации в соотношении 80:20%. Усредненные результаты представлены в таблице 5.6.
После этого эксперимент продолжался в режиме адаптации. Процесс адаптации длился месяц. При каждой адаптации использовались варианты набора пользователя за последние 14 дней. Усредненные ошибки первого и второго рода после месяца адаптации, представлены в таблице 5.7.
1. Предложена методика для построения Парето-оптимальных нечетких моделей по трем критериям. Данная методика позволяет получать нечеткие модели с различным количеством правил, термов и расположением термов. Методика использует элементарные гиперпараллелипиды с динамически изменяемыми размерами, что позволяет добиться равномерного распределения получаемых решений по каждому из критериев. Методика предусматривает возможность дополнения новыми методами идентификации нечетких систем. Использование методики позволяет эксперту выбрать подходящую нечеткую модель среди расположенных на Парето-фронте.
2. Предложен оригинальный комплексный критерий, учитывающий геометрическую и семантическую интерпретируемость нечетких систем.
3. Предложен гибридный численный метод, основанный на схеме островов. Метод имеет следующие преимущества: а) гибкость и устойчивость к «застреванию» в локальных экстремумах, полученные за счет применения метода пчелиной колонии; б) скорость сходимости, присущую алгоритму эволюционной стратегии с адаптацией параметров на основе матрицы ковариации; в) точность, определяемую методом наименьших квадратов.
4. Предложен алгоритм генерации нечетких классификаторов на основе экстремумов таблицы наблюдений, позволяющий генерировать более точные нечеткие классификаторы, чем часто применяемые методы на основе кластеризации с-средних и его модификаций Gustafson-Kessel, Gath-Geva, при сравнимом или меньшем количестве правил. Предложенный алгоритм позволяет получить классификаторы, сравнимой точности с методом равномерного разбиения, при меньшем количестве правил.
5. Разработан программный комплекс с оригинальной многопоточной архитектурой, основанной на диспетчеризации параллельных вычислений, позволяющей добиться минимизации времени генерации и оптимизации нечетких систем. Архитектура является расширяемой за счет возможности подключения дополнительных алгоритмов идентификации структуры и параметров.
6. Предложено описание нечетких систем типа синглтон и питтсбургских классификаторов, совместимое со стандартом PMML 4.2.
7. Внедренная рекомендательная система и результаты проведенного исследования с применением разработанных алгоритмов используются при выполнении НИР «Немедикаментозное восстановительное лечение участников вооруженных конфликтов и чрезвычайных ситуаций» и для назначения комплексов реабилитации пациентам с посттравматическими стрессовыми расстройствами в НИИ КиФ.
8. Проведены исследования эффективности предложенных алгоритмов в задаче распознавания клавиатурного почерка. Осуществлено внедрение в ОАО ОЭЗ ТВТ.
Похожие диссертации на Алгоритмы и программные средства идентификации Парето–оптимальных нечетких систем на основе метаэвристических методов
