Сравнение алгоритмов классификации для кредитного скоринга (отчет)

Материал из MachineLearning.

Перейти к: навигация, поиск

Введение в проект

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

Описание проекта

Используемые в данном проекте реальные данные «German Credit Data», являются удобным инструментом тестирования различных алгоритмов классификации и их модификаций, а также сравнения их со стандартными алгоритмами.

Цель проекта

Разработка и сравнение алгоритмов классификации для кредитного скоринга.

Обоснование проекта

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

Описание данных

Данные взяты из репозитория UCI: Statlog (German Credit Data) Data Set . В выборке представлено 1000 объектов. Объектами являются анкеты людей, желавших получить кредит в банке. Изначально анкеты содержали 20 пунктов, таких как состояние банковсого счета заемщика, информация о его кредитной истории, цель займа, величина займа, возраст заемщика, время с момента трудоустройства на текущее место работы и другие. Но так как некоторые из них не были числовыми, а многие алгоритмы (в том числе рассматриваемый в данной статье) работают только с числовыми признаками, то из 20 разнородных признаков было составлено 24 числовых. Классы — «хорошим — 0» или «плохим — 1» заемщиком оказался человек, получивший кредит. По условию задачи, распознать «плохого» заемщика как «хорошего» в 5 раз хуже, чем «хорошего» как «плохого».

Критерии качества

Внутренним критерием качества служит среднеквадратичная ошибка S или критерий максимума логарифма правдоподобия. В данном случае критерии эквивалентны. Внешними критериями являются взвешенная сумма ошибок классификации Q для решающего дерева, а также средняя ошибка на контрольных данных для алгоритма отбора признаков. Критерием качества работы алгоритма служит скользящий контроль 10-fold Cross-Validation.

Требования к проекту

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

Используемые методы

В качестве алгоритма классификации используется бинарное решающее дерево с разделяющими гиперплоскостями в вершинах. Гиперплоскости настраиваются с помощью логистической регрессии, без отбора признаков, либо с помощью LALR (Least Angle Logistic Regression), с отбором признаков.

Постановка задачи

Дана полная выборка D^N, состоящая из множества объектов X и множества классов \{0,1\}. Задана обучающая выборка D^m =\{(\mathbf{x}_i, y_i)\}_{i=1}^m, где \mathbf{x}_i\in\mathbb{R}^n, y_i\in\{0,1\}. В данном случае количество объектов N=1000 и количество признаков n=24. Задана также функция потерь \mathcal{L}(a(\mathbf{x}),y)) в виде матрицы

a(\mathbf{x})=0 a(\mathbf{x})=1
y=0 0 1
y=1 5 0

Требуется построить алгоритм классификации a:\;X\to\{0,1\}, который доставляет минимум функционалу качества

Q(a,X)=\frac{1}{N}\sum_{i=1}^N \mathcal{L}(a(\mathbf{x}_i,X^\ell),y_i)

Описание алгоритмов

Обзор литературы

Базовые предположения

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

Математическое описание

Основные понятия

Деревом называется конечный связный граф с множеством вершин V, не содержащий циклов и имеющий выделенную вершину \upsilon_0\in V, в которую не входит ни одно ребро. Эта вершина называется корнем дерева. Вершина, не имеющая выходящих ребер, называется терминальной или листом. Обозначим за T множество всех терминальных вершин дерева. Остальные вершины называются внутренними. Дерево называется бинарным, если из любой его внутренней вершины выходит ровно два ребра. Выходящие ребра связывают каждую внутреннюю вершину \upsilon с левой дочерней вершиной L_{\upsilon} и с правой дочерней вершиной R_{\upsilon}. Каждой внутренней вершине \upsilon\in V можно поставить в соответствие некоторый предикат \delta_{\upsilon}:\;X\to\{0,1\}, а каждой терминальной вершине \upsilon\in V можно приписать метку класса c_{\upsilon}\in\{0,1\}.

Классификация объекта бинарным решающим деревом

При классификации объект x\in X проходит по дереву путь от корня до некоторого листа, согласно следующему алгоритму

  1. \upsilon:=\upsilon_0,
  2. пока вершина \upsilon внутренняя
  3. eсли \delta_{\upsilon}(x)=1 то
    \upsilon:=R_{\upsilon}; (переход вправо)
  4. иначе
    \upsilon:=L_{\upsilon}; (переход влево)
  5. вернуть c_{\upsilon}.

