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

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

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

Оглавление

Введение

1. Новые методы прогнозирования финансовых рядов

1.1 Классические подходы к анализу финансовых рынков

1.2 Эконометрические модели

1.3 Появление новых методов анализа информации

1.4 Основные алгоритмы машинного обучения

2. Модель ансамблей классификационных деревьев для прогнозирования динамики финансовых временных рядов

2.1 Постановка практической задачи

2.2 Выбор алгоритма для анализа данных

2.3 Практическая реализация модели

Заключение

Приложения



Введение

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

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

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

Актуальность исследования:

Финансовые рынки с самого их появления являются объектом пристального изучения множества ученых. Изучению динамики фондовых рынков, вопросам анализа и прогнозирования цен финансовых активов посвящено множество работ таких видных ученых, как Дж.Линтнер , Ж.Моссин , Г.Марковиц , Дж.Тобин , У.Шарп , Э.Элтон и др.

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

С начала 1960-х годов в экономической области были применены, революционные на тот момент, эконометрические методы. Со временем они были имплементированы в области финансов. Качество оценки этих методов и прогностические способности удовлетворяли мировую финансовую отрасль. В преддверии кризиса 2008 года, 12 сентября, JPMorgan заявил, что рост ВВП США ускорится в начале 2009 года. Однако неожиданность кризиса, его непредсказуемость показала, что эконометрические методы не в силах дать объяснение и спрогнозировать подобные критические моменты в экономике. Именно неспособность классических методов к прогнозированию кризисных явлений создает предпосылки к рассмотрению широкого круга альтернативных методов.

В последние годы большую популярность,в среде исследователей и профессионалов финансового рынка, приобрело новое направление - машинное обучение (machinelearning). Существует много определений этой междисциплинарной области, однако по мнению автора наилучшее объяснение дал Артур Эль Самуэль (Samuel, 1959).

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

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

Гипотезой исследования является тезис о способности методов машинного обучения эффективно анализировать финансовые временные ряды и давать качественные прогнозы.

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

* изучить подходы к определению стоимости финансовых инструментов;

* рассмотреть этапы развития области исследования, выявить актуальную проблематику; моделирование финансовый рынок временной

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

* оценить применимость такого-то метода для прогнозирования американского рынка акций

* создать практическую модель, реализую избранную концепцию;

* разработать программную реализацию модели;

* исследовать прикладное значение разрабатываемой модели.

Объектом исследования являются инструменты фондового рынка, в частности обыкновенные акции американской компании Apple (биржевой тикет AAPL) и индекс американских компаний S&P 500. Этот инструмент можно считать наиболее точным приближением рынка Америки. Он включает в себя бумаги 500 наиболее крупных компаний Американского фондового рынка - наиболее развитого из мировых финансовых центров.

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

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



1.Новые методы прогнозирования финансовых рядов

1.1Классические подходы к анализу финансовых рынков

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

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

При анализе ценных бумаг принято выделять следующие уровни фундаментального анализа:

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

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

В фундаментальном анализе принято выделять следующие группы отраслей:

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

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

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

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

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

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

Другим направлением, которое развивалось в среде фондовых аналитиков, является технический анализ. Изначально технический анализ зародился, как узкое направление «чартистов» (от англ. сhart - график) - исследователей, строивших прогнозы на нарисованных от руки графиках. От наглядности построения цен активов во многом зависел результат анализа. Средства анализа были достаточно простыми - линии поддержки/сопротивления, выявление различных рыночных фигур и анализ циклов.

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

Основные постулаты были впервые сформулированы Чарльзом Доу в цикле статей в Wall Street Journal. В них он изложил свое видение анализа рынка, а также принципы, которые в последствии легли в основу технического анализа:

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

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

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

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

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

1.2 Эконометрические модели

Эконометрические модели являются одними из самых распространенных методов проведения анализа и прогнозирования экономических показателей. Впервые предложенный в 1910 году П. Сиомпом, термин «эконометрия», он описывал поведение экономических временных рядов их графическое отображение. Позднее, в 1933 году нобелевский лауреат Рагнар Фриш дал другое обозначение термину «эконометрика» - самостоятельное направление в экономической науке. Задачей этого нового направления являлось «развитие экономической мысли в ее связи со статистикой и математикой». В 50-х годах эконометрическое моделирование стало приоритетным направлением для ряда ведущих экономических университетов. В 60-х годах развитие данной направления экономической науки стало развиваться по пути их дифференциации по секторам и отраслям, что в последствии привело к все большему усложнению самих моделей. Итогом стал тот факт, что большинство развитых стран, начиная с 80-х годов, стали основывать свои экономические политики на основе эконометрических прогнозов.

