包依勤 王嘉偉 陳可可

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

關鍵詞：KNN算法；共享自行車；車輛調控；智能預測系統(tǒng)

中圖分類號：TP39；TN914 文獻標識碼：A 文章編號：2095-1302（2018）09-0-03

0 引 言

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

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

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

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

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

2.1 Leak漏桶算法

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

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

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

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

3 機器學習算法

機器學習算法采用KNN算法，由于KNN算法主要依靠周圍有限的鄰近樣本，而不是靠判別類域的方法來確定所屬類別，因此對于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。

3.1 KNN算法

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

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

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

該項目中的訓練集由于標簽過多，只顯示某個用戶騎車鐘點的經(jīng)緯度，如圖2所示（橫坐標表示緯度，縱坐標表示經(jīng)度，坐標原點表示為用戶活動區(qū)域的范圍）。

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

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

3.3 預測分析處理

預測結果進行分析處理，采用托梅克連接方法。托梅克連接的是分類的程序，每個訓練樣例的價值可能是不同的，在使用訓練集之前先進行預處理，移除那些被認為無效的案例。托梅克連接點圖如圖3所示。

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

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

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

4.1 Mapv技術

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

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

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

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

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

5 結 語

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

參考文獻

[1]金濤.網(wǎng)絡爬蟲在網(wǎng)頁信息提取中的應用研究[J]. 現(xiàn)代計算機，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.機器學習導論[M].北京：機械工業(yè)出版社，2017.

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

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

[7]陳千.主題網(wǎng)絡爬蟲關鍵技術的研究與應用[D].北京：北京理工大學，2015.

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