Statistical Learning Method

统计学习方法

统计学习方法即机器学习方法，是计算机及其应用领域的一门重要学科。本书分为监督学习和无监督学习两篇，全面系统地介绍了统计学习的主要方法。

监督学习

统计学习及监督学习概论

1. 统计学习或机器学习是关于计算机基于数据构建概率统计模型并运用模型对数据进行分析与预测的一门学科。统计学习包括监督学习、无监督学习和强化学习。
2. 统计学习方法三要素 ----- 模型、策略、算法，对理解统计学习方法起到提纲挈领地作用。
3. 监督学习可以概括如下：从给定有限的训练数据出发，假设数据是独立同分布的，而且假设模型属于某个假设空间，应用某一评价准则，从假设空间中选取一个最优的模型，使它对已给训练数据及未知测试数据在给定评价标准意义下有最准确的预测。
4. 统计学习中，进行模型选择或者说提高学习的泛化能力是一个重要问题。如果只考虑减少训练误差，就可能产生过拟合现象。模型选择的方法有正则化与交叉验证。学习方法泛化能力的分析是统计学习理论研究的重要课题。
5. 分类问题、标准问题和回归问题都是监督学习的重要问题。统计学习方法包括感知机、k 近邻法、朴素贝叶斯法、决策树、逻辑斯谛 回归与最大熵模型、支持向量机、提升方法、EM 算法、隐马尔可夫模型和条件随机场。这些方法是主要的分类、标注以及回归方法。它们又可以归类为生成方法与判别方法。

感知机

1. 感知机是根据输入实例的特征向量 x 对其进行二类分类的线性分类模型：

   $$f(x) = sign(w \cdot x + b)$$

   感知机模型对应于输入空间（特征空间）中的分离超平面 w · x + b = 0。

2. 感知机学习的策略是极小化损失函数：

   $$\min_{w,b} L(w, b) = - \sum_{x_i \in M} y_i(w \cdot x_i + b)$$

   损失函数对应于误分类点到分离超平面的总距离。

3. 感知机学习算法是基于随机梯度下降法的对损失函数的最优化算法，有原始形式和对偶形式。算法简单且易于实现。原始形式中，首先任意选取一个超平面，然后用梯度下降法不断极小化目标函数。在这个过程中一次随机选取一个误分类点使其梯度下降。

4. 当训练数据集线性可分时，感知机学习算法是收敛的。感知机算法在训练数据集上的误分类次数 k 满足不等式：

   $$k \leq (\frac{R}{\gamma})^2$$

   当训练数据集线性可分时，感知机学习算法存在无穷多个解，其解由于不同的初值或不同的迭代顺序而可能有所不同。

k 近邻法

1. k 近邻法是基本且简单的分类与回归方法。k 近邻法的基本做法是：对给定的训练实例点和输入实例点，首先确定输入实例点的 k 个最近邻训练实例点，然后利用这 k 个训练实例点的类的多数来预测输入实例点的类。
2. k 近邻模型对应于基于训练数据集对特征空间的一个划分。k 近邻法中，当训练集、距离度量、k 值及分类决策规则确定后，其结果唯一确定。
3. k 近邻法三要素：距离度量、k 值的选择和分类决策规则。常用的距离度量是欧氏距离及更一般的 $L_p$ 距离。k 值小时，k 近邻模型更复杂；k 值大时，k 近邻模型更简单。k 值的选择反映了对近似误差与估计误差之间的权衡，通常由交叉验证选择最优的 k。常用的分类决策规则是多数表决，对应于经验风险最小化。
4. k 近邻法的实现需要考虑如何快速搜索 k 个最近邻点。kd 树是一种便于对 k 维空间中的数据进行快速检索的数据结构。kd 树是二叉树，表示对 k 维空间的一个划分，其每个结点对应于 k 维空间划分中的一个超矩形区域。利用 kd 树可以省去对大部分数据点的搜索，从而减少搜索的计算量。

