文档介绍：【十大经典数据挖掘算法】 1. 决策树模型与学****决策树( decision tree )算法基于特征属性进行分类,其主要的优点:模型具有可读性,计算量小,分类速度快。决策树算法包括了由 Quinlan 提出的 ID3 与 , Breiman 等提出的 CART 。其中, 是基于 ID3 的,对分裂属性的目标函数做出了改进。决策树模型决策树是一种通过对特征属性的分类对样本进行分类的树形结构,包括有向边与三类节点: ?根节点( root node ),表示第一个特征属性,只有出边没有入边; ?内部节点( internal node ),表示特征属性,有一条入边至少两条出边?叶子节点( leaf node ),表示类别,只有一条入边没有出边。上图给出了(二叉)决策树的示例。决策树具有以下特点: ?对于二叉决策树而言,可以看作是 if-then 规则集合,由决策树的根节点到叶子节点对应于一条分类规则; ?分类规则是互斥并且完备的,所谓互斥即每一条样本记录不会同时匹配上两条分类规则,所谓完备即每条样本记录都在决策树中都能匹配上一条规则。?分类的本质是对特征空间的划分,如下图所示, 决策树学****决策树学****的本质是从训练数据集中归纳出一组分类规则[2] 。但随着分裂属性次序的不同,所得到的决策树也会不同。如何得到一棵决策树既对训练数据有较好的拟合,又对未知数据有很好的预测呢? 首先,我们要解决两个问题: ?如何选择较优的特征属性进行分裂?每一次特征属性的分裂,相当于对训练数据集进行再划分,对应于一次决策树的生长。 ID3 算法定义了目标函数来进行特征选择。?什么时候应该停止分裂?有两种自然情况应该停止分裂,一是该节点对应的所有样本记录均属于同一类别,二是该节点对应的所有样本的特征属性值均相等。但除此之外,是不是还应该其他情况停止分裂呢? 2. 决策树算法特征选择特征选择指选择最大化所定义目标函数的特征。下面给出如下三种特征( Gender, Car Type, Customer ID )分裂的例子: 图中有两类类别( C0, C1 ),是对 C0 类别的计数。直观上,应选择 Car Type 特征进行分裂,因为其类别的分布概率具有更大的倾斜程度,类别不确定程度更小。为了衡量类别分布概率的倾斜程度,定义决策树节点 t 的不纯度( impurity ),其满足:不纯度越小,则类别的分布概率越倾斜;下面给出不纯度的的三种度量: 其中, p(c k |t) 表示对于决策树节点 t 类别 c k的概率。这三种不纯度的度量是等价的,在等概率分布是达到最大值。为了判断分裂前后节点不纯度的变化情况,目标函数定义为信息增益( information gain ): I(?) 对应于决策树节点的不纯度, parent 表示分裂前的父节点, N 表示父节点所包含的样本记录数, a i表示父节点分裂后的某子节点, N(a i) 为其计数, n 为分裂后的子节点数。特别地, ID3 算法选取熵值作为不纯度 I(?) 的度量,则Δ=H(c) ?∑ i=1 n N(a i )N H(c|a i )=H(c) ?∑ in p(a i )H(c|a i )=H(c) ? H(c|A) c 指父节点对应所有样本记录的类别;A 表示选择的特征属性,即a i的集合。那么,决策