试论基于信息论的数据挖掘方法

1,第九章基于信息论的数据挖掘方法,2,基于信息论的数据挖掘方法,信息论基本原理决策树方法,3,信息论原理,Shannon信息论信息论的创立1948年Shannon首次提出以数学方法度量并研究通信信号,4,信道模型,一个传递信息的系统是由发送端（信源）和接收端（信宿）以及连接两者的通道（信道）三者组成。信源发出的符号U取值为u1,u2.ur，信宿接收的符号V取值为v1,v2.vq。,信道,u1,u2.ur,信源U,v1,v2.vq,信宿V,5,不确定性,在进行实际的通信之前，收信者（信宿）不可能确切了解信源究竟会发出什么样的具体信息，不可能判断信源会处于什么样的状态。这种情形称为信宿对于信源状态具有不确定性。这种不确定性是存在于通信之前的，因而又叫做先验不确定性，表示成信息熵H（U）,6,不确定性,在进行了通信之后，信宿收到了信源发来的信息，这种先验不确定性才会被消除或者被减少。如果干扰很小，不会对传递的信息产生任何影响，信源发出的信息能够被信宿全部收到，在这种情况下，信宿的先验不确定性就会被完全消除。在一般情况下，干扰总会对信源发出的信息造成某种破坏，使信宿收到的信息不完全，先验不确定性不能全部被消除，只能部分地消除。即，通信结束之后，信宿仍可能具有一定程度的不确定性，称为后验不确定性，表示成：条件熵H（U/V）,7,互信息,后验不确定性总要小于或等于先验不确定性:H（U/V）H（X）故信源Y比信源X的平均不确定性要大。,14,讨论,如果n种可能的发生都有相同的概率，即所有的ui有P（ui）=1/n，H（U）达到最大值logn，系统的不确定性最大。P（ui）互相接近，H（U）就大。P（Ui）相差大，则H（U）就小。,15,举例,假设有茄子、番茄、黄瓜三种蔬菜，先对某蔬菜进行分类。不给人和描述时，可能是三种之一，不确定性大给出是长型时，可能是茄子，黄瓜两种给出是紫色时，只可能是茄子,16,条件熵定义,如果信源X与随机变量Y不是相互独立的，那么用条件熵H(X|Y)来度量收信者在收到随机变量Y之后，对随机变量X仍然存在的不确定性。设X对应信源符号ai，Y对应信源符号bj，p(ai|bj)为当Y为bj时X为ai的概率，则有,可得,由于,17,平均互信息量定义,平均互信息量，也称信息论测度值表示信号Y所能提供的关于X的信息量的大小，用I(X,Y)表示,【说明】：信息论在决策树学习中具有非常重要的意义。在决策树学习方法中，最关键的问题就是如何根据每个属性提供的信息量构造出一棵决策树，以此对整个实例空间进行合理的分类（划分）。,18,其他定义,后验熵：当接收到输出符号V=vj后，信宿对于信源的平均不确定性。定义为：,=,i,j,i,j,i,j,v,u,P,v,u,P,v,U,H,),|,(,1,log,),|,(,),|,(,19,信息论在决策树中的应用,设训练实例集为X，目的是将训练实例分为n类。设属于第i类的训练实例个数是Ci，X中总的训练实例个数为|X|，若记一个实例属于第i类的概率为P(Ci)，则,此时，决策树对划分C的不确定程度为：,【注意】：在无混淆的情况下，习惯将H(X,C)简记为H(X)。,20,基于信息论的数据挖掘方法,信息论基本原理决策树方法,21,决策树的方法,基本概念ID3的基本思想和算法ID3算法举例ID3算法的改进和讨论,22,决策树的基本概念,AdecisiontreeisatreeinwhichEachbranchnoderepresentsachoiceEachleafnoderepresentsaclassificationordecision,23,节点,每一个节点表示对样本实例的某个属性值进行测试，该节点后相联接的各条路径上的值表示该属性的可能取值（二叉，三叉）,24,叶子,每个叶子产生一条规则，规则由根到该叶子的路径上所有节点的条件组成，规则的结论是叶子上标注的结论（决策，分类，判断）,Ifoutlook=SunnythenPlayGolf=yes,25,决策树所产生的规则,决策树代表实例属性值约束的合取的析取式。从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取。,(outlook=sunny)V(outlook=overcasthumidity=normal),26,举例1：银行贷款决定,27,举例2：信用风险分析,28,决策树的生成一(BuildingTree),基本思想：用途：提取分类规则，进行分类预测,29,使用决策树进行分类,决策树一个树型的结构内部节点上选用一个属性进行分割每个分叉都是分割的一个部分叶子节点表示一个分布决策树生成算法分成两个步骤树的生成开始，数据都在根节点递归的进行数据分片树的修剪去掉一些可能是噪音或者异常的数据决策树使用:对未知数据进行分割按照决策树上采用的分割属性逐层往下，直到一个叶子节点,30,决策树算法,基本算法（贪心算法）自上而下分而治之的方法开始时，所有的数据都在根节点属性都是种类字段(如果是连续的，将其离散化)所有记录用所选属性递归的进行分割属性的选择是基于一个启发式规则或者一个统计的度量(如,informationgain)停止分割的条件一个节点上的数据都是属于同一个类别没有属性可以再用于对数据进行分割,31,伪代码(BuildingTree),ProcedureBuildTree(S)用数据集S初始化根节点R用根结点R初始化队列QWhileQisnotEmptydo取出队列Q中的第一个节点NifN不纯(Pure)for每一个属性A估计该节点在A上的信息增益选出最佳的属性，将N分裂为N1、N2,32,属性选择的统计度量,信息增益Informationgain(ID3/C4.5)所有属性假设都是种类字段经过修改之后可以适用于数值字段基尼指数Giniindex(IBMIntelligentMiner)能够适用于种类和数值字段,33,ID3基本思想,ID3的思想自顶向下构造决策树从“哪一个属性将在树的根节点被测试”开始使用统计测试来确定每一个实例属性单独分类训练样例的能力ID3的过程分类能力最好的属性被选作树的根节点根节点的每个可能值产生一个分支训练样例排列到适当的分支重复上面的过程直到所有训练样本使用完毕,34,用于概念学习的ID3算法,ID3(Examples,Target_attribute,Attributes)创建树的root节点如果Examples都为正,返回label=+的单节点树root如果Examples都为反,返回label=-的单节点树root如果Attributes为空，那么返回单节点root，label=Examples中最普遍的Target_attribute值否则开始AAttributes中分类examples能力最好的属性root的决策属性A对于A的每个可能值vi在root下加一个新的分支对应测试A=vi令Examplesvi为Examples中满足A属性值为vi的子集如果Examplesvi为空在这个新分支下加一个叶子节点，节点的label=Examples中最普遍的Target_attribute值否则在新分支下加一个子树ID3（Examplesvi,Target_attribute,Attributes-A）结束返回root,35,重要问题：哪个属性作为当前测试节点,构造好的决策树的关键在于如何选择好的逻辑判断或属性。对于同样一组例子，可以有很多决策树能符合这组例子。人们研究出，一般情况下或具有较大概率地说，树越小则树的预测能力越强。要构造尽可能小的决策树，关键在于选择恰当的逻辑判断或属性。由于构造最小的树是NP-难问题，因此只能采取用启发式策略选择好的逻辑判断或属性。,36,对蔬菜分类茄子，番茄，黄瓜形状长vs.圆颜色不确定性为0,37,属性选择,最佳分类属性问题信息增益(InformationGain)用来衡量给定的属性区分训练样例的能力ID3算法在增长树的每一步使用信息增益从候选属性中选择属性用熵度量样例的均一性熵刻画了任意样例集的纯度,38,熵的物理定义,Aformulatocalculatethehomogeneityofasample.Acompletelyhomogeneoussamplehasentropyof0.Anequallydividedsamplehasentropyof1.,39,决策树的学习过程,决策树学习过程就是使得决策树对划分的不确定程度逐渐减小的过程。大致过程如下：（1）选择测试属性a进行测试，在得知a=aj的情况下，属于第i类的实例个数为Cij个。记p(Ci;a=aj)=Cij/|X|p(Ci;a=aj)为在测试属性a的取值为aj时它属于第i类的概率。此时决策树对分类的不确定程度就是训练实例集对属性X的条件熵。,40,决策树的学习过程,可知属性a对于分类提供的信息量I(X;a)为：（2）信息量I(X;a)的值越大，说明选择测试属性a对于分类提供的信息量越大，选择属性a之后对分类的不确定程度越小。（3）依次类推，不断地计算剩余样本的条件熵及信息量，直至构造出完整的决策树。,41,信息增益（InformationGain）,信息增益度量期望的熵降低属性的信息增益，由于使用这个属性分割样例而导致的期望熵降低Gain(S,A)是在知道属性A的值后可以节省的二进制位数上式中：S:目标概念的正负样本的集合Sv：对某个属性v的的正负样本的子集Entropy(Sv)是将Sv中的样本划分到c个类的信息熵Value(A)：属性A所有可能取值的集合,42,信息增益（InformationGain）,43,训练集PE、NE,取子集建窗口,生成决策树,测试PE、NE,扩展窗口PE=PE+PENE=NE+NE,此决策树为最后结果,存在错判的PE，NE吗,是,否,ID3主算法流程,44,决策树的方法,基本概念ID3的基本思想和算法ID3算法举例ID3算法的改进和讨论,45,小王是一家著名高尔夫俱乐部的经理。但是他被雇员数量问题搞得心情十分不好。某些天好像所有人都来玩高尔夫，以至于所有员工都忙的团团转还是应付不过来，而有些天不知道什么原因却一个人也不来，俱乐部为雇员数量浪费了不少资金。小王的目的是通过下周天气预报寻找什么时候人们会打高尔夫，以适时调整雇员数量。因此首先他必须了解人们决定是否打球的原因。在2周时间内我们得到以下记录:,46,属性OutlookTemperatureHumidityWindy类,OvercastHotHighNotNOvercastHotHighVeryNOvercastHotHighMediumNSunnyHotHighNotPSunnyHotHighMediumPRainMildHighNotNRainMildHighMediumNRainHotNormalNotPRainCoolNormalMediumNRainHotNormalVeryNSunnyCoolNormalVeryPSunnyCoolNormalMediumP,47,属性OutlookTemperatureHumidityWindy类,13OvercastMildHighNotN14OvercastMildHighMediumN15OvercastCoolNormalNotP16OvercastCoolNormalMediumP17RainMildNormalNotN18RainMildNormalMediumN19OvercastMildNormalMediumP20OvercastMildNormalVeryP21SunnyMildHighVeryp22SunnyMildHighMediumP23SunnyHotNormalNotP24RainMildHighVeryN,48,在决策树方法中，所要做的工作就是构造决策树将数据进行分类。因初始时属于P类和N类的实例个数均为12，故初始熵值为：,(1)若选择Outlook作为测试属性，其条件熵为：,本实例中的条件熵计算过程,49,(2)若选择Temp作为测试属性，其条件熵为：,(3)若选择Humidity作为测试属性，其条件熵为：,50,(4)若选择Windy作为测试属性，其条件熵为：,由上述计算结果可知：（1）H(X|Outlook)最小，即有关Outlook的信息对于分类有最大的帮助，提供最大的信息量，故应选择Outlook属性作为测试属性。（2）H(X)=H(X|Windy),即I(X;Windy)=0，说明有关Windy的信息不能提供任何分类信息。（3）选择Outlook作为测试属性之后，将训练实例集分为三个子集，即生成三个节点，分别对每个节点依次利用上述过程，即可生成决策树：,51,Humidity,P,Outlook,Windy,N,P,Temp,N,N,N,N,N,Sunny,Overcast,Rain,High,Normal,Not,Medium,Very,Cool,Mild,Hot,依据信息熵对上述实例集进行训练所生成的决策树,52,结论,通过分类树给出了一个解决方案：老板在潮湿的天气或者刮风的雨天解雇了大部分员工，因为这种天气不会有人打高尔夫。而其他的天气会有很多人打高尔夫，因此可以雇用一些临时员工来工作。结论是决策树帮助我们把复杂的数据表示转换成相对简单的直观的结构。,53,训练集(练习),ID3算法,54,Log3=1.5850Log5=2.3219Log6=2.5850Log7=2.8074Log9=3.1699,55,使用信息增益进行属性选择,ClassP:buys_computer=“yes”ClassN:buys_computer=“no”I(p,n)=I(9,5)=0.940Computetheentropyforage:,HenceSimilarly,56,DecisionTree(结果输出),age?,overcast,student?,creditrating?,no,yes,fair,excellent,40,no,no,yes,yes,yes,30.40,57,决策树的方法,基本概念ID3的基本思想和算法ID3算法举例ID3算法的改进和讨论,58,ID3算法讨论,观察ID3的搜索空间和搜索策略：假设空间包含所有的决策树，它是关于现有属性的有限离散值函数的一个完整空间不进行回溯，可能收敛到局部最优每一步使用所有的训练样例，不同于基于单独的训练样例递增作出决定，容错性增强,59,ID3的归纳偏置,ID3的搜索策略优先选择较短的树选择那些信息增益高的属性离根节点较近的树很难准确刻画ID3的归纳偏置近似的ID3的归纳偏置较短的树比较长的树优先近似在于ID3得到局部最优，而不一定是全局最优一个精确具有这个归纳偏置的算法，BFS-ID3更贴切近似的归纳偏置较短的树比较长的树优先，信息增益高的属性更靠近根节点的树优先,60,为什么短的假设优先,哲学基础：奥坎姆剃刀原理（OccamsRazor):优先选择拟合数据的最简单的假设Story:奥卡姆剃刀定律，是由14世纪逻辑学家奥卡姆的威廉（WilliamofOccam，约1285年至1349年）提出。奥卡姆在箴言书注2卷15题说“切勿浪费较多东西去做用较少的东西同样可以做好的事情。”定理的原述：“如无必要，勿增实体”（Entitiesshouldnotbemultipliedunnecessarily）。例子物理学家优先选择行星运动的简单假设简单假设的数量远比复杂假设的数量少简单假设对训练样例的针对性更小，更像是泛化的规律，而不是训练样例的另一种描述,61,ID3算法的主要问题,ID3算法存在的主要不足确定决策树增长的深度处理连续属性值问题处理缺少属性值问题处理不同代价的属性问题针对ID3的这些不足，ID3被扩展成为C4.5,62,避免过学习、过度拟合,过学习的概念（过度拟合，Overfitting）对于一个假设，当存在其他的假设对训练样例的拟合比它差，但事实上在实例的整个分布上表现得却更好时，我们说这个假设过度拟合训练样例定义：给定一个假设空间H，一个假设hH，如果存在其他的假设hH，使得在训练样例上h的错误率比h小，但在整个实例分布上h的错误率比h小，那么就说假设h过度拟合训练数据。,63,过度拟合（Overfiting),64,避免过拟合（过学习）,导致过度拟合的原因一种可能原因是训练样例含有随机错误或噪声当训练数据没有噪声时，过度拟合也有可能发生，特别是当少量的样例被关联到叶子节点时，很可能出现巧合的规律性，使得一些属性恰巧可以很好地分割样例，但却与实际的目标函数并无关系。避免过度拟合的方法及早停止树增长后修剪法两种方法的特点第一种方法更直观第一种方法中，精确地估计何时停止树增长很困难第二种方法被证明在实践中更成功,65,避免过拟合（过学习）,避免过度拟合的关键使用什么样的准则来确定最终正确树的规模解决方法使用与训练样例截然不同的一套分离的样例，来评估通过后修剪方法从树上修建节点的效用。使用所有可用数据进行训练，但进行统计测试来估计扩展（或修剪）一个特定的节点是否有可能改善在训练集合外的实例上的性能。使用一个明确的标准来衡量训练样例和决策树的复杂度，当这个编码的长度最小时停止树增长。,66,避免过拟合,方法评述第一种方法是最普通的，常被称为训练和验证集法。可用数据分成两个样例集合：训练集合，形成学习到的假设验证集合，评估这个假设在后续数据上的精度方法的动机：即使学习器可能会被训练集合误导，但验证集合不大可能表现出同样的随机波动验证集合应该足够大，以便它本身可提供具有统计意义的实例样本。常见的做法是，样例的三分之二作训练集合，三分之一作验证集合。交叉验证（Cross-Validation）,67,CrossValidation,在给定的建模样本中，拿出大部分样本进行建模型，留小部分样本用刚建立的模型进行预报，并求这小部分样本的预报误差，记录它们的平方加和。这个过程一直进行，直到所有的样本都被预报了一次而且仅被预报一次。把每个样本的预报误差平方加和，称为PRESS(predictedErrorSumofSquares)。用交叉验证的目的是为了得到可靠稳定的模型。常用的精度测试方法有交叉验证，例如10倍交叉验证(10-foldcrossvalidation)，将数据集分成十分，轮流将其中9份做训练1份做测试，10次的结果的均值作为对算法精度的估计,68,规则后修剪,从训练集合推导出决策树，增长决策树直到尽可能好地拟合训练数据，允许过度拟合发生将决策树转化为等价的规则集合，方法是为从根节点到叶节点的每一条路径创建一条规则通过删除任何能导致估计精度提高的前件来修剪每一条规则按照修剪过的规则的估计精度对它们进行排序，并按这样的顺序应用这些规则来分类后来的实例,69,例子,If(outlook=sunny)V(outlook=overcasthumidity=normal)thenPlayGolf=No考虑删除先行词选择使估计精度有最大提升的步骤,70,C4.5,C4.5isaalgorithmextensionofthebasicID3algorithmtoaddressthefollowingissuesnotdealtwithbyID3:AvoidingoverfittingthedataDetermininghowdeeplytogrowadecisiontree.Reducederrorpruning.Rulepost-pruning.Handlingcontinuousattributes.e.g.,temperatureChoosinganappropriateattributeselectionmeasure.Handlingtrainingdatawithmissingattributevalues.Handlingattributeswithdifferingcosts.Improvingcomputationalefficiency.,71,规则后修剪(C4.5使用）,从训练集合推导出决策树，增长决策树直到尽可能好地拟合训练数据，允许过度拟合发生将决策树转化为等价的规则集合，方法是为从根节点到叶节点的每一条路径创建一条规则通过删除任何能导致估计精度提高的前件来修剪每一条规则按照修剪过的规则的估计精度对它们进行排序，并按这样的顺序应用这些规则来分类后来的实例,72,C4.5分析,优点用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；在树构造过程中进行剪枝；能够完成对连续属性的离散化处理；能够对不完整数据进行处理。总之：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。,73,处理连续值,ID3被限制为取离散值的属性学习到的决策树要预测的目标属性必须是离散的树的决策节