ML系列2：机器学习必会算法

1. 基础概念
2. 感知机
3. 线性回归
4. 逻辑回归
5. 决策树（包括 ID3，C4.5 决策树生成算法）
6. 集成学习（Boosting、bagging、随机森林）
7. 支持向量机（SVM）
8. 朴素贝叶斯
9. KNN 算法
10. 聚类算法（k-means）
11. 特征降维
12. 模型学习的最优化算法
13. EM算法与高斯混合模型（GMM）
14. 隐马尔可夫模型（HMM）
15. 条件随机场（CRF）

介绍机器学习必会算法

机器学习常见算法：

分类算法：

机器学习必掌握算法:

• 感知机
• 线性回归（Linear Regression）
• 逻辑回归（Logistic Regression）
• 决策树（包括 ID3，C4.5 决策树生成算法）
• 随机森林
• Boosting（Adaboost、GBDT、XGBoost）
• bagging
• GBDT（基于迭代累加的决策树算法）
• 支持向量机（SVM）
• 朴素贝叶斯法
• KNN 算法
• K-means算法
• 模型学习的最优化算法（梯度下降法、牛顿法和拟牛顿法、共轭梯度法等等）
• HMM和CRF
• 凸优化
• 主题模型LDA
• EM算法与高斯混合模型（GMM）
• 隐马尔可夫模型（HMM）
• 条件随机场（CRF）
• 卷积神经网络（CNN）
• 循环神经网络（RNN）和LSTM
• ……

基础概念

损失函数和风险函数：

• 0-1损失函数
• 平方损失函数
• 绝对损失函数
• 对数损失函数

经验风险最小化、结构风险最小化：
监督学习的两个基本策略：经验风险最小化、结构风险最小化

当样本容量足够大时，经验风险最小化能保证有很好的学习效果，在现实中被广泛采用。比如极大似然估计（MLE）就说一个例子。当模型是条件概率分布，损失函数是对数损失函数时，经验风险最小化就等价于极大似然估计。

但是当样本容量很小时，经验风险最小化学习效果未必很好，会产生过拟合。结构风险最小化就说为了防止过拟合而提出来的。结构风险最小化等价于正则化，给模型加上正则化项降低复杂程度。比如最大后验估计（MAP）就是结构风险最小化的一个例子。

生成模型、判别模型：

1. 生成方法由数据学习联合概率分布P(X,Y)，然后求出条件概率分布P(Y|X)作为预测的模型，P(Y|X)=P(X,Y)/P(X)，典型的生成模型有：朴素贝叶斯法、隐马尔科夫模型。
2. 判别方法由数据直接学习决策函数f(X)或者条件概率分布P(Y|X)作为预测的模型，典型的判别模型包括：KNN、感知机、决策树、逻辑回归、最大熵模型、SVM、boosting、CRF等。

感知机

什么是感知机：
感知机是二分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别+1/-1，感知机对应于输入空间（特征空间）中将实例分为正负两类的分离超平面。

定义出感知机的算法模型如下：f(x)=sign(w*x+b)

与SVM的区别：
支持向量机也是在特征空间中寻找一个划分样本实例类别的超平面，这点和感知机相似，但是不同的是，支持向量机支持在特征空间中寻找出非线性的平面(非线性支持向量机)。支持向量机寻找出的超平面唯一且最优，而感知机是根据误分类点定义出的代价函数求得的超平面不唯一，包含多个。

线性回归

掌握的重点：

• 掌握线性回归的实现过程
• 应用LinearRegression或SGDRegressor实现回归预测
• 知道回归算法的评估标准及其公式
• 知道过拟合与欠拟合的- 原因以及解决方法
• 知道岭回归的原理及与线性回归的不同之处
• 应用Ridge实现回归预测
• 应用joblib实现模型的保存与加载

线性回归(Linear regression)是利用回归方程(函数)对一个或多个自变量(特征值)和因变量(目标值)之间关系进行建模的一种分析方式。sklearn中对应的api是sklearn.linear_model.LinearRegression()。

梯度下降算法

