Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/



программный эпигенетический алгоритм дисперсионный



1

Аннотация

Целью данной выпускной квалификационной работы является разработка исследовательского программного(ПО) обеспечения для распознавания паттернов, позволяющего выявить корреляцию между вторичными структурами ДНК и эпигенетическими факторами, методами машинного обучения для кластеризации “без учителя”. Разработанное ПО будет использоваться учеными биологами как инструмент в исследовании вторичных структур ДНК человек. В работе так же были проанализированы алгоритмы классификации и исследованы зависимости характеристик, обучающих данных с прогнозируемой способностью методов. Наилучший алгоритм классификации был выбран и встроен в ПО для решения задач классификации. В этой научно-исследовательской работе для анализа наборов данных и классификатора шаблонов использовались библиотеки Pandas, NumPy, LightGBM, Sklearn, Scikit-learn и Matplotlib.

Возможности программы:

- Нахождение областей корреляции между вторичными структурами ДНК и их эпигенетическими факторами.

- Вывод результата в графической форме.

- Возможность создания пользователем кластеризации.

- Создание модели классификации.

- Нахождение паттернов.

- Создание файла отчета.

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

Объём отчёта по выпускной квалификационной работе, не включая приложения, составляет - 59 страниц. Количество таблиц в работе - 13, иллюстраций - 43, использованных источников - 32.



Annotation

The purpose of this final qualification work is developing research software(Software) the software for the recognition of patterns allowing to reveal correlation between secondary structures of DNA and epigenetic factors, methods of machine learning for a clustering "without teacher". Developed Software it will be used by erudite biologists as the tool in a research of secondary structures of DNA of people. The best algorithm of classification was chosen and built-in in Software for the solution of problems of classification. In this final qualification work for the analysis of data sets and the qualifier of templates Pandas, NumPy, LightGBM, Sklearn, Scikit-learn and Matplotlib libraries were used.

Possibilities of the program:

— Finding of areas of correlation between secondary structures of DNA and their epigenetic factors and result conclusion in a graphic form.

— Possibility of creation by the user of a clustering.

— Creation of model of classification and finding of patterns.

— Creation of the file of the report.

At the first stage of work preparation of data has been made for the further analysis. At the second stage has been written the cross-platform application by means of which regularities have been found and the correlation between them is counted. Highly correlating sites were included into a basis of the training selection in which 84 parameters for each gene in the site are counted. Also the user interface for convenience of work with the program has been written. All computing code is written on Python, and the user interface has been created by means of Tkinter library.

The volume of the report on final qualification work, not including applications, is - NN pages. The number of tables in work - 59, illustration - 43, the used sources - 32.



• Оглавление
• Введение
• 1. Обзор готовых средств
• 2. Вторичные структуры ДНК их эпигенетические данные
• 2.1 Первичные структуры ДНК
• 2.2 Вторичные структуры ДНК и их эпигенетические факторы
• 3. Описание методов обработки данных
• 3.1 Подсчет плотности
• 3.2 Нахождение паттернов
• 3.3 Подсчет параметров генома
• 3.4 Использование многопоточности
• 4. Машинное обучение в биоинформатике
• 4.1 Метрики оценки качества классификации
• 4.2 Линейная регрессия
• 4.2.1 Теория
• 4.2.2 Результаты
• 4.3 Логистическая регрессия
• 4.3.1 Теория
• 4.3.2 Результаты
• 4.4 Метод KNN
• 4.4.1 Теория
• 4.4.2 Результаты
• 4.5 Градиентный бустинг
• 4.5.1 Теория
• 4.5.2 Результаты
• 4.6 Метод опорных векторов
• 4.6.1 Теория
• 4.6.2 Результаты
• 4.7 Метод Lasso
• 4.7.1 Теория
• 4.7.2 Результаты
• 4.8 Случайный лес
• 4.8.1 Теория
• 4.8.2 Результаты
• 4.9 Оценка качества обучающей выборки
• 4.10 Сравнение методов и выбор метода классификации
• 5. Описание интерфейса
• 5.1 Сравнение библиотек
• 5.2 Используемые методы GUI
• 6. Результат работы
• 7. Описание вклада каждого участника
• Заключение
• Список литературы


Введение

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

В соответствии с материалами [1], предоставленными Всемирной организацией здравоохранения (ВОЗ), секвенированный файл ДНК человека занимает объем в 3,2 ГБ информации. Ежегодно количество таких данных растет, а количество биологов остается, примерно, таким же. Обнаружение консервативных позиций вторичных структур ДНК представляет интерес для эволюционных исследований последовательности генома так как указывает на их функциональную значимую роль.

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

