第9章预测建模分类和回归

2019/12/191五邑大学计算机学院何国辉数据仓库与数据挖掘DataWarehouseandDataMining2019/12/192数据仓库与数据挖掘DataWarehouseandDataMining第九章预测建模：分类和回归2019/12/193数据挖掘的任务：除模式挖掘以外，还包括描述建模和预测建模。预测建模的目的是建立一个模型，该模型允许人们根据已知的属性值来预测其它某个未知的属性值。当被预测的属性是范畴型时称为分类。当被预测的属性是数量型时称为回归。9.0基本概念2019/12/194在预测模型中，一个变量被表达成其它变量的函数。预测建模的过程可以看作是学习一种映射或函数Y=f（X；θ）。其中f是模型结构的函数表达式，θ是f中的未知参数，X称为输入量，是一个p维向量，代表观察到的对象的p的属性值。Y通常被称为响应变量，代表预测的结果。如果Y是数量型变量，则学习从向量X到Y的映射的过程称为回归。如果Y是范畴型变量，则称之为分类。9.1预测建模简介2019/12/195预测建模的训练数据由n对（X，Y）组成。预测建模的过程就是根据训练数据拟合出模型Y=f（X；θ）。模型中的拟合过程由以下几步组成：确定模型f的结构。确定参数θ的值。θ值是通过在数据集上最小化（或最大化）一个评分函数确定的。如何搜素最佳θ值涉及到优化问题。9.1预测建模简介（续）2019/12/1969.1.1用于预测的模型结构人们通常事先并不知道f（X；θ）的形式，为f选择一个合适的函数形式是非常具有挑战性的工作。2019/12/1971.用于回归的模型主要包括：线性回归模型非线性回归模型分段线性模型2019/12/198（1）线性回归模型是最简单的回归模型。在这种模型中，响应变量Y是输入变量X的线性函数，即：Ϋ=a0+a1X1+a2X2+...+apXp。其中：Xi（0≤i≤p）是输入向量X的分量，模型的参数θ={a0，a1，a2，...，ap}Ϋ代表模型的预测值，而Y代表实际观察到的值。拟合的质量由预测值Ϋ和实际值Y之间的差来衡量。2019/12/199（1）线性回归模型（续）Ψ2019/12/1910（2）非线性回归模型通过在基本的线性回归模型上添加多项式项，可以得到非线性回归模型。几何意义：多维空间中的一个超曲面。举例：一个三次多项式回归模型：Ϋ=a0+a1X1+a2X22+a3X332019/12/1911（2）非线性回归模型（续）通过对变量进行变换，可以将非线性模型转换成线性的。令Z1=X1，Z2=X22，Z3=X33，可以将上述三次多项式回归模型转换成线性形式，结果为：Ϋ=a0+a1Z1+a2Z2+a3Z3将线性模型扩展到非线性模型提高了模型的复杂度。线性模型是非线性模型的特例。2019/12/1912（3）分段线性模型响应变量Y是输入向量X的局部线性函数，该模型在p维空间的不同区域具有不同的函数形式。是基本的线性回归模型进行扩展的方法。当p=1时，该模型表示由k个不同的线段逼近的一条曲线。当p1时，该模型表示由多个超平面逼近的一个曲面。2019/12/19132.用于分类的预测模型主要有两种：判别模型概率模型2019/12/1914（1）判别模型判别模型的输入是输入向量X，输出是响应变量Y。Y的取值为{C1，C2，...，Cm}，其中Ci表示类别。目的：只要知道各个类别的决策区域，根据输入向量X的取值，就可以确定响应变量Y的值，实现分类预测。2019/12/1915（1）判别模型（续）举例：当X的取值介于0和a之间时，Y的取值为C1；X的取值介于a和b之间时，Y的取值为C2；X的取值大于b时，Y的取值为C3。2019/12/1916（1）判别模型（续）回归模型与判别模型比较在回归模型中，模型的函数形式表示的是Y如何与X关联，响应变量Y代表和第p+1维，关心的重点是输入X时Y的取值是什么。在判别分类中，响应变量Y同样代表和第p+1维，但它的取值早已确定，是C1、C2、...、Ck中的一个。在实际的分类问题中，类别之间的边界是不可能那么清晰的。2019/12/1917（2）概率模型分类的概率建模是要针对每一个类别Ci估计一种分布或密度函数ρ（X|Ci，θi），其中θi是该函数的参数，它反映了Ci类的主要特征。如果各个均值离得足够远，而且方差足够小，则各个类在输入空间中可以被很好地分割开来，从而使得分类的准确性最高。主要代表：贝叶斯分类方法。2019/12/19189.1.2用于预测的评分函数给定训练数据D={（X(1)，Y(1)），（X(2)，Y(2)），...，（X(n)，Y(n)）}，令Ϋ（i）为模型f（X；θ）使用参数值θ根据输入向量X(i)做出的预测值，则评分函数应该为预测值Ϋ（i）与实际值Y(i)间差值的函数。2019/12/19199.1.2用于预测的评分函数（续）几种评分函数：对于回归，普遍使用的评分函数--误差平方和。对于分类，普遍使用的是--误分类率。其中，当时，，否则等于1。NiiYiYNS12))()((1NiiYiYINS12))(),((1)()(iYiY0))(),((iYiYI2019/12/19209.1.3用于预测的搜索和优化策略搜索和优化的目标是：确定预测模型f（X；θ）的形式f及其参数值θ，以使评分函数达到最小值（或最大值）常用的优化方法：爬山法、最陡峭下降法、期望最大化法。常用的搜索方法：贪婪搜索法、分支界定法、宽度（深度）优先遍历法等。2019/12/1921决策树分类属于判别模型。决策树分类的主要任务是要确定各个类别的决策区域。在决策树分类模型中，不同类别之间的边界通过一个树状结构来表示。9.2决策树分类2019/12/1922举例：下图给出了一个商业上使用的决策树的例子。它表示了一个关心电子产品的用户是否会购买PC（buys_computer）的知识，用它可以预测某条记录（某个人）的购买意向。9.2决策树分类（续）Age?Credit_rating?student?yesnoyesyesno=30?4030…40yesnofairexcellent2019/12/1923其中：内部节点（方形框）代表对记录中某个属性的一次测试，叶子节点（椭圆形框）代表一个类别。9.2决策树分类（续）2019/12/1924用决策树进行分类的步骤：第一步，利用训练集建立一棵决策树，得到一个决策树分类模型。第二步，利用生成的决策树对输入数据进行分类。对于输入的记录，从根节点依次测试记录的属性值，直至到达某个叶子节点，从而找到该记录所属的类别。9.2决策树分类（续）2019/12/1925构造决策树是采用自上而下的递归构造方法。以多叉树为例，如果一个训练数据集中的数据有几种属性值，则按照属性的各种取值把这个训练数据集再划分为对应的几个子集（分支），然后再依次递归处理各个子集。反之，则作为叶结点。问题的关键是建立一棵决策树。这个过程通常分为两个阶段：建树（TreeBuilding）：决策树建树算法见下，这是一个递归的过程，最终将得到一棵树。剪枝（TreePruning）：剪枝的目的是降低由于训练集存在噪声而产生的起伏。9.2决策树分类（续）2019/12/19269.2.1建树阶段递归处理过程采用分而治之的方法。通过不断地将训练样本划分成子集来构造决策树。假设给定的训练集T总共有m个类别，则针对T构造决策树时，会出现以下三种情况：如果T中所有样本的类别相同，那么决策树只有一个叶子节点。如果T中没有可用于继续分裂的变量，则将T中出现频率最高的类别作为当前节点的类别。如果T包含的样本属于不同的类别，根据变量选择策略，选择最佳的变量和划分方式将T分为几个子集T1、T2、...、Tk，每个数据子集构成一个内部节点。2019/12/19279.2.1建树阶段（续）对于某个内部节点继续进行判断，重复上述操作，直到满足决策树的终止条件为止。终止条件是：节点对应的所有样本属于同一个类别，或者T中没有可用于进一步分裂的变量。2019/12/19289.2.1建树阶段（续）决策树构建算法：输入：训练集T，输入变量集A，目标（类别）变量Y输出：决策树TreeGenerate_decision_tree（T，A，Y）1；如果T为空，返回出错信息；2；如果T的所有样本都属于同一个类别C，则用C标识当前节点并返回；2019/12/19299.2.1建树阶段（续）3；如果没有可分的变量，则用T中出现频率最高的类别标识当前节点并返回；4；根据变量选择策略选择最佳变量X将T分为k个子集（T1、T2、...、Tk）；如何选择分裂变量呢？5；用X标识当前节点；6；对T的每个子集Ti，生成新节点：7；NewNode=Generate_decision_tree（Ti，A-X，Y）8；生成一个分枝，该分枝由节点X指向NewNode；9；返回当前节点。2019/12/19309.2.1建树阶段（续）有两种比较流行的分裂变量选择方法：信息增益（InformationGain）：指标的原理来自于信息论。1948年，香农（C.E.Shannon）提出了信息论。其中给出了关于信息量（Information）和熵（Entropy）的定义，熵实际上是系统信息量的加权平均，也就是系统的平均信息量。增益比（Gain_ratio）2019/12/19311.信息增益由Quinlan在80年代中期提出的ID3算法是分类规则挖掘算法中最有影响的算法。该算法提出了使用信息增益作为衡量节点分裂质量的标准。信息增益最大的变量被认为是最佳的分裂变量。2019/12/19321.信息增益（续）计算信息增益的思路：首先计算不考虑任何输入变量的情况下，要确定T中任一样本所属类别需要的信息Info(T);计算引入每个输入变量X后，要确定T中任一样本所属类别需要的信息Info（X，T）；计算两者的差Info(T)-Info（X，T），此即为变量X的信息增益，记为Gain（X,T）。2019/12/19331.信息增益（续）计算熵Info(T)如果不考虑任何输入变量，而将训练集T中的所有样本仅按照响应变量Y的值分到m个不相交的类别C1、C2、...、Cm的话，要确定任一样本所属的类别需要的信息为：mInfo(T)＝－Σi=1(|Ci|/|T|).log2(|Ci|/|T|))以2为底的原因是：信息按二进制位编码2019/12/19341.信息增益（续）计算熵Info（X，T）如果考虑某个输入变量X，将训练集T按照X的值划分为n个子集T1、T2、...、Tn的话，要确定T中任一样本所属的类别需要的信息为：其中：注：Sj为Tj中属于类别Cj的样本子集。nInfo(X，T)＝－Σi=1(|Ti|/|T|).Info(Ti)mInfo(Ti)＝－Σj=1(|Sj|/|Ti|).log2(|Sj|/|Ti|)2019/12/19351.信息增益（续）计算增益Gain（X,T）Gain（X,T）=Info（T）-Info（X，T）所有变量的信息增益计算完后，可以根据信息增益的大小多所有输入变量进行排序，优先使用信息增益大的变量。2019/12/19361.信息增益（续）举例：本例将如下表数据作为训练集。2019/12/19371.信息增益（续）训练例子的简单平面数据库数据库T：属性1属性2属性3属性4A70真类1A90真类2A85假类2A95假类2A70假类1B90真类1B78假类1B65真类1B75假类1C80真类2C70真类2C80假类1C80假类1C96假类12019/12/19381.信息增益（续）其中：有9个样本属于类1，有5个样本属于类2。因此分区前的熵为：Info(T)＝-9/14.log2(9/14)-5/14.log2(5/14)=0.940比特2019/12/1939