共享自行車市場智能預(yù)測系統(tǒng)

0 引言

目前共享單車在未來一線城市市場需求旺盛但是容量有限，三四線城市及海外市場是未來的兩大拓展方向。目前，共享單車市場主要集中在以一線及部分發(fā)達二線城市，市場需求非常顯著。一線及部分發(fā)達二線城市市場容量有限，單車數(shù)量很快將會達到飽和點，向三四線城市拓展成為必然，但市場需求及機會仍有待探索；海外市場自行車售價相對較高，但用戶需求旺盛，為共享單車出海提供良好的市場機會；同時，海外市場相對高的客單價將會幫助共享單車企業(yè)提高盈利能力。共享單車的前景發(fā)展良好，故共享單車管理也一定存在一些問題，那么我們的共享單車智能動態(tài)預(yù)測分析系統(tǒng)就可以緩解他們的共享單車調(diào)度不合理等管理問題。

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

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

數(shù)據(jù)采集采用網(wǎng)絡(luò)爬蟲技術(shù)，從網(wǎng)站上爬取數(shù)據(jù)，具體通過python工具來實現(xiàn)。

1.1數(shù)據(jù)爬取工作原理[8]

該項目中由于數(shù)據(jù)所需量巨大，故使用python網(wǎng)絡(luò)爬蟲對數(shù)據(jù)源進行爬取。網(wǎng)絡(luò)爬蟲是一個自動提取網(wǎng)頁的程序，它為搜索引擎從萬維網(wǎng)上下載網(wǎng)頁，是搜索引擎的重要組成。傳統(tǒng)爬蟲從一個或若干初始網(wǎng)頁的URL開始，獲得初始網(wǎng)頁上的URL，在抓取網(wǎng)頁的過程中，不斷從當(dāng)前頁面上抽取新的URL放入隊列,直到滿足系統(tǒng)的一定停止條件。聚焦爬蟲的工作流程較為復(fù)雜，需要根據(jù)一定的網(wǎng)頁分析算法過濾與主題無關(guān)的鏈接，保留有用的鏈接并將其放入等待抓取的URL隊列。然后，它將根據(jù)一定的搜索策略從隊列中選擇下一步要抓取的網(wǎng)頁URL，并重復(fù)上述過程，直到達到系統(tǒng)的某一條件時停止。另外，所有被爬蟲抓取的網(wǎng)頁將會被系統(tǒng)存貯，進行一定的分析、過濾，并建立索引，以便之后的查詢和檢索；對于聚焦爬蟲來說，這一過程所得到的分析結(jié)果還可能對以后的抓取過程給出反饋和指導(dǎo)。相對于通用網(wǎng)絡(luò)爬蟲，聚焦爬蟲還需要解決三個主要問題：對抓取目標(biāo)的描述或定義；對網(wǎng)頁或數(shù)據(jù)的分析與過濾；對URL的搜索策略。

1.2 數(shù)據(jù)爬取中采用re（正則表達式）

正則表達式是用于處理字符串的強大工具，它并不是Python的一部分。其他編程語言中也有正則表達式的概念，區(qū)別只在于不同的編程語言實現(xiàn)支持的語法數(shù)量不同。它擁有自己獨特的語法以及一個獨立的處理引擎，在提供了正則表達式的語言里，正則表達式的語法都是一樣的。如圖1所示，展示了使用正則表達式進行匹配的流程

圖1 正則表達式匹配原理

正則表達式的大致匹配過程：

1.依次拿出表達式和文本中的字符比較，

2.如果每一個字符都能匹配，則匹配成功；一旦有匹配不成功的字符則匹配失敗。

3.如果表達式中有量詞或邊界則采用其他的匹配方式。

1.3 數(shù)據(jù)爬取中代理的使用

在進行數(shù)據(jù)爬取的過程中，一些網(wǎng)站有相應(yīng)的反爬蟲措施，例如很多網(wǎng)站會檢測某一段時間某個IP的訪問次數(shù)，如果訪問頻率太快以至于看起來不像正常訪客，它可能就會會禁止這個IP的訪問。這個時候就需要設(shè)置一些代理服務(wù)器，每隔一段時間換一個代理，就算IP被禁止，依然可以換個IP繼續(xù)爬取。

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

數(shù)據(jù)的清理采用leak算法,對用戶的不良行為進行過濾，使得該程序的預(yù)測準(zhǔn)確性和合理性得到大幅提高。

2.1 leak漏桶算法[2]

