知识点一 贝叶斯分类

贝叶斯判别准则：已知各个分类的发生概率，判断某一事件或物品属于哪一个分类，比较$P(w_1|x)与P(w_i|x)$的大小，大的那个就是x所属类别

连续性随机变量使用条件概率密度函数，离散型随机变量使用条件概率
$$\begin{gathered} 若l_{12}(x)=\frac{p(x|w_1)}{p(x|w_2)}>\frac{P(w_2)}{P(w_1)},则x\in w_1 \\ 若l_{12}(x)=\frac{p(x|w_1)}{p(x|w_2)}<\frac{P(w_2)}{P(w_1)},则x\in w_2 \end{gathered}$$
其中，$l_{12}称为似然比，P(w_2)/P(w_1)={\theta }_{21}$称为似然比的判决阈值，此判别称为贝叶斯判别。

1. 两类单一属性值情况
   • 解题步骤

2. 朴素贝叶斯分类(多类多属性，属性条件独立)

   • 解题步骤：

     • 已知$P(w_i)发生的概率，也知道P(x_j|w_i)发生的概率，其中x_j是X的一个属性值$
     • 由贝叶斯定理和条件独立假设得(朴素贝叶斯就是将设各个特征之间相互独立)

     $$\begin{array}{r}P(w_i|X=X_j)=\frac{P(w_i){\prod }_{k=1}^{n}P(X_j^k|w_i)}{{\sum }_{i=0}^{n}P(w_i){\prod }_{k=1}^{n}P(X_j^k|w_j)}\end{array}$$

     ​ 由上式可以计算出$X_i属于w_i的所有可能概率，去最大值即为分类结果$

3. 贝叶斯最小风险判别

   • 首先列出各种判断所对应的风险值
   • 计算条件概率密度或者条件概率
   • 根据条件概率/条件概密求出似然比
   • 根据先验概率和风险值计算出阈值
   • 例题

​

4. 贝叶斯最小风险多类情况

   • 当L(损失函数)取如下值：

     

​ 可得判别函数：
$$d_i(x)=p(x|w_i)P(w_i),i=1,2,3\dots ,M$$
​ 则对于全部$j\ne i,若d_i(x)>d_j(x),则x\in w_i$

5. 正态分布模式的贝叶斯判别函数
   $$\begin{gathered} M种模式类别的多变量正态判别 \\ {d}_i(x)=lnP(w_i)-\frac{1}{2}ln|C_i|-\frac{1}{2}(x-m_i)C_i^{-1}(x-m_i),i=1,2,\dots ,M \end{gathered}$$

知识点二 贝叶斯分类器的参数估计

1. 均值，协方差矩阵的非随机参数估计

   设模式的类概率密度函数为$p(x)$其均值向量定义为：
   $$\begin{gathered} m=E(x)={\int }_{x}xp(x)dxx=(x_1,x_2,\dots ,x_n{)}^T,m=(m_1,m_2,\dots ,m_n{)}^T \\ 估计量\hat{m}为: \\ \hat{m}=\frac{1}{N}\sum _{j=1}^N{x}^j \end{gathered}$$
   协方差矩阵写成向量的形式为:
   C=E{(x−m)(x−m)T}=E{xxT}−mmT估计值为(N>>1):C^≈1N∑j=1N(xj−m^)(xj−m^)T C =E\{(x-m)(x-m)^T\}=E\{xx^T\}-mm^T\\ 估计值为(N>>1):\\ \hat{C}\approx \frac{1}{N}\sum_{j=1}^N(x^j-\hat{m})(x^j-\hat{m})^T C=E{(x−m)(x−m)T}=E{xxT}−mmT估计值为(N>>1):C^≈N1​j=1∑N​(xj−m^)(xj−m^)T

   1. 可以迭代的运算形式

   假设有$N$个样本的均值估计量，再加一个为：
   $$\hat{m}(N+1)=\frac{1}{N+1}[N\hat{m}(N)+x^{N+1}]$$
   协方差矩阵估计量的迭代运算：

   

   2. 具体实例：

2. 参数的贝叶斯估计(样本越大预测越准确)

   

   

知识点三 判别函数

