第3章 分类与回归 3.1 概述 3.2 决策树分类方法 3.3 贝叶斯分类方法 3.4 K-最近邻分类方法 3.5 神经网络分类方法

Presentation on theme: "第3章 分类与回归 3.1 概述 3.2 决策树分类方法 3.3 贝叶斯分类方法 3.4 K-最近邻分类方法 3.5 神经网络分类方法"— Presentation transcript:

1 第3章 分类与回归 3.1 概述 3.2 决策树分类方法 3.3 贝叶斯分类方法 3.4 K-最近邻分类方法 3.5 神经网络分类方法
3.1 概述 3.2 决策树分类方法 3.3 贝叶斯分类方法 3.4 K-最近邻分类方法 3.5 神经网络分类方法 3.6 支持向量机 3.7 组合学习方法 3.8 不平衡数据分类问题 3.9 分类模型的评价 3.10 回归方法

2 3.1 概述

3 分类的定义 分类是数据挖掘中的一种主要分析手段 分类的任务是对数据集进行学习并构造一个拥有预测功能的分类模型，用于预测未知样本的类标号，如：
根据电子邮件的标题和内容检查出垃圾邮件 根据核磁共振的结果区分肿瘤是恶性还是良性的 根据星系的形状对它们进行分类 划分出交易是合法或欺诈 将新闻分类金融、天气、娱乐体育等

4 分类与回归的区别 分类和回归都有预测的功能，但是： 分类与回归的例子： 分类预测的输出为离散或标称的属性； 回归预测的输出为连续属性值；
预测未来某银行客户会流失或不流失，这是分类任务； 预测某商场未来一年的总营业额，这是回归任务。

5 分类的步骤 分类的过程描述如下： 1)首先将数据集划分为2部分：训练集和测试集。 2) 第一步：对训练集学习，构建分类模型。
模型可以是决策树或分类规则等形式。 3) 第二步：用建好的分类模型对测试集分类 评估该分类模型的分类准确度及其它性能。 4)最后，使用分类准确度高的分类模型对类标号未知的未来样本数据进行分类。

6 分类与聚类的区别 分类因为使用了类标号属性，属于有监督的学习方法 聚类，事先没有使用任何类标号信息，属于无监督的学习方法

7 分类的应用 目前分类与回归方法已被广泛应用于各行各业，如： 股票预测 信用评估 医疗诊断 市场营销 图像分类等 ……

8 数据挖掘中分类算法归类 分类模型的学习方法大体上主要有以下几类 基于决策树的分类方法 贝叶斯分类方法 K-最近邻分类方法 神经网络方法
支持向量机方法 集成学习方法 ……

9 回归分析 回归分析可以对预测变量和响应变量之间的联系建模。 回归分析包括：线性回归、非线性回归以及逻辑回归等。
在数据挖掘环境下，预测变量是描述样本的感兴趣的属性，一般预测变量的值是已知的，响应变量的值是我们要预测的。当响应变量和所有预测变量都是连续值时，回归分析是一个好的选择。 回归分析包括：线性回归、非线性回归以及逻辑回归等。

10 3.2 决策树分类方法

11 决策树的基本概念

12 3.2.1 决策树的基本概念 决策树(Decision Tree)是一种树型结构，包括：决策节点(内部节点)、分支和叶节点三个部分。 其中：
决策树的基本概念 决策树(Decision Tree)是一种树型结构，包括：决策节点(内部节点)、分支和叶节点三个部分。 其中： 决策节点代表某个测试，通常对应于待分类对象的某个属性，在该属性上的不同测试结果对应一个分支。 叶节点存放某个类标号值，表示一种可能的分类结果。 分支表示某个决策节点的不同取值。 决策树可以用来对未知样本进行分类，分类过程如下：从决策树的根节点开始，从上往下沿着某个分支往下搜索，直到叶结点，以叶结点的类标号值作为该未知样本所属类标号。

13 典型决策树

14 决策树分类例题演示1 某银行训练数据下表， 请利用决策树分类方法预测类标号未知的新样本{“是”,“5000~10000”,“<2”,“是”,？}，其类标号属性为流失或不流失. 是否定期 存款数 月业务频率 是否投资 是否流失 "否" "10000~20000" "5~10" "不是" "不流失" "5000~10000" ">10" "是" "20000~30000" "<2" "流失" …

15 首先，建立决策树

16 然后，使用决策树对未知新样本分类： 未知样本：{“是”,“5000~10000”,“<2”,“是”,？}

17 决策树分类例题演示2 决策树模型 训练数据集 有房者 婚姻状态 categorical continuous class 年收入 YES
NO Yes No Married Single, Divorced < 80K > 80K 训练数据集 决策树模型

18 应用模型测试数据 测试数据 Start from the root of tree. 有房者 婚姻状态 年收入 YES NO Yes No
Married Single, Divorced < 80K > 80K

19 应用模型测试数据 测试数据 有房者 婚姻状态 年收入 Yes No NO Single, Divorced Married NO
< 80K > 80K NO YES

20 应用模型测试数据 测试数据 有房者 婚姻状态 年收入 Yes No NO Single, Divorced Married NO
< 80K > 80K NO YES

21 应用模型测试数据 测试数据 有房者 Yes No NO 婚姻状态 Single, Divorced Married 年收入 NO
< 80K > 80K NO YES

22 应用模型测试数据 测试数据 有房者 婚姻状态 年收入 Yes No NO Single, Divorced Married NO
< 80K > 80K NO YES

23 应用模型测试数据 分配拖欠房款属性为： “No” 测试数据 有房者 婚姻状态 年收入 Yes No NO Single, Divorced
Married 年收入 NO < 80K > 80K NO YES

24 3.2.2 决策树的构建 决策树在构建过程中需重点解决2个问题： (1)如何选择合适的属性作为决策树的节点去划分训练样本；
(2)如何在适当位置停止划分过程，从而得到大小合适的决策树。

25 1.决策树的属性选择 虽然可以采用任何一个属性对数据集进行划分，但最后形成的决策树会差异很大。需要寻找合适的属性选择方法。
属性选择是决策树算法中重要的步骤，常见的属性选择标准包括信息增益(information gain)和Gini系数。 信息增益是决策树常用的分枝准则,在树的每个结点上选择具有最高信息增益的属性作为当前结点的划分属性。 Gini系数是一种不纯度函数，用来度量数据集的数据关于类的纯度。

26 2.获得大小合适的树 决策树学习的目的是希望生成能够揭示数据集结构并且预测能力强的一棵树，在树完全生长的时候有可能预测能力反而降低，为此通常需要获得大小合适的树。 一般来说有两种获取方法: 一种为定义树的停止生长条件,常见条件包括最小划分实例数、划分阈值和最大树深度等。 另一种方法是对完全生长决策树进行剪枝，方法是对决策树的子树进行评估，若去掉该子树后整个决策树表现更好，则该子树将被剪枝。

27 3.决策树构建的经典算法 Hunt算法是许多经典决策树算法如ID3、C4.5的基础
Hunt算法对决策树的建立过程描述如下，假定Dt是与结点t相关联的训练记录集，C={C1,C2,…,Cm}是类标号，Hunt算法的递归定义如下： (1)如果Dt中所有记录都属于同一个类Ci(1≤i≤m),那么t是叶结点，用类标号Ci进行标记。 (2)如果Dt包含属于多个类的记录,则选择一个属性测试条件，将记录划分为更小的子集。对于测试条件的每个输出，创建一个子女节点，并根据测试结果将Dt中的记录分布到子女节点中，然后对每个子女节点递归调用该算法。

28 3.2.3 ID3分类算法 DI3分类算法概述 ID3分类算法由Quinlan于1986年提出
它使用信息增益(information gain)作为属性的选择标准。 首先检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有子集仅包含同一个类别的数据为止。最后得到一棵决策树，它可以用来对新的样本进行分类。

