На правах рукописи

Синьков Дмитрий Сергеевич

АЛГОРИТМЫ И ПРОГРАММНЫЕ СРЕДСТВА ИДЕНТИФИКАЦИИ

НЕЧЕТКИХ СИСТЕМ НА ОСНОВЕ МЕТОДА РОЯЩИХСЯ ЧАСТИЦ

Специальность 05.13.18 – Математическое моделирование, численные методы

и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Томск–2013 2

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

(ТУСУР)

Научный руководитель – доктор технических наук, профессор Ходашинский Илья Александрович

Официальные оппоненты: Тимченко Сергей Викторович, доктор физико-математических наук, Национальный исследовательский Томский государственный университет, профессор кафедры математической физики Аксенов Сергей Владимирович, кандидат технических наук, Национальный исследовательский Томский политехнический университет, доцент кафедры оптимизации систем управления

Ведущая организация – Национальный исследовательский Иркутский государственный технический университет

Защита состоится 19 декабря 2013 г. в 15 час. 15 мин. на заседании диссертационного совета Д 212.268.02 при ТУСУРе по адресу:

634050, г. Томск, пр. Ленина, 40.

С диссертацией можно ознакомиться в научной библиотеке ТУСУРа по адресу:

г. Томск, ул. Вершинина, 74.

Автореферат разослан 19 ноября 2013 г.

Ученый секретарь диссертационного совета Р.В. Мещеряков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Для оптимизации параметров НС в работе выбран активно исследуемый в последнее время метод роящихся частиц, так как он в классическом варианте описывается простыми математическими формулами и легко поддается гибридизации с другими алгоритмами и методами. Выбор метода роящихся частиц основан еще и на том, что данный метод относится к классу метаэвристик, хорошо себя зарекомендовавших в задачах многомерной оптимизации, к которым в частности и относится задача поиска оптимальных параметров НС. Построение алгоритмов на основе имитации поведения роя частиц основывалось на трудах Kennedy, J.; Eberhart, R.; Zhang, J.; Li; Chung; Z.

Ruiyou, W. Dingwei, Y. G. Petalas, V. Kalivarapu, S. B. Akat, V. Gazi, I. Scriven, W. Bo, Q. Liguo, T. Desell, K. T. Chaturvedi, P. Boonyaritdachochai, A. Chatterjee, P. Siarry, L. Yufeng, S. Xianjun, P. K. Tripathi, F. Shahzad, M. Ben Ghalia.

Основополагающие результаты в области нечеткого моделирования получили А.Н. Аверкин, И.З. Батыршин, Л.С. Берштейн, Ю.Н. Золотухин, С.М.

Ковалев, Л.Г. Комарцова, Ю.И. Кудинов, А.О. Недосекин, Ф.Ф. Пащенко, Пытьев Ю.П., В.Б.Тарасов, А.В. Язенин, Н.Г., Ярушкина, P. Angelov, R.

Babuska, A. Bastian, J.C. Bezdek, J. Casillas, J.L. Castro, O. Cordon, D. Dubois, D.

Filev, J. Gonzlez, S. Guillaume, F.Herrera, H. Ishibuchi, U. Kaymak, B. Kosko, R.

Krishnapuram, R. Kruse, E.H. Mamdani, J. M. Mendel, S. Oh, W. Pedrycz, H. Prade, M. Sugeno, T.Takagi, H. Tanaka, I. B. Turksen, R.R. Yager, T.Yasukawa, L.X.Wang, L.Zadeh.

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

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

1. Обзор и анализ существующих решений в области идентификации НС на основе алгоритмов роящихся частиц и метода наименьших квадратов.

2. Разработка методики построения Парето–оптимальных НС, учитывающей компромисс между сложностью и точностью.

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

4. Разработка унифицированного представления нечетких аппроксиматоров и нечетких классификаторов для решения задач имитационного моделирования.

