机器学习简明原理

1、机器学习简明原理讲明：本文整理自IBM大数据学习文档，原文作者：韩笑琳关于机器学习的简介机器学习是从大量数据中学习出特定规律的算法。其中提到的规律有专门多种，比如分类、聚类、回归、关联分析等。分类确实是给定大量带标签的数据，计算出未知标签样本的标签取值。如年龄 40 岁以上、工科、研究生以上学历，这类人薪资水平是高收入；年龄 20-30 岁、文科、大专学历，这类人的薪资水平是低收入；现有一位 23 岁大专文科人士，求该人的薪资水平是哪类？依照分类建模，就能够明白那个人的薪资水平专门可能是低收入。聚类是将大量不带标签的数据依照距离聚拢成不同的簇，每一簇数据有共同的特征。如电信行业能够依照用户的月

2、长途电话分钟数、上网时长、短信使用数、地理位置、月消费数，将所有用户聚拢成有典型特征的簇，聚拢出的某簇特征可能是月长途电话分钟数长、上网时刻长、地理位置变化不大、月消费数目低，分析可得这类人极有可能是在校大学生，那么电信公司就能够针对这类特定人群制定有针对性的营销策略。回归是依照特征值、目标变量拟合出特征值与目标变量之间的函数关系，可用来可能特征值对应的目标变量的可能取值。举个简单的例子，某市今年某 100 平米的房子价格是 80 万，某 150 平米房子价格是 120 万，那么某 200 平米的房子价格的取值就可能是 200*0.8=160 万左右。关联分析是计算出大量数据之间的频繁项集合。

3、如超市订单中有大量订单同时包含啤酒与尿布，这其中的频繁项确实是啤酒和尿布，那么超市就能够针对那个规律对啤酒和尿布进行组合促销活动。分类算法要紧包括K近邻、决策树、朴素贝叶斯、逻辑回归、支持向量机、AdaBoost等；回归要紧包括线性回归、岭回归、lasso、树回归等；聚类要紧包括 K-Means 以及它的各种变形算法；关联分析要紧包括 Apriori、FP-growth 等算法。支持向量机即 support vector machine(简称 SVM)，是机器学习领域经典的分类算法。关于 SVM 的简介支持向量是距离分类超平面近的那些点，SVM的思想确实是使得支持向量到分类超平面的间隔最大化。

4、动身点专门容易理解，距离分类超平面近的那些点到该超平面的间隔最大化代表了该超平面对两类数据的区分度强，不容易出现错分的情况。如 REF _Ref519850741 h * MERGEFORMAT 图 1所示，支持向量到超平面1的间隔大于支持向量到超平面2的间隔，因此超平面1优于超平面2。图 SEQ 图 * ARABIC 1 两个超平面示例SVM 能够专门好得解决二分类问题，关于多分类情况，就需要对模型进行改动。如 one-versus-rest 法，这种方法每次选择一个类不作为正样本，剩下其他类不作为负样本，假设一共有3个类不，如此相当于训练出了3个不同的SVM。然后将测试数据分不带入3个SV

5、M模型中，得到的3个结果中的最大值则为最终的分类结果。支持向量到分类超平面的间隔最大化的思路专门完美，按这种思路得到的模型理论上是准确度最高的一种模型。然而使用过SVM的朋友都明白，调用SVM算法的测试准确度并不一定都专门高。这其中有专门多缘故，比如数据预处理的效果、训练集的大小、特征值的选择、参数设置以及核函数的选择等因素。任何模型差不多上优点与缺点并存的。SVM的优点是：能够解决线性不可分的情况。如 REF _Ref519850852 h 图 2所示，两类数据点全然无法用超平面分隔开;计算复杂度仅取决于少量支持向量，关于数据量大的数据集计算复杂度低。SVM 的缺点是：经典的 SVM 算法仅

6、支持二分类，关于多分类问题需要改动模型;不支持类不型数据，需在预处理时期将类不型数据转换成离散型数据。类不型数据即男、 女这类由字符串表示某类信息的数据，需将这类数据转换成离散型数据如 1、2。图 SEQ 图 * ARABIC 2 线性不可分问题SVM 差不多原理SVM原理分为软间隔最大化、拉格朗日对偶、最优化问题求解、核函数、序列最小优化SMO等部分。尽管这些名词看起来专门晦涩，然而深入探究后就会发觉其中的思想并没有那么复杂。软间隔最大化SVM的核心思路是最大化支持向量到分隔超平面的间隔。后面所有的推导差不多上以最大化此间隔为核心思想展开。一般的机器学习问题差不多上先得到模型的目标函数和约束

