论文部分内容阅读
随着拥有定位能力的装置越来越轻便和普及(如智能手机和可穿戴式设备),使得用户的位置信息越来越容易被取得。许多社交网络提供用户分享轨迹数据的功能,如旅游轨迹、跑步轨迹、骑车路线和行车轨迹。另外,许多社交网络也提供用户分享位置信息的功能,如签到信息和上传包含位置信息的照片。这些包含地理信息的数据代表着用户的移动行为,如果能从这些数据中挖掘出用户的轨迹特征,则可以在社交平台上提供更多和地理相关的个性化服务。本文针对位置社交网络上不同的应用和服务所对应的不同类型的轨迹,提出了不同的挖掘用户轨迹模式的技术。不同类型的轨迹的特征具有显著的差异,为了解决该问题,本文分析了用户轨迹并采用它们特有的特征来表示个体的移动行为。本文分别针对三种类型的用户轨迹:1)被动记录的轨迹;2)主动记录的轨迹;3)主动记录的包含支持数据的轨迹,进行了以下三个方面的研究:在第一个研究主题中,本文提出了从用户被动记录的轨迹数据中发现有类似移动行为的用户社群问题。发现基于移动行为的社群,不仅能够为用户快速找到有相似移动行为的其他用户,还能在社交网络上提供基于移动行为的个性化服务,譬如用户推荐,轨迹推荐等。本文提出了一个解决该问题的框架:1)构建用户移动档案;2)计算移动档案之间的相似度;3)发现基于移动的用户社群。首先,本文设计了转移概率树TP-Tree(Transition Probability Tree)表示用户的移动档案,转移概率树是一个紧凑型的树形结构,不仅包含了用户轨迹中的序列模式,还包含了用户了下一步移动的转移概率。同时,针对不同类型的移动轨迹,本文提出了两种生成转移概率树的算法,深度优先和广度优先方法,能够高效地为用户生成转移概率树。接着,本文针对转移概率树结构,提出了相似度计算方法,充分考虑了树形结构中的所有信息。最后,基于用户移动档案之间的相似度,本文采用了图结构来组织用户和他们之间的相似度,并基于图结构提出了一个衡量聚类结果好坏的目标函数,采用了一个使得目标函数最小化的基于贪心算法的移动社群挖掘算法,发现基于移动的用户社群。实验结果表明,本文提出的转移概率树结构,基于转移概率树结构的相似度计算方法和社群挖掘算法,能够有效地发现基于移动的用户社群。在第二个研究主题中,本文提出了通过病毒营销的方式对社交网站中的指定位置进行推广问题。本文将该位置推广问题转换成社交网络中的影响力最大化问题来求解:通过用户的主动记录轨迹签到记录找到种子用户,让种子用户在目标位置签到,影响他们的朋友前来目标位置签到,进而影响更多人在目标位置签到,使得到访目标位置的用户数量最大化,达到位置推广的目的。首先,本文扩展了独立级联模型到位置感知独立级联模型来作为基于位置的社交网络(LBSN,Location-Based Social Networks)中的传播模型。接着,在计算传播概率时,本文认为用户的移动和签到行为由用户的移动偏好决定,所以本文提出了基于高斯的移动模型和基于距离的移动模型来捕获用户的移动偏好,并基于该移动模型来计算LBSN中的传播概率。获得传播模型和传播概率之后,采用已有的近似方法对影响力最大化问题求解,得到种子用户,让种子用户在目标位置签到进行位置推广,使得到目标位置签到的用户数量最大化。实验结果表明,本文提出的位置感知独立级联模型,基于距离的移动模型计算传播概率的方法,能够更精确地反映LBSN中的信息传播和扩散,进而能够有效地采用病毒营销的方式对LBSN中的位置进行推广。在第三个研究主题中,本文提出通过用户主动记录的包含支持数据(用户活动类别)的签到记录,对用户在特定时间特定位置的活动和用户在特定时间特定活动的移动区域进行推断问题,简称为用户活动和移动推断问题。针对该问题,首先,本文采用了贝叶斯网络对签到记录中的时间,位置和活动进行建模,并分别对用户的活动推断和移动推断问题进行简化。简化后的活动和移动推断问题中包含两个部分:时间和活动的关系,位置和活动的关系。接着,本文提出了下一步活动转移概率模型来为时间和活动建模。本文采用了高斯混合模型来为不同的活动中的活动和位置建模。最后,基于上述两个部分的结果,计算LBSN中用户的活动推断和移动推断。实验结果表明,本文提出的基于贝叶斯的方法,能够有效地对用户的活动和移动进行推断。综上所述,本文的研究专注于从不同类型的用户轨迹数据中挖掘用户移动行为,为不同的基于位置的个性化应用和服务提供支持,具有重要的理论和实践贡献。本文主要的创新贡献主要有:第一,本文提出了转移概率树结构从被动记录的用户轨迹中捕获用户移动档案,不仅包含用户轨迹中的序列模式,还包含序列模式的下一步转移概率。能够有效反映用户轨迹中的特征,为发现基于移动的用户社群提供了良好的数据结构支持。第二,本文采用病毒营销的方式对LBSN中的位置进行推广,其中计算传播概率的方法中,提出基于距离的移动模型为用户的签到行为建模,并基于该移动模型计算LBSN中的传播概率。计算出的传播概率更精确地反映了LBSN中的信息传播和扩散,为LBSN中的传播概率计算提供了新思路。第三,本文采用基于贝叶斯的方法对用户活动和移动推断问题进行简化,提出了下一步活动转移概率为用户的活动-时间关系建模,采用了高斯混合模型为用户位置-活动关系建模,进而得出用户的活动和移动推断结果。为LBSN中的个性化服务提供了更精确有力的技术支持。本文的主旨就是从不同类型的轨迹类型中,为不同的应用挖掘出不同的用户移动特性。三个研究主题分别从被动记录轨迹,主动记录轨迹和包含支持数据的主动记录轨迹中挖掘出用户移动行为,找到具有移动相似性的用户社群,计算LBSN中的传播概率,对用户的活动和移动进行推断,为位置社交网络的个性化服务应用提供支持。