29 基本概念 与ID3分类算法相关的基本概念包括： 信息熵 信息增益

30 信息熵 熵(entropy,也称信息熵)用来度量一个属性的信息量。
假定S为训练集，S的目标属性C具有m个可能的类标号值，C={C1,C2,…,Cm}，假定训练集S中，Ci在所有样本中出现的频率为 (i=1,2,3,…,m)，则该训练集S所包含的信息熵定义为： 熵越小表示样本对目标属性的分布越纯，反之熵越大表示样本对目标属性分布越混乱。

31 信息熵例题演示 考虑数据集weather如下, 求weather数据集关于目标属性play ball的熵。 outlook
temperature humidity wind play ball sunny hot high weak no strong overcast yes rain mild cool normal

32 信息熵例题演示(续) 解答：令weather数据集为S，其中有14个样本,目标属性play ball有2个值{C1=yes, C2=no}。14个样本的分布为： 9个样本的类标号取值为yes，5个样本的类标号取值为No。C1=yes在所有样本S中出现的概率为9/14，C2=no在所有样本S中出现的概率为5/14。 因此数据集S的熵为：

33 信息增益 信息增益是划分前样本数据集的不纯程度(熵)和划分后样本数据集的不纯程度(熵)的差值。
假设划分前样本数据集为S,并用属性A来划分样本集S，则按属性A划分S的信息增益Gain(S,A)为样本集S的熵减去按属性A划分S后的样本子集的熵： 按属性A划分S后的样本子集的熵定义如下：假定属性A有k个不同的取值，从而将S划分为k个样本子集{S1,S2,…,Sk}，则按属性A划分S后的样本子集的信息熵为: 其中|Si|(i,=1,2,…k)为样本子集Si中包含的样本数，|S|为样本集S中包含的样本数。信息增益越大，说明使用属性A划分后的样本子集越纯，越有利于分类。

34 信息增益例题演示 以数据集weather为例，设该数据集为S，假定用属性wind来划分S，求S对属性wind的信息增益。 outlook
temperature humidity wind play ball sunny hot high weak no strong overcast yes rain mild cool normal

35 信息增益例题演示(续) 解答： (1)首先由前例计算得到数据集S的熵值为0.94；
(2)属性wind有2个可能的取值{weak,strong}，它将S划分为2个子集：{S1,S2},S1为wind属性取值为weak的样本子集，共有8个样本；S2为wind属性取值为strong的样本子集，共有6个样本；下面分别计算样本子集S1和S2的熵。

36 信息增益例题演示(续) 对样本子集S1，play ball=yes的有6个样本，play ball=no的有2个样本，则：

37 信息增益例题演示(续) 利用属性wind划分S后的熵为： 按属性wind划分数据集S所得的信息增益值为：

38 ID3算法伪代码 函数：DT(S,F) 输入：训练集数据S，训练集数据属性集合F 输出：ID3决策树
(1)if 样本S全部属于同一个类别C then (2) 创建一个叶结点，并标记类标号为C； (3) return； (4)else (5) 计算属性集F中每一个属性的信息增益，假定增益值最大的属性为A； (6) 创建结点，取属性A为该结点的决策属性； (7) for 结点属性A的每个可能的取值V do (8) 为该结点添加一个新的分支，假设SV为属性A取值为V的样本子集； (9) if 样本SV全部属于同一个类别C then (10) 为该分支添加一个叶结点，并标记类标号为C； (11) else (12) 递归调用DT(SV, F-{A})，为该分支创建子树； (13) end if (11) end for (12)end if

39 ID3建树算法演示 以weather数据集为例，讲解ID3的建立过程。 outlook temperature humidity wind
play ball sunny hot high weak no strong overcast yes rain mild cool normal

40 数据集的构成 数据集具有属性：outlook, temperature, humidity, wind.
outlook = { sunny, overcast, rain } temperature = {hot, mild, cool } humidity = { high, normal } wind = {weak, strong }

41 ID3建立决策树 首先计算总数据集S对所有属性的信息增益，寻找根节点的最佳分裂属性:
Gain(S, outlook) = 0.246 Gain(S, temperature) = 0.029 Gain(S, humidity) = 0.152 Gain(S, wind) = 0.049 显然，这里outlook属性具有最高信息增益值，因此将它选为根结点.

42 ID3建立决策树(续) 以outlook做为根结点，继续往下：
因为outlook有3个可能值,因此对根结点建立3个分支{sunny, overcast, rain}. 那么，哪个属性用来最佳划分根结点的Sunny分支？overcast分支？Rain分支？ outlook sunny overcast rain ?

43 ID3建立决策树(续) 首先对outlook的sunny分支建立子树。
找出数据集中outlook = sunny的样本子集Soutlook=sunny，然后依次计算剩下三个属性对该样本子集Ssunny划分后的信息增益： Gain(Ssunny, humidity) = 0.971 Gain(Ssunny, temperature) = 0.571 Gain(Ssunny, wind) = 0.371 outlook sunny overcast rain ? Humidity 显然humidity具有最高信息增益值，因此它被选为outlook结点下sunny分支下的决策结点。

44 ID3建立决策树(续) 采用同样的方法，依次对outlook的overcast分支、rain分支建立子树，最后得到一棵可以预测类标号未知的样本的决策树。

45 ID3决策树对未知样本进行预测 下面利用决策树对类标号未知的样本X进行预测： X={rain, hot, normal, weak, ?}

46 ID3算法总结 ID3算法是所有可能的决策树空间中一种自顶向下、贪婪的搜索方法。

47 ID3算法优缺点分析 优点： 缺点： 理论清晰，方法简单，学习能力较强。 (1)算法只能处理分类属性数据，无法处理连续型数据；
(2)算法对测试属性的每个取值相应产生一个分支，且划分相应的数据样本集,这样的划分会导致产生许多小的子集。随着子集被划分得越来越小，划分过程将会由于子集规模过小所造成的统计特征不充分而停止； (3)ID3算法中使用信息增益作为决策树节点属性选择的标准，由于信息增益在类别值多的属性上计算结果大于类别值少的属性上计算结果，这将导致决策树算法偏向选择具有较多分枝的属性，因而可能导致过度拟合。在极端的情况下，如果某个属性对于训练集中的每个元组都有唯一的一个值，则认为该属性是最好的，这是因为对于每个划分都只有一个元组(因此也是一类)。

48 C4.5分类算法 基于ID3算法中存在的不足，Quinlan于1993年对其做出改进，提出了改进的决策树分类算法C4.5，该算法继承了ID3算法的优点，并在以下几个方面对ID3算法进行了改进： (1)能够处理连续型属性数据和离散型属性数据； (2)能够处理具有缺失值的数据； (3)使用信息增益率作为决策树的属性选择标准； (4)对生成的树进行剪枝处理，以获取简略的决策树； (5)从决策树到规则的自动产生。

49 C4.5算法的概念描述 假定S为训练集，目标属性C具有m个可能的取值，C={C1,C2,…,Cm}，即训练集S的目标属性具有m个类标号值C1,C2,…,Cm，C4.5算法所涉及的概念描述如下： (1)假定训练集S中，Ci在所有样本中出现的频率为pi(i=1,2,3,…,m)，则该集合S所包含的信息熵为：

50 C4.5算法的概念描述(续) (2)设用属性A来划分S中的样本,计算属性A对集合S的划分熵值EntropyA(S)定义如下:
若属性A为离散型数据，并具有k个不同的取值,则属性A依据这k个不同取值将S划分为k个子集{S1,S2,…,Sk}，属性A划分S的信息熵为： 其中|Si|和|S|分别是Si和S中包含的样本个数。