7、条件，然后在约束条件下对目标函数求得最优解。因此，我们下面首先需要推导出SVM模型的目标函数和约束条件。既然要最大化间隔，那么回忆下点x到超平面(w,b)的距离公式：其中超平面的公式为：由此可推出点 x 到超平面(w,b)的几何间隔为： 其中 xi代表第i条数据，yi代表第i条数据对应的目标变量的取值，取值有+1 和-1 两种。因此当第 i条数据被正确分类时，y 取值和 w*x+b 取值的正负一致，几何间隔为正；当被错误分类时，y 取值和 w*x+b 取值的正负相反，几何间隔为负。图 SEQ 图 * ARABIC 3 样本数关于w*x + b的取值符号定义几何间隔中最小的为：由此，能够得到间隔

8、最大化问题的目标函数：并遵循如下约束条件： 做如下变换：则目标函数转换为：相应的约束条件变为： 做如下变换：可得目标函数和约束条件变为： 由于 w, b 成倍数变化并可不能阻碍超平面的公式，因此：现在得到最终的间隔最大化的目标函数和约束条件如下：然而，到那个地点并没有真正得结束。考虑到现实生活中的真实数据，存在一些特异点即 outliers，这些数据点并不满足上面推导出的约束条件，如 REF _Ref519850779 h * MERGEFORMAT 图 4所示，图中点 A 确实是 outlier 特异点。图 SEQ 图 * ARABIC 4 Outlier特异点为了解决这种问题，对每个样本点

9、引进一个松弛变量，使得约束条件变为：如此给 outlier 的约束条件加上一个变量，使其能够满足大于等于 1 的条件。则相应的目标变量变为：其中 C 为惩处参数，它的目的是使得目标变量最小即几何间隔最大，且使得松弛变量最小化。加入松弛变量的目标函数确实是软间隔最大化。拉格朗日对偶关于凸二次优化问题，通过引入拉格朗日乘子，将目标函数和约束条件整合到拉格朗日函数中，如此能方便求解最值问题。那么，对每个不等式约束引入拉格朗日乘子，得到拉格朗日函数如下：分析可知：则原最优化问题转换成： 由于原最优化问题直接求解专门困难，利用拉格朗日对偶性，可通过求解原最优化问题的对偶问题得到原问题的最优解。原最优化问

10、题的对偶问题为：最优化问题求解到此为止，差不多将目标函数和约束条件转换成了极大微小化拉格朗日函数的问题了。首先求解关于拉格朗日函数的微小化问题。对三个变量分不求偏导得： 将以上三式带入拉格朗日函数中得：那么极大微小化拉格朗日函数转换成：为求解方便，将极大转换成微小得： 核函数关于线性不可分问题，如 REF _Ref519850852 h * MERGEFORMAT 图 2所示，这类问题是无法用超平面划分正负样本数据的。倘若能将超平面换成超曲面，则能够将正负样本正确分类，如 REF _Ref519850927 h * MERGEFORMAT 图 5所示。图 SEQ 图 * ARABIC 5 超曲

11、面分离正负样本我们明白曲面的公式是：映射到新坐标如下：可将超曲面在新坐标下表示成超平面：也确实是将在二维空间(x1,x2)下线性不可分的问题转换成了在五维空间(z1,z2,z3,z4,z5)下线性可分的问题。得映射后新坐标下的内积：有一核函数如下：可知 何为核函数？核函数在低维空间中完成了映射到高维空间后的内积运算。这点特不有用，利用核函数，无需先将变量一一映射到高维空间再计算内积，而是简单得在低维空间中利用核函数完成这一操作。什么缘故讲不用一一映射到高维空间专门有用呢？缘故就在于首先我们无法针对每种情况提供精确的映射函数，再者关于需要映射到无穷维的情况显然无法一一映射完成。那么什么缘故是映射

12、到高维后的内积运算呢？这是因为在上节中我们得到了如下目标函数： 正是因为该目标函数中包含自变量的内积运算，而映射到高维空间后的内积运算又恰好能够通过核函数在低维空间中直接求得，故而有了核函数的由来。较常用的核函数是高斯核，高斯核能够将低维空间映射到无穷维。运用核函数后，最优化问题的目标函数和约束条件变为： 序列最小优化 (Sequential minimal optimization)到目前为止，优化问题差不多转化成了一个包含 N 个 alpha 自变量的目标变量和两个约束条件。由于目标变量中自变量 alpha 有 N 个，为了便与求解，每次选出一对自变量 alpha，然后求目标函数关于其中一

13、个 alpha 的偏导，如此就能够得到这一对 alpha 的新值。给这一对 alpha 赋上新值，然后不断重复选出下一对 alpha 并执行上述操作，直到达到最大迭代数或没有任何自变量 alpha 再发生变化为止，这确实是 SMO 的差不多思想。讲直白些，SMO 确实是在约束条件下对目标函数的优化求解算法。为何不能每次只选一个自变量进行优化？那是因为只选一个自变量 alpha 的话，会违反第一个约束条件，即所有 alpha 和 y 值乘积的和等于 0。下面是详细的 SMO 过程。假设选出了两个自变量分不是 alpha1 和 alpha2，除了这两个自变量之外的其他自变量保持固定，则目标变量和约

