查询模型（共7篇）
查询模型 篇1
0引言
专家检索(亦称之为专家查询、专家推荐、专长定位、专长识别[1])作为实体检索的一个特例,要求返回的实体类型是具有特定专长(与查询主题相关的)的专家。由于在促进知识共享和交流、构建学术界和产业界的桥梁、知识管理等方面有重要的应用价值,近年来专家检索引起了学术界广泛兴趣。
企业搜索这一新领域的出现,给信息检索研究社群带来了新的挑战。一个典型企业内对于复杂信息需求的多样性和内联网数据的异质性使得提高总体检索质量比较困难。相反,研究者们仅仅集中于几项重要的检索任务。其中一个重要的任务就是要在一个组织内搜寻到相关的专家。这就意味着用户需要找到一名知识最渊博、学识最高深的专家来亲自解答他所查询的主题。用户只要在当地的内联网搜索引擎中输入几个关键字,就会检索到一组候选专家,并根据他们成为该主题专家的可能性进行排序。国际文本检索会议组织的企业追踪专题首创的搜寻专家任务推动了当前专家检索系统的发展。到目前为止,对语言模型方法出现的问题及可能的解决方案最全面的一种描述在文献[2]中有所介绍。本文采用了具有良好理论基础的语言建模方法,并应用不同的技术对模型进行评估和排序。
1查询扩展技术
查询扩展QE(Query Expansion)是采用计算机语言学、信息学等多种技术,将与原查询相关的词或者词组与原查询重新组合成新查询,以便更完整、更准确地描述原查询所隐含的语义或主题,帮助信息检索系统判断更多相关的文档,从而改善和提高信息检索系统的查询性能。它的核心问题是扩展词的来源及其权重的设置问题。
传统的查询扩展方法[3]主要分为基于全局分析、基于局部分析、基于用户查询日志和基于关联规则等几大类。
查询扩展方法[4]多沿袭信息检索领域查询扩展的研究成果,在查询时动态地扩展原始查询语句,使得扩展的查询语句能比原始查询语句更好地表达用户的查询意图。该技术有助于改进传统的文件检索性能,提高专家检索的准确度和覆盖面。不少工作采用常见的伪相关性反馈PRF(pseudo-relevance feedback)技术,主要是利用查询时返回的Top-N 最相关的支持文档来扩展原始查询语句。
2基于语言模型的排序方法
专家检索问题的实质是:根据用户的查询q,返回与q相关的专家并排序返回给用户。依据查询似然的思想,专家排序可以看作是:用户在检索中提出的查询表达式q是针对某个特定的专家e生成的,而检索系统观察(接受)到用户提出的查询q后,其任务是预测可能生成q的专家并将其根据可能性大小排序返回给用户,即将专家按照p(e|q)排序,模型如式(1):
对于一次确定的专家检索过程而言,查询q对每个专家e 都是确定的,因此p(q)与排序无关,则如式(2):
p(e|q)∝p(q|e)×p(e) (2)
p(e)则是每个专家的先验概率,可用来结合专家权重优先级等因素。在这里,假设p(e)是均匀分布的,即与排序无关。因此,也可以用p(q|e)对专家排序,则如式(3):
p(e|q)∝p(q|e) (3)
在TREC 2005中,Cao等[5]和Azzopardi等[6]介绍了两种用于专家检索任务的语言模型。它们被Balog等[2]解释为候选专家模型(模型1)和文档模型(模型2)。这是目前较常用的专家检索模型框架,它们为基于此的扩展和新方法的产生提供了理论基础。
2.1专家语言模型(模型1)
模型1基于的是Craswell等[7]提出的虚拟文档方法,Fang等[8]将该模型称之为基于专家档案的模型,Petkova和Croft则将其称之为查询独立法[9]。
该模型的主要思路为:根据每个专家e,估算一个专家语言模型,利用p(q|θe),计算专家θe产生q的概率,如式(4):
通常情况下,查询q是通过一系列词来表示的,tf(ti,q)表示出现在查询q中的词频。该公式假设各个词ti从θe中发生的事件是相互独立的。p(ti|θe)表示的是候选专家e写某种东西的概率。若一个候选专家对某方面谈论得越多,则他(她)越有可能是这方面的专家。给定候选专家e,生成查询q类似于询问该专家是否有可能写了与查询主题相关的东西。关于p(t|θe),可以认为θe是由与专家e主题相关的索引词分布模型和背景语言模型p(t|C)的插值,如式(5):
2.2文档语言模型(模型2)
该模型假定候选专家与查询之间是相互独立的。该模型将查询的生成过程看成如下两个步骤:选择与候选专家e相关的文档di;在di中,用户针对文档中专家的相关信息提出查询q。于是查询q的生成过程被划分到各个文档di中去,如式(6):
该思想可以表达为:查询q是针对每个文档生成的。在该模型中,p(di|e)的计算与模型1是相同的。而p(q|di,e)的计算可以简化为p(q|di),相对于模型1,模型2的优点在于可以对查询词之间的依存进行建模,而模型1由于首先引入索引词之间的独立假设,因此无法对索引词之间的依存性进行考察。而模型2保留了完整的查询q和每个文档di,从而可以利用各种文本检索中考察查询索引词依存的方法。
3基于查询模型的排序方法
查询建模方法中出现的大量特殊查询扩展和语言模型利用Top-N最相关的支持文档进行操作。本文运用掌握的运算法则建立一个集伪相关性反馈和查询扩展功能为一体的查询式模型。
基于查询模型的专家检索方法可以分为两步,第一步和第2节中模型1的方法相似,而第二步包含实际上的优化改进过程,也就是本文讨论的核心内容。
3.1步骤一:运用语言模型进行专家排序
语言建模的基本观点是评估每个专家有关文档的语言模型,然后根据评估的查询式模型和专家语言模型的交叉熵对专家候选人进行排序。在本文的程序设置中,集合中每个支持文档d都和专家候选人ca有关联,这种关联性可以表示为(d,ca)。信息检索中根据可能性排序原则存在的专家检索问题可以表述为:“专家候选人ca在给定查询式q范围内成为专家的概率是多少?”每位专家候选人ca用专业术语的多项概率分布p(t︱ca)来表示。专家语言模型θca被看作是对术语生成概率的最大似然规则的概率评估,通常应用语言模型语料的数据平滑技术。查询式q同样也由概率分布p(t︱ca)来表示,且查询式语言模型被表示为θq。因此,系统的输出应该包含语言模型θq 和 θca的交叉熵之间专家候选人的降序排列。关于专家模型的查询式交叉熵的表示方法如式(7):
步骤一的结果是使获得最高分数的Top-N专家退回到系统(而不是用户),这一过程中N是根据经验设定的。步骤二包含了对专家检索的优化过程。
3.2步骤二:运用查询模型对专家排序进行优化
为了更准确地对用户的查询主题建模,需要一个信息源来对该用户的信息需求进行更多了解。传统上的信息检索将查询式Top-N支持文档作为信息源,并用于建立广泛、详细的查询式模型。专家检索是与标准的文档检索截然不同的一项任务。用户搜寻的不是某些具体的信息,而是这些信息的实际发出者和(或者)收集者。这就意味着除了查询主题需要非常具体外,候选专家也要有与该主题相关的专业知识。此外,专家们的专业领域越广泛,对于某个比较专业的问题,他们被咨询的概率就越大。因此,在专家检索任务中需要利用两个用户信息需求的证据:
1) 在整个文档集合中检索的Top-N支持文档(运用经典的LM方法进行文档检索);
2) 与查询主题相关联的Top-N专家候选人(在步骤一中进行检索)。
第一个信息源让检索者对初始用户信息需求有了详细的了解,而第二个信息源相对而言不是很具体,对查询主题有所扩展。所以,作为一个新的查询式模型,本文采用两种查询式模型的混合式:基于Top-N文档的模型(表示为DocumentBasedNewθq)和基于Top-N专家的模型(表示为ExpertBasedNewθq),如式(8):
对于这两种查询式模型的评估,不是采用文献[2]中提到过的方法,而是应用文献[10]中由Zhai和Lafferty提出的原则性强、理论基础好的方法,这一方法优于本文之前信息检索分布实验中用到的其它类似的运算法则。一旦用于运算,就需要将新的查询式模型和初试模型混合以防止偏离主题。本文通过运用查询扩展和术语生成概率建立了一套新的专家排序体系。在式(9)中,用不同的新的查询式模型计算了交叉熵。
4实验结果与分析
4.1测试集的选择
如何获得实用数据集用于研究测试是专家检索的一个重要挑战,目前所使用的标准测试集大多是从组织内部网收集而来,它们各具优缺点。本文采用W3C数据集作为测试集,它是TREC企业追踪专题所采用的标准测试集,主要用于企业专家检索场景。TREC 2005和TREC 2006使用的专家检索数据集是在2004年6月从W3C(Wide Web Consortium)的公开网站(*.w3c.org)上抓取的,其数据集的详细信息如表1所示。
此外,在这两次的专家检索任务中,W3C给参与者提供了包含1092个候选专家的列表,在候选专家列表中包括了专家的全名和邮件地址。
4.2测试结果分析
在实验中,本文利用第2节中所提到的模型2作为基线语言排序方法,对TREC的企业追踪专题提供的W3C数据集进行检索。同时,运用查询模型方法索引了W3C数据集的邮件列表,并检索专家检索任务中官方主题的标题查询式部分。图1和图2显示了基线法和本文所采用方法关于前10组结果(P@10)的准确度对比情况。
通过观察,查询式建模对于检索方法的改进很有帮助。当步骤一中的平均准确度已经很高的时候,本文的方法是有效率的,但是当平均准确度低于中间值的时候,本文的方法就不会很成功。如果初始的排序很差,那么查询式建模也就会随之变差。但是最好的查询式的准确度会提高10%-20%,因而这种方法适合应用于已经很有效率的检索系统中。因此,查询式功能方面的预测对于查询式建模是非常关键的。
但是也能看到,虽然查询结果有提高,但提高不大,这是由于候选专家的档案和支持文档中包括了候选专家其他的与查询主题不相关的专家领域,如果将这个文档作为查询扩展,则其它不相关的专长领域会影响到查询扩展的效果,从而使得最后扩展的查询主题失去了原有意思(即跑题)。跑题是将查询扩展运用到专家检索中不可避免的现象。目前有一些衡量专家档案中跑题发生的次数的方法,但还未提出一些衡量跑题是何时与如何发生的方法。总之,查询扩展在专家检索中的成功运用有助于发现相似专家,也有助于在组织中自动创建“专长路线图”。
5结语
本文通过对基于语言模型的专家检索方法的研究,提出了一种基于查询式建模的专家检索方法。该方法通过运用查询扩展技术和术语生成概率建立了一套新的专家排序体系。实验结果表明,该方法有效,能提高和改善信息检索性能。进一步研究专家检索专门的查询式建模和预测查询式性能是未来研究检索领域的主要侧重点。
参考文献
[1]Serdyukov P.Search for Expertise Going Beyond Direct Evidence[M].2009.
[2]Balog K,Azzopardi L,M de Rijke.Formal models for expert finding inenterprise corpora[C]//SIGIR’06:Proceedings of the 29th Annual In-ternational ACM SIGIR Conference on Research and Development inInformation Retrieval.Seattle,USA,ACM Press,2006:43-50.
[3]黄名选,严小卫,张师超.查询扩展技术进展与展望[J].计算机应用与软件,2007,24(11):1-4,8.
[4]武洁,王美姣,冯佳明,等.专家检索研究进展[J].计算机应用研究,2010,27(10):3633-3638.
[5]Cao Y,Liu J,Bao S,et al.Research on Expert Search at EnterpriseTrack of TREC 2005[C]//Proceedings of the 14th Text REtrievalConference(TREC 2005),2005.
[6]Azzopardi L,Balog K,M de Rijke.Language Modeling Approaches forEnterprise Tasks[C]//Proceedings of the 14th Text REtrieval Confer-ence(TREC 2005),2005.
[7]Craswell N,Hawking D,Vercoustre A M,et al.P@noptic expert:searching for experts not just for documents[C]//Ausweb Poster Pro-ceedings,Queensland,Australia,2001.
[8]Fang H,Zhai C.Probabilistic Models for Expert Finding[C]//Pro-ceedings of the 29th annual European Conference on Information Re-trieval Research(ECIR’07),Rome,Italy,2007:418-430.
[9]Petkova D,Croft W B.Hierarchical language models for expert findingin enterprise corpora[J].International Journal of Artificial IntelligenceTools,2008,17(1).
[10]Zhai C,Lafferty J D.Model-based feedback in the language modeling approach to information retrieval[C]//CIKM’01:Proceedings of the 2001ACM CIKM International conference on Information and Knowl-edge Management.Atlanta,Georgia,USA,November5-10,2001:403-410.
[11]Macdonald C,Ounis I.Expertise Drift and Query Expansion in Expert Search[C]//Proceedings of the16h ACM conference on Conference on information and knowledge managemen,Lisboa,Portugal,2007:341-350.
查询模型 篇2
P2P网络是一种自组织系统, 可以为协同工作、对等计算和搜索引擎等网络应用提供较好技术支持。典型的P2P系统需要设计一个非集中式拓扑结构, 从而确定如何命名并组织系统中包含的大量节点, 以及节点的加入和离开方式、出错恢复等问题。P2P系统的分布式和强动态特性导致对等点之间的快速定位难度较大。决定一个P2P网络资源定位模型成败的关键是如何高效地发现网络中的节点, 并快速定位到所需资源。
基于DHT的全分布式结构化拓扑网络代表了P2P研究的最新方向, 较成熟的应用方案有CAN, Chord, Pastry, Tapestry和Kademlia等系统。在上述系统中, Kademlia的应用最普遍, 目前主流的P2P软件如eMule, BitTorrent, BitComet和BitSpirit等均采用它作为辅助检索协议。
1 现有技术的改进方法
1.1 基于路由表的改进
查询延迟主要是由于DHT采取多次跳转机制造成的, 因此减少跳数次数是降低查询延迟一个有效途径。通过增大路由表的容量来优化节点间的逻辑网络上的跳转次数, 可以达到减少跳转次数的目的。
1.2 基于网络拓扑的改进
P2P对等网络通常依靠一致性散列函数 (DistributedHashTable, DHT) 在应用层建立逻辑上的拓扑覆盖网络结构, 这样有利于资源定位、查询、数据存储。但是由于它没有考虑实际的底层的物理网络, 造成物理层拓扑与逻辑覆盖层拓扑不匹配, 这是查询延迟增大的一大重要原因。如果能提高物理拓扑与逻辑拓扑之间的匹配程度, 将能够有地效地降低查询延迟, 提高系统的查询性能。
1.3 基于网络分层的改进
在P2P系统中所有的节点对等的参与资源的发布和共享, 这就导致一些性能较低的节点成为整个系统瓶颈。针对这一问题, 一种具有分层结构的P2P文件定位系统被提出, 系统构建了一个二级覆盖网络, 这个二级覆盖网络能够充分考虑节点性能差异, 只有高性能节点才能参与系统大范围的查询搜索。
2 Kademlia模型原理及其存在的问题
2.1 Kademlia模型
Kademlia网络中的每个节点均拥有一个专属ID, 由节点随机生成。ID取值与SHA1散列值类似, 2个节点之间的距离定义为两者ID值的异或运算结果。根据条目的Key值, 该条目将被复制并存放在节点ID距离Key值最近的k个节点上。k是一个估计值, 决定其取值的准则如下:在当前规模的网络中任意选择至少k个节点, 使它们在任意时刻同时不在线的几率接近0。每个节点负责维护160个列表, 即k-bucket, 如图1所示。第i个列表记录当前节点已知的、与自身距离为2i～2i+1的节点的网络信息, 即 (Node ID, IP地址, UDP端口) , 每个列表中最多存放k个节点信息。
2.2 基于Kademlia的P2P网络资源定位模型存在的问题
基于Kademlia的P2P模型存在一个严重的问题:Kademlia依靠一致性散列函数在应用层建立逻辑上的拓扑覆盖网络, 这有利于其定位、查询、数据存储与复制。由于它不考虑实际的底层的物理网络, 造成了物理层的拓扑与逻辑覆盖层的拓扑不匹配, 这是使得查询延迟增大。
一个简单的例子来描述这种不匹配, 在一个Kademlia空间, 逻辑层拓扑和底层物理层拓扑如图2所示。
在逻辑拓扑空间中, 节点A要查询节点E, 按照Kademlia的算法通过连接B、C、D 3个节点和逻辑上的4次跳转成功定位节点E, 这个查找效率是非常高的。然而, 在底层的物理拓扑空间里, 虽然节点A和节点E在物理层上比较接近, 网络延时也很短, 但Kademlia系统由于逻辑层的引导, 需要先找到逻辑距离距节点E更近的节点B, 再依此由节点B找到节点C、节点D后才能定位节点E, 整个查询的网络延时To=Tab+Tbc+Tcd+Tde, 从图2中可以看出, 节点A节点B有多条路径, 最短路径为A-F-E-H-B, 即Tab=69s。同理可得Tbc=60s;Tcd=50s;Tde=62s, 由此可知, 整个查询的网络延时To=69+60+50+62=251s, 远大于节点A-E直接连接的23s, 而且定位过程多次跨越广域网, 对网络消耗巨大。因此, 若能提高物理拓扑与逻辑拓扑之间的匹配程度, 将能有效地降低查询延迟, 提高Kademlia系统的查询性能。
3 基于洪泛与DHT结合的NKademlia模型
NKademlia模型的主要思想是:在利用原Kademlia模型查询之前, 先利用洪泛式查找方式对周围邻居节点的信息进行查询, 比较返回的节点与目标节点的逻辑距离, 如果查询不成功则再次向距离目标节点逻辑距离最近的节点发出同样的查询信息, 依此反复, 直到查询到离目标节点最近的节点为止, 具体方法如下:
3.1 邻居节点的建立
很多策略在进行邻居节点划分时都采用了Landmark方法。这种方法也需要选择组首节点, 使得系统规模受到限制。为了达到不影响系统可扩展性的目的, 对于邻居节点的划分采用了更为简单的利用底层搜索机制发现邻居节点的方法。
邻居节点的建立分为以下几步: (1) 当节点加入系统时根据网络的规模选择一个合适的TTL值发出Ping命令, 主动探测与自己最接近的节点; (2) 收到该消息的节点返回应答消息。应答消息应该包含新节点与目标节点之间的网络延时和目标节点IP; (3) 新节点将收到的邻居节点分类, 大于某一临界值值的直接放弃, 小于的加入自己的k-bucket, 并加以标记; (4) 新节点给邻居节点发送消息, 使得该节点也将新节点加为邻居节点。
3.2 记录列表
研究表明, 在目前P2P网络的搜索中, 有50%以上的搜索的内容是一些网络热门资源, 因此存在着很多重复查询, 为了避免重复查询对网络资源的消耗, 特引入记录列表。
每个节点增加记录列表, 储存本节点和邻居节点查询成功的记录, 方便其它节点再次查找相同的信息。
记录列表存放在k-bucket的列队头, 即K[0]处, 逻辑距离自身距离为20=1, 如果逻辑距离自身距离为1的节点存在, 则加到此列表的队尾。
记录列表的形式与k-bucket一致, 内容为自身和周围邻居节点查询成功的对端节点的网络信息 (Node ID, IP地址, UDP端口) , 方便二次查询和热门资源的索引。
记录列表的结构如图3所示。
3.3 NKademlia的k-bucket
NKademlia的k-bucket如图4所示。
NKademlia的k-bucket主要有两个方面的变化: (1) 列表头原本为距离源节点距离为1的目标节点, 现在替换为记录节点; (2) 对端节点的网络信息由原先的 (Node ID, IP地址, UDP端口) 改变为 (标识, Node ID, IP地址, UDP端口) , 其中标识为该节点的状态, 分别是R表示记录节点;N表示邻居节点;NULL表示普通节点。
3.4 NKademlia的实施方法
3.4.1 节点加入
(1) 当节点加入系统时根据网络的规模选择一个合适的TTL值发出洪泛查找, 找到合适的邻居节点, 具体方法如3.1描述; (2) 在邻居节点中选择一个逻辑距离最近的目标节点, 发起针对自身ID的查询, 获取一系列普通节点, 加入自身k-bucket;
3.4.2 发起查询
(1) 当源节点A需要查询目标节点E时, A先在自身记录列表和邻居节点的记录列表中查询是否存在目标节点E, 如果存在则查询成功, 否则A在自身k-bucket和邻居节点的k-bucket中查询是否存在目标节点E或者与目标节点距离较近的节点, 并将每个邻居节点距离目标节点E最近的节点信息发给节点A, A收到这些节点信息后将这些返回节点中距离目标节点E最近的节点再次发送查询请求; (2) 收到的节点重复步骤 (1) 、直到无法找到更接近节点E的节点为止, 如果最后返回的节点是节点E或者是节点E周围存放着节点E的信息的节点, 则查询成功; (3) 查询成功后将查询结果加入节点A和节点A邻居的记录列表, 查询结束。
3.5 NKademlia改进结果
NKademlia改变了Kademlia单向跳转的形式, 利用邻居节点进行多向跳转。邻居节点虽然在物理距离上和源节点很近, 但逻辑距离可能很远, 更可能分部在DHT空间的各个位置, 因此在这些节点的k-bucket中查询目标节点成功的概率比单在自身k-bucket中查找到目标节点要高的多。加上记录列表的加入, 在热门资源的查找上效率有了进一步提高。
在图3的拓扑图中, 节点A利用Kademlia模型进行了4次跳转找到节点E。NKademlia模型的逻辑拓扑图如图5所示, 在第一次查询中, 节点A在自身k-bucket和周围的邻居节点C、F、G的k-bucket中查找节点E的信息, 第一次查询虽然没有成功, 但在返回的信息中发现节点F是离目标节点E逻辑距离最近的节点, 于是向节点F发出查询信息, F则用同样的查询方法找到节点E并返回给节点A, 查询结束。
在此查询中, 无论是逻辑跳数和物理跳数均小于原Kademlia模型, 查询延时得到很好的改善。在上面的例子中, 使用了新的查询方法后, 查询的网络延时为Tn=T1+T2, T1=MAX[TAC, TAG, TAF]=10s, T2=TEF=15s, 因此Tn=25s, 远小于之前的251s。
4 结束语
本文提出了一种基于洪泛式与DHT相结合的新模型NKademlia, 改进后的模型先考虑节点之间的物理距离, 由于节点在邻居节点集中寻找与节点物理距离近的节点进行路由, 因此极大降低了路由延时。
参考文献
[1]孙华志, 侯洁.基于资源位置与节点反馈的P2P搜索算法[J].计算机科学, 2008 (35) .
[2]赵科军, 刘洋, 仇一鸿, 等.基于异或运算对等网模型Kademlia研究[J].山东科学, 2007 (6) .
[3]李普聪, 魏文红.基于DHT的P2P覆盖网络的研究[J].计算机工程, 2008 (4) .
[4]綦宏伟, 代亚非, 李晓明.针对访问成功率的P2P动态网络对象定位模型[J].软件学报, 2005 (5) .
[5]熊忠阳, 刘玉龙, 张玉芳, 等.基于Gnutella协议的P2P搜索改进算法[J].计算机应用研究, 2008 (1) .
[6]周继鹏, 朱良愿.基于物理网络拓扑的P2P系统模型[J].微电子学与计算机, 2006 (13) .
[7]Andrea Binzenhofer, Holger Schnabel.Improving the Performance and Robustness of Kademlia-Based Overlay Networks.
[8]SCOTT A.CROSBY, DAN S.WALLACH.An Analysis of BitTorrent's Two Kademlia-Based DHTs.
[9]BRUNO SPORI.Implementation of the Kademlia Distributed Hash Table.
查询模型 篇3
近年来, 人们的饮食日益多样化, 餐桌上的菜品也是荤素搭配, 但是有些食物是不能一起吃的, 这些食物单独进食并没有任何问题, 如果将两种或者两种以上的食物混合起来食用, 则容易出现食物中毒或营养不被吸收等情况。不同食物由于组成的成分不同, 有些食物混在一起食用会在体内产生化学反应, 生成不能被人消化吸收的沉淀, 严重的会引起疾病。因此食物不可以乱搭配, 否则轻则流失营养, 重则有生命危险。
目前国内外对于食品搭配安全的研究基本上是靠专家的经验判断, 缺少系统化和智能化的查询方法或推理方法。本体理论和技术的发展与应用为食品搭配安全查询专项研究提供了一种新的途径。目前国内外对本体在食品领域安全的研究只局限于针对食品的分析和建模, 较少对食品搭配对人们身体所造成的影响进行深入探讨, 没有对食品搭配本体做相应的推理研究。
构建一个智能的食品搭配安全查询系统, 挖掘食品搭配有可能对人身造成影响的信息, 指导人们健康的饮食生活。
2 本体及推理
本体的目标是捕获相关领域的知识, 提供对该领域知识的共同理解, 确定该领域内共同认可的词汇, 并从不同层次的形式化模式上给出这些词汇 (术语) 和词汇间相互关系的明确定义[1,2]。总的来说, 构造本体可以实现某种程度的知识共享和重用, 以及提高系统通讯、互操作、可靠性的能力。
本体推理机可用于推理和查询语义, 属于语义web实现的主要途径之一, 推理是指依据一定的规则从已有事实推出结论的过程。本体推理机主要是针对本体进行推理, 构建一个完善的领域本体是推理的基础。Jena是面向语义Web的应用开发包, 包含的内容比较全面, Jena中的推理引擎是针对具体本体语言的推理机, 针对性强。OWL (Web Ontology Language) 是W3C开发的一种网络本体语言, 用于对本体进行语义描述。其中OWL DL (Description Logic, 描述逻辑) 将可判定推理能力和较强表达能力作为首要目标[3,4,5]。
本文采用OWL语言来描述并构建食品搭配安全领域本体, 根据推理规则构建部分自定义规则, 最后使用JEna推理机对食品搭配对人身所造成的影响进行推理。
3 食品搭配安全查询模型
3.1 模型结构
查询模块要有友好简洁的查询界面, 利于人们方便使用。同时, 为了能实现严密的逻辑推理功能, 必须要有领域本体库和推理规则的支撑。食品搭配安全查询模块框架如图1所示。
具体工作流程为:查询界面接收用户的查询搭配信息, 输送到推理机, 推理机结合领域本体以及推理规则进行相关的逻辑推理, 最后得出结果, 显示到查询界面。
3.2 食品搭配安全领域本体建模
任何一个食品都包含有丰富的元素, 比如, 虾这种食品, 含大量的维生素B12, 同时富含锌、碘、硒、热量和较低的脂肪。同时, 食品搭配进食后会造成相关的元素进行化学作用, 从而产生新的元素。这些新的元素有的是人身体所需的, 有益健康, 有的则是对人身造成有害影响的。根据营养专家的建议, 食品搭配安全领域的本体可以分为以下几类:
3.2.1 源食品本体。
源食品本体定义为进食之前食品的原本状态, 以及所包含的元素。食品的种类繁多, 每一种食品还包括有更细品种的食品, 各个食品也包含有丰富的元素。这些结构和内容都是通过源食品本体来表现出来。比如, 虾这类食品, 虾属节肢动物甲壳类, 种类很多, 包括青虾、河虾、草虾、小龙虾、对虾 (南美白对虾, 南美蓝对虾) 、明虾、基围虾、琵琶虾、龙虾等。其中虾还含有热量、碳水化合物、脂肪、蛋白质、纤维素、钙等元素。对于山楂这类食品, 可以分为酸甜两种山楂。其中, 酸山楂包含糖类、蛋白质、脂肪、维生素C、胡萝卜素、淀粉、苹果酸、鞣酸等元素。
3.2.2 终食品本体。
终食品定义为食品在进入人的身体后最终所存在的状态, 包括进入人身体后所发生的化学反应后产生的最终元素。比如, 虾和山楂同时进入人的身体之后, 原先的钙和鞣酸两种元素会生成新的不溶性结合物, 这种不溶性结合物就属于终食品本体的概念。
3.2.3 影响状况本体。
影响状况本体定义为终食品在人身体内对身体所造成的影响。包括有呕吐、头晕、恶心和腹痛腹泻等不良影响, 也包括补肾壮阳, 通乳抗毒、养血固精、化瘀解毒、益气滋阳、通络止痛、开胃化痰等功效。
根据食品搭配安全领域本体的分类, 采用OWL描述语言构建领域本体相关类之间的关系。
3.3 食品搭配安全领域本体关系经验模型
食品搭配安全领域本体包括有源食品本体、终食品本体、影响状况本体, 三个子本体相互之间存在着明显的关联性。各主要本体之间的关系主要包括有:
3.3.1 生成。
主要用于描述源食品本体和终食品本体之间的关系, 说明源两种或多种食品本体混合最终会生成什么样的终食品本体。例如, 钙和鞣酸两种元素会生成新的不溶性结合物。
3.3.2 产生。
主要用于终食品本体与影响状况本体之间的关系, 说明终食品本体对人身体会造成什么样的影响状况本体。例如, 不溶性结合物会对人体产生呕吐、头晕、恶心和腹痛腹泻等影响。
3.3.3 引发。
主要用于说明影响状况本体相互之间的关系, 说明两种或多种影响状况本体同时或接连发生会引发另外一种影响状况本体。例如, 头晕和呼吸困难会引发暂时性休克影响。
3.4 推理规则
Jena囊括了针对本体的推理规则, 可以检查概念是否满足, 保证不同种类关系以及不同种类的属性不相交[6], 但是从实际运行情况来看, 通用规则是不能满足推理要求以及信息检索的基本要求的。所以要从水利工程建筑安全隐患及各个隐患特点入手, 拟定最适合使用的推理机制, 在满足相关要求的基础下, 对其进行完善。对自定义规则进行推理, 从实例关系以及属性关系等角度入手, 介绍详细的制定过程。
3.4.1 生成反继承规则
若源食品本体a是源食品本体m的子类, 源食品本体b是n的子类, 而源食品a, b搭配会生成终食品本体c, 则源食品m和n搭配也会生成终食品c。
3.4.2 产生的反继承规则
若终食品本体a是终食品本体b的子类, 而终食品本体会产生影响状况本体c, 则终食品本体b也会产生影响状况本体c。
3.4.3 引发反继承规则
若影响状况本体a和b分别是m和n的子类, 而和b会引发另外一个影响状况本体c, 则m和n也会引发c。
3.5 推理过程
本次选用的推理实现平台为netbeans, 而在开发语言方面则使用java来实现, 通过加载jena2API库文件结合自定义程序的方式来实现推理。从Reasoner Registry当中获取OWLReasoner。Reasoner Registry.get OWLReasoner, 并在其标准配置当中直接返回OWL reasoner, 在返回OWL reasoner之后, 将reasoner和其本体相互绑定, 通过reasoner来实现返回, 从本体模型当中创建Inf Model。只要完成原始数据和owl的本体模型创建, 便可以与其余的Model相同处理。创建和查询推理模型部分代码如下:
4 查询效果分析
为了验证模型的查询功能, 构建了一个小型的食品搭配安全领域本体, 其中有小型的子本体包括源食品本体、终食品本体、影响状况本体。通过输入2个食品搭配信息来检验查询效果。
4.1 查询食物搭配为:虾+柿子, 结果显示如图3所示。
4.2 查询食物搭配为:河虾+韭菜, 结果显示如图4所示。
以上实验结果说明了本查询模型系统具有挖掘食品搭配对人体所造成的各种影响的功能, 无论是积极的影响还是消极的影响, 模型系统具有合理性、智能性、有效性的特点。
5 结语
本文将本体理论应用于食品搭配领域, 分析食品领域中的概念以及概念之间的关系, 创建食品搭配领域本体模型, 并采用Jena推理引擎和自定义的规则对其进行推理, 构建基于本体推理的食品搭配安全查询模型, 挖掘食品搭配对人身所造成的影响信息。经实验结果表明, 本模型具有合理性、智能性、有效性等特点。模型不足之处在于, 对食品搭配的量没有考虑, 因为有些食物搭配产生的影响会根据量的多少而有所变化, 这将是下一步研究的方向。
参考文献
[1]付秀东.OWL+DL本体中概念相似度算法研究[D].西南交通大学, 2009.
[2]李玉华, 卢正鼎, 廖振松.基于本体的通用知识网格架构研究[J].华中科技大学学报:自然科学版, 2006, 34 (3) :21-24.
[3]朱姬凤马宗民吕艳辉.OWL本体到关系数据库模式的映射[J].计算机科学, 2008, 35 (8) :165-169.
[4]田飞, 刘鲁.基于语义推理的DSS模型研究与应用[J].计算机工程与应用, 2009, 45 (17) :11-15.
[5]李宏伟, 蔡畅, 李勤超.基于Jena和地理本体的空间查询与推理研究[J].测绘工程, 2009, 18 (5) :5-9.
查询模型 篇4
空间查询优化是提高空间查询的效率的主要措施之一,是空间数据库研究领域的一个主要方向[3]。代价估算通过估算执行计划的代价来选出一个最优计划以指导查询的执行,从而优化空间查询。早期的空间代价估算研究以数据集上建立的索引为基础。但在实际情况中,空间查询所访问的数据集上往往没有建立足够的索引(例如作为查询所得中间结果的数据集),因此,直方图作为一种适用于数据集上不存在索引的代价估算方法引起了研究者关注。
针对空间选择和空间连接这两种常用的查询操作,研究者已提出了多种直方图以及基于这些直方图的代价估算方法[3]。其中,研究者在欧拉直方图上做了较深入的代价估算研究[1,2,3,4,5]。这些文献所使用的统计方法存在着边界问题。文[1]提出闭欧拉直方图统计方法以修正这一错误。
以上研究多数用MBR来近似描述空间对象。在使用近似度更高的描述形式表示空间对象的基础上,建立相应的代价模型,从而提高代价估算的准确度,这对优化整个空间查询的执行过程具有重要的意义。从现有资料来看,在这方面的研究成果并不多见。在使用多边形近似描述查询窗口和空间对象的情况下,文[4]提出了SQ直方图来估算空间选择的代价,但其准确度易受空间数据分布特征的影响。
无论空间数据是否均匀分布,文[1,2]证明了闭欧拉直方图都能较精确地估算基于MBR和SCP(简单凸多边形)近似描述的空间选择代价。改进统计方法,闭欧拉直方图可有效统计基于简单多边形描述的查询代价,并且此代价模型可以用于计算空间关系查询的代价,由此进一步拓展了闭欧拉直方图的使用范围。
1 基于SP描述的闭欧拉直方图
我们约定:将空间对象分布的二维空间称为数据空间;在本文以下讨论中,若无明确说明,用SP(Simple Polygons,简单多边形)近似描述二维空间对象;查询窗口为一矩形,其边界与坐标轴平行。本文将数据空间中与查询窗口相交的空间对象的数目称为空间选择查询代价。
造闭欧拉直方图方法如下[1]:分别用一组水平线和一组垂直线将查询窗口划分为M*N个单元格,然后在每个单元格的内部(cell)、边界(edge)以及顶点(point)分!建立桶(依次称为2维桶、1维桶、0维桶);根据闭欧拉直方图计数方法[1]对每一个空间对象进行计数,计数值存放在相应的桶中。这些水平线和垂直线称为分割线。闭欧拉直方图的例子如图1所示。
在构造了闭欧拉直方图后,对其中各维桶内的计数值使用欧拉公式[7],就能估算空间选择代价。由此,我们先讨论各维桶内的计数方法。
首先,我们引入文[6]的有关概念:
定义11将多边形各顶点依次按逆时针方向排列,顶点Vi处的角度约定为内角,即由后邻边ViVi+1绕Vi沿多边形内侧旋转到前邻边Vi-1Vi所转过的角度值。若多边形某顶点Vi的内角度q∈(0°,180°),则该顶点是凸的,称为凸顶点;若q∈(180°,360°),则该顶点为凹的,称为凹顶点。
定义2若构成简单多边形的所有顶点都是凸的,则称该简单多边形为凸多边形;若构成简单多边形的顶点至少存在一个凹顶点,则称该顶点为凹多边形。
目前已有多种分解凹多边形的算法。为了利于使用闭欧拉直方图进行统计,我们采用以下策略来分解数据空间D中的所有对象,并把分解凹多边形的线称为分解线[7]:
Decomposition(S)
{(1)SCPs(S)←Φ//SCP(S)为组成S所有SCP子部分(2)LNs(S)←Φ//LN(S)为用来分解S的所有分解线(3)Partition(S)}Partition(SP)//SP为需要分解的对象{}
(1)若SP为凸多边形,则SCP(S)←SCP(S)∪SP,退出;否则,进入步骤(2);
(2)过凹顶点Vi作Vi内角的角平分线Lk,Lk与SP边界的交点为以下情况中的一种:
SP的某条边内的一个点SP的一个凸顶点Vj(j≠i)SP的一个凹顶点Vj(j≠i)
(3)以Li作为分解线将SP分解为两部分SP1、SP2(SP1、SP2以Lk为共同边界、以Vi和(3)中交点之一为共同顶点),LN(S)←LN(S)∪Lk,对这两部分分别调用Partition(SP1)、Partition(SP2)。
假设被分解对象有n个凹顶点,则可以证明,Decomposition的时间复杂度为O(n)。
定理1使用Decomposition分解任意一个简单多边形,所得到的各个子部分均为凸多边形。
我们扩展基于SCP的闭欧拉直方图[2],即在每个桶内存放两个记录项:第一项为对各凸多边形进行计数所得结果;第二项为对各分解线进行计数所得结果。对各桶内的两项记录项的值分别使用欧拉公式计算得到Sel1、Sel2,即
其中,Fk1,(Q)、Fk,2(Q)分别表示所有k维桶内第一个和第二个记录项的值之和。那么所求的查询窗口的选择代价为:Selectivity(Q)=Sel1-Sel2,即:
在Composition分解策略以及每个桶内存放两个记录项的基础上,我们得到了改进的闭欧拉直方图计数方法:
SP_Statistic()
{For i=1 to n do//n个SP存储在数组S中{(1)调用Decomposition(S[i]),得到SCP(S)={S1,S2,…,Sm}、LN(S)={L1,L2,…,Lt}
(2)对SCPs(S)中的各凸多边形分别调用SCPs_Statistic进行计数,各计数值放入对应桶内的第一个记录项
(3)对LN(S)中的各分解线分别调用SCP_Statistic进行计数,各计数值放入对应桶内的第二个记录项
图1中Q的空间选择代价为:Selectivity(Q)=(-1)0*(5-0)+(-1)1*(21-3)+(-1)2*(21-6)=2
以下将证明基于SP的直方图的计数方法的正确性。首先有以下引理:
引理11当数据空间中的对象的形状为直线时,可直接用直线来描述该对象,那么基于这样的描述形式,使用SCP_Statistic方法和欧拉公式(1)估算查询窗口的选择代价所得的结果与实际值一致。
该引理的证明类似于文[2]中定理2的证明,在此我们将省略其详细的证明过程。
定理22当数据空间中仅有一个SP与查询窗口相交,使用基于SP的闭欧拉直方图和欧拉公式(2)估算空间选择代价,所得结果实际值一致。
证明:假设数据空间中仅有一个SP并令其为S,且设S与查询窗口Q相交。此外,为叙述方便,对基于SP的闭欧拉直方图,我们记Fk1,(Q,x)为k维桶中第一记录项对对象x进行计数后使用欧拉公式(1)计算得到的值、Fk,2(Q,y)为k维桶中第二记录项对对象y进行计数后使用欧拉公式(1)计算得到的值。我们将分三步进行证明:
(1)根据定理2,由Decomposition分解S得到SCP(S),SCP(S)={S1、S2、…、Sm},它们均为凸多边形。由定理1和引理1可知,对它们分别使用SCP_Statistic方法进行统计,并对这些统计值使用欧拉公式(1)计算得到Sel1,即:
(2)对S的分解线LN(S),LN(S)={L1,L2,…,Lt},对它们分别使用SCPs_Statistic方法进行统计,并对这些计数值使用欧拉公式(1)计算,由引理1可知,计算结果Sel2为:
(3)从Decomposition分解策略可知,每一次分解均是使用一分解线将某个简单多边形或其某子部分分解为两个更小的子部分。由此可知,对于简单多边形S的m个子部分和t条分解线有:t=m-1。
综合(1)、(2)的结果有:Selectivity(Q)=Sel1-Sel2=m-t=m-(m-1)=1
即查询窗口Q的空间选择代价为1,这与实际值一致,定理得证。
以上讨论的是仅有一个多边形对象和查询窗口相交的情况,当数据空间中有多个空间对象SP时基于SP的闭欧拉直方图和欧拉公式(2)进行空间选择估算同样是正确的。
2 闭欧拉直方图的应用
文[8]提出使用基于MBR描述的欧拉直方图来求分离(disjoin)、包含(contains)、交叠(overlaps)等三种空间查询的代价,在本节,我们将前述的闭欧拉直方图用于求出基于SP描述的此三类空间查询的代价。
首先我们引入以下式子[8]:
其中,nii表示其内部与查询窗口内部相交的对象数目,nei表示其外部与查询窗口内部相交的对象数目;|S|表述数据空间中的对象数目;Nd、Ncs、No分别为与查询窗口存在分离、包含、交叠关系的空间对象的数目。ib和eb分别为查询窗口内部和外部(不包含窗口边界)的直方图各维桶的计数值,在本文中,这些计数值可以通过上一节的计数方法和式(1)计算得到。
图2给出了一个计算Nd、Ncs、No的例子。图2(b)中阴影部分对应于图2(a)的查询窗口Q’的内部,将阴影部分的各维桶中的计数使用式(1)可得到nii=2。对图2(b)中虚线标注的部分对应于查询窗口Q’的外部,对其中各维桶中的计数使用式(1)可得到nei=2。由此得到,Nd=0,Ncs=0,No=2,这意味着,与查询窗口Q’相交的对象数目为2,没有对象与Q’存在分离和包含关系,与实际结果一致。
3 结论
欧拉直方图是空间查询代价估算的一种有用方法,文[1-2]指出这种计数方法存在边界问题,在MBR和SCP近似描述空间对象的基础上提出了闭欧拉直方图,并证明了其计数方法的正确性。本文使用简单多边形来近似描述空间对象,改进了闭欧拉直方图并证明其正确性,为基于欧拉直方图统计的研究和应用的深入研究奠定了理论基础。
参考文献
[1]Ping Guo,Hai-zhu Chen,Jun Yang,Liang Ge.“The Statistical Method of Closed_Euler Histogram”,Proceedings of the Third International Conference on Machine Learning and Cybernetics,Shanghai,2004,pp.1458-1463
[2]Ping Guo,Hai-zhu Chen,Jun Yang.“The Statistical Method of Closed_Euler Histogram Based on Simple Convex Polygon Approximations”,Proceedings of the6th International Progress on Wavelet Analysis and Active Media Technology,2005,pp.945-952
[3]朱焰炉,程昌秀,陈荣国,颜勋.基于直方图的空间查询选择率估计研究.计算机科学.37(12),2010,pp.125-129
[4]A.Shraf Aboulnaga,Jeffrey F.Naughton.“Accurate estimation of the cost of spatial selections”.In ICDE'00,Proceedings of the16th International Conference on Data Engineering,March2000,pp.123134
[5]Chengyu Sun,Divyakant Agrawal,and Amr El Abbadi,“Exploring spatial datasets with histograms”,Proceeding of IEEE ICDE,2002,pp.93-102
[6]Bing-fa Chen,Zhi-feng Qian,Wen-he Liao,“An Algorithm for Identifying Convexity-Concavity of A Simple Polygon”,Journal of Computer Aided Design&Computer Graphics,Vol.14,No.3,Mar.2002,pp.1-4
[7]J.M.Keil.“Polygon decomposition”.In Handbook of Computational Geometry,chapter11,pages491-518,Elsevier,1999
查询模型 篇5
1)搜索结果集庞大,用户为找到其真正感兴趣的信息,耗费大量的时间和精力。
2)不同用户在不同时期采用同样的查询关键词请求所得到的搜索结果几乎相同,对用户来说不能提供个性化的服务。
3)用户在使用搜索引擎检索时带有一定的目的性,但往往由于该用户相关领域知识的不足以及搜索引擎查询接口的局限性,导致用户不能清楚地表达其信息需求[2]。
针对传统搜索引擎不能提供面向用户的个性化服务这一缺陷,大量的专家学者开始研究查询扩展技术,并在此领域有所突破。文献[1]根据文档分析,提出局部共现的思想,利用词项与所有查询词在局部文档集合中的共现程度以及在语料集中的全局统计信息来评估扩展词的质量,选择合适的扩展词;文献[3-5]通过分析用户浏览历史,主要采用关联规则进行查询扩展;文献[6]利用HITS和Text Rank技术提取用户主题,并结合关联规则进行查询扩展;而文献[7]提出了一种基于二级向量的搜索引擎个性化服务模型SEPMBDVD(Search Engine Personalization Model Based on Double Vector Description),其实质也是利用对用户浏览的历史网页进行挖掘而得的用户兴趣模型生成与用户输入的查询关键词配对的扩展词。通过扩展词加入,使用户在利用搜索引擎检索的时候能够得到符合用户兴趣或者兴趣偏好的结果,经过实验验证该模型具有查准率高,反应速度快等优点。这种查询扩展模型依赖于用户兴趣模型,文献[7]采用的是二级向量模型,即通过一组关键词向量和扩展词向量描述用户兴趣,这种模型是基于一个全局词典对用户浏览的历史网页进行描述、聚类挖掘以后生成的。整个模型结构如图1所示。
全局词典由于词汇量过大,词汇太杂,无法体现用户的兴趣等原因,会对用户兴趣模型的生成造成较大的影响,从而影响到词扩展的效果。因此本文使用个性化词典替换全局词典,并采用查询扩展策略实现个性化服务,设计出一种基于个性化词典的搜索引擎查询扩展模型QEMBUPDSE(Query Expansion Model Based on User Personalization Dictionary for Search Engine)。该模型能够通过个性化词典优化用户兴趣模型,从而优化查询扩展词,使得用户的个性化搜索更快,更准确。
1 基于个性化词典的搜索引擎查询扩展模型
基于个性化词典的搜索引擎查询扩展模型从用户浏览历史网页描述开始就利用个性化词典的两级词典,即关键词词典和扩展词词典,形成网页的二级向量描述,接着通过数据挖掘手段更直接的生成用户兴趣的二级向量模型,最后根据用户输入的关键词进行查询扩展,如图2所示。
2.1 个性化词典的定义与实现
根据文献[10],个性化词典UPD(User Personalization Dictionary)由关键词词典(Key Dict)和扩展词词典(Ex Dict)两级构成,位于两级词典中的词分别定义为关键词和扩展词。每一级词典中包含n个(n由人为设定)由词和词权构成的二元组。关键词通常表示用户浏览兴趣,词的权值越大,表示在用户兴趣中的重要性越大。而扩展词用于描述用户在兴趣点上的兴趣偏好,从而在查询扩展时提供符合用户偏好的扩展检索词。
特定用户的UPD能够充分表达用户对信息需求的倾向性,同时对基于二级向量的用户兴趣模型提供支持,是一种符合用户兴趣的私有词典,在词典设计上主要考虑如下主要原则:
1)网页文档集合中,某词出现的频度越高,该词对用户特征的描述能力越强。
2)网页文档集合中,包含某词的网页数越多,该词对用户特征的描述能力越强。
3)对于一些网页中比较常用的,没有检索价值的词,我们称之为网页频繁词,如:评论、版权、文章等,在词典中应该被过滤掉,以免对用户的个人描述带来噪音。
基于以上设计原则,通过对传统的TF-IDF公式进行改进,得出用于计算UPD中词的权值的公式WTUPD(Weight of Term in the User Personalization Dictionary),如公式1所示:
在公式1中S为网页集合,T为词空间,W(t,S)为词t在S中的权重,tf(t,S)为词t在S中的词频,N为S包含的网页总数,nt为S中的文档出现t的数量,分母为归一化因子。在TF-IDF公式中,㏒(N/nt+0.01)为IDF因子,即“逆文本频率指数”,在WTUPD中依然沿用这个名称,IDF因子越大,表明该词在网页集合中分布越稀疏,那么该词的重要性越小,权值越小。反之,该词的IDF因子越小,表明其在网页集中分布越密集,越均匀,那么该词的重要性越大,权值越大。
考虑到词在网页集合中分布的均匀程度不同,本文认为词t在整个网页集合S中的权重与其在网页中的均匀度成正比。因此,本文引入衡量均匀度的因子对词t的权重进行修正,公式1中词t的均匀度由t在网页集合中的标准差(Standard Deviation)来衡量,如公式2所示:
在公式2中,fi表示词t在出现该词的第i张网页中出现的次数,f表示出现词t的网页集合中t出现的平均次数,这样计算得出的词t在网页集合中的标准差σ(t)表示t在网页集合中出现次数f的离散程度。σ(t)越大,f值的波动越大。反之,σ(t)越小,1/σ(t)值就越大,f值波动越小,分布越均匀。
通过WTUPD公式可以看出:词t在网页集S中的权重,与它在该网页集中的词频成正比,与它在该网页集中分布的稀疏程度和均匀程度成正比。通过WTUPD公式得到用户浏览的网页文集合中所有词的权重并排序,再根据个人浏览兴趣的广泛度选择关键词扩展词,兴趣点较集中的用户选择前1/3的词作为关键词,余下的词即为扩展词。而兴趣点较分散(核心兴趣点5个以上)的用户选择前1/2的词作为关键词,余下即为扩展词,以此形成关键词词典和扩展词词典。
最后还要清除关键词词典和扩展次词典中的频繁词,频繁词的特征是分布在网页集合中大多数文档中,且在单张网页中出现的次数往往较少(一般为1-2次)。本文采用如下的方法对这部分词进行过滤。
公式3中,采用函数filter()在词典中筛选并剔除网页频繁词,t∈W(2N/3)表示词t出现在占用户浏览的总网页集中2/3的网页中,E(tf(t,S)/n)≤2表示词t在网页中出现次数的均值不大于2。此函数除去了所有在2/3及更大比例的网页中出现且平均出现次数不大于2次的词。
经过以上公式处理,最终可以建立满足用户兴趣描述要求的个性化词典。
2.2 基于个性化词典的用户兴趣建模
最终的词扩展依赖于准确的用户兴趣模型,而个性化词典的建立将有利于用户兴趣模型快速、准确地建立,因此本文采取的用户兴趣建模方法如下:
首先,利用个性化词典将用户浏览的网页转换为特征向量,由于个性化词典包含两级词典,因此,生成的网页特征向量即为二级向量,例如某网页的特征向量表示为{[(单反,0.05327385),(摄影,0.04826857),(像素,0.03272436),(市场,0.02713352),(专业,0.02639451),……];[(镜头,0.01135712),(显示屏,0.01023895),(环境,0.09325765),(浏览,0.09031257),(效果,0.08736234)……]},分号之前是关键词向量而之后是扩展词向量。
接着,利用网页特征向量进行聚类分析,得到用户的各个兴趣子类。
最后,利用各类的网页特征向量将兴趣子类描述成为二级向量,生成用户兴趣模型。
由此可见,个性化词典使得整个用户兴趣建模过程均使用二级向量,用户兴趣模型的生成更直接和顺利,并且由于个性化词典规避了传统全局词典中的大量与用户兴趣无关的词和频繁词,使得网页特征描述更加准确,为后续的聚类分析和兴趣模型生成奠定良好的基础,并通过用户兴趣模型提供符合用户兴趣偏好的扩展词,有利于扩展词的分析比较和选取。
2.3 查询扩展策略的实现
根据文献[7]当用户向搜索引擎提交查询词时,查询扩展模型能够自动根据用户描述文件对初始查询词进行有效的扩展,为用户推荐合理的查询扩展词。这样的扩展词更能体现用户的信息检索意图,提高检索质量。那么这种查询扩展策略的实施步骤主要如下:
首先,要将用户的初始查询与用户兴趣模型中的兴趣类匹配,以掌握用户的查询意图。由于在二级向量模型中,用户兴趣类用对应的关键词向量ci={
其中,分子为向量ci与Qini各分量乘积的和,分母为向量模的乘积。本文选择与初始查询相似度最高的兴趣点C作为用户的查询意图。即:
为了尽可能的向用户提供查询扩展词,如果在关键词向量中无法找到用户的查询词,即Qini与关键词向量的相似度为0的话,那就将扩展词向量并入关键词向量中一起参与运算。
接下来,为了找到与用户查询词最相关的扩展词,需要计算词间关联度。本文参照LSI模型[7]中的方法,将一个网页文档集合表示成“词—文档”矩阵TD,如表1所示。
表1为“词—文档”矩阵TD的截取内容,顶部一行表示文档集合中所有文档的名称(编号),而左边一列中的“欧洲、足球”为用户向搜索引擎提交的初始查询词Qini,“国家队、世界杯、澳大利亚、…”为Qini所匹配兴趣类的扩展词向量中的扩展词。中间的矩阵单元TDij为对应的词Ti在文档Dj中的权值(频度)按行归一化后的结果。由于词和文档的数量都很大,而单个文档中出现的词又非常有限。因此,TD一般为高阶稀疏矩阵。
然后利用TD构造词间关系矩阵TT,并计算词间关联度,构造方法如公式(6):
其中TD’是TD的转置。所得矩阵TT中每一个单元的TTij的值所反映的是在特定环境下(特定用户的特定兴趣类)词i与词j之间的相似度。我们可以看到,每个词与它本身的相似程度为1,而在该兴趣类的任何文档中都没有同现的两个词之间的相似度为0。如表2所示。
最后,可以通过适当的方法选取扩展词帮助用户完成搜索。本文引入相对误差公式来对候选的扩展词进行合理筛选,如公式7所示:
公式7中x*表示词间关系矩阵TT中与初始查询词Qini相似度最大的候选扩展词对应的关联度,x表示其他候选扩展词与Qini的关联度。公式8中的参数δ表示x与x*的相对误差阈值,表示只要某候选扩展词与Qini的关联度与x*之间的相对误差只要小于δ,那么该候选扩展词就可以最终推荐给用户,在实际应用中δ通常取值10%,可以保留较好的扩展词,同时也减少运算时间。可以根据情况设置。这样将筛选出来的词进行按关联度从大到小的顺序排序以后,就可以推荐给用户了。由于过多的扩展词将导致搜索的返回结果减少,反而会不利于用户获取足够的信息。通常选择3个扩展词为宜,那么最终可以从已经排序的扩展词队列里面选择前3个进行推荐。当然,根据用户需求,扩展词的推荐数量可以自行设定。
3 实验与分析
3.1 评价指标SWUI
由于用户个性化词典UPD实际上几乎包含了用户所有感兴趣的词,并且从浏览历史网页里计算出的词的权值也反映了用户对这些词的感兴趣程度,因此,本文利用通过查询扩展搜索到的网页集合与用户个性化词典进行比较的方式来进行实验,评测本文提出的个性化服务模型的效果。
为了将检索到的网页集合与用户个性化词典进行比较,本文计算检索到的网页集合特征向量的中心向量,并称中心向量为用户向量UV(User Victor),然后计算UV与UPD之间的相似度(余弦函数值),通过该相似度反映网页集合与用户兴趣之间的相关程度,称该相似度为SWUI(Similarity between Webpages and User Interests)。
3.2 实验数据
本文实验基于三位用户进行,他们分别按照自己的兴趣浏览网页,然后将自己感兴趣的网页保存下来,接着对三位用户提供的兴趣网页进行兴趣建模,得到用户兴趣模型表4所示,限于篇幅,每个兴趣类只用部分关键词表示。
3.3 对比实验
本文在Google和百度两大主流搜索引擎上,进行了以下三组实验:
1)None实验:不采用查询扩展,只使用用户查询关键词进行检索的实验。
2)Standard实验:采用文献[7]提出的SEPMBDVD模型进行查询扩展,然后在搜索引擎上进行检索的实验。
3)UPD based实验:采用本文提出的QEMBUPDSE模型进行查询扩展,然后在搜索引擎上进行检索的实验。
对比实验由提供用户兴趣模型的三位用户实施,每位用户对自己的每个兴趣选用适当的关键词按以上三组实验要求在Google和百度上进行搜索,每组实验都将每种搜索引擎返回的前100张网页保存下来。接着针对每种搜索引擎,计算每个关键词搜索到的网页集合与UPD之间的SWUI,最后根据各SWUI计算各个兴趣类的ASWUIIC(Average Similarity between Webpages and User Interest in each Interest Class),计算公式如公式9所示:
公式9中,n为某兴趣类的测试关键词数量,因此ASWUIIC表示某兴趣类的所有关键词搜索的网页集合与UPD之间的SWUI的平均值。最终实验结果如表5所示:
为了更直观的反映对比的效果,本文计算了UPD based相对于None以及Standard的实验结果的提高百分比,如表6所示:
从表6可以看出,首先,使用QEMBUPDSE模型进行查询扩展后,搜索到的网页比不使用查询扩展明显与用户的兴趣更相关。其次,与使用SEPMBDVD模型扩展相比,使用QEMBUPDSE模型进行查询扩展后,搜索到的网页在与用户的相关性上也有一定的提高,反映了网页更符合用户的兴趣。这主要是由于在用户建模之前使用了UPD后,可以使整个用户建模过程得到一定程度的优化,最终的用户兴趣模型更加准确,使查询扩展发挥出更好的效果。
4 结束语
本文在文献[7]提出的基于二级向量的搜索引擎个性化服务模型基础上进行改进,加入了用户个性化词典,用以优化用户兴趣建模过程,进而改善查询扩展的效果。实验表明基于个性化词典的搜索引擎查询扩展模型能够更有效的辅助用户利用搜索引擎搜索到自己感兴趣的信息。在下一步的研究中,需要考虑如何更准确地建立个性化词典和用户兴趣模型,提出更好的相似度计算方法,用以改进整个个性化搜索模型的性能。
参考文献
[1]丁国栋,白硕,王斌.一种基于局部共现的查询扩展方法[J].中文信息学报,2006,20(3):48-53.
[2]袁薇,高淼.搜索引擎系统中个性化机制的研究[J].微电子学与计算机,2006(2):68-75.
[3]黄名选,严小卫,张师超.基于关联规则挖掘的查询扩展模型研究[J].现代图书情报技术,2007(10):47-51.
[4]黄名选,严小卫,张师超.基于矩阵加权关联规则挖掘的伪相关反馈查询扩展[J].软件学报,2009,20(7):1854-1865.
[5]黄名选,严小卫,张师超.完全加权关联规则挖掘及其在查询扩展中的应用[J].计算机应用研究,2008,25(6):1724-1730.
[6]支凤麟,徐炜民.基于主题的个性化查询扩展模型[J].计算机工程与设计,2010,31(20):4471-4475.
[7]徐静秋,朱征宇,谭明红,等.基于二级向量的搜索引擎个性化服务模型[J].计算机科学,2007,34(11):89-92.
[8]Zhengyu ZHU,Yunyan TIAN,Kunfeng YUAN,Yong YANG.An Improved Web Document Clustering Method.Journal of Computa tional Information Systems,2007,3(3):1087-1094.
[9]Khan M S,Khor S.Enhanced web document retrieval using automatic query expansion[J].Journal of the American Society for In formation Science and Technology,2004,55(1):29-40.
查询模型 篇6
关键词：交通安全,通用查询统计模型,专用语言,信息系统,语言解析
0 引言
随着公安部金盾工程二期建设任务的推进, 公安交通管理信息系统在标准体系、应用软件、业务数据等方面进行了深度整合, 建立了公安交通管理综合应用平台, 实现了机动车、驾驶人、交通违法、交通事故等核心业务数据的汇聚和应用软件的统一。但系统整合后, 各地公安交通管理部门对于数据查询、统计的需求, 尤其是对于业务交叉数据的综合类查询统计的需求急剧膨胀, 现有查询统计功能开发模式已不再适应各地快速增长的需求[1]。当前国内外研究人员一方面采用高级任意查询、统计功能模块, 试图通过1个功能满足用户的需求, 但该功能用户操作复杂, 也不能实现用户访问权限细粒度控制[2];另一方面采用IBM、微软公司等BI商业智能软件产品进行集成应用, 但商业软件成本高, 用户学习难度大, 不利于大规模推广应用[3]。为此, 需要通过对各地查询统计需求的深入分析, 抽取其本质的查询统计功能逻辑, 设计1种能够自动适应用户需求的通用查询统计模型及应用系统, 实现查询统计逻辑的管理[4], 快速构建Web方式的通用查询统计功能, 彻底解决公安交通管理快速增长的查询统计需求。
1 通用查询统计模型
通用查询统计模型从各类查询统计功能中抽取出的各项本质要素及其描述方式, 建立查询统计功能专用描述语言, 并将其保存至数据库表中, 以查询统计功能名称标识检索。同时, 研发专用描述语言的解释器软件, 从数据库中获取信息, 生成各种专用查询统计功能[5]。该模型主要由通用查询功能模型、通用统计功能模型和Web表单构建模型3个部分组成, 其中Web表单构建模型被通用查询功能模型和通用统计功能模型所引用。即采用查询功能模型和Web表单构建模型构建专用的查询功能, 采用统计功能模型和Web表单构建模型构建专用的统计功能。
1.1 通用查询模型
通用查询功能模型包括:查询条件页面显示描述 (引用Web表单构件模型) 、查询SQL配置描述、查询结果页面显示描述 (引用Web表单构件模型) , 以及根据上述描述语言负责解释执行实现查询功能的解释器[6], 其中专用描述语言是通用查询模块的核心结构[7]。查询模型专用语言与查询功能间的关系见图1。
1) 查询条件页面显示子模型描述语言基于Web表单构建模型, 用于构建专用查询功能模块的查询条件页面, 通过查询模型解释器解析后实现查询条件页面的显示。查询条件页面描述语言定义的页面域元素名称必须与查询SQL配置子模型描述中的查询条件变量名称保持一致。
2) 查询SQL配置子模型描述语言包括查询主表描述、查询子表及关联方式描述、条件字段及变量数据格式描述、基本条件描述、输出字段描述、排序字段描述和每页显示记录数描述等7个描述语言部分组成[8]。该子模型用于描述:依据条件页面输入的变量值, 解析生成动态SQL语句, 从后台数据库中抽取数据, 最后输出成基于Map的查询数据结果列表的过程。各组成部分进一步特征在于:1查询主表描述用于描述抽取SQL脚本中的主表名称;2查询子表及关联方式描述用于描述抽取SQL脚本中的子表名称, 以及子表与主表间的关联方式, 关联方式包括:普通连接和Exists连接, 并描述子表是采用强制关联方式, 还是采用根据是否存在子表查询条件变量而关联相应子表的关联方式;3条件字段及变量格式描述用于描述SQL脚本中查询条件以及查询条件变量的数据格式, 查询条件变量与查询页面域变量名称相对应, 如Web请求参数中存在查询条件变量, 那么此部分查询条件启用, 否则此部分查询条件不启用;4基本条件描述用于描述SQL脚本中必须的部分查询条件, 该部分查询条件变量为常量值;5输出字段描述用于描述SQL脚本中的输出字段, 输出字段必须在主表或子表字段范围内;6排序字段描述用于描述SQL脚本的排序字段列表及排序方式, 排序字段必须在主表或子表字段范围内;7各页显示记录数描述用于描述每次从后台数据库抽取查询结果记录的数量, 即查询结果页面每页显示的记录数量。例如, 道路交通事故业务信息查询功能查询SQL配置描述见表1。
3) 查询结果页面子模型描述语言基于Web表单构建模型, 用于构建专用查询功能模块的查询结果页面, 通过查询模型语言解释器解析后实现查询结果页面的显示。查询结果页面中描述的页面列元素名称须与查询SQL配置子模型描述语言中的输出字段描述名称一致。
1.2 通用统计功能模型
通用统计功能模型包括:统计条件页面显示描述 (基于Web表单构建模型) 、数据统计方式配置描述、报表格式描述、报表数据内容填写描述、统计图表的描述, 以及根据上述描述语言负责解释执行实现统计报表功能的解释器[9]。统计模型专用语言与统计功能间的关系见图2。
1) 统计条件页面显示描述语言基于Web表单构建模型, 用于构建专用统计功能的统计条件页面, 通过统计模型语言解释器解析后实现统计条件页面的显示。统计条件页面中描述语言定义的页面域元素名称必须与数据统计方式配置描述中的统计条件变量名称保持一致。
2) 数据统计方式描述语言用于描述统计功能从数据库抽取统计报表所需的数据, 主要包括:聚类字段、分组字段、统计条件、数据表名、同比环比及计算字段描述6个部分[10]。数据抽取根据数据统计方式描述语言配置的内容, 通过解释器转换为相应的SQL语句, 实现从数据库中抽取统计结果数据, 并将统计结果数据转化为以Map为单元的列表信息。各组成部分进一步特征在于:1聚类字段描述对应SQL语句中的统计指标字段, 其描述格式如下:[计算字段字段别名, ……], 字段别名与报表数据内容填写描述中的“JLZDMYM”“字段值”对应;2分组字段对应SQL语句中的统计分类字段, 其描述格式如下:[分组字段字段别名, ……], 字段别名与报表数据内容填写描述中的“字段名”相对应;3统计条件描述SQL语句中的条件部分, 包含动态条件和固定条件。动态条件可根据传入的页面参数值确定抽取数据的范围, 其描述格式如下:[表名.字段名, 比较类型#……], 比较类型为SQL条件中的运算符;固定条件是SQL条件中的固定内容;4数据表名对应统计SQL语句中的抽取数据表名, 包括主表描述和从表描述。主表描述格式如下:[表名表别名], 从表描述格式如下:[从表别名, 从表名, 与主表连接SQL, 连接方式#……], 与主表连接SQL指与主表关联SQL, 连接方式包换普通连接和EXISTS连接方式;5同比环比描述用于指定日期类型的条件字段作为同比或环比字段, 报表功能生成模块根据设定字段生成同比或环比统计数据;6计算字段描述用于描述统计报表中计算列的生成方法, 其描述格式如下:[计算类型 (源数据列索引) @计算列索引#......]。计算类型包括百分比、同期增减数、同期增减率、环比增减、环比增减率。源数据列索引用于指定报表数据的某列作为计算数据, 计算列索引用于指定计算类型生成的数据结果对应报表的列索引号。例如, 道路交通事故快报四项指数统计方式配置描述见表2。
3) 报表格式描述用于描述统计报表X轴向标题及Y轴向标题;该描述对于X轴向和Y轴向标题层数最多支持3个层次, 每层描述包含“层类型”和“层内容描述”[11]。“层类型”包括以下3种:1代码动态类型, 指当前层标题内容根据层说明指定代码内容, 如存在下层标题, 下层标题按当前各代码项循环输出;2固定不循环类型, 指当前标题内容按照“层内容描述”描述的固定内容输出, 如存在下层标题, 下层标题不按照当前标题内容循环输出;3固定循环类型, 指当前标题内容按照“层内容描述”描述的固定内容输出, 如存在下层标题, 下层标题按照当前标题内容循环输出。例如, 道路交通事故快报4项指数报表格式配置描述见表3。
4) 报表数据内容填写描述用于描述如何将统计结果数据定位到统计报表相应的单元中, 包括X轴和Y轴向数据定位描述。数据填充根据报表格式描述生成报表X轴与Y轴信息, 并初始化报表结果数据, 报表结果数据采用二维数组结构。在报表数据内容填写描述生成X轴Map和Y轴Map的基础上, 将统计结果数据填写至报表结果数据中;再根据数据统计方式描述处理计算字段信息, 根据统计图表描述将报表结果数据由报表数据结构转换为图表数据结构。
5) 统计图表描述用于描述统计图表的类型和图表对应的报表数据源, 统计图表的类型包括饼图、柱图、折线图等类型;图表数据源可支持多个报表结果数据列, 其描述格式如下:[数据列索引, 图表数据名称#, ……], 数据列索引与统计报表数据列索引对应, 图表数据名称根据数据内容含义自行描述。
1.3 Web页面构建模型
Web表单构建模型包括页面方案配置描述、页面域配置描述、页面元素配置描述, 以及相关专用描述语言的解释器[12]。该模型是查询条件页面显示描述、查询结果页面显示描述及统计条件页面显示描述的基础。Web表单构建模型与页面间的关系见图3。
1) 页面方案配置描述包括:方案信息、页面方案标签、页面表单类型、页面列数、行标签及表头标签的描述。方案信息描述用于说明Web页面构建的方案名称;页面表单类型包括:详细信息页面和列表信息页面两种类型, 其中详细信息页面用于查询条件页面、统计条件页面, 列表信息页面用于查询结果页面;页面列数用于描述页面表格的最大列数;页面方案标签描述用于说明页面总体JavaScript代码及相关CSS;行标签描述是在页面表单类型为列表信息页面时, 说明列表每行的JavaScript方法;表头标签描述是在页面表单类型为列表信息页面时, 说明构建表格第1行JavaScript的方法。
2) 页面域配置描述是基于页面元素配置描述, 属于页面方案配置描述的详细说明部分。包括页面域的顺序号、标题、页面元素标志号、HT-ML标识号。
3) 页面元素配置库是页面域扩展使用的基本元素库, 其描述包括元素标志号、元素名称、元素数据类型、元素标签、代码类别、元素类型描述。元素数据类型用于描述元素相应数据的数据类型, 包括:字符、数字、日期、照片、日期时间和时间数据格式;元素标签描述用于定制该元素的JavaScript代码;代码类别描述用于说明代码类元素所对应的标准代码的类别号;元素类型描述用于说明元素在页面上的表现形式, 包括:输入框、下拉列表、日期输入框 (不含日期控件) 、日期输入框 (含日期控件) 、单选框、复选框、文本输入框、图片、Flash、查询按钮、统计按钮等。
采用上述方法, 建立道路交通违法统计条件页面的配置描述见表4。
2 模型应用技术架构及成效
2.1 总体技术架构
基于通用查询统计模型的应用总体技术架构主要由查询统计配置功能、查询统计配置信息更新功能及查询统计配置信息解析功能组成。查询统计配置功能在通用查询统计模型的基础上, 对要构建的专用软件查询统计功能提供相关配置项目的可视化配置界面、配置信息逻辑校验及保存功能。查询统计配置信息更新功能采用Web服务技术方式, 实现将查询统计配置信息从查询统计配置服务器自动更新至应用服务器。查询统计配置信息解析功能, 读取查询统计配置信息, 并依据查询统计模型相关逻辑, 构建专用的查询统计功能。可配置型查询统计系统总体架构见图4。
2.2 应用成效
全国公安交通管理综合应用平台采用了上述可配置型的通用查询统计功能模型, 通过专用描述语言配置软件和解释器已生成道路交通事故、道路交通违法等各类查询统计功能107项, 将原有开发模式每个查询统计功能模块实现时间1~2工作日缩短至1h以内, 原有功能应用需升级各地应用软件优化为配置文件自动更新, 极大的提高了工作效率和管理力度, 满足了各地对业务数据查询统计分析的需求。同时, 在公安部端建立了查询统计功能集中配置管理和下发机制。其总体系统架构见图5。
公安部端采用基于上述模型的查询统计功能配置软件和各地公安交通管理综合应用平台动态构建的查询统计功能见图6、图7。
3 结束语
介绍了1种基于通用可配置型的查询统计模型、总体技术架构和应用情况, 阐述了通用查询功能模型、通用统计功能模型和WEB表单构建模型之间的关系, 详细描述了各模型的设计整体思路和具体实现方法。基于该模型的研究成果已在公安交通管理信息系统中得到了实施, 具有如下意义。
1) 查询统计功能由软件研发调整为通过配置工具快速构建, 减少了研发工作量, 提供了工作效率。
2) 建立了全国公安交通管理查询统计功能配置库和自动更新机制, 便于查询统计功能的管理与维护。
下一步, 要在当前模型和技术架构的基础上, 分析梳理后台定时统计报表功能本质关键要素, 将其融入本模型和技术架构体系, 使该模型应用能够适应各类实时、定时等更广泛的查询统计需求。
参考文献
[1]杨风召, 刘军.智能化交管综合业务管理系统[J].计算机系统应用, 2011, 20 (12) :132-135.Yang Fengzhao, Liu Jun, "BI-Based Integrated Traffic Information System", Computer Systems&Applications, 2011.20 (12) :132-135.
[2]祁新安, 吕代刚.通用查询模块的设计与实现[J].软件导刊, 2011 (4) :99-111.Qi Xinan, Lv Daigang.The design and implementation of general inquires the module[J].Soft Ware Guide, 2011 (4) :99-111.
[3]王刘杨.企业BI系统设计实践[J].计算机光盘软件与应用, 2012 (18) :19-21.Wang Liuyang.The practice of enterprise BI system design[J].Computer CD Software and Applications, 2012 (18) :19-21.
[4]张皓, 丁继成.基于组件对象模型的通用数据报表设计与实现[J].信息与电子工程, 2008 (6) :470-474.Zhang Hao, Ding Jicheng.Design of general data report based on component object model[J].Information And Electronic Engineering, 2008 (6) :470-474.
[5]史国友, 范中洲, 贾润, 等.基于字符串解析的智能查询方法及其应用[J].大连海事大学学报.2005, 31 (1) :91-93.Shi Guoyou, Fan Zhongzhou, Jia Run et al.Intelligent query method and its application based on character string parsing[J].Journal of Dalian Maritime University, 2005, 31 (1) :91-93.
[6]杨令省, 施继红, 张志龙.一种易扩展通用Web查询系统的设计模式[J].计算机时代, 2009 (3) :46-48.Yang Lingxing, Shi Jihong, Zhang hilong.An extended universal Web query system design model[J].Computer Era, 2009 (3) :46-48.
[7]楼翔, 张虑能.通用查询模块的设计与实现[J].计算机工程, 2004 (30) :564-565.Lou Xiang, Zhang Lvneng, Design and implementation of a general query module[J].Computer Engineering, 2004 (30) :564-565.
[8]任庆东, 李永盛, 袁文翠, 等.基于元数据驱动的勘探开发综合数据库通用查询系统[J].大庆石油学院学报, 2010, 34 (16) :91-95.Ren qingdong, Li Yongsheng, Yuan Wencui, et al."General database inquiry system based on metadara exploration and development"[J].Journal of Daqing Petroleuminstitute, 2010, 34 (16) :91-95.
[9]张素梅.统计分析软件驱动的可重构SPC系统[J].计算机工程与应用, 2008.44 (18) :203-205.Zhang Sumei.Statistical analysis software driven reconfigurable SPC system[J].Computer Engineering And Applications, 2008, 44 (18) :203-205.
[10]李文平, 王卫青, 赵额.居民出行OD调查数据统计分析方法的研究与实现[J].交通信息与安全, 2013 (3) :69-73.Li Wenpin, Wang Weiqing, Zhao Yi.Statistical analysis method of resident trip OD survey data[J].Journal of Transport Information and Safety, 2013 (3) :69-73.
[11]汪庆淼, 鞠时光.基于预测状态表示的多变量概率系统预测[J].计算机应用, 2012, 32 (11) :3044-3046.Wang Qingmiao, Ju Shiguang, "Prediction of multivariate probabilistic systems based on predictive state representation"[J].Journal of Computer Applications, 2012, 32 (11) :3044-3046.
查询模型 篇7
近年来,信息过量问题越来越受关注,如何从海量信息中准确高效地搜索到有价值的信息成为信息检索领域的研究热点。传统信息检索算法主要基于布尔查询和关键字查询,存在信息过载、信息迷向和不匹配等缺陷。将基于关联规则的数据挖掘技术应用于信息检索倍受关注,可以从根本上提高和优化信息检索性能。
文献[1]首次提出了一种基于关联规则的个性化信息检索模型,该模型主要通过用户访问日志挖掘出个性化信息之间的关联规则,帮助用户优化查询请求并提供具有个性化的搜索结果。文献[2]提出了一种基于正负关联规则的信息检索模型,采用正负关联规则的挖掘算法、两次检索技术和查询扩展优化等核心技术,达到区分和删除虚假扩展词的目的,从而得到比原查询更优的扩展查询结果。文献[3]融合了词语抽取、负关联规则挖掘算法和查询扩展三大关键技术,提出了基于词语抽取和负关联规则挖掘的信息检索算法,很大程度上改善了检索性能。文献[4]将负关联规则挖掘技术、频繁项集挖掘技术和查询优化扩展等技术进行融合,并且应用于信息检索,提出了基于频繁项集的挖掘算法和负关联规则挖掘的信息检索系统模型,实验结果验证了算法的有效性。文献[5]提出了一种新的基于完全加权关联规则挖掘与查询扩展技术的信息检索系统模型,该模型利 用传统的 向量空间 算法进行 初检,在第二次检索中则采用上述检索模型算法,显著提高了信息检索性能,实验结果表明结果是有效的。
本文在深入研究矩阵加权(完全加权)关联规则挖掘的基础上,提出基于项权值变化的矩阵加权关联规则挖掘算法,并将其应用于信息检索,采用一种新的模式支持度计算方法和项集剪枝技术,这样既避免出现无效的关联模式,又提高了挖掘效率。为测试该信息检索模型的检索性能,以1080篇论文作为原始测试文档集进行实验,实验结果表明本文算法能有效提高检索性能(MAP)。
1基于项权值变化的矩阵加权关联规则挖掘和查询扩展技术的信息检索模型
1.1主要设计思想
该检索模型基本思想为:整个检索过程中进行两次检索,第一次检索的主要目的是提取初检的前N篇排序文档作为初检局部文档集,主要利用搜索引擎对原查询进行初检和对局部文档集进行预处理;第二次检索采用上述关联规则挖掘和查询扩展技术优化原查询,得到扩展优化后的新查询,将最终检索结果返给用户。
1.2模型图及其模块功能
根据该模型设计思想,提出信息检索模型结构,如图1所示。该模型包括4个数据库和6个主要功能模块[5]。
1.3基于项权值变化的矩阵加权关联规则挖掘的关键技术
1.3.1矩阵加权项集剪枝策略
矩阵加权数据模型的固有特点是其项目权值随事务记录变化而变化,项目权值 是项集支 持度计算 的主要依据。矩阵加权关联规则挖掘算法中频繁项集的任意非空子集不一 定都是频 繁的,不适用Apriori算法的剪 枝性质。
经过对矩阵加权数据的深入分析研究,给出如下矩阵加权项集剪枝策略:生成矩阵加权候选k-项集CK前,将那些权值wK-1小于其包含 (K-1)-项集的K-项集权值频繁期望IWFE(CK-1,K)的候选 (K-1)-项集CK-1剪枝,候选 (K-1)-项集CK-1的后续K-项集一定是非频繁的;生成矩阵加权候选K-项集CK后,考察每个CK,只要存在某个 (K-1)-子集的权值为0或者小于其包含 (K1)-子集的K-项集权值频繁期望IWFE(CK-1,K),该候选K-项集CK一定是非频繁的,可以剪枝;最后,将权值为0的候选K-项集CK剪枝。
1.3.2挖掘算法
基于项权值变化的矩阵加权关联规则挖掘的基本思想为:
(1)对矩阵加权数据进行预处理,构建基于向量空间模型的矩阵加权数据库和特征词项目库。
(2)从项目库中挖掘矩阵加权频繁1-项集,计算出矩阵加权1-项集权值频繁期望IWFE(C1,2)。
(3)从K-项集 (K≥2)起,候选 (K-1)-项集CK-1进行Apriori连接生成候选K-项集CK,根据上述矩阵加权项集剪枝策略,从候选K-项集CK挖掘出矩阵加权频繁K-项集LK,直到候选K-项集CK为空为止。
(4)从频繁项集中挖掘矩阵加权强关联规则。
2实验设计及结果分析
编写实验源程序,以1080篇论文作为原始测试文档集,设计10个实际查 询 (Q1,Q2,...,Q10)作为查询 集。采用MAP(MeanofAveragePrecision)为主要评测指标,将本文信息检索算法(简写为A算法)、基于完全加权的关联规则算法(简写为B算法)、基于局部上下文分析的扩展查询技术(简写为C算法)和传统的向量空间模型算法(简写为D算法)进行检索性能比较,分别统计4种算法中10个查询的平均准确率,实验结果如表1所示。
可以看出,本文算法准确率有显著提高,该模型能有效地优化扩充原查询,检索出更加满意的文档。
3结语
本文在信息检索系统中首次将项权值变化的矩阵加权关联规则挖掘技术应用于查询扩展,将二者融合后应用于信息检索系统,提出基于项权值变化的矩阵加权关联规则挖掘的信息检索模型及算法,取得了非常显著的效果。该模型采用两次检索机制,先对全部文档集进行初检,采用基于项权值变化的矩阵加权关联规则挖掘算法对提取的局部初检文档进行关联挖掘分析,经查询优化扩展后,组成更佳的新查询来弥补原查询信息的不足,并将最终检索结果返回给用户。实验结果证明了该模型的有效性。
摘要：将项权值变化的矩阵加权关联规则挖掘技术应用于信息检索,提出一种基于项权值变化的矩阵加权关联规则挖掘的信息检索模型及其算法,采用新的剪枝策略和模式支持度计算方法。实验结果表明,新模型检索性能得到改善和提高。
关键词：文本信息检索,矩阵加权,查询扩展,关联规则
参考文献
[1]陈小华,赵捧未.基于关联规则的个性化信息检索系统研究[J].情报科学,2006,24(6):915-918.
[2]黄名选,朱豪安,冯平.基于正负关联规则融合的信息检索模型[J].信息系统,2011,34(7),116-119.
[3]黄名选,冯平,谢统义.基于词语抽取与负关联规则挖掘的信息检索[J].计算机技术与发展,2012,22(5),157-160.
[4]黄名选,余如.基于负关联规则与频繁项集挖掘的信息检索系统[J].知识组织与知识管理,2011,22(8),91-96.
[5]黄名选,严小卫,张师超.基于完全加权关联规则挖掘和查询扩展的信息检索[J].计算机应用与软件,2009,26(8):26-28.