文摘gydF4y2Ba

基于位置的服务是服务基于地理位置的移动手持设备如智能手机。本研究提出了基于位置的研究,利用位置信息找到路线异常,日常生活的一个常见问题。例如,应该生成警报当送货人不按正规途径使交付。不同的路线异常现象进行了讨论,提出了各种方法来检测异常。该方法基于线性路径表示发现匹配的路线从一组存储路径作为当前路线输入位置的位置。路线匹配是很容易通过比较当前位置线性路线。当不存在匹配路线生成警报。初步实验结果表明该方法是有效的和容易使用。gydF4y2Ba

1。介绍gydF4y2Ba

表gydF4y2Ba1gydF4y2Ba展示了全球个人电脑和手机销售根据各种市场研究报告gydF4y2Ba1gydF4y2Ba]。全球智能手机出货量的数量已经过了发货的个人电脑和服务器的数量预计在2011年和他们之间的差距更大。新兴智能手机创造了各种各样的应用程序是不可能的或不方便对个人电脑和服务器,甚至是笔记本电脑。畅销书的应用之一是基于位置的服务(lbs)根据以下市场研究。gydF4y2Ba(我)gydF4y2Ba希拉德(gydF4y2Ba2gydF4y2Ba]报道80%的智能手机用户提供基于位置的服务,其中一半使用服务,促销,销售根据其当前位置。gydF4y2Ba(2)gydF4y2Ba最方便的移动购物体验价格比较和产品研究根据JiWire [gydF4y2Ba3gydF4y2Ba]。gydF4y2Ba(3)gydF4y2Ba基于位置的服务用户的数量从1230万年的2009增加到3320万年的2010(增加170%)在美国根据SNL Kagan [gydF4y2Ba4gydF4y2Ba]。gydF4y2Ba

本文提出了基于位置的研究,使用位置信息找到路线异常。不同的路线异常现象进行了讨论,提出了各种方法检测异常在这个研究。它分为五个步骤:(i)路线数据收集,(ii)路线数据准备,(iii)路由模式发现,(iv)路由模式分析和可视化,异常检测(v)路线。增量位置搜索的主要方法使用一种技术基于线性路径表示,这便于存储和匹配的路线。这就开始搜索第一的位置输入搜索路线。Location-by-location,一个或多个可能的匹配路由发现,马上呈现。路线匹配是很容易通过比较当前位置线性路线。当不存在匹配路线生成警报。初步实验结果表明提出的方法是有效的和容易使用。gydF4y2Ba

本文的其余部分组织如下。部分gydF4y2Ba2gydF4y2Ba出这项研究的背景信息,包括三个主题定位服务(我),(2)相关的定位研究,(3)路线表示和匹配。提出系统中引入部分gydF4y2Ba3gydF4y2Ba,和几个简单的路线异常检测的方法解释。部分gydF4y2Ba4gydF4y2Ba详细描述了两个主要的方法使用一个线性和增量位置搜索路线表示。部分gydF4y2Ba5gydF4y2Ba给出了实验结果和评价。本研究的最后一部分给出了总结。gydF4y2Ba

2。背景gydF4y2Ba

三个主题相关研究:(i)基于位置的服务,(2)相关的定位研究,(3)路线表示和匹配,将在这一节中讨论。gydF4y2Ba

2.1。基于位置的服务(lbs)gydF4y2Ba

基于位置的服务是服务基于地理位置的移动手持设备(gydF4y2Ba5gydF4y2Ba,gydF4y2Ba6gydF4y2Ba]。两磅的例子(i)找一个附近的民族餐馆和(2)定位附近的商店产品的最好的价格。基于位置的服务的系统结构,如图gydF4y2Ba1gydF4y2Ba,包括以下五个主要组件(gydF4y2Ba7gydF4y2Ba]。gydF4y2Ba(一)gydF4y2Ba移动手持设备,小型计算机,可以一只手。在大多数情况下,他们是智能手机。gydF4y2Ba(b)gydF4y2Ba定位系统,这是一个导航卫星系统提供的位置和时间信息,任何一个有接收器。gydF4y2Ba(c)gydF4y2Ba移动和无线网络中继设备的查询和位置信息服务提供商和供应商的结果发送给设备。gydF4y2Ba(d)gydF4y2Ba服务提供商,提供基于位置的服务。gydF4y2Ba(e)gydF4y2Ba地理数据提供者的数据库存储大量的地理数据等信息的餐馆和加油站。gydF4y2Ba

使用我们的研究基于位置的服务的一个例子是一步一步给出如下。gydF4y2Ba(1)gydF4y2Ba智能手机(一)包含一个应用程序找到路线异常。gydF4y2Ba(2)gydF4y2Ba移动用户提交查询找到路线异常以及定位系统(b)的位置信息的应用程序,它在后台运行。gydF4y2Ba(3)gydF4y2Ba应用程序调用服务器端程序(d)位于北达科他州大学的航空航天学院以及位置信息通过手机或无线网络(c)。gydF4y2Ba(4)gydF4y2Ba程序服务器使用Oracle数据库执行路线异常检测(e)存储路由数据。发送一个警报等采取适当的动作异常发生时。gydF4y2Ba(5)gydF4y2Ba结果如确认发送警报发送回智能手机。gydF4y2Ba

