基于加权SimRank的中文查询推荐研究

查询推荐是搜索引擎系统中的一项重要技术,其通过推荐更合适的查询以提高用户的搜索体验。现有方法能够找到直接通过某种属性关联的相似查询,却忽略了具有间接关联的语义相关查询。该文将用户查询及查询间直接联系建模为查询关系图,并在图结构相似度算法SimRank的基础上提出了加权SimRank(简称WSimRank)用于查询推荐。WSimRank综合考虑了查询关系图的全局信息,因而能挖掘出查询间的间接关联和语义关系。然而,WSimRank复杂度太高而难以实用,该文将WSimRank转换为一个状态层次图的遍历和计算过程,进而采用动态规划、剪枝等策略对其进行优化从而可以实际应用。在大规模真实Web搜索日志上的实验表明,WSimRank在各项评价指标上均优于SimRank和传统查询推荐方法,其MAP指标接近0.9。

基于SimRank++算法和协同过滤算法的疾病-症状关联性研究

文章基于临床电子病历中医疗实体的共现关系,先构建疾病-症状二分网络,再利用SimRank++算法和协同过滤算法共同实现疾病实体和症状实体之间相关关系的度量,最后应用Spark分布式平台来适应大量数据的高计算强度,以提高计算效率。实验表明,本文方法可以有效度量疾病实体和症状实体之间的相关程度,可为临床医生的疾病诊断提供帮助。

基于SimRank的中药“效-效”相似关系挖掘

中药"效-效"关联分析是中医药研究中最基本也是最重要的问题,对药效判断具有重要意义。该文旨在利用数据挖掘技术,从中药方剂数据中自动挖掘"效-效"相似关系,自动归纳不同药效之间的相似度,提出了基于SimRank方法的"效-效"相似关系挖掘算法。中医专家对算法输出结果的大量验证表明,该算法具有较高的正确率,其中"优良"和"合理"共占70.568%。

基于加权SimRank的跨领域文本情感倾向性分析

近年来,跨领域文本倾向性分析已成为自然语言处理领域的一个研究热点.它利用已经标注倾向性的源领域文本,预测目标领域文本的倾向性.然而,由于不同领域的数据往往服从不同的分布,导致传统的监督分类模型通常不能取得理想的效果.为解决以上问题,提出了一种基于加权SimRank的分析模型.本模型在加权SimRank算法的基础上,构建潜在特征空间,然后在潜在特征空间下学习得到映射函数,并对每个样本重新映射,从而缩小了不同领域间的数据分布差异,实现了跨领域情感分类.最后,通过实验验证了该方法的有效性.

基于权重标准化SimRank方法的查询扩展技术研究

查询扩展是信息检索中的一项重要技术。传统的局部分析查询扩展方法利用伪相关文档作为候选词集合,然而部分伪相关文档并不具有很高的相关性。该文利用真实的搜索引擎查询日志,建立了查询点击图,经过多次图结构的转化得到能够反映词之间关联程度的词项关系图,并在图结构的相似度算法SimRank的基础上,提出了一种基于权重标准化的改进SimRank方法,该方法利用词项关系图中词项的全局和间接关系,能够有效挖掘与原始查询相关联的扩展词。同时,为降低SimRank算法的计算复杂度,该文采用了剪枝等策略进行优化,使得计算效率有大幅提高。在TREC标准数据集上的实验表明,该文的方法可以有效地选择相关扩展词。MAP指标较局部分析查询扩展方法提高了1.81%,在P@10和P@20指标评价中效果分别提高了5.44%和3.73%。

基于SimRank的跨领域情感倾向性分析算法研究

情感倾向性判断是指根据文本表述分析文本的倾向性,即发表文本的作者所持有的支持或反对的态度,对于特定领域的情感倾向性研究尤以运用监督分类方法所得出的实验结果较为理想。但若将此类方法直接运用于不同领域的文本,其效果却难以尽如人意。在这种情况下,如何利用已标注情感倾向性的源领域文本去判断未知情感倾向性的目标领域文本的倾向性,即跨领域的情感倾向性分析问题——成为当前研究的热点。为此,该文提出一种基于SimRank的跨领域情感倾向性分析算法,把在源领域和目标领域中共现的词汇作为连接两个领域的桥梁,利用情感词典和SimRank算法找出潜在情感空间,然后使用SVM对已标注的源领域进行训练进而得到训练模型,以便利用此模型预测目标领域的情感倾向性。该文亦通过相关实验所得到的实验结果表明了此方法的有效性。

一种面向不确定图的SimRank算法

针对以往的搜索引擎日志分析都主要集中在用户行为分析、查询推荐及搜索引擎评价等方面,采用社会网络分析法对搜索引擎进行日志分析。以不确定图的方式逻辑表示搜索引擎的日志中查询词和网页的链接关系,通过基于不确定图的SimRank算法,计算查询词与网页的相似度,最终以相似度和查询词的加权方式建立网页描述库。针对概率抽样的3点基本要求,提出一种渐进式的抽样策略,从而保证采用抽样技术对于不确定图中SimRank值计算的准确性。实验表明该算法具有较好的准确率和可行性。

