基于LBSN用户的轨迹聚类算法研究

VIP免费

3.0 侯斌 2024-11-19 4 4 1.32MB 55 页 15积分

侵权投诉

摘要

随着智能终端、移动定位和无线通信等技术的迅猛发展，移动通信和互联网

得到了有效的结合。利用手持无线终端记录用户在某时刻的位置信息，一系列位

置信息形成用户足迹的一个个点，对用户位置信息进行聚合和分析，存储在数据

库中，形成了代表用户行为特征的轨迹，用户通过社交关系对好友的轨迹相互影

响。这些轨迹蕴含了用户的位置信息和社交信息，因此，轨迹中的位置属性和社

交属性成为轨迹研究中一项越来越重要的热点。

本文基于 LSBN 用户的数据信息，主要研究两个问题：(1)利用用户间轨迹的

相似性，向用户推荐与其可能成为好友的用户；(2)发现用户好友间的热门轨迹或

热门区域，挖掘用户好友中的热点，实现热点信息推荐。针对形成轨迹的数据信

息特征以及轨迹聚类算法，本课题有以下研究：

首先，分析传统的轨迹聚类算法，研究传统聚类算法在轨迹聚类中的应用，

针对轨迹数据变化特性，在传统轨迹聚类的基础上提出一种基于兴趣点的轨迹推

荐聚类算法 UR-POI(User Recommendation Algorithm Based on Place Of Interest)。

该算法利用用户实际轨迹中的定位信息，设计一种新的算法寻找用户轨迹中的热

点区域，从热点区域中虚拟出代表用户兴趣点的点，将用户兴趣点轨迹转换为位

置轨迹，引入用户在兴趣点的停留语义，结合兴趣点在轨迹中的属性，采用分段

聚类的方法基础上对子轨迹进行权重分析，然后对轨迹作相似性分析，根据分析

结果得到与用户轨迹相似的 top-k 个用户，最后向用户推荐可能成为朋友或者好

友的用户，这种算法能够找出与用户行为习惯与兴趣相似的用户。

其次，研究社交网络中的轨迹聚类算法，针对社交网络中的位置属性和社交

特征，提出一种基于 LBSN 用户的热点轨迹聚类算法 LSHT(Clustering Algorithm

for Location-based Social-network Hot Trajectory)。该算法利用基于位置的社交网络

用户中的好友关系特征，引入用户亲密度和用户活跃度，对用户之间的联系进行

分析；同时，提出对用户轨迹的评价函数，计算用户轨迹的影响力。结合用户亲

密度和轨迹评分函数，对轨迹进行聚类，挖掘出 LBSN 用户的热点轨迹。

最后，使用 C++语言对上述算法实现，用真实数据集-LBSN 数据集和人工模

拟数据集对上述提出的两种算法进行验证，通过与其他算法比较，验证本算法的

可用性和优劣性。

关键词：LBSN；聚类；轨迹；兴趣点；用户推荐

ABSTRACT

As the rapid development of intelligent terminals, mobile positioning and wireless

communication, mobile communication and internet has been connected effectively. A

series of points of the location information recorded by a handheld wireless terminals in

a certain time have formed the footprints of users. Aggregation and analysis of user’s

location information stored in the database form the trajectory on behalf of the users’

behavior characteristics. Users are influenced through social relationships. Users’

location and social information are encompassed in those trails, of which location and

social attribute has become an increasingly important research topic.

Based on the trail data of LSBN users, this thesis mainly deals with two questions.

Firstly, some users who are likely to be good friends with others can be recommended

according to the trail similarities between users. Secondly, hot information can be

achieved through hot trails and areas between users. In light of information attributes

forming trails and trajectory clustering algorithm, this thesis focuses on the researches

as follows.

Firstly, UR-POI (User Recommendation Algorithm Based on Place of Interest) is

put forward based on the analysis of traditional trajectory clustering algorithm, and the

