一种新的基于距离的感知器算法

ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用２００８，４４（２４）６５

一种新的基于距离的感知器算法

邬长安，王新霞，李国梁

ＷＵＣｈａｎｇ－ａｎ，ＷＡＮＧＸｉｎ－ｘｉａ，ＬＩＧｕｏ－ｌｉａｎｇ

信阳师范学院计算机科学与技术系，河南信阳４６４０００

ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｔｅｒ，ＸｉｎｙａｎｇＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｘｉｎｙａｎｇ，Ｈｅｎａｎ４６４０００，ＣｈｉｎａＥ－ｍａｉｌ：ｗｘｘ＠ｍａｉｌ２．ｘｙｔｃ．ｅｄｕ．ｃｎ

ＷＵＣｈａｎｇ－ａｎ，ＷＡＮＧＸｉｎ－ｘｉａ，ＬＩＧｕｏ－ｌｉａｎｇ．Ｎｅｗｐｅｒｃｅｐｔｉｏｎａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｄｉｓｔａｎｃｅ．ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄ

（２４）：６５－６６．Ａｐｐｌｉｃａｔｉｏｎｓ，２００８，４４

Ａｂｓｔｒａｃｔ：ＴｈｉｓｐａｐｅｒｐｒｅｓｅｎｔｓａｎｅｗａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｔｈｅＳｈｏｒｔｅｓｔＤｉｓｔａｎｃｅｏｆｐｅｒｃｅｐｔｉｏｎ，ａｎｄｐｕｔｓｆｏｒｗａｒｄｔｈｅｐｒｏｃｅｓｓｂｙ

ａｎａｌｙｚｉｎｇｔｈｅｒｅｌａｔｉｏｎｂｅｔｗｅｅｎｓｏｌｕｂｌｅｖｅｃｔｏｒａｎｄｎｏｒｍａｌｖｅｃｔｏｒ．Ｓｉｍｕｌｔａｎｅｏｕｓｌｙ，ｉｔｃｏｍｐａｒｅｓｔｈｅｎｅｗａｌｇｏｒｉｔｈｍｐｒｏｖｅｄｂｙｅｘａｍｐｌｅｓｗｉｔｈｔｈｅＬＭＳＥａｎｄｔｈｅｌｅａｒｎｉｎｇａｌｇｏｒｉｔｈｍｏｆｖａｒｉａｂｌｅｐａｃｅｓ．Ｃｏｎｓｅｑｕｅｎｔｌｙ，ｏｎｌｉｎｅａｒｉｔｙｓｅｐａｒａｂｌｅ，ｉｔｓｈｏｗｓｔｈａｔｔｈｅｎｅｗａｌｇｏｒｉｔｈｍＳＤＡｃａｎｓｏｌｖｅｃｏｎｖｅｒｇｅｎｃｅｉｎａｌｌｔｈｅｔｒａｄｉｔｉｏｎｓａｎｄｅｎｈａｎｃｅｔｈｅｓｐｅｅｄｏｆｃａｌｃｕｌａｔｉｏｎ．

Ｋｅｙｗｏｒｄｓ：ｔｈｅｐｅｒｃｅｐｔｉｏｎａｐｐｒｏａｃｈ；ｓｏｌｕｂｌｅｖｅｃｔｏｒ；ｎｏｒｍａｌｖｅｃｔｏｒ；ｔｈｅｌｉｍｉｔｅｄｓｑｕａｒｅｅｒｒｏｒ；ｔｈｅｌｅａｒｎｉｎｇａｌｇｏｒｉｔｈｍｏｆｐｅｒｃｅｐｔｉｏｎｗｉｔｈｖａｒｉａｂｌｅｐａｃｅｓ

摘

要：分析了模式空间中解向量和法向量的关系，提出了一种新的基于最短距离的感知器算法。并对该算法和最小平方误差法

以及变步长学习法进行了分析和比较。结果表明，在线性可分的前提下，该算法有效解决了收敛性的问题，提高了计算速度。关键词：感知器；解向量；法向量；最小平方误差法；变步长学习法

ＤＯＩ：１０．３７７８／ｊ．ｉｓｓｎ．１００２－８３３１．２００８．２４．０１８文章编号：１００２－８３３１（２００８）２４－００６５－０２文献标识码：Ａ中图分类号：ＴＰ３０１．６

１引言

感知器是一类重要的分类学习机模型［１－２］，在模式识别、聚

对ｙｉ∈Ｒ２取－ｙｉ，令

（ｘ１，ｘ２，…，ｘｎ，１）Ｔ!ｙｉ∈Ｒ１ｙｉ＝

（２）ｙｉ′＝

（－ｘ１，－ｘ２，…，－ｘｎ，－１）Ｔ!ｙｉ∈Ｒ２－ｙｉ＝

称为ｙｉ的规范化增广向量，且对所有ｙｉ（ｙｉ′′ｉ＝１，２，…，Ｎ），有

（３）!Ｔｙｉ′＞０ｉ＝１，２，…，Ｎ

为描述方便，记ｙｉ$ｙｉ′。