5. Проведение исследований разработанных алгоритмов на типовых контрольных примерах.

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

7. Проектирование и разработка web-ориентированных программных комплексов построения и оптимизации НС и извлечения знаний на основе созданных алгоритмов и реализующих методику двухкритериальной настройки НС.

Объектом исследований является процесс идентификации НС и процесс извлечения знаний.

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

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

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

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

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

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

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

Разработанные алгоритмы и программные средства использованы при выполнении проектов:

грант РФФИ 06-08-00248 «Основанное на данных нечеткое моделирование технических систем» 2006 -2007 г.;

грант РФФИ 09-07-99008 «Исследование и разработка технологии идентификации нечетких моделей на базе метаэвристик и методов, основанных на производных» 2009-2010г.;

грант РФФИ 12-07-00055 «Методы построения Парето–оптимальных нечетких систем на основе гибридного подхода» 2012-2014г.;

грант РГНФ 12-06-12008 «Программный комплекс для прогнозирования эффективности реабилитации лиц опасных профессий с наиболее распространенными социально значимыми неинфекционными заболеваниями» 2012-2014г.;

проект УМНИК-2012 «Разработка облачного сервиса продвижения товаров и услуг на основе адаптивного алгоритма роящихся частиц».

На защиту выносятся:

1. Новая методика двухкритериального анализа данных, основанная на построении НС, включает два основных этапа:

генерацию структуры НС, основанную на алгоритме генерации базы правил НС равномерным разбиением и перебором;

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

Соответствует пункту 1 паспорта специальности: Разработка новых математических методов моделирования объектов и явлений.

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

Соответствует пункту 3 паспорта специальности: Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий.

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

Соответствует пункту 4 паспорта специальности: Реализация эффективных численных методов и алгоритмов в виде комплексов проблемноориентированных программ для проведения вычислительного эксперимента Достоверность полученных результатов обеспечена строгостью применения математических методов, результатами проведенных численных экспериментов, которые сопоставлены с данными, полученными другими авторами.

Внедрение результатов диссертационного исследования.

Разработанный программный комплекс используются при выполнении НИР Научно-исследовательского института курортологии и физиотерапии ФМБА Российской Федерации «Немедикаментозное восстановительное лечение участников вооруженных конфликтов и чрезвычайных ситуаций» для назначения комплексов реабилитации пациентам с посттравматическими стрессовыми расстройствами.

Результаты используются при выполнении курсовых, дипломных и научно-исследовательских работ студентами кафедры комплексной информационной безопасности электронно-вычислительных систем Томского государственного университета систем управления и радиоэлектроники (КИБЭВС ТУСУР).

Разработанные программные комплексы используются для извлечения знаний из истории о продажах в томском ресторане доставки «Хочу суши» (ИП Муравский Е.В. ОГРНИП 311702423700051).

Апробация работы. Основные положения работы докладывались и обсуждались на: Всероссийской конференции с элементами научной школы для молодежи «Проведение научных исследований в области обработки, хранения, передачи и защиты информации» 2009г.; VII Всероссийской научнопрактической конференции студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования» 2010г., г.

Томск; Международной научной конференции (заочной) «Системный анализ в медицине» (CАМ 2011) 25-26 мая 2011г., г. Благовещенск; Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых «Научная сессия ТУСУР» г. Томск, 2008, 2009, 2010, 2011, 2012, 2013гг;

Томском IEEE семинаре «Интеллектуальные системы моделирования, проектирования и управления» г. Томск, 2012, 2013гг; VII-ой Международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте» 20-22 мая 2013г., Коломна;

Публикации по теме диссертации. По результатам исследований опубликовано 17 печатных работ, из которых в рекомендованных ВАК РФ периодических изданиях – 4. Были получены 2 свидетельства о государственной регистрации программ для ЭВМ (номера свидетельств:

№2013611468, № 2013619210).

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

