Самоконфигурирующийся гибридный эволюционный алгоритм формирования нечетких классификаторов с активным обучением для несбалансированных данных

Полный текст

Введение. Современные методы машинного обучения часто используют эволюционные либо бионические алгоритмы, в качестве алгоритмов формирования структуры или настройки своих компонентов, таких как искусственные нейронные сети, машины опорных векторов (support vector machines, SVM), системы на нечеткой логике, нейронечеткие системы или же их объединения в коллективы. Эволюционные и бионические алгоритмы зачастую применяются из- за сложности возникающих в процессе обучения процедур классификации, которые могут содержать большое число переменных либо переменные различных типов, множество целевых функций, множество экстремумов, плато и т. д. Для решения подобных задач лучше всего себя зарекомендовали эволюционные подходы [1; 2]. Однако использование эволюционных методов, как правило, сопряжено с необходимостью использования значительных вычислительных ресурсов. Если говорить о задачах классификации, которые являются типичными задачами анализа данных, то существует ряд подходов, позволяющих производить машинное обучение на значительных объемах данных с использованием методов сокращения данных (Data reduction). Сокращение данных может преследовать две цели: снижение числа переменных, иначе выбор информативных признаков, и снижение числа измерений. Задача отбора информативных признаков является нетривиальной задачей, для которой разработано множество подходов и методов, в том числе использующих эволюционные алгоритмы [3; 4]. Задача отбора измерений также является важной задачей, и группу методов, выбирающих некоторые измерения из их большого массива, называют отбором обучающей выборки (Training Set Selection, TSS) или же селекцией измерений (Instance Selection, IS) [5]. Суть данных методов, как правило, сводится к отбору некоторых прототипов (Prototype Selection, PS) - объектов, в определенной степени описывающих тот или иной класс. Однако проблема отбора измерений часто связана с проблемой релевантности выбранной подвыборки, изначальной выборке данных. Удаление измерений из обучающей выборки не обязательно приводит к уменьшению информации, полезной для обучения. Более того, снижение объема выборки может помочь предотвратить переобучение в некоторых случаях, так как изначальная выборка может содержать шум. Таким образом, методы отбора измерений могут не только снизить объем требуемых вычислительных ресурсов, но и повысить качество формируемых моделей, например классификаторов. Таким образом, основной идеей данной работы является разработка таких алгоритмов выбора измерений, которые позволили бы формировать более точные и качественные классификаторы, затрачивая при этом меньше вычислительных ресурсов. Некоторые предыдущие работы в данной области использовали методы распараллеливания и разбиения выборки на подвыборки случайным образом [6]. В следующих разделах мы рассмотрим примененный алгоритм построения нечетких классификаторов, опишем идею активного выбора обучающих примеров и далее приведем результаты тестирования модифицированного алгоритма. Гибридный нечеткий эволюционный алгоритм. За основу в использованном алгоритме формирования нечетких баз правил для задач классификации был взят алгоритм, разработанный группой Х. Ишибучи и описанный в работе [6]. Данный метод использует комбинацию питсбургского и мичиганского подходов, при этом мичиганский подход применяется наряду с оператором мутации. Ниже будет приведено краткое описание метода, так как он был запрограммирован с нуля и потому отличается от изначальной идеи в некоторых аспектах. Основная популяция эволюционного алгоритма реализует питсбургский подход, где каждый индивид является базой правил целиком. В нашей реализации индивид представлял собой двумерную матрицу, строки которой являлись правилами. Элементы строки принимали значения в диапазоне [0, 14] соответственно 15 использованным нечетким множествам. Число правил в базе не фиксировано и может меняться в ходе работы алгоритма, однако не может превышать заранее заданный верхний лимит. Правила выглядят следующим образом: Rq : еслиXi это Aq,1 иX2 это Aq,2 и ... ИXn ЭТ° тогда X это Cq c весом CFq , ч ч где Xp = (Xp1,Xp2, ..., Xpm),p = 1... m - выборка измерений; n - число переменных в задаче; m - число измерений; Rq - это правило; Aq,i - нечеткое множество, Cq - номер соответствующего класса; CFq - вес правила. Набор нечетких множеств представляет собой 4 разбиения на 2, 3, 4 и 5 нечетких множеств, показанных на рис. 1. Помимо этих 14 множеств используется также терм игнорирования значения переменной (“Don’t care” condition, DC). Данный метод задания нечетких множеств является достаточно гибким и позволяет решать задачи с высокой точностью, не применяя процедур настройки положений термов. Тем не менее в литературе встречаются другие подходы, к примеру, 2-парное иерархическое представление. Рис. 1. Четыре нечетких разбиения, использованных в алгоритме В качестве операторов селекции использовались ранговая и турнирная селекция с размером турнира 2, а также три типа мутации - слабая, средняя, сильная. Применялся один оператор скрещивания, специфический для данного алгоритма. Вероятность мутации зависела от размера базы правил, т. е. от числа правил следующим образом: для слабой мутации - 1/(3 ^S|n), для средней - 1/(|S|n), для сильной - 3/(|S|n), где |S| - число правил в базе, n - число переменных. При скрещивании новая база правил состояла из правил, содержащихся у родителей, при этом число правил выбиралось как случайное число в диапазоне [1, |S1| + + |S2|]. Правила для заполнения нового индивида также выбирались равномерно и случайно из общего пула правил родителей. Если конечное число правил превышало верхний лимит, то несколько правил удалялись случайным образом. Инициализация популяции производилась с использованием измерений, содержащихся в выборке. Данный шаг необходим, потому что при генерации случайных правил вероятность того, что сгенерированное правило будет описывать хотя бы часть выборки, очень мала. Поэтому для формирования базы правил случайным образом выбиралось измерение. Далее подбиралось правило, которое в наилучшей степени описывает данное измерение, при этом, если под это правило подходят несколько термов из различных разбиений, то они имеют шанс быть выбранными в правило с определенной вероятностью, зависящей от степеней принадлежности. После формирования правила половина термов в нем случайным образом изменяется на терм игнорирования значения переменной. Этот шаг необходим для получения более общих правил. После генерации правил рассчитывается наиболее подходящий номер класса и вес нечеткого правила. Эти величины рассчитываются с использованием меры поддержки (Confidence, Conf) правила по выборке, позаимствованной из области оценки ассоциативных правил: xpeClasskЦAq () Conf (Aa ^ Class k )= p , q m X pAq (xp ) где цAq (xp) - это степень принадлежности измерения xp к нечеткому множеству Aq. Класс, которому соответствует наибольшее значение поддержки, устанавливается в качестве наиболее подходящего класса. Вес правила рассчитывается также с использованием поддержки [7]: CFq = Conf (Aq ^ Class q )- M - X Conf (Aq ^ Class k ). k=1, k pCq При нечетком выводе объект классифицируется правилом-победителем, т. е. правилом, имеющим наибольшее произведение степени принадлежности на вес правила. Степень принадлежности при этом рассчитывается как произведение степеней принадлежности по всем переменным. Стоит отметить, что эвристика назначения номера класса назначает правилу тот класс, который имеет наибольшее значение поддержки, однако для несбалансированных данных значения поддержки по каждому из классов может быть смещено, так как поддержка зависит от числа измерений каждого класса. Это значит, что для классов, имеющих меньшее число измерений, значения поддержки могут быть меньше не потому, что данное правило хуже описывает этот класс, а потому что меньше измерений этого класса описывается правилом. Это приводит к тому, что значительная часть сгенерированных правил связывается с классами, имеющими большее число измерений, в то время как данные правила могут оказаться важными для описания миноритарного класса. Чтобы избежать данного смещения, здесь мы используем модифицированную процедуру определения наиболее подходящего номера класса, использующую число измерений каждого класса в качестве веса: Conf (Aq ^ Class k) Class q = arg max( • m), k mk где mk - это число измерений класса k. Мичиганская часть могла быть выполнена тремя способами: добавление правил, удаление правил и замещение правил. При этом каждое правило рассматривалось как индивид, а база правил - как популяция. Пригодности правилам назначались в соответствии с числом измерений, которые были корректно классифицированы правилом. При этом удалялись правила, имеющие наименьшую пригодность. Добавление новых правил производилось двумя типами: генетическим подходом и эвристическим подходом. Генетический подход подразумевал получение новых правил из имеющихся в базе посредством применения генетических операторов, таких как селекция, скрещивание и мутация. Эвристический подход генерировал новые правила из некорректно классифицированных измерений. Замещение правил подразумевало сначала удаление нескольких правил, а затем добавление равного числа правил. При этом число правил для удаления / добавления зависело от текущего числа правил в базе. Пригодность базы правил рассчитывалась как сумма точности на обучающей подвыборке в процентах с весом 100, числа правил в базе с весом 1 и общей длины всех правил с весом 1. На сегодняшний день множество алгоритмов использует многокритериальные подходы [8]. Так как в алгоритме использовалось несколько типов селекции, мутации, а также несколько операторов в мичиганской части и типов добавления правил, и для всех них была применена процедура самонастройки. Самонастройка необходима по той причине, что различные типы операторов имеют разные свойства и меняют поведение алгоритма в процессе поиска. Заранее, до решения поисковой задачи, невозможно определить, какие из операторов будут лучшими для конкретной задачи. Применение самонастройки меняет вероятности применения операторов в процессе работы алгоритма так, что более успешные операторы получают большую вероятность быть выбранными. В данной работе был использован подход, ранее описанный в [9; 10] и показавший свою эффективность в [11]. Суть метода заключается в поощрении тех операторов, которые позволили получить более высокую пригодность в среднем на каждом поколении. Пусть z - число операторов определенного типа. Начальные вероятности устанавливаются равными: рі = 1/z. Успешность операторов определяется с использованием усредненных пригодностей: AvgFUi = - £,і =1 2 ..., z nij=1 j где ni - количество потомков, в формировании которых принял участие і-й тип оператора; f - пригодность j-го потомка, построенного с помощью і-го оператора; AvgFiti - средняя пригодность решений, построенных при помощи і-го оператора. После этого вероятность применения оператора, чье значение AvgFUt является наибольшим среди всех операторов такого типа, увеличивается на (zK-K)/(zN), а вероятности применения остальных операторов уменьшаются на K/(zN), где N - число поколений генетического алгоритма, K - константа, её значение устанавливалось равным 0,5. Активный выбор обучающих примеров из выборки. Как мы отмечали во введении, сокращение данных может в некоторых случаях привести к более низкой точности на тестовой выборке. Таким образом, следовало бы разработать метод селекции измерений, который бы позволял получать как минимум столь же точные результаты, как и классический подход. Подобные подходы ранее рассматривались в [12; 13]. Метод выбора измерений, предлагаемый в данной работе, использует информацию о корректной классификации объектов выборки для выбора тех измерений, которые более сложны для классификации. Так как мы используем эволюционный подход, то существует возможность менять обучающую выборку в ходе обучения каждые несколько поколений. На начальном этапе мы выбираем 33 % начальной обучающей выборки и формируем подвыборку, при этом все измерения имеют равную вероятность быть выбранными. После процедуры инициализации алгоритм обучается в течение 200 поколений. На каждом поколении лучший текущий индивид проверяется на всей выборке, и если он представляет собой лучшее известное решение для всей выборки, то запоминается. Лучшее известное решение всегда включается в популяцию наряду с лучшим решением для всей выборки. Стоит отметить, что, так как мы работаем с подвыборкой, то лучший текущий индивид может проявлять признаки переобучения на подвыборку, вследствие чего он может некорректно классифицировать всю имеющуюся выборку. По этой причине необходимо запоминать наилучшее найденное на текущий момент решение. После периода адаптации длительностью в 200 поколений в наших вычислительных экспериментах мы рассчитываем точности каждого индивида на всей выборке. Это шаг является важным, так как при том, что лучшее решение для подвыборки может показывать средние результаты для всей выборки, в популяции могут присутствовать другие индивиды, которые, хотя и являются не лучшими решениями для подвыборки, представляют собой очень хорошие решения для описания всей выборки. Для того чтобы направить процесс обучения на следующем периоде адаптации и сконцентрировать процесс обучения на «проблематичных» областях пространства переменных, необходимо изменить вероятности выбора измерений. Во-первых, необходимо выбирать те измерения, которые не были использованы на предыдущих этапах. Во-вторых, следует также выбирать измерения, которые были неверно классифицированы. Первый принцип соответствует исследованию новых имеющихся измерений, в то время как второй означает поиск и концентрацию на наиболее интересных областях пространства. После каждого периода адаптации длиной в 200 поколений необходимо заново выбрать новые измерения для формирования подвыборки. Для реализации данной идеи каждому измерению ставится в соответствие число иі, і = 1, ..., m. В начале все иі устанавливаются равными 1. После выбора этих измерений и обучения классификатора значения иі для тех измерений, которые были выбраны, изменяются в соответствии с лучшим индивидом для подвыборки. Если измерение j было выбрано и классифицировано корректно, то Uj = Uj + 1, если же оно было классифицировано неверно, то Uj = 1. После обновления значений иі формируется обучающая выборка с использованием процедуры, подобной пропорциональной селекции в классическом генетическом алгоритме. Вероятность измерения быть выбранным Р рассчитывается как E , mi ■k’ к Ave=z i=0 Acc = = 1Ut P = Z 1/Uj j =\...m Те измерения, которые были классифицированы корректно, увеличивают свой счетчик успешных использований в обучающей выборке. В случае, если после периода адаптации лучший индивид для подвыборки неверно классифицирует какое-либо измерение, которое было неоднократно классифицировано корректно, его счетчик устанавливается равным \, что означает большую вероятность быть выбранным в будущем. Таким же образом те измерения, которые всегда некорректно классифицируются, всегда сохраняют большую вероятность быть выбранными. После нескольких периодов адаптации те измерения, которые неоднократно были классифицированы корректно, получают меньшие вероятности выбора. Это приводит к ситуации, когда те измерения, которые легко поддаются классификации, реже выбираются в подвыборку, так как они представляют меньший интерес для процесса обучения. Метод стремится использовать эти измерения равномерно, чтобы покрыть всю информацию, имеющуюся в обучающей выборке. После значительного числа поколений алгоритм находит проблематичные области и фокусируется на них, чтобы найти лучшее разделение классов. Рис. 2. Изменение вероятностей выбора примеров Чтобы лучше понять эффекты, которые возникают в результате подобной процедуры, далее приводится два рисунка (рис. 2, 3), объясняющих изменение вероятностей выбора измерений и изменение того, какие из измерений выбираются. На рис. 2 представлен пример изменения вероятностей для случая 8 измерений. В начале все измерения имеют равные вероятности и все Uj равны \. Выбранные измерения показаны серым цветом. После первого периода адаптации измерение 3 было классифицировано некорректно, так что значение U3 было установлено равным \, а измерение 6 было верно классифицировано, поэтому U6 увеличилось на \. После нескольких периодов адаптации значения U были обновлены в соответствии с формулой. Таким образом, измерения \ и 7 имеют более высокую вероятность быть выбранными, чем другие. На рис. 3 показан графический пример того, какие измерения выбираются алгоритмом и как процедура активного выбора примеров приводит к повышению качества классификации. В примере 2 класса и 3\ измерение, различные классы показаны крестиками и квадратами. Слева показано начало работы алгоритма, при котором все измерения имеют равные вероятности быть выбранными. Большие либо меньше вероятности показаны размерами знаков. Знаки, обведенные кружками, означают выбранные для данного периода адаптации. Разделяющая поверхность, полученная к концу первого периода адаптации, некорректно классифицирует измерения \6 и \8, которые имеются в подвыборке. Справа показан следующий период адаптации, где измерения \6 и \8 не изменили размер (U\6 = U\8 = \) и их размер равен размеру неиспользованных измерений, в то время как верно классифицированные примеры (\, 3, 7, \2, \4, \9, 20, 28, 29) получили меньший размер и соответственно меньшую вероятность. Нижний график (рис. 3) демонстрирует ситуацию после нескольких периодов адаптации, где те измерения, которые ближе к разделяющей поверхности, получили большие вероятности быть выбранным (и они действительно выбраны на данной итерации), в то время как далекие от разделяющей поверхности измерения получили меньшие вероятности. Меры Acc и Ave для определения качества классификации. При решении сложных задач классификации методы машинного обучения могут быть неэффективны вследствие различных свойств имеющихся данных. Одним из таких свойств является сбалансированность выборки по классам. Если один из классов представлен большим числом измерений, чем другой, то у алгоритма обучения могут быть проблемы с корректным выделением миноритарного класса. Задачи классификации со значительным дисбалансом, как правило, более сложны при решении, чем сбалансированные задачи. Несмотря на то, что на них может быть получена высокая точность классификации, это может означать, что верно классифицирован только мажоритарный класс, в то время как миноритарный класс, который часто представляет больший интерес, классифицируется неверно. Это означает, что, несмотря на высокую точность, задача остается нерешенной. Проблема несбалансированных данных ранее рассматривалась в [\4]. Наряду с общей точностью Acc, как мера классификации для несбалансированных данных часто применяется средняя точность по классам Ave. Точности на всех классах суммируются и затем делятся на число классов, что в итоге дает значение меры Ave. Следующие два выражения формально описывают данные меры: к Ze i=0 к Z m i=0 где Ei - это число ошибок классификатора на i-м истинном классе; тк - это число измерений класса к. Далее будет показано, как активный подход к обучению может повысить не только точность классификации, но и сбалансированность по классам даже при использовании меры Acc в функции пригодности. Рис. 3. Активный выбор обучающих примеров Тестирование алгоритма и результаты. Для тестирования алгоритма было выбрано 4 задачи классификации с репозиториев KEEL и UCI [15; 16]. Данные задачи могут представлять трудности для некоторых алгоритмов, так как содержат большое число переменных, множество классов, а также несколько тысяч измерений. Задачи, на которых мы протестировали алгоритмы, следующие: 1) Page-blocks, 5472 измерения, 10 переменных, 5 классов; 2) Phoneme, 5404 измерения, 5 переменных, 2 класса; 3) Segment, 2310 измерений, 19 переменных, 7 классов; 4) Satimage, 6435 измерений, 36 переменных, 6 классов. Табл. 1 показывает число измерений для каждого класса этих задач. При тестировании алгоритма мы использовали следующие параметры: число индивидов - 100, число поколений - 10 000, число правил - 40, размер обучающей подвыборки - 33 % от всей выборки, длительность периода адаптации - 200 поколений. Для каждой задачи тестировалось 8 вариантов алгоритма: с активным обучением и без, с несмещенной процедурой назначения номеров классов и оригинальной, с мерой Acc и мерой Ave в функции пригодности. Для получения адекватных результатов мы использовали процедуру 10-частной кроссвалидации со стратифицированным разбиением, 2 раза для каждой задачи. Стоит отметить, что время работы алгоритма с активным обучением сокращалось в 3 раза. В табл. 2 показаны результаты для задачи Page- blocks. Следует отметить, что для данной задачи активный выбор примеров из обучающей выборки незначительно меняет поведение алгоритма обучения и получаемые в результате классификаторы. На обучающей выборке точность обоих методов практически одинакова, также как и точность на тестовой. При этом мера Ave для случая с активным обучением оказывается ниже практически во всех случаях. Следует отметить, что данная задача является наименее сбалансированной из всех. Результаты для задачи Phoneme демонстрируют преимущество активного обучения перед классическим подходом: точность при использовании активного обучения увеличивается как для обучающей, так и для тестовой выборки, хотя в случае использования меры Acc в функции пригодности это приводит к получению менее сбалансированных классификаторов (табл. 3). При использовании меры Ave в качестве меры качества классификации, алгоритм получает в равной мере сбалансированные классификаторы, но с более высокой точностью. Для задачи Segment, для которой все классы сбалансированы, активное обучение позволяет достичь значительного улучшения качества классификации (табл. 4). Так как эта задача сбалансирована, то значения меры Ave и Acc совпадают. Число объектов классов для всех задач Таблица 1 Задача/класс 1 2 3 4 5 6 7 Page-blocks 4913 329 28 87 115 - - Phoneme 3818 1586 - - - - - Segment 330 330 330 330 330 330 330 Satimage 1533 703 1358 626 707 1508 - Результаты для задачи Page-blocks Таблица 2 Результаты без активного обучения Конфигурация Acc на обуч. Acc на тест. Ave на обуч. Ave на тест. Acc+смещ. 0,965 0,960 0,647 0,623 Acc+несмещ. 0,946 0,944 0,582 0,566 Ave+смещ. 0,925 0,922 0,919 0,867 Ave+несмещ. 0,917 0,917 0,927 0,895 Результаты с активным обучением Acc+смещ. 0,964 0,959 0,635 0,586 Acc+несмещ. 0,964 0,960 0,660 0,663 Ave+смещ. 0,909 0,900 0,877 0,849 Ave+несмещ. 0,898 0,892 0,902 0,848 Таблица 3 Результаты для задачи Phoneme Результаты без активного обучения Конфигурация Acc на обуч. Acc на тест. Ave на обуч. Ave на тест. Acc+смещ. 0,827 0,818 0,798 0,788 Acc+несмещ. 0,819 0,812 0,783 0,774 Ave+смещ. 0,816 0,807 0,836 0,825 Ave+несмещ. 0,805 0,794 0,820 0,808 Результаты с активным обучением Acc+смещ. 0,837 0,826 0,738 0,767 Acc+несмещ. 0,839 0,829 0,785 0,773 Ave+смещ. 0,820 0,815 0,831 0,823 Ave+несмещ. 0,820 0,810 0,836 0,824 Результаты для задачи Segment Таблица 4 Результаты без активного обучения Конфигурация Acc на обуч. Acc на тест. Ave на обуч. Ave на тест. Acc+смещ. 0,934 0,919 0,934 0,919 Acc+несмещ. 0,933 0,918 0,933 0,918 Ave+смещ. 0,928 0,910 0,928 0,910 Ave+несмещ. 0,930 0,917 0,930 0,917 Результаты с активным обучением Acc+смещ. 0,967 0,942 0,967 0,942 Acc+несмещ. 0,966 0,939 0,966 0,939 Ave+смещ. 0,965 0,943 0,965 0,943 Ave+несмещ. 0,967 0,949 0,967 0,949 Таблица 5 Результаты для задачи Satimage Результаты без активного обучения Конфигурация Acc на обуч. Acc на тест. Ave на обуч. Ave на тест. Acc+смещ. 0,842 0,831 0,760 0,748 Acc+несмещ. 0,843 0,834 0,761 0,752 Ave+смещ. 0,845 0,835 0,770 0,759 Ave+несмещ. 0,843 0,836 0,769 0,760 Результаты с активным обучением Acc+смещ. 0,886 0,873 0,843 0,830 Acc+несмещ. 0,884 0,865 0,844 0,822 Ave+смещ. 0,878 0,863 0,860 0,845 Ave+несмещ. 0,874 0,857 0,856 0,835 Для задачи Satimage активное обучение также демонстрирует лучше результаты, чем классический подход (табл. 5). При этом значительное улучшение наблюдается как на обучающей, так и на тестовой выборке, как при использовании меры Acc, так и меры Ave в функции пригодности. Более того, получаемые классификаторы во всех случаях значительно более сбалансированы. Заключение. В данной работе был рассмотрен подход к сокращению данных, который позволяет не только сократить объем требуемых вычислительных ресурсов, но и повысить качество получаемых классификаторов. Представленный алгоритм активного обучения классификаторов посредством выбора обучающих примеров показал свою эффективность на ряде задач классификации, при этом формируя не только более точные в целом базы правил, но также и одинаково точные на всех классах. Дальнейшая разработка данного метода может включать модификации назначения счетчиков для измерений, изучение зависимости результатов от объема подвыборки и длины периода адаптации. Также интересным представляется применение данного подхода для других алгоритмов и методов классификации, например, для нейронных сетей [17; 18], машин опорных векторов [19], генетического программирования [20] и других методов.

Об авторах

Владимир Вадимович Становов

Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева

Email: vladimirstanovov@yandex.ru
аспирант Российская Федерация, 660014, г. Красноярск, просп. им. газ. «Красноярский рабочий», 31

Ольга Эрнестовна Семенкина

Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева

Email: semenkina.olga@mail.ru
доктор технических наук, профессор кафедры высшей математики Российская Федерация, 660014, г. Красноярск, просп. им. газ. «Красноярский рабочий», 31

Список литературы

Дополнительные файлы