Метод и алгоритмы выбора признаков в предсказательном моделировании фенотипических характеристик на основе транскриптомных данных Сметанников Иван Борисович

Содержание к диссертации

Введение

1 Обзор предметной области 12

1.1 Экспрессия и транскрипция генов 12

1.2 Предсказательные модели и их обучение 16

1.3 Метод опорных векторов 23

1.4 Задача выбора признаков 25

1.5 Алгоритмы оптимизации функции, представленной черным ящиком 33

1.6 Задача о многоруком бандите и алгоритм UCB-1 37

1.7 Мета-обучение 39

1.8 Задачи, решаемые в диссертационном исследовании 42

Выводы по главе 1 43

2 Предлагаемый метод выбора признаков 45

2.1 Метод MeLiF 45

2.2 Алгоритм MeLiF-1 47

2.3 Алгоритмы оптимизации функции QC для метода MeLiF 50

Выводы по главе 2 55

3 Предлагаемые параллельные алгоритмы, реализующие предложенный метод 56

3.1 Алгоритм MeLiF+ 56

3.2 Алгоритм PqMeLiF 59

3.3 Алгоритм MaMeLiF 63

Выводы по главе 3 67

4 Предлагаемый алгоритм на основе мета-обучения, реализующий предложенный метод 68

4.1. Система мета-обучения для предсказания стартовых точек 68

4.2. Алгоритм GPSMeLiF 70

Выводы по главе 4 73

5 Описание программного комплекса 75

5.1 Состав комплекса программ 75

5.2 Структура проекта 76

5.3 Руководство пользователя 82

5.4 Внедрение программного комплекса в Insilico Medicine Inc. (Москва) 84

Выводы по главе 5 85

Заключение 87

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

Ресурсы сети интернет 97

Приложение А Расширенные таблицы экспериментов 99

А.1 Результаты алгоритма MeLiF-1 99

А.2 Результаты различных методов оптимизации для алгоритма MeLiF 100

A.3 Время работы различных конфигураций алгоритмов PqMeLiF и MaMeLiF 102

A.4 F1 мера различных конфигураций алгоритмов PqMeLiF и MaMeLiF 103

А.5 Результаты алгоритма GPSMeLiF 104

• Задача выбора признаков
• Алгоритмы оптимизации функции QC для метода MeLiF
• Алгоритм GPSMeLiF
• Структура проекта

Введение к работе

Актуальность темы. Дезоксирибонуклеиновая кислота (ДНК), представляющая собой длинную полимерную двухцепочечную молекулу, закрученную в спираль, является основным механизмом хранения и передачи наследственной информации живых организмов. Он реализуется через экспрессию генов — процесс, в ходе которого наследственная информация преобразуется в рибонуклеиновую кислоту (РНК) или белок. Вследствие этого уровень экспрессии генов связан с объективными характеристиками проистекающих в клетках живых организмов процессов.

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

Несмотря на существующую каузальную связь между экспрессией генов и фенотипических характеристик, построение точных математических моделей для этих связей принципиально недостижимо ввиду чрезвычайно большого числа переменных и связей между ними. Перечисленные ограничения позволяет решить подход на основе данных (data driven approach), дающий возможность строить предсказательные модели за счет автоматического выявления представленных в выборке значимых зависимостей между переменными.

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

Степень разработанности темы. Значительных результатов в данном направлении добились Veronica Bolon-Canedo¹, Kenneth N. Ross², Yu Wang³, a также Загоруйко H. Г.⁴, Князев Д. И.⁵ и др. Общая схема построения предсказа-

¹ Bolon-Canedo V., et.al. A review of microarray datasets and applied feature selection methods // Information
sciences. —2014. —Vol. 282. —P. 111-135.

² Shipp M, etal. Diffuse large B-cell lymphoma outcome prediction by gene-expression profiling and super
vised machine learning // Nature medicine. — 2002. — Vol. 8. — P. 68-74.

³ Wang Yu, etal. Gene selection from microarray data for cancer classification — a machine learning ap
proach // Computational biology and chemistry. — 2005. — Vol. 29. — P. 37^16.

⁴ Alves A. et.al. Predictive Analysis of Gene Data from Human SAGE Libraries // Proceedings of the Workshop
ECML/PKDD. — 2005. —P. 60-71.