Структура и объем работы. Диссертационная работа состоит из введения, пяти глав и заключения. Объем работы составляет 163 страницы.

Список литературы содержит 88 наименований.

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

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

В первой главе производится обзор проблемы исследования.

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

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

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

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

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

При решении задачи аппроксимации НС представляется системой типа синглтон, описываемой по формуле где x = [ x1,..., xm ], n – количество правил НС; m – количество входных переменных в НС; µ A ji – функция принадлежности нечеткой области.

Нечеткий аппроксиматор может быть представлен как где y – скалярный выход аппроксиматора, = ||1,…, N|| – вектор оптимизируемых параметров, N = a * bi, a – число параметров, описывающих одну функцию принадлежности, bi – число термов, описывающих i-тую входную переменную. Пусть дано множество обучающих данных (таблица наблюдений) {(xp; tp), p = 1,..., m}, тогда среднеквадратическая функция ошибки (RMSE), являющаяся численным критерием адекватности модели, вычисляется по следующей формуле:

Задача аппроксимации сводится к поиску параметров НС, при которых значение данного критерия минимально.

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

Rij: ЕСЛИ x1=А1i И x2=А2i И…И xm=Аmi ТО class = cj, w=CFi;

где, x = (x1, x2, x3, …, xn) – вектор признаком классифицируемого объекта;

Aij – нечеткий терм, характеризущий k-ый признак в i-том правиле (i[1,R]), R – число правил; cj – идентификатор j-того класса, j [1,m]; CFi – вес правила или уровень доверия i-тому правилу, CFi [0,1].

Задача традиционной классификации может быть описана функцией:

где f(x)=(c1, c2, …, cm) причем ci=1, а cj=0 (j [1, m], i j), когда объект, заданный вектором x, принадлежит к классу ci.

Нечеткая классификация описывается функцией f : n [0,1] m, которая относит классифицируемый объект к каждому классу с определенной степенью принадлежности, вычисленной по следующей формуле:

Выходом классификатора является класс, определяемый следующим образом:

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

Пусть дано множество обучающих данных (таблица наблюдений) {(xp; tp), p = 1,..., z}, определим следующую единичную функцию:

Тогда численный критерий адекватности системы классификации может быть выражен следующим образом:

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

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

Во второй главе приводятся разработанные алгоритмы настройки НС.

Методика двухкритериального анализа НС. Для нахождения компромисса между сложностью НС и ее точностью в работе предложена методика построения двухкритериальных Парето–оптимальных НС (рисунок 1).

Основными этапами построения Парето–оптимального множества НС являются: 1) задание сложности НС; 2) генерация НС со структурой заданной сложности; 3) настройка НС алгоритмами параметрической идентификации; 4) выбор недоминируемых НС; 5) построение Парето–фронта.

Сложность НС в работе определена как сумма числа правил и числа термов НС.

Исследователь Алгоритмы генерации структуры НС Алгоритмы настройки параметров НС Задать сложность НС Сгенерировать структуру НС Оптимизировать параметры НС Выбрать недоминируемые НС Построить Парето-фронт Рис. 1 Диаграмма формирования двухкритериальных Парето–оптимальных НС Для генерации структуры в работе используется алгоритм генерации базы правил НС равномерным разбиением и перебором представленный ниже:

Вход: таблица наблюдений {xp,tp}, Type – тип функции принадлежности, вектор Count_terms с указанием количества термов, требуемых по каждому признаку.

Выход: – начальная база правил аппроксиматора.

Алгоритм:

Шаг 1. Для каждого i-го входного параметра делать:

Шаг 1.1. Рассчитать длину одного терма как distance = max(xpi) - min(xpi) / (Count_termsi - 1) Шаг 1.2. Задать базовую точку построения терма term_base =min(xpi) Пока term_base 0,5 то частица передает свое найденное наилучшее решение всем своим «соседям». Таким образом, происходит постоянный ускоренный обмен решениями, что положительно влияет на скорость сходимости роя к оптимуму.

