Yihang

Have a nice day!

机器学习相关知识点总结

发表于 更新于

机器学习相关知识点总结

特征工程

“Garbage in, garbage out” 数据和特征决定了模型的上限，而模型、算法的选择及优化只是在逐步接近这个上限

特征工程，对原始数据的一系列工程处理、并提炼为特征，作为输入供算法和模型使用

本质上，为一个表示和展现数据的过程

结构化数据：关系型数据库的一张表，数值型，类别型

特征归一化

  • 常用方法：
    • Min-Max归一化：对原始数据的等比缩放
    • 零均值归一化：Z-Score Normalization, 减均值除以标准差
  • 归一化动机：
    • 无量纲化，使得不同指标之间具有可比性
    • 以SGD为例，可使得各分量更新速度更为一致，更容易找到最优解
  • Tips：
    • 通过梯度下降法求解的模型通常是需要归一化的：如线性回归、LR、SVM、神经网络等
    • 而对于决策树模型并不适用，如C4.5，结点分裂（特征选择）时，主要是依据数据集$D$关于特征$x$的信息增益比，而信息增益比跟特征是否经过归一化是无关的（归一化不会改变样本在特征$x$上的信息增益）

类别型特征

原始输入通常是字符串形式，除了决策树等少数模型能直接处理字符串形式的输入，对于逻辑回归、SVM等来说，类别型特征必须经过处理转换成数值型特征才能正常工作

  • 序号编码（Ordinal Encoding）: 通常用于处理类别间具有大小关系的数据 i.e. 成绩=（高，中，低）= （3， 2， 1）
  • 独热编码（One-Hot Encoding）: ～～不具有大小关系的数据 i.e. 血型 = （A，B，AB，O）—-> 四维稀疏向量：A = （1， 0， 0， 0）， B = （0， 1， 0， 0）， 类推
    对于取值类别较多时：
    • 使用稀疏向量来节省空间
    • 配合特征选择来降低维度
  • 二进制编码（Binary Encoding）: 先用序号编码给每个类别赋予一个类别ID，然后将类别ID对应的二进制编码作为结果
    本质上，是利用二进制对ID进行哈希映射，最终得到0/1特征向量，且维数少于独热编码，节省了存储空间（状态压缩）
  • 其他编码

组合特征

高维组合特征的处理

为了提高复杂关系的拟合能力，特征工程中经常会把一阶离散特征两两组合，构成高阶组合特征

对于两个高维特征组合：

  • 利用降维的方法：用$k$维的低维向量表示，需要学习的参数规模由原来的$m\times n$变为$m\times k + n \times k$，（在推荐算法中，这等价于矩阵分解）
有效地寻找组合特征

对于多个高维特征：

  • 基于决策树的特征组合寻找方法
    • 根据原始输入和标签构造决策树
    • 每一条从根节点到叶结点的路径都可以看成是一种特征组合的方式
    • 给定原始输入，有效构造决策树：梯度提升决策树（GBDT），即每次都在之前构建的决策树的残差上构建下一棵决策树

非结构化数据：无简单数值表示、无清晰类别定义、无固定大小

包括文本、图像、音频、视频等

