基于主题的轨迹模式挖掘

摘 要：随着社交网络中的地理标记信息的增多，传统的轨迹模式挖掘方法不能处理这些数据中丰富的信息。传统的轨迹模式挖掘算法能根据GPS数据挖掘出人们的移动模式，但是无法利用文本信息中上下文相关的潜在主题来实现轨迹模式挖掘。本文主要介绍一种基于潜在主题的聚类算法，它能发现地理标记文本信息中的轨迹模式。

关键词：主题；轨迹模式挖掘；聚类；概率模型

Abstract： With the increasing of geo-tagging messages in social network， traditional trajectory pattern mining methods can not deal with these rich data. Traditional trajectory pattern mining algorithms can find the patterns of peoples movements using GPS data， but latent topics in text messages posted with local contexts have not been utilized. In this paper， a latent topic-based clustering algorithm is introduced. It can find trajectory pattern in geo-tagged text messages.

Keywords： Topic； Trajectory Pattern Mining； Cluster； Probabilistic Model

1 引言

随着网络技术的发展，社交网络在人类生活中的位置越来越重，微博等社交网络工具已经成为人们交流的一个重要方式。人们通过移动设备随时随地的对自己的状态进行更新，随时刷新自己的位置，自己在做的事，以及自己的心情。伴随着用户生成的媒体中，越来越多的关于位置信息的文本和照片出现在微博等网络媒体中，对于用户的轨迹模式的挖掘，不仅可以使用用户的位置信息，还可以使用在这些位置上用户的行为信息。

对于GPS传感器收集到的轨迹数据进行研究，挖掘用户的轨迹模式一直是很多应用的研究重点，这些应用需要分析用户的位置信息，如移动导航系统，城市交通分析以及飓风追踪等等。但是这种传统的轨迹模式挖掘技术主要是根据GPS传感器的数据来分析移动物体的轨迹模式，这些数据非常频繁，足以支撑对应的模式分析对数据量的需求。而且，这种轨迹模式的挖掘也不考虑位置信息的语义含义。

在社交网络中，对用户的轨迹模式的分析能为其他用户提供路线推荐或发现有趣的轨迹模式，这种轨迹模式挖掘已经成为一个新的研究热点。但是，在社交网络中，由于用户提供的带有位置信息的文本和照片是稀疏的，在该信息中，对于语义的理解和表示也存在着差异，因此，对这些具有主题的轨迹模式进行分析可以得到很多有用的信息[1]。

本文主要探讨在社交网络中，对于用户提供的带有语义的位置信息进行基于主题的轨迹模式挖掘问题。首先介绍轨迹模式挖掘的相关工作成果，然后分析基于主题的轨迹模式挖掘问题面对的难题，最后介绍一种基于概率模型的主题轨迹模式挖掘方法，并分析其性能。

2 基础知识

对移动对象的GPS数据进行轨迹模式挖掘已经有了广泛的研究，最初的挖掘算法只使用GPS位置数据，这些挖掘算法通常把相似的位置信息进行聚类，找到共同的、普通的轨迹模式。有的聚类算法不仅能找出相似轨迹模式的类，还能找出具有相似子轨迹的类。有的算法基于HIT算法发现共同的轨迹模式，还有算法能找出给定的两个位置之间最流行的路径。然而，这些轨迹模式挖掘算法都仅仅关注从GPS传感器得到的数据，这些数据记录的位置信息非常频繁，数据量也很大。

随着网络的发展，在微博等服务上出现了大量的具有位置标记的信息，这些数据是稀疏的，并且具有语义信息。为了挖掘这些数据中的轨迹模式，轨迹模式挖掘算法不仅需要使用位置数据，还要能使用位置的语义信息。最近出现的轨迹模式算法中，有的算法能通过图片中的GPS位置信息找到语义模式，发现用户生成标签的顺序模式；有的算法能发现社交媒体中的多样性的短轨迹模式；有的算法能基于用户生成的位置类别，对用户的轨迹模式进行很好的聚类[2]。

使用社交媒体红的位置标记信息挖掘轨迹模式，主要有三个问题：如何找到主题一致的区域；如何处理噪音信息；如何解决轨迹模式的稀疏问题[3]。

由于位置标记是一对分别表示经度和纬度的实数，所以首先对相近位置主题相近的位置标记信息进行聚类，并把这些具有一致主题的区域称为语义区域。由于在微博等服务上的大部分信息是关于个人的，很难把这些信息按同一个主题来聚类，另外，在带有噪音的语句信息中挖掘出轨迹模式也使问题的難度加大。

为了从位置标记信息中挖掘与主题相关的轨迹模式，文[4]给出了一个称为LGTA的基于概率模型的聚类算法，该算法能把具有相同主题的相似位置的位置标记信息进行聚类[4]。但是LGTA算法不能处理带噪音的数据，也不能处理轨迹稀疏问题。而TOPTRAC算法不仅能发现用户一致主题的潜在的语义区域，还能发现在多个语义区域内用户的各种移动模式，找到用户参观一个区域的各种的目的。TOPTRAC算法发现主题一致的语义区域具有很好的粒度，该算法通过对同一语义区域中出现过的信息进行加权实现语义区域之间的粒度。

3 TOPTRAC算法的概率模型

TOPTRAC算法给出了一个概率模型来发现潜在的语义区域。下面是该模型需要用到的定义、公式及具体的概率模型[5]。

