试论基于信息论的数据挖掘方法课件.ppt

1、1 1第九章 基于信息论的数据挖掘方法2 2基于信息论的数据挖掘方法?信息论基本原理?决策树方法3 3信息论原理Shannon信息论?信息论的创立?1948年Shannon首次提出?以数学方法度量并研究通信信号4 4信道模型?一个传递信息的系统是由发送端（信源）和接收端（信宿）以及连接两者的通道（信道）三者组成。?信源发出的符号U取值为u1,u2.ur，信宿接收的符号V取值为v1,v2.vq。信道u1,u2.ur信源Uv1,v2.vq信宿V5 5不确定性?在进行实际的通信之前，收信者（信宿）不可能确切了解信源究竟会发出什么样的具体信息，不可能判断信源会处于什么样的状态。这种情形称为信宿对于信源

2、状态具有不确定性。?这种不确定性是存在于通信之前的，因而又叫做先验不确定性，表示成信息熵 H（U）6不确定性?在进行了通信之后，信宿收到了信源发来的信息，这种先验不确定性才会被消除或者被减少。?如果干扰很小，不会对传递的信息产生任何影响，信源发出的信息能够被信宿全部收到，在这种情况下，信宿的先验不确定性就会被完全消除。?在一般情况下，干扰总会对信源发出的信息造成某种破坏，使信宿收到的信息不完全，先验不确定性不能全部被消除，只能部分地消除。?即，通信结束之后，信宿仍可能具有一定程度的不确定性，称为后验不确定性，表示成：条件熵 H（U/V）7 7互信息?后验不确定性总要小于或等于先验不确定性:H（

3、U/V）H（X）故信源Y比信源X的平均不确定性要大。XP Xaa().12099001YP Ybb().1205051414讨论?如果n种可能的发生都有相同的概率，即所有的ui有P（ui）=1/n，H（U）达到最大值log n，系统的不确定性最大。?P（ui）互相接近，H（U）就大。P（Ui）相差大，则H（U）就小。1515举例?假设有茄子、番茄、黄瓜三种蔬菜，先对某蔬菜进行分类。?不给人和描述时，可能是三种之一，不确定性大?给出是长型时，可能是茄子，黄瓜两种?给出是紫色时，只可能是茄子1616条件熵定义?如果信源X与随机变量Y不是相互独立的，那么用条件熵H(X|Y)来度量收信者在收到随机变量

4、Y之后，对随机变量X仍然存在的不确定性。设X对应信源符号ai，Y对应信源符号bj，p(ai|bj)为当Y为bj时X为ai的概率，则有11(|)()lg(|)rsijijijH X Yp abp ab=-?I可得()(|)()ijijjp abp abp b=?I由于11(|)()(|)lg(|)srjijijjiH X Yp bp a bp a b=-?1717平均互信息量定义?平均互信息量，也称信息论测度值表示信号Y所能提供的关于X的信息量的大小，用I(X,Y)表示(,)()(|)HX YHXHXY=-【说明】：信息论在决策树学习中具有非常重要的意义。在决策树学习方法中，最关键的问题就是如何