Целью работы является разработка исследовательской системы для анализа геномных данных человека, основываясь на уже найденных закономерностях во вторичных структурах ДНК, и имеющейся аннотации генома человека эпигенетическими факторами, которое способно рассчитывать различные параметры генома и алгоритмов обнаружения паттернов между вторичными структурами ДНК и другими функциональными элементами генома с помощью методов машинного обучения [2], а также написание GUI приложения для простоты взаимодействия с пользователем. Готовая технология может использоваться биологами в качестве инструмента автоматического анализа.



1. Обзор готовых средств

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

Рассмотрим три основных программы по анализу геномных данных:

- ChromaSig;

- ChromaHMM;

- Bedtools.

ChromaSig - программа которая работает с картированными данными, получаемыми в результате экспериментов технологий секвенирования следующего поколения (NGS) [3].

Основными преимуществами программы ChromaSig являются:

- может находить коррелирующие между собой области хроматиновых сигнатур;

- может создавать отчеты в виде иллюстрированного pdf файла.

Основными недостатками программы ChromaSig являются:

- не имеет пользовательского интерфейса;

- отсутствие возможности кластеризации и классификации;

- не поддерживается с 2008 года.



Рис. 1. ChromaSig.Отчет по анализу. Распределение хроматиновых структур.

ChromaHMM - программа для изучения и характеристики состояний хроматина [4].

Основными преимуществами программы ChromaHMM являются:

— различный анализ цепочки ДНК;

— использование скрытых цепей Маркова для анализа данных;

— создание отчетов в виде различных файлов.

Основными недостатками программы ChromaSig являются:

— отсутствие пользовательского интерфейса;

— не умеет работать со вторичными структурами ДНК.

Рис. 2. ChromaHMM. Пример отчета.

BedTools - многофункциональная программа для работы функциональными аннотациями генома, а также результатами экспериментов NGS в широко используемом формате файлов .bed  [5].

Основными преимуществами пакета bedtools являются:

— позволяет производить различные манипуляции над геном (объединение, дополнение, подсчет вхождений, перемешивание и т. п.);

— статистический анализ цепочек.

Основными недостатками пакета bedtools являются:

— нет графического интерфейса;

— отсутствие возможности кластеризации и классификации.

Рис. 3. BedTools. Пример одной из команд.

Сравнение существующих проектов приведено в Таблице 1.

Таблица 1.

Сравнение существующих технических решений.

Проект	Пользовательский интерфейс	Кластеризация	Классификация
ChromaSig	-	+	-
ChromaHMM	-	-	-
Bedtools	-	+	-

Из Таблицы 1. видно, что ни одна программа не имеет пользовательского интерфейса, не производит анализ классификации, а ChromaSig и Bedtools могут производит кластеризацию.

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



2. Вторичные структуры ДНК их эпигенетические данные

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

4.1 Первичные структуры ДНК

Первичные структуры ДНК - это линейная последовательность нуклеотидов ДНК в цепи [6]. Последовательность нуклеотидов в цепи ДНК записывают в виде буквенной формулы ДНК. Каждая буква представляет собой нуклеотид, их четыре вида: A - аденин, T - тимин, G - гуанин, C - цитозин. Саму первичную последовательность ДНК получают из секвенатора, процесс получения первичной последовательности называется секвенированием.

Секвенирование - определение аминокислотной или нуклеотидной последовательности (от лат. sequentum -- последовательность) [6]. В результате секвенирования получают формальное описание первичной структуры линейной макромолекулы в виде последовательности мономеров в текстовом виде. Файл, в котором хранятся структуры ДНК имеет расширение *.bed [7]. Если секвенатор не смог разобрать нуклеотид, он обозначается как N - not available (с англ. - недоступный).

Пример первичной структуры ДНК в текстовом виде (Рис. 4).

Рис. 4. Пример первичной структуры ДНК в текстовом виде.

4.2 Вторичные структуры ДНК и их эпигенетические факторы

Вторичные структуры ДНК - две параллельные полинуклеотидные цепи, закрученные вокруг общей оси [8]. Такая пространственная структура удерживается множеством водородных связей, образуемых азотистыми основаниями, направленными внутрь спирали. Кроме канонической правозакрученной спирали, так называемой B-формы ДНК, в настоящее время показано, что ДНК способна образовывать множество альтернативных структур, таких как структуры стебель-петля, квадруплексы, триплексы, а также H-форму и Z-форму. В настоящей работе мы будем анализировать один класс вторичных структур ДНК, так называемые, структуры стебель-петля.

Эпигенетические факторы - факторы которые влияют на активность экспрессии определенных генов на нескольких уровнях, что приводит к изменению фенотипа клетки или организма. Существует множество различных эпигенетических факторов: метилирования, модификация гистонов, положение хроматина. В данной работе были взяты файлы консорциумного проекта The Epigenomics Roadmap, содержащие аннотацию генома местами связывания с ферментом ДНК-азой (HDNase). Данная эпигенетическая разметка позволяет определить места открытого и закрытого хроматина, которые специфичны для каждого типа ткани.

