計(jì)程車(chē)路線(xiàn)挖掘

?分務(wù)屯工濺診說(shuō)XFuilan orTechnolnEy課程設(shè)計(jì)說(shuō)明書(shū)(論文)題目 交通軌跡數(shù)據(jù)模式提取 課程名稱(chēng) 數(shù)據(jù)挖掘 專(zhuān) 業(yè) 信息與計(jì)算科學(xué)學(xué)生姓名崔卓須(3101301308)姚順蘭(3101301304)陳曉強(qiáng)(3101301230)設(shè)計(jì)地點(diǎn) 數(shù)理系機(jī)房 指導(dǎo)教師 賀文武 摘要一個(gè)城市的交通是一個(gè)非常龐大復(fù)雜的系統(tǒng)，如果對(duì)于交通系統(tǒng)的調(diào)度管理適當(dāng)?shù)脑?huà)，保持道路通暢，能為我們的生活提供很多的方便。然而交通混亂成為了北京上海廣州等大城市的一塊心病，每當(dāng)上下班高峰期必然堵車(chē)。從而建立關(guān)于交通的數(shù)學(xué)模型，與我們的生活息息相關(guān)。對(duì)于問(wèn)題一，尋找營(yíng)業(yè)額高于平均水平的司機(jī)的行車(chē)模式，無(wú)非就是找出一天中載客時(shí)間最長(zhǎng)并且放空時(shí)間最短的出租車(chē)，在這種模式下，從而達(dá)到利益最大化。于是找出他們的行車(chē)軌跡和出車(chē)和收車(chē)時(shí)間，指導(dǎo)其他司機(jī)。對(duì)于問(wèn)題二，尋找十個(gè)最活躍的中心區(qū)域，本文提出兩種方法，方法一：首先通過(guò)經(jīng)緯度對(duì)福州市區(qū)進(jìn)行劃分。每隔0.01經(jīng)度和0.01緯度劃分為一個(gè)小塊，統(tǒng)計(jì)每個(gè)小塊中計(jì)程車(chē)軌跡點(diǎn)，找出10塊密度最大的小塊，這些小塊就是最活躍的地區(qū)。方法二：然而上面的結(jié)果可能是交叉路口或行駛必經(jīng)之地，并不是乘客最多的地方，于是提出另一種最活躍地區(qū)的尋找方法，即統(tǒng)計(jì)所以計(jì)程車(chē)數(shù)據(jù)中乘客上車(chē)次數(shù)出現(xiàn)最多的區(qū)域?yàn)樽罨钴S區(qū)域。對(duì)于問(wèn)題三，一共有計(jì)程車(chē)數(shù)據(jù)1000組和非計(jì)程車(chē)數(shù)據(jù)1000組，每一組計(jì)程車(chē)數(shù)據(jù)中有8個(gè)屬性，同時(shí)在兩千多個(gè)時(shí)間點(diǎn)對(duì)這些屬性的值進(jìn)行了統(tǒng)計(jì)。然而由于數(shù)據(jù)龐大，我們必須對(duì)數(shù)據(jù)進(jìn)行處理。本文提出兩種方法：特征時(shí)間點(diǎn)數(shù)據(jù)提取法和求期望法。然后構(gòu)建支持向量機(jī)（SVM）分類(lèi)器，從而判斷車(chē)輛類(lèi)型。關(guān)鍵字：交通，計(jì)程車(chē)，特征提取，支持向量機(jī)（SVM）問(wèn)題重述Datal.rar文件為某市部分出租車(chē)某天的行車(chē)軌跡（通過(guò)車(chē)載GPS設(shè)備獲得），解壓后的文件夾中每個(gè)文件對(duì)應(yīng)一輛車(chē)一天的GPS數(shù)據(jù)。通常每30秒左右采集一次，對(duì)應(yīng)文件中的一行，每行包含車(chē)輛的9個(gè)屬性，用逗號(hào)分隔，分別是:車(chē)輛ID,區(qū)域ID（備用），經(jīng)度，緯度，速度，方向（0-7,0為正北，順時(shí)針+45度，值+1）,有無(wú)載客（1表示有載客，0表示無(wú)），GPS采集時(shí)間，車(chē)輛類(lèi)型（41表示出租車(chē)，非41表示其它營(yíng)運(yùn)車(chē)輛）。1.假設(shè)你是出租車(chē)公司的管理者，怎樣利用給定數(shù)據(jù)尋找有趣模式，以提高服務(wù)與效益？（1） 尋找營(yíng)業(yè)額高于平均水平的司機(jī)的行車(chē)模式，用以指導(dǎo)其他司機(jī)；（2） 找出該市十個(gè)最活躍的中心區(qū)域，在這些區(qū)域中可能有更多的人需要坐出租車(chē)。3.Data2.rar文件中給出某市1000輛出租車(chē)和1000輛其它營(yíng)運(yùn)車(chē)輛某天的行車(chē)軌跡（數(shù)據(jù)格式和Data1.rar相同）。請(qǐng)根據(jù)行車(chē)模式判斷車(chē)輛類(lèi)型（是出租車(chē)還是其它營(yíng)運(yùn)車(chē)輛）。（本文選取題目的問(wèn)題一和問(wèn)題三）問(wèn)題分析對(duì)于問(wèn)題一，尋找營(yíng)業(yè)額高于平均水平的司機(jī)的行車(chē)模式，無(wú)非就是找出一天中載客時(shí)間最長(zhǎng)并且放空時(shí)間最短的出租車(chē)，在這種模式下，從而達(dá)到利益最大化。于是找出他們的行車(chē)軌跡和出車(chē)和收車(chē)時(shí)間，指導(dǎo)其他司機(jī)。對(duì)于問(wèn)題二，尋找十個(gè)最活躍的中心區(qū)域，本文提出兩種方法，方法一：首先通過(guò)經(jīng)緯度對(duì)福州市區(qū)進(jìn)行劃分。每隔0.01經(jīng)度和0.01緯度劃分為一個(gè)小塊，統(tǒng)計(jì)每個(gè)小塊中計(jì)程車(chē)軌跡點(diǎn)，找出10塊密度最大的小塊，這最活躍的地區(qū)。方法二：然而上面的結(jié)果可能是交叉路口或行駛必經(jīng)之地，并不是乘客最多的地方，于是提出另一種最活躍地區(qū)的尋找方法，即統(tǒng)計(jì)所以計(jì)程車(chē)數(shù)據(jù)中乘客上車(chē)次數(shù)出現(xiàn)最多的區(qū)域?yàn)樽罨钴S區(qū)域。對(duì)于問(wèn)題三，一共有計(jì)程車(chē)數(shù)據(jù)1000組和非計(jì)程車(chē)數(shù)據(jù)1000組，每一組計(jì)程車(chē)數(shù)據(jù)中有8個(gè)屬性，同時(shí)在兩千多個(gè)時(shí)間點(diǎn)對(duì)這些屬性的值進(jìn)行了統(tǒng)計(jì)。然而由于數(shù)據(jù)龐大，我們必須對(duì)數(shù)據(jù)進(jìn)行處理。本文提出兩種方法：特征時(shí)間點(diǎn)數(shù)據(jù)提取法和求期望法。然后構(gòu)建支持向量機(jī)（SVM）分類(lèi)器，從而判斷車(chē)輛類(lèi)型。模型建立1?基于密度的離群點(diǎn)檢測(cè):對(duì)數(shù)據(jù)進(jìn)行異常檢測(cè)，去掉異常的數(shù)據(jù)。從基于密度的觀(guān)點(diǎn)來(lái)說(shuō)，離群點(diǎn)是在低密度區(qū)域中的對(duì)象。一個(gè)對(duì)象的離群點(diǎn)得分是該對(duì)象

