Содержание к диссертации
Введение
1. Задача текстовой классификации как задача обучения по прецедентам 12
1.1 Оценка качества методов классификации 15
1.1.1 Метрики точности и полноты 16
1.1.2 Метрика Accuracy 17
1.1.3 Метрика AUC 19
1.1.4 Комбинированные метрики 20
1.2 Методы решения задачи текстовой классификации 23
1.2.1 Наивный байесовский метод 23
1.2.2 Метод ближайших соседей 24
1.2.3 Оценка качества 25
2. Задача классификации текстов 27
2.1 Линейные методы классификации 27
2.1.1 Наивный байесовский метод и его модификации 27
2.1.2 Логистическая регрессия 32
2.2 Модельные деревья решений 35
2.2.1 Одномерная линейная регрессия 41
2.2.2 Инкрементальное обновление 47
2.2.3 Многомерная линейная регрессия 48
2.3 Алгоритмические композиции 54
2.3.1 Алгоритмические композиции в задаче регрессии 57
2.3.2 Алгоритмические композиции в задаче бинарной классификации 58
2.4 Матричное разложение как метод выделения признаков 59
2.5 Выводы 62
3. Экспериментальное исследование рассмотренных методов 65
3.1 Методика экспериментального исследования 65
3.1.1 Метод скользящего контроля 66
3.1.2 Стратификация 68
3.2 Исследуемые наборы данных 69
3.2.1 Коллекция Reuters-21578 69
3.2.2 Коллекция UCI 70
3.3 Результаты численных экспериментов 72
3.3.1 Линейные методы классификации 72
3.3.2 Линейные методы восстановления регрессии 75
3.3.3 Модельные деревья решений в задаче восстановления регрессии 77
3.3.4 Алгоритмические композиции на основе модельных деревьев в задачах классификации 84
3.4 Выводы 92
Заключение 93
4. Список сокращений и условных обозначений 94
Литература 96
- Комбинированные метрики
- Модельные деревья решений
- Алгоритмические композиции в задаче бинарной классификации
- Линейные методы восстановления регрессии
Введение к работе
Актуальность темы. Классификация текстов – одна из важных задач информационного поиска, заключающаяся в отнесении документа к одной или нескольким категориям (классам) из некоторого заранее определенного набора на основании анализа содержания этого документа. Простейшим и исторически первым методом классификации документов является ручная классификация, примеры которой можно видеть в виде рубрик в СМИ, категорий в библиотеках, полученных разделением художественных текстов на жанры, научных текстов по тематикам и т.д. Ручная классификация весьма ограничена в способности быстро обрабатывать большие массивы текстов, характерные для многих приложений автоматических методов классификации текстов. Такие методы широко используются современными интернет-системами: новостные агрегаторы, такие, как сервис Яндекс.Новости или Google News решают задачи тематической рубрикации новостных документов и сюжетов, почтовые сервисы, например, Яндекс.Почта, gmail или Mail.ru, используют алгоритмы обнаружения спама для фильтрации почты, поисковые системы (Яндекс, Google, Mail.ru, Yahoo и другие) решают задачи обеспечения разнообразия поисковой выдачи, и т.д.
Методы машинного обучения широко используются для задач текстовой классификации. Это обусловлено несколькими причинами, среди которых следует отметить высокую скорость классификации, а также снижение роли человека в процессе получения решения. Действительно, использование методов машинного обучения позволяет свести задачу для человека лишь к формированию обучающей выборки прецедентов, что, как правило, не требует высокой квалификации.
По этой причине в диссертационной работе рассматриваются, в основном, вопросы, связанные с применением методов машинного обу-
чения к задаче автоматической классификации текстов. Отметим некоторые характерные особенности этой задачи:
-
Тексты являются текстами на естественном языке, не имеют четкой формализации, не структурированы, не являются техническими.
-
Количество классов в задачах классификации текстов, как правило, достаточно велико, а сами классы имеют мало общего. Впрочем, в более сложных случаях, не рассмотренных в настоящей работе, классы могут образовывать иерархию.
-
Как правило, большой важностью обладают вопросы производительности, т.к. в приложениях тексты необходимо обрабатывать в реальном масштабе времени.
-
Сама задача достаточно хорошо исследована, имеется большое количество публикаций, посвященных этой теме и содержащих оценки качества работы различных алгоритмов на стандартных наборах данных.
Цель диссертационной работы. Повышение качества классификации новостных текстов на основе использования современных методов машинного обучения.
Для достижения этой цели в диссертации решаются следующие задачи:
-
Разработка способов признакового описания текстовых документов.
-
Анализ существующих методов решения традиционных задач машинного обучения и модификация этих методов с целью повышения показателей качества моделей, получаемых с их помощью.
-
Разработка модифицированных версий классических алгоритмов машинного обучения.
-
Разработка методов построения модельных деревьев решений и алгоритмических композиций на их основе для решения задач восстановления регрессии и классификации.
-
Сравнительный анализ известных и предложенных автором методов машинного обучения применительно к задачам восстановления регрессии и классификации.
-
Разработка метода понижения размерности в задаче классификации текстов.
-
Разработка метода машинного обучения для задачи классификации текстов, использующего предложенные автором методы классификации и обработки документов.
-
Сравнительный анализ всех рассмотренных методов применительно к решению задачи классификации текстов.
Методы исследования. Полученные в диссертации результаты основываются на применении методов статистического и лингвистического анализа текстов, теории вероятностей, математической статистики, теории алгоритмов, численных методов.
Научная новизна. Основные результаты работы, являющиеся новыми и оригинальными, заключаются в следующем:
-
Разработан метод признакового описания документов, позволяющий учитывать специфику написания текстов путем взвешивания позиций вхождений слов в документы.
-
Разработаны модификации стандартных линейных методов классификации: наивного байесовского метода и метода логистической
регрессии, позволяющие существенно повысить качество решения задачи классификации текстов при использовании этих методов.
-
Разработано несколько оригинальных способов получения оценок ошибки многомерной линейной регрессии в условиях постоянно изменяющейся выборки, использующих в качестве основы решение задачи одномерной линейной регрессии и градиентный бу-стинг для приближенного решения задачи. Предложенные методы получения оценок ошибки многомерной линейной регрессии успешно использованы в качестве критериев качества разбиений при построении модельных деревьев решений.
-
Разработана общая схема построения алгоритмических композиций, позволяющая решать, как задачи регрессии, так и задачи классификации при использовании произвольных базовых методов решения задачи восстановления регрессии. Разработан метод декомпозиции матриц, позволяющий решать задачу тематического моделирования применительно к матрицам вхождений слов в документы, не только обеспечивающий снижение размерности признакового пространства, но и осуществляющий определенного рода семантический анализ текстов. Метод принципиально отличается как от известных методов разложения матриц, так и от известных методов тематического моделирования.
-
Реализован и исследован метод решения задачи классификации текстов, использующий матричное разложение для получения признаковых описаний документов и алгоритмическую композицию на основе модельных деревьев решений для решения задачи классификации.
Практическая ценность.
-
В результате программной реализации всех рассматриваемых в работе методов и последующего их исследования на коллекциях задач из репозитория UCI было установлено, что предложенные методы решения задач восстановления регрессии и классификации значительно превосходят известные методы по качеству получаемых моделей.
-
В результате экспериментов на коллекции текстовых документов Reuters-21578 было установлено, что предложенные модификации стандартных линейных методов классификации значительно превосходят стандартные методы по качеству моделей: для показателей качества наивного байесовского метода на 20% по сравнению с оригинальным, а для метода логистической регрессии – на 8%. Также было установлено, что алгоритм, основанный на алгоритмической композиции модельных деревьев, имеет наилучшие показатели качества среди всех рассмотренных в работе методов.
-
Результаты диссертационной работы внедрены в сервис «Ян-декс.Новости», разрабатываемый ООО «Яндекс», и используются в задачах рубрикации и кластеризации новостных документов (подтверждено актом об использовании результатов диссертации).
Апробация. Положения диссертационной работы докладывались на XVII ежегодной международной научно-технической конференции студентов и аспирантов «Радиоэлектроника, электротехника и энергетика» в 2011 году, XVIII ежегодной международной конференции «Информационные средства и технологии» в 2010 году, на рабочих совещаниях и выступлениях в компании «Яндекс».
Публикации. По теме диссертации опубликовано четыре научные работы, в том числе две – в изданиях по перечню ВАК.
Объем и структура работы. Диссертация состоит из введения, трех глав и заключения. Список использованной литературы содержит 54 наименования. Текст диссертации содержит 108 страниц машинописного текста, включая 16 рисунков и 7 таблиц.
Комбинированные метрики
Неформально задача обучения по прецедентам [45] может быть сформулирована следующим образом. Имеется множество объектов и множество возможных ответов. Существует некоторая зависимость между объектами и ответами – целевая функция, но она неизвестна. Известно только конечное множество прецедентов – пар, состоящих из объектов и соответствующих им ответов. Это множество будем называть выборкой. На основе множества прецедентов необходимо восстановить неизвестную зависимость, то есть, построить алгоритм, способный для всякого объекта предсказать соответствующий ему ответ. Этот алгоритм будет называться решающей функцией. Значения решающей функции будем называть предсказаниями. Способ построения решающей функции по множеству прецедентов называется методом обучения, а процесс построения решающей функции будем называть процессом обучения. Выборку, используемую в процессе обучения, будем называть обучающей выборкой.
Для измерения качества предсказаний необходимо определить функционал качества – функцию, которая всякому набору прецедентов и решающей функции сопоставляет некоторое число, причем считается, что большие значения функционала качества означают лучшее качество предсказаний. Можно, напротив, определять функционал потерь, для которого лучшее качество предсказаний соответствует меньшему значению функционала. И функционалы потерь, и функционалы качества также называют метриками.
Требованием к методу обучения является обеспечение качественных предсказаний не только на объектах, входящих в обучающее множество, но и на других объектах. Для проверки этого требования рассматривается другая выборка прецедентов, никак не связанная с обучающей - тестовую (контрольную), и измерить качество предсказаний на ней.
Способность осуществлять качественные предсказания не только на объектах обучающей выборке, но и на других объектах, называется обобщающей способностью.
Более формально, будем считать, что имеется множество объектов , множество ответов и существует неизвестная целевая функция , значения которой измерены на конечном подмножестве \Х\ . Обучающая выборка определяется тогда следующим образом: «) Ш Будем считать, что все возможные решающие функции образуют множество . Тогда метод обучения - это функция, определенная на множестве всех возможных обучающих выборок и принимающая значения в множестве . Если , то значение ( ) называется предсказанием решающей функции на объекте . Функционал качества (а равно и функционал потерь) - это функция, определенная для всякой выборки и решающей функции. Если - тестовая выборка, то значение функционала ( ( )) можно считать оценкой обобщающей способности метода обучения . Впрочем, эта оценка верна лишь для конкретных обучающей и тестовой выборки. Вопросы получения более содержательных оценок обсуждаются в главе 3.
Как правило, в задачах машинного обучения используется признаковое описание объектов, т.е. объект задается некоторым набором измеренных для него значений. В настоящей работе мы будем считать, что все признаки являются значениями некоторых вещественных функций, определенных на множестве объектов. Поэтому для простоты мы будем считать, что множество объектов является множеством признаковых описаний, т.е. . В зависимости от множества ответов различают следующие задачи машинного обучения: задача восстановления регрессии, если ; задача бинарной классификации, если \Y\ ; задача мультиклассификации, если \Y\ и другие некоторые другие. Для бинарной классификации обычно полагают {).
Задачи текстовой классификации часто не укладываются в стандартную схему мультиклассификации: как правило, в реальных задачах оказывается возможной ситуация, при которой некоторым документам сопоставляются более одного класса, а некоторым документам не сопоставляются никакие классы.
Поэтому вполне естественно рассматривать задачу текстовой классификации с классами как бинарных задач классификации. В таком случае ясно и то, каким образом можно приписывать документу более одного класса, и то, каким образом измерять качество. Кроме того, оказывается возможным настраивать параметры алгоритма под каждый конкретный класс индивидуальным образом.
Модельные деревья решений
В простейшем варианте наивного байесовского метода [11,26] используется модель представления документа, носящая название bag of words. Это название подчеркивает тот факт, что модель рассматривает документ как множество (в лучшем случае - мультимножество) входящих в него слов без учета очередности их упоминания.
В таком случае признаковым описанием документа является вектор вхождений слов в этот документ (для этого все используемые в документах слова необходимо предварительно соответствующим образом пронумеровать). В наивном байесовском методе вероятность того, что документ , содержащий слова , принадлежит классу , вычисляется следующим образом: (\) ( )Yl(\) где ( ) - условная вероятность того, что слово появится в документе из класса , ( ) - априорная вероятность класса .
Априорная вероятность ( ) вычисляется как отношение количества документов, относящихся к классу , к общему количеству документов. Условная вероятность (\) определяется как отношение количества документов, относящихся к классу , в которых встречается слово , к общему числу документов, относящихся к классу . Эти оценки могут быть получены по принципу максимума правдоподобия [26].
Наивный байесовский метод, несмотря на свою простоту, является достаточно мощным методом, который до сих пор достаточно активно исследуется. Среди направлений исследований можно отметить следующие:
Метод ближайших соседей [26] - простейший метрический классификатор. Имея некоторую меру сходства объектов, т.е. функцию [ ], можно относить каждый объект к тому классу, к которому принадлежит ближайший к нему с точки зрения меры объект обучающей выборки. Такой метод называется методом ближайшего соседа.
Для повышения надежности классификации объект относят к тому классу, которому принадлежит большая часть его соседей. Метод, в котором для предсказания используются соседей, называется методом к ближайших соседей (kNN).
К ключевым проблемам метода к ближайших соседей применительно к задаче классификации текстов можно отнести следующие: Чрезвычайно высокая размерность признакового пространства, влекущая за собой высокую вычислительную сложность применения метода. Высокая чувствительность к масштабу признаков. Сложность решения вопроса об оптимальном значении коэффициента . В связи с этим, для метода к ближайших соседей важными оказываются вопросы отбора и выделения признаков [26], нормализации значений признаков [26], использования эффективных структур для поиска ближайших соседей [3,10,13] и др.
Сравнение различных методов классификации на коллекции Reuters-21578.
Впрочем, необходимо отметить, что методика получения приведенных оценок отличается от методики, используемой в настоящей работе. Конкретнее, приведенные оценки верны для некоторого фиксированного разбиения коллекции на обучающую и тестовую выборки. Такого рода оценка может быть смещенной и, кроме того, легко поддается «накрутке», т.к. фактически возможно осуществлять обучение внешних параметров алгоритмов по тестовой выборке. В настоящей работе используется метод скользящего контроля [46,47], который подробно описан в главе 3 и который не обладает этим недостатком, а, кроме того, позволяет получать несмещенные оценки обобщающей способности алгоритмов.
Алгоритмические композиции в задаче бинарной классификации
Дерево решений [26,29,30,39,43,54] - это бинарное дерево, предназначенное для получения предсказаний на основании набора признаков, описывающих предъявляемый объект. В каждом узле дерева осуществляется проверка того или иного условия; на основании результата этой проверки выполнение алгоритма перемещается в левое или в правое поддерево рассматриваемого узла. Процедура повторяется в каждом посещенном узле до тех пор, пока очередной узел не окажется листом. В этом случае осуществляется предсказание на основании модели, размещенной в листе.
Дерево решений можно рассматривать и в качестве линейной модели. В самом деле, фактически дерево решений осуществляет разбиение признакового пространства на непересекающиеся подпространства. Каждое из таких подпространств является множеством объектом, попадающих в соответствующий лист дерева. Пусть - разбиение, порождаемое деревом решений, а - модели, соотнесенные соответствующим листьям.
Тогда предсказание дерева можно записать в виде ?( ( ) [ J) В листьях дерева, как правило, используются чрезвычайно простые модели: например, константные предсказания: для задач регрессии – средние величины ответов на объектах обучающей выборки, попадающих в этот лист, для задач классификации – класс, наиболее часто встречающийся среди объектов обучающей выборки, попадающих в этот лист.
В настоящей работе будут исследоваться решающие деревья только применительно к задаче регрессии. Традиционно решающие деревья, осуществляющие константные предсказания в листьях, называют регрессионными деревьями, тогда как деревья, осуществляющие в листьях предсказания с использованием более сложных моделей, называют модельными [30,39].
Условия, проверяемые в узлах дерева, суть сравнения некоторого признака объекта с пороговым значением. Теоретически возможны и более сложные условия, но в задачах построения деревьев решений они не находят значительного распространения.
Процесс построения дерева решения можно описать следующим образом. Изначально дерево пусто. В него добавляется корневая вершина, содержащая всю обучающую выборку. Выбирается разделяющее правило – т.е. выбираются некоторый признак и некоторый порог. После этого образуются две новых вершины, непосредственные потомки корневой вершины, одна из которых содержит те объекты, для которых значение выбранного признака превосходит порог, а другая – те объекты, для которых значение выбранного признака не превосходит порог. Затем процедура повторяется в каждой из вновь образованных вершин. Применяемые критерии останова весьма разнообразны: получение подвыборки с чрезвычайно малой ошибкой, получение подвыборки чрезвычайно малого размера, превышение максимально допустимого удаления от корневой вершины, и т.д.
Ключевым является вопрос о выборе разделяющего правила. Если в задаче имеются объектов, каждый из которых описывается признаками, то временная сложность нахождения оптимального разделяющего правила при условии предварительной сортировки объектов может быть оценена как ( ( )), где ( ) временная сложность вычисления функционала качества для одного разделяющего правила. Рассмотрим простейший пример подобного рода. При построении регрессионных деревьев один из наиболее распространенных методов выбора наилучшего разбиения заключается в минимизации остаточной дисперсии значений целевой функции. Пусть имеется выборка , представленная непустым конечным множеством пар вещественных чисел, в которых первый компонент пары является значением признака, а второй - значением целевой функции: {{),{)1 Для получения разбиения выбирается порог - вещественное число, разбивающее множество на два подмножества: , где {()\x} { ) } Дисперсия значений целевой функции (для простоты изложения будем использовать смещенную оценку) в исходном множестве равняется ( )yiy У А У (у) (у) После осуществления разбиения «остаточная» дисперсия окажется равной ( ) ( ). Оценка качества разбиения - изменение дисперсии выборки: ( ) ( ) ( ) i) Чем больше значение функционала ( ), тем лучше разбиение. Задача заключается в нахождении оптимального порога - т.е. такого порога, для которого функционал ( ) принимает минимальное значение. Традиционный способ решения этой задачи заключается в следующем. Отсортируем пары из множества в порядке неубывания первой компоненты: {(х)Лх),Л)} Тогда множество возможных значений порога можно считать состоящим из средних величин идущих подряд в этом списке первых компонент пар: { } где Заметим, что дисперсия значений целевой функции для множества пар выражается через три величины: мощность этого множества, сумму значений целевой функции в этом множестве и сумму квадратов значений целевой функции в этом множестве. Введем соответствующие обозначения: ( )
Таким образом, весь алгоритм выполняется за время, пропорциональное длине выборки (если не учитывать затраты на сортировку пар) для одного признака. Если в задаче имеется признаков, то, очевидно, поиск наилучшего из разбиений по всем факторам окажется возможным выполнить за время ( ), что оказывается вполне допустимым даже для весьма объемных выборок.
В настоящей работе будут рассматриваться модельные деревья, в листьях которых предсказание осуществляется линейной моделью. То есть в листьях деревьев будет решаться задача многомерной линейной регрессии. Дисперсия ответов в листе может рассматриваться теперь как верхняя оценка для среднего квадрата отклонения предсказаний линейной регрессии. Впрочем, эта оценка весьма груба. Использование более точных оценок может оказаться хорошим способом повысить качество предсказаний модельных деревьев.
Рассмотрим теперь способы получения оценок для качества многомерных линейных регрессионных моделей, допускающих эффективное обновление при изменении выборки. Будут рассмотрены четыре способа построения оценок как: ошибки одномерной линейной регрессии, построенной по тому признаку, который используется в разбиении; наименьшей из ошибок одномерных линейных регрессий, построенных по каждому из признаков; ошибки многомерной линейной регрессии, построенной методом градиентного бустинга; ошибки многомерной линейной регрессии, построенной методом многократного решения задачи одномерной линейной регрессии.
Изложение в основном будет касаться только вопросов обновления интересующих нас величин, при этом опускаются детали общего алгоритма нахождения оптимального разбиения, т.к. они уже были рассмотрены в связи с обновлением дисперсии ответов.
Ясно, что вопрос о наименьшей из ошибок одномерных линейных регрессий сводится к задачам об ошибке одномерной линейной регрессии, поэтому нет нужды в его отдельном рассмотрении.
Линейные методы восстановления регрессии
Результаты измерения качества линейных методов в задаче классификации представлены на рис. 3.1. Рассматриваются следующие методы: классический наивный байесовский метод (Naive Bayes, NB); наивный байесовский метод с итеративным пересчетом весов и регуляризацией (improved Naive Bayes, iNB); классический метод логистической регрессии (Logistic Regression, LR); метод логистической регрессии, обученный при помощи модифицированного метода стохастического градиентного спуска (stratified Logistic Regression, sLR); метод логистической регрессии, обученный при помощи модифицированного метода стохастического градиентного спуска с использованием смещений в функционале потерь (stratified biased Logistic Regression, sbLR).
Очевидно, что наивный байесовский метод плохо подходит для решения задачи бинарной классификации. В то же время, модифицированный наивный байесовский алгоритм значительно превосходит по качеству оригинальный метод. Также видно, что предложенные модификации метода логистической регрессии значительно увеличивают показатели качества этого метода. Результаты сравнения линейных методов классификации.
Рассмотрим теперь вопрос трансдуктивного обучения логистической регрессии. Предлагаемый метод трансдуктивного обучения логистической регрессии (transductive stratified biased Logistic Regression, tsbLR) предназначен прежде всего для повышения полноты классификации на неразмеченной коллекции. Гипотеза заключается в том, что это необходимо прежде всего в ситуациях, когда длина обучающей выборки мала по сравнению с длиной тестовой выборки.
Для проверки этой гипотезы был проведен следующий эксперимент. Осуществлялся стандартный стратифицированный скользящий контроль, в котором в обучающую выборку всегда попадала некоторая доля от общего количества документов. Например, при метод оказывается «инвертированным» методом скользящего контроля, при котором выборка разбивается на десять блоков, каждый из которых поочередно служит обучающей выборкой, а объединение остальных блоков – тестовой выборкой. При ситуация аналогична, но количество блоков равно четырем. Значение соответствует стандартной процедуре скользящего контроля по пяти блокам, – по десяти блокам. Результаты экспериментов представлены на рис. 3.2. Рис. Показатели качества методов логистической регрессии в зависимости от длины обучающей выборки. По вертикальной оси отложена доля объектов, попадающих в обучающую выборку, по горизонтали – значение -меры.
Действительно, видно, что, основной эффект от трансдуктивного обучения достигается для небольших значений . Так, в условиях, когда длина тестовой выборки превосходит длину обучающей выборки в девять раз ( ), трансдуктивное обучение увеличивает метрику практически на десять процентов (или пять процентных пунктов). Для достаточно больших значений выигрыш от трансдуктивного обучения практически не ощутим. 3.3.2 Линейные методы восстановления регрессии Рассмотрим теперь вопрос о качестве оценок ошибки многомерной линейной регрессии. Для этого сравним показатели качества следующих методов линейной регрессии: константное предсказание, равное среднему значению ответа на обучающей выборке (constant); предсказание наилучшей одномерной линейной регрессионной модели (best simple linear regression, bslr); предсказание линейной регрессионной модели, построенной после десяти итераций метода градиентного бустинга (gradient boosted linear regression, gblr); предсказание линейной регрессионной модели, построенной после десяти итераций метода последовательного решения одномерных задач линейной регрессии (positional linear regression, plr) предсказание линейной регрессионной модели, построенной по методу МНК. Соответствующие метрики сведены в таблицу 3.5. Видно, что, как правило, более сложные методы обеспечивают лучшее приближение. Это, впрочем, является неверным для метода градиентного бустинга, который, как оказывается, сходится весьма медленно, что можно продемонстрировать графиками зависимости величины ошибки при обучении для рассматриваемых методов на нескольких задачах.
Из графиков на рис. 3.3 и 3.4 хорошо видно, что метод gblr сходится намного медленнее, чем метод plr. Учитывая, что метод gblr при этом является существенно более вычислительно сложным, следует сделать вывод, что использование метода gblr является неоправданным. Выигрыш метода gblr для случая одной итерации обусловлен тем, что эта итерация применяется к решению, построенному методом bslr и совпадающему поэтому с решением метода plr за одну итерацию.
Разница между регрессионными и модельными деревьями, как легко видеть, весьма существенна. Что касается авторских методов построения модельных деревьев, то они во всех задачах превосходят по качеству метод M5P, причем в большинстве ситуаций использование более точных оценок ошибки многомерной линейной регрессии приводит к построению более качественной модели.
Впрочем, необходимо заметить, что самый простой из методов построения модельных деревьев – основанный на оценке стандартного отклонения ответов – на некоторых задачах проигрывает методу M5P. Это говорит о том, что используемые в методе M5P эвристики достаточно сильны. Вопрос о применении этих эвристик с одновременным использованием более точных оценок ошибки много может стать темой отдельного исследования. Рассмотрим теперь алгоритмические композиции для задачи восстановления регрессии на основе различных модельных деревьев. Рассматриваться будут алгоритмические композиции из десяти деревьев. Значение оптимального коэффициента сжатия определялось по методу скользящего контроля. При этом исключим из рассмотрения метод gbLR, как наиболее вычислительно сложный и при этом не оправдывающий эту сложность качеством моделей.
Из таблицы видно, что, по-прежнему, использование более точных оценок приводит к построению более качественных моделей. Любопытным оказывается результат метода M5P в задаче cpu_act. Превзойти его показатели в этой задаче сумел только самый сложный из предложенных автором методов.
Для того, чтобы проиллюстрировать механизмы работы различных методов построения деревьев решений, рассмотрим следующую модельную задачу. одной или несколькими прямыми. Простейшим решением было бы провести прямую, воспользовавшись стандартным методом наименьших квадратов. Соответствующее приближении изображено на рис. 3.6. Рис. 3.6. Линейная апроксимация функции ( ) .
Построим теперь для этой функции приближения в виде модельных деревьев высоты один. Рассмотрим два способа построения модельных деревьев: метод, основанный на минимизации стандартного отклонения ответов (deviation) и метод, основанный на ошибке одномерной линейной регрессии (slr). На рис. 3.7 изображены оценки ошибок этих методов в зависимости от выбора точки разбиения.
