ML Model Zoo


本文对常见的机器学习模型进行小结，包括线性回归（Linear Regression）、逻辑斯蒂回归（Logistic Regression）、感知机（Perceptron）、朴素贝叶斯（Naive Bayes）、决策树（Decision Tree）、集成模型（Ensemble）、聚类算法（Clustering）、支持向量机（Support Vector Machine）。神经网络（Neural Network）相关请参考 A Neural Net Example、Deep Learning Notes。


目录

线性回归（Linear Regression）

基本模型

线性回归是机器学习和统计学中基本的线性模型，适用于回归任务。

$$ F(x) = wx + b $$

\(x\)是模型输入，\(w,b\)是模型参数

模型优化

线性回归使用最小二乘法进行优化，其损失函数也成为均方差损失函数（Mean Square Error）。基本形式如下：

$$ L(w, b) = \sum_{i=1}^{N}\left(y_{i} - (wx_{i} + b)\right)^2 $$

该最小化损失函数几何上的意义是：找到一条直线，使所有样本点到该直线在欧式空间下的距离总和最小。 也可以从极大似然估计的角度推导出该损失函数，详细推导见 ML Q&A 里面的 Q：线性回归（Linear Regression）为什么使用均方差作为损失函数？

泛化能力

对于线性回归，可以通过在均方差损失函数中加入 L1 或 L2 正则项进行正则化，提高模型泛化能力。损失函数中加入 L1 正则项，则成为 LASSO 算法，其损失函数形式如下：

$$ C=\frac{1}{N}\sum_{i=1}^N L(y_i,f(x_i)) + \lambda \sum_w \left\| w\right\| $$

加入 L2 正则项，则成为 Ridge 回归算法，其损失函数形式为：

$$ C=\frac{1}{N}\sum_{i=1}^N L(y_i,f(x_i))+\frac{\lambda}{2} \sum_w \left\| w\right\|^2$$

如果同时加入 L1 和 L2 正则项，则成为 ElasticNet 回归算法，其损失函数形式为：

$$ C=\frac{1}{N}\sum_{i=1}^N L(y_i,f(x_i))+ \lambda_1 \sum_w \left\| w\right\| + \frac{\lambda_2}{2} \sum_w \left\| w\right\|^2$$

LASSO 和 Ridge 的区别

  1. 从损失函数的形式上看，LASSO 的损失函数是线性回归加上 L1 正则项，Ridge 的损失函数则是加上了 L2 正则项
  2. 从理论推导上，假定误差服从正态分布，则可以通过极大似然估计推导出最小二乘法；在此基础上如果假定参数 w 服从正态分布，则可以推导出 Ridge 回归；如果假定参数 w 服从拉普拉斯分布，则可以推导出 LASSO
  3. 从模型效果上来说，L2 正则的 Ridge 使参数普遍变小，L1 正则的 LASSO 参数更加稀疏。实践中，通常两者效果不会差太多，有时 Ridge 稍微好点， LASSO 可以用于特征选择。


逻辑斯谛回归（Logistic Regression）

基本模型

逻辑斯谛回归是机器学习中经典的分类模型，属于对数线性模型。本质上是对训练样本中正例负例的对数几率作线性回归（对数是 logit，回归是 regression，因此叫 Logistics Regression），模型将对输入 \(x\) 作线性变化 \(h(x)=wx+b\)，再通过逻辑斯谛函数得到模型的输出：

$$F(x)=\frac{1}{1+e^{-(wx + b)}}$$

\(x\)是模型输入，\(w,b\)是模型参数

逻辑斯谛函数图形是一条 S 型曲线(Sigmoid Curve)，因此也称 Sigmoid 函数。Sigmoid 曲线单调递增，以(0, 0.5)中心对称，在中心附近增长较快，在两端增长放慢。当输入线性变换后的值 h»0 时，输出概率无限接近 1，h«0 时无限接近 0。

