基于模糊C均值算法的单交叉口.doc

基于模糊C均值算法的单交叉口交通流模式界定方法研究诸 云, 胡启洲, 高宁波（南京理工大学自动化学院，南京 210094）摘要：为提高交叉口交通管理水平，对交叉口交通流模式类型进行研究。以模糊C均值聚类算法为基础，结合模糊聚类质量综合系数评价准则方法，对聚类中心值进行了质量评价，优化聚类过程。基于此，提出了基于模糊C均值聚类方法的交叉口交通流模式识别流程。然后以南京市北京西路西康路交叉口实地采集的数据进行分析，实例分析表明该交叉口的交通流共可以划分为分别对应高高峰、晚高峰、上午平峰、下午平峰以及中午高峰5种模式，并进行仿真延误对比分析，验证了该方法的有效性和实用性。关键词：交叉口；交通流模式；模糊C均值；质量评价；聚类算法中图分类号：U 文献标识码：A 作者简介：诸云（1985年），女，汉族，江苏省南京市，南京理工大学自动化学院教师，助理研究员,博士生, 研究方向：系统工程、智能交通控制，邮编210094，联系电话02584303003基金项目：本文系国家自然科学基金资助项目（51178157）；中央高校基本科研业务专项基金项目（NO.2011zdjh29）；国家统计科研计划项目（NO.2012LY150）；江苏省高校“青蓝工程”资助项目（NO.201211）阶段研究成果。Study on Traffic Flow Patterns Identification of Single Intersection Based on Fuzzy c-means Clustering Algorithm ZHU Yun，HU Qizhou，GAO Ningbo (Nanjing University of Science and Technology, Jiang Su Nanjing, 210094)Abstracted: To improve intersection traffic management, traffic flow patterns on the intersection type research. This paper used the Fuzzy C-means clustering algorithm based on fuzzy clustering coefficient comprehensive quality evaluation criteria method, to value the cluster center quality, and to optimize the clustering process. Based on this proposed intersection traffic flow pattern recognition based on fuzzy C-means clustering method. West Beijing Road, Nanjing, then the data collected in the field XiKang intersection analyzed case study shows that the total intersection traffic flow can be divided into corresponding high peak, evening peak, flat peak morning, noon, afternoon, flat peak and peak 5 modes and comparative analysis of simulation delay, verify the effectiveness and practicality of the method.Key words: Intersection; Traffic flow patterns; Fuzzy C-Means; Quality evaluation; Clustering algorithm0 引言交叉口拥堵是城市交通拥堵的一种具体体现，其本质是交叉口时空资源分配与交通流需求不均衡造成的，通过对交叉口交通流模式进行特征划分有助于合理分配交叉口通行路权，提高交通口通行效率，缓解城市交通拥堵。目前，国外对交通流模式的研究主要集中于仿真方法以及分类理论的研究。例如在仿真方法层面，Jin等人利用计算机仿真技术，研究了不同几何尺寸特征对交叉口交通流的影响1；Cassidy等通过检测器测到的各时间间隔实时流量的差值与研究排队内部的流量波动2；在分类理论层面，MontazeriGh等基于K-means聚类分析提出了一种交通状态识别的数学方法3；Mohamed Abdel-Aty等分析实时交通流参数和交通事故的相关关系，为识别事故车速和非事故车速，设计了一种基于神经网络的BAYES分类器4。国内对交通流模式识别的研究主要是集中在分类方法的研究方面，例如于荣等利用支持向量机的不同核函数对城市道路交通流模式进行了分类，并探讨了不同核函数下的分类正确率5；弓晋丽等在对交通流模式划分的研究中提出了时间相识度序列分类方法，得出模式距离加欧式距离是最优的交通流时序模式划分距离6，除此之外还有许多学者将研究重点放在对交通流模式的预测等方面7-9。模糊C均值聚类算法是一种基于函数最优方法的聚类算法，使用微积分计算技术求最优代价函数，具有算法简单，分类准确的特点10-11。因此，利用模糊C均值聚类算法能够快速实现短时交通流状态的预测和模式划分，提高交通信号控制效率，减少交通控制延误的目的。1 交通流模式交通流量、密度、速度和占有率等参数在空间和时间分布上都具有离散性以及不确定性12-13，因此不能够用单一的指标去判断交通流的运行状态，根据已有的研究结果，比较有效且能简单地表达交通流状态的方法是将交通流表示为M维流量状态空间的“质点”，每一个流量状态M维空间示意了交叉口特定的交通流向数目。例如，对于一个十字交叉口为例，交通流由12个方向的交通流向组成，如图1所示，其具体流向如下：向北直行（NBT，northbound through）、向南直行（SBT, Southbound Through）、向东直行（EBT, Eastbound Through）、向西直行（WBT, Westbound Through）、向北左转（NBL, Northbound Left）、向南右转（SBR ,Southbound Right）、向东右转（EBR, Eastbound Right）、向南左转（SBL, Southbound Left）、向西左转（WBL, Westbound Left）、向东左转（EBL, Eastbound Left ）向北右转（NBR, Northbound Right）和向西右转（WBR, Westbound Right）。图1 十字交叉口交通流向示意图交通流模式划分与定义是将历史交通流数据点分类成一个个特征群，将任何给定的交通流数据点（实时检测到的交通流数据），最佳匹配到对应的群中。群的中心点可以定义为特征点，即典型交通流模式。2模糊C均值聚类算法2.1 模糊C均值算法 (1)模糊C划分设交通流数据集，表示实数维向量空间，其中是样本的第个属性值。所谓X的一个模糊c-划分是指： （1）式中，是阶矩阵的集合；表示样本隶属于第i类的隶属度。(2)模糊C均值目标函数假设： （2）其中，是X的一个模糊c-划分。是权重因子，m1时收敛。记为聚类中心， 。，A是一个阶正定系数矩阵。表示样本与各聚类中心加权距离平方和，其权重为的m次方(为对于类的隶属度)。由于是m次方误差聚类准则，所以样本的最优模糊c划分是的最小方差稳定点(U，)。由可以解出最佳模糊隶属度U的各元素为 （3）其中，若，则。U矩阵必须满足以下3个条件：；，每个样本相对于各类的隶属度之和为1；，即每一类都不为空。则类中心 为： （4）（3）聚类质量评价利用模糊C均值算法可以计算出交通流量空间的C聚类中心值，这些中心点代表着交通流数据的聚集点。评价交通流聚类质量就是评价最佳分类数目c的好坏。通过评估不同c和m值的效果，可确定这两个参数的最佳值，从而可以确定模糊数据最佳的分类结构14。交通流聚类质量评价准则：距离相同数据群中数据点越近，且距离不同数据群中数据点越远，分类越好。该准则是以模糊聚类质量系数为基础。 （5）其中，是数据群数；,表示第个或第个聚类中心的第个交通流向（可以是交叉口的任何交通流向）；表示第个数据群中第个点的第个交通流向；是第个数据群中的点数；是第个数据群中的交通流向数。通过值的情况可以分析聚类质量的优良。2.2交通流模式的聚类划分流程交通流模式模糊聚类就是根据获取的交叉口各方向的交通流数据，利用模糊聚类算法迭代循环寻找最优交通流特征分类，具体过程如下：Step1. 数据标准化采集到的交通流量数据利用极大极小值方法归一到0,1区间，然后将标准化的每个交通流量数据点构成矩阵，M表示交叉口交通流向数量（M=2,3,4n）,t表示数据采集的时间序列数（t=1,2,3T）。Step2. 聚类种类设定聚类种类设定有两种方式，一种是利用模糊算法直接迭代运算最后得出聚类种类；另外一种是根据特定的要求人工设定聚类种类，这里我们采取自动聚类方法。Step3. 模糊C均值聚类将交叉口交通流标准化矩阵数据利用上式（1）至（4）进行模糊C均值聚类算法计算出模糊聚类中心点，得出分类类别。Step4. 聚类质量评价根据步骤3得出的聚类分析结果按照上式（5）进行聚类质量评价，评价的目的是对聚类的准确性评估，如果聚类质量评价高，则输出聚类结果，否则进入步骤2循环。Step5. 得出聚类结果输出最后的最佳聚类数目，得出聚类中心矩阵以及聚类类别。聚类流程如下图2所示：图2 交通流模式定义流程图3交叉口实例分析以南京市北京西路西康路交叉口为例，经过现场调查分析，被研究的交叉口有12个交通流向，这就构成一个12维的模糊空间。每15分钟检测交通流，每天可获得96组样本数据（），交叉口的特征见下面的交叉口现状图3所示：图3 现状交叉口（1）交通流数据采集根据人工和检测器采集和调查的交通流，得出北京西路西康路某一日12小时交通流量如表1。表1 西康路某日12小时交通流量表时间段 交通流流向 （单位：vehicles/hour）SBLSBTSBRNBLNBTNBRWBLWBTWBREBLEBTEBR7:00-8:0072 185 56 360344 23291 6814888720888:00-9:0092232 70 480430 320113 8526011010001209:00-10:00144 371 112 760688 440181 136396176135717610:00-11:00120 309 93 628573 340151 108080147113110011:00-12:00108 278 84 528516 288136 10227213210187212:00-13:0079 204 62 440378 240100 80053977479213:00-14:0073 180 55 360350 22095 64051906819614:00-15:0096 247 75 520459 296121 9086411790512015:00-16:0089 231 75 480430 241112 8006211285012016:00-17:00126 324 98 656602 376159 112084154118816417:00-18:0096 247 75 548459 296121 10006411790512418:00-19:0020 46 60 16086 8823 400122217052（2）模式划分借助Matlab软件所编制的模糊聚类程序代码，分析该交叉口历史交通流数据，确定聚类中心和交通流模式、最优配时方案和模糊聚类隶属矩阵。得到最佳交通流模式数目为5、模糊划分隶属度见下表2所示：表2 西康路某日12小时交通流模糊划分隶属度表时间段第一类第二类第三类第四类第五类7:00-8:000.00760.00440.01890.96120.00798:00-9:000.03400.05480.62240.14560.14329:00-10:000.00040.99520.00120.00070.002610:00-11:000.00430.02130.02940.01110.933911:00-12:000.03140.08360.43150.09990.353612:00-13:000.05070.04140.26800.55720.082713:00-14:000.03250.01620.06310.85970.028514:00-15:000.00460.00750.94700.02010.020815:00-16:000.04260.04750.51630.28670.106916:00-17:000.01640.12360.08970.03950.730817:00-18:000.02530.04940.68720.09180.146318:00-19:000.99940.00010.00020.00030.0001聚类中心矩阵见下表3所示： 表3 西康路某日12小时交通流聚类输出的聚类中心矩阵表交通流流向第一类第二类第三类第四类第五类SBL0.02010.14370.09510.07380.1209SBT0.04630.37020.23680.18690.3108SBR0.06000.11180.07450.05700.0938NBL0.16050.75840.51440.37380.6298NBT0.08660.68660.45370.35320.5773NBR0.08830.43900.29280.22940.3482WBL0.02310.18060.11940.09430.1522WBT0.40071.35990.91240.68531.0871WBR0.01210.09580.06350.05020.0806EBL0.02210.17560.11600.09060.1479EBT0.17111.35440.91900.71421.1402EBR0.05210.17560.11730.09230.1197根据上表2和表3可得出交叉口各种交流模式中心值如下表4所示：表4 西康路定义的典型交通流模式表交通流模式 交通流流向 （单位：veh/h）SBLSBTSBRNBLNBTNBRWBLWBTWBREBLEBTEBR模式1204660160868823401122217152模式21443701127586874391801360961761354176模式3952377551445429311991264116919117模式4741875737435322994685509171492模式5121311946305773481521087801481140120根据上述表可知，聚类计算生成5个不同的典型交通流模式：（1）交通流模式一: 18:00- 19:00；（2）交通流模式二:9:00-10:00；（3）交通流模式三:8:00-9:00和11:00-12:00和14:00-16:00 和17:00-18:00；（4）交通流模式四:7:00-8:00 和12:00-14:00；（5）交通流模式五:10:00-11:00 和16:00-17:00，如图4所示。图4 北京西路西康路不同交通流模式时间段划分图4结论首先介绍了模糊C均值聚类方法的聚类原理，在此基础上，同时根据分类结果，采用模糊聚类质量综合系数评价准则进行优化，提高交通流模式定义的质量。基于此，提出了基于模糊C均值聚类方法的交叉口交通流模式识别流程，然后以南京市北京西路西康路交叉口实地采集的数据进行分析，经过聚类划分得到5类交通流模式。因此，通过模糊C均值的聚类方法应用于交叉口的交通流模式划分，使得交叉口交通流模式更具有科学性、动态性和适应性，与传统仅凭借交通工程师经验划分的交通流模式相比，采用模糊C均值的聚类技术划分交通流模式更能提高交叉口的信号控制效率和交叉口的通行能力。参考文献：1 Jin W L, Zhang Y. Paramics simulation of periodic oscillations caused by network geometryJ. Transportation Research Record: Journal of the Transportation Research Board, 2005, 1934(1): 188-196.2 Ahn S, Cassidy M J. Freeway traffic oscillations and vehicle lane-change maneuversC.Transportation and Traffic Theory 2007. Papers Selected for Presentation at ISTTT17. 2007.3 MMontazeriGh，A FotouhiTraffic condition recognition using the k-means clustering methodJTransportation Research B：Mechanical Engineering，201 1，18(4)：930-9374 Mohamed AbdelAty，A