对显著位置进行建模

1.一种方法，包括：
由移动设备从所述移动设备的位置确定子系统来接收所述移动设备的多个位置，每个位置与指示所述位置被所述位置确定子系统确定的时间的时间戳相关联，所述多个位置基于所述位置的时间戳顺序地排序；
由所述移动设备基于群集条件来确定所排序的多个位置中的两个或更多个连续位置形成位置群集，
所述群集条件规定一个或多个标准，所述一个或多个标准指示所述两个或更多个连续位置各自属于所述位置群集，以及
所述位置群集指示所述移动设备已经停留在如下的地理位置处：所述地理位置对应于在用于预测所述移动设备的移动的状态模型中被表示的显著位置，其中所述显著位置是通过对所述位置群集中的位置应用具有恒定增益的递归滤波器基于所述位置群集来确定的；
由所述移动设备基于所述显著位置来确定所述状态模型，包括将所述显著位置添加为所述状态模型中的状态以及将所述移动设备的从第一显著位置到第二显著位置的每个移动表示为从表示所述第一显著位置的第一状态到表示所述第二显著位置的第二状态的过渡，所述过渡与过渡开始时间和过渡结束时间相关联；以及
将所述状态模型提供给所述移动设备的预测子系统以用于生成所述移动设备在给定的未来时间处的未来位置是所述状态模型中表示的所述显著位置中的一个显著位置的预测，其中基于如下项来生成所述预测：当前时间、所述未来时间、当前位置和基于所述状态模型的所述状态和所述过渡确定的状态过渡的概率密度。
2.根据权利要求1所述的方法，其中接收所述位置包括从所述位置确定子系统一次一个地读取所述位置，所述位置确定子系统的每次读取是通过由位置预测应用程序或功能之外的应用程序或功能对所述位置确定子系统的激活而触发的。
3.根据权利要求l所述的方法，其中所述群集条件规定：
所述连续位置是相同的，或者每对所述连续位置之间的距离小于空间邻近阈值；并且与所述连续位置中的第一位置相关联的时间戳和与所述连续位置中的最后位置相关联的时间戳之间的时间差大于时间邻近阈值，其中所述显著位置是所述移动设备已经在其中停留了至少与所述时间邻近阈值所指示的时间段一样长的时间段的位置。
4.根据权利要求1所述的方法，其中确定所述位置群集包括：
基于与每个相应位置相关联的不确定性值来验证所述两个或更多个连续位置中的每个位置，所述不确定性值指示所述相应位置被所述位置确定子系统正确确定的可能性；
从所述连续位置排除一个或多个异常值，每个异常值是与超过阈值的不确定性值相关联的位置；以及
利用不是异常值的所验证的位置来确定所述位置群集。
5.根据权利要求1所述的方法，其中所述状态模型中的每个状态与状态进入时间戳和状态离开时间戳相关联。
6.根据权利要求1所述的方法，其中确定所述状态模型包括如下中的一者：
在确定所述位置群集已经被指定为所述状态模型中的所述状态时，向所述状态模型添加所述移动设备在所述状态和另一状态之间的过渡或者向所述状态添加状态进入时间和状态离开时间戳；或者
在确定所述位置群集还未被表示为所述状态模型中的所述状态时，向所述状态模型添加所述位置群集。
7.根据权利要求1所述的方法，包括：
确定所述状态模型的至少一个属性满足统计阈值；以及然后
确定所述状态的语义含义和所述过渡的语义含义。
8.根据权利要求7所述的方法，其中：
所述统计阈值包括每个状态的寿命；
确定所述状态的所述语义含义包括确定所述状态是否与生活活动模式有关；并且所述过渡的所述语义含义是基于两个生活活动之间的往返的属性来确定的。
9.根据权利要求1所述的方法，包括利用自回归滤波器来随时间推移调节所述状态模型中的状态，其中调节所述状态包括在确定所述移动设备在给定的时间段没有访问过由所述状态模型表示的显著位置时从所述状态模型移除陈旧状态。
10.一种系统，包括：
一个或多个处理器；和
非暂态计算机可读介质，所述非暂态计算机可读介质耦接到所述一个或多个处理器并存储用于使所述一个或多个处理器执行包括如下的操作的指令：
接收移动设备的多个位置，每个位置与指示所述位置被位置确定子系统确定的时间的时间戳相关联，所述多个位置基于所述位置的时间戳顺序地排序；
基于群集条件来确定所排序的所述多个位置中的两个或更多个连续位置形成位置群集，
所述群集条件规定一个或多个标准，所述一个或多个标准指示所述两个或更多个连续位置各自属于所述位置群集，以及
所述位置群集指示所述移动设备已经停留在如下的地理位置处：所述地理位置对应于在用于预测所述移动设备的移动的状态模型中被表示的显著位置，其中所述显著位置是通过对所述位置群集中的位置应用具有恒定增益的递归滤波器基于所述位置群集来确定的；
基于所述显著位置来确定所述状态模型，包括将所述显著位置添加为所述状态模型中的状态以及将所述移动设备的从第一显著位置到第二显著位置的每个移动表示为从表示所述第一显著位置的第一状态到表示所述第二显著位置的第二状态的过渡，所述过渡与过渡开始时间和过渡结束时间相关联；以及
将所述状态模型提供给所述移动设备的预测子系统以用于生成所述移动设备在给定的未来时间处的未来位置是所述状态模型中表示的所述显著位置中的一个显著位置的预测。
11.根据权利要求10所述的系统，其中接收所述位置包括从所述位置确定子系统一次一个地读取所述位置，所述位置确定子系统的每次读取是通过由位置预测应用程序或功能之外的应用程序或功能对所述位置确定子系统的激活而触发的。
12.根据权利要求10所述的系统，其中所述群集条件规定：
所述连续位置是相同的，或者每对所述连续位置之间的距离小于空间邻近阈值；并且与所述连续位置中的第一位置相关联的时间戳和与所述连续位置中的最后位置相关联的时间戳之间的时间差大于时间邻近阈值，其中所述显著位置是所述移动设备已经在其中停留了至少与所述时间邻近阈值指示的时间段一样长的时间段的位置。
13.根据权利要求10所述的系统，其中确定所述位置群集包括：
基于与每个相应位置相关联的不确定性值来验证所述两个或更多个连续位置中的每个位置，所述不确定性值指示所述相应位置被所述位置确定子系统正确确定的可能性；
从所述连续位置排除一个或多个异常值，每个异常值是与超过阈值的不确定性值相关联的位置；以及
利用不是异常值的所验证的位置来确定所述位置群集。
14.根据权利要求10所述的系统，其中所述状态模型中的每个状态与状态进入时间戳和状态离开时间戳相关联。
15.根据权利要求10所述的系统，其中确定所述状态模型包括如下中的一者：
在确定所述位置群集已经被指定为所述状态模型中的所述状态时，向所述状态模型添加所述移动设备在所述状态和另一状态之间的过渡或者向所述状态添加状态进入时间和状态离开时间戳；或者
在确定所述位置群集还未被表示为所述状态模型中的所述状态时，向所述状态模型添加所述位置群集。
16.根据权利要求10所述的系统，所述操作包括：
确定所述状态模型的至少一个属性满足统计阈值；以及然后
确定所述状态的语义含义和所述过渡的语义含义。
17.根据权利要求16所述的系统，其中：
所述统计阈值包括每个状态的寿命；
确定所述状态的所述语义含义包括确定所述状态是否与生活活动模式有关；以及所述过渡的所述语义含义是基于两个生活活动之间的往返的属性来确定的。
18.根据权利要求10所述的系统，所述操作包括利用自回归滤波器来随时间推移调节所述状态模型中的状态，其中调节所述状态包括在确定所述移动设备在给定的时间段没有访问过由所述状态模型表示的显著位置时从所述状态模型移除陈旧状态。
19.一种系统，包括：
用于接收移动设备的多个位置的装置，每个位置与指示所述位置被位置确定子系统确定的时间的时间戳相关联，所述多个位置基于所述位置的时间戳顺序地排序；
用于基于群集条件来确定所排序的所述多个位置中的两个或更多个连续位置形成位置群集的装置，
所述群集条件规定一个或多个标准，所述一个或多个标准指示所述两个或更多个连续位置各自属于所述位置群集，以及
所述位置群集指示所述移动设备已经停留在如下的地理位置处：所述地理位置对应于在用于预测所述移动设备的移动的状态模型中被表示的显著位置，其中所述显著位置是通过对所述位置群集中的位置应用具有恒定增益的递归滤波器基于所述位置群集来确定的；
用于基于所述显著位置来确定所述状态模型的装置，所述确定包括将所述显著位置添加为所述状态模型中的状态以及将所述移动设备的从第一显著位置到第二显著位置的每个移动表示为从表示所述第一显著位置的第一状态到表示所述第二显著位置的第二状态的过渡，所述过渡与过渡开始时间和过渡结束时间相关联；和
用于将所述状态模型提供给所述移动设备的预测子系统以用于生成所述移动设备在给定的未来时间处的未来位置是所述状态模型中表示的所述显著位置中的一个显著位置的预测的装置。
20.根据权利要求19所述的系统，其中用于接收所述位置的装置包括用于从所述位置确定子系统一次一个地读取所述位置的装置，所述位置确定子系统的每次读取是通过由位置预测应用程序或功能之外的应用程序或功能对所述位置确定子系统的激活而触发的。
21.根据权利要求19所述的系统，其中所述群集条件规定：
所述连续位置是相同的，或者每对所述连续位置之间的距离小于空间邻近阈值；并且与所述连续位置中的第一位置相关联的时间戳和与所述连续位置中的最后位置相关联的时间戳之间的时间差大于时间邻近阈值，其中所述显著位置是所述移动设备已经在其中停留了至少与所述时间邻近阈值指示的时间段一样长的时间段的位置。
22.根据权利要求19所述的系统，其中用于确定所述位置群集的装置包括：
用于基于与每个相应位置相关联的不确定性值来验证所述两个或更多个连续位置中的每个位置的装置，所述不确定性值指示所述相应位置被所述位置确定子系统正确确定的可能性；
用于从所述连续位置排除一个或多个异常值的装置，每个异常值是与超过阈值的不确定性值相关联的位置；以及
用于利用不是异常值的所验证的位置来确定所述位置群集的装置。
23.根据权利要求19所述的系统，其中所述状态模型中的每个状态与状态进入时间戳和状态离开时间戳相关联。
24.根据权利要求19所述的系统，其中用于确定所述状态模型的装置包括如下中的一者：
用于在确定所述位置群集已经被指定为所述状态模型中的所述状态时，向所述状态模型添加所述移动设备在所述状态和另一状态之间的过渡或者向所述状态添加状态进入时间和状态离开时间戳的装置；或者
用于在确定所述位置群集还未被表示为所述状态模型中的所述状态时，向所述状态模型添加所述位置群集的装置。
25.根据权利要求19所述的系统，还包括：
用于确定所述状态模型的至少一个属性满足统计阈值的装置；以及
用于确定所述状态的语义含义和所述过渡的语义含义的装置。
26.根据权利要求25所述的系统，其中：
所述统计阈值包括每个状态的寿命；
用于确定所述状态的所述语义含义的装置包括用于确定所述状态是否与生活活动模式有关的装置；以及
所述过渡的所述语义含义是基于两个生活活动之间的往返的属性来确定的。
27.根据权利要求19所述的系统，还包括用于利用自回归滤波器来随时间推移调节所述状态模型中的状态的装置，其中用于调节所述状态的装置包括用于在确定所述移动设备在给定的时间段没有访问过由所述状态模型表示的显著位置时从所述状态模型移除陈旧状态的装置。