周?chē)芏鹊哪妗；诿芏鹊碾x群點(diǎn)檢測(cè)與基于鄰進(jìn)度的離群點(diǎn)檢測(cè)密切相關(guān)，因?yàn)槊芏韧ǔＳ绵徑榷x。一種常用的定義密度的方法是，定義密度為到k個(gè)最近鄰的平均距離的倒數(shù)。如果該距離小，則密度高，反之亦然。逆距離:density(x,density(x,k)= yeN(x,k)distance(x,y)'V(x,k)-1其中，N（x,k）是包含x的k-最近鄰的集合，|N（x,k）是該集合的大小，而y是個(gè)最近鄰。2.尋找營(yíng)業(yè)額高于平均水平的司機(jī)的行車(chē)模式：無(wú)非就是找出一天中載客時(shí)間最長(zhǎng)并且放空時(shí)間最短的出租車(chē)，計(jì)程車(chē)雖然是按路程收費(fèi)，但是在紅燈或堵車(chē)時(shí)是按時(shí)間收費(fèi)的，所以在本文中用載客時(shí)間來(lái)衡量盈利，同時(shí)計(jì)程車(chē)在放空車(chē)時(shí)也會(huì)浪費(fèi)郵費(fèi)。因此我們?cè)O(shè)載客時(shí)間為si，放空時(shí)間為s2，貝UF=F=(si-wxs2)十si+s224w為權(quán)重（取1/3），當(dāng)F最大時(shí)，最為盈利。在2290輛計(jì)程車(chē)的數(shù)據(jù)中找出F值排名前100的計(jì)程車(chē)，畫(huà)出他們的行車(chē)軌跡如下：圖一盈利前100圖一盈利前100名行車(chē)軌跡圖由圖一可知，他們基本上是在福州市繁華地段行駛。我們還可以得到他們的上班時(shí)間和收車(chē)時(shí)間如下表1表1盈利前100名的上下班時(shí)間車(chē)牌號(hào)上班時(shí)間收車(chē)時(shí)間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.9586

11002960.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.9475

11002520.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名的司機(jī)都是在福州市繁華地區(qū)跑全體的行車(chē)模式,可見(jiàn)一分耕耘一分收獲，只有在凌晨時(shí)還堅(jiān)守崗位的司機(jī)才能得到最大的盈利。3?找出該市十個(gè)最活躍的中心區(qū)域：首先畫(huà)出全部計(jì)程車(chē)的行車(chē)軌跡圖，如下圖二所有計(jì)程車(chē)行車(chē)軌跡方法一：由圖二大概可以得知計(jì)程車(chē)活躍的區(qū)域?yàn)闁|經(jīng)119.2119.4，北緯26—26.15。通過(guò)對(duì)這個(gè)區(qū)域進(jìn)行劃分，每隔0.01經(jīng)度和0.01緯度為一個(gè)小塊，計(jì)算每個(gè)小塊軌跡點(diǎn)的數(shù)目，然后進(jìn)行排序，尋找出10塊密度最大的小塊作為最活躍的地區(qū)。

