R 分而治之——决策树(Machine Learning With R by Brett Lantz)

来自 Machine Learning With R by Brett Lantz

基本背景

学习 Machine Learning With R by Brett Lantz 第五章——分治/决策树 。

决策树

决策树根据数据的属性采用树状结构建立决策模型。

决策树模型常常用来解决分类和回归问题。常见的算法包括:

  1. CART (Classification And Regression Tree);
  2. 随机森林 (Random Forest) 等;
  3. C5.0(J.Ross Quinlan 开发,ID3 -> C4.5 -> C5.0)。

一个决策树包含三种类型的节点:

  1. 决策节点:通常用矩形框来表示;
  2. 机会节点:通常用圆圈来表示;
  3. 终结点:通常用三角形来表示。

C5.0

较为流行的算法是 C5.0(在 Java 中,与其十分类似的是 J48,可在 RWeka 实现中使用),其单线程版遵循 GPL 协议开放源代码。

C5.0 建立的决策树模型与其他先进模型(神经网络、SVM)几乎一样好,而且易于部署。当然,C5.0 也是有缺陷的,比如说它容易 过度/不充分 拟合等。

信息熵

C5.0 使用信息熵度量,0 表示样本完全同质,1 表示样本凌乱的最大数量。信息熵定义如下:

Entropy(S) = ∑ i = 1c -pi log 2( pi )

与信息熵类似的数据不纯度度量方法还有基尼系数(Gini)。

信息增益

InfoGain(F) = Entropy(S1) – Entropy(S2)

其中 S1 是分割前数据分区,S2 是分割后数据分区。对于决策树节点最合适的特征选择,就是 Gain(A) 值最大的特征。

剪枝

修剪决策树,是为了能更好的推广的未知数据。分为两种:

  1. 预剪枝:当决策树达到一定数量的决策,或者决策节点仅含少量节点时,停止其增长;
  2. 后剪枝:当树过大时,依据节点错误率使用剪枝准则将决策树减小到何时大小。

C5.0 可以自动修剪,他关注许多准则,自行调整,包括运用子树提升子树替换

C5.0 识别高风险银行贷款

来自原书 5.2 节。

数据收集和划分

#!/usr/bin/env RScript

# Machine Learning With R by Brett Lantz

credit <- read.csv('credit.csv')
credit_length <- nrow(credit)

# Randomization
set.seed(12345)
credit_rand <- credit[order(runif(credit_length)), ]

num_train <- credit_length * .9

credit_train <- credit_rand[1:num_train, ]
credit_test <- credit_rand[(num_train + 1):credit_length, ]

C5.0 模型构建

# The C5.0 decision tree
library('C50')
library('gmodels')

credit_train$default<-as.factor(credit_train$default)

credit_model <- C5.0(credit_train[-17], credit_train$default)
credit_pred <- predict(credit_model, credit_test)

CrossTable(credit_test$default, credit_pred,
  prop.chisq = FALSE, prop.c = FALSE, prop.r = FALSE,
  dnn = c('actual default', 'predicted default'))

预测结果:

               | predicted default
actual default |         1 |         2 | Row Total |
---------------|-----------|-----------|-----------|
             1 |        54 |        14 |        68 |
               |     0.540 |     0.140 |           |
---------------|-----------|-----------|-----------|
             2 |        11 |        21 |        32 |
               |     0.110 |     0.210 |           |
---------------|-----------|-----------|-----------|
  Column Total |        65 |        35 |       100 |
---------------|-----------|-----------|-----------|

对角线为正确结果,错误率 25%。

自适应增强改进

采用自适应增强(adaptive boosting)算法,添加 trials 参数,表示模型中添加独立决策树的数量,在额外试验无法提高模型准确性时,添加将停止。

# Improve
credit_boost10 <- C5.0(credit_train[-17], credit_train$default,
  trials = 10)
credit_boost_pred10 <- predict(credit_boost10, credit_test)

CrossTable(credit_test$default, credit_boost_pred10,
  prop.chisq = FALSE, prop.c = FALSE, prop.r = FALSE,
  dnn = c('actual default', 'predicted default'))

改进后的结果:

               | predicted default
actual default |         1 |         2 | Row Total |
---------------|-----------|-----------|-----------|
             1 |        63 |         5 |        68 |
               |     0.630 |     0.050 |           |
---------------|-----------|-----------|-----------|
             2 |        16 |        16 |        32 |
               |     0.160 |     0.160 |           |
---------------|-----------|-----------|-----------|
  Column Total |        79 |        21 |       100 |
---------------|-----------|-----------|-----------|

改进后错误率 21%。

使用代价矩阵

C5.0 可设置代价矩阵,将惩罚因子分配到不同类型上,此处设置违约的代价为最大值 4。

# Using error cost matrix
error_cost <- matrix(c(0, 1, 4, 0), nrow = 2)

credit_cost <- C5.0(credit_train[-17], credit_train$default,
  costs = error_cost)
credit_cost_pred <- predict(credit_cost, credit_test)

CrossTable(credit_test$default, credit_cost_pred,
  prop.chisq = FALSE, prop.c = FALSE, prop.r = FALSE,
  dnn = c('actual default', 'predicted default'))

结果:

               | predicted default
actual default |         1 |         2 | Row Total |
---------------|-----------|-----------|-----------|
             1 |        38 |        30 |        68 |
               |     0.380 |     0.300 |           |
---------------|-----------|-----------|-----------|
             2 |         5 |        27 |        32 |
               |     0.050 |     0.270 |           |
---------------|-----------|-----------|-----------|
  Column Total |        43 |        57 |       100 |
---------------|-----------|-----------|-----------|

错误率虽达到 35%,但错误类型不太一样了,违约类型错误预测率下降许多,增加错误肯定,减少错误否定是可以接受的。

参考:

  1. Machine Learning With R by Brett Lantz
  2. https://www.ibm.com/developerworks/cn/analytics/library/ba-1507-decisiontree-algorithm/index.html

作者: V

Web Dev

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Google photo

您的留言將使用 Google 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s