51 C4.5算法的概念描述(续) 如果属性A为连续型数据，则按属性A的取值递增排序，将每对相邻值的中点看作可能的分裂点，对每个可能的分裂点，计算： 其中SL和SR分别对应于该分裂点划分的左右两部分子集，选择EntropyA(S)值最小的分裂点作为属性A的最佳分裂点，并以该最佳分裂点按属性A对集合S的划分熵值作为属性A划分S的熵值。

52 C4.5算法的概念描述(续) (3) C4.5以信息增益率作为选择标准，不仅考虑信息增益的大小程度，还兼顾为获得信息增益所付出的“代价”：
信息增益率定义为 这样如果某个属性有较多的分类取值，则它的信息熵会偏大，但信息增益率由于考虑了分裂信息而降低，进而消除了属性取值数目所带来的影响。

53 C4.5算法演示 以weather数据集为例，演示C4.5算法对该数据集进行训练，建立一棵决策树的过程，对未知样本进行预测。

54 Step1:计算所有属性划分数据集S所得的信息增益分别为(参考ID3例题演示):

55 Step2:计算各个属性的分裂信息和信息增益率
以outlook属性为例，取值为overcast的样本有4条，取值为rain的样本有5条，取值为sunny的样本有5条： 同理依次计算其它属性的信息增益率分别如下：

56 Step3:取值信息增益率最大的那个属性作为分裂结点，因此最初选择outlook属性作为决策树的根结点，产生3个分支，如下：

57 Step4:对根结点的不同取值的分支，递归调用以上方法，求子树，最后通过C4.5获得的决策树为：

58 C4.5对缺失数据的处理 由于决策树中节点的测试输出决定于单个属性的不同取值，当训练集或测试集中的某个样本数据的测试属性值未知，就无法得到当前节点的测试输出，因此ID3算法不允许训练集和测试集中存在缺失数据。 对数据缺失值的处理，通常有两种方法： 方法一：抛弃数据集中具有缺失值的数据。 当数据集中只有少量缺失值数据的情况下，可以抛弃具有缺失值的数据，但是当数据集中存在大量缺失值时不能采用这种方法。 方法二：以某种方式填充缺失的数据。 如以该属性中最常见值或平均值替代该缺失值，或者以与缺失值样本所对应的类标号属性值相同的样本中该缺失值属性的最常见值或平均值来代替。 在C4.5算法中采用概率的方法，为缺失值的每个可能值赋予一个概率，而不是简单地将最常见的值替代该缺失值。

59 C4.5算法伪代码 C4.5决策树的建立过程可以分为两个过程： 首先使用训练集数据依据C4.5树生长算法构建一棵完全生长的决策树
然后对树进行剪枝，最后得到一棵最优决策树。

60 C4.5决策树的生长阶段算法伪代码 函数名：CDT(S,F) 输入：训练集数据S，训练集数据属性集合F 输出：一棵未剪枝的C4.5决策树
(1)if 样本S全部属于同一个类别C then (2) 创建一个叶结点，并标记类标号为C； (3) return； (4)else (5) 计算属性集F中每一个属性的信息增益率，假定增益率值最大的属性为A； (6) 创建结点，取属性A为该结点的决策属性； (7) for 结点属性A的每个可能的取值V do (8) 为该结点添加一个新的分支, 假设SV为属性A取值为V的样本子集； (9) if 样本SV全部属于同一个类别C then (10) 为该分支添加一个叶结点，并标记为类标号为C； (11) else (12) 则递归调用CDT(SV ,F-{A})，为该分支创建子树； (13) end if (14) end for (15)end if

61 C4.5决策树的剪枝处理阶段算法伪代码 函数名：Prune(node) 输入：待剪枝子树node 输出：剪枝后的子树
(1)计算待剪子树node中叶节点的加权估计误差leafError； (2)if 待剪子树node是一个叶节点 then (3) return 叶节点误差； (4)else (5) 计算node的子树误差subtreeError； (6) 计算node的分支误差branchError为该节点中频率最大一个分支误差 (7) if leafError小于branchError和subtreeError then (8) 剪枝，设置该节点为叶节点； (9) error=leafError； (10) else if branchError小于leafError和subtreeError then (11) 剪枝，以该节点中频率最大那个分支替换该节点； (12) error=branchError; (13) else (14) 不剪枝 (15) error=subtreeError; (16) return error; (17) end if (18)end if

62 C4.5算法的优缺点 与其它分类算法相比，C4.5分类算法具有如下优点： 其缺点是： 产生的分类规则易于理解，准确率较高。
在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。 此外，C4.5只适合于能够驻留与内存的数据集，当训练集大得无法在内存容纳时程序无法运行。 为适应大规模数据集，在C4.5后出现有SLIQ和SPRINT等算法。

63 3.4.5 CART算法 CART(Classification and Regression Tree)算法，由美国斯坦福大学和加州大学伯克利分校的Breiman等人于1984年提出。 CART决策树采用的是二元递归划分方法，能够处理连续属性数据和标称属性作为预测变量和目标变量下的分类，当输出变量是标称属性数据时，所建立的决策树称为分类树(classification tree)，用于分类的预测。当输出变量为数值型变量时，所建立的决策树称为回归树(regression tree)，用于数值的预测。

64 3.4.5 CART算法 与C4.5相比，CART算法的主要差别体现在： (1)CART为二叉树，而C4.5可以为多叉树。
(3)CART使用Gini系数作为变量的不纯度量，而C4.5使用信息增益率。 (4)如果目标变量是标称的，并且具有两个以上的类别，则CART可能考虑将目标类别合并成两个超类别。 (5)如果目标变量是连续的，则CART算法找出一组基于树的回归方程来预测目标变量。 (6)对于缺失值的处理方法不同，CART采用代理测试(surrogate)来估计测试的输出值，而C4.5直接将其分配到该分支中概率最大的分类。 (7)对决策树的剪枝方法不同。

65 CART算法的基本概念 分类回归树的建树过程是对训练集的反复划分的过程，涉及如何从多个属性中选择当前最佳划分属性的问题。另外针对CART的分类树和回归树，它们的计算方法有所不同，数值型和分类型属性变量的计算法方法也存在差异。 下面介绍CART算法的两个基本概念： 属性选择标准 分类树与回归树的属性选择

66 属性选择标准 ID3使用信息增益作为属性选择标准，C4.5使用信息增益率作为属性选择标准。
CART算法使用Gini系数来度量对某个属性变量测试输出的两组取值的差异性，理想的分组应该尽量使两组中样本输出变量取值的差异性总和达到最小，即“纯度”最大，也就是使两组输出变量取值的差异性下降最快，“纯度”增加最快。 设t为分类回归树中的某个节点，称函数： 为Gini系数,k为当前属性下测试输出的类别数，p(j|t)为节点t中样本测试输出取类别j的概率。

67 属性选择标准(续) 设t为一个节点，ξ为该节点的一个属性分枝条件，该分枝条件将节点t中样本分别分到左分支SL和右分支SR中，称：
为在分枝条件ξ下节点t的差异性损失。其中，G(t)为划分前测试输出的Gini系数，|SR|和|SL|分别表示划分后左右分枝的样本个数。为使节点t尽可能的纯，我们需选择某个属性分枝条件ξ使该节点的差异性损失尽可能大。用ξ(t)表示所考虑的分枝条件ξ的全体，则选择分枝条件应为：

68 属性选择 分类树的属性选择 对于CART分类树的属性选择，针对属性类型为分类型和数值型，方法有所不同。
对于数值型属性，方法是将数据按升序排序，然后从小到大依次以相邻数值的中间值作为分隔，将样本分为两组，并计算所得组中样本测试输出取值的差异性。 理想的分组是使两组中样本测试输出取值的差异性总和达到最小，即“纯度”最大，也就是使两组输出变量取值的差异性下降最快，“纯度”增加最快。