Объект x доходит до вершины \upsilon тогда и только тогда, когда выполняется конъюнкция K_{\upsilon}(x), составленная из всех предикатов, приписанных внутренним вершинам дерева на пути от корня \upsilon_0 до вершины \upsilon. Множество объектов \Omega_{\upsilon}=\{x\in X: K_{\upsilon}(x)=1\}, выделяемых терминальными конъюнкциями \upsilon\in T, попарно не пересекаются, а их объединение совпадает со всем пространством X.

Отсюда следует, что алгоритм классификации a:\;X\to\{0,1\}, реализуемый бинарным решающим деревом, можно записать в виде простого голосования конъюнкций:

a(x)=\arg\max_{y\in\{0,1\}}\sum_{\upsilon\in T\\c_{\upsilon}=y}K_{\upsilon}(x),

причем \forall x\in X одно и только одно слагаемое во всех этих суммах равно единице.

Построение решающего дерева

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

Алгоритм построения решающего дерева

Вход:

  • D^m — обучающая выборка;

Выход:

  • возвращает корневую вершину дерева, \upsilon_0.
  1. ПРОЦЕДУРА LearnTree(D);
  2. eсли все объекты из D лежат в одном классе c\in\{0,1\} то
    создать новый лист \upsilon;
    c_{\upsilon}:=c;
    вернуть (\upsilon);
  3. найти оптимальные параметры разделяющей гиперплоскости:
    \mathbf{\beta}=\arg\min_{\mathbf{\beta}}S(\mathbf{\beta});
    положить \delta(\mathbf{x})=\begin{cases}1,\quad p(\mathbf{x},\mathbf{\beta})>=\frac{1}{2} \\ 0,\quad p(\mathbf{x},\mathbf{\beta})<\frac{1}{2} \end{cases};
  4. разбить выборку на две части D=D_0\cup D_1 по предикату \delta;
  5. eсли U_0 = ∅ или U_1 = ∅ то
    создать новый лист \upsilon;
    c_{\upsilon} — класс, в котором находится большинство объектов из D;
  6. иначе
    создать новую внутреннюю вершину \upsilon;
    L_{\upsilon} = LearnTree(D_0); (построить левое поддерево)
    R_{\upsilon} = LearnTree(D_1); (построить правое поддерево)
  7. вернуть (\upsilon)

Шаг 3 имеет следующую интерпретацию. Для каждой подвыборки D принимается модель логистической регрессии, согласно которой, свободные переменные \mathbf{x} и зависимая переменная \mathbf{y}\in Bernulli(\mathbf{p}) связаны соотношением

\mathbf{y}=\mathbf{p}+\varepsilon=\frac{1}{1+\exp(-X\mathbf{\beta})}+\varepsilon,

где \mathbf{\beta}=\{\beta_0,\beta_1,\ldots,\beta_n\} — вектор весов признаков (направляющий вектор разделяющей гиперплоскости). При ветвлении дерева ищется такой вектор параметров \mathbf{\beta}, который бы доставлял минимум функционалу среднеквадратичной ошибки

S(\mathbf{\beta})=||\mathbf{y}-\mathbf{p}||_2^2\to \min_{\mathbf{\beta}}

Оптимальный вектор параметров \mathbf{\beta} находится с помощью метода наименьших квадратов с итеративным пересчётом весов (IRLS), см. также логистическая регрессия (пример).

О сложности

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

Формально, будем считать, что алгоритмы классификации с помощью деревьев различной сложности принадлежат различным алгоритмическим моделям. Обозначим a_t — алгоритм классификации с помощью дерева T_t сложности t, т.е дерева, содержащего t гиперплоскостей. Некоторое фиксированное дерево T, сложности t, можно свести к дереву T_j, j\leq t, удалив необходимое количество гиперплоскостей. Обозначим A_T^j=\{a_j^1,a_j^2,\cdots} — множество всех алгоритмов классификации с помощью деревьев сложности j, полученных из дерева T.

Теперь рассмотрим некоторое бинарное решающее дерево T с t гиперплоскостями, построенное согласно вышеуказанному алгоритму. В этом случае A_T^t=\{a_t\}. Удаление любой терминальой гиперплоскости из дерева, уменьшит сложность дерева не единицу. Таким образом, получим некоторое множество A_T^{t-1}=\{a_{t-1}^1,a_{t-1}^2,\cdots\}, и т.д., удалив все, кроме одной, получим множество A_T^1=\{a_1\}. Задача состоит в том, чтобы выбрать из множества алгоритмов