模型优化

LR 模型可以解释为概率模型，也可以解释为非概率模型。 以概率模型的观点，LR 将输入（通过线性变化和逻辑斯谛函数）映射为一个分类概率，使用 极大似然估计法 估计模型参数。

令分类概率：

$$ \pi(x_i)=P(y=1 \mid x;w,b)=\frac{1}{1+e^{-(w x + b)}}$$

似然：

$$ L(w)\prod_{i=1}^N \pi(x_i)^{y_i} \left( 1-\pi(x_i) \right) ^{1-y_i}$$

对数似然：

$$ \log{L(w)}=\sum_{i=1}^N y_i \log{\pi(x_i)} + (1-y_i)\log{(1-\pi(x_i))}$$

对参数 \(w\) 进行 极大似然估计 即可。通常将损失函数定义为负对数似然，然后基于梯度下降算法最小化损失函数。

从非概率模型的观点出发，LR 是通过交叉熵损失函数定义模型经验风险，并通过最小化经验风险优化模型。

最小化经验风险和极大似然估计在 LR 模型中本质上是相同的，只是解释的角度不同。最后推导得到的求解问题属于无约束优化问题，可以使用随机梯度下降算法(SGD)或拟牛顿法求解。

泛化能力

对于 LR，通常在损失函数中加入 L2 正则项提高模型泛化能力，加入 L2 正则项的代价函数表达式如下：

$$ C=\frac{1}{N}\sum_{i=1}^N L(y_i,f(x_i))+\frac{\lambda}{2} \sum_w \left\| w\right\|^2$$

其中第一项为损失函数(经验风险)，第二项为模型复杂度，\(\lambda \geq 0\)为正则系数。

NOTE

  1. LR 模型的输出不是正例的概率，而是正负例的对数几率，可以理解为一种可能性。可能性越大，正例的概率越大。
  2. LR 和 Linear Regression 的区别：Linear Regression 在整个实数域内回归，并且整个实数域内回归敏感度一致，而 LR 在[0, 1]区间回归，由于逻辑斯谛函数特性使得其在 h=0 时十分敏感，在 h » 0 或 h « 0 处不敏感。
  3. LR 模型非常简单，可解释性强，经过训练能得到各个特征的权重（重要程度），对于高维度（上亿维）的数据仍有不错的性能，在实际场景中应用广泛。
  4. LR 属于判别模型，对条件概率 \(P(y\mid X)\) 进行建模。
  5. LR 属于线性模型，可以应用核技巧转化为非线性模型。


感知机（Perceptron）

感知机(Perceptron)是一种简单的线性二分类模型，模型输出为：

$$f(x)=\text{sign}(wx+b)$$

其本质在特征空间中划分一个分类超平面\(wx+b=0\)，使得误分类点到超平面的总距离最小。 其损失函数（经验风险）定义为：

$$L(w,b)=-\sum_{x_i\subseteq M}y_i(wx_i+b)$$

M 是误分类点集合

感知机模型学习策略是最小化误分类点到分类超平面的总距离，学习算法可以使用随机梯度下降法(SGD)。

NOTE

  • 感知机属于线性模型，对于非线性数据效果较差。当数据线性可分时，算法保证收敛，但存在无穷多个解（取决于训练数据的顺序和参数的初始值设置）
  • 感知机属于判别模型，对条件概率 \(P(y\mid X)\) 进行建模。
  • Demo: Perceptron


朴素贝叶斯（Naive Bayes）

朴素贝叶斯是一种基于贝叶斯定理的多分类模型，利用贝叶斯定理基于样本估计联合概率分布\(P(X,Y)\)，进而得到后验概率 \(P(Y\mid X)\)，最后将样本划分到后验概率最大的类别中。朴素贝叶斯算法优化思想是最大化后验概率。

$$P(Y \mid X)=\frac{P(X \mid Y)P(Y)}{P(X)}$$