• 梯度下降算法(Full gradient descent）,
• 随机梯度下降算法（Stochastic gradient descent）,
• 小批量梯度下降算法（Mini-batch gradient descent）,
• 随机平均梯度下降算法（Stochastic average gradient descent）

全梯度下降算法（FG）：计算训练集所有样本误差，对其求和再取平均值作为目标函数。因为在执行每次更新时，我们需要在整个数据集上计算所有的梯度，所以批梯度下降法的速度会很慢，同时，批梯度下降法无法处理超出内存容量限制的数据集。批梯度下降法同样也不能在线更新模型，即在运行的过程中，不能增加新的样本。

随机梯度下降算法（SG）：其每轮计算的目标函数不再是全体样本误差，而仅是单个样本误差，即每次只代入计算一个样本目标函数的梯度来更新权重，再取下一个样本重复此过程，直到损失函数值停止下降或损失函数值小于某个可以容忍的阈值。

小批量梯度下降算法（mini-batch）：每次从训练样本集上随机抽取一个小样本集，在抽出来的小样本集上采用FG迭代更新权重。

随机平均梯度下降算法（SAG）：随机平均梯度算法克服了这个问题，在内存中为每一个样本都维护一个旧的梯度，随机选择第i个样本来更新此样本的梯度，其他样本的梯度保持不变，然后求得所有梯度的平均值，进而更新了参数。

常见的梯度下降算法：

欠拟合与过拟合

1. 欠拟合原因以及解决办法

• 原因：学习到数据的特征过少
• 解决办法：
  1）添加其他特征项，有时候我们模型出现欠拟合的时候是因为特征项不够导致的，可以添加其他特征项来很好地解决。例如，“组合”、“泛化”、“相关性”三类特征是特征添加的重要手段，无论在什么场景，都可以照葫芦画瓢，总会得到意想不到的效果。除上面的特征之外，“上下文特征”、“平台特征”等等，都可以作为特征添加的首选项。
  2）添加多项式特征，这个在机器学习算法里面用的很普遍，例如将线性模型通过添加二次项或者三次项使模型泛化能力更强。

2. 过拟合原因以及解决办法

• 原因：原始特征过多，存在一些嘈杂特征， 模型过于复杂是因为模型尝试去兼顾各个测试数据点
• 解决办法：
  1）重新清洗数据，导致过拟合的一个原因也有可能是数据不纯导致的，如果出现了过拟合就需要我们重新清洗数据。
  2）增大数据的训练量，还有一个原因就是我们用于训练的数据量太小导致的，训练数据占总数据的比例过小。
  3）正则化
  4）减少特征维度，防止维灾难

什么是正则化？
在学习的时候，数据提供的特征有些影响模型复杂度或者这个特征的数据点异常较多，所以算法在学习的时候尽量减少这个特征的影响（甚至删除某个特征的影响），这就是正则化

1. L2正则化

• 作用：可以使得其中一些W的都很小，都接近于0，削弱某个特征的影响
• 优点：越小的参数说明模型越简单，越简单的模型则越不容易产生过拟合现象
• Ridge回归

2. L1正则化

• 作用：可以使得其中一些W的值直接为0，删除这个特征的影响
• LASSO回归

正则化线性模型

1. Ridge Regression（岭回归）：岭回归是线性回归的L2正则化版本，即在原来的线性回归的 cost function 中添加正则项
2. Lasso Regression(Lasso 回归)：Lasso 回归是线性回归的L1正则化版本，正则项为权值向量的ℓ1范数。Lasso Regression 有一个HMM
3. 很重要的性质是：倾向于完全消除不重要的权重。
4. Elastic Net (弹性网络)：弹性网络在岭回归和Lasso回归中进行了折中，通过 混合比(mix ratio) r 进行控制，r=0时弹性网络变为岭回归，r=1时弹性网络便为Lasso回归。

一般来说，弹性网络的使用更为广泛。因为在特征维度高于训练样本数，或者特征是强相关的情况下，Lasso回归的表现不太稳定。

逻辑回归

掌握的重点：

• 知道逻辑回归的损失函数、优化方法
• 知道逻辑回归的应用场景
• 应用LogisticRegression实现逻辑回归预测
• 知道精确率、召回率等指标的区别
• 知道如何解决样本不均衡情况下的评估
• 会绘制ROC曲线图形
• 模型最优化算法（改进的迭代尺度法、拟牛顿法）

逻辑回归的损失函数不能采用线性回归的损失函数（如MSE），而应该采用交叉熵损失函数。

精确率与召回率

• 精确率：预测结果为正例样本中真实为正例的比例（了解）
• 召回率：真实为正例的样本中预测结果为正例的比例（查得全，对正样本的区分能力）
• F1-score：反映了模型的稳健型，F1-score=（2*precision*recall）/（precision+recall）

ROC曲线与AUC指标

• ROC曲线：ROC曲线的横轴就是FPRate，纵轴就是TPRate，当二者相等时，表示的意义则是：对于不论真实类别是1还是0的样本，分类器预测为1的概率是相等的，此时AUC为0.5。其中TPRate是所有真实类别为1的样本中预测类别为1的比例，FPRate是所有真实类别为0的样本中预测类别为1的比例。

• AUC指标：AUC的概率意义是随机取一对正负样本，正样本得分大于负样本得分的概率。AUC的范围在[0, 1]之间，并且越接近1效果越好，越接近0.5效果就是胡说，越接近0效果越差。

决策树（包括 ID3，C4.5 决策树生成算法）

掌握的重点：

• 掌握决策树实现过程
• 知道信息熵的公式以及作用
• 知道信息增益、信息增益率和基尼指数的作用
• 知道ID3，C4.5，CART算法的区别
• 了解CART剪枝的作用
• 知道特征提取的作用
• 应用DecisionTreeClassifier实现决策树分类

决策树：是一种树形结构，其中每个内部节点表示一个属性上的判断，每个分支代表一个判断结果的输出，最后每个叶节点代表一种分类结果，本质是一颗由多个判断节点组成的树。

什么是熵？
物理学上，熵 Entropy 是“混乱”程度的量度。系统越有序，熵值越低；系统越混乱或者分散，熵值越高。”信息熵” (information entropy)是度量样本集合纯度最常用的一种指标。

决策树的划分依据1——信息增益
信息增益：以某特征划分数据集前后的熵的差值。熵可以表示样本集合的不确定性，熵越大，样本的不确定性就越大。因此可以使用划分前后集合熵的差值来衡量使用当前特征对于样本集合D划分效果的好坏。信息增益 = entroy(前) - entroy(后)。

一般而言，信息增益越大，则意味着使用属性 a 来进行划分所获得的”纯度提升”越大。因此，我们可用信息增益来进行决策树的划分属性选择，著名的 ID3 决策树学习算法 [Quinlan， 1986] 就是以信息增益为准则来选择划分属性。

决策树的划分依据2——信息增益率
实际上，信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，著名的 C4.5 决策树算法 [Quinlan， 1993J 不直接使用信息增益，而是使用”增益率” (gain ratio) 来选择最优划分属性.

增益率：增益率是用前面的信息增益Gain(D, a)和属性a对应的”固有值”(intrinsic value) [Quinlan , 1993J的比值来共同定义的。

为什么使用C4.5要好？

1. 用信息增益率来选择属性
   克服了用信息增益来选择属性时偏向选择值多的属性的不足。
2. 采用了一种后剪枝方法
   避免树的高度无节制的增长，避免过度拟合数据
3. 对于缺失值的处理
   在某些情况下，可供使用的数据可能缺少某些属性的值。假如〈x，c(x)〉是样本集S中的一个训练实例，但是其属性A的值A(x)未知。

决策树的划分依据3——基尼值和基尼指数
CART 决策树（Classification and Regression Tree的简称，这是一种著名的决策树学习算法,分类和回归任务都可用）使用”基尼指数” (Gini index)来选择划分属性。

基尼值Gini（D）：从数据集D中随机抽取两个样本，其类别标记不一致的概率。故，Gini（D）值越小，数据集D的纯度越高。
基尼指数Gini_index（D）：一般，选择使划分后基尼系数最小的属性作为最优化分属性。

以下是信息熵相关概念：

决策树算法：ID3、C4.5、CART

ID3算法：
ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树，具体方法：

• 从根节点开始，对节点计算所有可能特征的信息增益，选择信息增益最大的特征作为节点的特征，由该特征的不同取值建立子节点
• 再对子节点递归地调用以上方法，构建决策树，知道所有特征的信息增益均很小或没有特征可以选择为止

C4.5算法：
和ID3类似，只是把信息增益更换为了信息增益比。
具体方法：

• 从根节点开始，对节点计算所有可能特征的信息增益比，选择信息增益比最大的特征作为节点的特征，由该特征的不同取值建立子节点
• 再对子节点递归地调用以上方法，构建决策树，知道所有特征的信息增益均很小或没有特征可以选择为止

CART算法（分类与回归树模型）：
CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。算法如下：

• 决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大
• 决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准

其中，决策树的生成就说递归地构建二叉决策树的过程，对回归树用平方误差最小化准则，对分类树用基尼系数最小化准则，进行特征选择，生成二叉树。

1. ID3 算法的缺点

• ID3算法在选择根节点和各内部节点中的分支属性时，采用信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多的属性，在有些情况下这类属性可能不会提供太多有价值的信息.
• ID3算法只能对描述属性为离散型属性的数据集构造决策树。

2. C4.5算法的优缺点

• 优点：产生的分类规则易于理解，准确率较高。
• 缺点：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。

3. CART算法

• CART算法相比C4.5算法的分类方法，采用了简化的二叉树模型，同时特征选择采用了近似的基尼系数来简化计算。
• C4.5不一定是二叉树，但CART一定是二叉树。

集成学习（Boosting、bagging、随机森林）

掌握的重点：

• 了解集成学习中主要解决的两个核心任务
• 知道bagging集成原理
• 知道随机森林决策树的建立过程
• 知道为什么需要随机有放回(Bootstrap)的抽样
• 应用RandomForestClassifie实现随机森林算法
• 知道boosting集成原理
• 知道bagging和boosting的区别
• 了解GBDT实现过程

机器学习两个核心任务

1. 欠拟合问题：弱弱组合变强，如boosting
2. 过拟合问题：互相遏制变壮，如Bagging

bagging

​ Bagging + 决策树/线性回归/逻辑回归/深度学习… = bagging集成学习方法

经过上面方式组成的集成学习方法:

• 均可在原有算法上提高约2%左右的泛化正确率
• 简单, 方便, 通用

随机森林
随机森林够造过程中的关键步骤（M表示特征数目）：
​ 1）一次随机选出一个样本，有放回的抽样，重复N次（有可能出现重复的样本）
​ 2） 随机去选出m个特征, m <<M，建立决策树

1. 为什么要随机抽样训练集？　　
如果不进行随机抽样，每棵树的训练集都一样，那么最终训练出的树分类结果也是完全一样的
2. 为什么要有放回地抽样？
如果不是有放回的抽样，那么每棵树的训练样本都是不同的，都是没有交集的，这样每棵树都是“有偏的”，都是绝对“片面的”（当然这样说可能不对），也就是说每棵树训练出来都是有很大的差异的；而随机森林最后分类取决于多棵树（弱分类器）的投票表决。

Boosting（包括Adaboost、GBDT、XGBoost）
随着学习的积累从弱到强，简而言之：每新加入一个弱学习器，整体能力就会得到提升，代表算法有Adaboost，GBDT，XGBoost。

以下是Adaboost的学习过程：

如何确认投票权重？如何调整数据分布？

bagging和boosting对比

1. 区别一:数据方面
   Bagging：对数据进行采样训练；
   Boosting：根据前一轮学习结果调整数据的重要性。
2. 区别二:投票方面
   Bagging：所有学习器平权投票；
   Boosting：对学习器进行加权投票。
3. 区别三:学习顺序
   Bagging的学习是并行的，每个学习器没有依赖关系；
   Boosting学习是串行，学习有先后顺序。
4. 区别四:主要作用
   Bagging主要用于提高泛化性能（解决过拟合，也可以说降低方差）
   Boosting主要用于提高训练精度 （解决欠拟合，也可以说降低偏差）

GBDT（基于迭代累加的决策树算法）
梯度提升决策树(GBDT Gradient Boosting Decision Tree) 是一种迭代的决策树算法，该算法由多棵决策树组成，所有树的结论累加起来做最终答案。它在被提出之初就被认为是泛化能力（generalization)较强的算法。近些年更因为被用于搜索排序的机器学习模型而引起大家关注。
GBDT = 梯度下降 + Boosting + 决策树

GBDT主要执行思想

1. 使用梯度下降法优化代价函数；
2. 使用一层决策树作为弱学习器，负梯度作为目标值；
3. 利用boosting思想进行集成。

XGBoost
XGBoost= 二阶泰勒展开+boosting+决策树+正则化

• Boosting：XGBoost使用Boosting提升思想对多个弱学习器进行迭代式学习
• 二阶泰勒展开：每一轮学习中，XGBoost对损失函数进行二阶泰勒展开，使用一阶和二阶梯度进行优化。
• 决策树：在每一轮学习中，XGBoost使用决策树算法作为弱学习进行优化。
• 正则化：在优化过程中XGBoost为防止过拟合，在损失函数中加入惩罚项，限制决策树的叶子节点个数以及决策树叶子节点的值。

支持向量机（SVM）

掌握的重点：

• 什么是 SVM 算法？
• 如何调整 SVM 的参数？
• 什么是间隔最大化？
• 硬间隔最大化、软间隔最大化
• 什么是学习的对偶算法？
• 什么是核函数？
• 什么是KKT条件？
• 什么是kernel trick？
• 序列最小最优化算法

什么是 SVM 算法？
支持向量机(SVM) 是一个监督学习算法，既可以用于分类问题也可以用于回归问题。但是，SVM算法还是主要用在分类问题中。在 SVM 算法中，我们将数据绘制在 n 维空间中（n 代表数据的特征数），每个特征数的值是特定坐标的值。然后我们通过查找可以将数据分成两类的超平面。

SVM 的优点和缺点

1. 优点：

• 对于边界清晰的分类问题效果好；
• 对高维分类问题效果好；
• 当维度高于样本数的时候，SVM 较为有效；
• 因为最终只使用训练集中的支持向量，所以节约内存

2. 缺点：

• 当数据量较大时，训练时间会较长；
• 当数据集的噪音过多时，表现不好；
• SVM 不直接提供结果的概率估计，它在计算时直接使用 5 倍交叉验证。

朴素贝叶斯

掌握的重点：

• 贝叶斯定理
• 后验概率最大化
• 朴素贝叶斯法 Naive Bayes
• 极大似然估计 MLE
• 最大后验估计 MAP
• 朴素贝叶斯分类器的应用

贝叶斯定理
P(B|A) = P(B)P(A|B)/P(A)
其中，
P（B） 为先验概率，即在得到新数据前某一假设的概率；
P（B|A）为后验概率，即在观察到新数据后计算该假设的概率；
P（A|B）为似然度，即在该假设下得到这一数据的概率；
P（A）为标准化常量，即在任何假设下得到这一数据的概率。

朴素贝叶斯法
朴素贝叶斯法是典型的生成学习方法，生成方法由训练数据学习联合概率分布P(X,Y)，然后求得后验概率分布P(Y|X)，具体来说，利用训练数据学习P(X|Y)和P(Y)的估计，得到联合概率分布：P(X,Y)=P(Y)P(X|Y)。概率估计方法可以是极大似然估计或贝叶斯估计。

朴素贝叶斯法的基本假设条件独立性，模型包含的条件概率的数量大为减少，朴素贝叶斯法的学习与预测大为简化，因而朴素贝叶斯法高效且易于实现，其缺点是分类的性能不一定很高。

朴素贝叶斯分类器
朴素贝叶斯分类是一种十分简单的分类算法，叫它朴素贝叶斯分类是因为这种方法的思想真的很朴素，朴素贝叶斯的思想基础是这样的：对于给出的待分类项，求解在此项出现的条件下各个类别出现的概率，哪个最大，就认为此待分类项属于哪个类别。通俗来说，就好比这么个道理，你在街上看到一个黑人，我问你你猜这哥们哪里来的，你十有八九猜非洲。为什么呢？因为黑人中非洲人的比率最高，当然人家也可能是美洲人或亚洲人，但在没有其它可用信息下，我们会选择条件概率最大的类别，这就是朴素贝叶斯的思想基础。

KNN 算法

掌握的重点：

• 掌握K-近邻算法实现过程
• 知道K-近邻算法的距离公式
• 知道K-近邻算法的超参数K值以及取值问题
• 知道kd树实现搜索的过程
• 应用KNeighborsClassifier实现分类
• 知道K-近邻算法的优缺点
• 知道交叉验证实现过程
• 知道超参数搜索过程
• 应用GridSearchCV实现算法参数的调优

什么是KNN算法（k近邻算法）？
如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。

距离度量有哪些？

1. 欧式距离(Euclidean Distance)
2. 曼哈顿距离(Manhattan Distance)——只考虑横竖两种情况
3. 切比雪夫距离 (Chebyshev Distance)——考虑直行、横行、斜行三种情况
4. 闵可夫斯基距离(Minkowski Distance)——闵氏距离不是一种距离，而是一组距离的定义，是对多个距离度量公式的概括性的表述，根据参数的不同，可以表示欧氏距离、曼哈顿距离、切比雪夫距离
   当p=1时，就是曼哈顿距离；
   当p=2时，就是欧氏距离；
   当p→∞时，就是切比雪夫距离。
5. 标准化欧氏距离 (Standardized EuclideanDistance)——在计算过程中添加了标准差,对量刚数据进行处理

6. 余弦距离(Cosine Distance)
7. 汉明距离(Hamming Distance)【了解】——两个等长字符串s1与s2的汉明距离为：将其中一个变为另外一个所需要作的最小字符替换次数。
8. 杰卡德距离(Jaccard Distance)【了解】——用两个集合中不同元素占所有元素的比例来衡量两个集合的区分度
9. 马氏距离(Mahalanobis Distance)【了解】——通过样本分布进行计算

K值如何选择？

• K值过小：容易受到异常点的影响、容易过拟合
• k值过大：受到样本均衡的问题、容易欠拟合

K值的减小就意味着整体模型变得复杂，容易发生过拟合，K值的增大就意味着整体的模型变得简单。在实际应用中，K值一般取一个比较小的数值，例如采用交叉验证法（简单来说，就是把训练数据在分成两组:训练集和验证集）来选择最优的K值。

为什么要引入kd树？
k近邻法最简单的实现是线性扫描（穷举搜索），即要计算输入实例与每一个训练实例的距离。计算并存储好以后，再查找K近邻。当训练集很大时，计算非常耗时。为了提高kNN搜索的效率，可以考虑使用特殊的结构存储训练数据，以减小计算距离的次数。

kd树：为了避免每次都重新计算一遍距离，算法会把距离信息保存在一棵树里，这样在计算之前从树里查询距离信息，尽量避免重新计算。其基本原理是，如果A和B距离很远，B和C距离很近，那么A和C的距离也很远。有了这个信息，就可以在合适的时候跳过距离远的点。这样优化后的算法复杂度可降低到O（DNlog（N））。

kd树(K-dimension tree)是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。kd树是一种二叉树，表示对k维空间的一个划分，构造kd树相当于不断地用垂直于坐标轴的超平面将K维空间切分，构成一系列的K维超矩形区域。kd树的每个结点对应于一个k维超矩形区域。利用kd树可以省去对大部分数据点的搜索，从而减少搜索的计算量。

kd树的构建过程

1. 构造根节点
2. 通过递归的方法，不断地对k维空间进行切分，生成子节点
3. 重复第二步骤，直到子区域中没有示例时终止

需要关注细节：a.选择向量的哪一维进行划分；b.如何划分数据

kd树的搜索过程

1. 二叉树搜索比较待查询节点和分裂节点的分裂维的值，（小于等于就进入左子树分支，大于就进入右子树分支直到叶子结点）
2. 顺着“搜索路径”找到最近邻的近似点
3. 回溯搜索路径，并判断搜索路径上的结点的其他子结点空间中是否可能有距离查询点更近的数据点，如果有可能，则需要跳到其他子结点空间中去搜索
4. 重复这个过程直到搜索路径为空

什么是特征工程？
通过一些转换函数将特征数据转换成更加适合算法模型的特征数据过程，包含归一化、标准化。

• 归一化：是对原始数据进行变换把数据映射到(默认为[0,1])之间
  鲁棒性比较差(容易受到异常点的影响)
  只适合传统精确小数据场景(以后不会用你了)
• 标准化：是对原始数据进行变换把数据变换到均值为0,标准差为1范围内
  异常值对我影响小
  适合现代嘈杂大数据场景(以后就是用你了)

什么是交叉验证？
交叉验证目的：为了让被评估的模型更加准确可信
交叉验证：将拿到的训练数据，分为训练和验证集。以下图为例：将数据分成4份，其中一份作为验证集。然后经过4次(组)的测试，每次都更换不同的验证集。即得到4组模型的结果，取平均值作为最终结果。又称4折交叉验证。

聚类算法（k-means）

掌握的重点：

• 掌握聚类算法实现过程
• 知道K-means算法原理
• 知道聚类算法中的评估模型
• 说明K-means的优缺点
• 了解聚类中的算法优化方式
• 知道特征降维的实现过程
• 应用Kmeans实现聚类任务

聚类算法：一种典型的无监督学习算法，主要用于将相似的样本自动归到一个类别中。在聚类算法中根据样本之间的相似性，将样本划分到不同的类别中，对于不同的相似度计算方法，会得到不同的聚类结果，常用的相似度计算方法有欧式距离法。

聚类算法是无监督的学习算法，而分类算法属于监督的学习算法。

k-means
1、随机设置K个特征空间内的点作为初始的聚类中心
2、对于其他每个点计算到K个中心的距离，未知的点选择最近的一个聚类中心点作为标记类别
3、接着对着标记的聚类中心之后，重新计算出每个聚类的新中心点（平均值）
4、如果计算得出的新中心点与原中心点一样（质心不再移动），那么结束，否则重新进行第二步过程

由于每次都要计算所有的样本与每一个质心之间的相似度，故在大规模的数据集上，K-Means算法的收敛速度比较慢。

模型评估

1. 误差平方和(SSE \The sum of squares due to error)
2. 肘”方法 (Elbow method) — K值确定

（1）对于n个点的数据集，迭代计算k from 1 to n，每次聚类完成后计算每个点到其所属的簇中心的距离的平方和；
（2）平方和是会逐渐变小的，直到k==n时平方和为0，因为每个点都是它所在的簇中心本身。
（3）在这个平方和变化过程中，会出现一个拐点也即“肘”点，下降率突然变缓时即认为是最佳的k值。
在决定什么时候停止训练时，肘形判据同样有效，数据通常有更多的噪音，在增加分类无法带来更多回报时，我们停止增加类别。

3. 轮廓系数法（Silhouette Coefficient）
4. CH系数（Calinski-Harabasz Index）
   CH需要达到的目的：用尽量少的类别聚类尽量多的样本，同时获得较好的聚类效果。

K-means算法优化

K-means的优点：
​ 1. 原理简单（靠近中心点），实现容易
​ 2. 聚类效果中上（依赖K的选择）
​ 3. 空间复杂度o(N)，时间复杂度o(IKN)
K-means的缺点：
​ 1. 对离群点，噪声敏感 （中心点易偏移）
​ 2. 很难发现大小差别很大的簇及进行增量计算
​ 3. 结果不一定是全局最优，只能保证局部最优（与K的个数及初值选取有关）

1. Canopy算法

2. K-means++
kmeans++目的，让选择的质心尽可能的分散，如下图中，如果第一个质心选择在圆心，那么最优可能选择到的下一个点在P(A)这个区域（根据颜色进行划分）

3. 二分k-means
实现流程:

• 所有点作为一个簇
• 将该簇一分为二
• 选择能最大限度降低聚类代价函数（也就是误差平方和）的簇划分为两个簇。
• 以此进行下去，直到簇的数目等于用户给定的数目k为止。

二分K均值算法可以加速K-means算法的执行速度，因为它的相似度计算少了并且不受初始化问题的影响，因为这里不存在随机点的选取，且每一步都保证了误差最小。

4.k-medoids（k-中心聚类算法）
K-medoids和K-means是有区别的，不一样的地方在于中心点的选取
K-means中，将中心点取为当前cluster中所有数据点的平均值，对异常点很敏感!
K-medoids中，将从当前cluster 中选取到其他所有（当前cluster中的）点的距离之和最小的点作为中心点。

算法流程：
　　 ( 1 )总体n个样本点中任意选取k个点作为medoids
　　 ( 2 )按照与medoids最近的原则，将剩余的n-k个点分配到当前最佳的medoids代表的类中
　　 ( 3 )对于第i个类中除对应medoids点外的所有其他点，按顺序计算当其为新的medoids时，代价函数的值，遍历所有可能，选取代价函数最小时对应的点作为新的medoids
　　 ( 4 )重复2-3的过程，直到所有的medoids点不再发生变化或已达到设定的最大迭代次数
　　 ( 5 )产出最终确定的k个类

k-medoids只能对小样本起作用，样本大，速度就太慢了，当样本多的时候，少数几个噪音对k-means的质心影响也没有想象中的那么重，所以k-means的应用明显比k-medoids多。

5. Kernel k-means（了解）
kernel k-means实际上，就是将每个样本进行一个投射到高维空间的处理，然后再将处理后的数据使用普通的k-means算法思想进行聚类。
6 ISODATA（了解）
7 Mini Batch K-Means（了解）

特征降维

掌握的重点：
降维是指在某些限定条件下，降低随机变量(特征)个数，得到一组“不相关”主变量的过程，降维的两种方式：

1. 特征选择
2. 主成分分析

方法

1. Filter(过滤式)：主要探究特征本身特点、特征与特征和目标值之间关联

• 方差选择法：低方差特征过滤
• 相关系数（Pearson相关系数、Spearman相关系数）

2. Embedded (嵌入式)：算法自动选择特征（特征与目标值之间的关联）

• 决策树:信息熵、信息增益
• 正则化：L1、L2
• 深度学习：卷积等

PCA
定义：高维数据转化为低维数据的过程，在此过程中可能会舍弃原有数据、创造新的变量
作用：是数据维数压缩，尽可能降低原数据的维数（复杂度），损失少量信息。
应用：回归分析或者聚类分析当中

模型学习的最优化算法

掌握的重点：

• 梯度下降法
• 改进的迭代尺度法
• 牛顿法和拟牛顿法
• 共轭梯度法

EM算法与高斯混合模型（GMM）

掌握的重点：

• 什么是EM算法
• EM算法的收敛性
• EM算法在GMM中的应用
• EM算法的推广

隐马尔可夫模型（HMM）

掌握的重点：

• HMM基本概念
• HMM的3个基本问题
• 直接计算法、前向算法、后向算法
• 学习算法（监督学习算法、Baum-Welch算法）
• 预测算法（近似算法、维特比算法）

条件随机场（CRF）

掌握的重点：

• 什么是概率无向图模型
• 什么是条件随机场
• 概率计算（前向-后向算法）
• 学习算法（改进的迭代尺度法、拟牛顿法）
• 预测算法

sklearn官网给出的机器学习算法选择路径图如下：