精彩的介绍LBS技术和标准是由王et al。gydF4y2Ba8gydF4y2Ba]。gydF4y2Ba

2.2。相关的定位研究gydF4y2Ba

各种基于位置的研究可以在期刊和会议上。本节讨论了几个重要的定位文章涉及旅游序列。gydF4y2Ba

(我)郑et al。gydF4y2Ba9gydF4y2Ba)提出一个方法来我的有趣的地方和旅游序列。三个步骤被用于这项研究。gydF4y2Ba

步骤1。gydF4y2Ba模型中多个个人位置历史树型层次图(TBHG)。gydF4y2Ba

步骤2。gydF4y2Ba基于TBHG,打击——(超文本诱导主题搜索)为基础的推理模型。gydF4y2Ba

步骤3。gydF4y2Ba我旅游序列位置考虑这些位置的利益和用户的旅游经历。gydF4y2Ba

最后,一个大的GPS数据,收集了107用户一年在现实世界中,用来评估他们的系统。结果显示他们HITS-based超过基线的方法如rank-by-count和rank-by-frequency推理模型。gydF4y2Ba

(2)在一篇从郑et al。gydF4y2Ba10gydF4y2Ba),提出了一种基于监督学习的方法从原始GPS数据自动推断出交通模式。运输方式,如走路和开车,隐含在用户的GPS数据可以提供宝贵的知识来理解用户。他们的方法包括三个部分:(i)基于改变点的分割方法中,(2)一个推理模型,(3)基于条件概率的后处理算法。他们评估的方法使用GPS数据收集的45用户在6个月期间。结果表明改变积分方法实现更高程度的准确性预测交通模式和检测它们之间的转换。gydF4y2Ba

(3)可以使用以前的路线推荐未来的旅游模式。Yoon et al。gydF4y2Ba11gydF4y2Ba]提出行程推荐基于多个用户生成GPS轨迹。用户只需要提供一个起点,一个终点,旅行时间收到一个行程的建议。刘和张gydF4y2Ba12gydF4y2Ba)提供了一个路线推荐系统引导用户通过一系列的位置。他们的系统使用序列模式挖掘的方法来提取流行路线从一组存储路线从以前的用户。然后建议路线通过匹配用户的当前路线与提取的路线。gydF4y2Ba

可以找到一些相关的定位研究的文章(gydF4y2Ba13gydF4y2Ba- - - - - -gydF4y2Ba18gydF4y2Ba]。gydF4y2Ba

2.3。路线表示和匹配gydF4y2Ba

传统上,一个旅行路线是存储为一系列的位置(经度和纬度)和路由匹配使用简单的比较。本研究保存路径线段序列和路线匹配成为发现当前位置之间的距离和线段。gydF4y2Ba

2.3.1。路线表示gydF4y2Ba

路线表示计算机类似于图像表示因为每个由一组/像素在一个二维平面上的位置。因此,图像的表示可以应用于路由表示和匹配。gydF4y2Ba(我)gydF4y2BaChang et al。gydF4y2Ba4gydF4y2Ba提出了一种二维字符串表示。匹配查询可以指定一个2 d字符串,将检索转化成二维子序列匹配。gydF4y2Ba(2)gydF4y2Ba空间知识表示2 d c字符串,使用切削机理和一组空间算子,提出了1990年由李和徐(gydF4y2Ba19gydF4y2Ba]。gydF4y2Ba(3)gydF4y2Ba黄和琼gydF4y2Ba20.gydF4y2Ba)提出了一种2 d CgydF4y2Ba^+gydF4y2Ba延长了2 d c字符串的字符串表示计划包括相对度量的信息图片到字符串。gydF4y2Ba

从文章中可以找到其他表示李et al。gydF4y2Ba21gydF4y2Ba和吴和张gydF4y2Ba22gydF4y2Ba]。gydF4y2Ba

2.3.2。路线匹配gydF4y2Ba

