人工智能之机器学习C4．5算法解析.doc

前言:人工智能之机器学习主要有三大类:1)分类;2)回归;3)聚类。。

[参见人工智能(23)]的算法。该算法是对Quinlan之前开发的ID3算法的一个扩展。,因此该算法也可以用于统计分类。
,并和ID3一样通过学习数据来建立决策树。ID3算法使用的是信息熵的变化值,。在决策树构造过程中进行剪枝,因为某些具有很少元素的结点可能会使构造的决策树过适应(Overfitting),如果不考虑这些结点可能会更好。对非离散数据能处理,并对不完整数据进行处理。

:
,用来构造决策树。。它是一系列用在机器学习和数据挖掘分类问题中的算法。它的目标是监督学习:给定一个数据集,其中的每一个元组都能用一组属性值来描述,每一个元组属于一个互斥的类别中的某一类。通过学习,找到一个从属性值到类别的映射关系,并且这个映射能用于对新的类别未知的实体进行分类。
:
,:1)通过信息增益率选择分裂属性,克服了ID3算法中分裂属性的不足;2)通过将连续型的属性进行离散化处理,克服ID3算法不能处理连续型数据缺陷;3)构造决策树之后进行剪枝操作,解决ID3算法中可能会出现的过拟合问题;4)能够处理具有缺失属性值的训练数据。
:
ID3采用的信息增益度量。它优先选择有较多属性值的Feature,因为属性值多的Feature会有相对较大的信息增益。信息增益反映的给定一个条件以后不确定性减少的程度,分得越细的数据集确定性更高,也就是条件熵越小,信息增益越大。避免这个不足的一个度量就是不用信息增益来选择Feature,而是用信息增益比率(gain raTIo)。
增益比率通过引入一个被称作分裂信息(Split informaTIon)的项来惩罚取值较多的Feature,分裂信息用来衡量Feature分裂数据的广度和均匀性(有点像煎饼中均匀摊鸡蛋的感觉^_^)。
分裂信息公式:
信息增益比率公式:
但是当某个Di的大小跟D的大小接近时,则
SpliTInformaTIon(D,A)→0
GainRatio(D,A)→∞
为了避免这样的属性,采用启发式思路,只对那些信息增益比较高的属性才用信息增益比率。:
,而是一组算法。。

,具体步骤为:
1)把需要处理的样本(对应根节点)或样本子集(对应子树)按照连续变量的大小从小到大进行排序;
2)假设该属性对应的不同的属性值一共有N个,那么总共有N?1可能的候选分割阈值点,每个候选的分割阈值点的值为上述排序后的属性值中两两前后连续元素的中点,根据这个分割点把原来连续的属性分成离散属性(比如BooL属