14、束条件转化为： 将约束条件中的 alpha1 用 alpha2 表示，并代入目标函数中，则将目标函数转化成只包含 alpha2 的目标函数，让该目标函数对 alpha2 的偏导等于 0： 可求得 alpha2 未经修剪的值： 之因此讲 alpha2 是未经修剪的值是因为所有 alpha 都必须满足大于等于 0 且小于等于 C 的约束条件，用此约束条件将 alpha2 进行修剪，修剪过程如下： 由此得： 分两种情况讨论：情况 1.当 y1 等于 y2 时，有： 情况 2.当 y1 不等于 y2 时，有：修剪后，可得 alpha2 的取值如下：由 alpha2 和 alpha1 的关系，可得：在完

15、成 alpha1 和 alpha2 的一轮更新后，需要同时更新 b 的值，当 alpha1 更新后的值满足 0alpha1C 时，由 KKT 条件得：由于篇幅有限，在此就不把推导过程一一列举，可得：同样的道理，当 alpha2 更新后的值满足 0alpha1 牛奶，该规则的置信度是 0.9，意味着在所有买了鸡蛋和面包的客户中，有 90%的客户还买了牛奶。关联规则能够用来发觉专门多有味的规律。这其中需要先阐明两个概念：支持度和置信度。支持度 Support支持度指某频繁项集在整个数据集中的比例。假设数据集有 10 条记录，包含鸡蛋, 面包的有 5 条记录，那么鸡蛋, 面包的支持度确实是 5/10

16、 = 0.5。置信度 Confidence置信度是针对某个关联规则定义的。有关联规则如鸡蛋, 面包 - 牛奶，它的置信度计算公式为鸡蛋, 面包, 牛奶的支持度/鸡蛋, 面包的支持度。假设鸡蛋, 面包, 牛奶的支持度为 0.45，鸡蛋, 面包的支持度为 0.5，则鸡蛋, 面包 - 牛奶的置信度为 0.45 / 0.5 = 0.9。关联规则用于发觉 if - then 如此的规则，并能够给出这条规则的可信度（即置信度）。现实场景中能够用来发觉专门多规律，下面举个例子。在信息安全领域，需要依照已有流量数据制定规则，来推断是否触发安全报警。如规则数据包大，多个ip地址同时发送数据 - 异常，该规则的置

17、信度为 0.85。这条规则表示，当流量数据包大，并有多个ip地址同时向目标ip发送数据时，则有 85%的概率存在异常，需要触发报警。频繁项集挖掘原理频繁项集挖掘分为构建 FP 树，和从 FP 树中挖掘频繁项集两步。本节用如下表所示的数据集作为例子展开，该示例数据集共四条数据。表格 SEQ 表格 * ARABIC 1 示例数据集数据集a,b,cc,d,b,ad,e,ab,a构建 FP 树构建 FP 树时，首先统计数据集中各个元素出现的频数，将频数小于最小支持度的元素删除，然后将数据集中的各条记录按出现频数排序，剩下的这些元素称为频繁项；接着，用更新后的数据集中的每条记录构建 FP 树，同时更新头

18、指针表。头指针表包含所有频繁项及它们的频数，还有每个频繁项指向下一个相同元素的指针，该指针要紧在挖掘 FP 树时使用。下面用上文提到的数据集展开讲明，假设最小支持度为 2。首先，统计数据集中各元素出现的次数，得 a 出现 4 次, b 出现 3 次, c 出现 2 次, d 出现 2 次, e 出现 1 次。接着，将出现次数小于最小支持度 2 的元素（即 e）在数据集中删除，并将数据集按出现次数由高到低排序，得 REF _Ref519851008 h * MERGEFORMAT 表格 2。表格 SEQ 表格 * ARABIC 2 示例数据集数据集a,b,ca,b,c,da,da,b然后，用更新

19、后的数据集中的记录创建 FP 树，并同时更新头指针表。创建 FP 树时，当待添加的记录与 FP 树中的路径相同，则只需更新元素对应的频数；假如待添加的记录与 FP 树存在不一致，则在不一致的地点分叉，创建新的结点。如 REF _Ref519851068 h * MERGEFORMAT 图 6 REF _Ref519851073 h * MERGEFORMAT 图 9所示。注意，FP 树的根节点是 null。图 SEQ 图 * ARABIC 6 向FP树添加第一条记录 a,b,c 图 SEQ 图 * ARABIC 7向FP树添加第二条记录 a,b,c,d 图 SEQ 图 * ARABIC 8向F

20、P树添加第三条记录 a ,d 图 SEQ 图 * ARABIC 9向FP树添加第四条记录 a ,b 挖掘频繁项集得到 FP 树后，需要对每一个频繁项，逐个挖掘频繁项集。具体过程为：首先获得频繁项的前缀路径，然后将前缀路径作为新的数据集，以此构建前缀路径的条件 FP 树。然后对条件 FP 树中的每个频繁项，获得前缀路径并以此构建新的条件 FP 树。不断迭代，直到条件 FP 树中只包含一个频繁项为止。下面以元素 c 为例，从上文 REF _Ref519851073 h * MERGEFORMAT 图 9创建好的 FP 树中挖掘频繁项集。首先，获得以 c 元素的前缀路径a:2,b:2，注意此处 a

