模式识别论文--结束版本

判别函数分类器的设计与实现

1 判别函数分类器

1.1 判别函数概念

直接用来对模式进行分类的准则函数。 若分属于ω1，ω2的两类模式可用一方程d(X) =0来划分，那么称d(X) 为判别函数，或称判决函数、决策函数。

如，一个二维的两类判别问题，模式分布如图示，这些分属于ω1，ω2两类的模式可用一直线方程 d(X)=0来划分。

d(X)w1x1w2x2w30 式中： x1,x2 为坐标变量。

x2x1

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

将某一未知模式 X 代入： d(X)w1x1w2x2w3 若d(X)0，则X1类； 若d(X)0，则X2类；

若d(X)0，则Xω1或Xω2或拒绝 维数=3时：判别边界为一平面。

1

维数>3时：判别边界为一超平面。

1.2 判别函数正负值的确定

判别界面的正负侧，是在训练判别函数的权值时确定的。

图1-2 判别函数正负的确定

d(X) 表示的是一种分类的标准，它可以是1、2、3维的，也可以是更高维的。

x1

1.3 确定判别函数的两个因素

1）判决函数d(X)的几何性质。它可以是线性的或非线性的函数，维数在特征提取时已经确定。

已知三维线性分类 —— 判决函数的性质就确定了判决函数的形式：

d(X)w1x1w2x2w3x3w4

非线性判决函数，其示意图如下图所示

2

x2

x

2

x1

x1

图1-3 非线性判决函数图示

2）判决函数d(X)的系数，由所给模式样本确定的。

2感知器算法设计与实现

对一种分类学习机模型的称呼，属于有关机器学习的仿生学领域中的问题，由于无法实现非线性分类而下马。但“赏罚概念（ reward-punishment concept）” 得到广泛应用。

2.1 感器算法原理及特点

2.1.1 感知器算法原理

T

两类线性可分的模式类 1,2，设d(X)WX其中，

TT

Ww1,w2,,wn,wn1，Xx1,x2,,xn,1应具有性质

0,若X1

d ( X )  W X  （2-1）

0,若X2

T

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

T

d(X)WX0 (2-2)

3

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

感知器算法步骤：

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

{ X1, …, XN }构成增广向量形式，并进行规范化处理。任取权向量初

始值W(1)，开始迭代。迭代次数k=1 。

（2）用全部训练样本进行一轮迭代，计算WT(k)Xi 的值，并修正权向量。

分两种情况，更新权向量的值：

1. 若WTkXi≤0， 分类器对第i个模式做了错误分类，权向量校正为：

Wk1WkcXi c：正的校正增量。

T

kXi0，W2.若分类正确，权向量不变：Wk1Wk,统一写为：

Wk,

Wk1

WkCXk,

WTkXk0

WTkXk0

(2-3)

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

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

分类正确时，对权向量“赏”——这里用“不罚”，即权向量不变； 分类错误时，对权向量“罚”——对其修改，向正确的方向转换。

2.1.2 感知算法特点--收敛性

收敛性：经过算法的有限次迭代运算后，求出了一个使所有样本都能正确分类的W，则称算法是收敛的。感知器算法是在模式类别线性可分条件下才是收敛的。

4

2.1.3 感知器算法用于多类情况

采用多类情况3的方法时，应有：

若Xi，则di(X)djX,ji, j1,,M 对于M类模式应存在M个判决函数： 算法主要内容：

设有M中模式类别：1,2,,M设其权向量初值为：Wj1,

di,

i1,,M,,,,,

j1,,M训

练样本为增广向量形式，但不需要规范化处理。第K次迭代时，一个属于ωi 类的模式样本X被送入分类器，计算所有判别函数

djkWjTkX,分二种情况修改权向量：

j1,,M

(2-4)

① 若dikdjk,ji;j1,2,,M，则权向量不变；

Wjk1Wjk,

j1,2,,M

② 若第L个权向量使dik≤dlk，则相应的权向量作调整，即：

Wik1WikcX



Wlk1WlkcX (2-5) Wk1Wk,ji,l

jj

c为正的校正增量

只要模式类在情况3判别函数时是可分的，则经过有限次迭代后算法收敛。

2.2 实例说明

为了说明感知器算法的具体实现，下面举出实例加以说明： 已知两类训练样本

1:X10,0TX20,1T

2:X31,0TX41,1T

用感知器算法求出将模式分为两类的权向量解和判别函数。

解：所有样本写成增广向量形式；进行规范化处理，属于ω2的样本乘以(－

5

1)。

X10,0,1T X20,1,1T X31,0,1 X41,1,1T

T

任取W(1)=0，取c=1，迭代过程为： 第一轮：

00,WT(1)X10,0,000,101,WT(2)X20,0,110,1-1

-1,WT(3)X30,0,100,-1-1

1,WT(4)X4-1,0,0-10,-1

T

故W(2)W(1)X10,0,1

T

故W(3)W(2)0,0,1

T

故W(4)W(3)X3-1,0,0

T

故W(5)W(4)-1,0,0

有两个WT(k)Xi ≤0的情况（错判），进行第二轮迭代。 第二轮：

TWT(5)X100,故W(6)W(5)X1-1,0,1 T

WT(6)X210,故W(7)W(6)-1,0,1

T

WT(7)X300,故W(8)W(7)X3-2,0,0 T

WT(8)X420,故W(9)W(8)-2,0,0

第三轮：

T

WT(9)X100,故W(10)W(9)X1-2,0,1

