〔摘 要〕针对搜索引擎在信息检索过程中存在的缺陷,本文提出了一种基于Multi-Agent的Web个性化信息推送系统模型,并给出了该模型的结构､工作流程以及算法设计｡该系统采用Multi-Agent系统的体系结构和反馈机制,各个Agent分工协作完成信息推送任务,体现了信息服务的智能化与个性化等特点｡
　　〔关键词〕Agent;信息检索;信息过滤;信息推送;向量空间模型;相似度;文档聚类
　　〔中图分类号〕TP393 〔文献标识码〕B 〔文章编号〕1008-0821(2009)08-0117-05
　　
　　Study of Web Personalized Information Push System Based on Multi-AgentHuang Jizheng
　　(Library,Zhanjiang Normal University,Zhanjiang 524048,China)
　　〔Abstract〕Because of the limitation which exists in the information retrieval process,its proposed that Web personalized information push model based on Multi-Agent.Its system structure,work flow,algorithms design are given too.The system adopts system structure and feedback mechanism of Multi-Agent system.Each Agent cooperates to finish information push task,manifest the characteristics of intellectualization and individuality of information service etc.
　　〔Key words〕Agent;information searching;information filtering;information push;vector space model;similarity;documents clustering
　　
　　根据中国互联网络信息中心(CNNIC)《第21次中国互联网络发展状况统计报告》显示,中国网站数､网页数和网页字节数超过60%的增长速度,反映了网上信息资源的增加速度很快,网民可以享用的信息资源越来越丰富,截至2007年12月,网民数己达到2.1亿人,目前2.1亿网民中使用搜索引擎的比例是72.4%[1]｡搜索引擎是通往浩瀚信息海洋的捷径,实践表明,搜索引擎是有效的网络信息拉取(查询)的辅助工具｡遗憾的是,尽管目前提供的搜索引擎很多,但仍存在着一些缺陷:①信息导引能力差,只要所输入的关键词相同,就会返回相同的信息,而不会考虑到不同用户的不同兴趣爱好和学科领域,导致大量无关信息的涌现｡②不能主动给用户反映网络上的信息的动态变化｡③往往具有相同兴趣的用户对信息的需求基本一致,但传统的搜索引擎并不提供协作过滤功能,使用户失去了准确获取信息的一个重要方式｡④一般不具备学习功能,不能主动发现和收集用户所需要的信息｡⑤普通用户往往因不能准确地用关键词描述自己的信息需求而难以获取准确信息｡因此,如何使用户能真正享受到快捷准确的个性户信息服务已成为一个重要的研究课题｡
　　
　　1 智能Agent
　　
　　1.1 Agent技术
　　Agent用来最一般地说明一个软硬件系统,它具有以下4个特性:①自治性:Agent可以在没有人或其他Agent直接干预的情况下运作,而且对自己的行为和内部状态有某种控制能力;②社会性:Agent和其他Agent(也可能是人)通过某种Agent语言进行信息交流;③反应性:Agent能够理解周围的环境,并对环境的化作出实时的响应;④能动性:Agent不仅简单地对其环境作出反应,也能够通过接受某些启动信息,表现出有目标的行为｡Agent除了具备以上特性外,还具备一些人类才具有的特性,如知识､信念､义务､意图等[2]｡
　　1.2 MAS(Multi-Agent System)
　　Agent一般由知识库､通信模块和可选的功能组件组成,它可以感知系统环境的变化,并对这种变化做出自主的反映,因而具有智能性｡由于一个智能主体的能力受其知识､计算资源及其与其他主体相互关系的制约,限制了单主体系统解决问题的能力｡为了解决大型､复杂的现实问题,在分布式人工智能领域引入了多主体系统MAS(Multi-Agent System)｡MAS是由分布在网络上的多个Agent松散藕合而成的大型复杂系统,各Agent要对熟悉的环境做出迅速的响应,同时能够协调与其他Agent的冲突,并最终做出决策[3]｡
　　Agent技术作为目前人工智能(AI)领域研究的一个热点,为实现信息服务的智能化､个性化及主动性提供了新的方向｡针对这一情况,本文提出了一种基于Multi-Agent的web个性化信息推送系统模式,并详细叙述了系统的设计思想､体系结构和算法设计｡
　　
　　2 系统结构与设计
　　
　　2.1 系统的设计思想
　　本文所设计的Web个性化信息推送系统是一个基于Multi-Agent的智能系统,应用机器学习技术自适应调整用户兴趣模型,以提供智能化､个性化的主动信息服务｡系统由用户Agent､学习Agent､过滤Agent､检索Agent､推荐Agent､用户模型库､领域模型库和文档信息库组成｡根据用户的兴趣,这些Agent通过共同的通信语言和通信机制进行相互交流和协作来快速准确地完成对中文网络信息的个性化过滤,主动为用户提供某类感兴趣的相关信息｡
　　2.2 系统的体系结构
　　Web个性化信息推送系统的总体结构如图1所示｡
　　2.3 系统工作流程
　　系统的工作流程是:用户Agent与用户进行交互,接受用户的个性化信息要求;学习Agent观察用户Agent记录的用户检索查询记录和浏览行为以获取用户兴趣,并将之写入用户模型库;同时提取和计算出各主题概念所对应的关键词及其相应权重,根据该领域的专业词典,写入领域模型库;检索Agent在领域模型库中取权值最大的3-10个特征项作为查询关键词,借助搜索引擎进行相关检索,将查询到的结果URL作为起点,开始进行文档采集;过滤Agent依据领域模型对采集的文档进行分析,抽取文档特征,形成文档结构化表示;推荐Agent通过比较结构化的文档属性与用户模型,寻找相似度最大的若干用户,并将其选择的文档通过用户Agent推送给用户;学习Agent利用机器学习技术对用户相关性反馈信息进行学习,自适应地调整用户模型和领域模型,使用户模型更好地体现用户的兴趣｡
　　模型系统的工作流程如上所述,经过相关性反馈学习之后,修改后的用户模型更加体现用户的兴趣,因此用户利用修改过的用户模型进行信息挖掘的时候将获得更高的查准率｡经过整个检索过程,一方面用户得到了符合自己兴趣的信息,另一方面系统学习到了用户的信息兴趣,为个性化信息检索和主动信息服务提供基础知识｡
　　2.4 系统功能分析
　　2.4.1 用户模型库
　　用户模型库记录反映用户各兴趣点的模型｡用户模型库的主要作用是:
　　(1)用户模型用于信息文档的过滤,可为推荐Agent提供用户的兴趣模型,通过与过滤Agent所提供的领域相关的信息文档的结构化特征进行相似性比较,从而提供给用户其最感兴趣的文档｡
　　(2)用于推荐Agent比较用户之间相似性的标准,从而可向相似用户推荐相关文档｡
　　2.4.2 领域模型库
　　领域模型库用来描述各知识领域中主题概念间的关系及与各概念相关的关键词｡本文所设计的领域模型为树形结构｡领域模型库的主要作用是:
　　(1)作为构造用户模型的基础,用户可通过选择领域的主题概念及其关键词作为其基本的兴趣点,形成用户模型的框架基础;
　　(2)作为搜集信息的基础,为检索Agent调用其他搜索引擎提供关键词;
　　(3)作为对网页进行分类的基础｡过滤Agent利用领域模型库中的信息,通过分析文档特征形成文档的结构化表示,计算网页与各主题概念的隶属程度,从而对网页进行分类｡
　　2.4.3 文档信息库
　　文档信息库记录所收集的网页(全文和URL)､相应文档的结构化信息(主要是关键词的词频)及与之相关性最大的若干主题概念的隶属度｡文档信息库的主要作用是:
　　(1)为用户提供快速的获取相关网页的手段,通过该库向用户推荐隶属度较高的网页;
　　(2)为检索Agent记录历史信息避免重复搜索同一页面｡
　　2.4.4 用户Agent
　　用户Agent是用户与系统的交互接口,接受用户的个性化信息要求｡用户Agent的任务是:
　　(1)与用户进行交互,接受用户反馈信息,将用户反馈信息提供给学习Agent进行机器学习,以修改用户模型,使用户模型能更好地表现用户的兴趣;
　　(2)在交互过程中,通过监测用户的查询､浏览等行为过程,并将这些信息提供给学习Agent进行分析,动态地学习用户兴趣｡
　　2.4.5 学习Agent
　　学习Agent的任务是通过接收用户Agent所记录的用户显式和隐式相关性反馈信息学习用户兴趣,通过机器学习修改用户模型并调节领域模型｡
　　2.4.6 检索Agent
　　检索Agent的主要任务是:
　　(1)借助搜索引擎在网络中搜集与领域相关的网页;
　　(2)在系统设定的时间内对资源数据库信息扫描,将扫描到的变化结果写入到搜索信息索引中,使得更新能够被用户搜索而又不必更新智能Agent系统程序｡
　　2.4.7 过滤Agent
　　过滤Agent是整个系统的核心,它的设计直接关系到系统的功能和性能｡过滤Agent的主要功能是对网页进行分析,抽取文档特征,形成文档的结构化表示,作用如下:
　　(1)对网页进行特征抽取,形成结构化的网页属性｡
　　(2)分析网页中有价值的超链接,向信息检索Agent提供进一步下载的URL列表｡
　　(3)对新收入的网页进行分析,提取新的主题概念关键词,并将其加入用户模型库｡
　　2.4.8 推送Agent
　　推送Agent负责把收入的网页推荐给感兴趣的相关用户｡推送Agent每隔一定的时间或当收入的网页达到一定数量时启动文档选择任务,通过比较结构化的文档属性与用户模型,寻找相似度最大的若干文档通过用户Agent推送给用户｡
　　
　　3 多Agent的通信和协作
　　
　　3.1 Agent间的通信
　　多Agent通信机制直接影响了多Agent系统的协同工作能力和系统的性能｡本系统下的多个Agent通过ACL通信语言和FIPA消息传递机制进行通信和协同工作｡在FIPA规范下的Agent平台有3个主要的子系统:索引器､AMS(Agent Manage System,Agent管理系统)和MTS(MessageTransport Service,消息传输服务)｡Agent间消息的传送通过MTS系统中的ACC(Agent Communication Channel)提供的消息传送服务以“信封+消息”的格式传输来实现｡根据信封中定义的地址等信息,在MTS为Agent平台上的Agent找到合适的消息传送通道ACC后,ACC进行通信协议的判定和消息的传输｡当消息抵达目的地后,再通过ACC,Agent就可以解读ACL所要传达的信息,多Agent之间的沟通也随即完成[4]｡
　　3.2 Agent间的协作
　　Agent的协作是保证系统能在一起工作的关键｡协调与协作是多Agent研究的核心问题之一,因为以自主的Agent为中心,使多Agent的知识､愿望､意图､规划､行动协调,以致到达协作是多Agent的目标｡协调是指一组Agent完成一些集体活动时相互作用的性质｡在开放､动态的多Agent环境下,具有不同目标的多个Agent必须对其目标､资源的使用进行协调｡在出现资源冲突时,若没有很好的协调就可能出现死锁｡而在另一种情况下,即单个Agent无法独立完成目标,需要其他Agent的帮助,这时就需要协作｡一般来说,当某个Agent相信通过协作能带来好处时,会产生协作的愿望,进而寻求协作伙伴｡在多Agent中协作不仅能提高单个Agent以及由多个Agent所形成系统的整体行为的性能,增强Agent及Agent系统解决问题的能力,还能使系统具有更好的灵活性[5]｡正是协作使得几个智能Agent能将它们各自的努力组合起来完成信息的推送这一目标｡
　　
　　4 算法设计
　　
　　4.1 文档的向量空间模型
　　为了将文本文档表示成计算机容易处理的形式,需要对文档进行一定的特征抽取,该特征既要能包括文档的大部分关键词,又要方便计算机根据这些特征计算文档之间的关联度｡根据实际情况,我们选取了向量空间模型(VSM)来对文档的语义结构进行建模｡VSM是由一组规范化正交词条矢量所张成的向量空间,每个文档映射成向量空间的一个点,向量间的距离表示文档的相似度｡
　　假如用符号D表示文档,t表示特征项,w表示权重,那么根据VSM的定义可以得到文档的向量空间模型:D=(t1w1,t2w2,…,tnwn)｡由于t1,t2,…,tn互不关联,可以把它们看作是n维向量空间的n个维度,而w则表示该文档在这些方向上面的投影坐标,每个坐标反映了该文档在相应的特征项所表示的含义上面的意义大小[6]｡
　　在信息检索向量空间模型中,文档是由相互独立的关键词t1,t2,…,tn构成,令D=(D1,D2,…,Dn)表示由m个索引关键词构成的n个文档,其中Dj=(d1j,d2j,…,dmj)是文档向量,dij表示关键词i发生在文档j中的频率权重,这样就定义了一个m维关键词文档向量空间,即词语向量空间[6]｡在文档向量空间当中,对文档进行分类､聚类､排序和相关性反馈都要分析两个向量之间的相似度｡
　　4.2 相似度的计算
　　在基于VSM的信息检索中,有许多种计算相似度(点与点的距离)的方法,基于简化的数学公式分析,我们采用余弦系数计算文本的相关性[6-7]｡
　　sim(Di,Dj)=∑mk=1dkidkj∑mk=1dki2∑mk=1dkj2(1)
　　4.3 文档聚类算法
　　为了从用户的反馈文档当中总结出某种规律,得到用户的信息检索模型,下面分析一下文档的聚类过程｡聚类是指将文档集合分成若干个簇,要求同一个簇内文档内容的相似度尽可能地大,而不同簇间的相似度尽可能地小[8]｡目前,基于向量空间模型的常见文档聚类算法有分割算法中的k-means算法和层次算法中的凝聚层次算法｡
　　4.3.1 k-means算法
　　k-means算法以k为参数,把n个对象分为k个簇,以使簇内具有较高的相似度,簇间的相似度较低｡一般步骤如下:
　　(1)在N个对象中随机选取K个对象作为初始的聚类中心;
　　(2)把其余的N-K个对象归到距离最近的聚类中;
　　(3)重新计算每一个聚类的中心;
　　(4)重复(2)和(3),直到每个聚类中心不再改变｡
　　这种算法的实质是一种多次迭代的方法,把每篇文档看成一个对象,利用文档与聚类中心之间的相似度进行聚类,在数据量较小时,具有较好的聚类效果,当处理大规模数据时,时间复杂度也是O(n),但聚类效果差,计算量也会增大[9]｡
　　4.3.2 凝聚的层次算法
　　凝聚的层次算法将数据对象组成一棵聚类的树｡其一般步骤如下:
　　(1)把N个对象作为N个聚类,计算所有聚类两两之间的相似度;
　　(2)合并最为相似(满足距离要求)的聚类;
　　(3)重新计算更新后的所有聚类两两之间的相似度;
　　(4)重复(2)和(3),直到剩下一个聚类｡
　　这种算法尽管方法简单,聚类效果一般比k-means算法要好,但是时间复杂度为O(n2)｡由于聚类之间不能交换对象,如果某一步选择不恰当,将导致低质量的聚类结果,它也不具有很好的伸缩性[9]｡
　　为了从用户的行为中得到用户信息检索的行为模型,本文借鉴了聚类算法中的一些基本思想,目的在于尽可能减少用户的介入,自动完成用户信息检索模型的建立和修改｡
　　4.4 用户信息检索模型
　　4.4.1 模型的建立
　　为了将用户的兴趣表示成计算机可以理解的形式,需要对用户的兴趣进行建模｡用户的兴趣可以概括为各个不同的相互独立的主题,主题相当于用户输入的检索关键字｡在建立用户兴趣模型的过程中,同样可以利用类似VSM的办法,将本来抽象的文档的意义进行合理的量化,映射为向量空间的一个可计算的点,具体步骤如下:
　　(1)用户提交检索主题;
　　(2)用户在返回的结果集中选择自己喜欢的文档;
　　(3)计算机对入选的文档进行分词､预处理;
　　(4)对预处理后的文档特征向量进行降维,并根据一定的规则对每个维度赋予权值｡
　　4.4.2 用户模型的重建
　　从用户模型的建立过程来看,刚开始的时候模型可能是不够精确的｡首先,对于某个新的检索主题,不存在任何可以代表该主题的示例文档,因此用户需要选择可以代表这一主题的示例文档,但是由于一级搜索引擎如Google等,可没有覆盖该主题相关的全部文档,或者由于用户挑选的失误而遗漏了与该主题相关的重要文档,仅选择部分不那么称心的文档,这时用户的模型就出现了偏差｡当用这些不准确的文档作为重心向量去过滤从搜索引擎返回的结果时,将不会反映整个文档域的中心｡其次,由于Internet上的文档不是静态的,而是不断增长的,因而重心向量也是随着文档的不断增长而不断变化的,因此,同样要采取一定的措施来保证重心向量能够根据用户的选择不断更新｡
　　针对这一问题,本系统设计将采用一种基于反馈的方案｡反馈的概念来源于经典控制理论,是一种通过不断比较输出信号与目标信号的偏差,来修正输入信号,以保证输出信号能够得到有效的控制､与预期相符的方法｡根据这个思想,用户兴趣模型的建立并不是一个孤立的过程,而是与信息过滤模型紧密相连的｡一般来说,这个过程包含3个模块:
　　(1)Profile的生成模块负责生成用户兴趣文件｡它通过分析用户给出的示例文档(一般可认为是第一次检索后经用户选择的结果),形成profile文件,并将该文件保存在磁盘上面｡该模块在后台运行｡
　　(2)过滤模块负责过滤文档流｡它通过比较后台存储的profile文件和输入文档的相关程度,过滤出用户感兴趣的结果文档,并将它们按照相关性排序后提交给用户｡该模块运行在前台｡
　　(3)Profile的重建模块负责profile的修改｡在建立用户兴趣文件时,用户有时难以准确表述自己的信息需求,但是可以准确地判断返回的信息是否符合要求而采取针对性的处理,如阅读､下载､浏览等｡该模块利用用户对结果文档的评估结果重新修改profile文件｡此模块运行在后台｡
　　4.4.3 用户信息检索模型的3个步骤
　　(1)profile的建立
　　在用户给出示例文档后,使用聚类算法中的训练算法来建立profile文件｡具体采用类重心分类算法(Text Categorization based on Category,简记为TC3),将每个类别看作是词条的集合,并为类别引入重心矢量的概念｡给定类别C和一批类别标识为C的训练文档DCtraining,该训练文档可以被认为是第一次检索的结果集,C的重心是指DCtraining中的所有文档矢量的累加矢量平均值｡根据上述定义,类别C的重心矢量可以由该类别的训练文档的矢量来计算｡公式如下:
　　∑/∑,d∈DCtraining(2)
　　从程序设计的角度来说,建立profile的过程也就是由示例文档训练出profile的类矢量的过程｡算法描述如下所示｡
　　输入:示例文档集合DCtraining
　　输出:Profile的类别矢量
　　算法:①←0
　　②for each d∈DCtraining
　　←+;
　　③←/
　　(2)文档过滤
　　过滤可以看作是一个分类的过程,也就是说存在两种不同的类别:一类是用户感兴趣的,另一类是用户不感兴趣的｡过滤就是要判断出文档属于哪个类,然后将属于用户感兴趣的类的文档返回给用户,而将用户不感兴趣的文档过滤掉｡由于过滤算法将会比较Profile文件中的文档向量和待过滤的文档向量,因此过滤算法与生成profile的算法密切相关｡目前,存在多种过滤算法,由于在本系统中profile的生成采用了TC3分类算法,故与此相应的过滤算法中,待过滤文档与用户兴趣的相似度比较采用余弦方法,见公式(1)｡
　　(3)Profile的重建
　　用户兴趣的学习是一个长期的过程,需要不断的维护,而维护的方式就是通过用户给出的反馈自动更新模型｡比如,当一个页面被选中时,则该页面会展现给用户,同时由用户给出反馈｡如果用户喜欢这个页面,则从这个页面抽取出的词的权重将会加到用户兴趣文件中相应词的权重上｡这一过程被称为相关度反馈｡本系统中采用Rccchio反馈模型｡更有效的用户兴趣文件可以由以下公式迭代产生:
　　Pk+1=Pk+β∑n1k=1Rkn1-γ∑n1k=1Skn2(3)
　　其中,Pk+1,是新的用户兴趣文件,Pk是旧的用户兴趣文件,Rk是用户反馈中认为感兴趣的(相关的)文档k的内容表示,Sk是用户认为不感兴趣的(不相关)文档k的内容表示,n1是相关文档数,n2是不相关文档数,β､γ值决定了正负反馈的相对作用｡
　　
　　5 结束语
　　
　　将人工智能领域的Agent技术引入网络信息服务研究是一个有代表性的研究方向｡本文提出了一种基于Multi-Agent的Web个性化信息推送系统模型,并详细叙述了系统的体系结构､设计思想和相关算法｡与传统搜索引擎相比,该模型具有搜索信息关联度高､能够满足用户个性化需求等优点,为主动开展个性化信息服务提出了一种有效的实现途径｡但文中用户信息检索模型采用的是基于向量空间模型的信息过滤方法,对于文档的描述普遍使用关键词向量,从而存在很大的信息丢失,因此希望下一步能够在文档语义理解方面作初步的探索,研究一种更高质量和高效率的信息过滤算法｡
　　
　　参考文献
　　[1]中国互联网络信息中心(CNNIC).中国互联网络发展状况统计报告(2008.1)[EB]. http:∥www.cnnic.com.cn,2008-03-02.
　　[2]王汝传,徐小龙,黄海平.智能Agent及其在信息网络中的应用[M].北京:北京邮电大学出版社,2006:10.
　　[3]王俊松,崔世钢.Multi-Agent技术及应用[J].计算机工程与应用,2003,(18):22-2 4.
　　[4]王汝传,徐小龙,黄海平.智能Agent及其在信息网络中的应用[M].北京:北京邮电大学出版社,2006:31-42.
　　[5]王汝传,徐小龙,黄海平.智能Agent及其在信息网络中的应用[M].北京:北京邮电大学出版社,2006:46-69.
　　[6]王伟,王惠荣,刘志强.自动分类模型及算法研究[J].微电子学与计算机,2004,(5) :93-96.
　　[7]陶跃华.基于向量的相似度计算方案[J].云南师范大学学报,2001,(5):17-18.
　　[8]徐宝文,张卫丰.搜索引擎与信息获取技术[M].北京:北京邮电大学出版社,2003:86-94.
　　[9]唐春生,金以慧.基于聚类特性的大规模文档聚类算法研究[J].计算机科学,2002,(9):9-11.