决策树和随机森林(2)
3.决策树的评价
记号：
假定样本总类别是K；
对于决策树的某叶节点，假定该叶节点中所含的样本个数为n，其中第K类样本个数为nkn_knk，k=1,2,⋯ ,Kk=1,2,\cdots,Kk=1,2,⋯,K，若某类样本nj=nn_j=nnj=n,而n1,⋯ ,nj−1,nj+1,⋯ ,nK=0n_1,\cdots,n_{j-1},n_{j+1},\cdots,n_K=0n1,⋯,nj−1,nj+1,⋯,nK=0,则称该节点为纯节点，若各类样本数目n1=n2=⋯=nK=nKn_1=n_2=\cdots=n_K=\frac{n}{K}n1=n2=⋯=nK=Kn，则称该样本为均样本；
纯节点熵Hp=0H_p=0Hp=0,最小；
均节点熵Hu=lnKH_u=lnKHu=lnK，最大；
对所有叶节点熵求和，该值越小，说明对样本的分类越精确，各叶节点包含的样本数目不同，可使用样本数加权求熵和。
评价函数:
C(T)=∑t∈leafNt⋅H(t)
C(T)=\sum_{t\in leaf}N_t \cdot H(t)
C(T)=t∈leaf∑Nt⋅H(t)
该损失函数越小越好，也可叫做“损失函数”。
3.决策树的过拟合
决策树对训练集有很好的分类能力，但对未知的测试数据未必有好的分类能力，泛化能力弱，即可能发生过拟合现象。
解决过拟合方法：
随机森林：
（1）Bagging策略:
从样本集中重采样（有重复的）选出n个样本；
在所有属性中，对这n个样本建立分类器（ID3，C4.5，CART，SVM，logistic回归）；
重复以上以上两步m次，即获取了m个分类器；
将数据放在这m个分类器中，根据投票结果，决定数据属于哪一类。
Bagging策略如下图示意：
（2）OOB数据
可以看出，Bootstrap（有放回采样）每次约有36.7936.79%36.79的样本不会出现在Bootstrap所采集的样本集合中，将未参与模型训练的数据叫做袋外数据（OOB），他可以取代测试集用于误差估计。Breiman以经验性实例的形式证明袋外数据误差估计与同训练集一样大小的测试集精度相同，得到的模型参数是无偏估计。
（3）随机森林
从样本集中用Bootstrap采样选出了n个样本；
从所有属性中随机选择k个属性，选择最佳分割属性作为节点建立CART决策树；
重复以上两步m次，即建立了m棵CART决策树;
这m个CART形成了随机森林，通过投票表决结果，决定数据属于哪一类。
4.随机森林和决策树的关系
可以使用决策树作为基本分类器，但也可以使用SVM，Logistic回归等其他分类器，习惯上，这些分类器组成的“总分类器“，仍然叫随机森林。
5.样本不均衡的常用处理方法
假定样本数目A类比B类多，且严重不平衡：
A类欠采样：随机欠采样，将A类分成若干子类，分别与B类进入ML模型，基于聚类的A类分割。
B类过采样，避免欠采样造成的信息丢失。
B类数据合成Synthetic Data Generation：随机插值得到新样本。
敏感学习：降低A类权值，提高B类权值。
6.随机森林的应用
（1）使用RF建立计算样本间相似度：
原理：若两个样本同时出现在相同叶节点的次数越多，则二者越相似。
算法过程：
记样本个数为N，初始化N×NN\times NN×N的零矩阵S，S[i,j]S[i,j]S[i,j]表示样本i和样本j的相似度。
对于m棵决策树形成的随机森林，遍历所有决策树的所有叶子节点：
记该叶子节点包含的样本为sample[1,2,⋯ ,k]sample[1,2,\cdots,k]sample[1,2,⋯,k],则 S[i][j]S[i][j]S[i][j]累加1。样本i,j∈sample[1,2,⋯ ,k]i,j\in sample[1,2,\cdots,k]i,j∈sample[1,2,⋯,k]，样本i.ji.ji.j出现在相同叶节点的次数增加1次。
遍历结束，则S为样本间相似度矩阵。
（2）使用RF计算特征重要度
随机森林是常用的衡量特征重要性的方法。计算正例经过的节点，使用经过节点的数目，经过节点的gini系数和等指标。或者，随机替换一列数据，重新建立决策树，计算新模型的正确率变化，从而考虑这一列特征的重要性。
（3）Isolation Forest
随机选择特征，随机选择分割点，生成一定深度的决策树iTree，若干课iTree组成iForest。计算iTree中样本x从根到叶子节点的长度f(x)，计算iForest中f(x)的总和F(x)F(x)F(x)。异常检测：若样本x为异常值，他应该在大多数iTree中很快达到叶子节点，即F(x)较小。
作者：bingxiash
