数据是什么类型，决定了建模的路径该怎么选。在机器学习或人工智能领域，第一步往往是盯着算法的学习方式。目前有几种主流的学习方式值得了解一下。把算法按学习方式归归类，确实是个好主意——这样在建模和选算法时，就能根据输入数据的特点，找到最合适的方案，拿到最好的结果。

1. 监督式学习

监督学习里，输入数据被称为“训练数据”，每组数据都有一个明确的标签或结果——比如垃圾邮件分类中的“垃圾”和“非垃圾”，或者手写数字识别里的“1”“2”“3”“4”。建模时，监督学习会建立一个学习过程，把模型的预测结果和训练数据的实际结果做比较，然后不断调整模型，直到预测准确率达到预期。常见的应用场景包括分类问题和回归问题。代表算法有逻辑回归（Logistic Regression）和反向传播神经网络（Back Propagation Neural Network）。

2. 非监督式学习

非监督学习里，数据没有事先打标签，学习模型的目标是推断数据内部的结构。典型应用有关联规则学习和聚类。常见算法包括Apriori算法和k-Means算法。

3. 半监督式学习

半监督学习的情况是：输入数据部分有标签，部分没有。模型先要学习数据的内在结构，才能合理组织数据去预测。应用场景包括分类和回归，常用的算法是对监督学习算法的延伸——它们先对未标注数据建模，再基于已有标注做预测。例如图论推理算法（Graph Inference）和拉普拉斯支持向量机（Laplacian SVM）等。

4. 强化学习

强化学习里，输入数据直接作为模型的反馈。和监督学习不同，输入不只是用来检查对错，而是直接反馈到模型，模型必须立刻调整。常见应用包括动态系统和机器人控制。代表算法有Q-Learning和时间差学习（Temporal difference learning）。

在企业数据应用中，最常用的还是监督学习和非监督学习模型。而在图像识别等领域，因为存在大量未标注数据和少量标注数据，半监督学习成了一个热门话题。强化学习则更多应用在机器人控制以及其他需要系统控制的场合。

5. 算法类似性

根据算法在功能和形式上的相似性，可以把它们分分类，比如基于树的算法、基于神经网络的算法等。当然，机器学习的范围很大，有些算法很难明确归到某一类。而且同一类里的算法，也可能解决不同类型的问题。这里尽量把常用算法按最容易理解的方式梳理出来。

6. 回归算法

回归算法试图用误差的衡量来探索变量之间的关系。它是统计机器学习的一把利器。在机器学习领域，说到“回归”有时指一类问题，有时指一类算法，初学者容易搞混。常见的回归算法包括：最小二乘法（Ordinary Least Square）、逻辑回归（Logistic Regression）、逐步式回归（Stepwise Regression）、多元自适应回归样条（Multivariate Adaptive Regression Splines）和本地散点平滑估计（Locally Estimated Scatterplot Smoothing）。

7. 基于实例的算法

这类算法常用来对决策问题建模，先选一批样本数据，然后根据某种近似性把新数据和样本数据做比较，找出最佳匹配。因此也被称为“赢家通吃”学习或“基于记忆的学习”。常见算法包括k-Nearest Neighbor (KNN)、学习矢量量化（Learning Vector Quantization，LVQ）和自组织映射算法（Self-Organizing Map，SOM）。

8. 正则化方法

正则化方法是其他算法（通常是回归算法）的延伸，它根据算法的复杂度进行调整。通常对简单模型给予奖励，对复杂算法给予惩罚。常见算法包括Ridge Regression、LASSO（Least Absolute Shrinkage and Selection Operator）和弹性网络（Elastic Net）。

9. 决策树学习

决策树算法根据数据的属性，用树状结构建立决策模型，常用于分类和回归。常见算法包括：分类及回归树（CART）、ID3、C4.5、CHAID、Decision Stump、随机森林（Random Forest）、多元自适应回归样条（MARS）和梯度推进机（GBM）。

10. 贝叶斯方法

贝叶斯方法基于贝叶斯定理，主要解决分类和回归问题。常见算法包括朴素贝叶斯、平均单依赖估计（AODE）和贝叶斯信念网络（BBN）。

11. 基于核的算法

基于核的算法中，最著名的当属支持向量机（SVM）。它将输入数据映射到高维向量空间，在这个空间里分类或回归问题往往更容易解决。常见算法包括支持向量机（SVM）、径向基函数（RBF）和线性判别分析（LDA）。

12. 聚类算法

聚类和回归类似，有时指一类问题，有时指一类算法。聚类算法按中心点或分层的方式对输入数据进行归并。所有聚类算法都试图找到数据的内在结构，以便按最大的共同点进行分类。常见算法包括k-Means和期望最大化算法（EM）。