江厝路彌路沿即西湖.蛇山大酒忑福押尊愴.華美達(dá)大飯匡g褊屏山公回大夢(mèng)山?天城⑺區(qū)外貿(mào)中心酒匡棉新東踣忘村稻［E畝路?福福粘車(chē)飛北站福州世紀(jì)金遞大飯匡洋下河畝前此工路路東街口于山鳳囂A2村■■\H7F5QM二寶禪寸望龍園*令群江厝路彌路沿即西湖.蛇山大酒忑福押尊愴.華美達(dá)大飯匡g褊屏山公回大夢(mèng)山?天城⑺區(qū)外貿(mào)中心酒匡棉新東踣忘村稻［E畝路?福福粘車(chē)飛北站福州世紀(jì)金遞大飯匡洋下河畝前此工路路東街口于山鳳囂A2村■■\H7F5QM二寶禪寸望龍園*令群眾東路金牛山丈林山*金牛U必回籀 衛(wèi)魅公園*褊卿萬(wàn)達(dá)威斯汀酒豬中洲召H國(guó)誼丸酒忑"番福新蹈丸酒迂福啊市里拉國(guó)爲(wèi)西涪Jk百陞-閩旅園X連潘村上濟(jì)村國(guó)燹樂(lè)路a緯度地點(diǎn)經(jīng)度26.06~26.07萬(wàn)寶商圈119.28~119.2926.07~26.08五一廣場(chǎng)119.3~119.3126.11~26.12福州黃金大酒店119.31~119.3226.06~26.07茶亭公園119.3~119.3126.07~26.08黎明中學(xué)119.28~119.2926.08~26.09晉安二小119.32~119.3326.05~26.06育智學(xué)校119.3~119.3126.07~26.08福州則徐中學(xué)119.31~119.3226.05~26.06臺(tái)江步行街119.29~119.3026.07~26.08福州鼓山中醫(yī)院119.33~119.34可見(jiàn)這十個(gè)區(qū)域都為福州繁華地段，可見(jiàn)本模型與實(shí)際相符合。圖三10個(gè)最活躍的地區(qū)方法二：尋找上車(chē)點(diǎn)：行車(chē)最活躍的地區(qū)并不一定是乘客最多的地方，有可能是多條馬路的交叉路口或某個(gè)行車(chē)必經(jīng)的路段。于是我們尋找出乘客上車(chē)的地點(diǎn)，當(dāng)一個(gè)地點(diǎn)有許多乘客再次上車(chē)的話(huà)，這就是最符合司機(jī)意愿的地方。畫(huà)出這些地點(diǎn),如圖圖四乘客上車(chē)點(diǎn)4.車(chē)輛類(lèi)型判斷（1） 數(shù)據(jù)的處理：一共有計(jì)程車(chē)數(shù)據(jù)1000組和非計(jì)程車(chē)數(shù)據(jù)1000組，每一組計(jì)程車(chē)數(shù)據(jù)中有8個(gè)屬性分別是｛車(chē)輛ID,經(jīng)度，緯度，速度，方向（0-7,0為正北，順時(shí)針+45度，值+1）,有無(wú)載客（1表示有載客，0表示無(wú)），GPS采集時(shí)間，車(chē)輛類(lèi)型｝。同時(shí)在兩千多個(gè)時(shí)間點(diǎn)對(duì)這些屬性的值進(jìn)行了統(tǒng)計(jì)。然而由于數(shù)據(jù)龐大，每一輛車(chē)就有兩千多個(gè)時(shí)刻點(diǎn)的數(shù)據(jù)，我們必須對(duì)數(shù)據(jù)進(jìn)行處理。本文提出兩種方法：方法一：特征時(shí)間點(diǎn)數(shù)據(jù)提取，比如8:00am和6:00pm,這是上下班時(shí)間。6:00am和10:00pm這就是比較空閑的時(shí)間。我們對(duì)n個(gè)時(shí)間點(diǎn)進(jìn)行抽樣，每個(gè)時(shí)間點(diǎn)的數(shù)據(jù)有各自的特征，從而達(dá)到特征提取的效果。然后把不同時(shí)間點(diǎn)的車(chē)輛ID，經(jīng)度，緯度等看成是不同的屬性，從而有n*7+1個(gè)屬性。方法二：對(duì)所有時(shí)間點(diǎn)的數(shù)據(jù)求期望，由于期望具有很高的穩(wěn)定性，同時(shí)在一定的程度上可以反映總體的信息，所以求期望是一種好的選擇。（2） 關(guān)聯(lián)分析：首先對(duì)數(shù)據(jù)進(jìn)行中心化處理，方法一有n*7+1個(gè)屬性，方法二有8個(gè)屬性，我們要建立分類(lèi)器，通過(guò)前面的n*7（7）個(gè)屬性值來(lái)判別第最后一個(gè)屬性即車(chē)輛類(lèi)型（是否為計(jì)程車(chē)）。然而并不是前面的每一個(gè)屬性與車(chē)輛類(lèi)型這個(gè)屬性有關(guān)聯(lián)，于是我們進(jìn)行關(guān)聯(lián)分析，去除與車(chē)輛類(lèi)型不相關(guān)的屬性。以方法二為例，得到如下結(jié)果：經(jīng)度，緯度，速度,GPS采集時(shí)間h車(chē)輛屬性（3）支持向量機(jī)SVM：通過(guò)關(guān)聯(lián)分析后剩下屬性。訓(xùn)練集數(shù)據(jù)來(lái)自與data2的前500輛車(chē)的數(shù)據(jù)，這個(gè)問(wèn)題實(shí)際上屬于模式識(shí)別問(wèn)題。于是建立支持向量機(jī)的分類(lèi)器。支持向量機(jī)（SportVectorMachine，以下簡(jiǎn)稱(chēng)SVM）是一種基于統(tǒng)計(jì)學(xué)習(xí)理論的模式識(shí)別方法。在模式識(shí)別等領(lǐng)域獲得了廣泛的應(yīng)用。其主要思想是這樣：找到一個(gè)超平面，使得它能夠盡可能多的將兩類(lèi)數(shù)據(jù)點(diǎn)正確地分開(kāi)，同時(shí)使分開(kāi)的兩類(lèi)數(shù)據(jù)點(diǎn)距離分類(lèi)面最遠(yuǎn)，如圖

