ID3算法

决策树-信息论方法1信息论原理2决策树方法3决策规则树方法4其它分类预测方法1信息论原理-1信息论：是关于信息的本质和传输规律的科学的理论，是研究信息的计量、发送、传递、交换、接收和储存的一门新兴学科信道模型：信源（发送端）信道信宿（接收端）通信过程是在随机干扰环境中传递信息的过程；信宿对信源的先验不确定性：在实际通信前，信宿不能确切了解信源的状态；信宿对信源的后验不确定性：由于存在干扰，在实际通信后，信宿对所受到的信息仍具有不确定性；后验不确定性总要小于先验不确定性信息：是用来消除不确定性的度量，信息量的大小，由所消除的不确定性的大小来计量（香农）1信息论原理-2由于不确定性是由随机性引起的，所以用概率来描述和计量熵entropy：源于热力学，是分子混乱程度的度量依据分子运动论的观点对熵所作的微观解释，使得熵与概率建立起联系，可以用熵的概念研究和描述“不确定性”使用概率描述通讯系统内信号源的随机性时，就创立了信息熵数学理论，熵是信息论中重要的基本概念1信息论原理-3若X是一个离散型随机变量，其概率分布为：p(x)=P(X=x)，x∈X，则X的熵H(X)为：H(X)=-∑x∈Xp(x)log2p(x)，其中，约定0log20=0，通常单位为bits一个随机变量的熵越大，它的不确定性就越大，正确估计其值的可能性就越小。越不确定的随机变量越需要大的信息量用以确定其值熵又称为自信息（self-information），表示信源X每发一个符号（不论发什么符号）所提供的平均信息量1信息论原理-4例：计算英文（26个字母和空格，共27个字符）信息源的熵：（1）假设27个字符等概率出现；（2）英文字母的概率分布如表所示：字母空格ETOANIRS概率0.19560.1050.0720.06540.0630.0590.0550.0540.052字母HDLCFUMPY概率0.0470.0350.0290.0230.02250.02250.0210.01750.012字母WGBVKXJQZ概率0.0120.0110.01050.0080.0030.0020.0010.0010.001英文字母概率分布表1信息论原理-5解：（1）等概率出现情况：H(X)=-∑x∈Xp(x)log2p(x)=log227=4.75（2）实际情况：H(X)=-∑x∈Xp(x)log2p(x)=4.02说明：考虑了英文字母和空格实际出现的概率后，英文信源的平均不确定性，比把字母和空格看作等概率出现时英文信源的平均不确定性要小1信息论原理-6离散情况下，信源数学模型（样本空间/概率空间）：ui：信源可能取的消息（符号）；P(ui)：信源选择信源符号ui作为消息进行发送的先验概率如果知道事件ui已发生，则该事件所含有的自信息定义为：I(ui)=-logP(ui)，两种含义：当事件发生以前，表示发生的不确定性；当事件发生以后，表示事件所含的信息量；即：通信前，不确定性在状态空间[U,P]中；通信后，不确定性被缩小至状态ui)u(P),...,u(P),u(Pu...,,u,u]P,U[r21r211信息论原理-7信源发出的符号U的取值是一个离散随机变量，U=[u1,u2,…,ur]，所以U的信息熵为：H(U)=-∑i=1,2,,…,rP(ui)log2P(ui)讨论：H(U)是信源发出前的平均不确定性，是先验熵，其性质为：H(U)=0，说明不存在不确定性，所提供的信息量为0；如果r种可能的发生都有相同概率，则H(U)达到最大值log2r，不确定性最大，所提供的信息量最大；P(ui)互相接近，则H(U)就大；P(ui)相差大，则H(U)就小1信息论原理-8信道的数学模型：(U,P(V|U),V)U=[u1,u2,…,ur]：信源所发消息，离散随机变量；V=[v1,v2,…,vq]：信宿所收消息，离散随机变量；P(V|U)：转移概率，表示发送为U,收到消息V的概率，存在：∑P(vj|ui)=1，i=1,2,…,r先验概率P(U)：信源发送消息前，U的概率分布；后验概率P(U|vj)：信宿端收到消息vj后，U的概率分布——由于信道噪声，不能确定所收即所发1信息论原理-9后验熵：信宿端接收到输出符号vj后，关于U的平均不确定性为：H(U|vj)=-∑i=1,2,,…,rP(ui|vj)log2P(ui|vj)条件熵：H(U|V)=-∑j=1,…,qP(vj)∑i=1,…,rP(ui|vj)log2P(ui|vj)条件熵即信道疑义度，对后验熵在输出符号集V中求期望值，表示在信宿端接收到全部输出符号V后，对信源端U尚存在的不确定性在通信后总能消除一些关于信源端的不确定性，所以存在关系：H(U|V)H(U)1信息论原理-10互信息(信息增益)：衡量通过信道传输进行通信后所消除的不确定性的大小，定义为：I(U,V)=H(U)-H(U|V)表示接收到V后获得的关于U的信息量，是不确定性的消除，是信宿端所获得的信息量，其中：H(U)=-∑i=1,2,,…,rP(ui)log2P(ui)H(U|V)=-∑j=1,…,qP(vj)∑i=1,…,rP(ui|vj)log2P(ui|vj)信道容量：互信息取得最大值时的量，即：C=Max{I(U,V)}可以C为特征选择量，来有效区分类别特征，即选择C大的特征（信息量大的特征），去掉C小的特征（信息量小的特征）1信息论原理-11类别译码准则：重要性：译错的概率既与信道的统计特性有关，又与译码准则有关问题描述：定义译码准则就是要设计一个函数，对于输出的每一个符号能唯一确定一个类别的输入符号与之对应（根据输出判定输入是什么类别）求二元信道译码准则问题的方法：最大后验概率准则最大似然译码准则2决策树分类方法概述-1决策树：知识表示的一种方式决策树的基本组成：决策结点：样本属性；分支：属性的取值；叶结点：样本所属的类别，即标签2决策树分类方法概述-2决策树分类方法：构建决策树：利用信息论原理对大量样本的属性进行分析和归纳而产生使用决策树：对新样本分类，从树的根节点开始，按样本属性的取值沿树向下直至找到叶节点所表示的类别典型算法：ID3方法、C4.5方法、IBLE方法等3.ID3算法概述起源于概念学习系统CLSCLS：找出最有判别力的因素将数据分成多个子集，对每个子集重复上述步骤，直到所有子集仅含同类型数据；然后用得到的决策树对新样本进行分类ID3：引入信息论中互信息（信息增益），作为判别因素的度量，即：以信息熵的下降速度作为选取测试属性的标准，所选的测试属性是从根到当前节点的路径上尚未被考虑的具有最高信息增益的属性3.ID3算法示例-1已知：气候训练数据集，预定义两个类别P、N；求：各类别的描述特征No.天气气温湿度风类别1晴热高无N2晴热高有N3多云热高无P4雨适中高无P5雨冷正常无P6雨冷正常有N7多云冷正常有PNo.天气气温湿度风类别8晴适中高无N9晴冷正常无P10雨适中正常无P11晴适中正常有P12多云适中高有P13多云热正常无P14雨适中高有N3.ID3算法示例-2计算各属性的信息增益/互信息，找出最大者作为决策树的根节点，过程：先验熵——没有接收到其他属性值时的平均不确定性：后验熵——接收到输出符号vj时关于信源的不确定性；条件熵——对后验熵在输出符号集V中求期望，接收到全部符号后对信源的不确定性；互信息——先验熵与条件熵的差，是信宿端所获得信息量对剩余属性重复上述步骤3.ID3算法示例-3例题中各数据的属性及其取值分别为：类别：P、N；——u1、u2天气A1：晴、多云、雨；气温A2：冷、适中、热；湿度A3：高、正常；风A4：有、无选择全部数据记录，求先验熵（对类别）：P(u1)=9/14，P(u2)=5/14H(U)=-∑i=1,2P(ui)log2P(ui)=0.94bit后验熵（对A1）：v1=晴，v2=多云，v3=雨P(v1)=5/14，P(v2)=4/14，P(v3)=5/14P(u1|v1)=2/5，P(u2|v1)=3/5H(U|v1)=-∑i=1,2P(ui|v1)log2P(ui|v1)=0.97同理，H(U|v2)=0，H(U|v3)=0.973.ID3算法示例-4条件熵（对A1）：H(U|V)=∑j=1,2,3P(vj)H(U|vj)=0.69互信息（对A1）：I(A1)=H(U)-H(U|V)=0.25同理，有：I(A2)=0.03，I(A3)=0.15，I(A4)=0.05I(A1)值最大，所以选择“天气”作为决策树的根节点，将其三个取值分别作为三个分支，并划分原数据集合为三个子集判断子集中各记录是否属于同一类别，若是则在树上作标记，否则对子集重复上述步骤结果：教材47页图4.63.ID3算法示例-5已知：流感训练数据集，预定义两个类别；求：各类别的描述特征流感训练数据集No.头痛肌肉痛体温患流感1是(1)是(1)正常(0)否(0)2是(1)是(1)高(1)是(1)3是(1)是(1)很高(2)是(1)4否(0)是(1)正常(0)否(0)5否(0)否(0)高(1)否(0)6否(0)是(1)很高(2)是(1)7是(1)否(0)高(1)是(1)体温头痛很高正常高是否是否否是图7.3：流感例题的决策树3.ID3算法示例-6例题中各数据的属性及其取值分别为：类别：是、否；——u1、u2头痛A1：是、否；肌肉痛A2：是、否；体温A3：很高、高、正常选择全部数据记录，求先验熵（对类别）：P(u1)=4/7，P(u2)=3/7H(U)=-∑i=1,2P(ui)log2P(ui)=0.985bit后验熵（对A1）：v1=是，v2=否P(v1)=4/7，P(v2)=3/7P(u1|v1)=3/4，P(u2|v1)=1/4H(U|v1)=-∑i=1,2P(ui|v1)log2P(ui|v1)=0.811同理，H(U|v2)=0.9183.ID3算法示例-7条件熵（对A1）：H(U|V)=∑j=1,2,3P(vj)H(U|vj)=0.857互信息（对A1）：I(A1)=H(U)-H(U|V)=0.128同理，有：I(A2)=0.006，I(A3)=0.592I(A3)值最大，所以选择“体温”作为决策树的根节点，将其三个取值分别作为三个分支，并划分原数据集合为三个子集判断子集中各记录是否属于同一类别，若是则在树上作标记，否则对子集重复上述步骤结果：图7.34.ID3算法描述-建树算法建树算法：1)对当前窗口中数据记录，计算各特征属性的互信息；2)选择互信息最大的特征Ak；3)把在Ak处取值相同的记录归于同一子集，将当前窗口记录划分成不同的子集；4)判断子集，若各子集中记录同属于一个类别，则在决策树上作相应类别标记，并返回，否则对子集递归调用本算法5.ID3算法评价-1对决策树分类方法：基本算法自上而下分而治之的方法；开始时，所有的数据都在根节点；所有记录用所选属性递归的进行分割；属性的选择是基于一个启发式规则或者一个统计的度量(如ID3基于互信息)停止分割的条件一个节点上的数据都是属于同一个类别；没有属性可以再用于对数据进行分割5.ID3算法评价-2对ID3算法：优点：理论清晰，算法简单，很有实用价值的示例学习算法；计算时间是例子个数、特征属性个数、节点个数之积的线性函数，总预测准确率较令人满意缺点：存在偏向问题，各特征属性的取值个数会影响互信息量的大小；特征属性间的相关性强调不够，是单变元算法；对噪声较为敏感，训练数据的轻微错误会导致结果的不同；鲁棒性结果随训练集记录个数的改变而不同，不便于进行渐进学习C4.5方法1构造决策树信息增益率2连续属性处理3决策树剪枝其它分类方法概述数据库中隐藏着许多可以为商业、科研等活动的决策提供所需要的知识分类与预测