公司网站建设报价,西安建设工程信息网怎么看,wordpress头像无法显示,做去自己的网站首页文章目录 一、决策树算法1、基本思想2、构成1#xff09;节点3#xff09;有向边/分支 3、分类步骤1#xff09;第1步-决策树生成/学习、训练2#xff09;第2步-分类/测试 4、算法关键 二、信息论基础1、概念2、信息量3、信息熵#xff1a; 二、ID3 (Iterative Dichotomis… 文章目录 一、决策树算法1、基本思想2、构成1节点3有向边/分支 3、分类步骤1第1步-决策树生成/学习、训练2第2步-分类/测试 4、算法关键 二、信息论基础1、概念2、信息量3、信息熵 二、ID3 (Iterative Dichotomiser 3)算法1、基本思想2、熵引入1经验熵2条件熵3经验条件熵4信息增益information gain 3、算法4、算法案例5、算法特点 三、ID3算法问题1、 属性筛选度量标准2、 剪枝处理1问题2解决3案例 3、 连续值处理4、 缺失值处理5、不同代价属性的处理 一、决策树算法
1、基本思想
基本思想采用自顶向下的递归方法以信息熵为度量构造一棵熵值下降最快的树到叶子节点处的熵值为零此时每个叶节点中的实例都属于同一类
2、构成
决策树是一种树型结构由结点和有向边组成
1节点
内部结点表示一个属性或特征叶结点代表一种类别
3有向边/分支
分支代表一个测试输出
3、分类步骤
1第1步-决策树生成/学习、训练
利用训练集建立(并精化)一棵决策树建立决策树模型。这个过程实际上是一个从数据中获取知识进行机器学习的过程
step 1选取一个属性作为决策树的根结点然后就这个属性所有的取值创建树的分支。 step 2用这棵树来对训练数据集进行分类
如果一个叶结点的所有实例都属于同一类则以该类为标记标识此叶结点。如果所有的叶结点都有类标记则算法终止 step 3否则选取一个从该结点到根路径中没有出现过的属性为标记标识该结点然后就这个属性所有的取值继续创建树的分支重复算法步骤step 2
2第2步-分类/测试
利用生成的决策树对输入数据进行分类。对输入的记录从根结点依次测试记录的属性值直到到达某个叶结点从而找到该记录所在的类。
4、算法关键
建立决策树的关键即在当前状态下选择哪个属性作为分类依据
目标每个分支节点的样本尽可能属于同一类别即节点的“纯度”(purity)越来越高最具区分性的属性 根据不同目标函数建立决策树主要有以下三种算法 ◼ ID3 信息增益 ◼ C4.5 信息增益率 ◼ CART基尼指数
二、信息论基础
1、概念
信息论与概率统计中熵表示随机变量不确定性的大小是度量样本集合纯度最常用的一种指标
2、信息量
信息量具有确定概率事件的信息的定量度量 定义 I ( x ) − l o g 2 p ( x ) I(x)-log_2p(x) I(x)−log2p(x) 其中p(x)为事件x发生的概率
3、信息熵
事件集合的信息量的平均值。 定义 H ( x ) ∑ i h ( x i ) ∑ i p ( x i ) I ( x i ) − ∑ i p ( x i ) l o g 2 p ( x i ) H(x) \sum_{i}h(x_i)\sum_{i} p(x_i)I(x_i)-\sum_{i} p(x_i)log_2p(x_i) H(x)∑ih(xi)∑ip(xi)I(xi)−∑ip(xi)log2p(xi)
熵定义了一个函数(概率密度函数pdf)到一个值(信息熵)的映射 p ( x ) → H p(x) → H p(x)→H (函数→数值)
熵是随机变量不确定性的度量 ◼ 不确定性越大熵值越大 ◼ 若随机变量退化成定值熵为0
二、ID3 (Iterative Dichotomiser 3)算法
ID3算法是一种最经典的决策树学习算法。
1、基本思想
以信息熵为度量用于决策树节点的属性选择每次优先选取信息增益最大的属性亦即能使熵值变为最小的属性以构造一颗熵值下降最快的决策树到叶子节点处的熵值为0。此时每个叶子节点对应的实例集中的实例属于同一类。
熵值下降 → 无序变有序
2、熵引入
1经验熵
假设当前样本集合D 中第cc1,2,…,C类样本所占比例为 p c p_c pcc1,2,…,C则D 的经验信息熵(简称经验熵定义为: H ( D ) − ∑ c 1 C p c l o g 2 p c − ∑ c 1 C D c D l o g 2 D c D H(D)-\sum_{c1}^{C}p_clog_2p_c-\sum_{c1}^{C}\frac{D_c}{D}log_2\frac{D_c}{D} H(D)−∑c1Cpclog2pc−∑c1CDDclog2DDc
H(D)的值越小则D 的纯度越高
2条件熵
对随机变量 ( X , Y ) (X, Y) (X,Y)联合分布为 p ( X x i , Y y i ) p i j p(Xx_i,Yy_i)p_{ij} p(Xxi,Yyi)pij
条件熵 H ( Y ∣ X ) H(Y |X ) H(Y∣X) 表示在已知随机变量X 的条件下随机变量Y的不确定性 H ( Y ∣ X ) − ∑ i 1 n p i H ( Y ∣ X x i ) H(Y|X)-\sum_{i1}^{n}p_iH(Y|Xx_i) H(Y∣X)−∑i1npiH(Y∣Xxi)
可证明条件熵(Y|X)相当于联合熵(,)减去单独的熵(X)即 H ( Y ∣ X ) H ( X , Y ) − H ( X ) H(Y|X)H(X,Y)-H(X) H(Y∣X)H(X,Y)−H(X)
3经验条件熵 即特征a的信息对样本D 的信息的不确定性减少的程度
4信息增益information gain
特征 a 对训练数据集 D 的信息增益 G ( D , a ) G(D, a) G(D,a) 定义为集合D 的经验熵 H(D) 与特征 a 给定条件下 D 的经验条件熵 H ( D ∣ a ) H(D | a) H(D∣a) 之差即 G ( D , a ) H ( D ) − H ( D ∣ a ) H ( D ) − ∑ n 1 N D n D H ( D n ) G(D,a)H(D)-H(D|a)H(D)-\sum_{n1}^{N}\frac{D^n}{D}H(D^n) G(D,a)H(D)−H(D∣a)H(D)−∑n1NDDnH(Dn)
ID3算法即是以此信息增益为准则对每次递归的节点属性进行选择的
3、算法 4、算法案例 5、算法特点
最大优点是它可以自学习在学习的过程中不需要使用者了解过多背景知识只需要对训练实例进行较好的标注就能够进行学习。
决策树的分类模型是树状结构简单直观比较符合人类的理解方式。
可将决策树中到达每个叶节点的路径转换为IF—THEN形式的分类规则这种形式更有利于理解。
从一类无序、无规则的事物(概念)中推理出决策树表示的分类规则。
三、ID3算法问题
信息增益偏好取值多的属性(分散极限趋近于均匀分布)
1、 属性筛选度量标准
可能会受噪声或小样本影响易出现过拟合问题。 结果训练出来的形状是一棵庞大且深度很浅的树这样的划分是极为不合理的。 改进方法
2、 剪枝处理
1问题
无法处理连续值的属性。
决策树对训练数据有很好的分类能力但对未知的测试数据未必有好的分类能力泛化能力弱即可能发生过拟合现象。
训练数据有噪声对训练数据拟合的同时也对噪音进行拟合影响了分类效果。
叶节点样本太少易出现耦合的规律性使一些属性恰巧可以很好地分类但却与实际的目标函数并无关系。
2解决
剪枝是决策树学习算法中对付“过拟合”的主要手段 预剪枝策略pre-pruning 决策树生成过程中对每个节点在划分前进行估计若划分不能带来决策树泛化性能提升则停止划分并将该节点设为叶节点 优点预剪枝“剪掉了”很多没必要展开的分支降低了过拟合的风险并且显著减少了决策树的训练时间开销和测试时间开销 劣势有些分支的当前划分有可能不能提高甚至降低泛化性能但后续划分有可能提高泛化性能预剪枝禁止这些后续分支的展开可能会导致欠拟合 后剪枝策略post-pruning 先利用训练集生成决策树自底向上对非叶节点进行考察若将该叶节点对应子树替换为叶节点能带来泛化性能提升则将该子树替换为叶节点 优点优势测试了所有分支比预剪枝决策树保留了更多分支降低了欠拟合的风险泛化性能一般优于预剪枝决策树。 劣势后剪枝过程在生成完全决策树后在进行且要自底向上对所有非叶节点逐一评估因此决策树的训练时间开销要高于未剪枝决策树和预剪枝决策树
3案例 预剪枝算法 后剪枝算法
3、 连续值处理
无法处理属性值不完整的训练数据 基本思想采用二分法(bi-partition)进行离散化
4、 缺失值处理
无法处理不同代价的属性 前面假设所有样本的属性完整 实际情况存在不完整样本即样本的某些属性缺失特别是属性数目较多时 如果简单放弃不完整样本会导致数据信息的浪费 实际中确实需要属性缺失情况下进行决策 ◼ 不同代价属性的处理 需要解决的两个问题
如何在属性值缺失的情况下进行划分属性选择计算信息增益 给定划分属性若样本在该属性上的值缺失如何对样本进行划分 案例
5、不同代价属性的处理
不同的属性测量具有不同的代价 在属性筛选度量标准中考虑属性的不同代价 优先选择低代价属性的决策树 必要时才依赖高代价属性
