[文学]机器学习.pptVIP

* * * * * * * * * 另一棵决策树 同样一个训练数据集，可以有多棵树与其一致 * * 决策树学习 2. ID3算法(1/11) ID3算法是昆兰（J.R.Quinlan）于1979年提出的一种以信息熵（entropy）的下降速度作为属性选择标准的一种学习算法。其输入是一个用来描述各种已知类别的例子集，学习结果是一棵用于进行分类的决策树。 主要讨论： ID3算法的数学基础 ID3算法及其举例 * 决策树学习 2. ID3算法(2/11) (1) ID3算法的数学基础 下面讨论信息熵和条件熵的数学概念 信息熵 信息熵是对信息源整体不确定性的度量。假设X为信源，xi为X所发出的单个信息，P(xi)为X发出xi的概率，则信息熵可定义为： 其中，k为信源X发出的所有可能的信息类型，对数可以是以各种数为底的对数，在ID3算法中，我们取以2为底的对数。 信息熵反应的是信源每发出一个信息所提供的平均信息量。 * 条件熵 条件熵是收信者在收到信息后对信息源不确定性的度量。若假设信源为X，收信者收到的信息为Y， P(xi/yj)为当Y为yj时X为xi的条件概率，则条件熵可定义为： 它表示收信者收到Y后对X不确定性的估计。 决策树学习 2. ID3算法(3/11) * 决策树学习 2. ID3算法(4/11) (2) ID3算法及举例 ID3算法的学习过程： 首先以整个例子集作为决策树的根节点S，并计算S关于每个属性的期望熵（即条件熵）； 然后选择能使S的期望熵为最小的一个属性对根节点进行分裂，得到根节点的一层子节点； 接着再用同样的方法对这些子节点进行分裂，直至所有叶节点的熵值都下降为0为止。 这时，就可得到一棵与训练例子集对应的熵为0的决策树，即ID3算法学习过程所得到的最终决策树。该树中每一条从根节点到叶节点的路径，都代表了一个分类过程，即决策过程。 * 例7.1 用ID3算法完成下述学生选课的例子 假设将决策y分为以下３类： y1：必修AI y2：选修AI y3：不修AI 做出这些决策的依据有以下3个属性： x1：学历层次　x1=1 研究生，x1=2 本科 x2：专业类别　x2=1 电信类，x2=2 机电类 x3：学习基础　x3=1 修过AI，x3=2 未修AI 表7.1给出了一个关于选课决策的训练例子集S。 决策树学习 2. ID3算法(5/11) * 表7-1　关于选课决策的训练例子集 在该表中，训练例子集S的大小为８。ID3算法是依据这些训练例子，以S为根节点，按照信息熵下降最大的原则来构造决策树的。 序号 属性值 决策方案 yi x1 x2 x3 1 1 1 1 y3 2 1 1 2 y1 3 1 2 1 y3 4 1 2 2 y2 5 2 1 1 y3 6 2 1 2 y2 7 2 2 1 y3 8 2 2 2 y3 决策树学习 2. ID3算法(6/11) * 解： 首先对根节点，其信息熵为： 其中，3为可选的决策方案数，且有 　　　　P(y1)=1/8，P(y2)=2/8，P(y3)=5/8 即有： H(S)= -(1/8)log2(1/8)- (2/8)log2(2/8)- (5/8)log2(5/8) =1.2988 按照ID3算法，需要选择一个能使S的期望熵为最小的一个属性对根节点进行扩展，因此我们需要先计算S关于每个属性的条件熵： 其中，t为属性xi的属性值，St为xi=t时的例子集，|S|和|Si|分别是例子集S和Si的大小。 决策树学习 2. ID3算法(7/11) * 下面先计算S关于属性x1的条件熵： 在表7-1中，x1的属性值可以为1或2。当x1=1时，t=1时，有： S1={1，2，3，4} 当x1=2时，t=2时，有： S2={5，6，7，8} 其中，S1和S2中的数字均为例子集S中的各个例子的序号，且有|S|=8，|S1|=|S2|=4。 由S1可知： Ps1(y1)=1/4, Ps1(y2)=1/4, Ps1(y3)=2/4 则有： H(S1)= - Ps1(y1)log2 Ps1(y1) - Ps1(y2)log2 Ps1(y2 )- Ps1(y3)log2 Ps1(y3 ) = -(1/4)log2(1/4)- (1/4)log2(1/4)