69 属性选择 回归树的属性选择 回归树确定当前最佳分组变量的策略与分类树相同，主要不同在于度量节点测试输出值差异性的指标有所不同，采用方差作为指标，其定义为： 其中，t为节点，N为节点t所含的样本个数，yi(t)为节点t中测试输出变量值， 为节点t中测试输出变量的平均值。于是，差异性损失的度量指标为方差的减少量，其定义为： 其中，R(t)和N分别为分组前输出变量的方差和样本个数，R(tR)、NR和R(tL)、NL分别为分组后右子树的方差和样本量以及左子树的方差和样本量。使达到最大的属性变量为当前最佳划分属性变量。

70 CART算法描述 函数名：CART(S,F) 输入：样本集数据S，训练集数据属性集合F 输出：CART树
(1)if 样本S全部属于同一个类别C，then (2) 创建一个叶结点，并标记类标号为C； (3) return; (4)else (4) 计算属性集F中每一个属性划分的差异性损失，假定差异性损失最大的属性为A； (5) 创建结点，取属性A为该结点的决策属性； (6) 以属性A划分S得到S1和S2两个子集； (7) 递归调用CART(S1 ,F)； (8) 递归调用CART(S2 ,F)； (9)end

71 3.3 贝叶斯分类方法 贝叶斯分类方法是一种基于统计的学习方法。 是一种利用概率统计知识进行学习分类的方法。 主要算法有：
如：预测一个数据对象属于某个类别的概率。 如：计算邮件是垃圾邮件或合法邮件的概率，取概率大的为预测结果 主要算法有： 朴素贝叶斯分类算法 贝叶斯信念网络分类算法等。 朴素贝叶斯分类算法和贝叶斯信念网络分类算法都是建立在贝叶斯定理基础上的算法

72 3.3.1 贝叶斯定理 假定X为类标号未知的一个数据样本，H为样本X属于类别C的一个假设
分类问题就是计算概率P(H|X) 的问题，即给定观察样本X下假设H成立的概率有多大。 这里： P(H)表示假设H的先验概率(prior probability)。 P(X)表示样本数据X的先验概率。 P(H|X)表示在条件X下，假设H的后验概率(posterior probability)。 P(X|H)表示在给定假设H的前提条件下，样本X的后验概率

73 例: 假设数据集由三个属性构成： {年龄、收入、是否购买计算机} 样本X为：{35, 4000, ?} 假设H为：顾客将购买计算机。 则：
P(H)表示任意给定的顾客将购买计算机的概率，而不考虑年龄、收入其它信息。 P(X)表示数据集中，样本年龄为35，工资为4000的概率。 P(H|X)表示已知顾客的年龄和收入分别为35和4000，顾客购买计算机的概率。 P(X|H)表示已知顾客购买计算机，顾客年龄和收入属性值为35和4000的概率。

74 贝叶斯定理(续) 假设X,Y是一对随机变量，它们的： 贝叶斯定理是指X和Y的联合概率和条件概率满足如下关系：
联合概率P（X=x,Y=y）是指X取值x且Y取值y的概率 条件概率是指一随机变量在另一随机变量取值已知的情况下取某一个特定值的概率。 例如P(Y=y|X=x）是指在变量X取值x的情况下，变量Y取值y的概率)。 贝叶斯定理是指X和Y的联合概率和条件概率满足如下关系：

75 例：考虑A和B两队之间的足球比赛：假设过去的比赛中，65%的比赛A对取胜，35%的比赛B对取胜。A对胜的比赛中只有30%是在B对的主场，B对取胜的比赛中75%是在主场。

76 解答：根据贝叶斯定理,假定 已知： 随机变量X代表东道主，X取值范围为{A,B} 随机变量Y代表比赛的胜利者，取值范围为{A,B}。
A对取胜的概率为0.65，表示为：P(Y=A)=0.65， B对取胜的概率为0.35 ，表示为： P(Y=B)=0.35， B对取胜时作为东道主的概率是0.75，表示为： P(X=B|Y=B) = 0.75, A对取胜时B对作为东道主的概率是0.3,表示为: P(X=B|Y=A) = 0.3,

77 计算： 下一场比赛在B对主场，同时A对胜出的概率表示为： P(Y=A|X=B)
P(Y=A|X=B) = P(X=B|Y=A)*P(Y=A)/P(X=B) = (0.3*0.65)/0.4575=0.4262 下一场比赛在B对主场，同时B对胜出的概率表示为： P(Y=B|X=B) P(Y=B|X=B)=P(X=B|Y=B)*P(Y=B)/P(X=B) =(0.75*0.35)/0.4575=0.5737 根据计算结果，可以推断出，下一场最有可能是B对胜出。

78 P(X=B)的计算 ： P(X=B)= P(X=B,Y=A)+P(X=B,Y=B)
= P(Y=A|X=B)*P(X=B) + P(Y=B|X=B)*P(X=B) = P(X=B|Y=A)*P(Y=A) + P(X=B|Y=B)*P(Y=B) = 0.3* *0.35= =

79 3.3.2 朴素贝叶斯分类算法 朴素贝叶斯分类算法，即：Naïve Bayes
朴素贝叶斯分类算法利用贝叶斯定理来预测一个未知类别的样本属于各个类别的可能性，选择其中可能性最大的一个类别作为该样本的最终类别。

80 朴素贝叶斯分类算法(续) 设数据集为D，对应属性集：{A1,A2,…,An, C}
A1,A2,…,An是样本的属性变量，C是有m个取值C1,C2,..,Cm的类标号属性变量。 数据集D中的每个样本X可以表示为X={x1,x2,…,xn,Ci} 朴素贝叶斯分类算法的概念描述如下： 1)假定朴素贝叶斯分类器将未知样本X分配给类Ci，则：

81 根据贝叶斯定理: 由于P(X)对所有类为常数，最大化后验概率P(Ci|X)可转化为最大化先验概率P(X|Ci)P(Ci)。
类的先验概率P(Ci)可以用si/s来估计，其中si是数据集D中属于类Ci的样本个数，s是数据集D的样本总数 朴素贝叶斯假定一个属性值对给定类的影响独立于其他属性值，属性之间不存在依赖关系,这样：

82 从数据集中求概率 这里xk表示样本X在属性Ak下的取值。对于每个属性，考察该属性是分类的还是连续的。
①如果属性Ak是分类属性，则：P(xk|Ci)=sik/si，其中sik是D中属性Ak的值为xk的Ci类的样本个数，si是D中属于Ci类的样本个数。 ②如果属性Ak是连续值属性，则通常假定该连续值属性服从高斯分布，因而类别Ci下属性xk的类条件概率近似为： 即 的最大值点等价于 的最大值点： 这里的 和 分别是数据集中属于Ci类的样本属性Ak的值的平均值和标准差。

83 为对未知样本X分类，对每个类Ci，计算P(X|Ci)，样本X被指派到类别Ci中，当且仅当:

84 朴素贝叶斯分类算法的基本描述 函数名：NaiveBayes 输入：类标号未知的样本X={x1,x2,…,xn} 输出：未知样本X所属类别号
(1) for j=1 to m (2) 计算X属于每一个类别Cj的概率； (3) 计算训练集中每个类别Cj的概率P(Cj)； (4) 计算概率值； (5) end for (6) 选择计算概率值最大的Ci(1≤i≤m)作为类别输出。

85 朴素贝叶斯分类算法演示 对weather数据集使用朴素贝叶斯算法预测未知样本X={rainy,hot,normal,false,?}的play ball类标号属性的值。