基于SimRank的作者相似度计算

现有的相似度计算方法大都依赖于作者间的直接关联,忽略了间接关联。文章提出一种新的基于SimRank的作者相似度计算方法,充分考虑作者关键词二分图网络的整体结构特性,利用图结构相似度算法挖掘出作者间以及词汇间的潜在关联关系。初步实验表明该方法能够有效地识别作者之间的相似度,相比于传统的关键词耦合,该方法可以明显提高作者相似度计算的准确性。

基于改进SimRank的产品特征聚类研究

针对在线用户评论中产品特征的提取和聚类问题进行了研究,提出一种改进的SimRank算法。将情感词-特征对放入二分网中,在二分网中使用改进后的SimRank算法计算特征词之间的相似度;再通过谱聚类算法对特征相似度进行聚类,提取网络产品的特征集合。以某电脑评论为例,从中提取情感词-特征对进行研究。实验结果显示,改进后的算法准确率更高。改进后的特征相似度检测方法可以作为检测特征相似度的有效方法,实验采用在线产品的评论语料。实验结果表明,使用改进后的SimRank相似度对特征词进行聚类提取出特征更加准确。

基于SimRank全局矩阵平滑收敛的网络社区发现

SimRank方法是一种基于图的拓扑结构信息来衡量任意两个对象间相似程度的方法,针对在真实的大规模社交网络中节点与节点之间的迭代计算过程需要消耗大量的时间,提出了一种基于SimRank全局矩阵平滑收敛的网络社区发现方法(SimRank global smooth convergence,SGSC)。首先,该算法通过经典度量来识别网络中的初始核心节点;然后利用矩阵平滑收敛来计算SimRank得到最终核心节点;最后,基于全局收敛矩阵,将社区聚集在核心节点周围,使用Closeness指数合并两个社区,通过递归的重复该过程,聚类出最终社区。在3种真实的不同规模的社交网络中将SGSC和其他2种具有代表性的方法进行比较,并验证了提出的算法在不同规模的社交网络中社区划分的准确率和算法运行的时间性能上有所提升。

基于随机游走路径的分布式SimRank算法

SimRank算法是一种常用的相似性度量模型,它基于图的拓扑结构信息来衡量任意两个对象之间的相似程度。随着数据规模的不断增大,集中式SimRank算法已不适用,而已有的分布式Sim Rank算法在运行效率和扩展性等方面存在缺陷。针对上述问题,提出了一种两阶段的基于随机游走路径的分布式Sim Rank算法。第一阶段基于BSP(bulk synchronous parallel)模型建立随机游走路径索引信息,支持新路径的动态添加,并通过阈值过滤尽可能减少生成路径的数量;第二阶段利用第一阶段生成的索引信息,提出了基于MapReduce的分布式SimRank算法。最后,通过实验验证了算法的可行性和有效性。

Asyn-SimRank:一种可异步执行的大规模SimRank算法

SimRank算法利用网络结构来评估网络中任意2点的相似性,它被广泛应用于社交网络和链接预测等诸多领域中.近年来,随着大数据技术的发展,SimRank算法处理的数据不断增大,人们利用MapReduce等分布式计算模型设计实现分布式的大规模SimRank算法来适应大数据处理的需求.但是,由于SimRank算法包含开销较大的迭代过程,每次迭代之后都需要一个全局同步,且每次迭代的计算复杂度高、通信量大,SimRank算法不能在分布式环境下高效地实现.1)提出Asyn-SimRank算法,该算法采用迭代-累积的方式完成迭代计算,异步执行SimRank的核心迭代过程,避免了大规模分布式计算中的大量同步开销,同时有效降低计算量并减少通信开销;2)提出关键点优先调度计算,提升了AsynSimRank算法的全局收敛速度;3)证明了Asyn-SimRank算法的正确性和收敛性以及关键点优先调度计算的有效性;4)支持异步迭代的分布式框架Maiter上实现了Asyn-SimRank算法.实验结果显示,相比较于Hadoop,Spark上实现的SimRank算法和Delta-SimRank算法,Asyn-SimRank算法大大提升了算法的计算效率,加速了算法收敛.

大规模图上的SimRank计算研究综述

SimRank是一种衡量有向图中任意两节点间结构相似度的模型,其主要思想为,若图中两个节点被相似节点引用,则这两个节点相似.SimRank计算的相似度被广泛应用到网络图聚类、近似查询和协同过滤等领域.SimRank计算模型是一个递归模型,其计算时间、空间复杂度非常高,很难应用于大规模图计算.过去十几年,研究者们针对大规模图提出了许多高效或近似计算的SimRank计算算法.本文首先介绍SimRank模型的描述,以及常见的SimRank计算问题定义,然后按照计算方式将这些算法分为迭代法、非迭代法与随机游走法三类;将非迭代法分为基于矩阵运算求解、基于节点对图求解以及基于线性表示求解,将随机游走法分为基于不同索引结构求解、基于不同抽样方式求解以及其他随机游走算法;介绍了这些算法的基本概念、计算原理以及算法特点;分析了随机游走法与迭代法、非迭代法之间的关系;对各种算法的时间复杂度、空间复杂度、计算精确度以及可扩展性进行了论述;在此基础总结了这些SimRank算法所对应的计算场景,主要包括单点对/单源(Single Pair/Single Source)查询问题、全体/部分节点对(All Pair/Partial Pair)计算问题以及查询问题.最后对不同算法实验中图的规模进行了总结,并对大规模图上的SimRank计算方法进行了总结和展望.

