ASP.NET网站建设实战,站长统计芭乐官方网站下载,衡水网络推广 衡水网站建设,百度排名优化咨询电话文章目录1 决策树1.1决策树定义1.2信息增益1.3 信息增益的算法1.4 信息增益比2 决策树ID32.1 ID3树的构建2.2 决策树的剪枝2.2.1 损失函数定义与计算2.2.2 剪枝过程2.3 CART树2.3.1 CART回归树2.3.2 CART分类树2.3.3 CART树剪枝1 决策树
1.1决策树定义
决策树的基本组成…
文章目录1 决策树1.1决策树定义1.2信息增益1.3 信息增益的算法1.4 信息增益比2 决策树ID32.1 ID3树的构建2.2 决策树的剪枝2.2.1 损失函数定义与计算2.2.2 剪枝过程2.3 CART树2.3.1 CART回归树2.3.2 CART分类树2.3.3 CART树剪枝1 决策树
1.1决策树定义
决策树的基本组成决策节点、分支、叶子。
决策树表示给定特征条件下的概率分布。 条件概率分布定义在特征空间的一个划分上。将特征空间划分为互不相交的单元。并在每个单元上定义一个类的概率分布就构成了一个条件概率分布。 决策树的一条路径对应于划分中的一个单元。
决策树的本质是在特征空间上的切割。
1.2信息增益
熵设X是一个取有限个值的离散随机变量其概率分布为P(Xxi)pi,i1,2,3...nP(Xx_i)p_i,i1,2,3...nP(Xxi)pi,i1,2,3...n 那么X的熵为H(X)−∑i1npilogpiH(X)-\sum_{i1}^np_ilogp_iH(X)−∑i1npilogpi 对数以2为底或者以e为底这时熵的单位称为比特或者纳特。熵只依赖于X的分布而与X的具体取值无关。 熵的理论解释熵越大随机变量的不确定性越大。0H(X)logn0H(X)logn0H(X)logn. 例如一个骰子6个面全是1那么H(X)−1∗log10H(X)-1*log10H(X)−1∗log10。因为结果是确定的。 如果6个面分别为1,2,3,4,5,6并且每个面的概率相同都是16\dfrac{1}{6}61。那么H(X)−(16log(16)16log(16)16log(16)16log(16)16log(16)16log(16))−(0.17∗(−2.58)∗6)2.58H(X)-(\dfrac{1}{6}log(\dfrac{1}{6})\dfrac{1}{6}log(\dfrac{1}{6})\dfrac{1}{6}log(\dfrac{1}{6})\dfrac{1}{6}log(\dfrac{1}{6})\dfrac{1}{6}log(\dfrac{1}{6})\dfrac{1}{6}log(\dfrac{1}{6}))-(0.17*(-2.58)*6)2.58H(X)−(61log(61)61log(61)61log(61)61log(61)61log(61)61log(61))−(0.17∗(−2.58)∗6)2.58这个时候的不确定性就比刚才要高。
设有随机变量(X,Y)其联合概率分布为P(Xxi,Yyi)pi,j,i1,2,3...n;j1,2,3...mP(Xx_i,Yy_i)p_{i,j},i1,2,3...n; j1,2,3...mP(Xxi,Yyi)pi,j,i1,2,3...n;j1,2,3...m 条件熵H(Y|X)表示在已知随机变量X的条件下Y的不确定性。定义为X给定条件下Y的条件概率分布的熵对X的数学期望H(Y∣X)∑i1npiH(Y∣Xxi)H(Y|X)\sum_{i1}^np_iH(Y|Xx_i)H(Y∣X)∑i1npiH(Y∣Xxi)
当熵和条件熵由数据估计得到时分别称为经验熵与经验条件熵。
信息增益特征A对训练数据集D的信息增益g(D,A)定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差g(D,A)H(D)−H(D∣A)g(D,A)H(D)-H(D|A)g(D,A)H(D)−H(D∣A) 这表示了特征X的引入使得分类Y的不确定性减少的程度。 互信息信息熵H(Y)-条件熵H(Y|X)
1.3 信息增益的算法
设训练数据集为D |D|表示其样本容量即样本个数 设有K个类CkC_kCk,k1,2,3…K ∣Ck∣|C_k|∣Ck∣表示属于类CkC_kCk的样本数 特征A有n个不同的取值{a1,a2,...ana_1,a_2,...a_na1,a2,...an}。根据特征A的取值将D划分为n个子集D1,D2...DnD_1,D_2...D_nD1,D2...Dn。 ∣Di∣|D_i|∣Di∣为子集DiD_iDi的样本个数 子集DiD_iDi中属于类CkC_kCk的样本集合为DikD_{ik}Dik ∣Dik∣|D_{ik}|∣Dik∣为集合DikD_{ik}Dik的样本数
输入数据集D以及特征A 输出特征A对数据集的信息增益g(D,A) 1 计算数据集D的经验熵H(D)H(D)−∑k1K∣Ck∣∣D∣log2∣Ck∣∣D∣H(D)-\sum_{k1}^K\dfrac{|C_k|}{|D|}log_2\dfrac{|C_k|}{|D|}H(D)−∑k1K∣D∣∣Ck∣log2∣D∣∣Ck∣ 2 计算特征A对数据集D的经验条件熵H(D|A):H(D∣A)∑i1n∣Di∣∣D∣H(Di)∑i1n∣Di∣∣D∣∑k1K∣Dik∣∣Di∣log2∣Dik∣∣Di∣H(D|A)\sum_{i1}^n\dfrac{|D_i|}{|D|}H(D_i)\sum_{i1}^n\dfrac{|D_i|}{|D|}\sum_{k1}^K\dfrac{|D_{ik}|}{|D_i|}log_2\dfrac{|D_{ik}|}{|D_i|}H(D∣A)∑i1n∣D∣∣Di∣H(Di)∑i1n∣D∣∣Di∣∑k1K∣Di∣∣Dik∣log2∣Di∣∣Dik∣ 3 计算信息增益g(D,A):g(D,A)H(D)−H(D∣A)g(D,A)H(D)-H(D|A)g(D,A)H(D)−H(D∣A)
1.4 信息增益比
以信息增益来选择特征会倾向于选择特征取值多的特征。可以使用信息增益比来解决这个问题。
特征A对数据集D的信息增益比定义为信息增益与训练数据集D关于特征A的值的熵的比gR(D,A)g(D,A)HA(D)g_R(D,A)\dfrac{g(D,A)}{H_A(D)}gR(D,A)HA(D)g(D,A) HA(D)−∑i1n∣Di∣∣D∣log2∣Di∣∣D∣H_A(D)-\sum_{i1}^n\dfrac{|D_i|}{|D|}log_2\dfrac{|D_i|}{|D|}HA(D)−∑i1n∣D∣∣Di∣log2∣D∣∣Di∣n为特征A的取值个数
2 决策树ID3
2.1 ID3树的构建
按照信息增益选择特征形成的决策树称为ID3树。
输入训练数据集D、特征集合A、阈值ϵ\epsilonϵ 输出决策树T 1 若D中所有实例属于同一类CkC_kCk则T为单节点树并将类CkC_kCk作为该节点的类标签返回T 2 若A∅A\emptyA∅则T为单节点树并选择D中实例数最大的类CkC_kCk作为该节点的类标签返回T 3 按照信息增益的算法计算特征集合A中每个特征对D的信息增益选择信息增益最大的特征AgA_gAg; 4 如果AgA_gAg的信息增益小于阈值ϵ\epsilonϵ则T为单节点树并选择D中实例数最大的类CkC_kCk作为该节点的类标签返回T 5 否则对AgA_gAg的每一个可能的值aia_iai依AgaiA_ga_iAgai将D分割为若干非空子集DiD_iDi将DiD_iDi中实例数最大的类作为节点标记构建子节点。由节点及其子节点构成树T返回T 6 对第i个子节点以数据集DiD_iDi作为训练集以A-{AgA_gAg}为特征集递归地调用步骤1-5得到子树TiT_iTi返回TiT_iTi。
2.2 决策树的剪枝
2.2.1 损失函数定义与计算
通过极小化 决策树整体的损失函数 来实现。 设树|T|的叶子节点个数为|T|t是树T的叶子节点该叶子节点有NtN_tNt个样本。其中k类的样本量为NtkN_{tk}Ntkk1,2,3…K。 说明一棵树T的叶子节点不一定只包含一类数据。例如在上述步骤2和5就可能一个节点中实际存在多个类别的数据。只是因为再细分特征的信息增益太小了不再划分。
Ht(T)H_t(T)Ht(T)为叶子节点t上的经验熵α0\alpha0α0为参数 损失函数Cα(T)∑i1∣T∣NtHt(T)α∣T∣C_{\alpha}(T)\sum_{i1}^{|T|}N_tH_t(T)\alpha|T|Cα(T)∑i1∣T∣NtHt(T)α∣T∣ 说明树的损失函数对所有叶子节点的遍历。每一个叶子节点计算当前叶子节点个数NtN_tNt以及叶子节点的熵Ht(T)H_t(T)Ht(T)。它们的乘积表示当前叶子节点不确定的度量也就是损失。对所有叶子节点不确定性的度量就称为树的损失。 α∣T∣\alpha|T|α∣T∣是为了防止树过拟合。
∑i1∣T∣NtHt(T)\sum_{i1}^{|T|}N_tH_t(T)∑i1∣T∣NtHt(T)熵越小说明叶子节点越来越多这一部分会使得模型越来越复杂。α∣T∣\alpha|T|α∣T∣是为了对抗模型过渡复杂。
经验熵Ht(T)−∑kNtkNtlogNtkNtH_t(T)-\sum_k\dfrac{N_{tk}}{N_t}log\dfrac{N_{tk}}{N_t}Ht(T)−∑kNtNtklogNtNtk
C(T)∑i1∣T∣NtHt(T)−∑i1∣T∣∑k1KNtklogNtkNtC(T) \sum_{i1}^{|T|}N_tH_t(T)-\sum_{i1}^{|T|}\sum_{k1}^KN_{tk}log\dfrac{N_{tk}}{N_t}C(T)∑i1∣T∣NtHt(T)−∑i1∣T∣∑k1KNtklogNtNtk
那么 Cα(T)C(T)α∣T∣C_{\alpha}(T)C(T)\alpha|T|Cα(T)C(T)α∣T∣
2.2.2 剪枝过程
输入决策树T参数α\alphaα 输出剪枝后的子树TαT_{\alpha}Tα 1 计算每个节点的经验熵 2 递归地从树的叶子结点向上缩 设一组叶子节点回缩到其父节点之前与之后的损失函数分别为Cα(TB)C_{\alpha}(T_B)Cα(TB)Cα(TA)C_{\alpha}(T_A)Cα(TA) 如果Cα(TA)C_{\alpha}(T_A)Cα(TA)Cα(TB)C_{\alpha}(T_B)Cα(TB),则进行剪枝。 3 返回2直至不能继续为止得到损失最小的子树TaT_aTa。
以上过程将信息增益换成信息增益比那么得到的树就是C4.5。
2.3 CART树
CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。 CART树是一棵二叉树。左分支的取值为是右分支的取值为否。 这样的决策树等价于递归地二分每个特征将输入空间划分为有限个单元并在这些单元上确定预测的概率分布。 CART算法决策树生成 决策树剪枝
2.3.1 CART回归树
树的定义
设Y是连续变量给定训练数据集D{(x1,y1),(x2,y2),...(xn,yn)}D\{(x_1,y_1),(x_2,y_2),...(x_n,y_n)\}D{(x1,y1),(x2,y2),...(xn,yn)}yi∈Ry_i \in Ryi∈R 。假设已经将输入空间划分为M个单元R1,R2…Rm每个单元上RmR_mRm上有一个固定的输出CmC_mCm则回归树表示为f(x)∑m1MCmI(x∈Rm)f(x)\sum_{m1}^MC_mI(x\in R_m)f(x)∑m1MCmI(x∈Rm) 备注遍历所有分割的子空间数据属于某个子空间函数值就是该空间的输出值。
求解每个单元上的最优输出值
平方误差来表示预测误差用平方误差最小准则求解每个单元上的最优输出值∑xi∈Rm(yi−f(x))2\sum_{x_i \in R_m}(y_i-f(x))^2∑xi∈Rm(yi−f(x))2
那么RmR_mRm上的CmC_mCm的最优值怎么计算呢cm^ave(yi∣xi∈Rm)\hat{c_m} ave(y_i|x_i \in R_m)cm^ave(yi∣xi∈Rm) 使用落在RmR_mRm空间内所有点的y值求平均得到。
如何对输入空间进行划分
使用启发式选择的方法。 选择第j个变量x(j)x^{(j)}x(j)和它的取值s作为切分变量和切分点定义两个区域一个是比s小的一个是比s大的R1{x∣x(j)s}R_1\{x|x^{(j)}s\}R1{x∣x(j)s}R2{x∣x(j)s}R_2\{x|x^{(j)}s\}R2{x∣x(j)s}
寻找最优切分变量和切分点 minj,s[mine1∑xi∈R1(yi−c1)2mine2∑xi∈R2(yi−c2)2]min_{j,s}[min_{e_1}\sum_{x_i \in R_1}(y_i-c_1)^2min_{e2}\sum_{x_i\in R_2}(y_i-c_2)^2]minj,s[mine1∑xi∈R1(yi−c1)2mine2∑xi∈R2(yi−c2)2]
c1^ave(yi∣xi∈R1)\hat{c_1}ave(y_i|x_i\in R_1)c1^ave(yi∣xi∈R1) c2^ave(yi∣xi∈R2)\hat{c_2}ave(y_i|x_i\in R_2)c2^ave(yi∣xi∈R2) 使得两部分误差和最小的变量j和切分点s 需要对所有变量和所有切分点遍历。这是NP问题吧
再对两个区域重复上述划分直到满足停止条件。
总结成算法是这样的最小二乘回归树生成算法。 输入训练数据集D 输出回归树f(x) 在训练数据集所在的输入空间中递归地将每个区域划分为2个子区域并决定每个子区域上的输出值构建二叉决策树。 1 选择最优切分变量j和切分点s求解
minj,s[mine1∑xi∈R1(yi−c1)2mine2∑xi∈R2(yi−c2)2]min_{j,s}[min_{e_1}\sum_{x_i \in R_1}(y_i-c_1)^2min_{e2}\sum_{x_i\in R_2}(y_i-c_2)^2]minj,s[mine1∑xi∈R1(yi−c1)2mine2∑xi∈R2(yi−c2)2]
遍历变量j对固定的切分变量j扫描切分点s选择使得上式达到最小值的对j,s 2 用选定的对(j,s)划分区域并决定相应的输出值 R1{x∣x(j)s}R_1\{x|x^{(j)}s\}R1{x∣x(j)s} R2{x∣x(j)s}R_2\{x|x^{(j)}s\}R2{x∣x(j)s} cm^1Nm∑xi∈Rm(j,s)yi\hat{c_m}\dfrac{1}{N_m}\sum_{x_i\in R_m(j,s)}y_icm^Nm1∑xi∈Rm(j,s)yix∈Rm,m1,2x\in R_m,m1,2x∈Rm,m1,2 每个子空间数据的y的平均值作为空间的输出。
3 继续对2个子区域调用步骤1,2直到满足停止条件 4 将输入空间划分为M个区域R1,R2,...RMR_1,R_2,...R_MR1,R2,...RM生成决策树f(x)∑m1MCmI(x∈Rm)f(x)\sum_{m1}^MC_mI(x\in R_m)f(x)∑m1MCmI(x∈Rm)
2.3.2 CART分类树
选择依据基尼指数 假设有K个分类每个样本点属于分类k的概率是PkP_kPk。则概率分布的基尼指数Gini(p)∑k1Kpk(1−pk)1−∑k1Kpk2Gini(p)\sum_{k1}^K p_k(1-p_k)1-\sum_{k1}^Kp_k^2Gini(p)∑k1Kpk(1−pk)1−∑k1Kpk2 对于二分类Gini(p)2p(1−p)Gini(p)2p(1-p)Gini(p)2p(1−p)
对于给定数据集的基尼指数:Gini(D)1−∑k1K(∣Ck∣∣D∣)2Gini(D)1-\sum_{k1}^K(\dfrac{|C_k|}{|D|})^2Gini(D)1−∑k1K(∣D∣∣Ck∣)2
如果样本集合D根据特征A是否为a划分为数据集D1和数据集D2。 D1{(x,y)∈D∣A(x)a}D_1\{(x,y)\in D|A(x)a\}D1{(x,y)∈D∣A(x)a} D2D−D1D_2D-D_1D2D−D1
在特征A下集合D的基尼指数为Gini(D)∣D1∣∣D∣Gini(D1)∣D2∣∣D∣Gini(D2)Gini(D)\dfrac{|D_1|}{|D|}Gini(D_1)\dfrac{|D_2|}{|D|}Gini(D_2)Gini(D)∣D∣∣D1∣Gini(D1)∣D∣∣D2∣Gini(D2)
CART分类树生成算法 输入训练数据集D停止计算条件 输出CART分类树 从根节点开始递归对每个结点操作。 1、设结点数据集为D对每个特征A对其每个值a根据样本点对Aa的测试为是或否将D分为D1D2计算Aa的基尼指数 2、在所有的特征A以及所有可能的切分点a中选择基尼指数最小的特征和切分点将数据集分配到两个子结点中。 3、对两个子结点递归调用12步骤 算法停止的条件是节点中的样本个数小于阈值或者样本集的基尼指数小于阈值。
2.3.3 CART树剪枝
计算子树的损失函数:Cα(T)C(T)α∣T∣C_{\alpha}(T)C(T)\alpha|T|Cα(T)C(T)α∣T∣ 当α\alphaα很大的时候这样得到的会是一棵偏小的决策树。也就是叶子节点少的决策树。 α\alphaα从0到一个较大的值的过程中可以生成很多颗树。选择最优的子树TαT_{\alpha}Tα
