Chp4 Classification

数据挖掘导论 笔记 Classification

1 Overview

It is not suitable for describing ordinal number.
confusion matrix
accuracy
error rate

2 Decision Tree

Hunt:
1) $D_t$如果都是一个类的话，变成叶子结点
2) 若有多个类，按一定条件进行划分

如何分裂：
二元属性，直接分
标称属性，多路划分or二元划分(CART)
序数属性，不要打乱顺序
连续属性，可采用离散化的办法

不纯性度量，
$Entropy(t)=-\Sigma p_ilog(p_i)$
$Gini(t)=1-\Sigma p_i^2$
$Classification error=1-max(p_i)$
增益：$\Delta = I(parent)-\Sigma \frac{N_i}{N}I_i$
增益率：$Gain ratio=\frac{\Delta}{Split Info}, Split Info=-\Sigma p_i ln(p_i),p_i=\frac{N_i}{N}$

tree-pruning

properties:
1.非参数方法
2.最佳决策树是NP问题
3.构建快，分类也快
4.容易解释
5.某些特定的bool问题表现很差，如奇数个true值是0，偶数个true值是1
6.抗噪声
7.抗冗余属性，不相关属性造成的影响还是比较大的，要去掉
8.样本少于一定数量时，不分裂了，避免data fragment
9.子树重复
10.都是用一个数据进行划分，会出问题，解决办法：
斜决策树(oblique DT):x+y<1
构造归纳(constructive induction):构造新属性
11.不纯性度量方法对决策树影响较小。相比之下，树剪枝影响更大

3 Over fitting

原因：噪声，缺乏代表性样本

over fitting & multiple comparison procedure
在构造决策树时是有好多属性可以选择的，某一个带来的增益超过阈值可能性不大，但是所有的都超不过阈值可能性就少了，所以产生了过拟合，就和多重决策过程一样。

估计泛化误差：
1.训练误差
2.Occams razor：加入关于复杂度的惩罚项\ minimum description length,MDL
3.估计统计上界
4.使用validation set

处理over fitting：
先剪枝：提前终止生长
后剪枝：1.用叶节点代替子树，2.用子树中最常用的分支代替子树

4 Evaluation

1. hold out：validation set
2. random subsampling
3. cross validation
4. bootstrap(.632 bootstrap:$acc_{boot}=\frac{1}{b} \Sigma (0.632*\epsilon_i+0.368*acc_s)$)

5 Comparison

1 置信区间

binomial test
由$\frac{acc-p}{\sqrt{p(1-p)/N}}~N(0,1)$
可得在某一水平下的置信区间

2 比较两个模型的性能

模型$M_1,M_2$在$D_1,D_2$上评估，错误率为$e_1,e_2$，检验他们观测差是否是统计显著的。
$e_1,e_2$用正态分布来近似，$d=e_1-e_2,\hat\sigma^2=\frac{e_1(1-e_1)}{n_1}+\frac{e_2(1-e_2)}{n_2}$

3 比较两个分类法的性能

k-cross validation
每次$d_i=e_{1i} - e_{2i}$，$\bar d ~ t_{k-1}*\hat\sigma, \hat\sigma^2 = \frac{\Sigma(d_i-\bar d)}{k(k-1)}$