86 该问题描述如下： 题目即求: 样本X={rainy, hot, normal, false, ?}
类标号play ball有2个取值{yes, no} 题目即求: 样本X在play为yes的概率P(play=yes|X) 和样本在play为no的概率P(play=no|X) 样本X将被预测为概率值大的那个类。

87 解： 根据朴素贝叶斯定理： 其中： 因此： P(play=yes|X)=1/3×2/9×2/3×2/3×9/14=0.0211
P(play=yes|X)=P(X|play=yes)*P(play=yes) =P(x1|play=yes)*P(x2|play=yes)*P(x3|play=yes)*P(x4|play=yes)*P(play=yes) 其中： P(x1|play=yes)=P(outlook=rainy|play=yes)=3/9 P(x2|play=yes)=P(temperature=hot|play=yes)=2/9 P(x3|play=yes)=P(humidity=normal|play=yes)=6/9 P(x4|play=yes)=P(windy=false|play=yes)=6/9 P(play=yes)=9/14 因此： P(play=yes|X)=1/3×2/9×2/3×2/3×9/14=0.0211

88 同样方法计算： P(play=no|X)=P(X|play=no)*P(play=no) =P(x1|play=no)*P(x2|play=no)*P(x3|play=no)*P(x4|play=no)*P(play=no) 其中： P(x1|play=no)=P(outlook=rainy|play=no)=2/5 P(x2|play=no)=P(temperature=hot|play=no)=2/5 P(x3|play=no)=P(humidity=normal|play=no)=1/5 P(x4|play=no)=P(windy=false|play=no)=2/5 P(play=no)=9/14 因此： P(play=no|X)=2/5×2/5×1/5×2/5×9/14=0.0082

89 根据计算结果： 所以： P(play=yes|X) > P(play=no|X)
样本X={rainy,hot,normal,false,?}的play类标号值应为yes.

90 朴素贝叶斯分类算法在计算概率的时候存在概率为0及概率值可能很小的情况，因此在某些情况下需要考虑条件概率的Laplace估计以及解决小概率相乘溢出问题。

91 1. 条件概率的Laplace估计 在后验概率的计算过程中，当有一个属性的条件概率等于0，则整个类的后验概率就等于0，简单地使用记录比例来估计类条件概率的方法显得太脆弱，尤其是当训练样本很少而属性数目很大的情况下。 一种更极端的情况是，当训练样例不能覆盖那么多的属性值时，我们可能无法分类某些测试记录。 例如：若P(outlook=overcast |play=no)为0而不是1/7,则具有属性集X=(outlook=overcast，temperature=hot，humidity=normal，wind=weak)的记录的类条件概率如下： 此时将导致无法计算获取记录X的类标号信息。

92 1. 条件概率的Laplace估计(续) 为避免这一问题，条件概率为零时一般采用Laplace估计来解决这个问题，Laplace估计定义如下： 其中n是类Yj中的实例总数，nc是类Yj的训练样例中取值为Xi的样例数，l是称为等价样本大小的参数，而p是用户指定的参数。如果没有训练集(即n=0)，则P(Xi|Yj)=p。因此p可以看作是在类Yj的记录中观察属性值Xi的先验概率。等价样本大小l决定先验概率p和观测概率nc/n之间的概率。 在前面的例子中，条件概率 P(outlook=overcast |play=no)=0.使用Laplace估计方法，l=5,p=1/5,则条件概率不再是0，而是P(outlook=overcast |play=no)=(0+5×1/5)/(5+5)=0.1。

93 2. 解决溢出问题 对于概率值 ，即使每一个乘积因子都不为零，但当n较大时也可能几乎为零，此时将难以区分不同类别。注意到以下两个表达式取极大值的条件相同： 为解决这一问题，将乘积的计算问题转化为加法计算问题，可以避免“溢出”。

94 朴素贝叶斯分类算法的优缺点 朴素贝叶斯分类算法的优点在于： 缺点： 容易实现 在大多数情况下所获得的结果比较好。
算法成立的前提是假设各属性之间互相独立。 当数据集满足这种独立性假设时，分类准确度较高。 而实际领域中，数据集可能并不完全满足独立性假设

95 3.4 K-最近邻分类方法 K-最近邻分类算法是一种基于实例的学习算法，它不需要先使用训练样本进行分类器的设计，而是直接用训练集对数据样本进行分类，确定其类别标号。

96 K-最近邻分类方法概述 基本思想: 如果它走路象鸭子，叫声象鸭子，则它可能是一个鸭子 训练集 测试集

97 K-最近邻算法的基本思想是： 对于未知类标号的样本，按照欧几里得距离找出它在训练集中的k个最近邻，将未知样本赋予k最近邻中出现次数最多的类别号。

98 K-最近邻分类算法的基本描述 令D为训练集，Z为测试集，K为最近邻数目，其中每个样本可以表示为(x,y)的形式，即 ，其中
表示样本的n个属性，y表示样本的类标号，则KNN分类算法的基本描述如下 算法名：KNN 输入：最近邻数目K ，训练集D，测试集Z 输出：对测试集Z中所有测试样本预测其类标号值 (1)for 每个测试样本 do (2) 计算z和每个训练样本 之间的距离 (3) 选择离z最近的k最近邻集合 (4) 返回 中样本的多数类的类标号 (5)end for

99 K-最近邻分类算法的基本描述(续) kNN算法根据得到的最近邻列表中样本的多数类进行分类，实现方法是通过投票进行多数表决得到最终类标号 ，其中： 其中 为类标号的所有可能取值， 是测试样本z的一个最近邻类标号， 是指示函数，如果其参数为真，则返回1，否则返回0。

100 kNN算法演示 对weather数据集，利用KNN算法，测试样本X=(rain, hot, normal, weak，?)的类标号属性，其中k取3。

101 kNN算法演示(续) Step2:取离样本X最近的三个近邻p5,p10,p13
Distance(X,p1)=2, Distance(X,p2)=3，Distance(X,p3)=2，Distance(X,p4)=2， Distance(X,p5)=1，Distance(X,p6)=2，Distance(X,p7)=3，Distance(X,p8)=3， Distance(X,p9)=2，Distance(X,p10)=1，Distance(X,p11)=3，Distance(X,p12)=1， Distance(X,p13)=1，Distance(X,p14)=3； Step2:取离样本X最近的三个近邻p5,p10,p13 Step3:因为三个最近邻对应的类标号都为yes,因此样本X的类标号被预测为yes。

102 KNN算法优缺点 优点： 缺点： 算法思想简单，易于实现。 最近邻分类对每个属性指定相同的权重。
而数据集中的不同属性可能需要赋予不同的权值； 由于K-NN存放所有的训练样本，直到有新的样本需要分类时才建立分类，因此当训练样本数量很大时，该学习算法的时间复杂度为n2。

103 3.5 神经网络分类方法 神经网络(Neural Network)是模拟人脑思维方式的数学模型，它是在现代生物学研究人脑组织成果的基础上提出的，用来模拟人类大脑神经网络的结构和行为。神经网络反映了人脑功能的基本特征，如并行信息处理、学习、联想、模式分类、记忆等。

104 典型神经网络模型 神经网络模型性能主要由以下因素决定： 目前神经网络模型的种类相当丰富，已有40余种神经网络模型。
(1)神经元(信息处理单元)的特性； (2)神经元之间相互连接的形式—拓扑结构； (3)为适应环境而改善性能的学习规则。 目前神经网络模型的种类相当丰富，已有40余种神经网络模型。 典型的有感知器模型、多层前向传播网络、BP模型、Hopfield网络、ART网络、SOM自组织网络、学习矢量量化(LVQ)网络、Blotzman机网络等。

