Оценка результатов построения деревьев решений при помощи регрессионного анализа

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

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ОБРАЗОВАНИЯ

«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»

Факультет социальных наук

Выпускная квалификационная работа - МАГИСТЕРСКАЯ ДИССЕРТАЦИЯ

Оценка результатов построения деревьев решений при помощи регрессионного анализа

Клементьев Александр Александрович

Руководитель ВКР

д-р экономических наук, проф.

Ю. Н. Толстова

Москва 2019



Оглавление

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

1. Введение

1.1 История возникновения и применения метода построения деревьев решений

1.2 Механизм работы метода построения деревьев решений

1.3 Ключевые особенности метода, преимущества и недостатки

1.3.1 Преимущества

1.3.2 Недостатки

1.4 Основные существующие алгоритмы и решаемые ими задачи

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

2. Программа исследования

2.1 Предмет и объект

2.2 Цель и задачи

3. Критерии оценки качества моделей

3.1 Выбор данных для проведения анализа

3.2 Выбор моделей

4. Построение и оценка моделей

4.1 Категориальная бинарная целевая переменная

4.2 Категориальная небинарная целевая переменная

4.3 Интервальная целевая переменная

4.4 Порядковая целевая переменная

4.5 Обобщение результатов

5. Выводы и рекомендации

5.1 Рекомендации по применению методов

5.2 Ограничения и направления для дальнейших исследований

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

Приложение 1 Код для оценки модели с интервальной целевой переменной

Приложение 2 Код для оценки модели с категориальной целевой переменной

Приложение 3 Результаты построения отдельных моделей

Интервальная целевая переменная

Порядковая целевая переменная

Категориальная бинарная целевая переменная

Категориальная небинарная целевая переменная



1. Введение

1.1 История возникновения и применения метода построения деревьев решений

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

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

Первые шаги в этом направлении были сделаны в работах Ховленда и Ханта ещё в 50-х годах двадцатого века. Earl B. Hunt, Janet Marin, Philip J. Stone Experiments in induction. Academic Press, 1966. 247 C. К настоящему времени в распоряжении исследователей и аналитиков находится несколько десятков различных методов построения деревьев решений, которые могут различаться между собой по механизму группировки наблюдений, по требованиям которые предъявляются к изначальным данным, по скорости работы и т.д.

Широкий спектр применения, нетребовательность к типу исходных данных, а также относительная простота использования и интерпретации результатов принесли деревьям решений популярность как в коммерческой, так и в академической среде. Методы и модели анализа данных: OLAP и Data Mining / А.А. Барсегян и др. - СПб.: БХВ- Петербург, 2004.

К сожалению, большое разнообразие доступных методик несет в себе и некоторые проблемы. Так, разные способы построения деревьев решений могут отличаться друг от друга по типу переменных, которые они могут обрабатывать, по тому, какие статистические критерии используются во время работы метода (и используются ли они вообще), по степени трудоемкости операций, и соответственно, потребности в вычислительных мощностях. Более того, различные способы реализации метода могут давать различные результаты в зависимости от поставленной задачи и структуры анализируемых данных. Подобные сложности приводят к тому, что выбрать один единственный универсальный метод для решения всех исследовательских задач не представляется возможным. Wei-Yin Loh, Nunta Vanichsetakul Tree-Structured Classification Via Generalized Discriminant Analysis // Journal of the American Statistical Association. 1988. Vol. 83, No. 403. C. 715-725 Loh, W., Y. and Shih, Y.-S. Split selection methods for classification trees // Statistica Sinica. 1997. №7: С. 815-840. Statistica Sinica 7: 815-840.

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

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

Цели литературного обзора

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

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

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

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

5. Составить перечень критериев сравнения эффективности решений, полученных при помощи деревьев решений и при помощи прочих статистических методов.

6. Определить, какие данные являются наиболее подходящими для сравнения эффективности деревьев решений и прочих статистических методов.

1.2 Механизм работы метода построения деревьев решений

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

