基于位置历史确定用户相似性的制作方法
专利名称：基于位置历史确定用户相似性的制作方法
基于位置历史确定用户相似性诸如全球定位系统(GPS)和全球移动通信系统(GSM)网络等位置获取技术的日渐流行导致许多个体的大量时空数据集的集合。此数据集提供了发现用户移动行为的有价值的知识的机会，所述知识包括基本信息，例如特定路径的距离、持续时间和速度等。该知识可被用于找出用户之间的相似性，因为有类似位置历史的人可能共享类似的兴趣和偏好。 因此，用户共享的位置历史越多，这些用户可能越相关联。MM此处所述为用于基于位置历史确定用户相似性的各种技术的实现。在一个实现中，计算机应用程序可从计算网络中的两个或多个用户处接收全球定位系统(GPQ日志。 该计算机应用程序可将每个GPS日志中所列的纬度和经度坐标对映射为地图上的一个节点。在将坐标对映射到地图上时，计算机应用程序可添加从一个节点到另一个的箭头以指示各个坐标对被各用户访问的顺序。所得到的地图可指示该用户的GPS轨迹或第一位置历史。计算机应用程序然后可定位可能在第一位置历史上的一个或多个停留点。在一个实现中，停留点可作为在一组节点的中心的带纬度和经度坐标的虚拟位置，所述一组节点可均为在彼此的近距离内。所述计算机应用程序然后可将两个或多个停留点分组在一起以创建群集。群集可被定义为围绕多个密集地位于彼此附近的停留点的地理区域。在一个实现中，每个群集可包括两个或多个子群集。每个子群集可包括两个或多个在所述群集内的停留点，但是子群集内的停留点可能比群集内的停留点彼此更为接近。在为网络中的所有用户确定了群集和子群集后，计算机应用程序可创建等级框架以表示所有的群集和子群集。该等级框架可在一个层的等级中列出所有群集和子群集，从而使得等级中每个更高层可描述更大的地理区域。每个子群集可表示框架中的一层，该层位于其相对的群集所处的层之下。由所述等级框架，计算机应用程序可作为每个用户创建等级图。所述等级图可包括等级图的每层的一个或多个图，其可指示用户可能在其中途经过的群集或子群集。使用两个用户的等级图，计算机应用程序可通过评估两个用户均途经过的位置以确定这两个用户之间的相似性。在确定两个用户之间的相似性时，计算机应用程序可以某些项为因子，例如，被用户所访问的位置的热门性、两个用户行进至多个位置的类似顺序、 以及每个用户行进至多个位置所用时间。提供以上引用的概述章节以便以简化形式介绍将在以下详细描述章节中进一步描述的一些概念。本发明内容并不旨在标识所要求保护的主题的关键特征或必要特征，也不旨在用于限制所要求保护的主题的范围。此外，所要求保护的主题不限于解决在本发明的任一部分中提及的任何或所有缺点的实现。附图简述
图1示出其中可结合和实践此处所描述的各种技术的计算系统的示意图。图2示出根据此处所描述的各种技术的一个或多个实现的用于创建等级图以模
6拟一个或多个用户的位置历史的方法的流程图。图3示出了表示根据此处所描述的各种技术的一个或多个实现的用于创建等级图的过程的示意图。图4示出根据此处所描述的各种技术的一个或多个实现的用于基于位置历史确定两个用户之间的用户相似性的方法的流程图。详细描述通常，此处所描述的一个或多个实现涉及基于位置历史确定用户相似性。将在以下段落中结合附图1-4更为详细地描述用于基于位置历史确定用户相似性的各种技术的一个或多个实现。此处所描述的各种技术的实现可以用众多通用或专用计算系统环境或配置来操作。适用于此处所描述的各种技术的公知的计算系统、环境和/或配置的示例包括，但不限于，个人计算机、服务器计算机、手持式或膝上型设备、多处理器系统、基于微处理器的系统、机顶盒、可编程消费电子产品、网络PC、小型机、大型计算机、包括上述系统或设备中的任一个的分布式计算环境等。此处所描述的各种技术可以在诸如程序模块等由计算机执行的计算机可执行指令的一般上下文中实现。一般而言，程序模块包括执行特定的任务或实现特定的抽象数据类型的例程、程序、对象、组件、数据结构等。此处所描述的各种技术还可在其中任务由通过例如硬连线链路、无线链路或其组合等通信网络链接的远程处理设备执行的分布式计算环境中实现。在分布式计算环境中，程序模块可以位于包括存储器存储设备在内的本地和远程计算机存储介质中。图1示出其中可结合和实践此处所描述的各种技术的计算系统100的示意图。虽然计算系统100可以是如上所述的常规台式或服务器计算机，但可以使用其它计算机系统配置。计算系统100可包括中央处理单元(CPU) 21、系统存储器22和将包括系统存储器 22在内的各种系统组件耦合到CPU 21的系统总线23。虽然图1中只示出了一个CPU，但应当理解，在一些实现中计算系统100可包括超过一个CPU。系统总线23可以是几种类型的总线结构中的任何一种，包括存储器总线或存储控制器、外围总线、以及使用各种总线体系结构中的任一种的局部总线。作为示例，而非限制，这样的体系结构包括工业标准体系结构(ISA)总线、微通道体系结构(MCA)总线、增强型ISA(EISA)总线、视频电子技术标准协会(VESA)局部总线和外围部件互连(PCI)总线(也称为小背板(Mezzanine)总线)。系统存储器22可包括只读存储器(ROM) 24和随机访问存储器(RAM) 25。基本输入/输出系统 ("BIOS") 26可以被存储在ROMM中，它包含有助于例如在启动期间在计算机系统100内的各个元件之间传送信息的基本例程。计算系统100还可包括用于对硬盘进行读写的硬盘驱动器27、用于对可移动磁盘 29进行读写的磁盘驱动器28、以及用于对诸如CD-ROM或其它光介质等可移动光盘31进行读写的光盘驱动器30。硬盘驱动器27、磁盘驱动器观以及光盘驱动器30可分别通过硬盘驱动器接口 32、磁盘驱动器接口 33和光盘驱动器接口 34连接至系统总线23。驱动器及其关联的计算机可读介质可以向计算系统100提供对计算机可读指令、数据结构、程序模块和其它数据的非易失性存储。
虽然此处将计算系统100描述为具有硬盘、可移动磁盘四和可移动光盘31，但本领域技术人员应当理解，计算系统100还可以包括可由计算机访问的其它类型的计算机可读介质。例如，这种计算机可读介质可包括计算机存储介质和通信介质。计算机存储介质可包括以用于存储诸如计算机可读指令、数据结构、程序模块或其它数据等信息的任何方法或技术实现的易失性和非易失性、以及可移动和不可移动介质。计算机存储介质还可包括，RAM、ROM、可擦可编程只读存储器(EPROM)、电可擦可编程只读存储器(EEPROM)、闪存或其它固态存储器技术、CD-ROM、数字多功能盘(DVD)或其它光盘存储、磁带盒、磁带、磁盘存储或其它磁性存储设备、或能用于存储所需信息且可以由计算系统100访问的任何其它介质。通信介质能以诸如载波或其它传输机制等已调制数据信号来体现计算机可读指令、数据结构、程序模块或其它数据，并且包括任何信息传递介质。术语“已调制数据信号”可指的是以在信号中编码信息的方式设定或更改其一个或多个特征的信号。作为示例而非限制， 通信介质包括有线介质，诸如有线网络或直接线连接，以及无线介质，诸如声学、射频、红外线和其他无线介质。上述的任意组合也可以包含在计算机可读介质的范围内。多个程序模块能存储在硬盘27、磁盘四、光盘31、ROM 24或RAM 25上，包括操作系统35、一个或多个应用程序36、位置相似性应用程序60、程序数据38和数据库系统55。 操作系统35可以是能控制联网的个人或服务器计算机的操作的任何合适的操作系统，如 Windows XP、Mac 0S X、Unix变型(例如Linux 和BSD )等。位置相似性应用程序 60可作为能使用户基于两个或多个用户的位置历史以确定他们的相似性的应用程序。位置相似性应用程序60将参考图2-4在以下段落中更详细地描述。用户可通过诸如键盘40和定点设备42等输入设备向计算系统100中输入命令和信息。其它输入设备可以包括话筒、操纵杆、游戏手柄、圆盘式卫星天线、扫描仪等等。这些和其它输入设备可通过耦合到系统总线23的串行端口接口 46连接到CPU 21，但是可以通过诸如并行端口、游戏端口或通用串行总线(USB)等其它接口连接。全球定位系统(GPS) 设备61可通过串行端口接口 46连接到计算系统100。GPS设备61可包括关于用户已经途经的位置的位置数据。位置数据可上传至计算系统100，经由串行端口接口和系统总线23 而至系统存储器22或硬盘驱动器27以供存储。监视器47或其它类型的显示设备也可经由接口，诸如视频适配器48，连接至系统总线23。除监视器47之外，计算系统100还可包括其它外围输出设备，如扬声器和打印机。此外，计算系统100可以使用到一个或多个远程计算机的逻辑连接在联网环境中工作。逻辑连接可以是办公室、企业范围计算机网络、内联网和因特网中常见的任何连接， 如局域网(LAN)51和广域网(WAN)52。当在LAN联网环境中使用时，计算系统100可通过网络接口或适配器53连接到局域网51。当在WAN联网环境中使用时，计算系统100可包括调制解调器M、无线路由器或用于通过诸如因特网等广域网52来建立通信的其它装置。或为内置或为外置的调制解调器M可经由串行端口接口 46连接到系统总线23。在联网环境中，就计算系统100所描绘的程序模块或各其部分可被储存在远程存储器存储设备中。能够理解，所示的网络连接是示例性的，并且可以使用在计算机之间建立通信链路的其他手段。应该理解，此处描述的各种技术可以结合硬件、软件或两者的组合来实现。因此， 各种技术或其某些方面或部分，可以采用包含在诸如软盘、⑶-ROM、硬盘驱动器或任何其它
8机器可读存储介质等有形介质中的程序代码(即，指令)的形式，其中，当程序代码被加载至诸如计算机等机器并由其运行时，该机器成为用于实现该各种技术的装置。在程序代码在可编程计算机上执行的情况下，计算设备可包括处理器、该处理器可读的存储介质(包括易失性和非易失性的存储器和/或存储元件)、至少一个输入设备、以及至少一个输出设备。可以实现或利用此处所描述的各种技术的一个或多个程序可以使用应用程序编程接口 (API)、可重用控件等。这样的程序可以用高级过程语言或面向对象编程语言来实现，以与计算机系统通信。然而，如果需要，程序可以用汇编语言或机器语言来实现。在任一情况下， 语言都可以是编译的或解释的语言，并与硬件实现相结合。图2示出根据此处所描述的各种技术的一个或多个实现的用于创建等级图以模拟一个或多个用户的位置历史的方法的流程图。以下方法200的描述是根据此处所描述的各种技术的一个或多个实现参考图1的计算系统100来作出的。此外，应当理解，尽管操作流程图指示了操作执行的特定次序，但在某些实现中，这些操作的特定部分可按照不同的次序执行。在一个实现中，用于创建等级图以模拟一个或多个用户的位置历史的过程可由位置相似性应用程序60来执行。在步骤210，位置相似性应用程序60可从计算网络中的一个或多个用户处接收一个或多个GPS日志，所述GPS日志可存储于GPS设备61、系统存储器22、硬盘驱动器27、或相似性存储器存储设备。GPS日志可包括GPS位置信息，例如每个被用户所访问的位置的一对纬度和经度坐标，以及指示每个坐标对何时被访问的对应时间戳。在步骤220，位置相似性应用程序60由从两个或多个用户的GPS日志编制 (formulate)出GPS路径或第一位置历史。第一位置历史可描述用户已经途经的路径，并包括根据时间戳而按时间先后排列的纬度和经度坐标对的列表的显示。在一个实现中，位置相似性应用程序60可从用户的GPS日志中提取每个纬度和经度坐标对(GPS坐标)以及这些坐标对的时间戳。位置相似性应用程序60然后可将每个纬度和经度坐标对表示为图或地图上的一个节点。位置相似性应用程序60可以箭头连接图上的每个节点，从而箭头方向为从一个节点到用户所访问的下一节点。节点也可包括对应于坐标的时间戳。在步骤230，位置相似性应用程序60可确定一个或多个GPS日志的停留点。停留点可表示在用户可能停留了超过特定时间间隔的地理区域的中心的虚拟位置。停留点的确定可依赖于距离阈值(Diwt)和时间阈值(Tiwt)。在一个实现中，停留点可被认为是由一组节点所表征的虚拟位置，其中每个节点之间的距离可小于距离阈值，而所述组中第一节点和最后节点的时间间隔可大于时间阈值。在一个实现中，停留点可通过找出所述节点组的纬度坐标的平均值以及所述节点组的经度坐标的平均值来生成。停留点可被视为具有和所述节点组的纬度坐标平均值和经度坐标平均值相同的纬度坐标和经度坐标。在一个实现中，每个停留点(Si)可被一组包括纬度坐标、经度坐标、到达时间、以及离开时间的数据所描述，或者S=[纬度坐标(Lat)，经度坐标(Lngt)，到达时间(arv)， 离开时间(d印)]，其中停留点纬度(Lat)= Σ =πι Pi-Lat/\P\停留点讳度(Lngt)= Σ =πι Pi-^ngt/\Ρ\
停留点到达时间(arv) = pm. T停留点离开时间(cbp) = pn. T此处，P可表示GPS点的集合P= {pl,p2,…，pn}，且每个GPS点pi e P可包括一个纬度(pi. Lat)、一个经度(pi. Lngt)、和一个时间戳(pi. Τ)。停留点到达和离开时间可表示用户到达和离开该停留点的时间。典型地，当个人保持静止的时间超过时间阈值时(例如，当个人进入了建筑物并丢失卫星信号一段时间直至返回户外)，或当用户在特定的地理空间范围内徘徊的时间周期超过了时间阈值时(例如，当个人在户外旅行并被周围环境所吸引时)，可获得停留点。在步骤Μ0，位置相似性应用程序60可用在步骤230所获得的停留点以编制第二位置历史。第二位置历史可包括用户可能访问超过一时间间隔的停留点的记录。在一个实现中，第二位置历史可包括可在步骤230所确定的停留点的序列。该第二位置历史可描述位置以及用户访问一个或多个位置的顺序。第二位置历史(LocH)可被定义为
Ati At 2 Atn^1LocH = (S1 — S2 —,…,——^ Sn) 其中 Si G S，并且 Δ = si+1. BrvT-Si. IevT
f其中Si可表示特定的停留点，而Ati可表示用户从一个停留点到下一个停留点所用的时间量。在步骤250，位置相似性应用程序60可作为在步骤230所确定的所有停留点确定一个或多个群集。每个群集可包括一个或多个可密集地填充在一个地理区域内的停留点。 在一个实现中，位置相似性应用程序60可收集存储在存储器中的每个GPS日志的所有停留点，并将该停留点的集合提供给基于密度的群集算法以基于数据集中的停留点的地理空间区域来创建一个或多个等级群集。在一个实现中，第一群集可包括围绕一大集合区域的最大数量的停留点。第一群集可作为等级群集的最高层的部分。所述基于密度的群集算法可进一步在第一群集中定位一个或多个子群集。每个子群集可包括可作为第一群集的部分的一个或多个停留点；然而，可作为子群集的部分的停留点可包括比在第一群集中的停留点更为密集地填充的停留点。所述基于密度的群集算法可依靠一个或多个停留点的接近度来在群集中定位附加的子群集。每个子群集可表示其群集在等级群集中所在层的下方一层。在一个实现中，每个子群集可表示比其可作为其中部分的群集更小的地理区域。在步骤沈0，位置相似性应用程序60可基于在步骤250所确定的群集和子群集编制等级框架。该等级框架F可被定义为在一个或多个层L上的群集C(以及子群集)的集合，从而F= (C，L)，其中L= {11；12,…，IJ，其中Cij表示在层Ii e L上的停留点S的第 j个群集，而Ci是层Ii上的群集的集合。在一个实现中，来自各个用户或GPS日志的停留点可被分配给一个或多个层L上的一个或多个群集C。例如，停留点的第一群集可包括其内部的一个或多个子群集。此处，第一群集可被视为等级框架的顶(高)层，而第一群集内的各子群集可被视为在所共享的等级框架的同一层上，该层可作为等级框架的第一群集层下方的一层。从等级框架的顶部到底部，群集的集合范围减小，而集合区域的粒度可从粗略增加为细致。该框架的等级特征可用于以不同相似性等级来区分人。因此，共享等级框架的较低层上的类似第二位置历史的用户要比共享较高层上的第二位置历史的用户更为相关联。共享等级框架的示例被示于图3。
10
在步骤270，位置相似性应用程序60可基于每个用户的等级框架(F)和第二位置历史(LocH)以构建个人等级图(HG)。该个人等级图HG可包括描述根据用户的第二位置历史该用户已经途经的群集或子群集的一个或多个图。在一个实现中，位置相似性应用程序 60可用等级框架的每个层交叉引用用户的第二位置历史。位置相似性应用程序60可将第二位置历史中的用户停留点映射至其在等级框架中的各层中的各自群集或子群集。群集或子群集然后可包括用户的停留点，而一个边可连接两个群集或子群集以表示用户可访问各个群集或子区级(地理区域)的顺序。个人等级图可包括一个或多个图，从而每个图对应等级框架的一个层。给定用户的第二位置历史和等级框架，该用户的等级图可被编制为一组图，其描述HG= (Gi = (Ci5Ei)5K i ^ |L|}，其中每个层Ii e LiGi e HG，而一组顶点或群集Ci以及边Ei可连接Cij e Ci。图3示出了表示根据此处所描述的各种技术的一个或多个实现的用于创建等级图的过程300的示意图。以下过程300的描述是根据此处所描述的各种技术的一个或多个实现参考图1的计算系统100以及图2的方法200来作出的。应当理解，尽管过程300指示了操作执行的特定次序，但在某些实现中这些操作的特定部分可按照不同的次序执行。另外，过程300可对应图2中所例示的某些步骤。在某些实现中，过程300可包括来自两个或更多个用户的两个或更多个GPS日志 GL、一个或多个群集cu、一个或多个停留点S、一个等级框架F、一个或多个等级图HG、一个或多个第二位置历史、以及一个或多个层1。图3示出根据图2中所描述的方法200为两个用户所创建的等级框架和两个用户等级图HG。参考步骤210，GPS日志GL可包括一个或多个用户的一个或多个GPS日志GL。在一个实现中，GPS日志GL可从GPS设备61处下载，并存储在可被计算系统100所访问的存储器存储设备中。参考步骤230，位置相似性应用程序60可由GPS日志GL在一图上创建一个或多个节点以表示停留点S。如图3中所示，停留点S可由节点来表示。在一个实现中，位置相似性应用程序60可为每个用户的GPS日志GL确定停留点S。参考步骤250，位置相似性应用程序60可用一基于密度的群集算法来确定一个或多个群集cu。位置相似性应用程序60可通过将一个或多个停留点包括在一个圆内来在图上指示群集cu。群集中的第j个变量可被编号以区分在共享等级框架F的特定层Ii上的各个不同群集，且第i个变量可对应于其中可放置群集的层1”在群集中，位置相似性应用程序60可找出一个或多个子群集c(i+1…其可包括比原群集中的停留点S的彼此距离更接近的一组停留点S。在群集中的每个子群集c(i+1”可指示在共享等级框架F 或等级图HG中的一个新级别或层Ii。每个子群集Ci(J+1)，如果其自身内部包括两个或多个子群集c(i+2)j，则其也可被视为群集c(i+1)j。例如，在过程300中，群集C1可表示群集Cij的最大的地理区域(层Ii = 1)，因为其包括了来自每个GPS日志GL的所有停留点S。子群集C2可表示群集C1的子群集(层Ii =幻。子群集C3然后可表示子群集C2的子群集(层 Ii =幻。群集的每个层可表示共享等级框架F中的一级或一层，或可表示可作为等级图HG的部分的独立图。层Ii可对应于停留点S的接近度，从而层I(C1)可对应较大的地理区域，而较低层(2+级)可对应逐渐更小的地理区域。参考步骤沈0，位置相似性应用程序60可通过根据群集Cij可对应的层来表示群集Cu，从而编制共享等级框架F。例如，群集从Cltl可对应群集C1、群集C2tl和群集C21可对应群集c2，而群集c3(1、c31、c32、C33及C34可对应上述的群集c3。可在等级框架F的最低层Ii 上的各个群集中表示停留点S。参考步骤270，位置相似性应用程序60可为特定用户编制等级图HG。在一个实现中，位置相似性应用程序60可根据用户的GPS日志GL从等级框架F中提取用户的群集Cij 和停留点S。在等级框架F的不同层Ii上的每个群集可对应不同的图&。在一个实现中，位置相似性应用程序60可由特定用户的GPS日志GL来确定第二位置历史LocH。例如，可通过将用户1的GPS日志GL1的停留点S组织为时间顺序并用指向箭头连接每个停留点来确定用户1的第二位置历史LocHlt5然后可通过用将第二位置历史LocH1和等级框架F中的群集其包括第二位置历史LocH1的停留点)相映射来确定等级图HG115第二位置历史LocH1的停留点S部分可按照在等级框架F中列出的群集Cij来分组。等级框架F的每个层Ii可对应等级图HG的一个图G”图4示出根据此处所描述的各种技术的一个或多个实现的用于基于位置历史确定两个用户之间的用户相似性的方法400的流程图。以下方法400的描述是根据此处所描述的各种技术的一个或多个实现参考图1的计算系统100以及图3的过程300来作出的。 此外，应当理解，尽管操作流程图指示了操作执行的特定次序，但在某些实现中，这些操作的特定部分可按照不同的次序执行。在一个实现中，可由位置相似性应用程序60来执行用于基于位置历史而确定用户相似性的方法。在步骤410，位置相似性应用程序60可从两个用户(由相似性应用程序60来为其确定相似性)的等级图HG中的各图中提取一系列群集或子群集。在一个实现中，每个用户的等级图HG可提供用户的第二位置历史LocH的有效表示，其可暗示基于不同范围的地理空间的一系列用户移动行为。给定如图3中所示的两个用户^和心的HGjP HG2，位置相似性应用程序60可首先定位在每个层Ii e L上被两个用户共享的的一个或多个相同图顶点片‘2，其中
权利要求
1.一种用于确定网络中第一用户和第二用户之间的相似性的方法包括 从所述网络中各用户处接收一个或多个全球定位系统(GPQ日志；构建针对第一用户的GPS日志的第一等级图和针对第二用户的GPS日志的第二等级图；以及基于所述第一等级图和第二等级图计算第一和第二用户之间的相似性得分。
2.如权利要求1所述的方法，其特征在于，构建第一等级图和第二等级图包括 将GPS日志的信息合并入等级框架中；基于所述等级框架创建针对第一用户的GPS日志的第一等级图；以及基于所述等级框架创建针对第二用户的GPS日志的第二等级图。
3.如权利要求2所述的方法，其特征在于，合并GPS日志的信息包括基于每个用户的GPS日志编制第一位置历史，其描述每个用户以时间顺序所途经的一个或多个位置；确定沿每个第一位置历史的一个或多个停留点； 将所述停留点分组成一个或多个群集； 将所述群集中的停留点分组为一个或多个子群集；以及将所述群集映射至所述等级框架的一个或多个较高层；以及将所述子群集映射至所述等级框架的一个或多个较低层。
4.如权利要求3所述的方法，其特征在于，确定停留点包括标识所述一个或多个位置的位于预定距离阈值内的部分，其中所述部分中的第一位置和最后位置之间的时间间隔超过了预定时间阈值； 为每个标识的位置提取纬度坐标和经度坐标； 计算所述位置的所述部分的纬度坐标和经度坐标的平均值；以及在所述纬度坐标和经度坐标的平均值处创建停留点。
5.如权利要求3所述的方法，其特征在于，使用基于密度的群集算法将所述停留点分组为群集和子群集。
6.如权利要求3所述的方法，其特征在于，创建第一等级图包括基于第一用户的GPS日志编制以时间先后顺序描述第一用户所途经的停留点的第二位置历史；将第二位置历史的停留点映射至所述等级框架的各层中的群集或子群集；以及为所述等级框架的各层创建一图，该图描述第一用户所途经的群集或子群集。
7.如权利要求3所述的方法，其特征在于，创建第二等级图包括基于第二用户的GPS日志编制以时间先后顺序描述第二用户所途经的停留点的第三位置历史；将第三位置历史的停留点映射至所述等级框架的各层中的群集或子群集；以及为所述等级框架的各层创建一图，该图描述被第二用户所途经的群集或子群集。
8.如权利要求3所述的方法，其特征在于，计算第一和第二用户之间的相似性等分包括从第一等级图和第二等级图中的一个或多个图中提取第一用户和第二用户所途经的群集或子群集的序列，其中第一等级图中的各图描述第一用户所途经的群集或子群集，而第二等级图中的各图描述第二用户所途经的群集或子群集； 将各序列分割成一个或多个子序列；标识第一用户和第二用户所途经的、具有最大数量的共同群集或子群集的子序列； 使用逆文档频率方法量化所述子序列中的各群集或子群集的热门度，其中所述共同群集或子群集的逆文档频率被定义为⑴ =ZDag，其中Hij定义所述网络中访问了所述共同群集或子群集的用户的总数量，U定义网络中的用户总数量；确定每个共同群集或子群集的相似性得分sV其中相似性得分ss,等于腳g X mini^p,mq)，且其中min (叫，y代表第一和第二用户连续访问所述共同群集或子群集的一次或多次； 添加每个共同群集或子群集的相似性得分；以及归一化总和。
9.如权利要求8所述的方法，其特征在于，所述最大数量的共同群集或子群集是相同时间先后顺序的。
10.如权利要求8所述的方法，其特征在于，在所述最大数量的共同群集或子群集中， 每个群集或子群集之间的行进时间是基本相似的。
11.如权利要求8所述的方法，其特征在于，分割各序列包括确定所述序列中两个连续的群集或子群集之间的时间量是否超过一时间值；以及当所述两个连续的群集或子群集超过所述时间值时，将所述序列分割成子序列。
12.如权利要求8所述的方法，其特征在于，计算第一和第二用户之间的相似性等分还包括基于所述最大数量的共同群集或子群集，为每个共同群集或子群集的相似性得分分配权重。
13.如权利要求8所述的方法，其特征在于，计算第一和第二用户之间的相似性等分还包括基于所述等级框架中所述最大数量的共同群集或子群集所处的一层，为每个共同群集或子群集的相似性得分分配权重。
14.一种计算机系统，包括 处理器；以及存储器，其包括可由所述处理器执行以用于以下动作的程序指令 从网络中两个或更多个用户处接收一个或多个全球定位系统(GPQ日志； 将GPS日志的信息合并入等级框架中；基于所述等级框架创建针对第一用户的GPS日志的第一等级图；以及基于所述等级框架创建针对第二用户的GPS日志的第二等级图；以及基于所述第一等级图和第二等级图计算第一和第二用户之间的相似性得分。
15.如权利要求14所述的计算机系统，其特征在于，所述可由所述处理器执行以将GPS 日志的信息合并入等级框架中的程序指令包括可由所述处理器执行以进行以下动作的程序指令基于每个用户的GPS日志编制第一位置历史，其描述各用户以时间顺序所途经的一个或多个位置；确定沿每个第一位置历史的一个或多个停留点； 将所述停留点分组成一个或多个群集； 将所述群集中的停留点分组为一个或多个子群集；以及将所述群集映射至所述等级框架的一个或多个较高层；以及将所述子群集映射至所述等级框架的一个或多个较低层。
16.如权利要求15所述的计算机系统，其特征在于，所述可由所述处理器执行以确定停留点的程序指令包括可由所述处理器执行以进行以下动作的程序指令标识所述一个或多个位置的位于预定距离阈值内的部分，其中所述部分中的第一位置和最后位置之间的时间间隔超过预定时间阈值； 为每个标识的位置提取纬度坐标和经度坐标； 计算位置的所述部分的纬度坐标和经度坐标的平均值；以及在所述纬度坐标和经度坐标的平均值处创建停留点。
17.如权利要求15所述的计算机系统，其特征在于，使用基于密度的群集算法将所述停留点分组为群集和子群集。
18.一种其上存储有计算机可执行指令的计算机可读介质，所述指令在由计算机执行时使得所述计算机从网络中两个或更多个用户处接收一个或多个全球定位系统(GPQ日志； 基于各用户的GPS日志编制以时间先后顺序描述各用户所途经的一个或多个位置的第一位置历史；确定沿每个第一位置历史的一个或多个停留点；将所述停留点分组成一个或多个群集；将所述群集中的停留点分组为一个或多个子群集；以及将所述群集映射至一等级框架的一个或多个较高层；将所述子群集映射至所述等级框架的一个或多个较低层；基于所述等级框架创建针对第一用户的GPS日志的第一等级图；基于所述等级框架创建针对第二用户的GPS日志的第二等级图；以及基于所述第一等级图和第二等级图计算第一和第二用户之间的相似性得分。
19.如权利要求18所述的计算机可读介质，其特征在于，所述用于计算第一用户和第二用户之间的相似性得分的计算机可执行指令被配置为从第一等级图和第二等级图中的一个或多个图中提取第一用户和第二用户所途经的群集或子群集的序列，其中第一等级图中的各图描述第一用户所途经的群集或子群集，而第二等级图中的各图描述第二用户所途经的群集或子群集； 将各序列分割成一个或多个子序列；标识第一用户和第二用户所途经的、具有最大数量的共同群集或子群集的子序列； 使用逆文档频率方法量化所述子序列中的各群集或子群集的热门度，其中所述共同群集或子群集的逆文档频率被定义为⑴ =,Mg,其中定义所述网络中访问了所述共同群集或子群集的用户的总数量，U定义网络中的用户总数量；为了每个共同群集或子群集确定相似性得分ssa，其中相似性得分等于IBFijxmin(mp,mq),且其中min(nip，mq)代表第一和第二用户连续访问所述共同群集或子群集的一次或多次；添加每个共同群集或子群集的相似性得分；以及归一化总和。
20.如权利要求18所述的计算机可读介质，其特征在于，使用基于密度的群集算法将所述停留点分组到所述群集或子群集中。
全文摘要
用于确定网络中第一用户和第二用户之间相似性的方法，包括从网络中各用户接收一个或多个全球定位系统(GPS)日志，构建针对第一用户的GPS日志的第一等级图和针对第二用户的GPS日志的第二等级图，并基于第一等级图和第二等级图计算第一用户和第二用户之间的相似性得分。
文档编号G06F9/44GK102203729SQ200980143794
公开日2011年9月28日 申请日期2009年11月3日 优先权日2008年11月3日
发明者W-Y·马, X·谢, Y·郑 申请人:微软公司
基于位置历史确定用户相似性诸如全球定位系统(GPS)和全球移动通信系统(GSM)网络等位置获取技术的日渐流行导致许多个体的大量时空数据集的集合。此数据集提供了发现用户移动行为的有价值的知识的机会，所述知识包括基本信息，例如特定路径的距离、持续时间和速度等。该知识可被用于找出用户之间的相似性，因为有类似位置历史的人可能共享类似的兴趣和偏好。 因此，用户共享的位置历史越多，这些用户可能越相关联。MM此处所述为用于基于位置历史确定用户相似性的各种技术的实现。在一个实现中，计算机应用程序可从计算网络中的两个或多个用户处接收全球定位系统(GPQ日志。 该计算机应用程序可将每个GPS日志中所列的纬度和经度坐标对映射为地图上的一个节点。在将坐标对映射到地图上时，计算机应用程序可添加从一个节点到另一个的箭头以指示各个坐标对被各用户访问的顺序。所得到的地图可指示该用户的GPS轨迹或第一位置历史。计算机应用程序然后可定位可能在第一位置历史上的一个或多个停留点。在一个实现中，停留点可作为在一组节点的中心的带纬度和经度坐标的虚拟位置，所述一组节点可均为在彼此的近距离内。所述计算机应用程序然后可将两个或多个停留点分组在一起以创建群集。群集可被定义为围绕多个密集地位于彼此附近的停留点的地理区域。在一个实现中，每个群集可包括两个或多个子群集。每个子群集可包括两个或多个在所述群集内的停留点，但是子群集内的停留点可能比群集内的停留点彼此更为接近。在为网络中的所有用户确定了群集和子群集后，计算机应用程序可创建等级框架以表示所有的群集和子群集。该等级框架可在一个层的等级中列出所有群集和子群集，从而使得等级中每个更高层可描述更大的地理区域。每个子群集可表示框架中的一层，该层位于其相对的群集所处的层之下。由所述等级框架，计算机应用程序可作为每个用户创建等级图。所述等级图可包括等级图的每层的一个或多个图，其可指示用户可能在其中途经过的群集或子群集。使用两个用户的等级图，计算机应用程序可通过评估两个用户均途经过的位置以确定这两个用户之间的相似性。在确定两个用户之间的相似性时，计算机应用程序可以某些项为因子，例如，被用户所访问的位置的热门性、两个用户行进至多个位置的类似顺序、 以及每个用户行进至多个位置所用时间。提供以上引用的概述章节以便以简化形式介绍将在以下详细描述章节中进一步描述的一些概念。本发明内容并不旨在标识所要求保护的主题的关键特征或必要特征，也不旨在用于限制所要求保护的主题的范围。此外，所要求保护的主题不限于解决在本发明的任一部分中提及的任何或所有缺点的实现。附图简述
图1示出其中可结合和实践此处所描述的各种技术的计算系统的示意图。图2示出根据此处所描述的各种技术的一个或多个实现的用于创建等级图以模
6拟一个或多个用户的位置历史的方法的流程图。图3示出了表示根据此处所描述的各种技术的一个或多个实现的用于创建等级图的过程的示意图。图4示出根据此处所描述的各种技术的一个或多个实现的用于基于位置历史确定两个用户之间的用户相似性的方法的流程图。详细描述通常，此处所描述的一个或多个实现涉及基于位置历史确定用户相似性。将在以下段落中结合附图1-4更为详细地描述用于基于位置历史确定用户相似性的各种技术的一个或多个实现。此处所描述的各种技术的实现可以用众多通用或专用计算系统环境或配置来操作。适用于此处所描述的各种技术的公知的计算系统、环境和/或配置的示例包括，但不限于，个人计算机、服务器计算机、手持式或膝上型设备、多处理器系统、基于微处理器的系统、机顶盒、可编程消费电子产品、网络PC、小型机、大型计算机、包括上述系统或设备中的任一个的分布式计算环境等。此处所描述的各种技术可以在诸如程序模块等由计算机执行的计算机可执行指令的一般上下文中实现。一般而言，程序模块包括执行特定的任务或实现特定的抽象数据类型的例程、程序、对象、组件、数据结构等。此处所描述的各种技术还可在其中任务由通过例如硬连线链路、无线链路或其组合等通信网络链接的远程处理设备执行的分布式计算环境中实现。在分布式计算环境中，程序模块可以位于包括存储器存储设备在内的本地和远程计算机存储介质中。图1示出其中可结合和实践此处所描述的各种技术的计算系统100的示意图。虽然计算系统100可以是如上所述的常规台式或服务器计算机，但可以使用其它计算机系统配置。计算系统100可包括中央处理单元(CPU) 21、系统存储器22和将包括系统存储器 22在内的各种系统组件耦合到CPU 21的系统总线23。虽然图1中只示出了一个CPU，但应当理解，在一些实现中计算系统100可包括超过一个CPU。系统总线23可以是几种类型的总线结构中的任何一种，包括存储器总线或存储控制器、外围总线、以及使用各种总线体系结构中的任一种的局部总线。作为示例，而非限制，这样的体系结构包括工业标准体系结构(ISA)总线、微通道体系结构(MCA)总线、增强型ISA(EISA)总线、视频电子技术标准协会(VESA)局部总线和外围部件互连(PCI)总线(也称为小背板(Mezzanine)总线)。系统存储器22可包括只读存储器(ROM) 24和随机访问存储器(RAM) 25。基本输入/输出系统 ("BIOS") 26可以被存储在ROMM中，它包含有助于例如在启动期间在计算机系统100内的各个元件之间传送信息的基本例程。计算系统100还可包括用于对硬盘进行读写的硬盘驱动器27、用于对可移动磁盘 29进行读写的磁盘驱动器28、以及用于对诸如CD-ROM或其它光介质等可移动光盘31进行读写的光盘驱动器30。硬盘驱动器27、磁盘驱动器观以及光盘驱动器30可分别通过硬盘驱动器接口 32、磁盘驱动器接口 33和光盘驱动器接口 34连接至系统总线23。驱动器及其关联的计算机可读介质可以向计算系统100提供对计算机可读指令、数据结构、程序模块和其它数据的非易失性存储。
虽然此处将计算系统100描述为具有硬盘、可移动磁盘四和可移动光盘31，但本领域技术人员应当理解，计算系统100还可以包括可由计算机访问的其它类型的计算机可读介质。例如，这种计算机可读介质可包括计算机存储介质和通信介质。计算机存储介质可包括以用于存储诸如计算机可读指令、数据结构、程序模块或其它数据等信息的任何方法或技术实现的易失性和非易失性、以及可移动和不可移动介质。计算机存储介质还可包括，RAM、ROM、可擦可编程只读存储器(EPROM)、电可擦可编程只读存储器(EEPROM)、闪存或其它固态存储器技术、CD-ROM、数字多功能盘(DVD)或其它光盘存储、磁带盒、磁带、磁盘存储或其它磁性存储设备、或能用于存储所需信息且可以由计算系统100访问的任何其它介质。通信介质能以诸如载波或其它传输机制等已调制数据信号来体现计算机可读指令、数据结构、程序模块或其它数据，并且包括任何信息传递介质。术语“已调制数据信号”可指的是以在信号中编码信息的方式设定或更改其一个或多个特征的信号。作为示例而非限制， 通信介质包括有线介质，诸如有线网络或直接线连接，以及无线介质，诸如声学、射频、红外线和其他无线介质。上述的任意组合也可以包含在计算机可读介质的范围内。多个程序模块能存储在硬盘27、磁盘四、光盘31、ROM 24或RAM 25上，包括操作系统35、一个或多个应用程序36、位置相似性应用程序60、程序数据38和数据库系统55。 操作系统35可以是能控制联网的个人或服务器计算机的操作的任何合适的操作系统，如 Windows XP、Mac 0S X、Unix变型(例如Linux 和BSD )等。位置相似性应用程序 60可作为能使用户基于两个或多个用户的位置历史以确定他们的相似性的应用程序。位置相似性应用程序60将参考图2-4在以下段落中更详细地描述。用户可通过诸如键盘40和定点设备42等输入设备向计算系统100中输入命令和信息。其它输入设备可以包括话筒、操纵杆、游戏手柄、圆盘式卫星天线、扫描仪等等。这些和其它输入设备可通过耦合到系统总线23的串行端口接口 46连接到CPU 21，但是可以通过诸如并行端口、游戏端口或通用串行总线(USB)等其它接口连接。全球定位系统(GPS) 设备61可通过串行端口接口 46连接到计算系统100。GPS设备61可包括关于用户已经途经的位置的位置数据。位置数据可上传至计算系统100，经由串行端口接口和系统总线23 而至系统存储器22或硬盘驱动器27以供存储。监视器47或其它类型的显示设备也可经由接口，诸如视频适配器48，连接至系统总线23。除监视器47之外，计算系统100还可包括其它外围输出设备，如扬声器和打印机。此外，计算系统100可以使用到一个或多个远程计算机的逻辑连接在联网环境中工作。逻辑连接可以是办公室、企业范围计算机网络、内联网和因特网中常见的任何连接， 如局域网(LAN)51和广域网(WAN)52。当在LAN联网环境中使用时，计算系统100可通过网络接口或适配器53连接到局域网51。当在WAN联网环境中使用时，计算系统100可包括调制解调器M、无线路由器或用于通过诸如因特网等广域网52来建立通信的其它装置。或为内置或为外置的调制解调器M可经由串行端口接口 46连接到系统总线23。在联网环境中，就计算系统100所描绘的程序模块或各其部分可被储存在远程存储器存储设备中。能够理解，所示的网络连接是示例性的，并且可以使用在计算机之间建立通信链路的其他手段。应该理解，此处描述的各种技术可以结合硬件、软件或两者的组合来实现。因此， 各种技术或其某些方面或部分，可以采用包含在诸如软盘、⑶-ROM、硬盘驱动器或任何其它
8机器可读存储介质等有形介质中的程序代码(即，指令)的形式，其中，当程序代码被加载至诸如计算机等机器并由其运行时，该机器成为用于实现该各种技术的装置。在程序代码在可编程计算机上执行的情况下，计算设备可包括处理器、该处理器可读的存储介质(包括易失性和非易失性的存储器和/或存储元件)、至少一个输入设备、以及至少一个输出设备。可以实现或利用此处所描述的各种技术的一个或多个程序可以使用应用程序编程接口 (API)、可重用控件等。这样的程序可以用高级过程语言或面向对象编程语言来实现，以与计算机系统通信。然而，如果需要，程序可以用汇编语言或机器语言来实现。在任一情况下， 语言都可以是编译的或解释的语言，并与硬件实现相结合。图2示出根据此处所描述的各种技术的一个或多个实现的用于创建等级图以模拟一个或多个用户的位置历史的方法的流程图。以下方法200的描述是根据此处所描述的各种技术的一个或多个实现参考图1的计算系统100来作出的。此外，应当理解，尽管操作流程图指示了操作执行的特定次序，但在某些实现中，这些操作的特定部分可按照不同的次序执行。在一个实现中，用于创建等级图以模拟一个或多个用户的位置历史的过程可由位置相似性应用程序60来执行。在步骤210，位置相似性应用程序60可从计算网络中的一个或多个用户处接收一个或多个GPS日志，所述GPS日志可存储于GPS设备61、系统存储器22、硬盘驱动器27、或相似性存储器存储设备。GPS日志可包括GPS位置信息，例如每个被用户所访问的位置的一对纬度和经度坐标，以及指示每个坐标对何时被访问的对应时间戳。在步骤220，位置相似性应用程序60由从两个或多个用户的GPS日志编制 (formulate)出GPS路径或第一位置历史。第一位置历史可描述用户已经途经的路径，并包括根据时间戳而按时间先后排列的纬度和经度坐标对的列表的显示。在一个实现中，位置相似性应用程序60可从用户的GPS日志中提取每个纬度和经度坐标对(GPS坐标)以及这些坐标对的时间戳。位置相似性应用程序60然后可将每个纬度和经度坐标对表示为图或地图上的一个节点。位置相似性应用程序60可以箭头连接图上的每个节点，从而箭头方向为从一个节点到用户所访问的下一节点。节点也可包括对应于坐标的时间戳。在步骤230，位置相似性应用程序60可确定一个或多个GPS日志的停留点。停留点可表示在用户可能停留了超过特定时间间隔的地理区域的中心的虚拟位置。停留点的确定可依赖于距离阈值(Diwt)和时间阈值(Tiwt)。在一个实现中，停留点可被认为是由一组节点所表征的虚拟位置，其中每个节点之间的距离可小于距离阈值，而所述组中第一节点和最后节点的时间间隔可大于时间阈值。在一个实现中，停留点可通过找出所述节点组的纬度坐标的平均值以及所述节点组的经度坐标的平均值来生成。停留点可被视为具有和所述节点组的纬度坐标平均值和经度坐标平均值相同的纬度坐标和经度坐标。在一个实现中，每个停留点(Si)可被一组包括纬度坐标、经度坐标、到达时间、以及离开时间的数据所描述，或者S=[纬度坐标(Lat)，经度坐标(Lngt)，到达时间(arv)， 离开时间(d印)]，其中停留点纬度(Lat)= Σ =πι Pi-Lat/\P\停留点讳度(Lngt)= Σ =πι Pi-^ngt/\Ρ\
停留点到达时间(arv) = pm. T停留点离开时间(cbp) = pn. T此处，P可表示GPS点的集合P= {pl,p2,…，pn}，且每个GPS点pi e P可包括一个纬度(pi. Lat)、一个经度(pi. Lngt)、和一个时间戳(pi. Τ)。停留点到达和离开时间可表示用户到达和离开该停留点的时间。典型地，当个人保持静止的时间超过时间阈值时(例如，当个人进入了建筑物并丢失卫星信号一段时间直至返回户外)，或当用户在特定的地理空间范围内徘徊的时间周期超过了时间阈值时(例如，当个人在户外旅行并被周围环境所吸引时)，可获得停留点。在步骤Μ0，位置相似性应用程序60可用在步骤230所获得的停留点以编制第二位置历史。第二位置历史可包括用户可能访问超过一时间间隔的停留点的记录。在一个实现中，第二位置历史可包括可在步骤230所确定的停留点的序列。该第二位置历史可描述位置以及用户访问一个或多个位置的顺序。第二位置历史(LocH)可被定义为
Ati At 2 Atn^1LocH = (S1 — S2 —,…,——^ Sn) 其中 Si G S，并且 Δ = si+1. BrvT-Si. IevT
f其中Si可表示特定的停留点，而Ati可表示用户从一个停留点到下一个停留点所用的时间量。在步骤250，位置相似性应用程序60可作为在步骤230所确定的所有停留点确定一个或多个群集。每个群集可包括一个或多个可密集地填充在一个地理区域内的停留点。 在一个实现中，位置相似性应用程序60可收集存储在存储器中的每个GPS日志的所有停留点，并将该停留点的集合提供给基于密度的群集算法以基于数据集中的停留点的地理空间区域来创建一个或多个等级群集。在一个实现中，第一群集可包括围绕一大集合区域的最大数量的停留点。第一群集可作为等级群集的最高层的部分。所述基于密度的群集算法可进一步在第一群集中定位一个或多个子群集。每个子群集可包括可作为第一群集的部分的一个或多个停留点；然而，可作为子群集的部分的停留点可包括比在第一群集中的停留点更为密集地填充的停留点。所述基于密度的群集算法可依靠一个或多个停留点的接近度来在群集中定位附加的子群集。每个子群集可表示其群集在等级群集中所在层的下方一层。在一个实现中，每个子群集可表示比其可作为其中部分的群集更小的地理区域。在步骤沈0，位置相似性应用程序60可基于在步骤250所确定的群集和子群集编制等级框架。该等级框架F可被定义为在一个或多个层L上的群集C(以及子群集)的集合，从而F= (C，L)，其中L= {11；12,…，IJ，其中Cij表示在层Ii e L上的停留点S的第 j个群集，而Ci是层Ii上的群集的集合。在一个实现中，来自各个用户或GPS日志的停留点可被分配给一个或多个层L上的一个或多个群集C。例如，停留点的第一群集可包括其内部的一个或多个子群集。此处，第一群集可被视为等级框架的顶(高)层，而第一群集内的各子群集可被视为在所共享的等级框架的同一层上，该层可作为等级框架的第一群集层下方的一层。从等级框架的顶部到底部，群集的集合范围减小，而集合区域的粒度可从粗略增加为细致。该框架的等级特征可用于以不同相似性等级来区分人。因此，共享等级框架的较低层上的类似第二位置历史的用户要比共享较高层上的第二位置历史的用户更为相关联。共享等级框架的示例被示于图3。
10
在步骤270，位置相似性应用程序60可基于每个用户的等级框架(F)和第二位置历史(LocH)以构建个人等级图(HG)。该个人等级图HG可包括描述根据用户的第二位置历史该用户已经途经的群集或子群集的一个或多个图。在一个实现中，位置相似性应用程序 60可用等级框架的每个层交叉引用用户的第二位置历史。位置相似性应用程序60可将第二位置历史中的用户停留点映射至其在等级框架中的各层中的各自群集或子群集。群集或子群集然后可包括用户的停留点，而一个边可连接两个群集或子群集以表示用户可访问各个群集或子区级(地理区域)的顺序。个人等级图可包括一个或多个图，从而每个图对应等级框架的一个层。给定用户的第二位置历史和等级框架，该用户的等级图可被编制为一组图，其描述HG= (Gi = (Ci5Ei)5K i ^ |L|}，其中每个层Ii e LiGi e HG，而一组顶点或群集Ci以及边Ei可连接Cij e Ci。图3示出了表示根据此处所描述的各种技术的一个或多个实现的用于创建等级图的过程300的示意图。以下过程300的描述是根据此处所描述的各种技术的一个或多个实现参考图1的计算系统100以及图2的方法200来作出的。应当理解，尽管过程300指示了操作执行的特定次序，但在某些实现中这些操作的特定部分可按照不同的次序执行。另外，过程300可对应图2中所例示的某些步骤。在某些实现中，过程300可包括来自两个或更多个用户的两个或更多个GPS日志 GL、一个或多个群集cu、一个或多个停留点S、一个等级框架F、一个或多个等级图HG、一个或多个第二位置历史、以及一个或多个层1。图3示出根据图2中所描述的方法200为两个用户所创建的等级框架和两个用户等级图HG。参考步骤210，GPS日志GL可包括一个或多个用户的一个或多个GPS日志GL。在一个实现中，GPS日志GL可从GPS设备61处下载，并存储在可被计算系统100所访问的存储器存储设备中。参考步骤230，位置相似性应用程序60可由GPS日志GL在一图上创建一个或多个节点以表示停留点S。如图3中所示，停留点S可由节点来表示。在一个实现中，位置相似性应用程序60可为每个用户的GPS日志GL确定停留点S。参考步骤250，位置相似性应用程序60可用一基于密度的群集算法来确定一个或多个群集cu。位置相似性应用程序60可通过将一个或多个停留点包括在一个圆内来在图上指示群集cu。群集中的第j个变量可被编号以区分在共享等级框架F的特定层Ii上的各个不同群集，且第i个变量可对应于其中可放置群集的层1”在群集中，位置相似性应用程序60可找出一个或多个子群集c(i+1…其可包括比原群集中的停留点S的彼此距离更接近的一组停留点S。在群集中的每个子群集c(i+1”可指示在共享等级框架F 或等级图HG中的一个新级别或层Ii。每个子群集Ci(J+1)，如果其自身内部包括两个或多个子群集c(i+2)j，则其也可被视为群集c(i+1)j。例如，在过程300中，群集C1可表示群集Cij的最大的地理区域(层Ii = 1)，因为其包括了来自每个GPS日志GL的所有停留点S。子群集C2可表示群集C1的子群集(层Ii =幻。子群集C3然后可表示子群集C2的子群集(层 Ii =幻。群集的每个层可表示共享等级框架F中的一级或一层，或可表示可作为等级图HG的部分的独立图。层Ii可对应于停留点S的接近度，从而层I(C1)可对应较大的地理区域，而较低层(2+级)可对应逐渐更小的地理区域。参考步骤沈0，位置相似性应用程序60可通过根据群集Cij可对应的层来表示群集Cu，从而编制共享等级框架F。例如，群集从Cltl可对应群集C1、群集C2tl和群集C21可对应群集c2，而群集c3(1、c31、c32、C33及C34可对应上述的群集c3。可在等级框架F的最低层Ii 上的各个群集中表示停留点S。参考步骤270，位置相似性应用程序60可为特定用户编制等级图HG。在一个实现中，位置相似性应用程序60可根据用户的GPS日志GL从等级框架F中提取用户的群集Cij 和停留点S。在等级框架F的不同层Ii上的每个群集可对应不同的图&。在一个实现中，位置相似性应用程序60可由特定用户的GPS日志GL来确定第二位置历史LocH。例如，可通过将用户1的GPS日志GL1的停留点S组织为时间顺序并用指向箭头连接每个停留点来确定用户1的第二位置历史LocHlt5然后可通过用将第二位置历史LocH1和等级框架F中的群集其包括第二位置历史LocH1的停留点)相映射来确定等级图HG115第二位置历史LocH1的停留点S部分可按照在等级框架F中列出的群集Cij来分组。等级框架F的每个层Ii可对应等级图HG的一个图G”图4示出根据此处所描述的各种技术的一个或多个实现的用于基于位置历史确定两个用户之间的用户相似性的方法400的流程图。以下方法400的描述是根据此处所描述的各种技术的一个或多个实现参考图1的计算系统100以及图3的过程300来作出的。 此外，应当理解，尽管操作流程图指示了操作执行的特定次序，但在某些实现中，这些操作的特定部分可按照不同的次序执行。在一个实现中，可由位置相似性应用程序60来执行用于基于位置历史而确定用户相似性的方法。在步骤410，位置相似性应用程序60可从两个用户(由相似性应用程序60来为其确定相似性)的等级图HG中的各图中提取一系列群集或子群集。在一个实现中，每个用户的等级图HG可提供用户的第二位置历史LocH的有效表示，其可暗示基于不同范围的地理空间的一系列用户移动行为。给定如图3中所示的两个用户^和心的HGjP HG2，位置相似性应用程序60可首先定位在每个层Ii e L上被两个用户共享的的一个或多个相同图顶点片‘2，其中
权利要求
1.一种用于确定网络中第一用户和第二用户之间的相似性的方法包括 从所述网络中各用户处接收一个或多个全球定位系统(GPQ日志；构建针对第一用户的GPS日志的第一等级图和针对第二用户的GPS日志的第二等级图；以及基于所述第一等级图和第二等级图计算第一和第二用户之间的相似性得分。
2.如权利要求1所述的方法，其特征在于，构建第一等级图和第二等级图包括 将GPS日志的信息合并入等级框架中；基于所述等级框架创建针对第一用户的GPS日志的第一等级图；以及基于所述等级框架创建针对第二用户的GPS日志的第二等级图。
3.如权利要求2所述的方法，其特征在于，合并GPS日志的信息包括基于每个用户的GPS日志编制第一位置历史，其描述每个用户以时间顺序所途经的一个或多个位置；确定沿每个第一位置历史的一个或多个停留点； 将所述停留点分组成一个或多个群集； 将所述群集中的停留点分组为一个或多个子群集；以及将所述群集映射至所述等级框架的一个或多个较高层；以及将所述子群集映射至所述等级框架的一个或多个较低层。
4.如权利要求3所述的方法，其特征在于，确定停留点包括标识所述一个或多个位置的位于预定距离阈值内的部分，其中所述部分中的第一位置和最后位置之间的时间间隔超过了预定时间阈值； 为每个标识的位置提取纬度坐标和经度坐标； 计算所述位置的所述部分的纬度坐标和经度坐标的平均值；以及在所述纬度坐标和经度坐标的平均值处创建停留点。
5.如权利要求3所述的方法，其特征在于，使用基于密度的群集算法将所述停留点分组为群集和子群集。
6.如权利要求3所述的方法，其特征在于，创建第一等级图包括基于第一用户的GPS日志编制以时间先后顺序描述第一用户所途经的停留点的第二位置历史；将第二位置历史的停留点映射至所述等级框架的各层中的群集或子群集；以及为所述等级框架的各层创建一图，该图描述第一用户所途经的群集或子群集。
7.如权利要求3所述的方法，其特征在于，创建第二等级图包括基于第二用户的GPS日志编制以时间先后顺序描述第二用户所途经的停留点的第三位置历史；将第三位置历史的停留点映射至所述等级框架的各层中的群集或子群集；以及为所述等级框架的各层创建一图，该图描述被第二用户所途经的群集或子群集。
8.如权利要求3所述的方法，其特征在于，计算第一和第二用户之间的相似性等分包括从第一等级图和第二等级图中的一个或多个图中提取第一用户和第二用户所途经的群集或子群集的序列，其中第一等级图中的各图描述第一用户所途经的群集或子群集，而第二等级图中的各图描述第二用户所途经的群集或子群集； 将各序列分割成一个或多个子序列；标识第一用户和第二用户所途经的、具有最大数量的共同群集或子群集的子序列； 使用逆文档频率方法量化所述子序列中的各群集或子群集的热门度，其中所述共同群集或子群集的逆文档频率被定义为⑴ =ZDag，其中Hij定义所述网络中访问了所述共同群集或子群集的用户的总数量，U定义网络中的用户总数量；确定每个共同群集或子群集的相似性得分sV其中相似性得分ss,等于腳g X mini^p,mq)，且其中min (叫，y代表第一和第二用户连续访问所述共同群集或子群集的一次或多次； 添加每个共同群集或子群集的相似性得分；以及归一化总和。
9.如权利要求8所述的方法，其特征在于，所述最大数量的共同群集或子群集是相同时间先后顺序的。
10.如权利要求8所述的方法，其特征在于，在所述最大数量的共同群集或子群集中， 每个群集或子群集之间的行进时间是基本相似的。
11.如权利要求8所述的方法，其特征在于，分割各序列包括确定所述序列中两个连续的群集或子群集之间的时间量是否超过一时间值；以及当所述两个连续的群集或子群集超过所述时间值时，将所述序列分割成子序列。
12.如权利要求8所述的方法，其特征在于，计算第一和第二用户之间的相似性等分还包括基于所述最大数量的共同群集或子群集，为每个共同群集或子群集的相似性得分分配权重。
13.如权利要求8所述的方法，其特征在于，计算第一和第二用户之间的相似性等分还包括基于所述等级框架中所述最大数量的共同群集或子群集所处的一层，为每个共同群集或子群集的相似性得分分配权重。
14.一种计算机系统，包括 处理器；以及存储器，其包括可由所述处理器执行以用于以下动作的程序指令 从网络中两个或更多个用户处接收一个或多个全球定位系统(GPQ日志； 将GPS日志的信息合并入等级框架中；基于所述等级框架创建针对第一用户的GPS日志的第一等级图；以及基于所述等级框架创建针对第二用户的GPS日志的第二等级图；以及基于所述第一等级图和第二等级图计算第一和第二用户之间的相似性得分。
15.如权利要求14所述的计算机系统，其特征在于，所述可由所述处理器执行以将GPS 日志的信息合并入等级框架中的程序指令包括可由所述处理器执行以进行以下动作的程序指令基于每个用户的GPS日志编制第一位置历史，其描述各用户以时间顺序所途经的一个或多个位置；确定沿每个第一位置历史的一个或多个停留点； 将所述停留点分组成一个或多个群集； 将所述群集中的停留点分组为一个或多个子群集；以及将所述群集映射至所述等级框架的一个或多个较高层；以及将所述子群集映射至所述等级框架的一个或多个较低层。
16.如权利要求15所述的计算机系统，其特征在于，所述可由所述处理器执行以确定停留点的程序指令包括可由所述处理器执行以进行以下动作的程序指令标识所述一个或多个位置的位于预定距离阈值内的部分，其中所述部分中的第一位置和最后位置之间的时间间隔超过预定时间阈值； 为每个标识的位置提取纬度坐标和经度坐标； 计算位置的所述部分的纬度坐标和经度坐标的平均值；以及在所述纬度坐标和经度坐标的平均值处创建停留点。
17.如权利要求15所述的计算机系统，其特征在于，使用基于密度的群集算法将所述停留点分组为群集和子群集。
18.一种其上存储有计算机可执行指令的计算机可读介质，所述指令在由计算机执行时使得所述计算机从网络中两个或更多个用户处接收一个或多个全球定位系统(GPQ日志； 基于各用户的GPS日志编制以时间先后顺序描述各用户所途经的一个或多个位置的第一位置历史；确定沿每个第一位置历史的一个或多个停留点；将所述停留点分组成一个或多个群集；将所述群集中的停留点分组为一个或多个子群集；以及将所述群集映射至一等级框架的一个或多个较高层；将所述子群集映射至所述等级框架的一个或多个较低层；基于所述等级框架创建针对第一用户的GPS日志的第一等级图；基于所述等级框架创建针对第二用户的GPS日志的第二等级图；以及基于所述第一等级图和第二等级图计算第一和第二用户之间的相似性得分。
19.如权利要求18所述的计算机可读介质，其特征在于，所述用于计算第一用户和第二用户之间的相似性得分的计算机可执行指令被配置为从第一等级图和第二等级图中的一个或多个图中提取第一用户和第二用户所途经的群集或子群集的序列，其中第一等级图中的各图描述第一用户所途经的群集或子群集，而第二等级图中的各图描述第二用户所途经的群集或子群集； 将各序列分割成一个或多个子序列；标识第一用户和第二用户所途经的、具有最大数量的共同群集或子群集的子序列； 使用逆文档频率方法量化所述子序列中的各群集或子群集的热门度，其中所述共同群集或子群集的逆文档频率被定义为⑴ =,Mg,其中定义所述网络中访问了所述共同群集或子群集的用户的总数量，U定义网络中的用户总数量；为了每个共同群集或子群集确定相似性得分ssa，其中相似性得分等于IBFijxmin(mp,mq),且其中min(nip，mq)代表第一和第二用户连续访问所述共同群集或子群集的一次或多次；添加每个共同群集或子群集的相似性得分；以及归一化总和。
20.如权利要求18所述的计算机可读介质，其特征在于，使用基于密度的群集算法将所述停留点分组到所述群集或子群集中。
全文摘要
用于确定网络中第一用户和第二用户之间相似性的方法，包括从网络中各用户接收一个或多个全球定位系统(GPS)日志，构建针对第一用户的GPS日志的第一等级图和针对第二用户的GPS日志的第二等级图，并基于第一等级图和第二等级图计算第一用户和第二用户之间的相似性得分。
文档编号G06F9/44GK102203729SQ200980143794
公开日2011年9月28日 申请日期2009年11月3日 优先权日2008年11月3日
发明者W-Y·马, X·谢, Y·郑 申请人:微软公司
最新回复(0)