朴素贝叶斯法

1. 朴素贝叶斯法是典型的生成学习方法。生成方法由训练数据学习联合概率分布 P（X，Y），然后求得后验概率分布 P（Y | X）。具体来说，利用训练数据学习P（X | Y）和 P（Y）的估计，得到联合概率分布：

   $$P(X, Y) = P(Y)P(X | Y)$$

   概率估计方法可以是极大似然估计或者贝叶斯估计。

2. 朴素贝叶斯法的基本假设是条件独立性，

   $$P(X = x | Y = c_k) = P(X^{(1)} = x^{(1)}, ..., X^{(n)} = x^{(n)}|Y = c_k) = \prod_{j=1}^nP(X^{(j)} = x^{(j)}|Y = c_k)$$

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

3. 朴素贝叶斯法利用贝叶斯定理与学到的联合概率模型进行分类预测。

   $$P(Y|X) = \frac{P(X,Y)}{P(X)} = \frac{P(Y)P(X|Y)}{\sum_{Y} P(Y)P(X|Y)}$$

   将输入 x 分到后验概率最大的类 y。

   $$y = \arg max_{c_k}P(Y = c_k) \prod_{j = 1}^n P(X_j = x^{(j)}|Y = c_k)$$

   后验概率最大等价于 0-1 损失函数时的期望风险最小化。

决策树

1. 分类决策树模型是表示基于特征对实例进行分类的树形结构。决策树可以转换成一个 if-then 规则的集合，也可以看作是定义在特征空间划分上的类的条件概率分布。

2. 决策树学习旨在构建一个与训练数据拟合很好，并且复杂度小的决策树。因为从可能的决策树中直接选取最优决策树是 NP 完全问题。现实中采用启发式方法学习次优的决策树。

   决策树学习算法包括 3 部分：特征选择、树的生成和树的剪枝。常用的算法有 ID3、C4.5 和 CART。

3. 特征选择的目的在于选取对训练数据能够分类的特征。特征选择的关键是其准则。常用的准则如下：

   （1）样本集合 D 对特征 A 的信息增益（ID3）

   $$g(D, A) = H(D) - H(D|A) \\ H(D) = -\sum_{k = 1}^K \frac{|C_k|}{D} \log_2 \frac{|C_k|}{D} \\ H(D|A) = \sum_{i = 1}^n \frac{D_i}{D} H(D_i)$$

   其中，$H（D）$是数据集 $D$ 的熵，$H（D_i）$是数据集 $D_i$ 的熵，$H(D|A)$ 是数据集 $D$ 对特征 $A$ 的条件熵。$D_i$ 是 $D$ 中特征 $A$ 取第 $i$ 个值的样本子集，$C_k$ 是 $D$ 中属于第 $k$ 类的样本子集。$n$ 是特征 $A$ 取值的个数，$K$ 是类的个数。

   （2）样本集合 D 对特征 A 的信息增益比（C4.5）

   $$g_R(D, A) = \frac{g(D, A)}{H_{A}(D)}$$

   其中，$g（D，A）$ 是信息增益，$H_A(D)$ 是 D 关于特征 A 的值的熵。

   （3）样本集合 D 的基尼指数（CART）

   $$\text{Gini}(D) = 1 - \sum_{k=1}^K(\frac{|C_k|}{D})^2$$

   特征 A 条件下集合 D 的基尼指数：

   $$\text{Gini}(D,A) = \frac{|D_1|}{|D|} \text{Gini}(D_1) + \frac{|D_2|}{D} \text{Gini}(D_2)$$

4. 决策树的生成。通常使用信息增益最大、信息增益比最大或基尼指数最小作为特征选择的准则。决策树的生成往往通过计算信息增益或其他指标，从根节点开始，递归地产生决策树。这相当于用信息增益或其他准则不断地选取局部最优的特征，或将训练集分割为能够基本正确分类的子集。