A_T=A_T^1\cup\ldots\cup A_T^t

алгоритм a:\;X\to\{0,1\}, доставляющий минимум функционалу качества Q(a,X):

a=\arg\min_{a\in A_T}Q(a,X)

Обозначим функционал суммы ошибок

E(a,D^N)=\sum_{i=1}^N \mathcal{L}(a(\mathbf{x}_i,X^\ell),y_i)

В данном случае Q(a,D^N)=\frac{1}{l}E(a,D^N) Минимизация функционала Q(a,D^N) производится с помощью следующего алгоритма.

Алгоритм выбора оптимального решающего дерева

Вход:

  • корневая вершина дерева, \upsilon_{learn}.(построенное дерево)
  • полная выборка D^N (или тестовая выборка);

Выход:

  • возвращает корневую вершину дерева, \upsilon_{opt}.(оптимальное дерево, т.е без лишних ветвей)
  1. ПРОЦЕДУРА TreeChoice(\upsilon_0,D);
  2. вычислить E(a,D) и запомнить как параметр вершины;
  3. eсли \upsilon_{learn} — лист то
    создать новый лист \upsilon, с теми же параметрами;
    вернуть (\upsilon);
  4. разбить выборку на две части D=D_0\cup D_1 по предикату \delta;
  5. eсли U_0 = ∅ или U_1 = ∅ то
    создать новый лист \upsilon;
    c_{\upsilon} — присвоить метку класса, которую имеет вершина \upsilon_{learn};
  6. иначе
    создать новую внутреннюю вершину \upsilon;
    L_{\upsilon} = LearnTree(L_{\upsilon_{learn}}, D_0); (построить левое поддерево)
    R_{\upsilon} = LearnTree(R_{\upsilon_{learn}}, D_1); (построить правое поддерево)
    eсли E\leq L_{\upsilon}.E+R_{\upsilon}.E то
    вершину \upsilon сделать листом, с параметрами вершины \upsilon_{learn};
    иначе
    E:=L_{\upsilon}.E+R_{\upsilon}.E
  7. вернуть (\upsilon)

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

Варианты или модификации

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

Описание LALR

Предполагается, что столбцы матрицы объекты-признаки X (в матрицу дополнительно включен константный признак) линейно независимы и являются свободными переменными, а зависимая переменная \mathbf{y}\in Bernulli(\mathbf{p}). Принята модель логистической регрессии, согласно которой

\mathbf{y}=\mathbf{p}+\varepsilon=\frac{1}{1+\exp(-X\mathbf{\beta})}+\varepsilon=\frac{1}{1+\exp(-\mathbf{\mu})}+\varepsilon,

где \mathbf{\beta}=\{\beta_0,\beta_1,\ldots,\beta_n\} — вектор весов признаков. Требуется найти для каждого шага LALR вектор весов \mathbf{\beta} доставляющий минимум среднеквадратичной ошибки

S(\mathbf{\beta})=||\mathbf{y}-\mathbf{p}||^2

Обозначим множество индексов \mathcal{I}=\{1,2,\ldots,m\}. Для некоторого подмножества \mathcal{A}\subseteq\mathcal{I}, назовем его активным множеством, определим матрицу активных признаков


X_{\mathcal{A}}=(\cdots s_j\cdot\mathbf{x}_j \cdots)_{j\in\mathcal{A}},

где s_j\pm1. Определим также матрицы разностей и сумм для некоторого d\in\mathcal{A}^c,


M_{d-}=(\cdots (s_j\cdot\mathbf{x}_j-s_d\cdot\mathbf{x}_d) \cdots)_{j\in\mathcal{A}}


M_{d+}=(\cdots (s_j\cdot\mathbf{x}_j+s_d\cdot\mathbf{x}_d) \cdots)_{j\in\mathcal{A}}.

Далее, обозначим


A_{d\pm}=M_{d\pm}^T\mathbf{p}(1-\mathbf{p})X_{\mathcal{A}},


\mathbf{b}_{d\pm}=M_{d\pm}^T(\mathbf{y}-\mathbf{p}),

здесь «\pm» означает две разные матрицы, соответствующие «+» и «-».

Теперь полностью опишем алгоритм. Начальное приближение положим \hat{\mathbf{\mu}}=0,\quad\mathbf{\hat{\beta}}=0. Пусть \mathbf{\hat{\mu}}_{\mathcal{A}} текущее приближение функции регрессии. Вектор текущих корреляций имеет вид


