中科大,2014年,模式识别

模式识别大作业实验报告

MyZenith（PB1*210***）

ByN_3104_EVER

实验一：

（1） 已知二维模式样本集 X1={（1,0），（1,1），（0,2）} X2={（2,1），（2，2），（1,3）} ，

用固定增量算法求分界面方程，并作图。

（2） 分别改变初始权值向量和样本集中样本顺序来获得不同的结果。

（3） 自定义线性不可分样本（如 X1={（1,0），（1,1）} X2={（0,1），（1,0）}），通过限

定算法迭代次数（如 100 次）得到结果并分析。

（4） 分析实验结果和所得结论，撰写实验报告。

实验目的：

通过编程实现感知器算法，加深对感知器算法的认识，掌握对分界面求取的步骤与过

程。

实验代码: 使用 MATLAB

编程实现：主程序：

function [ output_args ] = main1( input_args )

x1=[1,0;1,1;0,2]; x2=[2,1;2,2;1,3];

[m,n]=size(x1);

% w=double(ones(1,n+1));%设定权向量

w=double([1,0,1]);

w=func1(x1,x2,w,0.3); axis([-1 3 -1

4]);hold;

scatter(x1(1,1),x1(1,2),'red');

scatter(x1(2,1),x1(2,2),'red');

scatter(x1(3,1),x1(3,2),'red');

scatter(x2(1,1),x2(1,2),'blue');

scatter(x2(2,1),x2(2,2),'blue');

scatter(x2(3,1),x2(3,2),'blue');

line([0,-w(3)/w(1)],[-w(3)/w(2),0]);end

功能函数：

function [ output_args ] = func1( w1,w2,w,c )

[m1,n1]=size(w1); [m2,n2]=size(w2);

ww1=double(ones(m1,n1+1));%¹¹ÔìÔö¹ãÏòÁ¿

ww2=double(ones(m2,n2+1));for i=1:m1for

j=1:n1

ww1(i,j)=w1(i,j);endendfor

i=1:m2for j=1:n2

ww2(i,j)=w2(i,j);endend

ww2=-ww2;

isover=0;while isover ~= m1+m2

中科大,2014年,模式识别

isover = 0;for i=1:m1

g=ww1(i,:).*w;

sm=sum(g);if sm <= 0

w = w+c*ww1(i,:);else

isover = isover+1;endendfor

i=1:m2 g=ww2(i,:).*w;

sm=sum(g);if sm <= 0

w = w+c*ww2(i,:);else

isover = isover+1;endendend

output_args = w;end

运行结果：

中科大,2014年,模式识别

（2）改变权值 w=[1,1,0] 结果如下：

中科大,2014年,模式识别

其图均相同,故可知 w 的选择影响算法的迭代次数。

（3）

代码如下:

x=[1 1 0 -1;

0 1 -1 0; 1 1 -1 -1;]; w=[1,1,1]; k=0; p=1; n=0; while ((n<4)&&(k<100)) i=mod(k,4)+1; g=w*x(:,i);if(g<=0) w=w+p*x(:,i)';

n=0;else n=n+1;end k=k+1;endlx=-3:1:3;tx=[1 1 0 1;];ty=[0 1

1 0;]; tx1=[1 1];tx2=[0 1];ty1=[0 1];ty2=[1 0]; plot(tx1,ty1,'blue'); hold on;plot(tx2,ty2,'red'); hold on;ly=-

((w(:,1)*lx+w(:,3))/w(:,2));plot(lx,ly);hold on;

中科大,2014年,模式识别

由图可知，感知器算法在得到最优解之前会一直迭代下去。

实验小结：使用 matlaB 成功展示了感知器算法在模式识别中的作用，对权向量，线性 可分/不可分的数据都进行了处理，由此可以验证感知器算法的一系列性质。

实验二：

实验题目：

1

2

3

4 试就不同的初始分化，观察集群结果对初始分化的敏感性。 比较各群样本都很密集并且彼此明显分开的情况下与各群样本数目相差很大时，误差平方和集群效果，了解误差平方和准则函数集群的优势和缺陷。 试对算法进行适当改进使其可以对样本数目相差很大的情况进行集群，用文字叙述改进的思路。 给出以上各种情况的图形结果，撰写实验报告。

实验目的：熟悉误差平方和函数的集群方法，能分析初始化对集群带来的影响，了解误差平方和集群方法的优劣。原理分析与程序源码：

误差平方和准则函数：

实验代码：

N=100;m=5;sample=r

and(N,2);center=ra

nd(m,2);times=0;cl

ass=ones(N);while

(times<=100)

times=times+1for

i=1:Ndist=2;for

j=1:m

中科大,2014年,模式识别

t=norm(sample(i,:)-

center(j,:));if t<dist

dist=t;no=j;endend

class(i)=no;endfor j=1:m

tt=[0,0];number=0;for i=1:Nif class(i)==j

