包依勤 王嘉偉 陳可可

摘 要：文中設(shè)計(jì)了一種基于共享自行車目的地預(yù)測(cè)的智能預(yù)測(cè)系統(tǒng)。該系統(tǒng)對(duì)單位用戶信息進(jìn)行整合，并使用機(jī)器學(xué)習(xí)算法實(shí)現(xiàn)目的地預(yù)測(cè)，每當(dāng)有用戶使用自行車時(shí)，系統(tǒng)將會(huì)對(duì)用戶的目的地進(jìn)行預(yù)測(cè)，從而提前采取措施，對(duì)車輛進(jìn)行調(diào)控。該系統(tǒng)采用網(wǎng)絡(luò)爬蟲技術(shù)獲取數(shù)據(jù)源作為訓(xùn)練集，機(jī)器學(xué)習(xí)算法采用Leak漏桶和KNN算法。通過(guò)機(jī)器學(xué)習(xí)，系統(tǒng)對(duì)共享自行車未來(lái)時(shí)段的車輛密度以圖形化方式進(jìn)行了展示。整個(gè)系統(tǒng)的使用性能良好、準(zhǔn)確率達(dá)92%以上，能夠較好地預(yù)測(cè)自行車下一時(shí)段的密度，從而達(dá)到調(diào)控的目的。

關(guān)鍵詞：KNN算法；共享自行車；車輛調(diào)控；智能預(yù)測(cè)系統(tǒng)

中圖分類號(hào)：TP39；TN914 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2018）09-0-03

0 引 言

未來(lái)共享單車在一線城市市場(chǎng)需求旺盛但容量有限，三四線城市及海外市場(chǎng)是兩大拓展方向。共享單車市場(chǎng)主要集中在一線及部分發(fā)達(dá)二線城市，市場(chǎng)需求非常顯著。由于一線及部分發(fā)達(dá)二線城市市場(chǎng)容量有限，單車數(shù)量將很快達(dá)到飽和，共享單車向三四線城市拓展成為必然，市場(chǎng)需求提升較大。同時(shí)，海外市場(chǎng)因自行車售價(jià)相對(duì)較高，為共享單車走出去也提供了良好的市場(chǎng)機(jī)會(huì)。共享單車雖然發(fā)展前景良好，但車輛管理也存在一些問(wèn)題，共享單車智能動(dòng)態(tài)預(yù)測(cè)分析系統(tǒng)可緩解共享單車調(diào)度不合理等管理問(wèn)題。

本系統(tǒng)在數(shù)據(jù)采集、存儲(chǔ)、計(jì)算、分析和可視化等方面做了大量的工作，通過(guò)對(duì)數(shù)據(jù)的挖掘處理分析，動(dòng)態(tài)預(yù)測(cè)共享單車的停放情況，從而達(dá)到對(duì)共享單車實(shí)時(shí)調(diào)度的目的。該系統(tǒng)的研究具有較高的實(shí)用和商業(yè)價(jià)值。

1 數(shù)據(jù)的采集

數(shù)據(jù)采集采用網(wǎng)絡(luò)爬蟲技術(shù)[1]，從網(wǎng)站上爬取數(shù)據(jù)，具體通過(guò)Python工具實(shí)現(xiàn)。該項(xiàng)目中由于數(shù)據(jù)所需量巨大，故使用Python網(wǎng)絡(luò)爬蟲對(duì)數(shù)據(jù)源進(jìn)行爬取。網(wǎng)絡(luò)爬蟲是一個(gè)自動(dòng)提取網(wǎng)頁(yè)的程序，為搜索引擎從萬(wàn)維網(wǎng)下載網(wǎng)頁(yè)，是搜索引擎的重要組成。傳統(tǒng)爬蟲從一個(gè)或若干初始網(wǎng)頁(yè)的URL開(kāi)始，獲得初始網(wǎng)頁(yè)上的URL，在抓取網(wǎng)頁(yè)的過(guò)程中，不斷從當(dāng)前頁(yè)面上抽取新的URL放入隊(duì)列，直到滿足系統(tǒng)的條件。聚焦爬蟲的工作流程較為復(fù)雜，需根據(jù)一定的網(wǎng)頁(yè)分析算法，過(guò)濾與主題無(wú)關(guān)的鏈接，保留有用的鏈接并將其放入待抓取的URL隊(duì)列。其次將根據(jù)一定的搜索策略從隊(duì)列中選擇下一步要抓取的網(wǎng)頁(yè)URL，并重復(fù)上述過(guò)程，直至達(dá)到系統(tǒng)的某一條件時(shí)停止。另外，所有被爬蟲抓取的網(wǎng)頁(yè)將會(huì)被系統(tǒng)存儲(chǔ)，進(jìn)行一定的分析、過(guò)濾，并建立索引，以便之后的查詢和檢索；對(duì)于聚焦爬蟲來(lái)說(shuō)，這一過(guò)程所得到的分析結(jié)果還可對(duì)以后的抓取過(guò)程給出反饋和指導(dǎo)。相對(duì)于通用網(wǎng)絡(luò)爬蟲，聚焦爬蟲還需解決三個(gè)主要問(wèn)題：對(duì)抓取目標(biāo)的描述或定義；對(duì)網(wǎng)頁(yè)或數(shù)據(jù)的分析與過(guò)濾；對(duì)URL的搜索策略。爬取到的部分?jǐn)?shù)據(jù)見(jiàn)表1所列，表字段含義包括：ordered，單車訂單號(hào)；userid，用戶id；bikeid，單車id；biketype，單車類型；starttime，開(kāi)始騎行時(shí)間；geohashed_start_loc，開(kāi)始地點(diǎn)（geohash編碼）；geohashed_end_loc，停止地址（geohash編碼）。