文本表示模型

  • 词袋模型（Bag of Words）: 将每篇文章看作一袋子词，忽略每个词出现的顺序

    • 以词为单位切分开，每篇文章可以表示成一个长向量，向量的每一维代表一个单词，该维对应的权重则反映这个词在原文章中的重要程度
    • 常用TF-IDF（Term Frequency - Inverse Document Frequency）来计算权重: $\operatorname{TF-IDF}(t, d) = \operatorname{TF}(t, d) \times \operatorname{IDF}(t)$
      其中，$\operatorname{TF}(t, d)$为单词$t$在文档$d$中出现的频率，$\operatorname{IDF}(t)$为逆文档频率，用来衡量单词$t$对表达语意所起的重要性，表示为 $\operatorname{IDF}(t) = \operatorname{log}\frac{\text{文章总数}}{包含单词t的文章总数+1}$
      直观解释：如果一个单词在非常多的文章里都出现，那么它可能是一个比较通用的词汇，对于区分某篇文章特殊语义的贡献较小，因此对权重做一定惩罚

    显然上述以单词为基本划分单位存在缺陷

  • N-gram （词组）模型：将连续出现的$n$个词（$n \le N$）组成的词组也作为一个单独的特征放到向量表示中去

    • 同一个词可能有多种词性变化，却具有相似的含义，一般会对单词进行词干抽取（Word Stemming）处理，即将不同词性的单词统一成为同一词干的形式

  • 主题模型：用于从文本库中发现有代表性的主题（得到每个主题上词的分布特性），计算出每篇文章的主题分布

    • 词嵌入（Word Embedding）: 是一类将词向量化的模型的统称
      • 核心思想：将每个词都映射成低维空间（K=50～300维）上的一个稠密向量。每一维可看作一个隐含的主题，只不过不像主题模型中的主题那样直观
      • 如果一篇文章有$N$个词，就可用一个$N\times K$的矩阵来表示这篇文档，但是过于底层，需要加工出更高层的特征
      • 比较：传统的浅层机器学习模型中，一个好的特征工程往往可以带来算法效果的显著提升；而深度学习模型为我们提供了一种自动进行特征工程的方式，模型中的每个隐层都可以认为对应着不同抽象层次的特征
      • CNN和RNN的结构在文本表示中取得了很好的效果，主要是由于它们能够更好地对文本进行建模，抽取出一些高层的语义特征。相比于全连接神经网络，它俩一方面较好地抓住了文本的特性，另一方面减少了网络中待学习的参数，提高了训练速度的同时降低了过拟合的风险

Word2Vec

Google 2013 常用的词嵌入模型之一，浅层神经网络模型，两种网络结构：CBOW(continuous Bag of Words) 和 Skip-gram

  • CBOW：根据上下文出现的词语来预测当前词的生成概率
  • Skip-gram: 根据当前词来预测上下文中各词的生成概率
  • 均可表示成由输入层（one-hot）、隐含层（CBOW需要对计算出的隐含单元求和）、和输出层（softmax）组成的神经网络
  • Note：Word2Vec 与 LDA(隐狄利克雷模型)的区别和联系：待补充

图像数据不足时的处理方法

  • 一个模型所能提供的信息一般来源于两个方面：
    • 一是训练数据中蕴含的信息
    • 二是在模型形成过程中（包括构造、学习、推理等），人们提供的先验信息
  • 当训练数据不足时，说明模型从原始数据获取的信息比较少，这种情况下要想保证模型的效果，就需要更多先验信息
    • 先验信息可以作用在模型上，如让模型采用特定的内在结构、条件假设或添加其他一些约束条件
    • 也可以直接施加在数据集上，即根据特定的先验假设去调整、变换或扩展训练数据，让其展现出更多的、更有用的信息
  • 缓和过拟合，从基于数据的角度，泛化误差上界会降低
  • 数据扩充（Data Augmentation）, 即根据一些先验知识，在保持特定信息的前提下，对原始数据进行适当变换以达到扩充数据集的效果。具体到图像分类任务中：
    • 一定程度内的随机旋转、平移、缩放、裁剪、填充、左右翻转等，对应同一个目标在不同角度下的观察结果
    • 对图像中的像素添加噪声扰动，比如高斯白噪声等
    • 颜色变换（RGB颜色空间主成分分析，添加0均值小方差的高斯增量）
    • 改变图片的亮度、清晰度、对比度、锐度等
    • 先提取图像特征、然后在图像的特征空间内进行变换、利用一些通用的数据扩充或上采样技术，如SMOTE算法
    • 使用生成模型合成新样本，如生成式对抗网络模型
    • 借助已有的模型或数据来进行迁移学习，如借助pre-trained 的模型，在针对目标任务的小数据集上进行微调（fine-tune）（这种微调可以看成是一种简单的迁移学习）

