共享自行車市場智能預測系統

包依勤 王嘉偉 陳可可

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

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

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

0 引 言

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

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

1 數據的采集

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

2 數據的清理

2.1 Leak漏桶算法

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

2.2 數據處理過程

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

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

3 機器學習算法

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

3.1 KNN算法

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

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

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

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

3.2 算法具體實現

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

3.3 預測分析處理

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

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

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

4 數據可視化

4.1 Mapv技術

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

4.2 可視化部分具體實現

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

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

使用上述熱力圖的數據，最終產生的散點如圖6所示（數字表示該區域的單車數量）。

5 結 語

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

參考文獻

[1]金濤.網絡爬蟲在網頁信息提取中的應用研究[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.機器學習導論[M].北京：機械工業出版社，2017.

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

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

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

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