leak漏桶算法是強制一個常量的輸出速率而不管輸入數(shù)據(jù)流的突發(fā)性,當(dāng)輸入空閑時，該算法不執(zhí)行任何動作.就像用一個底部開了個洞的漏桶接水一樣,水進入到漏桶里,桶里的水通過下面的孔以固定的速率流出,當(dāng)水流入速度過大會直接溢出,可以看出漏桶算法能強行限制數(shù)據(jù)的傳輸速率.如圖2所示:

圖2 leak算法原理圖

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

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

圖3 數(shù)據(jù)分析圖

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

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

3.1 KNN算法[1]

本項目技術(shù)使用機器學(xué)習(xí)中的KNN算法。最近鄰(KNN，K-Nearest Neighbor)分類算法最早由菲克斯（Fix）和霍奇斯（Hodges）提出，但是最早地、系統(tǒng)地分析師由卡渥（Cover）、哈特（Hart）給出的。隨后，達薩拉斯（Dasarathy）的書對它進行了詳盡的研究。后加權(quán)k臨近算法是由杜達尼（Dudani）提出。哈特（Hart）描述了最早用于找到訓(xùn)練集的一致子集的技術(shù)。托梅克連接的概念由托梅克提出。KNN算法的核心思想是如果一個樣本在特征空間中的K個最相鄰的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別，并具有這個類別上樣本的特性。由于該方法在確定分類決策上只依據(jù)最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別，并且用戶在同一時間段內(nèi)可以斷定目的地為相近目的地。所以可以將訓(xùn)練集中的每個用戶的目的地進行統(tǒng)一集合，并進行預(yù)測。 KNN方法在類別決策時，只與極少量的相鄰樣本有關(guān)。

KNN算法中，所選擇的鄰居都是已經(jīng)正確分類的對象。該方法在定類決策上只依據(jù)最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。 KNN方法雖然從原理上也依賴于極限定理，但在類別決策時，只與極少量的相鄰樣本有關(guān)。

圖4 KNN算法圖

在有噪聲的域中，最鄰近的域的真?zhèn)魏懿豢煽浚试摮绦蛑性黾恿艘欢ǖ泥徲虻臄?shù)量通過對數(shù)量的判別可增加系統(tǒng)預(yù)測的準(zhǔn)確程度。我們知道當(dāng)我們使用更加通用的K臨近分類器（K>1）時，近鄰分類器的性能會有所改善，因為一些噪聲的臨近點參與投票時會被其他臨近點抑制，數(shù)學(xué)上已經(jīng)證明錯誤率隨著K值的增加在減小，直到k逼近無限大時收斂到理想貝葉斯的錯誤率。所以至少在理論上，適當(dāng)增加K的個數(shù)能夠增加預(yù)測準(zhǔn)確率。

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

圖5 帶權(quán)KNN算法圖

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

在該算法，由于既有離散的數(shù)據(jù)，又有連續(xù)的數(shù)據(jù)，故我們先將離散的數(shù)據(jù)進行歸一化，針對用戶的起始時間很容易將一天的時間標(biāo)為0至1之間的任意一個值，但起始地點的經(jīng)緯度卻不能進行有效縮放，一方面原因為縮小比例過多，縮小后會減少預(yù)測的準(zhǔn)確性，另一方面為縮小后用戶的起始點的經(jīng)緯度可能會帶有很多位小數(shù)，如果使用有效位數(shù)的話會使得測試數(shù)據(jù)不準(zhǔn)確。但考慮到一個用戶騎車范圍很有限，所以起始位置每次只縮放用戶所在的那一塊很小的范圍，保證了歸一化后數(shù)據(jù)沒有改變。由于考慮到用戶在同一時間段（比如每個工作日）騎車的地點相對于固定，所以將時間點很相近的點分為一個集合。我們使用帶權(quán)KNN算法將用戶目的地的三個最接近同一時間點（比如早上9：00整）來進帶行權(quán)值的距離計算（權(quán)值以時間點為主），預(yù)測出用戶騎車目地的一個很小的范圍。這樣的算法也可以用實際情況來解釋，比如：一個上班族在工作日每天早上8：00左右騎車到達公司上班，所以當(dāng)不久以后的某一天該上班族早上8：00左右使用了車輛，我們有很大的理由堅信他是騎車去上班。這樣也很好的滿足了改預(yù)測算法的可解釋性。下圖為KNN分類器的一個簡單的版本。

假設(shè)我們有一種度量屬性之間相似性的機制，以此來決定x的類別。

1.在訓(xùn)練樣本中，找到x的k個最近鄰（與x最相似的樣例）。

2.假如ci是這k個最近鄰中包含最多的類別。

