C45算法.ppt

文档介绍：
《人工智能》
1
整理ppt
一、
二、
三、

2
整理ppt
一、
。
, 此算法用信息增益率来选择决策属性，其核心算法是ID3算法。它继承了ID3算法的全部优点，并在ID3的基础上增加了对连续属性的离散化、对未知属性的处理和产生规则等功能，克服了ID3算法的不足。
3
整理ppt
:
(1)用信息增益率代替信息增益来选择属性;
(2)能够完成对连续属性的离散化处理,这是一个很关键的改进;
(3)在决策树构造过程中或者构造完成之后,进行剪枝;
(4)能够对不完整数据进行处理,如未知的属性值;
(5) 。
一、
4
整理ppt
二、
(1)用信息增益率代替信息增益来选择属性;
(2)能够完成对连续属性的离散化处理,这是一个很关键的改进;
(3)在决策树构造过程中或者构造完成之后,进行剪枝;
(4)能够对不完整数据进行处理,如未知的属性值;
(5) 。
5
整理ppt
设T 为训练数据集,共有k 个类别,集合表示为 { C1 ,C2 , ⋯,Ck } , | Cj |为Cj 类的例子数,
| T |为数据集T 的例子数。
选择一个属性V, 设它有n个互不重合的取值va ( 1≤a≤n) ,则T 被分为n个子集{ T1,T2⋯,Tn } , 这里Ti 中的所有实例的取值均为vi。|Ti|为V =vi 的例子数, |Cjv|是V =vi 的例子中,具有Cj 类别的例子数。则有：
(1)类别Cj 的发生概率: p (Cj) = |Cj|/|T|;
(2)属性V = vi 的发生概率:p (vi) =|Ti|/|T|;
(3)属性V = vi 例子中,具有类别Cj 的条件概率:
p(Cj | vi ) = |Cjv | / | Ti |。
类别的信息熵：
(1)用信息增益率代替信息增益来选择属性;
6
整理ppt
按照属性V 把集合T分割,分割后的类别条件熵为：
(1)用信息增益率代替信息增益来选择属性;
7
整理ppt
信息增益(Gain) ：
属性V的信息熵：
(1)用信息增益率代替信息增益来选择属性;
8
整理ppt
信息增益率：
采用了信息增益率作为对选择分枝属性的分枝准则。信息增益率表示了由分枝产生的有用信息的比率。因此,这个值越大, 分枝包含的有用信息越多。
(1)用信息增益率代替信息增益来选择属性;
9
整理ppt
与ID3算法相比，ID3算法选择信息增益最大即熵下降最大的属性进行分支的。当有大量不同的属性值和采用标准化的处理程序时, 这种启发式方法很有效。。从局部看，ID3算法每一步都选择最优分支属性，但是从整体上看，有可能使得整个决策树复杂。，但是从整体看，分支更明确，获得的有用信息更多。
(1)用信息增益率代替信息增益来选择属性;
10
整理ppt