Началом дерева является особый, «корневой», узел, который содержит в себе все наблюдения. Затем, в результате проведения ряда статистических тестов над значениями некоего целевого атрибута, заданного исследователем, корневой узел разделяется на две или более непересекающиеся группы наблюдений. Получившиеся в результате разделения подгруппы образуют новые узлы и становятся новым уровнем дерева. Ташкинов А.А., Вильдеман А.В., Бронников В.А. Арименение метода деревьев классификации к прогнозированию уровня развития моторики у больных с нарушениями двигательных функций // Российский журнал биомеханики. - 2008. - №4 (42), С 84-95. Алгоритм построения дерева пытается найти закономерности в данных, определяя при помощи статистических тестов, какие переменные (и их значения) лучше всего разделяют наблюдения на группы, таким образом, что внутри итоговых групп оказываются наиболее однородные наблюдения, а отличия между группами оказываются максимальны. Rokach, L.; Maimon, O. Top-down induction of decision trees classifiers-a survey // IEEE Transactions on Systems, Man, and Cybernetics, Part C. 2005. № 4 (35) С 476-487. Затем над каждым из получившихся узлов вновь проводятся статистические тесты и, если это возможно, узлы делятся дальше, образуя следующие уровни дерева.

Существует несколько механизмов разделения узлов, каждый из которых использует свой критерий качества разделения. Среди наиболее часто встречающихся критериев можно выделить уменьшение коэффициента нечистоты Джини, прирост информации и уменьшение дисперсии для интервальных переменных. Kotsiantis S. B. Decision trees: a recent overview. // Springer Science+Business Media B.V. 2011

В терминах статистики механизм, заложенный в построение деревьев решений является «жадным алгоритмом», т.е. алгоритм стремится принять локально оптимальное решение в каждом отдельном случае, при каждом разделении, предполагая, что это приведет к оптимальному решению всей задачи. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 16. Жадные алгоритмы // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. -- 2-е изд. -- М.: Вильямс, 2005. -- 1296 с.

Процесс деления узлов или «роста дерева» продолжается, пока алгоритм не столкнется с одним из нескольких формальных ограничений:⁷

· Все наблюдения принадлежат к одному и тому же значению целевой переменной.

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

· Число наблюдений в узле меньше, чем минимальное число наблюдений для делящегося узла.

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

· Значение критерия, по которому происходит разделение (Джини, прирост информации и т.д.) ниже порогового.

Узлы, находящиеся на последнем уровне дерева, называются «листьями» и, в идеале, объединяют наблюдения, максимально похожие по значению целевой переменной. Далее, в зависимости от используемого алгоритма, сложности итогового дерева (количества уровней и узлов) и наполненности листьев, к дереву может быть применен процесс «обрезки» (pruning) или регулирования глубины дерева, во время которого от дерева отсекают отдельные ветви. Обрезка производится с целью упростить финальное решение или для борьбы с «переобучением» модели. Переобучение - ситуация, когда дерево гораздо лучше классифицирует данные, на которых было построено, чем новые данные c такой же структурой. William J. Long, John L. Griffith, Harry P. Selker, Ralph B D'Agostino A comparison of Logistic Regression to Decision-Tree Induction in a Mediacal Domain // Computers and biomedical research. - 1993. - №26. C. 74-97.

Деревья решений также можно представить в виде набора правил вида «если [логическое условие с использованием значений переменной-предиктора], то [попадание в группу с определенным значением целевой переменной]», следуя которым можно шаг-за-шагом классифицировать каждое наблюдение в отдельности. Поскольку логические правила, применяемые при построения дерева строятся на исходных переменных, их достаточно просто интерпретировать. Открытость и интерпретируемость правил, по которым происходит классификация, позволяет отнести алгоритмы построения деревьев решений к т.н. алгоритмам «белого ящика», т.е. тем, чьи принципы работы полностью ясны исследователю, поддаются описанию и интерпретации. Kotsiantis S. B. Decision trees: a recent overview. // Springer Science+Business Media B.V. 2011

1.3 Ключевые особенности метода, преимущества и недостатки

1.3.1 Преимущества