21、和 b 的频数为 2 是因为 c 的频数为 2，因此与 c 共同出现的 a 和 b 的频数就都为 2。接着，创建条件 FP 树，具体的创建过程和上一节创建 FP 树的过程一样，如 REF _Ref519851137 h * MERGEFORMAT 图 10所示。图 SEQ 图 * ARABIC 10 c元素的前缀路径构成的条件 FP 树注意现在头指针表中包含两个元素，因此对每个元素，需要获得前缀路径，并将前缀路径创建成条件 FP 树，直到条件 FP 树中只包含一个元素时返回。对元素 a，获得前缀路径为 ，则频繁项集返回c,a;对元素 b，获得前缀路径a，则将前缀路径创建成条件 FP 树，如 R

22、EF _Ref519851168 h * MERGEFORMAT 图 11所示。注意现在条件 FP 树中只包含一个元素，故返回频繁项集c,b,a。由于元素 b 也是频繁项，因此c,b也是频繁项集。再加上c本身确实是频繁项集，因此 c 对应的频繁项集有：c c,a c,b c,b,a。图 SEQ 图 * ARABIC 11 b元素的前缀路径构成的条件FP树将其他元素 a,b,d 同样按照上述对 c 的操作，得到 REF _Ref519851195 h * MERGEFORMAT 表格 3所示频繁项集。表格 SEQ 表格 * ARABIC 3 元素a,b,c,d对应的频繁项集元素频繁项集a a b

23、 b b,a c c c,a c,b c,b,a d d d,a 关联规则挖掘原理关联规则挖掘首先需要对上文得到的频繁项集构建所有可能的规则，然后对每条规则逐个计算置信度，输出置信度大于最小置信度的所有规则。以频繁项集a,b,c为例，构建所有可能的规则：b,c - a, a,c - b,a,b - c,c - a,b,b - a,c,a - b,c。对每条规则计算置信度后，输出满足要求的规则即可。NaiveBayes差不多原理朴素贝叶斯模型要紧用来分类，然而与 SVM 模型不同的的是，朴素贝叶斯模型不需要针对目标变量建立模型，而是借助贝叶斯公式计算样本属于各个类不的概率，然后取概率值大的类不作

24、为分类类不。之因此称之为朴素，是因为朴素贝叶斯模型假设各属性之间是条件独立的，该假设极大得简化了运算，使得朴素贝叶斯模型变得特不简单。朴素贝叶斯模型要紧应用在文本分类方面。那个地点需要用到向量空间模型，立即文本转换成词向量。词向量的每一项是该词出现的频数。在朴素贝叶斯中会将频数进一步转换成频率。如此就完成了文本到数值上的转化，方便后期计算条件概率和先验概率。朴素贝叶斯模型也有它的优缺点，优点是模型简单，计算快；缺点是依靠于属性之间条件独立这一假设，然而现实场景下专门多情况并不满足这一假设，使得朴素贝叶斯的准确率受到阻碍。这种情况需要考虑半朴素贝叶斯，即放松属性之间条件独立这一假设，一定程度上考

25、虑属性之间的依靠关系。由于篇幅有限，对半朴素贝叶斯感兴趣的话可自行参照文末参考资源学习，本文重点介绍朴素贝叶斯的原理和实现。朴素贝叶斯原理朴素贝叶斯模型要紧利用贝叶斯公式进行展开。贝叶斯公式如下：公式中 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),只需考虑如下：假如P(X|C0) *P(C0) P(X|C1) *

26、P(C1)，则 P(C0|X) P(C1|X)，可得 X 属于 C0 类；假如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。决策树差不多原理决策树

27、算法又分专门多种，常用的有ID3，C4.5 和 CART 决策树。其中ID3和C4.5决策树更倾向于处理类不型的离散属性值，关于连续型属性值，则需要额外利用连续属性离散化技术将其划分成离散型属性值。而CART决策树，即分类回归树，直接支持连续型属性值。由于篇幅限制CART树会放在下一篇文章进行介绍，本文要紧详细介绍 ID3 和 C4.5 决策树。决策树利用了树型结构进行决策，是经典的 if-then 结构。叶节点存储类不，内部节点代表特征或属性。注意本文中提到的特征和属性是同一个概念。为了让读者有一个感性的认识，请看 REF _Ref520122910 h * MERGEFORMAT 图 12

