什么是ID3算法

什么是ID3算法

ID3算法是由Quinlan首先提出的。该算法是以信息论为基础，以信息熵和信息增益度为衡量标准，从而实现对数来自据的归纳分类。以下是一些信息论的基本概念：

定义1：若存在n观们设模际意传个相同概率的消息，则每个消息的概率p是1/n，一个消息传递的信息量为-Log2(1/n)

定义2：若有n个消息，其给定概率分布为P=(p1,p2…pn)，则由该分布传递的信息量称为P的熵，记为

。

定义3：若一个记录集合T根据类别属性的值被分成互相独立的类C1C2..Ck，则识别T的一个元素所属哪个类所需要的信息量为Info(T)=I(p)，其中P为C1C2…Ck的概率分布，即P=(|C1|/|T|,…..|Ck|/|T|)

定义4：若我们改杨粒参先根据非类别属性X的值将T分成集合T1,T2…Tn，则确定T中一个元素类的信息360问答量可通过确定Ti的加权话后控少个平均值来得到，即Info几稳反度概师父祖煤(Ti)的加权平均值为：

Inf针时考好来o(X,T)=(i=1ton求和)((|Ti|/|T|)Info(Ti))

定义5：信息增益度是两个信息量之间的差值，其中一个信息量是需确定T的一个元素的信息量，另一个信息量是在已得到的属性X的值后需确定的T一个元素的信息量，信息增益度公式为制古需至爱查：

Gain(X,T)=Inf药听顾某急讲香o(T)-Info粒做坏信边际飞校端括待(X,T)

ID3算法计算每有花意推呀个属性的信息增益，并青富编检两老选取具有最高增益的属性作为给定集合的测试属性。对被选取的测试属性创建一个远首富言存工士愿节点，并以该节点的属性标记，对该属性的每个值创建一个分支据此划分样本.

数据描述

所使用的样本数据有一定的要求,ID3是:

描述-属性-值相同的属性必须描述每个例子和有固定数量的价值观。

预定义类-实例的属性必怀静滑贵慢百持史须已经定义的,也就是说,他们不是学习的ID3。

离散类-类必须是尖锐的鲜明。连战内针胜担群续类分解成模糊范畴(如金属被“努力,很困难的,灵活的,温师硫柔的,很软”都是不可信的。

足够的例子——因为归纳概括用于(即不可查明)必须选择足够多的测试用例来量区分有效模式并消除特殊巧合因素的影响。

属性选择

ID3决定哪些属性如何是最好的。一个统计特性,被称为信谓谈硫就喜意音顺只息增益,使用熵得到给定属性衡量培训例子带入目标类分开。信息增益最高的信息(信息是最有益的分类)被选择。为了明确增益,我们首先从信息论借用一个定义，叫做熵。每个地决燃属性都有一个熵。