Высокая интерпретируемость результатов. Результат анализа обычно представляется в форме наглядного графика, с которого легко считывается информация о количестве и составе конечных классов, а также о переменных, которые послужили разделителями. Кроме того, как уже было отмечено выше, логические правила, по которым группируются наблюдения, написаны «на естественном языке», т.е. в терминах исходных данных, а сами правила доступны исследователю, а значит результаты анализа можно легко описать и объяснить. Кроме того, процесс последовательного учета нескольких факторов для окончательного принятия решения больше похож на процесс принятия решения человеком, нежели механизм работы иных статистических методов. Последняя особенность делает деревья решений предпочтительным методом для анализа процессов принятия решений людьми. An Introduction to Statistical Learning / James, G., Witten, D., Hastie, T., Tibshirani, R., - New York: Springer, 2013. - 418 с.

Нетребовательность к данным. В зависимости от конкретного алгоритма построения деревьев, метод может применяться для анализа переменных, измеренных по интервальным, порядковым и номинальным шкалам. Также метод позволяет успешно работать с данными, содержащими пропущенные значения, выбросы и «шум» - ошибки в оценках параметров. Alexandru G. Floares, George A. Calin, Florin B. Manolache Bigger Data Is Better for Molecular Diagnosis Tests Based on Decision Trees // Data Mining and Big Data. - 2016. - №14. - С. 288-295.

Удобство при выделении ключевых предикторов. Метод позволяет легко выделить наиболее значимые предикторы, а также значимые рубежные значения для интервальных переменных. Алгоритмы разделения узлов подбирают для разделения выборки переменные, обладающие наибольшей дискриминирующей силой. На практике это приводит к тому, что наиболее «значимые» с точки зрения целевой переменной предикторы появляются в дереве раньше, ближе к корню. В случае с интервальными предикторами такие алгоритмы как CHAID автоматически разделяют значение переменной на группы, различия между которыми максимальны, что позволяет осмысленно устанавливать границы на шкалах интервальных переменных в последующем анализе и при интерпретации результатов. Breiman L., Friedman J. H., Olshen R. A., & Stone C. J. Classification and regression trees. Monterey, CA: Wadsworth & Brooks/Cole Advanced Books & Software. - 1984

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

1.3.2 Недостатки

Отсутствие гарантий оптимальности решения. Использование «жадного» алгоритма для разделения каждого из узлов в отдельности не может гарантировать оптимальности всей модели в целом. Murthy S. Automatic construction of decision trees from data: A multidisciplinary survey // Data Mining and Knowledge Discovery. - 1998. № 2 (4). - С 345-389.

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

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

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

Смещение в оценках категориальных переменных. При использовании категориальных переменных в качестве предикторов больший информационный вес присваивается переменным с большим числом уровней измерения. Deng,H.; Runger, G.; Tuv, E. Bias of importance measures for multi-valued attributes and solutions. Proceedings of the 21st International Conference on Artificial Neural Networks (ICANN). 2011. pp. 293--300.

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

1.4 Основные существующие алгоритмы и решаемые ими задачи

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

Существует два основных типа деревьев решений: деревья классификации и деревья регрессии. Тип дерева при этом определяется исходя из типа используемой целевой переменной.

Дерево для классификации предоставляет результат в виде класса, к которому принадлежит наблюдение или же вероятность принадлежности наблюдений, к тому или иному классу.

Дерево для регрессии предоставляет результат, который можно рассматривать как вещественное число (например, стоимость, продолжительность жизни и т.д.). Breiman, Leo; Friedman, J. H., Olshen, R. A., & Stone, C. J. (1984).

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

Список алгоритмов построения деревьев решений является достаточно обширным, однако многие из них имеют очень узкое, отраслевое применение (например, используются для решения задач машинного обучения) и применение их для решения социологических задач нерационально. Nyce, Charles. Predictive Analytics White Paper // American Institute for Chartered Property Casualty Underwriters / Insurance Institute of America, 2007. p. 1 Тем не менее, существует ограниченный набор алгоритмов, пользующихся устойчивой популярностью у специалистов, занимающихся анализом данных. Как правило в этот список включаются следующие методы: CHAID, CART и Сtree. Именно эти методы (или их большая часть) обычно становятся частью статистических пакетов. Introduction to SPSS Classification Trees / SPSS UK Ltd., UK: 2005. С. 5. В этот список также можно включить метод C4.5/C5, завоевавший популярность в качестве метода классификации. Kotsiantis S. B. Decision trees: a recent overview. // Springer Science+Business Media B.V. 2011 Наконец, существует класс гибридных методов, использующих при построении моделей как регрессионный анализ, так и алгоритмы деревьев решений. Представим краткий обзор особенностей этих алгоритмов.