3.則x的類別即為ci。

3.3 預(yù)測分析處理

預(yù)測結(jié)果進行分析處理，采用托梅克連接方法

托梅克連接:所關(guān)心的是分類的程序，則每一個訓(xùn)練樣例的價值可能是不同的：一些是所代表的類別中典型的，一些稍弱點，但是另外的一些可能完全就是誤導(dǎo)。這就是為什么在使用訓(xùn)練集之前先要對它進行預(yù)處理：移除那些被認為是無效的案例。例如下圖。

圖6 帶有托梅克連接的點圖

本程序中采用了托梅克連接技術(shù)來移除這些帶有誤導(dǎo)性的點，如果一個點具有以下3點要求，即該點為托梅克連接：x是y的最鄰近。y是x的最鄰近。x和y類別不同。

這些條件是邊界樣例的特征，也是被其他類別的樣例所包圍的樣例的特征，從訓(xùn)練集中移除這些樣例對是有道理的。甚至這些還不夠。有時候，移除存在的托梅克連接還會生成新的托梅克連接，因此，這個程序必須執(zhí)行多次。但存在一個問題：因為令K>1的主要原因就是減輕噪聲的消極影響，然而一旦移除托梅克連接，參與投票的近鄰個數(shù)也會減少，甚至有可能出現(xiàn)使用1近鄰分類器就可以取得K近鄰分類器在整個原始訓(xùn)練集上所取得的分類性能。所以，雖然經(jīng)驗證明托梅克連接確實改善了整體數(shù)據(jù)的質(zhì)量。但使用時因注意一下兩種特殊情況：

當(dāng)訓(xùn)練集非常小的時候。當(dāng)一類樣本數(shù)顯著的多于另一類的時候。我們將程序中的所有托梅克連接去除后保證了程序的預(yù)測率大幅度提升。

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

輸入：N個樣例的一個訓(xùn)練集。

1.令i=1，T為一個空集。

2.令x是第i個訓(xùn)練樣例，y是x的最近鄰。

3.如果x和y屬于同一個類別，則轉(zhuǎn)到5.

4.如果x是y的最近鄰，則令。

5.令i=i+1。如果，則轉(zhuǎn)到2。

6.從訓(xùn)練集中將所有在T中的樣例全部移除。

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

這一部分主要采用了Mapv技術(shù)實現(xiàn)數(shù)據(jù)可視化部分。

4.1 Mapv技術(shù)

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

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

（1）選取合適模型

為了更好的展示單車的分布情況，我們擬選擇熱力圖或散點圖來實現(xiàn)可視化部分。但是在測試中，熱力圖的表現(xiàn)效果并不是很好。雖然能夠顯示出某地方的單車的分布，但是沒有具體的數(shù)據(jù)在地圖上可供參考，所以我們最終選擇了用“散點圖+地圖”這種模式來實現(xiàn)當(dāng)前部分。下面將具體介紹如何用散點圖實現(xiàn)地圖上的單車分布情況。

圖7?熱力圖測試結(jié)果

（2）散點圖具體實現(xiàn)

要實現(xiàn)散點圖的繪制，我們需要以下幾個步驟：

1）?畫出底板地圖

2）?使用mapv的方法構(gòu)造出一個mapv對象并設(shè)置相關(guān)屬性

3）?通過后臺訪問數(shù)據(jù)庫中每一輛單車的起始坐標(biāo)并將其顯示在地圖上（數(shù)字表示該區(qū)域的單車數(shù)量）。

圖8?北京部分城區(qū)單車分布圖

4 總結(jié)

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

參考文獻

[1]?KNN臨近算法.https://baike.baidu.com/item/%E9%82%BB%E8%BF%91%E7%AE%97%E6%B3%95/1151153?fr=aladdin.

[2] 限流算法之漏桶算法、令牌桶算法.http://blog.csdn.net/tianyaleixiaowu/article/details/74942405.

[3]?Miroslav Kubat.機器學(xué)習(xí)導(dǎo)論.第三章，相似性：最鄰近分類器.機械工業(yè)出版社.2017.

[4]?Dasarathy,B. V.(1991).Nearest-neighbor classification techniques.Los Alomitos:IEEE Computer Society Press.

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

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

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

[8]金濤.網(wǎng)絡(luò)爬蟲在網(wǎng)頁信息提取中的應(yīng)用研究[J],現(xiàn)代計算機：下半月版.2012(1):16-18.

數(shù)據(jù)挖掘 機器學(xué)習(xí)

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網(wǎng)站將在24小時內(nèi)刪除侵權(quán)內(nèi)容。