决策树算法..doc

图10决策树模型图从上图可以看到,决策树由“树的节点”和“树枝”组成,节点有两种类型:内部结点和叶结点,分别用圆形和矩形表示,内部结点表示一个特征或属性,叶结点表示一个类。用决策树解决分类问题,从根结点开始,对实际问题中的某一个特征变量进行检测判断,根据判断的结果,将某个实例分配到其相应的子结点中,按这样一直分下去,最终到达其中的某个叶结点,说明该实例属于该节点对应的类[7]。,基本上可以分为三步:特征选择、决策树的生成、决策树的剪枝。(1特征选择选出对训练数据集有较好分类能力的特征。特征选择一般采用的准则是基尼系数、信息增益或者信息增益比。1先给出熵的定义(熵是表示随机变量不确定性的度量:对于一个离散的有限的随机变量X,概率分布为nipxXPii,...,2,1,(===(8则∑=-=niiippXH1log(叫做关于X的熵。由定义可知熵只依赖于分布,而与X的取值无关,所以也可以把熵记为(pH。下面我们给出条件熵的概念。∑===niiixXYHpXYH1|(|((9经验熵:由已知的数据估计得到的熵。对应的条件熵为经验条件熵。2信息增益表示得知特征X的信息而使类Y的信息的不确定性减少的程度。|((,(ADHDHADg-=(10为特征A对训练集D的信息增益。由信息增益的定义可知,信息增益和特征的分类能力呈正比,故利用信息增益来选择特征的步骤如下:对于训练数据集D,计算每个特征的信息增益,尽量选取信息增益大的特征,来构建决策树。在实际应用中,信息增益一般都是用经验熵和经验条件熵的差来近似的,其算法如下:设|D|表示样本容量,即样本个数;设有K个类KC,|KC|表示属于KC的样本个数。设特征A有n个子集nDDD,...,,21,|iD|为iD的样本个数。记子集iD中属于类KC的样本的集合为ikD,同样|ikD|为ikD样本个数。所以,训练数据集D的经验熵[8]:∑=-=KkkkDCDCDH12||||log||||((11而特征A对数据集D的经验条件熵:∑∑∑===-==niKkiikiikiniiiDDDDDDDHDDADH1121||||log||||||||(|||||((12所以信息增益:|((|(ADHDHADg-=(133以信息增益当作划分训练数据集的特征的准则,存在的问题:该准则对于取值较多的特征有优选考虑的问题,而使用信息增益比可以对这一问题进行校正:(,(,(DHADgADgAR=(14其中,∑=-=niiiADDDDDH12||||log||||(,n是特征A取值的个数