Akira's Blog
Akira Lyu 的头像Akira's Blog

図書室でしか見たことない世界確かめたい

模式识别

模式识别期末考试知识点总结

发布 最后修改 分类 机器学习

贝叶斯决策

贝叶斯公式：

P(ωi∣x)=P(ωi,x)P(x)=P(x∣ωi)P(ωi)P(x)P(\omega_i | x)=\dfrac{P(\omega_i,x)}{P(x)}=\dfrac{P(x|\omega_i)P(\omega_i)}{P(x)}

先验概率：P(ωi)P(\omega_i)；后验概率：P(ωi∣x) P(\omega_i | x)

总体密度：P(x)P(x)；联合概率密度：P(ωi,x)P(\omega_i,x)；类条件概率密度：P(x∣ωi) P(x|\omega_i)

最小错误率

P(e)=∫P(e∣x)p(x)dxP(e)=\int P(e|x)p(x)dx

最小错误率决策：minP(e)=min∫P(e∣x)p(x)dxminP(e)=min\int P(e|x)p(x)dx

最小风险

风险R(ai∣x)=∑j=1cλ(ai,ωj)P(ωi∣x)R(a_i|x) = \sum_{j=1}^{c} \lambda(a_i,\omega_j)P(\omega_i|x)

最小风险：minR(α)=min∫R(α(x)∣x)p(x) minR(\alpha) = min \int R(\alpha(x)|x)p(x)

正态分布贝叶斯

p(x∣ωi)=1(2π)d/2∣∑i∣1/2exp{−12(x−μi)T∑iT(x−μi)}p(x|\omega_i) = \dfrac{1}{(2\pi)^{d/2}|\sum_i|^{1/2}}exp\{-\frac{1}{2}(x-\mu_i)^{T}\sum_i^{T}(x-\mu_i)\}

判别函数gi(x)=ln[p(x∣ωi)P(ωi)]=g_i(x)=ln[p(x|\omega_i)P(\omega_i)]=

−d2ln2π−12ln∣∑i∣−12(x−μi)T∑i−1(x−μi)+ln[P(ωi)]-\frac{d}{2}ln2\pi - \frac{1}{2}ln|\sum_i|-\frac{1}{2}(x-\mu_i)^T\sum_i^{-1}(x-\mu_i)+ln[P(\omega_i)]

决策面方程：gi(x)=gj(x)g_i(x)=g_j(x)

−12[(x−μi)T∑i−1(x−μi)−(x−μj)T∑j−1(x−μj)]−12ln∣∑i∣∣∑j∣+lnP(ωi)P(ωj)=0-\frac{1}{2}[(x-\mu_i)^T\sum_i^{-1}(x-\mu_i)-(x-\mu_j)^T\sum_j^{-1}(x-\mu_j)]-\frac{1}{2}ln\dfrac{|\sum_i|}{|\sum_j|}+ ln\dfrac{P(\omega_i)}{P(\omega_j)}=0

当p(ωi)=p(ωj)p(\omega_i)=p(\omega_j)时，判别函数：

gi(x)=−(x−μi)T(x−μi)2σ2g_i(x)=-\dfrac{(x-\mu_i)^T(x-\mu_i)}{2\sigma^2}

即计算欧氏距离的平方并根据其最小值归类

概率密度函数估计

最大似然估计

每类样本满足独立同分布，类条件概率存在某种具体确定的函数形式，只是参数未知，根据样本求出该参数

l(θ)=p(χ∣θ)=∏i=1Np(xi∣θ)l(\theta)=p(\chi|\theta)=\prod_{i=1}^{N}p(x_i|\theta) H(θ)=lnl(θ)=lnp(X/θ)=∑i=1Nlnp(xi/θ)H(\theta)=lnl(\theta)=lnp(X/\theta)=\sum_{i=1}^{N}lnp(x_i/\theta) ∑i=1N∂∂θ1ln⁡p(xi∣θ)\sum_{i=1}^N \frac{\partial}{\partial \theta_1} \ln p(x_i \mid \theta) ⋮\vdots \nonumber ∑i=1N∂∂θsln⁡p(xi∣θ)\sum_{i=1}^N \frac{\partial}{\partial \theta_s} \ln p(x_i \mid \theta)