WT(10)X210,故W(11)W(10) WT(11)X310,故W(12)W(11)

WT(12)X410,故W(13)W(12) 第四轮：

WT(13)X110,故W(14)W(13)

6

WT(14)X210,故W(15)W(14) WT(15)X310,故W(16)W(15)

WT(16)X410,故W(17)W(16)

该轮迭代的分类结果全部正确，故解向量W2,0,1T 相应的判别函数为：d(X)2x11

X10,0

xX20,13x1

图2-1 判决函数示意图 判别界面d(X)=0如图示。当c、W(1)取其他值时，结果可能不一样，所以感知器算法的解不是单值的。

2.3 matlab的感知器算法设计与实现

本设计是按照线性函数判决函数的感知算法思想结合数字识别，来进行设计，通过训练数字样本（每个数字样本都大于120），结合个人写字习惯，记录测试结果，最后通过matlab编码来实现感知器的数字识别。

2.3.1 Matlab代码设计

function y=jiangcheng(sample) clc;

load templet pattern;

7

w=zeros(26,10); d=[];

maxpos=0; maxval=0; f=1;

n=[];m=[];

%依次输入样本 for j=1:100 for i=1:10 f=1;

pattern(i).feature(26,j)=1; for k=1:10

m=pattern(i).feature(:,j); d(k)=w(:,k)*m; end

%判断是否为最大值，如果是，f=1，否则f=0； for=1:10 if k=i

if d(i)

%修正权值 if f

for k=1:10 if k==i

w(:,k)=w(:,k)+pattern(i).feature(:,j); else

w(:,k)=w(:,k)-pattern(i).feature(:,j); end end end end end

sample(26)=1; h=[];

%计算各类别的判别函数 for k=1:10

h(k)=w(:k)'*sample'; end

[maxval,maxpos]=max(h); y=maxpos-1;

8

2.3.2 matlab实现

首先通过，手写输入0-9个数字的训练样例各130个，如下图所示：

图2-2 数字训练样品

训练样本准备好后，进行数字识别测试,其测验如下：

图2-3 数字测验结果正确样例

图2-4 数字测试不正确样例

9

2.3.3 设计结果分析

通过多次手写验证测试，有65%通过，其结果如节显示，由于模式识别的算法复杂，步骤较多，实现起来有一定的难度。为了使样品库少一些，将精力着重放在算法的理解及编程实现上，此次设计用的是6x6的设计模板，这个比较小，其对测试结果的正确性起着确定性的作用。故增大设计模板以及提高算法的精确度可以使计算更为准确。

3 增量校正算法设计与实现

3.1 增量校正算法原理

增量校正算法采用绝对偏差的平均值为最小的原则，这时准则函数取为

J(Wi,X)E{|ri(x)WiTX|} （3-1）

式中

ri(x)

上式对Wi进行偏微分，可得



1,XWi

0,XWi

（3-2）

J

E{Xsgn[ri(X)WiTX]} Wi

（3-3）

式中

sgn[ri(X)WiX]

由于

T



1,ri(X)WiTX1,ri(X)WiTX

（3-4）

f(Wi,X)

Xsgnri[(X)WiTX]

Wi

（3-5）

因而算法方程为

Wi(k1)Wi(k)kX(k)sgn{ri[X(k)]WiT(k)X(k)]}（3-6）

10

Wi的初值W(1)是可以任意选取的，上式也可以写成

Wi(k1)



Wi(k)kX(k),WiT(k)X(k)ri[X(k)]Wi(k)kX(k),WiT(k)X(k)ri[X(k)]

（3-7）

算法的每一步都要校正权向量。而感知器算法只在某一个模式样品被错误分类时才校正。由式（3-7）或式（5-40）看出，算法每一步得的校正值都正比于增量k，故称为增量校正算法。

对于多类问题来说，判别函数为

di(X)WiT(k) （3-8）

如果XWi，则di(X)WiT(k)ri[X]1而di(X)WiT(k)rj[X]0

3.2 实例说明

为了说明该算法的实现过程，这里举出如下例子，给定两类样品：

Tw1,0,0)T,(1,0,1)T,(1,1,0)T1:(0,0,0),(

w2:(0,0,1)T,(0,1,0)T,(0,1,1)T,(1,1,1)T

现在用增量校正算法计算判别函数。在进行迭代运算之前，各样品的特征向量经过增1：

w1)T,(1,0,0,1)T,(1,0,1,1)T,(1,1,0,1)T 1:(0,0,0,

w2:(0,0,1,1)T,(0,1,0,1)T,(0,1,1,1)T,(1,1,1,1)T 以W(1)=0，k=1/k进行讨论。

Ta) 令X(1)=(0,0,0,1)，

X(1)1,W(2)W(1)1X(1)sgn{r[X(1)]WT(1)X(1)}因为1=1，r[X(1)]=1和r[X(1)]> WT(1)X(1)

T

因而W(2)W(1)0(0,0,0,1) T

b) 令X(2)=(1,0,0,1)，

1

X(2)1,2,r[X(2)]1,W(3)W(2)2X(2)sgn{r[X(2)]WT(2)X(2)}

2因

11

为r[X(2)]WT(2)X(2)

111

因此 W(3)W(2)-(1,0,0,1)T(,0,0,)

222T

c) 令X(3)=(1,0,1,1)，

X(3)1,r[X(3)]1,W(4)W(3)2X(3)sgn{r[X(3)]WT(3)X(3)} 因为r[X(3)]WT(3)X(3)