Аннотация генома вторичными структурами ДНК и эпигенетическими факторами хранится в виде *.bed файлов, которые представляют собой информацию о расположении хромосом в гене, где под расположением хромосомы в гене понимается название хромосомы и её координаты начала и конца базовой пары. Базовая пара - пара нуклеотидов, соединенных между собой. Вторичные структуры ДНК состоят из комплементарных пар оснований, соединенных между собой по определенным правилам).

Пример содержания файла вторичных структур ДНК и их эпигенетических факторов (Рис. 5).



Рис. 5. Содержание файла вторичных структур ДНК и их эпигенетических факторов.

Пример биологического представления вторичных структур (Рис. 6).

Рис. 6. Виды вторичной структуры ДНК.



3. Описание методов обработки данных

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

4.3 Подсчет плотности

В данной выпускной квалификационной работе также проверяется гипотеза о том, что существует взаимосвязь между вторичными структурами ДНК и эпигенетическими факторами в виде некоторой корреляции по плотности расположения внутри хромосомы. Что такое плотность расположения функционального элемента внутри хромосомы? Плотностью расположения функционального элемента внутри хромосомы считается процентное соотношение покрытия некоторого участка, например, от 10 до 25 оснований, функциональным элементом. Так же бывают случаи, когда на рассматриваемом участке функционального элемента нет, и тогда покрытия и нет вовсе.

По данным аннотации вторичными структурами ДНК и эпигенетическими факторами были посчитаны значения плотности распределения вторичных структур ДНК и эпигенетических факторов для каждого из видов данных. Для подсчета плотностей в геноме, были взяты 22 файла генома человека, где одна хромосома записана в одном файле. В каждом файле аннотации генома вторичными структурами ДНК или эпигенетическими факторами, в среднем, может содержаться от 3-х до 5-ти миллионов ридов - строк. Подсчет плотностей производился для окна размером 10 kB, то есть бралось окно в 10 000 пар оснований, и плотность распределения рассчитывалась для этого окна.

Расчет плотностей был произведен по следующему алгоритму (алг. 1):



Алгоритм 1. Подсчет плотностей распределения функциональных элементов на хромосоме.

На выходе после алгоритма расчета плотностей был получен файл следующего содержания (Рис. 7).

Рис. 7. Файл плотностей функциональных элементов на хромосоме.

4.4 Нахождение паттернов

После нахождения распределения плотностей функциональных элементов на хромосомах в геноме человека для каждого из файлов, был написан алгоритм [9,10] для дальнейшего поиска корреляции между двумя заданными аннотациями (алг. 2 - 3).

Алгоритм 2. Алгоритм сравнения двух данных по плотностям пиков.



Алгоритм 3. Алгоритм сравнения двух данных по плотностям впадин.

Также было реализовано визуальное отображения распределения плотностей функциональных элементов (Рис. 8). По О(х) - координаты пар оснований, по О(у) - значение плотности распределения. Участки графика, где плотность равняется нулю свидетельствует о том, что данный участок не был обработан секвенатором в виду технических сложностей. Обычно такие участки находятся в начале и конце хромосом и в области цетромер.

Рис. 8. Графики плотности распределения функциональных элементов.



Был реализован отдельный вывод ненормализованных и уже нормализированных участков двух графиков с корреляцией более 80%, а также вывод значения корреляции для этого участка, его номера из всех участков и его тип (Рис. 9). Все найденные участки паттернов делятся на четыре типа:

— пик первого графика совпадает с пиков второго графика;

— пик первого графика совпадает с впадиной второго графика;

— впадина первого графика совпадает с пиков второго графика;

— впадина первого графика совпадает с впадиной второго графика.

Рис. 9. Вывод найденных паттернов.

4.5 Подсчет параметров генома

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

На первой хромосоме генома человека присутствует 250 миллионов строк хранящиеся в формате *.bed, а подсчет параметров производился над данными первичной последовательности ДНК, которые хранятся в виде текстовых файлов заполненных цепочками нуклеотидов (A,T,G,C). Объем полного генома занимает 3,2 Гб текста, состоящего из символов (A,T,G,C). Для того что бы посчитать 20 различных параметров генома берется одна запись интервала из файла вторичных структур, считывается область интервала и сопоставляются с файлом первичной последовательности генома, где во взятой области подсчитывается количество вхождений различных комбинаций символов (A,T,G,C) с длиной конечной строки от 1 до 3-х символов.

