模式识别实验

《模式识别》实验报告

班级：电子信息科学与技术13级02 班姓名：

学号：

指导老师：

成绩：

通信与信息工程学院二〇一六年

实验一 最大最小距离算法

一、实验内容

1. 熟悉最大最小距离算法，并能够用程序写出。

2. 利用最大最小距离算法寻找到聚类中心，并将模式样本划分到各聚类中心对应的类别中。

二、实验原理

N 个待分类的模式样本{}N X X X ， 21,，分别分类到聚类中心{}N Z Z Z ， 21,对应的类别之中。

最大最小距离算法描述：

（1）任选一个模式样本作为第一聚类中心1Z 。

（2）选择离1Z 距离最远的模式样本作为第二聚类中心2Z 。

（3）逐个计算每个模式样本与已确定的所有聚类中心之间的距离，并选出其中的最小距离。

（4）在所有最小距离中选出一个最大的距离，如果该最大值达到了

21Z Z -的一定分数比值以上，则将产生最大距离的那个模式样本定义为新增的聚类中心，并返回上一步。否则，聚类中心的计算步骤结束。这里的21Z Z -的一定分数比值就是阈值T ，即有：

102

1<<-=θθZ Z T

（5）重复步骤（3）和步骤（4），直到没有新的聚类中心出现为止。在这个过程中，当有k 个聚类中心{}N Z Z Z ， 21,时，分别计算每个模式样本与所有聚类中心距离中的最小距离值，寻找到N 个最小距离中的最大距离并进行判别，结果大于阈值T 是，1+k Z 存在，并取为产生最大值的相应模式向量；否则，停止寻找聚类中心。

（6）寻找聚类中心的运算结束后，将模式样本{}N i X i ,2,1, =按最近距离划分到相应的聚类中心所代表的类别之中。

三、实验结果及分析

该实验的问题是书上课后习题2.1，以下利用的matlab中的元胞存储10个二维模式样本

X{1}=[0;0];X{2}=[1;1];X{3}=[2;2];X{4}=[3;7];X{5}=[3;6];

X{6}=[4;6];X{7}=[5;7];X{8}=[6;3];X{9}=[7;3];X{10}=[7;4];

利用最大最小距离算法，matlab运行可以求得

从matlab运行结果可以看出，聚类中心为

9

7

1

,

,X

X

X，以

1

X为聚类中心的

点有

3

2

1

,

,X

X

X，以

7

X为聚类中心的点有

7

6

5

4

,

,

,X

X

X

X，以

9

X为聚类中心的有10

9

8

,

,X

X

X。同时，做出聚类分析后的分布图，如下：

012345678

1

2

3

4

5

6

7

8

9

样本坐标聚类显示图

图中用蓝色大圈标记了聚类中心，用星号标记了以

1

X为聚类中心的样本，

用三角符号标记了以以

7

X为聚类中心的样本，用红色小圈标记了以

9

X为聚类中

心的样本，该程序成功进行了分类

实验二 感知器算法

一、实验内容

1. 熟悉感知器算法，并能够用程序写出。

2. 利用感知器算法进行判别分类，算出判别函数，画出判别界面。

二、实验原理

直接用来对模式进行分类的准则函数。若分属于ω1，ω2的两类模式可用一方程0)(=X d 来划分，那么称)(X d 为判别函数，或称判决函数、决策函数。如，一个二维的两类判别问题，模式分布如图示，这些分属于ω1，ω2两类的模式可用一直线方程0)(=X d 来划分。其中0)(32211=++=w x w x w d X 式中： 21,x x 为坐标变量。

图2-1 两类二维模式的分布

将某一未知模式 X 代入：

32211)(w x w x w d ++=X

若0)(>X d ，则1ω∈X 类；

2x 1x

若0)(

若0)(=X d ，则21ωω∈∈X X 或或拒绝。

两类线性可分的模式类 21,ωω，设X W X d T )(=其中，

[]T 121,,,,+=n n w w w w W ，[]T

211,,,,n x x x =X 应具有性质

??

?∈<∈>=2

1

,0,0)(ωωX X X W X T d 对样本进行规范化处理，即ω2类样本全部乘以(－1)，则有：

0)(T >=X W X d

感知器算法通过对已知类别的训练样本集的学习，寻找一个满足上式的权向量。

感知器算法步骤：

（1）选择N 个分属于ω1和 ω2类的模式样本构成训练样本集

{}N X X X ， 21,构成增广向量形式，并进行规范化处理。任取权向量初始值W(1)，

开始迭代。迭代次数k=1。

（2）用全部训练样本进行一轮迭代，计算()i k X W 的值，并修正权向量。 分两种情况，更新权向量的值：

1. ()，若0≤T i k X W 分类器对第i 个模式做了错误分类，权向量校正为：

()()i c k k X W W +=+1

c ：正的校正增量。

2. 若()0T >i k X W 分类正确，权向量不变：()()k k W W =+1,统一写为：

?????<+>=+0

)(,)(0

)(),()1(k T

k k T

k c k k k k X W X W X W W W （3）分析分类结果：只要有一个错误分类，回到（2），直至对所有样本正确分类。

感知器算法是一种赏罚过程：

分类正确时，对权向量“赏”——这里用“不罚”，即权向量不变；

分类错误时，对权向量“罚”——对其修改，向正确的方向转换。

三、实验结果与分析

已知两类训练样本为：

T

T

T

T

T

T

T

T

)1,1,1(,

)0,1,0(,

)1,1,0(,

)1,0,0(

:

)0,1,1(,

)1,0,1(,

)0,0,1(,

)0,0,0(

:

2

1

ω

ω

设T)0,2

,2

,1

(

)1(-

-

-

=

W，同样地，利用matlab元胞数组存储该两类训练样本

利用感知器算法，matlab运行得到如下结果：

因此，可以得到感知器算法算出的判别函数为：

1

3

2

3

)

(

3

2

1

+

-

-

=x

x

x

X

d

利用matlab的画图函数画出判别界面以及样本点，得到如下的分布图：由样本分布图可以看出，判别界面成功将两类训练样本分离。