5. 决策树的剪枝。由于生成的决策树存在过拟合问题，需要对它进行剪枝，以简化学到的决策树。决策树的剪枝，往往从已生成的树上剪掉一些叶结点或叶结点以上的子树，并将其父结点或根结点作为新的叶结点，从而简化生成的决策树。

逻辑斯谛回归与最大熵模型

1. 逻辑斯谛回归模型是由以下条件概率分布表示的分类模型。逻辑斯谛回归模型可以用于二类或多类分类。

   $$P(Y = k|x) = \frac{\text{exp}(w_k \cdot x)}{1 + \sum_{k = 1}^{K - 1}}\exp(w_k \cdot x)$$

   这里，$x$ 为输入特征，$w$ 为特征的权值。

   逻辑斯谛回归模型源自逻辑斯谛分布，其分布函数 $F(x)$ 是 S 形函数。逻辑斯谛回归模型是由输入的线性函数表示的输出的对数几率模型。

2. 最大熵模型是由以下条件概率分布表示的分类模型。最大熵模型也可以用于二类或多类分类。

   $$P_w(y|x) = \frac{1}{Z_w(x)} \exp(\sum_{i = 1}^n w_if_i(x,y)) \\ Z_w(x) = \sum_y \exp(\sum_{i=1}^n w_if_i(x,y))$$

   其中，$Z_w(x)$ 是规范化因子，$f_i$ 为特征函数，$w_i$ 为特征的权值。

3. 最大熵模型可以由最大熵原理推导得出。最大熵原理是概率模型学习或估计的一个准则。最大熵原理认为在所有可能的概率模型（分布）的集合中，熵最大的模型是最好的模型。

   最大熵原理应用到分类模型的学习中，有以下约束最优化问题：

   $$\min \quad -H(P) = \sum_{x,y} \tilde{P}(x)P(y|x)\log P(y|x) \\ \text{s.t.} \quad P(f_i) - \tilde{P}(f_i) = 0, i= 1, 2, ..., n \\ \sum_y P(y|x) = 1$$

   求解此最优化问题的对偶问题得到最大熵模型。

4. 逻辑斯谛回归模型与最大熵模型都属于对数线性模型。

5. 逻辑斯谛回归模型及最大熵模型学习一般采用极大似然估计，或正则化的极大似然估计。逻辑斯谛回归模型及最大熵模型学习可以形式化为无约束最优化问题。求解该最优化问题的算法有改进的迭代尺度法、梯度下降法、拟牛顿法。

支持向量机

1. 支持向量机最简单的情况是线性可分支持向量机，或硬间隔支持向量机。构建它的条件是训练数据线性可分。其学习策略是最大间隔法。可以表示为凸二次规划问题，其原始最优化问题为：

   $$\min_{w,b} \quad \frac{1}{2}||w||^2 \\ \text{s.t.} \quad y_i(w \cdot x_i + b) - 1 \geq 0, \quad i = 1,2,...,N$$

   求的最优化问题的解为 $w^*$，$b^*$，得到线性可分支持向量机，分离超平面是：

   $$w^* \cdot x + b^* = 0$$

   分类决策函数是：

   $$f(x) = \text{sign} (w^* \cdot x + b^*)$$

   最大间隔法中，函数间隔与几何间隔是重要的概念。

   线性可分支持向量机的最优解存在且唯一。位于间隔边界上的实例点为支持向量。最优分离超平面由支持向量完全决定。

   二次规划问题的对偶问题是：

   $$\min \quad \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i \cdot x_j) - \sum_{i=1}^N \alpha_i \\ \text{s.t.} \quad \sum_{i=1}^N \alpha_iy_i = 0 \\ \alpha_i \geq 0, \quad i = 1,2, ..., N$$

   通常，通过求解对偶问题学习线性可分支持向量机，即首先求解对偶问题的最优值 $\alpha^*$，然后求最优值 $w^*$ 和 $b^*$，得出分离超平面和分类决策函数。