Таким образом был написан алгоритм решающий эту задачу (алг. 4).

Алгоритм 4. Подсчет параметров.

На выходе приведенный выше алгоритм создает файл отчета со следующей структурой (Рис. 10).



Рис. 10. Ген с подсчитанными параметрами.

4.6 Использование многопоточности

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

После изучения раздела о многопоточности языка Python [11], а также упрощению и замене используемых функций на более быстрые, алгоритм подсчета параметров был переписан под возможность использования восьмиядерного ПК (алг. 5).



Алгоритм 5. Оптимизированный алгоритм подсчета параметров.

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



5. Машинное обучение в биоинформатике

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

Алгоритмы классификации бывают 2 типов:

— С учителем (Supervised)

— Без учителя (Unsupervised)

Методы классификации Unsupervised (без учителя) анализируют входные данные с целью разбиения их на классы (группы) так, чтобы внутри одного класса оказывались наиболее родственные объекты, а различные объекты попадали в различные классы. В реализации данного метода отсутствует “учитель”, представляющую из себя обучающее подмножество объектов и заранее известное множество исходов. Методы классификации без “учителя” являются алгоритмами кластеризации, которые должны самостоятельно принимать решения о составе и количестве исходных классов (групп родственных объектов). В рамках нашей дипломной работы кластеризацию (разделение на группы) делает пользователь по несколько объектов разных классов, поэтому мы не будем уделять внимание на алгоритмы кластеризации, а рассмотрим следующие алгоритмы методов машинного обучения с “учителем” (Supervised):

— Линейная регрессия

— K-ближайших соседей

— Деревья принятия решений

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

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

— Для демонстрации работы алгоритмов и их оценки, создадим тестовую выборку, по которым будем обучать модели и оценивать их качество прогнозирования;

— Рассмотрим методы оценки качества обучающей выборки

— Рассмотрим метрики оценки качества классификации

— Опишем алгоритмы машинного обучения и сделаем оценку качества классификации

— Сравним методы классификации и выберем один метод для использования в программном обеспечении

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

5.1 Метрики оценки качества классификации

Для анализа метрик оценки качества классификации рассмотрим все методы, использованные в данной работе, в примере бинарной классификации, где каждый объект относятся одному из множества классов {0, 1}. Для описания оценочных метрик введем концепцию, как матрица ошибок (табл. 2) [13,14], где - это предсказанный метка классификации; - истинное значение класса на объекте. Таблица 2. содержит следующую информацию:

— TP (True Positive) - истинное положительное предсказание;

— FP (False Positive) - ложное положительное предсказание;

— FN (False Negative) - ложное отрицательное предсказание;

— TN (True Negative) - истинное отрицательное предсказание.



Таблица 2.

Матрица ошибок.

	b = 1	b = 0
a = 1	TP	FP
a = 0	FN	TN

Исходя из таблицы можно сделать вывод, что FN и FP - это ошибки классификации, а TP и TF правильные ответы.

Рассмотрим следующие метрики:

— Среднеквадратичная ошибка

— Доля правильных ответов

— Точность

— Полнота

— F-мера

— AUC-ROC

Среднеквадратичная ошибка (Mean Squared Error) высчитывается по следующей формуле:

	(1)

где - предсказанное значение классификации для i-го объекта,

- истинное значение i-го объекта.

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

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

	(2)

Точность (precision) показывает долю реально положительных ответов, от количества правильных ответов классификации. Данная метрика высчитывается по следующей формуле:

	(3)

Полнота (recall) показывает долю правильных ответов классификации от всех правильных ответов. Данная метрика высчитывается по следующей формуле:

	(4)

F-мера показывает гармоничную среднюю оценку между точностью и полнотой. Данная метрика высчитывается по следующей формуле:

	(5)

Area Under Curve Receiver Operating Characteristic (AUC-ROC) показывает оценку модели без привязки к конкретному порогу. Данный метод с визуальной точки зрения является некой площадью под кривой ошибок, которая ограничивается линиями, координаты которого (0, 0) и (1, 1), и значением TPR и FPR в этих координатах.

TPR (True Positive Rate) высчитывается аналогично как полноте по следующей формуле:

	(6)



FPR (False Positive Rate) показывает долю неправильно предсказанных классов из негативного класса и высчитывается по следующей формуле:

	(7)

Когда классификатор не ошибается, то значение FPR = 0, а TPR = 1. В этом случае можно получить площадь под кривой равную единице (Рис. 11).

Когда классификатор будет выдавать случайные значения, то кривая будет стремится к прямой, построенная по точкам (0, 0) и (1, 1), значение ROC к 0,5.

AUC-ROC можно еще толковать как вероятность предсказанной метрики будет положительным у истинного объекта положительного класса будет больше, чем у истинного объекта отрицательного класса.