\mathbf{\hat{c}}=X'(\mathbf{y}-\mathbf{p}(\mathbf{\hat{\mu}}_{\mathcal{A}})).

Положим


s_j=sign\{\hat{c}_j\}\qquad\forall j\in\mathcal{I}.

Новое приближение для оценки \mathbf{\hat{\mu}}_{\mathcal{A}} получаем при добавлении некоторой линейной комбинации выбранных активных признаков


\mathbf{\hat{\mu}}_{\mathcal{A}_+}=\mathbf{\hat{\mu}}_{\mathcal{A}}+X_{\mathcal{A}}\mathbf{\hat{\gamma}}

где


\hat{\mathbf{\gamma}}=A^{-1}_{d^*}\mathbf{b}_{d^*},\qquad(*)


d^*=\arg\min_{d+,d-}{}^{+}\{\mathbf{\hat{c}}^T_{\mathcal{A}}A^{-1}_{d-}\mathbf{b}_{d-},\mathbf{\hat{c}}^T_{\mathcal{A}}A^{-1}_{d+}\mathbf{b}_{d+}\},


d=\arg\min_{d\in\mathcal{A}^c}{}^{+}\{\mathbf{\hat{c}}^T_{\mathcal{A}}A^{-1}_{d-}\mathbf{b}_{d-},\mathbf{\hat{c}}^T_{\mathcal{A}}A^{-1}_{d+}\mathbf{b}_{d+}\};

«\min{}^{+}» означает, что минимум берется только из положительных значений. В случае когда \mathcal{A} пусто, что соответствует первой итерации, d находится из условия максимума абсолютной корреляции


d=\arg\max_{d\in\mathcal{I}}\{|\hat{c}_j|\}.

Таким образом, алгоритм определяет оптимальный признак \mathbf{x}_d, обновляет вектор весов \mathbf{\hat{\beta}}_{\mathcal{A}}=\mathbf{\hat{\beta}}_{\mathcal{A}}+\mathbf{s}_{\mathcal{A}}\mathbf{\hat{\gamma}} и добавляет новый активный индекс \mathcal{A}_+=\mathcal{A}\cup\{d\}. В итоге, алгоритм сделает m шагов. На последнем шаге, когда \mathcal{A}=\mathcal{I}, веса настраиваются стандартным итерационным МНК с перевзвешиванием элементов (IRLS), как и в логистической регрессии.

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

\ell(\mathbf{p})=\sum_{i=1}^my_i\ln(p_i)+(1-y_i)\ln(1-p_i),
при условии, что абсолютная корреляция нового вектора остатков \mathbf{y}-\mathbf{p}(\hat{\mu}_{\mathcal{A}}) на любой активный признак \mathbf{x}_{j}|j\in\mathcal{A} больше абсолютной корреляции на любой неактивный признак \mathbf{x}_{d}|d\in\mathcal{A}^c. Последующая линеаризация этих условий приводит к задаче линейного программирования:



\begin{cases}
\sum_{j\in\mathcal{A}}\hat{c}_j\gamma_j\to\min_{\mathbf{\gamma}} \\
\mathbf{A}_{d-}\mathbf{\gamma}\leq\mathbf{b}_{d-} \\
\mathbf{A}_{d+}\mathbf{\gamma}\leq\mathbf{b}_{d+} \\
\forall d\in\mathcal{A}^c 
\end{cases}
решение которой можно выразить в виде (*).

Применение LALR

Результатом работы алгоритма LALR является последовательность весов признаков . На каждом шаге добавлялся один признак, тем самым увеличивалось на единицу число настраиваемых параметров \{\mathbf{\beta}_1,\ldots,\mathbf{\beta}_n\}. Таким образом, получаем последовательность моделей с различным числом параметров. В качестве внешнего критерия выбора модели можно использовать информационный критерий Акаике (AIC)

AIC = 2k-2\ell(\mathbf{p}(\mathbf{\hat{\beta}}_k)),
где k — число параметров модели, в данном случае, число активных признаков, а \ell — максимум логарифма правдоподобия. Лучшая модель соответствует минимальному значению критерия Акаике.

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

Анализ работы LALR на модельных данных

Одним из наиболее простых методов отбора признаков является итеративный алгоритм Forward Stagewise. На каждом шаге алгоритм выбирает признак \mathbf{x}_j, имеющий наибольшую корреляцию с текущим вектором остатков \mathbf{y}-\mathbf{p}(\mathbf{\hat{\mu}}) и с достаточно малым по модулю шагом \gamma смещает текущее приближение \mathbf{\hat{\mu}} в направлении выбранного вектора \mathbf{x}_j,


