机器学习简明原理（D.docx

机器学习简明原理说明：本文整理自IBM大数据学习文档，原文作者：韩笑琳1. 关于机器学习的简介机器学习是从大量数据中学习出特定规律的算法。其中提到的规律有很多种，比如分类、聚类、回归、关联分析等。分类就是给定大量带标签的数据，计算出未知标签样本的标签取值。如年龄 40 岁以上、工科、研究生以上学历，这类人薪资水平是高收入；年龄 20-30 岁、文科、大专学历，这类人的薪资水平是低收入；现有一位 23 岁大专文科人士，求该人的薪资水平是哪类？根据分类建模，就可以知道这个人的薪资水平很可能是低收入。聚类是将大量不带标签的数据根据距离聚集成不同的簇，每一簇数据有共同的特征。如电信行业可以根据用户的月长途电话分钟数、上网时长、短信使用数、地理位置、月消费数，将所有用户聚集成有典型特征的簇，聚集出的某簇特征可能是月长途电话分钟数长、上网时间长、地理位置变化不大、月消费数目低，分析可得这类人极有可能是在校大学生，那么电信公司就可以针对这类特定人群制定有针对性的营销策略。回归是根据特征值、目标变量拟合出特征值与目标变量之间的函数关系，可用来估计特征值对应的目标变量的可能取值。举个简单的例子，某市今年某 100 平米的房子价格是 80 万，某 150 平米房子价格是 120 万，那么某 200 平米的房子价格的取值就可能是 200*0.8=160 万左右。关联分析是计算出大量数据之间的频繁项集合。如超市订单中有大量订单同时包含啤酒与尿布，这其中的频繁项就是啤酒和尿布，那么超市就可以针对这个规律对啤酒和尿布进行组合促销活动。分类算法主要包括K近邻、决策树、朴素贝叶斯、逻辑回归、支持向量机、AdaBoost等；回归主要包括线性回归、岭回归、lasso、树回归等；聚类主要包括 K-Means 以及它的各种变形算法；关联分析主要包括 Apriori、FP-growth 等算法。支持向量机即 support vector machine(简称 SVM)，是机器学习领域经典的分类算法。2. 关于 SVM 的简介支持向量是距离分类超平面近的那些点，SVM的思想就是使得支持向量到分类超平面的间隔最大化。出发点很容易理解，距离分类超平面近的那些点到该超平面的间隔最大化代表了该超平面对两类数据的区分度强，不容易出现错分的情况。如图 1所示，支持向量到超平面1的间隔大于支持向量到超平面2的间隔，因此超平面1优于超平面2。图 1 两个超平面示例SVM 可以很好得解决二分类问题，对于多分类情况，就需要对模型进行改动。如 one-versus-rest 法，这种方法每次选择一个类别作为正样本，剩下其他类别作为负样本，假设一共有3个类别，这样相当于训练出了3个不同的SVM。然后将测试数据分别带入3个SVM模型中，得到的3个结果中的最大值则为最终的分类结果。支持向量到分类超平面的间隔最大化的思路很完美，按这种思路得到的模型理论上是准确度最高的一种模型。但是使用过SVM的朋友都知道，调用SVM算法的测试准确度并不一定都很高。这其中有很多原因，比如数据预处理的效果、训练集的大小、特征值的选择、参数设置以及核函数的选择等因素。任何模型都是优点与缺点并存的。SVM的优点是：1. 可以解决线性不可分的情况。如图 2所示，两类数据点根本无法用超平面分隔开;2. 计算复杂度仅取决于少量支持向量，对于数据量大的数据集计算复杂度低。SVM 的缺点是：1. 经典的 SVM 算法仅支持二分类，对于多分类问题需要改动模型;2. 不支持类别型数据，需在预处理阶段将类别型数据转换成离散型数据。类别型数据即男、 女这类由字符串表示某类信息的数据，需将这类数据转换成离散型数据如 1、2。图 2 线性不可分问题3. SVM 基本原理SVM原理分为软间隔最大化、拉格朗日对偶、最优化问题求解、核函数、序列最小优化SMO等部分。虽然这些名词看起来很晦涩，但是深入探索后就会发现其中的思想并没有那么复杂。3.1. 软间隔最大化SVM的核心思路是最大化支持向量到分隔超平面的间隔。后面所有的推导都是以最大化此间隔为核心思想展开。一般的机器学习问题都是先得到模型的目标函数和约束条件，然后在约束条件下对目标函数求得最优解。因此，我们下面首先需要推导出SVM模型的目标函数和约束条件。既然要最大化间隔，那么回顾下点x到超平面(w,b)的距离公式：其中超平面的公式为：由此可推出点 x 到超平面(w,b)的几何间隔为： 其中 xi代表第i条数据，yi代表第i条数据对应的目标变量的取值，取值有+1 和-1 两种。所以当第 i条数据被正确分类时，y 取值和 w*x+b 取值的正负一致，几何间隔为正；当被错误分类时，y 取值和 w*x+b 取值的正负相反，几何间隔为负。图 3 样本数关于w*x + b的取值符号定义几何间隔中最小的为：由此，可以得到间隔最大化问题的目标函数：并遵循如下约束条件： 做如下变换：则目标函数转换为：相应的约束条件变为： 做如下变换：可得目标函数和约束条件变为： 由于 w, b 成倍数变化并不会影响超平面的公式，所以：此时得到最终的间隔最大化的目标函数和约束条件如下：但是，到这里并没有真正得结束。考虑到现实生活中的真实数据，存在一些特异点即 outliers，这些数据点并不满足上面推导出的约束条件，如图 4所示，图中点 A 就是 outlier 特异点。图 4 Outlier特异点为了解决这种问题，对每个样本点引进一个松弛变量，使得约束条件变为：这样给 outlier 的约束条件加上一个变量，使其可以满足大于等于 1 的条件。则相应的目标变量变为：其中 C 为惩罚参数，它的目的是使得目标变量最小即几何间隔最大，且使得松弛变量最小化。加入松弛变量的目标函数就是软间隔最大化。3.2. 拉格朗日对偶对于凸二次优化问题，通过引入拉格朗日乘子，将目标函数和约束条件整合到拉格朗日函数中，这样能方便求解最值问题。那么，对每个不等式约束引入拉格朗日乘子，得到拉格朗日函数如下：分析可知：则原最优化问题转换成： 由于原最优化问题直接求解很困难，利用拉格朗日对偶性，可通过求解原最优化问题的对偶问题得到原问题的最优解。原最优化问题的对偶问题为：3.3. 最优化问题求解到此为止，已经将目标函数和约束条件转换成了极大极小化拉格朗日函数的问题了。首先求解关于拉格朗日函数的极小化问题。对三个变量分别求偏导得： 将以上三式带入拉格朗日函数中得：那么极大极小化拉格朗日函数转换成：为求解方便，将极大转换成极小得： 3.4. 核函数对于线性不可分问题，如图 2所示，这类问题是无法用超平面划分正负样本数据的。倘若能将超平面换成超曲面，则可以将正负样本正确分类，如图 5所示。图 5 超曲面分离正负样本我们知道曲面的公式是：映射到新坐标如下：可将超曲面在新坐标下表示成超平面：也就是将在二维空间(x1,x2)下线性不可分的问题转换成了在五维空间(z1,z2,z3,z4,z5)下线性可分的问题。得映射后新坐标下的内积：有一核函数如下：可知 何为核函数？核函数在低维空间中完成了映射到高维空间后的内积运算。这点非常有用，利用核函数，无需先将变量一一映射到高维空间再计算内积，而是简单得在低维空间中利用核函数完成这一操作。为什么说不用一一映射到高维空间很有用呢？原因就在于首先我们无法针对每种情况提供精确的映射函数，再者对于需要映射到无穷维的情况显然无法一一映射完成。那么为什么是映射到高维后的内积运算呢？这是因为在上节中我们得到了如下目标函数： 正是因为该目标函数中包含自变量的内积运算，而映射到高维空间后的内积运算又恰好可以通过核函数在低维空间中直接求得，故而有了核函数的由来。较常用的核函数是高斯核，高斯核可以将低维空间映射到无穷维。运用核函数后，最优化问题的目标函数和约束条件变为： 3.5. 序列最小优化 (Sequential minimal optimization)到目前为止，优化问题已经转化成了一个包含 N 个 alpha 自变量的目标变量和两个约束条件。由于目标变量中自变量 alpha 有 N 个，为了便与求解，每次选出一对自变量 alpha，然后求目标函数关于其中一个 alpha 的偏导，这样就可以得到这一对 alpha 的新值。给这一对 alpha 赋上新值，然后不断重复选出下一对 alpha 并执行上述操作，直到达到最大迭代数或没有任何自变量 alpha 再发生变化为止，这就是 SMO 的基本思想。说直白些，SMO 就是在约束条件下对目标函数的优化求解算法。为何不能每次只选一个自变量进行优化？那是因为只选一个自变量 alpha 的话，会违反第一个约束条件，即所有 alpha 和 y 值乘积的和等于 0。下面是详细的 SMO 过程。假设选出了两个自变量分别是 alpha1 和 alpha2，除了这两个自变量之外的其他自变量保持固定，则目标变量和约束条件转化为： 将约束条件中的 alpha1 用 alpha2 表示，并代入目标函数中，则将目标函数转化成只包含 alpha2 的目标函数，让该目标函数对 alpha2 的偏导等于 0： 可求得 alpha2 未经修剪的值： 之所以说 alpha2 是未经修剪的值是因为所有 alpha 都必须满足大于等于 0 且小于等于 C 的约束条件，用此约束条件将 alpha2 进行修剪，修剪过程如下： 由此得： 分两种情况讨论：情况 1.当 y1 等于 y2 时，有： 情况 2.当 y1 不等于 y2 时，有：修剪后，可得 alpha2 的取值如下：由 alpha2 和 alpha1 的关系，可得：在完成 alpha1 和 alpha2 的一轮更新后，需要同时更新 b 的值，当 alpha1 更新后的值满足 0alpha1C 时，由 KKT 条件得：由于篇幅有限，在此就不把推导过程一一列举，可得：同样的道理，当 alpha2 更新后的值满足 0alpha1 牛奶，该规则的置信度是 0.9，意味着在所有买了鸡蛋和面包的客户中，有 90%的客户还买了牛奶。关联规则可以用来发现很多有趣的规律。这其中需要先阐明两个概念：支持度和置信度。4.2.1. 支持度 Support支持度指某频繁项集在整个数据集中的比例。假设数据集有 10 条记录，包含鸡蛋, 面包的有 5 条记录，那么鸡蛋, 面包的支持度就是 5/10 = 0.5。4.2.2. 置信度 Confidence置信度是针对某个关联规则定义的。有关联规则如鸡蛋, 面包 - 牛奶，它的置信度计算公式为鸡蛋, 面包, 牛奶的支持度/鸡蛋, 面包的支持度。假设鸡蛋, 面包, 牛奶的支持度为 0.45，鸡蛋, 面包的支持度为 0.5，则鸡蛋, 面包 - 牛奶的置信度为 0.45 / 0.5 = 0.9。关联规则用于发现 if - then 这样的规则，并可以给出这条规则的可信度（即置信度）。现实场景中可以用来发现很多规律，下面举个例子。在信息安全领域，需要根据已有流量数据制定规则，来判断是否触发安全报警。如规则数据包大，多个ip地址同时发送数据 - 异常，该规则的置信度为 0.85。这条规则表示，当流量数据包大，并有多个ip地址同时向目标ip发送数据时，则有 85%的概率存在异常，需要触发报警。4.3. 频繁项集挖掘原理频繁项集挖掘分为构建 FP 树，和从 FP 树中挖掘频繁项集两步。本节用如下表所示的数据集作为例子展开，该示例数据集共四条数据。表格 1 示例数据集数据集a,b,cc,d,b,ad,e,ab,a4.3.1. 构建 FP 树构建 FP 树时，首先统计数据集中各个元素出现的频数，将频数小于最小支持度的元素删除，然后将数据集中的各条记录按出现频数排序，剩下的这些元素称为频繁项；接着，用更新后的数据集中的每条记录构建 FP 树，同时更新头指针表。头指针表包含所有频繁项及它们的频数，还有每个频繁项指向下一个相同元素的指针，该指针主要在挖掘 FP 树时使用。下面用上文提到的数据集展开说明，假设最小支持度为 2。首先，统计数据集中各元素出现的次数，得 a 出现 4 次, b 出现 3 次, c 出现 2 次, d 出现 2 次, e 出现 1 次。接着，将出现次数小于最小支持度 2 的元素（即 e）在数据集中删除，并将数据集按出现次数由高到低排序，得表格 2。表格 2 示例数据集数据集a,b,ca,b,c,da,da,b然后，用更新后的数据集中的记录创建 FP 树，并同时更新头指针表。创建 FP 树时，当待添加的记录与 FP 树中的路径相同，则只需更新元素对应的频数；如果待添加的记录与 FP 树存在不一致，则在不一致的地方分叉，创建新的结点。如图 6图 9所示。注意，FP 树的根节点是 null。图 6 向FP树添加第一条记录 a,b,c 图 7向FP树添加第二条记录 a,b,c,d 图 8向FP树添加第三条记录 a ,d 图 9向FP树添加第四条记录 a ,b 4.3.2. 挖掘频繁项集得到 FP 树后，需要对每一个频繁项，逐个挖掘频繁项集。具体过程为：首先获得频繁项的前缀路径，然后将前缀路径作为新的数据集，以此构建前缀路径的条件 FP 树。然后对条件 FP 树中的每个频繁项，获得前缀路径并以此构建新的条件 FP 树。不断迭代，直到条件 FP 树中只包含一个频繁项为止。下面以元素 c 为例，从上文图 9创建好的 FP 树中挖掘频繁项集。首先，获得以 c 元素的前缀路径a:2,b:2，注意此处 a 和 b 的频数为 2 是因为 c 的频数为 2，所以与 c 共同出现的 a 和 b 的频数就都为 2。接着，创建条件 FP 树，具体的创建过程和上一节创建 FP 树的过程一样，如图 10所示。图 10 c元素的前缀路径构成的条件 FP 树注意此时头指针表中包含两个元素，所以对每个元素，需要获得前缀路径，并将前缀路径创建成条件 FP 树，直到条件 FP 树中只包含一个元素时返回。1. 对元素 a，获得前缀路径为 ，则频繁项集返回c,a;2. 对元素 b，获得前缀路径a，则将前缀路径创建成条件 FP 树，如图 11所示。注意此时条件 FP 树中只包含一个元素，故返回频繁项集c,b,a。由于元素 b 也是频繁项，所以c,b也是频繁项集。再加上c本身就是频繁项集，所以 c 对应的频繁项集有：c c,a c,b c,b,a。图 11 b元素的前缀路径构成的条件FP树将其他元素 a,b,d 同样按照上述对 c 的操作，得到表格 3所示频繁项集。表格 3 元素a,b,c,d对应的频繁项集元素频繁项集a a b b b,a c c c,a c,b c,b,a d d d,a 4.4. 关联规则挖掘原理关联规则挖掘首先需要对上文得到的频繁项集构建所有可能的规则，然后对每条规则逐个计算置信度，输出置信度大于最小置信度的所有规则。以频繁项集a,b,c为例，构建所有可能的规则：b,c - a, a,c - b,a,b - c,c - a,b,b - a,c,a - b,c。对每条规则计算置信度后，输出满足要求的规则即可。5. NaiveBayes基本原理朴素贝叶斯模型主要用来分类，但是与 SVM 模型不同的的是，朴素贝叶斯模型不需要针对目标变量建立模型，而是借助贝叶斯公式计算样本属于各个类别的概率，然后取概率值大的类别作为分类类别。之所以称之为朴素，是因为朴素贝叶斯模型假设各属性之间是条件独立的，该假设极大得简化了运算，使得朴素贝叶斯模型变得非常简单。朴素贝叶斯模型主要应用在文本分类方面。这里需要用到向量空间模型，即将文本转换成词向量。词向量的每一项是该词出现的频数。在朴素贝叶斯中会将频数进一步转换成频率。这样就完成了文本到数值上的转化，方便后期计算条件概率和先验概率。朴素贝叶斯模型也有它的优缺点，优点是模型简单，计算快；缺点是依赖于属性之间条件独立这一假设，但是现实场景下很多情况并不满足这一假设，使得朴素贝叶斯的准确率受到影响。这种情况需要考虑半朴素贝叶斯，即放松属性之间条件独立这一假设，一定程度上考虑属性之间的依赖关系。由于篇幅有限，对半朴素贝叶斯感兴趣的话可自行参照文末参考资源学习，本文重点介绍朴素贝叶斯的原理和实现。5.1. 朴素贝叶斯原理朴素贝叶斯模型主要利用贝叶斯公式进行展开。贝叶斯公式如下：公式中 P(C|X)表示 X 属于类别 C 的概率，P(X|C)表示类别 C 中 X 出现的概率，P(C)表示类别 C 出现的概率。其中 P(C)称为先验概率，P(X|C)是条件概率，P(C|X)称为后验概率，将后验概率最大的类作为 X 的类别输出。假设有 C0 和 C1 两个类，由于 P(X)都是一样的，所以不需要考虑 P(X),只需考虑如下：1. 如果P(X|C0) *P(C0) P(X|C1) *P(C1)，则 P(C0|X) P(C1|X)，可得 X 属于 C0 类；2. 如果P(X|C0) *P(C0) P(X|C1) *P(C1)，则 P(C0|X) log(P(X|C1) *P(C1) )，则 P(C0|X) P(C1|X)，可得 X 属于 C0 类；如果 log(P(X|C0) *P(C0) ) log(P(X|C1) *P(C1) )，则 P(C0|X) -2.84, 所以 log(P(X|C1) *P(C1) ) log(P(X|C0) *P(C0) ), 即 P(C1|X) P(C0|X)，可得测试文本book, campus, study属于类别 1。6. 决策树基本原理决策树算法又分很多种，常用的有ID3，C4.5 和 CART 决策树。其中ID3和C4.5决策树更倾向于处理类别型的离散属性值，对于连续型属性值，则需要额外利用连续属性离散化技术将其划分成离散型属性值。而CART决策树，即分类回归树，直接支持连续型属性值。由于篇幅限制CART树会放在下一篇文章进行介绍，本文主要详细介绍 ID3 和 C4.5 决策树。决策树利用了树型结构进行决策，是经典的 if-then 结构。叶节点存储类别，内部节点代表特征或属性。注意本文中提到的特征和属性是同一个概念。为了让读者有一个感性的认识，请看图 12所示决策树。图 12 决策树示例图1所示决策树用来将数据分为两类，是苹果和非苹果。如图中所示，圆的和红的，就是苹果。不圆的不是苹果。圆的但不红的不是苹果。本文将着重介绍ID3和C4.5两种决策树。决策树需要选择最优特征划分数据集。这两种决策树的不同之处是划分数据集的最优特征选择方法不同。用最优特征划分数据会使得数据集趋于更纯，即数据集的类别数更单一，这样的数据会更有序。衡量数据的混乱程度就必须提到信息和信息熵的概念。待分类的事物可能划分在多个类别中，则符号 Xi 的信息是:可知P(Xi) 越大，则 I(Xi) 越小，即Xi的概率越大，则Xi包含的信息越少。我们都知道物理中的熵用来衡量混乱程度，熵越大说明越混乱，熵越小说明越单一。同样，信息熵用来衡量信息中的混乱程度。用所有类别所有可能值包含的信息期望值表示信息熵，计算方法如下：ID3 决策树利用了信息增益来选择最优特征，用这种方法选择的特征是使得信息熵增益最大的特征。而 C4.5决策树利用了信息增益比来选择最优特征。用这种方法选择的特征是使得信息增益比最大的特征。为什么要提出信息增益比呢？这是因为只考虑信息增益来划分数据集是有缺陷的。这种缺陷体现在信息增益对选择属性取值多的特征更有利。因为按属性取值多的特征划分数据集后，划分后的各个子数据集的类别更单一，即更趋于有序，这就使得划分后的信息熵更小，那么信息增益就会更大。信息增益比可以很好的解决这个问题。信息增益比通过引入类似惩罚因子的概念，对属性取值多的特征会有一定惩罚。6.1. 决策树原理6.1.1. 选择最优特征决策树通过不断选择最优特征划分数据集，对划分后的子数据集不断迭代得选择最优特征划分，直到所有的数据集属于同一个类别，或者没有特征可以选择为止。选择最优特征的算法有很多种，ID3 决策树用信息增益选择最优特征，C4.5 决策树用信息增益比选择最优特征。6.1.2. 信息增益-用于ID3决策树信息增益，顾名思义就是原数据集的信息熵比划分后数据集的信息熵大的程度。信息增益越大，说明划分后的数据集信息熵更小，即该数据集类别更趋于一致。特征 A 对数据集 D 的信息增益 g(D,A)为 D 的信息熵与按特征 A 进行划分后 D 的信息熵之差，即其中， 6.1.3. 信息增益比 用于 C4.5 决策树信息增益比为了避免倾向于选择属性值多的特征作为最优特征这个问题，在信息增益的基础上引入了类似惩罚因子的概念。特征 A 对数据集 D 的信息增益比gg(D,A)为信息增益 g(D,A) 与数据集 D 关于特征 A 的取值的熵 HA(D) 的比值，即其中,其中，n 是特征 A 取值的个数。HA(D) 就类似惩罚因子，对于属性值多的特征，虽然信息增益 g(D,A) 会比较大，但是数据集 D 关于特征 A 的取值的熵 HA(D) 会比较大，因而两者的比值信息增益比 gg(D,A) 会比较小。除了可以使用信息增益和信息增益比来选择最优划分特征之外，基尼指数也可以用来实现这个目的。基尼指数主要用于 CART 树(即分类回归树)的分类树中的特征选择。关于基尼指数的详细内容会在下一篇文章介绍。6.2. 用 ID3 决策树进行分类本节主要介绍用 ID3 决策树进行分类。为了便于理解，用表1所示数据集进行详细说明。利用 C4.5 决策树进行分类的过程会在下节介绍。表格 8 示例数据集圆的红的分类1111000100001006.2.1. ID3决策树选择最优特征表格 8数据集的信息熵为:-1/5 * log(1/5) - 4/5 * log(4/5) = 0.2171. 按特征圆的划分数据集，则信息熵为：3/5 * H(D1) + 2/5 * H(D0)= 3/5 * -1/3 * log(1/3) 2/3 * log(2/3) + 2/5 * -2/2 * log(2/2)= 0.166则信息增益为：0.217 0.166 = 0.0512. 按特征红的划分数据集，则信息熵为：2/5 * H(D1) + 3/5 * H(D0)= 2/5 * -1/2 * log(1/2) 1/2 * log(1/2) + 3/5 * -3/3 * log(3/3)= 0.120则信息增益为：0.217 0.120 =0.097综上所述，由于按特征红的比按特征圆的划分的信息增益大，所以特征红的为最优划分特征。6.2.2. 按最优特征划分数据集按特征红的划分数据集后，有两种情况，第一种为如果是红的:0,则分类:0; 第二种为如果是红的:1, 则得到如下数据子集 圆的:1,分类：1; 圆的:0, 分类:0接下来需要对数据子集圆的:1,分类：1; 圆的:0, 分类:0继续划分。由于剩下一个特征，故按特征圆的划分数据子集。划分后，如果是圆的:1，则分类:1；如果是圆的:0, 则分类:0。返回的决策树用字典表示为：红的: 0: 类别0, 1: 圆的: 0: 类别0, 1: 类别16.3. 用 C4.5 决策树进行分类为了让读者对 ID3 和 C4.5 决策树的不同之处有更好的理解，本节介绍用 C4.5 决策树进行分类。为了便于理解，仍然使用表格 8所示数据集进行说明。6.3.1. C4.5 决策树选择最优特征表格 8数据集的信息熵为:-1/5 * log(1/5) - 4/5 * log(4/5) = 0.2171. 按特征圆的划分数据集，则信息熵为：3/5 * H(D1) + 2/5 * H(D0)= 3/5 * -1/3 * log(1/3) 2/3 * log(2/3) + 2/5 * -2/2 * log(2/2)= 0.166则信息增益为：0.217 0.166 = 0.051数据集关于特征圆的的取值的熵为:-3/5 * log(3/5) 2/5 * log(2/5) = 0.29则信息增益比为0.051 / 0.29 = 0.1762. 按特征红的划分数据集，则信息熵为：2/5 * H(D1) + 3/5 * H(D0)= 2/5 * -1/2 * log(1/2) 1/2 * log(1/2) + 3/5 * -3/3*log(3/3)= 0.120则信息增益为：0.217 0.120 =0.097数据集关于特征红的的取值的熵为：-2/5 * log(2/5) 3/5 * log(3/5) = 0.29则信息增益比为 0.097 / 0.29 = 0.334综上所述，由于按特征红的比按特征圆的划分的信息增益比大，所以特征红的为最优划分特征。6.3.2. 按最优特征划分数据集C4.5 决策树按最优特征划分数据集方法与上节 ID3 决策树方法相同。7. 分类回归树基本原理在上节中，主要介绍了 ID3 和 C4.5 决策树。它们利用信息增益和信息增益比划分数据集。但是这两种决策树是有缺陷的，即按某特征划分后，该特征将不会在后面的划分中出现。这就导致了划分过于迅速，从而影响分类结果。在这篇文章中将要介绍的CART（Classification And Regression Tree）树，即分类回归树利用二分策略，有效地避免了划分过于迅速这一问题。而且二分策略可以直接处理连续型属性值。CART树（分类回归树）分为分类树和回归树。顾名思义，分类树用于处理分类问题；回归树用来处理回归问题。我们知道分类和回归是机器学习领域两个重要的方向。分类问题输出特征向量对应的分类结果，回归问题输出特征向量对应的预测值。分类树和 ID3、C4.5决策树相似，都用来处理分类问题。不同之处是划分方法。分类树利用基尼指数进行二分。如图 13所示就是一个分类树。图 13 分类树示例回归树用来处理回归问题。回归将已知数据进行拟合，对于目标变量未知的数据可以预测目标变量的值。如图 14所示就是一个回归树，其中 s 是切分点，x 是特征，y 是目标变量。可以看出图 14利用切分点s将特征空间进行划分，y是在划分单元上的输出值。回归树的关键是如何选择切分点、如何利用切分点划分数据集、如何预测y的取值。图 14 回归树示例7.1. CART 树原理7.1.1. 分类树二分分类树利用二分划分数据。将特征值等于切分点值的数据划分为左子树，将特征值不等于切分点值的数据划分为右子树。基尼指数：同信息增益、信息增益比作用类似，不过基尼指数相对更快假设有 N 个类，样本属于第 n 类的概率为Pn，则基尼指数为：若数据集按特征A取值是否等于切分点值划分为D1和D2两部分，则在特征A下，集合D的基尼指数为：7.1.2. 回归树二分回归树也利用二分划分数据。与分类树不同的是，回归树将特征值大于切分点值的数据划分为左子树，将特征值小于等于切分点值的数据划分为右子树。平方误差不同于分类树，回归树用平方误差选择切分点。若数据集按特征取值是否大于切分点值划分为两部分，则在特征A下，集合D的平方误差为：7.2. 用 CART 树进行分类和回归本节主要用示例数据详细说明如何用 CART 树进行分类和回归。7.2.1. 分类树表格 9 示例数据集圆的红的分类111100010000100选择最优特征按特征圆的 = 1 划分数据集，则Gini为：3/5 * Gini(D1) + 2/5 * Gini(D0)= 3/5 * 1/3 * 2/3 + 2/3 * 1/3 + 2/5 * 0= 0.266按特征红的 = 1 划分数据集，则Gini为：2/5 * Gini(D1) + 3/5 * Gini(D0)= 2/5 * 1/2 * 1/2 + 1/2 * 1/2 + 3/5 * 0= 0.2综上所述，由于按特征红的比特征圆的划分的基尼指数小，所以特征红的 = 1 为切分点。按最优特征划分数据集按特征红的划分数据集后，有两种情况，第一种为如果是红的:0,则分类:0; 第二种为如果是红的:1, 则有如下数据子集 圆的:1,分类：1; 圆的:0, 分类:0接下来需要对数据子集圆的:1,分类：1; 圆的:0, 分类:0继续划分。由于剩下一个特征，故按特征圆的划分数据集。划分后，如果是圆的:1，则分类:1；如果是圆的:0, 则分类:0。返回的决策树为：红的: 0: 类别 0, 1: 圆的: 0: 类别 0, 1: 类别 17.2.2. 回归树表格 10 示例数据集面积/平米价格/万2040.12140.33570.43670.2选择最优特征1. 按特征面积 = 20 划分数据集，y1 均值为 40.1，y2 均值为(40.3 + 70.4 + 70.2) / 3 = 60.3,则平方误差为：0 + （40.3 60.3）2+ （70.4 60.3）2+（70.2 60.3）2 = 600.022. 按特征面积 = 21 划分数据集，则平方误差为：y1 均值为(40.1 + 40.3)/ 2 = 40.2，y2 均值为(70.4 + 70.2) / 2 = 70.3,则平方误差为：（40.1 40.2）2+（40.3 40.2）2+ （70.4 70.3）2+（70.2 70.3）2 = 0.043. 3.按特征面积 = 35 划分数据集，则平方误差为：y1 均值为(40.1 + 40.3 + 70.4) / 3 = 50.27，y2 均值为 70.2,则平方误差为：（40.1 50.27）2+ （40.3 50.27）2+（70.4 50.27）2+ 0 = 608.05综上所述，由于按特征面积 = 21 比特征面积 = 20、面积 = 35 划分的平方误差小，所以特征面积 = 21 为切分点。按最优特征划分数据集以特征面积 = 21 为切分点，将数据切分为面积 = 20,价格 = 40.1; 面积 = 21, 价格 = 40.3， 面积 = 35,价格 = 70.4; 面积 = 36, 价格 = 70.2两个子集。其中子集面积 = 20,价格 = 40.1; 面积 = 21, 价格 = 40.3的目标变量非常接近，故不继续划分，得叶节点值(40.1 + 40.3) / 2 = 40.2； 同理得子集面积 = 35,价格 = 70.4; 面积 = 36, 价格 = 70.2的叶节点值为 (70.4 + 70.2) / 2 = 70.3。8. Adaboost基本原理前面内容涵盖了分类、回归、关联分析等诸多模型，其中分类模型被介绍得最多。原因是分类在机器学习方向是应用最广的方向之一。本文将要介绍的是分类模型中的另一种模型，AdaBoost（adaptive boosting），即自适应提升算法。Boosting 是一类算法的总称，这类算法的特点是通过训练若干弱分类器，然后将弱分类器组合成强分类器进行分类。为什么要这样做呢？因为弱分类器训练起来很容易，将弱分类器集成起来，往往可以得到很好的效果。俗话说，三个臭皮匠，顶个诸葛亮，就是这个道理。这类 boosting 算法的特点是各个弱分类器之间是串行训练的，当前弱分类器的训练依赖于上一轮弱分类器的训练结果。各个弱分类器的权重是不同的，效果好的弱分类器的权重大，效果差的弱分类器的权重小。值得注意的是，AdaBoost 不止适用于分类模型，也可以用来训练回归模型。这需要将弱分类器替换成回归模型，并改动损失函数。本文将重点介绍用 AdaBoost 进行分类的算法原理。AdaBoost 算法有其独特的优点，那就是可以将不同的分类算法组合起来，形成强分类器。这就可以充分利用不同分类算法的优势进行建模。也可以将同一算法的不同设置进行组合，这样训练的模型比单一设置模型的训练精度高。当然，就如每一个算法都有自己的优缺点一样，AdaBoos