Рис. 11. Площадь AUC-ROC.

В Таблице 3 приведены значения типов оценки для лучшей модели. При выборе метода классификации будем пользоваться этой таблицей (табл. 3).



Таблица 3.

Значение оценки для лучшей модели.

Тип оценки	Для лучшей модели она будет
Среднеквадратичная ошибка	Наименьшей
Доля правильных ответов	Наибольшей
Точность	Наибольшей
Полнота	Наибольшей
Площадь AUR-ROC	Наибольшей

5.2 Линейная регрессия

5.2.1 Теория

Линейная регрессия (метод наименьших квадратов) -высчитывает параметры w и b, для минимизации среднеквадратичной ошибки (mean squared error) между фактическими ответами из обучающего набора и спрогнозированными [15]. Среднеквадратичная ошибка равна сумме квадратов разностей между фактическими и спрогнозированными значениями. Линейная регрессия довольно проста, что является преимуществом, но в то же время у нее нет инструментов, позволяющих контролировать сложность модели.

Уравнение оценивающие линию простой (парной) линейной регрессии:

	(8)

где - предикт или независимая переменная,

- переменная отклика или зависимая переменная,

- свободный член линии оценки,

- градиент оценённой линии.

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

Метод наименьших квадратов (МНК) является одним из самых простых методов определения коэффициентов и . Оценивание подгонки осуществляется за счет, рассматривая остатки - вертикальное расстояние каждой точки от линии.

Линию подгонки выбирают так, чтобы сумма квадратов остатков была минимальной (Рис. 12).

Рис. 12. Линия линейной регрессии с изображенными остатками (вертикальные пунктирные линии).

5.2.2 Результаты

Результаты работы модели машинного обучения построенной методом линейной регрессии (табл. 4).

Таблица 4.

Результаты модели на основе линейной регрессии

Среднеквадратичная ошибка:	0.34
Доля правильных ответов:	0.7
Точность для класса 1:	0.74
Точность для класса 0:	0.64
Полнота:	0.69
F-мера:	0.71
AUC-ROC:	0.66

Линейная регрессия сделала предсказание (скоринг) объектов класса 1 ближе к значению 1, а объектов класса 0 ближе к значению -1, как это показано на Рис.13, поэтому и среднеквадратичная ошибка равна 0.34, а точность модели 70% по F-мере.

Рис. 13. Выходные ответы модели.

5.3 Логистическая регрессия

5.3.1 Теория

Логистическая регрессия - метод предсказания события с помощью построения логистической функции. Впервые данный метод использовали для описания роста численности популяции [16]. Эту модель относят к методам бинарной классификации. Построение модели заключается в составлении уравнения логистической регрессии. Входные данные линейно объединяются с помощью весовых коэффициентов и начальных значений.

где, - это некий входной параметр, линейный коэффициент, начальное смещение.

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



5.3.2 Результаты

Результаты работы модели машинного обучения построенной методом логической регрессии (табл. 5).

Таблица 5.

Результаты модели на основе логической регрессии

Среднеквадратичная ошибка:	0.17
Доля правильных ответов:	0.61
Точность для класса 1:	0.64
Точность для класса 0:	0.7
Полнота:	0.6
F-мера:	0.62
AUC-ROC:	0.67

Логистическая регрессия сделала предсказание (скоринг) объектов класса 1 значением 1, а объектов класса 0 значением 0, как это показано на Рис.14, поэтому и среднеквадратичная ошибка равна 0.17. Точность модели 61%.

Рис.14. Выходные ответы модели.

5.4 Метод KNN

5.4.1 Теория

Метод классификации K-ближайших соседей (K-Nearest Neighbors KNN) основывается на гипотезе, которая предполагает, что объекты одного класса в пространстве будут находится рядом друг с другом и образуют компактную область, а области различных классов не будут пересекаться [17,18]. Исходя из этой гипотезы можно делать вывод, что прогнозируемый объект имеет схожую метку класса с соседними классами из обучающей выборки. Алгоритм KNN относит прогнозируемый объект к преобладающему классу его соседей число который можно передавать в алгоритм как значение k. Когда k = 1прогнозируемый объект будет относится к ближайшему ему объекту. Этот алгоритм определяет границы между группами локально и тем самым лучше справляется с несвязанными и несферическими классами. Область каждого класса в пространстве представляется как выпуклый многогранник. (Рис. 15). На рисунке алгоритм пытается определить класс новому объекту (Отмечена звездочной), которая попадает в область группы “треугольник”, при k = 1 новому объекту будет присвоен класс “треугольник”, а при k = 3 класс “кружок”. Значение k нужно выбирать экспериментальным способом, где качество классификации на тестовых данных будет наивысшей (алг.6).