28、所示决策树。图 SEQ 图 * ARABIC 12 决策树示例图1所示决策树用来将数据分为两类，是苹果和非苹果。如图中所示，圆的和红的，确实是苹果。不圆的不是苹果。圆的但不红的不是苹果。本文将着重介绍ID3和C4.5两种决策树。决策树需要选择最优特征划分数据集。这两种决策树的不同之处是划分数据集的最优特征选择方法不同。用最优特征划分数据会使得数据集趋于更纯，即数据集的类不数更单一，如此的数据会更有序。衡量数据的混乱程度就必须提到信息和信息熵的概念。待分类的事物可能划分在多个类不中，则符号 Xi 的信息是:可知P(Xi) 越大，则 I(Xi) 越小，即Xi的概率越大，则Xi包含的信息越少。我们都

29、明白物理中的熵用来衡量混乱程度，熵越大讲明越混乱，熵越小讲明越单一。同样，信息熵用来衡量信息中的混乱程度。用所有类不所有可能值包含的信息期望值表示信息熵，计算方法如下：ID3 决策树利用了信息增益来选择最优特征，用这种方法选择的特征是使得信息熵增益最大的特征。而 C4.5决策树利用了信息增益比来选择最优特征。用这种方法选择的特征是使得信息增益比最大的特征。什么缘故要提出信息增益比呢？这是因为只考虑信息增益来划分数据集是有缺陷的。这种缺陷体现在信息增益对选择属性取值多的特征更有利。因为按属性取值多的特征划分数据集后，划分后的各个子数据集的类不更单一，即更趋于有序，这就使得划分后的信息熵更小，那么

30、信息增益就会更大。信息增益比能够专门好的解决那个问题。信息增益比通过引入类似惩处因子的概念，对属性取值多的特征会有一定惩处。决策树原理选择最优特征决策树通过不断选择最优特征划分数据集，对划分后的子数据集不断迭代得选择最优特征划分，直到所有的数据集属于同一个类不，或者没有特征能够选择为止。选择最优特征的算法有专门多种，ID3 决策树用信息增益选择最优特征，C4.5 决策树用信息增益比选择最优特征。信息增益-用于ID3决策树信息增益，顾名思义确实是原数据集的信息熵比划分后数据集的信息熵大的程度。信息增益越大，讲明划分后的数据集信息熵更小，即该数据集类不更趋于一致。特征 A 对数据集 D 的信息增益

31、 g(D,A)为 D 的信息熵与按特征 A 进行划分后 D 的信息熵之差，即其中， 信息增益比 用于 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) 会比

32、较小。除了能够使用信息增益和信息增益比来选择最优划分特征之外，基尼指数也能够用来实现那个目的。基尼指数要紧用于 CART 树(即分类回归树)的分类树中的特征选择。关于基尼指数的详细内容会在下一篇文章介绍。用 ID3 决策树进行分类本节要紧介绍用 ID3 决策树进行分类。为了便于理解，用表1所示数据集进行详细讲明。利用 C4.5 决策树进行分类的过程会在下节介绍。表格 SEQ 表格 * ARABIC 8 示例数据集圆的红的分类111100010000100ID3决策树选择最优特征 REF _Ref520123803 h * MERGEFORMAT 表格 8数据集的信息熵为:-1/5 * log(

33、1/5) - 4/5 * log(4/5) = 0.217按特征圆的划分数据集，则信息熵为：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按特征红的划分数据集，则信息熵为：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.0

34、97综上所述，由于按特征红的比按特征圆的划分的信息增益大，因此特征红的为最优划分特征。按最优特征划分数据集按特征红的划分数据集后，有两种情况，第一种为假如是红的:0,则分类:0; 第二种为假如是红的:1, 则得到如下数据子集 圆的:1,分类：1; 圆的:0, 分类:0接下来需要对数据子集圆的:1,分类：1; 圆的:0, 分类:0接着划分。由于剩下一个特征，故按特征圆的划分数据子集。划分后，假如是圆的:1，则分类:1；假如是圆的:0, 则分类:0。返回的决策树用字典表示为：红的: 0: 类不0, 1: 圆的: 0: 类不0, 1: 类不1用 C4.5 决策树进行分类为了让读者对 ID3 和 C4

35、.5 决策树的不同之处有更好的理解，本节介绍用 C4.5 决策树进行分类。为了便于理解，仍然使用 REF _Ref520123803 h * MERGEFORMAT 表格 8所示数据集进行讲明。C4.5 决策树选择最优特征 REF _Ref520123803 h * MERGEFORMAT 表格 8数据集的信息熵为:-1/5 * log(1/5) - 4/5 * log(4/5) = 0.217按特征圆的划分数据集，则信息熵为：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

36、/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.176按特征红的划分数据集，则信息熵为：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

37、.29则信息增益比为 0.097 / 0.29 = 0.334综上所述，由于按特征红的比按特征圆的划分的信息增益比大，因此特征红的为最优划分特征。按最优特征划分数据集C4.5 决策树按最优特征划分数据集方法与上节 ID3 决策树方法相同。分类回归树差不多原理在上节中，要紧介绍了 ID3 和 C4.5 决策树。它们利用信息增益和信息增益比划分数据集。然而这两种决策树是有缺陷的，即按某特征划分后，该特征将可不能在后面的划分中出现。这就导致了划分过于迅速，从而阻碍分类结果。在这篇文章中将要介绍的CART（Classification And Regression Tree）树，即分类回归树利用二分策