⁵ Князев Д. и др. Особенности сплайсинг-ориентированных ДНК-микрочипов и их применение в биоме
дицинских исследованиях // Современные технологии в медицине. — 2015. — Т. 7. — №4. — С. 162-173.

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

Наиболее важным этапом второго шага является уменьшение размерности — выбор значимых генов, которые в контексте машинного обучения будут называться признаками. В общем случае, наборы данных, для которых осуществляется выбор признаков, имеют число объектов \Х\ больше числа признаков | F |. Однако в случае выбора наиболее значимых генов это не верно, так как число объектов (образцов) измеряется десятками, а число признаков (генов) — тысячами. Выбор наиболее значимых генов позволяет строить более точные предсказательные модели для выявления врожденных и приобретенных заболеваний и других фенотипических характеристик обследуемых.

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

Целью работы является снижение времени построения и доли ошибок предсказательной модели фенотипических характеристик на основе транскриптомных данных за счет разработки метода и алгоритмов выбора признаков.

Указанная цель достигается последовательным решением основных задач диссертационной работы:

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

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

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

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

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

5. Метод построения ансамблей фильтрующих методов выбора признаков MeLiF, основанный на поиске оптимальных коэффициентов линейной комбинации мер значимости признаков (МЗП) этих алгоритмов. Новизна предложенного метода заключается в сведении задачи выбора признаков к задаче оптимизации в проективном пространстве коэффициентов линейной комбинации МЗП.

6. Алгоритм выбора признаков MeLiF-X, реализующий новый метод MeLiF и основанный на поиске оптимальных коэффициентов линейной комбинации МЗП агрегируемых фильтров при помощи жадной модификации метода покоординатного спуска. Показано, что разработанный алгоритм получает более качественный набор признаков, чем другие методы выбора признаков, применяемые для построения предсказательных моделей по транскриптомным данным, однако проигрывает им во времени работы.

7. Алгоритм выбора признаков PqMeLiF, реализующий новый метод MeLiF и основанный на поиске оптимальных коэффициентов линейной комбинации МЗП агрегируемых фильтров при помощи параллельной модификации алгоритма MeLiF-X на основе очереди с приоритетами. Показано, что разработанный алгоритм получает схожий по качеству набор признаков, как и алгоритм MeLiF-X, и тратит меньше времени на вычисления.

8. Алгоритм выбора признаков MaMeLiF, реализующий новый метод MeLiF и основанный на поиске оптимальных коэффициентов линейной комбинации МЗП агрегируемых фильтров при помощи параллельной модификации алгоритма MeLiF-X на основе обучения с подкреплением. Показано, что разработанный алгоритм получает схожий по качеству набор признаков, как и алгоритм MeLiF-X, но тратит меньше времени на вычисления.

9. Алгоритм выбора признаков GPSMeLiF, реализующий новый метод MeLiF и основанный на поиске оптимальных коэффициентов линейной комбинации МЗП агрегируемых фильтров, который выбирает стартовые точки для алгоритма MeLiF-X на основе мета-обучения. Показано, что в большинстве случаев разработанный алгоритм позволяет значительно сократить пространство оптимизации.

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

Положения, выносимые на защиту:

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

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

2. Совокупность алгоритмов выбора признаков, реализующих предложенный метод, на основе поиска оптимальных коэффициентов линейной комбинации МЗП агрегируемых фильтров.

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

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

Практическая значимость работы состоит в том, что предложенный метод позволяет автоматически выбирать наиболее значимые гены на транскриптомных данных эффективнее других методов, применяемых для решения этой задачи, что, в частности, было применено в процессе синтеза новых лекарств в компании Insilico Medicine Inc. (Москва) и подтверждается актом о внедрении. Кроме того, предложенный метод и алгоритмы обеспечивают повышение эффективности систем автоматической кластеризации голосов дикторов в массивах неразмеченных данных, что подтверждается актом о внедрении.

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

Внедрение результатов работы. Предложенный метод выбора признаков на транскриптомных данных MeLiF применяется в компании Insilico Medicine Inc. (Москва). Результаты диссертации нашли применение в Университете ИТМО при выполнении прикладных научных исследований и экспериментальных разработок по теме "Разработка технологии автоматической кластеризации голосов дикторов в массивах неразмеченных данных для решения задач голосовой биометрии" в рамках Соглашения о предоставлении субсидии с Минобр-науки России № 14.578.21.0126 от 27.10.2015 г. (Ш проекта RFMEFI57815X0126). Результаты работы использовались в учебном процессе кафедры «Компьютерные технологии» Университета ИТМО при руководстве тремя бакалаврскими работами, авторы и названия которых приведены в диссертации.

