（计算数学专业论文）基于监督分类的城市交通环境分区.pdf

独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 武汉理工大学或其它教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 关于论文使用授权的说明 期：型! ：! ! ：! 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即 学校有权保留、送交论文的复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段 保存论文。 ( 保密的论文在解密后应遵守此规定) 摘要 城市交通环境是城市交通系统可持续发展的主要研究问题之一。城市交通 环境问题已被越来越多地被引入城市交通系统规划、交通管理、交通控制等方 面的研究中。成为制定城市交通系统规划方案、交通管理与控制措施等考虑的重 要因素。交通环境的分区就是将整个环境分成不同的区域，然后再对其进行治 理、优化控制。 本文将监督分类和非监督分类与城市交通分区相结合，针对城市交通环境 分区情况对其进行了深入的研究。 全文具体内容主要分为5 部分，具体安排如下： 第l 章：绪论，对本文的内容做了简单的概述。主要介绍了课题的研究背 景、意义及研究现状等。第2 章：传统监督与非监督方法和理论，本章介绍了 监督分类方法和非监督分类方法，并对其算法的优缺点进行了介绍。同时介绍 了图像的预处理，主成分分析方法以及支持向量机方法的基本理论。第3 章： 城市交通环境分区算法探讨，本章将城市交通分区的算法做了较为细致的介绍， 同时提出了建立在非监督分类方法上的监督分类方法。第4 章：实证研究，本 章针对国北京城市的城区运用算法进行分析，对算法进行验证。第5 章：总结 和展望，该章概括了本文的主要内容及创新点，并且指出所存在的不足以及今 后的发展方向等。 本文的创新点如下： ( 1 ) 对传统的i s o d a t a 算法中增加了噪声控制变量，通过其来控制数据中 潜在的噪声，同时在距离函数设定的过程中引入了加权街道距离，并对权值的 选取做了讨论。 ( 2 ) 根据城市情况的特点并且结合实际，提出了较符合城市交通环境的指 标体系，并根据数据缺失的不同情况，采用不同的数据插值方式。 ( 3 ) 根据本文分类情况的特殊性，结合支持向量机的多分类情况提出了二 叉树分类法和一对一分类法相互监督与依赖的分类算法。 关键词：监督分类；非监督分类；指标；交通环境分区 a b s t r a c t u r b a nt r a m ce n v i r o n m e n ti so n eo ft h em a i nr e s e a r c hq u e s u o n si ns u s t a i n a b l e d e v e l o p m e n to fu r b a nt r a n s p o r ts y s t e m u r b a nt r a f f i c e n v i r o n m e n th a sb e e n r e s e a r c h e di n t h ef i e l d so fu r b a nt r a n s p o r ts y s t e m sp l a n n i n g ，t r a f f i cm a n a g e m e n t ， t r a f f i cc o n t r o la n do t h e rf i e l d s ，a n db e c o m ea l li m p o r t a n tc o n s i d e r a t i o ni nu r b a n t r a n s p o r ts y s t e mp l a n n i n g ，t r a f f i cm a n a g e m e n t a n dc o n t r o lm e a s u r e s t r a f j f i c e n v i r o n m e n tp a r t i t i o nw i l ld i v i d et h ec i t yi n t od i f f e r e n ta r e a so ft h ee n v i r o n m e n t ，t h e n o p t i m a la n dg o v e r ni t s u p e r v i s e dc l a s s i f i c a t i o nm e t h o d sa n du n s u p e r v i s e dc l a s s i f i c a t i o nm e t h o d sa r eu s e d i nu r b a nt r a n s p o r t a t i o np a r t i t i o n ，a n dt h es i t u a t i o no fu r b a nt r a n s p o r t a t i o np a r t i t i o n w a sf u r t h e rr e s e a r c h e d t h es p e c i f i cc o n t e n to ft h ep a p e ri sd i v i d e di n t of i v ep a r t s ，a sf o l l o w s ： c h a p t e rl ：i n t r o d u c t i o n ，h a v i n gd o n eab r i e fo v e r v i e wo ft h ec o n t e n to ft h i s a r t i c l e ，m a i n l yi n t r o d u c e st h et o p i co f r e s e a r c hb a c k g r o u n d ，s i g n i f i c a n c e ，t h er e s e a r c h s t a t u sa n ds oo nc h a p t e r 2 ：t r a d i t i o n a ls u p e r v i s e da n du n s u p e r v i s e dm e t h o d sa n d t h e o r i e s ，t h i sc h a p t e rd e s c r i b e st h es u p e r v i s e dc l a s s i f i c a t i o na n du n s u p e r v i s e d c l a s s i f i c a t i o nm e t h o d sa n dt h e i ra d v a n t a g e sa n dd i s a d v a n t a g e so ft h ea l g o r i t h mw a s i n t r o d u c e d a l s oi n t r o d u c et h ei m a g ep r e p r o c e s s i n g ，t h ep r i n c i p a lc o m p o n e n ta n a l y s i s a n ds u p p o r tv e c t o rm a c l f i n e st h eb a s i ct h e o r y c h a p t e r3 ：e n v i r o n m e n t a lp a r t i t i o n 、 a 垮研t ! 倚惩。西t a b a nt r a n s p o r t a t i o n ，u r b a nt r a n s p o r t a t i o nd i s t r i c ti nt h i sc h a p t e rt h e a l g o r i t h mw i l ld oam o r ed e t a i l e dd e s c r i p t i o n ，a n dp r o p o s e dt h ee s t a b l i s h m e n to f n o n s u p e r v i s e dc l a s s i f i c a t i o nm e t h o d si ns u p e r v i s e dc l a s s i f i c a t i o nm e t h o d c h a p t e r4 ： e m p i r i c a ls t u d y , t h i sc h a p t e rw i l lu s eb e i j i n gt oa n a l y z et h ea l g o r i t h mc l a s s i f i c a t i o n a c c u r a c y c h a p t e r5 ：s u m m a r ya n do u t l o o k ，t h i sc h a p t e ro u t l i n e st h em a i nc o n t e n t so f t h i sa r t i c l ea n di n n o v a t i o n ，a n dp o i n t e do u tt h es h o r t c o m i n g sa n dt h e f u t u r e 一一二- j 一 一一 d e v e l o p m e n td i r e c t i o n i n n o v a t i o no ft h i sp a p e ra r ea sf o l l o w s ： ( 1 ) a d d e dt ot h et r a d i t i o n a lm e t h o do fn o i s ec o n t r o lv a r i a b l e s ，t h ed a t at h r o u g h n i t sp o t e n t i a lt oc o n t r o lt h en o i s e ，w h i l et h ed i s t a n c ef u n c t i o ni n t r o d u c e di nt h ep r o c e s s o fs e t t i n gt h ed i s t a n c ew e i g h t e ds t r e e t s ，a n dt h es e l e c t i o no fw e i g h t sw e r ed i s c u s s e d ( 2 ) a c c o r d i n gt ot h ec h a r a c t e r i s t i c so fu r b a ns i t u a t i o na n dr e a l i t y , m a d em o r ei n l i n ew i t ht h ei n d e xs y s t e mo fu r b a nt r a f f i ce n v i r o n m e n t ，a n da c c o r d i n gt ot h ed i f f e r e n t s i t u a t i o n so fm i s s i n gd a t a ，u s i n gd i f f e r e n tm e t h o d so f d a t ai n t e r p o l a t i o n ( 3 ) a c c o r d i n gt ot h es p e c i a ln a t u r eo ft h i sc l a s s i f i c a t i o n ，s u p p o r tv e c t o rm a c h i n e m u l t i - c l a s s i f i c a t i o n m e t h o d s ：b i n a r yt r e e c l a s s i f i c a t i o na n dt a x o n o m y - o n ea r e c o m b i n e dt oan e wa l g o r i t h m k e y w o r d s ：s u p e r v i s e dc l a s s i f i c a t i o n ；u n s u p e r v i s e dc l a s s i f i c a t i o n ；i n d e x ；t r a f f i c e n v i r o n m e n td i v i s i o n i i i 目录 摘要i 目勇乏 第1 章绪论1 1 1 研究背景与意义1 1 2 国内外研究现状1 1 2 1 城市交通环境国内外研究现状1 1 2 2 监督分类方法国内外研究现状2 1 3 本文结构2 第2 章城市交通分区相关方法4 2 1 监督分类方法4 2 1 1 最小距离法5 2 1 2 平行六( 多) 面体法5 2 1 3 最大似然法6 2 2 城市交通环境分区：7 2 3 图像预处理7 2 4 传统主成分分析法。8 2 5 支持向量机方法l0 2 5 1 线性支持向量机10 2 5 2 非线性支持向量机1 4 2 6 本章小结1 5 第3 章城市交通环境分区算法探讨1 6 3 1 主要思路和流程图，16 3 2 图片的预处理。j l7 3 3 城市地图栅格化o 17 3 4 指标的选取和处理1 7 3 4 1 指标的选取17 3 4 2 指标值的处理2 0 i v 3 5 改进1 s o d a t a 初始分类：2 l 3 5 1 初始中心选取的改进2 3 3 5 2 分类过程中增加判断是否为噪声点2 4 3 5 3 距离函数的改进2 4 3 6 改进支持向量监督分类2 4 3 6 1 主成分分析预处理2 4 3 6 2 改进支持向量机多分类法分类2 5 3 7 分类结果评价2 8 3 8 本章小结2 9 第4 章实证研究3 0 第5 章总结与展望3 5 5 1 本文的主要研究内容和创新点3 5 5 2 展望3 5 参考文献3 6 致 射3 9 攻读硕士学位期间发表论文及参加科研项目情况4 0 v 武汉理工大学硕士学位论文 1 1 研究背景与意义 第1 章绪论 在经济迅速发展的当下，城市污染，道路绿化，交通状况等是人们比较关 心的城市问题，怎样根据现有的情况对城市交通环境系统做一个合理的有效的 分区，对我们以后对城市交通环境的优化和根据找出的城市交通环境的缺点进 行相应的改进都有十分重要的借鉴价值。然而一般的城市交通环境的划分是依 据环境学或交通学中的一些算法和理论进行分区，本文从图像信息的角度出发 将城市交通环境分区问题抽象为图像中的问题，并利用图像中的算法进行相应 的试探，并得到了较好的预期结果。 1 2 国内外研究现状 1 2 1 城市交通环境国内外研究现状 国内研究现状： 。 8 0 年代噪声和大气这两个因子是城市交通环境所研究的重点，然而生态环 境，社会环境，景观因子等影响的研究是城市交通环境还没有涉及到的。9 0 年 代相应的关于城市交通环境分区的研究的广度相度增加。城市交通环境的研究 内容涉主要及到交通环境影响现状分析、影响机制、污染控制措施、预防环境 影响的原理等方面。其中涉及到的环境影响领域包括传统的自然环境、生态环 境和社会环境。进入2 1 世纪，面临交通可持续和环境可持续方面提出的要求， 研究更加的系统化，从环境的系统和整体考虑，不局限于某一个环境因子，在 围绕道路交通噪声污染和大气污染这两个核心因子的情况下，对道路交通造成 的生态、社会、景观的影响逐渐展开和深入。同时，对单个因子影响的分析更 深入，随着对单一环境因子分析加深，对环境系统影响也有了整体的分析和研 究。李铁柱等对城市道路交通空气污染进行了狄色聚类决策评价，对城市机动 车车型构成与大气污染进行了关联分析，提出了控制城市道路交通污染的建议： 杨晓娜等从交通环境的角度，分别从空气污染、道路交通噪声、交通能源三个 武汉理工大学硕士学位论文 方面利用数学方法对北京市交通的发展作了比较分析。 国外在交通与环境的研究上较国内更广泛、更深入一些。在研究交通对环 境影响方面关注噪声、尾气等自然环境影响与关注拥挤、交通事故等社会环境 影响并重，研究的综合性高。并且国外对交通污染造成的经济损失进行了很多 研究，这也是现在对环境影响研究的一个重要方面。欧洲在交通规划中考虑的 环境影响，既包括大范围的全球影响( 能源和自然资源的消耗、气候变化) 也包括 区域影响酸沉降和光化学烟雾，这些影响与交通流量密切相关，美国的城市交 通规划是经济、社会、环境的综合评价，s e a 中评价的社会经济影响，主要包 括社区分离、经济发展、土地利用和城市结构分析。欧洲大部分的国家在评价 中只考虑环境影响，但也有个别国家将作为可持续发展的工具来应用( 如芬兰) ， 所以社会经济影响在部分评价中也有考虑【l 】。 1 2 2 监督分类方法国内外研究现状 统计模式识别方法和句法模式识别方法是两种遥感影像分类方法，其中， 模糊分类方法，人工神经网络方法，决策树方法等是句法分类方法，而经典的 如最大似然法等是统计模式识别方法，纯粹的监督分类方法主要存在的缺点是 需要大量的工作需要在人工指导之下进行，遥感影像中的分类方法主要是针对 非监督分类而言的，刘志刚史文中李德仁提出了新的基于支持向量机的不完全 监督的方法，张锦水何春阳等在多源信息的支持向量机的分类中引入了空间信 息，夏建涛，何明等在支持向量机的多分类方法中做了研究【2 1 。 1 3 本文结构 本文共分为5 章来对基于监督的城市环境交通分区算法进行探讨，其组织 结构如下： 第l 章：绪论，对本文的主要工作做了简单的概述。主要介绍了城市交通 环境的研究背景、意义及研究现状等。 第。2 章：城市交通分区相关方法，本章介绍了监督分类方法并对其算法的 优缺点进行了介绍。同时介绍了图像的预处理，主成分分析方法以及支持向量 机方法的基本理论。 第3 章：城市交通环境分区算法探讨，本章介绍了传统交通环境分区的方 2 武汉理工人学硕士学位论文 法，将城市交通分区的算法做了较为细致的介绍，同时提出了建立在非监督分 类方法上的监督分类方法。 第4 章：实证研究，本章针对国北京城市的城区运用算法进行分析，对分 类算法进行验证。 第5 章：总结和展望，该章概括了本文的主要内容及创新点，并且指出所 存在的不足以及今后的发展方向等。 武汉理t 大学硕士学位论文 第2 章城市交通分区相关方法 2 1 监督分类方法 有时候在分类的过程中需要加入人工的判断，例如先验类别知识，有些样 本我们已经具有了一定的先验知识，我们称这些样本为训练场地，把训练场地 中的有代表性的样本中提取有价值的指标值，然后根据它们的统计特性，建立 判别函数，进行分类，若果分类精度不满足需求，则进一步修改和调整，直到 满足精度需求，这种方法就称之为监督分类方法。 其分为两个过程：1 学习过程2 分类过程。学习过程是利用训练场地进行 训练或估计参数从的过程，识别过程是利用判别函数对未知样本进行分类的过 程。 示意图如下图2 2 所示： 学习过程 分 类 过 程 图2 1 监督分类的原理图 监督分类主要的三种识别方法：，最小距离法，平行六面体( 多) 面体法，一一。 最大似然法。 4 武汉理j l ：大学硕士学位论文 2 1 1 最小距离法 最小距离法：根据最小距离原则进行分类，在遥感图像的分类中此方法使 用较多。其原理是首先从训练组数据得到每一类的均值向量和标准差向量，然 后以均值向量作为该类在多维空间中的中心位置，计算图像中的每一个像元到 各类中心的距离，看一下该像元到哪一个类中心的距离最小，则就将该像元划 到哪一类中。示意图如下图2 3 所示： 类别a 图2 2 最小距离法算法示意图 最小距离法经常用到的两个距离函数有： 欧几里得距离： 芝g ，一i 歹 d 。= 上| 上一 街道距离： 。= 霉。卜习 2 1 2 平行六( 多) 面体法 平行六( 多) 面体法：是在三维空间中或多维空间中，每一类形成一个平 行六面体或多面体，若样本落入某一平行六面体，则该像元属于该类，否则就 不属于该类，平行六面体一般以每一类均值坐标点作为中心，在每个变量上的 两倍标准差作为棱长，以达到分类的目的，其算法示意图如下图2 4 所示： 2 1 3 最大似然法 图2 3 平行六( 多) 面体算法示意图 最大似然法：应用最广泛的监督分类方法，分类的判别函数是每一个像元 值属于每一个类别的可能性。基本原理是对每一个像元计算其落入各先验类别 的概率，概率最大的为其相应的类别。以下图2 5 为例，说明该算法。 0 图2 4 最大似然算法图例 欲根据这些数据和先验知识求想点x 属于a 、b 、c 中的哪一类，则x 属于a 的概率为：p ( x ，彳) = d x a ) p 0 ) ，p ( x a ) 为先验x 已知值，也就是在已知类a 内获得x 的条件概率，p 0 ) 为先验已知值。 6 武汉理工大学硕士学位论文 2 2 城市交通环境分区 伴随着经济的发展，与此同时城市的污染状况也在进一步的提高，城市交通 环境做为城市交通系统可持续发展的一部分。交通环境分区使分析者对复杂的 城市交通网络的研究变的简单，容易实现，从而对产生的交通环境问题分而治 之。如何真实地预测交通趋势和反映城市交通的现状是交通环境分区的侧重点。 城市交通系统与一个城市的发展相互影响相互作用，它与城市其他基础设施相 比较，既存在着共性也有很多的特性。对整个城市将交通系统的好坏作出评价 是为了把一个城市中各方面对交通的需求( 包括人的、经济的以及社会的) 同交 通系统能够为我们提供服务的能力相比较，从而把把它们之间的矛盾反映出来。 交通环境的分区就是将城市的整个环境按照一定的指标划分成不同的区域，以 便于观察、分析和进一步的优化控制。 2 3 图像预处理 一般图像在处理之前需要进行，去噪，增强或者几何校正处理，下面介绍 其主要方法。 图像几何校正：指从具有几何变形的图像中消除变形的过程。它的步骤如下： 1 确定校正的方法：根据图像几何畸变的性质和可利用于校正的数据确定校 正的方法。 2 确定校正公式：确定原始图像上的像素点和校正后的图像像素点之间的关 系，并得出变换公式。 3 验证方法的有效性：检查几何变形能不能得到充分校正，若果畸变不能得 到有效的校正，分析原因，找出可行的方法。 4 对原始图像进行再次采样，得到消除畸变的图像。 几何校正的主要方法有，仿射变换，三角形线性法，多项式变换等。 图像噪声：图像在摄取或者是传输的时候受到的随机干扰信息，常见的有椒 盐噪声和高斯噪声。图像噪声的抑制主要是采用滤波器的方法，即在尽可能保 持原图像的信息的基础上，抑制噪声。常见的滤波器有中值滤波器、边界保持 滤波器和均值滤波器。 均值滤波器的原理：在图像上，对要处理的像素设定一个模板，在这个模板中 7 武汉理工大学硕十学位论文 包含了周围的邻近像素。将模板中的全体像素的均值代替原来的像素值。均值 滤波器容易使图像变的模糊，其原因是将所有的点都进行同样的处理，将噪声 点和边界点进行了同样的处理，最终使得边界模糊。 中值滤波器：与均值滤波器相仿，其并非将一个不一定真实存在的均值代替 原先的像素值，而是将模板元素中的中值代替原来模板中心的像素值，这样图 像不会变的模糊，比较适合于高斯噪声的处理。 2 4 传统主成分分析法 主成分分析的主要思想是：利用降维的方法。将多个指标化为少数的几个 综合指标。在研究多变量的问题时，若果变量太多，问题的分析和计算会提升 复杂性，自然而然人们希望在进行分析的时候尽量涉及较少的变量，并且获得 较多的信息，主成分分析正是这样的一种方法。 主成分分析的几何意义： x 2 图2 5 变换前 变换函数如下： 人2 、y 2 。 - 以 墨 iy t = 而c o s 8 + 而s i n 秒 t y 2 = 一而s i n 9 + 工2 c o s 8 图2 6 变换后 一娈换的目的是将k 个样本点在y 。方向上的离散度变为最大，也就是说y 。方向 上的方差达到最大，同样也说明y 。代表了原来数据的大部分信息，即使忽略y ：对 整体的影响也不大，也就是说将两个指标合并为一个指标了。达到了降维的目 武汉理工大学硕士学位论文 的。 主成分分析的基本思想： 主成分分析的最大问题是其受量纲的影响，所以一般要对数据进行标准化，一 般使用协方差矩阵或者相关系数矩阵进行分析。 假设五，x ：x p 表示以而，x ：z p 为样本观测值的变量，如果能够找到 c i ，乞c ，s j m a x d ( c i x i + c 2 x 2 + c p x pj 显而易见上述公式必须要加上限制， n c , ，c 2 c ，可取无穷大而变得没有意义， 通常有如下规定： c i + c 2 + c p = 1 c 1 , c ：c ，是p 维空间的一个单位向，其代表一个方向，称之为主成分方向。当 然一个主成分不太可能代表原来的p 个向量的信息，所以我们要寻找第二个， 第三个，甚至是第四个主成分，原则上讲第二主成分不应该再包括第一主成分 的信息，也就是说这两个主成分的协方差为0 ，从几何上来看这两个主成分的方 向是正交的，确定各个主成分的方法如下： 设z ；表示第f 个主成分，则有 确定c i l ，c 1 2 c l ，j j 确定c 2 1 ，c 2 2 c 2 p ，“ z i2c l l x i + c 1 2 置+ c l p x p z 2 = c 2 1 x 1 + c 2 2 x 2 + c 2 j p x p z p = c p l x t + c p 2 五+ c 即x p m a x d ( z 。) ，并且满足 c l l 2 + 蠢+ c l ，2 = l m a x d ( z 2 ) 并满足c i i ，c 1 2 c l ，与c 2 l ，c 2 2 c 2 p 垂直和 c 2 1 2 + c 2 2 2 + c 2 ，2 = l 确定c 3 i ，c 3 2 c 3 p ，s jm a x d ( z 3 ) 并满足c 3 i ，c 3 2 c 3 p 与c 2 l ，c 2 2 c 2 p 和c q 2 c l p 垂直和 。 c 3 l + c 3 2 + c 3 p = 1 那怎么确定主成分的个数呢，在实际的研究中，主成分的主要目的是为了降维， 减少变量的个数，所以一般选取少量的主成分( 一般不超过5 个) ，当然也要损 失一些信息，只要总信息占原来信息的8 0 以上就可以了。 9 武汉理工大学硕士学位论文 主成分分析的实现主要步骤： 设相关矩阵为r 胛，求特征方程陋一2 1 i = 0 的特征根 由小到大进行排序 如五口 0 1 c t lc ，：c 如实际上是对应于以的特征向量。如果变量服从于正态分布，那么 各个主成分之间是相互独立的。 2 所有p 个主成分反映的是刀个样本的信息总和，其等于p 个原变量的总信息 和，用变量的方差来衡量信息量的多少。 3 按其主成分大小可以进行如下排序： z l z 2 z p 4 第f 个主成分的贡献率是 l x l 0 0 口 乃 i - 1 5 前m 个主成分的累积贡献率是： 以 l 1 0 0 p 乃 扣l 实际应用时一般取累计贡献率取8 0 以上为较好。 2 5 支持向量机方法 2 5 1 线性支持向量机 支持向量机( s u p p o r t v e c t o r sm a c h i n e s ，s v m ) 理论最初来自于对数据分 类的处理，如把可分数据分为两类，如果我们采用神经网络的方法来实现，其 方法可以进行如下的描述：我们先随机生成一个超平面并且移动这个超平面， 如果训练集合中的不同类别的点落在超平面的不同侧时，就达到了对对网络的 设计要求。但是这也有一个缺点，既是这种机制不能决定要分类的两个类中心， 其容错性比较差1 4 6 1 。 一一：一， 一一一 确保我们最终获得的超平面在两个类中心之间的位置在实际应用中非常重 要，恰好支持向量机方法满足了这一方面的需求，其原理可以简约的描述为： 1 0 武汉理工大学硕士学位论文 找一个满足分类要求的最优的分类超平面，为超平面在保证分类精度的同时， 能够使两侧的空白区域的间距最大化，一般来说，支持向量机可以实现对线性 可分数据的最优分类，那怎么样解决非线性分类问题呢? v a p n i k 等人引入了核 映射的方法把地位空间上的非线性问题转化为高维空间的线性可分问题。 如果是线性可分的数据集，我们可以进行训练样本融，y ，) 矧7 ，其中是输 入模式的第f 个输入，相对应的y ；是而的期望输出。我们首先假设子集y ；= 1 和 y ，= 一1 代表的模式是线性可分的，用超平面的方程表示为： w x + b = 0 在其中x 代表输入向量，w 是可以调整的权值的向量，b 是偏移量。 为了简单直观，这里仅讨论线性可分情况，如下图3 3 所示二维线性可分的 情况： x h j 图2 7 最优超平面示意图 图中的圆圈和叉号分别表示两类的训练样本，中间的直线日把两类没有错误 的分开的平行线，日。和日：分别是各类样本中离分类线最近的点并且是平行于分 类的直缘哪、日和：之间的距离称之为两类的最大分类间隔。最优分类线是指 不仅能够将两个类正确无误的分开，并且要使两个类的分类间隔达到最大。一 般的人工智能算法是保证经验风险最小，支持向量机是使置信风险最小，因而 实际风险最小，这是保证结构风险最小原则的实现。把上述情况推广到高纬空 间，最优分类线就变成了最优超平面。 下面介绍一下支持向量机的结构化风险最小和经验风险最小。假设有刀个样 本g ，y 。) ，g ：，y ：l g 。，y 。) 在二函数扩b i 0 ) ) 中寻找一个最优的函数纱g ，w o ) ， s t ： r ( w ) = 肛，厂g ，w ) p f g ，y ) 武汉理工大学硕士学位论文 上述定义的期望风险最小必须依赖概率，g ，y ) 的信息，但是我们在实际中 只能利用有限的样本信息，所以期望风险无法进行计算，人们利用均值代替上 式中的数学期望，其公式为： ( w ) = 丢喜三y l ，厂“，w ) ) ( w ) 是通过已知样本获得的经验风险，通过参数w 使( 曲达到最小就 是期望风险最小原则( e r m 原则) 。 结构风险最小化准则( s r m 原则) 是把函数集构造成一个函数子集序列， 使，在v c 维下对其各个子集进行大小排列，在每个子集中搜索最小经验风险， 综合考虑经验风险和置范围，使得实际的经验风险最小。 为了确保分类面对所有的样本能够正确并且是最大的分类间隔，那它需要 满足如下的要求： 陟翌三1 加m 二1 营m ( w 6 ) - 1 o w x ，+ b - 1f o ry ；= - 1i 7 、7 由此可以计算出分类间隔为： w x i + bw 。x ；+ b2 m i n - 1 ) 育一m a 叫x ) 育= 佩 现在我们的目的是在服从约束的条件下使分类间隔最大化，也就是2 1 叫l 最 小化，这样我们可以用过使m 1 2 最小化的方法来实现，也就是说求解最优超平面 的可以转化成如下的优化问题，在约束条件下，最小化函数为： 矽( 们= o 5 1 1 w l l 2 = 0 5 w w 这个约束问题具有的特点是： 1 代价函数( w ) 是关于w 的凸集， 2 约束条件关于w 是线性的。 所以我们可以使用l a r g r a n g e 方法解决约束的最优化问题。 首先，我们先建l a r g r a n g e 函数： l ( w ，b ，口) = 0 5 1 q 1 2 一口，l v ，w x ，+ b ) - i 】 1 2 武汉理工大学硕+ 学位论文 式子中变i r a ，o 是l a r g r a n g e 乘子。约束最优化的解是由l a r g r a n g e 函数 l ( w , b ，a ) 的鞍点决定的，而此时函数对w 和b 必定也是最小化的，同时a 必定是 最大化的。l ( w ，b ，口) 对w 和b 求其微分方程并将结果置为0 ，我们可以获得如下 的两个最优条件： 条件1 ：a l ( w - , b , a ) ：0 条件2 ： 下o l ( w , b , a ) = 。 通过条件1 我们可以得到： ， w = q y f _ f i l 也就是说最优超平面的系数向量是训练样本的线性组合。通过条件2 我们可 以得到： ， 口f y i = o i - ! 是； 这样我们就可以把上述问题转化成一个比较简单的“对偶问题了。也就 形( 口) ：圭口，一o 5 圭口，口，m y g ，工，) i - il = l 这是一个不等式约束的二次函数的极值问题( q u a d r a t i cp r o g r a m m i m g ) 根据最优选择条t t 争k a r u s h k u h n t u ck e r 条件，这个优化问题的解应该满足如 下条件： a i 瓜w 五) + 6 k 一1 - - 0 ，i = 1 ，2 ， 因此，对多数样本口i 将为o ，若a ，不为0 的样本就是支持向量( s u p p o r t v e c t o r s ) ， 也就是图3 3 所示的方框中标记的点。对学习过程来说，支持向量是训练集中的 关键元素，因为它离决策边界很近，要是去掉所有的其它训练点，再进行训练， 得到的分类面是相同的。 一一二一一 求解上述问题后获得的最优分类函数是： + 1 3 武汉理工大学硕士学位论文 几) - - - - 5 印 煽“z ) + b l i - ij 由于非支持向量对应的a ，= 0 ，因此上述公式的求和实际上是只对支持向量 进行。b 是分类的阈值，可以通过任意一个支持向量形式获得两类中任意一对支 持想两种获得支持向量机。 2 5 2 非线性支持向量机 前面介绍了线性支持向量机，这是在在输入空间中构造最优分类面的方法 类似于经典单个的神经元方法。但这种方法仅当样本为线性可分的时候才能使 经验风险为0 。由于许多问题，甚至像异或这样简单的问题都不可以线性可分， 所以这种方法获得的解常常是因为经验风险过大而失去意义。 解决这一类问题的一种思路是把输入向量映射到一个高维的空间中，使之 变为一个高维的特征向量空间，并且在此空间中寻找最优分类平面。如果能够 选择合适的映射函数，大多数输入空间不可划分的问题就可以转化为线性可分 的问题来对待，但是在映射中，由于空间急剧的增长，大多数情况下很难直接 在特征空间中寻找到最优分类平面。支持向量机通过定义核函数 ( k e r n e lf u n c t i o n ) 的方式巧妙的把这个问题转化到输入空间进行计算，因为 前面的问题中都涉及到内积运算，所以需要进行非线性映射：r 4 - - - h ，在构 造最优超平面的时候，仅使用特征空间的点积，即( 而) ( x ，) 。所以，如果能 够找到一个函数k ( ，) ，s 1 k b ，x ，j = b ，) b ，j 这样在高维空间上只需要进行内积运算，此时的最优分 类函数是： ri、 厂g ) = s g n y 舟k “x ) + b 这罩的k b ，x ) 称之为核函数，在支持向量机中，常用的几种核函数有： 1 g 阶多项式函数：k g ，x ，) = 盼工，) + c r ，此时获得的支持向量机是一个 q 阶的多项式分类器；一。 一一一： ri1 。 厂g ) = s 印 y 以石) + c r + b lf i lj 1 4 得到的支持向量机是一种径向分类器： 脚印黔膨p ( 譬 + 6 ) 3 s i g m o i d 核函数： k ( x ，x ，) = t a n h v ( x x ，) + c j 这时支持向量机实现的是就是一个隐藏感知器，隐藏节点数是由算法自动 确定的。 2 6 本章小结 本章主要介绍了本文分析所涉及到的基本知识包监督分类的基本知识，图 像预处理，主成分分析法和支持向量机方法，在此基础上我们在下面的章节中 利用这些基本理论和方法做进一步的研究。 武汉理工大学硕士学位论文 第3 章城市交通环境分区算法探讨 3 1 主要思路和流程图 本文主要是将一个城市在空间上进行划分，以图像的方式进行呈现将城市 交通环境按照其状况分为4 个类。主要思路是首先对要处理的图片进行预处理， 然后对图片进行栅格化，其次进行选取指标，处理指标，利用非监督分类的方 法获取初始聚类效果图，再利用监督分类的方法进行进一步划分，最后是对算 法的验证。其流程图如下3 1 所示： 图3 1 城市交通环境分区流程图 1 6 武汉理工大学硕十学位论文 3 2 图片的预处理 在获得一幅城市地图之后我们要根据这幅地图存在的问题，例如地图模糊 或者有噪声存在，甚至有时图片有几何扭曲，这时我们根据地图存在的问题进 行相应的校正，模糊图像可以进行锐化处理，有噪声的图像可以进行滤波处理， 扭曲的图像进行几何校正，图片的预处理是给予我们视觉上的一种感受，实际 上城市地图仅是一种呈现方式，便于我们更直观的理解城市分区。 3 3 城市地图栅格化 地图的栅格化是指，我们要将整个城市进行分区，分区后的每一个小块在 地图上如何表示，假使该城市的面积为m 甩平方公里，城市地图的像素个数为 a b ，最简单的表示方法就是一个像素表示一个小块，即该小块的面积为 m 刀a b ，这样处理的缺点就是相当于将所有的城市地区的重要性按照同样的 标准来处理，事实上城市中心地带的重要性明显比郊区的重要，根据城市地带 的重要性不同，可以进行如下划分，将城市中心地带块的划分相对较小，而郊 区的划分块要相对大一些。 3 4 指标的选取和处理 3 4 1 指标的选取 城市交通评价是对交通系统的性能，运行状态和性能的评估，或者是对交 通方案的优劣进行相对价值的评价定，用比较容易理解的表述方式进行表述， 为城市规划建设提供依据。影响交通环境的因素是有很多方面的，不仅具有经 济，社会的，还有环境的，为了简化评价指标体系，下面主要以交通因素和环 境因素做为主要因素，对城市交通环境分区进行探讨。 交通环境的主要因素包括。动态交通，静态交通和交通设施三个方面，具 体指标图如下图3 2 所示： 1 7 武汉理： 大学硕士学位论文 图3 2 城市交通环境指标图 下面介绍各个指标值的含义和计算方法： 路网饱和度：城市交通需求量( v ) 与路网供应量( c ) 的比值， 。l o s = v | c l o s 是路网饱和度，该指标是动态交通的一个分量，由于其是一个动态的值， 在这里使用另一种计算方法： 三傩：竺：里堡生竺：生：生竺! 呈生 r ， 其中尺。是路网车道的总的时空总资源和，r ，= l ，r ，三，是路网机车道的有 效总长度，t 为路网的实际使用的时间总和，r 由为一般车的出行消耗的总和， 。 r 西= d ，矾为行车过程中的车头距离，f 为车在路网上的实际驾驶时间，刀 “为有效时间内卑辆薹野生的总和，k 为车和自行车之间的换算系数， 七：生：! ：旦兰 8 6 8 v i + 2 9 2 这个指标反