38、略，有效地幸免了划分过于迅速这一问题。而且二分策略能够直接处理连续型属性值。CART树（分类回归树）分为分类树和回归树。顾名思义，分类树用于处理分类问题；回归树用来处理回归问题。我们明白分类和回归是机器学习领域两个重要的方向。分类问题输出特征向量对应的分类结果，回归问题输出特征向量对应的预测值。分类树和 ID3、C4.5决策树相似，都用来处理分类问题。不同之处是划分方法。分类树利用基尼指数进行二分。如 REF _Ref520124355 h * MERGEFORMAT 图 13所示确实是一个分类树。图 SEQ 图 * ARABIC 13 分类树示例回归树用来处理回归问题。回归将已知数据进行拟合

39、，关于目标变量未知的数据能够预测目标变量的值。如 REF _Ref520124422 h * MERGEFORMAT 图 14所示确实是一个回归树，其中 s 是切分点，x 是特征，y 是目标变量。能够看出 REF _Ref520124422 h * MERGEFORMAT 图 14利用切分点s将特征空间进行划分，y是在划分单元上的输出值。回归树的关键是如何选择切分点、如何利用切分点划分数据集、如何预测y的取值。图 SEQ 图 * ARABIC 14 回归树示例CART 树原理分类树二分分类树利用二分划分数据。将特征值等于切分点值的数据划分为左子树，将特征值不等于切分点值的数据划分为右子树。基尼

40、指数：同信息增益、信息增益比作用类似，只是基尼指数相对更快假设有 N 个类，样本属于第 n 类的概率为Pn，则基尼指数为：若数据集按特征A取值是否等于切分点值划分为D1和D2两部分，则在特征A下，集合D的基尼指数为：回归树二分回归树也利用二分划分数据。与分类树不同的是，回归树将特征值大于切分点值的数据划分为左子树，将特征值小于等于切分点值的数据划分为右子树。平方误差不同于分类树，回归树用平方误差选择切分点。若数据集按特征取值是否大于切分点值划分为两部分，则在特征A下，集合D的平方误差为：用 CART 树进行分类和回归本节要紧用示例数据详细讲明如何用 CART 树进行分类和回归。分类树表格 SE

41、Q 表格 * ARABIC 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 为切分点。按最优特征划分数据集按特

42、征红的划分数据集后，有两种情况，第一种为假如是红的:0,则分类:0; 第二种为假如是红的:1, 则有如下数据子集 圆的:1,分类：1; 圆的:0, 分类:0接下来需要对数据子集圆的:1,分类：1; 圆的:0, 分类:0接着划分。由于剩下一个特征，故按特征圆的划分数据集。划分后，假如是圆的:1，则分类:1；假如是圆的:0, 则分类:0。返回的决策树为：红的: 0: 类不 0, 1: 圆的: 0: 类不 0, 1: 类不 1回归树表格 SEQ 表格 * ARABIC 10 示例数据集面积/平米价格/万2040.12140.33570.43670.2选择最优特征按特征面积 = 20 划分数据集，y1