CHAID - Chi-Square Automatic Interaction Detection, алгоритм представленный в 1980 году считается - классическим методом построения деревьев решений. Этот алгоритм выстроен вокруг применения статистического критерия хи-квадрат при сравнении подвыборок. Метод CHAID характеризуется способностью производить деление выборки более чем на две категории за один шаг дерева, т.е. многоуровневым ветвлением. Реализация алгоритма в среде R позволяет использовать только категориальные целевые переменные.

CART (или C&RT - Classification and Regression Trees) - алгоритм, основанный на регрессионном анализе. При построении дерева при помощи этого алгоритма совокупность всегда делится на две части, т.е. метод использует исключительно бинарные ветвления. Применение метода часто приводит к построению чрезмерно глубоких деревьев решений, что может приводить к сложностям при интерпретации результатов. Там же.

С4.5 и его обновленная версия С5.0/See5 - алгоритмы, созданные для работы как с дискретными, так и с интервальными переменными. Алгоритм основан на теории энтропии, т.е. при каждом разделении он пытается подобрать такой критерий деления выборки, при котором в каждом из результирующих узлов окажутся максимально однородные элементы (т.е. будет наименьший беспорядок, энтропия). Помимо уже отмеченной непредвзятости к типу целевой переменной алгоритмы этой серии характеризуются простотой реализации и интерпретации, а также способностью эффективно работать с пропущенными значениями в данных. Decision Trees - C4.5 // Octavian's blog URL: https://octaviansima.wordpress.com/2011/03/25/decision-trees-c4-5/ (дата обращения: 18.03.2018). Max Kuhn, Kjell Johnson Applied Predictive Modeling. - 1st ed. 2013, Corr. 2nd printing 2018 Edition изд. Springer, 2018. Реализация алгоритма в среде R позволяет использовать только категориальные целевые переменные.

Ctree - Conditional Inference Tree - группа алгоритмов, авторы которых пытаются обойти обозначенную выше склонность деревьев решений отдавать предпочтение категориальным предикторам с большим числом категорий при помощи использования другого критерия - силы связи между целевой и зависимой переменной при помощи критерия p-value. Авторы алгоритма заявляют, что их подход позволяет автоматически добиться такой точности прогнозов, которую можно получить от деревьев, построенных при помощи иных алгоритмов, только после процедуры дополнительной «обрезки». Torsten Hothorn, Kurt Hornik, Achim Zeileis Unbiased Recursive Partitioning: A Conditional Inference Framework // Journal of Computational and Graphical Statistics. - 2006. - Volume 15, Number 3, Pages 651-674. Реализация алгоритма в среде R позволяет использовать только интервальные целевые переменные.

LMT - Logistic Model Trees, алгоритм являющий собой попытку соединить в рамках одной модели преимущества деревьев решений и регрессионного анализа. Подобно другим алгоритмам, при построении модели выборка итеративно разбивается на всё более однородные части по значению целевой переменной, но после получение итогового списка «листов» для каждого из них строится отдельная регрессионная модель - биномиальная логистическая регрессия - с целью увеличить точность предсказания и получить числовые коэффициенты связи между целевой переменной и предикторами. Niels Landwehr, Mark Hall, Eibe Frank Logistic Model Trees // Machine Learning. - 2005. - №Volume 59, Issue 1-2. pp 161-205. Алгоритм используется для работы с категориальными целевыми переменными.

M5P - аналог предыдущего алгоритма, однако вместо логистической регрессии в каждом из листов строятся простые линейные регрессии, что предполагает применение алгоритма к целевым переменным, измеренным по интервальной шкале. Y. Wang, I. H. Witten: Induction of model trees for predicting continuous classes. In: Poster papers of the 9th European Conference on Machine Learning, 1997.

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

