基于本地文档库的搜索引擎自动排序算法

基于本地文档库的搜索引擎自动排序算法

随着公司规模的扩大，公司积累了大量文档和业务数据，这些资源分散在公司的各种应用程序和服务器上，无法有效使用。另一方面，员工无法通过有效手段获取必要的资源。另一方面，大量资源处于闲置状态，无法有效使用。公司搜索引擎的出现改变了这种情况。通过整合公司内部不同的资源，公司搜索为公司内部提供了一个标准化的信息搜索接口，提高了公司资源的使用水平。企业搜索引擎作为一种特殊的企业内部的搜索服务,带有鲜明的业务特性.与互联网搜索引擎相比,企业搜索引擎具有许多特性.首先,互联网的搜索内容对于用户来说都是未知的,而企业级的搜索对象已知.在对这些信息进行索引时,用户需要按照内容而不是通过分析网页之间的链接关系进行排列.其次,与互联网搜索引擎相比,企业搜索引擎要求具有严格的安全性和高可靠性.针对企业网中不同的用户对不同的资源,其使用权限都可能不一样,需要企业搜索引擎能够对用户、资源、权限分级管理和控制,确保系统的安全.最后,与互联网搜索引擎服务不同,企业内部的搜索结果将直接参与到企业的运行和决策过程中,而前者仅提供信息参考的角色.所以,对于搜索的结果处理,搜索过程中采用相关智能技术以达到准确定位目标信息非常重要.本文拟将个性化技术引入企业搜索引擎中,根据用户对不同信息关注程度的不同,使用户关注度较高的结果排在结果列表的前面,关注度较低的结果排在后面,从而提高企业搜索引擎查询结果的准确性.本文提出了一种基于本地文档库的个性化检索算法,该算法由3部分构成:个性化表示、更新与结果排序算法.首先,与传统基于内容的个性化检索算法广泛采用的通过关键词向量表示用户个性的方法不同,本文采用本地文档库的方式表示用户个性.基于关键词向量的表示方法通过对用户浏览的历史文档的分析,提取若干关键词构成关键词向量,并对关键词赋予不同权值,以权值的大小体现用户个性.基于本地文档集的方法首先将用户浏览的历史文档分类,并评定用户对不同分类的喜好程度.本地文档库由从各分类中抽取的文档构成,用户越喜好的分类,在本地文档库中所占的文档数越多.本地文档库通过属于各分类文档数的多少体现用户个性.其次,个性化更新算法.由于传统基于内容的个性化检索算法采用关键词权值的方法度量用户个性,而用户短期的浏览历史对关键词权值的改变影响微小,因此传统基于内容的个性化检索算法很难对用户近期的兴趣转移作出快速反映.本文提出的基于本地文档集的个性化表示方法采用模糊推理技术,可以迅速捕捉用户近期的兴趣转移,只需要对本地文档库中的文档进行简单的增加或删除,即可体现用户个性的转移.最后,本文提出的结果排序算法通过将企业搜索引擎的查询结果与本地文档库中的文档进行相似性比较,对结果重新排序,体现用户的个性.综上所述,本文的主要贡献是提出了基于本地文档库的个性化表示方法,并给出基于此方法的个性化排序算法.与传统基于内容的个性化检索算法相比,本文提出的算法能够对用户兴趣的转移作出快速反映,并给出更能体现用户个性的查询结果.1协作过滤算法目前存在着许多个性化服务系统,文献对这些系统的优缺点进行了比较和总结.这些个性化算法主要分为3类:基于规则的个性化检索算法、基于内容的个性化检索算法和协作过滤算法.基于规则的系统利用预定义的规则对信息进行过滤.其优点是简单、直接,缺点是规则质量很难保证.基于内容的个性化系统利用资源和用户兴趣的相似性来过滤信息.其关键问题是用户的个性化表示方法和相似性计算.其优点是简单、有效,缺点是难以区分资源内容的品质和风格,且不能为用户发现新的感兴趣的资源.协作过滤系统利用用户之间的相似性来检索信息,它能够为用户发现新的感兴趣的内容.其关键问题是对兴趣相似的用户聚类.其缺点是需要用户的参与,且容易暴露用户的隐私.2形成分类根据的个性化排序本文拟根据用户偏好,从用户浏览的历史文档中抽取一部分典型文档,构成一个小型文档库.以此文档库描述用户个性,并对通用企业搜索引擎返回的检索结果进行个性化排序.由于这个小型文档库保存在本地,故又称为本地文档库.首先对用户浏览的历史文档进行聚类,通过对所形成的每一类文档集的属性进行模糊推理,得到用户偏好.根据用户对各分类喜好程度的不同,分配从不同分类抽取的文档数量.上述构建过程需要解决3个问题:1)对于某个分类,需要确定反映用户偏好的属性;2)需要根据这些属性计算用户对某个分类的喜好程度;3)需要根据用户对不同分类的喜好程度确定从该分类抽取的文档数.下面将分别解决上述3个问题.2.1di的属性本文采用通过对用户历史浏览文档的分析,发现用户的个性化需求.具体地,设t1表示过去的某个时间点,将从t1到聚类算法运行的时间点t2为止用户所浏览的所有文档构成的集合记为D,称文档集D为用户浏览的历史文档集,称时间段(t2-t1)为用户的浏览历史.目前有很多成熟的文档聚类工具(如WEKA等),因此可以利用这些工具对文档集D进行聚类分析.设经过聚类分析后,文档集D被划分为n个互不相交的分类,分别用D1,D2,…,Dn,表示,且D=D1∪D2∪…∪Dn.设第i个分类Di由m篇文档构成,记为Di={di1,di2,…,dim}.可以根据Di的属性了解用户对第i个分类的喜好程度.本文主要利用Di的两个属性描述用户对该分类的喜好程度.第1个属性称为“文档数”,表示第i个分类所包含的文档个数|Di|;第2个属性称为“冷却时间”.分类Dt的冷却时间的计算方法如式(1)所示:设文档dij最后一次被用户访问的时间为tij,则t2-tij表示分类Di的第j个文档最后一次被用户访问的时间与时间点t2的时间间隔,式(1)定义的冷却时间表示第i个分类所有文档被用户最后一次访问的时间距时间点t2的平均时间间隔.用户对某个分类的喜好程度可以按照如下的启发式判定:若用户访问属于某个分类的文档数量越多,且用户对这些文档访问的时间都是最近发生的,则说明用户越喜欢该分类.我们用分类的文档数属性描述用户浏览该分类文档的数量,用分类的冷却时间属性度量用户访问该分类文档与当前时间的间隔.据此,上述启发式等价于如下规则:属于某个分类的文档数越多,且该分类的冷却时间越短,用户越喜欢该分类.在构建的本地文档库中,应该包含更多从该分类中抽取的文档.除文档数和冷却时间外,还有其他属性可以用来表达用户对某分类的喜好程度,在以后的工作中将考虑更多属性,以进一步提高描述用户偏好的准确性.下面要解决的问题是如何利用第i个分类的文档数和冷却时间量化用户对该分类的喜好程度.本文拟采用基于模糊推理的技术实现.2.2模糊推理技术模糊推理技术主要采用基于模糊规则的推理方法解决问题.运用模糊推理技术解决问题分3步完成.1)模糊化.其目的是通过隶属函数将精确数据模糊化.例如,用于描述属于一个分类的文档数的模糊集共包括3个元素{多,中,少},而第i个分类的文档数|Di|是一个精确值,模糊化通过隶属函数给出这个精确值属于上述模糊集3个元素的程度.2)模糊推理.完成了对所有输入精确值的模糊化后,就可以利用模糊规则进行推理.例如某条模糊规则是“若分类所包含的文档数多且分类的冷却时间短,则用户喜好该分类”.利用第1步计算的结果,及上述模糊规则即可计算出用户对该分类的“喜好程度”.3)去模糊化.模糊推理得到的结论也是模糊的,去模糊化将其转换为精确数据用于以后的计算.例如,在本文中需要将用户对各个分类的喜好程度转换某个具体数值,为确定从各分类中抽取的文档数作准备.下面将详细介绍将模糊推理技术应用于确定用户偏好的3个步骤.2.2.1分类冷却时间的归一化第2.1节为分类确定了两个反映用户个性的属性——文档数和冷却时间.与这两个属性对应的模糊集是:与文档数对应的模糊集是{多,中,少},与冷却时间对应的模糊集是{短,中,长}.给定一个精确的文档数或冷却时间,需要一个隶属函数对其进行模糊化.隶属函数用于描述一个精确值隶属于模糊集中某个元素的程度.对上述两个属性,本文均采用如图1所示的隶属函数.该函数的横轴表示待模糊化的精确值,纵轴表示精确值属于模糊集中某元素的程度.图1所示的隶属函数的横轴范围为,故需要对每个分类的文档数和冷却时间进行归一化处理.分类冷却时间的归一化方法见式(2),其中n表示分类个数.将式(2)中的改变为|Di|即为分类文档数的归一化公式.图1所示的隶属函数横轴上(0.25,0.45)和(0.65,0.85)两个区域值得注意.根据隶属函数的定义,如果某分类的文档数或冷却时间经过归一化处理后未落入这两个范围内,则这个精确值只属于一个模糊元素;否则,该精确值同时属于两个模糊元素,精确值所对应的纵坐标表示此精确值属于某个模糊元素的程度.2.2.2模糊推理的应用本文的推理规则利用模糊元素推理用户对各分类的喜好程度,而推理规则主要由相关领域专家制定.利用分类的文档数和冷却时间定义用户对分类喜好程度的模糊规则定义如表1所示.用于描述用户对某分类喜好程度的模糊集定义为{很喜欢,较喜欢,一般,较没兴趣,没兴趣},分别对应表1中的5,4,3,2,1.表1共给出了9条模糊规则,采用“&”运算表示模糊规则被触发的条件.例如,若某分类的文档数多(对应表1中的Many)&冷却时间短(对应表1中的short),则用户“很喜欢”该分类(表1中Many和short交叉处的数字为5).下面通过一个例子讲解模糊推理的过程.假设经过归一化处理后,若第i个分类Di的文档数为0.3,根据图1所示的隶属函数可以计算出分类Di的文档数属于“少”的程度为0.75,属于“中”的程度为0.25,属于“多”的程度为0.分类Di的冷却时间数为0.5,表明该类文档的冷却时间属于“中”的程度为1,属于其他两种情况的程度为0.利用隶属程度和9条模糊推理规则可以计算出用户对分类Di的偏好程度.具体方法是:对规则“若某分类的文档数中冷却时间中,则用户喜好该分类的程度一般”,分类Di的文档数属于中的程度为0.25,其冷却时间属于中的程度为1.根据模糊推理系统对运算符“&”的定义,取文档数和冷却时间的较小值作为推理规则结论的支持度.即用户对分类Di喜好程度“一般”的支持度为0.25.采用相同方法根据其他8条规则,分别计算出用户对分类Di“较喜欢”、“喜欢”、“一般”、“较没兴趣”和“没兴趣”的支持度.2.2.3模糊元素偏好度计算去模糊化指将用户对分类Di的喜好程度转换为某个精确值,转换的方法如下:令模糊集{很喜欢,较喜欢,一般,较没兴趣,没兴趣}中各模糊元素所对应的权值为1/20,1/21,1/22,1/23和1/24.设2.2.2节计算的用户对分类Di的5种喜好支持度为S1,S2,S3,S4,S5,则用户对分类Di喜好程度去模糊化的结果由式(3)给出:2.3设计聚类分配算法设本地文档库中共包含N个文档,则可以按照用户对不同分类喜好程度的不同计算分配给该分类的抽样文档个数.设聚类算法将用有户浏览的历史文档集聚集为n个分类,利用式(3)计算出用户对每个分类的喜好程度,则从第i个分类Di中抽取的文档数由式(4)给出:最后,将剩余的个文档名额平均分配给用户最喜好的个分类.3本地医疗设计及本地医疗库构建算法确定了每个分类的抽样文档数后,需要选择抽取文档的方法,本文提出3种文档抽取方法.1)随机抽样.设第i个分类Di中包含的文档数为|Di|,为每个文档分配1个[1,|Di|]范围内的自然数作为该文档的ID.若要从该分类中抽取个文档数,只需在[1,|Di|]范围内产生个互不相同的随机数,ID与随机数对应的文档即为被抽样的文档.2)中心抽样.设第i个分类Di的聚类中心向量为Vi,将分类Di中的所有文档向量与V,进行相似性比较,选择其中与Vi最相似的个文档作为抽样文档.3)覆盖抽样.设分类Di的聚类中心向量为Vi,该向量共包含W个关键词.分类中的第j篇文档的文档向量包含Wj个关键词.从分类Di中最多选择个文档,使这些文档对应的文档向量所包含的关键词构成的集合最大限度地覆盖W.分别对聚类算法形成的各分类进行抽样,将抽样文档合并在一起就得到本地文档库.定期运行本地文档库构建算法即可完成对本地数据库的更新,反映用户最新的个性偏好.完整的本地文档库构建算法如下所示:算法1.本地文档集建立算法.4本地医疗知识数据库的应用本地运行的个性化结果排序算法如下所示:算法2.基于本地文档集的结果排序算法.算法首先将从用户处接收的查询词发往企业搜索引擎查询.企业搜索引擎将查询结果集的每一篇文档转换为关键词向量并返回客户端.客户端利用本地文档库对企业搜索引擎返回的结果进行重新排序,具体计算方法如下:取出企业搜索引擎返回的一篇文档的关键词向量,计算这篇文档与本地文档库中所有文档关键词向量的相似度,将所有相似度结果累加就得到这篇文档的排序值.显然,若一篇文档与本地文档集中相似的文档个数越多,相似度越大,则这篇文档排序值就越大.因为在选择构成本地文档库的过程中,是根据用户对不同分类喜好程度的不同对各分类进行文档数分配的.可以保证用户偏好在对结果排序值的计算过程中得到体现.5实验1:本地城市远程高效资源库下面通过3组实验验证本文提出的基于本地文档集的个性化表示和结果排序算法可以体现出用户的个性偏好.实验的设置如下:我们采用由1778篇新闻组文档构成的文档集作为测试集,并通过聚类算法将这些文档分为3个分类.文档集全集构成远程文档库,从属于不同分类的文档集中抽取一定数量的文档构成的集合表示用户在本地浏览了远程文档库中相关分类的文档.为了度量个性化排序算法的性能,本文采用统计各分类在查询结果集排名前50个结果中所占的比例作为度量标准.Solr作为一款开源的搜索引擎核心被广泛运用,它可以给出未经过个性化处理的搜索结果.本文采用Solr作为基准,与本文提出的个性化算法的处理结果进行比较,从而体现出用户个性对结果的影响.实验的具体内容如下:首先,本文共提出了3种抽样方法:实验1(见5.1节)通过改变用户浏览某分类的文档数和分类的冷却时间,寻找一种最好的抽样方法;其次,实验2(见5.2节)采用实验1所选的抽样方法构建本地文档库,考察本地文档库所包含的文档数对本文提出的个性化排序算法的影响;最后,实验3(见5.3节)将本文提出的个性化排序算法与传统基于关键词权值的个性化排序算法进行比较,说明本文提出的算法可以对用户个性的变化作出更迅速的反应,并更突出用户的个性.5.13种抽样方法的实验结果比较本实验通过在4种不同的用户浏览各分类文档数和各分类冷却时间设置条件下,比较3种抽样方法的优劣.实验的所有数据均是向搜索引擎发送5个查询词所得实验结果的平均值.各实验的参数设置如下:在所有子实验中均固定本地文档库所包含的文档数为200.在子实验1中,设置用户浏览3个分类的文档数之比为1:0.6:0.2,浏览3个分类的冷却时间之比为1:0.6:0.2,实验结果如图2(a)所示.显然,文档数的比值越高说明用户浏览该分类的文档数越多,而冷却时间的比值越高,说明用户越久没有访问该分类中的文档.因此子实验1中模拟的场景是在很久以前用户关心分类1,但随着时间的推移,用户最近的兴趣正转向分类3.根据图2(a)所示的实验结果,“Solr”表示没有经过个性化算法处理的排序结果,“随机抽样”、“中心抽样”和“覆盖抽样”分别表示本地文档集采用随机抽样、抽取与各分类中心距离最近的文档以及覆盖分类中心向量的方式构成.图2(a)中,按3种抽样方法形成的本地文档库对结果排序后,3种抽样方法使第1个分类在前50个结果中所占比例较Solr都有所下降,而对第3个分类,3种抽样方法较Solr的都有所增加.说明个性化排序算法检查到了用户个性的转移,尽管当前用户浏览第3个分类中的文档数还比较小,但也可以适当增加属于第3个分类的文档在前50个结果中所占的比例.在这组实验中,覆盖抽样表现最好,即分类1下降最多,分类3增加最多.子实验2的参数设置为:3个分类文档数之比为1:0.6:0.2,冷却时间之比为1:1:1.该实验中各分类的冷却时间相同,因此通过文档数体现用户个性.显然,分类1的文档数最多,表明用户最关心分类1.实验结果如图2(b)所示,对分类1在结果集所占的比例,3种抽样的个性化方法较Solr均有不同程度的提高,而对于分类3,3种抽样方法较Solr均有所抑制,正确反映了用户偏好的变化.进一步,中心抽样方法较其他两种方法表现得更好.子实验3的参数设置为:3个分类文档数之比为1:0.6:0.2,冷却时间之比为0.2:0.6:1.由此可见,用户浏览分类1的文档数最多,且冷却时间最短,因此对分类1非常关注,而对分类3则完全相反.图2(c)的实验结果也验证了这一点,基于抽样的3种方法在前50个结果中对属于分类1的文档数较Solr均有更大幅度的增加,对分类3则刚好相反.同样是中心抽样方法表现最好.子实验4的参数设置为:3个分类文档数之比为1:1:1,冷却时间之比为1:0.6:0.2.在文档数相同的条件下,冷却时间越短说明用户越关心某类文档.因此用户最关心分类3,图2(d)的实验结果验证了这一点,对属于分类3的文档在前50个结果的比例,抽样方法较Solr均有明显的增加,仍然是中心抽样方法增加最明显.综合上述4个实验,中心抽样方法是3种抽样方法中效果最好的一种.5.2dn:400和dn的分类结果根据5.1节得到的结果,3种抽样方法中,中心抽样方法的效果最好,因此本实验采用中心抽样方法,测试本地文档库所包含的文档数对本文提出的个性化排序算法的影响.具体地,测试本地文档库包含的文档数(documentnumber,DN)分别为200和400两种情况下,基于中心抽样的个性化排序算法反应用户个性变化的及时性.本实验共包括4个子实验,实验结果如图3所示.各实验的参数设置如下:在子实验1中,设置用户浏览3个分类的文档数之比为1:0.6:0.2,浏览3个分类的冷却时间之比为1:0.6:0.2,实验结果如图3(a),所示.子实验1中模拟的场景是在很久以前用户关心分类1,但随着时间的推移,用户最近的兴趣正转向分类3.根据图3(a)所示的实验结果,“Solr”表示没有经过个性化算法处理的排序结果,DN=200和DN=400分别表示本地文档集包含的文档数为200和400且经过个性化算法处理的排序结果.经中心抽样方法对结果排序后,分类1在前50个结果中的比例较Solr的排序结果都有所下降,而对第3个分类,DN=200和DN=400较Solr的都有所增加.通过比较DN=200和DN=400减小和增加的幅度可知,在这组实验中,DN=400比较DN=200更能反映用户个性的变化.子实验2的参数设置为:3个分类文档数之比为1:0.6:0.2,冷却时间之比为1:1:1.分类1的文档数最多,表明用户最关心分类1,实验结果如图3(b)所示.对分类1在结果集所占的比例,DN=400所增加的比例较DN=200高,而对于分类3,DN=400较DN=200有更强的抑制作用,因此子实验2说明DN=400表现得更好.子实验3的参数设置为:3个分类文数之比为1:0.6:0.2,冷却时间之比为0.2:0.6:1.说明用户对分类1非常关注,而对分类3则完全相反.图3(c)的的实验结果同样说明DN=400时的表现要好于DN=200的情况,其解释同子实验1和实验2,在此不再赘述.子实验4的参数设置为:3个分类文档数之比为1:1:1,冷却时间之比为1:0.6:0.2.说明用户最关心分类3,图3(d)的实验结果说明DN=400时的表现更好.综合以上4个实验的结果可知,适当增加本地文档集所包含的文档数可以更好地体现用户偏好.5.3实验结果与分析本实验将基于本地文档集的个性化排序算法和基于关键词的个性化排序算法进行对比.基于关键词的个性化排序算法的主要思想是从用户浏览的历史文档中提取关键词.通过对用户浏览文档的分析,赋予这些关键词不同的权值,以体现不同关键词代表用户个性的强度,将查询结果集中的代表各文档的关键词向量与该关键词向量进行相似性比较,根据相似度的高低确定其在新结果集中的排序.本实验共包括2个子实验.子实验1将测试文档集聚集为3个分类,实验结果如图4所示,根据5.1和5.2节所得到的结果,本文提出的基于本地文档集的个性化排序算法所设定的参数为采用中心抽样方法构建本地文档集,且文档集中包含的文档数为400.图4中的Document-Based-1表示本文提出算法在用户浏览3个分类的文档数之比为1:0.6:0.2,浏览3个分类的冷却时间之比为0.2:0.6:1条件下的实验结果.图4中的Document-Based-2表示本文提出算法在用户浏览3个分类的文档数之比为1:0.6:0.2,浏览3个分类的冷却时间之比为1:0.6:0.2条件下的实验结果.图4中的KeywordBased表示传统基于关键词的个性化排序算法的实验结果.Document-Based-1的实验设置模拟用户对分类1非常关注,而对分类3则完全相反.图4的实验结果显示与基于关键词的方法相比,DocumentBased-1所得到的结果集中属于分类1的文档高于Keyword-Based方法,而属于分类3的文档数低于Keyword-Based方法.说明基于关键词的方法相比,本文提出的方法对用户感兴趣的分类在结果集中进行了增强,而对用户不感兴趣的分类在结果集中进行了消弱.Document-Based-2的实验设置模拟用户的兴趣从分类1转移到分类3.根据图4所示的实验结果,与基于