其中先验概率 \(P(Y)\) 直接由训练数据得到，条件概率\(P(X \mid Y)\)可以通过极大似然估计得到，由于对于所有样本分母 \(P(X)\) 都是相同的，因此只需比较分子，即：

$$y=argmax P(X \mid Y)P(Y)$$

严格估计条件概率 \(P(X \mid Y)\)实际上是不可行的（指数数量级的参数），因此朴素贝叶斯对条件概率分布做了条件独立性的假设：

$$\begin{aligned} P(X=x \mid Y=y_k)&=P(X^{(1)}=x^{(1)},...,X^{(n)}=x^{(n)} \mid Y=y_k)\\ &=\prod_{i=1}^{n}P(X^{(i)}=x^{(i)} \mid Y=y_k) \end{aligned}$$

这是一个比较强的假设，直接使得\(P(X \mid Y)\)的可以被估计（“朴素”由此得名）。也因为这个假设，当特征之间相关性比较高时朴素贝叶斯效果往往较差（不过实际中特征之间往往会相互抵消掉一部分相关性，使得朴素贝叶斯在多数情况下也可以 work）。

NOTE

  • 极大似然估计时可能会出现概率为 0 的情况，可以采用拉普拉斯平滑，在估计时计数加 1，避免 0 概率的出现。在样本数量足够多的情况下不会对分类结果产生太大影响。
  • 朴素贝叶斯模型是典型的生成模型，模型尝试去拟合数据的联合分布概率 P(X,Y)，因而可以使用拟合到的模型合成数据。
  • 朴素贝叶斯将样本划分到后验概率最大的类中（最大化后验概率），等价于采用 0-1 损失函数时的期望风险最小化。
  • 总体而言，朴素贝叶斯模型简单高效，对于小数据集表现良好，并且对缺失数据不太敏感。


决策树（Decision Tree）

决策树是机器学习中常见的一种分类与回归模型，决策树是一种树型结构，可以理解为是 if-then 规则的集合，也可以理解为定义在特征空间与类空间上的条件概率分布。通常决策树学习包含三个步骤：特征选择、决策树的生成和决策树的修剪。

特征分裂选择

分类决策树特征以及分裂点的选择是根据信息增益或信息增益比或基尼指数。（信息增益、信息增益比最大，基尼指数最小）

1. 信息增益（ID3 算法）

信息增益指按照某个属性进行划分后的熵减程度，信息增益 = 划分前信息熵 - 划分后各子集的信息熵之和

$$ Ent(D) = -\sum_{k=1}^{K}p_k \log{p_k} $$ $$ Gain(D, a) = Ent(D) - \sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v) $$

其中 D 为数据集，k 为类别，a 为某一属性，v 为按照属性 a 划分后的各个子集

\(Ent(D)\) 可以理解为划分前分类的不确定性，第二项为划分后子集的信息熵之和（不确定性），划分越纯(正确区分不同样本)，第二项值越低，则信息增益越高。

2. 信息增益比（C4.5 算法）

按照信息增益划分的方法的缺点是会倾向于选择取值较多的属性，使用信息增益比进行划分可以修正这一问题。信息增益比的表达式如下

$$ Gain\_ratio(D, a) = \frac{Gain(D, a)}{IV(a)} $$ $$ IV(a) = -\sum_{v=1}^{V}\frac{|D^v|}{|D|} \log{\frac{|D^v|}{|D|}} $$

其中 IV(a) 为属性 a 的固有值，样本越多，取值越大

NOTE：由于信息增益比对取值较少的属性有所偏好，因此 C4.5 中采取了启发式的方法：首先通过信息增益找出高于平均值的属性，再通过信息增益比找出其中最佳的属性。

3. 基尼指数（CART 算法）

基尼指数是另外一种度量纯度的指标，其基本公式为：