怎么选择特征

特征选择：目标-寻找最优子集

特征选择能剔除不相关(irrelevant)或冗余(redundant )的特征，从而达到减少特征个数，提高模型精确度，减少运行时间的目的。

特征选择的一般过程：

  1. 生成子集：搜索特征子集，为评价函数提供特征子集
  2. 评价函数：评价特征子集的好坏
  3. 停止准则：与评价函数相关，一般是阈值，评价函数达到一定标准后就可停止搜索
  4. 验证过程：在验证数据集上验证选出来的特征子集的有效性

模型评估

分类准确率

分类正确的样本占总样本的比例：(等价于0-1 损失)： $ \text{Accuracy} = \frac{n_{\text{correct}}}{n_{\text{total}}}$

  • 缺点：当数据标签失衡时，占比大的类别往往成为影响准确率的最主要因素

  • 解决：改用平均准确率，即每个类别下的样本准确率的算术平均

精确率与召回率（Precision & Recall）

  • 精确率是指分类正确的正样本个数(TP)占分类器判定为正样本的样本个数(TP+FP)的比例: $\frac{TP}{TP+FP}$
  • 召回率是指分类正确的正样本个数(TP)占真正的正样本个数(TP + FN)的比例: $\frac{TP}{TP+FN}$
  • Precision 和 Recall 之间往往存在一个权衡，它们通常用来衡量一个排序模型的性能
  • 为了综合评估一个排序模型的好坏，最好绘制出模型的P-R曲线
    它上面的一个点代表在某一阈值下，模型将大于该阈值的结果判定为正样本，小于该阈值的结果判定为负样本，此时返回结果对应的Recall 和 Precision
    整条P-R曲线是通过将阈值从高到低移动而生成的
    只用某个点对应的精确率和召回率是不能全面衡量模型性能的，只有通过P-R曲线的整体表现才能对模型进行更为全面的评估

F1-score

精确率和召回率的调和平均值：

>

综合地反应一个排序模型的性能

ROC曲线, AUC值

  • ROC曲线：横坐标为假阳性率（$\text{FPR}=\frac{FP}{N}$），纵坐标为真阳性率($\text{TPR}=\frac{TP}{P}$)
    ROC曲线是通过不断移动分类器的截断点（区分正负预测结果的阈值）来生成曲线上的一组关键点的
    当截断点选择为正无穷，即模型把样本全部预测为负类，那么FP和TP都为0，相应的FPR和TPR都为0，因此曲线的第一个点的坐标就是（0，0），其余同理

  • AUC值：ROC曲线下的面积大小，量化基于ROC曲线衡量出的模型性能。

    • 既然是面积，那就只需要沿着ROC的横轴积分就可以了
    • ROC曲线一般都处于y=x这条直线上方（如果不是，只需把模型预测概率反转成1-p就可以得到更好的分类器），因此AUC的值一般在0.5～1之间，
    • AUC越大，说明分类器越可能把真正的正样本排在前面，分类性能越好
    • 另一个定义：随机给定一个正样本和一个负样本，分类器输出该正样本为正的那个概率值 比 分类器输出该负样本为正的那个概率值 要大的可能性，此时有显示表达式：$\frac{\sum I(P_{\text{正样本}}， P_{\text{负样本}})}{M\times N}$, $I(P_{\text{正样本}}， P_{\text{负样本}}) = 1 \quad \text{if} \quad P_{\text{正样本}} > P_{\text{负样本}}, \quad \text{elif} \quad P_{\text{正样本}} = P_{\text{负样本}} \quad 0.5 \quad \text{else} \quad 0$

当正负样本的分布发生变化时，ROC曲线的形状基本保持不变，而P-R曲线的形状一般会剧烈变化，因此ROC曲线能更稳定地反映模型本身的好坏。

