JS第10章 补充

1、,1,分类和预测 分类与预测的内涵 有关分类和预测的若干问题 基于决策树的分类 Microsoft 决策树挖掘模型简介 Microsoft 决策树挖掘模型的使用 贝叶斯分类 神经网络 小结,2,分类和预测 分类: 预测分类标号（或离散值） 在分类属性中的训练样本集和值(类标号)的基础上分类 数据(建立模型)并使用它分类新数据 预测: 为连续值函数建模,预测未知的或缺省值 典型应用 信誉证实 选择购物 医疗诊断 治疗的性能分析,3,分类一个两步的过程 数据分类是一个两步过程: 第一步，建立一个模型，描述预定的数据类或概念集。 第二步，使用模型进行分类。 假设每一元组/样本属于一个预定的类，由一个

2、类标号属性 的属性确定。 用来建立模型的元组集被称为训练样本集。 模型可用分类规则，决策树或数学公式表示。,4,分类一个两步的过程 模型的使用: 为了分类将来或未知的对象。 评估模型的准确性 对于每个测试样本，将已知的的类标号和该样本的模型 分类结果进行比较。 准确率是正确被模型分类的测试样本的百分比。 测试集独立于样本集，否则会出现过分适合的现象。,5,分类过程(1):建立模型 分类算法 训练数据 分类规则 (模型) IF rank = professor OR years 6 THEN tenured = yes,6,分类过程(2):使用模型进行分类 分类规则,测试数据,新数据 (Jeff

3、, Professor, 4) Tenured?,7,有指导学习和无指导学习 有指导学习(分类) 有指导:类标号伴随着训练数据,只是训练数据 所属的类。 新数据在训练集的基础上进行分类 无指导学习(聚类) 训练数据的类标号未知 给定一个度量和观测值班员集,意图确定数据 中类或聚类的存在。,8,第六章:分类和预测 分类与预测的内涵 有关分类和预测的若干问题 基于决策树的分类 Microsoft 决策树挖掘模型简介 Microsoft 决策树挖掘模型的使用 贝叶斯分类 神经网络 小结,9,关于分类和预测的问题(1):数据准备 数据清洗 预处理数据是为了减少噪声和处理空缺值 相关性分析(特征选择)

4、删除不相关和冗余属性 数据转换 概化和或规格化数据,10,关于分类和预测的问题(2): 评估分类模型 (1)预测的准确率 (2)速度 建立模型的时间 使用模型的时间 (3)强壮行 处理噪声和空缺值的能力 (4)可扩展性 (5)易理解性,11,第六章:分类和预测 分类与预测的内涵 有关分类和预测的若干问题 基于决策树的分类 Microsoft 决策树挖掘模型简介 Microsoft 决策树挖掘模型的使用 贝叶斯分类 神经网络 小结,12,决策树生成算法 决策树 一个类似于流程图的树结构 内部节点表示一个属性(取值)上的测试 每个分支代表一个测试的结果 叶结点代表类或类分布 决策树的生成包括两个过

5、程 树的建构 首先所有的训练样本都在根结点 基于所选的属性循环的划分样本 树的数量决定于分类的精度和树的大小,13,决策树生成算法,图6.2概念buys_computer的决策树 指出AllElectronics的顾客是否可能购买计算机。每个内部（非树叶）结点表示一个属性上的测试，每个树叶结点代表一个类（buys_computer=yes,或buys_computer=no）。,14,决策树生成算法 基本算法(贪心算法)ID3算法 以自顶向下递归的各个击破方式构造决策树 首先，所有的训练样本都在根结点 所有属性都是分类的(如果值是连续的，它们应预先被离散化) 基于所选属性递归的划分样本 在启发

6、式或统计度量的基础上选择测试属性(例如，信息增益) 停止划分的条件 给定节点的所有样本属于同一个类 没有剩余属性可以用来进一步划分样本-使用多数表决来分类叶节点 没有剩余的样本,15,属性选择度量 在树的每个结点上使用信息增益度量选择测试属性。 这种度量称作属性选择度量或分裂的优劣 设S是s个数据样本的集合。假定类标号属性具有m个不同值，定义 m个不同类Ci(i=1,.,m)。设si是类Ci中的样本数。对一个给定的样本分 类所需的期望信息由下式给出： 其中，pi是任意样本属于Ci的概率，并用si/s估计。 注意，对数函数以2为底，因为信息用二进位编码。,16,属性选择度量 设属性A具有v个不同