Гибридный АРЧ совместно с МНК. Ниже представлено описание работы гибридного адаптивного АРЧ в связке с методом наименьших квадратов.

Вход. Параметры алгоритма: c1, c2, w, M; kmax – максимальное количество итераций или Emin – минимальное значение ошибки.

Выход. Вектор оптимальных параметров.

Шаг 1. Начинается работа адаптивного алгоритма роящихся частиц с модифицированной топологией обмена решениями.

Шаг 2. После завершения работы АРЧ запускается метод наименьших квадратов для оптимизации консеквентов базы правил.

Шаг 4. Если достигнуто условие окончания работы (kmax, Emin), то ОСТАНОВ, иначе начинается новый цикл оптимизации: переход к шагу 1.

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

Вход. Данные, из которых необходимо извлечь правила.

Выход. Массив часто встречающихся множеств.

Шаг 1. Задание параметров алгоритма: vi(0)=0 c1, c2, w, N, минимальные значения поддержки.

Шаг 2. Генерация роя случайным образом, k =1. Каждая частица представляет вектор из 0 и 1. Если элемент входит в часто встречающееся множество то он кодируется 1, иначе 0.

Шаг 3. Если достигнуто условие окончания работы (выполнилось заданное количество итераций), то переход на шаг 6. Происходит оценка каждого вектора по формуле Log(Supp(xi)*Length(xi) + 1), где Supp(xi) – поддержка множества, Length(xi) – количество элементов найденного множества. Поиск идет на нахождение максимума. Если данный вектор удовлетворяет минимальной поддержке, то он заносится в массив часто встречающихся множеств.

Шаг 4. Для каждой частицы происходит определение ее вектора скорости vi(k+1) и новых координат xi(k+1) согласно бинарному АРЧ.

Шаг 5. Расчет новых лучших позиций каждой частицы pi(k+1). Определение частицы с лучшей позицией в рое pg(k+1).

k=k+1; переход к шагу 3.

Шаг 6. Окончание работы.

После работы алгоритма поиска часто встречающихся множеств происходит генерация и оценка достоверности правил.

Бинарный алгоритм роящихся частиц с нечетким оцениванием.

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

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

Комплекс «Fuzzy System». Программный комплекс «Fuzzy System»

предназначен для создания, настройки и использования НС, построенных при помощи технологии нечеткого моделирования. В состав комплекса входит программа создания НС «Fuzzy System» и программа использования НС на практике «Model Explorer».

Web-ориентированный программный комплекс настройки НС. Сайт разработан на php-фреймворке CakePHP 2 c использованием СУБД MySQL.

Сайт состоит из пользовательской части и панели администратора. Сайт позволяет создавать и настраивать НС в режиме online. Для оптимизации НС используется комплекс «FuzzySystem».

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

Унифицированное представление НС. Важной задачей при построении программных комплексов на основе НС является сохранение и перенос между модулями уже настроенных НС. В работе предложен формат UFS. Данный формат представления основан на языке разметки XML и предназначен для детального описания структуры НС, таблиц наблюдения, и результатов обучения НС. Описание НС в формате UFS позволяет хранить, редактировать, переносить и использовать созданные и обученные НС в разрабатываемых технических системах или в исследованиях. Отличием представленного формата от аналогов является возможность описания двух типов НС:

аппроксиматоров и классификаторов.

В таблице 1 приведен фрагмент описания основных структурных элементов НС типа синглтон для задачи аппроксимации данных diabetes из репозитария KEEL. Корневым тегом, объединяющим все элементы НС, является тег FuzzySystem, определяющий тип описываемой НС:

Четвертая глава содержит описание экспериментов по идентификации НС разработанными алгоритмами.

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

1) f(x1, x2) = x1*sin(x2), -/2 < x1, x2 < /2;