对显著位置进行建模\n技术领域\n[0001] 本公开整体涉及基于位置的服务。\n背景技术\n[0002] 很多电子设备具有基于位置的功能。例如，移动设备能够利用卫星导航系统(例如全球定位系统或GPS)或蜂窝通信系统来估计移动设备的位置。移动设备能执行各种特定于位置的任务。例如，在移动设备上运行的地图应用程序能使移动设备显示地图。地图上的标记可指示移动设备的当前位置。在接收到选择该标记的用户输入时，移动设备能显示当前位置附近的兴趣点，例如，餐厅或加油站。在接收到指定目的地的用户输入时，移动设备能显示从当前位置到目的地的路线、以及基于关于该路线的交通信息所估计的到达时间。\n发明内容\n[0003] 描述了用于对显著位置进行建模的技术。显著位置可以是由于各种原因而对于移动设备的用户而言显著的位置。在以足够的确定性确定移动设备已经在某个地方或区域停留了足够的时间量时，该移动设备可确定这个地方或区域是显著位置。移动设备可构建作为一个或多个显著位置的抽象的状态模型。状态模型可包括表示显著位置的状态、和表示移动设备在位置之间的移动的过渡。移动设备可使用状态模型来提供预测用户辅助。\n[0004] 可以实现本说明书中描述的特征以获得一个或多个优点。移动设备可学习移动设备的移动模式，并使其自身适配于该移动模式。利用本说明书中所述的技术，移动设备能够实施预测用户辅助。实施预测用户辅助的移动设备能够基于移动模式来提供辅助，而不需要附加的用户输入。因此，移动设备的用户可具有使用移动设备的服务的更好体验，尤其是基于位置的服务。例如，移动设备可确定用户通常在工作日上午8点离开家去工作，而在周末上午8点离开家去健身房。当在上午8点前不久被打开时，在工作日，移动设备可自动地显示从家到工作地的路线的交通信息；而在周末，移动设备可自动地显示从家到健身房的路线的交通信息。\n[0005] 在附图和以下说明书中阐述了对显著位置进行建模的一个或多个具体实施的细节。根据说明书、附图及权利要求，对显著位置进行建模的其他特征、方面和优点将显而易见。\n附图说明\n[0006] 图1是示出预测用户辅助的示例性具体实施的图示。\n[0007] 图2是示出确定位置群集的示例性技术的图示。\n[0008] 图3是示出基于位置群集来识别显著位置的示例性技术的图示。\n[0009] 图4是示出基于位置群集确定的示例性状态模型的图示。\n[0010] 图5是示出对状态模型的增量改变的图示。\n[0011] 图6A是示出确定示例性状态之间的过渡概率密度的图示。\n[0012] 图6B是示出确定示例性状态的进入概率密度的图示。\n[0013] 图7A、7B、和7C是示出实施预测用户辅助的示例性移动设备的部件的框图。\n[0014] 图8是示出生成状态模型的示例性过程的流程图。\n[0015] 图9是示出预测未来位置的示例性过程的流程图。\n[0016] 图10是示出实现图1至图9的特征和操作的移动设备的示例性设备架构的框图。\n[0017] 图11是实现图1至图9的特征和操作的移动设备的示例性网络操作环境的框图。\n[0018] 各附图中类似的参考符号表示类似的元件。\n具体实施方式\n[0019] 示例性预测用户辅助\n[0020] 图1是示出预测用户辅助的示例性具体实施的图示。示例性移动设备102可使用移动设备102的过去移动来预测移动设备102的未来位置。移动设备102于是可适配移动设备\n102的行为以执行特定于所预测的未来位置的服务。\n[0021] 移动设备102可利用机器学习和数据挖掘技术来学习移动设备102的过去移动。过去移动可被记录作为移动设备102访问的显著位置和移动设备102在这些显著位置之间的移动。在以足够的确定性确定移动设备102已经在某个地方或区域停留了足够的时间量时，移动设备102可确定这个地方或区域是显著位置。在所述时间量满足各种标准的情况下，例如当时间量满足时间长度阈值(例如X小时)或频率阈值(例如每天X分钟、每周Y天)时，所述时间量可以是足够的。移动设备102的移动的记录可包括进入每个显著位置的所测量或计算的时间和离开每个显著位置的所测量或计算的时间。显著位置可与多个进入和离开相关联。\n[0022] 除了显著位置之外，移动的记录可包括显著位置之间的过渡。从第一显著位置向第二显著位置的每个过渡可与指示移动设备102离开第一显著位置的时间的过渡开始时间戳以及指示移动设备102进入第二显著位置的时间的过渡结束时间戳相关联。\n[0023] 移动设备102可将移动的记录表示为状态模型104。状态模型104可包括各自表示一个显著位置的状态(例如状态106和其他状态)、和各自表示移动设备102在显著位置之间的移动的过渡(例如过渡107和状态之间的其他过渡)。在下文中将参考图2至图5描述确定状态模型104的附加细节。\n[0024] 基于状态模型104，移动设备102可确定(1)在给定时间，移动设备102从给定显著位置移动到每个其他显著位置的过渡概率密度，或者(2)移动设备102从先前未知或未表示的位置进入显著位置的进入概率密度。移动设备102的模式分析器可利用状态模型104来确定移动设备102的每日、星期、月度、或年度移动模式。移动设备102的预测引擎可使用过渡概率密度(或进入概率密度)和移动模式来预测移动设备102在未来时间将进入(或停留)的显著位置。移动设备102然后可使用所述预测来提供预测用户辅助，例如辅助用户为未来事件进行计划。\n[0025] 在图1的实例中，移动设备102可利用移动设备102的位置确定子系统来确定当前位置108。移动设备102可确定当前时间110。基于当前位置、当前时间、和状态模型104的概率和模式，移动设备102可确定移动设备102在未来某个时间的最可能位置是由状态106表示的显著位置。移动设备102于是可执行对应于所述显著位置、或者对应于从当前位置到所述显著位置的过渡的用户辅助功能。例如，在被开启或解锁时，移动设备102可在移动设备\n102的显示表面上提供显示提示112。提示112可包括用户辅助信息116。用户辅助信息116例如可包括从当前位置到可能的未来位置的路线、和沿该路线的交通信息。移动设备102可自动地提供显示提示112和用户辅助信息116，而不要求用户输入可能的未来位置作为目的地。\n[0026] 在一些具体实施中，移动设备102可提供与可能的未来位置相关联的标签。该标签可以是用户预先指定或者移动设备102通过反向地理编码或通过对移动设备102的移动的语义分析而确定的兴趣点的地址或名称。例如，移动设备102可确定第一位置可能是家并且第二位置可能是工作场所。因此，移动设备102可在用户辅助信息116中使用术语“家”和“工作地”。\n[0027] 构建状态模型的示例性技术\n[0028] 图2是示出确定位置群集的示例性技术的图示。(图1的)示例性移动设备102可使用学习技术来确定(图1的)状态模型104。\n[0029] 移动设备102可随时间(T)顺序地跟踪位置数据。顺序地跟踪位置数据可通过借助另一应用程序来执行，以避免或降低位置数据收集的成本。例如，移动设备102可在另一服务向移动设备102的位置确定子系统请求位置时收集位置数据。因此，收集位置数据可以是“免费的”，而不必仅仅为了确定移动设备102的移动模式而激活位置确定子系统。\n[0030] 移动设备102可随着时间T收集到位置202、204、206、208、210、和212。收集位置可以是持续的操作。比指定时间段早的位置可被清除。所述时间段可由用户偏好或隐私策略来指定。位置202、204、206、208、210、和212可各自包括纬度、经度和海拔坐标并且与指示相应位置被收集的时间的时间戳相关联。\n[0031] 移动设备102可确定位置202、204、206、208、210、和212中的一些属于可指示显著位置的位置群集。移动设备102可在确定(1)至少预先指定的阈值数量(例如两个)的连续位置被收集到；(2)连续位置的时间跨度满足预先指定的阈值时间窗口；和(3)在位置被收集的时间段，这些位置是相同的从而表明移动设备102静止、或者彼此足够近从而表明移动设备102位于足够小的限定区域中时，确定位置群集被形成。\n[0032] 例如，移动设备102可随时间T确定两个位置群集：位置群集218和位置群集220。位置群集218可包括在比阈值时间窗口(例如45分钟的时间窗口)长的时间段[T1，T2]上收集的位置202、204、和206。移动设备102可在确定位置202、204、和206的变化小到足以满足变化阈值时确定位置群集218包括位置202、204、和206。同样，位置群集220可包括在时间段[T3，T4]内收集的位置210和212。移动设备102可在确定位置210和212的变化满足变化阈值时确定位置群集220包括位置210和212。\n[0033] 异常值检测机制可滤除不属于群集的位置。例如，移动设备102可确定位置208与位置206和位置210不同(例如位置206和208之间的距离以及位置208和位置210之间的距离超过阈值)。此外，移动设备102可确定没有其他位置(1)在位置208之前或之后的阈值时间窗口内被收集并且(2)地理上与位置208靠近。作为响应，移动设备102可确定位置208是异常值并且丢弃位置208。此外，如果时间段中的位置显著不同于所述时间段中的很多其他位置，则移动设备102可将这个不同的位置作为异常值丢弃，并且利用所述时间窗口中的其他位置来确定位置群集。移动设备102可使用位置群集218和220来确定显著位置和状态模型\n104中的状态。\n[0034] 图3是示出基于位置群集识别显著位置的示例性技术的图示。利用上文中参考图2所述的技术，移动设备102可识别位置群集218、220、302、和303。移动设备102可基于位置群集218、220、302、和303来确定显著位置304、306、和308。\n[0035] 移动设备102可基于位置群集218、220、302、和303，利用位置群集218、220、302、和\n303中的每一者中的位置来确定显著位置304、306、和308中的每一者。确定显著位置304、\n306、和308可以基于具有恒定增益的递归滤波器。下文在下一段落中提供确定显著位置\n304、306、和308的细节。显著位置304、306、和308中的每一者可包括纬度、经度、并且任选地还有海拔的坐标。显著位置304、306、和308中的每一者可与一个或多个位置群集相关联。例如，显著位置304可在时间段[T1,T2]中对应于位置群集218，并且在时间段[T7,T8]期间对应于位置群集303。位置群集218和位置群集303中的位置可以是相同的。时间段[T1,T2]和时间窗口[T7,T8]的长度可以是相同的，也可以是不同的。\n[0036] 移动设备102可在时间T2具有初始状态模型。在时间T2+k，移动设备102可接收增量位置数据，其中k是时间T2与附加位置数据被接收的时间之间的差异(在这个实例中，k＝T7-T2)。移动设备102可使用增量位置数据来确定用于在状态模型中使用的显著位置304。\n移动设备102可确定位置群集218对应于纬度和经度坐标X1。移动设备102可确定位置群集\n303对应于纬度和经度坐标X2。移动设备102可确定X1和X2之间的距离满足阈值。作为响应，移动设备102可确定位置群集218和位置群集303属于同一位置(显著位置304)。移动设备\n102于是可利用下面在滤波器1中所示的恒定增益滤波器将位置群集303添加到显著位置\n304。(例如，采样数据例如5、6、7的函数，可能对于所有群集不是相同的)\n[0037] 其中α≥1        (1)\n[0038] 滤波器1中的值α(例如5、6、7)可以是采样数据的函数，并且可以对于所有位置群集都是相同的或者对于每个位置群集是不同的。\n[0039] 显著位置304、306、和308中的每一者可与一个或多个进入时间戳和一个或多个离开时间戳相关联。每个进入时间戳可对应于与位置群集中第一位置相关联的时间。例如，与显著位置304相关联的第一进入时间戳可以是与作为位置群集218的第一位置的位置202相关联的时间戳。与显著位置304相关联的第二进入时间戳可以是与位置群集303中第一位置相关联的时间戳。同样，每个离开时间戳可对应于与位置群集中最后位置相关联的时间。例如，与显著位置304相关联的第一离开时间戳可以是与作为位置群集218的最后位置的位置\n206相关联的时间戳。与显著位置304相关联的第二离开时间戳可以是与位置群集303中最后位置相关联的时间戳。\n[0040] 显著位置304、306、和308中的每一者可与标签相关联。标签可由用户来指派(例如“家”、“健身房”、或“工作地”)，或者由移动设备102通过反向地理编码来自动确定。在一些具体实施中，标签可源自对与显著位置相关联的每个位置群集的时点和星期几的模式的语义分析。语义分析可基于人类自然的行为。移动设备102可被编程为应用反映人类行为的预先确定的模式。行为可包括例如每个人都需要一定时间的睡眠。睡眠的时间可以是移动设备102完全静止的时间。用户每天睡眠8小时，并且在家吃饭可能在工作日在家花费X小时(例如10至12小时)、在周末花费Y小时。用户在星期一到星期五的正常工作时间工作。移动设备102可利用这些模式来将显著位置确定为“家”，在“家”中，(1)移动设备102每周度过超过第一阈值数量的小时数(例如60小时)；(2)移动设备102记录大多数进入和离开；并且(3)那些进入和离开表明移动设备每天停留至少第二阈值数量的小时数(例如8小时)。\n[0041] 例如，移动设备102可确定与显著位置304相关联的每个位置群集对应于被指定为工作日晚上的时间段(例如从晚上7点到第二天早上8点)。移动设备102于是可将显著位置\n304指定为“家”并且提供所述指定作为显著位置304的标签。\n[0042] 移动设备102可确定从一个显著位置向另一显著位置的过渡。例如，移动设备102可确定在某个工作日，移动设备102在时间T2和时间T3之间从显著位置304(“家”)过渡(312)到显著位置308(“工作地”)。移动设备102可将所述过渡与过渡开始时间戳(例如T2)和过渡结束时间戳(例如T3)相关联。移动设备102可基于显著位置304、306、和308以及过渡\n312、314、和316来构建状态模型104。在下文中参考图4描述状态模型104的细节。\n[0043] 图4是示出基于位置群集确定的示例性状态模型104的图示。状态模型104可以是描绘状态和状态过渡的n阶自回归过程(例如一阶自回归过程)，其中过渡到状态q中是取决于前一状态r。因此，状态模型104可捕获给定状态之前的状态和过渡的完整历史。状态和状态过渡可以是移动设备102在显著位置之间的移动的抽象。与传统的高斯-马尔可夫模型相比，状态模型104可以是一种充分模型，从而利用时间和持续时间的分配函数保持状态过渡的随机特性。\n[0044] 状态模型104可包括状态106、402、和404。状态106、402、和404可分别对应于显著位置304、308、和306。移动设备102可基于位置群集218、220、302、和303来确定显著位置\n304、308、和306，如上文参考图3所述。状态106、402、和404中的每一者可分别是显著位置\n304、308、和306的表示。\n[0045] 状态模型104可包括从每个状态向每个其他状态的多个过渡。过渡可包括例如从状态106到状态402的过渡406、和从状态106到状态402的过渡408。在状态模型104中，从状态106到状态402的每个过渡可对应于从显著位置304的位置群集到显著位置308的位置群集的过渡。例如，过渡406可表示从显著位置304的位置群集218到显著位置308的位置群集\n220的过渡312。过渡408可表示从显著位置304的位置群集303到显著位置308的下一位置群集的过渡。\n[0046] 过渡406和408中的每一者可与过渡开始时间戳和过渡结束时间戳相关联。每个过渡开始时间戳可以是移动设备102离开由状态106所表示的显著位置304的时间。例如，过渡\n406的过渡开始时间戳可以是星期二上午7点；过渡408的过渡开始时间戳可以是星期三上午7点。每个过渡结束时间戳可以是移动设备102进入由状态402所表示的显著位置308的时间。例如，过渡406的过渡结束时间戳可以是星期二上午9点；过渡408的过渡结束时间戳可以是星期三上午9点。\n[0047] 状态模型104的每个状态可与一个或多个状态进入时间戳和一个或多个状态离开时间戳相关联。例如，状态106的第一状态进入时间戳可以是与位于显著位置304的位置群集218中的移动设备102的第一位置(位置202)相关联的时间。第一状态离开时间戳可以是与位于显著位置304的位置群集218中的移动设备102的最后位置(位置206)相关联的时间。\n第一状态进入时间戳和第一状态离开时间戳可定义移动设备102停留在状态106的第一停留时间412。状态106的第二状态进入时间戳可以是与位于显著位置304的位置群集303中的移动设备102的第一位置相关联的时间。第二状态离开时间戳可以是与显著位置304的位置群集303中的移动设备102的最后位置相关联的时间。第二状态进入时间戳和第二状态离开时间戳可定义移动设备102停留在状态106的第二停留时间414。\n[0048] 图5是示出对状态模型104的增量改变的图示。状态模型104可具有可变拓扑结构，从而允许增量增加新状态和删除废弃状态。\n[0049] 移动设备102可确定新状态502。例如，移动设备102可确定一系列位置读数指示移动设备102位于一个地方处的持续时间长得足以以足够的确定性表明这个地方是显著位置。移动设备102可确定这个显著位置在状态模型104中没有被表示。作为响应，移动设备\n102可创建新状态502，并将新状态502添加(504)到状态模型104。移动设备102可基于移动设备102在访问状态502之前访问的最后一个显著位置来添加进入状态502的过渡。移动设备102可将状态502与第一位置读数的状态进入时间戳相关联，该第一位置读数的状态进入时间戳指示移动设备102位于状态502的显著位置处。移动设备102可将状态502与最后位置读数的状态离开时间戳相关联，该最后位置读数的状态离开时间戳指示在移动设备102进入另一显著位置之前移动设备102位于状态502所表示的显著位置处。移动设备102可基于状态模型104中表示的由移动设备102所访问的下一显著位置来添加从状态502的过渡。\n[0050] 除了添加状态之外，移动设备可周期性地从状态模型104中移除状态。移动设备\n102可确定移动设备102已经有足够长的时间(例如超过X天或周阈值)没有访问状态404表示的显著位置。因此，移动设备102可从状态模型104中移除(506)状态404。移除状态404可包括移除进入状态404的过渡和离开状态404的过渡。\n[0051] 移动设备102可使用状态模型104来预测移动设备102的未来位置。预测未来位置可以至少部分地基于移动设备102的当前位置。当前位置可以是“在状态中”，其中当前位置由状态模型104的状态表示。在确定当前位置是在状态中时，移动设备102可基于状态之间的过渡概率密度来预测未来位置。当前位置可以是“在状态外”，其中当前位置没有由状态模型104的状态表示。在确定当前位置是“在状态外”时，移动设备102可基于从当前位置进入状态模型104的状态的进入概率密度来预测未来位置。关于确定过渡概率密度和进入概率密度的细节在下文中参考图6A和图6B来介绍。\n[0052] 图6A是示出确定示例性状态106和402之间的过渡概率密度602的示意图。过渡概率密度602可指示移动设备102从状态模型104的状态106过渡到状态402的概率分布。移动设备102可在接收到预测移动设备102的未来位置的请求时确定过渡概率密度602。所述请求可与当前时间和未来时间相关联。在当前时间，移动设备102可位于对应于状态106的显著位置处。未来时间可以是时间点或时间窗口。\n[0053] 过渡概率密度602可以是一个时间段(例如[Ta,Tb])上的分布，其中Ta是这个时间段的开始时间，Tb是这个时间段的结束时间。时间段[Ta,Tb]可以是预测窗口。在一些具体实施中，开始时间Ta可对应于当前时间、或者具有偏差的当前时间(例如当前时间之前或之后X分钟)；结束时间Tb可对应于未来时间、或者具有偏差的未来时间(例如未来时间之前或之后Y分钟)。在一些具体实施中，开始时间Ta和结束时间Tb可分别对应于一个时间窗口(例如一天或一周)的开始和结束。\n[0054] 移动设备100可基于移动设备100从状态106到状态402的过去过渡来确定过渡概率密度602。在Ta和Tb之间的给定时间，(1)过去在所述给定时间从状态106到状态402的越多过渡可对应于越高的概率密度值；(2)过去在所述给定时间对过渡的越多的确定性可对应于越高的概率密度值；并且(3)过去在所述给定时间过渡的越稳定模式可对应于越高的概率密度值。\n[0055] 例如，t0对应于上午8点，t1对应于下午3点。在过去并且如状态模型104中所记录的，在上午7点和上午9点之间在状态106和状态402之间发生了X次过渡；并且在下午2点和下午4点之间发生了Y次过渡。如果X大于Y，则t0可对应于相对较高的概率密度值604，而t1可对应于相对较低的概率密度值606。\n[0056] 此外，过渡的确定性可以是相关的。如果这X次过渡的过渡开始时间戳的平均时间更接近t0的程度更甚于这Y次过渡的过渡开始时间戳的平均时间更接近于t1的程度，则t0可对应于相对较高的概率密度值604，而t1可对应于相对较低的概率密度值606。如果这X次过渡的过渡开始时间戳的方差比这Y次过渡的过渡开始时间戳的方差小，则t0可对应于相对较高的概率密度值604，而t1可对应于相对较低的概率密度值606。\n[0057] 此外，过去过渡模式的稳定性可以是相关的。移动设备102可基于时间来确定移动模式。例如，移动设备102可基于状态模型104中的过渡来确定移动设备102的移动是按照星期模式的。在工作日，移动设备102在上午7点和上午9点之间从状态106过渡到状态402。在周末，移动设备102在下午2点和下午4点之间从状态106过渡到状态402。基于这个所识别的星期模式，移动设备102可在t0在工作日的情况下为时间t0关联相对较高的概率密度值\n604，或者在t0在周末的情况下为时间t0关联相对较低的概率密度值。\n[0058] 过渡概率密度602可以是离散的，也可以是连续的。在确定过渡概率密度602和状态模型104的状态之间的其他过渡概率密度后，移动设备102可确定移动设备102从当前状态(例如状态106)直接或间接(例如通过一个或多个中间状态)过渡到每个其他状态的基于时间的可能性。移动设备102可基于当前位置、未来时间、和移动设备102过渡到每个状态的概率来确定所预测的移动设备102的未来位置。\n[0059] 图6B是示出确定示例性状态106的进入概率密度620的示意图。进入概率密度620可指示移动设备102从在状态模型104中没有表示的当前位置进入状态106的概率分布。移动设备102可在接收到用于预测移动设备102的未来位置的请求时确定进入概率密度620。\n所述请求可与当前时间和未来时间相关联。在当前时间，移动设备102可位于未表示的当前位置处。未来时间可以是时间点或时间窗口。\n[0060] 进入概率密度620可以是一个时间段(例如[Tc,Td])上的分布，其中Tc是这个时间段的开始时间，Td是这个时间段的结束时间。时间段[Tc,Td]可以是预测窗口。在一些具体实施中，开始时间Tc可对应于当前时间、或者具有偏差的当前时间(例如当前时间之前或之后X分钟)；结束时间Td可对应于未来时间、或者具有偏差的未来时间(例如未来时间之前或之后Y分钟)。在一些具体实施中，开始时间Tc和结束时间Td可分别对应于一个时间窗口(例如一天或一周)的开始和结束。\n[0061] 移动设备102可基于移动设备102在状态106中的停留时间来确定进入概率密度\n620。停留时间(例如停留时间412、414、和622)可如上文中参考图4所述那样来确定。\n[0062] 在Tc和Td之间的给定时间，(1)移动设备102过去在所述给定时间越多次停留在状态106中可对应于越高的概率密度值；(2)过去进入到状态106中的越高的进入确定性可对应于越高的概率密度值；并且(3)过去进入到状态106中的越稳定的进入模式可对应于越高的概率密度值。\n[0063] 例如，t2对应于上午10点，t3对应于下午3点。在过去并且如状态模型104中通过停留时间412、414、和622所记录的，在X次的情形中，移动设备102在时间t2位于状态106中；并且在Y次的情形中，移动设备102在时间t3位于状态106中。如果X小于Y(例如在这个实例中，X＝2，Y＝3)，则t2可对应于相对较低的概率密度值624，而t3可对应于相对较高的概率密度值626。\n[0064] 附加地或另选地，移动设备102可基于根据状态模型104所确定的状态停留时间来确定移动设备102的位置是按照星期模式。例如，移动设备102可确定停留时间414和多个其他停留时间只在工作日发生，而停留时间412和622只在周末发生。基于这个所识别的星期模式，移动设备102可在时间t2和时间t3落在工作日的情况下将相对较低的概率密度值624关联到时间t2，而将较高的概率密度值624关联到时间t3。移动设备102可将相等的概率密度值关联到落在周末的时间t2和时间t3。\n[0065] 进入概率密度620可以是离散的或是连续的。在确定进入概率密度620和状态模型\n104的状态之间的其他进入概率密度后，移动设备可确定移动设备102从当前位置直接或间接(例如通过一个或多个中间状态)进入到每个其他状态的基于时间的可能性。移动设备\n102可基于当前位置、未来时间、和移动设备102进入每个状态的概率来确定所预测的移动设备102的未来位置。\n[0066] 移动设备102可在基于各种因素计算进入概率密度之前、期间、或之后从状态模型\n104中滤除状态。滤除状态可包括阻止这个状态被用于特定位置预测，而不将这个状态从状态模型104中移除。用于滤除状态的因素可包括当前位置与状态模型104中状态所表示的位置之间的距离。移动设备102可在确定移动设备102在预测时间窗口期间不太可能从当前位置到达某个状态的位置时滤除那个状态。移动设备可基于当前时间与时间窗口的开始时间或结束时间之间的时间差、以及移动设备102的移动的预先指定的最大速度来执行所述滤除。\n[0067] 例如，移动设备102可确定当前时间与预测时间窗口的结束时间Td之间的时间差为X小时。移动设备可确定当前位置与由状态106所表示的显著位置之间的距离为Y公里。基于预先指定的最大速度每小时Z公里，移动设备102可在确定X*Z