j=\arg\max_{j\in\mathcal{I}}|\hat{c}_j|


\hat{\mu}\rightarrow\hat{\mu}+\gamma\cdot sign(\hat{c}_j)\cdot\mathbf{x}_j.

Чем меньше абсолютная величина шага \gamma, тем точнее оценка параметров, но вместе с тем возрастает трудоемкость.

Для сравнения двух алгоритмов мы сгенерировали m=1000 объектов с 10 независимыми, нормально распределенными признаками \mathbf{x}_i\sim\mathcal{N}_{10}(\mathbf{0},\mathbf{I}) и вектором ответов y_i\sim~Bern\big(\frac{1}{1+\exp(-\mathbf{x}_i^t\beta)}\big), где \beta\sim\mathcal{N}_{10}(0,1). На рисунке приведены результаты работы алгоритмов LALR и Forward Stagewise.

На первых двух графиках показана зависимость оценок весов \hat{\beta}_j от суммы их абсолютных значений \frac{\sum|\hat{\beta}_j|}{\max\sum|\hat{\beta}_j|}. Каждая ветвь обозначена номером, который соответствует выбранному признаку. Признак с номером 1 является константным. Видно, что последовательности выбираемых признаков совпадают. На нижних графиках приведена зависимость |\mathbf{\hat{c}}_k|, абсолютной текущей корреляциии признаков с вектором остатков, от шага k. Номера кривых соответствуют номерам признаков. Из графиков видно, что с ростом k максимум абсолютного значения корреляции монотонно убывает.

Описание системы

  • Ссылка на файл system.docs
  • Ссылка на файлы системы

Отчет о вычислительных экспериментах

Визуальный анализ работы алгоритма

Модельные данные

Рассмотрим задачу «XOR», которая представляет собой задачу классификации объектов с двумя признаками из 4-х кластеров, образующих линейно неразделимую выборку. В пределах каждого из кластеров объекты имеют нормальное распределение. Количество объектов каждого класса составляет 200 — обучающая выборка, 100 — контрольная.

На графике представлены результаны работы бинарного решающего дерева с логистической регрессией. По осям графика отложены координаты признаков. Точки — объекты, цвет точек обозначает принадлежность к тому или иному классу, цвет кружков вокруг точек — результат работы алгоритма. Прямые — суть разделяющие гиперплоскости; над каждой прямой указан номер, показывающий глубину дерева, и буква (R — правая дочерняя вершина, L — левая дочерняя вершина), указывающая направление ветвления дерева. Черным цветом показано оптимальное решающее дерево (отобранное с помощью TreeChoice), а дополнительные зеленые ветви показывают изначальное дерево (построенное с помощью LearnTree). В углу графика показано процентное соотношение обучающих и тестовых объектов, а также доля ошибок при классификации. Использование LALR в данном случае дает практически те же результаты, т.к всего 2 признака.

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

Оценка качества проводилась с помощью 10-кратного скользящего контроля, при котором вся выборка разбивалась на q=10 непересекающихся блоков примерно равной длины k_1,\ldots,k_q:

D^N = D^{k_1}_1\cup\cdots\cup D^{k_q}_q,

k_1+\dots+k_q = N. Каждый блок по очереди становился контрольной подвыборкой, при этом обучение производилось по остальным q-1 блокам. Критерий определяется как средняя ошибка на контрольной подвыборке:

CV(\mu,D^N)=\frac{1}{q}\sum_{n=1}^q Q\bigl(\mu(D^N\setminus D^{k_n}_n), D^{k_n}_n \bigr).

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

a=\arg\min_{n=1,\cdots,q} Q(\mu(D^m_n), D^N)

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

Алгоритм средняя стоимость ошибок при обучении (СV) средняя стоимость ошибок на контроле (CV) стоимость ошибок при обучении, Q-опт. стоимость ошибок на контроле, Q-опт. количество ошибок классификации при обучении. количество ошибок классификации на контроле.
LogTree 0.030 0.804 0.043 0.610 4.3% 29%
LogTree, LALR 0.013 0.274 0.028 0.170 2.3% 17%

Анализ зависимости работы алгоритма от параметров

Отчет о полученных результатах

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

Данная статья является непроверенным учебным заданием.
Студент: Константин Скипор
Преподаватель: В.В. Стрижов
Срок: 15 декабря 2009

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.


Личные инструменты