圖五最佳超平面分類(lèi)圖記n(這里n=500)個(gè)已知觀(guān)測(cè)樣本為(t,g)(,g)???,(t,g)。其11 2 2 nn中，teR5,g二1為計(jì)程車(chē)，g=-1為非計(jì)程車(chē)。樣本線(xiàn)性或非線(xiàn)性可分，我們TOC\o"1-5"\h\zi i i要找一個(gè)最優(yōu)分類(lèi)面wTx+b=0，其中w,tgR5,beR,w,b，待定，滿(mǎn)足如下條件:wTt+b>1,g=1時(shí)i iwt+b<-1,g=-1時(shí)i i即有g(shù)(wt-b)>1，其中，滿(mǎn)足方程w"+b=±1的樣本稱(chēng)為支持向量。ii i要使兩類(lèi)總體到分類(lèi)面的距離最大，則有m訕=min2|w|1于是建立SVM的數(shù)學(xué)模型如下:min2Hl2s.s.t. gi-+b>1,i=1,2,…,ni求得最優(yōu)值對(duì)應(yīng)的w*,b*，可得分類(lèi)函數(shù):g(g(x)=sgn*tx+b)本模型是一個(gè)二次規(guī)劃模型。下面把模型化為其對(duì)偶問(wèn)題。定義廣義拉格朗日函數(shù)L(w,a)=—w2+丫a2iiii ii=1由Karush-Kuhn-Tucker互補(bǔ)條件，通過(guò)對(duì)w和b求偏導(dǎo)可得dL—w—dw6Ldb6LdbHagii得w-工agt,工ag—0，代入原始拉格朗日函數(shù)得iii iii—1 i—1L—Ha-1工另aagg(?t)i2 ijijiji—1 i—1j—1其中(x-x)表示向量的內(nèi)積ij最終可以得到如下結(jié)果：對(duì)于方法一分類(lèi)正確率為85%,對(duì)于方法二分類(lèi)正確率為75%。模型的檢驗(yàn)根據(jù)我們所得的幾條交通要道，上網(wǎng)查閱資料可知福州市的交通要道與我們所標(biāo)識(shí)出來(lái)的路段基本吻合，所以所得出交通要道基本正確，即模型可靠。對(duì)于福州市活躍地區(qū)的尋找，尋找到了萬(wàn)寶商圈，五一廣場(chǎng)福州黃金大酒店，茶亭公園，臺(tái)江步行街等十個(gè)地段，與實(shí)際情況相符合。支持向量機(jī)分類(lèi)器的構(gòu)造，可以看到分類(lèi)器的正確率達(dá)到85%以上，分類(lèi)效果比較好，具有較高的精度模型的評(píng)價(jià)1?模型的優(yōu)點(diǎn)：?jiǎn)栴}一直接根據(jù)生活實(shí)際情況建立模型，貼近生活實(shí)際，具有實(shí)際意義；運(yùn)用軟件分組合并數(shù)據(jù)，方便MATLAB使用所有數(shù)據(jù)，再剔除異常數(shù)據(jù)，這樣所得結(jié)果的精確度比選用隨機(jī)數(shù)據(jù)高；實(shí)踐表明，該模型得到的結(jié)果與福州的實(shí)際情況十分吻合，說(shuō)明該模型可靠。支持向量機(jī)分類(lèi)器是目前分類(lèi)效果最好的分類(lèi)器之一，在模式識(shí)別領(lǐng)域，該分類(lèi)算法具有很強(qiáng)的優(yōu)越性。2.模型的缺點(diǎn)：模型二分類(lèi)精度并不是非常好，但由于原始數(shù)據(jù)有部分?jǐn)?shù)據(jù)量太少，例如車(chē)輛ID為1000678的數(shù)據(jù)量?jī)H為一個(gè)，嚴(yán)重影響判斷精度，部分樣本的數(shù)據(jù)有錯(cuò)誤也影響分類(lèi)精度，故而可以先對(duì)數(shù)據(jù)進(jìn)行分析，剔除不良數(shù)據(jù)，并人工選擇出有代表性的樣本，在進(jìn)行訓(xùn)練、分類(lèi)，可以大大提高分類(lèi)精度。附件程序1(尋找生意最好的計(jì)程車(chē))foraa=1:2293[id, 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;fori=10:c-10t=a(i)-a(i-1);ifl(i)==1ss=ss+t;elsest=st+t;endendDD(aa)=ss-(1/3)*st;end[x,y]=sort(DD,'descend');yy=y(1:100);fori=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);holdonendyyAABB程序2（尋找最密集的地區(qū)）%%A=load('l.txt');[xl,yl]=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');[x6,y6]=size(F);G(1+x1+x2+x3+x4+x5:x1+x2+x3+x4+x5+x6,:)=F(:,[2:3]);%%%%y=119.2:0.01:119.4;x=26:0.01:26.15;A=zeros(15,20);fori=1:15forj=1:20forz=1:5070163ifG(z,1)