模式识别

固定增量法求分界面

实验目的：

1. 使用C++编写程序，完成对固定增量法求分界面的上机实现。
2. 深入理解固定增量法求分界面，包括初始权向量、样本集顺序对所求分界面的影响；固定增量值的大小对迭代进程和迭代是否收敛的影响；线性不可分样本使用有限迭代次数得到结果等等。
3. 提高编写程序的分而治之程度，注释完善、提高可读性。

实验原理：

感知器算法中固定增量ρ。在每一次迭代过程中，若发现未正确分类的样本，就对判别函数进行权值修正，直到全部样本都正确分类，输出判别函数。
① 给定初始值：置 k  0，分别给每个权向量赋任意值，可选常数c  0。
② 输入训练样本 Xk ， xk {x1, x2,…, xn}
③ 计算判决函数值： g(Xk)=[w(k)]*Xk
④ 修正权向量 w(k) ，修正规则如下：
若 x w k i  和 g(xk )  0，则 w(k 1)  w(k)  cxk
若 x w k j  和 g(xk )  0，则 w(k 1)  w(k)  cxk
如果类型 wj 的训练样本 xk 的各分量均乘以（－ 1），则修正规则统
一为：
若： g(xk )  0,则 w(k 1)  w(k)  cxk
⑤ 令k  k 1，返回②。直到 w对所有训练样本均稳定不变，则结
束。一般情况， 0  c 1。 c值大小会影响收敛速度和稳定性， c太小收
敛速度慢， c太大，会使 w(k) 的值不稳定。

设计思路：

1. 定义C++结构体变量sample来表达每一个样本特征值扩展向量，同时使用该结构体表达权向量。
2. 使用sample结构体数组存储样本集的值。
3. 定义一系列函数，包括：对样本赋值函数、对样本判别值求解函数、判断分类是否正确函数、各种输出函数、固定增量迭代函数、限制迭代次数的固定增量迭代函数等等。
4. 固定增量迭代函数是整个实验核心函数，根据固定增量感知器算法原理，使用while循环，并用变量Nc记录正确分类的样本数，当所有样本正确分类，while循环结束。循环内部主要由判断是否正确分类函数、权向量修正函数够成。
5. 主函数中依次调用函数实现
   1） 固定增量法求分界面方程
   2） 改变样本集顺序并使用固定增量法求分界面函数
   3） 改变初始权向量并使用固定增量法求分界面函数
   4） 限定迭代次数为100求线性不可分样本集的分界面函数

实验内容及对应结果与结论：

1. 二维模式样本集使用固定增量感知器算法求解分界面方程
   程序结果：
   

据程序结果可以看出感知器固定增量算法得到了可以将所有样本集正确分类的分界面。
作图如下：

从图形上显然易见，分界面成功正确的将样本集分类

2. 改变样本集顺序并使用固定增量法求分界面
   程序结果：
   

根据程序结果，可得结论：相同的初始权向量、相同的固定增量值，若样本集顺序不同，迭代得到的分界面方程可能不同，但都能将样本集正确的分类。

3. 改变初始权向量并使用固定增量法求分界面
   程序结果：
   

根据程序结果，可得结论：样本集顺序相同、固定增量值相同，若初始权向量不同，迭代得到的分界面方程可能不同，但都能将样本集正确的分类。
另外，还可以看到，不同的初始条件，例如初始权向量、样本集顺序都可能影响迭代的次数。

4. 自定义线性不可分样本并使用固定增量法求分界面
   程序结果：
   若不限定算法迭代次数，程序会一直停留如下界面
   

说明找不到能使样本正确分类的权向量，算法迭代陷入无限循环，因为找不到可以正确分类的分界面
限定迭代次数为100次时得到如下结果：

首先，限定迭代次数之后，程序不会陷入无限循环，将会得到一个具体的分界面。检验该分界面可知，该分界面只能将一部分样本值正确分类。

/*
  
  固定增量法求分界面
  
*/ 


//#include<math.h>
//#include<stdio.h>
#include<iostream>
//#include<iomanip>
using namespace std;
struct sample{                                      //样本增值模式结构体定义 
	int a;
	int b;
	int c;
}; 

void initsample(sample &W,int m,int n,int o){ //样本赋值函数 
	W.a=m;
	W.b=n;
	W.c=o;
}

int WX(sample W1,sample W2){                        //判别函数求值 
	int t;
	t=W1.a*W2.a+W1.b*W2.b+W1.c*W2.c;
	return t;
}

int judge(sample W1,sample W2){                     //权向量是否合理分类判别函数 
	int t;
	t=WX(W1,W2);
	if(t>0) return 1;
	if(t<=0) return 0;
}