Рис. 15. Работа алгоритма.



Алгоритм 6. Метод KNN.

5.4.2 Результаты

Результаты работы модели машинного обучения построенной методом KNN (табл. 6).

Таблица 6.

Результаты модели на основе метода KNN

Среднеквадратичная ошибка:	0.21
Доля правильных ответов:	0.75
Точность для класса 1:	0.8
Точность для класса 0:	0.7
Полнота:	0.72
F-мера:	0.76
AUC-ROC:	0.75

Для поиска оптимального значения k, которая является основным параметром KNN, был использован класс GridSearchCV - поиск наилучшего параметра (рис. 16), предоставляющий минимальную ошибку cross-validation (перекрестного контроля). Например, результатом поиска наилучшего значения k из [1, 3, 4, 5, 6, 7, 8, 10, 15] является значение 7, а ошибка перекрестного контроля равняется 13,1%, что даже больше ошибки на тестовые выборки для значения k = 3, причиной этому служит то, что для построения моделей в схеме перекрестного контроля используются не все данные.

Рис. 16. Поиск оптимального параметра с помощью cross-validation.

Методом ручного перебора было найдено наилучшее значение k = 3, с этим значением ошибка на тестовых данных начала составлять 16% (Рис. 17).

Рис. 17. Ошибка KNN на тренировочных и тестовых данных при k = 3.

При значении k = 7, ошибка на тестовых данных составляет 18,1%. (Рис. 18)

Рис. 18. Ошибка KNN на тренировочных и тестовых данных при k = 7.



5.5 Градиентный бустинг

5.5.1 Теория

Бустинг - последовательное построение композиции алгоритмов машинного обучения, когда каждый следующий алгоритм стремится погасить недостатки композиции всех предыдущих алгоритмов [19]. Бустинг основан на жадном алгоритме построения композиции. Понятие бустинга изначально возникло в работах по практически точному обучению в связи с вопросом: возможно ли, располагая множеством плохих (не сильно отличающихся от случайных) алгоритмов обучения, получить один хороший.

С точки зрения качества классификации бустинг над решающими деревьями считается одним из самых эффективных методов. По мере наращивания композиции на независимой тестовой выборке во многих экспериментах наблюдалось практически неограниченное уменьшение частоты ошибок. Даже после достижения безошибочного распознавания всей обучающей выборки качество на тестовой выборке часто продолжало улучшаться. Это перевернуло существовавшие на тот момент представления о том, что для повышения обобщающей способности необходимо ограничивать сложность алгоритмов. На примере бустинга было выяснено, что хорошим качеством могут обладать сколь угодно сложные композиции, если правильно провести их настройку [20]. Алгоритм градиентного бустинга (алг. 7).



Алгоритм 7. Градиентный бустинг. Построение композиции.

5.5.2 Результаты

Результаты работы модели машинного обучения построенной методом градиентного бустинга (табл. 7).

Таблица 7.

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

Среднеквадратичная ошибка:	0.11
Доля правильных ответов:	0.68
Точность для класса 1:	0.72
Точность для класса 0:	0.73
Полнота:	0.66
F-мера:	0.69
AUC-ROC:	0.72

Алгоритм Градиентного бустинг сделал предсказание (скоринг) объектов класса 1 значением 1, а объектов класса 0 значением 0, как это показано на Рис. 19. Точность модели 68%.



Рис. 19. Выходные ответы модели.

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

5.6.1 Теория

Алгоритм опорных векторов (SVM, Support Vector Machines) - разработан В. Н. Вапником в 1990-е годы, производит поиск в векторном пространстве документов разделяющей поверхности двух классов, которая максимально удалёна от всех точек обучающего выборки [21, 22]. Зазор классификации - расстояние между найденной поверхностью и ближайшей точкой данных.

В алгоритме опорных векторов решающая поверхность полностью определяется небольшим подмножеством документов. Опорными векторами называются элементы данного подмножества. Алгоритм ищет разделяющую поверхность, заданную уравнением:

	(9)

где - вектор весов или вектор нормали к разделяющей поверхности; b - параметр сдвига.

Обучающее множество представляет собой множество пар:

	(10)

где - это документы обучающего множества,

- это соответствующая метка класса, причём в алгоритме опорных векторов метка принимает одно из двух значений и . Тогда линейный классификатор описывается следующей формулой:

	(11)

где значение классификатора соответствует одному классу, а - другому; - тестовый документ.

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

Рис. 20. Разделяющая поверхность и опорные вектора.

Функция (11) принимает значение 1 для одного класса и -1 для другого. Учитывая условие максимизации расстояния от гиперплоскости до каждого класса, можно сформулировать задачу оптимизации, которая решается с помощью множителя Лагранжа.

