下载文档原格式
第七章分类和预测数据库内容丰富，蕴藏大量信息，可以用来作出智能的商务决策。
分类和预测是两种数据分析形式，可以用于提取描述重要数据类的模型或预测未来的数据趋势。
然而，分类是预测分类标号（或离散值），而预测建立连续值函数模型。
例如，可以建立一个分类模型，对银行贷款的安全或风险进行分类；而可以建立预测模型，给定潜在顾客的收入和职业，预测他们在计算机设备上的花费。
许多分类和预测方法已被机器学习、专家系统、统计和神经生物学方面的研究者提出。
大部分算法是内存算法，通常假定数据量很小。
最近的数据挖掘研究建立在这些工作之上，开发了可规模化的分类和预测技术，能够处理大的、驻留磁盘的数据。
这些技术通常考虑并行和分布处理。
本章，你将学习数据分类的基本技术，如判定树归纳、贝叶斯分类和贝叶斯网络、神经网络。
数据仓库技术与分类的集成，以及基于关联的分类也在本章讨论。
本章还介绍其它分类方法，如k-最临近分类、基于案例的推理、遗传算法、粗糙集和模糊逻辑技术。
预测方法，包括线性的、非线性的、广义线性回归也将简要讨论。
你将学会修改、扩充和优化这些技术，将它们应用到大型数据库的分类和预测。
7.1 什么是分类？什么是预测？数据分类是一个两步过程（图7.1）。
第一步，建立一个模型，描述预定的数据类或概念集。
通过分析由属性描述的数据库元组来构造模型。
假定每个元组属于一个预定义的类，由一个称作类标号属性的属性确定。
对于分类，数据元组也称作样本、实例或对象。
为建立模型而被分析的数据元组形成训练数据集。
训练数据集中的单个元组称作训练样本，并随机地由样本群选取。
由于提供了每个训练样本的类标号，该步也称作有指导的学习（即，模型的学习在被告知每个训练样本属于哪个类的“指导”下进行）。
它不同于无指导的学习（或聚类），那里每个训练样本的类标号是未知的，要学习的类集合或数量也可能事先不知道。
聚类是第8章的主题。
通常，学习模型用分类规则、判定树或数学公式的形式提供。
「数据挖掘⼊门系列」数据挖掘模型之分类与预测-决策树决策树在分类、预测、规则提取等领域有着⼴泛的应⽤。
决策树是⼀种树状结果，它的每⼀个叶节点对应⼀个分类。
构造决策树的核⼼问题是：在每⼀步如何选择适当的属性对样本做拆分。
对于分类问题，从已知类标记的训练样本中学习并构造出决策树是⼀个⾃上⽽下，分⽽治之的过程。
常见的决策树算法如下：1. ID3算法2. C4.5算法3. CART算法其中ID3是最经典的决策树分类算法。
ID3算法ID3算法基于信息熵来选择最佳测试属性。
它选择当前样本集中具有最⼤信息增益值的属性作为测试属性。
总的信息熵计算⽅式如下：设S是s个数据样本的集合。
假定某个类别有m个不同的取值：Ci(i = 1, 2, …, m)。
设Si是某个类别Ci中的样本数。
对于⼀个给定样本，它总的信息熵为：其中，Pi是任意样本属于Ci的概率，⼀般可以⽤Si/s估计。
每个属性的信息熵计算⽅式如下：假设⼀个属性A具有k个不同的值{a1, a2, …, ak}，利⽤属性A将集合S划分为若⼲个⼦集 {S1, S2, …, Sk}，其中Sj包含了集合S中属性A取aj值的样本。
若选择属性A为测试属性，则这些⼦集就是从集合S的节点⽣长出来的新的叶⼦节点。
设Sij是⼦集Sj中类别为Ci的样本数，则根据属性A划分样本的信息熵值为：其中，，是⼦集Sj中类别为Ci的样本的概率。
最后，⽤属性A划分样本集S后所得的信息增益（Gain）为：Gain值越⼤，说明选择测试属性A对于分类提供的信息越⼤，选择A之后对于分类的不确定程度越⼩。
ID3算法具体流程1. 对当前样本集合，计算所有属性的信息增益（总的信息熵）2. 选择信息增益最⼤的属性作为测试属性，把测试属性取值相同的样本划分为同⼀个样本集3. 若⼦样本集的类别属性只含有单个属性，则分⽀为叶⼦节点，判断其属性值并标上相应的符号，然后返回调⽤出；否则对⼦样本集递归调⽤本算法决策树案例接下来通过⼀个案例来了解天⽓、是否周末、是否有促销对销量的影响。
数据挖掘主讲教师：钟将E-mail: zhongjiang@第7章分类和预测⏹什么是分类？什么是预测?关于分类和预测的问题⏹用判定树归纳分类⏹贝叶斯分类⏹后向传播分类⏹基于源自关联规则挖掘概念的分类⏹其他分类方法⏹预测⏹分类法的准确性分类与预测⏹分类:❑预测分类标号⏹预测:❑建立连续值函数模型⏹典型应用数据分类—一个两步过程⏹模型建立: 描述预定的数据类集⏹模型使用:为了将来或未知的对象分类分类和预测的问题(1): 数据准备⏹数据清理⏹相关性分析⏹数据变换分类和预测的问题(2):比较分类方法⏹预测的准确率⏹速度⏹强壮性⏹可伸缩性⏹可解释性第7章分类和预测⏹什么是分类？什么是预测?⏹用判定树归纳分类⏹贝叶斯分类⏹后向传播分类⏹基于源自关联规则挖掘概念的分类⏹其他分类方法⏹预测⏹分类法的准确性用判定树归纳分类⏹判定树❑一个类似流程图的树结构❑每个内部节点表示在一个属性上的测试❑每个分支代表一个测试输出❑每个树叶节点代表类或类分布⏹判定树的产生包含两个方面❑树的构造❑树的剪枝⏹判定树的使用: 对未知样本分类❑样本的属性值在判定树上测试输出: 概念“buys_computer ”的判定树age?overcast student?credit rating?no yes fair excellent <=30>40nonoyesyesyes30..40判定树归纳算法⏹基本算法(贪心算法)❑自顶向下递归的各个击破方式构造判定树❑开始，所有的训练样本在根部❑属性分类(假如是连续值, 属性首先离散化)❑基于选定的属性递归的形成每个划分❑选择属性基于启发式或统计式策略(比如, 信息增益)⏹停止划分的条件❑给定节点的所有样本属于同一类❑没有剩余属性可以用来进一步划分样本–使用多数表决❑没有样本剩余由判定树提取分类规则⏹以IF-THEN形式表示分类规则⏹对从根到树叶的每条路径创建一个规则⏹沿着给定路径上的每个属性-值对形成规则前件的一个合取项⏹叶结点包含类预测⏹规则易于理解⏹例子IF age= “<=30”AND student= “no”THEN buys_computer= “no”IF age= “<=30”AND student= “yes”THEN buys_computer= “yes”IF age= “31…40”THEN buys_computer= “yes”IF age= “>40”AND credit_rating= “excellent”THEN buys_computer = “yes”IF age= “>40”AND credit_rating= “fair”THEN buys_computer= “no”分类中避免过分适应数据问题⏹产生的判定树会出现过分适应数据的问题❑由于数据中的噪声和孤立点，许多分枝反应的是训练数据中的异常❑对新样本的判定很不精确⏹两种方法❑先剪枝❑后剪枝防止分类中的过分适应❑先剪枝通过提前停止树的构造——如果在一个节点划分样本将导致低于预定义临界值的分裂（e.g. 使用信息增益度量)。
浅析数据挖掘的分类与预测方书晴【摘要】数据挖掘技术是信息时代的宠儿,而分类和预测是数据分析的两种基本形式,能预测未知数据的趋势.本文主要介绍了何为数据的分类和预测,并且通过判定树归纳细化了数据分类的划分步骤；通过介绍线性回归、多元回归以及非线性回归等预测方法加深了对数据预测的认识；并介绍了分类法准确率评估方法以及分类和预测的异同点.【期刊名称】《软件》【年(卷),期】2012(033)006【总页数】4页(P77-79,82)【关键词】数据挖掘分类预测判定树归纳线性回归保持法【作者】方书晴【作者单位】重庆邮电大学计算机科学与技术学院,重庆400000【正文语种】中文【中图分类】TP311在当今社会中，数据库蕴藏着丰富的信息，能为我们做出明智的商务决策提供帮助。
而分类和预测是数据分析的两种最基本的形式，能预测未知数据的发展趋势。
[1] 数据挖掘的分类需要两个过程，过程一（如图1所示），首先建立一个可以表述预先给定的数据类的模型，这个模型由一些描述数据库属性的数据库元组来建造，并且假设任何一个数据库元组都属于一个由类标号属性确定的类，一般来说，每个类都是预先设定的类。
对于数据挖掘的分类来说，每一个数据元组也可以作为一个实例、一个样本或者一个对象。
训练数据集是指由为组建数据类模型而被分析的数据元组成的集合，其中每一个单个元组叫做一个训练样本，每一个训练样本都可由样本群随机选取。
由于在选取的过程中，被选取的每个训练样本都有一个类标号，所以过程一也被称作有指导的学习，即在明确了被选取的每个训练样本的类标号属于哪个类的“指导”下进行的模型的学习。
[2-5]在一般情况下，数据类学习模型的提供形式主要有三种，分别为判定树、分类规则和数学公式。
例如，可用用分类规则来处理一个给定消费者的信用信息数据库，可根据消费者的信誉度情况来识别消费者，并且此分类规则可以作为今后的数据样本分类的标准。
过程二（如图2所示），利用过程一中的数据模型进行分类。
第七章分类和预测数据库内容丰富，蕴藏大量信息，可以用来作出智能的商务决策。
分类和预测是两种数据分析形式，可以用于提取描述重要数据类的模型或预测未来的数据趋势。
然而，分类是预测分类标号（或离散值），而预测建立连续值函数模型。
例如，可以建立一个分类模型，对银行贷款的安全或风险进行分类；而可以建立预测模型，给定潜在顾客的收入和职业，预测他们在计算机设备上的花费。
许多分类和预测方法已被机器学习、专家系统、统计和神经生物学方面的研究者提出。
大部分算法是内存算法，通常假定数据量很小。
最近的数据挖掘研究建立在这些工作之上，开发了可规模化的分类和预测技术，能够处理大的、驻留磁盘的数据。
这些技术通常考虑并行和分布处理。
本章，你将学习数据分类的基本技术，如判定树归纳、贝叶斯分类和贝叶斯网络、神经网络。
数据仓库技术与分类的集成，以及基于关联的分类也在本章讨论。
本章还介绍其它分类方法，如k-最临近分类、基于案例的推理、遗传算法、粗糙集和模糊逻辑技术。
预测方法，包括线性的、非线性的、广义线性回归也将简要讨论。
你将学会修改、扩充和优化这些技术，将它们应用到大型数据库的分类和预测。
7.1 什么是分类？什么是预测？数据分类是一个两步过程（图7.1）。
第一步，建立一个模型，描述预定的数据类或概念集。
通过分析由属性描述的数据库元组来构造模型。
假定每个元组属于一个预定义的类，由一个称作类标号属性的属性确定。
对于分类，数据元组也称作样本、实例或对象。
为建立模型而被分析的数据元组形成训练数据集。
训练数据集中的单个元组称作训练样本，并随机地由样本群选取。
由于提供了每个训练样本的类标号，该步也称作有指导的学习（即，模型的学习在被告知每个训练样本属于哪个类的“指导”下进行）。
它不同于无指导的学习（或聚类），那里每个训练样本的类标号是未知的，要学习的类集合或数量也可能事先不知道。
聚类是第8章的主题。
通常，学习模型用分类规则、判定树或数学公式的形式提供。
例如，给定一个顾客信用信息的数据库，可以学习分类规则，根据他们的信誉度优或相当好来识别顾客（图7.1(a)）。
该规则可以用来为以后的数据样本分类，也能对数据库的内容提供更好的理解。
第二步（图7.1(b)），使用模型进行分类。
首先评估模型（分类法）的预测准确率。
本章的7.9节介绍评估分类准确率的多种方法。
保持（holdout）方法是一种使用类标号样本测试集的简单方法。
这些样本随机选取，并独立于训练样本。
模型在给定测试集上的准确率是正确被模型分类的测试样本的百分比。
对于每个测试样本，将已知的类标号与该样本的学习模型类预测比较。
注意，如果模型的准确率根据训练数据集评估，评估可能是乐观的，因为学习模型倾向于过分适合数据（即，它可能并入训练数据中某些异常，这些异常不出现在总体样本群中）。
因此，使用测试集。
如果认为模型的准确率可以接受，就可以用它对类标号未知的数据元组或对象进行分类。
（这种数据在机器学习也称为“未知的”或“先前未见到的”数据）。
例如，在图7.1(a)通过分析现有顾客数据学习得到的分类规则可以用来预测新的或未来顾客的信誉度。
“预测和分类有何不同？”预测是构造和使用模型评估无标号样本，或评估给定样本可能具有的属性值或值区间。
在这种观点下，分类和回归是两类主要预测问题；其中，分类是预测离散或标称值，而回归用于预测连续或有序值。
然而，我们的观点是：预测类标号为分类，预测连续值（例如，使用回归方法）为预测。
这种观点在数据挖掘界广泛接受。
分类和预测具有广泛的应用，包括信誉证实、医疗诊断、性能预测和选择购物。
图7.1 数据分类过程：(a) 学习：用分类算法分析训练数据。
这里，类标号属性是credit_rating，学习模型或分类法以分类规则形式提供。
(2) 分类：测试数据用于评估分类规则的准确率。
如果准确率是可以接受的，则规则用于新的数据元组分类例7.1假定我们有一个AllElectronics的邮寄清单数据库。
邮寄清单用于分发介绍新产品和降价信息材料。
数据库描述顾客的属性，如他们的姓名、年龄、收入、职业和信誉度。
顾客可以按他们是否在AllElectronics购买计算机分类。
假定新的顾客添加到数据库中，你想将新计算机的销售信息通知顾客。
将促销材料分发给数据库中的每个新顾客的费用可能很高。
一个更有效的方法是只给那些可能买新计算机的顾客寄材料。
为此，可以构造和使用分类模型。
另外，假定你想预测在一个财政年度，一个顾客将在AllElectronics进行的主要购买数量。
由于预测的值是有序的，为此可以构造一个预测模型。
7.2 关于分类和预测的问题本节介绍分类和预测数据的预处理问题。
分类方法的比较和评估标准也在本节介绍。
7.2.1 准备分类和预测数据可以对数据使用下面的预处理，以便提高分类和预测过程的准确性、有效性和可规模性。
⏹数据清理：是旨在消除或减少数据噪音（例如，使用平滑技术）和处理遗漏值（例如，用该属性最常出现的值，或根据统计，用最可能的值替换遗漏值）的数据预处理。
尽管大部分分类算法都有处理噪音和遗漏值的机制，但该步骤有助于减少学习时的混乱。
⏹相关性分析：数据中许多属性可能与分类和预测任务不相关。
例如，记录银行贷款星期几签署的数据可能与应用的成功不相关。
此外，其它属性可能是冗余的。
因此，可以进行相关分析，删除学习过程中不相关或冗余属性。
在机器学习，这一过程称为特征选择。
包含这些属性将减慢和误导学习步骤。
理想地，用在相关分析上的时间，加上从“压缩的”结果子集上学习的时间，应当少于由原来的数据集合上学习所花的时间。
因此，这种分析可以帮助提高分类的有效性和可规模性。
⏹数据变换：数据可以泛化到较高层概念。
概念分层可以用于此目的。
对于连续值属性，这一步非常有用。
例如，属性income的数值值可以泛化为离散的区间，如low, medium和high。
类似地，标称值，如street，可以泛化到高层概念，如city。
由于泛化压缩了原来的训练数据，学习时的输入/输出操作将减少。
数据也可以规范化，特别是在学习阶段使用神经网络或涉及距离度量的方法时。
规范化涉及将属性的所有值按比例缩放，使得它们落入较小的指定区间，如-1.0到 1.0，或0.0到1.0。
例如，在使用距离度量的方法中，这可以防止具有较大初始域的属性（如income）相对于具有较小初始域的属性（如二进位属性）权重过大。
数据清理、相关分析和数据变换已在本书的第3章详细介绍。
相关分析还在第5章介绍过。
7.2.2 比较分类方法。
分类和预测方法可以根据下列标准进行比较和评估：⏹预测的准确率：这涉及模型正确地预测新的或先前未见过的数据的类标号的能力。
⏹速度：这涉及产生和使用模型的计算花费。
⏹强壮性：这涉及给定噪音数据或具有遗漏值的数据，模型正确预测的能力。
⏹可规模性：这涉及给定大量数据，有效地构造模型的能力。
⏹可解释性：这涉及学习模型提供的理解和洞察的层次。
这些问题的讨论贯穿本章。
数据库研究界对数据挖掘的分类和预测的贡献一直强调可规模性，特别是对判定树归纳。
7.3 用判定树归纳分类“什么是判定树？”判定树是一个类似于流程图的树结构；其中，每个内部结点表示在一个属性上的测试，每个分枝代表一个测试输出，而每个树叶结点代表类或类分布。
树的最顶层结点是根结点。
一棵典型的判定树如图7.2所示。
它表示概念buys_computer，即，它预测AllElectronics的顾客是否可能购买计算机。
内部结点用矩形表示，而树叶用椭圆表示。
为了对未知的样本分类，样本的属性值在判定树上测试。
路径由根到存放该样本预测的叶结点。
判定树容易转换成分类规则。
在7.3.1小节，我们介绍学习判定树的基本算法。
在判定树构造时，许多分枝可能反映的是训练数据中的噪音或局外者。
树剪枝试图检测和剪去这种分枝，以提高在未知数据上分类的准确性。
树剪枝在7.3.2小节介绍。
由判定树提取分类规则在7.3.3小节讨论。
基本判定树算法的加强在7.3.4小节给出。
大型数据库判定树归纳的可规模性问题在7.3.5小节讨论。
7.3.6小节介绍判定树归纳与诸如数据方等数据仓库机制的集成，允许多个粒度层的判定树挖掘。
判定树已在由医疗到游戏理论和商务等应用领域广泛使用。
判定树是一些商业规则归纳系统的基础。
图7.2 概念buys_computer的判定树，指出AllElectronics的顾客是否可能购买计算机。
每个内部（非树叶）结点表示一个属性上的测试，每个树叶结点代表一个类（buys_computer = yes, 或buys_computer = no）算法：Generate_decision_tree。
由给定的训练数据产生一棵判定树。
输入：训练样本samples，由离散值属性表示；候选属性的集合attribute_list。
输出：一棵判定树。
方法：(1)创建结点 N；(2)if samples都在同一个类C then(3) return N 作为叶结点，以类C标记；(4)if attribut_list为空then(5) return N 作为叶结点，标记为samples中最普通的类； //majority voting(6)选择attribute_list中具有最高信息增益的属性test_attribute；(7)标记结点 N 为test_attribute；(8)for each test_attribute中的未知值a i //partition the samples(9)由结点 N 长出一个条件为test_attribute = a i的分枝；(10)设s i是samples中test_attribute = a i的样本的集合；//a partition(11) if s i为空then(12)加上一个树叶，标记为samples中最普通的类；(13) else加上一个由 Generate_decision_tree(s i, attribute_list–test_attribute)返回的结点；图7.3 由训练样本归纳判定树的基本算法7.3.1 判定树归纳判定树归纳的基本算法是贪心算法，它以自顶向下递归的划分-控制方式构造判定树。
算法在图7.3中，是一种著名的判定树算法ID3版本。
算法的扩展将在7.3.2到7.3.6小节讨论。
算法的基本策略如下：⏹树以代表训练样本的单个结点开始（步骤1）。
⏹如果样本都在同一个类，则该结点成为树叶，并用该类标号（步骤2和3）。
⏹否则，算法使用称为信息增益的基于熵的度量作为启发信息，选择能够最好地将样本分类的属性（步骤6）。
该属性成为该结点的“测试”或“判定”属性（步骤7）。
在算法的该版本中，所有的属性都是分类的，即离散值。
连续属性必须离散化。
