计程车路线挖掘.doc

课程设计说明书(论文)题 目 交通轨迹数据模式提取 课 程 名 称 数据挖掘 专 业 信息与计算科学 学 生 姓 名 崔卓须（3101301308） 姚顺兰（3101301304） 陈晓强（3101301230） 设 计 地 点 数理系机房 指 导 教 师 贺文武 摘要一个城市的交通是一个非常庞大复杂的系统，如果对于交通系统的调度管理适当的话，保持道路通畅，能为我们的生活提供很多的方便。然而交通混乱成为了北京上海广州等大城市的一块心病，每当上下班高峰期必然堵车。从而建立关于交通的数学模型，与我们的生活息息相关。对于问题一，寻找营业额高于平均水平的司机的行车模式，无非就是找出一天中载客时间最长并且放空时间最短的出租车，在这种模式下，从而达到利益最大化。于是找出他们的行车轨迹和出车和收车时间，指导其他司机。对于问题二，寻找十个最活跃的中心区域，本文提出两种方法，方法一：首先通过经纬度对福州市区进行划分。每隔0.01经度和0.01纬度划分为一个小块，统计每个小块中计程车轨迹点，找出10块密度最大的小块，这些小块就是最活跃的地区。方法二：然而上面的结果可能是交叉路口或行驶必经之地，并不是乘客最多的地方，于是提出另一种最活跃地区的寻找方法，即统计所以计程车数据中乘客上车次数出现最多的区域为最活跃区域。对于问题三，一共有计程车数据1000组和非计程车数据1000组，每一组计程车数据中有8个属性，同时在两千多个时间点对这些属性的值进行了统计。然而由于数据庞大，我们必须对数据进行处理。本文提出两种方法：特征时间点数据提取法和求期望法。然后构建支持向量机（SVM）分类器，从而判断车辆类型。关键字：交通，计程车，特征提取，支持向量机（SVM）问题重述Data1.rar文件为某市部分出租车某天的行车轨迹（通过车载GPS设备获得），解压后的文件夹中每个文件对应一辆车一天的GPS数据。通常每30秒左右采集一次，对应文件中的一行，每行包含车辆的9个属性，用逗号分隔，分别是：车辆ID，区域ID（备用），经度，纬度，速度 ，方向（0-7，0为正北，顺时针+45度，值+1），有无载客（1表示有载客，0表示无），GPS采集时间，车辆类型（41表示出租车，非41表示其它营运车辆）。1. 假设你是出租车公司的管理者，怎样利用给定数据寻找有趣模式，以提高服务与效益？（1）寻找营业额高于平均水平的司机的行车模式，用以指导其他司机；（2）找出该市十个最活跃的中心区域，在这些区域中可能有更多的人需要坐出租车。3. Data2.rar文件中给出某市1000辆出租车和1000辆其它营运车辆某天的行车轨迹（数据格式和Data1.rar相同）。请根据行车模式判断车辆类型（是出租车还是其它营运车辆）。（本文选取题目的问题一和问题三）问题分析对于问题一，寻找营业额高于平均水平的司机的行车模式，无非就是找出一天中载客时间最长并且放空时间最短的出租车，在这种模式下，从而达到利益最大化。于是找出他们的行车轨迹和出车和收车时间，指导其他司机。对于问题二，寻找十个最活跃的中心区域，本文提出两种方法，方法一：首先通过经纬度对福州市区进行划分。每隔0.01经度和0.01纬度划分为一个小块，统计每个小块中计程车轨迹点，找出10块密度最大的小块，这最活跃的地区。方法二：然而上面的结果可能是交叉路口或行驶必经之地，并不是乘客最多的地方，于是提出另一种最活跃地区的寻找方法，即统计所以计程车数据中乘客上车次数出现最多的区域为最活跃区域。对于问题三，一共有计程车数据1000组和非计程车数据1000组，每一组计程车数据中有8个属性，同时在两千多个时间点对这些属性的值进行了统计。然而由于数据庞大，我们必须对数据进行处理。本文提出两种方法：特征时间点数据提取法和求期望法。然后构建支持向量机（SVM）分类器，从而判断车辆类型。模型建立1.基于密度的离群点检测:对数据进行异常检测，去掉异常的数据。从基于密度的观点来说，离群点是在低密度区域中的对象。一个对象的离群点得分是该对象周围密度的逆。基于密度的离群点检测与基于邻进度的离群点检测密切相关，因为密度通常用邻近度定义。一种常用的定义密度的方法是，定义密度为到个最近邻的平均距离的倒数。如果该距离小，则密度高，反之亦然。逆距离:其中，是包含的-最近邻的集合，是该集合的大小，而是一个最近邻。2.寻找营业额高于平均水平的司机的行车模式:无非就是找出一天中载客时间最长并且放空时间最短的出租车，计程车虽然是按路程收费，但是在红灯或堵车时是按时间收费的，所以在本文中用载客时间来衡量盈利，同时计程车在放空车时也会浪费邮费。因此我们设载客时间为，放空时间为，则为权重（取1/3），当最大时，最为盈利。在2290辆计程车的数据中找出值排名前100的计程车，画出他们的行车轨迹如下：图一 盈利前100名行车轨迹图由图一可知，他们基本上是在福州市繁华地段行驶。我们还可以得到他们的上班时间和收车时间如下表1表 1 盈利前100名的上下班时间车牌号上班时间收车时间9685000.009723.96069691850.023923.97069696830.027823.96949691180.026923.96929693590.027823.97539696540.026723.971911975700.032223.958111003280.035323.961411842880.033923.959711001120.035023.950612541820.035323.956912309000.036723.958311002160.033323.954712586810.035623.957213128160.033123.960312294890.033123.960011002630.032223.948611947670.034223.958611859100.045323.960811000680.045323.960811002480.037223.960811969380.043323.958311845870.034423.956711081530.036423.958611969050.038123.960311975680.043923.957211094020.039723.961411842260.046123.95929693800.042823.955613122110.035023.955012540490.029223.948612171020.046723.956411968860.046723.956412540350.031723.957516459950.031723.953310817960.973623.934711842430.024423.955811003310.038623.953311243850.042223.947811002640.046123.959413146060.039423.958611002960.040323.959411085510.045823.94789693700.051923.955611003240.063623.95589698700.036923.954210325530.055823.916417563260.059423.913116754660.068323.911916703420.078923.915615952690.071723.906415952720.075823.907810265050.070623.904715952710.070623.904415236440.092223.915015235900.075623.893315952760.078123.902217167170.067523.89979697380.101723.907816689230.074723.907511845850.000023.960816674860.091723.87699686970.141123.808917167140.078323.915016674720.997523.98199740620.000023.94589744410.002823.949213513310.004423.949216459960.242222.286111003170.040623.954716754640.094423.910611001260.031923.959411842970.000023.96009744100.007823.945811001990.000023.955811441540.002823.950811004430.000023.972213513720.000023.945811000580.000023.957211001210.015323.97069744130.001123.945811969660.033323.955611975650.033123.959213513390.004423.947511002520.039223.974711003230.027223.957211001840.032223.967511842680.061723.936910009740.000023.953312540250.047823.956716754630.083123.896711842500.031923.960311842790.026723.924211003300.037223.95899740390.001123.947510999940.033623.958311001810.000023.960013513190.002823.945811000240.033623.952811857360.046923.9572综上所述，盈利前100名的司机都是在福州市繁华地区跑全体的行车模式，可见一分耕耘一分收获，只有在凌晨时还坚守岗位的司机才能得到最大的盈利。3.找出该市十个最活跃的中心区域：首先画出全部计程车的行车轨迹图，如下图二 所有计程车行车轨迹方法一：由图二大概可以得知计程车活跃的区域为东经119.2-119.4，北纬2626.15。通过对这个区域进行划分，每隔0.01经度和0.01纬度为一个小块，计算每个小块轨迹点的数目，然后进行排序，寻找出10块密度最大的小块作为最活跃的地区。表2 10个最活跃的地区纬度地点经度26.0626.07万宝商圈119.28119.2926.0726.08五一广场119.3119.3126.1126.12福州黄金大酒店119.31119.3226.0626.07茶亭公园119.3119.3126.0726.08黎明中学119.28119.2926.0826.09晋安二小119.32119.3326.0526.06育智学校119.3119.3126.0726.08福州则徐中学119.31119.3226.0526.06台江步行街119.29119.3026.0726.08福州鼓山中医院119.33119.34可见这十个区域都为福州繁华地段，可见本模型与实际相符合。图三10个最活跃的地区方法二：寻找上车点：行车最活跃的地区并不一定是乘客最多的地方，有可能是多条马路的交叉路口或某个行车必经的路段。于是我们寻找出乘客上车的地点，当一个地点有许多乘客再次上车的话，这就是最符合司机意愿的地方。画出这些地点，如图图四 乘客上车点4. 车辆类型判断（1）数据的处理：一共有计程车数据1000组和非计程车数据1000组，每一组计程车数据中有8个属性分别是车辆ID，经度，纬度，速度 ，方向（0-7，0为正北，顺时针+45度，值+1），有无载客（1表示有载客，0表示无），GPS采集时间，车辆类型。同时在两千多个时间点对这些属性的值进行了统计。然而由于数据庞大，每一辆车就有两千多个时刻点的数据，我们必须对数据进行处理。本文提出两种方法：方法一：特征时间点数据提取，比如8:00am和6:00pm，这是上下班时间。6:00am和10:00pm这就是比较空闲的时间。我们对个时间点进行抽样，每个时间点的数据有各自的特征，从而达到特征提取的效果。然后把不同时间点的车辆ID，经度，纬度等看成是不同的属性，从而有个属性。方法二：对所有时间点的数据求期望，由于期望具有很高的稳定性，同时在一定的程度上可以反映总体的信息，所以求期望是一种好的选择。（2） 关联分析：首先对数据进行中心化处理，方法一有个属性，方法二有8个属性，我们要建立分类器，通过前面的（7）个属性值来判别第最后一个属性即车辆类型（是否为计程车）。然而并不是前面的每一个属性与车辆类型这个属性有关联，于是我们进行关联分析，去除与车辆类型不相关的属性。以方法二为例，得到如下结果： （3）支持向量机SVM：通过关联分析后剩下属性。训练集数据来自与data2的前500 辆车的数据，这个问题实际上属于模式识别问题。于是建立支持向量机的分类器。支持向量机（Sport Vector Machine ,以下简称SVM）是一种基于统计学习理论的模式识别方法。在模式识别等领域获得了广泛的应用。其主要思想是这样：找到一个超平面，使得它能够尽可能多的将两类数据点正确地分开，同时使分开的两类数据点距离分类面最远，如图图五 最佳超平面分类图记（这里 = 500）个已知观测样本为。其中,为计程车，为非计程车。样本线性或非线性可分，我们要找一个最优分类面，其中,，待定，满足如下条件：即有，其中，满足方程的样本称为支持向量。要使两类总体到分类面的距离最大，则有于是建立SVM 的数学模型如下：求得最优值对应的，可得分类函数：本模型是一个二次规划模型。下面把模型化为其对偶问题。定义广义拉格朗日函数其中，。由Karush-Kuhn-Tucker 互补条件，通过对和求偏导可得 得，代入原始拉格朗日函数得其中表示向量的内积最终可以得到如下结果：对于方法一分类正确率为85%，对于方法二分类正确率为75%。模型的检验根据我们所得的几条交通要道，上网查阅资料可知福州市的交通要道与我们所标识出来的路段基本吻合，所以所得出交通要道基本正确，即模型可靠。对于福州市活跃地区的寻找，寻找到了万宝商圈，五一广场福州黄金大酒店，茶亭公园，台江步行街等十个地段，与实际情况相符合。支持向量机分类器的构造，可以看到分类器的正确率达到85%以上，分类效果比较好，具有较高的精度模型的评价1.模型的优点：问题一直接根据生活实际情况建立模型，贴近生活实际，具有实际意义；运用软件分组合并数据，方便MATLAB使用所有数据，再剔除异常数据，这样所得结果的精确度比选用随机数据高；实践表明，该模型得到的结果与福州的实际情况十分吻合，说明该模型可靠。支持向量机分类器是目前分类效果最好的分类器之一，在模式识别领域，该分类算法具有很强的优越性。2.模型的缺点：模型二分类精度并不是非常好，但由于原始数据有部分数据量太少，例如车辆ID为1000678的数据量仅为一个，严重影响判断精度，部分样本的数据有错误也影响分类精度，故而可以先对数据进行分析，剔除不良数据，并人工选择出有代表性的样本，在进行训练、分类，可以大大提高分类精度。附件程序1（寻找生意最好的计程车）for aa=1:2293id, x, y, v, d, l, dates, h, m, s, answers=textread(strcat(D:A,int2str(aa),%f,%f,%f,%f,%f,%f,%s %f:%f:%f,%f); a=h+m./60+s./3600;A=id, x, y, v, d, l,a,answers;c,b=size(A);ss=0;st=0;for i=10:c-10 t=a(i)-a(i-1); if l(i)=1 ss=ss+t; else st=st+t; endendDD(aa)=ss-(1/3)*st; endx,y=sort(DD,descend);yy=y(1:100);for i=1:100 id, x, y, v, d, l, dates, h, m, s, answers=textread(strcat(D:A,int2str(yy(i),%f,%f,%f,%f,%f,%f,%s %f:%f:%f,%f); a=h+m./60+s./3600; len=length(x); AA(i)=a(5); BB(i)=a(len-5); plot(x,y); hold onendyyAABB程序2（寻找最密集的地区）%A=load(1.txt);x1,y1=size(A);G(1:x1,:)=A(:,2:3);B=load(2.txt);x2,y2=size(B);G(x1+1):x1+x2,:)=B(:,2:3);C=load(3.txt);x3,y3=size(C);G(1+x1+x2:x1+x2+x3,:)=C(:,2:3);D=load(4.txt);x4,y4=size(D);G(1+x1+x2+x3:x1+x2+x3+x4,:)=D(:,2:3);E=load(5.txt);x5,y5=size(E);G(1+x1+x2+x3+x4:x1+x2+x3+x4+x5,:)=E(:,2:3);F=load(6.txt);x