数据挖掘决策树算法和.ppt

文档介绍：数据挖掘决策树算法和学****数据挖掘的工具-wekaweka是用Java语言编写的完整的软件资源Explorer是weka的主要图形用户界面weka存储数据的原始方式是ARFF或CSV文件格式ARFF文件是由一组实例组成,并且每组实例的属性值由逗号分开。(属性的类别)天气数据outlook temperature humidity windy play1 sunny hot high FALSE no2 sunny hot high TRUE no3 overcast hot high FALSE yes4 rainy mild high FALSE yes5 rainy cool normal FALSE yes6 rainy cool normal TRUE no7 overcast cool normal TRUE yes8 sunny mild high FALSE no9 sunny cool normal FALSE yes10 rainy mild normal FALSE yes11 sunny mild normal TRUE yes12 overcast mild high TRUE yes13 overcast hot normal FALSE yes14 rainy mild high TRUE no我们希望从上面的实例中找出者若干条规则,使得能够对这些实例的类做出判断(理想情况下)(举例)ifoutlook=sunnyand=highthenplay=noifhumidity=normalthenplay=yes第二条规则错分了一个实例样本决策节点:,是整个决策树的开始。。(二叉树、多叉树)分支:判断过程,要么是新的决策节点,要么是叶子树叶:树的结尾,每个叶子代表一个类别根节点叶子节点决策节点叶子节点叶子节点步骤::由训练样本数据集(根据历史数据生成、有一定综合程度的用于数据分析处理的数据集):采用新的样本数据集(测试数据集或者训练数据修剪集)检验决策树生成过程中产生的初步规则,将影响预测准确性的分支剪除。,并对该属性的每个值产生一个分支。,并移到子女节点,产生一棵局部树。。。。,选择一棵增益最大的属性的局部树。-6步。。如果一个节点上的所有实例都具有相同的类,则停止局部树的生长。选择属性作为根产生分支计算信息增益选择max增益数据进一步分裂?结束否是算法流程图信息值(熵)、信息增益的概念熵:entropy(p1,p2,...,pn)=-p1logp1-p2logp2••••-pnlogpn使用负号是因为分数p1,p2,...,pn的对数值是负数,而熵是一个正数。熵是以位bit位单位的,公式里的p1,p2,...,pn他们的和为1。entropy(p,q,r)=entropy(p,q+r)+(q+r)*entropy(q/(q+r),r/(q+r))我们需要一种度量来表示节点的纯度,并需要这种度量告诉我们根据一个变量的属性值将一个不纯的节点上的数据划分到其子女后,纯度提高了多少。最为广泛使用的度量是信息值(熵)。(以天气数据为例)outlook属性的树桩yesyesnononoyesyesyesyesyesyesyesnonooutlooksunnyovercastrainy在叶子节点上的yes和no类的实例数量分别是[2,3]、[4,0]、[3,2],因此,这些节点上的信息值分别是:info([2,3])=entropy(2/5,3/5)=([4,0])=entropy(1,0)=0bitinfo([3,2])=entropy(3/5,2/5)=,并考虑到达每个分支的实例数量:有5个实例到达第一和第三个分支;4个实例到达第二个分支:那么平均信息值info([2,3],[4,0],[3,2])=(5/14)*+(4/14)*0+(5/14)*=,处于根节点的训练样本由9个yes和5个no组成,与之相对应的信息值:info([9,5])=:gain(outlook)=info([9,5])-info([2,3],[4,0],[3,2])=-=