Machine Learning
如果公式无法正常显示，请尝试多刷新几次页面。
Unsupervised
Clustering
K-Means
算法复杂度不易控制 $ O(KNm) $ 。
K-Means时候出现的超级大群现象，如何解决?如何确定 K？
根据实际的应用场景，比如衣服分成 S, M, L 三类。
降维后可视化，观察然后选择 K。
将重构误差或对数似然作为 K 的函数绘制图形，并找出拐点（不是最低点）。
DBSCAN，省去选择 K 的步骤；或Hierarchical Clustering，观察得到的聚类树，来决定 K 的值。
优点：
计算时间短，速度快
容易解释
聚类效果还不错
缺点：
需要提前确定 K 值
对初始的聚类中心的选择比较敏感
对异常值敏感（因为聚类中心是取平均，因此出现了
K-Medoids）在欧式空间进行，不适用于 categorical 数据的聚类（
K-Medoids可以解决）。收敛到局部最优解而不是全局最优解
要求数据为凸集
不能识别噪音点
Bisecting K-Means
结合了
Hierarchical Clustering的思想，递增的进行聚类（先聚成 1 个类，然后 2 个，…，最后 K 个类)。SSE：Sum of Squared Error
K-Means++
首先选出 K 个聚类中心，然后执行原始的
K-Means算法。优点：
缺点：
- 它内在的有序性特性：下一个中心点的选择依赖于已经选择的中心点。k-means++和k-means||
参考
K-Medoids
聚类中心只能选择数据中的点（
K-Means是取聚类簇的点的平均值作为新的聚类中心）。这样就可以解决
K-Means不能处理 categorical 类型数据的缺点（K-Means需要求欧氏距离的平均值，而 categorical 类型数据的欧氏距离或平均值都没有意义）。由于中心点是在已有的数据点里面选取的，因此相对于 k-means 来说，不容易受到那些由于误差之类的原因产生的 Outlier 的影响，更加 robust 一些。
欧氏距离 在这里也不再使用，而是使用一个 dissimilarity matrix。漫谈 Clustering (2): k-medoids « Free Mind
参考
Spectral Clustering
Graph Cut就是Spectral Clustering的最基本/根本/原始的思想，最终求解可以转化成图拉普拉斯矩阵（Graph Laplacin）的求解。这也是大多数博客都讲到Graph Cut的原因。简单易学的机器学习算法——谱聚类(Spectal Clustering)谱聚类相当于先进行 非线性 降维，使原始数据点能够线性可分，最后再使用
K-Means聚类就可以得到比较好的聚类效果。相似度矩阵 与 邻接矩阵 不是同一个东西：对 相似度矩阵 进行切图后得到的是 邻接矩阵 。接下来的操作都是 邻接矩阵 针对进行的。
优点：
和
K-Medoids类似，Spectral Clustering只需要数据之间的 相似度矩阵 就可以了，而不必像K-Means那样要求数据必须是 N 维欧氏空间中的向量。由于抓住了主要矛盾，忽略了次要的东西，因此比传统的聚类算法更加健壮一些，对于不规则的误差数据不是那么敏感，而且 performance 也要好一些。许多实验都证明了这一点。事实上，在各种现代聚类算法的比较中，
K-Means通常都是作为 baseline 而存在的。计算复杂度比
K-Means要小，特别是在像文本数据或者平凡的图像数据这样维度非常高的数据上运行的时候。过程对数据结构并没有太多的假设要求，如
K-Means则要求数据为凸集。可以通过构造稀疏 similarity graph ，使得对于更大的数据集表现出明显优于其他算法的计算速度。
由于
Spectral Clustering是对图切割处理，不会存在像KMeans聚类时将离散的小簇聚合在一起的情况。无需像
GMM一样对数据的概率分布做假设。
缺点：
对于选择不同的 similarity graph 比较敏感（如 epsilon-neighborhood， k-nearest neighborhood，fully connected等）。
对于参数的选择也比较敏感（如 epsilon-neighborhood的epsilon，k-nearest neighborhood的k，fully connected的 ）。
谱聚类的松弛条件是对原问题的一个近似，但是并不能保证该近似是合适的，其误差有可能非常大，而且导致聚类问题不稳定；
构造相似度矩阵的尺度参数根据经验设定，尺度参数的选择对聚类效果影响较大；
同其他聚类方法一样，聚类数目的选择难以确定；
根据图最小分割的目标函数可知，谱聚类适用于均衡分类问题，即各簇之间点的个数相差不大，对于簇之间点个数相差悬殊的聚类问题，谱聚类则不适用。
参考
DBSCAN
如果 MinPts 不变，Eps 取得值过大，会导致大多数点都聚到同一个簇中，Eps 过小，会导致一个簇的分裂；如果 Eps 不变，MinPts 的值取得过大，会导致同一个簇中点被标记为离群点，MinPts 过小，会导致发现大量的核心点。简单之美 | DBSCAN聚类算法原理及其实现
可以把
DBSCAN看做一种树结构（非叶子节点为 core points，core points 的 Eps 区域内的点为子节点），则有：父节点和与其 直接相连 的子节点为 直接密度可达（子节点通过父节点密度可达，反过来不成立，因为子节点可能是叶节点，而叶节点不是 core points）。
从父节节点向下走到叶节点的路径上的节点之间是 密度可达（子节点通过父节点密度可达，反过来不成立，因为子节点可能是叶节点，而叶节点不是 core points）。
同一个树中的 任意 两个节点之间 互为 密度相连。
此时，与
并查集很像（但是并查集只考虑了连通性，而这里考虑了 Eps 与 MinPts）。聚类簇的构建就是类似于树的构建，使用的是
Breadth First Search，一个聚类簇就是一棵树。
优点：
不需要事先知道要形成的簇类的数量。
可以对 任意形状 的稠密数据集进行聚类，相对的，
K-Means之类的聚类算法一般只适用于凸数据集。可以在聚类的同时 识别噪声点，对数据集中的异常点不敏感。
聚类结果没有偏倚，相对的，
K-Means之类的聚类算法初始值对聚类结果有很大影响。
缺点：
如果样本集的密度不均匀、聚类间距差相差很大时，聚类质量较差，这时用
DBSCAN聚类一般不适合。聚类算法初探（五）DBSCAN如果样本集较大时，聚类收敛时间较长，此时可以对搜索最近邻时建立的 KD tree 或者 Ball tree 进行规模限制来改进。
调参相对于传统的
K-Means之类的聚类算法稍复杂，主要需要对距离阈值 \( \epsilon \) ，邻域样本数阈值MinPts联合调参，不同的参数组合对最后的聚类效果有较大影响。
参考
层次聚类
不过言归正传，这里要说的 Hierarchical Clustering 从某种意义上来说也算是解决了 K 的选择问题，因为在做 Clustering 的时候并不需要知道类别数，而得到的结果是一棵树，事后可以在任意的地方横切一刀，得到指定数目的 cluster ，按需取即可。
参考
聚类评估
有label
无label
参考
参考
Supervised
Classification
LR
用于解决二分类
可以认为是在
线性回归的基础上添加了一个Sigmoid函数，即把线性回归的输出作为Sigmoid的输入，Sigmoid的输出作为最终的结果。\[ g(x) = \frac {1} {1 + e^{-x}} \]
\[ g’(x) = g(x) \cdot (1 - g(x)) \]
概率函数如下。$ h_\theta(x) $ 函数的值有特殊的含义，它表示结果取 1 的概率。
\[ P(y|x;\theta) = (h_\theta(x))^y \cdot (1 - h_\theta(x))^{1-y}，y \in {0, 1 } \]
使用交叉熵 (Cross Entropy) 作为损失函数
为什么使用它作为 loss function？
答案：来源于最大释然估计。
参考
Softmax回归
当类别数 \( k = 2 \) 时，softmax 回归退化为 logistic 回归。这表明 softmax 回归是 logistic 回归的一般形式。
Softmax 回归 vs. k 个二元分类器：这一选择取决于你的类别之间是否互斥。
多层感知机
贝叶斯
生成模型
\( P(Y | X) = P(X \cdot Y) / P(X) = P(X | Y) \cdot P(Y) / P(X) \propto P(X | Y) \cdot P(Y) \)
假设某个体有 \( n \) 项特征（Feature），分别为 \( F_1、F_2、…、F_n \)。现有 \( m \) 个类别（Category），分别为 \( C_1、C_2、…、C_m \) 。贝叶斯分类器就是计算出概率最大的那个分类，也就是求下面这个算式的最大值：
\[
P(C|F_1F_2…F_n) = P(F_1F_2…F_n|C) \cdot P(C) / P(F_1F_2…F_n)
\]由于 $ P(F_1F_2…F_n) $ 对于所有的类别都是相同的，可以省略，问题就变成了求
\[ P(F_1F_2…F_n|C) \cdot P(C) \]
的最大值。
朴素贝叶斯分类器则是更进一步，假设所有特征都彼此条件独立，因此
\[
P(F_1F_2…F_n|C) \cdot P(C) = P(F_1|C)P(F_2|C) … P(F_n|C) \cdot P(C)
\]
上式等号右边的每一项，都可以从统计资料中得到，由此就可以计算出每个类别对应的概率，从而找出最大概率的那个类。如何处理连续变量？
离散化
如果无法离散化，解决办法见第一个参考。
Laplace 校准
另一个需要讨论的问题就是当 \( P(a|y)=0 \) 怎么办，当某个类别下某个特征项划分没有出现时，就是产生这种现象，这会令分类器质量大大降低。为了解决这个问题，我们引入
Laplace校准，它的思想非常简单，就是对每类别下所有划分的计数加 1，这样如果训练样本集数量充分大时，并不会对结果产生影响，并且解决了上述频率为 0 的尴尬局面。[2]贝叶斯网络
参考
决策树
决策树的特征分裂选择是”贪心“算法，也就是没有回溯的。
决策树类型的算法几乎不对数据的分布做任何统计学假设，这使它们能拟合复杂的非线性函数。
ID3
假设有一堆样本 \( D \)，那么 \( D \) 的熵：
\[ H(D)=-\sum_{i=1}^{m}{p_ilog_2(p_i)} \]
把 \( D \) 按照 特征 \( A \) 分割后，得到的总体的熵（各个部分的熵的加权和）：
\[ H(D|A) = \sum_{j=1}^{v} \frac{|D_j|}{|D|} H(D_j) \]
信息增益：
\[ Gain(A) = H(D) - H(D|A) \]
ID3算法就相当于选择一个特征进行分割，使得分割后的各个部分的 熵之和 最低，也就是 信息增益（原始的熵 - 分割后的各个部分的熵之和）最大。因为有多个特征可以选择，所以这里就选择使得信息增益 最大 的那个特征进行分割。特征为连续值的情况，需要对特征进行 离散化 处理。
但是
ID3算法倾向于选择特征的取值比较多的那个特征进行分割，导致训练出来的树非常的宽，然而深度不深，非常容易导致过拟合。所以有了C4.5。
C4.5
C4.5用 信息增益比 来决定对哪一个特征进行分割。算法中定义了 分裂信息：
\[ SplitInfo(A)=-\sum_{j=1}^{v}{\frac{|D_j|}{|D|}log_2{\frac{|D_j|}{|D|}}} \]
然后，通过该信息，定义 信息增益比 为：
\[ GainRatio(A)=\frac{Gain(A)}{SplitInfo(A)} \]C4.5选择信息增益比 最大 的特征作为分裂特征，而其余步骤和ID3完全一致。采用信息增益比则有效地抑制了
ID3倾向于选择取值比较多的特征进行分割的缺点：取值多的特征，以它作为根节点的单节点树的熵很大，即 \( H_A(D) \) 较大，导致信息增益比减小，在特征选择上会更加合理。
CART
CART在选择分裂节点的时候，用 基尼指数（Gini） 来挑选最合适的特征进行分裂。
\[ Gini(D) = 1 - \sum_{j=1}^{N}{P_j^2} \]其中，\( P_j \) 表示每个类别出现的概率。 同熵一样，基尼指数 的值越小，样本越纯。
对于分裂后整体的基尼指数，同样是先计算各个分裂部分的基尼指数，然后求加权和：
\[ Gini(D, A) = \sum_{j}^{k}{\frac{|D_j|}{|D|}} Gini(D_j) \]
与
ID3不同的是，如果特征的类别超过两类，CART不会根据特征的所有类别分出子树，而是选择其中的一个类别，根据是否属于这个类别分成两棵子树。也就是说CART每一个非叶子节点只有两个分支，所以CART是一棵 二叉树。这里还需要注意一点，在
ID3中，已经选择过的特征是没法在之后的节点分裂中被选上的，即每个特征只能被挑选一次。但CART没有这种限制，每次都是将所有特征放在一起，通过 基尼指数 选出最好的，哪怕这个特征已经在之前被挑选过了。
算法的终止条件
分割得到的部分只含有一个类别。
没有多余的特征可以分了，此时按照 voting 的方式决定这个部分的类别。（
ID3中用过的特征不能在接下的分割中使用，但是C4.5没有这样的情况）。
剪枝：防止过拟合
前剪枝
后剪枝
参考
集成学习
Averaging（各个弱学习器之间 没有 依赖关系）
Bagging
随机森林
各个决策树之间相互独立。每棵决策树都尽最大程度的生长，并且 没有剪枝 过程。
随机 的 有放回 的抽取训练样本。
如果不进行随机抽样，每棵树的训练集都一样，那么最终训练出的树分类结果也是完全一样的，这样的话完全没有 bagging 的必要；
如果不是有放回的抽样，那么每棵树的训练样本都是不同的，都是没有交集的，这样每棵树都是”有偏的”，都是绝对”片面的”（当然这样说可能不对），也就是说每棵树训练出来都是有很大的差异的；而随机森林最后分类取决于多棵树（弱分类器）的投票表决，这种表决应该是”求同”，因此使用完全不同的训练集来训练每棵树这样对最终分类结果是没有帮助的，这样无异于是”盲人摸象”。
也可以对特征进行抽样（即不一定用上所有的特征）。
降低时间复杂度
增加不同模型之间的差异性，降低过拟合的程度（如果有一个特征和标签特别强相关。选择划分特征时，如果不随机的从所用特征中随机取一些特征的话，那么每一次那个强相关特征都会被选取。那么每个数都会是一样的。这就是随机森林随机选取一些特征的作用，让某些树，不选这个强相关特征。）
参考
Boosting（各个弱学习器之间 有 依赖关系）
Boosting 是提升的意思。怎么提升？做法就是在前一次的训练的基础上，对某些分错的样本进行着重的训练。
Adaboost
Gradient boosting
参考
Bagging vs Boosting
区别
样本选择上：
Bagging：训练集是在原始集中 有放回 选取的，从原始集中选出的各轮训练集之间是 独立 的。
Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。
样例权重：
Bagging：使用均匀取样，每个样例的权重相等
Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大。
预测函数：
Bagging：所有预测函数的权重相等。
Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。
并行计算：
Bagging：各个预测函数可以并行生成
Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果。
参考
Other
Cross Entropy vs Log Likelihood
LR虽然是一个二分类器，但是它的输出是 一个 标量（经过sigmoid处理过的），所以它的 loss function 是Cross Entropy；相对的softmax regression是多分类器，输出的是k个标量（且k个标量的和为1，也就是说每个输出都是互斥的），因而不能用Cross Entropy，而要用Log Likelihood。因为上面的原因，对于多分类的问题：
参考
机器学习性能评估指标
针对二元分类器
混淆矩阵
FP：预测为
正例，但是它是负例。准确率(Accuracy)
精确率(Precision)
- 针对 预测结果 而言，
正确预测的正例占预测的正例的百分比。
- 针对 预测结果 而言，
召回率(Recall)
- 针对 样本 而言，
正确预测的正例占样本中真正的正例的百分比
- 针对 样本 而言，
F1 值
精确率和召回率两者是互斥的关系：一个变高，另一个就会变低。为了在两者都要求高的情况下，可以用F1来衡量。精确率和召回率都高时，F1值也会高。
ROC
TPR：就是召回率。
FPR：
错误预测的正例占样本中真正的负例的百分比。（与召回率对应）越靠近
左上角，表明模型的性能越好。ROC曲线不会随训练数据中正负样本的比例的变化而变化。虽然
ROC曲线相比较于 Precision 和 Recall 等衡量指标更加合理，但是其在高不平衡数据条件下的的表现仍然过于理想，不能够很好的展示实际情况。在多类别分类任务中你如何绘制 ROC 曲线？
AUC
AUC是指： 随机给定一个正样本和一个负样本，分类器输出该正样本为正的概率值比分类器输出该负样本为正的概率值要大的可能性。
参考
L1 vs L2
两者都是用来防止过拟合的，做法就是在loss function中加上对权重参数的惩罚项。
L1与L2的区别：画那个图
从梯度下降的偏导数比较：
L1总会减去一个固定的数值L2总是缩小为原来的固定倍数
L1倾向于使得权重变成 $ 0 $ （因而有特征选择的功能），L2倾向于选择较小的权重。
所以(不失一般性，假定：wi等于不为0的某个正的浮点数，学习速率η 为0.5)：
L1的权值更新公式为wi = wi - η * 1 = wi - 0.5 * 1，也就是说权值每次更新都固定减少一个特定的值(比如0.5)，那么经过若干次迭代之后，权值就有可能减少到0。
L2的权值更新公式为wi = wi - η * wi = wi - 0.5 * wi，也就是说权值每次都等于上一次的1/2，那么，虽然权值不断变小，但是因为每次都等于上一次的一半，所以很快会收敛到较小的值但不为0。
$$
\begin{align}
L_1 &= |w_1| + |w_2| + … + |w_n|, \frac{\partial L_1}{\partial w_i} = sign(w_i) = -1 or 1 \
L_2 &= \frac{1}{2} (w_{1}^{2} + w_{2}^{2} + … + w_{n}^{2}), \frac{\partial L_2}{\partial w_i} = w_i
\end{align}
$$L1 不可导
参考
过拟合，欠拟合
过拟合的本质：相对于数据规模，但是模型复杂度过高，导致模型过分地学习了训练样本中的噪音，从而削弱了模型的泛化能力。参数太多，模型复杂度过高，同时数据相对较少，或噪声相对较多。
为什么权重接近 0 的时候能防止过拟合？
最简单的解释就是加了先验。在数据少的时候，先验知识可以防止过拟合。最小二乘回归问题：加2范数正则等价于加了高斯分布的先验，加1范数正则相当于加拉普拉斯分布先验。
能够使得权重变得很小，这样就可以使得每个权重起到的作用都差不多，不会出现某些权重很大，某些权重非常小，导致对噪音比较敏感。这样就可以减轻过拟合（对
L1和L2都是这样的道理）。
减轻过拟合的方法
正则化
dropout
early stopping（根据验证数据集的效果好坏评价是否过拟合）
cross validation（相当于增加数据集）
data augmentation
减少特征的数量
降低模型的复杂度
当然，尽可能的扩大 training dataset 才是王道。
在训练之前记得 shuffle 一下数据集，一般是每次训练一个 epoch（就是把 training dataset 训练了一遍）后就 shuffle 一次，但是对于较大的数据集可以只 shuffle 一次，虽然这样会使得训练在第二个 epoch 就变得 biased，但是带来的好处可以 overcome 这种缺陷。
欠拟合的解决办法
增大训练时间
增加特征的数量
增大模型复杂度
Bias-Variance Tradeoff
Bias: “用所有可能的训练数据集训练出的所有模型的输出的平均值” 与 “真实模型” 的输出值之间的差异。Variance: 不同的训练数据集 训练出的模型的输出值之间的差异。说到底就是模型的拟合程度的选择问题：模型训练的效果太好，可能过拟合，generalization 比较差；反过来，想要模型的 generalization 好，就不能训练的太好（防止过拟合），但这样可能又会产生欠拟合。（正因为如此，我们才需要每训练一段事件就在 test 训练数据集上跑一下模型，来大概的表示模型的 generalization 能力。）
模型的 loss 包括 3 部分：
Bias,Variance,Noise。Noise 没法控制，所以只能权衡 bias 和 variance。（也就是上面说的用 test 数据集来测试模型的 generalizaiton 能力。）解决办法
cross validation
train-test
leave one
k-fold
这些方法都是为了使用一个 test 数据集来验证模型的 generalizaiton 能力。
参考
判别模型和生成模型对比
本质区别
discriminative model 估计的是条件概率分布(conditional distribution)p(class|context)；generative model 估计的是联合概率分布（joint probability distribution）p(class, context)。
生成模型，就是生成（数据的分布）的模型；判别模型，就是判别（数据输出量）的模型；
只要过程中要求解联合概率分布（或者数据的分布）的都是生成模型
GAN/VAE都是试图生成数据的概率分布，所以是一种生成模型。比较
训练时，二者优化准则不同
生成模型优化训练数据的联合分布概率；
判别模型优化训练数据的条件分布概率，判别模型与序列标记问题有较好的对应性。
对于观察序列的处理不同
生成模型中，观察序列作为模型的一部分；
判别模型中，观察序列只作为条件，因此可以针对观察序列设计灵活的特征。
训练复杂度不同
判别模型训练复杂度较高。
是否支持无指导训练
生成模型支持无指导训练。
另外，由生成模型可以得到判别模型，但由判别模型得不到生成模型。
参考
Graph Model
Hidden Markov Model
图模型，有向图
参考