5、根据每个属性提供的信息量构造出一棵决策树，以此对整个实例空间进行合理的分类（划分）。18其他定义后验熵：当接收到输出符号V=vj后，信宿对于信源的平均不确定性。定义为：?=ijijijvuPvuPvUH)|(1log)|()|(1919信息论在决策树中的应用?设训练实例集为X，目的是将训练实例分为 n类。设属于第i类的训练实例个数是 Ci，X中总的训练实例个数为|X|，若记一个实例属于第 i类的概率为P(Ci)，则()|iiCp CX=此时，决策树对划分C的不确定程度为：(,)()lg()iiH X Cp CP C=-?【注意】：在无混淆的情况下，习惯将H(X,C)简记为H(X)。2020基于

6、信息论的数据挖掘方法?信息论基本原理?决策树方法2121决策树的方法?基本概念?ID3的基本思想和算法?ID3算法举例?ID3算法的改进和讨论2222决策树的基本概念?A decision tree is a tree in which?Each branch node represents a choice?Each leaf node represents a classification or decision23节点?每一个节点表示对样本实例的某个属性值进行测试，该节点后相联接的各条路径上的值表示该属性的可能取值（二叉，三叉）HumidityPOutlookWindyNPTempNNN

7、NNSunnyOvercastRainHighNormalNotMediumVeryCoolMildHot24叶子?每个叶子产生一条规则，规则由根到该叶子的路径上所有节点的条件组成，规则的结论是叶子上标注的结论（决策，分类，判断）HumidityPOutlookWindyNPTempNNNNNSunnyOvercastRainHighNormalNotMediumVeryCoolMildHotIf outlook=Sunny then PlayGolf=yes25决策树所产生的规则?决策树代表实例属性值约束的合取的析取式。从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取

8、。HumidityPOutlookWindyNPTempNNNNNSunnyOvercastRainHighNormalNotMediumVeryCoolMildHot(outlook=sunny)V(outlook=overcast humidity=normal)2626举例1：银行贷款决定2727举例2：信用风险分析2828决策树的生成一(Building Tree)?基本思想：?用途：提取分类规则，进行分类预测判定树分类算法output训练集决策树input2929使用决策树进行分类?决策树?一个树型的结构?内部节点上选用一个属性进行分割?每个分叉都是分割的一个部分?叶子节点表示一个分

9、布?决策树生成算法分成两个步骤?树的生成?开始，数据都在根节点?递归的进行数据分片?树的修剪?去掉一些可能是噪音或者异常的数据?决策树使用:对未知数据进行分割?按照决策树上采用的分割属性逐层往下，直到一个叶子节点3030决策树算法?基本算法（贪心算法）?自上而下分而治之的方法?开始时，所有的数据都在根节点?属性都是种类字段(如果是连续的，将其离散化)?所有记录用所选属性递归的进行分割?属性的选择是基于一个启发式规则或者一个统计的度量(如,information gain)?停止分割的条件?一个节点上的数据都是属于同一个类别?没有属性可以再用于对数据进行分割3131伪代码(Building Tr

10、ee)Procedure BuildTree(S)用数据集S初始化根节点R用根结点R初始化队列QWhile Q is not Empty do 取出队列Q中的第一个节点NifN不纯(Pure)for 每一个属性 A估计该节点在A上的信息增益选出最佳的属性，将 N分裂为N1、N23232属性选择的统计度量?信息增益Information gain(ID3/C4.5)?所有属性假设都是种类字段?经过修改之后可以适用于数值字段?基尼指数Gini index(IBM IntelligentMiner)?能够适用于种类和数值字段3333ID3基本思想?ID3的思想?自顶向下构造决策树?从“哪一个属性将在

11、树的根节点被测试”开始?使用统计测试来确定每一个实例属性单独分类训练样例的能力?ID3的过程?分类能力最好的属性被选作树的根节点?根节点的每个可能值产生一个分支?训练样例排列到适当的分支?重复上面的过程直到所有训练样本使用完毕3434用于概念学习的ID3算法1.ID3(Examples,Target_attribute,Attributes)2.创建树的root节点3.如果Examples都为正,返回label=+的单节点树root4.如果Examples都为反,返回label=-的单节点树root5.如果Attributes为空，那么返回单节点root，label=Examples中最普遍的

12、Target_attribute值6.否则开始1.AAttributes中分类examples能力最好的属性2.root的决策属性A3.对于A的每个可能值vi1.在root下加一个新的分支对应测试 A=vi2.令Examplesvi 为Examples中满足A属性值为vi的子集3.如果Examplesvi 为空1.在这个新分支下加一个叶子节点，节点的label=Examples中最普遍的Target_attribute值2.否则在新分支下加一个子树ID3（Examplesvi,Target_attribute,Attributes-A）7.结束8.返回root3535重要问题：哪个属性作为当前

13、测试节点?构造好的决策树的关键在于如何选择好的逻辑判断或属性。对于同样一组例子，可以有很多决策树能符合这组例子。人们研究出，一般情况下或具有较大概率地说，树越小则树的预测能力越强。要构造尽可能小的决策树，关键在于选择恰当的逻辑判断或属性。由于构造最小的树是 NP-难问题，因此只能采取用启发式策略选择好的逻辑判断或属性。3636?对蔬菜分类?茄子，番茄，黄瓜?形状?长 vs.圆?颜色 不确定性为03737属性选择?最佳分类属性问题?信息增益(Information Gain)?用来衡量给定的属性区分训练样例的能力?ID3算法在增长树的每一步使用信息增益从候选属性中选择属性?用熵度量样例的均一性?

14、熵刻画了任意样例集的纯度3838熵的物理定义?A formula to calculate the homogeneity of a sample.?A completely homogeneous sample has entropy of 0.?An equally divided sample has entropy of 1.1122()()()()()()()rrH Xp a I ap aI ap a I a=?L1()lg()riiip ap a=-?3939决策树的学习过程?决策树学习过程就是使得决策树对划分的不确定程度逐渐减小的过程。大致过程如下：（1）选择测试属性a进行测试，

15、在得知a=aj的情况下，属于第i类的实例个数为Cij个。记p(Ci;a=aj)=Cij/|X|p(Ci;a=aj)为在测试属性a的取值为aj时它属于第i类的概率。此时决策树对分类的不确定程度就是训练实例集对属性X的条件熵。4040决策树的学习过程?可知属性a对于分类提供的信息量I(X;a)为：（2）信息量I(X;a)的值越大，说明选择测试属性a对于分类提供的信息量越大，选择属性a之后对分类的不确定程度越小。（3）依次类推，不断地计算剩余样本的条件熵及信息量，直至构造出完整的决策树。(;)()(|)IX aHXH Xa=-4141信息增益（Information GainInformation

16、Gain）?信息增益度量期望的熵降低?属性的信息增益，由于使用这个属性分割样例而导致的期望熵降低?Gain(S,A)是在知道属性A的值后可以节省的二进的值后可以节省的二进制位数?上式中：?S:目标概念的正负样本的集合?Sv：对某个属性v的的正负样本的子集?Entropy(Sv)是将S v中的样本划分到c个类的信息熵?Value(A)：属性A所有可能取值的集合4242信息增益（Information GainInformation Gain）4343训练集PE、NE取子集建窗口窗口PE、NE生成决策树测试PE、NE扩展窗口PE=PE+PENE=NE+NE此决策树为最后结果存在错判的PE，NE吗是

17、否ID3主算法流程4444决策树的方法?基本概念?ID3的基本思想和算法?ID3算法举例?ID3算法的改进和讨论4545?小王是一家著名高尔夫俱乐部的经理。但是他被雇员数量问题搞得心情十分不好。某些天好像所有人都来玩高尔夫，以至于所有员工都忙的团团转还是应付不过来，而有些天不知道什么原因却一个人也不来，俱乐部为雇员数量浪费了不少资金。?小王的目的是通过下周天气预报寻找什么时候人们会打高尔夫，以适时调整雇员数量。因此首先他必须了解人们决定是否打球的原因。?在2周时间内我们得到以下记录:4646属性OutlookTemperature HumidityWindy 类1OvercastHotHigh

18、 Not N2OvercastHotHigh Very N3Overcast HotHighMedium N4SunnyHotHigh Not P5Sunny HotHighMedium P6RainMildHighNot N7RainMildHighMedium N8RainHotNormal Not P9Rain CoolNormal Medium N10RainHotNormal Very N11SunnyCoolNormal Very P12SunnyCoolNormal Medium P4747属性 OutlookTemperature Humidity Windy 类13Overc

19、astMildHighNot N14 OvercastMildHighMedium N15 OvercastCoolNormal Not P16OvercastCoolNormal Medium P17 RainMildNormal Not N18 RainMildNormal Medium N19 OvercastMildNormal Medium P20 OvercastMildNormal Very P21 SunnyMildHighVery p22 SunnyMildHighMedium P23 SunnyHotNormal Not P24 RainMildHighVery N4848

20、在决策树方法中，所要做的工作就是构造决策树将数据进行分类。因初始时属于P类和N类的实例个数均为12，故初始熵值为：1212121 2()lglg1242 42 42 4HX=-=(1)若选择Outlook作为测试属性，其条件熵为：5528.077lg77247)87lg8781lg81(248)95lg9594lg94(249)|(=-?-?-=OutlookXH本实例中的条件熵计算过程11(|)()(|)lg(|)srjijijjiH X Yp bp a bp a b=-?4949(2)若选择Temp作为测试属性，其条件熵为：84444114477(|)(lglg)(lglg)2488882

21、411111 11154411(lglg)0.6739245555H X Tem p=-?-?-=(3)若选择Humidity作为测试属性，其条件熵为：124488(|)(lglg)2412121212124488(lglg)0.91832412121212HXHumidity=-?-=5050(4)若选择Windy作为测试属性，其条件熵为：8444463337(|)(lglg)(lglg)248888246666105555(lglg)12410101010H X Windy=-?-?-=由上述计算结果可知：（1）H(X|Outlook)最小，即有关Outlook的信息对于分类有最大的帮助，

22、提供最大的信息量，故应选择Outlook属性作为测试属性。（2）H(X)=H(X|Windy),即I(X;Windy)=0，说明有关Windy的信息不能提供任何分类信息。（3）选择Outlook作为测试属性之后，将训练实例集分为三个子集，即生成三个节点，分别对每个节点依次利用上述过程，即可生成决策树：5151HumidityPOutlookWindyNPTempNNNNNSunnyOvercastRainHighNormalNotMediumVeryCoolMildHot依据信息熵对上述实例集进行训练所生成的决策树5252结论?通过分类树给出了一个解决方案：老板在潮湿的天气或者刮风的雨天解雇了

23、大部分员工，因为这种天气不会有人打高尔夫。而其他的天气会有很多人打高尔夫，因此可以雇用一些临时员工来工作。结论是决策树帮助我们把复杂的数据表示转换成相对简单的直观的结构。5353训练集(练习)ageincome studentcredit_ratingbuys_computer=30highnofairno40mediumnofairyes40lowyesfairyes40lowyesexcellentno3140 lowyesexcellentyes=30mediumnofairno40mediumyesfairyes40mediumnoexcellentnoID3算法5454?Log3=1

24、.5850?Log5=2.3219?Log6=2.5850?Log7=2.8074?Log9=3.16995555使用信息增益进行属性选择?Class P:buys_computer=“yes”?Class N:buys_computer=“no”?I(p,n)=I(9,5)=0.940?Compute the entropy for age:HenceSimilarlyagepiniI(pi,ni)40320.9716936.0)2,3(145)0,4(144)3,2(145)(=?=IIIageE048.0)_(151.0)(029.0)(=ratingcreditGainstudentG

25、ainincomeGain)(),()(agEnpIageGain-=5656Decision Tree(Decision Tree(结果输出结果输出)age?overcaststudent?credit rating?noyesfairexcellent40nonoyesyesyes30.405757决策树的方法?基本概念?ID3的基本思想和算法?ID3算法举例?ID3算法的改进和讨论5858ID3算法讨论?观察ID3的搜索空间和搜索策略：?假设空间包含所有的决策树，它是关于现有属性的有限离散值函数的一个完整空间?不进行回溯，可能收敛到局部最优?每一步使用所有的训练样例，不同于基于单独的训练

26、样例递增作出决定，容错性增强5959ID3 的归纳偏置?ID3的搜索策略?优先选择较短的树?选择那些信息增益高的属性离根节点较近的树?很难准确刻画ID3的归纳偏置?近似的ID3的归纳偏置?较短的树比较长的树优先?近似在于ID3得到局部最优，而不一定是全局最优?一个精确具有这个归纳偏置的算法，BFS-ID3?更贴切近似的归纳偏置?较短的树比较长的树优先，信息增益高的属性更靠近根节点的树优先60为什么短的假设优先?哲学基础：奥坎姆剃刀原理（Occams Razor):?优先选择拟合数据的最简单的假设?Story:?奥卡姆剃刀定律，是由 14世纪逻辑学家奥卡姆的威廉（William of Occam

27、，约1285年至1349年）提出。奥卡 姆在箴言书注 2卷15题说“切勿浪费较多东西去做用较 少的东西同样可以做好的事情。”?定理的原述：“如无必要，勿增实体”（Entities should not be multiplied unnecessarily）。?例子?物理学家优先选择行星运动的简单假设?简单假设的数量远比复杂假设的数量少?简单假设对训练样例的针对性更小，更像是泛化的规律，而不是训练样例的另一种描述61ID3算法的主要问题?ID3算法存在的主要不足?确定决策树增长的深度?处理连续属性值问题?处理缺少属性值问题?处理不同代价的属性问题?针对ID3的这些不足，ID3被扩展成为C4.5

28、6262避免过学习、过度拟合?过学习的概念（过度拟合，Overfitting）?对于一个假设，当存在其他的假设对训练样例的拟合比它差，但事实上在实例的整个分布上表现得却更好时，我们说这个假设过度拟合训练样例?定义：给定一个假设空间H，一个假设hH，如果存在其他的假设hH，使得在训练样例上h的错误率比h小，但在整个实例分布上h的错误率比h小，那么就说假设h过度拟合训练数据。6363过度拟合（Overfiting)6464避免过拟合（过学习）?导致过度拟合的原因?一种可能原因是训练样例含有随机错误或噪声?当训练数据没有噪声时，过度拟合也有可能发生，特别是当少量的样例被关联到叶子节点时，很可能出现巧

