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

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

Версия от 15:15, 9 марта 2010; SkiporKostya (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

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

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

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

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

Цель проекта

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

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

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

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

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

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

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

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

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

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

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

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

Имеется множество объектов $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$ , количество объектов обучающей выборки $m=690$ и количество признаков $n=24$ . Задана также функция потерь $\mathcal{L}(a(\mathbf{x}),y))$ в виде матрицы

	$y=0$	$y=1$
$a(\mathbf{x})=0$	0	1
$a(\mathbf{x})=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$ проходит по дереву путь от корня до некоторого листа, согласно следующему алгоритму

$\upsilon:=\upsilon_0$ ,
пока вершина $\upsilon$ внутренняя
eсли $\delta_{\upsilon}(x)=1$ то
$\upsilon:=R_{\upsilon}$ ; (переход вправо)
иначе
$\upsilon:=L_{\upsilon}$ ; (переход влево)
вернуть $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$ .

ПРОЦЕДУРА $LearnTree(D)$ ;
eсли все объекты из $D$ лежат в одном классе $c\in\{0,1\}$ то
создать новый лист $\upsilon$ ;
$c_{\upsilon}:=c$ ;
вернуть $(\upsilon)$ ;
найти оптимальные параметры разделяющей гиперплоскости:
$\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}$ ;
разбить выборку на две части $D=D_0\cup D_1$ по предикату $\delta$ ;
eсли $U_0$ = ∅ или $U_1$ = ∅ то
создать новый лист $\upsilon$ ;
$c_{\upsilon}$ — класс, в котором находится большинство объектов из $D$ ;
иначе
создать новую внутреннюю вершину $\upsilon$ ;
$L_{\upsilon} = LearnTree(D_0)$ ; (построить левое поддерево)
$R_{\upsilon} = LearnTree(D_1)$ ; (построить правое поддерево)
вернуть $(\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_i$ — алгоритм классификации с помощью дерева $T_i$ сложности $i$ , т.е дерева, содержащего $i$ гиперплоскостей. Некоторое фиксированное дерево $T$ , сложности $t$ , можно свести к дереву $T_j$ , $j\leq t$ , удалив необходимое количество гиперплоскостей. Обозначим $A_T^j=\{a_j^1,a_j^2,\cdots}$ — множество всех алгоритмов классификации с помощью дерева $T_j$ , полученного из дерева $T$ .

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

$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)$

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

Описание 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
Ссылка на файлы системы

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

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

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

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

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

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

Данная статья является непроверенным учебным заданием.

Студент: Константин Скипор

Преподаватель: В.В. Стрижов

Срок: 15 декабря 2009

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

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

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A1%D1%80%D0%B0%D0%B2%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D0%B8%D1%84%D0%B8%D0%BA%D0%B0%D1%86%D0%B8%D0%B8_%D0%B4%D0%BB%D1%8F_%D0%BA%D1%80%D0%B5%D0%B4%D0%B8%D1%82%D0%BD%D0%BE%D0%B3%D0%BE_%D1%81%D0%BA%D0%BE%D1%80%D0%B8%D0%BD%D0%B3%D0%B0_%28%D0%BE%D1%82%D1%87%D0%B5%D1%82%29»

Категория: Непроверенные учебные задания