第5章52ID3.ppt

2020
第5章52ID3
NO.
属性
类别
天气
气温
湿度
风
1
晴
热
高
无风
N
2
晴
热
高
有风
N
3
多云
热
高
无风
P
4
雨
择互信息最大的特征天气作为树根，在14个例子中对天气的3个取值进行分枝，3 个分枝对应3 个子集，分别是:
F1={1，2，8，9，11}，F2={3，7，12，13}，F3={4，5，6，10，14}
其中F2中的例子全属于P类，因此对应分枝标记为P，其余两个子集既含有正例又含有反例，将递归调用建树算法。
⒌ 递归建树
分别对F1和F3子集利用ID3算法，在每个子集中对各特征（仍为四个特征）求互信息.
（1）F1中的天气全取晴值，则H（U）=H（U|V），有I（U|V）=0，在余下三个特征中求出湿度互信息最大，以它为该分枝的根结点，再向下分枝。湿度取高的例子全为N类，该分枝标记N。取值正常的例子全为P类，该分枝标记P。
（2）在F3中，对四个特征求互信息，得到风特征互信息最大，则以它为该分枝根结点。再向下分枝，风取有风时全为N类，该分枝标记N。取无风时全为P类，该分枝标记P。
这样就得到图的决策树

ID3算法在数据挖掘中占有非常重要的地位。但是，在应用中，ID3算法不能够处理连续属性、计算信息增益时偏向于选择取值较多的属性等不足。
，。。

（1）用信息增益率来选择属性，它克服了用信息增益选择属性时偏向选择取值多的属性的不足；
（2）在树构造过程中或者构造完成之后，进行剪枝；
（3）能够完成对连续属性的离散化处理；
（4）能够对于不完整数据的处理，例如未知的属性值；
（5），并最终可以形成产生式规则。

Quinlan在ID3中使用信息论中的信息增益（gain）来选择属性，（gain ratio）来选择属性。
信息增益率
。
理论和实验表明，采用“信息增益率”（）比采用“信息增益”（ID3方法）更好，主要是克服了ID3方法选择偏向取值多的属性。
基于信道容量的IBLE方法
我们于91年研制的IBLE方法
IBLE方法是利用信息论中信道容量来选择属性，比互信息更好。

IBLE方法建决策规则树，每个结点由多个属性取值组成，各特征的正例标准值由译码函数决定。结点中判别正反例的阈值是由实例中权值变化的规律来确定的。
决策规则树
规则1
规则2
规则n
u1
u1
u1
u2
u2
u2
决策规则树结点
（1）规则表示形式
决策规则树中非叶结点均为规则。规则表示为：
特征： A1，A2，...， .Am
权值： W1，W2，...，.Wm
标准值：V1，V2，...， .Vm
阈值：Sp，Sn
该规则可形式描述为：
（1）sum:=0；
（2）对i:=1到m作：若（Ai）=Vi，则 sum:=sum+wi；
（3）若sumsn，则该例为N类；
（4）若sumsp，则该例为P类；
（5）若sn<sum<sp，则该例暂不能判，转下一条规则判别。
其中sum表示权和，（Ai）表示特征Ai的取值。
（2）举例
设问题空间中例子有10个特征（属性），特征编号从1到10。每个特性取值为{no,yes}，用{0,1}表示，规则是由重要特征组成的，对每个特征求出权值以表示其重要程度，删除不重要特征得规则如下：
特征： 1 3 4 6 7
权值： 100 90 105 500 40
标准值： 1 0 1 1 0
阈值： 220，100
现有三个测试例子：
例子1：（1，0，0，0，1，0，0，1，1，1）
例子2：（0，1，0，0，1，0，0，0，1，0）
例子3：（0，1，0，0，1，0，1，0，1，1）
例子1的权和sum=230，有sum>220，判定例子1属于u1类。
例子2的权和sum=130，有100<s