2. 现实中训练数据是线性可分的情形很少，训练数据往往是近似线性可分的，这时使用线性支持向量机，或软间隔支持向量机。线性支持向量机是最基本的支持向量机。

   对于噪声或例外，通过引入松弛变量 $\xi_i$，使其 “可分”，得到线性支持向量机学习的凸二次规划问题，其原始最优化问题是：

   $$\min_{w,b, \xi} \quad \frac{1}{2}||w||^2 + C\sum_{i=1}^N \xi_i \\ \text{s.t.} \quad \sum_{i=1}^N \alpha_i y_i = 0 \\ \alpha_i \geq 0, \quad i = 1,2, ..., N$$

   求的最优化问题的解为 $w^*$，$b^*$，得到线性可分支持向量机，其分离超平面是：

   $$w^* \cdot x + b^* = 0$$

   分类决策函数为：

   $$f(x) = \text{sign}(w^* \cdot x + b)$$

   线性支持向量机的解 $w^*$ 唯一但 $b^*$ 不一定唯一。

   对偶问题是：

   $$\min \quad \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i \cdot x_j) - \sum_{i=1}^N \alpha_i \\ \text{s.t.} \quad \sum_{i=1}^N \alpha_iy_i = 0 \\ 0 \leq \alpha_i \leq C, \quad i = 1,2, ..., N$$

   线性支持向量机的对偶学习算法，首先求解对偶问题得到最优解 $\alpha^*$，然后求原始问题最优解 $w^*$ 和 $b^*$，得出分离超平面和分类决策函数。

   对偶问题的解 $\alpha^*$ 中满足 $\alpha_{i}^* > 0$ 的实例点 $x_i$ 称为支持向量。支持向量可在间隔边界上，也可在间隔边界与分离超平面之间，或者在分离超平面误分一侧。最优分离超平面由支持向量完全决定。

   线性支持向量机学习等价于最小化二阶范数正则化的合页函数

   $$\sum_{i=1}^N[1 - y_i(w \cdot x_i + b)]_+ + \lambda||w||^2$$

3. 非线性支持向量机

   对于输入空间中的非线性分类问题，可以通过非线性变换将它转化为某个高维特征空间中的线性分类问题，在高维特征空间中学习线性支持向量机。由于在线性支持向量机学习的对偶问题里，目标函数与分类决策函数都只涉及实例与实例之间的内积，所以不需要显示地指定非线性变换，而是用核函数来替换当中的内积。核函数表示，通过一个非线性转换后的两个实例间的内积。具体地，$K(x,z)$ 是一个核函数，或正定核，意味着存在一个从输入空间 $\chi$ 到特征空间 $H$ 的映射 $\phi(x): \chi \to H$，对任意 $x, z \in \chi$，有：

   $$K(x,z) = \phi(x) \cdot \phi(z)$$

   对称函数 $K(x,z)$ 为正定核的重要条件如下：对任意 $x_i \in \chi, i=1,2,...,m$，任意正整数 $m$，对称函数 $K(x,z)$ 对应的 Gram 矩阵是半正定的。

   所以，在线性支持向量机学习的对偶问题中，用核函数 $K(x,z)$ 替代内积，求解得到的就是非线性支持向量机：

   $$f(x) = \text{sign} (\sum_{i=1}^N \alpha_i^*y_iK(x,x_i) + b^*)$$

4. SMO 算法

   SMO 算法是支持向量机学习的一种快速算法，其特点是不断地将原二次规划问题分解为只有两个变量的二次规划子问题，并对子问题进行解析求解，直到所有变量满足 KKT 条件为止。这样通过启发式的方法得到原二次规划问题的最优解。因为子问题有解析解，所以每次计算子问题都很快，虽然计算子问题次数很多，但在总体上还是高效的。

Boosting

