基于时空相似性的大规模轨迹数据融合技术

如何利用大数据技术来支撑地铁路网规划、运营调度、应急管理和公共服务是当前学术界和工业界的研究热点。该文使用集成电路(Integrated Circuit,IC)卡交易记录和手机 WiFi 信号记录两种不同的数据,提出一种基于时空相似性的设备关联方法来重现乘客的完整轨迹。通过计算 IC 卡和手机 两种不同设备历史轨迹的时空相似性,来关联同一乘客的 IC 卡和对应的手机。基于这种关联可以融合粗粒度的 IC 卡轨迹和细粒度的手机站内轨迹,进而重现乘客在地铁网络里的完整轨迹。实验通过对深 圳地铁连续两个月智能 IC 卡刷卡数据和 WiFi 信号数据进行分析,同时利用最长公共子序列方法,在Spark 集群计算了 728 万张 IC 卡轨迹数据和 4 010 万个移动设备轨迹数据的时空相似性。实验结果显示,该方法可以重现 20.3 万乘客的完整轨迹,足以用来支撑地铁清分和智慧警务等应用。     

一种基于熵的文本相似性计算方法

文本比较是求解两个文本间相似度的过程,文本间的相似度越高代表两个文本越趋于类似。传统的相似度算法主要从字符的角度度量文本的相似性,而忽略了文本内多个共同文本串对于文本相似度的影响。针对此问题,本文提出一种基于熵的相似度求解方法。该方法在对文本间字符信息的提取基础上,建立共同子文本串度量维度,然后采用熵的方法进行相似度度量。实验表明,该方法具有更平滑的相似度曲线,验证了算法的有效性和准确性。     

基于校园无线网络的时空轨迹相似性度量

为挖掘校园无线网络用户之间的关联性,提高用户相似性度量的准确性,针对无线网络中产生的时空轨迹数据的特征,提出一种基于最短时间距离子序列的时空轨迹相似性度量模型。同时考虑轨迹的时间参数和空间参数特征,利用最短时间距离模型求取空间相似性,采用最短时间距离子序列模型,引入连续因子体现轨迹序列特征,求取轨迹空间相似性;将时间和空间相似性汇总得到轨迹整体相似性,反映用户之间的相似性结果;利用并行滑动时间窗对用户轨迹进行划分,提高计算效率。基于真实校园无线网络数据集进行实验分析,验证了该方法在局部轨迹段和整体轨迹集中均有较好准确性。     

基因序列相似程度的LCS算法研究

首先重新审视了采用穷举法求解LCS问题的困难,以及对应的优点;随后针对穷举法的优点进行了两类优化;最后给出了算法实现的图示以及算法的结论。通过实验证明,算法的效率较传统的动态规划的LCS算法有了很大的提升。     

应用Hausdorff距离的时空轨迹相似性度量方法

相似性度量方法的选取和稳健性对时空轨迹聚类结果的有效性是至关重要的.针对时空轨迹数据复杂的多重维度信息,选取空间维和时间维2个维度度量时空轨迹的相似性,提出一种应用Hausdorff距离的时空轨迹相似性度量方法.首先从时空轨迹的3个特性出发,提出面向相似性度量的时空轨迹重组策略;然后将传统的以点为中心进行相似性度量的思路转换为以轨迹段为中心,提出一个考虑时间同步性的时空轨迹段距离度量公式;最后鉴于传统的Hausdorff距离进行时空轨迹相似性度量具有时空轨迹整体形状特征的优点,针对其容易受时空轨迹局部空间分布影响和忽略时间维信息的缺陷,提出一种基于单位时间平均值Hausdorff距离的时空轨迹相似性度量方法.采用微博签到轨迹数据和出租车GPS轨迹数据进行轨迹时空聚类实验,将文中提出的时空轨迹相似性度量方法与已有的其他方法进行比较,实验结果表明,该方法可以有效地计算时空轨迹的相似性,满足时空轨迹聚类的需求.     

基于LCSS的数据流相似性查询处理算法研究