1115

因此 W(4)W(3)(1,0,1,1)T(,0,,)T

3636

按照同样的步骤把一下的样品逐个输入。当输入样品Xw2时，ri[X(k)]0，以此确定函数sgn{r[X(k)]WT(k)X(k)的符号，由此决定修正量的方向。一直进1

行到第15步，即k=15, k，得到可以令人满意的结果，这时

15

T

W(16)(0.23,3 0.23,90.21,60.61)9因此判别方程为：

d(X)P(w|X)

11

WTX0.233x10.239x20.216x30.1190 22

3.3 实现步骤

① 设各个权矢量的初始值为0，即W0(0)W1(0)W2(0)W9(0)0。 ② 输入第k次样品X(k)，计算di(k)WiT(k)X(k)。 ③ 若X(k)wi,则ri[X(k)]1，否则ri[X(k)]0。 ④

W(k1)计算Wi(k1) ，i



其中，k1/k。

Wi(k)kX(k),WiT(k)X(k)ri[X(k)]Wi(k)kX(k),WiT(k)X(k)ri[X(k)]

⑤ 循环执行第二步，直到属于wi类的所有样品都满足条件：

di(X)dj(X),ji

12

3.4 matlab实现增量校正算法

增量校正判决器实现与感知器算法的验证平台是一样的，都是通过足够的数字样品训练，再通过增量校正算法来实现数字识别的测试。

3.4.1 matlab的增量校正算法设计

其matlab编码实现如下：

function y=zengliangjiaozheng(sample) clc;

load templet pattern; w=zeros(26,10); d=[];

maxpos=0; maxval=0; r=[]; flag=1; num1=0; num2=0; f=1;

n=[];m=[]; while flag flag=0;

num2=num2+1; forj=1:20 for i=1:10

num1=num1+1;

%初始化向量r，当前类别r(i)为1 r=[0 0 0 0 0 0 0 0 0 0]; r(i)=1; f=1;

pattern(i).feature(26,j)=1; for k=1:10

m=pattern(i).feature(:,j); d(k)=w(:,k)*m; end

%判断是否为最大值，不是则flag为1 for k=1:10 if k~=i

if d(i)

13

flag=1; end end end %修正权值

for k=1:10 if r(k)>d(k)

w(:,k)=w(:,k)+pattern(i).feature(:,j)/num1; else

w(:,k)=w(:,k)-pattern(i).feature(:,j)/num1; end end end end

if num2>400 flag=0; end end

sample(26)=1; h=[];

%计算判别函数

%计算各类别的判别函数 for k=1:10

h(k)=w(:k)'*sample'; end

[maxval,maxpos]=max(h); y=maxpos-1;

3.4.2 matlab设计的数字验证平台的实现

在测试之前需要足够的样本训练，以便建立足够信息的样品库，训练示意图如下：

14

图3-1 数字训练示意图

在随机测试中，有70%的数字测试是通过的，下面把测试过程中正确的与不正确的分别以图形的形式展现出来：

图3-2 测试通过样例

图3-3 未通过测试样例

15

3.4.3 设计结果分析

增量校正算法与感知器算法最大的不同是，其每一步都修改权值，而感知器只在发生错误的时候修改权值，相对算法更加复杂，但是准确度比感知器算法高。

16

模糊K-均值判决器设计与实现

1 模糊K值算法原理

模糊K-均值算法基本思想：首先设定一些类及每个样本对各类的隶属度；然后通过迭代，不断调整隶属度至收敛。

模糊K值算法实现的步骤如下：

(1) 确定模式类数K，1

(2) 根据先验知识确定样本从属于各类的隶属度ij0，

建立初始隶属度矩阵U0[ij0]， i为类别编号、矩阵的行号， j为样本编号、矩阵的列号。矩阵U(0)每列元素之和等于1。

X1



U0

X2X3X4

0.90.80.70.11

 

0.10.20.30.92 （1-1）

(3) 求各类的聚类中心ZiL，L为迭代次数。

ZiL

[L]

ij

j1N

ij

j1

N

m

Xj

i1,2,,K;

m2

（1-2）

[L]

i1

m

mX1mX2mX3

例如，3个样本时：Zi mmm



i2

i3

i1

i2

i3

可以看出：各聚类中心的计算必须用到全部的N个样本，这是与一般K-均值算法的区别之一。

(4) 计算新的隶属度矩阵U(L+1)，矩阵元素计算如下：

ijL1

1

(

p1

K

ijdpj

)m1

（1-3）

i1,2,,K,j1,2,,N,m2

17

式中，dij是第L次迭代完成时，第j个样本到第i类聚类中心ZiL的距离。 例当有两个聚类中心时，样本j对两个类别隶属度的计算：

1j

(

1

1jd1j

)m1(

1jd2j

)m1

2j

(

1

2jd1j

)m1(

2jd2j

)2m1

（1-4）

可见：dij越大，ijL1越小。

ijL1

1K

(ij)2m1

p1dpj

为避免分母为零，特规定：

若dij0，则ijL11,pjL10pi (5) 回到(3)求聚类中心，重复至收敛。收敛条件：

maxi,j

ijL1ijL

， 为规定的参数。

(6) 根据隶属度矩阵U(L+1)进行聚类： 若 ijL11maxpK

pjL10,

j1,2,,N

则 Xji类。 X1

X2X3X4

如： U00.90.80.70.11

0.10.20.30.9



22 实例说明

设有4个二维样本，分别是

XT

10,0，X20,1T

X3,1T

3，X43,2T

利用模糊K-均值算法把它们聚为两类。 解：（1）根据要求N=4，K=2。

（2）根据先验知识确定初始隶属度矩阵：

18

1-5）

（

X1X2X3X4

0.90.80.70.11

U00.10.20.30.9 

2由U(0)可知，倾向于X1、X2、X3为一类，X4为一类。

N

ZiL

[L]

ij

j1

N

ij

j1

m

Xj

m

[L]

X1X2X3X4 0.90.80.70.11

U00.10.20.30.9 

2

其中 ：

X10,0

T

X20,1

T

T

X33,1 T

X43,2

(3) 计算聚类中心Z10、Z20，取m=2，有

0202323Z10(0.90.80.70.1) 0112

0.77

(0.920.820.720.12)0.59

0033

Z20(0.120.220.320.92)

0112

2

2.84(0.10.20.30.9) 1.84

2

2

2

2

ijL1其中：

2.840.77

Z0Z01.84 1K0.592ijm1

()p1dpj

1

X10,0

T

X20,1

T

T

X33,1

19

T

X43,2

(4) 计算新的隶属度矩阵U(1)。取m=2，分别计算ij(1)。

2

如对X3有： d13(30.77)2(10.59)25.14 2 d23(32.84)2(11.84)20.73

11

0.12 得 131d13d13

2

2

5.140.73d13d23

231

1

d23d23

22d13d23

(

1)5.140.73

0.88

类似地，可得到U(1)中其它元素，有 X1

X2X3X4

0.920.920.120.011

U1ij(1)0.080.080.880.99

2

若满足收敛条件 maxijL1ijL

i,j

，则迭代结束，

否则返回(3)计算聚类中心。

假设此时满足收敛条件，迭代结束，则根据U(1)进行聚类。

11(1)21(1)，12(1)22(1)，X11,X21 23(1)13(1)，24(1)14(1)，X32,X42

3 matlab的模糊K-均值设计与实现

本代码设计用随机函数randn与矩阵乘法函数结合一起产生4组3列的矩阵数据样品，作为模糊K均值分类的对象，再设计simple_kmeans函数实现K均值算法功能，即整个设计分两大步：第一步，产生分类的对象数据—matlab测试；第二步，模糊K均值算法的实现—对应matlab代码设计。

20

3.1 matlab代码设计

function [means,Nmeans] = simple_kmeans(X,K,maxerr)

[Ndata, dims] = size(X);

dist = zeros(1,K);

% Initial prototype assignment (arbitrary)

for i=1:K-1

means(i,:) = X(i,:);

end

means(K,:) = mean(X(K:Ndata,:));

cmp = 1 + maxerr;

while (cmp > maxerr)

% Sums (class) and data counters (Nclass) initialization

class = zeros(K,dims);

Nclass = zeros(K,1);

% Groups each elements to the nearest prototype

for i=1:Ndata

for j=1:K

% Euclidean distance from data to each prototype

dist(j) = norm(X(i,:)-means(j,:))^2;

end

% Find indices of minimum distance

index_min = find(~(dist-min(dist)));

% If there are multiple min distances, decide randomly

index_min = index_min(ceil(length(index_min)*rand));

class(index_min,:) = class(index_min,:) + X(i,:);

Nclass(index_min) = Nclass(index_min) + 1;

end

for i=1:K

class(i,:) = class(i,:) / Nclass(i);

end

% Compare results with previous iteration

cmp = 0;

for i=1:K

cmp = norm(class(i,:)-means(i,:));

end

% Prototype update

means = class;

end

Nmeans = Nclass;

21

3.2 matlab测试

K = 4;

dim = 3;

variance = 1;

sdev = sqrt(variance);

cluster1 = sdev*randn(200,dim) + kron(ones(200,1),[0,0,0]); cluster2 = sdev*randn(300,dim) + kron(ones(300,1),[0,0,6]); cluster3 = sdev*randn(100,dim) + kron(ones(100,1),[0,6,0]); cluster4 = sdev*randn(500,dim) + kron(ones(500,1),[6,0,0]);

% Build data matrix

X = [cluster1 ; cluster2 ; cluster3; cluster4];

% Now apply K-means algorithm

% Note that order of results may vary

maxerr = 0;

[proto Nproto] = simple_kmeans(X,K,maxerr)

1.测试结果一：

proto =

0.0561 5.9792 0.0470

0.0470 -0.0258 -0.0329

0.0071 -0.0466 5.9565

6.0519 0.0082 -0.0012

Nproto =

101

199

300

500

2.测试结果二：

proto =

-0.1291 0.0759 6.0721

6.0445 0.0336 0.0418

-0.0271 6.0249 -0.0105

0.0068 -0.0923 0.0234

Nproto =

300

501

100

199

22

3.3 结果分析

在这里只展现了算法实现测试的两组结果，因为测试样本是在[0 0 0],[0 0 6],[0 6 0],[6 0 0]四组数据上加上随机噪声，最后通过K均值算法出来的分组都比较平均，跟各个数基样例个数：100,200,300,500基本相差一个，不足1%的误差，所以模糊K均值算法的精确度比较高。

可以看出基于模糊K_均值算法的模糊分类器主要优点是：(1)简单；(2)结构系统化；(3)在聚类过程中，基于模糊K均值的聚类算法能预处理训练数据。以至于训练数据能够保证 100％地被模糊分类器分类；它还具有很好的通用性。

23

判别函数分类器的设计与实现

1 判别函数分类器

1.1 判别函数概念

直接用来对模式进行分类的准则函数。 若分属于ω1，ω2的两类模式可用一方程d(X) =0来划分，那么称d(X) 为判别函数，或称判决函数、决策函数。

如，一个二维的两类判别问题，模式分布如图示，这些分属于ω1，ω2两类的模式可用一直线方程 d(X)=0来划分。

d(X)w1x1w2x2w30 式中： x1,x2 为坐标变量。

x2x1

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

将某一未知模式 X 代入： d(X)w1x1w2x2w3 若d(X)0，则X1类； 若d(X)0，则X2类；

若d(X)0，则Xω1或Xω2或拒绝 维数=3时：判别边界为一平面。

1

维数>3时：判别边界为一超平面。

1.2 判别函数正负值的确定

判别界面的正负侧，是在训练判别函数的权值时确定的。

图1-2 判别函数正负的确定

d(X) 表示的是一种分类的标准，它可以是1、2、3维的，也可以是更高维的。

x1

1.3 确定判别函数的两个因素

1）判决函数d(X)的几何性质。它可以是线性的或非线性的函数，维数在特征提取时已经确定。

已知三维线性分类 —— 判决函数的性质就确定了判决函数的形式：

d(X)w1x1w2x2w3x3w4

非线性判决函数，其示意图如下图所示

2

x2

x

2

x1

x1

图1-3 非线性判决函数图示

2）判决函数d(X)的系数，由所给模式样本确定的。

2感知器算法设计与实现

对一种分类学习机模型的称呼，属于有关机器学习的仿生学领域中的问题，由于无法实现非线性分类而下马。但“赏罚概念（ reward-punishment concept）” 得到广泛应用。

2.1 感器算法原理及特点

2.1.1 感知器算法原理

T

两类线性可分的模式类 1,2，设d(X)WX其中，

TT

Ww1,w2,,wn,wn1，Xx1,x2,,xn,1应具有性质

0,若X1

d ( X )  W X  （2-1）

0,若X2

T

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

T

d(X)WX0 (2-2)

3

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

感知器算法步骤：

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

{ X1, …, XN }构成增广向量形式，并进行规范化处理。任取权向量初

始值W(1)，开始迭代。迭代次数k=1 。

（2）用全部训练样本进行一轮迭代，计算WT(k)Xi 的值，并修正权向量。

分两种情况，更新权向量的值：

1. 若WTkXi≤0， 分类器对第i个模式做了错误分类，权向量校正为：

Wk1WkcXi c：正的校正增量。

T

kXi0，W2.若分类正确，权向量不变：Wk1Wk,统一写为：

Wk,

Wk1

WkCXk,

WTkXk0

WTkXk0

(2-3)

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

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

分类正确时，对权向量“赏”——这里用“不罚”，即权向量不变； 分类错误时，对权向量“罚”——对其修改，向正确的方向转换。

2.1.2 感知算法特点--收敛性

收敛性：经过算法的有限次迭代运算后，求出了一个使所有样本都能正确分类的W，则称算法是收敛的。感知器算法是在模式类别线性可分条件下才是收敛的。

4

2.1.3 感知器算法用于多类情况

采用多类情况3的方法时，应有：

若Xi，则di(X)djX,ji, j1,,M 对于M类模式应存在M个判决函数： 算法主要内容：

设有M中模式类别：1,2,,M设其权向量初值为：Wj1,

di,

i1,,M,,,,,

j1,,M训

练样本为增广向量形式，但不需要规范化处理。第K次迭代时，一个属于ωi 类的模式样本X被送入分类器，计算所有判别函数

djkWjTkX,分二种情况修改权向量：

j1,,M

(2-4)

① 若dikdjk,ji;j1,2,,M，则权向量不变；

Wjk1Wjk,

j1,2,,M

② 若第L个权向量使dik≤dlk，则相应的权向量作调整，即：

Wik1WikcX



Wlk1WlkcX (2-5) Wk1Wk,ji,l

jj

c为正的校正增量

只要模式类在情况3判别函数时是可分的，则经过有限次迭代后算法收敛。

2.2 实例说明

为了说明感知器算法的具体实现，下面举出实例加以说明： 已知两类训练样本

1:X10,0TX20,1T

2:X31,0TX41,1T

用感知器算法求出将模式分为两类的权向量解和判别函数。

解：所有样本写成增广向量形式；进行规范化处理，属于ω2的样本乘以(－

5

1)。

X10,0,1T X20,1,1T X31,0,1 X41,1,1T

T

任取W(1)=0，取c=1，迭代过程为： 第一轮：

00,WT(1)X10,0,000,101,WT(2)X20,0,110,1-1

-1,WT(3)X30,0,100,-1-1

1,WT(4)X4-1,0,0-10,-1

T

故W(2)W(1)X10,0,1

T

故W(3)W(2)0,0,1

T

故W(4)W(3)X3-1,0,0

T

故W(5)W(4)-1,0,0

有两个WT(k)Xi ≤0的情况（错判），进行第二轮迭代。 第二轮：

TWT(5)X100,故W(6)W(5)X1-1,0,1 T

WT(6)X210,故W(7)W(6)-1,0,1

T

WT(7)X300,故W(8)W(7)X3-2,0,0 T

WT(8)X420,故W(9)W(8)-2,0,0

第三轮：

T

WT(9)X100,故W(10)W(9)X1-2,0,1

WT(10)X210,故W(11)W(10) WT(11)X310,故W(12)W(11)

WT(12)X410,故W(13)W(12) 第四轮：

WT(13)X110,故W(14)W(13)

6

WT(14)X210,故W(15)W(14) WT(15)X310,故W(16)W(15)

WT(16)X410,故W(17)W(16)

该轮迭代的分类结果全部正确，故解向量W2,0,1T 相应的判别函数为：d(X)2x11

X10,0

xX20,13x1

图2-1 判决函数示意图 判别界面d(X)=0如图示。当c、W(1)取其他值时，结果可能不一样，所以感知器算法的解不是单值的。

2.3 matlab的感知器算法设计与实现

本设计是按照线性函数判决函数的感知算法思想结合数字识别，来进行设计，通过训练数字样本（每个数字样本都大于120），结合个人写字习惯，记录测试结果，最后通过matlab编码来实现感知器的数字识别。

2.3.1 Matlab代码设计

function y=jiangcheng(sample) clc;

load templet pattern;

7

w=zeros(26,10); d=[];

maxpos=0; maxval=0; f=1;

n=[];m=[];

%依次输入样本 for j=1:100 for i=1:10 f=1;

pattern(i).feature(26,j)=1; for k=1:10

m=pattern(i).feature(:,j); d(k)=w(:,k)*m; end

%判断是否为最大值，如果是，f=1，否则f=0； for=1:10 if k=i

if d(i)

%修正权值 if f

for k=1:10 if k==i

w(:,k)=w(:,k)+pattern(i).feature(:,j); else

w(:,k)=w(:,k)-pattern(i).feature(:,j); end end end end end

sample(26)=1; h=[];

%计算各类别的判别函数 for k=1:10

h(k)=w(:k)'*sample'; end

[maxval,maxpos]=max(h); y=maxpos-1;

8

2.3.2 matlab实现

首先通过，手写输入0-9个数字的训练样例各130个，如下图所示：

图2-2 数字训练样品

训练样本准备好后，进行数字识别测试,其测验如下：

图2-3 数字测验结果正确样例

图2-4 数字测试不正确样例

9

2.3.3 设计结果分析

通过多次手写验证测试，有65%通过，其结果如节显示，由于模式识别的算法复杂，步骤较多，实现起来有一定的难度。为了使样品库少一些，将精力着重放在算法的理解及编程实现上，此次设计用的是6x6的设计模板，这个比较小，其对测试结果的正确性起着确定性的作用。故增大设计模板以及提高算法的精确度可以使计算更为准确。

3 增量校正算法设计与实现

3.1 增量校正算法原理

增量校正算法采用绝对偏差的平均值为最小的原则，这时准则函数取为

J(Wi,X)E{|ri(x)WiTX|} （3-1）

式中

ri(x)

上式对Wi进行偏微分，可得



1,XWi

0,XWi

（3-2）

J

E{Xsgn[ri(X)WiTX]} Wi

（3-3）

式中

sgn[ri(X)WiX]

由于

T



1,ri(X)WiTX1,ri(X)WiTX

（3-4）

f(Wi,X)

Xsgnri[(X)WiTX]

Wi

（3-5）

因而算法方程为

Wi(k1)Wi(k)kX(k)sgn{ri[X(k)]WiT(k)X(k)]}（3-6）

