（计算机应用技术专业论文）deep+web集成查询接口生成技术研究.pdf

摘要 随着网络的发展，网上蕴藏着越来越多的信息，而更多的信息被 隐藏在网络深处，称之为d e e pw e b ，俗称深网。为了挖掘d e e pw ，e b 中的信息，d e e pw r e b 数据集成的研究成为当务之急。而其中一个非 常重要的方面就d e e pw e b 查询接1 2 1 的集成。 查询接口是d e e pw _ e b 的唯一入口，而查询接口通常以表单的形 式表示。在本文中表单是主要的研究对象，所以在前面部分首先对表 单的基本知识做了介绍，然后列举了一些常用的分类算法。 本文主要做了两个部分的工作：第一个工作就是d e e pw r e b 查询 接口识别，将w e b 网页中的表单作为研究对象，利用一定的规则提 取表单特征，构成表单特征向量，而后利用c 4 5 分类算法识别d e e p w e b 查询接口，也就是找到深网的入口。在实验中利用w e k a 平台对 几种常见的分类算法进行了比较，验证了c 4 5 分类算法的优越性。 找到深网入口后，接着对d e e pw - e b 查询接口进行分类，确定查 询接口属于哪个领域，如：音乐，商业，新闻等，这部分工作的主要 研究对象也是表单，提取表单的文本特征，以向量空间模型表示。然 后利用朴素贝叶斯分类算法对d e e pw e b 查询接口进行分类，以确定 查询接口属于哪个领域。在这部分也通过实验对几种分类算法进行了 比较( 如：s v m ，c 4 5 ，n b ) ，最后发现朴素贝叶斯分类算法精确度最 高。 关键词数据集成；分类；c 4 5 分类算法；朴素贝叶斯分类 a bs t r a c t w i t ht h ed e v e l o p m e n to fn e t w o r k ，m o r ea n dm o r ei n f o r m a t i o ni s i n c l u d e di nt h en e t w o r k ，b u tm u c hm o r ei sh i d d e ni nt h en e t w o r kd e e p l y ， c a l l e dd e 印w e b i no r d e rt om i n et h ei n f o r m a t i o no fd e e pw e b ，i ti sa n u r g e n c yt a s kt o d os o m er e s e a r c ho nt h ed a t ai n t e r g r a t i o no fd e e p w e b h o w e v e r , av e r yi m p o r t a n ta s p e c ti st h ei n t e r g r a t i o no fd e e pw e b q u e r y i n t e r f a c e q u e r yi n t e r f a c ei st h eo n l ye n t r a n c eo fd e e pw e b ，a n di ti su s u a l l y r e p r e s e n t e db yf o r m i nt h i sp a p e rf o r mi st h em a i no b j e c to fr e s e a r c h ，s o f i r s t l ys o m eb a s i ci m f o r m a t i o na b o u tf o r mi si n t r o d u c e di nt h ef r o n to f t h e p a p e r , t h e ns o m ea l o g r i t h m so fs o r t i n ga r ee n u m e r a t e d t w ot a s k sh a v eb e e nd o n ei nt h ep a p e r ：t h ef i r s ti st h ei d e n t i f i c a t i o n o fd e e pw e bq u e r yi n t e r f a c e t h ef o r mi nt h ew e bi sr e s e a r c h f u lo b j e c ti n t h i sp a p e r , f i r s t l ys o m er u l e sa r eu s e dt oe x t r a c tt h ec h a r a c t e r i s t i c so f f o r m w h i c hc o n s t i t u t e e i g e n v e c t o r , t h e nc 4 5 s o r ta l o g r i t h mi su t i l i z e dt o i d e n t i f yd e e pw e bq u e r yi n t e r f a c e ，i no t h e rw o r d si tm e a n st of i n dt h e e n t r a n c et oh i d d e nw e b t h es u p e r i o r i t yo fc 4 5s o r t i n ga l o g r i t h mi s v a l i d a t e do nt h ew e k ai ne x p e r i m e n t a f t e rf i n d i n gt h ee n t r a n c eo fd e e pw e b ，t h ej o bi st h ec l a s s i f i c a t i o n o fd e e pw e bq u e r yi n t e r f a c ew h i c hi su s e dt oe n s u r et h ed o m a i no f q u e r y i n t e r f a c e ，s u c ha sm u s i c ，b u s i n e s s ，n e w se t c t h em a i no b j e c to fr e s e a r c h i sa l s of o r m ，t h e nt h ec h a r a c t e r so ft e x tw h i c ha r de x p r e s s e db yv s m m o d e la r ep i c k e du p t h e nn a t i v eb a y e ss o r t i n ga l o g r i t h mi su s e dt o c l a s s i f yd e e pw e bq u e r yi n t e r f a c e t oe n s u r et h ed o m a i no fq u e r y i n e r f a c e i nt h i s p a r t s e v e r a l s o r t i n ga l o g r i t h m s a r e c o m p a r e d i n e x p e r i m e n t ，a n dt h ea d v a n t a g eo f n a t i v eb a y e sc l a s s i f i e ri sa l s op r o v e d k e yw o r d sd a t ai n t e r g r a t i o n ，c l a s s i f i c a t i o n ，c 4 5s o r t i n ga l o g r i t h m ， n a t i v eb a y e sc l a s s i f i e r , h i d d e nw e b l l 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共 同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名盥 眺耳年月丝日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有 权保留学位论文并根据国家或湖南省有关部门规定送交学位论文，允 许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：! 坌垂塾导师签名：三i ，乏之日期：必上月2 垡日 中南大学学位论文第一章绪论 1 1d e e pw e b 背景知识 第一章绪论 随着网络规模在全球的迅猛发展，网络已成为生活中不可或缺的一部分， i n t e m e t 上的w e b 网站以及网页的数量目前在以爆炸性的趋势增长，网上蕴藏着 巨大的信息资料。但是，目前主流的搜索引擎如：谷歌、百度，基本上只能收集 的互联网上部分称为表层网( s u r f a c ew e b ) 的信息，这些s u r f a c ew ，e b 的信息都是 通过静态网页链接的，然而更加丰富的、有价值的信息被隐藏在网络深处，它们 被当前的搜索引擎所忽视，这就是深度 网( h i d d e nw e b ) ，也称为d e e pw e b 。 s u r f a c ew e b 是指存储在w e b 空间、由超链接连接起来的静态网页、文件等 资源，一般来说通过超链接就可以访问这些资源。且静态网页在一定时间内保持 不变。这里所说的表层网是指传统网页搜索引擎可以索引的w e b ，以超链接可以 到达的静态网页为主构成的w e b 。 d e e pw e b 指那些存储在网络数据库里、不能通过超链接访问而需要通过动 态网页技术访问的资源集合。动态网页通常是由后台的数据库支持，只有当用户 查询的时候才会由c g i 或a s p 程序产生，而且作为响应只会在一次请求应答过 程中存在。 据b f i g h t p l a n e t 公司技术白皮书【l 】，深度网资源容量约为表层网的5 0 0 倍， 而且包含着更多有价值的资源，其研究结果表明： 1 ) d e e pw e b 页面信息大约是表面页面信息的5 0 0 倍，其大约有3 0 7 ，0 0 0 个 站点，4 5 0 ，0 0 0 个后台数据库和1 , 2 5 8 ，0 0 0 个查询接口。它仍在迅速增长，从2 0 0 0 年到2 0 0 4 年，它增长了3 7 倍。 2 ) d e e pw e b 内容分布于多种不同的主题领域，尽管电子商务是其主要的驱 动力量，w e b 数据库的发展趋势不仅在此领域，而在非商业领域相对占更大比重。 3 ) 当今的爬虫并非完全爬行不到d e e pw 曲后台数据库内容，当前主要的 搜索引擎已经覆盖d e e pw e b 大约三分之一的内容。然而，在覆盖率上当前搜索 引擎存在技术上的本质缺陷。 4 ) d e e pw e b 中的后台数据库大多是结构化的，其中结构化的是非结构化的 3 4 倍之多。 5 ) 虽然一些d e e pw e b 目录服务已经开始索引w e b 数据库，但是它们的覆 盖率比较小，仅为0 2 - 15 6 。 中南大学学位论文 第一章绪论 6 ) w e b 数据库查询接口往往位于站点浅层，9 4 之多的大量w e b 数据库查 询接口可以在站点前3 层发现。 以上可见，深度网包含数量巨大、高质量、结构化的数据。研究和挖掘深度 网对于提高搜索覆盖率和准确率有着非常重要的意义。 1 2 课题研究的意义 d e e pw e b 中的w e b 数据库不但数量众多，而且覆盖了现实世界的各个领域。 一些专门的机构，像c o m p l e t e p l a n e t 和i n v i s i b l e w e b 等，构建了d e e pw r e b 目录， 按现实世界的领域对d e e pw r e b 的内容做了分类，主要包括商业与经济、计算机 与互联网、新闻媒体、娱乐等一共十几个分类。这只是宏观的分类，每个分类下 面还有小的分类，比如科学可以继续分为社会科学与自然科学，而自然科学又可 分为若干学科。从表1 1 【2 】中可以看出，尽管这些网站对w r e b 数据库进行了细致 的分类，但所列出的w e b 数据库仅仅只是整个w e b 数据库的很小的一个比例( 即 使最大的c o m p l e t e p l a n e t 也只有1 5 6 蚴。因此从宏观上对w e b 数据库按现实世 界的领域分类做一个定量的分析是十分迫切而且必要的工作。 表i - 1d e e pw e b 目录的覆盖率 w e b 数据库的数目覆盖率 c o m p l e t e p l a n e t c o m 7 0 0 0 01 5 6 l i i o r g 1 4 0 0 03 1 t u r b o l 0 c o r n2 3 0 0o 5 i n v i s i b l e w e b n e t1 0 0 0o 2 对d e e pw r e b 中信息的获取主要是对网站中所提供的查询接口提交查询来获 得，查询接口顾名思义是外部访问w e b 数据库的门户，是从w e b 中获得数据的 主要途径，因此在w e b 数据库研究领域，对查询接口的信息研究占有极其重要 的地位。 传统的搜索引擎仅能爬行公共可索引的页面，它是通过分析页面中的超链接 来爬行的。然而深度网页面也就是d e e p w e b 页面是通过响应来自客户端的表单 查询请求，服务器端后台数据库动态产生的。因此，要获取这个页面集就需要一 种特殊的方式来搜索这些页面。为了获取d e e pw e b 中的有效信息，我们一般通 过填写表单，提交表单的方式，获取动态生成的响应页面，从中选取我们想要的 查询结果( 如图1 1 所示) 。 2 中南大学学位论文 第一章绪论 裹单 结果页自 w e b 数据库 珊览器 囤1 1 查询d e e pw e b 数据库的过程 虽然整个d e e pw e b 中几乎包含了大量我们所需要的信息，但要想以手工的 方式对其加以有效的利用在实际当中是一件非常困难的事情，而对d e e p w e b 数 据的集成正是为了以尽可能自动的方式来完成对w e b 数据库中信息的有效利用。 在d e e p w e b 数据集成系统中必须要提供一个统一的访问途经。每个w e b 数据库 都提供丁查询接口，我们需要把每个w e b 数据库的查询接口进行集成并得到一 个统一的接口，该接口称为集成接口。通过在集成接口上提交查询，就达到了同 时在多个w e b 数据库的查询接口提交查询的目的。为了得到这个集成接口，需 要经历几个步骤：首先要在w e b 上发现要集成的查询接口；其次对这些接口进 行解析，获得它们的模式信息，即查询能力；第三要把它们按不同的领域分类把 属于同一个领域的接口集成为一个统一的接口。 13 国内外研究现状 d e e p w e b 数据集成是近十几年来发展起来的新领域。所以d e e p w e b 集成查 询接口的生成还处于探索阶段，对其研究还不够成熟，需要进一步发展与完善。 关于发现d e e pw e b 站点入口的工作，比较早的有斯坦福大学的h i d d e n w c b e x p o s e r ( h i w e ) 项目d , s i 作者r a 曲a v a i l 和g a r c i a - m o l i n a 提出两条规则来判断是 否是要寻找的深度网入口：1 ) 要填写或选择的字段过少的l m n l 表单将被忽略不 予考虑；2 1 表单中的控件能与作者所建立的l a b e lv a l u es e t ( l v s ) t a b l e 相匹配为 需要的表单。类似文章州同样使用条启发机制，第一条与r a g h a v a n 和 g a r c i a - m o l i n a t 45 】提出的相同，第二是对于给定表单，如果这个表单含有密码框 ( p a s s w o r d ) ，这个表单将被略不予考虑。c h i d l o v s k i i 和b e r g h o l z t8 】将表单( f o r m ) 分 一露碱謇亡进一一 蔫凸 中南大学学位论文第一章绪论 类，排除掉不是深度网表单的其他类型表单，但没有具体讲如何实现，并且它的 分类漏掉了一些深度网入口。有网站 9 1 做了很多主题搜索引擎，索引的都是深度 网中的资源。据客户的要求，对指定的深度网站点进行搜索，去掉重复的网页， 对页排序。但是这些深度网站点是由客户提供的，并不是自动搜索到的 q p r o b e r l l 0 1 。 使用深度网站点含有的文档对其进行层次化分类。对w e b 数据库的分类实 质上是对查询接口的分类。分类方法共分为两类：指导方式和非指导方式。文献 【1 2 】针对应用意义最广泛的电子商务的w e b 数据库提出了一种有效的分类方法。 这种方法是一种非指导的方式，主要利用了电子商务的w e b 数据库的查询接口 所在页面上的可用特征信息，包括接口中出现的频繁词和商品的价格特征。其实 验结果表明，按这种分类方式进行分类，p r e c i s i o n 和r e c a l l 都在9 0 左右。文献 【1 3 】完全利用查询接口的模式信息提出了一种更一般的w e b 数据库分类解决方 案，属于指导方式。他们根据统计特性认为查询接口的模式信息可以作为对w e b 数据库分类的依据。基于这样的统计结论，他们提出通过建立概率模型来表示所 有可能出现的属性在每个领域中出现的可能性。对于一个给定的查询接口，考察 其属性集合，在这个模型上计算出这个查询接口与每个领域的相似性。前面两种 方法都是基于查询接口的特征信息实现对w e b 数据库的分类。 1 4 本文的主要工作 d e e pw 曲查询接口的集成是一个复杂的过程，每个过程都是一个承上启下 的功能，并且每个过程都是完成特定的任务，可以分为三步：d e e pw e b 查询接 口的识别即寻找深网的入口；d e e pw e b 查询接1 3 分类即对d e e pw 曲查询接口按 照不同的领域进行分类；d e e pw e b 查询接1 3 集成即提取d e e pw ，e b 查询接1 3 模 式，对相同领域的查询接口集成一个统一的接口。整个过程如图1 2 所示： 4 中南大学学位论文第一章绪论 图卜2d e e pw e b 查询接口集成模型 本文研究的主要内容包括以下两个部分： 1 ) 研究d e e pw ，e b 查询接口识别的问题：表单是访问d e e pw e b 的唯一入口， 因此将表单作为研究对象，按照一定的规则提取表单特征，然后利用合适的分类 算法对分类效果进行比较，此部分用到了经典的分类算法：c 4 5 分类，贝叶斯 分类，k 最邻近分类，支持向量机分类。最后通过实验数据进行比较，发现c 4 5 分类算法在p r e c i s i o n 和r e c a l l 这两个评价标准上都优于其他分类算法。 2 ) 研究d e e pw e b 查询接口分类问题：一个d e e pw - e b 查询接口属于不同的 领域，因此在对d e e pw e b 查询接口进行集成时先要确定查询接口所属的领域。 在处理这个问题时，利用一定的规则提取d e e pw e b 查询接口的特征尤其是文本 特征，然后对提取的特征向量进行预处理，最后利用分类算法对d e e pw e b 查询 接口进行分类，在实验部分对分类算法进行了比较，验证了朴素贝叶斯算法的精 确性。 5 中南大学学位论文 第二章d e e pw e b 集成查询接口生成相关技术 第二章d e e p w e b 集成查询接口生成相关技术 d e e pw ，e b 查询接口集成的过程主要分为：d e e pw e b 查询接口识别：根据查 询接口特征，对查询接口进行分类；对同类查询接口按照相同领域进行统一接口 集成。本文的d e e pw 曲查询接口识别主要针对表单；通过分析表单的特征，对 查询接口进行分类。 2 1 表单相关知识 d e e pw - e b 查询接口是获取后台数据库内容的唯一入口。一个查询接口通常 是一个w e b 页面中用h t m l 表示的网页表单，h t r r d o a y p e rt e x tm a r k u pl a n g u a g e ) 臣p 超文本标记语言，是w w w 的描述语言。设计h t m l 语言的目的是为了能把存放 在一台电脑中的文本或图形与另一台电脑中的文本或图形方便地联系在一起，形 成有机的整体，人们不用考虑具体信息是在当前电脑上还是在网络的其它电脑上 只需使用鼠标在某一文档中点取一个图标，i n t e r n e t 就会马上转到与此图标相关 的内容上去，而这些信息可能存放在网络的另一台电脑中。h t m l 文本是由h t m l 命令组成的描述性文本，h t m l 命令可以说明文字、图形、动画、声音、表格、链 接等。h t m l 的结构包括头部( h e a d ) 和主体( b o d y ) 两大部分，其中头部描述浏览器 所需的信息，而主体则包含所要说明的具体内容。 网页表单即包含在h t m l 标签 之内的相关内容。其一般格式 为 。 h t m l 表单( f o r m ) 是h t m l 的一个重要部分，主要用于采集和提交用户输入的信 息。举个简单的例子，一个让用户输入姓名的h t m l 表单( f o r m ) 。示例代码如下： 请输入你的姓名： 学习h t m l 表单( f o r m ) 最关键要掌握的有三个要点： 1 ) a c t i o n 。 2 ) m e t h o d 。 6 中南大学学位论文 第二章d e e pw e b 集成查询接口生成相关技术 3 ) 表单控件( f o r mc o n t r o l s ) 。 用户填入表单的信息总是需要程序来进行处理，表单里的a c t i o n 就指明了处 理表单信息的文件。比如上面例句里的h t t p ：w w w a d m i n 5 c o m h t m l a s d o c s h t - m lt u t o r i a l s y o u m a m e a s p 。 至于m e t h o d ，表示了发送表单信息的方式。m e t h o d 有两个值：g e t 和p o s t 。 g e t 的方式是将表单控件的n a m e v a l u e 信息经过编码之后，通过u r l 发送( 可以在 地址栏里看到) 。p o s t 则将表单的内容通过h t t p 发送，且在地址栏看不到表单的 提交信息。那什么时候用g e t ，什么时候用p o s t 呢? 一般是这样来判断的，如果 只是为取得和显示数据，用g e t ；一旦涉及数据的保存和更新，建议用p o s t 。 通过h t m l 表单的各种控件，用户可以输入文字信息，或者从选项中选择， 以及做提交的操作。比如上面的例句里，i n p u tt y p e = ”t e x t ”就是一个表单控件， 表示一个单行输入框。一个表单通常包括几类控件，它们都在 标 签对中，平时所说的表单元素是指表单控件，h t m l 表单( f o r m ) 常用控件如表2 1 所示。 表2 - 1 表单常用控件 表单控件( f o 而c o n t r o l s ) 说明 i n p u tt y p e = t e x t ” 单行文本输入框 i n p u tt y p e 2 ”s u b m i t “ 将表单( f o r m ) 里的信息提交给表单里a c t i o n 所指向的文件 i n p u tt y p e = ”c h e c k b o x ” 复选框 i n p u t 咖e = ”r a d i o ” 单选框 s e l e c t下拉框 t e x t a r e a 多行文本输入框 f i l e用以传输文件 i n p u tt y p e 2 ”p a s s w o r d ” 密码输入框( 输入的文字用牢表示) i n p u tt y p e = ”h i d d e n ” 隐藏的控件 1 ) 单行文本输入框 单行文本输入框( i n p u tt y p e = ”t e x t ”) 允许用户输入一些简短的单行信息，比如 用户姓名。例句如下： 2 ) 复选框 复选框( i n p u tt y p e = ”c h e c k b o x ”) 允许用户在一组选项里，选择多个。示例代码： 苹果 桔子 芒果 7 中南大学学位论文 第二章d e e pw e b 集成查询接口生成相关技术 用c h e c k e d 表示缺省已选的选项。 桔子 3 ) 单选框 单选核取表单( i n p u tt y p e = ”r a d i o ”) 通常是好几个选项一起摆出来供使用者点 选，一次只能从中选一个，故为单选核取表单。示例代码： 苹果 桔子 芒果 用c h e c k e d 表示缺省已选的选项。 桔子 4 ) 下拉框 下拉框( s e l e c t ) 是卷动选单标记，每一项由 所标示。例句如下： 苹果 桔子 芒果 5 ) 多行输入框( t e x t a r e a ) 多行输入框( t e x t a r e a ) 主要用于输入较长的文本信息。例句如下： 6 ) 密码输入框 密码输入框( i n p u tt y p e = ”p a s s w o r d ”) 主要用于一些保密信息的输入，比如密 码。因为用户输入的时候，显示的不是输入的内容，而是黑点符号。例句如下： 7 ) 提交 通过提交( i n p u tt ) r p e = s u b m i t ) 可以将表单( f o r m ) r e 的信息提交给表单里a c t i o n 所指向的文件。 例如： 8 ) 图片提交 图片提交( i n p u tt y p e - - i m a g e ) 相当于i n p u tt y p e = s u b m i t ，不同的是，i n p u t t y p e = i m a g e 以一个图片作为表单的提交按钮，其中s r c 属性表示图片的路径。 9 ) 文件按纽 文件按坌 ( f i l e ) 例如： 显示为： 二二二二二二二二二二 匝蟹互刁通常用以 8 中南大学学位论文第二章d e e pw e b 集成查询接口生成相关技术 传输文件，参数a c c e p t 表示可接受文件的类别，有2 6 种选择。 1 0 ) 隐藏的控件 隐藏的控件( h i d d e n ) 允许w e b 程序员将数值引入到h t m l 表单中，使这些 值与其它控件一起发送回w e b 服务器。这些控件通常用来让w e b 程序员存储不 能更改的只读值。 例如： 它不会显示任何输入 界面。此例提交表单时产生i d = t h e v a l u e 。 2 2 分类的基本技术 在数据挖掘的各种方法中，分类是一种主要的分析手段，旨在生成一个分类 函数或分类模型，由该模型把数据库中的数据项映射到某一给定类别中。 2 2 1 分类定义 分类可以描述如下：大量的样本构成输入数据集，即训练集( t r a i n i n g s e t ) 。每 个样本有多个属性，属性既可以是连续属性，也可以是离散属性。其中有一个属 性被称为类别属性，用来标明该样本所属的类别。那么，所谓分类就是：通过对 已知类别的训练集的分析，用样本的其他属性建立一个关于类别属性准确划分的 模型，以便用来判定新的测试数据的类别。数据分类步骤为： 1 ) 建立一个模型，描述预定的数据类集或概念集。通过分析由属性描述的 数据库元组来构造模型。假定每个元组属于一个预定义的类，由一个称作类标号 属性的属性确定。对于分类，数据元组也称为样本、实例或对象。为建立模型而 被分析的数据元组形成训练数据集。训练数据集中的单个元组称为训练样本，并 随机的由样本群选取。由于提供了每个训练样本的类标号，该步也称为有指导的 学 - - j ( 且p 模型的学习在被告知每个训练样本属于哪个类的指导下进行) 。它不同于 无指导的学习( 或聚类) ，那里每个训练样本的类标号是未知的，要学习的类集合 或数量也可能事先不知道。例如：给定一个顾客信用信息的数据库，可以学习分 类规则，根据他们的信誉优良或相当好来识别顾客( 见图2 1 ) 。 9 中南大学学位论文 第二章d e e pw e b 集成查询接口生成相关技术 图2 - 1 用分类算法分析训练数据 2 ) 使用模型进行分类( 见图2 2 ) 。首先评估模型( 或分类方法) 的预测准确率。 保持方法是一种使用类标号样本测试集的简单方法。这些样本随机选取，并独立 于训练样本。模型在给定测试集上的准确率是正确被模型分类的测试样本的百分 比。对于每个测试样本，将己知的类标号与该样本的学习模型类预测比较。对模 型的准确率，如果根据训练数据集评估，估计可能是乐观的，因此，一般使用测 试集进行评估。 图2 2 测试数据用于评估分类规则的准确率 2 2 2 分类数据的预处理 根据分类的定义可知分类方法( 分类器) 是分类的核心，其结果在多大程度上 成为对人们有用的知识。分类方法有很多种，它们各有所长。通过对它们比较评 估，一来可以扬长避短，在特定情况下使用最优的分类方法加以改进，使其性能 得到优化。可以根据下列标准比较和评估： 1 0 中南大学学位论文 第二章d e e pw e b 集成查询接口生成相关技术 1 ) 准确率 指模型正确地预测新的或未见过的数据的类标号的能力，在其他条件等同的 情况下，我们当然首选准确率高的分类模型。 2 ) 速度 指产生和使用模型的时间复杂度。如果产生和使用模型的速度很低，将严重 影响用户的使用。 3 ) 强壮性 指给定噪声数据或具有空缺值的数据，模型正确预测的能力，数据库通常有 噪声，有时还很大。如果一个分类器不善于消除噪声势必影响分类准确率。 4 1 可伸缩性 指给定大量数据，有效的构造模型的能力。有些分类器在数据量小的情况下 可以有效的构造模型，随着数据量的增大，其构造模型的能力显著下降，其最终 也会影响分类准确率。 5 ) 可解释性 指学习模型提供的理解和洞察的层次。 2 3 分类算法 目前许多分类方法已被机器学习、专家系统、关联规则、统计学和神经生物 学方面的研究者提出。如决策树，关联规则，贝叶斯，神经网络，遗传算法，基 于案例的推理等。不同的算法有不同的特点，充分认识各算法的优点和缺陷，掌 握其特定的适应环境，便于研究者明确其算法的改进点和研究方向，也便于使用 者选择和应用。 2 3 1 决策树分类 基于决策树的分类模型以其特有的优点广为人们采用。首先，决策树方法结 构简单，便于人们理解；其次，决策树模型效率高，对训练集数据量较大的情况 较为适合；第三，决策树方法通常不需要受训数据外的知识；第四，决策树方法 具有较高的分类精确度。 总的来说，决策树方法是利用信息论中的信息增益寻找示例数据库中具有最 大信息量的属性字段，建立决策树的一个节点，再根据该属性字段的不同取值建 立树的分支，在每个分枝集中重复建立树的下一个节点和分支的过程。 决策树中最重要的就是对大区分度属性的选择方法。通常认为有最高信息增 益的属性是给定数据最高区分度的属性。通过计算信息增益，可以得到属性的排 序。定义信息增益如下一1 ： 中南大学学位论文 第二章d e e pw e b 集成查询接口生成相关技术 o ：一型l 。g 型一n 。al o g 型一型l 。g 型一n o al o g 型( 2 - 1 ) 疗。刀。 刀。刀o ，气 力l刀l刀l 树的质量取决于分类精度和树的大小。一般来说，决策树的构造主要由两个 阶段组成：第一阶段，建树阶段。选取部分受训数据建立决策树，决策树是按广 度优先建立直到每个叶节点包括相同的类标记为止。第二阶段，调整阶段。用剩 余数据检验决策树，如果所建立的决策树不能正确回答所研究的问题，我们要对 决策树进行调整( 剪枝和增加节点) 直到建立一棵正确的决策树。这样在决策树每 个内部节点处进行属性值的比较，在叶节点得到结论。从根节点到叶节点的一条 路径就对应着一条规则，整棵决策树就对应着一组析取表达式规则。 i d 3 和c 4 5 是最经典的决策树算法，它们以自顶向下各个击破的方式构造 决策树。i d 3 算法的基本原理如下【3 0 l ： 设e = d l x d 2 x d 3 x x d n 是1 1 维有穷向量空间，其中d j 是有穷离散符号集，e 中的元素e - n q 做例子，其中v j d j ，j = 1 ，2 ，a ，设p e 和n e 是e 的 两个子集，分别叫做正例集和反例集。 假设向量空间e 中的正例集p e 和反例集n e 的大小分别为p 和n ，i d 3 基于 下列两个假设：( 1 ) 在向量空间e 上的一棵正确决策树对任意例子的分类概率同 e 中正反例的概率一致；( 2 ) 一棵决策树能对一个例子作出正确类别判断所需的 信息量为： j ( p ， ) ：( l l 0 9 2 上+ 三l 0 9 2 一)( 2 2 ) 如果以属性a 作为决策树的根，a 具有v 个值 v t ，v 2 ，v v ) ， 为v 个子集 e l ，e 2 ，e v ) ，假设e i 中含有p i 个正例和l l i 个反例， e i 所需的信息期望是i ，n i ) ，以属性a 为根所需的期望信息是： 剐) = 喜等( p j 因此，以a 为根的信息增益是： 它将e 分 那么子集 ( 2 - 3 ) g a i n ( a ) = i ( p ，刀) 一e ( 彳) ( 2 - 4 ) i d 3 选择使g a i n ( a ) 最大的属性a 作为根节点，对a 的不同取值对应的e 的v 个子集e i 递归调用上述过程生成a 幸的子节点b l ，b 2 ，。 i d 3 是一个典型的决策树学习系统，其核心是在决策树的各级节点上选择属 性，用信息增益作为属性选择标准，使得在每个非叶节点上进行测试时，能获得 关于被测试例子最大的类别信息，使用该属性将例子集分成子集后，系统的熵值 最小，期望该非叶节点到达后代叶节点的平均深度较小，准确率较高。 1 2 中南大学学位论文 第二章d e e pw e b 集成查询接口生成相关技术 2 3 2 贝叶斯分类 贝叶斯分类是统计学分类方法。它们可以预测类成员关系的可能性，如计算 给定样本属于一个特定类的概率。 设x 是类标记的未知的数据样本。设h 为某种假定，如数据样本x 属于某 特定的类c 。对于分类问题，我们希望确定p ( h l 为广一给定观测数据样本x ，假 定h 成立的概率。 p ( h i x ) 是后验概率，获取条件x 下h 的后验概率。例如，假定数据样本域 由水果组成，用它们的颜色和形状描述。假定x 表示红色和圆的，h 表示假定x 是苹果，则p ( h i x ) 反映当我们看到x 是红色并是圆的时，我们对x 是苹果的确 信程度。作为对比，p ( h ) 是先验概率，或h 的先验概率。对于我们的例子，它 是任意给定的数据样本为苹果的概率，而不管数据样本看上去如何。后验概率 p ( h i x ) 比先验概率p ( h ) 基于更多的信息。p ( h ) 是独立于x 的。 类似地，p ( ) ( 1 h ) 是条件h 下，x 的后验概率。即是说，它是已知x 是苹果， x 是红色并且是圆的概率。p ( x ) 是x 的先验概率。使用我们的例子，它是由水 果集取出一个数据样本是红和圆的概率。 p ( 均，p ( 1 4 ) ，p ( x i h ) 可以由给定的数据计算。贝叶斯定量是： p ( hix ) ：p ( x ih ) p ( h ) ( 2 5 ) 。 尸( x ) 、。 那么在分类中使用贝叶斯定量就是贝叶斯分类。 2 3 3 支持向量机分类 支持向量机( s u p p o r tv e r t o rm a c h i n e ，s v m ) 是v a p n i k 根据统计学习理论提出 的一种新的学习方法，近来受到国际学术界的重视。s v m 建立在计算学习理论 的结构风险最小化的原则之上，可以提高学习机的泛化能力。s v m 的复杂度与 实例集的维数无关，适合于两分类问题和线性不可分问题，因为它可将样本空间 映射到一个高维空间，使原来线性不可分的情况在高维空间中解决。现在数据挖 掘领域已经开始使用s v m 原理，构造一些数据预处理算法及挖掘算法，如s y e d 、 l i u 和s u n g 提出了两种增量学习方法，给出了三种评价增量学习算法的鲁棒性 和可行性的标准，并使用s v m 的增量学习算法进行概念提升，证明了得到的支 撑矢量可以形成一个简洁而充分的集合。由于s v m 可以选择和保存有用的训练 数据即支持矢量，取自大型数据库中的小样本的训练数据可使计算的复杂度降 低。所以，s v m 方法可用于数据预处理、样本化等k d d 的过程，也可用于其它 的数据挖掘应用。研究表明：对同一数据库，使用不同核函数训练的s v m ，在 测试数据上均具有较高的预测准确率。 1 3 中南大学学位论文 第二章d e e pw e b 集成查询接口生成相关技术 2 3 4k 最邻近分类 在图2 3 中，圆要被决定赋予哪个类，是三角形还是四方形? 如果k = 3 ，由 于三角形所占比例为2 3 ，圆将被赋予三角形那个类，如果k = 5 ，由于四方形比 例为3 5 ，因此圆被赋予四方形类。 图2 - 3k n n 算法决策过程 k 最近邻( k - n e a r e s tn e i g h b o r ，k n n ) 分类算法，是一个理论上比较成熟的方 法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空 间中的k 个最相似( 即特征空间中最邻近) 的样本中的大多数属于某一个类别，则 该样本也属于这个类别。k n n 算法中，所选择的邻居都是已经正确分类的对象。 该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本 所属的类别。k n n 方法虽然从原理上也依赖于极限定理，但在类别决策时，只 与极少量的相邻样本有关。由于k n n 方法主要靠周围有限的邻近的样本，而不 是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分 样本集来说，k n n 方法较其他方法更为适合。 k n n 算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k 个 最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。 更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值 ( w e i g h t ) ，如权值与距离成正比。 该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量 很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的k 个邻居中大容量类的样本占多数。因此可以采用权值的方法( 和该样本距离小的 邻居权值大) 来改进。该方法的另一个不足之处是计算量较大，因为对每一个待 分类的文本都要计算它到全体已知样本的距离，才能求得它的k 个最近邻点。 目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的 样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较 小的类域采用这种算法比较容易产生误分。 1 4 中南大学学位论文第三章d e e pw e b 查询接1 ：3 识别 第三章d e e pw e b 查询接口识别方法的分析和研究 查询接口是d e e pw r e b 的唯一入口，一个查询接口通常是一个w r e b 页面中用 h t m l 表示的网页表单，表单也可以分为很多类型，在对查询接口进行集成之前， 首先要识别哪些表单是d e e pw e b 查询接口。 3 1d e e pw e b 查询接口识别流程 查询接口是外部访问w e b 数据库的门户，表单是访问d e e pw e b 的唯一入口， d e e pw e b 查询接口的识别就是表单的分类，表单可以分成d e e pw e b 查询接口表 单和非d e e pw 曲查询接口表单两类。而表单通常是以h t m l 的形式镶嵌在w e b 网页中，通过对表单的h t m l 表达形式的分析，按照一定的规则提取表单特征， 然后利用合适的分类算法识别哪些表单是d e e pw r c b 查询接口，哪些是非d e e p w e b 查询接口。 非d e e pw e b 查询接1 ：3 表单主要包括搜索引擎、元搜索引擎、登陆表单、用 户注册表单，购物表单等。而其他各类常见的表单都是d e e pw 曲查询接口表单， 因此，可以得出包含d e e pw - e b 查询接口的网页是整个网络中的- d , 部分，如图 3 1 所示。 图3 - 1d e e pw e b 查询接口网页在整个网络的比例 d e e pw e b 查询接口的识别是一个复杂的过程，从图3 1 可以看出，研究对 象最初是一个一个的网页，由于网页的数量巨大，如何对网页信息进行管理也是 面临的一个问题，通常通过存储该网页的u r l 实现，整个d e e pw e b 查询接口 的识别的过程如图3 2 所示。 中南大学学位论文第三章d e e pw e b 查询接口识别 图3 - 2d e e pw e b 查询接口识别基本过程图 由图3 - 2 知d e e pw e b 查询接口的识别主要由三个部分组成：查询接口的获 取、查询接口特征的提取、查询接口分类即判断表单是否为d e e pw e b 查询接 口，在下面的几个小节将对这几个问题进行分析。 3 2 查询接口获取 查询接口都是h t m l 表单，所以要提取