决策树学习

✍ dations ◷ 2025-07-25 06:06:14 #决策树,分类算法

统计学,数据挖掘和机器学习中的决策树训练,使用决策树作为预测模型来预测样本的类标。这种决策树也称作分类树或回归树。在这些树的结构里, 叶子节点给出类标而内部节点代表某个属性。

在决策分析中,一棵决策树可以明确地表达决策的过程。在数据挖掘中,一棵决策树表达的是数据而不是决策。本页的决策树是数据挖掘中的决策树。

在数据挖掘中决策树训练是一个常用的方法。目标是创建一个模型来预测样本的目标值。例如右图。每个 内部节点 对应于一个输入属性,子节点代表父节点的属性的可能取值。每个叶子节点代表输入属性得到的可能输出值。

一棵树的训练过程为:根据一个指标,分裂训练集为几个子集。这个过程不断的在产生的子集里重复递归进行,即递归分割。当一个训练子集的类标都相同时 递归停止。这种 (TDITD) 是 贪心算法的一种, 也是目前为止最为常用的一种训练方法,但不是唯一的方法。


数据以如下方式表示:

其中Y是目标值,向量x由这些属性构成, x1, x2, x3 等等,用来得到目标值。

在数据挖掘中,决策树主要有两种类型:

术语分类和回归树 (CART) 包含了上述两种决策树, 最先由Breiman 等提出. 分类树和回归树有些共同点和不同点—例如处理在何处分裂的问题。

有些的方法产生多棵树:

还有其他很多决策树算法,常见的有:

构建决策树时通常采用自上而下的方法,在每一步选择一个最好的属性来分裂。 "最好" 的定义是使得子节点中的训练集尽量的纯。不同的算法使用不同的指标来定义"最好"。本部分介绍一些最常见的指标。

在CART算法中, 基尼不纯度表示一个随机选中的样本在子集中被分错的可能性。基尼不纯度为这个样本被选中的概率乘以它被分错的概率。当一个节点中所有样本都是一个类时,基尼不纯度为零。

假设y的可能取值为 J {\displaystyle J} (sunny, overcast, rainy), (hot, mild, cool), (high, normal), and (true, false), 目标值(yes, no), 总共14个数据点。为建造决策树,需要比较4棵决策树的信息增益,每棵决策树用一种属性做划分。信息增益最高的划分作为第一次划分,并在每个子节点继续此过程,直至其信息增益为0。

使用属性做划分时,产生2个子节点:值为真与为假。当前数据集,6个数据点的值为真,其中3个点的值为真,3个点的值为假;其余8个数据点的为假,其中6个点的值为真,2个点的值为假。 =true的子节点的信息熵计算为:

=false的子节点的信息熵计算为:

这个划分(使用属性)的信息熵是两个子节点信息熵的加权和:

为计算使用属性的信息增益,必须先计算出最初(未划分)的数据集的信息熵,数据集的有9个yes与5个no:

使用属性的信息增益是:

与其他的数据挖掘算法相比,决策树有许多优点:

在决策树中, 从根节点到叶节点的路径采用汇合或。而在决策图中, 可以采用 最小消息长度 (MML)来汇合两条或多条路径。

演化算法可以用来避免局部最优的问题

相关

  • 荧光淬灭荧光淬灭(英语:Quenching)猝灭是当常温物质经射线照射(通常为紫外线或X射线)所发出会萤光强度降低的任何过程。淬灭受压力和温度的影响很大,许多过程都可导致淬灭,例如激发态反应,能
  • 迈锡尼迈锡尼希腊语是希腊语的已知最古老的形式,多利亚人入侵前,在迈锡尼时期(公元前16至前12世纪)使用于希腊大陆和克里特岛上。它保存在线形文字B写的题字中,这种文字是公元前14世纪
  • 戏剧古希腊戏剧是指大致繁荣于公元前6世纪末至前4世纪初之间的古希腊世界的戏剧。当时古希腊的政治和军事中心雅典城同时也是古希腊戏剧的中心。雅典的悲剧和喜剧也包括在全世界
  • 弗雷德里克·布莱克曼弗雷德里克·弗罗斯特·布莱克曼(英语:Frederick Frost Blackman,1866年7月25日-1947年1月30日),英国植物生理学家, 皇家学会院士。1907年11月19日出生于英国英格兰大伦敦内伦敦兰
  • 佳木斯市佳木斯市(满语:ᡤᡳᠶᠠᠮᡠᠰᡳ,穆麟德:Giyamusi,太清:Giyamusi)是中华人民共和国黑龙江省下辖的地级市,是中国最东边的地级行政区。名字来源于满语,佳木斯为驿丞。一说意为“巫师(萨
  • 高异柠檬酸高异柠檬酸(英语:Homoisocitric acid,或homoisocitrate)是高柠檬酸的一种同分异构体,其羟基位于2号位而不是3号位。高异柠檬酸是赖氨酸生物合成的α-氨基己二酸途径(英语:Alpha-ami
  • 邓子龙邓子龙(1531年-1598年12月16日),字武桥,号大千,别号虎冠道人,明朝水师将领,生于江西省丰城市杜市镇邓家村。明嘉靖年间江西内乱,邓子龙样貌魁梧,骁捷绝伦,参军后以“平乱”有功,授广东把
  • 萨克拉门托县萨克拉门托县(英语:Sacramento County)又译沙加缅度县是美国加利福尼亚州的一个县,位于中央谷地。面积2,578平方公里,根据美国2000年人口普查数字,共有人口1,223,499人。县治萨克
  • 真如寺真如寺,又称云居禅院、龙昌禅院、真如禅寺,位于江西省九江市永修县云居山上,汉族地区佛教全国重点寺院之一。真如寺始建于唐宪宗元和年间,初名为云居禅院。道容建寺后,与弟子全庆
  • 纳坦·瑟德布卢姆拉尔斯·奥洛夫·约纳坦·瑟德布卢姆(瑞典语:Lars Olof Jonathan Söderblom,又称纳坦·瑟德布卢姆,1866年1月15日-1931年7月12日),瑞典牧师,瑞典教会乌普萨拉大主教,1930年因倡导世