10

Wi的初值W(1)是可以任意选取的，上式也可以写成

Wi(k1)



Wi(k)kX(k),WiT(k)X(k)ri[X(k)]Wi(k)kX(k),WiT(k)X(k)ri[X(k)]

（3-7）

算法的每一步都要校正权向量。而感知器算法只在某一个模式样品被错误分类时才校正。由式（3-7）或式（5-40）看出，算法每一步得的校正值都正比于增量k，故称为增量校正算法。

对于多类问题来说，判别函数为

di(X)WiT(k) （3-8）

如果XWi，则di(X)WiT(k)ri[X]1而di(X)WiT(k)rj[X]0

3.2 实例说明

为了说明该算法的实现过程，这里举出如下例子，给定两类样品：

Tw1,0,0)T,(1,0,1)T,(1,1,0)T1:(0,0,0),(

w2:(0,0,1)T,(0,1,0)T,(0,1,1)T,(1,1,1)T

现在用增量校正算法计算判别函数。在进行迭代运算之前，各样品的特征向量经过增1：

w1)T,(1,0,0,1)T,(1,0,1,1)T,(1,1,0,1)T 1:(0,0,0,

w2:(0,0,1,1)T,(0,1,0,1)T,(0,1,1,1)T,(1,1,1,1)T 以W(1)=0，k=1/k进行讨论。

Ta) 令X(1)=(0,0,0,1)，