1. Boosting 是将弱学习算法提升为强学习算法的统计学习方法。在分类学习中，提升方法通过反复修改训练数据的权值分布，构建一系列基本分类器（弱分类器），并将这些基本分类器线性组合，构成一个强分类器。代表性的 Boosting 是 AdaBoost 算法。

   AdaBoost 模型是弱分类器的线性组合：

   $$f(x) = \sum_{m=1}^M \alpha_mG_m(x)$$

2. AdaBoost 算法的特点是通过迭代每次学习一个基本分类器。每次迭代中，提高那些被前一轮分类器错误分类数据的权值，而降低那些被正确分类的数据的权值。最后，AdaBoost 将基本分类器的线性组合作为强分类器，其中给分类误差率小的基本分类器以大的权值，给分类误差率大的基本分类器以小的权值。

3. AdaBoost 的训练误差分析表明，AdaBoost 的每次迭代可以减少它在训练数据集上的分类误差率，这说明了它作为 Boosting 的有效性。

4. AdaBoost 算法的一个解释是该算法实际是前向分步算法的一个实现。在这个方法里，模型是加法模型，损失函数是指数损失，算法是前向分布算法。

   每一步中极小化损失函数

   $$(\beta_m, \gamma_m) = \arg min_{\beta,\gamma} \sum_{i=1}^N L(y_i, f_{m-1}(x_i) + \beta b(x_i;\gamma))$$

   得到参数 $\beta_m$，$\gamma_m$。

5. 提升树是以分类树或回归树为基本分类器的 Boosting。提升树被认为是统计学习中最有效的方法之一。

EM 算法及其推广

1. EM 算法是含有隐变量的概率模型极大似然估计或极大后验概率估计的迭代算法。含有隐变量的概率模型的数据表示为 $P(Y,Z|\theta)$。这里，$Y$ 是观测变量的数据，$Z$ 是隐变量的数据，$\theta$ 是模型参数。EM 算法通过迭代求解观测数据的对数似然函数 $L(\theta) = \log P(Y|\theta)$ 的极大化，实现极大似然估计。每次迭代包括两步：$E$ 步，求期望，即求 $\log P(Y,Z|\theta)$ 关于 $P(Z|Y,\theta^{(i)})$ 的期望：

   $$Q(\theta,\theta^{(i)}) = \sum_z \log P(Y,Z|\theta)P(Z|Y,\theta^{(i)})$$

   称为 $Q$ 函数，这里 $\theta^{(i)}$ 是参数的现估计值；$M$ 步，求极大，即最大化 $Q$ 函数得到参数的新估计值：

   $$\theta^{(i+1)} = \arg \max_\theta Q(\theta, \theta^{(i)})$$

   在构建具体的 EM 算法时，重要的是定义 $Q$ 函数。每次迭代中，EM 算法通过极大化 $Q$ 函数来增大对数似然函数 $L(\theta)$。

2. EM 算法在每次迭代后均提高观测数据的似然估计函数值，即

   $$P(Y|\theta^{(i + 1)}) \geq P(Y|\theta^{(i)})$$

   在一般条件下 EM 算法是收敛的，但不能保证收敛到全局最优。

3. EM 算法应用极其广泛，主要应用于含有隐变量的概率模型的学习。高斯混合模型的参数估计是 EM 算法的一个重要应用隐马尔可夫模型的无监督学习也是 EM 算法的一个重要应用。

4. EM 算法还可以解释为 $F$ 函数的极大-极大算法。EM 算法有许多变形，如 GEM 算法。GEM 算法的特点是每次迭代增加 $F$ 函数值（并不一定是极大化 $F$ 函数），从而增加似然函数值。

隐马尔可夫模型