13. 关联规则学习

关联规则学习通过寻找能解释数据变量之间关系的规则，从大量多元数据集中找出有用的关联。常见算法包括Apriori和Eclat。

14. 人工神经网络

人工神经网络模拟生物神经网络，属于模式匹配算法，常用于分类和回归。它是机器学习的一个庞大分支，有几百种算法（深度学习是其中一类，会单独讨论）。重要算法包括感知器神经网络、反向传播、Hopfield网络、自组织映射（SOM）和学习矢量量化（LVQ）。

15. 深度学习

深度学习是人工神经网络的发展，近年来备受关注。计算能力越来越便宜，使深度学习能建立更大更复杂的神经网络。很多深度学习算法是半监督的，用来处理存在少量未标注数据的大数据集。常见算法包括受限玻尔兹曼机（RBM）、深度信念网络（DBN）、卷积网络和堆栈式自动编码器。

16. 降低维度算法

和聚类算法类似，降低维度算法也试图分析数据的内在结构，但它是用非监督的方式，用较少的信息来归纳或解释数据。这类算法可用于高维数据的可视化，或者简化数据以便监督学习使用。常见算法包括主成分分析（PCA）、偏最小二乘回归（PLS）、Sammon映射、多维尺度（MDS）和投影追踪。

17. 集成算法

集成算法用一些相对弱的学习模型独立地对同一批样本训练，然后把结果整合起来做整体预测。难点在于集成哪些弱模型，以及如何整合结果。这类算法非常强大，也相当流行。常见算法包括Boosting、Bagging、AdaBoost、堆叠泛化（Blending）、梯度推进机（GBM）和随机森林（Random Forest）。

常见机器学习算法优缺点

朴素贝叶斯

1. 如果特征向量长度不同，需要归一化成统一长度（以文本分类为例）。比如以句子中的单词为特征，则长度为整个词汇量大小，对应位置是该单词出现的次数。

2. 计算公式如下：

其中一项条件概率可以通过朴素贝叶斯条件独立展开。注意的计算方法，由朴素贝叶斯的前提假设可知=。一般有两种计算方式：一是在类别为ci的样本集中，找到wj出现次数的总和除以该样本总数；二是找到wj出现次数的总和除以该样本中所有特征出现次数的总和。

3. 如果中的某一项为0，则联合概率乘积可能为0。为避免这种情况，一般初始化为1，分母对应初始化为2（因为是2类，加2；如果是k类则加k，即Laplace平滑，分母加k是为了满足全概率公式）。

优点：对小规模数据表现好，适合多分类任务，支持增量训练。

缺点：对输入数据的表达形式很敏感。

决策树

决策树的关键在于选择哪个属性进行分枝，因此需要理解信息增益的计算公式。

信息熵计算公式：

其中n代表有n个分类类别（比如二分类则n=2）。分别计算这2类样本在总样本中间出现的概率p1和p2，得到未选中属性分枝前的信息熵。

选中一个属性xi用于分枝：如果xi=vx，样本分到一个分支，否则进入另一个分支。分支中的样本可能包含两个类别，分别计算两个分支的熵H1和H2，得到分枝后的总熵H'=p1*H1+p2*H2，信息增益ΔH=H-H'。将所有属性测试一遍，选择使增益最大的属性作为本次分枝属性。

优点：计算量小，可解释性强，适合处理有缺失属性值的样本，能处理不相关特征。

缺点：容易过拟合（后续随机森林减小了过拟合）。

Logistic回归

Logistic用于分类，是一种线性分类器。需要注意：

1. logistic函数表达式：

其导数形式：

2. logistic回归用最大似然估计学习。单个样本的后验概率：

整个样本的后验概率：

其中：

通过对数进一步化简：

3. 其loss function为-l(θ)，需使loss function最小，可用梯度下降法。梯度下降公式：

优点：1. 实现简单；2. 分类计算量小，速度快，存储资源低。

缺点：1. 容易欠拟合，准确度一般不高；2. 只能处理二分类（衍生softmax可用于多分类），且必须线性可分。

线性回归

线性回归真正用于回归，而不是分类。基本思想是用梯度下降法优化最小二乘形式的误差函数，也可以用normal equation直接求解参数：

在LWLR（局部加权线性回归）中，参数计算式为：

因为此时优化的是：

可见LWLR是非参数模型，每次回归计算都要遍历训练样本至少一次。

优点：实现简单，计算简单。

缺点：不能拟合非线性数据。

KNN算法

KNN即最近邻算法，主要过程：

1. 计算训练样本和测试样本中每个样本点的距离（常见度量有欧式距离、马氏距离等）。

2. 对所有距离值排序。

3. 选前k个最小距离的样本。

