共享自行车市场智能预测系统

0 引言

目前共享单车在未来一线城市市场需求旺盛但是容量有限，三四线城市及海外市场是未来的两大拓展方向。目前，共享单车市场主要集中在以一线及部分发达二线城市，市场需求非常显著。一线及部分发达二线城市市场容量有限，单车数量很快将会达到饱和点，向三四线城市拓展成为必然，但市场需求及机会仍有待探索；海外市场自行车售价相对较高，但用户需求旺盛，为共享单车出海提供良好的市场机会；同时，海外市场相对高的客单价将会帮助共享单车企业提高盈利能力。共享单车的前景发展良好，故共享单车管理也一定存在一些问题，那么我们的共享单车智能动态预测分析系统就可以缓解他们的共享单车调度不合理等管理问题。

本系统在数据采集、存储、计算、分析和可视化等做了大量的工作，通过对数据的挖掘处理分析，动态预测共享单车的停放情况，从而达到对共享单车实时调度的目的。该系统的研究具有很好的实用和商业价值。

  1 数据的采集

  数据采集采用网络爬虫技术，从网站上爬取数据，具体通过python工具来实现。

  1.1数据爬取工作原理^[8]

该项目中由于数据所需量巨大，故使用python网络爬虫对数据源进行爬取。网络爬虫是一个自动提取网页的程序，它为搜索引擎从万维网上下载网页，是搜索引擎的重要组成。传统爬虫从一个或若干初始网页的URL开始，获得初始网页上的URL，在抓取网页的过程中，不断从当前页面上抽取新的URL放入队列,直到满足系统的一定停止条件。聚焦爬虫的工作流程较为复杂，需要根据一定的网页分析算法过滤与主题无关的链接，保留有用的链接并将其放入等待抓取的URL队列。然后，它将根据一定的搜索策略从队列中选择下一步要抓取的网页URL，并重复上述过程，直到达到系统的某一条件时停止。另外，所有被爬虫抓取的网页将会被系统存贮，进行一定的分析、过滤，并建立索引，以便之后的查询和检索；对于聚焦爬虫来说，这一过程所得到的分析结果还可能对以后的抓取过程给出反馈和指导。相对于通用网络爬虫，聚焦爬虫还需要解决三个主要问题：对抓取目标的描述或定义；对网页或数据的分析与过滤；对URL的搜索策略。

1.2 数据爬取中采用re（正则表达式）

正则表达式是用于处理字符串的强大工具，它并不是Python的一部分。其他编程语言中也有正则表达式的概念，区别只在于不同的编程语言实现支持的语法数量不同。它拥有自己独特的语法以及一个独立的处理引擎，在提供了正则表达式的语言里，正则表达式的语法都是一样的。如图1所示，展示了使用正则表达式进行匹配的流程

图1 正则表达式匹配原理

正则表达式的大致匹配过程：

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

2.如果每一个字符都能匹配，则匹配成功；一旦有匹配不成功的字符则匹配失败。

3.如果表达式中有量词或边界则采用其他的匹配方式。

1.3 数据爬取中代理的使用

在进行数据爬取的过程中，一些网站有相应的反爬虫措施，例如很多网站会检测某一段时间某个IP的访问次数，如果访问频率太快以至于看起来不像正常访客，它可能就会会禁止这个IP的访问。这个时候就需要设置一些代理服务器，每隔一段时间换一个代理，就算IP被禁止，依然可以换个IP继续爬取。

  2 数据的清理

数据的清理采用leak算法,对用户的不良行为进行过滤，使得该程序的预测准确性和合理性得到大幅提高。

  2.1 leak漏桶算法^[2]

leak漏桶算法是强制一个常量的输出速率而不管输入数据流的突发性,当输入空闲时，该算法不执行任何动作.就像用一个底部开了个洞的漏桶接水一样,水进入到漏桶里,桶里的水通过下面的孔以固定的速率流出,当水流入速度过大会直接溢出,可以看出漏桶算法能强行限制数据的传输速率.如图2所示:

图2 leak算法原理图

