第1章 SVM支持向量机算法
1.1 算法思想
SVM（Support Vector Machines）是分类算法中应用广泛、效果不错的一类。由简至繁SVM可分类为三类：线性可分（linear SVM in linearly separable case）的线性SVM、线性不可分的线性SVM、非线性（nonlinear）SVM。
1.1.1 线性可分
对于二类分类问题，训练T={(x1,y1),(x2,y2),⋯,(xN,yN)}T={(x1,y1),(x2,y2),⋯,(xN,yN)}，其类别yi∈{0,1}yi∈{0,1}，线性SVM通过学习得到分离超平面:
以及相应的分类决策函数：
有如下图所示的分离超平面，哪一个超平面的分类效果更好呢？
直观上，超平面B1B1的分类效果更好一些。将距离分离超平面最近的两个不同类别的样本点称为支持向量（support vector）的，构成了两条平行于分离超平面的长带，二者之间的距离称之为margin。显然，margin更大，则分类正确的确信度更高（与超平面的距离表示分类的确信度，距离越远则分类正确的确信度越高）。通过计算容易得到：
从上图中可观察到：margin以外的样本点对于确定分离超平面没有贡献，换句话说，SVM是有很重要的训练样本（支持向量）所确定的。至此，SVM分类问题可描述为在全部分类正确的情况下，最大化
（等价于最小化
）；线性分类的约束最优化问题：
对每一个不等式约束引进拉格朗日乘子
；构造拉格朗日函数（Lagrange function）：
根据拉格朗日对偶性，原始的约束最优化问题可等价于极大极小的对偶问题：
将L(w,b,α)L(w,b,α)对w,bw,b求偏导并令其等于0，则
将上述式子代入拉格朗日函数(3)(3)中，对偶问题转为
等价于最优化问题：
线性可分是理想情形，大多数情况下，由于噪声或特异点等各种原因，训练样本是线性不可分的。因此，需要更一般化的学习算法。
1.1.2 线性不可分
线性不可分意味着有样本点不满足约束条件(2)(2)，为了解决这个问题，对每个样本引入一个松弛变量ξi≥0ξi≥0，这样约束条件变为：
目标函数则变为
其中，C为惩罚函数，目标函数有两层含义：
· margin尽量大，
· 误分类的样本点计量少
C为调节二者的参数。通过构造拉格朗日函数并求解偏导（具体推导略去），可得到等价的对偶问题：
与上一节中线性可分的对偶问题相比，只是约束条件αiαi发生变化，问题求解思路与之类似。
1.1.3 非线性
对于非线性问题，线性SVM不再适用了，需要非线性SVM来解决了。解决非线性分类问题的思路，通过空间变换ϕϕ（一般是低维空间映射到高维空间x→ϕ(x)x→ϕ(x)）后实现线性可分，在下图所示的例子中，通过空间变换，将左图中的椭圆分离面变换成了右图中直线。
在SVM的等价对偶问题中的目标函数中有样本点的内积xi⋅xjxi⋅xj，在空间变换后则是ϕ(xi)⋅ϕ(xj)ϕ(xi)⋅ϕ(xj)，由于维数增加导致内积计算成本增加，这时核函数（kernel function）便派上用场了，将映射后的高维空间内积转换成低维空间的函数：
将其代入一般化的SVM学习算法的目标函数(7)(7)中，可得非线性SVM的最优化问题：
第2章 决策树算法
2.1 决策树
决策树（Decision Tree）是一种基本的分类与回归方法。决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。相比朴素贝叶斯分类，决策树的优势在于构造过程不需要任何领域知识或参数设置，因此在实际应用中，对于探测式的知识发现，决策树更加适用。
分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型：内部节点和叶节点，内部节点表示一个特征或属性，叶节点表示一个类。
分类的时候，从根节点开始，对实例的某一个特征进行测试，根据测试结果，将实例分配到其子结点；此时，每一个子结点对应着该特征的一个取值。如此递归向下移动，直至达到叶结点，最后将实例分配到叶结点的类中。
举一个通俗的例子，各位立志于脱单的单身男女在找对象的时候就已经完完全全使用了决策树的思想。假设一位母亲在给女儿介绍对象时，有这么一段对话：
母亲：给你介绍个对象。
女儿：年纪多大了？
母亲：26。
女儿：长的帅不帅？
母亲：挺帅的。
女儿：收入高不？
母亲：不算很高，中等情况。
女儿：是公务员不？
母亲：是，在税务局上班呢。
女儿：那好，我去见见。
这个女生的决策过程就是典型的分类决策树。相当于对年龄、外貌、收入和是否公务员等特征将男人分为两个类别：见或者不见。假设这个女生的决策逻辑如下： 
上图完整表达了这个女孩决定是否见一个约会对象的策略，其中绿色结点（内部结点）表示判断条件，橙色结点（叶结点）表示决策结果，箭头表示在一个判断条件
在不同情况下的决策路径，图中红色箭头表示了上面例子中女孩的决策过程。 这幅图基本可以算是一棵决策树，说它“基本可以算”是因为图中的判定条件没有量化，如收入高中低等等，还不能算是严格意义上的决策树，如果将所有条件量化，则就变成真正的决策树了。
2.2 决策树模型的两种解释
分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型：内部结点和叶节点。内部结点表示一个特征或属性，叶节点表示一个类。
2.2.1 决策树与if-then规则
可以将决策树看成一个if-then规则的集合。即由决策树的根结点到叶节点的每一条路径构建一条规则；路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。
决策树的路径或其对应的if-then规则集合的重要性质：互斥且完备（每一个实例都被一条路径或一条规则所覆盖，且只被一条路径或一条规则所覆盖，这里的覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件）
2.2.2 决策树与条件概率分布
决策树还表示给定特征条件下类的条件概率分布，它定义在特征空间的一个划分。将特征空间划分为互不相交的单元，并在每个单元定义一个类的概率分布就构成了一个条件概率分布。决策树的每一条路径对应于划分中的一个单元。
假设X为表示特征的随机变量，Y为表示类的随机变量，那么这个条件概率分布可以表示为P(X|Y)，各叶结点上的条件概率往往偏向于某一个类，即属于某一类的概率越大。决策树分类时将该结点的实例强行分到条件概率大的那一类去。
2.3 特征选择
知道了什么是决策树，那么如果构造决策树呢？为什么拿年龄作为第一个分类？那么就涉及到特征选择的问题。特征选择中用的最多的方法是通过熵和基尼进行对比。
特征选择的标准是找出局部最优的特征，判断一个特征对于当前数据集的分类效果，也就是按照这个特征进行分类后，不同分类的数据是否能够被尽量分开。
2.3.1 熵
2.3.1.1 信息量
信息量由这个事件发生的概率所决定。经常发生的事件是没有什么信息量的，只有小概率的事件才有信息量，所以信息量的定义为：
例如：英语有26个字母，假如每个字母在文章中出现的次数是平均数，那每个字母的信息量是：
2.3.1.2 熵
熵，就是信息量的期望，熵表示随机变量**不确定性**的度量。熵越大，随机变量的不确定性就越大。信息熵的公式为：<br /><br />条件熵表示在已知随机变量Y的条件下随机变量X的不确定性，公式为：<br />
2.3.1.3 条件熵
H(Y|X) 表示在已知随机变量X的条件下随机变量Y的不确定性定义为X给定条件下Y的条件概率分布的熵对X的数学期望。
经验熵和经验条件熵：当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵和条件经验熵。
2.3.1.4 信息增益
信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即
g(D,A)=H(D)−H(D|A)
这个差又称为互信息。信息增益大的特征具有更强的分类能力。
根据信息增益准则的特征选择方法是：对训练数据集（或子集）计算其每个特征的信息增益，选择信息增益最大的特征。
计算信息增益的算法如下：
输入：训练数据集D和特征A；
输出：特征A对训练数据集D的信息增益g(D,A).
(1)计算数据集D的经验熵H(D)
(2)计算特征A对数据集D的经验条件熵H(D|A)
2.3.1.5 信息增益比
[单纯的信息增益只是个相对值，因为这依赖于H(D)]()的大小，所以信息增益比更能客观地反映信息增益。特征A对训练数据集D的信息增益比gR(D,A)定义为其信息增益g(D,A)与训练数据集D关于特征A的值的熵HA(D)之比，即<br /><br />，n是特征A取值的个数。
2.3.2 基尼系数
2.4 决策树生成
2.4.1 ID3算法
ID3算法由Ross Quinlan发明，建立在“奥卡姆剃刀”的基础上：越是小型的决策树越优于大的决策树（be simple简单理论）。**ID3算法中根据信息增益评估和选择特征**，每次选择信息增益最大的特征作为判断模块建立子结点。ID3算法可用于划分标称型数据集，没有剪枝的过程，为了去除过度数据匹配的问题，可通过裁剪合并相邻的无法产生大量信息增益的叶子节点（例如设置信息增益阀值）。使用信息增益的话其实是有一个缺点，那就是它偏向于具有大量值的属性。就是说在训练集中，某个属性所取的不同值的个数越多，那么越有可能拿它来作为分裂属性，而这样做有时候是没有意义的，另外ID3不能处理连续分布的数据特征，于是就有了C4.5算法。CART算法也支持连续分布的数据特征。 <br /> 算法步骤如下： <br />
2.4.2 C4.5算法
C4.5算法用信息增益比来选择属性，继承了ID3算法的优点。并在以下几方面对ID3算法进行了改进：<br />· 克服了用信息增益选择属性时偏向选择取值多的属性的不足；<br />· 在树构造过程中进行剪枝；<br />· 能够完成对连续属性的离散化处理；<br />· 能够对不完整数据进行处理。<br />C4.5算法产生的分类规则易于理解、准确率较高；但效率低，因树构造过程中，需要对数据集进行多次的顺序扫描和排序。也是因为必须多次数据集扫描，C4.5只适合于能够驻留于内存的数据集。在实现过程中，C4.5算法在结构与递归上与ID3完全相同，区别只在于选取决决策特征时的决策依据不同，二者都有贪心性质：即通过局部最优构造全局最优。以下是算法步骤：
2.4.3 CART
分类树与回归树（classification and regression tree，CART）模型（Breiman）由特征选择、树生成及剪枝组成，既可用于分类也可用于回归。CART是在给定输入随机变量X条件下输出变量Y的条件概率分布的学习方法。它假定决策树是二叉树，内部取值为“是”（左分支）和“否”（右分支）。<br />它的基本步骤为<br />o 1）决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大。<br />o 2）决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这是用损失函数最小作为剪枝的标准。
2.4.3.1 分类树
对分类树用基尼系数（Gini index）最小化准则，进行特征选择，生成二叉树。<br /> 具体算法步骤如下：<br />o 1）设结点的训练数据集为D，计算现有特征对该数据集的基尼指数。此时，对每一个特征A，对其可能取的每个值aa，根据样本点对A=aA=a的测试为”是”或者“否”将D分割为D1D1和D2D2两部分，计算其基尼系数。<br />o 2）在所有可能的特征A以及他们所有可能的切分点aa中，选择基尼系数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。<br />o 3）对两个子结点递归地调用上述两个步骤，直至满足停止条件。<br />o 4）生成CART决策树
2.4.3.2 回归树
首先看一个简单的回归树生成实例：<br /><br />接下来具体说说回归树是如何进行特征选择生成二叉回归树的。<br />假设X与Y分别为输入和输出变量，并且Y是连续变量，给定训练数据集<br /><br />我们利用最小二乘回归树生成算法来生成回归树f(x)，即在训练数据集所在的输入空间中，递归地将每个区域分为两个子区域并决定每个子区域上的输出值，构建二叉决策树，步骤如下：<br />1） 选择最优切分变量j与切分点s，求解<br /><br />遍历变量j，对固定的切分变量j扫描切分点s，选择使上式达到最小值得对j,s<br />2） 用选定的对(j,s)划分区域并决定相应的输出值：<br /><br />3） 继续对两个子区域调用步骤（1），（2），直至满足停止条件。<br />4） 将输入空间划分为M个区域R1,R2,···,RM，在每个单元Rm上有一个固定的输出值cm，生成决策树：<br />
2.5 决策树剪枝
[决策树生成算法对于训练集是很准确的，也就是生成的树枝很详细，但这样会过拟合，需要通过剪枝操作来提高泛化能力，思路很简单，就是在决策树对训练集数据的预测误差和树复杂度之间找一个平衡。]()<br />表示该叶节点的样本点个数，而表示该叶子节点的经验熵：<br /><br /> 树的复杂度由叶子节点的个数来表示：T。<br /> 所以，剪枝的标准就是极小化损失函数：<br /><br /> 其中，是调节参数。其越大表示选择越简单的树，而越小表示选择越复杂的树，对训练集拟合度高的树。<br /> 树的剪枝算法就是从叶子节点往上回溯，比较剪掉该叶子节点前后的损失函数的值。如果剪掉该叶子节点后，损失函数更小就剪掉，具体流程如下：<br /> 输入：生成算法产生的整个树T，参数。<br /> 输出：修剪后的子树。<br />1）计算每个节点的经验熵。<br />2）递归地从树的节点向上回溯。<br />设一组叶子节点回溯到其父节点之前与之后的整体树分别为和，其对应的损失函数值分别是和。如果小于等于，则进行剪枝，即将父节点变为新的叶子节点。<br />3） 返回2），直到不能继续为止，最终得到损失函数最小的子树。
2.6 CART剪枝
2.7 Spark MLlib案例实现
第3章 K近邻算法
3.1 算法概述
K近邻算法简单、直观。首先给出一张图，根据这张图来理解最近邻分类器。<br /><br />根据上图所示，有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是待分类的数据。也就是说，现在，我们不知道中间那个绿色的数据是从属于哪一类（蓝色小正方形或者红色小三角形），下面，我们就要解决这个问题：给这个绿色的圆分类。<br />我们常说，物以类聚，人以群分，判别一个人是一个什么样的人，常常可以从他身边的朋友入手，所谓观其友，而识其人。我们不是要判别上图中那个绿色的圆是属于那一类数据么，好说，从他的邻居下手。但一次性看多少个邻居呢？从上图中，你还可以看到：<br />o 如果K=3,绿色圆点最近的3个邻居是2个红色小三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。<br />o 如果K=5,绿色圆点的最近5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，基于统计的方法，判定绿色这个待分类点属于蓝色的正方形一类。<br />于是，我们看到，KNN算法为给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例，这K个实例的多数属于某个类，就把该输入实例分为这个类。<br />K近邻法算法步骤如下：<br /> 输入：训练数据集<br />，其中，是实例的特征向量，是实例的类别；新实例的特征向量x。<br />输出：新实例x所属的类别y。<br />o 1)根据给定的距离度量，在训练集T中找出与x最邻近的k个点，涵盖这k个点的x领域记作<br />o 2)在中根据分类决策规则（如多数表决）决定x的类别y:<br /><br />其中I为指示函数，即当时为1，否则为0。
3.2 K近邻模型
3.2.1 模型
k近邻法中，当训练集、距离度量、K值以及分类决策规则确定后，对于任何一个新的输入实例，它所属的类唯一地确定。这相当于根据上述要素将特征空间划分为一些子空间，确定子空间里的每个点所属的类。
3.2.2 距离度量
特征空间中两个实例点的距离可以反映出两个实力点之间的相似性程度。K近邻模型的特征空间一般是N维实数向量空间，使用的距离可以是欧式距离，也可以是其他距离。
1) 欧氏距离：最常见的两点之间或多点之间的距离表示法，又称之为欧几里得度量，它定义于欧几里得空间中
2) 曼哈顿距离：我们可以定义曼哈顿距离的正式意义为L1距离或城市区块距离，也就是在欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投射的距离总和。
通俗来讲，想想你在曼哈顿要从一个十字路口开车到另一个十字路口，驾驶距离是两点间的直线距离吗？显然不是，除非你能穿越大楼。而实际驾驶距离就是这个“曼哈顿距离”,此即曼哈顿距离名称的来源，同时，曼哈顿距离也称为城市街区距离。
3) 切比雪夫距离：
4) 闵可夫斯基距离：它不是一种距离，而是一组距离的定义。
当p=1时，即曼哈顿距离
当p=2时，即欧式距离
当p→∞，即切比雪夫距离
5) 标准化欧氏距离：对样本集先进行标准化
经过简单的推导就可以得到来标准化欧氏距离。
6) 夹角余弦：几何中夹角余弦可用来衡量两个向量方向的相似度，机器学习中借用这一概念来衡量向量之间的相似度。
3.2.3 K值得选择
K值得选择会对K近邻法的结果产生重大影响。
如果选择较小的K值，就相当于用较小的领域中的训练实例进行预测，“学习”近似误差会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是“学习”的估计误差会增大，换句话说，K值得减小就意味着整体模型变得复杂，容易发生过拟合（容易受到训练数据的噪声而产生的过拟合的影响）。
如果选择较大的K值，就相当于用较大领域中的训练实例进行预测，其优点是可以减小学习的估计误差，但缺点是学习的近似误差会增大。这时候，与输入实例较远的训练实例也会对预测器作用，使预测发生错误，且K值得增大就意味着整体的模型变得简单。
如果K=N。那么无论输入实例是什么，都将简单地预测它属于在训练实例中最多的类。这时，模型过于简单，完全忽略训练实例中的大量有用信息，是不可取的（最近邻列表中可能包含远离其近邻的数据点），如下图所示。
3.2.4 分类决策规则
K近邻法中的分类决策规则往往是多数表决，即由输入实例的K个邻近的训练实例中的多数类决定输入实例的类。
在实际应用中，K值一般取一个比较小的数值。通常采用交叉验证法来选取最优的K值（经验规则：K一般低于训练样本数的平方根）。
3.3 K紧邻的优缺点
3.3.1 优点
简单、易于理解、易于实现、无需估计参数、无需训练。
适合对稀有事件进行分类（如大概流式率很低时，比如0.5%，构造流失预测模型）；
特别适合多酚类问题，如根据基因特征来判断其功能分类，KNN比SVM的表现要好。
3.3.2 缺点
懒惰算法，对测试样本分类时的计算量大，内存开销大，评分慢。
可解释性较差，无法给出决策树那样的规则。
当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。
KNN是一种懒惰算法，平时不好好学习，考试（对测试样本分类）时才临阵磨枪（临时去找K个近邻），懒惰的后果，构造模型很简单，但在测试样本分类地系统开销大，因为要扫描全部训练样本并计算距离。已经有一些方法提高计算的效率，例如压缩训练样本量。
决策树和基于规则的分类器都是积极学习eager learner的例子，因为一旦训练数据可用，它们就开始学习从输入属性到类标号的映射模型。一个相反的策略是推迟对训练数据的建模，直到需要分类测试样例时再进行。采用这种策略的技术被称为消极学习法lazy learner。最近邻分类器就是这样的一种方法。
第4章 聚类算法概述
4.1 算法概述
“物以类聚，人以群分”
聚类算法属于无监督学习，类别提前是未知的。解决的问题是如何在海量的数据中将未知的数据分布特性收敛到具体的类别上。和分类不一样，分类是提前直到标签，属于有监督学习。
4.2 应用场景
4.2.1 基于用户位置信息的商业选址
随着信息技术的快速发展，移动设备和移动互联网已经普及到千家万户。在用户使用移动网络时，会自然的留下用户的位置信息。随着近年来GIS地理信息技术的不断完善普及，结合用户位置和GIS地理信息将带来创新应用。希望通过大量移动设备用户的位置信息，为某连锁餐饮机构提供新店选址。
4.2.2 搜索引擎查询聚类以进行流量推荐
在搜索引擎中， 很多网民的查询意图的比较类似的，对这些查询进行聚类，一方面可以使用类内部的词进行关键词推荐；另一方面， 如果聚类过程实现自动化，则也有助于新话题的发现；同时还有助于减少存储空间等。
4.2.3 保险投保者分组
通过一个高的平均消费来鉴定汽车保险单持有者的分组，同时根据住宅类型，价值，地理位置来鉴定一个城市的房产分组。
4.2.4 网站关键词来源聚类整和
以领域特征明显的词和短语作为聚类对象，在分类系统的大规模层级分类语料库中，利用文本分类的特征提取算法进行词语的领域聚类，通过控制词语频率的影响，分别获取领域通用词和领域专类词。
第5章 KMEANS聚类算法
5.1 算法思想
K-means的目标是要将数据点划分为k个cluster，找到这每个cluster的中心未知，使最小化函数
其中
就是第i个cluster的中心。上式就是要求每个数据点要与它们所属cluster的中心尽量接近。
基本思想使初始随机给定K个簇中心，按照最邻近原则把待分类样本点分到各个簇。然后按平均法重新计算各个簇的质心。一直迭代，直到簇心得移动距离小于某个给定的值。
5.2 KMEANS算法演示
设定K取2，即设定有两个类别。
1. 未聚类的初始点集；
2. 随机选取两个点作为聚类中心；
3. 计算每个点到聚类中心的距离，并聚类到离该点最近的聚类中去；
4. 计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心；
5. 重复（c），计算每个点到聚类中心的距离，并聚类到离该点最近的聚类中去；
6. 重复（d），计算每个聚类中的所有点的坐标平均值，并将这个平均值作为新的聚类中心。
KMEANS结束条件：直到类中心不再进行大范围移动或者聚类迭代次数达到要求为止。
5.3 最邻近算法
5.3.1 欧氏距离
欧几里德距离，这个距离就是平时我们理解的距离，如果是两个平面上的点，也就是（X1，Y1），和（X2，Y2），那这俩点距离就是√( (x1-x2)^2+(y1-y2)^2) ，如果是三维空间中呢？√( (x1-x2)^2+(y1-y2)^2+(z1-z2)^2；推广到高维空间公式就以此类推。可以看出，欧几里德距离真的是数学加减乘除算出来的距离，因此这就是只能用于连续型变量的原因。
5.3.2 余弦相似度
余弦相似度，余弦相似度用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小。相比距离度量，余弦相似度更加注重两个向量在方向上的差异，而非距离或长度上。下图表示余弦相似度的余弦是哪个角的余弦，A，B是三维空间中的两个向量，这两个点与三维空间原点连线形成的角，如果角度越小，说明这两个向量在方向上越接近，在聚类时就归成一类：
从上图可以看出，欧氏距离衡量的是空间各点的绝对距离，跟各个点所在的位置坐标直接相关；而余弦距离衡量的是空间向量的夹角，更加体现在方向上的差异，而不是位置。如果保持A点位置不变，B点朝原方向远离坐标轴原点，那么这个时候余弦距离是保持不变的（因为夹角没有发生变化），而A、B两点的距离显然在发生改变，这就是欧氏距离和余弦距离之间的不同之处。
欧氏距离和余弦距离各自有不同的计算方式和衡量特征，因此它们适用于不同的数据分析模型：欧氏距离能够体现个体数值特征的绝对差异，所以更多的用于需要从维度的数值大小中体现差异的分析，如使用用户行为指标分析用户价值的相似度或差异。
余弦距离更多的是从方向上区分差异，而对绝对的数值不敏感，更多的用于使用用户对内容评分来区分兴趣的相似度和差异，同时修正了用户间可能存在的度量标准不统一的问题（因为余弦距离对绝对数值不敏感）。
5.4 K的取值
这个真的没有确定的做法，分几类主要取决于个人的经验与感觉，通常的做法是多尝试几个K值，看分成几类的结果更好解释，更符合分析目的等。或者可以把各种K值算出的SSE做比较，取最小的SSE的K值。
如果有业务专家可以进行分析，或者可以使用层次聚类先进行比较粗粒度的聚类。
5.5 K的初始位置
k-means++算法选择初始位置的基本思想就是：初始的聚类中心之间的相互距离要尽可能的远。
1. 从输入的数据点集合中随机选择一个点作为第一个聚类中心
2. 对于数据集中的每一个点x，计算它与最近聚类中心(指已选择的聚类中心)的距离D(x)
3. 选择一个新的数据点作为新的聚类中心，选择的原则是：D(x)较大的点，被选取作为聚类中心的概率较大
4. 重复2和3直到k个聚类中心被选出来
5. 利用这k个初始的聚类中心来运行标准的k-means算法
从上面的算法描述上可以看到，算法的关键是第3步，如何将D(x)反映到点被选择的概率上，一种算法如下：
1. 先从我们的数据库随机挑个随机点当“种子点”
2. 对于每个点，我们都计算其和最近的一个“种子点”的距离D(x)并保存在一个数组里，然后把这些距离加起来得到Sum(D(x))。
3. 然后，再取一个随机值，用权重的方式来取计算下一个“种子点”。这个算法的实现是，先取一个能落在Sum(D(x))中的随机值Random，然后用Random -= D(x)，直到其<=0，此时的点就是下一个“种子点”。
4. 重复2和3直到k个聚类中心被选出来
5. 利用这k个初始的聚类中心来运行标准的k-means算法
可以看到算法的第三步选取新中心的方法，这样就能保证距离D(x)较大的点，会被选出来作为聚类中心了。至于为什么原因比较简单，如下图所示： 
假设A、B、C、D的D(x)如上图所示，当算法取值Sum(D(x))*random时，该值会以较大的概率落入D(x)较大的区间内，所以对应的点会以较大的概率被选中作为新的聚类中心。
5.6 Spark MLlib案例实现
第6章 EM算法
6.1 定义
6.2 Jensen不等式
6.3 EM思想
6.3.1 极大似然估计
6.3.2 EM算法思想
6.4 EM推导
第7章 FPGrowth关联规则算法
7.1 算法思想
FPGrowth算法通过构造一个FPTree树结构来压缩数据记录，使得挖掘频繁项集只需要扫描两次数据记录，而且该算法不需要生成候选集合，所以效率会比较高。如何从购物篮里面发现 尿布+啤酒 的最佳组合。 我们以以下数据集为例：
| TID | Items |
|---|---|
| T1 | { 面包 ， 牛奶 } |
| T2 | { 面包 , 尿布 , 啤酒 , 鸡蛋 } |
| T3 | { 牛奶 , 尿布 , 啤酒 , 可乐 } |
| T4 | { 面包 , 牛奶 , 尿布 , 啤酒 } |
| T5 | { 面包 , 牛奶 , 尿布 , 可乐 } |
注意：牛奶、面包叫做项，{ 牛奶、面包 }叫做项集。项集出现的次数叫做支持度。T* 表示用户每次的购物清单。
7.1.1 构造FPTree
FPTree是一种树结构，需要将表中的数据以及关系进行保存，我们先来看构建过程：假设我们的最小支持度是3。
Step 1：扫描鼓舞数据记录，生成一级频繁项集，并按出现次数由多到少排序，如下所示：
| Item | Count |
|---|---|
| {牛奶} | 4 |
| {面包} | 4 |
| {尿布} | 4 |
| {啤酒} | 3 |
可以看到，鸡蛋和可乐在上表中要删除，因为可乐只出现2次，鸡蛋只出现1次，小于最小支持度，因此不是频繁项集，非频繁项集的超集一定不是频繁项集，所以可乐和鸡蛋不需要再考虑。
Step 2：再次扫描数据记录，对每条记录中出现在Step 1产生的表中的项，按表中的顺序排序。初始时，新建一个根结点，标记为null；
1）第一条记录：{面包，牛奶}需要根据Step1中结果转换成：{牛奶,面包}，新建一个结点，name为{牛奶}，将其插入到根节点下，并设置count为1，然后新建一个{面包}结点，插入到{牛奶}结点下面，插入后如下所示：
2）第二条记录：{面包,尿布,啤酒,鸡蛋}，过滤并排序后为：{面包,尿布,啤酒}，发现根结点没有包含{面包}的儿子（有一个{面包}孙子但不是儿子），因此新建一个{面包}结点，插在根结点下面，这样根结点就有了两个孩子，随后新建{尿布}结点插在{面包}结点下面，新建{啤酒}结点插在{尿布}下面，插入后如下所示：
3）第三条记录：{牛奶,尿布,啤酒,可乐}，过滤并排序后为：{牛奶,尿布,啤酒}，这时候发现根结点有儿子{牛奶}，因此不需要新建结点，只需将原来的{牛奶}结点的count加1即可，往下发现{牛奶}结点有一个儿子{尿布}，于是新建{尿布}结点，并插入到{牛奶}结点下面，随后新建{啤酒}结点插入到{尿布}结点后面。插入后如下图所示：
4）第四条记录：{面包,牛奶,尿布,啤酒}，过滤并排序后为：{牛奶，面包,尿布,啤酒}，这时候发现根结点有儿子{牛奶}，因此不需要新建结点，只需将原来的{牛奶}结点的count加1即可，往下发现{牛奶}结点有一个儿子{面包}，于是也不需要新建{面包}结点，只需将原来{面包}结点的count加1，由于这个{面包}结点没有儿子，此时需新建{尿布}结点，插在{面包}结点下面，随后新建{啤酒}结点，插在{尿布}结点下面，插入后如下图所示：
5）第五条记录：{面包,牛奶,尿布,可乐}，过滤并排序后为：{牛奶，面包,尿布}，检查发现根结点有{牛奶}儿子，{牛奶}结点有{面包}儿子，{面包}结点有{尿布}儿子，本次插入不需要新建结点只需更新count即可，示意图如下：
按照上面的步骤，我们已经基本构造了一棵FPTree（Frequent Pattern Tree），树中每个路径代表一个项集，因为许多项集有公共项，而且出现次数越多的项越可能是公共项，因此按出现次数由多到少的顺序可以节省空间，实现压缩存储，另外我们需要一个表头和对每一个name相同的结点做一个线索，方便后面使用，线索的构造也是在建树过程形成的（下图虚线）。最后的FPTree如下：
至此，整个FpTree就构造好了。
7.1.2 利用FPTree挖掘频繁项集
FPTree建好后，就可以进行频繁项集的挖掘，挖掘算法称为FPGrowth（Frequent Pattern Growth）算法，挖掘从表头header的最后一个项开始。<br />**1）**此处即从{啤酒}开始，根据{啤酒}的线索链找到所有{啤酒}结点，然后找出每个{啤酒}结点的分支：{牛奶，面包，尿布，啤酒：1}，{牛奶，尿布，啤酒:1}，{面包，尿布，啤酒:1}，其中的“1”表示出现1次，注意，虽然{牛奶}出现4次，但{牛奶，面包，尿布，啤酒}只同时出现1次，因此分支的count是由后缀结点{啤酒}的count决定的，除去{啤酒}，我们得到对应的前缀路径{牛奶，面包，尿布：1}，{牛奶，尿布:1}，{面包，尿布:1}，根据前缀路径我们可以生成一颗条件FPTree，构造方式跟之前一样，此处的数据记录变为：
| TID | Items |
|---|---|
| T1 | {牛奶，面包，尿布 ： 1} |
| T2 | {牛奶，尿布： 1} |
| T3 | {面包，尿布： 1} |
绝对支持度依然是3，我们发现此时，牛奶的支持度为2、面包的支持度为2、尿布的支持度为3，由于我们的支持度为3，所以删除牛奶和面包。按照相同的算法构造得到的FPTree为：
构造好条件树后，对条件树进行递归挖掘，当条件树只有一条路径时，路径的所有组合即为条件频繁集，假设{啤酒}的条件频繁集为{S1,S2}，则{啤酒}的频繁集为{S1+{啤酒},S2+{啤酒},S1+S2+{啤酒}}，即{啤酒}的频繁集一定有相同的后缀{啤酒}，此处的条件频繁集为：{{}，{尿布}}，于是{啤酒}的频繁集为{{啤酒}{尿布，啤酒}}。
2）接下来找header表头的倒数第二个项{尿布}的频繁集，同上可以得到{尿布}的前缀路径为：{面包：1}，{牛奶：1}，{牛奶，面包：2}，条件FPTree的数据集为：
| TID | Items |
|---|---|
| T1 | {面包 ：1 } |
| T2 | {牛奶 ：1} |
| T3 | {牛奶，面包 ：2} |
构造的条件FpTree为：
这颗条件树路径上的所有组合即为条件频繁集：{{}，{牛奶}，{面包}，{牛奶，面包}}，加上{尿布}后，又得到一组频繁项集{{尿布}，{牛奶，尿布}，{面包，尿布}，{牛奶，面包，尿布}}，这组频繁项集一定包含一个相同的后缀：{尿布}，并且不包含{啤酒}，因此这一组频繁项集与上一组不会重复。
重复以上步骤，对header表头的每个项进行挖掘，即可得到整个频繁项集，频繁项集即不重复也不遗漏。
7.2 Spark MLlib案例实现
第8章 Apriori关联规则算法
8.1 关联分析
8.1.1 引言
8.1.2 简单关联规则初探
8.1.3 简单关联规则的有效性
8.1.4 简单关联规则的实用性
8.2 Apriori算法
8.2.1 简介
8.2.2 频繁项集的相关定义
8.2.3 寻找频繁项集
8.2.4 在最大频繁项集的基础上产生简单关联规则
第9章 协同过滤推荐算法
9.1 算法思想
比如你想看一个电影，但是不知道具体看哪一部，你会怎么做？有两种办法，一种是问问周围兴趣相似的朋友，看看他们最近有什么好的电影推荐。另外一种是看看电影的相似程度，比如都喜欢看僵尸片，那就会找电影名带有僵尸、丧尸之类的电影。<br />协同过滤算法就是基于上面的思想，主要包含基于用户的协同过滤推荐算法以及基于物品的协同过滤推荐算法。<br />实现协同过滤，一般需要几个步骤：<br />1、 收集用户偏好。<br />2、 找到相似的用户或者物品。<br />3、 计算推荐。
9.2 推荐数据准备
要进行推荐我们需要的数据如下： 用户ID、物品ID、偏好值
偏好值就是用户对物品的喜爱程度，推荐系统所做的事就是根据这些数据为用户推荐他还没有见过的物品，并且猜测这个物品用户喜欢的概率比较大。
用户ID和物品ID一般通过系统的业务数据库就可以获得，偏好值的采集一般会有很多办法，比如评分、投票、转发、保存书签、页面停留时间等等，然后系统根据用户的这些行为流水，采取减噪、归一化、加权等方法综合给出偏好值。一般不同的业务系统给出偏好值的计算方法不一样。
9.3 相似性度量
基于用户的推荐和基于物品的推荐都需要找相似，即需要找相似用户以及相似物品。比如一个男生和一个女生是朋友，不能讲该女生穿的衣服推荐给男生。要找相似。那么衡量的指标有哪些？比如皮尔逊相关系数、欧式距离、同现相似度、Cosine相似度、Tanimoto系数等。
9.3.1 皮尔逊相关系数
皮尔逊相关系数是介于1到-1之间的数，他衡量两个一一对应的序列之间的线性相关性。也就是两个序列一起增大或者一起减小的可能性。两个序列正相关值就趋近1，否者趋近于0。
数学含义：两个序列协方差与二者方差乘积的比值
如果比较两个人的相似度，那么他们所有共同评价过的物品可以看做两个人的特征序列，这两个特征序列的相似度就可以用皮尔逊相关系数去衡量。物品的相似度比较也是如此。
皮尔逊对于稀疏矩阵表现不好，可以通过引入权重进行优化。
9.3.2 欧式距离
这个已经在KMEANS中讲过，同理可以将两个人所有共同评价过的物品看做这个人的特征，将这些特征看做是空间中的点，计算两点之间的距离。<br />
9.3.3 同现相似度
物品i和物品j的同相似度公式定义：<br /><br /> 其中，分母是喜欢物品i的用户数，而分子则是同时喜欢物品i和物品j的用户数。因此，上述公式可用理解为喜欢物品i的用户有多少比例的用户也喜欢j (和关联规则类似)<br /> 但上述的公式存在一个问题，如果物品j是热门物品，有很多人都喜欢，则会导致Wij很大，接近于1。因此会造成任何物品都和热门物品交有很大的相似度。为此我们用如下公式进行修正：<br /><br />这个格式惩罚了物品j的权重，因此减轻了热门物品和很多物品相似的可能性。(也归一化了[i,j]和[j,i])
9.4 邻域大小
[有了相似度的比较，那么比较多少个用户或者物品为好呢？一般会有基于固定大小的邻域以及基于阈值的领域。具体的数值一般是通过对模型的评比分数进行调整优化。]()<br /> <br />
9.5 基于用户的CF
模型核心算法伪代码表示：
基于该核心算法，完成用户商品矩阵：
预测用户对于未评分的物品的分值，然后按照降序排序，进行推荐。
9.6 基于物品的CF
先计算出物品-物品的相似矩阵：
基于上面的结果：
给用户推送预测偏好值n个最高的物品。
9.7 Spark MLlib算法实现
第10章 ALS交替最小二乘算法
10.1 算法思想
10.1.1 矩阵分解模型
在协同过滤推荐算法中，最主要的是产生用户对物品的打分，用户对物品的打分行为可以表示成一个评分矩阵A(m*n)，表示m个用户对n各物品的打分情况。如下图所示：<br /><br />其中，A(i,j)表示用户user i对物品item j的打分。但是，用户不会对所有物品打分，图中？表示用户没有打分的情况，所以这个矩阵A很多元素都是空的，我们称其为“缺失值（missing value）”，是一个稀疏矩阵。在推荐系统中，我们希望得到用户对所有物品的打分情况，如果用户没有对一个物品打分，那么就需要预测用户是否会对该物品打分，以及会打多少分。这就是所谓的“矩阵补全（填空）”。<br />我们从另外一个层面考虑用户对物品的喜爱程序，而不是通过用户的推荐。用户之所以喜欢一个物品，绝大对数是因为这个物品的某些属性和这个用户的属性是一致或者是接近的，比如一个人总是具有爱国情怀或者侠义情怀，那么根据这些推断一定喜欢比如《射雕英雄传》、抗战剧等电视剧，因为这些电视剧所表达的正是侠义和爱国。可以设想用户拥有某些隐含的特征、物品也具有某种隐含的特征，如果这些特征都相似，那么很大程度上用户会喜欢这个物品。<br />根据上面的假设，我们可以把评分矩阵表示成两个低纬度的矩阵相乘，如下：<br /><br />我们希望学习到一个P代表user的特征，Q代表item的特征。特征的每一个维度代表一个隐性因子，比如对电影来说，这些隐性因子可能是导演，演员等。当然，这些隐性因子是[机器学习](http://lib.csdn.net/base/machinelearning)到的，具体是什么含义我们不确定。<br /> ALS 的核心就是下面这个假设：打分矩阵A是近似低秩的。换句话说，一个 的打分矩阵A 可以用两个小矩阵和的乘积来近似：。这样我们就把整个系统的自由度从一下降到了。 一个人的喜好映射到了一个低维向量，一个电影的特征变成了纬度相同的向量，那么这个人和这个电影的相似度就可以表述成这两个向量之间的内积。<br />我们把打分理解成相似度，那么**“打分矩阵A(m*n)”**就可以由**“用户喜好特征矩阵U(m*k)”**和**“产品特征矩阵V(n*k)”**的乘积来近似了。这种方法被称为概率矩阵分解算法(probabilistic matrix factorization，PMF)。ALS算法是PMF在数值计算方面的应用。
10.1.2 交替最小二乘法（ALS）
为了使低秩矩阵X和Y尽可能地逼近R，需要最小化下面的平方误差损失函数：
考虑到矩阵的稳定性问题，使用吉洪诺夫正则化Tikhonov regularization，则上式变为：
所以整个矩阵分解模型的损失函数为：
有了损失函数之后，下面就开始谈优化方法了，通常的优化方法分为两种：交叉最小二乘法（alternative least squares）和随机梯度下降法（stochastic gradient descent）。本次使用交叉最小二乘法（ALS）来最优化损失函数。算法的思想就是：我们先随机生成
然后固定它求解
，再固定求解
，这样交替进行下去，直到取得最优解min(C)。因为每步迭代都会降低误差，并且误差是有下界的，所以ALS 一定会收敛。但由于问题是非凸的，ALS 并不保证会收敛到全局最优解。但在实际应用中，ALS 对初始点不是很敏感，是不是全局最优解造成的影响并不大。
算法的执行步骤：
1、先随机生成一个。一般可以取0值或者全局均值。
2、固定（即：认为是已知的常量），来求解。
此时，损失函数为：
由于C中只有Vj一个未知变量，因此C的最优化问题转化为最小二乘问题，用最小二乘法求解Vj的最优解：
固定j（j=1,2,……,n），则：C的导数
令
，得到：
即：
令
，
，则：
按照上式依次计算v1，v2，……，vn，从而得到。
3、固定（即：认为是已知的量），来求解。
此时，损失函数为：
同理，用步骤2中类似的方法，可以计算ui的值：
令
，得到：
即：
令
，
，则：
依照上式依次计算u1，u2，……，um，从而得到。
4、循环执行步骤2、3，直到损失函数C的值收敛（或者设置一个迭代次数N，迭代执行步骤2、3 N次后停止）。这样，就得到了C最优解对应的矩阵U、V。
10.2 Spark MLlib算法实现
第11章 SVD推荐系统算法
11.1 传统的SVD算法
11.2 Funk-SVD算法
11.2.1 基本思想
11.2.2 Funk-SVD
11.3 Bias-SVD
11.4 SVD++
11.5 矩阵分解的优缺点
第12章 随机森林算法
12.1 算法原理
顾名思义，是用随机的方式建立一个森林，森林里面有很多的决策树组成，随机森林的每一棵决策树之间是没有关联的。在得到森林之后，当有一个新的输入样本进入的时候，就让森林中的每一棵决策树分别进行一下判断，看看这个样本应该属于哪一类（对于分类算法），然后看看哪一类被选择最多，就预测这个样本为那一类。
我们可以这样比喻随机森林算法：每一棵决策树就是一个精通于某一个窄领域的专家（因为我们从M个特征中选择m个让每一棵决策树进行学习），这样在随机森林中就有了很多个精通不同领域的专家，对一个新的问题（新的输入数据），可以用不同的角度去看待它，最终由各个专家，投票得到结果。
下图为随机森林算法的示意图：
随机森林算法有很多优点：
· 在数据集上表现良好，两个随机性的引入，使得随机森林不容易陷入过拟合
· 在当前的很多数据集上，相对其他算法有着很大的优势，两个随机性的引入，使得随机森林具有很好的抗噪声能力
· 它能够处理很高维度（feature很多）的数据，并且不用做特征选择，对数据集的适应能力强：既能处理离散型数据，也能处理连续型数据，数据集无需规范化
· 可生成一个
矩阵，用于度量样本之间的相似性：
表示样本i和j出现在随机森林中同一个叶子结点的次数，N随机森林中树的颗数
· 在创建随机森林的时候，对generlization error使用的是无偏估计
· 训练速度快，可以得到变量重要性排序（两种：基于OOB误分率的增加量和基于分裂时的GINI下降量
· 在训练过程中，能够检测到feature间的互相影响
· 容易做成并行化方法
· 实现比较简单
12.2 随机森林的生成
12.2.1 生成步骤
步骤如下：
1）如果训练集大小为NN，对于每棵树而言，随机且有放回地从训练集中抽取NN个训练样本（bootstrap抽样方法），作为该树的训练集；每棵树的训练集都是不同的，但里面包含重复的训练样本
2）如果每个样本的特征维度为MM，指定一个常数mm，且mm
12.2.2 影响分类效果的参数
随机森林的分类效果（即错误率）与以下两个因素有关：
1）森林中任意两棵树的相关性：相关性越大，错误率越大
2）森林中每棵树的分类能力：每棵树的分类能力越强，整个森林的错误率越低
减小特征选择个数m，树的相关性和分类能力也会相应的降低；增大m，两者也会随之增大。所以关键问题是如何选择最优的m（或者是范围），这也是随机森林唯一的一个参数。
12.2.3 袋外误差率
如何选择最优的特征个数m，要解决这个问题，我们主要依据计算得到的袋外错误率oob error（out-of-bag error）。
随机森林有一个重要的优点就是，没有必要对它进行交叉验证或者用一个独立的测试集来获得误差的一个无偏估计。它可以在内部进行评估，也就是说在生成的过程中就可以对误差建立一个无偏估计。
我们知道，在构建每棵树时，我们对训练集使用了不同的bootstrap sample（随机且有放回地抽取）。所以对于每棵树而言，部分训练实例没有参与这棵树的生成，它们称为第k棵树的oob样本。
袋外错误率（oob error）计算方式如下：
1）对每个样本计算它作为oob样本的树对它的分类情况
2）以简单多数投票作为该样本的分类结果
3）最后用误分个数占样本总数的比率作为随机森林的oob误分率
12.3 随机采样与完全分裂
在建立每一棵决策树的过程中，有两点需要注意，分别是采样与完全分裂。
12.3.1 随机采样
首先是两个随机采样的过程，random forest对输入的数据要进行行、列的采样。对于行采样，采用有放回的方式，也就是在采样得到的样本集合中，可能有重复的样本。假设输入样本为N个，那么采样的样本也为N个。这样使得在训练的时候，每一棵树的输入样本都不是全部的样本，使得相对不容易出现over-fitting。然后进行列采样，从M个feature中，选择m个(m << M)。
有放回抽样的解释
如果不是有放回的抽样，那么每棵树的训练样本都是不同的，都是没有交集的，这样每棵树都是”有偏的”，都是绝对”片面的”（当然这样说可能不对），也就是说每棵树训练出来都是有很大的差异的；而随机森林最后分类取决于多棵树（弱分类器）的投票表决，这种表决应该是”求同”，因此使用完全不同的训练集来训练每棵树这样对最终分类结果是没有帮助的，这样无异于是”盲人摸象”。
对Bagging__的改进
随机森林对Bagging的改进就在于随机采用的不同，即以下两点：
1）Random forest是选与输入样本的数目相同多的次数（可能一个样本会被选取多次，同时也会造成一些样本不会被选取到），而bagging一般选取比输入样本的数目少的样本；
2）bagging是用全部特征来得到分类器，而Random forest是需要从全部特征中选取其中的一部分来训练得到分类器； 一般Random forest效果比bagging效果好。
12.3.2 完全分裂
之后就是对采样之后的数据使用完全分裂的方式建立出决策树，这样决策树的某一个叶子节点要么是无法继续分裂的，要么里面的所有样本的都是指向的同一个分类。一般很多的决策树算法都一个重要的步骤 - 剪枝，但是这里不这样干，由于之前的两个随机采样的过程保证了随机性，所以就算不剪枝，也不会出现over-fitting。 按这种算法得到的随机森林中的每一棵都是很弱的，但是大家组合起来就很厉害了。
12.4 随机森林的变体
也可以使用SVM、Logistic回归等其他分 类器，习惯上，这些分类器组成的“总分类器”，仍然叫做随机森林。
比如回归问题，图中离散点为臭氧(横轴)和温度(纵轴)的关系，试拟合变化曲线，记原始数据为D，长度为N(即图中有N个离散点)
算法过程为：
1）做100次bootstrap，每次得到的数据Di，Di的长度为N
2）对于每一个Di，使用局部回归(LOESS)拟合一条曲线(图 中灰色线是其中的10条曲线)
3）将这些曲线取平均，即得到红色的最终拟合曲线
4）显然，红色的曲线更加稳定，并且没有过拟合明显减弱
第13章 AdaBoost算法
13.1 集成学习
13.1.1 定义
所谓集成学习（ensemble learning），是指通过构建多个弱学习器，然后结合为一个强学习器来完成分类任务。并相较于弱分类器而言，进一步提升结果的准确率。严格来说，集成学习并不算是一种分类器，而是一种学习器结合的方法。
下图显示了集成学习的整个流程：首次按产生一组“个体学习器”，这些个体学习器可以是同质的（homogeneous）（例如全部是决策树），这一类学习器被称为基学习器（base learner），相应的学习算法称为“基学习算法”；集成也可包含不同类型的个体学习器（例如同时包含决策树和神经网络），这一类学习器被称为“组件学习器”（component learner）。
集成学习通过将多个学习器进行结合，可获得比单一学习器显著优越的泛化性能，它基于这样一种思想：对于一个复杂任务来说，将多个专家的判断进行适当的综合所得出的判断，要比其中任何一个专家单独的判断好，直观一点理解，就是我们平时所说的“三个臭皮匠，顶个诸葛亮”，通过使用多个决策者共同决策一个实例的分类从而提高分类器的泛化能力。
13.1.2 集成学习的条件
当然，这种通过集成学习来提高学习器（这里特指分类器）的整体泛化能力也是有条件的：
首先，分类器之间应该具有差异性，即要有“多样性”。很容易理解，如果使用的是同一个分类器，那么集成起来的分类结果是不会有变化的。‘
其次，每个个体分类器的分类精度必须大于0.5，如果p<0.5p<0.5那么随着集成规模的增加，分类精度会下降；但如果是大于0.5的话，那么最后最终分类精度是可以趋于1的。
因此，要获得好的集成，个体学习器应该“好而不同”，即个体学习器要有一定的“准确性”，即学习器不能太坏，并且要有“多样性”，即学习器间具有差异。
13.1.3 集成学习的分类
当前，我们可以立足于通过处理数据集生成差异性分类器，即在原有数据集上采用抽样技术获得多个训练数据集来生成多个差异性分类器。根据个体学习器的生成方式，目前集成学习方法大致可分为两大类：第一类是个体学习器之间存在强依赖关系、必须串行生成的序列化方法，这种方法的代表是“Boosting”；第二类是个体学习器间不存在强依赖关系、可同时生成的并行化方法，它的代表是“Bagging”和“Random Forest”
Bagging：通过对原数据进行有放回的抽取，构建出多个样本数据集，然后用这些新的数据集训练多个分类器。因为是有放回的采用，所以一些样本可能会出现多次，而其他样本会被忽略。该方法是通过降低基分类器方法来改善泛化能力，因此Bagging的性能依赖于基分类器的稳定性，如果基分类器是不稳定的，Bagging有助于减低训练数据的随机扰动导致的误差，但是如果基分类器是稳定的，即对数据变化不敏感，那么Bagging方法就得不到性能的提升，甚至会降低。
Boosting：提升方法是一个迭代的过程，通过改变样本分布，使得分类器聚集在那些很难分的样本上，对那些容易错分的数据加强学习，增加错分数据的权重，这样错分的数据再下一轮的迭代就有更大的作用（对错分数据进行惩罚）。
Bagging与Boosting的区别：
二者的主要区别是取样方式不同。Bagging采用均匀取样，而Boosting根据错误率来取样，因此Boosting的分类精度要优于Bagging。Bagging的训练集的选择是随机的，各轮训练集之间相互独立，而Boostlng的各轮训练集的选择与前面各轮的学习结果有关；Bagging的各个预测函数没有权重，而Boosting是有权重的；Bagging的各个预测函数可以并行生成，而Boosting的各个预测函数只能顺序生成。对于象神经网络这样极为耗时的学习方法。Bagging可通过并行训练节省大量时间开销。
bagging是减少variance，而boosting是减少bias。Bagging 是 Bootstrap Aggregating 的简称，意思就是再取样 (Bootstrap) 然后在每个样本上训练出来的模型取平均，所以是降低模型的 variance. Bagging 比如 Random Forest 这种先天并行的算法都有这个效果。Boosting 则是迭代算法，每一次迭代都根据上一次迭代的预测结果对样本进行加权，所以随着迭代不断进行，误差会越来越小，所以模型的 bias 会不断降低。这种算法无法并行。
13.2 AdaBoost算法
13.2.1 AdaBoost算法思想
对于分类问题而言，给定一个训练样本集，求比较粗糙的分类规则（弱分类器）要比求精确地分类规则（强分类器）容易得多。提升算法就是从弱学习算法出发，反复学习，得到一系列弱分类器（又称为基本分类器），然后组合这些弱分类器，构成一个强分类器。大多数的提升方法都是改变训练数据的概率分布（训练数据的权值分布），针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。
这样，对提升方法来说，有两个问题需要回答：一是在每一轮如果改变训练数据的权值或概率分布；二是如何将弱分类器组合成一个强分类器。对于第一个问题，AdaBoost的做法是，提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。这样一来，那些没有得到正确分类的数据，由于其权值的加大而受到后一轮的弱分类器的更大关注，于是，分类问题就被一系列的弱分类器“分而治之”。至于第二个问题，即弱分类器的组合，AdaBoost采取加权多数表决的方法。具体地，加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用，减小分类误差率较大的弱分类器的权值，使其在表决中起较小的作用。
AdaboostBoost的算法的框架如下图所示
具体来说，整个AdaBoost算法包括以下三个步骤：
1）初始化训练样本的权值分布。如果有N个样本，则每一个训练样本最开始时都被赋予相同的权值：1/N1/N。
2）训练弱分类器。具体训练过程中，如果某个样本已经被准确地分类，那么在构造下一个训练集中，它的权值就会被降低；相反，如果某个样本点没有被准确地分类，那么它的权值就得到提高。然后，权值更新过的样本被用于训练下一个分类器，整个训练过程如果迭代地进行下去，使得分类器在迭代过程中逐步改进。
3）将各个训练得到的弱分类器组合成强分类器。各个弱分类器的训练过程结束后，加大分类误差率小的弱分类器的权重，使其在最终的分类函数中起着较大的决定作用，而降低分类误差率大的弱分类器的权重，使其在最终的分类函数中起着较小的决定作用。换言之，误差率低的弱分类器在最终分类器中权重较大，否则较小。得到最终分类器。
13.2.2 AdaBoost算法流程
13.2.3 AdaBoost算法的一个实例
13.3 AdaBoost算法的训练误差分析
13.3.1 AdaBoost的训练误差界
13.3.2 二类分类问题AdaBoost的训练误差界
13.3.3 推论
13.4 AdaBoost算法的数学推导
13.4.1 前向分布算法
13.4.2 基于前向分布算法的AdaBoost推导
第14章 XgBoost算法
14.1 XGBoost简介
在数据建模中，经常采用Boosting方法通过将成百上千个分类准确率较低的树模型组合起来，成为一个准确率很高的预测模型。这个模型会不断地迭代，每次迭代就生成一颗新的树。但在数据集较复杂的时候，可能需要几千次迭代运算，这将造成巨大的计算瓶颈。<br /> 针对这个问题。华盛顿大学的陈天奇博士开发的XGBoost（eXtreme Gradient Boosting）基于C++通过多线程实现了回归树的并行构建，并在原有Gradient Boosting算法基础上加以改进，从而极大地提升了模型训练速度和预测精度。<br /> 在Kaggle的希格斯子信号识别竞赛，XGBoost因为出众的效率与较高的预测准确度在比赛论坛中引起了参赛选手的广泛关注，在1700多支队伍的激烈竞争中占有一席之地。随着它在Kaggle社区知名度的提高，最近也有队伍借助XGBoost在比赛中夺得第一。其次，因为它的效果好，计算复杂度不高，也在工业界中有大量的应用。
14.2 监督学习的三要素
因为Boosting Tree本身是一种有监督学习算法，要讲Boosting Tree，先从监督学习讲起。在监督学习中有几个逻辑上的重要组成部件，粗略地可以分为：模型、参数、目标函数和优化算法。
14.2.1 模型
14.2.2 参数
14.2.3 目标函数：误差函数+正则化项
14.2.4 优化算法
上面三个部分包含了机器学习的主要成分，也是机器学习工具划分模型比较有效的办法。其实这几部分之外，还有一个优化算法，就是给定目标函数之后怎么学的问题。有时候我们往往只知道“优化算法”，而没有仔细考虑目标函数的设计问题，比如常见的例子如决策树的学习算法的每一步去优化基尼系数，然后剪枝，但是没有考虑到后面的目标是什么。而这些启发式优化方法背后往往隐含了一个目标函数，理解了目标函数本身也有利于我们设计相应的学习算法。
14.3 回归树与树集成
14.3.1 回归树
14.3.2 树集成
14.4 XGBoost的推导过程
14.4.1 XGBoost的目标函数与泰勒展开
14.4.2 决策树的复杂度
14.4.3 目标函数的最小化
14.4.4 枚举树的结果——贪心法
第15章 GBDT算法
15.1 Regression Desicion Tree：回归树
15.1.1 回归树简介
15.1.2 回归树的生成
15.2 Boosting Decision Tree：提升树
15.2.1 提升树模型
15.2.2 提升树算法
15.2.3 提升树实例
15.3 Gradient Boosting Decision Tree：梯度提升决策树
15.3.1 GBDT简介
15.3.2 GBDT算法步骤
若有收获，就点个赞吧
0 人点赞