首先给出描述收集到的社交媒体中位置标记信息的符号。

定义1 轨迹是指一个用户在给定的时间间隔内给出的一组位置标记信息的序列。endprint

其中，时间间隔可以是一天或一周，并且位置标记信息是按时间顺序列出的。

设是N个轨迹的集合，其中每个轨迹用表示，。设是轨迹集合中至少出现一次的词的序号的集合。因此，轨迹是由个位置标记信息组成的，其中中的第i个信息表示为。每个位置标记信息由一个位置标记和一个词袋组成。其中是一个二维向量，分别表示位置信息中的纬度和经度。是一个词袋，包括一共个词，而表示中的第j个词，并且它是所有词的集合V中的一个。

定义2 语义区域是指一个由具有相同主题的位置标记信息聚类得到的地理位置。

定义3 主题转变模式是在某个轨迹集合C中的从一个语义区域到另一个语义区域的移动模式。

每个主题转变模式是指一对实际的位置标记信息，它们表明转变模式中语义区域的主题。

由于长的轨迹模式在低样本空间中很少出现，因此TOPTRAC算法专注于挖掘长度为2的轨迹模式。

主题轨迹模式挖掘问题可以定义为：给定一个位置标记信息轨迹的集合C，主题轨迹模式挖掘就是发现主题转变模式以及最能表示每个转变模式的top-k转变片段。

TOPTRAC算法的概率模型假设每个位置标记信息序列都是由用户独立生成的，序列中的每个位置标记信息依靠该序列中该位置标记信息前面的信息来处理。假设位置标记信息轨迹的集合C中，有M个潜在的语义区域和K个隐藏的主题。K个主题在一个语义区域r中的分布表示为，其中，是语义区域r中主题k被选中生成一个文本信息的概率。一个主题k在词汇的集合V上的分布表示为，其中，表示一个词t被主题k选中的概率。

假设表示潜在的语义区域的随机变量，表示为轨迹中中信息选中的潜在主题。对于C中的每个序列，假设存在一个伯努利分布，该分布能反应中的每个位置标记信息是否与语义区域相关。如果与局部上下文无关，则随机变量=0，否则=1。

如果一个信息不属于任何潜在的语义区域，那么的区域以概率1/M被选为区域M中的一个区域，的位置标记也均匀分布概率生成。如果信息有局部的上下文，则根据它先前的信息是否与该语义区域相关，来选择一个潜在的语义区域。如果信息是序列中的第一个信息或者它先前的信息与局部的上下文不相关，则根据潜在语义区域M上的类别分布选择潜在的语义区域。对于一个选中的区域，选择一个服从的主题，选择服从的中的每个词。

4 主题轨迹模式挖掘

通过引入随机变量可以识别出现在任何位置上的局部无关的信息，而使用转变概率能对语义区域进行加权，表示用户从一个语义区域移动到另一个语義区域的可能性。为了找到最有意义的转变模式，TOPTRAC算法提供一个动态规划算法，能计算出一个给定的轨迹的潜在语义区域的最可能序列。

给定一个带有n个位置标记信息的序列，对于信息与局部的上下文无关的情况，随机变量=0，生成序列的最大概率pi由和决定，计算公式为

。对于

信息由局部的上下文决定的情况，随机变量=1，需要分的先前信息是否与该语义区域相关两种情况来选择最可能的区域，即=0和=1。对于=0的情况，由于它之前的信息与语义区域无关，所以可以不考虑和来计算最大概率p[i，r，k]。对于=1的情况，由于是依据和来选择的，因此，最大概率p[i，r，k]的计算需要通过枚举出每一对和生成的最大概率来得到。因此，p[i，r，k]的计算公式为

由于的计算不依赖于k，因此它可以通过一次计算，为后面的算法一直使用。

基于最可能的序列可以发现频繁的转变模式，对每个转变模式，选择能最好的代表该转变模式的top-k个转变片段。

5 结束语

随着带有位置标记信息的社交网络资源的增加，对这些信息进行轨迹模式挖掘有了越来越多的应用。在对位置标记信息进行轨迹挖掘过程中，把位置的语义信息也放入到模式挖掘的算法中能提高挖掘的模式的效果，找到更多的让用户感兴趣的模式。但是能实现主题轨迹模式挖掘的算法还不是很多，在未来的工作中，可以针对主题轨迹模式挖掘进行进一步的研究。

参考文献

[1] 张晨逸，孙建伶，丁轶群.基于 MB-LDA 模型的微博主题挖掘[J].计算机研究与发展，2015， 48（10）：1795-1802

[2] 牛新征，牛嘉郡，苏大壮等.基于FP-Tree模型的频繁轨迹模式挖掘方法[J].电子科技大学学报， 2016，45（1）：86～90，134

[3] 王兴，蒋新华，蔡伟文等. 基于后缀自动机的轨迹模式挖掘方法[J].计算机学应用研究，2016， 33（2）：409-412，416

[4] Z Yin， L Cao， J Han， etc. Geographical topic discovery and comparison[A]. The International Conference of World Wide Web， 2011： 247-256

[5] Y Kim， J Han， C Yuan. TOPTRAC： Topical trajectory pattern mining[A]. Conference on Knowledge Discovery and Data Mining， 2015：587～596

作者简介

马恺（1978-），男，副教授，硕士，主要研究领域为数据挖掘和计算机网络。endprint