7、值a1,.,av。可以用属性A将S划分为v个子集 S1,.,Sv；其中，Sj包含S中这样一些样本，它们在A上具有值aj。如果 A选作测试属性（即，最好的划分属性），则这些子集对应于由包含集 合S的结点生长出来的分枝。设sij是子集Sj中类Ci的样本数。根据A划分 子集的熵或期望信息由下式给出： 熵值越小，子集划分的纯度越高。注意，对于给定的子集Sj， 其中， 是Sj中的样本属于Ci的概率。,17,属性选择度量 在A上分支将获得的信息增益是 Gain(A)是由于知道属性A的值而导致的熵的期望压缩。 算法计算每个属性的信息增益。具有最高信息增益的属性选作给定 集合S的测试属性。创建一个结点，并以该

8、属性标记，对属性的每个值 创建分支，并据此划分样本。,18,训练数据 集,表6-1 一个商场顾客数据库()训练样本集合,19,决策树的归纳描述 例6.2判定树归纳。表6-1给出了取自AllElectronics顾客数据库数据元组 训练集。类标号属性buys_computer有两个不同值（即,yes,no），因此 有两个不同的类(m=2)。设类C1对应于yes，而类C2对应于no。类yes有 9个样本，类no有5个样本。 为计算每个属性的信息增益，我们首先使用公式，计算对给定样本 分类所需的期望信息：,20,决策树的归纳描述 下一步，我们需要计算每个属性的熵。从属性age开始。需要观察 age的

9、每个样本值的yes和no分布。我们对每个分布计算期望信息。 对于age=”40” s13=3 s23=2 I(s13,s23)=0.971 如果样本按age划分，对一个给定的样本分类所需的期望信息为： 因此，这种划分的信息增益是 可以计算Gain(income)=0.029,Gain(student)=0.151和Gain(credit_rating) =0.048。由于age在属性中具有最高信息增益，它被选作测试属性。,21,决策树的归纳描述 创建一个结点，用age标记，并对于每个属性值，引出一个分支。样本据此划分，如图6.4所示。注意，落在分区age=“31.40”的样本都属于同一类。由于

10、它们都属于同一类yes，因此要在该分枝的端点创建一个树叶，并用yes标记。算法返回的最终判定树如图7.2所示。,22,树剪枝 树剪枝 识别和删除哪些反应映噪声或孤立点的分支 两种常用树剪枝方法: 先剪枝方法 后剪枝方法 其它: (1)可以根据编码所需的二进位位数，而不是根据期望错误率，对树进行 剪枝。“最佳剪枝树”使得编码所需的二进位最少。这种方法采用最小描述 长度（MDL）原则。由该原则，最简单的解是最期望的。不象代价复杂性剪 枝，它不需要独立的样本集。 (2)可以交叉使用先剪枝和后剪枝，形成组合式方法。后剪枝所需的计算 比先剪枝多，但通常产生更可靠的树。,23,树剪枝 ID3算法 C4.5

11、算法 SLIQ算法 SPRING算法,24,由决策树提取分类规则 “我可以由我的判定树得到分类规则吗？如果能，怎么做？” 可以提取判定树表示的知识，并以IF-THEN形式的分类规 则表示。对从根到树叶的每条路经创建一个规则。沿着给定路径 上的每个属性-值对形成规则前件（“IF”部分）的一个合取项。 叶结点包含类预测，形成规则后件（“THEN”部分）。 IF-THEN规则易于理解，特别是当给定的树很大时。,25,由决策树提取分类规则 例6.3由判定树产生分类规则。 沿着由根结点到树叶结点的路经，图6.2的决策树可以转换 成IF-THEN分类规则。由图6.2提取的规则是： IF age=”40”A

12、ND credit_rating=“excellent” THEN buys_computer=“yes” IF age=”40”AND credit_rating=“fair” THEN buys_computer=“no”,26,第六章:分类和预测 分类与预测的内涵 有关分类和预测的若干问题 基于决策树的分类 Microsoft 决策树挖掘模型简介 Microsoft 决策树挖掘模型的使用 贝叶斯分类 神经网络 小结,27,贝叶斯分类 “什么是贝叶斯分类？” 贝叶斯分类是统计学分类方法。它们可以预测类成员关系的可能性， 如给定样本属于一个特定类的概率。 贝叶斯分类基于贝叶斯定理。 分类算法