X(1)1,W(2)W(1)1X(1)sgn{r[X(1)]WT(1)X(1)}因为1=1，r[X(1)]=1和r[X(1)]> WT(1)X(1)

T

因而W(2)W(1)0(0,0,0,1) T

b) 令X(2)=(1,0,0,1)，

1

X(2)1,2,r[X(2)]1,W(3)W(2)2X(2)sgn{r[X(2)]WT(2)X(2)}

2因

11

为r[X(2)]WT(2)X(2)

111

因此 W(3)W(2)-(1,0,0,1)T(,0,0,)

222T

c) 令X(3)=(1,0,1,1)，

X(3)1,r[X(3)]1,W(4)W(3)2X(3)sgn{r[X(3)]WT(3)X(3)} 因为r[X(3)]WT(3)X(3)

1115

因此 W(4)W(3)(1,0,1,1)T(,0,,)T

3636

按照同样的步骤把一下的样品逐个输入。当输入样品Xw2时，ri[X(k)]0，以此确定函数sgn{r[X(k)]WT(k)X(k)的符号，由此决定修正量的方向。一直进1

行到第15步，即k=15, k，得到可以令人满意的结果，这时

15

T

W(16)(0.23,3 0.23,90.21,60.61)9因此判别方程为：

d(X)P(w|X)

11

WTX0.233x10.239x20.216x30.1190 22

3.3 实现步骤

① 设各个权矢量的初始值为0，即W0(0)W1(0)W2(0)W9(0)0。 ② 输入第k次样品X(k)，计算di(k)WiT(k)X(k)。 ③ 若X(k)wi,则ri[X(k)]1，否则ri[X(k)]0。 ④

W(k1)计算Wi(k1) ，i



其中，k1/k。

Wi(k)kX(k),WiT(k)X(k)ri[X(k)]Wi(k)kX(k),WiT(k)X(k)ri[X(k)]

⑤ 循环执行第二步，直到属于wi类的所有样品都满足条件：

di(X)dj(X),ji

12

3.4 matlab实现增量校正算法

增量校正判决器实现与感知器算法的验证平台是一样的，都是通过足够的数字样品训练，再通过增量校正算法来实现数字识别的测试。

3.4.1 matlab的增量校正算法设计

其matlab编码实现如下：

function y=zengliangjiaozheng(sample) clc;

load templet pattern; w=zeros(26,10); d=[];

maxpos=0; maxval=0; r=[]; flag=1; num1=0; num2=0; f=1;

n=[];m=[]; while flag flag=0;

num2=num2+1; forj=1:20 for i=1:10

num1=num1+1;

%初始化向量r，当前类别r(i)为1 r=[0 0 0 0 0 0 0 0 0 0]; r(i)=1; f=1;

pattern(i).feature(26,j)=1; for k=1:10

m=pattern(i).feature(:,j); d(k)=w(:,k)*m; end

%判断是否为最大值，不是则flag为1 for k=1:10 if k~=i

if d(i)

13

flag=1; end end end %修正权值

for k=1:10 if r(k)>d(k)

w(:,k)=w(:,k)+pattern(i).feature(:,j)/num1; else

w(:,k)=w(:,k)-pattern(i).feature(:,j)/num1; end end end end

if num2>400 flag=0; end end

sample(26)=1; h=[];

%计算判别函数

%计算各类别的判别函数 for k=1:10

h(k)=w(:k)'*sample'; end

[maxval,maxpos]=max(h); y=maxpos-1;

3.4.2 matlab设计的数字验证平台的实现

在测试之前需要足够的样本训练，以便建立足够信息的样品库，训练示意图如下：

14

图3-1 数字训练示意图

在随机测试中，有70%的数字测试是通过的，下面把测试过程中正确的与不正确的分别以图形的形式展现出来：

图3-2 测试通过样例

图3-3 未通过测试样例

15

3.4.3 设计结果分析

增量校正算法与感知器算法最大的不同是，其每一步都修改权值，而感知器只在发生错误的时候修改权值，相对算法更加复杂，但是准确度比感知器算法高。

16

模糊K-均值判决器设计与实现

1 模糊K值算法原理

模糊K-均值算法基本思想：首先设定一些类及每个样本对各类的隶属度；然后通过迭代，不断调整隶属度至收敛。

模糊K值算法实现的步骤如下：

(1) 确定模式类数K，1

(2) 根据先验知识确定样本从属于各类的隶属度ij0，

建立初始隶属度矩阵U0[ij0]， i为类别编号、矩阵的行号， j为样本编号、矩阵的列号。矩阵U(0)每列元素之和等于1。

X1



U0

X2X3X4

0.90.80.70.11

 

0.10.20.30.92 （1-1）

(3) 求各类的聚类中心ZiL，L为迭代次数。

ZiL

[L]

ij

j1N

ij

j1

N

m

Xj

i1,2,,K;

m2

（1-2）

[L]

i1

m

mX1mX2mX3

例如，3个样本时：Zi mmm



i2

i3

i1

i2

i3

可以看出：各聚类中心的计算必须用到全部的N个样本，这是与一般K-均值算法的区别之一。

(4) 计算新的隶属度矩阵U(L+1)，矩阵元素计算如下：

ijL1

1

(

p1

K

ijdpj

)m1

（1-3）

i1,2,,K,j1,2,,N,m2

17

式中，dij是第L次迭代完成时，第j个样本到第i类聚类中心ZiL的距离。 例当有两个聚类中心时，样本j对两个类别隶属度的计算：

1j

(

1

1jd1j

)m1(

1jd2j

)m1

2j

(

1

2jd1j

)m1(

2jd2j

)2m1

（1-4）

可见：dij越大，ijL1越小。

ijL1

1K

(ij)2m1

p1dpj

为避免分母为零，特规定：

若dij0，则ijL11,pjL10pi (5) 回到(3)求聚类中心，重复至收敛。收敛条件：

maxi,j

ijL1ijL

， 为规定的参数。

(6) 根据隶属度矩阵U(L+1)进行聚类： 若 ijL11maxpK

pjL10,

j1,2,,N

则 Xji类。 X1

X2X3X4

如： U00.90.80.70.11

0.10.20.30.9



22 实例说明

设有4个二维样本，分别是

XT

10,0，X20,1T

X3,1T

3，X43,2T

利用模糊K-均值算法把它们聚为两类。 解：（1）根据要求N=4，K=2。

（2）根据先验知识确定初始隶属度矩阵：

18

1-5）

（

X1X2X3X4

0.90.80.70.11

U00.10.20.30.9 

2由U(0)可知，倾向于X1、X2、X3为一类，X4为一类。

N

ZiL

[L]

ij

j1

N

ij

j1

m

Xj

m

[L]

X1X2X3X4 0.90.80.70.11

U00.10.20.30.9 

2

其中 ：

X10,0

T

X20,1

T

T

X33,1 T

X43,2

(3) 计算聚类中心Z10、Z20，取m=2，有

0202323Z10(0.90.80.70.1) 0112

0.77

(0.920.820.720.12)0.59

0033

Z20(0.120.220.320.92)

0112

2

2.84(0.10.20.30.9) 1.84

2

2

2

2

ijL1其中：

2.840.77

Z0Z01.84 1K0.592ijm1

()p1dpj

1

X10,0

T

X20,1

T

T

X33,1

19

T

X43,2

(4) 计算新的隶属度矩阵U(1)。取m=2，分别计算ij(1)。

2

如对X3有： d13(30.77)2(10.59)25.14 2 d23(32.84)2(11.84)20.73

11

0.12 得 131d13d13

2

2

5.140.73d13d23

231

1

d23d23

22d13d23

(

1)5.140.73

0.88

类似地，可得到U(1)中其它元素，有 X1

X2X3X4

0.920.920.120.011

U1ij(1)0.080.080.880.99

2

若满足收敛条件 maxijL1ijL

i,j

，则迭代结束，

否则返回(3)计算聚类中心。

假设此时满足收敛条件，迭代结束，则根据U(1)进行聚类。

11(1)21(1)，12(1)22(1)，X11,X21 23(1)13(1)，24(1)14(1)，X32,X42

3 matlab的模糊K-均值设计与实现

本代码设计用随机函数randn与矩阵乘法函数结合一起产生4组3列的矩阵数据样品，作为模糊K均值分类的对象，再设计simple_kmeans函数实现K均值算法功能，即整个设计分两大步：第一步，产生分类的对象数据—matlab测试；第二步，模糊K均值算法的实现—对应matlab代码设计。

20

3.1 matlab代码设计

function [means,Nmeans] = simple_kmeans(X,K,maxerr)

[Ndata, dims] = size(X);

dist = zeros(1,K);

% Initial prototype assignment (arbitrary)

for i=1:K-1

means(i,:) = X(i,:);

end

means(K,:) = mean(X(K:Ndata,:));

cmp = 1 + maxerr;

while (cmp > maxerr)

% Sums (class) and data counters (Nclass) initialization

class = zeros(K,dims);

Nclass = zeros(K,1);

% Groups each elements to the nearest prototype

for i=1:Ndata

for j=1:K

% Euclidean distance from data to each prototype

dist(j) = norm(X(i,:)-means(j,:))^2;

end

% Find indices of minimum distance

index_min = find(~(dist-min(dist)));

% If there are multiple min distances, decide randomly

index_min = index_min(ceil(length(index_min)*rand));

class(index_min,:) = class(index_min,:) + X(i,:);

Nclass(index_min) = Nclass(index_min) + 1;

end

for i=1:K

class(i,:) = class(i,:) / Nclass(i);

end

% Compare results with previous iteration

cmp = 0;

for i=1:K

cmp = norm(class(i,:)-means(i,:));

end

% Prototype update

means = class;

end

Nmeans = Nclass;

21

3.2 matlab测试

K = 4;

dim = 3;

variance = 1;

sdev = sqrt(variance);

cluster1 = sdev*randn(200,dim) + kron(ones(200,1),[0,0,0]); cluster2 = sdev*randn(300,dim) + kron(ones(300,1),[0,0,6]); cluster3 = sdev*randn(100,dim) + kron(ones(100,1),[0,6,0]); cluster4 = sdev*randn(500,dim) + kron(ones(500,1),[6,0,0]);

% Build data matrix

X = [cluster1 ; cluster2 ; cluster3; cluster4];

% Now apply K-means algorithm

% Note that order of results may vary

maxerr = 0;

[proto Nproto] = simple_kmeans(X,K,maxerr)

1.测试结果一：

proto =

0.0561 5.9792 0.0470

0.0470 -0.0258 -0.0329

0.0071 -0.0466 5.9565

6.0519 0.0082 -0.0012

Nproto =

101

199

300

500

2.测试结果二：

proto =

-0.1291 0.0759 6.0721

6.0445 0.0336 0.0418

-0.0271 6.0249 -0.0105

0.0068 -0.0923 0.0234

Nproto =

300

501

100

199

22

3.3 结果分析

在这里只展现了算法实现测试的两组结果，因为测试样本是在[0 0 0],[0 0 6],[0 6 0],[6 0 0]四组数据上加上随机噪声，最后通过K均值算法出来的分组都比较平均，跟各个数基样例个数：100,200,300,500基本相差一个，不足1%的误差，所以模糊K均值算法的精确度比较高。

可以看出基于模糊K_均值算法的模糊分类器主要优点是：(1)简单；(2)结构系统化；(3)在聚类过程中，基于模糊K均值的聚类算法能预处理训练数据。以至于训练数据能够保证 100％地被模糊分类器分类；它还具有很好的通用性。

23