$$ Gini(D) = 1 - \sum_{k=1}^{K}p_k^2 $$ $$ Gini\_index(D, a) = \sum_{v=1}^{V} \frac{|D^v|}{|D|} Gini(D^v)$$

其中 Gini(D) 为数据集 D 的基尼值，数据集纯度越高，则基尼值越。基尼指数表明了按照属性 a 划分后的各个子集的基尼值之和。基尼指数最低表明对应属性划分后各子集纯度最高

分类决策树特征分裂选择小结

分类决策树本质上就是根据划分后子集纯度进行属性选择，划分后纯度越高，则该划分越好。只是对于纯度的衡量有不同的指标。主要两大类有：

  1. 信息熵（信息熵越低，纯度越高）
    • 信息增益 = 划分前信息熵 - 划分后各子集的信息熵之和
  2. 基尼指数（基尼指数越低，纯度越高）
    • 基尼指数 = 划分后各子集的基尼指数之和
回归决策树特征分裂选择

回归决策树将分裂前后平方和误差（SSE）作为分裂依据，选择分裂后平方和误差降低最多的特征及分裂点。

$$ SSE(D) = \sum_{i \in D}(y_i - \bar{y})^2 $$ $$ \Delta SSE(a) = SSE(D) - \sum_{v=1}^{V} \frac{|D^v|}{|D|} SSE(D^v)$$

其中 \(\bar {y}\) 是数据集中所有样本的平均 y 值，v 为按照属性 a 划分后的各个子集

决策树生成

决策树的生成通常利用信息增益、信息增益比、基尼指数为指标，不断选择最优节点。从根节点开始，递归地产生决策树。

防止过拟合（剪枝）

剪枝可以分为预剪枝和后剪枝，两者区别如下：

  1. 预剪枝 通过边构建树边判断是不是分裂后泛化性能变差，如果变差则停止分裂，将该节点作为叶子节点。
    • 缺点：过于贪婪，有时某个节点划分虽然会暂时地降低泛化性能，但是可能提高全局的泛化性能。预剪枝在这种情况下会剪掉，因此有欠拟合的风险。
    • 优点：有效防止过拟合，由于避免了很多不必要的节点分裂，可以节省训练开销
  2. 后剪枝 构建完成一颗完整的树，使用验证集自底向上考察非叶子结点，如果某个节点替换成叶子节点能够带来泛化性能的提升，则替换为叶子节点
    • 缺点：训练开销相比预剪枝大
    • 优点：欠拟合风险小，泛化性能通常比预剪枝好

连续值和缺失值的处理

  1. 连续值处理
  2. 对连续的 n 个值进行排序，每相邻的两个取值有一个分界点，总共有 n-1 个分界点

  3. 依次计算按照 n-1 个分界点划分的信息增益，选择最大的分界点

  4. 缺失值处理 在计算信息增益的时候可以只根据非缺失部分的数据计算信息增益，因此决策树可以比较好的处理缺失值。

NOTE

  • 决策树模型学习本质：最大化（正则化的）后验概率，采用极大似然估计，最小化损失函数对数似然损失加模型复杂度，其学习策略是基于启发式算法，通过特征选择、生成、剪枝启发式进行正则化的极大似然估计；
  • 决策树属于判别模型，对条件概率进行建模；
  • 优点是模型简单、模型具有可解释性、通常对数据类型没有限制，对训练数据量要求不高；
  • 缺点是单棵树无法预测非常准确（因为树是贪婪逐步构建的），并且通常是单棵树是不稳定的（训练数据的一点小变化可能会对结果造成非常大的影响）。通常对多棵树进行集成（boosting 或 bagging）可以改善这个问题。


支持向量机（Support Vector Machines）

SVM 是一种二分类模型，基本模型是定义在特征空间上的间隔最大的线性分类器，SVM 可以通过引入核方法成为非线性分类器。SVM 基本思路是在特征空间划分一个分类超平面，使得正负类支持向量构成的平面间隔最大化。SVM 的求解可以抽象为一个求解凸二次规划的问题，通常利用拉格朗日对偶性对问题进行转化，使用序列最小最优化(SMO)算法进行求解。