RMSE

  • 常用来衡量回归模型的好坏：$\text{RMSE} = \sqrt{\frac{\sum_{i=1}^{n}(y_i-\hat{y_i})^2}{n}}$

  • Outlier 会让RMSE指标变得很差
    解决办法：

    • 如果认定这些离群点是噪声点，降噪处理；
    • 如果不认为是噪声点，需要在建模的时候考虑相应机制来提高模型的预测能力，这里比较复杂；
    • 更换更合适的指标，比如平均绝对百分比误差MAPE，它把每个点的误差进行了归一化，降低了离群点带来的绝对误差的影响：$\text{MAPE} = \sum_{i=1}^{n}|\frac{y_i - \hat{y_i}}{y_i}|\times\frac{100}{n}$

余弦距离的应用

在机器学习问题中，通常将特征表示为向量的形式，所以在分析两个特征的向量表示之间的相似性时，常用余弦相似度来表示

  • 余弦相似度：$cos(A,B) = \frac{A\cdot B}{|A|_2|B|_2}$, 即两个向量夹角的余弦，角度关系，不关心绝对大小，取值范围是$[-1, 1]$， 相同的两个向量相似度为1

  • 为什么使用余弦相似度：

    • 当一对文本长度差距很大，但内容相似时，如果使用词频或者词向量作为作为特征，它们在特征空间的欧式距离通常很大；
    • 而使用余弦相似度的话，它们之间的夹角可能很小，因而相似度高。
    • 此外，在文本、图像、视频等领域，研究的对象的特征维度往往很高，余弦相似度在高维情形下依然保持“相同为1，正交为0，相反为-1”的性质；而欧式距离的数值受维度影响，范围不定，含义模糊

  • 余弦距离

    • 定义：$\operatorname{dist}(A,B) = 1 - cos(A,B)$
    • 余弦距离满足正定性和对称性，但是不满足三角不等式性（反例：A=(1,0), B=(1, 1), C=(0,1)），因此它不是一个严格定义的距离
      Note: 被称为距离，却不满足三条性质的还有KL距离（KL-Divergence）， 也叫做相对熵，常用于计算两个分布之间的差异，却不满足对称性和三角不等式

A/B Test

模型评估的验证方法

超参数调优

  • 网格搜索
  • 随机搜索

过拟合与欠拟合

回归

Least Square

  • 有闭形式的解：$(X^{\top}X)^{-1}X^{\top}y$ （当括号内可逆时）

Ridege

  • $L_2$正则化
    也有闭形式的解：$(X^{\top}X + \lambda I)^{-1}X^{\top}y$ （适当的$\lambda$使得括号内一定可逆）

Lasso

  • $L_1$正则化，稀疏性，不可求梯度
    求解：Proximal Gradient Descent （= proximal point + gradient descent）分成可以求梯度和不可以求梯度的两部分，对于前者用线性近似，后者用函数本身, 得到新的目标函数之后，分解，对求和中的每一项分别求最小，就可以得到相应的参数对应的分量的迭代表达式，而且是闭形式的

P-Value

给定原假设和备择假设，在假定原假设成立的情况下，构造相应的检验统计量，计算出对应的P-value，如果P-value很小，低于我们预先给定的显著性水平，说明小概率事件发生了，而现实中小概率事件发生往往是不太可能的，所以我们应该拒绝原假设，接受备择假设

P-Value不用于证明任何事情。、当结果具有统计学意义时，p值将用作质疑我们最初假设（无效假设）的工具

传统机器学习算法