tt=tt+sample(i,:);

number=number+1;endend tt=tt/number;

center(j,:)=tt;endend

temp=['o','+','^','*','p','h','.','v','>','<'];for

i=1:N

plot(sample(i,1),sample(i,2),temp(class(i)));hold on;endfor j=1:m plot(center(j,1),center(j,2),temp(j),'MarkerSize',15,'Color','r');hol d on;

end

实验结果：

各群样本都很密集并且彼此明显分开的情况下：

各群样本数目相差很大时，由于程序中已经设置聚类中心随机生成，故其的图也是随机变化的：

中科大,2014年,模式识别

中科大,2014年,模式识别

实验小结：使用 matlab 编程验证了最小均方误差算法的适用性以及在不同场合下产生的不同聚类效果，直观的效果加强了对其的认识。

实验三：

实验题目：

给定正规文法 G={Vn,Vt,P,S} Vn={S,B} Vt={a,b} P: S-

>aB, B->bS, B->aB, B->a

构造确定的有限自动机后，编制确定的有限自动机算法，并分析链：检验

X=aababaaababaaa 和 X=ababaababaaba 是否能被 G 接受。

（1） 总结出被接受的链的一般特征。

（2） 分析正规文法和确定的有限自动机的联系并撰写实验报告。

实验目的：掌握语言根据文法的构造方法，总结被接受的链的一般特征。知道有限状态自

动机识别

语言的过程。

实验代码：方案一：

%vector=(1,0,0)=>S

%vector=(0,1,0)=>B%vector=(0,0,

1)=>Wrongs1='aababaaababaaa';ch

eck(s1);s2='ababaababaaba';chec

k(s2); function

output=check(ss)

vector=[1,0,0];

中科大,2014年,模式识别

A=[0 1 0;0 1 0;0 0 1];

B=[0 0 1;1 0 0;0 0 1];for

i=1:length(ss)-1if

(ss(i)=='a')

vector=vector*A;else

vector=vector*B;endend

if (vector==[0 1 0] & ss(end)=='a')

disp('¿ÉÒÔ±»½ÓÊÜ');else

disp('²»¿ÉÒÔ±»½ÓÊÜ');endend；

实验结果：

另外参考代码：

function [ T ] = func3( X )

% Sigma='ab';%¡Æ

% Q='SBT';

q0='S';

T=myfind(q0,X);if(T==

'T')

T='recepted';else

T='unrecepted';endend

function [result]=myfind(recent,X)

result = ' '; n=size(X,2);

next=delta(recent,X(1),1);if

n==1&&next=='T' result =

'T';return;elseif n==1||next==' '

result = ' ';% return;else

T=myfind(next,X(1,2:n));if

T=='T' result =

T;return;endendif recent=='B'&&

X(1)=='a'

next=delta(recent,X(1),2);if

中科大,2014年,模式识别

n==1&&next=='T'

result = 'T';return;elseif n==1

result = ' ';return;else

T=myfind(next,X(1,2:n));if T=='T'

result = T;return;else

result = ' ';return;endendend

end

function [next] =

delta(recent,step,n)%¦Äswitch

recentcase'S'switch stepcase'a'

next='B';case'b'

next=' ';endcase'B'switch

stepcase'a'switch ncase 1

next='B';case 2

next='T';endcase'b'

next='S';endcase'T'switch stepcase'a'

next=' ';case'b'

next=' ';endend

end

经过验证有同样的效果！

实验小结：有限状态自动机是具有离散输入和输出的系统的一种数学模型。

其主要特点有以下几个方面：

– (1)系统具有有限个状态，不同的状态代表不同的意义。按照实际的需要，系统可以在不同的状态下完成规定的任务。

– (2)我们可以将输入字符串中出现的字符汇集在一起构成一个字母表。系统处理的所有字符串都是这个字母表上的字符串。

– (3)系统在任何一个状态下，从输入字符串中读入一个字符，根据当前状态和读入的这个字符转到新的状态。

– (4)系统中有一个状态，它是系统的开始状态。

– (5)系统中还有一些状态表示它到目前为止所读入的字

被接受的链的一般特征：

非确定有限状态自动机与确定有限状态自动机的唯一区别是它们的转移函数不同。确定有限状态自动机对每一个可能的输入只有一个状态的转移。非确定有限状态自动机对每一个可能的输入可以有多个状态转移，接受到输入时从这多个状态转移中非确定地选择一个。

确定有限自动机(DFA)：

自动机的每个状态都有对字母表中所有符号的转移。

非确定有限自动机(NFA)：

自动机的状态对字母表中的每个符号可以有也可以没有转移，对一个符号甚至可以有多个转移。自动机接受一个字，如果存在至少一个从 q0 到 F 中标记(label)著这个输入字的一个

中科大,2014年,模式识别

状态的路径。如果一个转移是「未定义」的，自动机因此不知道如何继续读取输入，则拒绝这个字。