43、 均值为 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.02按特征面积 = 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.按特征面积 = 35 划分数据集，则平方误差为：y1 均值为(40.1 + 40

44、.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; 面积 =

45、21, 价格 = 40.3的目标变量特不接近，故不接着划分，得叶节点值(40.1 + 40.3) / 2 = 40.2； 同理得子集面积 = 35,价格 = 70.4; 面积 = 36, 价格 = 70.2的叶节点值为 (70.4 + 70.2) / 2 = 70.3。Adaboost差不多原理前面内容涵盖了分类、回归、关联分析等诸多模型，其中分类模型被介绍得最多。缘故是分类在机器学习方向是应用最广的方向之一。本文将要介绍的是分类模型中的另一种模型，AdaBoost（adaptive boosting），即自适应提升算法。Boosting 是一类算法的总称，这类算法的特点是通过训练若干弱分类器

46、，然后将弱分类器组合成强分类器进行分类。什么缘故要如此做呢？因为弱分类器训练起来专门容易，将弱分类器集成起来，往往能够得到专门好的效果。俗话讲，三个臭皮匠，顶个诸葛亮，确实是那个道理。这类 boosting 算法的特点是各个弱分类器之间是串行训练的，当前弱分类器的训练依靠于上一轮弱分类器的训练结果。各个弱分类器的权重是不同的，效果好的弱分类器的权重大，效果差的弱分类器的权重小。值得注意的是，AdaBoost 不止适用于分类模型，也能够用来训练回归模型。这需要将弱分类器替换成回归模型，并改动损失函数。本文将重点介绍用 AdaBoost 进行分类的算法原理。AdaBoost 算法有其独特的优点，那

47、确实是能够将不同的分类算法组合起来，形成强分类器。这就能够充分利用不同分类算法的优势进行建模。也能够将同一算法的不同设置进行组合，如此训练的模型比单一设置模型的训练精度高。因此，就如每一个算法都有自己的优缺点一样，AdaBoost 也有自身的缺点。AdaBoost 算法只直接支持二分类，遇到多分类的情况，需要借助 one-versus-rest 的思想来训练多分类模型。关于 one-verus-rest 的细节能够参考本系列第一篇文章 SVM。为了让读者有一个感性的认识，在文章一开始先举个 AdaBoost 训练出来的强分类器的例子，如下所示，强分类器 G(x)中包含三个弱分类器 f(x),

48、g(x) 和 z(x)， 其中每个弱分类器的权重分不为0.80, 0.69和0.71。G(x) = sign( 0.80 * f(x) + 0.69 * g(x) + 0.71 * z(x) )AdaBoost原理AdaBoost 的核心确实是不断迭代训练弱分类器，并计算弱分类器的权重。需要注意的是，弱分类器的训练依靠于样本权重。每一轮迭代的样本权重都不相同，依靠于弱分类器的权重值和上一轮迭代的样本权重。具体过程如下：训练当前迭代最优弱分类器最优弱分类器是错误率最小的那个弱分类器。错误率的计算公式是：其中m = 1,2,.,M，代表第m轮迭代。i代表第i个样本。w 是样本权重。I指示函数取值为

49、1或0，当I指示函数括号中的表达式为真时，I 函数结果为1；当I函数括号中的表达式为假时，I 函数结果为0。取错误率最低的弱分类器为当前迭代的最优弱分类器。注意，第一轮迭代计算时样本权重初始化为总样本数分之一。计算最优弱分类器的权重最优弱分类器的权重只与该弱分类器的错误率有关。弱分类器的权重计算公式如下：能够看出，错误率越小，则 alpha 值越大，即该弱分类器的权重越高；反之，错误率越大，则 alpha 值越小，则该弱分类器的权重越小。如此能够使分类精度高的弱分类器起到更大的作用，并削弱精度低的弱分类器的作用。依照错误率更新样本权重样本权重的更新与当前样本权重和弱分类器的权重有关。样本权重更

50、新公式如下：其中m = 1,2,.,M，代表第 m 轮迭代。i代表第i个样本。w 是样本权重。alpha 是弱分类器的权重。当样本被正确分类时，y 和 Gm 取值一致，则新样本权重变小；当样本被错误分类时，y 和 Gm 取值不一致，则新样本权重变大。如此处理，能够使被错误分类的样本权重变大，从而在下一轮迭代中得到重视。迭代终止条件不断重复1,2,3步骤，直到达到终止条件为止。终止条件是强分类器的错误率低于最低错误率阈值或达到最大迭代次数。用例子解释 AdaBoost 原理本节要紧用示例数据详细讲明用上节介绍的 AdaBoost 原理进行分类的过程。本例用到的数据集如表1所示。为方便讲明，本文所

51、用弱分类器为形如x1.5,则y=1，否则y=-1的简单分类算法。熟悉了 AdaBoost 原理的读者，能够使用其他分类算法作为弱分类器。如使用本系列上篇文章介绍的 CART 树中的分类树作为弱分类器，可训练出提升分类树模型。表格 SEQ 表格 * ARABIC 11 示例数据集x012345y11-1-11-1第一轮迭代1.a 选择最优弱分类器第一轮迭代时，样本权重初始化为（0.167, 0.167, 0.167, 0.167, 0.167, 0.167）。 REF _Ref520125828 h * MERGEFORMAT 表格 11数据集的切分点有0.5, 1.5, 2.5, 3.5, 4

52、.5。若按0.5切分数据，得弱分类器x 0.5, 则 y = -1。现在错误率为2 * 0.167 = 0.334。若按1.5切分数据，得弱分类器x 1.5, 则 y = -1。现在错误率为1 * 0.167 = 0.167。若按2.5切分数据，得弱分类器x 2.5, 则 y = -1。现在错误率为2 * 0.167 = 0.334。若按3.5切分数据，得弱分类器x 3.5, 则 y = -1。现在错误率为3 * 0.167 = 0.501。若按4.5切分数据，得弱分类器x 4.5, 则 y = -1。现在错误率为2 * 0.167 = 0.334。由于按1.5划分数据时错误率最小为0.167

53、，则最优弱分类器为x 1.5, 则 y = -1。1.b 计算最优弱分类器的权重alpha = 0.5 * ln(1 0.167) / 0.167) = 0.80471.c 更新样本权重x = 0, 1, 2, 3, 5时，y分类正确，则样本权重为：0.167 * exp(-0.8047) = 0.075x = 4时，y分类错误，则样本权重为：0.167 * exp(0.8047) = 0.373新样本权重总和为0.075 * 5 + 0.373 = 0.748规范化后，x = 0, 1, 2, 3, 5时，样本权重更新为：0.075 / 0.748 = 0.10 x = 4时, 样本权重更新

