Разработка алгоритмов ранговой регрессии для кредитного скоринга (отчет)

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

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

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

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

Цель проекта

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

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

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

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

Данные представляют собой матрицу объекты-признаки \|X\|_{i = 1..N}^{j = 1..M} и столбец ответов \|Y\|_{i = 1..N}. Признаки принимают действительные значения, ответы - натуральные из промежутка [0 \dots K-1].

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

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

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

SVM, Логистическая регрессия

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

Полная стратегия обучения или Full Fixed Margin approach (FFM)

Предположим, что есть некоторая функция f: x\to R, причем ее значения известны только по сравнению с набором порогов h_1 < \ldots < h_k. Объект x попадает в класс k если h_{k-1} \leq f(x) < h_k. Таким образом задача сводится к оценке функции \hat{f}(x) и порогов \hat{h}_k. Оцениваемую функцию положим линейной \hat{f}(x) = a^Tx. Тогда классификатор будет иметь вид:

\begin{cases}
a^Tx < \hat{h}_1 & \to y(x) = 0 \\
\hat{h}_1 \leq a^Tx < \hat{h}_2 & \to y(x) = 1 \\
\dots \\
\hat{h}_{K-1} \leq a^Tx < \hat{h}_K & \to y(x) = K
\end{cases}

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

\begin{cases}
a^Ta + C\sum_{i = 1}^N \sum_{j = 1}^M \delta_i^j \to \min_{a, h^j, \delta_i^j} \\
a^Tx_i - h_j \leq -1 + \delta_i^j, i: y_i < i \\
a^Tx_i - h_j \geq -1 + \delta_i^j, i: y_i >= i
\end{cases}
Вместо вышеуказанной оптимизационной задачи удобнее решать двойственную к ней:

\begin{cases}
\sum_{i = 1}^N \sum_{j = 1}^M \lambda_i^j - \frac{1}{2}\sum_{i = 1}^N \sum_{p = 1}^N \sum_{q = 1}^M\sum_{j = 1}^M g_i^j g_p^q x_i^Tx_p \lambda_i^j \lambda_p^q \to \max \\
\sum_{i=1}^N g_i^j\lambda_i^j = 0, 0\leq\lambda_i^j\leq \frac{C}{2}, i:y_i = j, j = 1..M
\end{cases}

\textrm{g_i^j = }
\begin{cases}
1 & y_i \geq j \\
-1 & y_i < j
\end{cases}
Зная оптимальные значения множителей Лагранжа, оптимальные значения параметров оценивадтся по следующим формулам:
a = \sum_{i = 1}^N (\sum_{j = 1}^M g_i^j\lambda_i^j)x_i, если множество I = \{i: 0 < \lambda_i^j < \frac{C}{2}\} не пусто, то h_j = \frac{\sum_I a^Tx_i - \sum_Ig_i^j}{|I|}, иначе:

\textrm{$h_j$ = }
\begin{cases}
\dot{h_j} = \max\{\max_{i: \lambda_i = 0, g_i = -1}(a^Tx_i + 1), \max_{i: \lambda_i = C/2, g_i = 1}(a^Tx_i - 1)\}, & \sum_{i: \lambda_i^j = C/2} g_i^j > 0 \\
\ddot{h_j} = \min\{\min_{i: \lambda_i = C/2, g_i = -1}(a^Tx_i + 1), \min_{i: \lambda_i = 0, g_i = 1}(a^Tx_i - 1)\}, & \sum_{i: \lambda_i^j = C/2} g_i^j < 0 \\
h_j \in [\dot{h_j}, \ddot{h_j}], & \sum_{i: \lambda_i^j = C/2} g_i^j = 0
\end{cases}

Логистическая ранговая регрессия

Предположим, что множество X\otimes Y является вероятностным пространством. Вероятность получения данных прецедентов при условии их независимости: p(X, Y | a, h) = \prod_{i = 1}^Np(x_i, y_i | a, h). Предположим, что плотность распределения векторов признаков объектов, при неизвестном ранге, равномерна, и не зависит от параметров гиперплоскостей, т.е.: p(x) = p(x | a, h) = const, методом наибольшего правдоподобия:

