数据挖掘导论--第4章-分类：基本概念、决策树与模型评估

1、数据挖掘分类：基本概念，决策树和模型评价，第四章分类：基本概念，决策树和模型评价，分类利用了可以将数据库中的数据映射到预定类别之一的分类函数(分类模型，分类器)。 分类、训练集：为了在数据库中构建模型而分析的数据元组形成训练集。 训练集中的单个元组称为训练样本，每个训练样本都有一个类标记。 具体的样本形式为：(v1、v2、vn； c )； vi是属性值，c是类别。 测试集：为了评估分类模型的精度，数据分类建立了两阶段流程(1)，第一阶段，描述给定的数据类集和概念集的模型，假定各组属于预定义的类，根据类标签属性将学习模型分类为分类规则、决策树、决策树为了在数据分类中使用两个阶段的过程(2)，第二

2、阶段，使用模型对将来或未知的对象进行分类，首先，评价模型的预测精度，已知的类标签及其样本的学习模型类预测比较模型在给定的测试集中的精度，在模型中被正确分类的测试器否则，发生“过度适应数据”的情况，在正确的性能被接受的情况下，可以使用分类规则对新数据进行分类的有监督的学习VS .没有监督的学习、有监督的学习(分类用)模式的学习， 没有监督的学习(集群用)使用在通知每个训练样本属于哪个类别的“监督”下进行新数据并收集了训练数据的规则进行分类，每个训练样本的类别编号未知，所学习的类别的集合和数量是事先不知道的一系列度量， 通过观察建立和聚类数据中的班级编号，对模型进行分类的结构方法，1 .机器学习方

3、法：决策树法规摘要2 .统计方法：知识表示是判别函数和原型事例贝叶斯法非参数法(邻近学习和基于事例的学习) 3 .神经网络方法： BP算法模型表示是前向反馈神经网络模型4 .粗糙集(rough set )知识表示是生成式规则，决策树的例子是，YES，NO，Married，Single，d 80K Splitting Attributes，训练数据，模型：的决策树，决策树的其他例子，categorical，categorical，continuous，class，MarSt，Refund，TaxInc 用决策树汇总分类Single，Divorced，80K，80K， 当属性上的测试分支从构建决策

4、树开始，该决策树由测试输出的每个叶节点代表类或类分布决策树的生成两个阶段组成时，树结构的每个内部节点类似于决策树的流程图，其中，所有训练样本取决于根节点上递归地选择的属性， 分割样本(必须是离散值)的树枝大多数反映训练数据中的噪声和孤立点的树的修剪，检测到这种修剪决策树的使用，尝试修剪：对未知样本进行分类，通过将样本的属性值与决策树进行比较，来确定未知数据可以基于决策树的结构测试数据集的属性，并形成了决策树的根节点到叶节点的路径对应对象的类测试。决策树是分类规则，决策树分类任务，决策树树，决策树的例子：Refund，MarSt，TaxInc，NO，NO，NO，Married，单，Divorce

5、d，80K，80k splitting attri 模型：决策树，应用决策树的分类，测试数据，startfromtherootofthetree .应用决策树的分类，测试数据，Refund，MarSt，TaxInc，NO，应用的NO，NO，Yes 单一，Divorced，80K，80K，是，否，Married，单一，Divorced，80K，80K，测试数据，Refund，mart，TaxInc，等等矩阵，单，Divorced，80K，80K，测试数据，Refund，mart，TaxInc，YES，YES，NO，NO，YES，NO，Married，单，divorc “否”，决策树分类，Deci

6、sion Tree， 决策树许多决策树算法： Hunt算法信息增益信息增益(ID3 )增益比率Gain ration(C4.5 )基尼指数Gini index (SLIQ，SPRINT )， 根据具有Hunt算法的Dt与节点t相关联的训练记录集合算法步骤：如果Dt的所有记录属于同一类yt，则t是叶节点，如果用yt表示，则如果Dt包含属于多个类的记录，则为一个为每个测试条件的输出创建子节点，并根据测试结果将Dt记录分布到子节点上。 然后，对每个子节点递归调用该算法时，Dt、 Hunt算法、Dont Cheat、决策树、Hunt算法采用贪婪策略构建决策树。 在选择划分数据的属性时，采用一系列局部最

7、优决策来构建决策树。 决策树总结的设计问题是如何分割训练记录为不同类型的属性指定测试条件的？ 如何评价各测试条件？ 如何停止分裂过程，决策树、Hunt算法采用贪婪策略来构建决策树。 在选择划分数据的属性时，采用一系列局部最优决策来构建决策树。 决策树总结的设计问题如何分裂训练记录并为不同类型的属性指定测试条件，如何评价各测试条件？ 如何停止分裂过程并为各种类型的属性指定测试条件？ 依赖于属性的类型的标称序号，连续依赖于被划分的道路数的2路分割多路复用，基于标称属性的分裂，多路复用：的划分数(输出数)依赖于该属性的不同属性值的数量。 二维分割：分割数为2，此分割是k个属性值的二维分割的所有2k-