2 數(shù)據(jù)的清理

2.1 Leak漏桶算法

數(shù)據(jù)的清理采用Leak算法[3]，可對(duì)用戶的不良行為進(jìn)行過(guò)濾，使得該程序的預(yù)測(cè)準(zhǔn)確性和合理性得到大幅提高。Leak漏桶算法是強(qiáng)制一個(gè)常量的輸出速率而不涉及輸入數(shù)據(jù)流的突發(fā)性，當(dāng)輸入空閑時(shí)，該算法不執(zhí)行任何動(dòng)作。就像用一個(gè)底部開(kāi)了洞的漏桶接水一樣，水進(jìn)入漏桶里，桶里的水通過(guò)下面的孔以固定的速率流出，水流入速度過(guò)大會(huì)直接溢出，可看出漏桶算法能強(qiáng)行限制數(shù)據(jù)的傳輸速率，如圖1所示。

2.2 數(shù)據(jù)處理過(guò)程

處理數(shù)據(jù)時(shí)，因騎車信息具有實(shí)時(shí)性，故過(guò)于久遠(yuǎn)的時(shí)間應(yīng)通過(guò)Leak算法漏掉，處理該數(shù)據(jù)時(shí)，將每個(gè)用戶的騎車時(shí)間只保留一個(gè)月，并將用戶同一時(shí)間段進(jìn)行多次同一操作的惡意數(shù)據(jù)進(jìn)行刪除，將多次相似的用戶數(shù)據(jù)采取更小的子集來(lái)代替（代替后可有效降低數(shù)據(jù)集過(guò)大與用戶在某個(gè)集合太集中的問(wèn)題）。

該算法中將每個(gè)用戶ID當(dāng)作一個(gè)集合，針對(duì)每個(gè)用戶在工作日及節(jié)假日的不同習(xí)慣量身定做不同的專屬用戶集，將距離當(dāng)前時(shí)間較早的數(shù)據(jù)集去掉（因騎車信息具有實(shí)時(shí)性，應(yīng)排除較早的時(shí)間對(duì)現(xiàn)在的影響）。在KNN算法中，分別將連續(xù)變量，用戶騎車的起始時(shí)間，起始地，將自行車類型及時(shí)間分離是否為節(jié)假日的離散量作為整體的標(biāo)簽，并將目的地作為類別，數(shù)據(jù)處理結(jié)果見(jiàn)表2所列。

3 機(jī)器學(xué)習(xí)算法

機(jī)器學(xué)習(xí)算法采用KNN算法，由于KNN算法主要依靠周圍有限的鄰近樣本，而不是靠判別類域的方法來(lái)確定所屬類別，因此對(duì)于類域的交叉或重疊較多的待分樣本集來(lái)說(shuō)，KNN方法較其他方法更為適合。

3.1 KNN算法

本項(xiàng)目技術(shù)使用機(jī)器學(xué)習(xí)KNN算法[2]。在KNN算法中，所選擇的鄰居都是已正確分類的對(duì)象。該方法在定類決策上只依據(jù)最鄰近的一個(gè)或幾個(gè)樣本的類別來(lái)決定待分樣本所屬的類別。 KNN方法雖然從原理上依賴于極限定理，但在類別決策時(shí)，只與極少量的相鄰樣本有關(guān)。

在有噪聲的鄰域中，最鄰近域的真?zhèn)慰煽啃暂^差，故該程序中增加了一定鄰域的數(shù)量，通過(guò)對(duì)數(shù)量的判別可增加系統(tǒng)預(yù)測(cè)的準(zhǔn)確度。當(dāng)使用更加通用的K臨近分類器（K>1）時(shí)，近鄰分類器的性能會(huì)有所改善，一些噪聲的臨近點(diǎn)參與投票時(shí)會(huì)被其他臨近點(diǎn)抑制，數(shù)學(xué)上已證明錯(cuò)誤率隨著K值的增加而減小，直到K→∞時(shí)收斂到理想貝葉斯的錯(cuò)誤率。因此理論上適當(dāng)增加K的個(gè)數(shù)能夠增加預(yù)測(cè)準(zhǔn)確率。

