数据挖掘-决策树分类

1、数据挖掘和模式识别，冯军QQ :1054685717，2016年12月，第四期。决策树分类，大纲，分类问题概述，1。分类问题概述，动物分类：有动物学家陪孩子们在森林里散步。如果一只动物突然从孩子们身边跑过，他们会问：“这是什么动物？”动物学家说“松鼠”！这就是所谓的动物分类。数据分类：对于类别标签未知的数据对象Zu，给出其类别名称或标签。动物学家认为动物可以给动物命名，因为他已经研究了很长时间，并且记住了各种动物的特征或分类规则。数据分类器：几个分类规则的集合。分类标签(离散或分类)基于训练集中分类属性的值，对数据进行分类(建立模型)，并使用它对新数据进行分类。分类分析包括三个步骤：挖掘分类规

2、则(建立分类器或分类模型)、评估分类规则和应用分类规则。挖掘分类规则(建立分类器)，假设元组/样本属于预定义的类别，由类标签属性确定的用于模型构建的元组集是训练集。首先，将一个已知类别标签的数据样本集(也称为样本库)随机分为训练集S(通常占2/3)和测试集T.通过分析S中的所有样本点(数据对象)，可以对每个类别进行准确的特征描述，或者建立分类模型，或者挖掘分类规则。这一步骤也称为监督学习，即在模型建立之前通知每个训练样本。训练集S=X1、X2、Xn和每个样本点Xi对应于已知的类别标签Cj。挖掘分类规则(建立分类器)，训练数据，分类算法，ifrank=教授或第6年，然后拉伸=是，分类器(模型)，

3、挖掘分类规则(建立分类器)，定义4-1对于给定的训练样本集S和分类属性C=C1，C2，CK，如果可以找到，每个XiS有一个唯一的Cj，以便f(Xi)=Cj，并且Cj=Xi | f(Xi)=Cj，1jk，XiS。函数f称为分类器、分类规则或分类方法，其搜索过程称为分类规则挖掘。挖掘分类规则(建立分类器)，并且类别标签Cj实际上表示属于该类别的样本点集合。例如，我们说采样点X1、X2和X3属于C1，这意味着采样点X1、X2和X3属于C1，即C1=X1、X2和X3。因此，C1不仅是一个类标签(分类属性值)，而且是属于这个类的所有样本点的集合。分类规则评估，如果测试集T中的N个样本点被分类模型正确分类

4、，则分类模型对测试集T的精度定义为“正确预测数/总预测数”，即精度=N/|T|。由于T中的样本点具有分类标记，因此很容易计算分类器的准确度来正确地对T中的样本进行分类。另外，T中的样本是随机选择的，并且完全独立于训练集S，高的测试准确度表明分类模型是可用的。如果训练集S直接用于评价，评价结果可能是乐观的，即准确率非常高。然而，因为分类模型是由S学习的，所以它倾向于过度拟合训练集S，而对除S之外的其他数据对象的分类可能非常不准确。因此，交叉验证是评估模型的更合理的方法。应用分类规则，如果评估分类模型的准确性是可接受的，下一步是使用这个分类器来分类没有类别标签的数据集z。也就是说，从Z中随机取出样

5、本点Zu并输入到分类器中，并且获得的类别标签是Zu所属的类别集。，分类规则应用，分类器，训练数据，不可见数据，(杰夫，教授，4)，拉伸？分类问题概述，分类方法评估，精度分类器精度：预测分类标签预测精度：猜测预测属性的值构建模型的速度时间(训练时间)使用模型的时间(分类/预测时间)鲁棒性(鲁棒性):通过可解释模型提供的理解和洞察力来处理噪声和缺失值，分类问题概述，评估标准，测试集的准确性和测试集的分类准确性。例如，如果100个测试用例中有90个被正确分类，准确率为90%。测试集的错误率、测试集的错误预测百分比、速度和可伸缩性、速度和可伸缩性、建立分类器和分类新案例的时间、数据大小的可伸缩性、分类