4. 根据这k个样本的标签投票得到分类类别。

如何选择最佳k值？取决于数据。分类时较大的k值能减小噪声影响，但会使类别界限模糊。好的k值可通过交叉验证等启发式技术获取。噪声和非相关特征向量会降低KNN准确性。

近邻算法具有较强的一致性结果：数据趋于无限时，错误率不超过贝叶斯算法错误率的两倍。对于好的k值，KNN保证错误率不超过贝叶斯理论误差率。

注：马氏距离需要先给出样本集的统计性质（均值向量、协方差矩阵等）。马氏距离介绍如下：

优点：1. 思想简单，理论成熟，可用于分类和回归；2. 可用于非线性分类；3. 训练时间复杂度O(n)；4. 准确度高，对数据无假设，对outlier不敏感。

缺点：1. 计算量大；2. 样本不平衡问题；3. 需要大量内存。

SVM

要学会使用libsvm及参数调节经验，同时理清SVM算法思路：

1. SVM中的最优分类面是对所有样本的几何间隔最大（为什么选最大间隔分类器？从数学角度：几何间隔与样本误分次数存在关系，分母是样本到分类间隔距离，分子R是所有样本中最长向量值）。即：

经过推导可得原始优化目标：

2. 拉格朗日理论：

将1中的目标转换为拉格朗日形式（通过对偶优化、KKT条件），最终目标函数为：

只需最小化上述函数，其中α为原始优化问题中的不等式约束拉格朗日系数。

3. 对2中最后式子分别对w和b求导得：

由第一个式子可知，优化出α后可直接求出w。第二个式子可作为后续优化的约束条件。

4. 对2中最后一个目标函数用对偶优化理论可转换为：

这个函数可用常用优化方法求得α，进而得到w和b。

5. 预测时：

尖括号可用核函数代替，这也是SVM常和核函数绑在一起的原因。

6. 引入松弛变量后，原始目标：

对应的对偶优化：

与前相比α多了上界。

优点：1. 可用于线性/非线性分类，也可用于回归；2. 低泛化误差；3. 容易解释；4. 计算复杂度较低。

缺点：1. 对参数和核函数的选择敏感；2. 原始SVM只擅长二分类。

Boosting

以Adaboost为例，流程图如下：

训练过程中需要训练多个弱分类器（图中3个），每个弱分类器由不同权重的样本（图中5个训练样本）训练得到。第一个弱分类器对应的输入样本权值相同，每个弱分类器对最终分类结果的作用也不同，通过加权平均输出，权值见图中的三角形数值。

这些弱分类器和对应权值如何训练？以5个训练样本为例，每个样本维度为2。训练第一个分类器时5个样本权重均为0.2。注意样本权值和最终弱分类器的权值α不同：样本权重只在训练过程中用到，α在训练和测试中都用到。

假设弱分类器是一个带一个节点的简单决策树，它选择两个属性中的一个，计算出最佳值用于分类。

Adaboost简单训练过程：

1. 训练第一个分类器，样本权值D均相同。通过弱分类器得到5个样本的预测标签，与真实标签对比产生误差。若样本预测错误，错误值为该样本权重；正确则错误值为0。累加5个样本错误率之和，记为ε。

2. 通过ε计算弱分类器权重α，公式：

3. 通过α计算下一个弱分类器的样本权值D：若样本分类正确，减小其权重，公式：

若分类错误，增加其权重，公式：

4. 循环步骤1,2,3训练多个分类器，每次D值不同。

测试过程：将样本输入每个训练好的弱分类器，每个输出标签乘以对应α，求和后符号即为预测标签。

优点：1. 低泛化误差；2. 容易实现，分类准确率较高，参数少。

缺点：对outlier敏感。

聚类

根据聚类思想划分：

1. 基于划分的聚类：K-means、k-medoids（每个类别选一个样本代表）、CLARANS。k-means最小化下式：

优点：（1）经典算法，简单快速；（2）可伸缩且高效，复杂度O(nkt)（n对象数，k簇数，t迭代数，k<

缺点：（1）需要簇的平均值可定义，不适合某些分类属性；（2）需用户指定k；（3）对初值敏感；（4）不适合非凸形状或大小差别大的簇；（5）对噪声和孤立点敏感。

2. 基于层次的聚类：自底向上的凝聚方法（如AGNES）和自上向下的分裂方法（如DIANA）。

3. 基于密度的聚类：DBSCAN、OPTICS、BIRCH（CF-Tree）、CURE。

4. 基于网格的方法：STING、Wa veCluster。

5. 基于模型的聚类：EM、SOM、COBWEB。

推荐系统

推荐系统的实现主要有两种：基于内容和协同滤波。