类分析等领域中有着重要应用。感知器算法（ｔｈｅｐｅｒｃｅｐｔｉｏｎ“学习”，从而得出分类判ａｐｐｒｏａｃｈ）是通过对训练模式样本的

该算法的优点是不需要对各类训练模式样本的统计性别函数。

质作任何假设，属于一种确定性分类方法。但固定增量法、最小平方误差法（ＬＭＳＥ）和２００１年邢进生等人提出的变步长的快速学习法（以下记为：ＦＬＡ）［３］，都不能避免收敛性问题（是否收敛、收敛速度的快慢）的困扰。本文提出的基于样本距离的感知器算法避免了上述问题。在模式可分的前提下，该算法能很快地找到满足条件的一簇解向量，并在国家自然科学基金项目的研究中得到具体《多菌株传染病动力学的数学建模与研究》应用。

#

２．２解向量和解区域

在线性可分情况下，满足!Ｔｙｉ＞０，ｉ＝１，２，…，Ｎ的权向量!称为解向量［４］，记为!＊。权向量!为权空间中的一点，每个样本

ｙｉ对!的可能位置都起到限制作用，就是要求!Ｔｙｉ＞０。方程"ｎ，其法向量为!Ｔｙｉ＝０，确定了一个通过权空间原点的超平面Ｈ

ｙｉ。线性函数如果存在，则必平行于法向量ｙｉ，或者就是ｙｉ。

"ｎ的正侧，因为只有在正侧才解向量如果存在，则一定在Ｈ

能满足!Ｔｙｉ＞０。Ｎ个样本将产生Ｎ个超平面，每个超平面把权空间分为两个半空间［５］。所以，解向量如果存在，必在Ｎ个正半空间的交迭区，而且该区中的任意向量都是解向量!＊。可见解向量往往不只一个，而是由无穷多个解向量组成的区域，则称该区域为解区域。对于二维问题，其解区域如图１所示，其中图（ａ）是未规范化样本，图１（ｂ）是规范化样本。１

２基于距离的感知器算法

２．１样本的规范化

设ｎ维样本集｛ｙ１，ｙ２，…，ｙＮ｝是线性可分的，并分为两类Ｒ１

和Ｒ２，ｙｉ＝（ｘ１，ｘ２，…，ｘｎ）Ｔ的增广向量为（ｘ１，ｘ２，…，ｘｎ，１）Ｔ，则存在权向量!＝（ｗ１，ｗ２，…，ｗｎ，ｗｎ＋１）Ｔ，使得

#!ｙ＜０

!Ｔｙｉ＞０

Ｔｉ

!ｙｉ∈Ｒ１!ｙｉ∈Ｒ２

（１）

２．３对解区域的限制

如果将式（３）中的阈值０改为一非负值!，则变为更一般

基金项目：国家自然科学基金（ｔｈｅＮａｔｉｏｎａｌＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＣｈｉｎａｕｎｄｅｒＧｒａｎｔＮｏ．１０６７１１６６）。

作者简介：邬长安（１９５９－），男，副教授，中国计算机学会会员（Ｅ２０－０００８２３１Ｓ），硕士生导师，主要研究方向：数字图像处理，模式识别。收稿日期：２００７－１０－２３

修回日期：２００８－０２－２７

向量形式，需要求!的第ｎ＋１维，即ｗｎ＋１，记ｃ’ｗｎ＋１。

步骤３求解向量!＊。根据式（３），对于任意样本ｙｉ∈Ｒ１，都

(

)))))))))))))*

ｙｉ１ｙｉ２

满足（ｗ１，ｗ２，…，ｗｎ，ｃ）…＞０，即得：

ｙｉｎ

１

（－（ｗ１ｙｉ１＋ｗ２ｙｉ２＋…＋ｗｎｙｉｎ））’ρｃ＞ｍａｘ１

(

)))))))))))))*

+,,,,,,,,,,,,,-

（５）

ｙｊ１ｙｊ２ｙｊｎ－１

同理，对于任意样本ｙｊ∈Ｒ２，都满足（ｗ１，ｗ２，…，ｗｎ，ｃ）…＞０，

化的表示式：

!Ｔｙｉ≥!ｉ＝１，２，…，Ｎ

对解区域加以限制的目的是使解向量!更可靠

＊

［４，５］

（４）

通常认为，。

+

,,,,,,,,,,,,,-

即得：

（ｗ１ｙｊ１＋ｗ２ｙｊ２＋…＋ｗｎｙｊｎ）’ρ（６）ｃ＜ｍｉｎ２

由式式（５）、（６）可得：

（ｗ１ｙｊ１＋ｗ２ｙｊ２＋…＋ｗｎｙｊｎ）＞ｃ＞ｍａｘ（－（ｗ１ｙｉ１＋ｗ２ｙｉ２＋…＋ｗｎｙｉｎ））（７）ｍｉｎ

求得ｃ为一开区间，即通过满足此区间的ｃ值所表示的!都是权向量，得到一簇解向量。取满足式（７）的ｃ为ｗｎ＋１。ｃ值的取值将 …… 此处隐藏：4613字，全部文档内容请下载后查看。喜欢就下载吧 ……