2018, Vol. 29
Instagram作为流行的图片共享社交应用, 被游客广泛用于记录位置、时间、UGC(user-generated context)等旅行信息, 其主要包含旅行路径、旅行密度分布、偏好、移动模式等.因此, 如何有效挖掘大规模Instagram轨迹数据, 对于旅游路线推荐有着极其重要的作用.但目前存在的轨迹组模式挖掘仅适用于数据等时间间隔采样的GPS轨迹数据.此外, 随着社交网的不断发展, 数据规模也逐渐增大, 形成了轨迹大数据, 而MapReduce作为一种并行编程框架为大规模数据处理提供了便捷.可以看出, 社交网轨迹大数据目前面临着以下问题:1)聚类算法能否通过MapReduce并行优化处理提高效率; 2)传统轨迹组模式具有输入数据等时间间隔采样约束, 能否找到适用于具有离散性、随机性的Instagram数据轨迹组模式挖掘方法; 3)目前存在的组模式只考虑轨迹信息, 没有考虑社交网UGC信息对旅游路线推荐的影响, 能否将UGC与社交网轨迹信息结合起来, 完成基于轨迹组模式的个性化旅游路线推荐.这些问题在旅游路线推荐中存在挑战, 目前尚未发现将以上几点结合起来进行旅游路线推荐的研究工作.
基于上述问题, 提出以下解决策略.
● 首先, 基于MapReduce并行编程框架实现轨迹大数据聚类处理, 并且改进了PRBP算法[1]完成社交网数据优化分区, 有效提高了聚类算法的效率;
● 其次, 目前存在的轨迹组模式处理均为GPS轨迹数据, 无法有效处理具有离散性、随机性的Instagram社交网轨迹数据.而Coterie组模式通过采用异步策略完成组模式挖掘, 解决了上述组模式同步相等时间间隔约束问题.Coterie模式是在异步情形下, 某一时间间隔内具有相似路径的轨迹组;
● 最后, 在基于组模式个性化旅游路线推荐中, 传统组模式挖掘由于语义信息缺失导致个性化推荐不完善, 因此提出基于语义的距离敏感推荐策略DRSS(distance-aware recommendation strategy based on semantics)和基于语义的从众性推荐策略CRSS(conformity-aware recommendation strategy based on semantics)两种推荐策略完成路线推荐.
本文主要框架为通过基于MapReduce的DBSCAN算法提高聚类算法效率完成轨迹数据聚类处理, 并且通过提出的nPRBP算法对数据进行优化分区处理; 然后, 通过ClusterGrowth算法找出closed coteries, 主要包含前验剪枝、后验剪枝、规则验证这3个处理步骤; 最后, 在closed coteries中通过提出的DRSS和CRSS推荐策略完成旅游路线推荐.
本文第1节介绍相关工作.第2节定义必要的概念.第3节介绍nMR-DBSCAN优化聚类.第4节说明Coterie轨迹组模式挖掘.第5节介绍基于语义的个性化旅游路线推荐.第6节提供研究实例和实验结果.最后, 第7节总结全文.
1 相关工作随着社交网的不断发展, 用户社交网信息不断增加.如何有效地从社交网信息中挖掘出有价值的信息, 对当前社交网发展起着不可替代的作用[2].在社交网中, 用户可以上传文本信息、位置信息和时间信息等, 还可以将这些信息共享给好友和附近的人.如今, 越来越多的学者意识到社交网信息的重要性, 并陆续投身到社交网信息挖掘的研究中来.
社交网数据挖掘思想与GPS轨迹数据挖掘思想相似.在GPS轨迹数据挖掘中, 主要应用包括关联规则、异常行为、出行方式[3-5]和GPS轨迹推荐[6].数据采集时间具有严格的等时间间隔限制, SHAHED[7]就体现了这个特点.在社交网轨迹数据挖掘中, 应用主要包括位置推荐、路线推荐和行为偏好推荐[8-11].数据采集时间具有离散性和随机性, 这也是社交网轨迹数据和GPS轨迹数据的主要区别.
目前, 在社交网数据挖掘中有很多处理方法, 主要包括数据挖掘中聚类、分类等传统技术.其中, 通过聚类方法找出社交网中组模式挖掘手段, 对于推荐用户路线和位置有很好的效果[12].在大规模数据处理上, MapReduce框架被广泛使用.目前, 将聚类算法与MapReduce框架结合进行大数据分析处理的方法逐渐发展, 例如基于MapReduce的DBSCAN聚类算法[13], 取得了良好的效果.
组模式挖掘方法主要有swarm、flock、convoy、gathering、platoon等, 文献[14-17]详细介绍了不同的组模式挖掘方法.Swarm是一种具有时间轴约束弱特点的组模式挖掘技术, 它只需满足不同轨迹同时出现在相同地点次数大于所设定阈值条件即可.而Flock和convoy比swarm在时间上约束更强, 但这种强约束同时也导致了准确率下降.Platoon模式综合上述组模式的优点并且通过允许控制连续时间约束来适应不同应用, 文献[18]详细介绍了platoon组模式.
个性化推荐方法主要有基于内容推荐、基于协同过滤推荐、基于关联规则推荐、基于效用推荐、基于知识推荐和组合推荐[19-21].同时, 推荐策略也有很多种, 不同的推荐策略产生的推荐结果也不同.但在基于组模式个性化旅游路线推荐中, 传统组模式挖掘由于语义信息缺失导致个性化推荐不完善.
2 问题定义表 1给出了符号列表和定义.
|
Table 1 Symbol list 表 1 符号列表 |
用户轨迹需要给出时间域Ttra, 闭区间[Tstart, Tend]∈Ttra, 带有地理与时间标记的用户信息, 用户信息是(photoID, geoLocation, uploadTime, userID, Text)元组, 包括标识唯一性photoID、上传图片地理位置经纬度geoLocation、图片上传时间uploadTime、上传者userID、上传文本Text.
定义1(用户轨迹). Otra={O1, O2, …, On}是所有轨迹对象集合.给出一个时间闭区间[Tstart, Tend]∈Ttra, 用户oi轨迹是有序位置序列, 表示为Tra(oi)=〈li1, li2, …, lik〉, lij(1≤i≤n, 1≤j≤k), 是在时间区间[Tstart, Tend]的第k个位置信息.
在时间闭区间[Tstart, Tend]内, Cluster聚类集被定义为Ctra={C1, C2, …, Cm}, C(oi)(1≤i≤m), 表示时间闭区间[Tstart, Tend]内对象oi轨迹经过的聚类集有序序列.
定义2(leaguer). 假定
定义3(coterie). 给出时间区间[Tstart, Tend]和mino, 如果在[Tstart, Tend]时间区间内, 所有的Leaguers都在相同聚类集C中, 则(C, O)为Coterie, 即
定义4(closed coterie). Coterie(C, O)为closed coterie, 表示为(Cc, Lc), 需要满足以下两个条件.
(1) ¬∃(C′, O′) s.t. (C′, O′)是coterie并且C⊆C′;
(2) ¬∃(C′, O′) s.t. (C′, O′)是coterie并且O⊆O′.
定义5(coterie挖掘问题). Leaguers作为输入, 通过ClusterGrowth和剪枝策略得到closed coteries.输入: {Lea1, Lea2, …, Leai}; 输出:(Cc, Lc).
3 nMR-DBSCAN优化聚类目前, 大部分有关旅游路线推荐的研究均在单机环境下实现, 无法面对数据量的爆发式增长.因此, 将Hadoop平台下的MapReduce并行编程框架应用在社交网轨迹大数据处理中, 以达到提高算法效率目的.由于DBSCAN算法可在具有噪声空间数据中发现任意形状聚类的优点, 因此将DBSCAN算法与MapReduce并行框架结合进行聚类处理.为了防止数据分区处理过程数据信息丢失, 边界点会同时存放在两个相邻分区中.同时, 为了节点负载均衡和提高算法运行效率, 通过改进PRBP算法[1]达到减少边界点的目的.除此之外, 节点内存溢出将会导致整个MapReduce任务失败, 而改进的nPRBP算法可以确保每个节点内存低于阈值, 并且拥有在固定n个分区条件下最少边界点数量.
nPRBP算法主要包含3个步骤:(1)构建以2eps为宽度的网格, 原因在于DBSCAN算法以eps为半径进行聚类, 这个宽度可以保存足够的聚类信息; (2)计算每片元素点总量和元素点累加量; (3)挑选最好的分片.遍历每个分片, 找出具有在最接近所设节点元素阈值的最少元素点分片, 迭代处理.图 1设定分区数n=2, 第4分片元素最少并且两个分区元素满足阈值, 因此, 4为分区边界.图 1(a)为分片处理图, 图 1(b)和图 1(c)为分区结果.
|
Fig. 1 Illustration of nPRBP algorithm 图 1 nPRBP算法分区图 |
nMR-DBSCAN聚类处理伪代码见算法1.输入为轨迹数据集, 输出为聚类结果.第1行~第13行程序对轨迹数据进行nPRBP分区处理.第14行~第24行程序完成基于MapReduce的DBSCAN聚类处理.在合并阶段, 找出具有相同核心边界点不同分区聚类进行合并处理.在重标记阶段, 将合并结果和分区聚类结果进行重新标记, 得到最终聚类结果.在聚类处理结束之后, 将用户轨迹按时间顺序, 以聚类序列的形式表示轨迹, 例如Tra(oi)= {C1, C2, …, Ck}.由定义2可获得Leaguer集.例如:Tra(o2)={C1, C2}, minc=3, 则轨迹对象o2不是Leaguer.
算法1. nMR-DBSCAN算法.
Input: tra: trajectory data;
Var tra=read input data;
{Step Ⅰ: running nPRBP on tra}
1. S=buildSliceUse2Eps(tra, Eps); /*initializing slices for each dimension*/
2. p=PRBP(tra); /*running PRBP on tra; */
3. P.add(p);
4. For each partition slice p in P do
5. For each slice s in S do
6. If s.total > p.total and s.index > p.index do
7. If sliceNumber < n and s.total < size do
8. P.add(s);
9. Delete p from P;
10. End if
11. End If
12. End for
13. End For
{Step Ⅱ: running DBSCAN in MapReduce phase}
14. For each partition p in P do /*select partition in Map phase*/
15. DBSCANClustering(p); /*running DBSCAN on p in Reduce phase*/
16. For each point Pts in p do
17. If Pts.isInner do /*storing result of inner points to local file*/
18. Output(partition.index, Pts.index+Pts.id);
19. End if
20. Else /*storing result of boundary points to HDFS*/
21. writeFile(partition.index, Pts.index+Pts.id+Pts.isCore);
22. End else
23. End for
24. End for
4 Coterie轨迹组模式挖掘由于传统挖掘轨迹组模式ObjectGrowth算法[22]在寻找轨迹闭模式时效率低, 因此提出ClusterGrowth算法挖掘closed coteries模式.图 2是在eps=2(邻域半径)和Minpts=2(邻域内点阈值)条件下对象轨迹和聚类图.
|
Fig. 2 Object trajectories and clusters 图 2 对象轨迹和聚类 |
由图 2得知:轨迹对象o1聚类轨迹为{C1, C4, C2, C3}, 聚类C1轨迹对象有{o1, o2, o3}.图 3是在图 2条件下生成的ClusterGrowth搜索树, 图中根节点具有所有Leaguer轨迹对象{o1, o2, o3, o4}.之后, 需要将所有Cluster进行前序有序全排列, 每个节点被聚类路线{Cx, …, Cy}和拥有聚类路线中所有轨迹对象{ox, …, oy}标记.由于当聚类数量较大时搜索空间较大, 为了有效地找出closed coteries, 使用前验剪枝和后验剪枝两种剪枝策略压缩搜索空间.
|
Fig. 3 ClusterGrowth algorithm 图 3 ClusterGrowth算法 |
规则1(前验剪枝). 对于一个Leaguer集, 若L={ox, …, oy}⊆Otra和|L|≤mino, 则Leaguer集满足前验剪枝条件.
当ClusterGrowth搜索树构建完成后, 深度优先搜索树, 若树节点轨迹对象Leaguer={ox, …, oy}中对象个数少于阈值mino, 节点被剪枝.例图 3中, 设mino=2, 则黄色节点被剪枝.
规则2(后验剪枝). 对于一个聚类集{Cx, …, Cy}⊆Ctra, 如果存在聚类Cm⊆Ctra并且m < y, 使得L({Cx, …, Cy})⊆ L({Cx, …, Cm, Cy}), 则聚类集{Cx, …, Cy}在聚类搜索空间被剪枝.
尽管前验剪枝压缩了搜索空间, 但整个搜索空间仍然巨大.因此, 使用后验剪枝进一步压缩搜索空间.后验剪枝的思想是:节点中轨迹对象数量不多于节点、子节点轨迹对象数量, 则节点被剪枝.原因在于聚类数量增加, 而轨迹对象没有减少, 即, 当前轨迹路线具有更大包容性.图 3蓝色节点为后验剪枝节点.
规则3(检验规则). 对于一个聚类集{Cx, …, Cy}⊆Ctra, 如果存在聚类Cm⊆Ctra并且m > y, 使得L({Cx, …, Cy})⊆ L({Cx, …, Cy, Cm}), 则聚类集{Cx, …, Cy}在聚类搜索空间被剪枝.
除了上述两种剪枝策略外, 还使用检验规则验证coterie是否为closed coterie.检验规则思想与后验剪枝策略思想大致相同, 由于后验剪枝只能在父节点和子节点之间进行剪枝条件判断, 而检验规则防止了其他节点之间剪枝遗漏.如图 3橙色节点, 由于不满足先验剪枝和后验剪枝条件被标记为closed coterie, 但检验规则可以将橙色节点剪枝.图 3中灰色节点为最终closed coteries.
5 基于语义的个性化旅游路线推荐传统组模式挖掘存在语义信息缺失问题, 降低了个性化旅游路线推荐质量, 因此提出两种基于语义的推荐策略DRSS和CRSS, 并且使用了tf-idf技术结合余弦相似性度量语义相关性.
tf-idf是一种用于信息检索与数据挖掘的常用加权技术, 主要思想是:某个词或短语在一篇文章中出现频率高, 并且在其他文章很少出现, 则认为此词或短语具有良好的类别区分能力.在一份给定文件中, 词频(tf)指的是某一个给定词语在文件中出现的频率.对于在某一特定文件中的词语, 重要性表示为
| $ t{{f}_{i, j}}=\frac{{{n}_{i, j}}}{\sum\nolimits_{k}{{{n}_{k, j}}}} $ | (1) |
其中, tfi, j表示在文件j中词语i的词频重要性, ni, j表示词语i在文件j中出现的次数,
逆向文件频率(idf)是词语普遍重要性度量.词语idf可以由总文件数目和词语出现文件数目衡量, 同时防止词语不存在于语料库, idf表示为
| $ id{{f}_{i}}=\log \frac{|D|}{1+|\{j:{{t}_{i}}\in {{d}_{j}}\}|} $ | (2) |
其中, idfi表示词语i的逆向文件频率.|D|表示语料库中的文件总数, |j:ti∈dj|表示包含词语i的文件数目.由公式(1)和公式(2)可得tf-idf为
| $ tf-id{{f}_{i}}_{, j}=t{{f}_{i}}_{, j}\times id{{f}_{i}}_{, j} $ | (3) |
公式(3)可知, 高词语频率与低文件频率可以产生高权重的tf-idf.即, tf-idf可以过滤掉常见词语, 保留重要的词语.
余弦相似性通过tf-idf产生的词语生成词频向量, 然后由向量余弦夹角计算公式求得余弦相似性:
| $ \cos \theta =\frac{\sum\limits_{i=1}^{n}{({{A}_{i}}\times {{B}_{i}})}}{\sqrt{\sum\limits_{i=1}^{n}{{{({{A}_{i}})}^{2}}}}\times \sqrt{\sum\limits_{i=1}^{n}{{{({{B}_{i}})}^{2}}}}} $ | (4) |
余弦值越接近1, 就表明两个向量越相似.通过将tf-idf技术与余弦相似性结合, 计算语义相似性.
5.1 基于语义的距离敏感推荐策略(DRSS)距离对于旅游者选择旅游路线起着十分重要的作用, 旅游者会尽量保证在不影响旅行地点前提下寻找最短旅行线路.因此, 将语义信息与距离信息结合起来实现旅行路线推荐, 可以提高个性化推荐质量, 称为DRSS.
首先, 在closed coteries中提取每条轨迹语义信息和距离信息.距离因素与推荐系数成反比, 距离越长, 旅游者选择此路线几率越小.而旅游者输入语义与轨迹语义相关性越大越容易被旅游者选择, 即, 语义相关性与推荐系数成正比.因此提出距离得分函数:
| $ Dscor{{e}_{i, j}}=1-\frac{Di{{s}_{tr{{a}_{i, j}}}}}{{{\max }_{k=tra{{N}_{j}}}}\{Di{{s}_{tr{{a}_{1, j}}}}, Di{{s}_{tr{{a}_{2, j}}}}, ..., Di{{s}_{tr{{a}_{k, j}}}}\}} $ | (5) |
其中,
由公式(4)可得, 语义相似度得分函数表示为
| $ Scor{{e}_{tr{{a}_{i, j}}}}=\cos \theta =\frac{\sum\limits_{i=1}^{n}{({{A}_{i}}\times {{B}_{i}})}}{\sqrt{\sum\limits_{i=1}^{n}{{{({{A}_{i}})}^{2}}}}\times \sqrt{\sum\limits_{i=1}^{n}{{{({{B}_{i}})}^{2}}}}} $ | (6) |
其中,
| $ scor{{e}_{tr{{a}_{i, j}}}}=\alpha \times Dscor{{e}_{tr{{a}_{i, j}}}}+(1-\alpha )\times Sscor{{e}_{tr{{a}_{i, j}}}} $ | (7) |
其中, a为距离因素所占比重, 设定为0.5;
在基于组模式个性化旅游路线推荐中, 从众性在个性化旅游路线推荐中起着重要作用.当旅游者来到一个陌生城市, 旅游计划会更倾向于游客多的旅游路线; 同时, 从众性因素和语义相关性均与推荐系数成正比.因此提出基于语义与从众性推荐策略, 称为CRSS.
从众性的旅游路线得分利用计算PageRank思想, 即, 计算起点到终点之间每个相邻聚类得分.相邻聚类之间得分被相邻聚类序列和包含在聚类中兴趣度两个因素影响.因为每个聚类中可能存在多个旅游者, 则旅游者在选择路径时, 路线在聚类中的概率也会影响路线选择.相邻聚类之间, 得分函数主要与如下5部分有关:(1)聚类Cx的兴趣得分; (2)聚类Cy的兴趣得分; (3)经过路径Cx→Cy的旅游者人数; (4)聚类Cx的出度概率; (5)聚类Cy的入度概率.具体表示如下:
| $ scor{{e}_{{{C}_{x}}{{C}_{y}}}}=\sum\nolimits_{tr{{a}_{{{C}_{x}}{{C}_{y}}}}\in tr{{a}_{{{C}_{start}}{{C}_{end}}}}}{({{I}_{{{C}_{x}}}}\times Ou{{t}_{{{C}_{x}}}}_{{{C}_{y}}}+{{I}_{{{C}_{y}}}}\times I{{n}_{{{C}_{x}}}}_{{{C}_{y}}})} $ | (8) |
其中,
如图 2所示, 假定旅游者要求起始位置为vstart={C1}∈Ctra, 终点位置为vend={C3}∈Ctra, 设图 2的o1和o2轨迹为closed coterie, 则两条轨迹的得分为
| $ \begin{align} &scor{{e}_{{{C}_{1}}{{C}_{4}}{{C}_{2}}{{C}_{3}}}}=scor{{e}_{{{C}_{1}}{{C}_{4}}}}+scor{{e}_{{{C}_{4}}{{C}_{2}}}}+scor{{e}_{{{C}_{2}}{{C}_{3}}}}=\\ &(0.5+1)+(1+0.5)+2\times (1+1)=7, \\ &scor{{e}_{{{C}_{1}}{{C}_{2}}{{C}_{3}}}}=scor{{e}_{{{C}_{1}}{{C}_{2}}}}+scor{{e}_{{{C}_{2}}{{C}_{3}}}}. \\ \end{align} $ |
为了从众性因素与语义因素结合, 标准化从众性得分:
| $ Cscor{{e}_{tr{{a}_{i, j}}}}=\frac{scor{{e}_{{{C}_{tr{{a}_{i, j}}}}:start{{C}_{tr{{a}_{i, j}}}}:end}}}{\sum\nolimits_{k=1}^{tra{{N}_{j}}}{scor{{e}_{{{C}_{tr{{a}_{k, j}}}}:start{{C}_{tr{{a}_{k, j}}}}:end}}}} $ | (9) |
其中,
| $ scor{{e}_{tr{{a}_{i, j}}}}=\beta \times Cscor{{e}_{tr{{a}_{i, j}}}}+(1-\beta )\times Sscor{{e}_{tr{{a}_{i, j}}}} $ | (10) |
其中, β为从众性得分占比, 设定为0.5;
在实验阶段, 通过算法执行效率和两种推荐策略的推荐结果展示实验结果.实验数据集为Sydney, Melbourne, Brisbane, Perth和Darwin这5座城市的Instagram数据.由于澳大利亚在9月~次年2月为旅游旺季, 并且推荐算法涉及用户语义信息, 因此提取了2012年9月~2013年2月并过滤掉缺乏语义信息的数据, 最终得到得到113 366个用户数据和851 888条数据.所有算法均由Java实现.
6.1 算法效率在聚类阶段, DBSCAN算法有eps和Minpts这两个参数, 输入数据量的规模也会对算法的运行时间产生影响.因此, 对DBSCAN算法和nMR-DBSCAN算法分别在eps, Minpts和输入数据量的规模上进行运行时间对比, 如图 4所示.
|
Fig. 4 Performance comparison on DBSCAN and nMR-DBSCAN 图 4 DBSCAN和nMR-DBSCAN算法性能比较 |
由图 4(a)可以看出, 两种算法的运行时间随着邻域内元素个数阈值Minpts的增加而减少.原因是Minpts增大会导致向外扩散的搜索元素减少.由图 4(b)可以看出, DBSCAN算法和nMR-DBSCAN算法的运行时间都随着邻域半径eps的增大而逐渐增大.原因是eps增大导致额外向外扩散的搜索元素增加.图 4(c)表明:随着数据量的增大, DBSCAN和nMR-DBSCAN算法的执行时间逐渐增加, 并且nMR-DBSCAN算法的运行时间相比于DBSCAN算法有了明显的降低.总之, 随着eps, Minpts和数据量的变化, nMR-DBSCAN算法相比于DBSCAN算法均有明显的运行时间优势.
在挖掘closed coteries阶段, 根据不同参数对比了ClusterGrowth算法和ObjectGrowth算法的运行时间. ObjectGrowth算法挑选数量更多的对象作为组合项, 而ClusterGrowth算法挑选更少的聚类作为组合项, 因此后者运行时间更少.图 5表明了随着minc和mino的变化, ClusterGrowth算法的执行时间始终少于ObjectGrowth算法.
|
Fig. 5 Performance comparison on ObjectGrowth and ClusterGrowth 图 5 ObjectGrowth和ClusterGrowth算法性能比较 |
在推荐旅游路线阶段, DRSS和CRSS的运行时间在固定minc=3和mino=2的前提下进行实验, 数据量从5 000~25 000.图 6表明:随着数据量的增大, DRSS和CRSS的运行时间逐渐增加.
|
Fig. 6 Performance comparison on DRSS and CRSS 图 6 DRSS和CRSS算法性能比较 |
6.2 旅游路线的推荐
在基于组模式个性化旅游路线推荐阶段, 提出了DRSS和CRSS两种推荐策略.旅游者可以提供旅行的出发地和目的地、途径旅游地点及语义信息.通过对所有closed coteries的分析处理, 可得到满足旅游者经过地点要求的closed coteries.然后, 按照DRSS和CRSS的得分计算公式计算closed coteries组轨迹中每条轨迹的得分, 将相对满足旅游者意愿的路线推荐给旅游者.同时, 由于DBSCAN聚类算法及ClusterGrowth算法具有参数敏感性, 因此将参数eps, minpts, minc和mino固定设置为0.5, 100, 2和2进行实验.通过展示路线经过的准确地点, 完善地展示推荐路线, 防止由于地图比例尺的影响无法详细获取路线信息.
个性化旅游路线推荐以从Perth到Melbourne、最后到达Sydney的路线及music关键词作为输入进行推荐展示.图 7展示了基于closed coteries的DRSS和CRSS推荐路线.
|
Fig. 7 Recommending routes by SDRS and SCRS based on closed coterie patterns 图 7 基于closed coterie模式的SDRS和SCRS的路线推荐 |
图 7(a)展示了城市之间旅游路线推荐, 由于比例尺大, 将DRSS和CRSS城市之间的轨迹推荐路线放入图 7(a)中.图 7(b)~图 7(d)展示了基于DRSS路线推荐的准确位置.图 7(b)展示了旅游者在Perth的The Hen House Live上传Good music in perth文本信息, 说明在Perth的Hen House Live听了一场音乐会.图 7(c)展示了推荐轨迹Melbourne位置的The Bottom End上传了Melb…文本信息, 说明旅游者在Melbourne去了Bottom End.图 7(d)展示了推荐轨迹在Sydney的位置为Sydney Opera House, 上传了I love music…文本信息, 说明旅游者到达Sydney去了Sydney Opera House听音乐.图 7(b)~图 7(d)这条轨迹是将距离和语义结合得到的推荐路线, 能够看出, 这条轨迹符合旅游者路线地点和音乐的要求.图 7(e)~图 7(g)展示了基于CRSS的路线推荐准确位置.图 7(e)显示, 旅游者在Perth的Hyde Park上传了Me and Burger文本信息, 说明在Perth的Hyde Park游玩.图 7(f)展示了推荐轨迹在Melbourne的Arts Center Melbourne上传了sweet music文本信息, 说明旅游者到达Melbourne后去了Arts Center Melbourne听音乐.图 7(g)展示了旅游者在Syndey的St mary’s Cathedral上传了beautiful…文本信息, 即, 去了St mary’s Cathedral.
从旅游路线推荐图中可以看出, 分别将距离因素和从众因素与语义信息结合起来进行路线推荐.以往的推荐celv均只考虑单一的影响因素, 并且未考虑社交网语义信息对旅游路线推荐的影响.从旅游路线推荐图可以看出:推荐的路线与用户输入的信息进行了信息匹配, 相比于传统的只考虑距离因素或者从众因素, 提出的推荐策略会更贴近用户的需求, 也会增加用户体验和推荐信息的完整性.
7 总结在coterie组模式挖掘阶段, 为了提高寻找closed coteries的效率, 使用了ClusterGrowth算法, 并采用前验剪枝和后验剪枝压缩搜索空间.最后, 提出验证规则找出closed coteries.实验结果表明, ClusterGrowth算法的效率高于ObjectGrowth算法.
在基于组模式的个性化旅游路线推荐阶段, 传统的组模式挖掘由于语义信息的缺失导致了个性化推荐不完善, 因此提出基于语义的DRSS和CRSS两种推荐策略, 完成个性化旅游路线的推荐.实验展示了DRSS和CRSS推荐的旅游路线.
在聚类处理阶段, 为了提高聚类算法的效率, 将DBSCAN聚类算法与Hadoop平台下的MapReduce框架结合起来, 并提出了nPRBP算法提高分区效率.实验结果表明, nMR-DBSCAN算法提高了聚类算法的效率.
| [1] |
Dai BR, Lin IC. Efficient Map/Reduce-based DBSCAN algorithm with optimized data partition. In: Proc. of the IEEE CLOUD. 2012. 59-66. [doi: 10.1109/CLOUD.2012.42] |
| [2] |
Nie LQ, Song XM, Chua TS. Learning from multiple social networks. In: Proc. of the Synthesis Lectures on Information Concepts, Retrieval, and Services. Morgan & Claypool Publishers, 2016. [doi: 10.2200/S00714ED1V01Y201603ICR048] |
| [3] |
Zheng Y, Zhang LZ, Xie X, Ma WY. Mining interesting locations and travel sequences from GPS trajectories. In: Proc. of the WWW. 2009. 791-800. [doi: 10.1145/1526709.1526816] |
| [4] |
Bastani F, Xie X, Huang Y, Powell JW. A greener transportation mode: Flexible routes discovery from GPS trajectory data. In: Proc. of the GIS. 2011. 405-408. [doi: 10.1145/2093973.2094034] |
| [5] |
Savage NS, Nishimura S, Chávez NE, Yan XF. Frequent trajectory mining on GPS data. In: Proc. of the LocWeb. 2010. 3. [doi: 10.1145/1899662.1899665] |
| [6] |
Yin PF, Ye M, Lee WC, Li ZH. Mining GPS data for trajectory recommendation. In: Proc. of the 18th Pacific-Asia Conf. on PAKDD. Springer-Verlag, 2014. 50-61. [doi: 10.1007/978-3-319-06605-9_5] |
| [7] |
Eldawy A, Mokbel MF, Al-Harthi S, Alzaidy A, Tarek K, Ghani S. SHAHED: A MapReduce-based system for querying and visualizing spatio-temporal satellite data. In: Proc. of the ICDE. 2015. 1585-1596. [doi: 10.1109/ICDE.2015.7113427] |
| [8] |
Tsai CY, Lai BH. A location-item-time sequential pattern mining algorithm for route recommendation. Knowl. -Based Syst., 2015, 73: 97-110. [doi: 10.1016/j.knosys.2014.09.012] |
| [9] |
Pires CSG, de Aguiar MS, Paulo R. Ferreira:Mobile ACORoute-route recommendation based on communication by pheromones. Polibits, 2015, 51: 27–32.
[doi:10.17562/PB-51-4] |
| [10] |
Dai J, Yang B, Guo CJ, Ding ZM. Personalized route recommendation using big trajectory data. In: Proc. of the ICDE. 2015. 543-554. [doi: 10.1109/ICDE.2015.7113313] |
| [11] |
Shen Y, Zhao LG, Fan J. Analysis and visualization for hot spot based route recommendation using short-dated taxi GPS traces. Information, 2015, 6(2): 134–151.
[doi:10.3390/info6020134] |
| [12] |
Wang MM, Zuo WL, Wang Y. An improved density peaks-based clustering method for social circle discovery in social networks. Neurocomputing, 2016, 179: 219–227.
[doi:10.1016/j.neucom.2015.11.091] |
| [13] |
He YB, Tan HY, Luo WM, Feng SZ, Fan JP. MR-DBSCAN:A scalable MapReduce-based DBSCAN algorithm for heavily skewed data. Frontiers of Computer Science, 2014, 8(1): 83–99.
[doi:10.1007/s11704-013-3158-3] |
| [14] |
Zheng K, Zheng Y, Yuan N, Shang S. On discovery of gathering patterns from trjaectories. In: Proc. of the IEEE 2013. 2013. 242-253. [doi: 10.1109/ICDE.2013.6544829] |
| [15] |
Vieira MR, Bakalov P, Tsotras VJ. On-Line discovery of flock patterns in spatio-temporal data. In: Proc. of the GIS. 2009. 286-295. [doi: 10.1145/1653771.1653812] |
| [16] |
Jeung HY, Yiu ML, Zhou XF, Jensen CS, Shen HT. Discovery of convoys in trajectory databases. Computer Science, 2010, 1(1): 1068–1080.
[doi:10.14778/1453856.1453971] |
| [17] |
Li YX, Bailey J, Kulik L. Efficient mining of platoon patterns in trajectory databases. Data Knowledge Engineering, 2015, 100: 167–187.
[doi:10.1016/j.datak.2015.02.001] |
| [18] |
Fan Q, Zhang DX, Wu HY, Tan KL. A general and parallel platform for mining co-movement patterns over large-scale trajectories. PVLDB, 2016, 10(4): 313–324.
[doi:10.14778/3025111.3025114] |
| [19] |
Liu HL, Li JH, Peng J. A novel recommendation system for the personalized smart tourism route: Design and implementation. In: Proc. of the ICCI*CC2015. 2015. 291-296. [doi: 10.1109/ICCI-CC.2015.7259400] |
| [20] |
Hasuike T, Katagiri H, Tsubaki H, Tsuda H. A route recommendation system for sightseeing with network optimization and conditional probability. In: Proc. of the SMC. 2015. 2672-2677. [doi: 10.1109/SMC.2015.467] |
| [21] |
Wen YT, Cho KJ, Peng WC, Yeo JY, Hwang SW. KSTR: Keyword-Aware skyline travel route recommendation. In: Proc. of the ICDM. 2015. 449-458. [doi: 10.1109/ICDM.2015.37] |
| [22] |
Li Z, Ding B, Han J, Kays R. Swarm:Mining relaxed temporal moving object clusters. Proc. of the VLDB Endowment, 2010, 3(1): 723–734.
[doi:10.14778/1920841.1920934] |