1. 线性判别函数

   • 多类情况1

     用线性判别函数将属于$w_1$类的模式与不属于$w_i$类的模式分开。

     共需要$M$个判别函数

     例题：

     

   • 多类情况2

     采用每对划分，即$w_i/w_j$两分法，此时一个判别界面只能分开两种类别，但不能把它与其余所有的界面分开。分开$M类模式需要M(M-1)/2$个判别函数

     存在不确定区域：若所有$d_{ij}(x),找不到\forall j\ne i,d_{ij}(x)>0$的情况

     重要性质：$d_{ij}=-d_{ji}$

     例题：

     

     分类失败。

   • 多类情况3

     没有不确定区域的$w_i/w_j$两分法。

     对应$M类情况，需要M个判别函数$

     例题：

     

     

   • 多类情况1和多类情况2比较

     1. 对于M类模式的分类，多类情况1需要M个判别函数，而多类情况2需要M (M -1)/2个判别函数，当M*较大时，后者需要更多的判别式（这是多类情况2的一个缺点）。

     2. 采用多类情况1时，每一个判别函数都要把一种类别的模式与其余M-1种类别的模式分开，而不是将一种类别的模式仅与另一种类别的模式分开。

     3. 由于一种模式的分布要比M-1种模式的分布更为聚集，因此多类情况2对模式是线性可分的可能性比多类情况1更大一些（这是多类情况2的一个优点）。

2. 广义线性判别函数

   • 广义线性判别函数就是将非线性判别函数升维化为线性判别函数。

   • 对于$n维x向量，若用r次多项式，d(x)的权系数的总项数为:N_w=C_{n+r}^r=\frac{(n+r)!}{r!n!},d(x)$是判别界面，实际情况一般只会遇到2次多项式。

     

     

     • 广义线性判别实例

       

3. 分段线性判别函数

   • 最小距离法

     

     对于各类交错分布的情况，若再用每类一个均值代表点产生最小距离分类器，就会产生很明显的错误率。在这种情况下，可以运用聚类方法将一些类分解成若干个子类，再用最小距离分类。如一下情况：

     

4. Fisher线性判别(主要是为了降维)

   主要任务：找到好的投影线，去降维。

   Fisher准则函数中的基本参量：

   

   • 两类情况下：

     • Fisher线性判别的准则函数：
       $$J_F(w)=\frac{w^T{S}_{b}w}{w^T{S}_{w}w},其中S_b是类间离散度矩阵，S_w是总样本类内离散度矩阵$$

     • Fisher线性判别最优投影方向为：
       $$w^{\ast }=S_w^{-1}(m_1-m_2),其中m_1是w_1(第一类)的样本均值，m_2是w_2(第二类)的样本均值$$

   • 多类情况下：不做重点

