2、X)=H(X,Y)-H(X)条件熵定义H(Y
3、X)=H(Y)-I(X,Y)根据互信息定义展开得到有些文献将I(X,Y)=H(Y)–H(Y
4、X)作为互信息的定义式对偶式H(X
5、Y)=H(X,Y)-H(Y)H(X
6、Y)=H(X)-I(X,Y)I(X,Y)=H(X)+H(Y)-H(X,Y)有些文献将该式作为互信息的定义式试证明：H(X
7、Y)≤H(X)，H(Y
8、X)≤H(Y)2强大的Venn图：帮助记忆3等式变化根据H
9、(Y
10、X)=H(Y)-I(X,Y)得到I(X,Y)=H(Y)-H(Y
11、X)I(X,Y)：在X中包含的关于Y的信息4k近邻分类5决策树(DecisionTree)一种描述概念空间的有效的归纳推理办法。基于决策树的学习方法可以进行不相关的多概念学习，具有简单快捷的优势，已经在各个领域取得广泛应用。决策树是一种树型结构，其中每个内部结点表示在一个属性上的测试，每个分支代表一个测试输出，每个叶结点代表一种类别。6决策树示意图7决策树学习决策树学习是以实例为基础的归纳学习。决策树学习采用的是自顶向下的递归方法，其基本思想是以信息熵为度量构造一棵熵值下降最快
12、的树，到叶子节点处的熵值为零，此时每个叶节点中的实例都属于同一类。8决策树学习算法的特点决策树学习算法的最大优点是，它可以自学习。在学习的过程中，不需要使用者了解过多背景知识，只需要对训练例子进行较好的标注，就能够进行学习。从一类无序、无规则的事物（概念）中推理出决策树表示的分类规则。9决策树学习的生成算法ID3C4.5CART10信息增益当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵和条件熵分别称为经验熵和经验条件熵。信息增益表示得知特征A的信息而使得类X的信息的不确定性减少的程度。定义：特征A对训练数据集D的信息增益g
13、(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D
14、A)之差，即：g(D,A)=H(D)–H(D
15、A)即训练数据集类别和特征的互信息。11基本记号设训练数据集为D，
16、D
17、表示其容量，即样本个数。设有K个类Ck，k=1,2,…,K，
18、Ck
19、为属于类Ck的样本个数。Σk
20、Ck
21、=
22、D
23、。设特征A有n个不同的取值{a1,a2…an}，根据特征A的取值讲D划分为n个子集D1,D2,…Dn,
24、Di
25、为Di的样本个数，Σi
26、Di
27、=D。记子集Di中属于类Ck的样本的集合为Dik，
28、Dik
29、为Dik的样本个数。12信息增益的计算方法
30、计算数据集D的经验熵计算特征A对数据集D的经验条件熵H(D
31、A)计算信息增益：g(D,A)=H(D)–H(D
32、A)13经验条件熵H(D
33、A)14其他目标信息增益率：gr(D,A)=g(D,A)/H(A)基尼指数：15讨论考察基尼指数的图像、熵、分类误差率三者之间的关系使用1-x近似代替-lnx16三种决策树学习算法适应信息增益来进行特征选择的决策树学习过程，即为ID3决策。所以如果是取值更多的属性，更容易使得数据更“纯”（尤其是连续型数值），其信息增益更大，决策树会首先挑选这个属性作为树的顶点。结果训练出来的形状是一棵庞大且深度很浅的树，这样的划
34、分是极为不合理的。C4.5：信息增益率CART：基尼系数一个属性的信息增益越大，表明属性对样本的熵减少的能力更强，这个属性使得数据由不确定性变成确定性的能力越强。17提升方法一个概念如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么，这个概念是强可学习的；一个概念如果存在一个多项式的学习算法能够学习它，并且学习的正确率仅比随机猜测略好，那么，这个概念是弱可学习的；强可学习与弱可学习是等价的。在学习中，如果已经发现了“弱学习算法”，能否将他提升为“强学习算法”。18Adaboost设训练数据集T={(x1,y1),(x2,y2)…(xN,
35、yN)}初始化训练数据的权值分布19Adaboost：对于m=1,2,…M使用具有权值分布Dm的训练数据集学习，得到基本分类器计算Gm(x)在训练数据集上的分类误差率计算Gm(x)的系数20Adaboost：对于m=1,2,…M更新训练数据集的权值分布这里，Zm是规范化因子它使Dm+1成为一个概率分布21Adaboost构建基本分类器的线性组合得到最终分类器22举例给定下列训练样本，试用AdaBoost算法学习一个强分类器。23解初始化训练数据的权值分布W1i=0.124m=1对于m=1在权值分布为D1的训练数据上，阈值v取2.5时误差率最低，故
36、基本分类器为：25m=1G1(x)在训练数据集上的误差率e1=P(G1(xi)≠yi)=0.3计算G1的系数：26m=1更新训练数据的权
