英语原文共 6 页，剩余内容已隐藏，支付完成后下载完整资料
基于马尔可夫链的自行车共享模型
系统
摘要
自行车共享系统最近在大多数城市变得无处不在，作为一种环保替代品到其他交通工具。对自行车共享服务的最佳管理原则上会从系统底层数学模型的可用性中受益。因此，在本文中，我们提出了一种基于马尔可夫链的方法来建立自行车共享系统的模型，我们相信这种方法有潜力开发替代方法来实现自行车共享系统中的经典控制行为（例如，在实施替代方案 搬迁策略或规划广告活动）。所提出的方法在美国波士顿的自行车共享系统的真实数据上进行了验证，并初步说明了该模型在论文中的第一个应用。
I简介
自行车分享计划现在在大多数城市都可以使用[1]，[2]，[3]，[4]; 例如巴黎的Veacute;lib#39;，巴塞罗那的Bicing，华盛顿特区首都Bikeshare和上海永久自行车。 一个很好的概述可以从[5]中获得其中的参考。 它们不仅被视为一个整体还可以用来减轻公共交通网络中的组件拥挤和肥胖问题，见[6]，[7]，[8]，[9]，但也作为防治城市污染的基本工具，见[10]，[11]，[12]。 他们也被认为是迈向一步解决智能交通最后一公里问题1系统，参见[13]。 有关IT的概述，另请参阅[14]北美地区的自行车分享计划和[15]电动自行车共享相关领域的仿真研究。鉴于最近的这种扩散，还有一个在开发管理自行车共享的最佳方式系统的兴趣。 事实上，正如[2]中指出的，大多数自行车共享系统必须依靠市政府的公共资金或其他公共资源，因为客户收费不足以匹配资本成本加上年度运营成本。因此，人们对设计智能方式有着浓厚的兴趣比如降低运营成本，例如降低成本：使用人工卡车手动搬迁自行车为了平衡供求之间的差异（见[16]）；或使收入最大化通过使用自行车获得广告获得。
我们的兴趣在于开发一个模型来捕捉自行车共享系统的宏观聚合特性。从这个角度来看，我们主要有兴趣回答涉及身份识别的高级问题的在自行车网络中的主要作用，或者自行车站相对于其他人有多重要。 我们的最终目标是最终支持自行车共享管理者实施计划和控制行动旨在改善以主动方式自行车网络的效率（即，预测战略变革的预期结果在自行车网络中）。 总体问题尤其突出如果有人打算在这个模型中嵌入大的话，这将是一个挑战。准确实时的从自行车网络提供数据量。 作为一个例子，我们在本文中使用从美国波士顿的自行车共享网络收集的数据2。
为此，我们的出发点是最近提出的基于马尔可夫链的框架捕捉宏观城市动态，即[17]。 那篇论文采用了图表理论和马尔可夫链理念来揭示一些不平凡的东西城市交通模式和支持工程师实用的工具来解决一些移动应用程序，如路由，交通灯规范和道路工程规划。 这样的工作最近已经沿着一条线延伸行数（参见其他[18]和[19]）和更多在乌得勒支的De Uithof小区进行了验证[20]）和北京市的实际数据（[21]）。
本文的目标有两个：（i）首先，我们解释[17]的原始思想如何适应这个问题，这里特别感兴趣的问题是即自行车共享网络（ii）其次，我们展示了一些初步结果已通过采用所提出的建模获得框架。来实际控制应用的发展目前正在调查基于提出的模型并将在后面的工作中加以说明。
本文组织如下：第二节解释我们如何从自行车中建立马尔可夫链转换矩阵旅行数据，并改变马尔科夫链期望它对处理大数据分析很有用。第三段简要描述了已有数据库的数据和基于这些数据建立的转移矩阵的有效性。第四部分显示了使用转移矩阵的第二特征向量获得的聚类结果，并提供了对结果的鉴于自行车网络的解释。最后，第五节总结了论文和概述了我们目前的研究。
II一种自行车共享的马尔可夫链模型系统
在本文中，我们对离散时间，有限状态，齐次马尔可夫链感兴趣。一个有个状态的马尔可夫链完全由转移概率描述矩阵，其入口表示通过概率从状态到状态恰好在一个步骤中。是行随机非负矩阵，作为每行中的元素是概率，在马尔可夫链中它们总和为1。理论上，转型之间存在着密切的关系矩阵和相应的图。该图包含一组通过边缘连接的节点。图表与矩阵相关的是有向图，其节点由状态给出，，并且有一个指导从到的边缘当且仅当如果对于每一对节点有一个强连接从第一个节点到第一个节点的有向边的序列第二个。矩阵当且仅当它是不可约的有向图是强有力的连接。我们在这里没有描述马尔可夫链的其他性质以及感兴趣的读者可以参考常规书籍，例如[22]以获得更多细节。
在我们的自行车共享网络模型中，我们假设第个自行车站与两个状态有关：状态是指目前停放在个自行车站的自行车,状态是指一辆正在从第个站点行驶到另外的站点的自行车。因此，在每一个时间步骤（在我们的模拟中，一秒钟），一辆停放的自行车状态可以保持在相同的状态或转移至（即，如果有人选择自行车来达到他的目的地）。同样，停留在点的自行车也可以要么保持在相同的状态（即，如果没到目的地的话他将继续前行）或可以移动到对应于任何自行车站的另一个状态，与目的地相关。请注意，可以等于（即，某些用户可能会在第个自行车站骑上自行车，然后在完成骑行之后把自行车返回原站点）。当然，值得注意的是如果条件下直接从状态到状态是不可能的，同理从到也是不可能的。我们的模型在图1所示的图表中被举例说明。
根据前面的讨论，马尔可夫链的大小为，其中是数字的自行车站，并且它非常稀疏（即，除了两个入口外都是如此，对于状态等于零，和条目对于状态等于零，）。然后，关于状态的对角条目应该是与给定的平均停留时间成比例自行车站（即通过用表示这样的时间，那么入口应该是，如附录中所述[17]），而同一行的其他非零入口很容易通过强制该行是随机的（即，总和等于1）
关于状态的对角条目是否按照从开始的旅行的平均长度按比例计算？第三个自行车站。其他条目在同一行中按照频率成比例地选择选择一个给定的自行车站作为目的地，从第个自行车站开始，并扩大为了行驶也是随机的。因此，过渡只有在平均停车时间平均的情况下才能建立矩阵旅程持续时间和完整的旅行列表。然而，注意这样的要求通常得到满足，因为这样无论如何数据也可用于其他目的，例如，通常，类似GPS的传感器安装在自行车上以防止盗用他们的人;自行车站被监控到选择最佳的搬迁策略，以避免自行车站保持空虚;最后关于旅行的信息是可用于定价目的。特别是，这些数据是公开可用于美国波士顿市和美国下一节我们解释我们如何构建转换矩阵为那个特定的用例。下一小节收集一些已知的结果来激励马尔可夫链的采用大数据应用程序。
- 简单更新马尔可夫链转换矩阵的影响
多种原因表明，马尔可夫链特别适用于大数据应用。
- 首先，微观行为嵌入在链条中通过聚合; 即以prob-能力。 这些概率很容易测量或无需进行大数据处理或计算存储功能。
- 马尔可夫链适合捕捉和捕捉建模复杂的动力学在[23]中被讨论和证明。
- 第三，马尔可夫链对大数据的适用性应用程序的讨论，例如，在上下文中Google的PageRank算法[24]。 这里显示已经建立完善和强大的算法可用于处理数千个数据集，如果不是数百万，则可能包含该网页的网页有关用户查询的相关信息。
为了深入了解马尔可夫链的快速重新计算，我们现在收集了一些定理可以在这方面使用。 在整个过程中设置符号这部分让我总是表示适当的身份矩阵，吃了维度，以及e和e我所有的向量， 适当维度的单位向量。 我们的出发点是以下着名的[25]定理。
定理1：令和是不可约的马尔可夫链过渡矩阵并让和分别为它们的左边Perron特征向量。 令进一步的让成为一个条件的一个条件广义逆，即满足。在这种情况下，下面的等式成立。
（1）
定理2：令和是不可约的马尔可夫链满足关系的转换矩阵其中。 令和分别为左边的Perron的特征向量和.让，并记为它的反函数。则有
. （2）
其中 .
定理3：设和是不可约的马尔科夫链转换矩阵等是从获得的乘以第个对角因子每个并缩放每个中的对角线条目以便它们的比例保持不变。 令和为和的相应左Perron特征向量
（3）
其中，.
III．波士顿数据
在这项工作中使用的Tha数据涉及约70000次自行车旅行发生在2011年7月28日至9月21日之间。总体而言，53辆自行车站和569辆自行车得到了有效使用在考试期间。 转换矩阵已建立根据这样的可用数据，并因此对应于平均值在检查的时间范围内的值。 转换矩阵大小为106times;106，并且与讨论一致第二部分，不超过个非零条目（实际上，有更少的非零条目，即2654，由于在考试期间某些特定事实用户从未选择成对的起点 - 终点）。
建立马尔可夫链所需的所有信息转换矩阵可以从行程列表中提取：in特是，每次旅行都会存储自行车的ID，时间在自行车被采取，起源的自行车站，时间在那里自行车交付回来和自行车站目的地。 其他信息也是可用的，例如无论用户是注册用户还是临时用户（即，没有自行车共享服务的会员资格）; 邮编户代码; 用户的出生年份和性别。请注意，所有这些信息都可以用于交付特定服务（例如广告），但尚未使用在这项工作中，他们的分析将留给未来的工作。
备注1：有人可能会期望的目的地一次旅行应该与下一次旅行的起点相一致同一辆自行车）。 这是真的，除非自行车被重新安置到另一个自行车站，在两个连续的一段时间旅行（例如，因为一辆自行车缺少自行车站）。 因此，在可用的旅行列表中数据，大部分时间这两个电台重合，但在有些情况存在差异。 我们假定每一个差异是由于搬迁，并没有考虑到这一点计算停车时间时不一致的行程（因为搬迁时间不可用，因此可能不能确定自行车停放了多久搬迁或重新安置后再次使用）。
备注2：请注意，可用数据仅显示a真实故事的一部分。 例如，一些用户可能有想用自行车去特定的旅行，但没有找到任何起源自行车站有自行车; 或一些用户可能想要选择一个特定的目的地，但发现它已经装满了自行车。 我们没有这方面的信息（有点）不满意的客户，但请注意，他们可能会在数据中引入一些噪声（即由于不可用）的自行车，他们可能会选择不同的起点所需的一个; 或由于充分的自行车站，他们可能会选择一个不同于目标点的目标点）。
图2以蓝色显示了Perron的特征向量马尔可夫链转换矩阵按照程序在第二部分描述。 Perron的条目特征向量对应于长期的时间分数一辆自行车花费在相应的状态，即停放在，还是从个站开始的行程。 图2还比较了Perron特征向量从相同的数据中提取相同的信息（和以红色显示）。 从图中可以看出，这两个密度非常接近，并且差异是由于事实上，真实的数据对应于一个可能的实现马尔科夫链转移矩阵给出了一个特定的初始值自行车的分配。 另一个有趣的信息，可以从图中提取的是，自行车可用更多可能比繁忙。
IV．聚类
正如参考文献[17]在不同背景下所阐明的那样在马尔可夫链中汇总数据的优点在于一些数量可以在上下文中轻松计算马尔可夫链有一个富有洞察力的解释在某些情况下不能轻易提取的原始数据以其他方式。 作为例子，“第二特征向量”（即，与第二特征值相关联的特征向量最大的模块，如果是真的）已知具有聚类属性（参见参考文献[17]的附录）。 获得一个我们在自行车网络中对集群进行有意义的解释只考虑了自行车的流量而忽略了所花费的时间停在车站，和沿着一条路走的时间行程。 因此，我们考虑了原始的子矩阵其国家将对应于TBi，并将其重新正规化行有一个单一的总和。 然后，第二个特征向量矩阵如图3所示。
集群的解释是最有可能的人在单个集群内旅行，更难以旅行一个群集到另一个群集。可能的会员资格到一个集群而不是另一个集群是由第二特征向量的相应条目的符号，图4显示了正面和负面的条目第二个具有不同颜色的特征向量（该图是取自Google Map，使用纬度信息和每个单车站的经度，可从数据集）。如此获得的集群的有趣属性是他们不利用任何有关的地理信息自行车站的位置，但他们只是利用了了解客户所做的典型旅行，以及因此，起源 - 目的地对的典型选择。如如图所示，集群似乎提供了一个正确的信息，因为这些地点事实上一直在位在两个地理上分开的地区。
备注3：原则上可能会有所不同集群出现在一天的不同时间。 在这种情况下，我们进一步计算第二个特征向量考虑到只有在早上发生的行程，下午的行程，而且我们仍然获得了相同的结果。 这表明在这个特定的应用程序集似乎不是随时间变化的。群集的知识可以用于一个数字的应用程序：因为大多数行程发生在一个集群内，并且从一个集群到另一个集群的次数更少大部分时间内，群集内的自行车应该保持不变。因此，可以计划两辆独立的卡车执行两个集群中的搬迁行动。 另外，因为有两个（完全）分开的两个集群内的行程流程，两个广告活动可以同时进行这两个领域。
V．结论
本文提出了一种新的基于马尔可夫链的模型来描述自行车共享网络的功能。该模型受到车辆类似工作的启发流动，并且适用于其中的具体应用其他的事情每个自行车站需要两个状态（即一个考虑停放在自行车站的自行车，以及一个考虑从该给定的自行车站出发的所有行程）。我们使用波士顿自行车共享网络的实际数据建立我们的马尔可夫链转换矩阵，并验证关于数据的模型。本文主要集中在建模部分，到目前为止所描述的实际应用只是聚类其中一个确实提供了一个有趣的划分自行车共享网络，无法从中提取以直截了当的方式提供相同的信息。然而，在我们的想法中，许多其他的实际应用可以基于在提出的模型上，特别是我们目前致力于设计新颖的搬迁策略和广告活动的新想法。为此我们计划使用其他变量，可以很容易地从中提取马尔可夫链（例如平均首次通过时间（MFPT）
全文共10329字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[13069]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