非参数方法

直方图法

把样本x的每个分量分为多个等间隔小窗，将样本数目作为概率

Kn近邻法

确定Kn个数，调整窗口大小直到包含Kn个样本，以每一点为中心进行估计

核密度估计

对已知的密度函数，在观测点上进行平均化，得到光滑估计曲线

线性分类器

基本概念

线性判别函数的一般表达式：g(x)=wTx+w0g(x)=\bold{w}^T \bold{x}+w_0

x\bold{x}：样本向量；w\bold{w}：权向量；w：阈值权

对于二分问题，决策规则g(x)=g1(x)−g2(x)g(x) = g_1(x)-g_2(x)

判别函数可以看成是特征空间中某点到决策超平面距离的一种代数度量

fisher线性判别

原理：将所有样本都投影到一个方向，在一维空间中确定分类阈值2

寻找投影方向w\bold{w}，使得投影后的样本为yi=wTxiy_i=\bold{w}^T x_i

投影前：

  • 类内离散度矩阵：
Si=∑(xj−mj)(xj−mj)TS_i=\sum(x_j-m_j)(x_j-m_j)^T
  • 类均值向量：
mi=1Ni∑xjm_i=\frac{1}{N_i}\sum x_j
  • 类内总离散度矩阵：
Sw=S1+S2S_w=S_1+S_2
  • 类间离散度矩阵：
Sb=(m1−m2)(m1−m2)TS_b = (m_1-m_2)(m_1-m_2)^T

投影后：

  • 类内离散度：
Si2~=∑(yi−mi~)2\tilde{S_i^2}=\sum(y_i-\tilde{m_i})^2
  • 类均值向量：
mi~=1Ni∑yj=wTmi\tilde{m_i}=\frac{1}{N_i}\sum y_j = w^Tm_i
  • 类内总离散度：
Sw~=S12~+S22~\tilde{S_w}=\tilde{S_1^2}+\tilde{S_2^2}
  • 类间离散度：
Sb~=(m1~−m2~)2\tilde{S_b}=(\tilde{m_1}-\tilde{m_2})^2

Fisher准则函数即为：maxJF(ω)=Sb~Sw~=(m1~−m2~)2S12~+S22~ maxJ_{F(\omega)} = \dfrac{\tilde{S_b}}{\tilde{S_w}}= \dfrac{(\tilde{m_1}-\tilde{m_2})^2}{\tilde{S_1^2}+\tilde{S_2^2}}

使得投影后两类尽可能分开，类内尽可能聚集，即类内总离散度小，类间离散度大

感知器

齐次化简：g(y)=αTyg(y)=\alpha^T y，存在α\alpha使得所有样本被正确分类，则根据g(y)大于小于0判断类别

令增广样本矩阵

