支持向量机

决策域与决策面

根据判别函数组中哪一个判别函数值为极值为准则可将特征空间划分成不同的区域，称为决策域，相邻决策域的边界是决策分界面或称决策面。例如两类问题的基于最小错误率的贝叶斯决策将整个特征空间划分成两个决策域，在同一个决策域中的每一点由同一类的后验概率占主导地位。

支持向量机是基于统计学习理论的一种分类器设计方法，是近年来在理论及实际问题都有重大影响的一种新方法。就分类器设计而言，它以设计线性分类器为基础，扩展到非线性分类器。在设计线性分类器时, 又分线性可分以及线性不可分两种情况:

• 在线性可分条件下，即两个类别训练样本集可用线性分界面无错误分开的条件下，找到使两类别训练样本正确分类的一个最佳分界面。
  • 最佳条件是指两类样本最靠近分界面的样本（称为支持向量）到该分界面的法向距离最大。也就是说使分界面两侧形成的一个隔离带（带中没有任一类训练样本）的间隔最宽。
• 在线性不可分条件下，即两类样本无法用线性界面无错分开的条件下，最佳准则改为综合考虑对错分样本进行控制, 与使间隔带尽可能宽这两个条件。 对线性不可分条件下分类也可使用非线性分类器，支持向量机中采用将原特征空间, 用非线性映射到一个新空间(核方法), 并在该空间采用线性分类器的方法。

考虑线性决策函数$g(x)=w^Tx+b$,令$\Pi:g(x)=0$则获得决策超平面。

可从线性方程的表示法说起，设二维空间一直线方程表示为：

$w_2x_2+w_1x_1+b=0$

其中$w_1$和$w_2$分别是$x_1$和$x_2$的系数。$b$是直线方程的参数项，由于$x=(x_1,x_2)^T$,$w=( w_1, w_2)^T$，则$w_2x_2+w_1x_1$就是这两个向量的点积，表示成$w^Tx+b=0$ 假设在该决策平面上有两个特征向量$x_1$与$x_2$，则应有 $\begin{aligned} w^T x_1+b=w^Tx_2+b \\ w^T(x_1-x_2)=0 \end{aligned}$ 因此$w$就是该超平面的法线向量。这就是向量$w$的几何意义。而$g(x)$也就是$d$维空间中任一点$x$到该决策面距离的代数度量，该决策平面将这两类样本按其到该面距离的正负号确定其类别。至于$b$则体现该决策面在特征空间中的位置，当$b=0$时，该决策面过特征空间坐标系原点，而$b\neq 0$时，则$\frac {b}{||w||}$表示了坐标原点到该决策面的距离。

对任意一个样本点$x$，$x=(x_1,\ldots,x_n)^T$及对应标签$y$,$y \in {+1,-1}$,到超平面的距离表示为$\gamma =\frac {y \cdot g(x)}{||w||}$

概念

• 贝叶斯决策理论：根据先验概率、类分布密度函数以及后验概率这些量来实现分类决策的方法，称为贝叶斯决策理论。由于这些量之间符合贝叶斯公式，因此称为贝叶斯决策理论。
• 基于最小错误率的贝叶斯决策：根据一个事物后验概率最大作为分类依据的决策，称为基于最小错误率的贝叶斯决策。从统计上讲，即从平均错误率角度看，分类错误率为最小，因此称为基于最小错误率的贝叶斯决策。
• 风险决策：对事物进行分类或做某种决策,都有可能产生错误，不同性质的错误就会带来各种不同程度的损失，因而作决策是要冒风险的。考虑到决策后果(风险)的决策是风险决策。如进行股票交易要冒风险，投资，确定建设项目，规划等都要冒风险，在衡量了可能遇到的风险后所作的决策称为风险决策。
• 基于最小风险的贝叶斯决策：如果样本$X$的实际类别为$w_i$，而作决策为$\alpha_j$则可以定义此时作$\alpha_j$决策的风险为$ \gamma (\alpha_j|w_i)$，由此可以确定对样本$X$做$\alpha_j$决策的期望损失，比较做不同决策的期望损失，选择期望损失最小的决策后最终决策。就是基于最小风险的贝叶斯决策。
• 判别函数：是一组与各类别有关的函数，对每一个样本可以计算出这组函数的所有函数值，然后依据这些函数值的极值(最大或最小)做分类决策。例如基于最小错误率的贝叶斯决策的判别函数就是样本的每类后验概率，基于最小风险的贝叶斯决策中的判别函数是该样本对每个决策的期望风险。
• 参数估计： 使用贝叶斯决策要知道先验概率，类分布密度函数等统计参数，为此，要从训练样本集中估计出这些统计参数，这就是参数估计。
• 非参数估计： 在分布密度函数形式也不确定条件下，估计统计参数，称为非参数估计。
• 非参数分类器： 不以统计参数为分类决策依据的分类决策方法称为非参数分类器, 线性分类器、非线性分类器以及近邻分类器都属于这种分类器，它们不需要统计参数。
  • 线性分类器：判别函数为线性函数的分类器是线性分类器，此时决策分界面的方程是线性方程。
  • 非线性分类器：是非参数分类器的一种，其中判别函数或决策面方程是某种特定的非线性函数，如二次函数，多项式函数等。
