深度解析决策树算法与应用.pptxVIP

一.示例学习

示例学习也称实例学习,它是一种归纳学习。示例学习是从若干实例(涉及正例和反例)中归纳出普通概念或规则的学习方法。;学习程序归纳出的语义网络;例1假设示例空间中有桥牌中同花概念的两个示例:

示例1：

花色(c1，梅花)∧花色(c2，梅花)∧花色(c3，梅花)∧花色(c4，梅花)→同花(c1，c2，c3，c4)

示例2：

花色(c1，红桃)∧花色(c2，红桃)∧花色(c3，红桃)∧花色(c4，红桃)→同花(c1，c2，c3，c4)

关于同花的普通性规则:

花色(c1，x)∧花色(c2，x)∧花色(c3，x)∧花色(c4，x)→同花(c1，c2，c3，c4);对于这个问题可采用通常的曲线拟合技术，归纳出规则：

(x，y，2x+3y+1)

即

z＝2x＋3y＋1;二.决议树学习

1．什么是决议树

决议树(decisiontree)也称判定树，它是由对象的若干属性、属性值和相关决议组成的一棵树。其中的节点为属性（普通为语言变量），分枝为相应的属性值（普通为语言值）。从同一节点出发的各个分枝之间是逻辑“或”关系；根节点为对象的某一种属性；从根节点到每一种叶子节点的所有节点和边，按次序串连成一条分枝路径，位于同一条分枝路径上的各个“属性-值”对之间是逻辑“与”关系，叶子节点为这个与关系的相应成果，即决议。;决议树示意图;例3下图所示是机场指挥台关于飞机起飞的简单决议树。;例4下图是一种描述“兔子”概念的决议树。;2.怎样学习决议树

决议树学习的基本方法和环节：

首先，选用一种属性，按这个属性的不同取值对实例集进行分类；并以该属性作为根节点，以这个属性的诸取值作为根节点的分枝，进行画树。

然后，考察所得的每一种子类，看其中的实例的结论是否完全相似。假如完全相似，则以这个相似的结论作为相应分枝路径末端的叶子节点；否则，选用一种非父节点的属性，按这个属性的不同取值对该子集进行分类，并以该属性作为节点，以这个属性的诸取值作为节点的分枝，继续进行画树。

如此继续，直到所分的子集全都满足：实例结论完全相似，而得到所有的叶子节点为止。;●决议树学习举例

设表1所示的是某保险企业的汽车驾驶保???类别划分的部分事例。我们将这张表作为一种实例集，用决议树学习来归纳该保险企业的汽车驾驶保险类别划分规则。;表1汽车驾驶保险类别划分实例集;将实例集简记为

S={(1,C),(2,C),(3,C),(4,B),(5,A),(6,A),(7,C),(8,B),(9,A),(10,A),(11,B),(12,B)}

其中每个元组表示一种实例，前面的数字为实例序号，背面的字母为实例的决议项保险类别。

用“小”、“中”、“大”

分别代表

“＜21”、“≥21且≤25”、“＞25”

这三个年纪段。;对于S，我们按属性“性别”的不同取值将其分类。由表1可见，这时S应被分类为两个子集：

S1={(3,C),(4,B),(7,C),(8,B),(11,B),(12,B)}

S2={(1,C),(2,C),(5,A),(6,A),(9,A),(10,A)}

于是，我们得到以性别作为根节点的部分决议树（见下图）。;决议树生成过程;决议树生成过程;决议树生成过程;最后生成的决议树;由决议树所得的规则集：

①女性且年纪在25岁以上，则给予A类保险；

②女性且年纪在21岁到25岁之间，则给予A类保险；

③女性且年纪在21岁如下，则给予C类保险；

④男性且年纪在25岁以上，则给予B类保险；

⑤男性且年纪在21岁到25岁之间且未婚，则给予C类保险；

⑥男性且年纪在21岁到25岁之间且已婚，则给予B类保险；

⑦男性且年纪在21岁如下且未婚，则给予C类保险；

⑧男性且年纪在21岁如下且已婚，则给予B类保险。;3.ID3算法

ID3算法是一种典型的决议树学习算法，由Quinlan于1979年提出。ID3算法的基本思想是，以信息熵为度量，用于决议树节点的属性选择，每次优先选用信息量最多的属性，亦即能使熵值变成最小的属性，以结构一棵熵值下降最快的决议树，到叶子节点处的熵值为0。此时，每个叶子节点相应的实例集中的实例属于同一类。;（1）信息熵和条件熵

设S是一种实例集(S也能够是子实例集),A为S中实例的一种属性。H(S)和H(S|A)分别称为实例集S的信息熵和条件熵,其计算公式如下:

其中,μi(i=1,2,