1. 隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态的序列，再由各个状态随机生成一个观测从而产生观测序列的过程。

   隐马尔可夫模型由初始状态概率向量 $\pi$、状态转移概率矩阵 $A$ 和观测概率矩阵 $B$ 决定。因此，隐马尔可夫模型可以写成 $\lambda = (A, B, \pi)$。

   隐马尔可夫模型是一个生成模型，表示状态序列和观测序列的联合分布，但是状态序列是隐藏的，不可观测的。

   隐马尔可夫模型可以用于标注，这时状态对应着标记。标注问题是给定观测序列预测其对应的标记序列。

2. 概率计算问题。给定模型 $\lambda = (A, B, \pi)$ 和观测序列 $O = (o_1, o_2, ..., o_T)$，计算在模型 $\lambda$ 下观测序列 $O$ 出现的概率 $P(O|\lambda)$。前向-后向算法通过递推地计算前向-后向概率可以高效地进行隐马尔可夫模型的概率计算。

3. 学习问题。已知观测序列 $O = (o_1, o_2, ..., o_T)$ ，估计模型 $\lambda = (A, B, \pi)$ 参数，使得在该模型下观测序列概率 $P(O|\lambda)$ 最大。即用极大似然估计的方法估计参数。Baum-Welch 算法，也就是 EM 算法可以高效地对隐马尔可夫模型进行训练。它是一种无监督学习算法。

4. 预测问题。已知模型 $\lambda = (A,B,\pi)$ 和观测序列 $O = (o_1, o_2, ..., o_T)$，求对给定观测序列条件概率 $P(I|O)$ 最大的状态序列 $I = (i_1,i_2,...,i_T)$。维特比算法应用动态规划高效地求解最优路径，即概率最大的状态序列。

条件随机场

1. 概率无向图模型是由无向图表示的联合概率分布。无向图上的结点之间的连接关系表示了联合分布的随机变量集合之间的条件独立性，即马尔可夫性。因此，概率无向图模型也称为马尔可夫随机场。

   概率无向图模型或马尔可夫随机场的联合概率分布可以分解为无向图最大团上的正值函数的乘积的形式。

2. 条件随机场是给定输入随机变量 $X$ 条件下，输出随机变量 $Y$ 的条件概率分布模型，其形式为参数化的对数线性模型。条件随机场的最大特点是假设输出变量之间的联合概率分布构成概率无向图模型，即马尔可夫随机场。条件随机场是判别模型。

3. 线性链条件随机场是定义在观测序列与标记序列上的条件随机场。线性链条件随机场一般表示为给定观测序列条件下的标记序列的条件概率分布，由参数化的对数线性模型表示。模型包含特征及相应的权值，特征是定义在线性链的边与结点上的。线性链条件随机场模型的参数形式是最基本的形式，其他形式是其简化与变形，参数形式的数学表达式是：

   $$P(y|x) = \frac{1}{Z(x)} \exp(\sum_{i,k} \lambda_k t_k(y_{i-1},y_i,x,i + \sum_{i,l} \mu_l s_l(y_i,x,i)))$$

   其中，

   $$Z(x) = \sum_y \exp(\sum_{i,k}\lambda_k t_k(y_{i-1},y_i, x, i) + \sum_{i,l} \mu_l s_l(y_i,x,i))$$

4. 线性链条件随机场的概率计算通常利用前向-后向算法。

5. 条件随机场的学习方法通常是极大似然估计方法或正则化的极大似然估计，即在给定训练数据下，通过极大化训练数据的对数似然函数估计模型参数。具体的算法有改进的迭代尺度算法、梯度下降法、拟牛顿法等。

6. 线性链条件随机场的一个重要应用是标注。维特比算法是给定观测序列求条件概率最大的标记序列的方法。

无监督学习

无监督学习概论

1. 机器学习或统计学习一般包括监督学习、无监督学习、强化学习。

   无监督学习是指从无标注数据中学习模型的机器学习问题。无标注数据是自然得到的数据，模型表示数据的类别、转换或概率。无监督学习的本质是学习数据中的统计规律或潜在结构，主要包括聚类、降维、概率统计。