• 分段线性分类器：相邻决策域的界面用分段线性函数表示的分类器。

• 近邻法：通过计算待分类样本与已知类别的模板样本集计算相似度（相邻性）,从而以最相似模板样本的类别作为分类依据的方法。

  • K-近邻法：是近邻法中的一种，对待分类样本找到K个近邻，并以该K个近邻中的主导类别作为待分类样本的分类依据，当K=1时称为最近邻法。
  • 剪辑近邻法：对近邻法使用的模板样本集通过剪辑进行修正，以达到进一步减小错误率，压缩模板样本数量为目的。
  • 压缩近邻法：是另一种改进近邻法的方法，以最大限度削减近邻法中模板样本数量为目的。

• Fisher准则判别函数：线性分类器中的一种分类决策面设计方法，是由Fisher提出而得名，一般用于两类别分类器中。该种设计方法要找到分界面的最佳法线, 使两类别训练样本到该法线向量的投影体现“类间尽可能分离，类内尽可能密集”的最佳准则。

• 感知准则函数：是线性分类器的另一种著名设计方法。该种方法通过迭代优化确定最佳分界面。最佳准则取决于所使用的最佳准则，如最小错分数准则等。其特点是利用错分类信息对当前的分界面进行修正。

特征

• 特征选择： 对样本采用多维特征向量描述，各个特征向量对分类起的作用不一样，在原特征空间中挑选中部分对分类较有效的特征组成新的降维特征空间，以降低计算复杂度，同时改进或不过分降低分类效果特征选择的另一种含义是指人们通过观察分析选择适用于分类的特征。
• 特征提取： 特征提取是从样本的某种描述状态（如一幅具体的图象，一段声波信等）提取出所需要的，用另一种形式表示的特征（如在图象中抽取出轮廓信号，声音信号提取中不同频率的信息等）。这种提取方法往往都要通过某种形式的变换。如对原特征空间进行线性变换或其它变换，滤波也是变换的一种形式。特征提取也往往可以达到降维的目的。 目前使用什么样方法提取特征。主要靠设计人员确定，如选择什么样的变换，主要由人来决定，但如确定用某种线性变换，则线性变换的参数可通过计算来确定。
  • K-L变换： K-L变换是一种特殊的正交变换，它是通过对样本集协方差矩阵求的特征值与特征向量的方式构造正交变换。利用部分特征值最大的特征向量构造的正交变换可对原信号进行降维重构，重构后的信号与原信号之差为截尾误差时的最佳正交变换。最佳条件是指在降维数相同条件下，K-L变换的平均截尾误差平方和比任何一个其它正交变换要小。K-L变换的这种性质对信息压缩有价值，在模式识别中广泛用于特征提取。
  • 主分量分析：主分量分析是K-L变换的另一种名称。

聚类

• 聚类：一个数据集可能由若干个聚集成群的子集，每个子集称为一个聚类。找出这些按自然分布的聚类, 是聚类算法的目的与任务。聚类方法一般可分为动态聚类方法与分级聚类方法两大类。
  • 动态聚类方法：通过迭代使聚类划分逐步优化的方法，典型的方法有C-均值算法，ISODATA算法等，由于动态聚类方法是一种迭代优化算法，需要确定一种准则函数，迭代过程是使准则函数值趋于极度值的过程。准则函数超于极值应能反映聚类趋于更合理。
    • C-均值算法：是动态聚类方法中的一个典型方法。其目的是将一数据集, 按自然密集程度划分成C个聚类，它的准则函数是对所有C个聚类中每个数据到其各自均值的距离平方和的总和为最小。计算距离的最简单形式是欧式距离。但也可使用其它形式的距离。迭代过程是计算这个数据, 从现属聚类转移至其它聚类, 是否能使准则函数值减小为依据，将该数据转移至合适聚类，直至这种数据转移不再发生为止。在数据转移过程中各个聚类的均值也随之改变。
    • ISODATA算法：是另一种典型的动态聚类方法，它与C-均值算法的主要不同点是它包含聚类的分裂与合并过程，从而可以根据需要改变聚类的数目。
  • 分级聚类方法：对数据集采用逐级合并的方法进行聚类，在初始时整个数据集的每个数据自成一类，然后按相似度最高的要求进行合并，随着相似度要求逐次降低，小的集群逐级合并，聚类数量逐渐减少。这种方法基于分类学原理，如人与类人猿相近，猫与虎同属猫科, 就是基于这种原理。

感知准则函数(一)(二)

　　感知准则函数是五十年代由Rosenblatt提出的一种自学习判别函数生成方法，由于Rosenblatt企图将其用于脑模型感知器，因此被称为感知准则函数。其特点是随意确定的判别函数初始值，在对样本分类训练过程中逐步修正直至最终确定。

再生希尔伯特空间