study of the application of traditional clustering algorithm in trajectory clustering

algorithm. By means of users’ practical location information, the algorithm aims to

design a new algorithm for users to track hot spots in the area. Afterwards, the points of

hot places visualized through hot areasare transformed into location trails, and user

interest points in semanticsare then brought in. Combined with the attribute of interest

points in trails, weight and similarity analysis are implemented on the trails based on the

segment clustering method and top-k users similar to these trails are obtained from the

findings. And then the potential friends can be recommended to users. Users that have

similar habits and interests can be found through the new algorithm.

Secondly, LSHT (Clustering Algorithm for Location-based Social-network Hot

Trajectory) is put forward according to the study of trajectory clustering algorithm in

social network and the attributes of location and socialization among social network.

The algorithm analyzes the contacts between users by means of the attributes of friend

relationship based on location, and intimacy and active degree between users. In the

meantime, scoring function for users’ trails is put forward to compute the influence of

users’ trails. Hot trails of LSBN users are dug out according to the combination of

intimacy and scoring function as well as trail clustering.

Finally, all the above algorithms are realized through C++ language, are validated

through real data cluster and LSBN data cluster as well as artificial simulation data

cluster in order to evaluate the effectiveness and accuracy of the algorithms.

Key Word：LBSN ；cluster；trajectory; points of interest; user

recommendation

摘要

ABSTRACT

第一章绪论 ............................................................................................................. 1

1.1 研究背景和意义 ..................................................................................................... 1

1.2 国内外研究现状 ..................................................................................................... 3

1.3 论文概要 ................................................................................................................. 5

1.4 主要研究内容 ......................................................................................................... 5

第二章轨迹数据挖掘 .................................................................................................. 7

2.1 轨迹数据挖掘......................................................................................................... 7

2.2 轨迹数据建模与表示............................................................................................. 8

2.2.1 轨迹数据建模 .................................................................................................. 8

2.2.2 轨迹表示 ........................................................................................................ 10

2.3 轨迹相似度度量方法........................................................................................... 12

2.4 轨迹聚类算法 ....................................................................................................... 15

2.4.1 层次聚类 ........................................................................................................ 15

2.4.2 划分式聚类 .................................................................................................... 17

2.4.3 基于网格聚类 ................................................................................................ 19

2.4.4 DBSCAN 算法 ............................................................................................... 20

第三章基于用户轨迹的聚类推荐算法 .................................................................... 22

3.1 框架模型.............................................................................................................. 22

3.2 问题定义 ............................................................................................................... 23

3.3 基于用户轨迹的聚类推荐算法 ........................................................................... 24

3.3.1 热点区域发现 ................................................................................................ 24

3.3.2 挖掘兴趣点和兴趣轨迹 ................................................................................ 26

3.3.3 兴趣点聚类分析及与位置轨迹转换 ............................................................ 27

3.3.4 轨迹相似性分析 ............................................................................................ 28

3.3.5 推荐算法 ........................................................................................................ 29

3.4 实验结果与分析................................................................................................... 31

3.4.1 算法参数选择 ................................................................................................ 31

3.4.2 聚类效果比较 ................................................................................................ 33

3.5 本章小结............................................................................................................... 34

第四章基于社交属性的热点轨迹聚类算法 LSHT ................................................. 35

4.1 相关工作 ............................................................................................................... 35

4.2 轨迹算法相关知识............................................................................................... 36

4.2.1 相关概念 ....................................................................................................... 36

4.3 基于社交关系的热点轨迹聚类算法................................................................... 38

4.4 实验及分析 ........................................................................................................... 41

4.4.1 算法参数实验 ................................................................................................ 42

4.4.2 算法效果分析 ................................................................................................ 44

4.5 本章小结............................................................................................................... 45

第五章结论与展望 ...................................................................................................... 46

参考文献 ........................................................................................................................ 47

在读期间公开发表的论文和承担科研项目及取得成果 ............................................ 51

