模式识别
贝叶斯决策
贝叶斯公式：
$$ P(\omega_i | x)=\dfrac{P(\omega_i,x)}{P(x)}=\dfrac{P(x|\omega_i)P(\omega_i)}{P(x)} $$
先验概率：$ P(\omega_i) $；后验概率：$ P(\omega_i | x)$
总体密度：$P(x)$；联合概率密度：$ P(\omega_i,x) $；类条件概率密度：$ P(x|\omega_i)$
最小错误率
$$ P(e)=\int P(e|x)p(x)dx $$
最小错误率决策：$minP(e)=min\int P(e|x)p(x)dx$
最小风险
风险$ R(a_i|x) = \sum_{j=1}^{c} \lambda(a_i,\omega_j)P(\omega_i|x) $
最小风险：$ minR(\alpha) = min \int R(\alpha(x)|x)p(x)$
正态分布贝叶斯
$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)}$
判别函数$g_i(x)=ln[p(x|\omega_i)P(\omega_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)] $$
决策面方程：$g_i(x)=g_j(x)$
$$ -\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(\omega_i)=p(\omega_j)$时，判别函数：
$g_i(x)=-\dfrac{(x-\mu_i)^T(x-\mu_i)}{2\sigma^2}$
即计算欧氏距离的平方并根据其最小值归类
概率密度函数估计
最大似然估计
每类样本满足独立同分布，类条件概率存在某种具体确定的函数形式，只是参数未知，根据样本求出该参数
$$ l(\theta)=p(\chi|\theta)=\prod_{i=1}^{N}p(x_i|\theta) $$
$$ H(\theta)=lnl(\theta)=lnp(X/\theta)=\sum_{i=1}^{N}lnp(x_i/\theta) $$
$$ \sum_{i=1}^N \frac{\partial}{\partial \theta_1} \ln p(x_i \mid \theta) $$
$$ \vdots \nonumber $$
$$ \sum_{i=1}^N \frac{\partial}{\partial \theta_s} \ln p(x_i \mid \theta) $$
非参数方法
直方图法
把样本x的每个分量分为多个等间隔小窗，将样本数目作为概率
Kn近邻法
确定Kn个数，调整窗口大小直到包含Kn个样本，以每一点为中心进行估计
核密度估计
对已知的密度函数，在观测点上进行平均化，得到光滑估计曲线
线性分类器
基本概念
线性判别函数的一般表达式：$g(x)=\bold{w}^T \bold{x}+w_0$
$\bold{x}$：样本向量；$\bold{w}$：权向量；w：阈值权
对于二分问题，决策规则$g(x) = g_1(x)-g_2(x)$
判别函数可以看成是特征空间中某点到决策超平面距离的一种代数度量
fisher线性判别
原理：将所有样本都投影到一个方向，在一维空间中确定分类阈值2
寻找投影方向$\bold{w}$，使得投影后的样本为$y_i=\bold{w}^T x_i$
投影前：
- 类内离散度矩阵：
$$ S_i=\sum(x_j-m_j)(x_j-m_j)^T $$
- 类均值向量：
$$ m_i=\frac{1}{N_i}\sum x_j $$
- 类内总离散度矩阵：
$$ S_w=S_1+S_2 $$
- 类间离散度矩阵：
$$ S_b = (m_1-m_2)(m_1-m_2)^T $$
投影后：
- 类内离散度：
$$ \tilde{S_i^2}=\sum(y_i-\tilde{m_i})^2 $$
- 类均值向量：
$$ \tilde{m_i}=\frac{1}{N_i}\sum y_j = w^Tm_i $$
- 类内总离散度：
$$ \tilde{S_w}=\tilde{S_1^2}+\tilde{S_2^2} $$
- 类间离散度：
$$ \tilde{S_b}=(\tilde{m_1}-\tilde{m_2})^2 $$
Fisher准则函数即为：$ 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)=\alpha^T y$，存在$\alpha$使得所有样本被正确分类，则根据g(y)大于小于0判断类别
令增广样本矩阵
$$ y_i^{’}=y_i,y_i \in \omega_1 \ -y_i,y_i \in \omega_2 $$
则解向量$\alpha$满足$\alpha^T y_i > 0$
感知器准则函数$J_p(\alpha)= min\sum_{\alpha^T y_k \leq 0} (-\alpha^T y_k) = 0$
非线性感知器
分段线性判别
对待分类样本，把他分到距离最近的子类所属的类
$$ g_k(x)=min||x-m_i^l|| $$
非线性支持向量机
$$ 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神经网络
主成分分析
定义$\bold{x}$为原变量指标，$\bold{y}$为变换后的向量
$$ \bold{Y=XP} $$
$\bold{P}$为负载矩阵，使得方差最大化
对原始数据$\bold{X_0}$进行标准化：$\bold{X=(X_0-1\mu^T)\sum^{-1}}$
PCA优化目标可表示为：
$$ max\ tr[\bold{P^T X^T X P}/(n-1)],s.t.\ \bold{P^T P = I} $$
采用拉格朗日乘子法，转化为特征值分解问题：
$$ (\bold{X^T X}/(n-1)\bold{p_i})=\lambda_i\bold{p_i} $$
根据累计方差贡献率确定k个主成分：
$$ \sum_{i=1}^k\lambda_i/\sum_{i=1}^m\lambda_i > threshold $$
降维：
$$ Y=XP $$
$\bold{P}$为前k个特征向量组成的矩阵
近邻法
最近邻法
以距离新样本最近已知样本作为新样本的类别
欧氏距离：$||x_i-x_j||$
K-近邻法
找出x的k个近邻，看其中多数属于哪一类，则把x分到哪一类
快速算法
- 对新样本，节点p,若
$$ D(x,M_p)>B+r_p $$
则p不可能是x的最近邻
- 若
$$ D(x,M_p)>B+D(x_i,M_p) $$
则p不可能是x的最近邻
剪辑近邻法
两类分布重合区的样本可能会误导决策，应当去掉
压缩近邻法
将样本分为储存集$X_S$与备选集$X_G$，若$X_G$中的样本x能用$X_S$中的样本进行正确分类，则留在$X_G$中，反之移入$X_S$
特征选择
基于类内类间距离的可分性判据
常用可分性判据：
$$ 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|} $$
基于概率分布的可分性判据
常用的概率距离度量：
$$ J_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(v_j)$
- 求极小点，做垂直与投影方向的超平面作为分类超平面
- 若没有极小点，继续用下一个本征值对应的本征向量做投影方向
动态聚类算法
C均值算法：
$$ J_e = \sum_{i=1}^c\sum_{y\in\Gamma_i}||y-m_i||^2=\sum_{i=1}^cJ_i $$
模糊聚类算法
模糊C均值算法：
$$ min\ J_e =min\ \sum_{i=1}^c\sum_{y\in\Gamma_i}||y-m_i||^2=\sum_{i=1}^cJ_i $$
分级聚类方法
从各类只有一个样本点开始，逐级合并，每级只合并两类，直到最后所有样本归到一个类，聚类过程中逐级考察类间相似度，依此决定类别数