105 感知器模型 感知器神经网络是一个具有单层计算神经元的神经网络，网络的传递函数是线性阈值单元。原始的感知器神经网络只有一个神经元，因此只能输出两个值，适合简单的模式分类问题。感知器模型图如下： 单层感知器可将外部输入分为两类。当感知器的输出为+1时，输入属于L1类，当感知器的输出为-1时，输入属于L2类，从而实现两类目标的识别。

106 感知器模型(续) 在多维空间，单层感知器进行模式识别的判决超平面由下式决定：
对于只有两个输入的判别边界是直线,选择合适的学习算法可训练出满意的 w1和w2，当它用于两类模式的分类时，相当于在高维样本空间中，用一个超平面将两类样本分开，即：w1x1+w2x2 +b=0

107 BP模型 BP模型也称反向传播模型，是一种用于前向多层的反向传播学习算法。
学习方法：可以对组成前向多层网络的各人工神经元之间的连接权值进行不断的修改，从而使该前向多层网络能够将输入信息变换成所期望的输出信息。 反向学习算法：在修改各人工神经元的连接权值时，所依据的是该网络的实际输出与其期望输出之差，将这一差值反向一层一层地向回传播，来决定连接权值的修改。 BP网络如图：

108 BP模型的基本描述 1)选择一组训练样例，每一个样例由输入信息和期望的输出结果两部分组成;
2)从训练样例集中取一样例，把输入信息输入到网络中; 3)分别计算经神经元处理后的各层节点的输出; 4)计算网络的实际输出和期望输出的误差; 5)从输出层反向计算到第一个隐含层，并按照某种能使误差向减小方向发展的原则，调整网络中各神经元的连接权值; 6)对训练样例集中的每一个样例重复3-5的步骤，直到对整个训练样例集的误差达到要求时为止。

109 BP模型优缺点 优点： 缺点： 理论基础牢固，推导过程严谨，物理概念清晰，通用性好等。所以，它是目前用来训练前向多层网络较好的算法。
1)学习算法的收敛速度慢； 2)网络中隐含节点个数的选取尚无理论上的指导； 3)从数学角度看，BP算法是一种梯度最速下降法，这就可能出现局部极小的问题。所以BP算法是不完备的。

110 3.6 支持向量机 支持向量机(Support Vector Machine)分类器的特点是能够同时最小化经验误差与最大化几何边缘区。因此支持向量机也被称为最大边缘区分类器。 支持向量机将向量映射到一个更高维的空间，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。平行超平面间的距离或差距越大，分类器的总误差越小。

111 支持向量机面临的问题 目前，用SVM构造分类器来处理海量数据面临以下两个困难： 1)SVM算法对大规模训练样本难以实施
由于SVM是借助二次规划来求解支持向量，而求解二次规划将涉及m阶矩阵的计算(m为样本的个数)，当m数目很大时该矩阵的存储和计算将耗费大量的机器内存和运算时间。 2)用SVM解决多分类问题存在困难 经典的支持向量机算法只支持二类分类问题，而实际应用中，一般要解决多类分类问题。可以通过多个二类支持向量机的集成来解决，主要有一对多集成模式、一对一集成模式和SVM决策树；再就是通过构造多个分类器的集成来解决。主要原理是克服SVM固有的缺点，结合其它算法的优势，解决多类问题的分类精度。

112 3.7 集成学习方法 集成学习法(Ensemble learning)通过将多个分类学习方法聚集在一起来提高分类准确率。
通常一个集成分类器的分类性能会好于单个分类器。集成学习法由训练数据构建一组基分类器(base classifier)，然后通过对每个基分类器的预测进行投票来进行分类。 在构建分类器的过程中，一般有两种集成方法： 一种是使用训练集的不同子集训练得到不同的基分类器。 另一种方法是使用同一个训练集的不同属性子集训练得到不同的基分类器。

113

114 集成学习方法的一般过程描述 集成学习方法的一般过程: (1) 令D表示原始训练数据集，k表示基分类器的个数，Z表示测试数据集
(2) for i=1 to k do (3) 由D创建训练集Di (4) 由Di创建基分类器Ci (5) end for (6) for 每一个测试样本do (7) C*(x)=Vote(C1(x),C2(x),…,Ck(x)) (8) end for

115 已有构建集成分类器的方法主要包括： 装袋(bagging) 提升(boosting) AdaBoost算法

116 1. 装袋(Bagging) 装袋又称自助聚集，是一种根据均匀概率分布从数据中重复抽样(有放回)的技术。
每个自助样本集都和原数据集一样大。由于抽样过程是有放回的，因此一些样本可能在同一个训练集中出现多次，而其它一些却可能被忽略。在每一个抽样生成的自助样本集上训练一个基分类器，对训练过的k个基分类器投票，将测试样本指派到得票最高的类。

117 装袋算法的基本描述 装袋算法 输入：大小为N的原始数据集D，自助样本集的数目k 输出：集成分类器C*(x)
(1) for i=1 to k do (2) 通过对D有放回抽样，生成一个大小为N的自助样本集Di (3) 在自助样本集体Di上训练一个基分类器Ci (4) end for (5) C*(x)= {如果参数为真，则 ，否则 }

118 装袋方法的特点 装袋通过降低基分类器的方差改善了泛化误差。 装袋的性能依赖于基分类器的稳定性。
如果基分类器是不稳定的，装袋有助于降低训练数据的随机波动导致的误差； 如果基分类器是稳定的，则集成分类器的误差主要是由基分类器的偏倚所引起的。 另外由于每一个样本被选中的概率相同，因此装袋并不侧重于训练数据集中的任何特定实例。因此对于噪声数据，装袋不太受过分拟合的影响。

119 2. 提升(Boosting) 提升是一个迭代的过程，用于自适应地改变训练样本的分布，使得基分类器聚焦在那些很难分的样本上。不像装袋，提升给每一个训练样本赋予一个权值，而且可以在每一轮提升过程结束时自动地调整权值。训练样本的权值可以用于以下方面： (1)可以用作抽样分布，从原始数据集中提取出自主样本集； (2)基分类器可以使用权值学习有利于高权值样本的模型；

120 3.AdaBoost算法 AdaBoost算法是对提升算法的一个具体实现。假定S表示样本数据集，Y表示类标号集，Y={-1, +1}。给定一个基分类器和一个训练集 ，其中 ，AdaBoost算法描述如下： 1)首先给所有的训练样本分配相同的权值，并指定第t轮提升的权值为Wt，通过调用基分类器，AdaBoost从训练集和Wt中产生一个弱学习器 。 2)然后使用训练样本来测试ht，并增加分类错误的样本的权重。这样就获得了一个更新的权重值Wt+1。 3)AdaBoost从训练集和Wt+1中通过再次调用基分类器产生另一个弱学习器。 4)这样反复执行T轮，最终的模型是由T个弱学习器基于权重的投票结果，这里每个弱学习器的权重是在训练阶段产生的。

121 AdaBoost算法伪代码 函数：AdaBoost(D, T) 输入：样本数据集D,学习提升轮数T 输出：集成分类器
初始化N个样本的权值 ， ， for t=1 to T do//对每一轮 (3) 根据权重Wt的分布，通过对D进行有放回抽样产生训练集Dt 在Dt上训练产生一个弱学习器(基分类器)ht 用ht对原训练集D中所有样本进行分类，并度量ht的误差et (6) if et>0.5 then (7) 重新将权重初始化为1/N，转步骤(3)重试 (8) end if (6) 决定ht的权重 (7) 更新权重分布 (8) end for //返回具有最大权重的类(其中sign()为符号函数) ，

122 AdaBoost算法伪代码(续) 基分类器ht的误差et的计算： 权重更新的计算：

123 AdaBoost算法演示 以下表一维数据集为例，分析AdaBoost算法是如何对该数据集进行分类的。