,	(12)

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

,	(13)

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

5.6.2 Результаты

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

Таблица 8.

Результаты модели на основе метода опорных векторов 

Среднеквадратичная ошибка:	0.14
Доля правильных ответов:	0.82
Точность для класса 1:	0.79
Точность для класса 0:	0.83
Полнота:	0.84
F-мера:	0.81
AUC-ROC:	0.82

Модель на основе метода опорных векторов сделала предсказание (скоринг) объектов класса 1 значением 1, а объектов класса 0 значением 0, как это показано на Рис.21. Точность модели 81% по F-score.



Рис. 21. Выходные ответы модели.

5.7 Метод Lasso

5.7.1 Теория

Метод наименьших квадратов (МНК) сильно зависит от обучающих данных, поэтому он довольно неустойчив, и может проявлять тенденции к переобучению. Избежать переобучения помогает регуляризация - метод, заключающийся в применении дополнительных ограничений на искомые параметры, которые могут предотвратить излишнюю сложность модели. Смысл процедуры заключается в “стягивании” вектора коэффициентов , чтобы они в среднем оказались несколько меньше по абсолютной величине, чем это было бы при оптимизации по МНК.

Метод регрессии “лассо” (LASSO, Least Absolute Shrinkage and Selection Operator) заключается во введении дополнительного слагаемого регуляризации в функционал оптимизации модели, что позволяет получать более устойчивое решение [23]. Условие минимизации квадратов ошибки при оценке параметров выражается следующей формулой:

	(14)

где - параметр регуляризации, имеющий смысл штрафа за сложность.

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

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

5.7.2 Результаты

Результаты работы модели машинного обучения построенной методом Lasso (табл. 9).

Таблица 9.

Результаты модели на основе методом Lasso 

Среднеквадратичная ошибка:	0.45
Доля правильных ответов:	0.69
Точность для класса 1:	0.75
Точность для класса 0:	0.76
Полнота:	0.67
F-мера:	0.71
AUC-ROC:	0.74

Модель машинного обучения на основе алгоритма Lasso сделала предсказание (скоринг) объектов класса 1 ближе к значению 1, а объектов класса 0 ближе к значению -1, как это показано на Рис. 22, поэтому и среднеквадратичная ошибка равна 0.45, а точность остается модели 0.71 по F-мере.



Рис. 22. Выходные ответы модели.

5.8 Случайный лес

5.8.1 Теория

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

Выбирается подвыборка обучающей выборки (м.б. с возвращением) - по ней строится дерево (для каждого дерева -- своя подвыборка). Для построения каждого расщепления в дереве просматриваем max_features случайных признаков (для каждого нового расщепления -- свои случайные признаки).

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

Алгоритм случайного леса может быть представлен в следующем виде (алг. 8) [24]:



Алгоритм 8. Построение случайного леса.

5.8.2 Результаты

Результаты работы модели машинного обучения построенной методом случайного леса (табл. 10).

Таблица 10.

Результаты модели на основе метода случайного леса 

Среднеквадратичная ошибка:	0.22
Доля правильных ответов:	0.72
Точность для класса 1:	0.78
Точность для класса 0:	0.7
Полнота:	0.75
F-мера:	0.743
AUC-ROC:	0.47

Модель машинного обучения на основе алгоритма Random Forest сделала предсказание (скоринг) объектов класса 1 значением 1, а объектов класса 0 значением 0, как это показано на Рис.23. Точность модели для 0 класса высока и равна 72%.

Рис. 23. Выходные ответы модели.

5.9 Оценка качества обучающей выборки

График quantile-quantile (QQ) показывает нормальное распределение данных, распределение Гауса. Если точки находятся близко к базовой линии, проходящая под углом 45°, то это говорит, что данные распределены нормально. На рисунке (Рис. 24) можем увидеть распределение параметра A (Аденин) матрицы признаков, она не нормально распределена. Так же при проверке выяснилось, что все остальные параметры не нормально распределены. Из этого следует, что все параметры обучающей и тестовой выборки надо нормализовать [25].

Рис. 24. График Quantile-Quantile для параметра A в матрице признаков.

В матрицу переменных еще добавили и длину каждого рида, как разность между значением конечным и начальным расположения рида в геноме, это параметры end и begin соответственно. После этого у нас матрица признаков состоит из 85 параметров по которым обучается или предсказывает модель.

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

Рис. 25. Матрица корреляции для всей матрицы признаков.

Для визуальной оценки взаимосвязи признаков между собой, можно рассматривать матрицу рассеяния, в котором указаны распределения точек (Рис. 26).

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



Рис. 26. Матрица рассеивания динуклеотидов.