决策树 （DT）

  • 自上而下，对样本数据进行树形分类的过程。（简单直观，解释性强）
    结点+有向边构成：每个内部结点表示一个特征，叶结点表示类别
    将决策树应用集成学习的思想可以得到随机森林，梯度提升决策树（GBDT）等模型
    决策树的生成：特征选择，树的构造，树的剪枝

  • 常用的决策树算法

    • ID3：最大信息增益。
      对于样本集合D, 类别数为K，数据集D的经验熵表示为：$H(D)=-\sum_{k=1}^{K}\frac{|C_k|}{|D|}log_2 \frac{|C_k|}{|D|}$, 其中$C_k$是样本集合D中属于第K类的样本子集
      某个特征A对于数据集D的经验条件熵为：$H(D|A)=\sum_{i=1}^{n}\frac{|D_i|}{D}H(D_i)=\sum_{i=1}^{n}\frac{|D_i|}{D}(-\sum_{k=1}^{K}\frac{|D_{ik}|}{D_i}log_2 \frac{|D_{ik}|}{D_i})$, 其中，$D_i$表示D中特征A取第i个值的样本子集，$D_{ik}$表示$D_i$中属于第k类的样本子集
      信息增益：$g(D,A) = H(D) - H(D|A)$, 优先选择信息增益最大的特征
    • C4.5：最大信息增益比。
      特征A对于数据集D的信息增益比：$g_R (D,A) = \frac{g(D,A)}{H_A(D)}$, 其中，$H_A (D) = -\sum_{i=1}^{n}\frac{|D_i|}{D} log_2 \frac{|D_i|}{D}$，称为数据集D关于A的取值熵
    • CART：最大基尼系数（Gini）
      Gini描述的是数据的纯度，与信息熵含义类似：$\text{Gini}(D)= 1 - \sum_{k=1}^{n}(\frac{|C_k|}{|D|})^2$
      每一次迭代中选取Gini指数最小的特征及其对应的切分点进行分类
      与ID3，C4.5不同的是，CART是一颗二叉树，采用二元切割法，每一步将数据按特征A的取值切成两份，分别进入左右子树，特征A的Gini指数定义为$\text{Gini}(D|A)=\sum_{i=1}^{n}\frac{|D_i|}{|D|}Gini(D_i)$

  • Note:

    • ID3 会倾向于取值较多的特征

    • C4.5是对ID3的优化，通过引入信息增益比，在一定程度上对取值较多的特征进行惩罚，避免ID3出现过拟合的特性，提升决策树的泛化能力

    • 样本类型角度：ID3只能处理离散型变量，而C4.5和CART都可以处理连续型变量
    • 应用角度：ID3和C4.5只能用于分类，而CART（classification and regression tree）还可以应用于回归（使用平方误差）
    • ID3对样本特征缺失值比较敏感，而C4.5和CART可以对缺失值进行不同方式的处理
    • ID3和C4.5可以在每个结点产生多叉分支，且每个特征在层级之间不会复用；CART只产生两个分支，每个特征可以被重复使用
      ID3和C4.5通过剪枝来权衡树的准确性与泛化能力，而CART直接利用全部数据发现所有可能的树结构进行对比

  • 剪枝：

    预剪枝（pre-pruning）：在生成决策树的过程中提前停止树的生长 （局限：有欠拟合的风险）

    1. 树的深度达到一定程度，停止树的生长；
    2. 到达当前结点的样本数量小于某个阈值的时候，停止树的生长；
    3. 计算每次分裂对测试集的准确度提升，当小于某个阈值时，停止

    后剪枝 (post-pruning): 让算法生成一颗完全生长的决策树，然后从最底层向上计算是否剪枝。剪枝过程将子树删除，用一个叶子结点替代，该结点的类别同样由多数投票的原则进行判断

    相比于预剪枝，后剪枝通常可以得到泛化能力更强的决策树，但时间开销会更大

决策树生成的伪代码 (递归生成：base-如果数据集中所有样本分类一致，创建携带类标签的叶子结点；不然，寻找划分数据集的最好特征，根据其划分数据集，对于每个划分好的数据集，进行递归创建决策子树)

支持向量机 (SVM)