增量搜索是一个逐步搜索,找到匹配的文本输入搜索字符串字符的字符。大多数增量搜索是基于研究霍和Corasick [gydF4y2Ba23gydF4y2Ba),开发一个算法来定位出现的所有任何的有限数量的关键字的文本字符串。算法由构造一个有限状态机模式匹配的关键字,然后利用机器来处理文本字符串模式匹配在一个单一的通过。建设模式匹配机器需要时间成正比关键字的长度的总和。状态转换的数量由处理文本字符串的模式匹配的机器是独立的关键词的数量。提出了几个增量搜索方法如下。gydF4y2Ba(我)gydF4y2Ba迈耶(gydF4y2Ba24gydF4y2Ba]给出了给定文本寻找问题出现的特定的字符串,在特定情况下的字符串搜索收益可能会改变。他修改了算法哦,Corasick允许增量图施工,以便新关键字可能在任何时间进入搜索。增量算法本质上保留的时间和空间复杂性nonincremental。gydF4y2Ba(2)gydF4y2Ba霍的机器和Corasick时必须再次重建一个关键字是附加的。津田et al。gydF4y2Ba25gydF4y2Ba)提出一个有效的算法来添加一个关键字的机器。他们现在的时间效率比较与原算法使用实际的仿真结果。仿真结果表明加速因子,算法,在25 - 270倍之间由霍与原算法相比,Corasick需要重建整个机器交流。gydF4y2Ba(3)gydF4y2BaKoenig et al。gydF4y2Ba26gydF4y2Ba)开发一种搜索算法,结合增量和启发式搜索,即终身计划* (LPA *)。它被命名为“终身计划”,因为它从以前的搜索重用信息。他们的方法多次找到最短路径从一个给定的开始顶点给定目标顶点而边缘图变化的成本。gydF4y2Ba

增量启发式搜索的调查可以发现从文章Koenig et al。gydF4y2Ba27gydF4y2Ba]。gydF4y2Ba

3所示。提出了系统gydF4y2Ba

智能手机的GPS(全球定位系统)功能提供了移动用户的位置信息。位置信息的集合能够描述移动用户的家庭和学校之间的旅游路线如散步路线或推销员的运送路线。本研究使用位置信息找到任何路线异常,例如,一个学生并不需要每日路线上学。该系统在本节介绍。gydF4y2Ba

3.1。建议的步骤gydF4y2Ba

本研究是寻找异常。它分为五个步骤,如图gydF4y2Ba2gydF4y2Ba。gydF4y2Ba(一)gydF4y2Ba路由数据收集gydF4y2Ba:这一步之前收集路线数据所使用的应用程序。gydF4y2Ba(b)gydF4y2Ba路由数据准备gydF4y2Ba:原始GPS数据通常是不可靠的和一致的,包括许多噪音。使用前必须准备好。gydF4y2Ba(c)gydF4y2Ba路由模式发现gydF4y2Ba:并不是所有的路线都是有效的,例如,一个很短的路线通常不是有用的。这一步将有效的路由到一个数据库,删除无效的路线。gydF4y2Ba(d)gydF4y2Ba路由模式分析和可视化gydF4y2Ba:分析了路线和允许用户查看地图上路线。gydF4y2Ba(e)gydF4y2Ba路线异常发现gydF4y2Ba:这一步是用来发现任何路线异常,本研究的主题。增量的方法搜索中使用这个步骤。gydF4y2Ba

图gydF4y2Ba3gydF4y2Ba(一个)显示了应用程序图标,线路检查,Android设备上。单击图标后,它将显示该系统的输入界面如图gydF4y2Ba3gydF4y2Ba(b),其中包括三个单选按钮。gydF4y2Ba(我)gydF4y2Ba收集路由数据gydF4y2Ba为路线,这是这个按钮提交后数据收集。这个函数可以随时被激活,但最有可能的是激活的开头使用这个应用程序。gydF4y2Ba(2)gydF4y2Ba检查线路gydF4y2Ba重定向到接口图gydF4y2Ba9gydF4y2Ba(b)进行线路检查后提交按钮。gydF4y2Ba(3)gydF4y2Ba显示存储路径gydF4y2Ba,用于显示信息的存储路径。基本路线信息的一个示例如表所示gydF4y2Ba2gydF4y2Ba包括数量和每个路线的开始和结束时间和地点。的经度和纬度位置表示gydF4y2Ba和gydF4y2BaθgydF4y2Ba极坐标系统。路线可以被添加到系统,用户可以删除不良或从未使用过的路线。表gydF4y2Ba2gydF4y2Ba显示了基本的路由信息。每个路由存储在其他地方的细节。gydF4y2Ba

3.2。系统实现gydF4y2Ba

