现代模式识别.docx

现代模式识别.docx

《现代模式识别.docx》由会员分享，可在线阅读，更多相关《现代模式识别.docx（31页珍藏版）》请在冰点文库上搜索。

现代模式识别

现代模式识别

算法实现

Parzen窗法原理：

在统计决策中，需要知道类的概率密度p（x/wi）、类的概率密度P（wi）或后验概率P（wi/x），但在实际应用中，这些知识往往是不知道或不完全知道的，这就需要根据来自这一类的样本来确定它们。

用估计序列：

（1）

来估计p（x）。

它与N，V，

有关，从理论上讲，要使

趋进p（x），就必须让其体积V近于零，同时让N，

无穷大。

Parzen窗法使区域序列的体积VN按N的某个函数随N的增大不断地缩小，例如

，这时对

和

/N都要加以适当的限制，以使

收敛于p（x）。

在n维特征空间中，我们取一n维超立方体区域，其棱长为hN，则其体积

。

因此，N个样本落入该立方体的样本数

将上式代入

（1）式，可得x点处概率密度估计：

其中，

（x）为满足下列两个条件的窗函数：

.

.

容易知道，条件

保证

非负，条件

保证

。

程序用到的四个窗函数：

1.方窗函数：

2.正态窗函数

3.指数窗函数

4.三角窗函数

二、具体实现

1.本方法是用matlab实现，

结果图如下

h1=0.25h1=1h1=4

N=1

N=16

h1=0.25h1=1h1=4

N=256

N=∞

从图中结果可以看出，样本量越大，估计越精确，同时在N较小时窗宽选择是否适当对估计结果

有一定的影响。

当N较小时，窗函数对估计结果影响较大，其估计结果与真实分布相差较远；当

N增大时，估计结果与真实分布较为接近。

附matlab程序：

%--------------------------------------------

%parzen窗估计法

%px为均值为零，方差为1的一维正态分布

%创函数选择为正态窗函数1/sqrt（2*pi）*exp（-u^2/2）

%窗宽hN=h1/sqrt（N）

%--------------------------------------------

clearall;

%预置参数

N=1;

h1=4;

px=zeros（1,201）;

x=-2:

0.02:

2;

fori=1:

N;

ran=randn（1,201）;%产生N个正态分布样本

forj=1:

201;

px（j）=px（j）+（sqrt（N）/（h1*sqrt（2*pi）））*exp（（x（j）-ran（j））^2*N/（-2*h1*h1））;

end;

end;

semilogy（x,px/N）;

axis（[-4,4,0.001,10.0]）;

2．用VC实现

doubleCParzenWnd:

:

WndFunc（vectoru）

{

vector:

:

iteratorvi;

doublelen=0.0;

//首先判断维数是否正确

if（u.size（）!

=m_nDim）

{

exit（0）;

return-1;

}

//判断其和原点的距离，利用二范数

for（vi=u.begin（）;vi!

=u.end（）;vi++）

{

len+=（*vi）*（*vi）;

}

if（sqrt（len）<=0.5）

return1;

else

return0;

}

doubleCParzenWnd:

:

Probility（vectorx）