29、合的规律性，使得一些属性恰巧可以很好地分割样例，但却与实际的目标函数并无关系。?避免过度拟合的方法?及早停止树增长?后修剪法?两种方法的特点?第一种方法更直观?第一种方法中，精确地估计何时停止树增长很困难?第二种方法被证明在实践中更成功6565避免过拟合（过学习）?避免过度拟合的关键?使用什么样的准则来确定最终正确树的规模?解决方法?使用与训练样例截然不同的一套分离的样例，来评估通过后修剪方法从树上修建节点的效用。?使用所有可用数据进行训练，但进行统计测试来估计扩展（或修剪）一个特定的节点是否有可能改善在训练集合外的实例上的性能。?使用一个明确的标准来衡量训练样例和决策树的复杂度，当这个编码的

30、长度最小时停止树增长。66避免过拟合?方法评述?第一种方法是最普通的，常被称为训练和验证集法。?可用数据分成两个样例集合：?训练集合，形成学习到的假设?验证集合，评估这个假设在后续数据上的精度?方法的动机：即使学习器可能会被训练集合误导，但验证集合不大可能表现出同样的随机波动?验证集合应该足够大，以便它本身可提供具有统计意义的实例样本。?常见的做法是，样例的三分之二作训练集合，三分之一作验证集合。?交叉验证（Cross-Validation）6767Cross Validation?在给定的建模样本中，拿出大部分样本进行建模型，留小部分样本用刚建立的模型进行预报，并求这小部分样本的预报误差，记