Апробация результатов работы. Основные результаты диссертационной работы докладывались на следующих научных и научно-практических конференциях:

XVIII Международная конференция по мягким вычислениям и измерениям (SCM'15). 2015, СПбГЭТУ «ЛЭТИ», Санкт-Петербург.

V Всероссийский конгресс молодых ученых (КМУ'16). 2016, Университет ИТМО, Санкт-Петербург.

Научная и учебно-методическая конференция Университета ИТМО. 2016-2017 гг., Университет ИТМО, Санкт-Петербург.

Девятая международная конференция «Управление развитием крупномасштабных систем» (MLSD'16). 2016, ИПУ РАН, Москва.

The 23rd European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning (ESANN'15). 2015, Брюгге, Бельгия.

First International Symposium of Information and Internet Technology (Symintech'15). 2015, Малакка, Малайзия.

First International Early Research Career Enhancement School on Biologically Inspired Cognitive Architectures BICA. 2016, Москва, Россия.

The 12th International Conference on Machine Learning and Data Mining in Pattern Recognition (MLDM'16). 2016, Нью-Йорк, США.

The 18th International Conference on Soft Computing and Machine Intelligence (ICSCMF16). 2016, Дубай, ОАЭ.

The 5th Young Scientists Conference in HPC and Simulation (YSC'16). 2016, Краков, Польша.

The 12th Artificial Intelligence Applications and Innovations (АІАГ16). 2016, Тессалоники, Греция.

The 8th Asian Conference on Machine Learning (ACML'16). 2016, Гамильтон, Новая Зеландия.

Личный вклад автора. Идея метода выбора признаков MeLiF принадлежит совместно автору диссертации и А.А. Фильченкову, формализация и разработка предложенного в работе метода MeLiF принадлежит лично автору диссертации. Все представленные в диссертации алгоритмы, реализующие предложенный метод, принадлежат лично автору диссертации. Реализация и проведение вычислительных экспериментов алгоритма MeLiF-І принадлежат лично автору диссертации, реализация и проведение вычислительных экспериментов алгоритмов MeLiF+, PqMeLiF, MaMeLiF, GPSMeLiF принадлежат совместно автору диссертации и Е.О. Варламову, И.П. Исаеву и А.В. Дейнеке.

Публикации по теме диссертации. Основные результаты по теме диссертации изложены в одиннадцати публикациях, одна из которых издана в журнале, рекомендованном ВАК, семь — в изданиях, индексируемых в международных базах цитирования Web of Science и Scopus.

Свидетельства о регистрации программы для ЭВМ. Автором по теме диссертации получено два свидетельства о регистрации программ для ЭВМ.

Участие в научно-исследовательских работах. Результаты диссертации использовались при выполнении следующей НИР: «Биоинформатика, машинное обучение, технологии программирования, теория кодирования, проактив-ные системы» (Программа государственной финансовой поддержки ведущих университетов Российской Федерации, субсидия 074-U01. Сроки выполнения: 2013-2018 гг.), а также государственном задании № 2.8866.2017/БЧ «Технология разработки программного обеспечения систем управления ответственными объектами на основе глубокого обучения и конечных автоматов», выполняемого в рамках базовой части государственного задания.

Структура диссертации. Диссертация изложена на ПО страницах и состоит из введения, четырех глав, заключения и приложений. Список источников содержит 102 наименования. Работа проиллюстрирована 9 рисунками и 6 таблицами.

Задача выбора признаков

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

Задача выбора признаков (feature selection) является одной из фундаментальных задач машинного обучения [39, 58, 82]. Прежде всего, она возникает во множестве различных областей, в которых число признаков объектов велико и достигает десятков или сотен тысяч признаков [71]. Признаки, отсеиваемые в процессе, делятся на три вида [22, 23]: избыточные, неинформативные и малоинформативные. Их устранение может привести не только к уменьшению времени построения и последующей работы алгоритмов машинного обучения, но и улучшить их качество. Кроме того, за счет уменьшения размерности данные могут стать более понятными и интерпретируемыми.

Существует огромное число различных алгоритмов выбора признаков, при этом их принято делить на три большие группы [23, 41, 52]:

– Алгоритмы обертки (wrappers). В алгоритмах обертки модель машинного обучения строится на различных подмножествах исходного набора признаков. Множества подмножеств признаков перебираются исходя из некоторого алгоритма оптимизации, где оптимизируемой величиной выступает качество построенного алгоритма машинного обучения. К сожалению, так как на каждом шаге работы алгоритмов обертки требуется заново обучать модель, они применимы лишь на небольших наборах данных. Общая схема работы таких алгоритмов изображена на рисунке 3.

Встраиваемые (embedded) алгоритмы. Данные алгоритмы не разделяют выбор признаков и построение модели машинного обучения, и производят выбор прямо во время построения. Данный подход работает значительно быстрее, чем предыдущий, однако жестко привязан к конкретной обучаемой модели. Общая схема работы таких алгоритмов изображена на рисунке 4.

– Алгоритмы фильтрации (filters). Данные алгоритмы оценивают признаки, исходя из некоторой меры значимости признаков (МЗП) [69], не вовлекая в процесс оценки построение моделей машинного обучения. Это позволяет производить выбор признаков максимально быстро и применять алгоритмы фильтрации к самым большим наборам данных. Общая схема работы таких алгоритмов изображена на рисунке 5.

Кроме того, в последнее время во многих работах отдельно выделяют гибридные (hybrid) и ансамблирующие (ensembling) алгоритмы [29, 61, 62]. В случае гибридных алгоритмов различные алгоритмы выбора признаков объединяются последовательно, например, из большого набора признаков с помощью фильтра отбирается маленький, а затем из полученного набора с помощью обертки выбирается несколько наиболее значимых признаков [29, 75]. В ансамблирующих алгоритмах различные алгоритмы выбора признаков объединяются параллельно [30, 32, 62]. При этом объединение может происходить на нескольких уровнях, например, можно объединять уже отобранные различными алгоритмами выбора признаков наборы признаков в один общий набор, либо объединять модели машинного обучения, построенные на таких наборах [23].

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

Пусть объекты из описываются вектором признаков из множества За дача выбора признаков состоит в поиске наиболее подходящего для решаемой задачи набора признаков.

Более строго она может быть сформулирована как задача оптимизации при заданном критерии качества подмножеств признаков.

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

Во встраиваемых алгоритмах множество значимых признаков извлекается при обучении самого алгоритма машинного обучения . В алгоритмах фильтрации признаки оцениваются на основе некоторой МЗП. При этом по типу меры значимости алгоритмы фильтрации можно разбить на две группы [23]: мультивариативные и унивариативные. В мультивариативных фильтрах МЗП задана на множестве подмножеств признаков и задача оптимизации ставится следую щим образом

В унивариативных фильтрах выбор признаков производится без решения задачи оптимизаци. Вместо этого каждый признак оценивается МЗП за данной на а затем к упорядоченному по мере множеству признаков применяется некоторое отсекающее правило заданное на {( )} Пусть ( ) {( ( ))} тогда унивариативный фильтр возвратит подмножество ( )( ), где — знак, обозначающий композицию функций.

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

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

Seijo-Pardo В, Boln-Canedo V., Alonso-Betanzos, А. в статье [62] предложили следующий метод: шесть алгоритмов выбора признаков применялись к одним и тем же наборам данных, после чего задача получения итогового набора признаков была сведена авторами к трем последовательным шагам: объединить все полученные наборы признаков в единый массив, установить пороговое значение и применить классификатор.

В свою очередь, в [85] к задаче выбора признаков была применена иная версия метода роя частиц, подходящая для бинарных наборов данных (binary bare bones particle swarm optimization, binary BPSO). На 7 из 8 наборов данных, приведенных в статье, выбранный алгоритм показал хорошую среднюю точность классификации, а также хорошую устойчивость.

Другая вариация метода роя частиц описана в статье [56]. Ее стратегия отличалась тем, что рассматривала несколько разных роев частиц на одном про странстве решений одновременно, что обеспечивало его лучшее покрытие. Метод был назван Multi-Swarm particle swarm optimization (MSPSO), и интегрирован с методом опорных векторов и оценкой через -меру. Весь получившийся ансамбль был обозначен как улучшенный выбор признаков (improved feature selection, IFS). Сравнение метода было произведено со стандартным генетическим алгоритмом и различными алгоритмами поиска по сетке, на 10 стандартных тестовых наборах данных из открытых баз данных UCI и StatLog.

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

Авторы статьи [47] предложили применение муравьиного алгоритма для выбора бинарных признаков (advanced binary ant colony optimization, ABACO). Признаки в ABACO рассматривались как вершины графа, у каждой из которых были две подвершины: одна для выбора и вторая для отмены выбора признака. Каждый муравей посещает все вершины и на выходе получается бинарный вектор длины, равной количеству вершин, где единица стоит в случае, если вершина выбрана, и ноль, если не выбрана. Эффективность алгоритма сравнивалась с BGA, BPSO, CatfishBPSO, IBGSA, и несколькими альтернативными ACO-алгоритмами.

Алгоритмы оптимизации функции QC для метода MeLiF

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

Рассмотрим более подробно, как были адаптированы различные методы, перечисленные выше, для оптимизации коэффициентов { } по мере . В ал горитме MeLiF-1 и его модификациях для оптимизации была использована жадная модификация метода спуска. Экспериментально было установлено, что алгоритм MeLiF заканчивает свою работу не более чем за 100 вычислений меры .

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

Для решения поставленной задачи оптимизации генетический алгоритм был адаптирован следующим образом. В качестве особи выступал набор оптимизируемых коэффициентов { } . Для произведения кроссовера между двумя наборами коэффициентов и формируется новый набор коэффициентов, по очередно использующий коэффициенты из двух старых наборов. После произведения кроссоверов новые наборы коэффициентов добавляются в общий набор особей. То, какие именно особи будут производить кроссовер, выбирается из доли лучших особей. Вероятность выбора каждой отдельно взятой особи прямо пропорциональна разнице значений между целевыми функциями лучшей и худшей особями среди всех особей, входящих в . Мутация реализована как случайное изменение случайного элемента новой особи (набора коэффициентов) на с вероятностью . Для реализации элитизма некоторая доля лучших особей переходит без изменений в следующее поколение. Для того, чтобы адаптированный алгоритм учитывал некоторые свойства оптимизируемой величины, описанные выше, в качестве начальной популяции особей брались наборы коэффициентов вида ( ) и набор ( ).

Мутация проводилась с вероятностью 10% и в случае ее возникновения, значение некоторого коэффициента менялось на значение, отличающееся от исходного не более, чем на 0,1. Для осуществления кросс-валидации выбирались три набора коэффициентов, имеющих лучшую функцию приспособленности, а потом два из них переходили в следующее поколение благодаря элитизму.

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

Стартовыми же точками берутся точки вида ( ) и точка ( ). Кри терием останова для таких алгоритмов может выступать ограничение по числу пройденных шагов.

В данном методе также требуется задать пространство поиска и стартовые точки, но кроме них еще коэффициенты сжатия и растяжения симплекса, а также коэффициент отражения вершин . В качестве пространства поиска здесь также служит проективное пространство коэффициентов . Вершинами сим плекса в данном методе могут выступать точки вида ( ) и точка ( ). В качестве коэффициентов были выбраны стандартные [51]: коэффи циент отражения , коэффициент сжатия и коэффициент растяжения В качестве критерия останова для метода Нелдера-Мида может выступать как ограничение на число шагов, так и проверкой дисперсии набора точек. Данная проверка заключается в том, чтобы выяснить насколько близко друг к другу находятся на данном шаге вершины симплекса, и, если они сблизились достаточно, остановить алгоритм.

В роевых алгоритмах в качестве пространства поиска так же, как и в некоторых обозначенных ранее методах, выступает проективное пространство коэффициентов . Наборы коэффициентов вида ( ) и набор ( ) используются в качестве начальных «агентов» для роя. Кроме того, начальными «агентами» могут выступать случайные точки, находящиеся в пределах гиперкуба [ ] . Этот же гиперкуб задает границы пространства поиска роевых алгоритмов. Рассмотрим более подробно каждый отдельный роевой алгоритм, из приведенных в разделе 2.2.

Для метода роя частиц были использованы ( ) стартовых «агентов». Из них «агентов» соответствуют наборам коэффициентов вида ( ) и набору ( ), а еще «агентов» задаются случайно в гиперкубе [ ] . Остальные параметры метода были взяты из статьи [60], в которой было показано что эти параметры обеспечивают быструю сходимость метода за первые несколько шагов оптимизации. В светлячковом алгоритме были опробованы различные стартовые популяции, а в качестве параметров для алгоритма выступали параметры, указанные в статье [81], полностью посвященной исследованию светлячковых алгоритмов, которые также обеспечивают быструю сходимость метода за первые несколько шагов оптимизации. В методе роя жуков-светлячков также были опробованы несколько разных стартовых популяции. В качестве параметров для метода были выбраны указанные в статье [87] параметры, обеспечивающие быструю сходимость метода на первых шагах оптимизации.

Таблица 2 показывает результаты экспериментального исследования алгоритмов. Полная таблица с результатами экспериментов может быть найдена в приложении А.2. Эксперименты проводились на тех же наборах данных, что и в разделе 1.2 для алгоритма MeLiF-1. Для каждого эксперимента в таблице 2 приведено усредненное значение метрики AUC по нескольким запускам соответствующего алгоритма на соответствующем наборе данных. При запуске методы ограничивались в 100 вычислений оптимизируемой величины, чтобы приблизительно соответствовать по затратам вычислений алгоритму MeLiF-1. В качестве фильтрующих алгоритмов выбора признаков, на основе которых строилась новая МЗП, использовались следующие четыре алгоритма, изложенные в разделе 1.3: критерий соответствия, корреляция Спирмена, симметричная неопределенность и метрика значения разности. В таблице 2 следующие обозначения: – алгоритм MeLiF-1 обозначен, как MeLiF; – различные виды светлячковых алгоритмов обозначены как FA5 — алгоритм с пятью хорошими стартовыми точками, FA10 — алгоритм с пятью случайными и пятью хорошими стартовыми точками, FA5R — алгоритм с пятью случайными стартовыми точками, параметры всех алгоритмов взяты в соответствии с [81]; – различные варианты алгоритма роя жуков-светлячков GW1 – GW4, примененные с наборами параметров в соответствии с [87]; – различные варианты алгоритмов роя частиц PSO1 – PSO5, примененные с наборами параметров в соответствии с [60]; – генетический алгоритм GA, алгоритм Нелдера-Мида NM, поиск по шаблону PS, различные варианты метода спуска D1 и D2.

Из таблицы 2 видно, что роевые алгоритмы иногда обходят покоординатный спуск, однако нет ни одного, который бы превосходил предложенный алгоритм MeLiF-1 в пределах статистической погрешности. Вследствие этого во всех дальнейших исследованиях мы будем использовать жадный спуск.

Алгоритм GPSMeLiF

Предположим, что система мета-обучения, описанная в предыдущем разделе, построена. Приведем описание алгоритма выбора признаков GPSMeLiF.

После того, как для нового набора данных методом фиксированного радиуса были получены ближайшие к наборы данных из имеющихся в мета базе, нужно на основе данных о запусках алгоритма MeLiF-1 на этих наборах получить стартовую точку, которая хорошо подойдет для набора . Пусть методом фиксированного радиуса было отобрано новых наборов данных, для каждого из них нам известен набор оптимальных для них коэффициентов { } и набор мета-признаков . Тогда, данному набору данных можно присвоить не который вес, который будет обратно пропорционален расстоянию до него

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

Схема всего алгоритма GPSMeliF представлена на рисунке 8.

Для экспериментальной проверки работы алгоритма GPSMeLiF было использовано leave-one-out тестирование, при котором тестируемая мета-база строится на всех наборах данных, кроме одного, а затем проверяет получаемые результаты на этом наборе данных и так делает для всех наборов данных из имеющихся.

Всего при выборе ближайших наборов данных было выделено пять возможных результатов запуска алгоритма MeLiF-1 на выбранном наборе стартовых точек, ранжированных от лучшего к худшему. Рассмотрим более детально каждый из них:

– В первом случае выбранный стартовый набор коэффициентов совпадает с одним из лучших наборов, к которым сходится алгоритм MeLiF-1 на наборе данных . Это лучший из возможных результатов, так как после старта на таком наборе коэффициентов алгоритм MeLiF-1 практически сразу остановит свою работу.

– Во втором случае выбранный стартовый набор коэффициентов не совпадал ни с одним из лучших наборов, к которым сходится алгоритм MeLiF 1 на наборе данных , однако запущенный на нем алгоритм сходился к набору, качество которого выше, чем у получаемого исходным алгоритмом MeLiF-1. Данный результат также является очень хорошим, так как алгоритм получает не только лучший результат , чем исходный MeLiF-1, но и производит в среднем в пять раз меньше вычислений.

– В третьем случае выбранный стартовый набор коэффициентов не совпадал ни с одним из лучших наборов, к которым сходится алгоритм MeLiF 1 на наборе данных , однако запущенный на нем алгоритм сходился к набору, качество которого примерно совпадает с получаемым исходным алгоритмом MeLiF-1. Данный результат является достаточно хорошим, так как хоть алгоритм и не получает результат лучше, чем исходный MeLiF-1, но он производит в среднем в пять раз меньше вычислений.

– В четвертом случае выбранный стартовый набор коэффициентов не совпадал ни с одним из лучших наборов, к которым сходится алгоритм MeLiF на наборе данных , и запущенный на нем алгоритм сходился к набору, качество которого меньше, чем у исходного алгоритма MeLiF 1, однако выше, чем у методов фильтрации, которые он агрегирует. Данный результат является приемлемым, так как хоть алгоритм и не получает результат лучше, чем исходный MeLiF-1, но все еще лучше, чем результат агрегируемых методов и производит в среднем в пять раз меньше вычислений.

– В пятом случае выбранный стартовый набор коэффициентов не совпадал ни с одним из лучших наборов, к которым сходится алгоритм MeLiF-1 на наборе данных , и запущенный на нем алгоритм сходился к набору, качество которого меньше, чем у исходного алгоритма MeLiF-1 и меньше, чем у методов фильтрации, которые он агрегирует. Данный результат является крайне плохим, так как алгоритм не получает результат ни лучше, чем исходный MeLiF-1, ни чем агрегируемые методы. Суммируя, в случаях 1–3 GPSMeLiF давал результат лучше, чем MeLiF-1, в случае 4 результат оказался хуже MeLiF-1, но лучше всех объединяемых алгоритмов, и в случае 5 — хуже.

Диаграмма, приведенная на рисунке 9, показывает соотношение между всеми возможными случаями.

Построенная в итоге система в 97,1% случаев выбирала стартовую точку, при запуске из которой алгоритм выбора признаков MeLiF-1 превосходил объединяемые им алгоритмы. В 79,5% случаев система выбирала точку, при запуске из которой алгоритм MeLiF-1 получал результат не хуже, чем алгоритм, запускаемый из пяти стартовых точек. Следовательно, для сокращения затрачиваемого на вычисления времени, алгоритм можно запускать на одной стартовой точке, выбираемой системой мета-обучения.

Структура проекта

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

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

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

– абстрактный класс WekaClassifier, реализующий все процедуры и функции, являющиеся общими для других классов подпакета;

– класс WekaHoeffdingTree, реализующий дерево Хефдинга;

– класс WekaJ48, реализующий дерево J48;

– класс WekaKNN, реализующий метод k ближайших соседей;

– класс WekaLinearRegression, реализующий линейную регрессию;

– класс WekaLMT, реализующий логистическое дерево;

– класс WekaMultilayerPerceptron, реализующий многослойный персептрон;

– класс WekaPART, реализующий C4.5 дерево;

– класс WekaRandomFores, реализующий случайный лес;

– класс WekaSVM, реализующий метод опорных векторов;

– класс WekaNaiveBayes, реализующий наивный байесовский классификатор.

Пакет dataset содержит классы, необходимые для хранения и работы с наборами данных, используемых для построения моделей машинного обучения. В частности, класс Feature реализует столбец значений одного признака, этот класс затем используется для формирования набора данных через класс FeatureDataSet. Класс Instance реализует строку значений признаков для одного объекта, который затем используется для формирования набора данных через класс InstanceDataSet. Оба класса FeatureDataSet и InstanceDataSet являются наследниками абстрактного класса DataSet, который используется в классе DataSetPair для одновременного хранения обучающего и тестирующего наборов данных.

Пакет executor содержит классы, необходимые для корректного функционирования очереди с приоритетами. В частности, класс PriorityThreadPoolExecutor унаследован от Java ThreadPoolExecutor и является адаптацией стандартного пула потоков, а класс PriorityFutureTask позволяет увязать отдельно запускаемые потоки алгоритма PqMeLiF и данную реализацию пула потоков.

Пакет feature позволяет оценивать некоторый признак объектов в соответствии с заданными мерами значимости признаков и в зависимости от приведенного списка целевых значений для соответствующих объектов. Абстрактный класс RelevanceMeasure, находящийся в подпакете measure, позволяет любому классу, наследующему его, быть использованным в качестве МЗП для построения новой МЗП алгоритмами интерфейса MeLiF из пакета melif. Также в данном подпакете находятся различные реализации МЗП, используемые в диссертационном исследовании, в частности:

– FitCriterion, реализующий критерий соответствия;

– SpearmanRankCorrelation, реализующий корреляцию Спирмена;

– SymmetricalUncetainty, реализующий симметричную неопределеность;

– VDM, реализующий метрику значения разности.

Класс MeasureEvaluator реализует построение новой МЗП на основе МЗП, унаследованных от абстрактного класса RelevanceMeasure и коэффициентов { } , передаваемых в виде объекта класса Point из пакета result.

Пакет filter содержит абстрактный класс DataSetFilter при наследовании от которого можно реализовать отсекающее правило , которое при подаче на вход набора данных и некоторой МЗП позволяет получить отфильтрованный набор данных по входной МЗП и реализованному отсекающему правилу. Классы Per-centFilter и PrefferedSizeFilter, унаследованные от класса DataSetFilter, реализуют отсекающие правила по проценту от общего числа признаков и по выбранному числу признаков.

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

– BasicMeLiF, реализующий алгоритм MeliF-1;

– ParallelMeLiF, реализующий алгоритм MeLiF+;

– PriorityQueueMeLiF, реализующий алгоритм PqMeLiF;

– MultiArmedBanditMeLiF, реализующий алгоритм MaMeLiF.

Пакет policy содержит абстрактный класс BanditStrategy, который позволяет реализовать различные стратегии для выбора ручек многорукого бандита в алгоритме MaMeLiF. В частности, в пакете реализованы следующие классы, унаследованные от абстрактного класса BanditStrategy:

– EpsilonGreedy, реализующий эпсилон-жадную стратегию;

– SoftMax, реализующий SoftMax стратегию;

– UCB1, реализующий UCB1 стратегию;

– UCBTuned, реализующий стратегию UCB1 с отложенным выигрышем.

Пакет result содержит различные классы, необходимы для хранения и передачи всевозможной дополнительной информации. Класс EvaluatedFeature содержит описание признака со значением некоторой МЗП данного признака. Классы OptimizationPoint и PriorityPoint, унаследованные от абстрактного класса Point, реализуют хранение некоторого набора коэффициентов { } , но второй класс также хранит значение приоритета, используемого в алгоритмах MaMeLiF и PqMeLiF. Класс SelectionResults хранит информацию об отобранном списке признаков, их порядок по некоторой МЗП и информацию об этой МЗП. Класс RunStats хранит информацию о запуске некоторого алгоритма выбора признаков.

Пакет splitter позволяет дробить исходный набор данных на обучающий и контрольный наборы. Классы OrderedSplitter и RandomSplitter, унаследованные от абстрактного класса DataSetSplitter, реализуют соответственно скользящий контроль по k стратам и разбиение на случайные поднаборы.

Пакет folds содержит абстрактный класс FoldsEvaluator и класс SequenialEvaluator, которые реализуют оценку МЗП на заданном наборе данных, разбитым на несколько экспериментов при помощи DataSetSplitter из пакета splitter.

Корневой пакет содержит точку входа и некоторые ключевые классы программного комплекса. Класс ScoreCalculator вычисляет по некоторой метрике, например качество построенной модели. Класс DatasetTransformer формирует из входного набора данных набор в формате, обрабатываемом впоследствии другими частями программного комплекса. Класс AlgorithmConfig содержит некоторую информацию запускаемой из точки входа конфигурации. Класс ParallelRun-ner позволяет пользоваться логированием информации в многопоточной среде программного комплекса. Класс Main является основной точкой входа для консольного интерфейса.

Пакет metaLearning состоит из четырех пакетов и нескольких классов, находящихся в корневом пакете. Перечислим и кратко опишем каждый из пакетов.

Пакет metaKnowledge содержит классы, позволяющие работать с мета-признаками, а также реализующие сами мета-признаки. Класс MetaExtracter извлекает из наборов данных заданные мета-признаки, класс MetaNormalizer их нормализует. Класс MetaDistanceCalculator позволяет вычислять расстояния между наборами данных по заданным мета-признакам.