Проблемами моделирования эконометрических систем и прогнозированием динамики основных макроэкономических показателей были заняты видные ученые того времени: Т. Браун, Зильнер, Дж. Джонсон, Хаавелмо, Мур,и др. Большой вклад внести и советские ученые: Ермилов А.П. и Чижов Ю.А. исследованием американского рынка на основе эконометрических моделей, Анчишин А.И. - прогнозированием динамики роста экономических показателей.

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

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

В эконометрике существует три класса методов:

1. Модель временных данных;

2. регрессионная модель с одним уравнением;

3. системы одновременных уравнений.

У всех этих моделей можно выделить общие этапы построения:

1. Определение целей и задач моделирования;

2. Формализация априорной информации;

3. выбор спецификации модели;

4. сбор количественной информации, ее фильтрация и обработка;

5. оценка параметров выбранной спецификации с последующим качественным анализом;

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

Прогнозирование финансовых временных рядов базируется на выборе адекватной модели, что является само по себе сложной задачей. В эконометрике существует большое разнообразие «стандартных» моделей. К ним относятся модели скользящего среднего порядка МА, авторегрессии порядка AR(p), смешанные модели авторегрессии и скользящего среднего порядка (p,q) - ARMA (p,q). Так, процесс ARMA выглядит следующим образом:

где = Yi - Yt;

ut - остаточный член ошибки в уравнении.

Базовой предпосылкой моделей ARMA является стационарность временных рядов, (наличие постоянного мат. ожидания и вариации). Заметим, что финансовые временные ряды редко являются стационарными. Не трудно заметить, проводя мониторинг рыночных данных, что финансовые переменные имеют низко волатильные интервалы, за которыми следуют периоды высокой «турбулентности», т.е. нестабильность основных показателей ряда является не постоянной, а изменяющейся во времени».

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

Понятие ARCH (Autoregressive conditional heteroscedasticy - авторегрессионная условная гетероскедастичность) было введено Инглом и обобщенно Боллерслейем до общей ARCH или GARCH. Эти модели относятся к нелинейным стохастическим процессам в отличие от линейно-зависимых процессов AR и MA.

Определим характеристики модели ACRH:

,

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

,где z ~ N(0,1).

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

Выше выведен общий вид линейной модели ARCH (p). Неотрицательность величины air может вызывать определённые трудности при использовании ARCH-модели. Данное условие необходимо для сохранения положительного значения условной дисперсии. При использовании множества лагов это условие может быть нарушено. Боллерслевым былииспользованы предыдущие значения условной дисперсии для ухода от длинных лагов ARCH(q). Обобщенная модель была названа GARCH-моделью:

где - предыдущие квадраты остатков из уравнений условной средней,

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

Необходимо отметить, что развитие семейства ARCH-моделей создало широкий инструментарий для анализа и объяснения экономических временных рядов. Например, модель E-GARCH(p,q) созданная Ф. Блэком, позволяет объяснить эффект асимметрии (волатильность имеет тенденцию к возрастанию после уменьшения котировок, то есть после падения величины отката). В модели HARCH(p) характер убывания автокорреляционной функции для квадратов величин ht более медленный, чем в моделях типа ARCH и GARCH. Этот же эффект памяти свойственен и моделям FIGARCH.

1.3 Появление новых методов анализа информации

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

Мы не можем представить нашу жизнь без таких атрибутов современного человека, как социальных сетей, предоставляющих возможность поддерживать постоянную связь с сотнями людей по всему миру, новостных агрегаторов, поставляющих актуальную информацию, обо всем происходящем в мире, торговых терминалов, открывающих круглосуточный доступ к десяткам финансовых центров по всему миру. Информация окружает нас всюду. Согласно исследованию, проведенному командой Мартина Гилберта из Университета Южной Калифорнии США, объем хранимой в цифровом виде информации составляет фантастические 277,3 эксабайта (1018 байт). При этом, по расчетам ученых, на все время наблюдений (исследование проводилось по периоду с 1986 по 2007 год) скорость вычислений растет со среднегодовым темпом в 58%, количество передаваемой информации - с темпом в 28%, а объемы хранимой информации - в 23% в год.

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

