第5卷第2期 智能系统学报 Vol.56.2 2010年4月 CAAI Transactions on Intelligent Systems Apr.2010 doi:10.3969/j.issn.16734785.2010.02.003 Web页面信息主动检索模型 袁鼎荣12，钟宁 (1.北京工业大学国际WIC研究院，北京100022；2.广西师范大学计算机科学与信息工程学院，广西柱林541004) 摘要：单个页面信息量远远大于特定用户对页面中的信息需求.为快速准确从当前页面中获取特定用户所需求的 兴趣信息，提出了页面信息主动检索模型.该检索模型中，根据页面Block特点将当前Wb页面转化成信息树，根据 用户过去的浏览行为构造用户特征树，挖掘用户特征树产生用户需求信息集，然后从当前页面中检索需求的信息， 获取用户兴趣信息集.详述了主动检索的基本原理，给出了相应的算法描述，并通过实验证明了该模型具有可行性。 关键词：页面Block;页面信息树；用户特征树；主动检索 中图分类号：TP301.6文献标识码：A文章编号：16734785(2010)02011205 Initiative retrieval of web information YUAN Ding-rong'2,ZHONG Ning' (1.The International WIC Institute,Beijing University of Technology,Beijing 100022,China;2.College of Computer Science and Information Technology,Guangxi Normal University,Guilin 541004,China) Abstract:The information capacity of a single web page is far more than the needs of any individual user.The goal of the authors was to construct a discriminative means for retrieving individualized web page information.Such a model could allow fast and precise retrieval of information from current pages,tuned as required by particular indi- viduals.The approach of the researchers was to begin by transforming a web page into an information tree in light of the block characteristics of the web.Next,a user characteristics tree was constructed from user behavior seen in previously browsed pages.This was mined to get information needed about the user.Based on this,elements inter- esting to the user were retrieved from current pages.The basic principles of discriminative retrieval were intro- duced,several retrieval algorithms described,and the model's feasibility experimentally verified. Keywords:Web Block;page information tree;user especial tree;initiative retrieval 信息检索是指依据一定的方法，从已经组织好 数据库查询还是富有挑战性的Wb信息检索都是 的大量的信息集合中，查找并获取特定相关信息的以搜索引擎为中心，当用户提出检索要求时，搜索引 过程.传统意义上的信息检索由用户、搜索引擎和数 擎才依据用户要求检索后台数据，最后将检索结果 据集组成.以引擎为中心，由搜索引擎根据用户的信。 返回给用户.随着Wb技术的发展，网络应用的普 息需求展开检索，然后将索引结果反馈给用户，搜索 及，网络信息资源急剧增长，页面信息的无限性与 的数据源包括关系数据库、文本数据集和Wb上的 用户接受信息的有限性的矛盾日益突出.尤其手机 多媒体数据.这种检索技术在关系数据库和文本数 用户接人Internet后加剧了这种矛盾.因此如何从 据集的查询检索中取得了良好的应用.不管成熟的 当前页面中快捷准确地发现特定用户潜在兴趣的有 限信息集成为新的应用挑战，为解决这种矛盾提出 收稿日期：2009-1204. 基金项目：国家自然科学基金重大研究计划资助项目(90718020)：澳 一种称为主动检索的检索模型，即搜索引擎根据用 大利亚ARC资助项目(Australian Research Council Discov- ery Grant,DP0667060). 户特征，自动产生检索条件，主动检索当前页面，提 通信作者：发鼎荣.E-mail:duan@mailbox.gnu.edl.cn. 取用户潜在兴趣的页面信息反馈给用户
第2期 袁鼎荣，等：Wb页面信息主动检索模型 ·113· 1相关研究背景 解析成树中的节点，最后通过解码器将解析的结果 以语法树的形式输出，内存中生成DOM标记树，实 1.1DOM树 现对整个文档的全面的、动态的有层次的访问，每一 DOM即document object model,它是W3C推荐 个网页对应一个DOM标记树 的用于访问诸如XML和XHTML文档的标准.DOM 1.2页面Block树 把XML和XHTML文档视为一棵树，文档中的各组 页面Block是页面中在内容或显示上独立的、 成部分定义为一个节点，节点主要包括元素节点、属 闭合的矩形区域.Wb页面可以分割为若干个互不 性节点和文本节点等，这棵节点树展示了节点的集 相交的Block,把这个过程称为页面Block分区.一 合，以及它们之间的联系，从根节点开始，然后在树 个Block可以由多个相互不重叠的子Block组成，如 的最低层级向文本节点长出枝条，节点之间的父子 图1(a)为Web页面，图1(b)为对应页面的Block 关系表示标签在页面之中的嵌套关系，兄弟关系表 分区，图1(c)为依据图1(b)的分区结构和层次所 示了标签在页面中的并列关系，这样在使用DOM 对应的树形结构，称为Block树. 树进行Wb页面解析时，将所有的页面中的元素都 VBI 1 VBI_3 VB221 iVB23I日 VB222 :VB2 11 VB223 -.VB22 NB232 VB212 VB2 1 0 VB2 3 VB3 VB4 (a)Wcb负面 (b)对应页由的Block分区 Web_Page VBI VB2 VB3 VB4 VBI_1VBI_2 VB2_1 VB2_2 VB2_3 VB2 11 VB2_1_2 VB2 2 1VB2 2 2VB2_2_3 VB2_3_1 VB2_3_2 (c)Block树 图1页面分区和页面Block树的示例 Fig.1 The example of page subarea and Web Block tree 分区级别表示该分区产生的Block树的最大深Layout表示网页的布局 度，用Level表示.选择合适的分区级别有助于得到 1.3页面结构分析 最理想的分区结果.Blok可以定义成一个由主题、 DOM提供了树形结构的页面模型，可以基于 内容组成的二元组：Block=,其 DOM来建立Block树，由于HTML语法的灵活性， 中，topic为Block主题，content为Block内容.用 很多Web页面并不完全遵守W3C的HTML规范
·114 智能系统学报 第5卷 依据DOM的分区只能代表布局结构独立的区域而 2)Domtree=xlmparser(xml file);/将xml文 不能完全代表语义上独立的区域.比如，同一个父节 件代码解释为一棵文档对象树。 点下面的2个子节点并不一定代表相同的主题，因 3)Blocktree=getblcoktree(html file);/从逻 此，进行页面结构分析时不能完全依赖DOM,还需 辑上将页面分成具有一定等级和关联的Block,并 要考虑其他一些因素.比如借助页面中大量的HT 将其转换成树形结构， ML标签来获取布局和位置信息，如、、、、~等.通 据DOM树和Block树构造初步的Web树 常，显示上独立的区域一般表示相同的主题，Wb 5)Webtree pruning(Webtree); 中提供了大量可见的元素来划分页面，例如字体、颜 6)output Webtree. 色、图像、空白，这些都是页面Block分区算法需要 如图2为一棵Webtree. 考虑的元素， Webtreel 分区过程中，从页面开始，逐级递归分区，抽取 出第n级Block(n初始化为1)，组成深度为n的 Block树，同时保存Layout..然后，判断n是否满足给 4,4 定的分区级别，如果小于该级别，则依次把Block树 中的每个叶子节点Block的内容(content)作为新的 DOM,重新抽取Block并组装n+1级Block树，如果 某个Block已经无法再分割，则忽略这个Block.如 图2页面树 此反复，直到Block树达到给定分区级别为止.对于 Fig.2 Webree 该树有5个儿子结点，代表5个不同的页面板 页面分块的详细规则见文献[14]，这里不再重复. 块，其中A,板块包括2个子版块，A,板块包括3个子 图1(a)例子页面通过3次分区算法迭代，产生 了图1(c)的Block树. 版块 2.2用户特征树 2主动检索模型 定义结点为：node=, Wb页面充斥着形形色色的信息，从信息的表 其中，topic、content对应Webtree中的结点，frequent 现形式来看有文本、动画、声音和视频等；从页面信 为频度，即访问Webtree中相应结点的次数.根结点 息的布局来看，有纯内容页面、目录页面，也有介于 对应特定的用户，如果某用户访问页面中的某一条 两者之间的综合性页面，如新浪、腾讯等50.为简 目，则Webtree中形成一条路径，称为主题路径.由 化起见，以综合性页面为研究对象 特定用户的浏览历史中所记录的主题路径构造用户 在检索模型中，首先对页面数据进行预处理，根 特征树的算法如下. 据页面的Block特点将平面的Wb数据转换为对应 算法2：用户特征树生成算法， 的树，称这种树为Web查询树，简称Web树. nput:visiting path set;/用户访问的路径集 2.1Wb树的建立 Output:clienttree;//用户特征树 首先将HTML代码转换为XML并生成Dom 1)Node open a new node; 树，借助页面分区标记将页面分成逻辑上不同的 2)Path=getpath(visiting item set);/用户访间 Blcok,再结合DOM树将页面信息用树形结构表示， 的路径集取一路径 然后对所获得的树进行清理剪枝，获得Wb树.算 3)If clienttree is NULL Then open a new tree and 法描述如下， label the tree; 算法1：Web树构造算法 4)clienttree=insert(clienttree,path);/根据 nput:html;/输入页面代码文件 用户新的访问记录更新用户特征树，插人时重叠的 Output:Web Tree./输出信息检索树 结点的frequent域加l; l)xml file=htmlparser(html);//将html文件 5)output clienttree. 格式解释为xml代码. 用户特征树是对用户浏览历史进行分析加工所产 生的特定用户的行为特征树，它记录了用户对网络页
第2期 哀鼎荣，等：Wb页面信息主动检索模型 ·115· 面中不同主题、不同板块、不同信息条目的兴趣度 表2用户兴趣主题向量表(N=5) 2.3潜在页面兴趣信息的近似检索 Table 2 Interesting topic vectors table of user(N =5 潜在兴趣信息的检索思想可描述为：当用户启 兴趣主题 频度 动Wb浏览器时，首先根据特征树产生潜在兴趣主 2 题向量集Q=91,92,…,,…,9n}·9:为潜在兴 宁 16 趣主题向量，即用户特征树中的兴趣路径，作为检索 B32 12 条件.然后依据一定规则，计算q:与当前页面树中 9 B型 各路径的匹配程度，依据匹配度高低选取符合兴趣 度要求的页面信息作为检索结果返回给用户 Clienttree 其算法描述如下： 算法3：潜在兴趣信息的检索算法、 B 9 2 input:clienttree,webtree,N; output:InterstingSet; 3 B 5 812 1)O=MiningintrestingPath(clienttree,N);// 从用户特征树中提取用户兴趣信息集。 5 2)T=ExtractItemPath webtree);//webtree 图3用户特征树，该树的3个儿子结点表示用户有3个 中抽取页面信息所在路径. 不同的兴趣主题，分别为B、B2、B 3)nterstingSet={;//初始兴趣信息集为空， Fig.3 UC Tree.There are three son nodes in the tree,which 4)retrieval(Q,T);/从webtree中检索用户 is three different interesting topics B,B,B 潜在兴趣信息集， 设用户访问某主页，该主页所对应的索引树为 For i=1 to IQ I 图2，则该页面的的主题信息向量集为：{A1,A2A21, Forj =1 to I T I A2A22,A3,A4A41,A4A42,A4A3,A5}然后依据式(1)计 算用户兴趣信息向量与页面主题信息向量的近似 ()=87 度，如表3 fsim(q:,T)≥0/0为给定的阈值 表3用户兴趣主题与页面信息向量相似度表 Table 3 Then InterestingSet←-T;/将兴趣路径并入兴 Similarity table between interesting topic and 趣集 webpage information vector 5)output InterestingSet. B3 B Bx B, B 0.100.200.31 0.160.30 3 实验说明 A24 0.80 0.30 0.25 0.22 0.32 0.10 0.41 0.90 0.10 0.10 设有用户特征树如图3，则该用户的主题信息 AAn 0.20 0.42 0.36 0.30 0.20 向量集如表1，如果设置支持度为7则有用户的兴 A.An 0.30 0.320.27 0.23 0.00 趣主题向量集如表2. A442 0.21 0.88 0.32 0.31 0.10 表1用户主题向量表 A4A430.22 0.23 0.22 0.46 0.30 Table 1 Topic vectors table of user A30.180.350.490.260.20 主题向量 颜度 如果给定相似度阈值为0.5，则有：A2A21、 B 16 B.Bi 3 A2A22A4A42是用户潜在兴趣信息项. B.B2 5 B2 9 4结束语 Ba 5 B 27 本文提出页面信息主动检索技术模型，首先给 B3 出主动检索技术的定义，然后依据页面信息的特点 B 12 将Wb页面转化为树形结构，构造页面信息树.通
·116. 智能系统学报 第5卷 过用户对页面的访问历史事件构造用户特征树，基 and storing web archive based on page block[J].Journal of 于用户特征树挖掘用户的浏览行为特征，主动产生 Software,2008,19(2):275-290 针对特定用户的兴趣信息集，以该信息集作为检索 [6]CHRISTOPHER D.Introduction to information retrieval 条件，检索信息树达到检索页面信息的目的.该技术 M].England:Cambridge University Press,2009:25-28. [7]CHEN K J,MA Weiyun.Unknown word extraction for Chi- 的发展应用将减少用户从大量繁杂的页面信息中挑 nese documents C]//19th International Conference on 选自己感兴趣的数条或数十条信息的劳累，尤其解 Computational Linguistics.Taipei,China,2002:169-175. 决了手机用户中，页面信息容量大和显示屏幕极其 [8]HOBBS J R.Information extraction from biomedical text 有限的矛盾.该技术的成熟发展需要良好的文本分 [J].Journal of Biomedical Informatics,2002,35(4):260- 类及其文本主题提取技术、页面Blok主题信息的 264. 提取等技术.用户特征树为Wb用户行为特征挖掘 [9]KONGACHANDRA R,KIMPANT C,SUWANAPONG T,et 提供良好的技术支持。 al.Newly-born keyword extraction under limited knowledge resources based on sentence similarity verification J.IEEE 参考文献： International Symposium on Communications and Information [1 ]CAI D,YUS,WEN J R,MA W Y.VIPS:a version-based Technology,2004,21(3):1183-1187. page segmentation algorithm MSR-TR-2003-79 R ] [10]GAO Junbo,LUAN Cuiju,WANG Xiaofeng.New key- [s.1.],2003. word extraction research[J].Computer Engineering and [2]SONG Ruihua,LIU Haifeng,WEN Jirong,et al.Leaming Design,2008,29(3):765-767 block improtance models for web pages[C]//The 13th In- 作者简介： ternational Conference on World Wide Web.New York, 袁鼎荣，男，1967年生，副教授，主 USA,2004:203-211. 要研究方向为文本信息处理、网络智 [3]CAI D,YU S,WEN J R,et al.Block-based Web search 能、机器学习、数据挖掘等.主持或主要 [C]//27th Annual Interational ACM SIGIR Conference on 参与国家或省部级项目4项，发表学术 Information Retrival.Sheffield,UK,2004:456-463. 论文20余篇。 [4]CAI D,YU S,WEN J R,et al.Block-based link analysis [C]//27th Annual Interational ACM SIGIR Conference on Information Retrival.Sheffield,UK,2004:440-447. 钟宁，男，1956年生，教授，博 [5]宋杰，王大玲，鲍玉斌，等.基于页面Blok的Web档 导，主要研究方向为网络智能、知识发 案采集和存储[J].软件学报，2008,19(2)：275-290. 现与数据挖掘、粗糙集(Rough Set)与软 SONG Jie,WANG Daling,BAO Yubin,et al.Collecting 计算、智能Agent技术与应用、脑信息学 等，发表学要论文多篇