Advanced Machine Learning: Unsupervised Learning, Sparse Learning, and Semi-Supervised Learning

聚类

从这一章开始 我们介绍一些经典的无监督学习手段 他们广泛的用于数据挖掘工作 尤其是EDA方向

聚类任务

聚类试图将数据集中的样本划分为若干个通常是不相交的子集,每个子集称 为一个“簇 ”(cluster).通过这样的划分，每个簇可能对应于一些潜在的概念

聚类过程仅能自动形成簇结构，簇所对应的概念语义需由使用者来把握

聚类既能作为一个单独过程，用于找寻数据内在的分布结构，也可作为分 类等其他学习任务的前驱过程.

聚类性能度量

参考 机器学习补充知识：聚类模型的性能度量

层次聚类

我们在多元统计中已经介绍过了 这里不进行重复的叙述 而是更换新的角度来阐述聚类的思想 多元统计分析中的系统聚类法

系统聚类是一种试图在不同层次对数据集进行划分，从而形成树形的聚类结构.数据集的划分可采用“自底向上”的聚合策略，也可采用 “自顶向下”的分拆策略. 层次聚类和系统聚类是一个东西

原型聚类

原型聚类亦称“基于原型的聚类”(prototype-based clustering) “原型”是指样本空间中具有代表性的点. 在现实聚类任务中极为常用

采用不同的原型表示、不同的求解方式, 将产生不同的算法 给出不一样的聚类结果

k 均值算法

原本的k均值算法是一个NP难问题 要求最小化平方误差

$$E=\sum_{i=1}^{k}\sum_{\boldsymbol{x}\in C_{i}}||\boldsymbol{x}-\boldsymbol{\mu}_{i}||_{2}^{2},$$

这并不容易计算 所以我们使用迭代的方式进行近似求解 在多元统计中介绍过了 多元统计分析中的动态聚类法 这个算法有自动停止的特点 不像系统聚类一样收敛为一类

k均值算法也有核化的手段，我们把数据映射到更高维度的空间来处理实现非线性的聚类，具体如何核化取决于我们的实际数据

学习向量量化

与 k 均值算法类似，”学习向量量化”（Learning Vector Quantization,简 称 LVQ ）也是试图找到一组原型向量来刻画聚类结构

不过 LVQ假设数据样本带有类别标记来辅助聚类，实际上是一种监督学习算法 训练的目标是找到一组$n$维原型向量 每个原型代表一个聚类簇

我们的算法思想为

1. 先初始化原型向量
2. 每个样本都找到离的最近的原型向量
3. 更新原型向量
4. 重复2 3 直到满足停止条件 核心在于如何更新原型向量 我们不能用前面直接均值的方法了 而用已有的分类标准来辅助我们的操作

直观上看，对样本$\boldsymbol{x}_j,$若最近的原型向量$p_i^*$ 与$x_j$ 的类别标记相同，则令$p_i$* 向$x_j$ 的方向靠拢， 此时新原型向量为

$$p^{\prime}=p_{i^{*}}+\eta\cdot(\boldsymbol{x}_{j}-\boldsymbol{p}_{i^{*}})$$

如果类别标记不同 则要求原理 也就是距离变化为$|(1+\eta)\cdot||p_{i^{*}}-x_{j}||_{2}$ 我们的$\eta$仍旧是学习率

高斯混合聚类

和前面不同的是 我们采用概率模型来表达聚类原型，我们各种模型来研究每个样本属于各个类别的概率。而不是给出一个确定的分类。

密度聚类

此类算法假设聚类结构能通过样本分布的紧密程度确定；密度聚类算法从样本密度的角度来考察样本之间的可连接性，并基于可连接样本不断扩展聚类簇以获得最终的聚类结果.

DBSCAN

DBSCAN是一种著名的密度聚类算法 基于一组邻域参数 刻画样本的紧密程度 对于给定的$n$维数据集 定义下面的概念

• $\epsilon$-邻域：对 $x_j\in D$, 其 $\epsilon$-邻域包含样本集 $D$ 中与 $\dot{x}_j$ 的距离不大于 $\epsilon$ 的样$\text{即 }N_{\epsilon}(\boldsymbol{x}_{j})=\{\boldsymbol{x}_{i}\in D\mid\mathrm{dist}(\boldsymbol{x}_{i},\boldsymbol{x}_{j})\leqslant\epsilon\};$
• 密度直达(directly density-reachable): 若$x_j$ 位于$x_i$ 的 $\epsilon$-邻域中，且$x_i$ 是核心对象，则称 $x_j$ 由 $x_i$ 密度直达；
• 密度可达(density-reachable): 对 $x_i$ 与 $x_j$,若存在样本序列 $p_1,p_2,\ldots,p_n$ 其中$\boldsymbol{p}_1=\boldsymbol{x}_i,\dot{p}_n\doteq\boldsymbol{x}_j$ 且$p_{i+1}$ 由$p_i$密度直达，则称 $x_j$ 由 $x_i$ 密度可达；
• 密度相连(density-connected): 对 $x_i$ 与 $x_j$, 若存在 $x_k$ 使得 $x_i$ 与 $x_j$ 均由$x_k$ 密度可达，则称 $x_i$ 与 $x_j$ 密度相连.（增加了一个新的样本作为连接）

