郴州免费招聘网站,页面设计怎么样,湖南微信网站公司电话号码,婚纱摄影网站开题报告本系列是七月算法机器学习课程笔记 文章目录1 从LR到决策树1.1 决策树1.2 决策树的终止条件1.3 决策树划分依据1.3.1 信息熵1.3.2 信息增益1.3.3 ID3模型1.3.4 信息增益率1.3.5 基尼指数1.3.6 信息熵与基尼指数1.3.7 连续值属性2 回归树2.1 回归树构建方法3 从决策树到随机森林…本系列是七月算法机器学习课程笔记
文章目录1 从LR到决策树1.1 决策树1.2 决策树的终止条件1.3 决策树划分依据1.3.1 信息熵1.3.2 信息增益1.3.3 ID3模型1.3.4 信息增益率1.3.5 基尼指数1.3.6 信息熵与基尼指数1.3.7 连续值属性2 回归树2.1 回归树构建方法3 从决策树到随机森林3.1 bagging思想3.2 随机森林1 从LR到决策树
1.1 决策树
决策树出现是模仿了人类自己做判断的一个过程。 例如一个相亲案例。要考查的数据维度可能有身高、财富积累、长相、是不是潜力股、品德如何。根据逻辑回归的决策过程是下图这样。计算出的概率高就去相亲。
但是人做决策可能是下面这样。例如年龄30不见。年龄30,长得丑不见。
这样的决策过程简单逻辑清晰可解释性好。上面的图就是一颗决策树。 每个绿色的节点称为内部节点对应于某一个属性。年龄、长相、收入、是否公务员都是属性。 每个分支对应于一种取值。 每个叶子节点对应一种结果。 学习过程通过对训练样本的分析确定“划分属性”。例如女孩看韩剧学习哪些属性重要以及怎么划分。 预测过程将测试样本从根节点开始沿着划分属性构成的“判断测试序列”走到叶子节点。
1.2 决策树的终止条件
决策树构建过程中遇到以下三种情况就可以停止构建了。 第一种情况当前节点包含的样本属于同一类别无需划分。例如当前节点下所有样本的结果都是相亲。那就无需划分下去了。
第二种情况当前属性集为空或者所有样本在所有属性上取值相同无法划分。例如集合中只有2个样本。一个样本身高180长相帅结果相亲一个样本身高180长相帅结果不相亲。所有条件都一样属性值都相同但结果不同。这个时候就不划分了。
第三种情况当前节点包含的样本集合为空不能划分。
1.3 决策树划分依据
1.3.1 信息熵
信息熵是度量样本集合信息“纯度”的一个指标。例如一个样本集合中全是黑球一个人伸手拿出一个球是黑球的概率是100%。这就是纯度很高的一种情况。如果样本集合中有100个球有100种颜色那拿出一个球是黑球的概率就是1100\dfrac{1}{100}1001。这就是非常混乱的一种情况。不利于人做出决策。 决策树不断递进的过程是一个信息熵不断较小的过程因为我们是要做出决策的。
如果样本集合集合中第k类样本的所占比例为pkp_kpk那样本信息熵的定义为Ent(D)−∑k1∣y∣pk∗log2pkEnt(D)-\sum_{k1}^{|y|}p_k*log_2p_kEnt(D)−∑k1∣y∣pk∗log2pk, pk0则log2pk0p_k0则log_2p_k0pk0则log2pk0 Ent(D)越小样本集合纯度越高。
1.3.2 信息增益
信息增益直接以信息熵计算为基础计算当前划分对信息熵造成的变化。 离散属性a的取值有a1,a2,a3...aV{a^1,a^2,a^3...a^V}a1,a2,a3...aV 信息增益是以属性a对数据集D进行划分所获得的的信息增益为Gain(D,a)Ent(D)−∑v1V∣Dv∣∣D∣Ent(Dv)Gain(D,a) Ent(D) - \sum_{v1}^{V}\dfrac{|D^v|}{|D|}Ent(D^v)Gain(D,a)Ent(D)−∑v1V∣D∣∣Dv∣Ent(Dv) |D|表示数据集D的样本数量 ∣Dv∣|D^v|∣Dv∣表示数据集D中aava^vav的样本数量
Ent(Dv)Ent(D^v)Ent(Dv)表示划分后的信息熵 具体例子参考周老师的西瓜书。
1.3.3 ID3模型
根据信息增益选择属性形成决策树的模型称为ID3。 在上面例子中可以用同样的方法计算出其他属性的信息增益。 发现按纹理的信息增益最大。那么就选择纹理这个属性做划分。形成下面这棵树。
接着以每一个节点为一个新的数据集计算其中每个属性的信息增益。以纹理清晰这个节点为例。该结点包含的样例集合 D1 中有编号为 {12, 3, 4, 5, 6, 8, 10, 15} 的 9 个样例可用属性集合为{色泽根蒂敲声脐部7 触感}.基于 D1 计算出各属性的信息增益: Gain(D1 色泽) 0.043; Gain(D1根蒂) 0.458; Gain(D1敲声) 0.331; Gain(D1脐部) 0.458; Gain(D1触感) 0.458. “根蒂”、 “脐部”、 “触感” 3 个属性均取得了最大的信息增益可任选其中之一作为划分属性。类似这样的继续划分下去直到遇到上面那三种情况不再划分。例子的具体信息可以查看西瓜书第四章。
1.3.4 信息增益率
根据信息增益增益率选择属性形成决策树的模型称为C4.5。 例如在上面例子中如果将编号作为一个属性。那它可以将每个样本分到不同的桶内就不能再继续划分下去但是这种划分显然没有任何意义。怎么避免选择这样的属性呢使用信息增益率。 信息增益率:Grain_ratio(D,a)Gain(D,a)IV(a)Grain\_ratio(D,a)\dfrac{Gain(D,a)}{IV(a)}Grain_ratio(D,a)IV(a)Gain(D,a) IV(a)−∑v1V∣Dv∣∣D∣log2∣Dv∣∣D∣IV(a)-\sum_{v1}^V\dfrac{|D^v|}{|D|}log_2\dfrac{|D^v|}{|D|}IV(a)−∑v1V∣D∣∣Dv∣log2∣D∣∣Dv∣ IV(a)其实是属性a在数据集上的信息熵。属性a的可能取值越多IV(a)越大。
ID3 模型会偏好选择属性数目多的属性C4.5会偏好选择属性数目少的属性。在实际应用中先从候选划分属性中找出信息增益高于平均水平的属性再从中选择增益率最高的。
1.3.5 基尼指数
根据基尼指数选择属性形成决策树的模型称为CART。
Gini(D)1−∑k1∣y∣pk2Gini(D)1-\sum_{k1}^{|y|}p_k^2Gini(D)1−∑k1∣y∣pk2
基尼指数反应了从D中随机抽取两个样例其类别标识不一样的概率。 基尼指数越小数据集D的纯度越高。 例如样本集中有黑球和白球两种。基尼指数反应了两次取到的球颜色不一样的概率。
属性a的基尼指数:Gini_index(D,a)∑v1V∣Dv∣∣D∣Gini(D)Gini\_index(D,a)\sum_{v1}^V\dfrac{|D^v|}{|D|}Gini(D)Gini_index(D,a)∑v1V∣D∣∣Dv∣Gini(D)
在候选属性集中选择那个划分后基尼指数最小的属性。
1.3.6 信息熵与基尼指数
对函数f(x)-lnx在x1处展开一阶泰勒展开得到f(x)≈1−xf(x)\approx1-xf(x)≈1−x 信息熵 Ent(D)−∑k1∣y∣pk∗log2pk≈∑k1∣y∣pk(1−pk)Ent(D)-\sum_{k1}^{|y|}p_k*log_2p_k\approx\sum_{k1}^{|y|}p_k(1-p_k)Ent(D)−∑k1∣y∣pk∗log2pk≈∑k1∣y∣pk(1−pk)这个式子和基尼指数是等价的。
也就是说基尼指数和信息熵从数学公式上来讲约等于。
根据属性选择的标准不同决策树分为三类ID3、C4.5和CART。
1.3.7 连续值属性
还有一个问题是关于连续值属性的分割问题。 连续属性的取值数量不再有限制。此时需要连续属性离散化。最简单的策略是采用二分法。 给定样本集 D 和连续属性 α假定 α在 D 上出现了 η个不同的取值将这些值从小到大进行排序记为α1α2..an{α^1 α^2..a^n}α1α2..an。对于属性值相邻的两个样本aia^iai和ai1a^{i1}ai1来说可以选择Taaiai12T_a\dfrac{a^ia^{i1}}{2}Ta2aiai1作为分割点。 例如在一个数据集中有4个样本年龄分别为25352128。将属性值标在数轴上21252835。在第一个和第二个元素之间使用23作为分割点。小于等于23的是一部分大于23的是一部分。同理在第二个元素和第三个元素使用26.5作为分割点在第三个和第四个元素之间用31.5作为分割点。
以上内容来自西瓜书。
2 回归树
回归树是决策树用于解决回归类问题的应用。经典案例是用运动员的从业年限和表现预测运动员的工资。 回归树背后的含义是 对空间做划分拿着一把刀垂直于坐标轴砍一刀将整个平面分为不同的矩形。 例如图中R1{X|Years4.5} , R2{X|Years4.5, Hits117.5},R3{X|Years4.5,Hits117.5}
如果说逻辑回归是产出一条边界完成分类那么决策树就是拿起一把刀垂直于坐标轴砍一刀把平面分成一个一个的小矩形。
2.1 回归树构建方法
把整个空间切分成J个没有重叠的区域R1,R2...RJR_1,R_2...R_JR1,R2...RJ 其中每一个区域RjR_jRj中的样本都给一样的预测结果1n∑j∈Rjyj\dfrac{1}{n}\sum_{j \in R_j}y_jn1∑j∈Rjyj 也就是区域内所有样本的y值的平均值。
目标函数 RSS∑j1J∑i∈Rj(yi−y~)2RSS\sum_{j1}^J\sum_{i \in R_j}(y_i-\tilde{y})^2RSS∑j1J∑i∈Rj(yi−y~)2,要是的RSS最小。 求解最小值的方法是探索式的递归二分。自顶向下不断从当前位置把样本切到2个分支中。贪婪每次选择当前最优切割方法。
如果我把平面一直切切到最后一个区域只要一个元素这就发生了过拟合。而且这样的切分毫无意义。
为了防止过拟合引入正则化项。 Ta{T_a}Ta是生成树的叶子节点个数。α\alphaα是正则化系数。
3 从决策树到随机森林
过拟合的本质是样本数据中是有噪声的。类比于练习册的答案是有错误的全部按照答案去学是不能拿到高分的。
3.1 bagging思想
bagging是每次从样本集中抽取一部分样本进行学习。根据抽取出的样本做学习。 对于t1,2…T 1对训练集进行第t次随机采样共采集m次得到一个样本量为m的采样集DmD_mDm 2)用采样集DmD_mDm训练第m个学习器GmxG_mxGmx。
对于分类场景则T个学习器投票票数最多的结果为最终类别。对于回归场景T个学习器得到的结果进行算数平均得到的值为最终输出结果。
3.2 随机森林
随机森林(random forest)是一种基于树模型的bagging优化版本。不同之处是 RF选择CART树作为基学习器。 对于t1,2…T 1对训练集进行第t次随机采样共采集m次得到一个样本量为m的采样集DmD_mDm 2)用采样集DmD_mDm训练第m个学习器GmxG_mxGmx。在训练决策树模型节点的时候选择所有特征中的一部分特征进行训练在这些随机选择的特征中选择一个最优的特征来做决策树左右子树划分。