2. 无监督学习可以用于对已有数据的分析，也可以用于对未来数据的预测。学习得到的模型有函数 $z = g(x)$，条件概率分布 $P(z|x)$，或条件概率分布 $P(x|z)$。

   无监督学习的基本想法是对给定数据（矩阵数据）进行某种 “压缩”，从而找到数据的潜在结构，假定损失最小的压缩得到的结构就是最本质的结构。可以考虑发掘数据的纵向结构，对应聚类。也可以考虑发掘数据的横向结构，对应降维。还可以同时考虑发掘数据的纵向与横向结构，对应概率模型估计。

3. 聚类是将样本集合中相似的样本（实例）分配到相同的类，不相似的样本分配到不同的类。聚类分硬聚类和软聚类。聚类方法有层次聚类和 k 均值聚类。

4. 降维是将样本集合中的样本（实例）从高维空间转换到低维空间。假设样本原本存在于高维空间，或近似地存在于高维空间，通过降维则可以更好地表示样本数据的结构，即更好地表示样本之间的关系。降维有线性降维和非线性降维，降维方法有主成分分析。

5. 概率模型估计假设数据由一个概率模型生成，同时利用训练数据学习概率模型的结构和参数。概率模型包括混合模型、概率图模型等。概率图模型又包括有向图模型和无向图模型。

6. 话题分析是文本分析的一种技术。给定一个文本集合，话题分析旨在发现文本集合中每个文本的话题，而话题由单词的集合表示。话题分析方法有潜在语义分析、概率潜在语义分析和潜在狄利克雷分配。

7. 图分析的目的是发掘隐藏在图中的统计规律或潜在结构。链接分析是图分析的一种，主要是发现有向图中的重要结点，包括 PageRank 算法。

聚类方法

1. 聚类是针对给定的样本，依据它们属性的相似度或距离，将其归并到若干个 “类” 或 “簇” 的数据分析问题。一个类是样本的一个子集。直观上，相似的样本聚集在同类，不相似的样本分散在不同类。

2. 距离或相似度度量在聚类中起着重要作用。

   常用的距离度量有闵可夫斯基距离，包括欧氏距离、曼哈顿距离、切比雪夫距离以及马哈拉诺比斯距离。常用的相似度度量有相关系数、夹角余弦。

   用距离度量相似度时，距离越小表示样本越相似；用相关系数时，相关系数越大表示样本越相似。

3. 类是样本的子集，比如有如下基本定义：

   用 $G$ 表示类或簇，用 $x_i$，$x_j$ 等表示类中的样本，用 $d_{i,j}$ 表示样本 $x_i$ 与样本 $x_j$ 之间的距离。如果对任意的 $x_i,x_j \in G$，有：

   $$d_{i,j} \le T$$

   则称 $G$ 为一个类或簇。

   描述类的特征的指标有中心、直径、散布矩阵、协方差矩阵。

4. 聚类过程中用到类与类之间的距离也称为连接。类与类之间的距离包括最短距离、最长距离、中心距离、平均距离。

5. 层次聚类假设类别之间存在层次结构，将样本聚到层次化的类中。层次聚类又有聚合或自下而上、分裂或自上而下两种方法。

   聚合聚类开始将每个样本各自分到一个类：之后将相距最近的两类合并，建立一个新的类，重复此操作直到满足停止条件；得到层次化的类别。分裂聚类开始将所有样本分到一个类；之后将已有类中相距最远的样本分到两个新的类，重复此操作直到满足停止条件；得到层次化的类别。

   聚合聚类需要预先确定下面三个要素：

   （1）距离或相似度；

   （2）合并规则；

   （3）停止条件。

   根据这些概念的不同组合，就可以得到不同的聚类方法。