参考

  • 一句话总结：最大化分类间隔的线性分类器（不使用核函数时）
    SVM有三宝，支撑（支持向量），间隔（分类间隔），核技巧（将低维非线性数据转换为高维线性数据的同时避免高维计算）；
    SVM的分类结果仅依赖于支持向量；
    超平面分离定理：对于两个不相交的凸集，存在一个超平面，将两个凸集分离

逻辑回归 (LR)

  • 一句话总结：假定数据服从逻辑斯蒂分布，利用MLE来求解参数
    与线性回归的联系：如果把一个事件的几率（odds）定义为该事件发生的概率与不发生的概率的比值，$\frac{p}{1-p}$，那么逻辑回归可以看作是对于$y=1|x$这一事件的对数几率的线性回归
    Since $\text{Pr}[y=+1|x;\theta] = h(\theta^{\top}x)=\frac{1}{1+e^{-\theta^{\top}x}}, \quad \text{Pr}[y=-1|x;\theta] = 1 - \text{Pr}[y=+1|x;\theta] = \frac{1}{1+e^{\theta^{\top}x}}$. Thus, $\text{Pr}[y|x;\theta] = \frac{1}{1+e^{-y\theta^{\top}x}}$
    假设我们学习到了$\theta$，则当$\text{Pr}[y|x;\theta] = \frac{1}{1+e^{-y\theta^{\top}x}} \ge \frac{1}{2}$ 时，我们把数据划分为正类，由这个式子可以推出等价于 $\theta^{\top}x \ge 0$.
    通过MLE，我们可以推导出Logistic损失函数：

没有闭形式的解，但因为是凸函数，可以用基于梯度的优化方法求解，且解一定是全剧最优解

降维

降维：即用一个低维度的向量表示原始高维度的特征
常见的降维方法：PCA、LDA、等距映射、局部线性嵌入、拉普拉斯特征映射、局部保留投影

主成分分析 (PCA)

线性、非监督
PCA旨在找到数据的主成分，用之表征原始数据，达到降维的目的：找到一个投影方向，最大化投影方差（数据分布得更为分散）
Tips：样本投影后的方差就是对应协方差矩阵的特征值，我们要找的最大方差对应于协方差矩阵的最大特征值，最佳投影方向就是相应的特征向量（次佳投影方向位于最佳投影方向的正交空间中，即第二大特征值对应的特征向量）

  • 中心化样本数据
  • 求样本协方差矩阵
  • 对协方差矩阵进行特征值分解，并将其从大到小进行排序
  • 取特征值前$d$ 大对应的特征向量$w_1, w_2, \dots, w_d$，通过以下映射将$n$ 维样本映射到$d$ 维：$x_i^{\prime} = [w_1^{\top}x_i, w_2^{\top}x_i, \dots, w_d^{\top}x_d]^{\top}$
    定义降维后的信息占比：$\eta = \sqrt{\frac{\sum_{i=1}^d \lambda_i^2}{\sum_{i=1}^n \lambda_i^2}}$
    注： 可以通过核映射对PCA进行扩展得到核主成分分析（KPCA），也可以通过流形映射的降维方法，比如等距映射，局部线性嵌入，拉普拉斯特征映射等对一些PCA效果不好的复杂数据集进行非线性降维操作
    另一个角度：最小平方误差（待完善）

线性判别分析（LDA）

线性、有监督
LDA为分类服务，旨在找到一个投影方向，使得投影后的样本尽可能按照原始类别分开：最大化类间距离和最小化类内距离
类间距离：$|w^{\top}(\mu_1-\mu2)|_2^2$，将整个数据集的类内方差定义为各个类分别的方差之和：$D_1+D_2$
将目标函数定义为类间距离和类内距离的比值，从而需要最大化的目标：
（后续推导待整理）
经过推导，我们最大化的目标对应了一个矩阵的特征值，于是LDA降维变成了一个求矩阵特征向量的问题
Notes：LDA对数据的分布做了很强的假设-每个类数据都是高斯分布，各个类的协方差相等；模型简单，表达能力有一定局限性，可以通过引入核函数扩展LDA方法以处理分布较为复杂的数据