基于这些概念 DNSCAN定义簇为 ： 由密度可达关系导出的最大的密度相连样本集合 也就是 以$x$为核心对象 所有密度可达样本组成的集合就是我们的簇

DBSCAN算法只需要 选定一个核心对象 找到它的簇 然后在剩余样本中找到新的核心对象 重复找簇的过程 知道我们认为可以结束了

最后没有被聚类的样本 称为噪声

核密度估计

核密度估计不是聚类方法，但是和聚类有着密切的联系。密度估计希望找到点密集的区域来确定未知的概率密度函数，这可以用于聚类。

作为一种无需参数的方法，他不假定存在某种概率模型，而是推断底层的概率密度。

一元核密度

累积分布函数的给出是非常容易的

$$\hat{F}(x)=\frac{1}{n}\sum_{i=1}^nI(x_i\leqslant x)$$

我们可以通过他的导数估计密度，考虑一个小窗口即可

$$\hat{f}(x)=\frac{\hat{F}(x+\frac{h}{2})-\hat{F}(x-\frac{h}{2})}{h}=\frac{k/n}{h}=\frac{k}{nh}$$ $h$的选取非常重要，适当大的$h$可以平滑密度的估计，过小的$h$会导致纳入的点太少而估计严重不准确

核密度估计依赖于一个非负、对称且积分为 1 的核函数$K$,即：$K(x)\geqslant0,K(-x)=$ $K(x)$ (对于所有$x$),且$\int K( x)$d$x= 1$。因此，$K$实际上是一个概率密度函数。

离散核 我们可以用离散核重写（实际的含义是完全等价的）前面的密度估计有

$$\hat{f}(x)=\frac{1}{nh}\sum_{i=1}^nK\left(\frac{x-x_i}{h}\right)$$

其中$K$为