31、录它们的平方加和。这个过程一直进行，直到所有的样本都被预报了一次而且仅被预报一次。把每个样本的预报误差平方加和，称为PRESS(predicted Error Sum of Squares)。?用交叉验证的目的是为了得到可靠稳定的模型。常用的精度测试方法有交叉验证，例如 10倍交叉验证(10-fold cross validation)，将数据集分成十分，轮流将其中9份做训练1份做测试，10次的结果的均值作为对算法精度的估计6868规则后修剪?从训练集合推导出决策树，增长决策树直到尽可能好地拟合训练数据，允许过度拟合发生?将决策树转化为等价的规则集合，方法是为从根节点到叶节点的每一条路径创建一

32、条规则?通过删除任何能导致估计精度提高的前件来修剪每一条规则?按照修剪过的规则的估计精度对它们进行排序，并按这样的顺序应用这些规则来分类后来的实例6969例子?If(outlook=sunny)V(outlook=overcasthumidity=normal)then PlayGolf=No?考虑删除先行词?选择使估计精度有最大提升的步骤7070C4.5C4.5?C4.5 is a algorithm extension of the basic ID3 algorithm to address the following issues not dealt with by ID3:?Avoi

33、ding overfitting the data?Determining how deeply to grow a decision tree.?Reduced error pruning.?Rule post-pruning.?Handling continuous attributes.?e.g.,temperature?Choosing an appropriate attribute selection measure.?Handling training data with missing attribute values.?Handling attributes with dif