Анализируемые данные имеют объем, который стремится к бесконечности;

Данные являются разнородными (количественные, качественные, мультимедийные, текстовые и др.);

Результаты анализа должны быть выражены в простой и понятной человеку форме.

Именно такие предпосылки легли в основу направления DataMining - области информатики, зародившейся в конце 80-х. Формальным появлением этой области исследования можно считать семинар проведенный Грегорием Пятецким-Шапиро в 1989 году. Основной гипотезой данного направления является тезис о том, что данные могут иметь некие «скрытые данные». Характеристиками скрытых знаний (hidden knowledge) являются:

Новизна. Данные не должны подтверждать результаты, полученные другими более простыми методами;

Нетривиальность. Данные должны выявлять зависимости, которые не могут быть объяснены простыми причинно-следственными связями;

Практически-полезными. Данные должны иметь практическое приложение.

Говоря о «скрытых данных» нельзя обойти важнейшее для DataMining'а понятие шаблона (pattern). Вся современная технология построена на концепции шаблона, отражающейфрагменты многоаспектных связей в анализируемых данных. Шаблоны предоставляют собой закономерности, характерные для определенных наборов данных. Важной особенностью данного направления является то, что методы, используемые для поиска шаблонов, не предполагают априорной структуры данных, вида их взаимосвязей. Это позволяет использовать данные, не обладая глубокими предметными знаниями в области исследуемых данных.

Как уже было сказано ранее, нетривиальность шаблонов является одним из важнейших критериев поиска. Изыскиваемые регулярности в данных должны быть неожиданными (unexpected), раскрывая целый пласт глубинных данных. Именно это дало название области - раскопки данных (datamining).

Рисунок 1 Уровни знаний



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

Рисунок 2 Подходы к анализу данных

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

Классификация методов обучения в machinelearning:

Индуктивное обучение - выявление взаимосвязей в исследуемых данных;

Обучение с учителем;

Обучение без учителя;

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

Обучение с учителем. Один из самых распространенных методов обучения в машинном обучении. Формально задачу можно описать так: имеется массив объектов A, состоящее из признаков объекта (a1, a2,a3 …ai),и поле откликов B,состоящее из реакций на эти признаки (b1, b2, b3 … bi) Между объектами полей существует взаимосвязи l, характер взаимосвязей неизвестен, лишь известно о существовании отображения. Задачей обучения является восстановить взаимосвязи l, сформулировав модельную взаимосвязь , которая бы могла дать достаточно точно интерпретировать каждый объектобучающей выборки. Этот метод получил название минимизации эмпирического риска(empiricalriskminimization). Эмпирическим риском называют среднюю ошибку модели на обучающей выборке. ERM-метод самый широко применимый при построении обучающего алгоритма.

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



Рисунок 3

Одной из важнейших проблем, которые возникают при использовании ERM-метода, является проблема переобучения (overfitting). Переобучение - явление, характеризующееся высокой разницей в объясняющей способности модели на обучающей и тестовой выборке. Данное явление может быть объяснено следующими причинами:

В рамках построения (fitting) модели, были выявлены закономерности, характерные для обучающей выборки, но не выявленные в тестируемых данных;

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

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

Для иллюстрации(machinelearning, 2010) рассмотрим задачу аппроксимации функции . Тренировочными данными будут являться

50 наблюдений . В качестве модели будет использована полиномиальная модель . Для построения обучающей модели будет использован МНК . Варьируя степень полинома, то есть сложность модели, можно увидеть, что происходит с моделью.

Рисунок 4 Источник:machinelearning.ru

Рисунок 5 Источник: machinelearning.ru

Рисунок 6 Источник:machinelearning.ru

Рисунок 7 Источник:machinelearning.ru

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

В рамках дисциплины был разработан ряд методов, позволяющих бороться с эффектом переобучения. Так широкое распространение приобрели следующие методы: перекрестная проверка (cross-validation), регуляризация (regularization), принудительная остановка алгоритма, априорная вероятность, уменьшение размерности и др.

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

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

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