SVM 模型由简至繁包括：线性可分 SVM（硬间隔 SVM），线性 SVM（软间隔 SVM），非线性 SVM（引入核方法）。详细 SVM 推导参考这篇 文章


K-Nearest Neighbors（KNN）

KNN 是一种无参数的度量学习（基于某种距离指标找到最相似的 k 个样本，基于这 k 个样本进行分类或回归（分类就 k 个样本进行（加权）投票，回归就对 k 个样本的值（加权）平均）。

k-NN 三个要素：

  • k 值的选择 （k 小 -> 模型复杂 -> 过拟合)
    • 小 k 值相当于只用较小的领域中的训练数据进行预测，对临近点敏感（若刚好临近点为噪声，则预测出错），k 值小意味着整体模型复杂，容易发生过拟合；
    • 大 k 值相当于用较大的邻域中的数据进行预测，整体模型简单。考虑极端情况 k=N，则无论输入数据是什么，模型都简单预测为训练数据中最多的类（忽略大量信息；
    • 实际中通常使用交叉验证寻找最优的 k 值。

  • 距离度量 曼哈顿距离，欧式距离，切比雪夫(无穷)，闵科夫斯基(general)

  • 聚合规则
    • 分类：多数表决
    • 回归：加权均值或加权中位数

实现方法

使用 KD 树能够省去对大部分节点的搜索，加快检索速度。 KD 树是一种便于对 k 维空间数据进行快速检索的数据结构，他是一种二叉树，表示对 k 维空间的一种划分，将 k 维空间划分成一个个的超矩形区域，每个节点对应一个超矩形区域。

KD 树构建方法： 根节点包含所有数据，从根节点开始，对数据某一维 k，找到中位数作为划分点（保证树的平衡），分裂左右节点，直至划分后的空间不包含任何数据。维度 k 的计算为 k = j(mod c) + 1，其中 j 是节点深度，c 是数据维度。

KD 树搜索方法：

  • 先找到最相似的叶节点（对应一个超矩形区域），然后至下而上直到抵达最近邻的叶子节点，记当前叶子节点与目标点的距离为最小距离。
  • 从叶子节点开始回溯，对于某个节点
    • 如果节点本身到目标点的距离小于最小距离，则更新最小距离
    • 检查该节点的另一子节点是否有更近的点，如果有则往下搜索，如果没有继续回溯
  • 回退到根节点时结束搜索


集成方法（Ensemble Methods）

Ensemble methods 通过构建结合多个弱学习器（基学习器）完成学习任务。一般先通过产生一组弱学习器，再通过某种策略结合起来。学习器之间可以是同构的，也可以是异构的。弱学习器要尽量保证“多样性”和“准确性”。学习器之间结合的策略一般是加权平均（对于连续值）、多数投票（对于分类任务）。

根据弱学习器的生成方式，Ensemble methods 可以分成两大类：

  1. 学习器间存在依赖关系，必须串行生成（Boosting 为代表）
  2. 学习器间不存在依赖关系，可以并行生成（Bagging、随机森林为代表）
ensemble_models


Boosting

对于给定数据集，求比较粗躁的分类比求精确的分类要简单，Boosting 的思路就是学习一系列若分类器（基本分类器，然后组合这些分类器，提高分类性能 主要的 Boosting 方法有 Adaboost 和 GBDT。Adaboost 是通过改变训练数据的概率分布，针对不同的训练数据分布调用一系列不同的弱分类器。GBDT 则是当前的弱学习器学习拟合前面模型的残差。