13、的比较研究发现，一种称作朴素贝叶斯分类的简单贝叶斯分类算法 可以与判定树和神经网络分类算法相媲美。 用于大型数据库，贝叶斯分类也已表现出高准确率与高速度。,28,贝叶斯分类 朴素贝叶斯分类假定一个属性值对给定类的影响独立于其它属性的值。该假 定称作类条件独立。做此假定是为了简化所需计算，并在此意义下称为“朴 素的”。 贝叶斯信念网络是图形模型。不象贝叶斯朴素分类，它能表示属性子集间的 依赖。 贝叶斯信念网络是基于贝叶斯分类技术的学习框架，集中在贝叶斯信念 网络本身架构以及它的推理算法研究上，其中， 比较有代表的工作有: 具有蕴 藏数据学习的信念网络及其推理算法EM等。 贝叶斯信念网络也可以用于

14、分类。,29,贝叶斯定理 设X是类标号未知的数据样本。设H为某种假定，如，数据样本X属于某特定 的类C。对于分类问题，我们希望确定P(H|X)给定观测数据样本X，假定 H成立的概率。 P(H|X)是后验概率，或条件X下，H的后验概率。 例如，假定数据样本世界由水果组成，用它们的颜色和形状描述。假定X表示 红色和圆的，H表示假定X是苹果，则P(H|X)反映当我们看到X是红色并是圆的 时，我们对X是苹果的确信程度。 P(H)是先验概率，或H的先验概率。P(H)是独立于X的。 对于该例子，它是任意给定的数据样本为苹果的概率，而不管数据样本看上去 如何。后验概率P(H|X)比先验概率P(H)基于更多的

15、信息（如，背景知识）。,30,贝叶斯定理,类似地，P(X|H)是条件H下，X的后验概率。 即，它是已知X是苹果，X是红色并且是圆的的概率。 P(X)是X的先验概率。 使用该例子，它是由我们的水果集取出一个数据样本是红的和圆的的概率。 “如何计算这些概率？” 正如我们下面将看到的，P(X)，P(H)和P(X|H)可以由给定的数据计算。贝叶斯定理是有用的，它提供了一种由P(X)，P(H)和P(X|H)计算后验概率P(H|X)的方法。 贝叶斯定理是：,31,朴素贝叶斯定理,朴素贝叶斯分类，或简单贝叶斯分类的工作过程如下： 1. 每个数据样本用一个n维特征向量, X=x1,x2,.,xn表示，描述由属

16、性A1,A2,.,An对样本的n个度量。 2 . 假定有m个类, C1,C2,.,Cm 。给定一个未知的数据样本X（即，没有类标号），分类法将预测X属于具有最高后验概率（条件X下）的类。即，朴素贝叶斯分类将未知的样本分配给类Ci，当且仅当： 这样，我们最大化P(Ci|X) 。其P(Ci|X)最大的类Ci称为最大后验假定。根据贝叶斯定理,32,朴素贝叶斯定理,3. 由于P(X)对于所有类为常数，只需要P(X|Ci)(Ci)最大即可。如果类的先验概率未知，则通常假定这些类是等概率的；即，P(C1)=P(C2).P(Cm) 。并据此对P(X|Ci)(Ci)最大化。否则，我们最大化P(X|Ci)(Ci

17、) 。注意，类的先验概率可以用P(Ci)=si/s计算；其中，si是类C中的训练样本数，而s是训练样本总数。,33,朴素贝叶斯定理,4. 根据给定包含多个属性的数据集, 直接计算P(X|Ci)的运算量是非常的。 为实现对P(X|Ci)的有效估算, 基于贝叶斯分类通常都假设各类别是相互独立的, 即各属性的取值是互相独立的。对于特定的类别且各属性相互独立, 就会有: 概率P(x1|Ci), P(x2|Ci), P(xn|Ci)可以由训练样本估值，其中， P(Xk|Ci)=sik/si ; 这里sik为训练样本中类别Ci且属性Ak取vk值的样本数, si 训练样本中类别为Ci 的样本数。 5.为对未

