（模式识别与智能系统专业论文）网页内容获取及基于意图的聚类.pdf

北京邮电人学硕l 学位论文 嘲页内容获取和基于意图的聚类 h 冬 ， 北京邮电大学硕士学位论文 网页内容芬取和基于意图的聚类 创新性声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 乏丝；虽 日期： 丝z 旦= ：! 尘 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释： 本人 导师 本学位论文不属于保密范围，适用本授权书。 签名：鹫0 三1 日期：垒巫二五皇_ 一 签名：- ：羔亟童。 日期：2 竺 ：丕! 兰 i i i i v 上0t 嘲页内容获取和基于意图的聚类 网页内容获取和基于意图的聚类 摘要 基于意图的信息检索研究如何针对用户查询意图进行检索结果 的提交，是信息检索智能化的一个热门课题，具有重要的发展前景。 本文针对意图信息检索中的网页内容获取和基于意图的网页聚类进 行研究。主要工作如下： 1 元搜索引擎平台的搭建 本文首先设计并实现了一个对多个搜索引擎检索结果的信息进 行抓取和结构化存储的元搜索引擎，为进一步获取检索结果数据奠定 基础。 2 基于v i p s ( v i s i o n - b a s e dp a g es e g m e n t a t i o n ) 原理的r e b v i p s ( r e g u l a r e x p r e s s i o nb a s e do nv i p s ) 算法模型 本文基于v i p s 技术提出了一种利用正则表达式建立视觉页面同 标签属性关系矩阵的网页内容获取算法r e b v i p s ，实现了网页的结 构化抓取模式，同时通过对属性标签的分析实现了网页噪声干扰处 理。实验表明，该方法具有较好的网页内容获取性能。 3 基于t r ( t o p i cr a n k ) 相似意图网页聚类 本文在总结现有网页意图分类标准和人工评测模型的基础上，采 用t r 特征进行面向网页意图的聚类分析。其中包括： ( 1 )分别采用k - 均值和k 中心聚类算法，分别考察了采用t r 特征与采用一般序列特征的聚类性能。实验表明，基于t r 特征的聚 类比基于通常特征聚类具有更好的意图聚类性能。 ( 2 )比较了所采用的聚类算法中的距离度量对于意图聚类的影 响。通过实验，分析了阂可夫斯基距离度量中p 范数对于聚类结果的 鲁棒性影响。 关键词：意图分析r e b v i p s 页面挖掘k 均值聚类k 中心聚类t r 特征提取v s m v 北京邮电人学硕： 二学位论文 网页内容获取和基于意图的聚类 v l ， 辛 咂bc o n t e n tm i n i n ga n dc l u s t e r i n gb a s e do n i n t e n t i o n a bs t r a c t i n t e n t i o n b a s e di n f o r m a t i o nr e t r i e v a li st oe x t r a c tt h ei n t e n t i o n a c t i v i t yo f i n t e r n e tu s e r sa n di n t e n t i o nt e n d e n c yo ft h ew e bp a g e s i ti st h e h o tt o p i ci ni n t e l l i g e n ti n f o r m a t i o nr e t r i e v a l ，w h i c hh a sa ni m p o r t a n t p r o s p e c tf o ri n f o r m a t i o nd e v e l o p m e n t i nt h i sp a p e r , i tm a i n l yr e s e a r c h e s o nt h ei n t e n t i o no fi n f o r m a t i o nr e t r i e v a li nt h ew e bc o n t e n ta c c e s sa n d i n t e n to fw e b b a s e dc l u s t e r i n g t h em a i nw o r ko ft h ep a p e ri sa sf o l l o w s 1 m e t a s e a r c he n g i n ef o u n d a t i o n t h ef i r s tw o r ki st oa c h i e v et h em e t as e a r c he n g i n e ，w h i c hc r a w l s i n f o r m a t i o nr e s u l t sf r o mm u l t i s e a r c h e n g i n e s a n ds t o r e st h e w e b i n f o r m a t i o na ss t r u c t u r ed o c u m e n t s i tm a k e sf i n es e t t l e m e n t sf o r d e e p e ri n f o r m a t i o nr e s u l t sm i n i n g ，2 r e b v i p sb a s e d o nv i p s ( v i s i o n - b a s e dp a g es e g m e n t a t i o n ) t h er e b v i p sb a s e d o nv i p sa d v a n c e san e wm o d u l eu s i n gr e g u l a r e x p t e s st oc o n n e c tw i t hh t m lt a g sa n dv i s i o ni n f o r m a t i o no ft h ew e b p a g e s m e a n w h i l ei t a c h i e v e sw e b s t r u c t u r em i n i n ga n de l i m i n a t e st h e n o i s ef r o mw e bp a g er e l i e do na n a l y z i n go nh t m lt a g s t h ee x p e r i m e n t s h o w st h a tt h er e b v i p sp o s s e s sw e l lq u a l i t yi nw e bc o n t e n t sm i n i n g 3 i n t e n t i o n b a s e dw e bc l u s t e r i n go fs i m i l a r i t yo nt rm o d u l e t h eo t h e rm a i nw o r ko nt h i sp a p e ri st os u mu pt h el e v e lo f c l a s s i f i c a t i o no fw e bp a g ei n t t e n t i o n sa n dt h ee v a l u a t i o nm o d u l e i tt a k e s t rc h a r a c t e rt oc a r r yt h r o u g ht h ec l u s t e r i n ga n a l y z i n gb a s e do nw e b p a g e si n t e n t s t h ed e t a i li sa sf o l l o w s ： ( 1 ) o u rm e t h o dt a k e sk - m e a n sa n dk - c e n t e ra st h em a i nc l u s t e r i n g a l g o r i t h m sf o rt h ec l u s t e r i n gm o d u l er e s p e c t i v e l y a n dt h ee x p e r i m e n t s c o m p a r et h et rc h a r a c t e r sa n dc o m m o nc h a r a c t e r sf r o mt h et e x t so fw e b p a g e s t h er e s u l ts h o w st h a tt h ec l u s t e r i n ga l g o r i t h mb a s i n g o nt r c h a r a c t e r sp e r f o r mb e t t e rt h a nt h ec o m m o nc h a r a c t e r si ni n t e n t i o nm i n i n g o nw e bp a g e 北京邮电大学硕卜学位论文 网页内容扶取和基于意图的聚类 ( 2 ) a tm a i nw h i l e ，t h ep a p e rm a k e sa c o m p a r i s o nb e t w e e nt h e e v a l u a t i o no f c l u s t e r i n gd i s t a n c e i nd i f f e r e n t c l u s t e r i n gm e t h o d s i t a n a l y s e st h ei n f l u e n c eo fp - f a c t o ri nt h er e s u l t so f c l u s t e r i n g k e yw o r d s ：i n t e n t i o n - a n a l y z e ，r e b v i p s ，w e b m i n i n g ，k - m e a n s ， k c e n t e r , t r c h a r a c t e re x t r a c t i o n ，v s m _ u 叩 北京邮电人学硕士学位论文嘲页内容获取和基于意图的聚类 密级：保密期限： 摘要 a b s t r a c t 目录 目录 i v v 第一章 引言 1 1 研究背景和研究意义l 1 2 研究现状2 1 2 1 元搜索引擎平台的研究现状2 1 2 2 网页挖掘的研究现状4 1 2 3 基于意图的文本聚类之研究现状_ 5 1 3 t 作内容与内容安排6 第二章网页内容获取 。9 2 ij ；l 言9 2 2 元搜索引擎平台9 2 2 1 元搜索引擎概述9 2 2 2 元搜索引擎需求规定。：9 2 2 3 开发语言和运行环境l l 2 3v i p s 算法l3 2 3 1 传统网页挖掘概述1 3 2 3 2 v i p s 算法介绍1 3 2 3 3基于正则表达式的v i p s 算法一r e b v i p s 模型1 5 2 4 数据获取实验2 0 2 4 1实验原理概述2 0 2 4 2实验结果分析2 0 2 5 小结2 3 2 5 1 本章总结一2 3 2 5 2待改进的工作2 3 第三章基于意图的网页聚类分析 2 5 3 1 引言2 5 3 2 意图分析2 5 3 2 1 意图分析的相关理论2 5 i x 北京邮电大学硕j 二学位论文 网页内容获取和基于意图的聚类 3 2 2 网页的意图倾向分析。2 7 3 3 聚类分析2 9 3 3 1 聚类技术介绍2 9 3 3 2 基于层次的聚类算法2 9 3 3 3 基于划分的聚类算法3 l 3 4 基于t r 特征选择的聚类实验3 5 3 4 1 实验准备。3 5 3 4 2 实验结果比较分析一4 0 3 5 小结4 3 3 5 1 本章总结4 3 3 5 2 待改进工作。4 3 第四章结论与展望 4 1 论文总结4 4 4 2 研究展望4 4 参考文献 致 射。 攻读学位期间发表的学术论文目录 x 5 1 北京邮电大学硕十学位论文网页内容获取和基于意图的聚类 1 1 研究背景和研究意义 第一章引言 在过去3 0 年中，信息检索【l 】领域已经得到了发展和壮大，并且超越了标引 文本和在某一集合中检索出有用信息的最初目标。近些年来，随着互联网的发展 以及信息的爆炸性增涨，信息检索已经成为现在互联网发展的一个核心课题。 早期的信息检索主要是通过手工检索的方式，它来源于图书情报【2 】的索引和 查找，应用在图书馆的参考咨询和文摘索引上。到2 0 世纪4 0 年代，信息检索经 过一个世纪的发展，已经成为图书馆不可或缺的工具和用户服务项目。此时的信 息检索更多的还是依靠手工编辑目录。 计算机检索【3 1 阶段是利用计算机实现自动化处理，在2 0 世纪6 0 8 0 年代， 计算机检索形成并发展。随着计算机技术的不断发展，包括高性能，高处理能力 的计算机的出现，计算机技术在信息检索领域的应用也是逐步提升，计算机与信 息检索理论也逐步紧密结合，形成完整的信息检索系统。同时，信息处理技术、 通信技术、数据库存储技术 3 】的发展也进一步推动了信息检索的发展。 随着信息检索面向海量网络信息，信息检索面临着巨大的挑战，其中首要的 就是如何使用户基于简单查询就可以在大规模数据中快速获取自己想要的信息。 这方面的研究已经成为当前信息检索的热点。 一般的检索首先通过进行网页内容与检索词的匹配查找满足条件的所有页 面，比如，用户输入检索词“苹果 ，那么所有包含“苹果”的页面都被找到( 显 然其中有作为电脑的苹果，也有作为水果的苹果) 。然后，检索系统依据某些因 素来排序这些页面并按这个次序向用户提交结果，在目前的研究中，这些排序因 素包括匹配程度、权威程度等等。 而实际上，对用户而言，返回的网页是否能满足此次搜索的意图才是最重要 的：比如，假设用户输入搜索词“苹果”，希望得到关于苹果营养价值的信息， 当返回结果中排序靠前的页面均为苹果电脑的网页时，显然不能满足用户的这一 搜索意图。不可否认，有的用户是通过输入苹果找到节果电脑的信息，这种情况 下，上述搜索结果可以满足用户需求。这也恰恰表明，单纯通过把一些关于作为 水果的苹果网页排在前面的话也是不行的，因为这时显然是不能满足后面这一类 用户的需求。如何使具有两种不同搜索意图的用户即使在使用相用搜索词时也能 快速进入满足搜索意图的网页中( 本文也使用基于意图的检索来指该问题) ，是目 前研究的一个重点。这个问题的解决对于提高用户检索效率、提高检索的个性化 水平都具有重要价值。 北京邮电大学硕二t 学位论文 网页内容获取和基于意图的聚类 本文将在此项研究中开展工作，重点包括两个方面的内容：其一是网页内容 获取研究。获取网页内容是进行下一步意图分析的必要基础：其二是基于获得的 网页内容进行基于意图的聚类重组。在对网页进行基于聚类的重组后，检索结果 就可以依据意图类别提交给用户，这就极大加快了不同用户获取满足其意图的检 索内容的速度。 本章以下首先介绍上述两方面的研究现状，之后介绍本文的研究内容和章节 安排。 1 2 研究现状 首先介绍网页内容获取的研究现状，其次介绍包括基于元搜索的相关网页获 取，最后是对所获得网页的内容的获取。 w e b 信息获取的基本形式有3 种，其中的两个是广为人知且广泛应用的。第 一种是搜索引擎的使用，它标引一部分网络文献作为全文数据库；第二种是w e b 目录，它按主题来对所选择的w e b 文献进行分类。第三种是利用超链接【4 】结构来 检索网络。 对于w 曲文献来说，最流行的格式是h t m l 5 1 ，其次是g i f 和j p g ( 两者都 是图像形式) 、a s c i i 文本和p o s t s c r i p t 。首先，大多数的h t m l 页面不是标准的， 这就意味着它们并不遵守所有的h t m l 的规范。另外，h t m l 页面通常都比较 小，且它们中的大部分都是标识信息。 大多数搜索引擎【6 】抓取网页内容采用了集中式的收集器标引器 ( c r a w l e r - i n d e x e r ) 的结构。收集器进行网页内容获取，它遍历网络，发回新的或者 更新过的网页，然后将发送回的数据存储在主服务器上，并建立索引。搜索引擎 对于网页内容的获取通常是以链接通篇的页面整体保存至本地端，对于不同的网 站建立索引。w e b 目录通常不进行网页内容获取，而是针对某些特定的领域提供 网页的类别、黄页或主题目录等。目录是各种知识的等级分类。 使用超链接搜索网页内容，是建立在每个页面的内容之上的。它是现在网页 获取的主流方式。超链接是属于h t m l 语言的一种特定标记形式，是网页的指 针信息。利用超链接信息获取网页的h t m l 源码是主流搜索引擎爬虫的基本工 作原理。尽管这不是在完全搜索网络，但也是网络挖掘的一个重要手段。 1 2 1元搜索引擎平台的研究现状 元搜索引擎是把一个给定的查询发送到几个搜索引擎、w e b 目录及其他数据 库、并收集和统一结果的一种网络服务器。例如m e t a c r a w l e r t 7 】和s a v v y s e a r c h 8 】 就是元搜索引擎【9 】。元搜索引擎的主要优点是能够将许多信息源的结果结合起 来，用户通过一个公共界面将相同的查询提交给各个不同的信息源。 2 北京邮电大学硕上学位论文网页内容获取和基于意图的聚类 元搜索引擎分为并行处理式和串行处理式两大类【1 0 1 。并行处理式元搜索引擎 将用户的查询请求同时转送给它调用链接的多个独立型搜索引擎进行查询处理， 串行处理式元搜索引擎将用户的查询请求依次转送给它调用链接的每一个独立 型搜索引擎进行查询处理。 元搜索引擎是用户同时利用多引擎进行网络搜索的中介。检索时，元搜索引 擎根据用户提交的检索请求，调用源搜索引擎进行搜索，对搜索结果进行汇集、 筛选、删并等优化处理后，以统一的格式在同一界面集中显示。元搜索引擎虽没 有网页搜寻机制，亦无独立的索引数据库，但在检索请求提交、检索接口代理和 检索结果显示等方面，均有自己研发的特色元搜索技术支持。如提交检索请求时， 根据源搜索引擎的特点和技术参数，指定优先顺序，并对检索时间、检索结果数 量进行控制；作为若干源搜索引擎的检索接口代理，元搜索引擎必须具有较强的 字符和语法转换功能，使用户的检索请求为各具语法特点的不同的源搜索引擎所 人知和接受；而对检索结果的显示，不同的元搜索引擎有不同的处理技术，由 于元搜索引擎设定的检索结果排序依据、最大返回结果数量、相关度参数及优化 机制等不同，调用相同的源搜索引擎的不同元搜索引擎显示检索结果的数量多 少、排序先后、结果信息描述选择亦有较大差异。 一款理想的元搜索引擎应该具备以下特点和功z 日匕v - 【l o 】：第一，含盖较多的搜索 资源，可随意选择和调用源搜索引擎；其次，具备尽可能多的可选择功能，如资 源类型( 网站、网页、新闻、软件、f t p 、m p 3 、图像等) 选择、返回结果数量 控制、结果时段选择、过滤功能选择等；第三，强大的检索请求处理功能( 如支 持逻辑匹配检索、短语检索、自然语言检索等) 和不同搜索引擎间检索语法规则、 字符的转换功能( 如对不支持 n e a r 算符的搜索引擎，可自动实现由 n e a r 向 a n d ”算符的转换等) ；第四，详尽全面的检索结果信息描述( 如网页名称、 u r l 、文摘、源搜索引擎、结果与用户检索需求的相关度等) ；第五，支持多种 语言检索。 目前运营的元搜索引擎各具特色，功能各有侧重，完全“理想”的尚否多见。 一些元搜索引擎在某些方面较为优秀，而其它功能则欠缺或需改进：如大多元搜 索引擎不支持多语种，尤其是汉语检索；一些元搜索引擎实现检索语法转换的能 力有限，不支持指定字段检索，不能充分发挥各个独立搜索引擎的高级检索功能； 部分元搜索引擎无源搜索引擎列表，用户不能自主选择和调用源搜索引擎；大部 分元搜索引擎仅支持调用a l t a v i s t a 1 1 j 、e x c i t e 、g o t o c o m 、y a h o o ! 、i n f o s e e k 、 l y c o s 等常用的搜索引擎，一些大型搜索引擎如n o r t h e m l i g h t 、h o t b o t 等被排除 在外，人为地限制了搜索资源的利用；在检索结果上，元搜索引擎只能返回十几、 数十条“相关度”较高的结果，大量可能有价值的源搜索引擎的检索结果被忽视， 3 北京邮电大学硕 ：学位论文网页内容获取和基于意图的聚类 影响检索结果的全面性【i2 1 。元搜索引擎的功能受着源搜索引擎和元搜索技术的双 重制约：一方面，源搜索引擎的各具特色的强大功能在元搜索引擎中受到限制而 不能充分体现，而另一方面，任何一种元搜索技术都不能发掘和利用源搜索引擎 的全部功能。 1 2 2网页挖掘的研究现状 网页的高速和无序增长，使整个互联网的信息资源缺乏有效的组织和结构。 传统的搜索引擎为用户检索w e b 信息提供了强有力的工具，但是随着互联网的高 速发展，它们越来越难以满足用户的检索需要。 传统的w e b 挖掘主要集中于文本挖掘，即从网页中提取信息w e b 内容挖掘 主要包括文本挖掘和多媒体挖掘两类，其对象包括文本、图像、音频、视频、多 媒体和其他各种类型的数据。这些数据一般由非结构化的数据( 如文本) 、半结 构化的数据( 如h t m l 文档) 和结构化的数据( 如表格) 构成。对非结构化文本进 行的w e b 挖掘，称为文本数据挖掘或文本挖掘，是w e b 挖掘中比较重要的技术 领域。w e b 挖掘中另一个比较重要的技术领域是w e b 多媒体数据挖掘。 目前，关于w e b 内容挖掘的研究大体以w e b 文本内容挖掘为主。w e b 内容挖掘 一般从资源查找和数据库两个不同的方面进行研究。 从资源查找的方面来看，w e b 内容挖掘的任务是从用户的角度出发，怎样提高信 息质量和帮助用户过滤信息。主要是对非结构化文档和半结构化文档的挖掘。非 结构化文档主要指w e b 上的自由文本，如小说、新闻等。w e b 上的半结构化文 档挖掘指在加入了h t m l 、超链接等附加结构的信息上进行挖掘，其应用包括超 链接文本的分类、聚类、发现文档之间的关系、提出半结构化文档中的模式和规 则等。 从数据库的观点进行w e b 内容挖掘主要是试图建立w e b 站点的数据模型并 加以集成，以支持复杂查询，而不只是简单的基于关键词的搜索。这要通过找 到w e b 文档的模式、建立w e b 知识库来实现。 对文本数据进行挖掘的文档分类和模型质量评价方法与传统的数据挖掘方法相 类似，分类算法主要应用朴素贝叶斯( n a i v eb a y e sc l a s s i f i e r ) 1 3 】。对模型的质量评 价主要有分类的正确率( c l a s s i f i c a t i o na c c u r a c y ) 、准确率( p r e c i s i o n ) 和信息估值 ( i n f o r m a t i o ns c o r e ) 。 有许多w e b 挖掘算法，它们搜索w e b 结构，分析网页的链接信息，并通过 对网页结构中的链接地址进行相关度比较，进行权威页面排序。常见的算法有 h i t s ( h y p e r t e x ti n d u c e dt o p i cs e a r c h ) 、p a g e r a l 世1 4 】、发现虚拟社区的算法【婚】、 发现相似页面的算法【1 6 1 、发现地理位置的算法和页面分类算法。w 曲结构挖 掘的算法一般可分为查询相关算法和查询无关算法两类。查询相关算法需要为每 4 北京邮电大学硕士学位论文 嘲页内容获取和基于意图的聚类 一个查询进行一次超链分析从而进行一次值的指派；而查询独立算法则为每个文 档仅进行一次值的指派，对所有的查询都使用此值。h i t s 和p a g e r a n k 分别是查 询相关算法和查询独立算法的代表。 常用的w e b 挖掘算法h i t s 通过对超链接与网页对应提取网页信息资源中页 到页的联系，然后构造页图模型。多数是一种横向的网页内容挖掘模式。基于广 泛链接的算法可以带来很好的结果，但是由于忽略文本内容，网页内容结构，这 种方法也可能遇到一些困难。例如，当中心页面包含多个主题时，h i t s 有时会 漂移。 针对网页内容的纵向挖掘，即对特定语义块的信息获取是一个近来的研究关 注热点。e m b l e y ，j i a n g 和n g 提出了基于d o m 结构的启发式规则。c h a k r a b a r t i 给出了超文本和网络的数据挖掘综述。最早考虑进行标签标记发现信息块的是 l i n 和h o 。通常采用的算法是基于超文本的距离截取模式，即对页面超文本进行 逐层扫描截取，计算标记间的距离，提取页面信息，这种算法是一种线性模型， 也可以成为逐层分割页面。对标记的识别是进行信息提取的关键，然后由于 h t m l 的语法弹性很大，对网页的标签标记准确率往往很低，导致有用信息的提 取难度较大。 1 2 3基于意图的文本聚类之研究现状 基于意图的网页文本聚类就是基于某些特征将具有相同意图的网页聚为一 类。显然，这里所说的基于意图的聚类可以利用通常的聚类算法进行，而要实现 以意图聚类的目标其关键是聚类所用的特征是否能反映文本的意图。 随着网络信息的快速增长，提供一种有效的机制用来组织网络文本、帮助使 用者获得他们想要的信息变得愈加重要。因此，文本聚类技术被广泛研究，文本 聚类一般有以下几个作用： ( 1 ) 文档聚类可以作为多文档自动文摘等自然语言处理应用的预处理步骤， 比较典型的例子是哥伦比亚大学开发的多文档文摘系统n e ws bl a s t 一1 8 】。能将每 天的报文文本进行聚类处理，并按主题进行冗余消除、信息融合等智能处理，为 用户的浏览提供方便； ( 2 ) 对用户感兴趣的文档聚类，能够挖掘用户的兴趣模式以用于信息过滤和 主动推荐等信息服务。对搜索引擎返回的结果进行聚类，然后按目录树的形式提 供给用户，可以使用户快速找到所需要的信息【l 川； ( 3 ) 聚类技术还可以用来改善文本分类的结果或者找出潜在的主题； ( 4 ) 数字图书馆服务。通过自组织映射神经网络等方法【2 0 】，可以将高维空间 的文档结构映射n - 维空间，使得聚类结果可视化和便于理解，如s o m l i b 系统； ( 5 ) 文档集合的自动整理。如对个人邮件进行分类，对个人短信息自动分类 北京邮电大学硕上学位论文网页内容获取和基于意图的聚类 处理等。而微软的j i r o n g w e n 等人则利用聚类技术对用户提出的查询记录进 行聚类，利用聚类结果来更新网站。 文本聚类依据著名的聚类假设：同类文本相似度较大，而不同类文本相似度 较小。作为一种无监督的机器学习方法，它在给定的某种相似性度量下把对象集 合进行分组，使彼此相近的对象分到同一个组内。文本聚类根据文档的某种联系 或相关性对文档集合进行有效的组织、摘要和导航，方便人们从文档集中发现相 关的信息。文本聚类方法通常先利用向量空间模型把文档转换成高维空间中的向 量，然后对这些向量进行聚类。由于中文文档没有词的边界，所以一般先由分词 软件对中文文档进行分词，然后再把文档转换成向量，通过特征抽取后形成样本 矩阵，最后再进行聚类，文本聚类的输出一般为文档集合的一个划分。其形式可 以是一个层次结构( 女 i a h c 算法【2 1 1 ) 或者二维平面图( 如s o m 神经网络) 。 聚类由于不需要训练过程，以及不需要预先对文档手工标注类别，因此具有 一定的灵活性和较高的自动化处理能力，已经成为对文本信息进行有效地组织、 摘要和导航的重要手段。 信息检索不断发展的今天，人们已经不再满足于高效的快捷的检索结果，而 是需要个性化，兴趣化的检索结果满足人们对信息的更加合理更加人性化的需 求。 1 3 工作内容与内容安排 本文的工作内容包括： 首先搭建一个元搜索引擎平台，将百度、谷歌搜索引擎得到的网页作为搜索 结果。之后，基于上述获得的网页进行网页内容挖掘。本部分主要采用v i p s 算 法对网页的内容结构进行挖掘，采用视觉模块与标签属性对应的挖掘模式。最后， 通过对网页文本的意图特征进行网页的意图聚类，并通过实验考察各种因素对聚 类性能的影响。 本文采用的系统框图如下图所示： 6 北京邮电大学硕上学位论文 网页内容获取和基十意图的聚类 一 ( ，麓 潆一 图1 - 2 网页内容获取和意图聚类的系统框架设计 首先，用户通过界面查询将检索词提交给元搜索引擎系统。元搜索引擎将检 索词提交给搜索引擎并将返回的结果进行网页内容挖掘和结构化存储，形成结构 化文本集。之后，系统对结构化文本进行文本处理和v s m 文本向量化1 2 引。系统 通过第二模块对文本信息进行去噪、分词、词性标注和意图特征提取。v s m 模 型也是通过意图的特征提取进行文本向量化工作。最后，通过基于意图特征的文 本距离和文本排序考察网页的意图聚类效果，并对意图聚类结果进行系统测试。 将测试结果返回给用户。整个系统框架流程大致如此。 本文的内容安排分为四章，第一章为引言，简要概述了本文的研究背景、研 究意义和研究现状。简述了本文的研究内容和章节安排。 第二章为网页内容获取，通过元搜索引擎平台搭建，利用v i p s 算法进行网 7 北京邮电大学硕二e 学位论文嘲页内容获取和基于意图的聚类 页抓取，完成网页数据的获取和结构化处理。这是本文的核心之一。 第三章是基于意图的网页聚类分析，通过对用户的意图分析，提取反映用户 意图的特征信息，通过无监督的聚类方法对文本进行聚类，并对实验结果进行分 析。这是本文的另一核心内容。 第四章是对全文进行归纳总结，对页面内容挖掘的已有方法和新方法进行比 较分析，对意图特征聚类方法和一般特征聚类方法进行比较。最后对课题研究方 法进行问题分析和前景展望。 北京邮电人学硕士学位论文网页内容获取和基于意图的聚类 ，) 1 己i 吉 二1jl 口 第二章网页内容获取 随着互联网的迅猛发展，如今我们面对的是一个包罗万象的网络世界，网络 信息的海量性和丰富性，使得如何获取网页信息成为一个非常重要的课题，对于 基于意图的信息检索而言，我们更希望去从大量的丰富的信息资源中发掘出和人 们意图相关的各种信息资源。网络内容获取是数据挖掘技术在信息社会下新的挑 战。 2 2 元搜索引擎平台 2 2 1元搜索引擎概述 对于基于意图的信息检索课题，建立元搜索引擎是较好的选择。 首先，无需担心庞大的网页数量，元搜索引擎不需要抓取庞大的页面、建立 庞大的索引来完成检索。 其次，数据信息的多样性。因为抓取的是多个搜索引擎的数据信息，数据的 丰富和多样性可以很好的保证意图的相对多样和实验效果。 第三，高效性。利用搜索引擎的a p i 接口和数据挖掘方法，我们抓取搜索引 擎返回的信息结果，无需利用深度优先算法而造成较大的时间复杂度。 最后，便于后期的数据分析。将元搜索引擎的结果统一存放于自行设计的数 据库或结构化文本，这样更有利于后期的研究。 元搜索引擎设计采用工厂模式的软件工程设计，将需要抓取的搜索引擎统一 写成接口模式，方便模块间的调用和用户界面配置。整个系统按功能分为三个主 要部分：核心抓取模块、数据封装模块、网络通信模块。各模块间以接口方式进 行数据调用，同时各模块可以进行单独管理和二次开发，便于w e b 工程管理。 2 2 2 元搜索引擎需求规定 元搜索引擎平台部分需求： 元搜索引擎的建立框架图如下所示： 9 北京邮电大学硕十学位论文 网页内容获取和笨于意图的聚类 图2 1 元搜索引擎框架 根据图2 1 框架图标示，基于意图信息检索的元搜索引擎实现了数据的模块 化设计和便捷的接口调用。 核心模块c o r e ： 核心模块封装在m e t a s e a r c h c o r e 的j a r 包中，进行实际实验的搜索引擎包括 百度、g o o g l e 、a s k ，如果需要其他搜索引擎接口，可直接通过添加 m e t a s e a r c h c o r e s e a r c h n a m e 可将其他搜索引擎直接配置到元搜索平台工程中 去。然后对此搜索引擎进行模块开发。 这里核心模块需要进行判断，如果通信模块将数据流输入，则核心模块只负 责进行r e b 模型的v i p s 视觉模块解析抓取；如果通信模块得到搜索引擎的a p i 接口，就直接对有用数据进行数据封装操作。 通信模块n e t ： 主要完成h t m l 的解析和h t m l 响应请求，把源码作为输入流提交给核心 模块。 数据封装模块i o ： 1 0 北京邮电大学硕- 上学位论文网页内容获取和幕于意图的聚类 数据封装模块，完成核心抓取任务的数据保存和信息结构化处理，主要将抓 取数据作为输出流按标签结构保存到数据库或保存成制定的结构化文本形式。数 据封装模块也可以利用其他形式进行数据的保存并且可以进行功能扩充而不用 过多修改源码本身。 各个模块间相互独立，便于维护、修改、扩展和建立相应的w e b 工程；模 块也可以单独作为j a r 包进行后续的研究分析处理。 2 2 3开发语言和运行环境 基于意图信息检索的搜索引擎平台，为了方便高效的抓取和保存搜索引擎数 据，平台的环境参数如下表所示： 表1 ：元搜索引擎平台的各项参数配置需求 m e t a s e a r c h 元搜索弓l 擎平台 开发工具 m ye c l i p s e 软件环境 w i n d o w ss e r v e r2 0 0 3 开发语言j a v a 硬件环境i b m 服务器 数据库 m y s q l 运行环境 t o m c a t 6 0 ， 北京邮电大学硕：l ：学位论文 网页内容获耿和基于意图的聚类 检索界面和运行结果界面如下图所示： 蟊霉二二0 。：。_ 一j ：_ ：? *+ ：+ j 一_ jj ij ? ：一t i _ _ “一j i 一笺 镩拙# 嘲h ；能# 嘲嘲謦期略秘簟，# 鞔；耘，p 确嘲够i _ 麓*， 图2 - 2 ( a ) 元搜索引擎界面 罢。二o 。：一“。+ ，”_ 爱一”：、篇，芦7 璎_ 。，。，i j ，! “e = ：= = = = ：二罐 骥张自瞬h # b 自* 舟 一一：。 ：。 ：z “ ，：，、”：”：“，：1 鼍 图2 - 2 ( b ) 搜索结果展示页面 通过元搜索引擎平台的搭建，我们可以实现定时定量的从搜索引擎获取数据 源，这样就为后续的分析网页提供了可靠保证。 1 2 北京邮电人学硕士学位论文 嘲页内容获取和基于意图的聚类 2 3v i p s 算法 2 3 1传统网页挖掘概述 与传统的纯文本相比，w e b 页面有更多结构。w e b 页面的源码认为是半结构 化数据，即h t m l 语言构成的文档对象模型。它的基本结构是d o m 2 3 ( d o c u m e n t o b j e c tm o d e l ) 。w e b 页面的d o m 结构是一种树结构，页面中每个h t m l 标签 对应于d o m 树的一个节点。w e b 页面实际上是被一些预定义的标签分割成片段。 而通常来说，大部分有用标签如 ( 段落) 、 ( 表) 、 列表、 - - ( 标 题) 等可以视为块标签集合元素。 正因为网页超文本存在着这样的标签属性，早期的页面挖掘通常是利用这样 简单标签，通过距离查找的方式进行页面内容挖掘。按照h t m l 2 4 】文本规范， 网页的内容通常如下列格式： lh t m ll ( i t m l 雏毒纛t it l 謦 ，耄l t l 静| c ，舞毋罩 貉霸露爹 爹，争 麓妻攀，t 童簟 t a b l e ，t 量基o 图2 - 3h t m l 结构 如图2 3 所示，我们可以很明显看到每个标签都有开始符和结束符，所以传 统的网页挖掘模式就是把开始符和结束符作为距离截取的标志进行页面内容挖 掘。 2 3 2v i p s 算法介绍 由于h t m l 语法的弹性很大，而且w 曲页面的标准发展也是经历一个漫长 的过程，许多w e b 页面并不遵守w 3 ch t m l 规范，所以导致计算抓取内容的距 离往往出现偏差，从而最终导致无法准确抓取网页内容信息。往往真正的抓取意 图不能实现。此外，d o m 树最初是为了浏览器中的表示，而不是为了w e b 页 面的语义结构描述引进的。例如，即使d o m 树中两个节点具有相同的父节点， 在语义上，这两个节点内容未必比其他节点更语义相关。 北京邮电大学硕f ：学位论文 嗍页内容获取和基十意图的聚类 图2 - 4 d o m 结构 从人的感观上来说，人们总是将一个w e b 页面看作不同的语义对象，而不 是单个的整体。研究表明，用户总是希望w e b 页面的一定功能块出现在w e b 页 面的一定位置上。实际上，当w e b 页面呈现给用户时，表现的是一种多媒体属 性而并非是简单的纯文本形式，空间和视觉线索能帮助用户下意识地基于这样的 观察，我们也可以开发基于空间和视觉信息提取w e b 页面内容结构的算法。 基于视觉的页面分害l j ( v i s i o n b a s e dp a g es e g m e n t a t i o n , v i p s ) 算法【2 5 】。v i p s 算 法旨在基于页面视觉表示提取w e b 页面的语义结构。这种语义结构是树结构： 树中每个节点对应于一块。每个节点将赋予一个值( 凝聚度) 指明基于视觉块中 内容的凝聚程度。v i p s 算法全部利用页面的布局特征。 首先，从h t m ld o m 树中提取所有合适的块，然后找出这些块的隔离物。 这里，隔离物是w e b 页面中的水平线或垂直线，在视觉上不与任何块相交。基 于这些隔离物可以构造w e b 页面的语义树。一个w e b 页面可以表示成块( 语义 树的叶节点) 的集合。与基于d o m 的方法相比，由v i p s 得到的分割聚集了更 多的语义信息。由于噪声信息，如导航、广告、修饰等，经常放在页面的特定位 置上，所以很容易去除。具有不同名词的内容区分为分离的块。 图2 5 描述了v i p s 算法的过程 1 4 北京邮电大学硕十学位论文 网页内容获取和基于意图的聚类 吟匾! 口 够喾 目 0 心 n o v i s i o n - b a s e dc o n t e n t ss t r u c t u r e , ls e g m e n t a t i o n lo