收集到的路由数据通常是原始因为GPS数据通常是不可靠的和一致的,包含了许多噪音gydF4y2Ba16gydF4y2Ba]。需要处理的数据在使用前有效。数据准备的方法包括过滤、复苏,恢复和发展轨迹。路由数据准备用于这项研究包括以下。gydF4y2Ba(我)gydF4y2Ba两个位置略有差异处理是相同的,例如,位置gydF4y2Ba=(5603年,243.10°)是一样的位置gydF4y2Ba243.10°)=(5609年,由于GPS精度较低和旅行者可能走同样的路线,但不同位置如走在街道的另一边。gydF4y2Ba(2)gydF4y2Ba类似的连续位置(例如,旅行者空闲)减少到一个。gydF4y2Ba(3)gydF4y2Ba如果连续两个地点之间的距离大于一个阈值,它可能意味着GPS断开。位置轨迹可能需要用来在两个地点之间插入位置(gydF4y2Ba28gydF4y2Ba]。gydF4y2Ba(iv)gydF4y2Ba如果一个位置是大大不同于周围的位置,它可能意味着一个GPS噪声。轨迹的位置可能被删除和位置。gydF4y2Ba

然后系统检查准备路线数据和删除无效的路线,其中可能包括以下。gydF4y2Ba(我)gydF4y2Ba路线是很短的距离,如几码长。gydF4y2Ba(2)gydF4y2Ba有许多破碎的位置或噪音的途径是,它无法固定的轨迹的方法。gydF4y2Ba(3)gydF4y2Ba路线是很长或短的持续时间,例如,不到一分钟或更长时间超过两个小时。gydF4y2Ba

本研究使用位置信息来检测异常。许多方法可以用来发现异常。四种检测介绍了分段:(i)时间检查,(ii)边境检查,(iii)启动和目标检查,检查(iv)路线。前三种方法是简单的,在本节说明。线路检查,最后一个方法是本研究的重点和更为复杂。它使用模式匹配的方法来发现任何异常。接下来的小节将致力于它。gydF4y2Ba(我)gydF4y2Ba时间检查gydF4y2Ba:例如,路线1号大约需要23分钟。如果旅行路线和需要远远超过23分钟,然后可能生成警报。同时,开始和结束时间可以用于这张支票。例如,学校从8:30点。如果学生没有到达学校8:30点,然后可能生成警报。gydF4y2Ba(2)gydF4y2Ba边境检查gydF4y2Ba:例如,运送路线是在一个社区。如果一个社区的路线伸出,然后警报可能会生成。一个简单的方法来找到边界框的路线如如图gydF4y2Ba4gydF4y2Ba。gydF4y2Ba(3)gydF4y2Ba启动和目标检查gydF4y2Ba:如果旅客不开始从任何位置的路线,或者一个特定的时间没有达到任何目标,它可能值得一个警告。gydF4y2Ba(iv)gydF4y2Ba线路检查gydF4y2Ba:上面的方法很简单,但缺乏准确性。该方法精度较高的检查路线,并使用更复杂的算法,将在下一节详细。gydF4y2Ba

4所示。使用线性路径表示线路检查gydF4y2Ba

路线检查更加复杂。本节讨论的方法用于查找路线异常。传统路线系列代表了不同的位置,这是复杂的,难以使用。一个算法开发整理的路线的路线可以存储为一组线段和路线匹配成为一个简单的任务检查当前位置之间的距离和线段。该路线检查可以分为两种情况,有序和无序的路线。没有生成警报如果旅行者不从头开始或停止的位置以来路线和目的地检查可以很容易地用来检查这种情况。gydF4y2Ba

4.1。线性近似人类的旅游路线gydF4y2Ba

提出了线性近似算法将人类的旅游路线转换成线段。近似捕获一个路线的本质在尽可能少的线段。多边形近似,基于误差函数,该方法应用于(gydF4y2Ba29日gydF4y2Ba]。应用该算法之前,然而,路线必须平滑单元厚度这可能位于分支路线。让gydF4y2Ba最大允许误差。对于一个给定的位置gydF4y2Ba一个gydF4y2Ba通过一个近似线必须通过,可以定义两个点gydF4y2Ba和gydF4y2Ba在远处gydF4y2Ba从gydF4y2Ba。曲线的算法搜索最长的部分包含两个平行切线之间开始gydF4y2Ba和gydF4y2BaCgydF4y2Ba(参见算法gydF4y2Ba1gydF4y2Ba)。gydF4y2Ba

这个函数gydF4y2BaBEST_PATHgydF4y2Ba时发现路线最长的线段的位置gydF4y2Ba有多个8-neighbor。这就是为什么路线应用之前需要平滑算法。nonunit厚度的路线可能误导算法调用gydF4y2BaBEST_PATHgydF4y2Ba函数。由于该算法需要二次时间gydF4y2BaBEST_PATHgydF4y2Ba函数需要检查尽可能多的路径和路径上的任何位置,可以调用它。图gydF4y2Ba5gydF4y2Ba显示了一个示例的路线和图gydF4y2Ba6gydF4y2Ba显示相应的线性路线后应用算法gydF4y2BaLINEAR_APPROXgydF4y2Ba在图的路线gydF4y2Ba5gydF4y2Ba。gydF4y2Ba

4.2。命令路线gydF4y2Ba

对于这种路线,地点的顺序是相关的,例如,公交线路。命令路线在图给出的一个例子gydF4y2Ba5gydF4y2Ba定向subroutes是数字1,2,3,4,5。数字也意味着旅游秩序,例如,旅行的路线:开始→1→2→3→4→5→结束。假设存储的旅行者必须沿着路线。一个简单的算法使用增量位置搜索寻找路线异常下令路线如下所示。它检查旅客的位置。如果当前位置和当前线段之间的距离大于一个阈值,然后报告异常。旅行的开始位置可以开始在一个路线,旅行者可以在任何地方、任何时间检查结束。(参见算法gydF4y2Ba2gydF4y2Ba)。gydF4y2Ba

假设有5个可用的路线的字母代表线段:gydF4y2Ba(1)gydF4y2BacgydF4y2Ba→→e s→p f l n→→→→→→g hgydF4y2Ba(2)gydF4y2Baf e d c→→→→→s→t m l n→→→→→→g p h→jgydF4y2Ba(3)gydF4y2Bas c→t h o g→→→→→→→→d f m→ngydF4y2Ba(4)gydF4y2Bap s→t l n→→→→→g h l s→t→→→→o pgydF4y2Ba(5)gydF4y2Bae b d c→→→→→s→t m r n→→→→→g hgydF4y2Ba

给出两个例子旁边显示该算法是如何工作的。gydF4y2Ba

(a)这个例子显示了一个路线不使用该算法生成警报。假设一个旅行路线gydF4y2Bac c→→→→d l l f d→→→→gydF4y2Ba。5存储路径后应用算法如下:gydF4y2Ba(1)gydF4y2Ba →gydF4y2Ba l f e→→→n→→→→→g p hgydF4y2Ba(2场)gydF4y2Ba(2)gydF4y2Ba e→→gydF4y2Ba →→n→gydF4y2Ba h g p s→t→→→→→jgydF4y2Ba(完美匹配)gydF4y2Ba(3)gydF4y2Bat s→→→→→g hgydF4y2Ba →m→ngydF4y2Ba(4场)gydF4y2Ba(4)gydF4y2Bap s→t l n→→→→→g h l s→t→→→→o pgydF4y2Ba(不匹配)gydF4y2Ba(5)gydF4y2Ba n r m e b→→→→→→→s t→g→hgydF4y2Ba(3场)gydF4y2Ba

一个下划线的位置意味着比赛的地方。路线2号有一个完美的匹配,所以没有警报是由该算法生成的。然而,生成警报可能因为没有任何路线的结束位置。这个异常可以启动和目标检查所发现的部分gydF4y2Ba4.1gydF4y2Ba。gydF4y2Ba

(b)这个例子显示了一个路线通过使用该算法生成警报。假设一个旅行路线gydF4y2Baf d d c→→→→→p→→pgydF4y2Ba。5存储路径后应用算法如下:gydF4y2Ba(1)gydF4y2Ba l f e→→→n→→→→→g p hgydF4y2Ba(2场)gydF4y2Ba(2)gydF4y2Ba t s l m→n→→→→→→→g p h→jgydF4y2Ba(4场)gydF4y2Ba(3)gydF4y2Bat s→→→→→g hgydF4y2Ba →m→ngydF4y2Ba(4场)gydF4y2Ba(4)gydF4y2Bap s→t l n→→→→→g h l s→t→→→→o pgydF4y2Ba(不匹配)gydF4y2Ba(5)gydF4y2Ba n r m e b→→→→→→→s t→g→hgydF4y2Ba(3场)gydF4y2Ba

最后一个位置gydF4y2BapgydF4y2Ba没有匹配的任何路线所以会由该算法生成警报。gydF4y2Ba

4.3。无序的路线gydF4y2Ba

无序的路线、地点的顺序也许除了开始和结束的位置,是无关紧要的,例如,报纸交付。图gydF4y2Ba7gydF4y2Ba显示了一个示例无序的路线,如果数字将被忽略。为了找到异常无序的路线,这条路线数据收集需要找到和保存所有线段连接到十字路口,如{3、4、8、9}和{5、6、12、13}在图gydF4y2Ba10gydF4y2Ba和双向subroutes的开始和结束段路线。一个十字路口是一个交叉路口,两个或两个以上的道路满足或在年级交叉。例如,在图的路线gydF4y2Ba10gydF4y2Ba包括以下项目:gydF4y2Ba(我)gydF4y2Ba开始段:段1,gydF4y2Ba(2)gydF4y2Ba结尾段:段13日gydF4y2Ba(3)gydF4y2Ba行组:{3、4、8、9}和{5、6、12、13},gydF4y2Ba(iv)gydF4y2Ba双向subroutes: 1gydF4y2Ba↔gydF4y2Ba2gydF4y2Ba↔gydF4y2Ba3、4gydF4y2Ba↔gydF4y2Ba5、6gydF4y2Ba↔gydF4y2Ba7gydF4y2Ba↔gydF4y2Ba8、9gydF4y2Ba↔gydF4y2Ba10gydF4y2Ba↔gydF4y2Ba11gydF4y2Ba↔gydF4y2Ba12和13。gydF4y2Ba

发现路由的算法异常无序的路线如下所示。相比它更复杂的命令路线,因为旅行者可以在几个可能的subroutes的下一个位置。当到达一个十字路口,该算法检查所有可用subroutes交集。gydF4y2Ba

算法gydF4y2Ba3gydF4y2Ba没有检查是否所有subroutes访问。它可以很容易地通过增加每subroute检查程序。同时,该算法生成警报如果subroute访问两次,因为它是不寻常的旅行subroute在大多数情况下的两倍。它可以很容易地修改如果用户不希望它为这个条件生成警报。再次,给出一个例子说明该算法有效。假设有三个可用的路线的字母代表线段。三个路线和每个路线的物品保存在下面列出:gydF4y2Ba

路线1。gydF4y2Bae c d b→→→→→f p t l n→→→→→→我→hgydF4y2Ba(我)gydF4y2Ba段:开始,段gydF4y2BacgydF4y2Ba,gydF4y2Ba(2)gydF4y2Ba结尾段:段gydF4y2BahgydF4y2Ba,gydF4y2Ba(3)gydF4y2Ba行组:{gydF4y2Bae、p、tgydF4y2Ba},{gydF4y2Bag, l, ngydF4y2Ba},gydF4y2Ba(IV)gydF4y2BaSubroutes:(我)gydF4y2BacgydF4y2Ba↔gydF4y2BabgydF4y2Ba↔gydF4y2BadgydF4y2Ba↔gydF4y2Ba一个gydF4y2Ba(二)gydF4y2BaegydF4y2Ba↔gydF4y2BafgydF4y2Ba↔gydF4y2BangydF4y2Ba(3)gydF4y2BalgydF4y2Ba↔gydF4y2BatgydF4y2Ba(四)gydF4y2BapgydF4y2Ba↔gydF4y2BaggydF4y2Ba,(v)gydF4y2Ba我gydF4y2Ba↔gydF4y2BahgydF4y2Ba。gydF4y2Ba

路线2。gydF4y2Bap c d b→→→→→g→o t l j r n→→→→→→→ugydF4y2Ba(我)gydF4y2Ba开始段:段gydF4y2BacgydF4y2Ba,gydF4y2Ba(2)gydF4y2Ba结尾段:段gydF4y2BaugydF4y2Ba,gydF4y2Ba(3)gydF4y2Ba行组:{gydF4y2Baa, p, sgydF4y2Ba},gydF4y2Ba(IV)gydF4y2BaSubroutes:(我)gydF4y2BacgydF4y2Ba↔gydF4y2BabgydF4y2Ba↔gydF4y2BadgydF4y2Ba↔gydF4y2Ba一个gydF4y2Ba(二)gydF4y2BapgydF4y2Ba↔gydF4y2BaggydF4y2Ba↔gydF4y2BaogydF4y2Ba↔gydF4y2BargydF4y2Ba↔gydF4y2BangydF4y2Ba↔gydF4y2BajgydF4y2Ba↔gydF4y2BalgydF4y2Ba↔gydF4y2BatgydF4y2Ba,(iii)gydF4y2Ba年代gydF4y2Ba↔gydF4y2BaugydF4y2Ba。gydF4y2Ba

路线3。gydF4y2Bac→f y e d→→→→→→→→n z我→hgydF4y2Ba(我)gydF4y2Ba开始段:段gydF4y2BacgydF4y2Ba,gydF4y2Ba(2)gydF4y2Ba结尾段:段gydF4y2BahgydF4y2Ba,gydF4y2Ba(3)gydF4y2Ba行组:没有,gydF4y2Ba(iv)gydF4y2BaSubroutes:gydF4y2BacgydF4y2Ba↔gydF4y2BadgydF4y2Ba↔gydF4y2Ba一个gydF4y2Ba↔gydF4y2BaegydF4y2Ba↔gydF4y2BaygydF4y2Ba↔gydF4y2BafgydF4y2Ba↔gydF4y2BazgydF4y2Ba↔gydF4y2BangydF4y2Ba↔gydF4y2BakgydF4y2Ba↔gydF4y2Ba我gydF4y2Ba↔gydF4y2BahgydF4y2Ba。gydF4y2Ba

下面的示例显示了一个路线通过使用该算法生成警报。假设一个旅行路线gydF4y2Ba一个m f f e→→→→→→n→我gydF4y2Ba。下面的列表显示了该算法是如何工作的位置,位置:gydF4y2Ba(1)gydF4y2Ba一个gydF4y2Bam f f e→→→→→→n→我gydF4y2Ba,当前位置在哪里gydF4y2Ba一个gydF4y2Ba:gydF4y2Ba路线1:gydF4y2BacgydF4y2Ba↔gydF4y2BabgydF4y2Ba↔gydF4y2BadgydF4y2Ba↔gydF4y2Ba 路线2:gydF4y2BacgydF4y2Ba↔gydF4y2BabgydF4y2Ba↔gydF4y2BadgydF4y2Ba↔gydF4y2Ba 路线3:gydF4y2BacgydF4y2Ba↔gydF4y2BadgydF4y2Ba↔gydF4y2Ba ↔gydF4y2BaegydF4y2Ba↔gydF4y2BaygydF4y2Ba↔gydF4y2BafgydF4y2Ba↔gydF4y2BazgydF4y2Ba↔gydF4y2BangydF4y2Ba↔gydF4y2BakgydF4y2Ba↔gydF4y2Ba我gydF4y2Ba↔gydF4y2BahgydF4y2Ba(2)gydF4y2Ba一个→gydF4y2BaegydF4y2Ba→→f m→→n→→我gydF4y2Ba,当前位置在哪里gydF4y2BaegydF4y2Ba:gydF4y2Ba路线1:gydF4y2BaegydF4y2Ba↔gydF4y2BafgydF4y2Ba↔gydF4y2BangydF4y2Ba路线2:没有gydF4y2Ba路线3:gydF4y2BacgydF4y2Ba↔gydF4y2BadgydF4y2Ba↔gydF4y2Ba一个gydF4y2Ba↔gydF4y2Ba ↔gydF4y2BaygydF4y2Ba↔gydF4y2BafgydF4y2Ba↔gydF4y2BazgydF4y2Ba↔gydF4y2BangydF4y2Ba↔gydF4y2BakgydF4y2Ba↔gydF4y2Ba我gydF4y2Ba↔gydF4y2BahgydF4y2Ba(3)gydF4y2Ba→e→gydF4y2BafgydF4y2Ban n m f→→→→→我gydF4y2Ba,当前位置在哪里gydF4y2BafgydF4y2Ba:gydF4y2Ba路线1:gydF4y2BaegydF4y2Ba↔gydF4y2Ba ↔gydF4y2BangydF4y2Ba路线2:没有gydF4y2Ba路线3:gydF4y2BacgydF4y2Ba↔gydF4y2BadgydF4y2Ba↔gydF4y2Ba一个gydF4y2Ba↔gydF4y2BaegydF4y2Ba↔gydF4y2BaygydF4y2Ba↔gydF4y2Ba ↔gydF4y2BazgydF4y2Ba↔gydF4y2BangydF4y2Ba↔gydF4y2BakgydF4y2Ba↔gydF4y2Ba我gydF4y2Ba↔gydF4y2BahgydF4y2Ba(4)gydF4y2Baf e→→→gydF4y2BafgydF4y2Ba→→n n→→我gydF4y2Ba,当前位置在哪里gydF4y2Ba米gydF4y2Ba:gydF4y2Ba路线1:gydF4y2BaegydF4y2Ba↔gydF4y2Ba ↔gydF4y2BangydF4y2Ba路线2:没有gydF4y2Ba路线3:gydF4y2BacgydF4y2Ba↔gydF4y2BadgydF4y2Ba↔gydF4y2Ba一个gydF4y2Ba↔gydF4y2BaegydF4y2Ba↔gydF4y2BaygydF4y2Ba↔gydF4y2Ba ↔gydF4y2BazgydF4y2Ba↔gydF4y2BangydF4y2Ba↔gydF4y2BakgydF4y2Ba↔gydF4y2Ba我gydF4y2Ba↔gydF4y2BahgydF4y2Ba(5)gydF4y2Baf e→→→gydF4y2Baf→gydF4y2Ba米gydF4y2Ba→n→→我gydF4y2Ba,当前位置在哪里gydF4y2Ba米gydF4y2Ba:gydF4y2Ba路线1:没有gydF4y2Ba路线2:没有gydF4y2Ba路线3:没有gydF4y2Ba

一个下划线部分意味着一场比赛。生成警报时,因为没有可用的subroutes当前位置gydF4y2Ba米gydF4y2Ba。gydF4y2Ba

5。实验结果gydF4y2Ba

本节给出了实验结果。gydF4y2Ba

5.1。路由数据收集gydF4y2Ba

本研究的第一步是信息收集途径。收集可能随时随地被激活。图gydF4y2Ba3gydF4y2Ba(b)显示了应用程序的入口页面。经过用户选择按钮“收集路由数据,系统显示界面如图gydF4y2Ba7gydF4y2Ba(一)包括以下三个单选按钮。gydF4y2Ba(我)gydF4y2Ba开始收集路由数据gydF4y2Ba开始收集数据。典型的智能手机提供的位置信息包括时间、位置的纬度和经度。尽可能频繁的位置信息被收集和收集频率取决于旅行的方法。例如,散步,骑自行车,开车的频率是不同的。这个过程在后台通过使用多线程运行,所以智能手机仍然可以像往常一样功能。gydF4y2Ba(2)gydF4y2Ba最后收集gydF4y2Ba数据收集,结束目前的路线。gydF4y2Ba(3)gydF4y2Ba检查当前路线gydF4y2Ba,用于检查当前的状态数据采集包括地图如图gydF4y2Ba7gydF4y2Ba(c)和数据表gydF4y2Ba3gydF4y2Ba。gydF4y2Ba

表gydF4y2Ba2gydF4y2Ba显示了基本的路由信息。每个路由存储在其他地方的细节。的一个例子1表中给出了详细的路线gydF4y2Ba3gydF4y2Ba定期收集的地点和时间,例如,每分钟走路和开车每10秒。gydF4y2Ba

5.2。路由数据准备和路由模式发现、分析和可视化gydF4y2Ba

收集到的路由数据通常是原始因为GPS数据通常是不可靠的和一致的,包含了许多噪音gydF4y2Ba13gydF4y2Ba]。该系统还允许用户查看存储路线如图gydF4y2Ba8gydF4y2Ba(b)。除了给他们的路由信息表gydF4y2Ba2gydF4y2Ba和gydF4y2Ba3gydF4y2Ba,用户还喜欢查看存储路线。的一个路线如图gydF4y2Ba8gydF4y2Ba(c)。gydF4y2Ba