6. $k$ 均值聚类是常用的聚类算法，有以下特点。基于划分的聚类方法；类别数 $k$ 事先指定；以欧式距离平方表示样本之间的距离或相似度，以中心或样本的均值表示类别；以样本和其所属类的中心之间的距离的总和为优化的目标函数；得到的类别是平坦的、非层次化的；算法是迭代算法，不能保证得到全局最优。

   $k$ 均值聚类算法，首先选择 $k$ 个类的中心，将样本分到与中心最近的类中，得到一个聚类结果；然后计算每个类的样本的均值，作为类的新的中心；重复以上步骤，直到收敛为止。

奇异值分解

1. 矩阵的奇异值分解是指将 $m \times n$ 实矩阵 $A$ 表示为以下三个实矩阵乘积形式的运算

   $$A = {U\Sigma V^T}$$

   其中 $U$ 是 $m$ 阶正交矩阵，$V$ 是 $n$ 阶正交矩阵，$\Sigma$ 是 $m \times n$ 矩形对角矩阵

   $$\Sigma = \text{diag} (\sigma_1,\sigma_2,...,\sigma_p), \quad p = \min \lbrace m,n \rbrace$$

   其对角线元素非负，且满足

   $$\sigma_1 \ge \sigma_2 \ge \cdot \cdot \cdot \ge \sigma_p \ge 0$$

2. 任意给定一个实矩阵，其奇异值分解一定存在，但并不唯一。

3. 奇异值分解包括紧奇异值分解和截断奇异值分解。紧奇异值分解是与原始矩阵等秩的奇异值分解，截断奇异值分解是比原始矩阵低秩的奇异值分解。

4. 奇异值分解有明确的几何解释。奇异值分解对应三个连续的线性变换：一个旋转变换，一个缩放变换和另一个旋转变换。第一个和第三个旋转变换分别基于空间的标准正交基进行。

5. 设矩阵 $A$ 的奇异值分解为 $A = U \Sigma V^T$，则有

   $$A^TA = V(\Sigma^T\Sigma)V^T$$

   $$AA^T = U(\Sigma\Sigma^T)U^T$$

   即对称矩阵 $A^TA$ 和 $AA^T$ 的特征分解可以由矩阵 $A$ 的奇异值分解矩阵表示。

6. 矩形 $A$ 的奇异值分解可以通过求矩阵 $A^TA$ 的特征值和特征向量得到：$A^TA$ 的特征向量构成正交矩阵 $V$ 的列：从 $AA^T$ 的特征值 $\lambda_j$ 的平方根得到奇异值 $\sigma_i$，即

   $$\sigma_j = \sqrt{\lambda_j}，j = 1,2,...,n$$

   对其从大到小排列，作为对角线元素，构成对角矩阵 $\Sigma$；求正奇异值对应的左奇异向量，再求扩充的 $A^T$ 的标准正交基，构成正交矩阵 $U$ 的列。

7. 矩阵 $A = [{a_{ij}}]_{m \times n}$ 的弗罗贝尼乌斯范数定义为

   $$||A||_F = (\sum_{t=1}^m \sum_{j=1}^n (a_{ij})^2)^{\frac{1}{2}}$$

   在秩不超过 $k$ 的 $m \times n$ 矩阵的集合中，存在矩阵 $A$ 的弗罗贝尼乌斯范数意义下的最优近似矩阵 $X$。秩为 $k$ 的截断奇异值分解得到的矩阵 $A_k$ 能够达到这个最优值。奇异值分解是弗罗贝尼乌斯范数意义下，也就是平方损失意义下的矩阵最优近似。

8. 任意一个实矩阵 $A$ 可以由其外积展开式表示

   $$A = \sigma_1 u_iv_i^T + \sigma_1u_2v_2^T + ... + \sigma_nu_nv_n^T$$

   其中 $u_kv_k^T$ 为 $m \times n$ 矩阵，是列向量 $u_k$ 和行向量 $v_k^T$ 的外积，$\sigma_k$ 为奇异值，$u_k$，$v_k^T$，$\sigma_k$ 通过矩阵 $A$ 的奇异值分解得到。