2.1 数据处理过程

   该算法中将每个用户ID当作一个集合，针对每个用户在工作日以及节假日的不同习惯来量身定做每一个专属的用户集，并且将距离当前时间下较早的数据集去掉（因为骑车信息具有实时性，应排除较早的时间对现在的影响）。在KNN中，我们分别将连续变量：用户，骑车的起始时间，起始地，将自行车类型以及时间分离为是否是节假日的离散量作为整体的标签，并将目的地作为类别，数据分析如图三所示：

图3 数据分析图

  3 机器学习算法

  机器学习算法采用KNN算法，由于KNN算法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。

3.1 KNN算法^[1]

本项目技术使用机器学习中的KNN算法。最近邻(KNN，K-Nearest Neighbor)分类算法最早由菲克斯（Fix）和霍奇斯（Hodges）提出，但是最早地、系统地分析师由卡渥（Cover）、哈特（Hart）给出的。随后，达萨拉斯（Dasarathy）的书对它进行了详尽的研究。后加权k临近算法是由杜达尼（Dudani）提出。哈特（Hart）描述了最早用于找到训练集的一致子集的技术。托梅克连接的概念由托梅克提出。KNN算法的核心思想是如果一个样本在特征空间中的K个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。由于该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别，并且用户在同一时间段内可以断定目的地为相近目的地。所以可以将训练集中的每个用户的目的地进行统一集合，并进行预测。 KNN方法在类别决策时，只与极少量的相邻样本有关。

KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。

                         图4 KNN算法图

在有噪声的域中，最邻近的域的真伪很不可靠，故该程序中增加了一定的邻域的数量通过对数量的判别可增加系统预测的准确程度。我们知道当我们使用更加通用的K临近分类器（K>1）时，近邻分类器的性能会有所改善，因为一些噪声的临近点参与投票时会被其他临近点抑制，数学上已经证明错误率随着K值的增加在减小，直到k逼近无限大时收敛到理想贝叶斯的错误率。所以至少在理论上，适当增加K的个数能够增加预测准确率。

在系统中由于考虑到起始和终止地点属于离散值，改项目中并没有采用欧氏距离而是通过将海明距离加入其中后得到公式：

图5 带权KNN算法图

3.2 算法具体实现

    在该算法，由于既有离散的数据，又有连续的数据，故我们先将离散的数据进行归一化，针对用户的起始时间很容易将一天的时间标为0至1之间的任意一个值，但起始地点的经纬度却不能进行有效缩放，一方面原因为缩小比例过多，缩小后会减少预测的准确性，另一方面为缩小后用户的起始点的经纬度可能会带有很多位小数，如果使用有效位数的话会使得测试数据不准确。但考虑到一个用户骑车范围很有限，所以起始位置每次只缩放用户所在的那一块很小的范围，保证了归一化后数据没有改变。由于考虑到用户在同一时间段（比如每个工作日）骑车的地点相对于固定，所以将时间点很相近的点分为一个集合。我们使用带权KNN算法将用户目的地的三个最接近同一时间点（比如早上9：00整）来进带行权值的距离计算（权值以时间点为主），预测出用户骑车目地的一个很小的范围。这样的算法也可以用实际情况来解释，比如：一个上班族在工作日每天早上8：00左右骑车到达公司上班，所以当不久以后的某一天该上班族早上8：00左右使用了车辆，我们有很大的理由坚信他是骑车去上班。这样也很好的满足了改预测算法的可解释性。下图为KNN分类器的一个简单的版本。

3.3 预测分析处理

预测结果进行分析处理，采用托梅克连接方法

托梅克连接:所关心的是分类的程序，则每一个训练样例的价值可能是不同的：一些是所代表的类别中典型的，一些稍弱点，但是另外的一些可能完全就是误导。这就是为什么在使用训练集之前先要对它进行预处理：移除那些被认为是无效的案例。例如下图。

图6 带有托梅克连接的点图

本程序中采用了托梅克连接技术来移除这些带有误导性的点，如果一个点具有以下3点要求，即该点为托梅克连接：x是y的最邻近。y是x的最邻近。x和y类别不同。

