势函数法

假设要划分属于两种类别${\omega }_1,{\omega }_2$的模式样本，这些样本可以看做是分布在$n$维模式空间中的点$x_k$，把属于${\omega }_1$的点比拟为某种能源点，在点上，电位达到峰值，随着与该点距离的增大，电位分布迅速减小，即把样本$x_k$附近空间$x$点上的电位分布看做一个实函数$K(x,x_k)$,，对于属于${\omega }_1$的样本集群，其附近空间会形成一个高地，这些样本点所处的位置就是山头，同理，用电位的几何分布来看待属于${\omega }_2$的样本，在其附近空间就形成一个凹地，只要在两类电位分布之间选择合适的等高线，就可以认为是模式分类的判别函数
模式分类的判别函数可由分布在模式空间中的许多样本向量{xk,k=1,2,⋯ ,xk∈(ω1⋃ω2)}\{x_k,k = 1,2,\cdots,x_k \in (\omega_1 \bigcup \omega_2)\}{xk​,k=1,2,⋯,xk​∈(ω1​⋃ω2​)}的势函数产生，任意一个样本所产生的势函数以$K(x,x_k)$表征，则判别函数$d(x)$可由势函数序列$K(x,x_1),K(x,x_2),\cdots$来构成，序列中的这些实函数相应于在训练过程中输入机器的训练模式样本$x_1,x_2,\cdots$，在训练状态，模式样本逐个输入分类器，分类器就连续计算相应的势函数，在第$k$步迭代时的积累位势决定于在该步前所有的单独实函数的累加，以$K(x)$表示积累位势函数，若加入的训练样本$x_{k+1}$是错误分类，则积累函数需要修改，若是正确分类，则不变

判别函数的产生