5.3。路线异常检测gydF4y2Ba

本研究使用位置信息来检测异常。一个警告如图gydF4y2Ba9gydF4y2Ba(c)是一个异常被发现时生成。否则,智能手机功能像往常一样。警报可以发送通过电子邮件或电话。接口图gydF4y2Ba9gydF4y2Ba(b)是为了检查路线包括以下三个单选按钮。gydF4y2Ba(我)gydF4y2Ba开始检查路线gydF4y2Ba运行在后台通过使用多线程编程,所以智能手机仍然可以像往常一样功能。gydF4y2Ba(2)gydF4y2Ba最终检查gydF4y2Ba停止当前的线路检查。此外,检查发现异常时结束。gydF4y2Ba(3)gydF4y2Ba显示当前检查gydF4y2Ba,用于检查当前的状态检查。例如,如何紧密地将当前路线触发警报或匹配到目前为止有多少线路?除了显示当前数据的路由表gydF4y2Ba3gydF4y2Ba通过使用底部按钮如图gydF4y2Ba10gydF4y2Ba(b),系统还显示当前位置的可能路线如图gydF4y2Ba10gydF4y2Ba(c)使用顶部的按钮,如图gydF4y2Ba10gydF4y2Ba(b)。gydF4y2Ba

拟议的方法是方便的和有效的。执行也是有效的。使用的时间检查和启动和目标检查是常数。《纽约时报》的边境检查和检查gydF4y2BaOgydF4y2Ba(gydF4y2BangydF4y2Ba),gydF4y2Ba用户位置的数量,因为位置执行检查的位置和每个位置都需要一个常数时间做匹配。这个过程的时间gydF4y2BaLinear_ApproxgydF4y2Ba也gydF4y2BaOgydF4y2Ba(gydF4y2BangydF4y2Ba),gydF4y2Ba的位置是一个路线,因为算法整理了一下位置,位置的路线。此外,程序只是用于路由集合,但不是路线检查,经常发生。gydF4y2Ba