K近邻 （KNN）

对于给定的训练数据集和新的样本，在训练数据集中找出与这个新的样本距离最近的k个样本点，然后多数投票原则决定该新样本点所属的分类
三要素：1. K值的选择（越小模型越复杂，交叉检验）；2.距离度量的选择（欧氏距离，马氏距离）； 3. 分类决策规则（多数表决）
KNN回归：在找到最近的k个实例之后，可以计算这k个实例的平均值作为预测值。或者还可以给这k个实例添加一个权重再求平均值，这个权重与度量距离成反比（越近权重越大）
KNN算法的优点：1.思想简单，理论成熟，既可以用来做分类也可以用来做回归；2.可用于非线性分类；3.训练时间复杂度为O(n)；3.准确度高，对数据没有假设，对outlier不敏感；
缺点：1.计算量大；2.样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）；3.需要大量的内存；
KD树：（待整理）

朴素贝叶斯 （Naive Bayes）

通过预测指定样本属于特定类别的概率$P(y_i|x)$来预测该样本的所属类别，即：$y = \text{argmax}_{y_i}P(y_i|x) =\frac{P(x|y_i)P(y_i)}{P(x)} $

K均值聚类 （K-Means）

通过迭代方式寻找K个簇（cluster）的一种划分方案，使得聚类结果对应的损失函数最小
损失函数可以定义为各个样本距离所属簇中心点的误差平方和：$J(c,\mu)=\sum_{i=1}^{n}|x_i-\mu_{c_i}|^2$, 其中$x_i$ 代表第$i$ 个样本，$c_i$是$x_i$所属的簇，$\mu_{c_i}$代表簇对应的中心点，$n$ 为样本总数。

算法步骤

  1. 数据预处理，如归一化、离群点处理等
  2. 随机选取K个簇中心，记为$\mu_1^{(0)}, \mu_2^{(0)}, \dots, \mu_K^{(0)}$
  3. 定义损失函数：$J(c,\mu)=\sum_{i=1}^{n}|x_i-\mu_{c_i}|^2$
  4. 令$t=0, 1, 2, \dots$ 为迭代步数，重复下面过程直到J收敛：
    4.1 对于每一个样本$x_i$，将其分配到距离最近的簇：$c_i^{(t)} \leftarrow \text{argmin}_k|x_i - \mu_k^{(t)}|^2$
    4.2 对于每一个类簇，重新计算该类簇的中心：$\mu_k^{(t+1)} \leftarrow \text{argmin}_{\mu}\sum_{i:c_i^{(t)}=k}|x_i - \mu|^2$
    优缺点
    缺点：受初始值和离群点的影响每次的结果都不稳定，得到的解通常不是全局最优而是局部最优，无法很好解决数据簇分布差别比较大的情况，不太适用于离散分类等
    优点：计算复杂度接近于线性 O(nKt)
    调优
  5. 数据归一化和离群点处理
  6. 合理选取K值：如手肘法（经验方法）， Gap Statistic方法（Gap(K) = E(logD_k) - logD_k, 只需找到最大Gap statistic所对应的K即可)
  7. 采用核函数 核K均值算法（核聚类方法的一种）

改进的模型
K-means++：（从改进初始值的角度）假设已经选取了n（0<n<K）个初始聚类中心，则在选取下一个聚类中心时，距离当前n个聚类中心越远的点会有更高的概率被选为下一个聚类中心
ISODATA算法：（当K值的大小不确定时）迭代自组织数据分析法 详见百面机器学习
手写Kmeans代码
待补充

集成学习