基于内容：以电影评分为例，可看作回归问题。每部电影提取特征向量x，为每个用户建模，以用户打分为y，用已有评分和特征训练回归模型（常用线性回归），预测未评分的电影。注意需为每个用户建立独立的回归模型。另一种思路：先给定用户对电影类型的喜好程度（权值），学出电影特征，再用回归预测未评分。也可同时优化用户喜好和电影特征。

基于协同滤波（CF）：CF可看作分类问题或矩阵分解问题。它基于“每个人喜好相似”的特征，不依赖个人基本信息。例如电影评分预测只依赖已有评分，无需学习电影特征。

SVD将矩阵分解为三个矩阵的乘积：

中间矩阵sigma为对角矩阵，对角元素为Data矩阵的奇异值（从大到小排列）。即使去掉小特征值，也能很好重构原始矩阵，如下图：

颜色深的部分代表去掉小特征值后重构的三个矩阵。若m代表商品数，n代表用户数，U矩阵每一行代表商品属性。降维后每个商品属性可用更低维度（k维）表示。新用户推荐向量X，可根据公式X'*U1*inv(S1)得到k维向量，在V'中找最相似用户（相似度可用余弦），根据该用户评分推荐未打分商品。

pLSA

pLSA由LSA发展而来，早期LSA通过SVD分解实现。pLSA模型图如下：

公式含义如下：

LDA主题模型

概率图如下：

和pLSA不同，LDA假设了很多先验分布，且一般参数先验分布设为Dirichlet分布，因为共轭分布先验和后验形式相同。

GBDT

GBDT（Gradient Boosting Decision Tree）又称 MART（Multiple Additive Regression Tree），阿里内部用得较多。它是一种迭代的决策树算法，由多棵决策树组成，所有树的输出累加得到最终答案。它和SVM一样被认为是泛化能力较强的算法，近年因用于搜索排序的机器学习模型而备受关注。GBDT是回归树，不是分类树。核心在于每棵树从之前所有树的残差中学习。为防止过拟合，类似Adaboost也加入了boosting项。

Regularization（正则化）作用

1. 数值上更容易求解；2. 特征数目太大时更稳定；3. 控制模型复杂度、光滑性；复杂度小且光滑的目标函数泛化能力强；4. 减小参数空间，参数空间越小复杂度越低；5. 系数越小模型越简单，泛化能力越强（Ng宏观解释）；6. 可视为权值的高斯先验。

异常检测

可以估计样本的密度函数，新样本密度小于某阈值则异常。密度函数一般采用多维高斯分布。若样本有n维，可将每个特征变换为高斯分布（如x=log(x+c)或x=x^(1/c)）。算法流程：

ε通过交叉验证得到。p(x)的学习用无监督，ε学习用有监督。为什么不直接用有监督的二分类？因为异常样本太少，正常样本太多，不足以学到好的异常模型，新异常样本可能与训练样本模式完全不同。

EM算法

当样本产生与隐含变量有关（隐含变量不可观测），用最大似然估计求参数时，因含有隐含变量，无法直接对似然函数求导，此时可用EM算法求参数。

E步：选一组参数，求出该参数下隐含变量的条件概率。

M步：结合E步求出的隐含变量条件概率，求似然函数下界函数（某个期望函数）的最大值。

重复直至收敛。公式如下：

M步下界函数的推导过程：

一个常见例子是GMM模型：每个样本可能由k个高斯产生，概率不同。隐含变量就是每个样本对应的某个高斯分布。GMM的E步公式（计算每个样本对应每个高斯的概率）：

更具体：

M步公式（计算每个高斯的比重、均值、方差）：

Apriori

Apriori是关联分析中较早的方法，用于挖掘频繁项集。思想：1. 若项目集合不是频繁集，则任何包含它的项目集也不是频繁集；2. 若项目集是频繁集，则其非空子集也是频繁集。Apriori需多次扫描项目表：从一个项目开始，舍去非频繁项目，得到L；对L中每个元素自组合，生成比上次多一个项目的集合C，再扫描去除非频繁，重复。

示例项目表：

若不去除非频繁项目集，扫描树形结构：

其中可能出现的非频繁项目集用阴影表示：

FP Growth

FP Growth比Apriori更高效，只需扫描项目表2次。第一次扫描获得单个项目频率，去掉不符合支持度要求的项并排序；第二次扫描建立FP-Tree（frequent-patten tree）。接下来在FP-Tree上挖掘。例如下表：

对应的FP_Tree：

从频率最小的单项P开始，找出P的条件模式基，用构造FP_Tree的方法构造P的条件模式基的FP_Tree，找出包含P的频繁项集。然后依次从m、b、a、c、f的条件模式基上挖掘，有些项需递归挖掘（如m节点）。