34、fering costs.?Improving computational efficiency.7171规则后修剪(C4.5(C4.5使用）使用）?从训练集合推导出决策树，增长决策树直到尽可能好地拟合训练数据，允许过度拟合发生?将决策树转化为等价的规则集合，方法是为从根节点到叶节点的每一条路径创建一条规则?通过删除任何能导致估计精度提高的前件来修剪每一条规则?按照修剪过的规则的估计精度对它们进行排序，并按这样的顺序应用这些规则来分类后来的实例7272C4.5分析?优点?用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；?在树构造过程中进行剪枝；?能够完成对连续属性

35、的离散化处理；?能够对不完整数据进行处理。?总之：产生的分类规则易于理解，准确率较高。?其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。7373处理连续值?ID3被限制为取离散值的属性?学习到的决策树要预测的目标属性必须是离散的?树的决策节点的属性也必须是离散的?简单删除上面第2个限制的方法?通过动态地定义新的离散值属性来实现，即先把连续值属性的值域分割为离散的区间集合?方法的扩展?连续的属性分割成多个区间，而不是单一阈值的两个空间7474选择其它度量标准?信息增益度量

36、存在一个内在偏置，偏向具有较多值的属性?避免方法：其他度量函数，比如增益比率?增益比率通过加入一个被称作分裂信息的项来惩罚多值属性，分裂信息用来衡量属性分裂数据的广度和均匀性7575缺少属性值的训练样例的处理?Attribute A=x,y,z?Gain(S,A)=?一种策略是赋给它节点n的训练样例中该属性的最常见值?另一种策略是赋给它节点n的被分类为c(x)的训练样例中该属性的最常见值?更复杂的策略，为A的每个可能值赋予一个概率，而不是简单地将最常见的值赋给A(x)7676决策树方法的几个有代表性的研究成果a)1966年Hunt等人提出的早期决策树学习算法CLS学习算法；b)1979年Qui

37、nlan提出的以信息熵的下降速度作为选取测试属性的标准的ID3算法。c)1986年Schlimmer等人构造了ID4算法，该算法允许递增式构造决策树。d)1986年Utgoff提出ID5算法，它允许通过修改决策树来增加新的训练实例，而无需重建决策树。77Ross QuinlanJohn Ross Quinlan is a computer science researcher in data miningand decision theory.He has contributed extensively to the development of decision treealgorithms

38、,including inventing the canonical C4.5 and ID3algorithms.He is currently running the company RuleQuest Researchwhich he founded in 19977878小结：决策树的优点?可以生成可以理解的规则；?计算量相对来说不是很大；?可以处理连续和离散字段；?决策树可以清晰的显示哪些字段比较重要?在相对短的时间内能够对大型数据源做出可行且效果良好的结果7979小结：不足之处?对连续性的字段比较难预测?当类别太多时，错误可能会增加的比较快?一般的算法分类的时候，只是根据一个属性来分类。?不是全局最优。