机器学习（machine learning）大合集
1、线性分类器怎么理解呢？
我们可以把此分类器理解为线性空间的划分，最简单的，在二维空间上，通过直线的划分。
第二个理解可以理解为模板匹配，W的每一行可以看做是其中一个类别的模板。每类得分，实际上是像素点和模板匹配度。模板匹配的方式是内积计算。
2、机器学习实战之AdaBoost算法
boosting算法系列的基本思想，如下图：
adaBoost分类器就是一种元算法分类器，adaBoost分类器利用同一种基分类器（弱分类器），基于分类器的错误率分配不同的权重参数，最后累加加权的预测结果作为输出。它的自适应在于：前一个弱分类器分错的样本的权值（样本对应的权值）会得到加强，权值更新后的样本再次被用来训练下一个新的弱分类器。在每轮训练中，用总体（样本总体）训练新的弱分类器，产生新的样本权值、该弱分类器的话语权，一直迭代直到达到预定的错误率或达到指定的最大迭代次数
算法原理
（1）初始化训练数据（每个样本）的权值分布：如果有N个样本，则每一个训练的样本点最开始时都被赋予相同的权重：1/N。
（2）训练弱分类器。具体训练过程中，如果某个样本已经被准确地分类，那么在构造下一个训练集中，它的权重就被降低；相反，如果某个样本点没有被准确地分类，那么它的权重就得到提高。同时，得到弱分类器对应的话语权。然后，更新权值后的样本集被用于训练下一个分类器，整个训练过程如此迭代地进行下去。
（3）将各个训练得到的弱分类器组合成强分类器。各个弱分类器的训练过程结束后，分类误差率小的弱分类器的话语权较大，其在最终的分类函数中起着较大的决定作用，而分类误差率大的弱分类器的话语权较小，其在最终的分类函数中起着较小的决定作用。换言之，误差率低的弱分类器在最终分类器中占的比例较大，反之较小。
优点
（1）精度很高的分类器
（2）提供的是框架，可以使用各种方法构建弱分类器
（3）简单，不需要做特征筛选
（4）不用担心过度拟合
（1）用于二分类或多分类
（2）特征选择
（3）分类人物的baseline
AdaBoost的一般流程如下所示：
（1）收集数据
（2）准备数据：依赖于所用的基分类器的类型，这里的是单层决策树，即树桩，该类型决策树可以处理任何类型的数据。
（3）分析数据
（4）训练算法：利用提供的数据集训练分类器
（5）测试算法：利用提供的测试数据集计算分类的错误率
（6）使用算法：算法的相关推广，满足实际的需要
#完整AdaBoost算法实现
#算法实现伪代码
#对每次迭代：
#利用buildStump()函数找到最佳的单层决策树
#将最佳单层决策树加入到单层决策树数组
#计算alpha
#计算新的权重向量D
#更新累计类别估计值
#如果错误率为等于0.0，退出循环
GBDT概述
GBDT也是集成学习Boosting家族的成员，但是却和传统的Adaboost有很大的不同。回顾下Adaboost，我们是利用前一轮迭代弱学习器的误差率来更新训练集的权重，这样一轮轮的迭代下去。GBDT也是迭代，使用了前向分布算法，但是弱学习器限定了只能使用CART回归树模型，同时迭代思路和Adaboost也有所不同。
在GBDT的迭代中，假设我们前一轮迭代得到的强学习器是ft−1(x)ft−1(x), 损失函数是L(y,ft−1(x))L(y,ft−1(x)), 我们本轮迭代的目标是找到一个CART回归树模型的弱学习器ht(x)ht(x)，让本轮的损失损失L(y,ft(x))=L(y,ft−1(x)+ht(x))最小。也就是说，本轮迭代找到决策树，要让样本的损失尽量变得更小。
GBDT的思想可以用一个通俗的例子解释，假如有个人30岁，我们首先用20岁去拟合，发现损失有10岁，这时我们用6岁去拟合剩下的损失，发现差距还有4岁，第三轮我们用3岁拟合剩下的差距，差距就只有一岁了。如果我们的迭代轮数还没有完，可以继续迭代下面，每一轮迭代，拟合的岁数误差都会减小。
GBDT主要的优点有：
1) 可以灵活处理各种类型的数据，包括连续值和离散值。GBDT使用的是cart树模型，可以处理连续值和离散值特征。对于连续值节点划分时，按照大于小于分割点，对于离散值，按照等于不等于划分分割点。
2) 在相对少的调参时间情况下，预测的准备率也可以比较高。这个是相对SVM来说的。
3）使用一些健壮的损失函数，对异常值的鲁棒性非常强。比如 Huber损失函数和Quantile损失函数。
GBDT的主要缺点有：
1)由于弱学习器之间存在依赖关系，难以并行训练数据。不过可以通过自采样的SGBT来达到部分并行。
2）对于稀疏矩阵，容易过拟合，比lr和fm效果要差，是因为若数据中存在假象数据（例如特征f1为1的样本，输出类别都是1），树模型没法进行过拟合处理。而lr或fm可以通过正则化，压缩w1的值。
xgboost
xgboost能自动利用cpu的多线程，而且适当改进了gradient boosting，加了剪枝，控制了模型的复杂程度
传统的GBDT算法以CART作为基分类器，xgboost还可以支持线性分类器，相当于带L1和L2的逻辑斯谛回归或者线性回归
传统的GBDT在优化的时候，使用的是一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶导数和二阶导数。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。
xgboost在代价函数中加入了正则项，用于控制模型的复杂度。正则项里面包括树的叶子节点的个数、每个叶子节点上输出的score的L2模的平方和。（ 从Bias-variance tradeoff 的角度来说，正则化降低了模型的variance，使得到的模型更加简单，防止过拟合，这是xgboost优于传统的GBDT的一个特征）
Shrinkage（缩减），相当于学习速率（xgboost中的eta）。xgboost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点。（sklearn中的GBDT的实现也有学习速率）
列抽样（column sampling),借鉴了随机森林的做法，支持列抽样可以降低过拟合，同时减少了计算量，这也是xgboost异于传统gbdt的一个特性
对缺失值的处理。对于样本有特征确实的情况下，xgboost可以自动学习它的分裂方向。
xgboost工具支持并行。xgboost的并行并不是tree粒度的并行，xgboost也是需要一次迭代完成之后，才能进行下一次迭代的。（第t次迭代的代价函数包含了前面t-1次的预测值）。xgboost的并行是特征粒度上的。决策树的学习最耗时的步骤是就是对特征进行排序（因为要确定最佳的分割点），xgboost在训练之前，预先对数据进行排序，然后保存成block结构，后面的迭代中重复的使用这个结构，大大的减少了计算量。这个结构也使并行成为可能。在进行节点分裂时，需要计算每个特征的信息增益，最终选择增益最大的那个特征去分裂，那么各个特征的增益计算就可以开多线程计算。
可并行的近似直方图算法。树节点在进行分裂时，需要计算每个特征的的每个分裂点的信息增益，即用贪心法枚举所有的可能的分割点。当数据无法一次性载入内存或者在分布式的情况下，贪心的算法效率就会变得很低，所以xgboost还提出了一种，可并行的近似直方图算法，用于高效的生成候选的分割点。
总结下来就是两者的区别：
xgboost里面的基学习器除了用tree(gbtree)，也可用线性分类器(gblinear)。而GBDT则特指梯度提升决策树算法。
xgboost相对于普通gbm的实现，可能具有以下的一些优势：
显式地将树模型的复杂度作为正则项加在优化目标
公式推导里用到了二阶导数信息，而普通的GBDT只用到一阶
允许使用column(feature) sampling来防止过拟合，借鉴了Random Forest的思想。（sklearn里的gbm好像也有类似实现）
实现了一种分裂节点寻找的近似算法，用于加速和减小内存消耗。
节点分裂算法能自动利用特征的稀疏性。
data事先排好序并以block的形式存储，利于并行计算
penalty function Omega主要是对树的叶子数和叶子分数做惩罚，这点确保了树的简单性
支持分布式计算可以运行在MPI，YARN上，得益于底层支持容错的分布式通信框架rabit。
3、决策树C4.5
C4.5是决策树算法的一种。决策树算法作为一种分类算法，目标就是将具有p维特征的n个样本分到c个类别中去。常见的决策树算法有ID3,C4.5,CART。
算法流程为：
while (当前节点”不纯“)
(1)计算当前节点的类别信息熵Info(D) （以类别取值计算）
(2)计算当前节点各个属性的信息熵Info(Ai) （以属性取值下的类别取值计算）
(3)计算各个属性的信息增益Gain(Ai)=Info(D)-Info(Ai)
(4)计算各个属性的分类信息度量H(Ai) （以属性取值计算）
(5)计算各个属性的信息增益率IGR(Ai)=Gain(Ai)/H(Ai)
end while
当前节点设置为叶子节点
4、CART算法
ID3：特征划分基于信息增益
C4.5：特征划分基于信息增益比
CART：特征划分基于基尼指数
CART算法由以下两步组成：
决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；
决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时损失函数最小作为剪枝的标准。
5、K-邻近算法/kNN
基本思想
kNN的思想很简单：在训练集中选取离输入的数据点最近的k个邻居，根据这个k个邻居中出现次数最多的类别（最大表决规则），作为该数据点的类别。kNN算法中，所选择的邻居都是已经正确分类的对象。
算法复杂度
kNN是一种lazy-learning算法，分类器不需要使用训练集进行训练，因此训练时间复杂度为0；kNN分类的计算复杂度和训练集中的文档数目成正比，也就是说，如果训练集中文档总数为n，那么kNN的分类时间复杂度为O(n)；因此，最终的时间复杂度是O(n)。
优点
理论成熟，思想简单，既可以用来做分类也可以用来做回归 ；
适合对稀有事件进行分类（例如：客户流失预测）；
特别适合于多分类问题(multi-modal,对象具有多个类别标签，例如：根据基因特征来判断其功能分类)， kNN比SVM的表现要好。
缺点
当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数；
计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点；
可理解性差，无法给出像决策树那样的规则。
6.Apriori算法
先验算法（Apriori Algorithm）是关联规则学习的经典算法之一。先验算法的设计目的是为了处理包含交易信息内容的数据库（例如,顾客购买的商品清单，或者网页常访清单。）而其他的算法则是设计用来寻找无交易信息（如Winepi算法和Minepi算法）或无时间标记（如DNA测序）的数据之间的联系规则。
在关联式规则中,一般对于给定的项目集合（例如，零售交易集合，每个集合都列出的单个商品的购买信息），算法通常尝试在项目集合中找出至少有C个相同的子集。先验算法采用自底向上的处理方法，即频繁子集每次只扩展一个对象（该步骤被称为候选集产生），并且候选集由数据进行检验。当不再产生匹配条件的扩展对象时，算法终止。
7、SVM算法
SVM(Support Vector Machine)中文名为支持向量机，是常见的一种判别方法。在机器学习领域，是一个有监督的学习模型，通常用来进行模式识别、分类以及回归分析。
svm算法通俗的理解在二维上，就是找一分割线把两类分开，哪条线是最优的呢，这就是我们要考虑的问题
8、朴素贝叶斯算法
朴素：特征条件独立；贝叶斯：基于贝叶斯定理。属于监督学习的生成模型，实现简单，没有迭代，并有坚实的数学理论（即贝叶斯定理）作为支撑。在大量样本下会有较好的表现，不适用于输入向量的特征条件有关联的场景。
假设某个体有n项特征（Feature），分别为F1、F2、…、Fn。现有m个类别（Category），分别为C1、C2、…、Cm。贝叶斯分类器就是计算出概率最大的那个分类。
9、EM算法
EM出现的原因就是抽取的样本不知道是哪个分布抽取的。例如刚开始的最大似然所说的，但现在两种高斯分布的人混在一块了，我们又不知道哪些人属于第一个高斯分布，哪些属于第二个，所以就没法估计这两个分布的参数。反过来，只有当我们对这两个分布的参数作出了准确的估计的时候，才能知道到底哪些人属于第一个分布，那些人属于第二个分布。所以这里就是说EM估计就是因为多了一个隐含变量（抽取得到的每个样本都不知道是从哪个分布抽取的）使得本来简单的可以求解的问题变复杂了。
这里简单的思路就是先初始化隐含变量，然后估计出每个类别对应的分布参数。然后再根据这个分布参数去调整每个样本的隐含参数，依次迭代。。。至于为什么最后能够迭代成功，就是因为在后面的似然函数的证明中可以证明似然函数最后就是一个单调函数
10、K-Means算法
在k-means算法中，用cluster来表示簇；容易证明k-means算法收敛等同于所有质心不再发生变化。
基本的k-means算法流程如下：
选取k个初始质心（作为初始cluster，每个初始cluster只包含一个点）；
repeat：
对每个样本点，计算得到距其最近的质心，将其类别标为该质心所对应的cluster；
重新计算k个cluster对应的质心（质心是cluster中样本点的均值）；
until 质心不再发生变化
11、随机森林
机器学习算法之随机森林算法工作原理
随机森林是一种有监督学习算法。 就像你所看到的它的名字一样，它创建了一个森林，并使它拥有某种方式随机性。 所构建的“森林”是决策树的集成，大部分时候都是用“bagging”方法训练的。 bagging方法，即bootstrap aggregating，采用的是随机有放回的选择训练数据然后构造分类器，最后组合学习到的模型来增加整体的效果。
简而言之：随机森林建立了多个决策树，并将它们合并在一起以获得更准确和稳定的预测。随机森林的一大优势在于它既可用于分类，也可用于回归问题，这两类问题恰好构成了当前的大多数机器学习系统所需要面对的。 接下来，将探讨随机森林如何用于分类问题，因为分类有时被认为是机器学习的基石。 下图，你可以看到两棵树的随机森林是什么样子的：
除了少数例外，随机森林分类器使用所有的决策树分类器以及bagging 分类器的超参数来控制整体结构。 与其先构建bagging分类器，并将其传递给决策树分类器，您可以直接使用随机森林分类器类，这样对于决策树而言，更加方便和优化。要注意的是，回归问题同样有一个随机森林回归器与之相对应。
12、自编码器
什么是自编码器（Autoencoder）
自编码器
自动编码器是一种数据的压缩算法，其中数据的压缩和解压缩函数是数据相关的、有损的、从样本中自动学习的。在大部分提到自动编码器的场合，压缩和解压缩的函数是通过神经网络实现的。
自编码是一种表示学习的技术，是deep learning的核心问题
让输入等于输出，取中间的一层作为embedding， 即编码
对中间的隐层进行约束，就可以得到不同类型的编码
h<x，这就是普通的降维编码
h>x, 并且约束其稀疏性，就得到稀疏编码
自编码网络，可以理解为，
完成训练后，Decoder部分就没有用了
1）自动编码器是数据相关的（data-specific 或 data-dependent），这意味着自动编码器只能压缩那些与训练数据类似的数据。比如，使用人脸训练出来的自动编码器在压缩别的图片，比如树木时性能很差，因为它学习到的特征是与人脸相关的。
2）自动编码器是有损的，意思是解压缩的输出与原来的输入相比是退化的，MP3，JPEG等压缩算法也是如此。这与无损压缩算法不同。
3）自动编码器是从数据样本中自动学习的，这意味着很容易对指定类的输入训练出一种特定的编码器，而不需要完成任何新工作。
搭建一个自动编码器需要完成下面三样工作：搭建编码器，搭建解码器，设定一个损失函数，用以衡量由于压缩而损失掉的信息。编码器和解码器一般都是参数化的方程，并关于损失函数可导，典型情况是使用神经网络。编码器和解码器的参数可以通过最小化损失函数而优化，例如SGD。
自编码器是一个自监督的算法，并不是一个无监督算法。
自监督学习是监督学习的一个实例，其标签产生自输入数据。要获得一个自监督的模型，你需要一个靠谱的目标跟一个损失函数。基本上，要求模型在像素级上精确重构输入不是机器学习的兴趣所在，学习到高级的抽象特征才是。
目前自编码器的应用主要有两个方面，第一是数据去噪，第二是为进行可视化而降维。配合适当的维度和稀疏约束，自编码器可以学习到比PCA等技术更有意思的数据投影。
对于2D的数据可视化，t-SNE（读作tee-snee）或许是目前最好的算法，但通常还是需要原数据的维度相对低一些。所以，可视化高维数据的一个好办法是首先使用自编码器将维度降低到较低的水平（如32维），然后再使用t-SNE将其投影在2D平面上。