这些条件是边界样例的特征，也是被其他类别的样例所包围的样例的特征，从训练集中移除这些样例对是有道理的。甚至这些还不够。有时候，移除存在的托梅克连接还会生成新的托梅克连接，因此，这个程序必须执行多次。但存在一个问题：因为令K>1的主要原因就是减轻噪声的消极影响，然而一旦移除托梅克连接，参与投票的近邻个数也会减少，甚至有可能出现使用1近邻分类器就可以取得K近邻分类器在整个原始训练集上所取得的分类性能。所以，虽然经验证明托梅克连接确实改善了整体数据的质量。但使用时因注意一下两种特殊情况：

    当训练集非常小的时候。当一类样本数显著的多于另一类的时候。我们将程序中的所有托梅克连接去除后保证了程序的预测率大幅度提升。

  在数据中可以看出，用户骑车的时间，起始地等标签中的几个可能会处于两个目的地点的集合之间，这样的标签既属于第一个集合并且和它最邻近的标签也在第二个集合中的灰白地带的点，可能会使我们的大多数的预测值也偏向于两个集合之间，这是我们不愿意见到的，故在该程序中，我们将每个既属于集合A也属于集合B 的集合做出以下处理：如果在A集合与B集合的交集中的点少于50个，则可根据托梅克连接将其中类别不同的临近点逐个去除，若点多余50个，则可在重新将这个点划分为同一个集合，这样的做法既不会使预测率下降的太多，也不会使去掉的点过于的多。以下为确认和移除托梅克连接的方法。

 4 数据可视化

这一部分主要采用了Mapv技术实现数据可视化部分。

4.1 Mapv技术

Mapv 是一款基于百度地图的大数据可视化开源库，可以用来展示大量的点、线、面的数据，每种数据也有不同的展示类型，如直接打点、热力图、网格、聚合等方式展示数据。在实现过程中，我们只需要使用JS API，可以很方便的通过JavaScript在网站或者任何可以执行JavaScript的高级浏览器中，编写想要的展示样式。除此之外，其最大的特点是可以实现动态数据图的功能。这也是此项目为什么选择将mapv与echarts技术相结合的方式来实现可视化的部分。

4.2可视化部分具体实现

（1）选取合适模型

为了更好的展示单车的分布情况，我们拟选择热力图或散点图来实现可视化部分。但是在测试中，热力图的表现效果并不是很好。虽然能够显示出某地方的单车的分布，但是没有具体的数据在地图上可供参考，所以我们最终选择了用“散点图+地图”这种模式来实现当前部分。下面将具体介绍如何用散点图实现地图上的单车分布情况。

图7 热力图测试结果

（2）散点图具体实现

要实现散点图的绘制，我们需要以下几个步骤：

1） 画出底板地图

2） 使用mapv的方法构造出一个mapv对象并设置相关属性

3） 通过后台访问数据库中每一辆单车的起始坐标并将其显示在地图上（数字表示该区域的单车数量）。

图8 北京部分城区单车分布图 

  4 总结

该系统的实现，解决了共享单车的重复利用率问题。共享单车企业不必再耗费大量的人力进行“蹲点式”管理，而是通过预测系统对单车进行动态摆放。当某地区的用户缺乏单车使用时，通过该系统的预测有关部门可以提前对该地进行单车投放的操作，使每一辆单车都能物尽其用。与其他传统预测系统相比，该系统使用了Mapv技术增加了可视化模块，使预测结果直接显示在地图上而不是一个坐标位置。使管理人员对系统调度位置更加简明易懂，即使非相关专业员工也可熟练使用。相比传统预测系统具有很高的应用及推广价值

参考文献

[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.机器学习导论.第三章，相似性：最邻近分类器.机械工业出版社.2017.

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

[5]孙骏雄.基于网络爬虫的网站信息采集技术研究[D].大连海事大学，2014

[6]陈千.主题网络爬虫关键技术的研究与应用[D],北京理工大学,2015

[7]金梅.网络爬虫性能提升与功能扩展的研究与实现[D],吉林大学，2012

[8]金涛.网络爬虫在网页信息提取中的应用研究[J],现代计算机：下半月版.2012(1):16-18.