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

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

Версия от 08:58, 12 марта 2012; Angriff (Обсуждение | вклад)

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

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

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

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

Используемые в данном проекте реальные данные «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$ проходит по дереву путь от корня до некоторого листа, согласно следующему алгоритму

$\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_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}{N}E(a,D^N)$ Минимизация функционала $Q(a,D^N)$ производится с помощью следующего алгоритма.

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

Вход:

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

Выход:

возвращает корневую вершину дерева, $\upsilon_{opt}$ .(оптимальное дерево, т.е без лишних ветвей)

ПРОЦЕДУРА $TreeChoice(\upsilon_0,D)$ ;
вычислить $E(a,D)$ и запомнить как параметр вершины;
eсли $\upsilon_{learn}$ — лист то
создать новый лист $\upsilon$ , с теми же параметрами;
вернуть $(\upsilon)$ ;
разбить выборку на две части $D=D_0\cup D_1$ по предикату $\delta$ ;
eсли $U_0$ = ∅ или $U_1$ = ∅ то
создать новый лист $\upsilon$ ;
$c_{\upsilon}$ — присвоить метку класса, которую имеет вершина $\upsilon_{learn}$ ;
иначе
создать новую внутреннюю вершину $\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$
вернуть $(\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^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$ максимум абсолютного значения корреляции монотонно убывает.

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

Описание системы: [1].
Файлы системы находятся в папке [2].

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

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

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

Рассмотрим задачу «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=<Q>)	стоимость ошибок на контроле (CV=<Q>)	средняя стоимость ошибок при обучении, 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%

Для сравнения приведем результаты работы разных алгоритмов на данных German с использованием 10-fold cross validation:

Название алгоритма	Средняя стоимость ошибкок при обучении	Средняя стоимость ошибкок на контроле
Discrim	0.509	0.535
Quadisc	0.431	0.619
Logdisc	0.499	0.538
SMART	0.389	0.601
ALLOC80	0.597	0.584
k-NN	0.000	0.694
k-NN,k=17, eucl,std	-	0.411
CASTLE	0.582	0.583
CART	0.581	0.613
IndCART	0.069	0.761
NewID	0.000	0.925
AC2	0.000	0.878
Baytree	0.126	0.778
NaiveBay	0.600	0.703
CN2	0.000	0.856
C4.5	0.640	0.985
ITrule	*	0.879
Cal5	0.600	0.603
Kohonen	0.689	1.160
DIPOL92	0.574	0.599
Backprop	0.446	0.772
RBF	0.848	0.971
LVQ	0.229	0.963
LogTree	0.043	0.610
LogTree, LALR	0.028	0.170

Последние две строки таблицы - результат работы представленных алгоритмов. Данные для построения таблицы взяты с http://www.is.umk.pl/projects/datasets-stat.html. Для наглядности представлен график зависимости средней стоимости ошибкок на контроле от средней стоимости ошибкок при обучении. Точками обозначены алгоритмы.

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

Смотри также

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

Efron, B.; Hastie, T.; Johnstone, I. & Tibshirani, R. Least angle regression. — 2004.

Hastie, T.; Taylor, J.; Tibshirani, R. & Walther, G. Forward Stagewise Regression and the Monotone Lasso. — 2006.
Madigan, D. & Ridgeway., G. Discussion of least angle regression.. — 2004.
Jerome Friedman, T. H. & Tibshirani, R. Additive Logistic Regression: A Statistical View of Boosting. — 2000.

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

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

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

Срок: 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»

Категория: Практика и вычислительные эксперименты