丁爱玲
(长安大学 西安710064)
摘 要 针对城市交通“智能运输系统”，提出了基于统计学习理论的交通流量时间序列预测，与传统统计学相比，统计学习理论能够在训练样本数很少的情况下达到很好分类推广能力。它具有收敛速度快，有效避免局部最小点的特点。对某一实际路口机动车流量的实验结果验证了该方法的有效性和先进性，有望在交通流量时间序列预测方面得到广泛的应用。 关键词 统计学习理论 支撑矢量机 时间序列预测 交通流量
Abstract:T h is paper pu ts fo rw ard the traffic flow ti m e series p rogno sticati on based on the statistical learn ing theo ry.Compared w ith the traditi onal statistics,the statistics learn ing theo ry has a good classificati on ab ility fo r li m ited train ing samp les.T h is theo ry featu res rap id convergence and local m in i m um avo idance.T he si m u lati on experi m en t fo r the traffic flow at a cro ssing p roves the validity and efficiency of th is m ethed.
Keywords:statistical learn ing theo ry;suppo rt vecto r m ach ine;ti m e series p rogno sticati on;
traffic flow
0 引 言
在智能交通系统IT S(In telligen t T ran spo r2 tati on System s)研究中，对路面交通流量进行预测[1]是个关键问题。近年来人们对此提出了多种识别算法，但距实用还有相当距离，特别是对快速性、小样本及不完全信息处理上还缺乏有效的方法[2]。基于此，本文将统计学习理论(Statistical L earn ing T heo ry)引入交通流动态时序预测中，给出了一种新的算法，有效地解决了神经网络结构选择问题、局部极小点等问题，实际数据验证了其正确性和有效性。
1 统计学习理论及SVM算法介绍基于统计学习理论交通流动态时序预测算法的理论基础是SVM分类算法的核心思想：类间距离的最大边缘，它实际上就是对小样本数据训练模型推广能力的一种控制。
统计学习理论就是研究小样本统计估计和预测的理论，主要内容包括四个方面[3]:
1)经验风险最小化准则下统计学习一致性的条件;
2)在这些条件下关于统计学习方法推广性的界的结论;
3)在这些界的基础上建立的小样本归纳推理准则;
4)实现新的准则的实际方法(算法)。
其中，最有指导性的理论结果是推广性的界，与此相关的一个核心概念是V C维。
1.1 VC维
为了研究学习过程一致收敛的速度和推广性，统计学习理论定义了一系列有关函数集学习性能的指标，其中最重要的是V C维(V ap n ik2 Chervonenk is D i m en si on)。模式识别方法中V C 维的直观定义是：对一个指示函数集，如果存在h 个样本能够被函数集中的函数按所有可能的2h 种形式分开，则称函数集能够把h个样本打散；函数集的V C维就是它能打散的最大样本数目h。若对任意数目的样本都有函数能将它们打散，则函数集的V C维是无穷大。 V C维反映了函数集的学习能力,V C维越大则学习机器越复杂(容量越大)。遗憾的是，目前尚没有通用的关于任意函数集V C维计算的理论，只对一些特殊的函数集知道其V C维。对于给定的函数集，如何(用理论或实验的方法)计算其V C维是当前统计学习理论中有待研究的一个问题[3]。
1.2 经验风险最小化
超市手推车广告收稿日期:2002201229
机器学习的目的是根据给定的训练样本求对某系统输入输出之间依赖关系的估计，使它能够对未知输出作尽可能准确的预测。可以一般地表示为：变量y与x存在一定的未知依赖关系，即遵循某一未知的联合概率F(x,y)，机器学习问题就是根据l个独立同分布观测样本:
(x1,y1),(x2,y2),+,(x l,y l)(1) 其中X i∈R N,y i∈{+1,-1},i=1,+,l。在一组函数{f(x,w)}中求一个最优函数f(x, w0)对依赖关系进行估计，最小化期望风险:
R(W)=∫L(y,f(x,w))d F(x,y)(2)其中L(y,f(x,w))是损失函数，但由于已知的只有样本(1),(2)式的期望风险并无法计算，因此传统的学习方法中采用了所谓经验风险最小化(简写为ERM)准则，即用样本定义经验风险:
R e m p(W)=1
l
2l
计算机取证工作站
i=1
L(y i,f(x i,w))
=1
l 2l
i=1
f(x i,w)-y i (3)
事实上，用ERM准则代替期望风险最小化并没有经过充分的理论论证，只是直观上合理的想当然做法：当样本点的个数l趋于无穷大时，经验风险趋于期望风险，但在有限样本下ERM准则得到的结果不能保证其真实风险最小。
1.3 结构风险最小化原理
统计学习理论系统的主要思想是结构风险最小化(Structu ral R isk M in i m izati on，简写为SRM)。V ap n ik和Chervonenk is研究后得出如下结论：经验风险R e m p(W)和实际风险R(W)之间以至少1-Γ的概率满足如下关系[3]:
R(W)≤R e m p(W)
+(h(ln(2l h)+1)-ln(Γ 4)
l
)(4)
其中h是函数集的V C维,l是样本数。这一结论从理论上说明了学习机器的实际风险是由两部分组成的：一是经验风险(训练误差)，另一部分称作置信范围，它和学习机器的V C维及训练样本数有关。显然,(4)式中经验风险R e m p(W)最小并不能保证实际风险R(W)最小，在有限训练样本下，学习机器的V C维越高，则置信范围越大，导致真实风险与经验风险之间可能的差别越大。为了解决这一问题,V ap n ik提出了结构风险最小化原理：为了达到期望风险最小，设法使V C维和经验风险R e m p(W)同时最小。
1.4 SV M的分类器算法
支撑矢量机简称SVM,
是结构化风险原理的近似实现，它能够提高学习机的泛化能力，既由有限的训练集样本得到小的误差，又能够保证对独立的测试集仍保持小的误差。而且，由于支撑矢量机算法是一个凸优化问题，因此局部最优解一定是全局最优解[4,5]。
图1 两类线性分类问题表述
1.4.1 广义最优分类面 支撑矢量机是从线性可分情况下的最优分类面发展而来的，其基本思想可由图1所示的两类线性分类问题表述。图中星号点和空心点代表两类样本,H为分类线, H1、H2分别为过各类中离分类线最近的样本且平行于分类线的直线，它们之间的距离叫做分类间隔(m argin)。所谓最优超平面就是要求分类线不但能将两类正确分开，而且使分类间隔最大，则H1、H2上的训练样本点就称作支撑矢量[5]。下面对其机理作详细地分析:
设数据集合C lass1和C lass2是线性可分的，即存在(w,b)，使
(w x i)+b≥1,Πx i∈C lass1(5a)
(w x i)+b≤-1,Πx i∈C lass2(5b)分类的目的是寻求(w,b)，最佳分离C lass1和C lass2，最优超平面应满足约束,y i[(w x i)+b]≥1,i=1,+,l，此时 (w x i)+b 的最小值为1，则样本与此最优超平面的最小距离是1 w ，使间隔最大等价于使 w 2最小，实际上，使分类间隔最大是对推广能力的控制。设 w ≤A，当数据点x1,x2,…,x l位于半径为R 的球内时,h满足:
h ≤m in{R 2A 2
,N }+1
(6)
因此, w 2最小可以使V C 维的上界最小，从
而实现结构风险最小化原理。另外，考虑到可能存在一些样本不能被超平面正确分类，因此引入松弛项Νi :
Νi ≥0,i =1,+,l ,(7)超平面的约束成为下式:
y i [(w x i )+b ]≥1-
Νi ,i =1,+,l (8)
此时构造的超平面是软间隔超平面，它是由(7)、
(8)约束条件下使泛函
5(w ,Ν
)=1
2
(w w )+C (2l
i =1Νi )
(9)
最小化的向量w 决定的(这里的C 是一个给定的
值)。其中第1项使样本到超平面的距离尽量大，以提高泛化能力，第2项则使误差尽量小。使公式(9)最小的超平面就是广义最优分类面。
利用L agrange 优化方法，通过引入L agrange 乘法系数Αi ，可以把以上最优分类问题转化为其对偶问题，即在约束条件:
2l
i =1
Αi y i =0
(10a )0≤Αi ≤C ,i =1,+,l
(10b )
对Αi 求解以下函数的最大值:
W (Α)=2l
i =1Αi -122l
i ,j =1
Αi Αj y i y j (x i x j )(11)对于这个典型的二次优化问题，很容易解出Αi ，根据最优化理论，存在唯一解，并且仅有一部分Αi 非零，其对应的样本就是支撑矢量。最终，得到基于最优超平面的决策函数:
f (x )=
2
支撑矢量
Αi y i (x x i )+b
(12)
1.4.2 支撑矢量机的分类算法
对于非线性分类,SVM 可用如下方法实现：通过某种事先选择的非线性映射5将输入向量x
酒店预定系统映射到一个高维特征空间Z ，用来构造最优分类超平面。在特征空间Z 中构造最优超平面时，并不需要以显示形式来考虑特征空间，只需能够计算支撑矢量与特征空间中向量的点积Z (x ) Z (y )=K (x ,y )，因此，在非线性情况下支撑矢量机对分类问题成为最大化函数:W (Α)=2l
i =1Αi -122l
i ,j =1
Αi Αj y i y j K (x i x j )(13)
其约束(10)保持不变，而决策函数为:
f (x )=
2
支撑矢量
Αi y i K (x x i )+b
(14)
其中K (x ,y )是核函数，核函数的选取应使其成
为特征空间的一个点积，任何对称函数K (x ,y )只要满足M ercer 定理即可符合要求[6]。
2 时间序列预测及仿真试验
基于统计学习理论的交通流量预测，是其一个新的应用。所谓预测就是利用过去和当前的观测值估计未来值，这实际上是基于这样一个假设，即未来值和过去值存在某种确定的函数关系。例如，假设当前时刻为t ，已知y (t -n ),y (t -n +1),……y (t )，要求预测y (t +1)，其相应的函数关系可以表示为:y (t +1)=+(y (t ),y (t -1),+,y (t -n ))，预测的目的就是试图构造这一函数，可见预测问题和函数逼近问题是等价的[7]。如果这一函数的自变量有n 个，预测就是在n +1维空间内对超平面进行拟合。
本文根据某个交通路口在过去一段时间的交通流量记录，预测后一时段的的交通流量。我们曾在1990年协助西安市公安局交通警察支队，进行过一次西安市各交叉路口的交通流量调查，调查的内容有：机动车流量流向调查，非机动车流量调查，交叉口延误调查，行人过街调查。其中机动车的调查地点有25个，本文选取其中的一个14h 调查地点：环东路什字，对东、南、西、北各个方向的机动车流量总和进行预测。其中训练区间为8:00～16:00时，预测区间为:18:00～22:00时。试验中从数据序列选择输入y (t -3),y (t -2),y (t -1),y (t )，经过SVM 处理后输出Y ，即预测出y (t +1)。图2中所示的预测结果较好，表1也显示出平均误差为6.03◊，而文献[2]中改进BP
算法的平均误差达到了11.18◊。因此，基于统计学习理论的交通流量有较好的预测结果。预付费智能电表
图2 交通流量的预测结果
收稿日期:2001210208;
修改稿收稿日期:2001212202
指纹细节匹配的遗传算法
金升平 陈定方
(武汉理工大学 武汉430063) (中科院计算所智能信息处理实验室 北京100080)
摘 要 指纹识别通常是采用一定的算法提取末梢点和分枝点，然后进行点匹配。文章根
据指纹细节的两种类型，设计适当的编码表示，使每个编码在类型上是一个可能匹配，然后设计遗传算法进行点的匹配，计算实例表明，在准确性和速度上均可得到满意的效果。
关键词 指纹 特征点 识别 遗传算法
Abstract :Based O n the tw o types of fingerp rin t m inu tiae ,th is paper design s a p roper p resen tm en t of codes ,w h ich m akes po ssib le the m atch ing of each code on types
.T he genetic algo rithm fo r fingerp rin t verificati on is p resen ted .Compu tati on of the examp les show s that the veracity and speed are satisfacto ry fo r the real ti m e fingerp rin t verificati on .
Keywords :fingerp rin ts ;verificati on ;m inu tiae ;genetic algo rithm
1 指纹识别
由于指纹终身不变性和唯一性，利用指纹识
别身份已经有很长的历史了，目前自动指纹识别系统有着广泛的应用前景，主要内容包括四个方面:
・指纹获取。怎样获取指纹图象以及如何将其表示成适当的格式;
・指纹识别。确定两幅指纹是否来自于同一个手指;
・指纹检索。在指纹库中查询一个特定的指纹;・指纹分类。根据指纹的几何外表特征，将其划分到特定的类别中。
大多数自动指纹识别系统是基于指纹特征的匹配[1～3]，指纹特征就是指纹的局部不连续点。FB I 使用两种类型的特征点：末梢点和分枝点，如
交通流量实测与预报结果
表1
数据类型时 间
18:0019:0020:0021:0022:00检测值43964163444643944048预测值
4102
391641604159开放式基金预测
3818
3 结束语
目前，现有的交通流量预测方法都是基于传统统计学的，其研究的是样本数目趋于无穷大的渐进理论，但当样本数目有限时难以取得理想的效果，因此，很难适应复杂多变的交通状况。统计学习理论
是V .V ap n ik 等人提出的一种小样本统计理论，有完备的理论基础和严格的理论体系，它具有收敛速度快，有效避免局部最小点的特点[6]。本文基于统计学习理论，试图到一种新的模型来解决交通流量的预测问题，有望在交通流量时间序列预测方面得到广泛的应用。
参考文献
1 杨明等.面向智能交通系统的图像处理.计算机工程
与应用,2001(9)
2 王宏杰等.基于改进BP 网交通流动态时序预测算法
的研究.交通与计算机,2001(3)
3 张学工译.统计学习理论的本质.北京：清华大学出版
社,2000
4 陈俊丽，焦李成.支撑矢量机的分类机理研究.西安电
转子动平衡
子科技大学学报,2000(增)
5 V apn ik V .T he natu re of statistical learn ing theo ry .
Sp ringer ,1995
6 C .J .C .Bu rges .A tu to rial on suppo rt vecto r m ach ines
fo r pattern recogn iti on .Know ledge D iscovery and D ata M in ing ,1998
7 杨一文等.基于神经网络的多变量时间序列预测及其
在股市中的应用.信息与控制,2001(5)
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议