1.4 Основные алгоритмы машинного обучения

В рамках интеллектуального анализа данных и в частности машинного обучения применяется множество алгоритмов. Однако стоит выделить ряд самых востребованных и широко используемых в практических исследованиях. Согласно результатам международной конференции по дата майнингу, проведенной институтом инженеров по электротехнике и электронике в декабре 2006 года(IEEE, 2007)был назван ряд алгоритмов, которые внесли наибольший вклад в развитие направления. К таким алгоритмам были отнесены: C4.5, k-Means, метод опорных векторов (SVM), Apriori, алгоритм максимизации ожидания (EM), алгоритм ссылочного ранжирования PageRank, метод усиления слабых классификаторов AdaBoost, метод k ближайших соседей, наивный байесовский классификатор, and алгоритм построения классификационно-регрессионных деревьев CART.

Алгоритм построения деревьев принятия решений С4.5

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

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

Алгоритм С4.5 был создан австралийским ученым Джоном Квинланом. Алгоритм является развитием другого алгоритма автора - ID3. В алгоритме реализованы такие решения, как отсечение лишних ветвей решений (pruning), работа с неполной обучающей выборкой и некоторые другие функции.

Алгоритм начинает свою работу с построения стартового дерева принятия решений. Этот этап выполнятся в соответствии с принципом построения алгоритмов «разделяй и властвуй». Основная идея данного подхода заключается в последовательном разбиение задачи на подзадачи с целью дальнейшей комбинации полученных результатов для получения решения главной задачи. Обычно разбиение происходит до момента, когда подзадачи низшего уровня не становятся элементарными.

Рисунок 8Принцип построения алгоритмов «Разделяй и властвуй»

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

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

После выполнения построения стартового дерева происходит процедура редукции (pruning) с целью предотвращения переподгонки (overfitting).Алгоритм редукции отталкивается от пессимистичной оценки уровня ошибок в наборе из Nслучаев, Eиз которых не принадлежат к наиболее частотному классу. Вместо отношения E/N, алгоритм определяет верхний предел биноминальной вероятности, что события Е наблюдались в Nиспытаниях с определенным уровнем доверия.

Алгоритм C4.5 относится к семейству алгоритмов построения деревьев принятия решений. В отличие от всех остальных алгоритмов, приведенных в этом списке, этот алгоритм является символьным, а не числовым. Это позволяет относительно просто перейти к форме, удобной для интерпретации человеком. Именно поэтому данный алгоритм широко применяется для формального построения логики.

k-Means: кластеризация методом k-средних

Алгоритм k-Meansбыл разработан в 50-х годах польским математиком Гуго Штейнгаузом. Алгоритм является одним из самых распространенных методов кластеризации -упорядочивания элементов массива по относительно однородным группам. Для осуществления кластеризации необходимо выбрать критерий, в соответствии с которым наблюдения будут относить к той или иной группе. В рамках описываемого алгоритма подобным критерием выбирается расстояния. Можно назвать множество видов расстояний: эвклидово, расстояние Чебышева, степенное расстояние и др. В k-Meansиспользуется Эвклидово расстояние, т.е. геометрическое расстояние в многомерном пространстве. В рамках алгоритма ставится задача минимизировать расстояние от точек кластера до его центроида - условного центра кластера.

,

гдеk - число кластеров, Si-полученные кластеры, i = 1,2,3, …, kи мi-центроиды кластеров.

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

Рисунок 9 Кластеризация методом k-средних



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

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

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

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

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

Рисунок 10 Построение линейных классификаторов SVM

На схеме (рис.9) представлены 3 опорных вектора (L1, L2, L3), которые разделяют пространство. Как не сложно догадаться может существовать множество векторов, удовлетворяющих данному критерию. Именно поэтому было введено требование к максимизации зазора. Разделяющим вектором выбирается тот вектор, который имеет наибольшее расстояние между двумя параллельными ему опорными векторами, касающимися классифицируемых наборов.

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

Очевидным вопросом остаются случаи, когда линейным способом невозможно разделить пространства. В таких случаях принято говорить о линейной неразделимости. В 1992 году в совместном исследовании( A training algorithm for optimal margin classifiers., 1992) Владимира Вапникова, Изабелы Гиойон и Бернанда Бозера было предложено решение проблемы. Для этого необходимо вложить пространство в пространство большей размерности H.Для этого применяется отображение . В этом случае при анализе образов изначального пространства в пространстве Hможно свести решение задачи к линейно разделимому случаю.