本质上提升方法采用了加法模型（基函数的线性组合）和前向分步算法。 前向分步加法模型 前向分步加法模型是加法模型，基本思路是从前向后，前面学得的基函数固定，每次只学一个基函数极其系数，逐步逼近优化目标函数式。这样可以简化优化的复杂度（每次只学一个而不是一次性学所有基函数的参数）

  • Adaboost

    Boosting 两个基本问题：1.如何在每轮改变数据的概率（权值）分布； 2.如何将弱分类器组合成强分类器

    第一个问题，Adaboost 的做法是提高前一轮误分类的样本权值，降低正确分类样本的权值。 第二个问题，Adaboost 采用加权多数表决的方法，即正确率高的弱分类器权值大，正确率低的弱分类器权值低。

    Adaboost 流程： 　　概率分布 D -> 学习得到弱分类器 G -> 计算分类误差 e -> 计算 G 的系数 alpha -> 更新分布 D’ -> 构建分类器的线性组合

    Adaboost 核心思想： 　　构建弱分类器，根据前一个分类器的结果调整训练数据分布（提高分类错误的数据的权重），构建下一个弱分类器。Repeat 构建 k 个弱分类器，最终弱分类器加权组合成强分类器

    Adaboost 优缺点： 　　不易过拟合；迭代生成多个弱分类器，逐渐降低 bias；弱分类器必须串行生成算法无法并行；

    具体算法流程：

    AdaBoost

    NOTE:

    • 在第 k 轮的计算中，误分类率为 \(e_k\) ，则在重新计算样本权重时，相当于正确的样本的权重乘上 \(\sqrt{\frac{e_k}{1-e_k}}\)，错误分类的样本权重乘上 \(\sqrt{\frac{1-e_k}{e_k}}\) ，最后再对结果进行归一化得到新的权重。
    • 当 \(e_k\) 大于 0.5 时几种解决方法： 翻转所有样本的分类结果；重新采样训练弱分类器直至 \(e_k\) 小于 0.5；舍弃这个分类器，重新开始 AdaBoost。
    • Adaboost 也可以解释为是 模型为加法模型、损失函数为指数损失 、学习方法为前向分步算法的二分类方法。Adaboost 是前向分步算法的一个特例。


  • 梯度提升决策树（GBDT）

    1. 基本思想 每一次的计算都是为了减少之前模型累加的残差，减少残差的方法是在损失函数减少的梯度上建立一个新模型。即每个新模型的建立都是使先前累加模型损失往梯度方向减少。 核心：使用损失函数的负梯度作为残差的拟合。

    2. 算法流程：

      • 首先确定划分点，计算使得划分后平方损失误差最小的划分点；
      • 根据划分点，拟合划分后的回归树；
      • 得到回归树和实际数据的残差；
      • 接下来重复上面的步骤，不过不是直接拟合数据，而是拟合当前模型的残差； 除了第一次的拟合，后面都是简单地拟合当前模型的残差（当前模型与训练数据的差距），然后得到拟合的残差后再加上当前模型得到新的模型。
    • NOTES：
      • GBDT 中的基学习器都是回归树而不是分类树，但是经过调整后可以用于分类。GBDT 适用于线性/非线性回归，分类，具有较优的抗过拟合性能
      • 某种程度上 GBDT 也有增大分类错误的数据权重的思想，就是如果在某棵子树中某个训练数据的残差很大，后续的学习器会更倾向于学习弥补这个残差，对于残差几乎为 0 的则不太关注了
      • GBDT 一般情况下不能够并行，但是做一些处理之后实际上也是可以并行的（XGBoost），详细见 ML Q&A 里面的 XGBoost 和 GBDT 的比较？
      • 关于 Gradient Boosting 方法的更详细内容，见 Gradient Boosting 这篇 post


Bagging

Boosting 是一种弱分类器间存在强依赖关系，串行生成的集成学习方法。而 Bagging 相反，弱学习器之间不存在强依赖关系，并行式集成学习方法。