Из обзора основных алгоритмов построения деревьев решений мы выяснили, что этот метод применяется, прежде всего, для решения задач классификации наблюдений (т.е. отнесения наблюдений к одной из категорий номинальной переменной) и для предсказаний значений непрерывной переменной. Существует большое количество других статистических методов, позволяющих решать эти задачи. К примеру, классификация наблюдений может проводиться при помощи некоторых видов кластерного анализа, при помощи нейронных сетей Искусственная нейронная сеть // Machine learning URL: http://www.machinelearning.ru/wiki/index.php?title=%D0%9D%D0%B5%D0%B9%D1%80%D0%BE%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D0%B5%D1%82%D1%8C (дата обращения: 13.05.18)., дискриминантного анализа, и многих других. Метод ближайших соседей // Machine learning URL: http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B1%D0%BB%D0%B8%D0%B6%D0%B0%D0%B9%D1%88%D0%B8%D1%85_%D1%81%D0%BE%D1%81%D0%B5%D0%B4%D0%B5%D0%B9 (дата обращения: 13.05.18). Однако сравнить деревья решений со всеми методами в рамках одной работы не представляется возможным, поэтому автор ограничивает круг рассматриваемых статистических методов наиболее часто встречающимися вариантами регрессионного анализа. Поскольку, настоящая работа ставит своей целью сравнить эффективность применения деревьев решений в сравнении с регрессионными методами анализа, необходимо составить список регрессионных моделей, пригодных для классификации наблюдений и для предсказаний значений непрерывной зависимой переменной.

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

Категориальная целевая переменная

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

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

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

· Зависимая переменная должна быть дихотомической по характеру (например, наличие или отсутствие признака).

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

· Между предсказателями не должно быть высоких корреляций (мультиколлинеарности).

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

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

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

Порядковая целевая переменная

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

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

· Зависимая переменная измерена по порядковой шкале;

· Независимые переменные могут быть измерены по непрерывной, порядковой или номинальной шкалам;

· Отсутствие мультиколлинеарности между предикторами;

· Пропорциональность шансов.

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

Непрерывная целевая переменная

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

Предпосылками линейной регрессии являются: Демиденко Е. З. Линейная и нелинейная регрессия. -- М.: Финансы и статистика, 1981. -- 302 с.

· Отсутствие линейной взаимосвязи между независимыми переменными;

· Нулевое математическое ожидание для случайной ошибки;

· Гомоскедастичность (постоянная или одинаковая дисперсия) случайных ошибок модели;

· Отсутствие автокорреляции случайных ошибок;

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



2. Программа исследования

2.1 Предмет и объект

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

Объект исследования - алгоритмы построения деревьев решений.

2.2 Цель и задачи

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

Задачи:

1. Составить перечень показателей, позволяющих сравнить качество моделей, построенных при помощи деревьев решений и традиционных методов.

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

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

4. Сравнить качество моделей при помощи ранее определенных критериев.