void updateW(sample &W,sample w){                   //权向量修正函数 
	W.a=W.a+w.a;
	W.b=W.b+w.b;
	W.c=W.c+w.c;
}

void output(sample W){                              //权向量、判别函数输出函数 
	cout<<"权向量为：";
	cout<<"("<<W.a<<","<<W.b<<","<<W.c<<")"<<endl;
    cout<<"判别函数为：";
	cout<<"G(x)="; 
	if(W.a!=0) cout<<W.a<<"x1";
	if(W.b!=0) {
		if(W.b>0) cout<<"+"<<W.b<<"x2";
		else cout<<W.b<<"x2";
	}
	if(W.c!=0){
		if(W.c>0) cout<<"+"<<W.c;
		else cout<<W.c;
	}
	cout<<endl;
}

void coutsample(sample *w,int k){                   //样本集输出函数 
	cout<<"训练样本(已正则化)："<<endl;
	for(int i=0;i<k;i++){
		cout<<"X"<<i+1;
	    cout<<"("<<w[i].a<<","<<w[i].b<<","<<w[i].c<<")"<<endl;	
	}
}

void initsamples(sample *w1,sample *w2,sample *w3){            //样本集赋值函数 
	initsample(w1[0],1,0,1);
	initsample(w1[1],1,1,1);
	initsample(w1[2],0,2,1);
	initsample(w1[3],-2,-1,-1);
	initsample(w1[4],-2,-2,-1);
	initsample(w1[5],-1,-3,-1);
	initsample(w2[0],1,1,1);
	initsample(w2[1],1,0,1);
	initsample(w2[2],0,2,1);
	initsample(w2[3],-1,-3,-1);
	initsample(w2[4],-2,-1,-1);
	initsample(w2[5],-2,-2,-1);
	initsample(w3[0],1,0,1);
	initsample(w3[1],1,1,1);
	initsample(w3[2],0,-1,-1);
	initsample(w3[3],-1,0,-1);
}

void output_init(sample W1){                        //初始权向量输出函数 
	cout<<"初始权向量为：";
    cout<<"("<<W1.a<<","<<W1.b<<","<<W1.c<<")"<<endl;
}

int doit(sample &W,sample *w){                     //固定增量迭代函数 
	int Nc=0,k=0,n=0;
	while(Nc!=6){
		if(judge(W,w[k]))                           //判断权向量是否合适 
		Nc+=1;
		else {
		updateW(W,w[k]);                            //对权向量进行修正 
		Nc=0;
	    }
	    k=(k+1)%6;                                  // 迭代找到权向量 
        n++;
	}
	return n;
}

void limited_doit(sample &W,sample *w,int n){       //限定迭代次数的迭代函数 
	int Nc=0,k=0,i=0;
	while(Nc!=4&&i<=n){
		if(judge(W,w[k]))                           //判断权向量是否合适 
		Nc+=1;
		else {
		updateW(W,w[k]);                            //对权向量进行修正 
		Nc=0;
	    }
	    k=(k+1)%4; 
		i++;                                        // 迭代次数计数器加一 
	}
}

int main(){
	sample w1[6],w2[6],w3[4];                                            //定义不同的样本集 
	sample W;                                                            //定义初始权向量 
    int n=0;
	initsamples(w1,w2,w3);                                               //为不同的样本集赋值 
	coutsample(w1,6);                                                    //输出样本集 
	initsample(W,1,1,1);                                                 //为初始权向量赋值                       
    output_init(W);                                                      //输出初始权向量 
    n=doit(W,w1);                                                          //进行固定增量求分界面迭代 
	output(W);                                                           //输出最终权向量及分界面方程 
    cout<<"迭代次数："<<n<<endl; 
	/*改变样本集顺序并使用固定增量法求界面方程*/	
	cout<<endl<<"************************************"<<endl<<endl;
	cout<<"改变样本集顺序："<<endl;
	coutsample(w2,6);
	initsample(W,1,1,1);                                             
    output_init(W);
    n=doit(W,w2);
	output(W);	
    cout<<"迭代次数："<<n<<endl;
	/*改变初始权向量并使用固定增量法求界面方程*/
	cout<<endl<<"************************************"<<endl<<endl;
	cout<<"改变初始权向量："<<endl;
	coutsample(w1,6);
	initsample(W,1,3,3);                                           
    output_init(W);
    n=doit(W,w1);
	output(W);
    cout<<"迭代次数："<<n<<endl;	
	/*限定算法迭代次数为100*/
	cout<<endl<<"************************************"<<endl<<endl;
	cout<<"线性不可分样本，限定算法迭代次数为100"<<endl;
	coutsample(w3,4);
	initsample(W,1,1,1);                                           
    output_init(W);
    limited_doit(W,w3,100);                                                //限定迭代次数为100次 
	output(W);		
	return 0;
}