设初始势函数$K_0(x)=0$
第一步：加入第一个训练样本$x^1$，则有：
$$K_1(x)=\{\begin{array}{ll}K(x,x^1)& x^1\in {\omega }_1\\ -K(x,x^1)& x^1\in {\omega }_2\end{array}$$
这里第一步积累势函数$K_1(x)$描述了加入第一个样本时的边界划分，当样本属于$w_1$时，势函数为正，否则为负
第二步：加入第二个训练样本$x^2$，则有

• 若$x^2\in w_1$且$K_1(x^2)>0$，或$x^2\in w_2$且$K_1(x^2)<0$则分类正确，此时$K_2(x)=K_1(x)$即累积势函数不变
• 若$x^2\in w_1$且$K_1(x^2)<0$，则
  $$K_2(x)=K_1(x)+K(x,x^2)=\pm K(x,x^1)+K(x,x^2)$$
• 若$x^2\in w_2$且$K_1(x^2)>0$，则
  $$K_2(x)=K_1(x)-K(x,x^2)=\pm K(x,x^1)-K(x,x^2)$$
  第$K$步：设$K_k(x)$为加入训练样本$x^1,x^2,\cdots ,x^k$后的积累位势，则加入第$k+1$个样本时，$K_{k+1}(x)$决定如下：
• 若$x^{k+1}\in w_1$且$K_k(x^{k+1})>0$，或$x^{k+1}\in w_2$且$K_k(x^{k+1})<0$则分类正确，此时$K_{k+1}(x)=K_k(x)$即累积势函数不变
• 若$x^{k+1}\in w_1$且$K_k(x^{k+1})<0$，则
  $$K_{k+1}(x)=K_k(x)+K(x,x^{k+1})$$
• 若$x^{k+1}\in w_2$且$K_k(x^{k+1})>0$，则
  $$K_{k+1}(x)=K_k(x)-K(x,x^{k+1})$$
  因此积累位势的迭代运算可写成$K_{k+1}(x)=K_k(x)+r_{k+1}K(x,x^{k+1})$，其中$r_{k+1}$为校正系数：
  $$r_{k+1}=\{\begin{array}{ll}0& x^{k+1}\in w_1,K_k(x^{k+1})>0\\ 0& x^{k+1}\in w_2,K_k(x^{k+1})<0\\ 1& x^{k+1}\in w_1,K_k(x^{k+1})<0\\ -1& x^{k+1}\in w_2,K_k(x^{k+1})>0\end{array}$$
  若从给定的训练样本集{x1,x2,⋯ ,xk,⋯ }\{x^1,x^2,\cdots,x^k,\cdots\}{x1,x2,⋯,xk,⋯}中去除不使积累位势发生变化的样本，即使$K_j(x^{j+1})>0$且$x^{j+1}\in w_1$或$K_j(x^{j+1})<0$且$x^{j+1}\in w_2$的那些样本，可得到一简化的样本序列{x^1,x^2,⋯ ,x^j,⋯ ,}\{\hat{x}^1,\hat x^2,\cdots,\hat x^j,\cdots,\}{x^1,x^2,⋯,x^j,⋯,}，他们完全是校正错误的样本，此时上述迭代公式可归纳为：
  $$K_{k+1}(x)=\sum _{{\hat{x}}_j}{a}_{j}K(x,{\hat{x}}^j)$$
  其中:
  $$a_j=\{\begin{array}{ll}1& {\hat{x}}^j\in w_1\\ -1& {\hat{x}}^j\in w_2\end{array}$$
  也就是说由$k=1$个训练样本产生的积累位势，等于$w_1,w_2$类中的校正错误样本的总位势之差

势函数的选择

选择势函数的条件：一般来说，若两个$n$维向量$x,x_k$的函数同时满足下面三个条件，则可作为势函数：

• $K(x,x_k)=K(x_k,x)$并且当且仅当$x=x_k$时达到最大值
• 当向量$x$与$x_k$的距离趋向于无穷时，$K(x,x_k)$趋向0
• $K(x,x_k)$是光滑函数，且是$x$与$x_k$之间距离的单调下降函数

下面是构成势函数的两种方式

• 第一类势函数：可用对称的有限多项式展开，即：
  $$K(x,x^k)=\sum _{i=1}^m{\phi }_i(x){\phi }_i(x^k)$$
  其中{φi(x)}\{\varphi_i(x)\}{φi​(x)}在模式定义域内为正交函数集，将这类势函数代入判别函数，有：
  $$\begin{array}{rl}{d}_{k+1}(x)& =d_k(x)+r_{k+1}\sum _{i=1}^m{\phi }_i(x^{k+1}){\phi }_i(x)\\ & =d_k(x)+\sum _{i=1}^m{r}_{k+1}{\phi }_i(x^{k+1}){\phi }_i(x)\end{array}$$
  得迭代关系：
  $$d_{k+1}(x)=\sum _{i=1}^m{C}_i(k+1){\phi }_i(x)$$
  其中
  $$C_i(k+1）=C_i(k)+r_{k+1}{\phi }_i(x^{k+1})$$
  因此，积累位势可写成：
  $$K_{k+1}(x)=\sum _{i=1}^m{C}_i(k+1){\phi }_i(x),$$
• 第二类势函数：选择双变量$x,x^k$的对称函数作为势函数，即$K(x,x^k)=K(x^k,x)$，并且它可展开成无穷级数，例如：
  $$\begin{array}{rl}K(x,x^k)& =e^{-a||x-x^k|{|}^2}\\ K(x,x^k)& =\frac{1}{1+\alpha ||x-x^k|{|}^2}\\ K(x,x^k)& =\frac{\sin \alpha ||x-x^k|{|}^2}{\alpha ||x-x^k|{|}^2}\end{array}$$

决策树

决策树对应于对特征空间的一个划分，它把特征空间分成若干个区域，在每个区域中，某类的样本占优势，二叉树结构分类器可以把一个复杂的多类别分类问题转化为多级多个两类问题来解决，在每个非终止节点都把样本集分成左右两个子集，分成的每一部分任然可能包含多个类别的样本，可以把每一部分再分成两个子集，如此下去，直至分成的每一部分只包含同一类别的样本，或某一类样本占优势为止