(a, h_1, \dots, h_K) = \arg\max \prod_{i = 1}^N p(x_i, y_i | a, h) = \arg\max \prod_{i = 1}^N p(y_i |x_i, a, h)p(x_i | a, h) = \arg\max \prod_{i = 1}^N p(y = y_i |x_i, a, h).
Пусть так же p(y \geq |x_i, a, h) = \frac{1}{1+exp[-(a^Tx - h_j)]}. При таких предположениях решение задачи сводиться к решению оптимизационной задачи:

\sum_{i: y_i = 0} \ln[1 - p(x_i | y \geq 1, a, h_1)] + \sum_{j=1}^{K-1} \sum_{i: y_i = j} \ln[p(x_i | y \geq j, a, h_j) - p(x_i | y \geq j+1, a, h_{j+1})] + \sum_{i: y_i = K} \ln[p(x_i | y \geq K, a, h_K)] \ra \max_{a, h_1, \ldots, h_K}

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

Пример работы программы:

%% This module shows how the algorithm works with real data (wine
%% classification) 
sizeTrainSet = 100
sizeControlSet = 100
 
%% load training set and control set
XTrain = load('Red.data');
XTrain = XTrain(1:sizeTrainSet, :);
YTrain = XTrain(:, 12);
YTrain = YTrain - min(YTrain) + 1;
XTrain = XTrain(:, 1:11);
hdim = max(YTrain) - 1;
 
%% load control set
XControl = load('Red.data');
XControl = XControl(sizeTrainSet + 1 : sizeTrainSet + sizeControlSet, :);
YControl = XControl(:, 12);
YControl = YControl - min(YControl) + 1;
XControl = XControl(:, 1:11);
 
%% learn algorithm. FFT method.
C = 0.01;
tic
[ a1, h1 ] = FfmTraining(XTrain, YTrain, hdim, C);
time1 = toc;
 
%% test FFT on learning set
RTrain1 = RankEstimate(a1, h1, XTrain);
ErrorsTrain1 = sum(abs(RTrain1 - YTrain) >= 2);
 
%% test FFT on control set
RControl1 = RankEstimate(a1, h1, XControl);
ErrorsControl1 = sum(abs(RControl1 - YControl) >= 2);
 
 
%% learn algorithm. Logistic regression method.
tic
[ a2, h2 ] = RankTraining(XTrain, YTrain, hdim);
time2 = toc
 
%% test Logistic regression on learning set
RTrain2 = RankEstimate(a2, h2, XTrain);
ErrorsTrain2 = sum(abs(RTrain2 - YTrain) >= 2);
 
%% test Logistic regression on control set
RControl2 = RankEstimate(a2, h2, XControl);
ErrorsControl2 = sum(abs(RControl2 - YControl) >= 2);

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

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

Алгоритмы проверялись на задаче wine classification с репозитория UCI.
размер обучения - 500
размер контроля - 1000
количество классов - 6

метод Ошибок на обучении не более чем в 1 ранг, % Ошибок на обучении не более чем в 2 ранга, % Ошибок на обучении не более чем в 3 ранга, % Ошибок на обучении не более чем в 4 ранга, % Ошибок на контроле не более чем в 1 ранг, % Ошибок на контроле не более чем в 2 ранга, % Ошибок на контроле не более чем в 3 ранга, % Ошибок на контроле не более чем в 4 ранга, % Время работы, сек
FFM 89.8 49.0 12.6 1.8 87.7 47.9 11.6 1.9 7017
Логистическая регрессия 89.4 51.2 3.2 0.2 85.9 44.7 4.4 0.8 0.71



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

  • Воронцов К.В. Лекции по линейным алгоритмам классификации
  • Куракин А.В. Байесовский принцип обучения в задаче восстановления ранговой модели данных
  • Mottl V., Tatarchuk A., Kurakin A. Support vector machines for ranking learning: the full and the truncated fixed margin strategies. International Conference on Machine Learning and Cybernatics, Hong Kong, China, 2007
  • Логистическая регрессия


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

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

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


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