数据流相似性查询广泛应用于智能家居、环境监测等领域.当前以LCSS(longest common subsequence)作为相似性测度函数的研究并不多.NAIVE算法使用基本动态规划方法计算测度函数值,通过该值与相似阈值的比较得到查询结果,对基于LCSS的数据流相似性查询问题进行研究.针对NAIVE算法必须在动态规划矩阵所有成员取值的计算完成后才能得到查询结果的缺点,提出了一种基于PS(possible solution)-CC(column critical)域优化策略的数据流相似性查询处理算法.该算法划定了每个窗口上动态规划矩阵的PS域和CC域,很好地利用了这2个域中成员所具有的性质和相似性查询的特点,无须获得测度函数的最终值便可得到查询结果,省略了很多矩阵成员的计算.实验部分证明了该算法的有效性,与同类算法相比,在处理具有更高精度结果要求的查询时效果更好.     

多序列的近似LCS改进算法

提出2种针对3条源序列的近似LCS算法,近似因子均为1/|?|。其中,线性近似LCS算法的时空复杂度均为 , 为最长源序列的长度,适于解决大规模问题。递归近似LCS算法时空复杂度均为O(nlogn),适于要求高精度问题。同时,这2种算法都能用于解决多序列的LCS和CLCS问题。实验验证了这2种算法的有效性。     

位置服务社交网络用户行为相似性分析

基于位置的社交网络(LBSN)能够支持用户分享地理位置信息,网站中保存用户访问真实世界地理位置的记录构成用户的行为轨迹,但LBSN用户相似性的分析并没有从用户的地理位置轨迹上加以考虑。为此,提出基于划分层次,在不同的邻域半径下密度聚类的方法,探索基于位置的服务(LBS)平台上用户地理位置上相似性的度量。该方法在不同空间位置比例尺下观察用户访问各个聚类区域的次数,进而利用向量空间模型(VSM)计算用户在各个层级的相似性,最终以不同权重叠加各层级的用户相似性值,得出用户在地理空间行为上的相似性。基于国内某大型位置社交网站真实用户数据的实验结果表明,该方法能有效识别出访问地理位置相似的用户。     

基于位置序列的广义后缀树用户相似性计算方法

为了解决移动数据形成的轨迹间用户相似性问题,提出了一种基于位置序列的广义后缀树(LSGST)用户相似性计算方法。该算法首先从移动数据中抽取位置序列,同时将位置序列映射为字符串,完成了对位置序列的处理到对字符串处理的转化工作;然后,构建不同用户间的位置序列广义后缀树;最后,分别从经过的相似地方个数、最长公共子序列、频繁公共位置序列三方面对相似性进行具体计算。理论分析和仿真表明,该算法提出的三个计算指标在计算相似性方面具有理想的效果;除此之外,与构造后缀树的普通方法相比,时间复杂度较低;与动态规划和朴素字符串匹配方法相比,该算法在寻找最长公共子串、频繁公共位置序列时,效率更高。实验结果表明LSGST能够有效测量相似性,同时减少了寻找测量指标时需要处理的轨迹数据量,并在时间复杂度方面明显优于对比算法。     

An efficient hybrid similarity measure based on user interests for recommender systems

Recommender systems are used to suggest items to users based on their interests. They have been used widely in various domains, including online stores, web advertisements, and social networks. As part of their process, recommender systems use a set of similarity measurements that would assist in finding interesting items. Although many similarity measurements have been proposed in the literature, they have not concentrated on actual user interests. This paper proposes a new efficient hybrid similarity measure for recommender systems based on user interests. This similarity measure is a combination of two novel base similarity measurements: the user interest–user interest similarity measure and the user interest–item similarity measure. This hybrid similarity measure improves the existing work in three aspects. First, it improves the current recommender systems by using actual user interests. Second, it provides a comprehensive evaluation of an efficient solution to the cold start problem. Third, this similarity measure works well even when no corated items exist between two users. Our experiments show that our proposed similarity measure is efficient in terms of accuracy, execution time, and applicability. Specifically, our proposed similarity measure achieves a mean absolute error (MAE) as low as 0.42, with 64% applicability and an execution time as low as 0.03 s, whereas the existing similarity measures from the literature achieve an MAE of 0.88 at their best; these results demonstrate the superiority of our proposed similarity measure in terms of accuracy, as well as having a high applicability percentage and a very short execution time.     

融合兴趣的微博用户相似度计算研究