将多个分类器的结果统一成一个最终的决策，其中每个单独的分类器称为基分类器
(1) 找到误差相互独立的基分类器
(2) 训练基分类器
(3) 合并基分类器的结果：Voting 和 stacking 两种。前者投票多数表决的方式，后者串行的方式

Boosting

相当于串联基分类器，层层叠加，对前一层分错的样本给予更高的权重，是一种迭代式的学习过程，就像复习错题并改正一样。对于模型的偏差有相应的改善
训练好一个弱分类器，计算弱分类器的残差，作为下一个分类器的输入（但使得各分类器之间是强相关的，缺乏独立性，不会对降低方差有用）
比如Adaboost, 又比如梯度提升决策树（GBDT）：其核心是，每一棵树学的是之前所有树结论和的残差

Bagging （Bootstrap Aggregating）

相当于并联基分类器，有一种D&C的思想在里面，对训练样本多次采样，分别训练出多个不同的模型，然后做综合来减小模型的方差
比如随机森林
Bagging所采用的基分类器最好是本身对样本分布较为敏感的（即不稳定的分类器），这样bagging才有用武之地

最常用的基分类器是决策树，原因：

  1. 更方便地把样本权重整合到训练过程中，不需要使用过采样的方法来调整样本权重
  2. 表达能力和泛化能力可以通过调节树的层数来做折中
  3. 不同子集样本集合生成的决策树基分类器随机性较大

偏差：模型预测值和真实值差的期望 由偏差带来的误差通常在在训练误差上就能体现出来
方差：所有模型预测值的方差 由方差带来的误差通常体现在测试误差相对于训练误差的增量上

GBDT

梯度提升决策树。Boosting的一种，体现了从错误中学习的理念，基于决策树预测的残差进行迭代的学习
Gradient Boosting是Boosting的一大类算法，其基本思想是根据当前模型损失函数的负梯度信息来训练新加入的弱分类器，然后将训练好的弱分类器以累加的形式结合到现有模型中
在每一轮迭代中，首先计算出当前模型在所有样本上的负梯度，然后以该值为目标训练一个新的弱分类器进行拟合并计算出该弱分类器的权重，最终实现对模型的更新
GBDT中使用的决策树通常为CART

梯度提升 and 梯度下降
梯度下降：模型以参数化的形式表示，模型的更新等价于参数的更新
梯度提升：模型并不需要参数化表示，直接定义在函数空间中，从而大大扩展了可以使用的模型种类

GBDT优缺点
优点：1. 预测阶段计算速度快，树与树之前可以并行化计算；2. 分布稠密的数据集上，泛化能力和表达能力都很好；3. 采用决策树作为弱分类器使得其具有较好的解释性和鲁棒性，能自动发现特征间的高阶关系，不需要对数据进行特殊预处理
缺点：1. 在高维稀疏数据上表现不如SVM或者神经网络； 2. 处理文本分类特征问题上的优势不如处理数值特征时明显；3. 训练过程需要串行训练

XGboost

实现了对GBDT算法的改进
原始的GBDT算法基于经验损失函数的负梯度来构造新的决策树，只是在决策树构建完成后再进行剪枝
而XGBoost在决策树构建阶段就加入了正则项
XGBoost有特定的准则来选取最优分裂

与GBDT的联系和区别：

  1. GBDT是机器学习算法；XGBoost是该算法的工程实现
  2. 使用CART作为基分类器时，XGBoost显示地加入了正则项来控制模型的复杂度，有利于防止过拟合
  3. GBDT在模型训练时只使用了损失函数的一阶导数信息，而XGBoost对损失函数进行二阶泰勒展开，可以同时使用一阶和二阶导数
  4. 传统的GBDT采用CART作为基分类器，而XGBoost支持多种类型的基分类器，比如线性的
  5. 传统的GBDT在每轮迭代时使用全部数据，而XGBoost则可以支持对数据采用
  6. 传统的GBDT没有设计对缺失值进行处理，而XGBoost能够自动学习出缺失值处理侧拉