18、知样本X分类，对每个类Ci ，计算P(X|Ci)(Ci) 。样本X被指派到类Ci ，当且仅当： 换言之，X被指派到其P(X|Ci)(Ci)最大的类Ci 。,34,朴素贝叶斯定理,例6.4使用朴素贝叶斯分类预测类标号. 训练数据在表7.1中。数据样本用属性age,income,student和credit_rating描述。类标号属性buys_computer具有两个不同值（即，yes,no）。设C1对应于类buys_computer=“yes”，而C2对应于类buys_computer=“no”。分类的未知样本为： X=(age=30,income=medium,student=yes,cre

19、dit_rating=fair). 我们需要最大化P(X|Ci)(Ci) ，i=1,2。每个类的先验概率P (Ci)可以根据训练样本计算： P(buys_computer=yes)=9/14=0.643 P(buys_computer=no)=5/14=0.357,35,朴素贝叶斯定理,例6.4使用朴素贝叶斯分类预测类标号. 为计算P(X|Ci)，i=1,2。我们计算下面的条件概率: P(age=“30”|buys_computer=“yes”)=2/9=0.222 P(age=“30”|buys_computer=“no”)=3/5=0.600 P(income=“medium”|buys_

20、computer=“yes”)=4/9=0.444 P(income=“medium”|buys_computer=“no”)=2/5=0.400 P(student=“yes”|buys_computer=“yes”)=6/9=0.667 P(student=“yes”|buys_computer=“no”)=1/5=0.200 P(credit_rating=“fair”|buys_computer=“yes”)=6/9=0.667 P(credit_rating=“fair”|buys_computer=“no”)=2/5=0.400 使用以上概率，我们得到： P(X|buys_comp

21、uter=“yes”)=0.2220.4440.6670.667=0.044 P(X|buys_computer=“no”)=0.6000.4000.2000.400=0.019 P(X|buys_computer=“yes”)P(buys_computer=“yes”)=0.0440.643=0.028 P(X|buys_computer=“no”)P(buys_computer=“no”)=0.0190.357=0.007 因此,对于样本X，朴素贝叶斯分类预测buys_computer=”yes”。,36,第六章:分类和预测 分类与预测的内涵 有关分类和预测的若干问题 基于决策树的分类 M

22、icrosoft 决策树挖掘模型简介 Microsoft 决策树挖掘模型的使用 贝叶斯分类 神经网络 小结,37,神经网络概述 优点 预测的准确率通常很高 强壮性好,当训练样本包含错误时很有效 输出可以是离散的,实数值的或几个离散或实数值属性的向量 学习目标函数的快速评估 缺点 训练时间长 学习函数(权重)很难理解 不容易包含论域知识,38,神经网络概述 神经网络最早是由心理学家和神经学家提出的，旨在 寻求开发和测试神经的计算模拟。 粗略地说，神经网络是一组连接的输入/输出单元，其 中每个连接都与一个权相相联。在学习阶段，通过调整神 经网络的权，使得能够预测输入样本的正确类标号来学习。 由于单

23、元之间的连接，神经网络学习又称连接者学习。,39,神经网络概述 神经网络需要很长的训练时间，因而对于有足够长训 练时间的应用更合适。 神经网络需要大量的参数，这些通常主要靠经验确定， 如网络拓扑或“结构”。由于人们很难解释蕴涵在学习权 之中的符号含义，神经网络常常因其可解释性差而受到批 评。这些特点使得神经网络在数据挖掘的初期并不看好。 然而，神经网络的优点包括其对噪音数据的高承受能 力，以及它对未经训练的数据的分类能力。此外，最近已 提出了一些由训练过的神经网络提取规则的算法。这些因 素推动了神经网络在数据挖掘分类方面的应用。 最流行的神经网络算法是80年代提出的后向传播算法。,40,前馈神

24、经网络 -多路前馈神经网络 后向传播算法在多路前馈神经网络上学习。,图6-22 一个多层前馈神经网络 训练样本X=x1,x2,.,xi馈入输入层。每层之间存在加权连接；其中，wij表示由某层的单元j到前一层的单元i的权。,41,前馈神经网络 -多路前馈神经网络 隐藏层和输出层的单元，有时称作neurodes（源于符号生物学），或输出单元。 图6-22所示的多层神经网络具有两层输出单元。因此，我们称之为两层神经网络。类似地，包含两个隐藏层的网络称作三层神经网络，如此等等。 网络是前馈的，如果其权都不回送到输入单元，或前一层的输出单元。 网络是全连接的，如果每个单元都向下一层的每个单元提供输入。