基本思路：训练 k 个弱分类器，每个弱分类器的训练数据都是从训练集中 bootstrap sample 得到的，即有放回的采样。因此训练数据可能在某个弱分类器的训练集中重复出现，也可能没有出现。弱学习器训练集的大小可以与原训练数据大小相同，或者略小。

优缺点：速度快；可以不经修改应用于多分类、回归问题；通过 bootstrap sample 增加了弱学习器之间的多样性

  • 随机森林（Random Forest）

    随机森林属于 Bagging 的算法，是以决策树为弱学习器构建 Bagging 的基础上，在决策树的训练过程中引入了随机属性选择。即决策树在选择属性时，不直接选最佳属性，而是先随机选 k 个属性，进而在 k 个里面选最优属性。一般 k 取 log2(特征数)。随机森林在 Bootstrap sample 增加样本扰动的基础上，引入随机属性扰动，进一步增加了弱学习器之间的差异性

    优缺点：

    • 相比传统的决策树，多棵树平均降低了过拟合风险；泛化能力比 Bagging 强。
    • 训练速度快；可并行化；
    • 对于多 feature 的情况不用进行特征选择，并且训练结束后能够给出 feature 的重要程度。

  • 极端随机生成树（Extremely randomize trees） 与随机森林有点相似，也是集成多棵决策树，树和树之间没有依赖性。不同的地方是极端随机生成树每课子树都是使用相同的全部训练数据进行训练；并且选择属性进行节点分裂是完全随机选择； 由于选择节点分裂是完全随机，因此相比随机森林具有更强的随机性。


Stacking

模型融合(Model Stacking)是另外一种集成方法，适用于不同类型的分类器之间的融合（比如 SVM 和决策树的融合）。模型融合涉及到 meta learning，即训练多个基分类器，将多个基分类器的分类结果作为 high level 分类器的输入，将 ground true 结果作为 high level 分类器的标签，本质是由这个 high level 的分类器去学习各个模型的最佳组合（融合）方式。

容易看到这样容易导致 high level 分类器的过拟合，因此通常使用 k-flod 交叉验证防止过拟合。

Stacking


聚类（Clustering）