{

constdoubleVN=1.0;

doublep=0.0;

list>:

:

iteratorli;

//实现在x处的内插函数

for（li=m_listSample.begin（）;li!

=m_listSample.end（）;li++）

{

p+=WndFunc（VecOperator（x,*li,1））;

}

returnp/m_listSample.size（）;

ISODATA算法的C++实现

算法原理：

略。

具体实现：

创建一个类classDef，该类主要包含的参数为：

float*centre;//类心；

floatdj_mean;//类中的模式到类心的平均距离

intnj;//类内模式的个数；

vectordeta_j;//类内距离的标准差矢量;

vectormodls;//类中的模式;

floatdetaj_max;//最大标准差;

intpos_max;//最大标准差分量的位置;

以及对参数的处理函数：

voidcmp_centre（）;//计算本类的中心

voidcmp_meandis（）;//计算类中模式到类心的平均距离

voidcmp_deta（）;//计算类内距离的标准差矢量；

程序实现时，模式以矩阵形式获得，将各个模式按算法原理分类，并处理各类，并根据输入（或默认）参数进行分裂合并活动。

验证结果，很好的体现了算法的思想，并获得了正确的结果。

采用书上的例子的数据，得出如下正确结果。

输入模式矩阵

输入矩阵的行数（即模式的个数）:

8

输入矩阵的列数（即模式的维数）:

2

请输入第1个模式

0

0

请输入第2个模式

1

1

请输入第3个模式

2

2

请输入第4个模式

4

2.6

请输入第5个模式

4

3.7

请输入第6个模式

5

2.6

请输入第7个模式

5

3.8

请输入第8个模式

6

4.6

00

11

22

42.6

43.7

52.6

53.8

64.6

是否需要定义/重新定义控制参数的值（y/n）n

第1次迭代

分成2类:

第1类的类心为:

4.373042.5375

00

11

22

42.6

43.7

52.6

53.8

64.6

第2类的类心为:

2.376962.5375

是否需要定义/重新定义控制参数的值（y/n）n

第2次迭代

分成2类:

第1类的类心为:

4.83.46

42.6

43.7

52.6

53.8

64.6

第2类的类心为:

11

00

11

22

是否需要定义/重新定义控制参数的值（y/n）n

第3次迭代

分成2类:

第1类的类心为:

4.83.46

42.6

43.7

52.6

53.8

64.6

第2类的类心为:

11

00

11

22

是否需要定义/重新定义控制参数的值（y/n）n

第4次迭代

分成2类:

第1类的类心为:

4.83.46

42.6

43.7

52.6

53.8

64.6

第2类的类心为:

11

00

11

22

迭代结束Pressanykeytocontinue

具体程序如下：

#include

#include

#include

#include

#include

#include

usingnamespacestd;

//输入参数定义----------------------------------------------

float**X;//模式矩阵；

//int**centre;//聚类中心矩阵,定义成c*dim有效个数为Nc*dim；因为Nc

intc=2;

intNc=1;

intseta_n=2;

intseta_s=1;

intseta_D=4;

intL=1;

intI=4;

//全局变量定义-----------------------------------------------

intdim,num;//模式矩阵的维数和列数（即个数）

floatd_mean;//各个模式到其类内中心的总体平均距离

intIp;//程序迭代次数；

vectorclassList;//所分的类

vector:

:

iteratorpointer;

//函数定义---------------------------------------------------

voidinputPara（）;

voidinputX（）;

voidinitiate（）;

voidclassAllot（）;

voidcls_combine（）;

voidcls_divide（）;

voidshowClass（）;

//类定义-----------------------------------------------

classclassDef

{

public:

float*centre;//类心；

floatdj_mean;//类中的模式到类心的平均距离

intnj;//类内模式的个数；

vectordeta_j;//类内距离的标准差矢量;

vectormodls;//类中的模式;

floatdetaj_max;//最大标准差;

intpos_max;//最大标准差分量的位置;

classDef（intdim,float*x）;

~classDef（）;

voidcmp_centre（）;

voidcmp_meandis（）;

voidcmp_deta（）;

//voidcmp_max（）;

};

classDef:

:

classDef（intdim,float*x）

{

inti;

nj=0;

centre=newfloat[dim];

for（i=0;i

*（centre+i）=*（x+i）;

}

classDef:

:

~classDef（）

{

//deletecentre;

}

/***********************************

*voidclassDef:

:

cmp_centre（）

*计算本类的中心

***********************************/

voidclassDef:

:

cmp_centre（）

{

inti,j;

floathe;

for（i=0;i

{

he=0;

for（j=0;j

{

he+=*（modls[j]+i）;

}

*（centre+i）=he/nj;

}

}

/**********************************

*voidclassDef:

:

cmp_deta（）

*计算各类中模式到类心的平均距离

**********************************/

voidclassDef:

:

cmp_meandis（）

{

inti;

floathe=0;

for（i=0;i

{

he+=distance（modls[i],centre）;

}

dj_mean=he/nj;

}

/*********************************

*voidclassDef:

:

cmp_deta（）

*计算各类类内距离的标准差矢量

*********************************/

voidclassDef:

:

cmp_deta（）

{

inti,j;

floatmid_deta;

detaj_max=0;

pos_max=0;

deta_j.clear（）;

for（i=0;i

{

mid_deta=0;

for（j=0;j

{

mid_deta+=pow（（*（modls[j]+i）-*（centre+i））,2）;

}

mid_deta=sqrt（mid_deta/nj）;

deta_j.push_back（mid_deta）;

if（mid_deta>detaj_max）

{

detaj_max=mid_deta;

pos_max=i;

}

}

}

//---------------------------------------------------------

voidmain（intargc,char*argv[]）

{

inputX（）;

inputPara（）;

initiate（）;

for（Ip=1;;Ip++）

{

//step2to4;

classAllot（）;

//step5

if（Ip==I）

{

seta_D=0;

//类合并，step9to10;

cls_combine（）;

cout<<"第"<

showClass（）;

break;

}

if（Nc<=（c/2））

{

//类分裂，step8

cls_divide（）;

}

else

{

if（（Nc>=2*c）|（Ip%2==0））

{

cls_combine（）;

}

else

{

cls_divide（）;

}

}

cout<<"第"<

showClass（）;

//检查是否要重新输入参数

if（Ip!

=I）

{

inputPara（）;

}

}

cout<

}

/**************************************

*

*voidinputX（）

*输入模式矩阵X[Num][dim]

*

***************************************/

voidinputX（）

{

inti,j;

cout<<"输入模式矩阵"<

cout<<"输入矩阵的行数（即模式的个数）:

";

cin>>num;

cout<

cout<<"输入矩阵的列数（即模式的维数）:

";

cin>>dim;

cout<

X=newfloat*[num];

for（i=0;i

{

cout<<"请输入第"<

X[i]=newfloat[dim];

for（j=0;j

{

cin>>X[i][j];

}

}

//显示矩阵；

for（i=0;i

{

cout<

for（j=0;j

{

cout<

}

}

cout<

}

/**************************************

*

*voidinputPara（）

*输入控制参数并判断是否需要重设；

*

***************************************/

voidinputPara（）

{

chara;

cout<<"是否需要定义/重新定义控制参数的值（y/n）";

cin>>a;

cout<

if（a=='y'）

{

cout<<"\n请输入预期的聚类中心数目:

";

cin>>c;

cout<

cout<<"请输入初始聚类中心个数:

";

cin>>Nc;

cout<

cout<<"\n请输入每一类中允许的最少模式数目:

";

cin>>seta_n;

cout<

cout<<"\n类中各分量分布的标准差上限:

";

cin>>seta_s;

cout<

cout<<"两类中心间的最小距离下限:

";

cin>>seta_D;

cout<

cout<<"输入每次迭代中可以合并的类的最多对数:

";

cin>>L;

cout<

cout<<"允许的最多迭代个数:

";

cin>>I;

cout<

}

}

floatdistance（float*mod,float*centre）

{

inti;

floatdis=0;

for（i=0;i

{

dis+=（*（mod+i）-*（centre+i））*（*（mod+i）-*（centre+i））;

}

returnsqrt（dis）;

}

/********************************

*voidinitiate（）

*取前Nc个模式初始聚类中心

********************************/

voidinitiate（）

{

inti;

for（i=0;i

{

classDefcld（dim,X[i]）;

classList.push_back（cld）;

}

}

/*******************************

*voidclassAllot（）

*将模式分类，

*并计算分类后各类的参数

*step2to4

*******************************/

voidclassAllot（）

{

inti,j,pos;

floatdis;

floatmin;

boolchange=true;

//清除分到该类的模式（以待分类/重新分类）

if（change）

{

for（i=0;i

{

classList[i].modls.clear（）;

classList[i].nj=0;

}

}

while（change）

{

change=false;

//将各个模式分类step

（2）

for（i=0;i

{

min=distance（X[i],classList[0].centre）;

pos=0;

for（j=1;j

{

dis=distance（X[i],classList[j].centre）;

if（dis

{

min=dis;

pos=j;

}

}

classList[pos].modls.push_back（X[i]）;

classList[pos].nj++;

}

//由seta_n判断合并step（3）

pointer=classList.begin（）;

intk=Nc;

for（i=0;i

{

if（classList[i].nj

{

change=true;

classList.erase（pointer）;

Nc--;

}

pointer++;

}

}

//计算分类后的参数step（4）（6）

for（i=0;i

{

classList[i].cmp_centre（）;

classList[i].cmp_meandis（）;

classList[i].cmp_deta（）;

}

//计算总体平均距离step（4）

d_mean=0;

for（i=0;i

{

d_mean+=classList[i].nj*classList[i].dj_mean;

}

d_mean/=num;

}

/******************************************

*voidcls_divide（）

*将符合条件的类分裂

*step8

******************************************/

voidcls_divide（）

{

inti;

intmid=Nc;

booldiv=false;

pointer=classList.begin（）;

for（i=0;i

{

if（（classList[i].detaj_max>seta_s）&&

（（（classList[i].dj_mean>d_mean）&（classList[i].nj>2*（seta_n+1）））

|（Nc<=c/2）））

{

//有类分裂发生

div=true;

mid++;

classDefcld（dim,classList[i].centre）;

//新的类心zj-

*（cld.centre+classList[i].pos_max）-=0.5*（classList[i].detaj_max）;

//加到类的容器中