54、为：0.373 / 0.748 = 0.50综上，新的样本权重为(0.1, 0.1, 0.1, 0.1, 0.5, 0.1)。现在强分类器为G(x) = 0.8047 * G1(x)。G1(x)为x 1.5, 则 y = -1。则强分类器的错误率为1 / 6 = 0.167。第二轮迭代2.a 选择最优弱分类器若按0.5切分数据，得弱分类器x 0.5,则 y = 1; x 0.5, 则 y = -1。现在错误率为0.1 * 4 = 0.4。若按1.5切分数据，得弱分类器x 1.5, 则 y = -1。现在错误率为1 * 0.5 = 0.5。若按2.5切分数据，得弱分类器x 2.5,则 y = 1

55、; x 3.5,则 y = 1; x 3.5, 则 y = -1。现在错误率为0.1 * 3 = 0.3。若按4.5切分数据，得弱分类器x 4.5, 则 y = -1。现在错误率为2 * 0.1 = 0.2。由于按4.5划分数据时错误率最小为0.2，则最优弱分类器为x 4.5, 则 y = -1。2.b 计算最优弱分类器的权重alpha = 0.5 * ln(1 0.2) / 0.2) = 0.6931。2.c 更新样本权重x = 0, 1, 5时，y分类正确，则样本权重为：0.1 * exp(-0.6931) = 0.05x = 4 时，y分类正确，则样本权重为：0.5 * exp(-0.6

56、931) = 0.25x = 2,3时，y分类错误，则样本权重为：0.1 * exp(0.6931) = 0.20新样本权重总和为 0.05 * 3 + 0.25 + 0.20 * 2 = 0.8规范化后，x = 0, 1, 5时，样本权重更新为：0.05 / 0.8 = 0.0625x = 4时, 样本权重更新为：0.25 / 0.8 = 0.3125x = 2, 3时, 样本权重更新为：0.20 / 0.8 = 0.250综上，新的样本权重为(0.0625, 0.0625, 0.250, 0.250, 0.3125, 0.0625)。现在强分类器为G(x) = 0.8047 * G1(x)

57、 + 0.6931 * G2(x)。G1(x)为x 1.5, 则 y = -1。G2(x)为x 4.5, 则 y = -1。按G(x)分类会使x=4分类错误，则强分类器的错误率为1 / 6 = 0.167。第三轮迭代3.a 选择最优弱分类器若按0.5切分数据，得弱分类器x 0.5, 则 y = -1。现在错误率为0.0625 + 0.3125 = 0.375。若按1.5切分数据，得弱分类器x 1.5, 则 y = -1。现在错误率为1 * 0.3125 = 0.3125。若按2.5切分数据，得弱分类器x 2.5,则 y = 1; x 3.5,则 y = 1; x 3.5, 则 y = -1。现

58、在错误率为0.0625 * 3 = 0.1875。若按4.5切分数据，得弱分类器x 4.5, 则 y = -1。现在错误率为2 * 0.25 = 0.5。由于按3.5划分数据时错误率最小为0.1875，则最优弱分类器为x 3.5,则 y = 1; x 3.5, 则 y = -1。3.b 计算最优弱分类器的权重alpha = 0.5 * ln(1 0.1875) / 0.1875) = 0.73323.c 更新样本权重x = 2, 3时，y分类正确，则样本权重为：0.25 * exp(-0.7332) = 0.1201x = 4 时，y分类正确，则样本权重为：0.3125 * exp(-0.73

59、32) = 0.1501x = 0, 1, 5时，y分类错误，则样本权重为：0.0625 * exp(0.7332) = 0.1301新样本权重总和为 0.1201 * 2 + 0.1501 + 0.1301 * 3 = 0.7806规范化后，x = 2, 3时，样本权重更新为：0.1201 / 0.7806 = 0.1539x = 4时, 样本权重更新为：0.1501 / 0.7806 = 0.1923x = 0, 1, 5时, 样本权重更新为：0.1301 / 0.7806 = 0.1667综上，新的样本权重为(0.1667, 0.1667, 0.1539, 0.1539, 0.1923,

60、 0.1667)。现在强分类器为G(x) = 0.8047 * G1(x) + 0.6931 * G2(x) + 0.7332 * G3(x)。G1(x)为x 1.5, 则 y = -1。G2(x)为x 4.5, 则 y = -1。G3(x)为x 3.5,则 y = 1; x 3.5, 则 y = -1。按G(x)分类所有样本均分类正确，则强分类器的错误率为0 / 6 = 0。则停止迭代，最终强分类器为G(x) = 0.8047 * G1(x) + 0.6931 * G2(x) + 0.7332 * G3(x)。高斯混合模型差不多原理高斯混合简介在本系列的前六篇中，笔者分不介绍了分类，关联规则