Рисунок 11 Классификатор во входном пространстве

Рисунок 12 Классификатор в пространстве большей размерности после преобразования

Стоит отметить, что кроме классической линейно реализации классификатора существует нелинейная реализация ядра классификатора. В 1992 году Изабель Гийон, ВладимирВапники Бернхард Босер предложили способ создания нелинейного классификатора. В данном случае предлагается переход от скалярных произведений к произвольным ядрам. К наиболее распространенным ядрам для нелинейно классификации относятся:

Полиномиальное (однородное):

Полиномиальное (неоднородное):

Радиальная базисная функция:

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

Алгоритм Apriori: поиск ассоциативных правил

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

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

Достоверность - является априорной вероятностью по Байесу для множества двух признаков.

Алгоритм Aprioriбыл предложен Ракешем Агравалом в 1994 году(Fast Algorithms for Mining Association Rules, 1994). В алгоритме используется свойство анти-монотонности: поддержка любого набора не может превышать минимальную поддержку его подмножеств. Однако обратное не верно. Основной целью использования данного свойства является задача снижения размерности области исследуемых данных.

В рамках работы алгоритма производится поуровневый поиск часто встречающихся наборов элементов. В данном случае свойство анти-монотонности является эвристикой. Допустим существует множество элементов N, состоящее из {a,b,c,d}. Тогда существует следующее множество комбинаций множества N.

Рисунок 13 Принцип анти-монотонности

Допустим было выявлено, что набор 2-ого уровня {c,d} не проходит установленное пороговое значение уровня поддержки. Из свойства анти-монотонности следует, что все супермножества для {c,d} не проходят проверку на уровень поддержки. Подобная эвристика позволяет экспоненциально уменьшить объем вычислений.

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

EM: алгоритм нахождения оценок функции правдоподобия

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

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

kNN: метод k ближайших соседей

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

Метод выполняет ряд простых и интуитивных шагов:

Вычисляет расстояние от исследуемого объекта до каждого объекта обучающей выборки;

Отбирает k «соседей» с наименьшим расстоянием;

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

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

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

Наивный байесовский классификатор

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

Основной идеей алгоритма является вычисление вероятности отнесения наблюдения к классу:

, где

Dc-количество наблюдений, принадлежащих классу св обучающей выборке

D - общее количество наблюдений в обучающей выборке

V - общее количество признаков в обучающей выборке

Wc - частота признака в наблюдениях, классифицированных как класс cв обучающей выборке

Mc - суммарное количество признаков в наблюдениях класса c

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

CART: классификационно-регрессионные деревья

Первые работы, связанные с созданием деревьев решений, то есть последовательного процесса принятия решений, относятся к исследованиям С. Ховленда (Hoveland) и Е. Ханта(Hunt) середины XXвека. Первой работой, давшей импульс развития для всего направления исследования, стала книга Е. Ханта "Experiments in Induction", написанная в 1966 году.

В рамках предметной области введен ряд терминов и обозначений:

Термин	Описание
Узел	логический элемент дерева, в котором происходит разбиение
Лист	Конечный элемент дерева, в котором отражается решение
Метка класса	Класс, присвоенный Объекту деревом
Проверка	Условие разбиения в Узле
Признак	Независимая переменная, определяющая класс
Объект	Наблюдение

Таблица 1

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



Рисунок 14

Область приложения деревьев достаточно широка и охватывает множество направлений, таких как интеллектуальный анализ данных, поддержка принятия решений, выстраивание формализованной логики. Однако все задачи можно объединить в 2 большие группы: классификация и регрессия. Деревья отлично справляются с задачами классификации, относя наблюдения к тому или иному классу. Классификационные деревья являются классическим примером алгоритма обучения с учителем. Так же данный метод может проводить регрессионный анализ по недискретным данным, выявляя зависимости между переменными.

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

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

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

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

Информационный подход к разбиению

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

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

Вероятностный подход

Подход, применяемый в методе CARTосновывается на индексе Джини, оценивающем «расстояние» между распределениями классов.

Критерием разбиения же является минимальный индекс Джини:

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

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

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