基于融合时间信息影响的SimRank算法的个性化推荐

由个性化推荐的实际应用环境,文章提出一种融合时间上下文信息的基于二分图模型个性化推荐算法。首先引入时间衰减函数对基于二分图模型的SimRank算法进行改进,使得时间对推荐的影响量化成图中节点的关联概率值,设计出融合时间信息的SimRank算法。再与协同过滤算法相结合,最终得到基于融合时间上下文信息的二分图模型的个性化推荐算法。实验结果表明：该算法比传统协同过滤算法以及基于二分图的SimRank算法在推荐的各项指标上有明显提高。

一种基于SimRank得分的谱聚类算法

传统的谱聚类算法在建立相似度矩阵时仅考虑数据点与点的距离,忽略了数据点之间隐含的内在联系。针对这一问题,提出了一种基于SimRank的谱聚类算法。该算法首先用无向图数据建立邻接矩阵,并计算出基于SimRank的相似度矩阵;然后根据相似度矩阵建立拉普拉斯矩阵表达式,对其进行归一化后再进行谱分解;最后对分解得到的特征向量进行k-means聚类。在Zoo等UCI标准数据集上的实验结果表明,所提算法在聚类精确度、标准互信息和纯度3个评价指标上均优于现有的LRR(Low Rank Rrepresentation)等基于距离相似度的谱聚类算法。

加权SimRank算法在超常规用药检测中的应用

异常医疗数据的挖掘是一个很有价值的领域,针对就诊时用药的规律性,在图结构的相似度算法SimRank的基础上提出了加权SimRank(WSimRank),并基于WSimRank算法提出了用药异常的检测模型。该模型利用WSimRank算法挖掘药品相似性,对相似的药品构建使用时长的交集,以此构造用药规则库,将待检用药行为与规则库进行比对从而确定异常。实验结果显示,在检测用药异常时,WSimRank算法的各项评价指标都比原始的SimRank算法更优秀。

基于SimRank的百度百科词条语义相似度计算

提出一种利用百度百科半结构化数据自动获取词语相似度的方法,该方法将百科词条与其相关词条看做有向图的两个节点,且两节点相互之间存在着链接关系,然后利用SimRank算法计算百科词条语义相似度。实验表明,该方法优于传统的词语语义相似度测量,能准确地反映词语之间的语义关系。

不确定图上的kNN查询处理

在现实中的许多领域产生大量不确定的图结构的数据,例如分子化合物、蛋白质交互网络等.同时现实中有很多应用例如推荐系统中的推荐过滤、欺诈检测和社会网络的链接预测等,需要查询给定节点的k个最相似节点,针对这一问题,提出了用基于SimRank度量的方法来求解.由于图的动态演变和不确定性导致用现有的SimRank计算方法求k个最近邻的代价昂贵,因此提出一个有效算法,在保证一定准确性的前提下,通过引入路径阈值,算法只需考虑查询点的邻居区域无需考虑整个图从而达到明显的剪枝效果,该方法在确定图和不确定图上都可以适用.在此基础上为了进一步提高效率,算法在不确定图上引入采样技术.最后从理论、实验说明验证了算法的高效性和有效性.

评论挖掘中产品属性归类问题研究

该文主要把产品评论中属性的不同描述进行归类。在产品评论中,同类的属性会有不同的描述,例如,手机的"外形"和"设计"指的是同类属性。同类属性虽然有不同的描述,但是在句中却和相同的情感词搭配使用。该文首先抽取评论句中属性和情感词的搭配关系,形成一个二部图,然后用权重标准化SimRank计算不同属性之间的相似度,并把所得的结果与半监督学习中的贝叶斯分类器进行融合,得到了更好的分类结果。通过实验证明了此方法的有效性。

基于仿射传播的有向网络聚类算法

现有大多数的网络聚类方法都只是针对无向网络,已有的有向网络聚类方法建立在传统聚类算法基础之上,存在着一定的局限性。针对上述问题,提出一种基于仿射传播的有向网络聚类算法,该算法首先采用Sim-Rank作为节点之间的相似度,并将计算得到的结果转换为适应于仿射传播算法的负值;然后将相似度矩阵作为输入,利用具有更好性能的仿射传播算法对有向网络进行聚类。实验结果表明,所提出算法的聚类性能优于其他几种具有代表性的有向网络聚类算法。