Модели будут построены при помощи языка программирования R, в среде `RStudio'. Возможность подключения дополнительных библиотек позволяет программе применять гораздо большее количество алгоритмов построения деревьев решений, чем прочие статистические пакеты (в т.ч. и SPSS). RStudio // rstudio.com URL: https://www.rstudio.com/products/rstudio/ (дата обращения: 09.06.2018).



3. Критерии оценки качества моделей

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

Категориальная бинарная целевая переменная

Для оценки качества классификации наблюдений, т.е. результата разнесения по заранее известным группам, наиболее часто применяется простой критерий точности, т.е. доля всех наблюдений, которые были классифицированы правильно. Kweku-Muata Osei-Bryson Evaluation of decision trees: a multi-criteria approach // Computers & Operations Research. 2004. №31. Kiran Singh, Raunak Sulekh The Comparison of Various Decision Tree Algorithms for Data Analysis // International Journal Of Engineering And Computer Science. - 2017. - №6 (6). - С. 21557-21562. При этом необходимо отметить, что результаты классификаций как при помощи регрессии, так и с помощью деревьев решений можно представить, как в виде вероятности попадания в ту или иную группу в процентах, так и в виде факта попадания. К примеру, по результатам построения логистической регрессии, вероятность «1» для конкретного наблюдения составляет 51%. Этот результат можно интерпретировать по разному в зависимости от того, какое пороговое значение выбрал исследователь. Если пороговое значение для попадания в группу «1» оставляет 50%, то это наблюдение необходимо классифицировать, как попавшее в группу «1». Очевидно, необходимо применять одинаковое пороговое значение при оценке результатов применения обоих методов. William J. Long, John L. Griffith, Harry P. Selker, Ralph B D'Agostino A comparison of Logistic Regression to Decision-Tree Induction in a Mediacal Domain // Computers and biomedical research. - 1993. - №26. C. 74-97.

Кроме того, для оценки моделей с бинарной целевой/зависимой переменной применяются критерии чувствительности и специфичности, где под чувствительностью понимается доля правильно определенных «успехов» от всех успехов в выборке (True positive / Actual positive), а под специфичностью - доля верно определенных «неудач» (True negative / Actual negative). Там же. Measures of Predictive Models: Sensitivity and Specificity // The Analysis Factor URL: https://www.theanalysisfactor.com/sensitivity-and-specificity/ (дата обращения: 14.05.18). Для некоторых предметных областей, например медицины и фармацевтики, «стоимость» ошибок разного рода неодинакова, и это учитывается при оценке моделей. Так, при использовании статистических методов в диагностике заболеваний, исследователи осознанно снижают важность ложноположительных ошибок классификации для того чтобы убедиться, что модель совершает как можно меньше ложноотрицательных классификаций, т.е. лучше ошибочно диагностировать у человека патологию и лишний раз его перепроверить, чем пропустить реальную болезнь и не узнать об этом.

Ещё одним методом оценки качества бинарной классификации являются ROC-кривые и показатель AUC (Area Under the Curve). ROC-кривые представляют собой график, на котором отображено соотношение между долей верно классифицированных «успехов» и долей «неудач», которые были неверно классифицированы как успехи (т.е. True positive rate / False positive rate) для всех пороговых значений классификации. Т.е. процесс построения кривой выглядит следующим образом: исследователь устанавливает порог классификации наблюдения как «1» в 1%, оценивает долю True positive rate / False positive rate, отмечает её точкой на графике, затем меняет порог отнесения наблюдения к «1» на 2%, вновь оценивает долю верных положительных предсказаний и т.д. для всех пороговых значений. Claudia P., Foster P. Jeffrey S. S. Tree Induction vs. Logistic Regression: A Learning-Curve Analysis // Journal of Machine Learning Research. - 2003. - №4. - С. 211-255.

Итоговый график выглядит следующим образом:

Рис. 1 Пример построения ROC-кривой

Модели, успешно классифицирующие наблюдения будут иметь высокую долю успешных предсказаний успехов, а значит выгнутый влево-вверх график. Формально качество модели можно оценить, вычислив площадь под кривой графика. Идеальная модель (всегда верно определяющая все наблюдения из группы «1») будет иметь график, площадь под которым равна 1, а модель, дающая верные предсказания с вероятностью 50% будет иметь график совпадающий с пунктирной линией, т.е. площадь под ним будет равна 0,5. Srinivasan, A. Note on the Location of Optimal Classifiers in N-dimensional ROC Space // Technical Report PRG-TR-2-99, Oxford University Computing Laboratory. - 1999.

Категориальная небинарная целевая переменная

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

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

К примеру, у нас есть номинальная переменная с четырьмя неравно-наполненными категориями: А - 2 наблюдения, В - 100 наблюдений, С - 2 наблюдения, D - 2 наблюдения. Оцениваемая модель предсказывает классы следующим образом:

Класс A: 1 верно и 1 неверно;

Класс B: 10 верно и 90 неверно;

Класс C: 1 верно и 1 неверно;

Класс D: 1 верно и 1 неверно.

В таком случае макро-среднее будет равно:

А микро-среднее будет рано:

Таким образом, макро-среднее учитывает точность предсказания каждого из классов в равной степени, вне зависимости от их размеров, а на показатель микро-среднего в большей степени влияет точность предсказания больших по объему классов.Многоклассовая классификация. Введение в машинное обучение // Сoursera.org URL: https://ru.coursera.org/lecture/vvedenie-mashinnoe-obuchenie/mnoghoklassovaia-klassifikatsiia-P9Zun (дата обращения: 10.12.2018).

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

Адаптация показателя AUC для небинарных переменных является чуть более сложной, т.к. при наличии C категорий целевой переменной ROC - пространство имеет C*(C-1) степеней свободы, т.е. для переменной с тремя значениями ROC пространство становится трехмерным и ROC-кривая превращается в ROC-плоскость. И если расчет площади под графиком трехмерного ROC-пространства ещё может быть проведен, то дальнейшее увеличение количества категорий целевой переменной делает этот метод малоприменимым. Srinivasan, A. Note on the Location of Optimal Classifiers in N-dimensional ROC Space // Technical Report PRG-TR-2-99, Oxford University Computing Laboratory. - 1999.

Существует ещё один способ адаптации ROC-кривых для небинарных классификаторов - так называемая «один против всех» перекодировка. Идея метода заключается в перекодировании целевой переменной в бинарную таким образом, что в первой категории остается только один класс наблюдений, а во второй - все остальные. Подобная перекодировка проводится для всех классов изначальной переменной. Во время каждой перекодировки для класса оценивается его показатель AUC. Наконец, после расчёта AUC для всех классов, вычисляется их арифметическое среднее. DAVID J. HAND, ROBERT J. TILL A Simple Generalisation of the Area Under the ROC Curve for Multiple Class Classification Problems // Machine Learning. - 2001. - №45.

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

Порядковая целевая переменная

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

Интервальная целевая переменная

Для оценки моделей, предсказывающих значение непрерывной переменной в сравнительных исследованиях моделей чаще всего применяются различные вариации критерия стандартной ошибки. Одним из наиболее популярных критериев является RMSE - (Root Mean Squared Error) - корень среднеквадратичной ошибки модели (также известен как RASE (Root Average Squared Error). Zaidah Ibrahim, Daliela Rusli predicting students' academic performance: comparing artificial neural network, decision tree and linear regression // 21st Annual SAS Malaysia Forum, 5th September. - 2007. Geoffrey K.F. Tso, Kelvin K.W. Yau Predicting electricity energy consumption: A comparison of regression analysis, decision tree and neural networks // Energy. - 2007. - №32. - С. 1761-1768. Показатель RMSE рассчитывается по формуле:

Где MSE - средняя квадратичная ошибка, SSE - сумма квадратов ошибок в оценках целевой/зависимой переменной, а n - число наблюдений. Очевидно, идеальная модель точно предсказывает значение все наблюдений, а значит корень средней стандартной ошибки у такой модели равен нулю. На практике идеальные модели практически не встречаются, но для целей настоящей работы это означает, что меньшие значения показателя RMSE соответствуют более точной модели.

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

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

· Для моделей с номинальной или порядковой целевой/зависимой переменной - критерии точности, специфичности и чувствительности, а также показатель AUC.

· Для моделей с непрерывной целевой/зависимой переменной - величина корня среднеквадратичной ошибки.

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

Наконец, для того, чтобы избежать переобучения моделей и, как следствие, искусственного завышения показателей качества, модели будут строиться и оцениваться на разных случайно сгенерированных подвыборках. Наблюдения, на основе которых будет оцениваться модель будут случайным образом разделены на две группы в соотношении 75%:25%. Модели будут строиться на первой, большей подвыборке, а качество модели будет оцениваться по результатам применения её к меньшей подвыборке. Подобный подход является общепринятым средством контроля над переобучением моделей. Training and Test Sets: Splitting Data // Machine Learning Crash Course. Google's fast-paced, practical introduction to machine learning URL: https://developers.google.com/machine-learning/crash-course/training-and-test-sets/splitting-data (дата обращения: 09.11.2018). Everitt B.S., Skrondal A. Overfitting // Cambridge Dictionary of Statistics. 2010. С. Cambridge University Press.

3.1 Выбор данных для проведения анализа

Наконец, необходимо выбрать набор данных, на котором будут построены модели. Исходя из проведённого выше обзора модно выдвинуть следующие требования к набору данных:

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

Достаточное количество наблюдений. Деревья решений обычно показывают плохие результаты при построении на маленьких выборках. Число наблюдений должно быть не менее 2000.

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

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

По мнению автора, подходящим набором данных для построения и сравнения моделей может стать база лонгитюдного обследование домохозяйств RLMS-HSE (РМЭЗ НИУ ВШЭ). RLMS представляет собой серию ежегодных общенациональных репрезентативных опросов на базе вероятностной стратифицированной многоступенчатой территориальной выборки.

В базе данных RLMS объединены наблюдения за 22 года проведения обследования, начиная с 1994 г. В базе присутствуют переменные, описывающие структуру доходов и расходов, материальное благосостояние, статус занятости, миграционное поведение, здоровье, структуру питания, образовательное поведение, досуге т.д. Российский мониторинг экономического положения и здоровья населения НИУ ВШЭ // Национальный исследовательский университет «Высшая школа экономики» URL: https://www.hse.ru/rlms/ (дата обращения: 14.05.2018).

База данных RLMS соответствует всем, указанным выше критериям. Кажется, обосновывать социологический характер данных, содержащихся в этой базе будет излишним, но в качестве доказательства того, что эти данные действительно применяются при проведении социологических исследований можно привести тот факт, что по данным Высшей Школы Экономики только в 2017 году на основе этих данных было опубликовано как минимум 109 статей в периодических изданиях. Публикации 2017 года // Российский мониторинг экономического положения и здоровья населения НИУ ВШЭ URL: https://www.hse.ru/rlms/ (дата обращения: 14.05.2018).

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

Наконец, тот факт, что во многих из этих работ применяются методы регрессионного анализа можно воспринимать как указание на соответствие распределений по крайней мере некоторых переменных исследования предпосылкам регрессионных моделей. См. к примеру. Yaroslav M., Tatiana R. Estimation of the Russian informal economy size on the household budget survey data // Cogent Economics & Finance. - 2017. - №5 (1).

3.2 Выбор моделей

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

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

Таблица 1

Работы - источники моделей

Интервальная	Порядковая	Категориальная бинарная	Категориальная небинарная
Тихонова Н.Е., Каравай А.В. Человеческий капитал российских рабочих: общее состояние и специфические особенности // Мир России. 2017. Т. 26. № 3. С. 6-35.	Senik, C. (2004). When information dominates comparison. Journal of Public Economics, 88(9-10), 2099-2123. doi:10.1016/s0047-2727(03)00066-5	Brzezinski, M. (2017). Diagnosing Unhappiness Dynamics: Evidence from Poland and Russia. University of Warsaw. Working Papers No. 2017-27.	Зудина А. А. Дороги, ведущие молодежь в NEET: случай России // Экономический журнал ВШЭ. 2018. Т. 22. № 2. С. 197-227.
Salahodjaev, R., & Ibragimova, N. (2018). Height and Life Satisfaction: Evidence from Russia. Applied Research in Quality of Life.doi:10.1007/s11482-018-9672-6	Nevalennaya A. Socio-demographic characteristics, alcohol drinking and self-rated health among Russian women // Centre for Health Equity Studies. 2014.	Radaev V.V. Divergent drinking patterns and factors affecting homemade alcohol consumption (the case of Russia) // International Journal of Drug Policy. 2016. №34. С. 88-95.	Лапшинова В. В., Рощина Я. М. Доступность добровольного Медицинского страхования в России // Вестник Российского мониторинга экономического положения и здоровья населения НИУ ВШЭ. Вып. 5. - М.: Нац. исслед. ун-т «Высшая школа экономи-ки», 2015. - 211 с.
Бирюкова С.С., Макаренцева А.О. Оценки "штрафа за материнство" в России //Население и экономика. 2017;11):50-70.	Мамонова, Наталья & Зайцев, Егор. (2018). Пробит-моделирование национальной солидарности на примере России. Известия Байкальского государственного университета. 28. 315-324. 10.17150/2500-2759.2018.28(2).315-324.	Гимпельсон В. Е., Капелюшников Р. И., Шарунина А. В. Низкооплачиваемые рабочие места на российском рынке труда: есть ли выход и куда он ведет? //Экономический журнал Высшей школы экономики. 2018. Т. 22. №. 4. C. 489-530.	Федорова Е.П., Утаралиева Р.Т. Внутрифирменная мобильность на российском рынке труда //Baikal Research Journal. 2017. Т. 8. №. 3. DOI: https://doi.org/10.17150/2411-6262.2017.8(3).12

4. Построение и оценка моделей

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

...