Алгоритм бинарной классификации на основе графов принятия решений в задачах кредитного скоринга

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

Важной настройкой алгоритма является такой параметр, как глубина обучения - количество узлов дерева, используемых для классификации по одному из признаков [5]. По причине того, что алгоритмы на основе деревьев решений относятся к «жадным», они имеют склонность к переобучению модели, что значительно усложняет оптимизацию деревьев. Снижение эффекта переобучения может быть достигнуто путем управления сложностью модели, например, с помощью различных критериев остановки, таких как ограничение глубины построения дерева и последующая «обрезка» (pruning) отдельных ветвей деревьев, что в итоге накладывает неявные ограничения на возможности алгоритма классификации, делая его не столь простым и универсальным [6].

На качество обучения, конечно же, влияет и объем выборки, который требуется для построения точной классификационной модели. Однако если на текущем наборе данных не удается выстроить качественную модель, то необходимы модификации базового алгоритма деревьев решений. В основе создания оптимальных правил классификации на выборке, которая не позволяет построить модель с приемлемым уровнем точности, лежат более сложные ансамблевые методы, такие как, например, randomforest (случайный лес) [7, 8] с последующей выборкой данных для обучения модели (bagging) или комбинированием работы нескольких алгоритмов на основе мажоритарного или мягкого голосования (boosting). Ансамблевые методы также накладывают ряд ограничений на исходный набор данных (датасет), размер которого должен быть достаточно большим, чтобы охватить большую часть сложности базового распределения, чтобы выборка из датасета была хорошим приближением к выборке из реального распределения (репрезентативность). Кроме того, выборки должны быть слабо коррелированными (независимыми).

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

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

Одним из направлений модификации ансамблевых алгоритмов на основе деревьев решений является использование рандомизированных ансамблей ориентированных ациклических графов принятия решений (decisionacyclicgraph DAG) [11, 12] в качестве средства получения компактных и в то же время точных классификационных моделей. В русскоязычных источниках этот подход называется графом решений, в англоязычной литературе чаще встречается наименование «джунгли» принятия решений [9] по аналогии с популярным алгоритмом бэггинга на деревьях принятия решений - random forest(случайного леса).

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

Рис. 1. Логика построения дерева решений (а) и графа решений (б)

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

Рассмотрим множество узлов на двух последовательных уровнях принятия решения DAG (см. рис. 1,б). Граф решений состоит из набора родительских N_pи дочерних N_cузлов. Глубина построения графа может быть обозначена как M= |N_c|. Пусть 0. - это правило классификации для родительского узла i е N_p, а S. - набор значений предикторов (x, у) для узла i. Зная 0. и S, можно вычислить набор значений предикторов узла i, проходящих через его левую и правую ветви соответственно [5, 9]:

Если l_i е N_c - значение левого внешнего ребра от родительского узла iе Nк дочернему узлу и r е N_c- значение правого внешнего ребра, тогда

набор значений предикторов, которые достигают любого родительского узла j е Ы_с, вычисляется как

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

(3)

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

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

(4)

где т - количество классов целевой переменной при номерах классов к = 1, 2,..., т. гдер_к -доля точек в прямоугольнике А (рис. 2,а), принадлежащих классу к. Эта мера принимает значения от 0 (когда все точки принадлежат к одному классу) и (т - 1)/т (когда все т классов представлены одинаковым количеством точек).

Значения индекса Джини в зависимости от р_к для двух классов показаны на рис. 2. Мера примеси находится на своем пике, когда р_к = 0,5 (т.е. когда прямоугольник содержит 50 % точек другого класса). Этот показатель также может быть использован для оценки качества классификации модели на основе графа принятия решений.

Рис. 2. Пример разбиения пространства признаков (а) и интерпретация неопределенности Джини (б) в задачах построения моделей классификации

Еще одним показателем оптимальности построения классификационной модели является энтропия Шеннона [14, 15], которая рассчитывается на основе гистограммы состояний и признаков процесса. Основной проблемой интерпретации показателя энтропии является «зашумленность» наблюдаемого процесса случайными событиями. Но при этом энтропия применяется для оценки «примесей» в задачах классификации и для прямоугольника А_к (см. рис. 2) определяется следующим образом:

Этот показатель колеблется от 0 (наиболее чистое разделение или все точки принадлежат к одному классу) до log₂(m) (в прямоугольнике все mклассов представлены одинаково). В случае двух классов мера энтропии достигает максимума при p_k= 0,5.

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

где Sj определяется по формуле (1), а H (Sj) - энтропия Шеннона меток

класса у в обучающем наборе предикторов (x,y)е S. Чем больше информационный прирост, тем полезнее взаимная информация всех узлов графа и тем он более полно описывает пространство признаков при минимальном количестве узлов. В случае, когда количество дочерних узлов M строго равно удвоенному количеству родительских узлов, т.е. M= 2 N_p, граф вырождается в дерево решений [9].

Результаты и обсуждение