25、给定足够多的隐藏单元，线性阈值函数的多层前馈神经网络可以逼近任何函数。,42,前馈神经网络 -定义网络拓扑 “如何设计神经网络拓扑？” 在开始训练之前，用户必须说明输入层的单元数、隐藏层数（如果多于一层）、每一隐藏层的单元数和输出层的单元数，以确定网络拓扑。,43,前馈神经网络 -定义网络拓扑 对训练样本中每个属性的值进行规格化将有助于加快学习过程。通常，对输入值规格化，使得们落入0.0和1.0之间。离散值属性可以重新编码，使得每个域值一个输入单元。 例如，如果属性A的定义域为(a0,a1,a2)，则可以分配三个输入单元表示A。即，我们可以用I0 ， I1 ， I2作为输入单元。每个单元初始化

26、为0。如果A=a0，则I0置为1；如果A=a1，I1置1；如此下去。一个输出单元可以用来表示两个类（值1代表一个类，而值0代表另一个）。如果多于两个类，则每个类使用一个输出单元。,44,前馈神经网络 -定义网络拓扑 对于“最好的”隐藏层单元数，没有明确的规则。网络设计是一个实验过程，并可能影响结果训练网络的准确性。权的初值也可能影响结果的准确性。一旦网络经过训练，并且其准确率不能被接受，则通常用不同的网络拓扑或使用不同的初始权值，重复训练过程。,45,前馈神经网络 -后向传播,“后向传播如何工作？” 后向传播通过迭代地处理一组训练样本，将每个样本的网络预测与实际知道的类标号比较，进行学习。 对

27、于每个训练样本，修改权，使得网络预测和实际类之间的均方误差最小。这种修改“后向”进行。即，由输出层，经由每个隐藏层，到第一个隐藏层（因此称作后向传播）。尽管不能保证，一般地，权将最终收敛，学习过程停止。,46,前馈神经网络 -后向传播,(1)初始化权：网络的权被初始化为很小的随机数（例如，由-1.0到1.0，或由-0.5到0.5）。每个单元有一个偏置，下面解释。偏置也类似地初始化为小随机数。 (2)向前传播输入：在这一步，计算隐藏层和输出层每个单元的净输入和输出。 首先，训练样本提供给网络的输入层。注意，对于输入层的单元j，它的输出等于它的输入；即，对于单元j，Oj=Ij。 然后，隐藏层和输出

28、层的每个单元的净输入用其输入的线性组合计算。为帮助解释这一点，图6-22给出了一个隐藏层或输出层单元。事实上，单元的输入是连接它的前一层的单元的输出。为计算它的净输入，连接该单元的每个输入乘以其对应的权，然后求和。,47,前馈神经网络 -后向传播,(2)向前传播输入： 给定隐藏层或输出层的单元j，到单元j的净输入Ij是： 其中，wij是由上一层的单元i到单元j的连接的权；Oi是上一层的单元i的输出；而j是单元j的偏置。偏置充当阈值，用来改变单元的活性。 隐藏层和输出层的每个单元取其净输入，然后将赋活函数作用于它，如图6-23所示。该函数用符号表现单元代表的神经元活性。使用logistic或si

29、moid函数。给定单元j的净输入Ij，则单元j的输出Oj用下式计算： 该函数又称挤压函数，因为它将一个较大的输入值域映射到较小的区间0到1。logistic函数是非线性的和可微的，使得后向传播算法可以对线性不可分的问题建模。,48,前馈神经网络 -后向传播,图6-23 一个隐藏或输出单元j：j的输入是来自前一层的输出。 这些与对应的权相乘，以形成加权和。加权和加到与单元j相联的偏置上。一个非线性的赋活函数用于净输入,49,前馈神经网络 -后向传播,(3)后向传播误差。 通过更新权和反映网络预测误差的偏置，向后传播误差。 对于输出层单元j，误差Errj用下式计算： 其中，Oj是单元j的实际输出，而Tj是j基于给定训练样本的已知类标号的真正输出。注意，Oj