（模式识别与智能系统专业论文）垂直检索中的关键问题研究.pdf

垂直检索中的关键问题研究 摘要 本文针对垂直搜索引擎“专 的特点，主要研究了产品层次信息 抽取和用户产品查询扩展两个问题，主要创新工作和成果如下： 第一，提出了基于网页分析的产品层次抽取算法。 该算法挖掘网页上已标注的产品链接附近区域的标签重复规律， 根据d o m 叶子结点的d o mp a t h 进行编码，并找出编码序列的最优 重复子串，统计重复子串连续覆盖的区域，将己知网页上的产品链接 ( p r o d u c t - u r l s ) 进行深层次聚类，并找到该类别的名字。 该方法在安全类产品领域网站构成的测试集中，产品链接聚类正 确率达到7 1 o ，( 类别) 命名正确率( 在聚类正确的基础上) 达到 7 7 3 。 第二，提出了基于概念格的产品优先的查询扩展算法。 信息检索中的“文档特征词 关系能够很自然的被看作形式概 念分析中的形式背景。因此，在文本处理中，文本作为实例，描述文 本的关键词作为属性，就构成了形式背景，从而建立概念格。考虑概 念格中的不同“概念结点 的距离，获取查询扩展词汇，并结合产品 层次，就给出了基于概念格的产品优先的查询扩展。 。 该方法在测试中展现出了良好的查询扩展性能，辅助用户精确定 位所需信息。 第三，本文给出一种小型检索系统的设计方案及实现。 该系统适用于各种信息检索领域的相关研究，使得个人能够在有 限的硬件资源下，最大限度地模拟信息检索平台。 其中，第一部分属于预处理，第二部分是本文的核心，第三部分 从工程上实现系统。 关键词：垂直搜索引擎概念格网页分析产品层次查询扩展 r e s e a r c ho ns e r a lk e yi s s u e si n r t i c a ls e a r c h a b s t r a c t f o rt h es p e c i a l t yo fv e r t i c a ls e a r c he n g i n e , t h i sp a p e rd e a l s1 ) l ，i lp r o b l e m so f p r o d u c th i e r a r c h y e x t r a c t i o na n dp r o d u c t - o r i e n t e dq u e r ye x p a n s i o n t h em a i n i n n o v a t i o nc o n t r i b u t i o n so ft h i sp a p e ra r el i s t e db e l o w ： 1 t h i sp a p e rp r o p o s e sa na l g o r i t h mo fp r o d u c th i e r a r c h ye x t r a c t i o nb a s e do n p a g ea n a l y s i s t h i sa l g o r i t h mi sa i m e da td e t e c t i n gr e p e a t i n gp a t t e r n sf r o me n c o d e d p a t t e r ns t r i n ga c c o r d i n gt o t h en o d e sd o m p a t hf r o ml e a ft or o o t a n dt h e nw e c l a s s i f yp r o d u c t - u r l si n t os e v e r a lc a t e g o r i e s f i n a l l yw ep i c kan a m ei nt h ep a g ef o r e a c hc a t e g o r y w eg o ta na c c u r a c yo f7 1 i nc l u s t e r i n ga n da l la c c u r a c yo f7 7 3 i n n a m i n g 2 t h i sp a p e rp r e s e n t san o v e lm e t h o db a s e do nc o n c e p tl a t t i c ew h i c hc a l lg i v e u s e rq u e r ye x p a n s i o n i ni n f o r m a t i o nr e t r i e v a l ，t h et e r mo fd o e - k e y w o r d sr e l a t i o nc a n b er e g a r d e da st h ec o n t e x ti nf o r m a lc o n c e p ta n a l y s i s t h u s ，ad o c u m e n tr e p r e s e n t s a l lo b j e c ta n di t sk e y w o r d sr e p r e s e n ta t t r i b u t e s ，a n dac o n c e p tl a t t i c ec a l lb e c o n s t r u c t e d a c c o r d i n gt ot h ed i s t a n c eb e t w e e nc o n c e p tn o d e s i nac o n c e p tl a t t i c ea n d t h ep r o d u c th i e r a r c h i e s ，w ec a ng e tp r o d u c t - o r i e n t e dq u e r ye x p a n s i o n s t h er e s u l t s h o w st h a tu s e r sf i n dap i e c eo fi n f o r m a t i o nb e c a m em o r ec o n c i s e l ya n dq u i c k l y 3 t h i sp a p e rp r e s e n t sas m a r ti n f o r m a t i o nr e t r i e v a ls y s t e m b a s e do nt h i ss m a r t s y s t e m , p e o p l ec a l ll e a dt h e i rr e s e a r c h e sm o r ee a s i l yi nap e r s o n a ll a b p a r t1i st h ep r e p r o c e s s i n gs t e p ，p a r t2i st h ek e r n e lm o d u l eo ft h ep a p e r , a n dp a r t 3i st h ee n g i n e e r i n gi m p l e m e n t k e yw o r d s ：v e r t i c a ls e a r c he n g i n e , c o n c e p tl a t t i c e , p a g ea n a l y s i s ，p r o d u c t h i e r a r c h y , q u e r ye x p a n s i o n 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论 本人签名： 处，本人承担一切相关责任。 日期：星生蒸：翌兰：2 2 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：鱼塑日期：逊：里主：2 皇 一 导师签名：2 弩卜骂一日期： 加莎；2 乙 北京邮电丈学硕士学位论文垂直检索中的关键问题研究 1 1 垂直信息检索 第一章绪论 当今社会已经进入了网络信息时代，计算机与网络信息技术的飞速发展使得 各个领域的数据和信息急剧增加，并且由于人类的参与使数据与信息系统中的不 确定性更加显著( 复杂系统) 。如何从大量的、杂乱无章的、强干扰的数据( 海量 数据) 中挖掘潜在的、有利用价值的信息( 有用知识) ，这给人类的智能信息处理 能力提出了前所未有的挑战。 近年来，i n t e m e t 正以令人难以置信的速度在飞速发展，越来越多的机构、 团体、个人在i n t e m e t 上发布信息、查找信息，但由于w e b 是无结构的、动态的， 人们要想找到自己想要的数据犹如大海捞针一般困难。解决问题的一个途径就是 将传统的数据挖掘技术和w e b 综合起来，进行w e b 挖掘口2 1 。 “什么是信息检索? 信息检索( i n f o r m a t i o nr e t r i e v a l ) 是从结构化的文档集 中找出与用户需求相关的信息，与数据库系统不同，信息检索研究的主要不是结 构数据的查询和事务处理的问题，而是研究大量文本文档的信息组织和检索。它 处理的对象是非结构化数据，主要有文本数据( 新闻、科技论文等) 、网页( h t m l ， 捌l ) 、多媒体数据( 图像、视频、图形、音频) 。典型的信息检索问题是基于用户 的输入定位相关的文档，典型的信息检索系统有联机图书馆目录系统和联机文档 管理系统。 信息检索通常是指从以任何方式组成的信息集合中，查找特定用户在特定时 间和条件下所需信息的方法与过程，完整的信息检索含义还包括信息的存储。 信息检索的实质是将描述特定用户所需信息的提问特征，与信息存储的检索 标识进行异同的比较，从中找出与提问特征一致或基本一致的信息。提问特征是 对信息的需求进行分析，从中选择出能代表信息需求的主题词、分类号或其它符 号。例如，要查找关于“贝叶斯网络在信息检索中的应用方面的信息，根据信 息需求的范围和深度，可选择“贝叶斯网络 和“信息检索 为提问特征。检索 标识是信息存储时，对信息内容进行分析提出能代表信息内容实质的主题词、分 类号或其它符号。例如，在分析、标引、存储有关“贝叶斯网络在信息检索中的 应用方面的信息时，可选择“贝叶斯网络”和“信息检索 作为存储和检索的 北京邮电大学硕上学位论文垂直检索中的关键问题研究 标识。检索时，将提问特征同检索标识进行对比匹配，若达到一致或部分一致， 即为所需信息。 狭义上讲，w e b 信息检索就是w e b 挖掘的一种，o 最初，信息检索的目标是 标引文本，并从集合中找出有用的文档；发展到今天，信息检索研究涉及到建立 模型、文档分类与聚类、用户交互、数据可视化、数据过滤等等。从这个角度看， w e b 挖掘只能作为信息检索过程的一部分。 2 0 0 7 年9 月份发布的( 2 0 0 7 年中国搜索引擎市场调查报告显示，调查的 总体样本中有4 4 7 1 的用户经常使用搜索( 每天多次使用) ，每天都会使用一次 搜索的占到1 7 2 ，这意味着超过6 0 的用户每天都会使用搜索引擎。搜索用户 的搜索频度较高，搜索引擎服务成为最受欢迎的网络服务。归其原因，是它解决 了用户在浩瀚的互联网海量信息中快速定位信息的瓶颈问题。 但是，互联网的信息量呈爆炸趋势增长，海量数据的增加带来的是传统综合 搜索引擎( 又称为水平搜索引擎) ，如百度和g o o g l e 的搜索品质的下降。搜索引 擎在搜集网络信息方面远远赶不上网络信息的增长速度，庞大的网络信息资源使 得搜索变得越来越难以控制。目前，尽管搜索引擎技术的发展日益成熟，但是要 准确、快速地查找到所需要的信息却越来越困难。一是查询的结果集是海量的， 经常是几十万笔的资料，在这些庞大的信息群中，有用的信息只是其中一小部分， 可谓“冰山一角 ，而且，这些搜索结果中存在着大量的重复信息和垃圾信息， 用户很难在短时间内准确地筛选出需要的内容，出现所谓的“认知过载 。二是 目前的搜索引擎都是要求用户严格按照所规定的格式输入查询词，但种种限制使 用户不知道如何确切地表达自己的信息需求，即所谓的“迷航。这些用户需求 和市场服务之间的巨大反差所产生的问题使人们开始呼唤更有针对性的搜索引 擎的出现。 由于通用搜索引擎面向所有的用户，力争在返回结果上做到面面俱到，包罗 万象的结果显然不能满足用户精确搜索的需求。因此，面向专业领域的搜索引擎 即垂直搜索引擎应运而生。与通用搜索引擎不同，垂直搜索引擎的网络蜘蛛只采 集w e b 中的部分信息。通过对网页的主题相关度进行预测和判断，专业网络蜘蛛 在爬行( c r a w l i n g ) 时避开了大量主题无关的区域。由于只采集主题相关的网页， 垂直搜索引擎在查询的准确率和效率上都有显著的提高。 垂直搜索是针对某一个行业的专业搜索引擎，是搜索引擎的细分和延伸，是 对网页库中的某类专门的信息进行一次整合，定向分字段抽取出需要的数据进行 处理后再以某种形式返回给用户。 垂直搜索引擎的应用方向很多，比如企业库搜索、供求信息搜索引擎、购物 搜索、房产搜索、人才搜索、地图搜索、m p 3 搜索、图片搜索几乎各行各业 2 北京邮电大学硕上学位论文 垂直检索中的关键问题研究 各类信息都可以进一步细化成各类的垂直搜索引擎。 在信息爆炸的现代，通过少数几个通用搜索引擎来获取信息已经变得越发艰 难。垂直搜索技术作为解决这问题的强有力手段，已经开始展现出强大的生命力 和市场前景。 1 2 垂直搜索引擎的发展概况 垂直搜索引擎的产生正是有效地解决了综合搜索引擎搜索质量不高的问题。 它为用户提供的不再是成千上万的相关网页信息，而是范围很小，且极具针对性 的具体信息。那么，什么是垂直搜索引擎昵? 垂直搜索引擎( v e r t i c a ls e a r c he n g i n e ) 的定义： ( 1 ) 是指应用于搜索某一学科领域或某一类信息( 如图像、影像) 的专业搜索 引擎，又称为专题搜索引擎、专门搜索引擎，是搜索引擎的细分和延伸。 ( 2 ) 是专为查询某一学科或主题的信息而产生的查询工具，是相对综合搜索 引擎的信息量大、查询不准确、深度不够等提出来的新的搜索引擎服务模式。 ( 3 ) 是以构筑某一专题或学科领域的i n t e r n e t 网络信息资源库为目标，智能 地在互联网上搜集符合这一专题或领域需要的信息资源，能够为包括学科信息门 户、专业信息机构、特定行业领域、公司信息中心、行业专家等等在内的信息用 户，提供整套的网络信息资源开发方案的信息查询与服务的网站。 垂直搜索引擎和综合搜索引擎所采用的基本技术非常相似，主要区别是垂直 搜索引擎利用搜索器只搜索特定的主题信息，并按照预先己定义好的专题有选择 地收集相关的网页。这样一来大大降低了收集信息的难度，提高了信息的质量。 由于所收集的学科领域小，信息量相对较少，因此可采用“专家分类标引的方 法对搜集到的信息进行组织整理，进一步提高信息的质量，建立起一个高质量的、 专业信息收集全、能实时更新的索引数据库。同时，由于垂直搜索引擎只涉及一 个或几个领域，词汇和用语“一词( 一语) 多意的可能性降低，而且可以利用专 业词表进行规范和控制，因此大大提高了查全率和查准率。 下面，通过从信息服务和所采用关键技术这两个方面将垂直搜索引擎和综合 搜索引擎进行比较，从而更加有助于理解二者的区别。 垂直搜索引擎和综合搜索引擎在信息服务上的异同： 垂直搜索引擎和综合搜索引擎虽然都是帮助网络用户进行网络信息定位和 查找的工具，但是二者在进行信息服务的时候还是有很大的不同，这些不同可以 从信息服务的对象、内容等方面加以比较。 ( 1 ) 信息服务对象的比较 3 北京邮电大学硕上学位论文垂直枪索中的关键问题研究 传统的综合搜索引擎提供整个互联网上与用户提问相关的各种网页信息，然 后由用户自己判断结果中的信息哪些是相关的，哪些是不相关的。使用垂直搜索 引擎的用户通常都有明确的信息需求，同时这种信息需求可以界定在某一个特定 范围内，并且满足其信息需求的信息产品是特定形式的结构化的信息，它提供的 结果都是与用户需求相关的，用户不用自己再进行分析和判断。 另外，从对关键字的选择上可以看出两者的差异。垂直搜索引擎对用户关键 字的选择要求很简单，直接输入要查找的产品名称即可得到相关度很高的结果； 而综合搜索引擎则要求用户对自己的信息需求很明确，并且完整、准确的表达在 搜索栏中，搜索引擎才能够提供一定的相关信息，并且要求用户自行对每一个信 息的相关度进行判断。一般说来，综合搜索引擎对用户的要求相对较高，在搜索 的过程中，需要有用户对自己需求的不断调整的过程；垂直搜索引擎对用户的要 求较低，直接输入产品名称即可。 ( 2 ) 信息服务内容的比较 对于搜索引擎来说，它所提供的信息服务的内容就是用户搜索的结果。综合 搜索引擎提供的搜索结果仅仅是网页链接和关于该网页的简单描述，其中匹配的 原则是网页描述与关键字的相关度。而垂直搜索引擎提供的搜索结果是结构化的 数据，几乎不需要用户具体打开网页就可以断定是否是自己需要的结果。 综合搜索引擎是按照系统设定的排序算法，自动根据相关性将网页排列，它 的用户不能自主选择排列方式，只能被动的接受搜索引擎的排列顺序。垂直搜索 引擎的排列方式可以由用户设定，自主的选择按照相关度的高低、按照价格的高 低、价格的范围或网上商店等多种方式进行排序。这一点对用户更好的找到所需 的内容是非常有帮助的。 通过综合搜索引擎所查询的结果往往是数量巨大的，结果覆盖面比较广。而 垂直搜索引擎因为检索的网站数目有限，所以检索结果的数量也维持在几百个左 右。但是，从查准率的角度看，垂直搜索引擎的准确率很高，几乎可以达到9 0 以上因为这些特定的信息都是在特定的相关网站上查找的，所以可以保证它的 准确性但是对于综合搜索引擎而言，因为搜索引擎在广泛的互联网上查找，另 外用户也不可能准确的表达信息需求，所以准确率相对比较低。 综合搜索引擎在搜索结果中提供描述的内容包括标题、描述、u r l 链接三个 部分。其中对网页的描述是非人工干预的( 除了参与了竞价排名广告的网页描 述) ，所以这些描述更多的是当前u r l 链接上的网页整体内容的介绍，而不是针 对用户检索的特定信息的介绍。垂直搜索引擎在搜索结果的描述针对性很强，从 多个角度描述用户查找的特定信息。比如对某个产品信息的产品名称、价格、图 片、规格参数等等都在搜索结果中实时体现这样，用户几乎不需要点击链接就 4 北京邮电大学硕士学位论文垂直检索中的关键问题研究 可以直接判断哪条检索结果是最需要的信息。 垂直搜索引擎和综合搜索引擎在关键技术上的异同： 由于垂直搜索引擎在信息服务方面的自身特点，因此在技术实现上也应该与 综合搜索引擎有很多不同之处。通过比较，可以总结出在关键实现技术上垂直搜 索引擎与综合搜索引擎四个方面的不同。 ( 1 ) 聚焦、实时和可管理的网页采集技术 综合搜索引擎面向全网信息，采集的范围广、数量大，但往往由于更新周期 的要求，采集的深度或者层级比较浅，采集动态网页优先级比较低，因而常被称 为水平搜索引擎。水平搜索引擎通常以被动方式进行信息采集，搜索引擎和被采 集的网页既没有没有事先的约定、也没有标准的格式。而垂直搜索引擎带有专业 性或行业性的需求和目标，所以只对局部来源的网页进行采集，采集的网页数量 适中。但其要求采集的网页全面，必须达到更深的层级，采集动态网页的优先级 也相对较高。在实际应用中，垂直搜索引擎的网页采集技术能够按需要控制采集 的目标和范围，并且支持深度采集以及复杂的动态网页采集。垂直搜索引擎采用 被动和主动相结合的方式，通过主动方式，有效采集网页中标引的元数据信息， 整合上下游网页资源或者商业数据库，提供更加准确的搜索服务。 ( 2 ) 从非结构化内容到结构化数据的网页解析技术 综合搜索引擎仅能对网页的标题和正文进行解析和提取，但不提供其时间、 来源、作者及其他元数据的解析和提取。由于垂直搜索引擎服务的特殊性，往往 要求按需提供时间、来源、作者及其他元数据解析，包括对网页中特定内容的提 取。比如：在论坛搜索、生活服务、订票服务、求职服务、风险信用、竞争情报、 行业供需、产品比较等特定垂直搜索服务中，要求对于作者、主题、地区、机构 名称、产品名称以及特定行业用语进行提取，才能进一步提供更有价值的搜索服 务。 一 ( 3 ) 精、准、全的全文索引和联合检索技术 综合搜索引擎并不能提供精确和完整的检索结果，只是给出预估的数量和排 在前面部分的结果信息，但响应速度是综合搜索引擎所追求的最重要因素；在文 本索引方面，它也仅对部分网页中特定位置的文本而不是精确的网页正文全文进 行索引，因而其最终检索结果是不完全的。而垂直搜索由于在信息的专业性和使 用价值方面有更高的要求，因此能够支持全文检索和精确检索，并按需提供多种 结果排序方式，比如按内容相关度排序( 与水平检索的p a g e r a n k 不同) 或按时间、 来源排序。另外，一些垂直搜索引擎还要求支持结构化和非结构化数据联合检索， 比如结合作者、内容、分类进行组合检索等。 ( 4 ) 高度智能化的文本挖掘技术 北京邮电大学硕上学位论文 垂直检索中的关键问题研究 垂直搜索引擎与综合搜索引擎的最大区别是它对网页信息进行了结构化信 息抽取加工，也就是将网页的非结构化数据抽取成特定的结构化信息数据，好比 网页搜索是以网页为最小单位，基于视觉的网页块分析是以网页块为最小单位， 而垂直搜索引擎是以结构化数据为最小单位。基于结构化数据和全文数据的结 合，垂直搜索引擎才能为用户提供更加到位、更有价值的服务。整个结构化信息 提取贯穿从网页解析到网页加工处理的整个过程。同时面对上述要求，垂直搜索 引擎还能够根据实际需要提供智能化处理功能，比如自动分类、自动聚类、自动 标引、自动排重、文本挖掘等等。这部分技术目前是垂直搜索引擎乃至信息处理 的前沿技术，虽然尚不够成熟，但有很大的发展潜力和空间，属于国内外科研机 构的研究热点。 综上所述，垂直搜索引擎可以针对专业特定的领域或行业的内容进行专业和 深入的分析挖掘，精细分类，过滤筛选，信息定位，更精准的提供有一定价值的 信息和相关服务，有效地弥补了综合搜索引擎对专门领域及特定主题信息覆盖率 过低的问题。同时，能够把具有相同兴趣点的人们集中在一个“主题社区一内， 不仅集中提供各种专业资源，而且给大家提供了一个相互交流、共享经验和教训、 展望行业发展前景的机会和场合。垂直搜索引擎的应用方向很多，比如企业库搜 索、供求信息搜索引擎、购物搜索、房产搜索、人才搜索、地图搜索、m p 3 搜索、 图片搜索几乎各行各业各类信息都可以进一步细化成各类的垂直搜索引擎。 相比较综合搜索引擎的海量信息无序化，垂直搜索引擎则显得更加专注、具体和 深入。 1 3 网页分析技术 w e b 被设计成一个面向信息发布和浏览的系统，w e b 网页中存在大量有价值 的信息，但是这些信息多半是以半结构化的形式存在的，机器很难自动对其进行 分析和理解。我们经常从w e b 网页中发现由多个数据元素所组成的具有一定结构 的数据块，它反映的通常是该网页中包含的最重要的信息。自动识别和抽取w e b 网页中的数据区域对w e b 数据发现、抽取和集成等都有重要的意义。 目前i n t e r n e t 上最普遍的交互方式，就是通过h t m l ( h y p e r t e x tm a r k u p l a n g u a g e ) 进行的。h t m l 是网络的通用语言，一种简单、通用的全置标记语言。 它允许网页制作人建立文本与图片相结合的复杂页面，这些页面可以被网上任何 其他人浏览到，无论使用的是什么类型的电脑或浏览器。 如果所有的h t m l 源码都严格的符合h t m l 标准，那么h t m l 解析将变得比较 简单，但是很不幸，由于微软的浏览器具有极佳的容错性，不完全符合h t m l 标 6 北京邮电大学硕士学位论文垂直检索中的关键问题研究 准的页面往往也能正确显示，这就纵容了网页设计者制造出大量的不完全符合 h t m l 标准的网页，使得h t m l 解析变的具有挑战性。 网页分析的作用，就是对网页进行预处理，一方面是将h t m l 源文件从生涩 的标签集合以及半结构化环境，转换为方便机器操作的信息集，另一方面指从该 源文件中，挖掘出其它有用的信息，为下一步分析提供更多有用的信息。 1 4 概念格与查询扩展 在哲学中，概念被理解为由外延和内涵两个部分所组成的思想单元。基于概 念的这一哲学理解，德国的w i l l e 教授( 1 9 8 2 年) 提出了形式概念分析口一1 ，用 于概念的发现、排序和显示。在形式概念分析中，概念的外延被理解为属于这个 概念的所有对象的集合，而内涵则被认为是所有这些对象所共有的特征或属性 集，这实现了对概念的哲学理解的形式化。所有的概念连同它们之间的泛化例 化关系构成一个概念格隋1 。概念格结构模型是形式概念分析理论中的核心数据结 构，它本质上描述了对象和特征之间的联系，表明了概念之间的泛化与例化关系， 其相应的h a s s e 图则实现了对数据的可视化。 从理论提出开始十年左右的时间里，对形式概念分析的研究主要集中在德国 国内少数学者中间。这一时期的研究理论性很强，对问题的描述、分析和论证多 采用数学的、很抽象的方法；与此同时，形式概念分析在德国国内的几个大型项 目中取得了成功的应用，其中包括著名的t o s c a n a 系统。 最近的十年左右时间里，对形式概念分析理论及其应用的研究，在国际上迅 速而广泛的开展起来，它的应用范围也扩大为包括语义学、经济学、心理学、软 件工程、人工智能和信息提取等诸多领域中。导致这种变化的原因是多方面的， 主要是因为信息科学的迅速发展，同时形式概念分析理论中的某些数据结构为信 息科学的研究提供了一些基本而有效的信息表示方法。例如，在知识发现中，形 式概念分析理论中的核心数据结构概念格可以将数据有机的组织起来， 格中的节点体现了概念内涵和外延的统一，因此非常适合用来发现规则型知识。 从2 0 0 3 年起，每年召开一次以形式概念分析为主题的国际学术会议，即 i n t e r n a t i o n a lc o n f e r e n c eo nf o r m a lc o n c e p ta n a l y s i s ( i c f c a ) ，专门讨论形式概念 分析的相关理论及其在某些具体领域中应用问题。可见，形式概念分析己经得到 越来越多的关注。 随着i n t e r a c t 的飞速发展，网络上的信息呈指数增长，其内容之丰富，种类 之繁多，堪称世界上最大的信息资源，如何能够更有效、更准确地找到用户感兴 趣的内容，滤除与用户的需求无关的信息，真正做到“各取所需 ，关系到我们 7 北京邮电大学硕士学位论文垂直检索中的关键问题研究 能否充分利用这个巨大的信息资源的问题，这己成为基于i n t e r n e t 的网络信息获 取的热点问题。 因为信息检索中的“文档特征词”关系能够很自然的被看作形式概念分 析中的形式背景，所以从二十世纪8 0 年代起，一些学者借助形式概念分析理论 的核心数据结构一概念格对信息检索进行了研究。基于概念格理论和应用的新发 展，概念格在信息检索领域引起了越来越多的研究者的关注。 w i l l e 教授在1 9 8 2 年发表的有( r e s t r u c t i n gl a t t i c et h e o r y ：a na p p r o a c hb a s e do i l h i e r a r c h i e so f c o n c e p t s ) 嘲标志着概念格理论的建立， f o r m a lc o n c e p ta n a l y s i s 脚 使概念格理论进一步成熟，其中讨论了它的完备性等若干性质随后，又有学者 研究了它的同构性阳1 ；近几年j 又有人提出邻域口1 、闭包嘲、极大和随机概念格嗍 等概念。总的来说，关于概念格的建格算法做的研究比较多建格的过程实际上 是概念聚类的过程，对同一批数据，所生成的格也是唯一的概念格建格算法可 以分为两类：批处理算法和增量算法批处理算法的思想是首先生成所有概念，然 后根据它们之间的直接前驱后继关系，生成边，完成概念格的构造根据其 构造格的不同方式，批处理算法又可以分为3 类：从顶向下算法，自底而上算法， 枚举算法。从顶向下算法首先构造格的最上层节点，再逐渐向下，如b o r d a t 算 法n 们；o s h a m 算法n ；自底而上算法首先构造底部的节点，再向上扩展，如 c h e i n n 2 1 的算法。枚举算法则是按照一定顺序枚举格的所有节点，然后再生成格 的h a s s e 图，如g a n t e r 算法n 羽，n o u r i n e 算法n 铂增量算法是把当前要插入的对 象和概念格中所有的概念相交，由交的结果把格中节点分为不变节点、更新节点 和新增节点，根据交的结果然后采取不同的方法，如g o d i n 的算法n 副、c a p i n e t o 算法n 们、t b h o 算法n 刀，渐进式生成算法n 哪! 。其中，概念格的维护算法妇“翻( 主 要涉及到对象的插入、删除、修改和属性的增加、删除) 也属于概念格的增量算 法。在概念格发展的基础上，吴刚、胡学钢等人对概念格进行了扩展，通过引入 等价内涵定义了扩展概念格( e x t e n d e dc o n c e p tl a t t i c e s ) 嘲，并证明扩展概念格和其 对应的一般概念格是同构的：随后又定义了约简概念格( r e d u c e dc o n c e p t l a t t i c e s ) 2 4 9 简化了扩展概念格，使其更利于大规模数据库知识发现的应用；针对 约简格中的生成内涵可以从其父概念内涵中获得，对约简概念格进一步简化又提 出了相对约简概念格( r e l a t i v er e d u c e dc o n c e p tl a t t i c e s ) 阱1 ：在概念格的内涵中引入 等价关系并将其外延量化，得到了量化概念格( q u a n t i t a t i v ec o n c e p t ) 哺1 ，利用量化 概念格可以更清晰的表示知识，从而便于挖掘包括关联规则在内的多种规则，并 且用户可根据自己的兴趣交互的挖掘关联规则，不需要计算频繁项目集，因而提 高了挖掘规则的效率在提出这些新概念格的基础上，并对这类概念格的性质、 构造及其维护做了一定的研究旧一另外结合z a d e t h 的模糊集理论( f u z z ys e t s 8 北京邮电大学硕士学位论文 垂直检索中的关键问题研究 t h e o r y ) 啪1 ( 1 9 6 5 年提出) ，a b u r u s e o 和r f u e n t e s 啪1 于1 9 9 4 年提出了卜模糊概 念格，讨论了它的层次结构，证明全体i ，_ 一模糊概念是一个完备格，并对其算 法做了一定的研究1 ；2 0 0 2 年，陈世权和程里春叉提出了描述概念内涵和外延 模糊关系的模糊概念格口剀，建立了概念的内涵与外延的模糊映射，用模糊集描述 模糊概念思维，并进一步探讨了模糊属性映射和模糊对象映射的隶属函数的一些 基本数学性质，证明全体模糊概念构成一个完备格，相关的研究工作对模糊概念 刻画、模糊推理、模糊形式语言具有重要的理论与应用价值。 以上都是针对单个概念格进行的，随着网络技术尤其是互联网的飞速发展， 数据的分布式存储和并行处理的需求越来越迫切，对多概念格的合并算法也有了 一些研究。其中，李云田1 通过定义概念的横向加运算，提出了一种多概念格的横 向合并算法，该算法适用于对概念格进行分布并行处理。 概念格的研究并不仅仅限于理论方面，在应用上也有一定的发展，如在软件 工程、信息检索、知识发现、数据挖掘、规则提取、聚类分析嘲删等领域。尤以 在规则提取方面的研究较多，如提取关联规则、蕴涵规则、分类规则等在知识 发现领域，概念格可以从关系数据中提取各种类型的知识，如关联规则、蕴涵规 则、分类规则等：在软件工程领域，概念格可以从类库以及类库的规范说明上构 造，从而对类库的可视化以及类库的重构和优化提供支持；在知识工程领域，概 念格可以用于知识库的重新结构化；在信息检索方面，概念格可以实现对信息的 有机组织并过滤掉无用的信息( 如和粗糙集理论n 5 1 相结合对信息系统进行属性约 简h 6 朋) ，来简化信息表。目前，也有人在应用概念格进行搜索引擎方面的研究。 而且，有人指出概念格将会在生物和生命科学领域有重大应用。 概念格中“概念 之间的关联性，特别适合用于描述查询词之间的关联性， 而后本文的实验中也证实了该工具在查询扩展方面的强大作用。 1 5 本文的工作及内容安排 w e b 被设计成一个面向信息发布和浏览的系统，w e b 网页中存在大量有价值 的信息，但是这些信息多半是以半结构化的形式存在的，机器很难自动对其进行 分析和理解。我们经常从w e b 网页中发现由多个数据元素所组成的具有一定结 构的数据块，它反映的通常是该网页中包含的最重要的信息。自动识别和抽取 w e b 网页中的数据区域对w e b 数据发现、抽取和集成等都有重要的意义。 通用的搜索引擎( 如g o o g l e 、百度等) 都是针对全领域的，当用户有特定需 求时( 比如检索某个产品) ，通常因为字符串匹配，返回若干不相关的结果。例 如用户在搜索产品“a b c ”的信息，而某人的博客因为提到了“a d 3 c 字符串， 9 北京邮电大学硕士学位论文垂直检索中的关键问题研究 也作为结果呈现出来，给用户寻找所需信息增加了难度。垂直搜索这一搜索模式 正式在这样的背景下诞生了。 此外，用户在使用搜索引擎时，所选用的关键词往往不是最优的，于是用户 需要不断地浏览检索结果后修正检索词，直到找到所需结果。如何修正检索词， 将大大影响用户定位信息的效率。 基于上面所述，本文首先提出一种网页分析算法，通过分析网站中产品的列 表页，找到产品链接结点d o mp a t h 的重复模式，挖掘出产品分类层次结构。通 过解析不同公司的产品展示页面，我们得到垂直搜索引擎的必要信息：该领域( 即 相关产品之间的关系) 的知识。该方法在安全领域网站构成的测试集中，产品链 接聚类正确率达到7 1 0 ，( 类别) 命名正确率( 在聚类j 下确的基础上) 达到7 7 3 。 本文又根据概念格概念关联的特性，随后提出了一个基于概念格的检索系 统，对用户输入关键词进行查询扩展，帮助用户修正关键词；本文将产品层次信 息与概念格的检索系统相结合，提出并实现了基于概念格的产品优先的查询扩展 系统。该方法当用户输入查询词包含某产品名称时，将优先给出同类产品名字作 为扩展词。该系统可作为一个简易的面向产品查询的垂直搜索引擎。在测试中， 该方法展示出良好的查询扩展性能，能帮助用户定位信息。 此外，文中所提出的小型信息检索系统，适用于各种信息检索相关技术研究， 让大家在有限的资源下，最大限度地能模拟w e b 信息检索系统。 论文的第一章介绍了本文的研究意义，并对相关研究领域的主要研究工作加 ，以介绍，最后提出了本文的研究动因及本文的主要工作。 第二章介绍了概念格的相关理论知识。 第三章提出了基于网页分析的产品层次抽取算法。 第四章基于概念格的产品优先的查询扩展系统的构造，主要介绍我们设计并 实现本系统的关键技术。 第五章给出了实验结果分析，分别对产品层次抽取和查询扩展系统进行了详 细的分析。 第六章结论与展望，对全文工作进行总结，并提出下一步的工作展望。 l o 北京邮电大学硕士学位论文垂直检索中的关键问题研究 第二章概念格的理论基础 2 1 概念格的定义和基本术语 下面给出概念格的定义和一些基本术语，并用实例简单加以说明，更详尽的 描述可参考文献。概念格模型是基于格理论n 1 建立起来的，是序论和格论相结合 的产物，因此本文首先介绍代数格的一些基本定义。 2 1 1 代数格 定义2 1设彳是一个集合，如果么上的一个关系尺，对于v x ，y ，z a ，满 足下面条件： x r y ，y r x jx = y x r y ，y r zj x r z ( 自反性) ( 反对称性) ( 传递性) 则称r 是彳上的一个偏序关系，把它记作”。序偶 a ，称为偏序集。 定义2 2设 a ，为偏序集且bs 么为一个子集，如果有a a 对曰的任 意元素x ，都满足工a ，则称a 为子集b 的上界。同理，对曰的任意元素x ，都 满足a x ，则称a 为子集b 的下界。 定义2 3设 a ，为偏序集且b 互彳为一个子集，a 为召的任一上界， 若对于b 的所有上界y 均有a y ，则称a 为曰的最小上界( 上确界s u p r e m u m ) ， 记作s u p ( b ) 。同样，若b 为b 上的任一下界，若对于b 的所有下界z ，均有z b ， 则称b 为b 的最大下界( 下确界i n f u n u m ) ，记作i n f ( b ) 。 定义2 4设 a ，为偏序集，如果彳中任一两个元素都有最小上界和最 大下界，则称 a ，为格。 定义2 5设 a ，是一个格，如果在彳上定义两个二元运算v 和a ，使得 对于任意的a ，b 彳，a v b 等于d 和b 的最小上界，a 6 等于a 和b 的最大下界， 那么就称 是由格所诱导的代数系统，二元运算v 和a 分别称为并运算 北京邮电大学硕士学位论文 垂直检索中的关键问题研究 和交运算。 代数格以偏序关系为基础，集合的元素之问存在上确界和下确界所构成的代 数结构成为格。 2 1 2 概念格 形式概念分析通常由形式背景这一基本概念开始。首先给出形式背景的定 义。 定义2 6形式背景定义为一个三元组k = ( g ，m ，j ) ，其中，g 是对象集合， m 是属性集合，g x m 是g 与m 之间的一个二元关系。若( g ，m ) i ，读作“对 象g 具有属性m 。 形式背景通常用交叉表( c r o s st a b l e ) 来表示。在交叉表中一行代表一个对象， 一列代表一个属性，第g 行和第研列的交叉点有一个“当且仅当国，朋) i 。 表l 是一个例子形式背景的交叉表。 i口扫cdo j -g ai l1010010l0 2101000101 3l00l00101 40l10010l0 5 0 1 001 0 10o 表1 一个例子形式背景 定义2 7在形式背景k 中，在g 的幂集和肘的幂集之间可以定义两个映 射厂和g 如下： c as g ：厂( 彳) = 聊mlv g a ，g r i n v b m ：g ( 曰) = g g i v m b ，g r i n 厂和g 被称为g 的幂集和肘的幂集之间的g a l o i s 联接。通常，为书写方便， 采用4 和b 分别代替f ( a ) 和g ( 8 ) 。 定义2 8背景k = ( g ，m ，i ) 上的一个形式概念定义为一个二元组( a ，b ) ， 满足： acg ，b m ，彳- b ，b t ：a 1 2 北京邮电大学硕士学位论文垂直检索中的关键问题研究 其中彳称为概念( 么，占) 的外延，占称为概念( 彳，曰) 的内涵。 概念的内涵是该概念所包括的一切对象的共同的本质属性的总和，概念的外 延是适合该概念的一切对象的范围。对一概念( 彳，召) ，属性b b 称为该概念所支 持的属性，对象a a 称为该概念所覆盖的对象。一个形式背景可能有许多概念。 事实上，形式概念的数目是形式背景大小的指数。形式背景k = ( g ，m ，) 上的所 有概念的集合记为b ( k ) 。 定义2 9 c l = ( a ，b ) 和c 2 = ( c d ) 是形式背景k = ( g ，m ，- i ) 上的任意两个 概念，称( a ，b ) 是( c ，d ) 的超概念( 等价地，( c ，d ) 为( 彳，曰) 的子概念) ，当且仅当 bc d ( 等价地，c 互么) ，记为( g d ) ( 彳，口) 。即： ( c ，d ) ( 么，曰) b d ( 铮c 彳) 通过这种序关系，得到一个有序集星伍) = ( 曰僻) ，) ，称为形式背景k 的概念 格。当不存在概念c 使得g c g ，此时称g 是c 2 的超概念或直接泛化，g 是 g 的子概念或直接例化。 概念格中概念的外延和内涵之间存在对偶关系，给定概念g = ( 么，b ) 和 c 2 = ( c d ) ，则有g g 营b cd ；又口cd 营c c 7 a ，从而有c i g 营cc a 。 因此，一个概念格可以看作是相互联系的两个格。 概念格是所有形式概念在子概念和超概念下的序集。因此，概念格可以图形 化表示为其所对应的h a s s e 图。这使得给定数据背景的概念结构变得清晰和易于 理解，从而实现了概念格的可视化的显示。表1 例子形式背景所对应概念格的 h a s s e 图在图2 - 1 中给出。 ( 1 ，2 ，3 ，4 ，5 ，卿 刃； a 。b 。c 。d ，e ，t o h 。璐 图2 - 1表l 例子形式背景对应的概念格 图2 - 1 中每个节点表示一个概念，每个概念用其外延和内涵来标识，节点之 北京邮电大学硕士学位论文 垂直检索中的关键问题研究