$$\left.K(z)=\left\{\begin{array}{ll}1&|z|\leqslant\frac{1}{2}\\0&\text{其他情况}\end{array}\right.\right.$$

为了更好的起到平滑的作用，我们可以考虑 高斯核 定义为

$$K(z)=\frac{1}{\sqrt{2\pi}}\exp\left\{-\frac{z^2}{2}\right\}$$

此时代入的前面的$\hat{f}(x)$有

$$K\left(\frac{x-x_i}{h}\right)=\frac{1}{\sqrt{2\pi}}\exp\left\{-\frac{(x-x_i)^2}{2h^2}\right\}$$

此时更大一个区间的点都被以不同的概率权重纳入到了局部密度的估计，平滑效果更好

多元核密度

为估计在一个$d$维点$x=(x_1,x_2,\cdots,x_d)^\mathrm{T}$上的概率密度，定义$d$维的“窗口”为$d$维空间中的一个超立方体，即一个以$x$为中心且边长为$h$的超立方体。这样一个$d$维超立方体的体积为：

$$\mathrm{vol}(H_d(h))=h^d$$

类比一元的情况，我们可以写出核密度估计式

$$\hat{f}(x)=\frac{1}{nh^d}\sum_{i=1}^nK\left(\frac{x-x_i}{h}\right)$$

其中$K$是多元核函数，是一个多元的概率密度函数，而不是机器学习导论与监督学习：核方法里面介绍的核函数

我们可以把离散核定义为

$$\left.K(z)=\left\{\begin{array}{ll}1&|z_j|\leqslant\frac{1}{2}\\0&\text{其他情况}\end{array}\right.\right.$$

高斯核定义为

$$K(z)=\frac{1}{(2\pi)^{d/2}}\exp\left\{-\frac{z^\mathrm{T}z}{2}\right\}$$

代入 $z=\frac{{x-x_{i}}}{h}$ 有

$$K(\boldsymbol{z})=\frac{1}{(2\pi)^{d/2}}\exp\left\{-\frac{(\boldsymbol{x}-\boldsymbol{x}_i)^\mathrm{T}(\boldsymbol{x}-\boldsymbol{x}_i)}{2h^2}\right\}$$

最邻近核密度

前面的方法是寻找固定体积内的点，来进行核密度的估计；另一种方法是固定点的数目$k$ 允许体积变化；一般称为密度估计的$k$临近方法，也是非参数的方法

给定邻居的数目$k$,估计$x$处的密度如下：

$$\hat{f}(\boldsymbol{x})=\frac k{n\mathrm{vol}(S_d(h_{\boldsymbol{x}}))}$$

其中$h_x$是$x$到它的第$k$个最近邻居的距离，$vol(S_d(h_x))$是以$x$为中心、$h_x$为半径的$d$维超球体$S_d(h_x)$的体积。换句话说，宽度(半径)$h_x$现在是一个依赖于$x$和$k$的变量。

DENCLUE

在核密度的基础上，我们可以给出一种基于密度的通用聚类方法；通过梯度优化找到密度中的峰；然后找到密度大于一定阈值的区域。

定义：若点$x^*$是概率密度函数$f$的一个局部极大点，则称其为密度吸引子(density attractor) 。一个密度吸引子可以从$x$开始，通过梯度下降的方法来找到。也就是概率密度函数的梯度最大方向。经过推导我们可以给出下面的公式

$$x_{t+1}=\frac{\sum_{i=1}^nK(\frac{\boldsymbol{x}_t-\boldsymbol{x}_i}{h})\boldsymbol{x}_i}{\sum_{i=1}^nK(\frac{\boldsymbol{x}_t-\boldsymbol{x}_i}{h})}$$

定义：给定一个簇$C\subseteq D$,若所有的点 $x\in C$ 都被密度吸引到一个唯一的密度吸引子 $x^*$,使得$\hat{f}(x^*)\geqslant\xi$,其中$\xi$是一个用户定义的最小密度阈值，则称它为中心定义的簇(center-defined cluster),即：

$$\hat{f}(\boldsymbol{x}^*)=\frac1{nh^d}\sum_{i=1}^nK\left(\frac{x^*-x_i}h\right)\geqslant\xi$$

定义：一个任意形状的簇$C\subseteq D$是一个基于密度的簇(density-based cluster),若存在一组密度吸引子$x_1^*,x_2^*,\cdots,x_m^*$,使得：

• 每个点$x\in C$都被吸引到某个吸引子$x_i^*;$
• 每个密度吸引子的密度都大于$\xi$,即$\hat{f}(x_i^*)\geqslant\xi;$
• 任意两个密度吸引子$x_i^*$和$x_j^*$都是密度可达的，即存在一条从$x_i^*$到$x_j^*$的路径，使得所有在该路径上的点$y$都有$\hat{f}(y)\geqslant\xi$。

DENCLUE算法的思路如下

1. 计算每个点的密度吸引子$x_i^*$，如果大于阈值$\xi$，则将其加入吸引子集合$A$，对应点加入被点信息的集合$R(x_i^{*})$
2. 找到所有吸引子的最大子集 $C$ 保证其中任意一对吸引子密度可达
3. 这些吸引子的最大子集 $C$构成了基于密度的簇的种子，被吸引进去的点加入对应的簇，形成聚类结果

可以证明，DBSCAN 是基于通用核密度估计的聚类方法 DENCLUE 的一种特例。若令$h=\epsilon$且$\xi=$minpts,并使用一个离散核，则 DENCLUE 会得到与 DBSCAN 一样的簇结果。每个密度吸引子对应一个核心点，连通核心点的集合定义了基于密度的簇的吸引子集合。

还可以证明，在选取合适的$h$和$\xi$的情况下，K-means 也是基于密度的聚类的特例，且密度吸引子对应于簇中心点。此外，值得注意的是，基于密度的方法可以通过变化$\xi$阈值，生成层次式簇。例如，减小$\xi$值会使得几个簇合并到一起。同时，若峰密度大于减小了的$\xi$值，则可能会生成新的簇。

谱聚类与图聚类

本节研究在图上进行聚类，他和层次聚类，矩阵的谱分解，基于核的聚类都有一定的联系，最后我们会将其解释清楚。

图和矩阵

给定由$\mathbb{R}^d$中的$n$个点构成的数据集$D=\{x_i\}_i=1^n$,令$A$代表这些点之间的$n\times n$的成对相似性矩阵：

$$A=\begin{pmatrix}a_{11}&a_{12}&\cdots&a_{1n}\\a_{21}&a_{22}&\cdots&a_{2n}\\\vdots&\vdots&\cdots&\vdots\\a_{n1}&a_{n2}&\cdots&a_{nn}\end{pmatrix}$$

其中$A(i,j)=a_{ij}$表示点$x_i$和$x_j$之间的相似性描述性统计与可视化中的距离和相似系数。我们要求相似性是对称且非负的，即$a_{ij}=a_{ji}$且$a_{ij}\geqslant0$。

矩阵$A$可以看作一个带权(无向)图$G=(V,E)$的带权邻接矩阵，代表着邻接关系，这样就把样本转化为了图数据进行分析。

对于每个顶点$x_i$，我们可以计算他的度$d_i$

$$d_i=\sum_{j=1}^na_{ij}$$

据此我们可以导出度数矩阵为

$$\left.\Delta=\left(\begin{array}{cccc}d_1&0&\cdots&0\\0&d_2&\cdots&0\\\vdots&\vdots&\ddots&\vdots\\0&0&\cdots&d_n\end{array}\right.\right)=\begin{pmatrix}\sum_{j=1}^na_{1j}&0&\cdots&0\\0&\sum_{j=1}^na_{2j}&\cdots&0\\\vdots&\vdots&\ddots&\vdots\\0&0&\cdots&\sum_{j=1}^na_{nj}\end{pmatrix}$$

通过将邻接矩阵的每一行除以对应节点的度数，我们可以得到 归一化邻接矩阵 如下

$$\begin{gathered}M=\Delta^{-1}A=\begin{pmatrix}\frac{a_{11}}{d_1}&\frac{a_{12}}{d_1}&\cdots&\frac{a_{1n}}{d_1}\\\frac{a_{21}}{d_2}&\frac{a_{22}}{d_2}&\cdots&\frac{a_{2n}}{d_2}\\\vdots&\vdots&\ddots&\vdots\\\frac{a_{n1}}{d_n}&\frac{a_{n2}}{d_n}&\cdots&\frac{a_{nn}}{d_n}\end{pmatrix}\end{gathered}$$

然后，我们可以定义 图的拉普拉斯矩阵 如下

$$L=\Delta-A$$

即

$$\begin{pmatrix}\sum_{j\neq1}a_{1j}&-a_{12}&\cdots&-a_{1n}\\-a_{21}&\sum_{j\neq2}a_{2j}&\cdots&-a_{2n}\\\vdots&\vdots&\ddots&\vdots\\-a_{n1}&-a_{n2}&\cdots&\sum_{j\neq n}a_{nj}\end{pmatrix}$$

他是一个半正定的对称矩阵；一共有$n$个非负实数特征值，并且其特征向量是正交的； 图的拉普拉斯矩阵也可以先进行归一化，再计算度数矩阵做差，得到 归一化的图拉普拉斯矩阵

图切割

一个图的$k$路割希望得到一个良好的分割$C$，使得同一个簇的节点相似度较高，不同簇的节点相似度较低，这非常符合直觉。下面我们先介绍一些图切割的基本知识。

对于给定的带权图以及其相似度矩阵，任意$S,T\subset V$ 我们定义$W(S,T)$ 表示一个节点在$S$另一个节点在$V$内的权值和有

$$W(S,T)=\sum_{v_i\in S}\sum_{v_j\in T}a_{ij}$$

给定$S\subseteq V$,用$\bar{S}$表示与之互补的顶点集合，即$\bar{S}=V-S$。图中的一个 (顶点)割(vertext cut) 定义为将$V$划分为$S\subset V$和$\bar{S}$。割的权值(cut weight)定义为$S$和$\bar{S}$中的顶点构成的边的权值之和，即$W(S,\bar{S})$

给定一个包含$k$个簇的聚类$C=\{C_1,\cdots,C_k\}$,一个 簇$C_i$的大小(size) 定义为簇中节点的数目，即$|C_i|$。一个簇 $C_i$的容量(volume) 定义为所有包含顶点在簇内的边的权值之和：

$$\mathrm{vol}(C_i)=\sum_{v_j\in C_i}d_j=\sum_{v_j\in C_i}\sum_{v_r\in V}a_{jr}=W(C_i,V)$$

令$c_i$为簇指示向量，他满足

$$\left.c_{ij}=\left\{\begin{array}{ll}1&v_j\in C_i\\0&v_j\notin C_i\end{array}\right.\right.$$

下面我们给出矩阵运算形式的割的权值：

$$\begin{aligned}W(C_{i},\overline{C_{i}})&=\sum_{v_r\in C_i}\sum_{v_s\in V-C_i}a_{rs}=W(C_i,V)-W(C_i,C_i)\\&=c_i(\Delta-A)c_i=c_i^\mathrm{T}Lc_i\end{aligned}$$

他和相似度矩阵的拉普拉斯矩阵联系起来了

至此，预备知识介绍的差不多了

图聚类的目标函数（最小化）

聚类目标函数可以就是一个$k$路割的优化问题，我们希望寻找一些好的优化目标，分别介绍两种常用的。

比例割

$k$路割上的比例割(ratio cut)目标定义如下 $$\min_{\mathcal{C}}J_{rc}(\mathcal{C})=\sum_{i=1}^k\frac{W(C_i,\overline{C}_i)}{|C_i|}=\sum_{i=1}^k\frac{c_i^\mathrm{T}Lc_i}{c_i^\mathrm{T}c_i}=\sum_{i=1}^k\frac{c_i^\mathrm{T}Lc_i}{\|c_i\|^2}$$

比例割试图最小化从簇$C_i$到其他不在簇$\overline{C}_i$中的点的相似度之和，并将每个簇的大小考虑进去。可以观察到，当割的权值最小化且簇较大时，目标函数的值较小。

不幸的是，对于二值簇指示向量$c_i$,比例割目标是 NP 难的。一种显而易见的松弛方法是允许$c_i$取任意的实数值。

归一割

归一割(normalized cut)与比例割类似，只不过它会将每个簇的割权值除以簇的体积，而不是它的大小。目标函数给出为：

$$\min_{\mathcal{C}}J_{nc}(\mathcal{C})=\sum_{i=1}^k\frac{W(C_i,\overline{C}_i)}{\mathrm{vol}(C_i)}=\sum_{i=1}^k\frac{c_i^\mathrm{T}Lc_i}{c_i^\mathrm{T}\Delta c_i}$$

归一割也存在和比例割一样的优化问题，需要松弛后求解

谱聚类

根据前面给出的优化算法（虽然我们没有推导算法的具体求解过程与结果，但是这里可以提示，我们实际上只需要研究给定的矩阵，如拉普拉斯矩阵$L$，拉普拉斯矩阵的幂$L^s$；然后计算其特征值与特征向量，选择其中最大特征值或最小特征值的$k$个特征向量作为指示向量）

我们最终计算得到了一系列实值簇指示向量$u_i$ 分别为 $u_n...u_{n-k+1}$ 由于这些指示向量是松弛后求解的，所以他们不是二值的，因此仍需要进一步处理。 我们把他看成一个新的矩阵：

$$\left.U=\left(\begin{array}{cccc}|&|&&|\\u_n&u_{n-1}&\cdots&u_{n-k+1}\\|&|&&|\end{array}\right.\right)=\begin{pmatrix}u_{n,1}&u_{n-1,1}&\cdots&u_{n-k+1,1}\\u_{n,2}&u_{n-1,2}&\cdots&u_{n-k+1,2}\\|&|&\cdots&|\\u_{n,n}&u_{n-1,n}&\cdots&u_{n-k+1,n}\end{pmatrix}$$

每一行进行归一化处理：

$$y_i=\frac{1}{\sqrt{\sum_{j=1}^ku_{n-j+1,i}^2}}(u_{n,i},u_{n-1,i},\cdots,u_{n-k+1,i})^\mathrm{T}$$

目前每一行都是一个单位向量，如下

$$\left.Y=\left(\begin{array}{ccc}-&y_1^\mathrm{T}&-\\-&y_2^\mathrm{T}&-\\&\vdots&\\-&y_n^\mathrm{T}&-\end{array}\right.\right)$$

现在就可以利用K-means等快速聚类算法，将目前的$n$行向量看成$n$个点聚类为$k$个簇，就是最后的聚类结果。这样的谱聚类方法只适合处理归一化后的相似度矩阵与拉普拉斯矩阵

图聚类的目标函数（最大化）

我们再讨论两个聚类目标函数

平均权值 目标定义如下

$$\max_{\mathcal{C}}J_{aw}(\mathcal{C})=\sum_{i=1}^k\frac{W(C_i,C_i)}{|C_i|}=\sum_{i=1}^k\frac{c_i^\mathrm{T}Ac_i}{c_i^\mathrm{T}c_i}$$

我们仍旧需要松弛后求解，否则是一个NP难问题

平均权值与K-means

我们这里来讨论一个有趣的联系，若带权邻接矩阵$A$代表一对点的核值，并有$a_{ij}=K(x_i,x_j)$,则可以使用核K-means 的平方误差和目标来进行图聚类。SSE 目标给出为：

$$\begin{aligned}\min_{\mathcal{C}}J_{sse}(\mathcal{C})&=\sum_{j=1}^nK(\boldsymbol{x}_i,\boldsymbol{x}_j)-\sum_{i=1}^k\frac{1}{|C_i|}\sum_{\boldsymbol{x}_r\in C_i}\sum_{\boldsymbol{x}_s\in C_i}K(\boldsymbol{x}_r,\boldsymbol{x}_s)\\&=\sum_{j=1}^na_{jj}-\sum_{i=1}^k\frac{1}{|C_i|}\sum_{v_r\in C_i}\sum_{v_s\in C_i}a_{rs}\\&=\sum_{j=1}^na_{jj}-\sum_{i=1}^k\frac{c_i^\mathrm{T}Ac_i}{c_i^\mathrm{T}c_i}\\&=\sum_{j=1}^na_{jj}-J_{aw}(\mathcal{C})\end{aligned}$$

能看出，$\sum_{j=1}^na_{jj}$与聚类无关，最小化SSE就是最大化平均权值AW，两个问题殊途同归最后等价；对于这个NP难问题，核K-means使用贪心迭代求解，平均权值则研究其松弛问题

模块度 模块度希望讨论同一个簇内连接的程度 聚类目标写作

$$\begin{aligned}\max_{\mathcal{C}}J_{Q}(\mathcal{C})&=\sum_{i=1}^k\left(\frac{c_i^\mathrm{T}Ac_i}{\mathrm{tr}(\boldsymbol{\Delta})}-\frac{(\boldsymbol{d}^\mathrm{T}c_i)^2}{\mathrm{tr}(\boldsymbol{\Delta})^2}\right)\\&=\sum_{i=1}^k\left(c_i^\mathrm{T}\left(\frac{A}{\mathrm{tr}(\boldsymbol{\Delta})}\right)c_i-c_i^\mathrm{T}\left(\frac{d\cdot d_i^\mathrm{T}}{\mathrm{tr}(\boldsymbol{\Delta})^2}\right)c_i\right)\\&=\sum_{i=1}^kc_i^\mathrm{T}Qc_i\end{aligned}$$

其中$Q$是模块度矩阵为

$$Q=\frac{1}{\mathrm{tr}(\boldsymbol{\Delta})}\left(A-\frac{d\cdot d_i^\mathrm{T}}{\mathrm{tr}(\boldsymbol{\Delta})}\right)$$

仍旧需要松弛后求解

归一化模块度等价于平均权值，因此在某些情况下等价于核K-means

马尔可夫聚类

马尔可夫聚类利用将原本的有向图权值看作马尔科夫链的转移一步转移矩阵，希望通过模拟马氏链的转移来得到最终的聚类结果，下面我们简单介绍其思想。

给定一个图$G$的带权邻接矩阵$A$,对应的归一化邻接矩阵 为$M=\Delta^{-1}A$。矩阵$M$可以看作$n\times n$的转移矩阵(transition matrix),其中每个矩阵项$m_{ij}=\frac{a_{ij}}{d_i}$可以看作从节点$i$跳转到节点$j$的概率。他满足马氏链转移矩阵的各个条件

假设这个马氏链是齐次的，也就是转移概率矩阵和当前位置无关，那么我们可以计算他的$n$步转移概率矩阵。最后当$n$步转移概率矩阵收敛（以矩阵范数记）我们终止计算。

最后得到的转移概率矩阵可以画出转移概率图，根据图我们可以自然的发现聚类的簇，例如下矩阵

$$\boldsymbol{M}=\begin{pmatrix}&1&2&3&4&5&6&7\\1&0&0&0&1&0&0&0\\2&0&0&0&1&0&0&0\\3&0&0&0&1&0&0&0\\4&0&0&0&1&0&0&0\\5&0&0&0&0&0&0.5&0.5\\6&0&0&0&0&0&0.5&0.5\\7&0&0&0&0&0&0.5&0.5\end{pmatrix}$$

第一列和第一行表示点的编号，不是转移概率。

异常检测

最主流的异常检测算法类似于我们在 探索性数据分析：异常值处理中介绍的内容，里面介绍到了有些情况下异常反而是信息，因此需要进行识别，其中最主流的方法是基于概率进行处理，当样本出现的概率低于某个阈值后，我们就可以判断其存在异常。至于这个概率的获取，可能是使用生成模型估计，也可能基于密度手段。总之无监督异常检测的整体思路还是非常简单的

很多异常检测手段需要一些完全信息的样本进行微调，此时我们就应该去讨论到底在什么时候选择异常检测算法，还是选择监督学习算法。当我们只拥有极少量的标注样本，比如金融欺诈检测领域我们会有较少的欺诈案例和较多的无标注样本，我们知道其中的欺诈案例是相当少的，此时异常检测可能是比较合适的方法。

事实上，监督学习和异常检测使用两种完全不同的思路去理解数据，后者去建模正常数据的模型，然后将其中不正常发现。后者则是通过监督学习的方式识别不正常的样本，当这类样本过少的时候，他难以学习到所有的不正常模式，而异常检测可以避免这个问题。也就是监督学习对没见过的内容难以泛化，这由其算法本身限制。

异常检测更加依赖特征的选择，需要更加缜密的判断各个特征的价值以及其分布情况是否符合模型的需要，比监督学习要求更多。需要根据个人在这个领域的经验构造更加精妙的特征，剔除那些不必要的特征。

特征选择与稀疏学习

考虑最基本的数据框形式

特征选择所考虑的问题是特征具有“稀疏性”，即矩阵中的许多列与当前学习任务无关，通过特征选择去除这些列，提高模型效果 可解释度 降低训练的难度；

现在我们来考虑另一种稀疏性：$D$所对应的矩阵中存在很多零元素，但这些零元素并不是以整列、整行形式存在的

当样本具有这样的稀疏表达形式时,对学习任务来说会有不少好处，高度的稀疏性，使大多数问题变得线性可分 所以SVM在这种数据中会有着很好的效果同时,稀疏样本并不会造成存储上的巨大负担，因为稀疏矩阵已有很多高效的存储方法. 所以现在 这种稀疏性 是我们在追求的

我们发现 这种适当的稀疏 对我们进行模型的构建是有好处的 （当然过度的稀疏数据是不好的） 那么，若给定数据集$D$是稠密的，即普通非稀疏数据，能否将其转化为“稀疏表示 “（sparse representation）形式 从而享受稀疏的好处

显然，在一般的学习任务中(例如图像分类)并没有《现代汉语常用字表》 可用，我们需学习出这样一个“字典”. 为普通稠密表达的样本找到合适的字典，将样本转化为合适的稀疏表示形式，从而使学习任务得以简化，模型复杂度得以降低，

这通常称为“字典学习”(dictionary learning),亦称“稀疏编码”(sparse coding)

给定数据集$\{x_1,x_2,\ldots,x_m\}$,字典学习最简单的形式为

$$\min_{\mathbf{B},\alpha_i}\sum_{i=1}^m\|x_i-\mathbf{B}\alpha_i\|_2^2+\lambda\sum_{i=1}^m\|\alpha_i\|_1\:,$$

其中$\mathbf{B}\in\mathbb{R}^d\times k$为字典矩阵，$k$称为字典的词汇量，通常由用户指定$,\boldsymbol{\alpha}_i\in\mathbb{R}^k$则是样本$x_i\in\mathbb{R}^d$的稀疏表示.显然，优化式第一项是希望由$\boldsymbol\alpha_i$能很好地重构$x_i$,第二项则是希望$\alpha_i$尽量稀疏

半监督学习

未标记样本

在显示世界中 大量的样本没有标记（缺少因变量的信息）是非常常见的一种情况 ，若直接使用传统监督学习技术，则大量的未标记样本信息被浪费，并且可能由于标记样本的数据集太小导致训练的结果不好，那么我们该如何去利用这些未标记样本呢 这就是半监督学习：利用未标记样本的机器学习方法

如何把未标记样本纳入模型？ 最自然的方法当然是直接将未标记样本标记，不过这样消耗的资源可能太大了 所以我们尝试去寻找其他的方法

我们可以先用有标记的样本训练一个模型，然后根据模型去找到对模型的进步最有用的样本 然后进行标记；从而使用比较少的样本实现比较好的效果，这种学习方式称为 “主动学习”（active learning）, 其目标是使用尽量少的“查询”（query）来获得尽量好的性能.

如果不引入额外的标记（专家知识），未标记样本可以提高模型泛化性能吗？ 这事实上是可行的 可能略微的违背了我们传统的认知

事实上，未标记样本虽未直接包含标记信息，但若它们与有标记样本是从同样的数据源独立同分布采样而来，则它们所包含的关于数据分布的信息对建 立模型将大有裨益 也就是 我们利用未标记样本带来的特征分布信息帮助我们提升模型泛化性能

要利用未标记样本，必然要做一些将未标记样本所揭示的数据分布信息与 类别标记相联系的假设

最常见的是“聚类假设”(cluster assumption),即假设数据存在簇结构，同一个簇的样本属于同一个类 另一种常见的假设是“流形假设 “(manifold assumption),即假设数据分布在一个流形结构上，邻近的样本拥有相似的输出值.“邻近”程度常用“相似”程度来刻画

流行假设对输出值没有限制，适用的范围更广 也是目前我们主要采用的假设方式 对微分流形的学习需要一些要求

半监督学习可进一步划分为纯(pure)半监督学习和直推学习(transductive learning),前者假定训练数据中的未标记样本并非待预测的数据，而后者则假 定学习过程中所考虑的未标记样本恰是待预测数据，学习的目的就是在这些未标记样本上获得最优泛化性能

生成式方法

生成式方法(generative methods)是直接基于生成式模型的方法.此类方法 假设所有数据(无论是否有标记)都是由同一个潜在的模型“生成”的.

这个假设使得我们能通过潜在模型的参数将未标记数据与学习目标联系起来，而未标记数据的标记则可看作模型的缺失参数，通常可基于E M 算法进行极大似然估计求解.

此类方法的区别主要在于生成式模型的假设，不同的模型假设将产生不同的方法.

给定样本$x$,其真实类别标记为$y\in\mathcal{Y}$,其中$\mathcal{Y}=\{1,2,\ldots,N\}$为所有可能的类别.假设样本由高斯混合模型生成，且每个类别对应一个高斯混合成分.换言之，数据样本是基于如下概率密度生成：

$$p(\boldsymbol{x})=\sum_{i=1}^N\alpha_i\cdot p(\boldsymbol{x}\mid\boldsymbol{\mu}_i,\boldsymbol{\Sigma}_i)\:,$$

其中，混合系数$\alpha_i\geqslant0,\sum_{i=1}^N\alpha_i=1;p(\boldsymbol{x}\mid\boldsymbol{\mu}_i,\boldsymbol{\Sigma}_i)$是样本$x$属于第$i$个高斯混 合成分的概率；$\boldsymbol{\mu}_i$和$\boldsymbol{\Sigma}_i$为该高斯混合成分的参数.

使用MLE估计 EM求解 就可以判断出类型信息了

半监督SVM

半监督支持向量机 (Semi-Supervised Support Vector Machine,简称S3VM) 是支持向量机在半监督学习上的推广.

在不考虑未标记样本时，支持向量机试图找到最大间隔划分超平面，而在考虑未标记样本后，S3VM 试图找到能将两类有标记样本分开，且穿过数据低密度区域的划分超平面，

这里的基本假设是“低密度分隔”(low-density separation), 显然，这是聚类假设在考虑了线性超平面划分后的推广.

至于如何进行求解这里就不介绍了

图半监督学习

给定一个数据集，我们可将其映射为一个图，数据集中每个样本对应于图中一个结点，若两个样本之间的相似度很高(或相关性很强)，则对应的结点之间存在一条边，边的 “强度” (strength)正比于样本之间的相似度(或相关性) 这是图机器学习的思想

我们可将有标记样本所对应的结点想象为染过色，而未标记样本所对应的结点尚未染色.于是，半监督学习就对应于“颜色”在图上扩散或传播的过程

基于分歧的方法

与生成式方法、半监督SVM、图半监督学习等基于单学习器利用未标记数据不同，基于分歧的方法(disagreement-based methods)使用多学习器，而学习器之间的“分歧”(disagreement)对未标记数据的利用至关重要.

“协同训练”(co-training)是此类方法的重要代表，它最初是针对“多视图”(multi-view)数据设计的，因此也被看作“多视图学习”(multi-view learning)的代表.在介绍协同训练之前，我们先看看什么是多视图数据.

在不少现实应用中，一个数据对象往往同时拥有多个“属性集”(attribute set),每个属性集就构成了一个“视图”(view).

例如对一部电影来说，它拥有多个属性集：图像画面信息所对应的属性集、声音信息所对应的属性集、字幕信息所对应的属性集、甚至网上的宣传讨论所对应的属性集等.每个属性集都可看作一个视图.

于是，一个电影片段可表示为样本$(\langle\boldsymbol{x}^1,\boldsymbol{x}^2\rangle,y)$,其中$x^i$是样本在视图$i$中的示例，即基于该视图属性描述而得的属性向量，不妨假定$x^{1}$为图像视图中的属性向量，$x^2$为声音视图中的属性向量；$y$是标记，假定是电影的类型，例如“动作片”、“爱情片”等.$(\langle x^1,x^2\rangle,y)$这样的数据就是多视图数据.

假设不同视图具有“相容性”(compatibility),即其所包含的关于输出空间$\gamma$的信息是一致的：令$\gamma^{1}$表示从图像画面信息判别的标记空间，$\gamma^{2}$表示从声音信息判别的标记空间，则有$\mathcal{Y}=\mathcal{Y}^1=\mathcal{Y}^2$, 显然，在“相容性”基础上，不同视图信息的“互补性”会给学习器的构建带来很多便利.

协同训练正是很好地利用了多视图的“相容互补性”,假设数据拥有两个充分(sufficient)且条件独立视图，“充分”是指每个视图都包含足以产生最优学习器的信息、“条件独立”则是指在给定类别标记条件下两个视图独立.在此情形下，可用一个简单的办法来利用未标记数据：

首先在每个视图上基于有标记样本分别训练出一个分类器，然后让每个分类器分别去挑选自己“最有把握的”未标记样本赋予伪标记，并将伪标记样本提供给另一个分类器作为新增的有标记样本用于训练更新…….这个“互相学习、共同进步”的过程不断迭代进行，直到两个分类器都不再发生变化，或达到预先设定的迭代轮数为止. 分类置信度的设置取决于学习器的类型

协同训练过程虽简单，但令人惊讶的是，理论证明显示出，若两个视图充分且条件独立，则可利用未标记样本通过协同训练将弱分类器的泛化性能提升到任意高. 不过，视图的条件独立性在现实任务中通常很难满足，因此性能提升幅度不会那么大，但研究表明，即便在更弱的条件下， 协同训练仍可有效地提升弱分类器的性能

协同训练算法本身是为多视图数据而设计的，但此后出现了一些能在单视图数据上使用的变体算法，它们或是使用不同的学习算法或使用不同的数据采样 甚至使用不同的参数设置 来产生不同的学习器，也能有效地利用未标记数据来提升性能.后续理论研究发现，此类算法事实上尤需数据拥有多视图，仅需弱学习器之间具有显著的分歧（或差异），即可通过相互提供伪标记样本的方式来提升泛化性能 各种方法都是为了产生分歧 是否具有多视图设计是不重要的