6。结论gydF4y2Ba

移动应用商店(或应用程序商店)出售或提供移动应用程序/服务智能手机等手持设备。应用程序/服务不一定是店家。他们中的许多人来自等第三方独立开发者。各种各样的移动应用程序可以在商店。最畅销的应用之一是相关的基于位置的服务,涵盖范围广泛的用法,如在附近的商店找到最低价格的产品和定位最近的加油站。本研究提出了基于位置的研究,利用位置信息找到路线异常,日常生活的一个常见问题。例如,应该生成警报当校车错过路线的一部分。不同的路线异常现象进行了讨论,提出了各种方法来检测异常。它分为五个步骤:(i)路线数据收集,(ii)路线数据准备,(iii)路由模式发现,(iv)路由模式分析和可视化,异常检测(v)路线。主要的方法使用一个线性和增量搜索路线表示地点,发现匹配路线的搜索路线输入位置的位置。 It begins the searching as soon as the first location of the search route is entered. Location by location, one or more possible matches for the route are found and immediately presented. An alert is generated when no matched routes exist. Experimental results show the proposed methods are effective and easy to use.

除了线性路径表示,拟议中的增量位置搜索是基于字符串匹配,这是简单而有效的。搜索基于以下方法值得考虑。gydF4y2Ba(我)gydF4y2Ba有限自动机gydF4y2Ba:收集到的路线是用来建立一个有限自动机,然后使用它来检查任何异常。gydF4y2Ba(2)gydF4y2Ba矩阵乘法gydF4y2Ba:类似的路线是通过矩阵乘法当前路线和存储之间的路线。如果产品比阈值的意思,据说是存储路线gydF4y2Ba类似的gydF4y2Ba当前的路线。由于矩阵存储为字符串,乘法可以有效地完成。gydF4y2Ba(3)gydF4y2Ba神经网络gydF4y2Ba:路线是一个序列的位置。路线匹配是用来发现任何异常和修改Hopfield神经网络可以用来解决这个问题。gydF4y2Ba(iv)gydF4y2Ba近似串匹配gydF4y2Ba:路线或序列位置被存储为字符串。然后使用近似串匹配找到任何异常。gydF4y2Ba