124 AdaBoost算法演示(续) 解答： Step1:首先初始化10个样本的权值为： Step2:第1轮提升过程：
根据权重W1,在数据集D上抽样产生训练集D1如下 在D1上训练产生一个基分类器h1，该分类器的最佳分裂点为k=0.75, x≤k, y=-1, x＞k, y=1。使用该基分类器对原数据集D进行分类. 分类结果？

125 AdaBoost算法演示(续) 分类结果为10个样本中有三个样本分类错误，7个样本分类正确，它们分别是分类正确的样本：{0.4,0.5,0.6,0.7,0.8,0.9,1}，分类错误的样本：{0.1,0.2,0.3}。 根据对原数据集D的分类结果，度量它的误差 ： 并计算h1的权重为：

126 AdaBoost算法演示(续) Step3:更新权重进入第2轮提升过程: 依次计算更新后权重w2(i)(i=1,2,…,10) 依据： 有：
于是：Z1=1.8265

127 AdaBoost算法演示(续) 更新后第二轮提升的权重分别为： 根据权重W2的分布，通过对D进行抽样产生训练集D2
在D2上训练产生基分类器h2. 该分类器的最佳分裂点为k=0.05, x≤k, y=-1, x＞k, y=1。使用该基分类器对原数据集D进行分类，分类结果为？

128 AdaBoost算法演示(续) 根据对原数据集D的分类结果，度量它的误差 ： 并计算h2的权重为 ：
分类结果为10个样本中有4个样本分类错误，6个样本分类正确，它们分别是分类正确的样本：{0.1，0.2，0.3，0.8,0.9,1}，分类错误的样本：{0.4,0.5,0.6,0.7}。 根据对原数据集D的分类结果，度量它的误差 ： 并计算h2的权重为 ：

129 AdaBoost算法演示(续) 根据算法计算更新后权重分别为： 计算Z2=0.6745 于是更新后第3轮提升的权重分别为：
Step4:更新权重进入第3轮提升过程： 根据算法计算更新后权重分别为： 计算Z2=0.6745 于是更新后第3轮提升的权重分别为： W3(1)=W3(2)=W3(3)=0.0285 W3(4)=W3(5)=W3(6)=W3(7)=0.228 W3(8)=W3(9)=W3(10)= 根据权重W3的分布，通过对D进行抽样产生训练集D3 如下：

130 AdaBoost算法演示(续) 根据对原数据集D的分类结果，度量它的误差 ： 并计算h2的权重为 ：
Step4:分类结果为10个样本中有4个样本分类错误，6个样本分类正确，它们分别是分类正确的样本：{0.1，0.2，0.3，0.8,0.9,1}，分类错误的样本：{0.4,0.5,0.6,0.7}。 根据对原数据集D的分类结果，度量它的误差 ： 并计算h2的权重为 ：

131 AdaBoost算法演示(续) 获取h3的误差: 计算h3的权重：
在D3上训练产生基分类器h3. 该分类器的最佳分裂点为k=0.3, x≤k, y=1, x＞k, y=-1。使用该基分类器对原数据集D进行分类，分类结果为10个样本中有3个样本分类错误，7个样本分类正确，它们分别是分类正确的样本：{0.1，0.2，0.3，0.4,0.5,0.6,0.7}，分类错误的样本：{0.8,0.9,1}。 获取h3的误差: 计算h3的权重：

132 AdaBoost算法演示(续) 下面以原始数据集中的x=0.1为例加以说明最后的集成分类的过程：
Step5:经过三轮学习提升后，得到每一轮弱学习器ht及其权重值at(t=1,2,3)。最后计算三轮学习得到的弱学习器h1,h2,h3的集成分类结果 下面以原始数据集中的x=0.1为例加以说明最后的集成分类的过程： 第1轮训练得到了弱学习器h1，它对x=0.1分类结果为-1，权重值为1.738；第2轮训练得到了弱学习器h2，它对x=0.1分类结果为1，权重值为2.7844；第3轮训练得到了弱学习器h3，它对x=0.1分类结果为1，权重值为 ； 这样，最后对样本x=0.1的集成分类结果为： 根据计算结果大于0，因此其分类结果为1 .

133 AdaBoost算法演示(续) 同样，对于其它样本的计算步骤类似，最后的结果如下表所示：

134 3.9 不平衡数据分类 所谓不平衡数据，是指在同一数据集中某些类的样本数远大于其它类的样本数，其中样本少的类为少数类(以下称为正类) ，样本多的类为多数类(以下称为负类)。 具有不平衡类分布的数据集出现在许多实际应用中，很多重要信息隐藏在少数类中。 找出数据中相应的最有价值部分(如识别网络安全中的入侵行为，银行交易中的欺诈行为或洗钱行为，邮件系统中的垃圾邮件，企业客户中的高风险客户与高价值客户等)，可能会给企业带来更多商业机会或让企业规避风险和危机，使企业避免或减少不必要的损失。

135 3.9 不平衡数据分类(续) 精度和召回率是评价不平衡数据分类模型的两个常用度量。
可以构造一个基线模型，它最大化其中一个度量而不管另一个。例如，将每一个记录都声明为正类的模型具有完美的召回率，但它的精度却很差；相反，将匹配训练集中任何一个正记录都指派为正类的模型具有很高的精度，但召回率很低。度量可以起到平衡两个度量的效果，高的度量值确保精度和召回率都比较高。

136 分类准确度 分类模型的性能常根据模型正确预测和错误预测的检验记录的百分比来进行评估。
方法是建立一个混合矩阵，根据混合矩阵来计算分类模型的分类准确率和分类差错率。

137 一个描述二元分类问题的混淆矩阵如表： 此时，分类准确率和分类差错率为： +  预测类别 实际类别 正确的正例(TP) 错误的负例(FN)
错误的正例(FP) 正确的负例(TN) 此时，分类准确率和分类差错率为：

138 其它度量指标 查准率(Precision)定义为正确分类的正例个数占分类为正例的样本个数的比例：
查全率(Recall)定义为正确分类的正例个数占实际正例个数的比例 ：

139 分类准确度度量的不足 通常分类算法寻找的是分类准确率高的分类模型。分类准确度在一般情况下已经满足分类器模型的比较。 但是，分类准确度：
①默认所有数据集都是平衡数据集，但很多数据集是不平衡的，即不同类的样本分布不平均。 ②默认所有的错误代价都是相同的，这在实际领域中往往不可行。

140 分类准确度度量的不足 考虑以上实际问题，除了可以使用分类准确度来度量分类器的性能外，可以采用ROC曲线分析方法，与分类准确度评估方法相比，ROC曲线分析方法具有以下优点： (1)充分利用了预测得到的概率值。 (2)给出不同类的不同分布情况差别，即当是不平衡数据时，不同的数据分布，将得到不同的分类结果，而准确率评估则默认所有的数据集都是平衡数据集。 (3)考虑了不同种类错误分类代价的不同。 (4)二类分类的Roc曲线通过斜率反映了正例和反例之间的重要关系，同时也反映出类的分布和代价之间的关系。 (5)可以使分类器的评估结果用曲线的形式更直观地展示在二维空间中。

141 ROC曲线的优点 与分类准确度评估方法相比，ROC曲线分析方法具有以下优点： 1) 充分利用了预测得到的概率值。
2) 给出不同类的不同分布情况差别，即当是不平衡数据时，不同的数据分布，将得到不同的分类结果，而准确率评估则默认所有的数据集都是平衡数据集。 3) 考虑了不同种类错误分类代价的不同。 4) 二类分类的ROC曲线通过斜率反映了正例和反例之间的重要关系，同时也反映出类的分布和代价之间的关系。 5) 可以使分类器的评估结果用曲线的形式更直观地展示在二维空间中。

142 3.9 分类模型的评价 分类模型性能评价指标 分类准确率 计算复杂度 可解释性 可伸缩性 稳定性 鲁棒性