8、1-1方法. OR必须考虑的复用分割：的分割数(输出数)取决于其属性不同的属性值的数量，双重分割：的分割数为2，需要保持序号属性值的规则性基于序数属性的分割、OR、基于连续属性的分割、复用分割：viAvi 1(i=1，k )双重分割： (A v) or (A v )考虑所有分割点来选择最佳的分割点v，连续属性的分割、决策树、决策树汇总的设计问题是如何分割训练记录而不同的类型如何评价各测试条件？ 如何停止分裂过程，如何选择最合适的划分？ 区分前： 10条记录class 1，10条记录class 1，如何选择最佳区分？ 选择最佳划分的尺度通常由划分后的子节点的不纯度决定。杂质程度越低，类分布越倾斜

9、节点的杂质尺度：杂质大，杂质小，如何找到最佳划分？ b？ 是，否，节点n3，节点n4，a？是，否，节点n1，节点N2，划分前：Gain=M0 M12 vs M0 M34，节点的不纯测量，Gini entropy类ification error， 杂质测定： GINI给定节点t的Gini值计算： (p(j | t )是在节点t发生类j的概率，在类分布均衡的情况下，Gini值达到最大值(1 - 1/nc )， 在只有一个类的情况下，计算Gini值达到最小值0的Gini的示例p (C1 )=0/6=0p (C2 )=6/6=1g ini=1p (C1 ) 2p (C2 )2=10=0， 基于GINI

10、的划分，一个p (C1 )=1/6p (C2 )=5/6Gini=1(1/6)2(5/6)2=0.278 p (C1 )=2/6p (C2 )=4/6Gini=1(2/6)2(4/6)2=0.444 n=父节点p的记录数，在二维属性：中计算GINI，在二维属性中，节点分割为两个部分的GINI的值越小，该分割越可能，b？ 是，否，节点n1，节点N2，Gini (n1 )=1(5/6)2(2/6)2=0.194 Gini (N2 )=1(1/6)2(4/6)2=0.528，Gini分割=7/12 * 0.194 /。 由于双重分割实际上集成了多重分割的输出，所以子集纯度自然下降，多分割、多分割连续

11、属性：计算Gini，使用二元分割点v选择n个记录中的所有属性值作为分割点，对各分割进行类A v and A v计算各候补点v的Gini指标，从其中选择具有最小值的分割点候补的时间复杂度为(n2 )，连续属性：计算Gini， 降低计算复杂性的方法从排序记录的两个相邻被排序的属性值之间，以中间值为分割点，计算各候补点的Gini值的时间复杂度为nlogn，定义：给定概率空间事件的自信息定义为原因，自信息反映了事件发生所需的信息量。 值越大，则为了识别事件的发生需要更多信息，随机性也变大，发生时携带的信息量也变大。 相反，值越小，以越少的信息量可靠地发生，即事件的随机性越小。 那个发生时携带的信息量很

12、少。 在不确定性大小的描绘中，熵-定义，熵-定义，1 .定义：在概率空间中定义的随机变量I(X )的数学期待，称为随机变量x的平均自信息，x的信息熵或熵标记为H(x )， 非负： h为0连续性以上： h对于任意q连续极值性： q全部等于1K时，h达到最大值logK，根据熵-定义信息gain的区分，某节点t的输入值计算： (p(j | t )为no 如果类分布均衡，那么如果Entropy值达到最大值(log nc )，并且相反只有一个类，那么计算的Gini值达到最小值0 Entropy并且与Gini类似的Entropy的例子，那么p (C1 )=0/6=0p (C2 )=6/6=1=1/6p (

13、C2 )=5/6输入=(1/6) log2 (1/6) (5/6) log2 (1/6)=0.65， 根据p (C1 )=2/6p (C2 )=4/6输入=(2/6) log2 (2/6) (4/6) log2 (4/6)=0.92信息增益的区分，信息增益： ni=儿童节点I的延迟如果在n=节点p的记录数. ID3 and C4.5中使用，则根据信息Gini的区分，增益率(Gain Ratio):熵、Gini指标等杂质有利于具有许多不同值的属性，例如，员工id 限制测试条件的只有二项划分的使用增益率。如果k越大Split Info的增益越小，且基于分类error的划分来计算给定节点t的分类er

14、ror值的：类分布均衡，则error值将达到最大值(1 - 1/nc )，反之，如果只有一个类，则为error值6=0p (c2)=6/6=1错误=1max=1max=0，p (C1 )=1/6p (C2 )=5/6错误=1max (1/6，5/6 )=1/6=1/6p (C1 )=2/6p (C2 )=4/6错误在选择划分数据的属性时，采用一系列局部最优决策来构建决策树。 决策树总结的设计问题是如何分割训练记录为不同类型的属性指定测试条件的？ 如何评价各测试条件？ 如何停止分裂过程，停止分裂过程，所有记录属于同一类，停止分裂，所有记录具有相同属性，停止分裂，加快树的生长，三种著名决策树，Cart :基本决策树算法利用Id3 :增益比的杂质，树采用二叉树停止标准是C4.5:id3的改进版，在所有记录属于同一类、停止分裂或所有记录具有相同属性时，停止分裂也是最受欢迎的分类数算法。 采用多种分支和剪枝技术。 决策树、特征：决策树不需要构建分类模型的非参数法中昂贵的计算成本决策树，是决策树