5. 感知器算法

   • 目的：若判别函数的形式确定，只需要求出每个项的系数即可，感知器算法采用一种“赏罚”机制来通过样本训练出系数。

   • 感知器算法通式：

   $$w(k+1)=\{\begin{array}{l}w(k)if{w}^T(k)x^k>0\\ w(k)+C{x}^{k}if{w}^T(k)x^k\le 0\end{array}$$

   • 感知器算法收敛性：

     只要模式类别是线性可分的，就可以在有限的迭代步数里求出权向量。

   • 例子

     

     

   • 多类情况

     感知器算法的多类情况是根据，多类情况3扩展的

   • 例子：

     

     

     

     

6. 可训练的确定性分类器的迭代算法

   • 梯度法

     定义：

     

     具体算法：

     

   • 最小平方误差(LMSE)算法

     H-K算法$w(k)和b(k)迭代式：$
     $$\begin{gathered} X^{\#}=(X^{T}X{)}^{-1}{X}^T \\ w(1)=X^{\#}b(1) \\ e(k)=Xw(k)-b(k) \\ w(k+1)=w(k)+C{X}^{\#}|e(k)| \\ b(k+1)=b(k)+C[e(k)+|e(k)|] \\ 注:b(1)和C都是自己取值，一般都取1,b是N为向量。 \end{gathered}$$
     例子：

     

7. 小结，固定增量和LMSE对比

   固定增量算法：实现相对简单，可直接引伸到多类模式的分类情况，但未提供模式线性可分的测试特征；

   LMSE算法：相对复杂，需要对$X^{T}X$求逆（维数高时求逆比较困难），但对两类情况，提供了线性可分的测试特征。

8. 势函数—非线性分类方法

   也是一种迭代求解判别函数的算法，通过样本训练出判别函数，主要在于势函数的选择。

   思路：

   • 第一步：确定势函数

   • 第二步：将第一个样本代入势函数，求得初始的判别函数

   • 第三步：将下一个样本代入判别函数，若分类正确则判别函数不变，若分类错误，则进行矫正，矫正方法和矫正系数为$K(x)$是积累位势即判别函数，$K(x,x^{k+1})是势函数$：

     

   • 第四步：对所有样本重复第三步

   • 第五步：若所有样本都分类正确则结束，否者重复代入所有样本进行第二轮迭代。

   两类势函数：

   

   • 例题：

     

     

     

     

     

知识点四 特征选择和提取

1. 对于独立特征的选择准则

   • 类别可分性准则应具有这样的特点，即不同类别模式特征的均值向量之间的距离应最大，而属于同一类的模式特征，其方差之和应最小。（高内聚，底耦合）
   • 假设个原始特征测量值是统计独立的，此时，只需对训练样本的n个测量值独立地进行分析，从中选出m个最好的作为分类特征即可。
   • 对于$w_i$和$w_j$两类训练样本地特征选择

   ​ 例：对于$w_i和w_j$两类训练样本,假设其均值向量为$m_i和m_j$,其$k$维方向的分量为$m_{ik}和m_{jk}$,方差为${\sigma }_{ik}^2和{\sigma }_{jk}^2$，定义可分性准则函数：
   $$G_k=\frac{(m_{ik}-m_{jk}{)}^2}{{\sigma }_{ik}^2+{\sigma }_{jk}^2},k=1,2,\dots ,n$$
   则$G_k$为正值。$G_k$值越大，表示测度值的第$k$个分量对分离$w_i和w_j$两类越有效。将$G_k,k=1,2,\dots ,n$按大小排队，选出最大的m个对应的测度值作为分类特征，即达到特侦选择的目的。

   利用$G_k$可以进行分类以及无法进行分类的情况：

   • 可进行分类：（a）中特征$x_k$的分布有很好的可分性，通过它足以分离$w_i和w_j$两种类别；
   

   • 不可进行分类的情况：

     • （b）中的特征分布有很大的重叠，单靠$x_k$达不到较好的分类，需要增加其它特征；
     • （c）中的$w_i$类特征$x_k$的分布有两个最大值，虽然它与j的分布没有重叠，但计算$G_k$约等于0，此时再利用$G_k$作为可分性准则已不合适。
   

   总结

   • 一般特征的散布矩阵准则

   ​ 类内：Sw=∑i=1MP(wi)E{(x−mi)(x−mi)T∣wi}S_w = \sum\limits_{i=1}^MP(w_i)E\{(x-m_i)(x-m_i)^T|w_i\}Sw​=i=1∑M​P(wi​)E{(x−mi​)(x−mi​)T∣wi​}

   ​ 类间：$S_b=\sum _{i=1}^{c}P(w_i)(m_i-m_0)(m_i-m_0{)}^T$

   直观上，类间离散度越大且类内离散度越小，则可分性越好。因此，可推导出散布矩阵准则采用如下形式：

   行列式形式(行列式是一个数)：$J_1=det(S_w^{-1}{S}_b)=\prod _i{\lambda }_i$

   迹形式：$J_2=tr(S_w^{-1}{S}_b)=\sum _i{\lambda }_i$

   其中，${\lambda }_i是矩阵S_w^{-1}{S}_b的特征值。使J_1和J_2最大的$子集可作为选择的分类特征。

   • 类内，类间的散布矩阵$S_w和S_b$
   • 类间离散度越大且类内离散度越小，可分性越好。
   • 散布矩阵准则$J_1和J_2$形式
   • 使$J_1和J_2$最大的子集可作为所选择的分类特征。

   注：这里计算的散布矩阵不受模式分布形式的限制，但需要有足够数量的模式样本才能获得有效的结果

2. 计算类内类间散布矩阵

   多类情况的类间散布矩阵：
   $$S_b=\sum _{i=1}^{M}P(w_i)(m_i-m_0)(m_i-m_0{)}^T$$
   类内散布矩阵：
   S=∑i=1M{(xi−m)(xi−m)T} S=\sum_{i=1}^M\{(x^i-m)(x^i-m)^T\} S=i=1∑M​{(xi−m)(xi−m)T}

   总体类内散布矩阵，可写成各类的类内散布矩阵的先验概率的加权和，即：
   $$S_w=\sum _{i=1}^{M}P(w_i)S_w^i$$
   其中$C_i$是第$i$类的协方差矩阵。

3. K-L变换进行特征选择

   解释：将样本的特征值尽量用一组无关的新特征值表示（正交向量组），然后取这组新的特征值的前d个特征值来进行类的划分，以达到降维的目的，但是取前d个特征值，必然会导致产生误差，在使这个误差最小的情况下进行特征值的选取就是K-L变换的目的。

   解题步骤：

   • 第一步：计算每个类别的先验概率$P(w_i)$

   • 第二步：计算矩阵R
     R=∑i=1nP(wi)E{xxT} R=\sum_{i=1}^nP(w_i)E\{xx^T\} R=i=1∑n​P(wi​)E{xxT}

   • 第三步： 计算矩阵R的特征值$\lambda$

   • 第四步： 将特征值从大到小排序，选前k个大的特征值，k为目标维度(比如降成两维就选前两个)

   • 第五步： 求出对应特征值的特征向量，并单位化，然后用特征向量${\varphi }_i$构成变换矩阵，由$y={\varphi }^{T}x$求出降维后的特征值。

     例子：

     

     

知识点五 统计学习理论基础

• 范数介绍：

  • $L_0范数$是指向量中非0的元素的个数。
  • $L_1$范数是指向量中各个元素绝对值之和
  • $L_2$范数是指向量各元素的平方和然后求平方根，就是向量的模(用于防止过拟合，提升模型泛化能力)

• 损失函数：损失函数是$f(x)和Y的非负实值函数，记作L(Y,f(x)),其中f(x)是预测所需的模型(也就是分类器),Y是真实值$

  • 常用的损失函数：

    • 0-1损失函数
      $$L(Y,f(X))=\{\begin{array}{l}1,Y\ne f(X)\\ 0,Y=f(X)\end{array}$$

    • 平方损失函数
      $$L(Y,f(X))=(Y-f(X){)}^2$$

    • 绝对损失函数
      $$L(Y,f(X))=|y-f(X)|$$

    • 对数损失函数
      $$L(Y,P(Y|X))=-logP(Y|X)$$

  • 损失函数的期望，又称为风险函数，期望损失
    $$\begin{gathered} R_{exp}(f)=E_P[L(Y,f(X))] \\ ={\int }_{x\ast y}L(y,f(x))P(x,y)dxdy \end{gathered}$$

  • 平均损失，又称为经验风险
    $$R_{emp}(f)=\frac{1}{N}\sum _{i=1}^{N}L(y_i,f(x_i))$$

  • 期望风险$ R_{exp}(f)$ 是模型关于联合分布的期望损失，经验风险 $R_{emp}(f)$是模型 关于训练样本集的平均损失。根据大数定律，当样本容量 N 趋于无穷时，经验风险 $趋R_{emp}(f)于期望风险$ $R_{exp}(f)$。

• 过拟合(过拟合问题，又称为回归问题)

  如果一味追求提高对训练数据的预测能力，所选模型的复杂度则往往会比真模型更高，这种现象称为过拟合。过拟合是指学习时选择的模型所包含的参数过多，以至出现这一模型对已知数据预测得很好，但对未知数据预测得很差的现象。

• 模型选择——正则化

  正则化是结构风险最小化策略的实现，是在经验风险上加一个正则化项（regularizer）或罚项（penalty term）。

• 泛化误差

  如果学到的模型是，那么用这个模型对未知数据预测的误差即为泛化误差（generalization error）∶
  $$\begin{gathered} R_{exp}(\hat{f})=E_P[L(Y,\hat{f}(X))] \\ ={\int }_{x\ast y}L(y,\hat{f}(x))P(x,y)dxdy \end{gathered}$$
  泛化误差就是期望风险，泛化误差越小，模型越好。

  • 泛化误差分析

    学习方法的泛化能力分析往往是通过研究泛化误差的概率上界进行的，简称为泛 化误差上界。

    泛化误差上界的性质：∶它是样本 容量的函数，当样本容量增加时，泛化上界趋于0;它是假设空间容量（capacity）的 函数，假设空间容量越大，模型就越难学，泛化误差上界就越大。

  • 泛化误差上界

    对二分类问题，当假设空间是有限个函数的集合F={f1,f2,…,fd}F=\{f_1,f_2,\dots,f_d\}F={f1​,f2​,…,fd​}时，对任意一个函数$f\in F$，至少以概率$1-\delta ,0<\delta <1$,一下不等式成立：
    $$R(f)\le \hat{R}(f)+\epsilon (d,N,\delta )$$
    其中：
    $$\epsilon (d,N,\delta )=\sqrt{\frac{1}{2N}\left(logd+log\frac{1}{\delta }\right)}$$
    不等式左端$R(f)$ 是泛化误差，右端即为泛化误差上界。在泛化误差上界 中，第1项是训练误差，训练误差越小，泛化误差也越小。第2项$\epsilon (d,N,\delta )$是 N 的 单调递减函数，当 N 趋于无穷时趋于 0;同时它也是$\sqrt{logd}$阶的函数，假设空间 F 包含的函数越多，其值越大。

知识点六 监督学习

1. 基础知识

   • 分类：分类是监督学习的一个核心问题。在监督学习中，当输出变量Y取有限个离散 值时，预测问题便成为分类问题。这时，输入变量 X 可以是离散的，也可以是连续 的。监督学习从数据中学习一个分类模型或分类决策函数，称为分类器（classifier）。 分类器对新的输入进行输出的预测，称为分类（classification）。可能的输出称为类 别（class）。

   • 回归：回归（regression）是监督学习的另一个重要问题。回归用于预测输入变量（自变 量）和输出变量（因变量）之间的关系，特别是当输入变量的值发生变化时，输出变量 的值随之发生的变化。回归模型正是表示从输入变量到输出变量之间映射的函数。回 归问题的学习等价于函数拟合∶选择一条函数曲线使其很好地拟合已知数据且很好地 预测未知数据。

   • 线性回归：

     线性回归是想要得到：$f(x_i)=w{x}_i+b,使得f(x_i)近似等于y_i$

     达到目的当方法：均方误差最小化$(w^{\ast },b^{\ast })=argmi{n}_{(w,b)}{\sum }_{i=1}^m(f(x_i)-y_i{)}^2$

     基于均方误差最小化来进行模型求解的方法称为“最小二乘法”。在线性回归中，最小二乘法就是试图找到一条直线，使所有样本到直线上的欧式距离之和最小。

   • 正则化项

     一般就是给模型加被估计值的$L_1,L_2范数$。

2. 逻辑回归LR：名字是回归，其实是分类，解决二分类问题

   • 逻辑回归函数：
     $$ln\frac{y}{1-y}=w^{T}x+b$$

   • 逻辑回归使用极大似然估计，进行$w$（权向量）的估计

3. 极大似然估计和最大后验估计

   极大似然估计相当于求$P(y_i|{\hat{w}}^T{x}_i)$最大的情况下$w$的值

   最大后验估计相当于求$P({\hat{w}}^T{x}_i|y_i)$最大的情况下$w$的值，最大后验相当于极大似然加一个正则化项。

   $P({\hat{w}}^T{x}_i|y_i)=P(y_i|{\hat{w}}^T{x}_i)P(y_i)其中P(y_i)是一个专家知识，相当于提前就告诉你y_i发生的概率，因为P(y_i)>0所以P({\hat{w}}^T{x}_i|y_i)正比于P(y_i|{\hat{w}}^T{x}_i)$

   有了这个专家知识后，最大后验估计相当于在极大似然的条件下加了一个正则化项，可以以逻辑回归为例。

知识点七 支持向量机

1. 硬间隔原始问题：（支持向量机是二类分类模型）

   目的是得到最大间隔的划分超平面：
   $$w^{T}x+b=0$$

   求参数$w和b，使\gamma 最大$，其中$\gamma$是间隔
   $$\begin{gathered} ma{x}_{w,b}\frac{2}{||w||} \\ s.t.y_i(w^T{x}_i+b)\ge 1i=1,2,\dots ,m. \end{gathered}$$
   等价于
   $$\begin{gathered} mi{n}_{w,b}\frac{1}{2}||w|{|}^2 \\ s.t.y_i(w^T{x}_i+b)\ge 1i=1,2,\dots ,m. \end{gathered}$$
   上式是SVM基本型。

   算法：

   

   

   例题：

   

   

2. 硬间隔对偶问题

   对原始问题使用拉格朗日乘子法可得其“对偶问题”，该问题的拉格朗日函数为：
   $$\begin{gathered} L(w,b,\alpha )=\frac{1}{2}||w|{|}^2+\sum _{i=1}^m{\alpha }_i(1-y_i(w^T{x}_i+b)) \\ 其中\alpha =({\alpha }_1;{\alpha }_2;\dots ;{\alpha }_m) \end{gathered}$$
   最终对偶问题为：
   $$\begin{gathered} ma{x}_{\alpha }\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j^T \\ s.t.\sum _{i=1}^m{\alpha }_i{y}_i=0 \\ {\alpha }_i\ge 0,i=1,2,\dots ,m. \\ w=\sum _{i=1}^N{\alpha }_i{y}_i{x}_i \\ b=y_j-\sum _{i=1}^N{\alpha }_i{y}_i(x_i\ast x_j) \end{gathered}$$

   支持向量机重要性质：

   训练完成后，大部分的训练样本都不需保留，最终模型仅与支持向量有关。

   算法：

   

   例题：

   

   

3. 函数间隔，几何间隔

   

   

   4. 软间隔原始问题

      

      

      • 对偶问题

        

        

   5. 核函数

      

      例子：

      

知识点八 聚类

1. 基础知识

   • 聚类的任务

     在无监督学习中，训练样本的信息是未知的。聚类试图将数据集中的样本划分为若干个通常是不相交的子集，每个子集称为一个“簇”。

     聚类是针对给定的样本，依据它们特征的相似度或距离，将其归并到若干个"类" 或"簇"的数据分析问题。

   • 样本间距离和相关系数

     闵可夫斯基距离：

     

     相关系数：

     

   • 簇的定义和特征

     通过聚类得到的类或簇，本质是样本的子集。如果一个聚类方法假定一个样本只能属于一个类，或类的交集为空集，那么该方法称为硬聚类（hard clustering）方法。 否则，如果一个样本可以属于多个类，或类的交集不为空集，那么该方法称为软聚 类（soft clustering）方法。

     用G表示类或簇（cluster），用$x_i,x_j$表示类中的样本，用 $n_G$ 表示$G$中样本的 个数，用$d_{ij}$表示样本$x_i与样本x_j$之间的距离。类或簇有多种定义，下面给出几个常 见的定义。

     

     特征：

     

     

   • 类间距离

     

   • 性能度量：有效性指标，聚类结果尽量做到**“簇内相似度”高且“簇间相似度“低**（类内样本距离小，类间样本距离大）。聚类性能度量大致有两类。一类是将聚类结果与某个”参考模型“进行比较，称为”外部指标“；另一类是直接考察聚类结果而不利用任何参考模型，称为”内部指标“。

     

     

2. K均值聚类(K-means)

   思路：k 均值聚类是基于样本集合划分的聚类算法。k 均值聚类将样本集合划分为k 个 子集，构成k 个类，将n 个样本分到k 个类中，每个样本到其所属类的中心的距离最 小。每个样本只能属于一个类，所以k 均值聚类是硬聚类。

   策略：k均值聚类归结为样本集合X 的划分，或者从样本到类的函数的选择问题。k均 值聚类的策略是通过损失函数的最小化选取最优的划分或函数 $C^{\ast }$。

   

   

   算法：

   

   例题：

   

   

   算法特点：

   总体特点：基于划分的聚类方法，类别数k事先指定，以欧氏距离表示样本之间的距离，以中心或样本的均值表示类别，以样本何其所属类的中心之间的距离的总和为最优化的目标函数；得到的类别是平坦的，非层次化的；算法是迭代算法，不能保证得到全局最优解。

   收敛性：k均值聚类属于启发式方法，不能保证收敛到全局最优。

   初始类的选择：选择不同的初始中心，会得到不同的聚类结果。可采用层次聚类对样本进行聚类，得到k个类时停止，然后从每个类中选择一个与中心距离最近的点。

   类别数k的选择：方法就是多试几个，但是k值增大到一定程度，平均直径就不会改变了。实验时，可以采用二分查找，快速找到最优k值。

3. GMM(高斯混合模型)属于软聚类

   思路：一个样本具有各个类一定的特点，选取特点权重最高的类，就是样本所属的类别。

   模型表达式：
   $$\begin{gathered} f(x)=\sum _{k=1}^K{w}_{k}g(x|u_k,{\Sigma }_k) \\ 等价于:p_M(x)=\sum _{i=1}^k{a}_i\cdot p(x|u_i,{\Sigma }_i) \end{gathered}$$
   以上模型是算出的是某个样本属于各个类别的特点的权重之和。

   样本属于某个类的后验概率：
   $$\begin{gathered} p_m(z_j=i|x_j)=\frac{P(z_j=i)\cdot p_m(x_j|z_j=i)}{p_m(x_j)} \\ =\frac{a_i\cdot p(x_j|u_i,{\Sigma }_i)}{{\sum }_{l=1}^k{a}_l\cdot p(x_j|u_{;},{\Sigma }_l)} \end{gathered}$$

   λj=argmaxi∈{1,2,…,k}γjiλj即为xj所属的类别 \lambda_j=argmax_{i\in \{1,2,\dots,k\}}\gamma_{ji}\\ \lambda_j 即为x_j所属的类别 λj​=argmaxi∈{1,2,…,k}​γji​λj​即为xj​所属的类别

   参数求解：

   

   

   

   算法：

   

4. 层次聚类(硬聚类)

   层次聚类又分为：聚合(自下而上聚类),分裂(自上而下聚类)两种方法。

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

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

   聚类思路：

   聚合聚类的具体过程如下∶对于给定的样本集合，开始将每个样本分到一个类; 然后按照一定规则，例如类间距离最小，将最满足规则条件的两个类进行合并;如此 反复进行，每次减少一个类，直到满足停止条件，如所有样本聚为一类。 由此可知，聚合聚类需要预先确定下面三个要素∶ （1）距离或相似度; （2）合并规则∶ （3）停止条件。

   特点：

   根据这些要素的不同组合，就可以构成不同的聚类方法。距离或相似度可以是闵 可夫斯基距离、马哈拉诺比斯距离、相关系数、夹角余弦。合并规则一般是类间距离 最小，类间距离可以是最短距离、最长距离、中心距离、平均距离。停止条件可以是类 的个数达到阈值（极端情况类的个数是1）、类的直径超过阈值。

   例子：

   

   

5. 密度聚类(DBSCAN)

   重要概念：

   

   

   

   算法流程：

   找到所有满足邻域参数的样本点，将其加入到核心对象集合。

   遍历所有核心对象：

   1. 将第一个核心对象从核心队列中移除，建立一个队列将核心对象放入
   2. 将与核心对象密度相连的样本加入队列中，然后将核心对象从队列中移除。
   3. 从队列里那下一个样本点，将样本点密度相连的样本加入队列，然后将样本点从队列中移除。
   4. 重复3中操作，直到队列为空，得到所有样本构成第一个簇
   5. 将核心队列中已经便利的样本点移除。
   6. 重复1-5，得到所有簇。

知识点九 降维

1. 线性降维：PCA降维(主成分分析法)就是K-L变换

   基于最近重构性，PCA优化目标：
   $$\begin{gathered} mi{n}_W-tr(W^{T}X{X}^{T}W) \\ s.t.W^{T}W=I. \end{gathered}$$
   基于最大可分性，PCA优化目标：
   $$\begin{gathered} ma{x}_{W}tr(W^{T}X{X}^{T}W) \\ s.t.W^{T}W=I. \end{gathered}$$
   PCA算法描述：

   

   舍弃小的特征值有哪些好处：

   一方面舍弃这部分信息可以增大采样密度，另一方面能在一定程度上起到去噪的效果。

2. 核主成分分析，核PCA降维，KPCA

   KPCA思想，使用核函数将地位原始数据，转化为高维数据，然后使用PCA选出高维特征空间中协方差矩阵的前k个大的特征值，以达到降维目的。KPCA需要对所有样本求和，因此它的计算开销较大。

3. 流型模型

   利用高维空间，局部具有欧式空间性质

   多维缩放MDS算法：

   

   全局嵌入算法：等度量映射(Isomap)

   

   局部嵌入算法：LLE

   思路：每个样本可由近邻的样本线性表示，依次作为降维的依据。

   

   

   算法：

   

知识点十 半监督学习

1. 半监督学习常用假设

   • 平滑假设：如果高密度空间两个点$x_1,x_2$距离较近，那么对应的输出$y_1,y_2$也应接近。

• 聚类假设：假设数据存在簇结构，同一个簇的样本属于同一个类别。
  • 流行假设：即假设数据分布在一个流行结构上，邻近的样本拥有相似的输出值。“邻近”程度常用“相似”程度来刻画，因此流行假设可看作聚类假设的推广，但流行假设对输出值没有限制，因此比聚类假设的适用范围更广。
  • 独立假设

2. 主动学习(自我训练，需要用到专家知识)

   算法描述：

   

   变体：

   

   优缺点：

   • 优点

   

   • 缺点

   

3. 多视角学习

   • 协同训练

     • 协同训练假设

       

     • 协同训练算法

       

     • 优缺点

       

   • 多视角学习

     

     

4. 生成模型

   • GMM(高斯混合模型)生成

     假设：样本由高斯混合模型生成，且每个类别对应一个高斯混合成分。（意味着混合成分与类别之间一一对应）。

     高斯混合模型进行半监督学习算法过程：

     

     

   • 半监督SVM(又叫S3VM或TSVM)

     基本假设是：低密度分割，是聚类假设在考虑了线性超平面划分后的推广。

     基本思想：试图找到能将两类有标记样本分开，且穿过数据低密度区域的划分超平面。

     TSVM：试图尝试对未标记样本进行标记指派。

     算法具体流程：

     

     伪代码：

     

     研究重点：S3VM是一个涉及巨大计算开销的大规模优化问题，因此研究重点是如何设计出高效的优化求解策略。

     • 避免无标签数据落在间隔内

       

     • 类别平衡限制

       

     • S3VM优化中的挑战

       

     • 用于S3VM训练的优化方法

       

知识点十一 概率图模型

1. 有向概率模型

   定义：有向图$G=(V,E)包含一个点集合V和一个边集合E，其中每条边为有序点对。$

   有向图模型可以表示因果关系

   有向图例子：

   

   三种经典图，独立性判别：

   

   条件独立(快速检验)

   

   

   

   小结：

   

   • 隐马尔科夫模型HMM

     马尔科夫链：系统下一时刻的状态仅由当前状态决定，不依赖于以往的任何状态。

     

     

     

     三个基本问题分别对应：前向算法，后向算法，Viterbi解码算法

2. Viterbi解码

   问题：如何发现“最优”状态序列，能够“最好的解释”观察序列。最优的定义：状态序列中的每一个状态都独立的具有概率，对于每个时刻$t(1\le t\le T),寻找q_i使得{\gamma }_t(i)=p(q_t=S_i|O,u)$最大。就是解决三个基本问题中的第三个问题

   算法流程：
   $$\begin{gathered} a_{ij}=P(y_{t+1}=s_j|y_t=s_i),1\le i,j\le N \\ {b}_{ij}=P(x_t=o_j|y_t=s_i),1\le i\le N,1\le j\le M \\ {\pi }_i=P(y_1=s_i),1\le i\le N \end{gathered}$$

   1. 初始化：$V_1^k=p(x_1,y_1=s_k)={\pi }_k{b}_{y_1,x_1}$
   2. 迭代：$V_t^k=p(x_t|y_t^k=1)ma{x}_i{a}_{i,k}{V}_{t-1}^i$
   3. 终止：$P^{\ast }=ma{x}_{1\le i\le N}{V}_T^i$

知识点十二 集成学习

1. 基础概念

   集成学习通过构建并结合多个学习器来完成学习任务，有时也被称为多分类器系统、基于委员会的学习等。

   用来组合的多个学习器被称为“基学习器”或“弱学习器”

   集成学习的结果通过投票产生，即“少数服从多数”

   个体学习器要有一定的“准确性”，还要有“多样性”，即学习器间具有差异。

   随着基分类器的增多，集成学习错误率将指数下降，最终趋于零。-

2. AdaBoost算法（通过最小化指数损失函数进行训练）

   

   损失函数另一个写法，损失函数是当前分类器对所有样本错误分类的指数误差（N是样本数）：
   $$\begin{gathered} J(\alpha ,\theta )=\sum _{i=1}^N{e}^{-y_i{F}_m(x_i)}=\sum _{i=1}^N{e}^{-y_i(F_{m-1}(x)+{\alpha }_m\varphi (x:{\theta }_m))} \\ =\sum _{i=1}^N{e}^{-y_i{F}_{m-1}(x)}{e}^{-y_i{\alpha }_m\varphi (x:{\theta }_m))} \\ 令w_i^m=e^{-y_i{F}_{m-1}(x)}(样本在第m-1次迭代时，所占的错误分类权重) \\ 原式=\sum _{i=1}^N{w}_i^m{e}^{-y_i{\alpha }_m\varphi (x:{\theta }_m))} \end{gathered}$$
   前m个分类器分类结果：
   $$F_m(x)=\sum _{k=1}^m{\alpha }_k\varphi (x:{\theta }_k)$$
   增量表示：
   $$F_m(x)=F_{m-1}(x)+{\alpha }_m\varphi (x:{\theta }_m)$$

   求$P_m(第m个分类器错误识别样本的平均权重)$
   $$\begin{gathered} P_m=\sum _{i=1}^N{w}_i^{m}I(1-y_i\varphi (x:\theta )) \\ I(y_i\ne \varphi (x:\theta ))等价于上面的I函数，都是指错分类的样本，I=\{\begin{array}{l}0,分类正确\\ 1,分类错误\end{array} \end{gathered}$$

   求${\alpha }_m$:
   $${\alpha }_m=\frac{1}{2}ln(\frac{1-P_m}{P_m})$$

3. Bagging 算法（著名的并行式集成学习方法）

   算法流程：

   1. 使用随机采样，从样本中随机选取一个样本加入训练样本集，然后将这个样本放回，进行第二次采样，循环进行m次，得到m个样本的样本集，然后用同样的方法进行T次采样，获得T个含m个样本的训练集。
   2. 使用T个样本集分别训练T个基分类器，然后合并基分类器。一般通过对分类任务使用简单投票法获得最终结果。

   

4. 偏差和方差

   总结：偏差高，欠拟合，模型复杂度低；方差高，过拟合，模型复杂度高。应选择适当复杂度的模型。

   偏差：

   

   方差：

   

   

5. 欠拟合和过拟合

   外在表现：

   

6. 小结

   

知识点十三 深度学习

1. 神经元基本模型

2. 激活函数（转移函数）：

   核心作用：引入非线性因素，使得神经网络可以逼近任何非线性函数。

   常用激活函数：

   

   sigmoid函数：

   

   

   整流线性函数：ReLU函数

   

   

3. 卷积神经网络

   

   卷积层稀疏连接：每个神经元只连接前一层部分神经元，不同神经元的感受野不同，但相邻神经元的感受野有部分重叠。

   

   参数训练技巧：