聚类属于无监督学习算法。常用的算法有 K-Means、高斯混合模型、层次聚类等。

  • k-means（基于划分的方法）：

    1. 随机选择 k 个对象, 每个对象代表一个簇的初始中心
    2. 对剩余所有对象, 根据它与簇中心的距离, 将他指派到最近的簇
    3. 计算每个簇的新中心
    4. 回到步骤 2, 循环直至准则函数收敛

    优化目标：最小化数据点到其所属的类的距离的和 终止条件：簇中心的位置不再发生变化

    优点：算法复杂度较低；对大数据集具有可伸缩性 缺点：必须定义好簇中心；必须给定簇的数目；不适合非凸形状的簇；对噪声和离群点数据敏感；容易陷入局部最优结果(可通过多次不同的簇中心初始化聚类, 对结果进行比较分析)

    k-means++ 算法： 由于经典 k-means 算法每次是随机选取初始簇中心，因此比较容易陷入局部最优，通常需要重复多次，使用不同的初始中心才能跳出局部最优。k-means++ 算法则对选取初始簇中心点的方法做了一点简单的修改，使得初始选择的簇中心之间的距离相对较远，可以较好地缓解陷入局部最优的问题。 具体的初始簇中心选择方法如下：

    1. 随机选取一个样本作为第一个簇中心
    2. 对于每个样本，计算该样本与离其最近的簇中心之间的距离，
    3. 将距离概率化，即距离越大，概率越大，使用这个概率采样得到下一个簇中心
    4. 重复 2-3 步，直至获得 k 个簇中心

    k-means 和 EM 算法的联系： EM 算法分两步：

    1. Expectation 将观测数据输入模型, 计算结果, 称为期望值计算过程 (这阶段模型不变
    2. Maximization 改变模型的参数, 最大化期望(模型参数改变)

    E 和 M 两步循环迭代, 如果优化的函数是凸函数, 则一定能获得全局最有解, 若为非凸则不一定。在 k-means 中，我们首先假设参数的值, 根据这些参数标记样本类别(对应 Expectation Step),然后固定样本类别, 调整参数(簇中心)的位置(对应 Maximization Step)。因此 k-means 和 EM 算法的思想是相同的。

  • 层次聚类

    层次聚类不需要确定类别数目，最后生成一棵类别树。生成方法主要由自底向上和自顶向下生成。

    自底向上（常用）：一开始每个数据点都是一个类别，每次迭代选取距离最近的两个类别，将他们合并，直至最后合并成一个类别，完成树的构造。主要解决两个问题：

    1. 距离的度量，根据不同问题确定，比如欧式距离；
    2. 如何确定两个包含多个数据点的类别的距离，有三种方法：
      • 取两个集合中距离最近的点作为两个类的距离（聚类比较松散
      • 相反取两个集合中距离最远的点作为两个类的距离（聚类比较集中）
      • 折中，取每个类所有数据点位置均值来计算距离（常用）

    树的构造完成后可以通过观察树的结构确定最终要分成几类（在树某层横向切一刀）

    自顶向下：思路与自底向上相反，通过不断的分割得到最后的树。

  • K-Medoids

    思路：和 K-Means 很相似，区别在确定聚类中心这一步。K-Means 是直接取当前 cluster 的所有点在欧氏空间的均值，而 K-Mediods 是在当前 cluster 里面的点中选中心，具体是遍历当前 cluster 中的所有点，找到与其他点距离之和最小的点作为中心。

    优点：由于聚类中心是在数据点中找的，所以不容易收 outlier 影响，更 robust 缺点：K-Mediods 也有可能陷入局部最优

  • Guassian Mixture Model（高斯混合模型）

    高斯混合模型可以看作是概率版本的 k-means。一个数据点属于某个类的概率可以由多个高斯分布概率混合得到。 假设每个类都是一个高斯分布，类似 k-means 也是通过两步迭代得到拟合真实的分布：

    1. 估计所有数据点属于各个高斯分布的概率（相当于 k-means 中给数据点分类）
    2. 根据当前的聚类情况更新各个高斯分布的参数（相当于 k-means 中更新簇中心的位置）

    参考：GMM, tutorial


模型小结

  • LR 实现简单；应用广泛； 容易欠拟合；当特征空间较大是效果不是很好；

  • NB 属于生成模型，能够得到联合概率分布；对于小数据集表现良好；对缺失数据不太敏感；算法比较简单； 有特征之间相互独立的假设，当特征之间相关性比较高时效果不好；需要知道先验概率；对输入数据的形式比较敏感

  • SVM 可以解决高维特征空间问题；预测速度快（仅依赖于特征向量）；可以通过加入惩罚项获得良好的泛华能力； 需要找到一个合适的核函数及惩罚参数；

  • NN 训练得当时准确率高；能充分逼近非线性关系；能处理高维特征空间； 需要大量的训练数据；网络结构、参数、权值初始化等需要大量调试；输出结果可解释性差；训练时间长

  • DT 计算简单，易于理解，结果可解释性强；能够处理不相关的特征；对数据类型没有限制； 容易发生过拟合（剪枝）；

  • Boosting（Adaboost, GBDT） 精度高，不用进行特征筛选；不易发生过拟合； 对 outlier 比较敏感；比较难并行；

  • Bagging（RF） 引入了随机属性选择，不易发生过拟合；泛化能力强； 不用进行特征选择，训练完成后能够给出 feature 的重要程度；弱学习器的训练是相互独立的（可并行）； NOTE：RF 在噪音较大的数据中也会发生过拟合。

如果数据维度比较高，数据量较小，可以首先尝试 SVM； 如果数据类型多样，可以考虑采用决策树（以及基于决策树的集成）； 如果拥有大量的数据，考虑使用神经网络；