143 分类模型的过分拟合 分类模型的误差大致分为两种，训练误差(training error)和泛化误差(generalization error)。 训练误差是在训练记录上错误预测分类样本的比例，泛化误差是模型在未知样本上的期望误差。 通常我们希望通过分类算法学习后建立的分类模型能够很好地拟合输入数据中类标号和属性集之间的联系，同时，还要能够正确地预测未知样本的类标号，就是分类准确率要高。所以，我们对分类算法的要求是，其建立的分类模型应该具有低训练误差和低泛化误差。 模型的过分拟合是指对训练数据拟合太好，即训练误差很低，但泛化误差很高，这将导致对分类模型未知记录分类的误差较高。

144 评估分类模型性能的方法 为了使分类结果更好地反映数据的分布特征，已经提出许多评估分类准确率的方法，评估准确率的常用技术包括：
保持、随机子抽样、交叉验证和自助法等。 它们都是基于给定数据的随机抽样划分来评估准确率的技术。

145 保持方法 保持(Hold Out)方法是我们目前为止讨论准确率时默认的方法。在这种方法中，给定数据随机地划分为两个独立的集合，作为训练集和检验集，其中训练集用于构造分类器，而测试机用于测试分类器的性能。 其执行步骤如下： (1)以不放回抽样方式把数据集分为两个相互独立的子集：训练集和测试集。通常情况下，指定三分之二的数据分配到训练集，其余三分之一分配到测试集。 (2)使用训练集来训练构建分类模型，用测试集来评估分类模型的分类准确率。

146 保持方法的局限性 第一，用于训练的被标记样本较少，因为要保留一部分记录用于检验，因此建立的模型不如使用所有被标记样本建立的模型好。
第二，模型可能高度依赖于训练集和检验集的构成。一方面，训练集越小，则模型的方差越大，另一方面，如果训练集太大，根据用较小的检验集估计的准确率又不太准确。 第三，训练集和检验集不再是互相独立的，因为训练集和测试集来源于同一个数据集，在一个自己种超出比例的类在另一个子集就低于比例，反之亦然。

147 随机子抽样 随机子抽样(Random Subsampling)方法可以看成是保持方法的多次迭代，并且每次都要把数据集分开，随机抽样形成测试集和训练集。其执行步骤如下： (1)以无放回抽样方式从数据集D中随机抽取样本；这些样本形成新的训练集D1，D中其余的样本形成测试集D2。通常D中的2/3数据作为D1，而剩下的1/3数据作为D2； (2)用D1来训练分类器，用D2来评估分类准确率； (3)步骤(1)(2)循环K次，K越大越好。总准确率估计取每次迭代准确率的平均值。 随机子抽样方法和保持方法有同样的问题，因为在训练阶段也没有利用尽可能多的数据。并且由于它没有控制每个记录用于训练和测试的次数，因此，有些样本用于训练可能比其它样本更加频繁。

148 k-折交叉验证 k-折交叉验证(k-fold Cross-Validation)方法的思想是，将初始数据集随机划分成k个互不相交的子集D1,D2,…,Dk，每个子集的大小大致相等，然后进行k次训练和检验过程： 第1次，使用子集D2,D3,…,Dk一起作为训练集来构建模型，并在D1子集上检验； 第2次，使用子集D1,D3,…,Dk一起作为训练集来构建模型，并在D2子集上检验； … … … … 在第i次迭代，使用子集Di检验，其余的划分子集一起用于训练模型； 如此下去，直到每个划分都用于一次检验。 k折交叉验证方法的一种特殊情况是令k=N（N为样本总数），这样每个检验集只有一个记录，这一方法被称为留一方法（leave-one-out）。 该方法的优点是使用尽可能多的训练记录，此外，检验集之间是互斥的，并且有效地覆盖了整个数据集。该方法的缺点是整个过程重复N次，计算上开销很大，此外，因为每个检验集只有一个记录，性能估计度量的方差偏高。

149 3.10 回归 回归是Frances Galton提出的一种统计方法。回归分析可以对预测变量和响应变量之间的联系建模。 在数据挖掘环境下：
预测变量是描述样本的感兴趣的属性，一般预测变量的值是已知的，响应变量是我们要预测的那个。 当响应变量和所有预测变量都是连续值时，回归分析是一个好的选择。许多问题可以用线性回归解决，而且很多问题可以通过对变量进行变换，将非线性问题转换为线性问题来处理。

150 3.10 回归(续) 线性回归 一元线性回归 多元线性回归 非线性回归 逻辑回归

151 一元线性回归 一元线性回归分析涉及到一个响应变量y和一个预测变量x，它是最简单的回归形式，并用x的线性函数对y建模。即： y=b+wx
其中y的方差假定为常数，b和w是回归系数，分别指定直线的y轴截距和斜率。回归系数b和w也可以看成是权重，则，上式可以等价表示为： y=w0+w1x 这些系数可以通过最小二乘方法求解，它将最佳拟合直线估计为最小化实际数据与直线的估计值的误差的直线。

152 设D是训练集，由预测变量x的值和他们的相关联的响应变量y的值组成。训练集包含m个形如(x1,y1), (x2, y2),…,(xm,ym)的数据点。回归系数可以用下式估计：
其中是x1,x2,…,xm的均值，而是y1,y2,…,ym的均值。系数w0和w1通常给出其它复杂的归回方程的很好的近似。

153 例： 下表中的数据为某商店的前10个月的月销售额情况，请使用线性回归方法对预测该商店11月份的销售额。 月份 销售额（万元） 1 13.5
2 15 3 15.5 4 5 17.5 6 18 7 19 8 19.5 9 21 10 23

154 从散布图看，数据基本上还是在一条线上。给定表中的数据，分别计算 和 ，然后代入W0和W1的公式 ：
做散点图： 月份 年薪(单位万元) 从散布图看，数据基本上还是在一条线上。给定表中的数据，分别计算 和 ，然后代入W0和W1的公式 ： 这样，最小二乘直线的方程估计为y=0.9697x ，使用该方程预测该商场第11个月的销售额为： y=0.9697* =23.034万元。

155 多元线性回归 多元线性回归是单元线性回归的扩展，涉及多个预测变量。它允许响应变量y用描述样本X的n个预测变量或属性A1,A2,…,An的线性函数建模。训练数据集包含形如(x1,x2,…,xn,y1),(x1,x2,…,xn,y2),…,(x1,x2,…,xn,yn)的数据 一个基于两个预测属性的多元线性回归模型的例子是： y=w0+w1x1+w2x2 其中x1和x2分别是X(x1,x2)中属性A1和A2的值。可以扩充上面介绍的最小二乘来求解W0,W1,W2,当然这个时候可以用统计软件来实现求解，如SPSS，SAS等。

156 非线性回归 对于有些模型，响应变量y对预测变量x不是线性的，如： 可以通过变换将非线性回归转为线性回归来处理 。
例如,上面的模型可以转为如下线性回归来分析：

157 逻辑回归 逻辑回归拓展了多元线性回归的思想，处理因变量y是二值的情形(为简单起见，我们通常用0和1对这些值进行编码)，自变量x1，x2……xm可以是分类变量、连续变量或者二者的混合类型。

158 3.11 本章小结 本章介绍了分类与回归算法中的经典算法，包括决策树分类方法（ID3、C4.5和CART算法）、贝叶斯分类方法、K-最近邻分类方法、神经网络分类方法、支持向量机分类方法、集成学习方法等。文中尽量对每个经典算法用详细的例子讲解来阐述算法的实现过程和原理。文中还对不平衡类问题以及分类模型的评价做了详细介绍。回归部分对线性回归、非线性回归以及逻辑回归做了详细介绍。

159 作业：