资源描述：
《数据挖掘：决策树算法及应用拓展》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、决策树生成基本思想：用途：提取分类规则，进行分类预测判定树分类算法output训练集决策树input决策树示意图使用决策树进行分类决策树一个树性的结构内部节点上选用一个属性进行分割每个分叉都是分割的一个部分叶子节点表示一个分布决策树生成算法分成两个步骤树的生成开始，数据都在根节点递归的进行数据分片树的修剪去掉一些可能是噪音或者异常的数据决策树使用:对未知数据进行分割按照决策树上采用的分割属性逐层往下，直到叶子节点决策树算法基本算法（贪心算法）自上而下分而治之的方法开始时，所有的数据都在根节点属性都是种类字段(如果是连续的，将其离散化)所有记录用所
2、选属性递归的进行分割属性的选择是基于一个启发式规则或者一个统计的度量(如,informationgain)停止分割的条件一个节点上的数据都是属于同一个类别没有属性可以再用于对数据进行分割伪代码(BuildingTree)ProcedureBuildTree(S)用数据集S初始化根节点R用根结点R初始化队列QWhileQisnotEmptydo{取出队列Q中的第一个节点NifN不纯(Pure){for每一个属性A估计该节点在A上的信息增益选出最佳的属性，将N分裂为N1、N2}}属性选择的统计度量信息增益——Informationgain(ID3/C
3、4.5)所有属性假设都是种类字段经过修改之后可以适用于数值字段基尼指数——Giniindex(IBMIntelligentMiner)能够适用于种类和数值字段信息增益度度量(ID3/C4.5)任意样本分类的期望信息：I(s1,s2,……,sm)=－∑Pilog2(pi)(i=1..m)其中，数据集为S，m为S的分类数目，PiCi为某分类标号，Pi为任意样本属于Ci的概率，si为分类Ci上的样本数由A划分为子集的熵：E(A)=∑(s1j+……+smj)/s*I(s1j+……+smj)A为属性，具有V个不同的取值信息增益：Gain(A)=I(s1,s
4、2,……,sm)－E(A)训练集(举例)ID3算法使用信息增益进行属性选择ClassP:buys_computer=“yes”ClassN:buys_computer=“no”I(p,n)=I(9,5)=0.940Computetheentropyforage:HenceSimilarlyDecisionTree(结果输出)age?overcaststudent?creditrating?noyesfairexcellent<=30>40nonoyesyesyes30..40符号描述贝叶斯理论贝叶斯分类器实验结果与分析贝叶斯分类器Ω={A1×A2
5、×...×Am}，是由所有未知类别的可能样本组成的集合；Ωc={A1×A2×...×Am×C}是由所有已知类别的样本组成的集合。DΩc是训练样例集合。Ω中的元素x表示为x=。Ωc中的元素x表示为x=。其中ai表示第i个属性的某个取值。描述用到的符号我们用Ai表示第i个属性，C表示决策属性；aik表示第i个属性的第k个取值，cj表示第j类；加上绝对值则表示相应的个数，如
6、Ai
7、表示第i个属性的取值个数，
8、cj
9、表示第j类样例个数。设x∈Ω是一个类别未知的数据样本，cj为某个类别，若数据样本x属于
10、一个特定的类别cj，那么分类问题就是决定P(cj
11、x)，即在获得数据样本x时，确定x的最佳分类。所谓最佳分类，一种办法是把它定义为在给定数据集D中不同类别cj先验概率的条件下最可能（mostprobable）分类。贝叶斯理论提供了计算这种可能性的一种直接方法更精确地讲，贝叶斯法则基于假设的先验概率、给定假设下观察到不同数据的概率，提供了一种计算假设概率的方法贝叶斯定理贝叶斯公式先验概率P(cj)P(cj
12、x)=P(x
13、cj)P(cj)P(x)联合概率P(x
14、cj)后验概率P(cj
15、x)如果没有这一先验知识，那么可以简单地将每一候选类别赋予相同的先
16、验概率。不过通常我们可以用样例中属于cj的样例数
17、cj
18、比上总样例数
19、D
20、来近似，即先验概率P(cj)P(cj)代表还没有训练数据前，cj拥有的初始概率。P(cj)常被称为cj的先验概率(priorprobability)，它反映了我们所拥有的关于cj是正确分类机会的背景知识,它应该是独立于样本的。联合概率是指当已知类别为cj的条件下，看到样本x出现的概率。联合概率P(x
21、cj)若设x=则P(x
22、cj)=P(a1,a2…am
23、cj)后验概率P(cj
24、x)即给定数据样本x时cj成立的概率,而这正是我们所感兴趣的P(cj
25、x)被称
26、为C的后验概率（posteriorprobability），因为它反映了在看到数据样本x后cj成立的置信度贝叶斯分类我们现在计算P(cM