在系統(tǒng)中由于考慮到起始和終止地點(diǎn)屬于離散值，改項(xiàng)目中并沒(méi)有采用歐氏距離而是通過(guò)將海明距離加入其中后得到：

該項(xiàng)目中的訓(xùn)練集由于標(biāo)簽過(guò)多，只顯示某個(gè)用戶騎車鐘點(diǎn)的經(jīng)緯度，如圖2所示（橫坐標(biāo)表示緯度，縱坐標(biāo)表示經(jīng)度，坐標(biāo)原點(diǎn)表示為用戶活動(dòng)區(qū)域的范圍）。

3.2 算法具體實(shí)現(xiàn)

由于既有離散的數(shù)據(jù)，又有連續(xù)的數(shù)據(jù)，故先將離散數(shù)據(jù)進(jìn)行歸一化，針對(duì)用戶的起始時(shí)間，將一天的時(shí)間標(biāo)為0～1之間的任意值，但起始地點(diǎn)的經(jīng)緯度卻不能進(jìn)行有效縮放，一方面原因?yàn)榭s小比例過(guò)多，縮小后會(huì)減少預(yù)測(cè)的準(zhǔn)確性，另一方面為縮小后用戶起始點(diǎn)的經(jīng)緯度可能會(huì)帶有很多位小數(shù)，若統(tǒng)一有效位數(shù)會(huì)使得測(cè)試數(shù)據(jù)不準(zhǔn)確?？紤]到每個(gè)用戶騎車范圍很有限，因此起始位置每次只縮放用戶所在的范圍，保證歸一化后數(shù)據(jù)不改變。由于考慮到用戶在同一時(shí)間段（比如每個(gè)工作日）騎車的地點(diǎn)相對(duì)于固定，因此將時(shí)間相近的點(diǎn)分為一個(gè)集合。使用帶權(quán)KNN算法將用戶目的地的三個(gè)最接近同一時(shí)間點(diǎn)（比如早上9∶00整）代進(jìn)權(quán)值的距離計(jì)算（權(quán)值以時(shí)間點(diǎn)為主），預(yù)測(cè)出用戶騎車目地的一個(gè)較小的范圍。

3.3 預(yù)測(cè)分析處理

預(yù)測(cè)結(jié)果進(jìn)行分析處理，采用托梅克連接方法。托梅克連接的是分類的程序，每個(gè)訓(xùn)練樣例的價(jià)值可能是不同的，在使用訓(xùn)練集之前先進(jìn)行預(yù)處理，移除那些被認(rèn)為無(wú)效的案例。托梅克連接點(diǎn)圖如圖3所示。

本程序中采用了托梅克連接技術(shù)移除這些帶有誤導(dǎo)性的點(diǎn)，如果某個(gè)點(diǎn)具有以下3點(diǎn)要求，即該點(diǎn)為托梅克連接，x是y的最鄰近，y是x的最鄰近，x和y類別不同。這些條件是邊界樣例的特征，也是被其他類別的樣例所包圍樣例的特征。

從數(shù)據(jù)中可看出，用戶騎車的時(shí)間，起始地等標(biāo)簽中的幾個(gè)可能會(huì)處于兩個(gè)目的地點(diǎn)的集合之間，這樣的標(biāo)簽既屬于第一集合，和它最鄰近的標(biāo)簽也在第二個(gè)集合中的灰白地帶，可能會(huì)使大多數(shù)的預(yù)測(cè)值偏向于兩個(gè)集合之間，故在該程序中，對(duì)訓(xùn)練集中既屬于集合A也屬于集合B 的集合做出如下處理：如果集合A與集合B的交集中的點(diǎn)少于50個(gè)，則可根據(jù)托梅克連接將其中類別不同的臨近點(diǎn)逐個(gè)去除；若點(diǎn)多余50個(gè)，則可在重新將這個(gè)點(diǎn)劃分為同一個(gè)集合，這樣的做法既不會(huì)使預(yù)測(cè)率下降較多，也不會(huì)使去掉的點(diǎn)過(guò)多。

4 數(shù)據(jù)可視化

4.1 Mapv技術(shù)

