《ID3算法》.ppt

决策树算法决策树算法1InputInputID3 AlgorithmData Mining AlgorithmOutputOutputData setData setDTDT2v决策树是用样本的属性作为结点，用属性的取值作为分支的树结构。v决策树的根结点是所有样本中信息量最大的属性。树的中间结点是该结点为根的子树所包含的样本子集中信息量最大的属性。决策树的叶结点是样本的类别值。决策树概念决策树概念3v决策树是一种知识表示形式，它是对所有样本数据的高度概括。v决策树能准确地识别所有样本的类别，也能有效地识别新样本的类别。4ID3方法基本思想方法基本思想v首先找出最有判别力的属性，把样例分成多个子集，每个子集又选择最有判别力的属性进行划分，一直进行到所有子集仅包含同一类型的数据为止。最后得到一棵决策树。vJ.R.Quinlan的工作主要是引进了信息论中的信息增益，他将其称为信息增益（information gain），作为属性判别能力的度量，设计了构造决策树的递归算法。v下面通过一个例子一个例子，说明ID3算法的基本思想。5 对于气候分类问题，属性为:天气(A1)取值为：晴，多云，雨 气温(A2)取值为：冷，适中，热 湿度(A3)取值为：高，正常 风(A4)取值为：有风，无风 一、一、ID3基本思想基本思想6v每个样例属于不同的类别，此例仅有两个类别，分别为P，N。P类和N类的样例分别称为正例和反例。将一些已知的正例和反例放在一起便得到训练集。v表表6.4.1给出一个训练集。由ID3算法得出一棵正确分类训练集中每个样例的决策树，见下图。7天 气湿 度风晴雨多云高正常有风无风PNNPPBACKGO8v决策树叶子为类别名，即P 或者N。其它结点由样例的属性组成，每个属性的不同取值对应一分枝。v若要对一样例分类，从树根开始进行测试，按属性的取值分枝向下进入下层结点，对该结点进行测试，过程一直进行到叶结点，样例被判为属于该叶结点所标记的类别。9v现用图来判一个具体例子，某天早晨气候描述为:天气：多云 气温：冷 湿度：正常 风：无风 它属于哪类气候呢?v从图中可判别该样例的类别为P类。10ID3就是要从表的训练集构造图这样的决策树。实际上，能正确分类训练集的决策树不止一棵。Quinlan的ID3算法能得出结点最少的决策树。11二、二、ID3算法算法 对当前例子集合，计算各属性的信息增益；选择信息增益最大的属性Ak；把在Ak处取值相同的例子归于同一子集，Ak取几个值就得几个子集；对既含正例又含反例的子集，递归调用建树算法；若子集仅含正例或反例，对应分枝标上P或N，返回调用处。12实例计算实例计算 对于气候分类问题进行具体计算有：信息熵的计算信息熵的计算 信息熵：其中S是样例的集合，P(ui)是类别i出现概率：13|S|表示例子集S的总数，|ui|表示类别ui的例子数。对9个正例和5个反例有：P（u1）=9/14P（u2）=5/14H（S）=（9/14）log（14/9）+（5/14）log（14/5）=0.94bit14信息增益的计算公式：其中A是属性，Value(A)是属性A取值的集合，v是A的某一属性值，Sv是S中A的值为v的样例集合，|Sv|为Sv中所含样例数。信息增益的计算信息增益的计算15属性属性Ai的信息增益的信息增益以属性A1为例，根据信息增益的计算公式，属性A1的信息增益为S=9+,5-/原样例集中共有14个样例，9个正例，5个反例S晴=2+,3-/属性A1取值晴的样例共5个，2正，3反S多云=4+,0-/属性A1取值多云的样例共4个，4正，0反S雨=3+,2-/属性A1取值晴的样例共5个，3正，2反故1617计算结果计算结果属性A1的信息增益最大，所以被选为根结点18 ID3算法将选择信息增益最大的属性天气作为树根，在14个例子中对天气的3个取值进行分枝，3 个分枝对应3 个子集，分别是:S1=1，2，8，9，11;S2=3，7，12，13;S3=4，5，6，10，14 其中S2中的例子全属于P类，因此对应分枝标记为P，其余两个子集既含有正例又含有反例，将递归调用建树算法。建决策树的根和分枝建决策树的根和分枝19天气S=D1,D2,D3,D14晴多云雨S1=D1,D2,D8,D9,D11S2=D3,D7,D12,D13S3=D4,D5,D6,D10,D14全为正例20 分别对S1和S3子集递归调用ID3算法，在每个子集中对各属性求信息增益.（1）对S1，湿度属性信息增益最大，以它为该分枝的根结点，再向下分枝。湿度取高的例子全为N类，该分枝标记N。取值正常的例子全为P类，该分枝标记P。（2）对S3，风属性信息增益最大，则以它为该分枝根结点。再向下分枝，风取有风时全为N类，该分枝标记N。取无风时全为P类，该分枝标记P。这样就得到如图所示的决策树 递归建树递归建树21对ID3的讨论 优点优点 ID3在选择重要属性时利用了信息增益的概念，算法的基础理论清晰，使得算法较简单，是一个很有实用价值的示例学习算法。该算法的计算时间是例子个数、属性个数、结点个数之积的线性函数。对有4761个关于苯的质谱例子作了试验。其中正例2361个，反例2400个，每个例子由500个属性描述，每个属性取值数目为6，得到一棵1514个结点的决策树。对正、反例各100个测试例作了测试，正例判对82个，反例判对80个，总预测正确率81%，效果是令人满意的。22 缺点缺点 （1）信息增益的计算依赖于属性取值的数目较多的属性，这样不太合理。一种简单的办法是对属性进行分解，如上节例中，属性取值数目不一样，可以把它们统统化为二值属性，如天气取值晴，多云，雨，可以分解为三个属性；天气晴，天气多云，天气雨。取值都为“是”或“否”，对气温也可做类似的工作。这样就不存在偏向问题了。23（2）用信息增益作为属性选择量存在一个假设，即训练例子集中的正，反例的比例应与实际问题领域里正、反例比例相同。一般情况不能保证相同，这样计算训练集的信息增益就有偏差。（3）ID3在建树时，每个节点仅含一个属性，是一种单变元的算法，属性间的相关性强调不够。虽然它将多个属性用一棵树连在一起，但联系还是松散的。24 （4）ID3对噪声较为敏感。关于什么是噪声，Quinlan的定义是训练例子中的错误就是噪声。它包含两方面，一是属性值取错，二是类别给错。（5）当训练集增加时，ID3的决策树会随之变化。在建树过程中，各属性的信息增益会随例子的增加而改变，从而使决策树也变化。这对渐近学习（即训练例子不断增加）是不方便的。25 总总的的来来说说，ID3ID3由由于于其其理理论论的的清清晰晰，方方法法简简单单，学学习习能能力力较较强强，适适于于处处理理大大规规模模的的学学习习问问题题 ，在在世世界界上上广广为为流流传传，得得到到极极大大的的关关注注，是是数数据据挖挖掘掘和和机机器器学学习习领领域域中中的的一一个个极极好好范范例例，也也不不失失为一种知识获取的有用工具。为一种知识获取的有用工具。26NO.属性属性类别类别天气天气气温气温湿度湿度风风D1晴晴热热高高无风无风ND2晴晴热热高高有风有风ND3多云多云热热高高无风无风PD4雨雨适中适中高高无风无风PD5雨雨冷冷正常正常无风无风PD6雨雨冷冷正常正常有风有风ND7多云多云冷冷正常正常有风有风PD8晴晴适中适中高高无风无风ND9晴晴冷冷正常正常无风无风PD10雨雨适中适中正常正常无风无风PD11晴晴适中适中正常正常有风有风PD12多云多云适中适中高高有风有风PD13多云多云热热正常正常无风无风PD14雨雨适中适中高高有风有风NBACK表表6.4.1 气候分类数据集气候分类数据集27