yi′=yi,yi∈ω1−yi,yi∈ω2y_i^{'}=y_i,y_i \in \omega_1 \\ -y_i,y_i \in \omega_2

则解向量α\alpha满足αTyi>0\alpha^T y_i > 0

感知器准则函数Jp(α)=min∑αTyk≤0(−αTyk)=0J_p(\alpha)= min\sum_{\alpha^T y_k \leq 0} (-\alpha^T y_k) = 0

非线性感知器

分段线性判别

对待分类样本，把他分到距离最近的子类所属的类

gk(x)=min∣∣x−mil∣∣g_k(x)=min||x-m_i^l||

非线性支持向量机

maxα:W(α)=∑i=1nαi−12∑i,j=1ny(i)y(j)αiαjK(x(i),x(j))max_\alpha: W(\alpha) = \sum_{i=1}^n\alpha_i - \frac{1}{2}\sum_{i,j=1}^ny^{(i)}y^{(j)}\alpha_i\alpha_jK(x^{(i),x^{(j)}})

神经网络

BP神经网络

主成分分析

定义x\bold{x}为原变量指标，y\bold{y}为变换后的向量

Y=XP\bold{Y=XP}

P\bold{P}为负载矩阵，使得方差最大化

对原始数据X0\bold{X_0}进行标准化：X=(X0−1μT)∑−1\bold{X=(X_0-1\mu^T)\sum^{-1}}

PCA优化目标可表示为：

max tr[PTXTXP/(n−1)],s.t. PTP=Imax\ tr[\bold{P^T X^T X P}/(n-1)],s.t.\ \bold{P^T P = I}

采用拉格朗日乘子法，转化为特征值分解问题：

(XTX/(n−1)pi)=λipi(\bold{X^T X}/(n-1)\bold{p_i})=\lambda_i\bold{p_i}

根据累计方差贡献率确定k个主成分：

∑i=1kλi/∑i=1mλi>threshold\sum_{i=1}^k\lambda_i/\sum_{i=1}^m\lambda_i > threshold

降维：

Y=XPY=XP

P\bold{P}为前k个特征向量组成的矩阵

近邻法

最近邻法

以距离新样本最近已知样本作为新样本的类别

欧氏距离：∣∣xi−xj∣∣||x_i-x_j||

K-近邻法

找出x的k个近邻，看其中多数属于哪一类，则把x分到哪一类

快速算法

  • 对新样本，节点p,若
D(x,Mp)>B+rpD(x,M_p)>B+r_p

则p不可能是x的最近邻

  • 若
D(x,Mp)>B+D(xi,Mp)D(x,M_p)>B+D(x_i,M_p)

则p不可能是x的最近邻

剪辑近邻法

两类分布重合区的样本可能会误导决策，应当去掉

压缩近邻法

将样本分为储存集XSX_S与备选集XGX_G，若XGX_G中的样本x能用XSX_S中的样本进行正确分类，则留在XGX_G中，反之移入XSX_S

特征选择

基于类内类间距离的可分性判据

常用可分性判据：

J1=tr(Sw+Sb)J2=tr(Sw1Sb)J3=ln∣Sb∣∣Sw∣J4=trSbtrSwJ5=∣Sb−Sw∣∣Sw∣J_1=tr(S_w+S_b) \\ J_2 = tr(S_w^1S_b) \\ J_3 = ln\frac{|S_b|}{|S_w|} \\ J_4 = \frac{trS_b}{trS_w} \\ J_5 = \frac{|S_b-S_w|}{|S_w|}

基于概率分布的可分性判据

常用的概率距离度量：

JB=−ln∫[p(x∣ω1)p(x∣ω2)]1/2dxJC=−ln∫[ps(x∣ω1)p1−s(x∣ω2)]dxJD=−ln∫[p(x∣ω1)−p(x∣ω2)]lnp(x∣ω1)p(x∣ω2)dxJ_B = - ln\int[p(x|\omega_1)p(x|\omega_2)]^{1/2}dx \\ J_C = - ln\int[p^s(x|\omega_1)p^{1-s}(x|\omega_2)]dx \\ J_D = - ln\int[p(x|\omega_1)-p(x|\omega_2)]ln\dfrac{p(x|\omega_1)}{p(x|\omega_2)}dx

特征选择的最优算法

  • 穷举算法
  • 分支界定算法

特征选择的次优算法

非监督模式识别

基于模型的方法

  • 主成分分析
  • 估计投影后的概率密度函数P(vj)P(v_j)
  • 求极小点，做垂直与投影方向的超平面作为分类超平面
  • 若没有极小点，继续用下一个本征值对应的本征向量做投影方向

动态聚类算法

C均值算法：

Je=∑i=1c∑y∈Γi∣∣y−mi∣∣2=∑i=1cJiJ_e = \sum_{i=1}^c\sum_{y\in\Gamma_i}||y-m_i||^2=\sum_{i=1}^cJ_i

模糊聚类算法

模糊C均值算法：

min Je=min ∑i=1c∑y∈Γi∣∣y−mi∣∣2=∑i=1cJimin\ J_e =min\ \sum_{i=1}^c\sum_{y\in\Gamma_i}||y-m_i||^2=\sum_{i=1}^cJ_i

分级聚类方法

从各类只有一个样本点开始，逐级合并，每级只合并两类，直到最后所有样本归到一个类，聚类过程中逐级考察类间相似度，依此决定类别数