6、问题概述、评估标准、二进制类值的混淆矩阵、“是”和“否”，一个矩阵表示真阳性、真阴性、假阳性和假阴性率、分类问题概述、评估技术、k倍交叉验证(k- :将数据集划分为k个子样本。在每次运行中，使用不同的子样本作为测试集。其余的K-1子样本用作训练集。该方法是通过K次运行的平均值来估计的。该方法降低了训练集/测试集的随机性。k-最近邻分类和k-最近邻(KNN)分类是基于距离的分类算法，它们不需要预先建立分类模型或评估分类模型，而只使用带有类别标签的样本集。假设样本集S中的每个数据点具有唯一的类别标签，并且每个类别标识符Cj具有多个数据对象。对于无标记数据点Zu，k-最近邻分类遍历搜索样本集S，找出

7、与Zu最接近的K个样本点，即k-最近邻集N，并将大多数样本的类别标签分配给Zu。k-最近邻分类，KNN算法描述，示例1:设置公司15名员工的基本信息，包括高、中和矮的分类标记。公司刚刚招聘了一名新员工，名叫刘萍，Z1，所以k=5。尝试用k-神经网络分类算法来判断刘萍属于哪一类员工。KNN算法实例分析，解：只有身高是与身高相关的属性，所以Xi用来表示ith员工的身高。首先，从x中选出5名员工作为初始k-最近邻集N。在不失一般性的情况下，取N=X1=1.60，X2=2.00，X3=1.90，X4=1.88，X5=1.70 (1) X6=1.85为S，X2=2.00为高度，N和Z1的员工之间的最大差

8、异为1.62为高度，有d (Z1，X2 X3=1.90，X4=1.88，X5=1.88 x4=Get N=X1=1.60，X6=1.85，X7=1.59，X8=1.70，X5=1.70 (4)，因为X9=2.20，X10=2.10，根据算法，N不需要改变。 (5)将X6=1.85替换为X11=1.80，其中N=X1=1.60，X11=1.80，X7=1.59，X8=1.70，X5=1.70；(6)因为X12=1.95，X13=1.90，X14=1.80，所以n不需要改变。(7)将X11=1.80替换为X15=1.75，其中N=X1=1.60，X15=1.75，X7=1.59，X8=1.70，X

9、5=1.70；(8)在步骤(7)中获得的N中，有五个雇员的高度最接近Z1=1.62，并且这四个雇员的类别是“矮”，并且只有X15=1.75的类别是“中”。因此，新员工Z1=刘萍很矮。决策树分类的基本概念。决策树表示是最广泛使用的逻辑方法之一，它从一组无序和不规则的案例中推断出决策树表示的分类规则。决策树分类方法采用自顶向下递归，比较决策树内部节点的属性值，根据不同的属性值判断从节点向下的分支，在决策树的叶节点得到结论。树的叶节点表示类别标签，即分类属性值，它对应于数据对象的子集；树的内部节点是一个条件属性，它是数据对象子集的标识符；内部节点为每个条件属性值或条件属性值的组合形成一个分支，它连接

10、到树的下一个节点(也是数据对象的子集)；从根节点到叶节点的路径称为决策规则，它可以对未知数据进行分类或预测。决策树是一种有向树，也称为根树，由矩形节点、椭圆节点和有向边组成。因为方向边的方向总是向下的，所以省略了指示方向的箭头。决策树包含三种类型的节点，它们由标记有属性值的有向边连接。(1)根节点，由矩形表示，例如“天气”节点，它具有零个或多个输出边。其中字符串“weather”是样本集属性的名称。(2)内部节点，由矩形表示。例如，“温度”节点正好有一个输入边，但有两个或多个输出边。温度是样本集属性名称。(3)叶节点或终端节点由椭圆表示，例如，“是”节点正好有一个输入边，但没有输出边。椭圆中的

11、字符串“是”是样本集的类别标签。(4)每条有向边都标有其出点的属性值，如“晴天”、“阴天”和“雨天”。通常，节点的有向边与属性值一样多，并且每条边代表属性值。下面是一个例子，来自Quinlan ID3，例子，训练数据集，例子，输出：a决策树为“buys _ computer”，例子，决策树分类的基本概念，为什么决策树被引入数据挖掘？学习速度更快(与其他分类方法相比)，可以转换成简单易懂的分类规则。SQL查询可以用来访问数据库，其分类精度与其他方法相当。决策树分类的基本概念，决策树分类算法通常分为两个步骤：决策树生成和决策树剪枝。(1)决策树生成算法决策树生成算法的输入参数是一组带有类别标记的样

12、本，输出是构造一棵决策树，它可以是二叉树或多叉树。二叉树的内部节点(非叶节点)一般表示为逻辑判断，构造决策树的方法是自顶向下递归方法。决策树分类的基本概念，基本算法(Hunt贪婪算法)从自顶向下递归分治法开始构建决策树。所有的训练示例都基于根目录属性的分类(如果它是一个连续的值，应该提前离散化)。例如，基于所选属性的分区递归，以及基于探索性或统计测量(例如，信息增益)的测试属性的选择停止分裂的条件对于给定的节点，所有样本属于同一类，并且没有剩余属性用于进一步的分区，则分类叶采用多数投票方法，并且没有样本剩余。决策树分类基本概念，算法4.1生成_决策树(决策树生成算法)输入：训练样本，由离散值属

13、性表示；候选属性属性列表的集合。输出：决策树(从给定的训练数据生成决策树)。建立节点n；如果样本都在同一个c类中，则n作为叶子节点返回，用c类标记，程序结束；如果attribute_list为空，则n作为叶节点返回，标记为样本中最常见的(多数投票)类，程序结束；决策树分类的基本概念，选择属性test _ attribute属性列表中的信息增益最高；将节点n标记为测试属性；对于测试属性中的每个已知值ai，测试属性=ai的分支从节点N开始增长；假设si是样本中test_attribute=ai的样本集合。如果si为空，则添加一个叶，并将其标记为样本中最常见的类，否则添加一个由Generate_de

14、cision_tree返回的节点。决策树分类的基本概念，构建好决策树的关键在于如何选择好的逻辑判断或属性。对于同一个样本集，可以有许多决策树来匹配这个样本集。一般来说，树越小，预测能力越强。为了构造尽可能小的决策树，关键是选择合适的属性来生成分支。决策树分类基本概念，(2)决策树修改算法的剪枝是克服噪声的基本技术，有两种基本的剪枝策略：预剪枝：在生成树时决定是否继续划分或停止不纯的训练子集。后修剪：拟合和简化的两阶段方法。首先，教师建立一棵完全符合训练数据的决策树，然后开始从树叶中修剪，逐渐向根部修剪。修剪时，使用测试数据集(调整集或调整集)。如果切割某片叶子后测试集的准确度或其他测试度没有降

15、低，则切割叶子；否则停止。决策树分类的基本概念，典型的DT算法ID3算法C4.5算法CN2算法SLIQ算法SPRINT算法ID3算法ID3算法基本策略和ID3算法核心熵和信息增益ID3算法描述ID3算法实例分析ID3算法源程序分析ID3算法特点ID3算法应用ID3算法基本策略和核心ID3算法基本策略如下：(1)树从代表训练样本的单个节点开始；(2)如果样本都在同一个类中，则该节点成为叶节点并被标记为该类；(3)否则，该算法利用信息熵(称为信息增益)作为启发式知识，帮助选择合适的属性对样本进行分类，从而将样本集分成若干子集，这些子集是对应节点的“测试”或“判断”属性；(4)为测试属性的每个已知离散值创建分支，并根据该分支划分样本；(5)该算法使用类似的方法在每个分区上递归地形成样本决策树；I