Mapv 是一款基于百度地圖的大數(shù)據(jù)可視化開(kāi)源庫(kù)，可用來(lái)展示大量點(diǎn)、線、面的數(shù)據(jù)，每種數(shù)據(jù)也有不同的展示類型，如直接打點(diǎn)、熱力圖、網(wǎng)格、聚合等方式。在實(shí)現(xiàn)過(guò)程中，只需要使用JSAPI，可方便地通過(guò)JavaScript在網(wǎng)站或任何可執(zhí)行JavaScript的高級(jí)瀏覽器中，編寫想要的展示樣式。除此之外，其最大特點(diǎn)是可實(shí)現(xiàn)動(dòng)態(tài)數(shù)據(jù)圖的功能。這也是此項(xiàng)目選擇將Mapv與Echarts技術(shù)相結(jié)合的方式來(lái)實(shí)現(xiàn)可視化的部分。

4.2 可視化部分具體實(shí)現(xiàn)

（1）選取合適模型，為了更好地展示單車的分布情況，擬選擇熱力圖或散點(diǎn)圖來(lái)實(shí)現(xiàn)可視化部分。在熱力圖中，使用了部分北京地區(qū)的預(yù)測(cè)數(shù)據(jù)進(jìn)行測(cè)試。地圖上有標(biāo)記的點(diǎn)為單車預(yù)測(cè)停放位置，顏色較高亮的位置為單車集中分布的區(qū)域。部分測(cè)試結(jié)果數(shù)據(jù)如圖4所示。

（2）通過(guò)測(cè)試數(shù)據(jù)，繪制測(cè)試結(jié)果熱力圖，如圖5所示，從測(cè)試圖可看出，熱力圖的表現(xiàn)效果較差。雖然能夠顯示出某地方的單車的分布，但沒(méi)有具體的數(shù)據(jù)可供參考，因此選擇用“散點(diǎn)圖”模型來(lái)實(shí)現(xiàn)當(dāng)前部分。

使用上述熱力圖的數(shù)據(jù)，最終產(chǎn)生的散點(diǎn)如圖6所示（數(shù)字表示該區(qū)域的單車數(shù)量）。

5 結(jié) 語(yǔ)

該系統(tǒng)的實(shí)現(xiàn)，解決了共享單車重復(fù)利用率的問(wèn)題。共享單車企業(yè)不必再耗費(fèi)大量的人力進(jìn)行“蹲點(diǎn)式”管理，而是通過(guò)預(yù)測(cè)系統(tǒng)對(duì)單車進(jìn)行動(dòng)態(tài)擺放。當(dāng)某地區(qū)的用戶缺乏單車使用時(shí)，通過(guò)該系統(tǒng)的預(yù)測(cè)，有關(guān)部門可提前對(duì)該地進(jìn)行單車投放，使每一輛單車能物盡其用。與其他傳統(tǒng)預(yù)測(cè)系統(tǒng)相比，該系統(tǒng)使用了Mapv技術(shù)增加了可視化模塊，使預(yù)測(cè)結(jié)果直接顯示在地圖上而不是單一的坐標(biāo)位置。使管理人員對(duì)系統(tǒng)調(diào)度位置更加簡(jiǎn)明易懂，即使非相關(guān)專業(yè)員工也可熟練使用。相比傳統(tǒng)預(yù)測(cè)系統(tǒng)具有較高的應(yīng)用及推廣價(jià)值。

參考文獻(xiàn)

[1]金濤.網(wǎng)絡(luò)爬蟲在網(wǎng)頁(yè)信息提取中的應(yīng)用研究[J]. 現(xiàn)代計(jì)算機(jī)，2012 （1）：16-18.

[2]佚名.KNN臨近算法[EB/OL].[2016-07-09]https：//baike.baidu.com/item/%E9%82%BB%E8%BF%91%E7%AE%97%E6%B3%95/1151153？fr=aladdin.

[3]佚名.限流算法之漏桶算法、令牌桶算法[EB/OL].[2014-05-24]http：//blog.csdn.net/tianyaleixiaowu/article/details/74942405.

[4] MIROSLAV K.機(jī)器學(xué)習(xí)導(dǎo)論[M].北京：機(jī)械工業(yè)出版社，2017.

[5] DASARATHY B V.Nearest-neighbor classification techniques [M].Los Alomitos：IEEE Computer Society Press，1991.

[6]孫駿雄.基于網(wǎng)絡(luò)爬蟲的網(wǎng)站信息采集技術(shù)研究[D].大連：大連海事大學(xué)，2014.

[7]陳千.主題網(wǎng)絡(luò)爬蟲關(guān)鍵技術(shù)的研究與應(yīng)用[D].北京：北京理工大學(xué)，2015.

[8]金梅.網(wǎng)絡(luò)爬蟲性能提升與功能擴(kuò)展的研究與實(shí)現(xiàn)[D].長(zhǎng)春：吉林大學(xué)，2012.