致谢 ................................................................................................................................ 52

第一章绪论

近年来，随着移动通信和互联网技术的快速发展，使得基于位置的服务和社

交网络很好地结合在一起。人们日常生活的足迹通过定位和导航技术以轨迹的形

式记录下来，轨迹在一定程度上反映了人们的行为模式，地理空间的相似性，侧

面反映出人们之间联系的紧密程度，也反映了不同人可能在某些生活习惯上具有

共性如品味、爱好相同[1]。研究人们在社交网络中的行为模式，需要分析人们的

日常活动记录--轨迹，通过对轨迹数据进行分析、聚类，根据聚类结果发现人们

在某种程度上的相似性或者向其他用户推荐其感兴趣的信息。

1.1 研究背景和意义

尽管很多有关轨迹聚类的算法，但目前的轨迹聚类算法还存在一些问题，并

有待于进一步的研究，随着移动社交的发展，需要新的轨迹聚类算法的出现来解

决新的问题。传统聚类算法中有轨迹特征点 CP(Characteristic Points)选取的问题，

但其轨迹聚类效果不好，对于目前社交网络中轨迹数据的研究，没有考虑社交网

络用户中社交关系和地理信息的融合。

过去对社交行为分析的研究往往只关注人们之间的社交关系，对智能终端产

生的大量位置信息没有过深的探究，而位置信息在数以亿计的大数据中扮演的角

色显得越来越重要，比如，人们到达某个景色非常美的旅游景点，想要把自己所

处的信息记录下来并与朋友分享；或者在某家商店购物时，看到了非常多物美价

廉的商品，想把此时的心情和位置分享到朋友圈，让好友看到自己所处的位置和

状态；又或者商家会推出一系列优惠活动，对在地图上商家所在位置“签到”并

分享到社交软件的用户给予折扣，用户即得到了实惠，同时分享活动也间接上为

商家做了免费广告推广。这些活动都需要定位技术和社交软件的支持。

用户通过社交软件中定位功能留下大量的数据，这些包含位置信息的数据也

蕴含了用户之间的社交信息，一系列包含位置和社交关系的点可以通过算法形成

轨迹，因此，对轨迹进行分析，弥补了对社交好友中位置信息的忽视。

目前，在物流、交通、社交等应用领域，通过手持终端(智能手机）、

PDA(personal digital assistant)等移动设备已经能够记录人们的轨迹，移动用户也

可以通过智能终端将自己的位置信息分享到社交软件中，在记录人们活动的同时，

通过用户之间对其他用户位置信息的关注，可以了解用户间的生活动态。

当复杂的社交网络与位置信息结合在一起后，新的社交网络比传统社交网络

更具空间感，社交网络中的用户活动的时间、地点、内容更能体现用户在现实世

界中真实的生活、学习、工作状态。国外以 MySpace、Facebook、Twitter、

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

摘要随着智能终端、移动定位和无线通信等技术的迅猛发展，移动通信和互联网得到了有效的结合。利用手持无线终端记录用户在某时刻的位置信息，一系列位置信息形成用户足迹的一个个点，对用户位置信息进行聚合和分析，存储在数据库中，形成了代表用户行为特征的轨迹，用户通过社交关系对好友的轨迹相互影响。这些轨迹蕴含了用户的位置信息和社交信息，因此，轨迹中的位置属性和社交属性成为轨迹研究中一项越来越重要的热点。本文基于LSBN用户的数据信息，主要研究两个问题：(1)利用用户间轨迹的相似性，向用户推荐与其可能成为好友的用户；(2)发现用户好友间的热门轨迹或热门区域，挖掘用户好友中的热点，实现热点信息推荐。针对形成轨迹...

展开>> 收起<<

基于LBSN用户的轨迹聚类算法研究.pdf

共55页,预览6页

还剩页未读，继续阅读

基于LBSN用户的轨迹聚类算法研究

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: