第4章第三部分之一.ppt

第三部分：数据挖掘 概念 决策树 神经网络 Na?ve Bayes 基本概念 分类：给定一个数据库D={t1,t2,….,tn}和一组类C={c1,c2,….,cm}, 分类问题是去确定一个映射f:D C, 每个元组ti被分配到一个类中。 分类技术之一：决策树 决策树的应用 假如负责借贷的银行官员利用决策树来决定支持哪些贷款和拒绝哪些贷款，那么他就可以用贷款申请表来运行这棵决策树，用决策树来判断风险的大小。“年收入￥40,00”和“高负债”的用户被认为是“高风险”，同时“收入 ￥40,000”但“工作时间5年”的申请，则被认为“低风险”而建议贷款给他/她。 商场中判断顾客的等级 电子商务活动中判断客户的类型 网上书店分析客户流失情况，决策树技术中的是解决这一问题的有效途径。 决策树 决策树一般都是自上而下的来生成的。每个决策或事件（即自然状态）都可能引出两个或多个事件，导致不同的结果，把这种决策分支画成图形很像一棵树的枝干，故称决策树。 选择分割的方法有好几种，但是目的都是一致的：对目标类尝试进行最佳的分割。 从根到叶子节点都有一条路径，这条路径就是一条“规则”。 使用决策树进行分类 决策树 一个树形的结构 内部节点上选用一个属性进行分割 每个分叉代表一个测试输出 叶子节点表示一个类 决策树生成算法分成两个步骤 树的生成 开始，数据都在根节点 递归的进行数据分片 树的修剪 去掉一些可能是噪音或者异常的数据 决策树使用: 对未知数据进行分割 按照决策树上采用的分割属性逐层往下，直到一个叶子节点 拆分的原则 信息是信号、符号或消息所表示的内容，用以消除对客观事物认识的不确定性 信息量的直观定义：信息量的大小取决于信息内容消除人们认识的“不确定程度”，所消除的不确定程度越大，则所包含的信息量就越大。(例子) 基尼 基尼：是一个通用的拆分标准。 结点的基尼值就是该类比例的平方之和。 对于只有两个类的结点来说 一个完美的纯结点的基尼分数为1 一个均衡结点基尼分数为多少？ 要计算拆分的效果，可以把每一子节点的基尼分数乘以到达那个节点的记录的比例，然后把所有得到的数值求和。 两种拆分中，哪一种能增加纯度 信息增益可定义如下: 已知: 被分好类的一组例子E(或称样本) E的一个划分P= {E1, ..., En} ig(E,P)=entropy(E)- ?i=1,...,nentropy(Ei)*|Ei|/|E| 决策树的优点 很容易理解 很容易转换成规则 应用到对真实问题的处理中 能处理数值和分类数据 所生成的决策树可能产生的问题：过度拟合 过度拟合的原因 噪声导致的过分拟合 气候训练样本 由于有反例，所以有的节点被过度有哪些信誉好的足球投注网站 处理决策归纳中的过分拟合 先剪枝（提前终止规则） 如果事例的个数少于用户指定的阀值 如果扩展纯度的增益小于某个阀值 后剪枝初始决策树按照最大规模增长，然后进行剪枝的步骤，按照自底向上的方式修剪完全增长的决策树 用新的叶节点替换子树，该叶节点类标号由子树下记录中的多数类确定 用子树中最常用的分枝代替子树 后剪枝 子树上升：把一个子树移动到决策树中更高一级上，替代它的父节点 模型的评估 重点放在一个模型的预测能力 而不是这个模型运行的多快或稳定性等 混淆矩阵 【例7-4】 用决策树考察某顾客是否会购买PC 类标号属性为购买PC，它有两个不同的值(“是”、“否”)，即有两个不同的类，m=2；设p对应“是”，n对应“否”，则p=9，n=5。 1) 创建根结点 先计算对给定样本分类所需的期望信息。 = 0.94 下面计算每个属性的熵。从年龄开始计算。 年龄=“=30”： p11=2，n11=3 I (p11，n11)=0.971 年龄=“30~40”： p12=4，n12=0 I (p12，n12)=0 年龄=“40”： p13=3，n13=2 I (p13，n13)=0.971 如果样本按年龄划分，对一个给定的样本分类所需的期望信息如下。 因此，这种划分的信息增益是： Gain(年龄)= I(P，N) - E(年龄)=0.246。 同理可得 Gain(收入)=0.029 Gain(是否学生)=0.151 Gain(信用)=0.048 在所有的属性中，年龄的信息增益最高，被选作测试属性。创建一个根结点，用年龄标记，并对每个属性值引出一个分支。 2) 分支建立 考虑分支“年龄=‘=30’”的结点。 因为Gain(收入)= 0.571 Gain(学生)=0.971 Gain(信用)= 0.