一个基于概念格的小型信息检索系统.pdf

一个基于概念格的小型信息检索系统 彭韬，陈光 北京邮电大学信息工程学院，北京 (100876) E-mail：ppttbupt@ 摘 要：互联网上信息爆炸式的增长，使得传统的搜索引擎很难让用户精准且快速地定位信 息。文中提出一种基于概念格的方法，将检索结果更好的展现给用户，并且能引导用户准确 定位信息。搭建并研究搜索引擎是非常昂贵的，本文还提出一种小型信息检索模型，能够模 拟普通搜索的功能，让个人能在有限的硬件条件下，参与到信息检索的研究。 关键词：信息检索，概念格，搜索引擎 1. 引言 随着Internet 的飞速发展，网络上的信息呈指数增长，其内容之丰富，种类之繁多，堪 称世界上最大的信息资源，如何能够更有效、更准确地找到用户感兴趣的内容，滤除与用户 的需求无关的信息，真正做到“各取所需”，关系到我们能否充分利用这个巨大的信息资源的 问题，这己成为基于Internet 的网络信息获取的热点问题。 因为信息检索中的文档——特征词关系能够很自然的被看作形式概念分析中的形式背 景，所以从二十世纪80 年代起，一些学者借助形式概念分析理论的核心数据结构——概念 格对信息检索进行了研究[1] 。基于概念格理论和应用的新发展，概念格在信息检索领域引起 了越来越多的研究者的关注[2] 。从理论提出开始十年左右的时间里，对形式概念分析的研究 主要集中在德国国内少数学者中间。这一时期的研究理论性很强，对问题的描述、分析和论 证多采用数学的、很抽象的方法；与此同时，形式概念分析在德国国内的几个大型项目中取 [3] 得了成功的应用，其中包括著名的TOSCANA 系统 。 概念格在知识发现方面展现出了强劲的力量[4]，但是研究的初期，创建概念格在时间空 间上都有着巨大的消耗，因此在信息检索领域可行性较差，信息检索领域的专家们对概念格 的热情也就告一段落。而随着网络技术尤其是互联网的飞速发展，数据的分布式存储和并行 处理的需求越来越迫切，对多概念格的合并算法也有了一些研究。其中，李云通过定义概念 的横向加运算，提出了一种多概念格的横向合并算法，该算法适用于对概念格进行分布并行 处理。从而使得构建概念格不再成为耗时巨大的工程，并逐步推广到普通检索系统中。本文 就是遵循这个思路，提出了基于概念格的新型轻便检索系统。 在我们提出的轻便检索系统，将概念格的特性展现在结果中，目前有两种模式：查询扩 展与结果聚类展示。这两种模式都是为了更好地向导用户，精确定位信息。 2. 概念格简介 形式概念分析通常由形式背景这一基本概念开始。首先给出形式背景的定义。 定义 2.1 形式背景定义为一个三元组K=(G,M,I) ，其中，G 是对象集合，M 是属性 集合，I ⊆G×M 是G 与M 之间的一个二元关系。若(g,m) ∈I，读作“对象g 具有属性m” 。 形式背景通常用交叉表（cross table ）来表示。在交叉表中一行代表一个对象，一列代 表一个属性，第 g 行和第 m 列的交叉点有一个“1”，当且仅当(g, m) ∈I 。图1是一个例子形 式背景的交叉表。 - 1 - 图1 一个例子形式背景 定义 2.2 在形式背景 K 中，在 G 的幂集和 M 的幂集之间可以定义两个映射 f 和 g 如下： ∨A ⊆G: f(A) ={m ∈M | ∨g ∈A, gRm} ∨B ⊆M: g(B) ={g ∈G | ∨m ∈B, gRm} f和g被称为G 的幂集和M 的幂集之间的Galois联接。通常，为书写方便，采用A′和 B′分 别代替 f(A)和 g(B) 。 定义 2.3 背景 K=(G,M,I)上的一个形式概念定义为一个二元组(A,B)，满足：