Далее рассмотрим применение алгоритмов машинного обучения, методы выбора наилучших признаков из матрицы признаков и параметров для алгоритмов. Размерность обучающей выборки составило 3988 строк на 85 столбцов-признаков, а размерность тестовой выборки 1710 строк на 85 столбцов-признаков. После разбиения изначальных данных на тестовую и обучающую выборку, надо нормализовать все признаки в них. Это необходимо для обучения и тестирования модели, так как некоторые модели машинного обучения не всегда корректно работают с ненормализованными данными. В итоге обучения и тестирования используемых нами алгоритмов классификации со всеми 85 параметрами получили Таблицу 11, где можно увидеть результаты точности каждой модели в этом шаге.



Таблица 11.

Качество алгоритмов классификации со 85 параметрами.

Модель	Средне-квадратичная ошибка	Доля правильных ответов	Точность класса 1	Точность класса 0	Полнота	F-мера	AUC-ROC
Линейная регрессия	0.22	0.65	0.42	0.66	0.07	0.13	0.538
Логистическая регрессия	0.34	0.645	0.39	0.66	0.08	0.14	0.509
Градиентный бустинг	0.29	0.64	0.36	0.662	0.07	0.11	0.504
SVM	0.31	0.658	0.4	0.661	0.01	0.02	0.502
Метод Lasso	0.225	0.65	0.2	0.66	0.001	0.003	0.55
Случайный лес	0.34	0.64	0.38	0.664	0.07	0.12	0.507
KNN (k = 1)	0.27	0.542	0.341	0.661	0.37	0.35	0.501
KNN (k = 3)	0.21	0.569	0.34	0.66	0.28	0.31	0.5
KNN (k = 4)	0.27	0.62	0.367	0.664	0.13	0.19	0.507

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

Отбор признаков (Feature Selection) с помощью алгоритма случайного леса

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

Цели проведения отбора значимых признаков:

* лучшее понимание задачи, поскольку человеку проще разобраться с малым количеством признаков;

* ускорение уже работающих алгоритмов;

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

Можно осуществлять отбор значимых признаков как «вручную» -- на основе анализа постановки задачи, так и «автоматически» -- с помощью универсальных алгоритмов.

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

Все, что нужно сделать, - это после вызова метода predict для случайного леса прочитать поле feature_importances_. Для каждого признака это поле содержит число, выражающее значимость этого признака. Чем больше число, тем значимее признак. Сумма всех чисел равна 1.

На Рис. 27. Можно увидеть веса всех 84 признаков. Самым весомым признаком оказалась признак длина рида, которая была добавлена нами.

Рис. 27. Веса всех 84 признаков.

Из всех признаков было отобрано 35 наиболее весомые признаки, которые даны в списке: ['num', 'A', 'T', 'C', 'G', 'AA', 'TT', 'TA', 'AT', 'TG', 'AG', 'TC', 'CT', 'GG', 'CA', 'GT', 'AC', 'AAA', 'TTT', 'GA', 'CC', 'GC', 'AAT', 'ATG', 'TAA', 'ATA', 'TAG', 'ACA', 'ATT', 'TTG', 'CTT', 'TCA', 'CAG', 'TCT', 'CAT']. На Рис. 28 можно увидеть веса отобранных признаков.



Рис. 28. Веса отобранных признаков.

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

Рис. 29. Матрица корреляции между отобранными признаками.

При оценке алгоритмов классификации мы использовали 35 отобранных признаков. Самую высокую точность с обучением на 35 признаков показал алгоритм SVM, с точностью 0,81 по F-мере.

5.10 Сравнение методов и выбор метода классификации

В Таблице 12 приведены оценки качества алгоритмов машинного обучения, которые мы использовали. Для выбора наиболее точного метода было по точности F-мере, которая дает максимально объективную оценку и гармонную оценку между точностью и полнотой. По точности F-мера была выбрана модель SVM с точностью 0,81.

Таблица 12.

Качество алгоритмов классификации с 35 параметрами.

Модель	Средне-квадратичная ошибка	Доля правильных ответов	Точность класса 1	Точность класса 0	Полнота	F-мера	AUC-ROC
Линейная регрессия	0.34	0.7	0.74	0.64	0.69	0.71	0.66
Логистическая регрессия	0.47	0.61	0.64	0.7	0.6	0.62	0.67
Градиентный бустинг	0.34	0.68	0.72	0.73	0.66	0.69	0.72
SVM	0.14	0.82	0.79	0.83	0.84	0.81	0.82
Метод Lasso	0.45	0.69	0.75	0.76	0.67	0.71	0.74
Случайный лес	0.22	0.72	0.78	0.7	0.75	0.743	0.71
KNN	0.21	0.75	0.8	0.7	0.72	0.76	0.75

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