针对传统基于用户的博文内容和共同好友数在计算微博用户的相似度时存在潜在误差过大的问题、而基于用户多源背景信息的相似度计算模型有计算复杂度高且忽略了用户的兴趣等问题,提出了一种结合用户兴趣和背景信息的综合相似度计算方法（BIBS）。首先从用户的标签中提取用户的兴趣,当用户的标签缺失时,通过对用户关注关系网络中的重要用户聚类来间接获取用户的兴趣点,以此计算用户的兴趣相似度;其次根据用户的性别、年龄和地点等背景属性计算用户的背景相似度,层次化地挖掘出最相似的用户;最后基于新浪微博的数据进行实验分析。结果表明,与基于多源信息相似度的微博用户推荐算法（MISUR）相比,该方法在用时更少的情况下,准确率、召回率和◢F◣值分别提高了8.1%、16.7%和13.6%,证明了提出的BIBS方法的有效性和准确性。     

基于面积划分的轨迹相似性度量方法

大数据时代背景下,时空轨迹数据应用的场景日益增多且这些数据蕴含着大量的信息,而轨迹的相似性度量作为轨迹挖掘工作的关键步骤起着举足轻重的作用。但传统轨迹相似度量方法有着时间复杂度高、基于轨迹点判断而不够精确的问题。为了解决这些问题,提出了适用于无路网结构轨迹的以轨迹间面积度量为原理的三角分割（TD）方法轨迹相似度量方法。通过建立“指针”选择两轨迹间的轨迹点连线以构建互不重叠的三角形,累加三角形面积并计算轨迹相似度,通过在不同应用场景下设置的阈值来确认轨迹的相似情况。实验结果表明,与传统的基于轨迹点的空间轨迹相似度量方法——最长公共子序列（LCSS）方法和弗雷歇距离度量方法相比,所提方法提升了识别的准确度,且时间复杂度降低了接近90%,能更好地适应轨迹点分布不均匀的轨迹相似度量工作。     

基于时空模式的轨迹数据聚类算法

针对轨迹聚类算法在相似性度量中多以空间特征为度量标准,缺少对时间特征的度量,提出了一种基于时空模式的轨迹数据聚类算法。该算法以划分再聚类框架为基础,首先利用曲线边缘检测方法提取轨迹特征点;然后根据轨迹特征点对轨迹进行子轨迹段划分;最后根据子轨迹段间时空相似性,采用基于密度的聚类算法进行聚类。实验结果表明,使用所提算法提取的轨迹特征点在保证特征点具有较好简约性的前提下较为准确地描述了轨迹结构,同时基于时空特征的相似性度量因同时兼顾了轨迹的空间与时间特征,得到了更好的聚类结果。     

一种结合用户可信度与相似度的鲁棒性推荐算法

协同过滤推荐系统面临着托攻击的安全威胁。研究抵御托攻击的鲁棒性推荐算法已成为一个迫切的课题。传统的鲁棒性推荐算法在算法稳定性与推荐准确度之间难以权衡。针对该问题,首先定义一种用户可信度指标,其次改进传统的相似度计算方法,通过结合用户可信度与改进的相似度,滤除攻击概貌,为目标用户作出推荐。实验表明,与传统算法相比,本文算法具备更强的稳定性,同时保持了良好的推荐准确度。     

基于移动用户上下文相似度的张量分解推荐算法

针对移动服务推荐中用户上下文环境复杂多变和数据稀疏性问题,提出一种基于移动用户上下文相似度的张量分解推荐算法——UCS-TF。该算法组合用户间的多维上下文相似度和上下文相似可信度,建立用户上下文相似度模型,再对目标用户的K个邻居用户建立移动用户-上下文-移动服务三维张量分解模型,获得目标用户的移动服务预测值,生成移动推荐。实验结果显示,与余弦相似性方法、Pearson相关系数方法和Cosine1改进相似度模型相比,所提UCS-TF算法表现最优时的平均绝对误差（MAE）分别减少了11.1%、10.1%和3.2%;其P@N指标大幅提升,均优于上述方法。另外,对比Cosine1算法、CARS2算法和TF算法,UCS-TF算法在数据稀疏密度为5%、20%、50%、80%上的预测误差最小。实验结果表明UCS-TF算法具有更好的推荐效果,同时将用户上下文相似度与张量分解模型结合,能有效缓解评分稀疏性的影响。