一种基于模糊相似粗糙集的WEB搜索优化方法(1)

一种基于模糊相似粗糙集的WEB搜索优化方法(1) 摘要 如何对Web信息搜索进行优化，是信息检索的重要研究课题。本文基于模糊相似粗糙集，在语义结构和Web的超链接结构间建立起映射，从而提高Web搜索的速度和准确率。关键词 Web信息搜索；模糊分类；超链分析；模糊粗糙集；相似关系1 引言Web作为信息制造、发布、加工与处理的主要平台，正以令人难以置信的速度在飞速发展着。如何在Web所提供的海量信息中发现有用的信息并加以有效利用，一直是人们努力研究的方向。搜索引擎（Search engine）是目前Web信息检索的主要工具。传统的搜索引擎大多是基于关键字匹配、目录分类等技术，但在查询速度与查准率、查全率等方面还具有较大的局限性。近几年的研究发现，分析Web网页间的超链接结构并充分利用，可以提高检索的质量。基于这种超链分析的思想，在1998年，Serger Brin和Lawrence Page提出了PageRank[1]算法。同年，J.Kleinberg提出了HITS[2]算法，还有其他一些研究者相继提出了一些改进算法，如SALSA、PHITS等，在实际应用中取得了良好的效果。为了进一步提高Web搜索的效率，我们提出了一种根据特定的需求，利用粗糙比较对Web信息的搜索路径进行优化的方法。首先对用户提交的反映用户需求的网页或关键字进行模糊分类，得到对信息空间的相似分类，再对识别出来的网页集团的超链接结构进行分析，用网页间作用力与文本信息的混和相似度，得到网页集团在用户需求信息上的相似类划分。通过对各自所得到的基于相似关系的模糊粗糙集之间相似程度的度量，找到与用户需求最接近的网页集团的排序表，从而达到对Web信息搜索的优化。本文首先回顾一些研究者在这一领域所做的一些相关工作；然后在核心部分详细论述了基于相似关系模糊粗糙集的Web搜索优化策略；最后是我们的结论。2 相关工作J．kleinberg等在文[3]中提出Web结构所呈现出来的自组织性，从而反映出Web上的一些信息分布知识。他们认为，尽管Web是一个分散的信息网络，但从全局来看，互不关联的创建过程由于作者共同的偏好而使得信息源之间产生了愈来愈紧密的联系，即通过超链接内容相同或相关而自然地聚合在一起，形成一个个网页集团[4]（Web community）。网页集团是指Web上一些网页所组成的集合，组成集合的成员网页指向集合内其他成员网页的超链接数，远比其指向集合外非成员网页的超链接数多得多。从形式上看，集团内部链接密集，而集团间链接稀疏，甚至根本不链接。集团内部的高密度链接通常表明构成集团的成员网页具有一定的信息相关性。这一发现对于我们进行Web信息搜索的优化具有很高的价值。PageRank算法和HITS算法是两种影响相当广泛的链接分析算法。其中，PageRank算法的基本出发点是试图为整个Web上的所有网页赋予一个量化的表征权威度的值，即通过迭代计算特征为每个网页分配PageRank值。由于所有处理过程是离线进行，因此不会为在线的查询过程付出额外的代价，但它最大的问题是没有对主题进行区分，因此，可能在返回结果中出现与主题无关的一些网页排在前面的情况。HITS算法模型中，提出了权威性网页（authority）和中心网页（hub）的概念。其中，权威性网页是被大量的超链接所指向的、包含高质量的主题内容的信息源。Hub网页是指向和主题相关的权威网页的一些不知名网页，提供对高质量主题内容存取的信息源。它们之间具有互相增强的关系（mutually reinforcing relationship）：一个“好的”Hub网页应该指向很多“好的”权威性网页，一个“好的”权威性网页应该被很多“好的”Hub网页所指向，这样就需要通过一个迭代过程来计算每个网页的Authority值和Hub值。Kleinberg所提出的具体计算方法如下：用传统的基于关键字匹配的搜索引擎对用户提交的查询进行搜索，得到满足条件的前n个网页组成的基集S，再通过加入S引用的网页和引用S的网页得到一个更大的集合T。对于集合T中的任何网页，用a(u)表示网页u的Authority值，用h(v)表示网页v的HubHITS算法是与特定查询主题相关的方式，因此在速度上有一定的优势，但也可能由于没有考虑链接的权重而造成主题漂移（topic drift）现象，但经过改进的加权（weighting）和修剪过滤（outlier filtering）等算法在一定程度上可以克服HITS算法的主题漂移问题。本文中所提出的Web搜索优化策略是在Web语义结构和网页集团的拓扑结构之间建立起一种映射，也就是在网页集团的拓扑结构中加入了用户的信息需求，从而提高搜索的速度和质量。在计算集团内网页间相似度与衡量网页重要性的工作中，我们引用了HITS算法中Authority和Hub的计算方法。另外，对于如何在Web中自动识别网页集团，已经有一些研究者提出了许多算法，如Gray和Steve[5]提出的基于Maximum Flow原理的识别网页集团的算法。因此我们的工作是假设在已经识别了一些网页集团结构的基础之上进行的。3 Web搜索优化策略3.1 Web信息空间划分对Web信息空间的划分，我们采用了模糊分类的方法。所谓分类就是采用某种方法把一些特征上类似的对象归并在一起，把一个对象的集合分为若干个子集，每个子集的元素具有类似的特征，而不同子集的元素尽量相异。在实际分类问题处理中，往往会发现精确地确定某个对象属于哪个分类是困难的，而只能近似给出它属于这个类的可能性有多大，在什么程度上相对地属于某一类，这就是我们所说的模糊分类的概念。这里采用文[6]中所提出的 “基于关键词的文本的模糊分类方法”。下面给出具体的实现。 3.1.1 通过文本模糊分类方法构建表征信息空间分类的模糊矩阵设D1,D2,…Dn是n个文本，每个文本Di由m个关键词d1,d2,…,dm来描述。这样文本Di可用一个m维向量表示：Di=(fi1,fi2,…,fim)其中