（计算机应用技术专业论文）基于查询接口特征的深度网络资源聚类分析.pdf

大连理工大学硕士学位论文 摘要 互联网的快速发展，给人们带来了海量的信息，并且这些信息仍然在快速增长。整 个互联网可以划分为表层网络和深度网络两部分，其中表层网络是指通过超链接可以被 传统搜索引擎索引到的页面的集合，而深度网络指的是互联网上的网络数据库，其资源 只能通过网络数据库提供的查询接口才能访问。与表层网络相比，深度网络包含的数据 质量更高、更专业。然而，由于深度网络数据的异构性和动态性，必须对其进行数据集 成后才能有效地加以利用，而有效地把这些信息按照领域分类则是对其进行数据集成的 先决条件。 查询接口是进入深度网络的唯一途径，它首先是一个表单，但并非所有的表单都是 查询接口，对此，本文实现表单分类器将查询接口从表单中分离。同时，通过对查询接 口的实验，发现查询接口所具有的特征可以代表深度数据资源的领域及查询能力，从而 利用查询接口特征来聚类深度网络资源。查询接口与普通文本聚类一个区别在于查询接 口的特征矩阵稀疏，因此利用传统的基于距离相似度的凝聚层次聚类算法聚类效果不是 很理想，针对该问题，本文利用非参数假设检验的方法来求类簇间的相似，并改进相似 度目标函数，将其运用到传统的凝聚层次聚类算法中，实现对查询接口的聚类，从而也 就实现了对查询接口所代表的深度网络资源的聚类。 运用假设检验进行聚类时，因为统计中对事件的观察值有要求，而初始类簇不经处 理可能不满足假设检验的要求，针对该问题，本文使用对查询接v i 进行预处理的思想即 首先对所有查询接1 ：3 进行接1 ：3 类型过滤，然后根据属性间的包含程度将数据分组，再根 据属性的发生次数对组进行过滤，最后只对那些观察值满足假设检验的组进行聚类。而 那些没有通过接口检查以及不满足观察值的查询接口称为孤立接口。对孤立接口，本文 采取了再分类的方式处理它们，利用概率的方法将它们分类到其最可能来自的类簇中。 通过这种先聚类再分类的方式，最终完成对接口的聚类。实验证明，利用该思想聚类取 得较好的聚类结果。 关键词：深度网络；聚类分析；非参数假设检验；凝聚层次聚类 大连理工大学硕士学位论文 c l u s t e r i n ga n a l y s i so fd e e pw e br e s o u r c e sb a s e d o n t h eq u e r yi n t e r f a c ef e a t u r e s a b s t r a c t t h er a p i dd e v e l o p m e n to ft h ei n t e m e tb r i n g su sag r e a td e a lo fi n f o r m a t i o n ，a n dt h a t i n f o r m a t i o ni ss t i l li nr a p i dg r o w t h t h ee n t i r ei n t e r a c tc a nb ed i v i d e di n t ot w op a r t s ；s u r f a c e w e ba n dd e e pw e b t h es u r f a c ew e bc a l lb ef o u n db yt r a d i t i o n a ls e a r c he n g i n et h r o u g hu r l d e e pw e br e f e r st ot h eo n s i t ed a t a b a s ea n dt h er e s o u r c e sc a no n l yb eg o tt h r o u g ht h eq u e r y i n t e r f a c e c o m p a r i n gt o t h es u r f a c ew e b t h ed e e pw e bc o n t a i n sm o r ep r o f e s s i o n a la n d h i g h e rq u a l i t yr e s o u r e c e s h o w e v e r ，t h ed a t ao fd e e pw e ba r eh e t e r o g e n e o u sa n dd y n a m i c ， b e f o r et h ee f f e c t i v en s e , t h ed a t am u s tb ei n t e g r a t e d , w h i l et h ec l a s s i f i c a t i o ni na c c o r d a n c e w i t hm e i rd o m a i n si sap r e r e q u i s i t ef o rd a t ai n t e g r a t i o n q u e r yi n t e r f a c ei st h eo n l yw a yt oa c c e s st h ed e e pw e b ，t h eq u e r yi saf o r m ，b u tn o ta l l t h ef o r m sa r eq u e r yi n t e r f a c e , s ot h i sp a p e rp e r f o r m saf o r mc l a s s i f i e rt of i l t e rt h en o n q u e r y i n t e r f a c ef o r m s t h r o u g he x p e r i m e n t so f q u e r yi n t e r f a c e ，t h i sp a p e rf i n dt h a tt h ec h a r a c t e r i s t i c s o f q u e r yi n t e r f a c ec a nr e p r e s e n td o m a i n so f d e e pw c bd a t ar e s o u r c e sa n dq u e r yc a p a c i t y , t h u s t h i sp a p e rc l u s t e r sd e e pw e br e s o u r c e so nt h eb a s i so ff e a t u r e so fq u e r yi n t e r f a c e a d i f f e r e n c eb e t w e e nq u e r yi n t e r f a c ea n do r d i n a r yt e x tc l u s t e r i n gi st h a tt h ef e a t u r em a t r i xo f q u e r yi n t e r f a c ei ss p a r s e t h e r e f o r et h er e s u l t so fc l u s t e r i n gi si n e f f e c t i v ew i mt h et r a d i t i o n a l h i e r a r c h i c a la g g l o m e r a t i v ec l u s t e r i n ga l g o r i t h mb a s e do ns i m i l a r i t y - d i s t a n c e t os o l v et h e p r o b l e m ，t h ep a p e ru s e dt h em e t h o do fn o n p a r a m e t r i ct e s t st om e a s u r et h es i m i l a r i t ya n dt h e n o b j e c t i v ef i m c t i o no fs i m i l a r i t yd e g r e ei sa l s oi m p r o v e d w h e nt h em e t h o di sa p p l i e di n t o t r a d i t i o n a la l g o r i t h mo f h i e r a r c h i c a la g g l o m e r a t i v ec l u s t e r i n g , t h ec l u s t e r i n go f q u e r yi n t e r f a c e i sa c h i e v e d a c c o r d i n g l y t h ec l u s t e r i n go fd e e pw e bs o u i c er e p r e s e n t e db yq u e r yi n t e r f a c ei s r e a l i z e d t h er e q u i r e m e n to f h y p o t h e s i st e s t i n gi st h ea m o u n to f t h ei n c i d e n t so b s e r v a t i o nv a l u e b e f o r et h ei n i t i a lc l u s t e r sa r et r e a t e d ，t h e ym a yn o ts a t i s f yt h er e q u i r e m e n t so fh y p o t h e s i s t e s t i n g i no r d e rt os o l v et h ep r o b l e m ，t h i sp a p e rp u tf o r w a r dt h ei d e ao f p r e p r o c e s s i n g f i r s t l y , a l lq u e r yi n t e r f a c e sa r ef i l t e r e db yt y p e s e c o n d l y , d a t aa r eg r o u p e di nt e r m so ft h ei n c l u s i o n d e g r e eb e t w e e na t t r i b u t e s t h i r d l y , d i f f e r e n tg r o u p sa r ef i l t e r e db yf r e q u e n c yo fa t t r i b u t e s a t l a s to n l yt h eg r o u p sw h o s eo b s e r v a t i o n ss a t i s f i e sh y p o t h e s i sa r ec l u s t e r e d l o n e ri n t e r f a c e s a r eq u e r yi n t e r f a c ew h i c hh a s n tc o m et h r o u g ht h ei n t e r f a c ec h e c ka n dt h eo n ew h i c hn o t s a r i s f yo b s e r v a t i o nv a l u e r e c l a s s i f i c a t i o n i su s e dt od e a lw i t ht h el o n e ri n t e r f a c e s b y p r o b a b i l i s t i cm e t h o d s ，t h e ya r ec l a s s i f i e dt oc l u s t e r sf r o mw h i c ht h e ya r em o s tl i k e l yt oc o m e 基于查询接口特征的深度网络资源聚类分析 b ym e a n so ft h ew a yt h a tb e g i n sw i t hc l u s t e r i n ga n dt h e ng o e so nw i t hr e c l a s s i f i c a t i o n ，t h e c l u s t e r i n gi sc o m p l e t e df i n a l l y i ti sd e m o n s t r a t e db ye x p e r i m e n t st h a tw i t ha d o p t i n gt h ei d e aa b e t t e rc l u s t e r i n go m c o m ec a nb eg o t t e n k e yw o r d s ：d e e pw e b ；c l u s t e r i n ga n a l y s i s ；n o n p a r a r n e 啊ch y p o t h e s i st e s t s ；h i e r a r c h i c a l a g g l o m e r a t i v ec l u s t e r i n g i v 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：整兰日期：! ! m ， 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名： 韩耄 导师签名：兰垒立迄 大连理工大学硕士学位论文 1 绪论 1 1 深度网络概述 1 1 1引言 互联网自发明以来就一直呈现蓬勃发展之势，到今天为止其蕴含着海量的丰富资 源。按照其分布状况可以分为“表层网络”( s u r f a c ew e b ) 和“深度网络”( d e e pw e b ) ， 也称为( i n v i s i b l ew e b ，h i d d e nw 曲) 。表层网络( s u r f a c ew e b ) 是指存储在w e b 空间，由 超链接连接起来的静态网页、文件等资源，一般来说通过超链接就可以访问这些资源， 且静态网页在一定时间内保持不变。深度网络( d e e p w 曲) 指那些存储在网络数据库里、 不能通过超链接访问而需要通过动态网页技术访问的资源集合。这些动态网页通常是由 后台的数据库支持，只有当用户查询的时候才会由c g i 或a s p 程序产生。 隐藏网络的定义最初由d r j i l le l l s w o r t h 于1 9 9 4 年提出，然而随着技术的发展，以 前一些不可见的信息可能渐渐可见，随着对隐蔽网络的逐步了解，在2 0 0 1 年，c h r i s t s h e r m a n ，g a r yp r i c e 再次对隐蔽网络给出如下定义：虽然通过互联网络可以获取，但是 普通搜索引擎由于技术受限制而不能，或者经过审慎考虑后而不作为索引的那些文本 页、文件或者其他通常是高质量、权威的信息。 b r i g i l tp l a n e t 公司根据深度网络的特点和内容，将其分为如下几个部分1 1 ： ( 1 ) 未被链接的网页。根据搜索引擎原理，网页设计者没有向搜索引擎提供网页地 址并且没有其他网页链接，搜索引擎的s p i d e r 程序就不能沿着其网页中的u r l 爬行到该 网页，也就不能将该网页的相关信息搜索到索引库。那么通过搜索引擎就无法找到这些 未被链接的孤岛网页。这是看不见的网页的一种组成部分。 ( 2 ) 动态生成的网页。当搜索引擎的s p i d e r 程序遇到大量的由c g i 、a s p 、i a v a s c r i p t 等专门制作动态网页的脚本语言所编写的网页或者u r l 中含“? ”的动态网页时，一般 会很慎重地考虑是否索引该网页。从技术层面上讲，动态网页可以被索引，但有些程序 员编写恶意程序“诱骗”搜索引擎来索引，并由此导致s p i d e r 程序进入死循环。因此， 搜索引擎为了避免“机器人陷阱”都会拒绝索引这些动态网页。 ( 3 ) 不透明网络。不透明网络是指搜索引擎可以索引但是没有索引的网页，主要是 由于经济的原因制约和搜索频率的限制等原因造成的。 ( 4 ) 私人网络。网上可检索的数据库有两种类型：可自由获取的公共数据库和订阅 或者付费的数据库。由于搜索引擎的s p i d e r 尚不具备在交互式检索窗体中填写或选择所 需信息的能力，无法向数据库提交检索提问式。同时，对于一些必须使用用户名和密码 基于查询接口特征的深度网络资源聚类分析 登录的数据库来说，搜索引擎的s p i d e r 同样没有足够的智能注册后登录系统。因此无论 哪种类型的数据库，搜索引擎都无法获取其中的数据。这部分网络主要指个人的非公开 信息、限制访问的网页，主要指需要用户进一步登陆输入用户名和密码等条件才能访问 的页面。这种页面多通过“r o b o t s 仅t ”协议来阻止爬虫器进行页面的爬行。 ( 5 ) 实时信息。如最新新闻、股票价格、天气信息、航班信息等。因为其变化快， 搜索引擎数据库更新的速度难以跟上实时数据的更新速度，所以搜索引擎收集的多是过 时的信息，对于实时信息搜索引擎多不予收集。 ( 6 ) 动态页面。包括非h t m l 格式的文档、以及网络数据库。其中非文本文件主要 包括：多媒体文件、图像、软件和非标准化格式的文档( 比如p d f 、压缩文件、m p 3 文 件等) 。 本文重点研究的深度网络是那些动态的，能根据用户需求从专业数据库中的实时生 成的数据。这部分信息多是结构化的信息，所谓数据的结构化是指数据是以属性名一值 对的形式表现，深度网络根据信息的结构化程度，可以划分为结构化信息、文档信息和 非文本文件。网上购物网站存储的信息属于结构化信息( 它包含结构化的查询接口和结 构化的数据对象，是成对的属性值关系) 例如：a m a z o n c o m 是个关于图书查询的站点， 不论用户查询时，还是结果返回时，信息都是以书名、价格、出版社等条件进行查询， 返回的图书记录也是包含书名、价格、内容提要等信息。新闻网站存储的信息属于文档 信息，n e w s s o h u c o m 就是一个关于新闻的非结构化的站点。而非文本文件，主要包括多 媒体文件、图像文件、软件和特定格式的文档( 比如p d 玟件) 。研究表明结构化的深度 网络和非结构化的深度网络之比为3 ：1 ，而且结构化的信息质量更高，所以本文重点研究 结构化的深度网络资淤”。 1 1 2 深度网络课题研究的意义 网络信息数量迅猛增加使人们很难判断其容量。b i i g h tp l a n e t 公司根据2 0 0 0 年3 月1 3 日搜集的数据。对深度网络的规模和相关性进行了研究。结果表明，与表层网络相比， 深度网络蕴含着更加丰富，更加专业( 专注于某一个领域) 的信息。据b r i g h tp l a n e t 公司 的技术白皮书统计，深度网络资源容量很大而且包含着更多有价值的资源。以下简述部 分研究结果i lj ： ( 1 ) 深度网络里包含的可访问公共信息容量是本文熟知的s u r f a c ew e b 的4 0 0 - - 5 0 0 倍。 ( 2 ) 深度网络包含7 5 0 0 t b 的信息，而s u r f a c ew e b 包含的信息容量只有1 9 t b 。 ( 3 ) 现有的深度网络站点估计超过1 0 0 ，0 0 0 个。 一2 大连理工大学硕士学位论文 ( 4 ) 平均看，深度网络站点的月访问量比s u r f a c e w e b 站点高出5 0 ，并且与s u r f a c e w e b 站点相比有更多的链接。可是那些典型的大型深度网络站点在互联网搜索领域却不 知名。 ( 5 ) 深度网络站点在信息内容范围上比一般s u r f a c e w e b 站点更专更深。 ( 6 ) 深度网络包含的有效高质内容总量至少是s u r f a c ew e b 的1 0 0 0 至l j 2 0 0 0 倍。 ( 7 ) 超过一半的深度网络内容都保存在专业领域的数据库中。 ( 8 ) 9 5 的深度网络信息都是面向公共访问的，而不是需要付费或者订阅的。 调查证明，这些通过用户输入信息，从后台数据库中自动生成的文件，其价值远远 高于表面网络的数据，而且，其访问量之高，数据量之庞大，数据质量之高让越来越多 的人开始关注深度网络。如何挖掘深度网络并且有效利用这些信息成为信息检索研究的 一个重要部分。 考虑以下情景，某个用户想在网上查询购房信息，在购买前想了解一下房屋相关的 内容和价格等具体信息。因此，用户首先需要找到一些网上房屋交易的网址，登陆到这 些网站的主页，向每个表单填写查询关键词，从返回的结果页中找到相关信息，对搜集 的结果进行筛选比较。因此，这就产生了新的信息服务需求，可否向用户提交一个统一 的查询接口，将该集成接口不仅包含了该领域的主要属性，而且还集成了该领域中某些 接口种所包含的特有的接口属性，通过这样一个接口，用户提交操作后，无须关注查询 接口背后的事情，只要根据返回的结果选择感兴趣的进行查看即可。这样省去了用户在 多个站点中查询、比对的过程，大大方便了用户查询。所以产生需要针对领域的集成接 口这样一种需求，但是将深度网络中的信息加以集成的前提则是将深度网络资源按照领 域进行聚类。本文主要研究深度网络按领域聚类，并且使用查询接口对网络进行聚类， 为今后的集成作准备。 1 2 深度网络现状和未来发展趋势 深度网络中蕴含了海量的可供访问的信息，并且还在迅速的增长。但是目前国内对 深度网络的搜索与挖掘方面的研究尚处于学习、跟踪和探索阶段，国内该领域的研究单 位及相关报道非常少，而且数据源的分类还是一个刚刚起步的过程，查询接口的集成多 是在已经手动分类好的一些数据源基础上进行的研究。由于搜索引擎目前还不能提供对 深度网络的搜索服务，分类目录服务是目前检索深度网络的一个途径，国内也出现一些 深度网络分类目录服务站点，但尚处于手工处理阶段，还不能实现自动化或半自动化索 引处趔3 1 。 基于查询接口特征的深度网络资源聚类分析 随着w e b 数据库在w e b 中不断大量的涌现，对w e b 数据库进行大规模集成的研究 成为一个非常迫切的问趔3 1 。而国外仅有b f i g h t p l a n e t 和d e e p w e b 以及i n v i s i b l e w e b 三 家公司生产相关产品。他们都采用半自动方式，人工干预较多而且目前还没有中文深度 网络信息服务一j 。 w a s h i n g t o n 大学的研究小组设计了一个针对消费产品的比较代理s h o p b o t 【5 】，它利 用特定领域的启发式方法来填写表单以比较其领域内的商业产品。其聚焦于处理卖主站 点的表单提交页面所返回的的产品列表。s h o p b o t 操作分为两个阶段：离线学习阶段和 在线产品比较阶段。在学习阶段，确定如何填写站点表单，以及对产品站点结果页面进 行分析获取其站点模式信息。在比较阶段，利用得到的站点模式结构来抽取结果信息， 寻找满足用户要求价格最优的产品，最终将这些产品信息格式化输出。可以看出其研究 领域非常狭窄，不适用于大规模的信息集成。 s t a n f o r d 大学的r a g h a v a ng a r c i a - m o l i n a 专注于研究如何发现站点中的深度网络资 源，设计了一种可以抽取深度网络信息的爬虫h i d d d e nw e be x p o s e r ( h i w e ) 【6 】。在此系 统中爬虫管理器负责管理搜集过程。它对下载的w e b 页面进行分析，包含表单的页面 被送到表单处理器中处理。由于需要系统自动完成表单填写，所以要求用户预先准备相 应的表单数据集。h i w e 只能面向特定的领域使用，而且必须在人工辅助下完成。因此 存在很大的局限性【”。 在集成系统方向上，w i s e - i n t e g r a t o r 8 】是对商务领域的深度网络进行数据集成的一个 系统，接口的集成是该系统其中的一个重要组成部分。它是一个综合的解决方案，首先 对每个查询接口进行分析，获取其中的属性信息。在语义分析的过程中用到了一个很重 要的工具w o r d n e t 3 。然后就是属性匹配，在完成对所有查询接口的属性匹配后，要为匹 配的属性在集成的查询接口上确定它的全局名称和它的类型和取值范围，这样就得到了 一个集成的查询接口。 针对数据库的分类，除了根据查询接口的属性进行分析从而分类之外，还可以通过 在查询接口上提交与领域相关的查询，根据返回结果进行分类，这是直接判断一个w 曲 数据库属于哪个领域的最有效方法。以汽车、音乐和图书三个领域的分类为例，如果提 交“t o y o t a ”的查询，后两个领域的w e b 数据库将不会返回任何结果，而汽车领域的 w c b 数据库则可能返回若干结果。 c o l o m b i a 大学的q p r o b e r 研究小组重点研究了深度网络的分类，它首先使用机器学 习技术生成一套基于规则的分类器( c l a s s i f i e r ) 【9 】。然后抽取分类器规则和基本u r l 组合 成查询u r l ，对后台数据库进行查询探测，计算查询结果数。其算法最后根据查询结果 大连理工大学硕士学位论文 数对数据库进行分类。然而其研究只集中文档数据库分类上，但实际上大量的深度网络 数据库提供的内容是结构化的数据。 至今，人们在深度网络领域已经作了一定的研究，但它们只是属于研究性的原型系 统，因此确切地说至今还没有一个真正可以作为实际应用的深度网络数据集成系统，而 且在集成的准备阶段，大部分工作仍然处于探索性的阶段。所以总的来说对深度网络数 据的研究仍然处于剐刚起步的阶段，离应用阶段还有很长的路要走，仍然有大量关键的 问题还需要做深入细致的研究。 1 3 本文主要内容 本论文的主要研究工作包括几个方面： 第一章为本文的绪论部分，首先介绍了深度网络的相关背景知识，具体包含深度网 络不可见的原因，分类方式以及研究意义，然后介绍了国内外研究状况和未来发展趋势。 第二章阐述了论文中的相关背景知识，对聚类基本知识给予简单概述，同时简要说 明了深度网络站点发现以及表单特征抽取的相关知识。 第三章研究了如何发现深度网络，这包括发现深度网络的站点以及在此基础上对表 单分类。通过查询接口中表单控件的特征生成特征集，在比较了几种分类结果之后，选 择决策树作为本文的分类算法。最终将表单划分为查询接口和非研究表单，后续聚类以 及分类操作都在查询接口上进行，为后续针对查询接口聚类做了充分的准备。 第四章本文通过对查询接口的观察实验，选择利用查询接口对深度网络资源进行按 领域聚类。查询接口的特征不同于其他文本，它的特征稀疏，如果使用基于距离的聚类 算法来评估相似性效果不是很理想，所以本文利用非参数假设检验的方法，利用模型相 似性的方法来聚类查询接口，避开了因查询接口特征稀疏带来的消极影响。将这种基于 模型相似性的相似性函数用于传统的凝聚层次聚类算法中，具有一定的挑战，因为假设 检验对事件的观察值有要求，不满足条件的无法使用假设检验的方法，针对该问题，本 文使用了查询接口预处理的过程，包括：查询接口类型识别、数据分组以及分组过滤， 最终选择观察值满足条件的查询接口，运用假设检验的方法，而那些不满足观察值条件 的组，本文利用概率的方法，将其分类到已经聚好的类簇中，通过这种先聚类再分类的 思想解决所有属性的分类问题。本章重点讲述了聚类的预处理以及进行聚类和孤立接口 分类的全过程。 第五章利用美国i l l i n o i s 大学所得到的表单作为数据集，运用本文的基于模型相似 性的凝聚层次聚类算法进行聚类，并且用同时考虑了分类准确率与召回率两方面效果的 基于查询接口特征的深度网络资源聚类分析 评估参数f - m e a s u r e 来评估聚类效果，同时与传统的基于距离的凝聚层次算法进行比较， 通过该值可以看出本文基于模型相似性的聚类方法在准确率上有一定的提高。 大连理工大学硕士学位论文 2 相关知识介绍 2 1聚类概述 聚类( c l u s t e r i n g ) 就是将物理或抽象的集合分组成为由类似的对象组成的多个类的 过程。它是在无监督的情况下根据一定的相似性或距离计算函数自动的将数据集分成若 干类【l o 】。其主要依据是把相似的样本归为一类，而把差异大的样本区分开来，这样所生 成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其它簇中的 对象彼此相异。在许多应用中可以把一个簇中的数据对象当作一个整体来对待。 在很多应用中，聚类分析作为一种数据预处理过程，是进一步分析和处理数据的基 础。聚类通过一些计算来把对象进行合理的分离，使得同一类的对象比较接近，不同类 的对象相差较多，这是无指导的学习。按照聚类的原理和方法，主要的聚类算法可以分 为：划分方法、层次方法、基于密度的方法、基于网格的方法和基于模型的方法。近年 来又出现了将多次聚类结果进行合并的聚类融合方法。图2 1 展示了各种聚类算法之间 的层次关系。 图2 1 聚类算法之间的层次关系 f i g 2 1r e l a t i o n s h i pb e t w e e nc l u s t e r i n ga l g o r i t h m s 如图2 1 所描述，聚类分析方法主要有以下几种：划分方法，层次方法，基于密度 的方法，基于网格的方法等。一些典型算法如下： 基于查询接口特征的深度网络资源聚类分析 ( 1 ) 划分法的代表算法有：k - m e a n s 算法，k m e d o i d s 算法等； ( 2 ) 层次法的代表算法有：b i r c h 算法，c u r e 算法等； ( 3 ) 基于密度的方法的代表算法有：o p t i c s 算法，d b s c a n 算法，d e n c l u e 算 法等，w a v e c l u s t e r 算法； ( 4 ) 基于网格的方法的代表算法有：s t i n g 算法，c l i q u e 算法，w a v e c l u s t e r 算法掣1 1 】； 下面重点介绍层次聚类算法以及基于模型的聚类算法： 层次聚类方法是聚类分析的一个重要方法，是对给定数据对象集合进行层次的分 解。这种方法对给定的数据集合进行层次的分解，根据层次的分解如何形成，它又可分 为凝聚法( 也称自底向上方法) 和分裂法( 也称为从上向下方法) 。凝聚的方法属于合并 法，也称自底向上法，开始将每个对象作为单独的一个簇类，然后相继地合并相近的对 象或簇类，直到所有的组合并为一个( 层次的最上层) ，或者达到一个终止条件。分裂的 方法，也称为自顶向下的方法，一开始将所有的对象置于一个簇类中，在迭代的每一步 中，一个簇类被分裂为更小的簇类，直到最终每个对象在单独的一个簇类中，或者达到 一个终止条件1 ”。在文档聚类中，由于用于分裂法的实现算法较少，所以层次法中主要 以凝聚法为主，本文这里只讨论凝聚层次聚类算法。 设有r 个数据对象的集合，品= 缸，x 2 ，x n ，若想要聚成足个类( 事先给定目，凝 聚的层次聚类算法步骤如下： b e g i n k = n ，c f = 锄 ，i = 1 ，2 ，” w h i l ek kd o 找到c f 与o 之间的距离d ( g ，o 最小的一对 c i 与c ，合并成一个类c f 去除c ， k = k - 1 e n dw h i l e e n d 凝聚的层次聚类算法描述为： 输入：待聚类对象的集合 输出：聚类层次树 ( 1 ) 初始构造n 个簇类，每个文档自成一簇类； ( 2 ) 计算各个对象之间的相似度； ( 3 ) 找出两个最相似的文档或点( 这里的点包括文档和簇类) ，将其合并成一个新簇 类： 大连理工大学硕士学位论文 ( 4 ) 计算新类与当前簇类的相似性，更新相似性，若簇类数等于1 或者达到一个停 止准则k ，则跳至( 5 ) ，否则跳至( 3 ) 。 ( 5 ) 根据选定分类阀值，决定簇类的个数和簇类f 1 1 】。 所谓停止准则是指用户提前定义的聚类数目，或者聚类程度，达到一定的聚类数目 或聚类程度，聚类自动停止。在文本分类中，将文档集d f d l ，d i ，d n 中的每一个 文档d i 看作一个具有单个成员的簇类c i - ( d i ) ，这些簇类构成了d 的一个聚类c = c l ， c i ，c n ) ；计算c 中每对簇类( c i ，c i ) 之间的相似度s i m ( c i ，c j ) 形成初始相似度，选取 具有最大相似度的簇类对m a x ( s i m c i ，c i ) ，并将c i , c j 合并为一个新的簇类中 c k = c u o ，从而构成d 的一个新的簇类c 暑 c l ，c 叫) ，更新相似度；重复上述步骤， 直到c 中只剩下一个类或满足停止规则为止。聚类过程如图2 2 所示，对于数据对象徊， b ，c ，d ，p ，的凝聚的和分裂的层次聚类过程。 凝聚的 主!兰!：兰： ： + ；了i i j 压丐五 - 分裂的 图2 2 层次聚类过程示例 f i g 2 2e x a m p l eo f h i e r a r c h i c a la g g l o m e r a t i v ec l u s t e r 现在算法研究主要集中在凝聚层次聚类方面，分裂方面的很少。不同的簇类间相似 性测度函数应用到上述程序中，就会得到不同的层次凝聚方法。其中，层次凝聚算法中 类间距离j ( c j ，c p 的相似度度量是关键的一步，选择不同的度量方法直接影响聚类的 效果。类间距离的度量方法有以下四种【12 】： 中心间距，也称平均值距离：以类中心的距离作为类问距离。表示为式( 2 1 ) ： d = l p f m 川 ( 2 1 ) t 其中m 。= 二y x ，m 是属于的对象c j 数。 基于查询接口特征的深度网络资源聚类分析 单链接，也称最小距离：是指以两个类中离得最近的两个数据对象的距离作为类 间距离，如式( 2 2 ) 。 d = m i nl i 工，一x ，0 ( 2 2 ) * e c 6 q ” 川 完全链接，也称最大距离：是指以两个类中离得最远的两个数据对象的距离作为类 间距离，如式( 2 3 ) 。 d = m a xi i x , 一工 ( 2 3 ) c ，- c j ” 。” 平均链接，也称平均距离：是用两个类所有数据点距离对的均值作为两个类间的距 离，如式( 2 4 ) 。 d = k i i 一_ o i i ( 2 4 ) ”h 一一 j ”t ”ix l e c i1j e c f 从上面对聚类的介绍可以看出，聚类的方法很多，效果也各不相同，但是大致上可 以把这些方法分成两类：一类为基于距离或相似度的方法，也被称之为区分式方法；另 一类是基于模型的方法，也可以称之为生成式方法【”】。在基于距离或者相似度的方法中， 首先需要确定一个计算距离或者相似度的方程，通过这个方程来确定哪些数据较为相 似，从而把他们归为一簇。相似度或距离计算方程的选取对于此类方法来说是很重要的， 因为它将直接影响到聚类效果的好坏。当对一种结构比较复杂的数据进行聚类处理的时 候，相似度方程的选取通常是要依赖于数据和专业的知识背景的，而对很多的应用领域， 数据被计算的次序也会影响计算的结果，所以目前还没有一个相似度的计算方法能够很 好的符合所有聚类数据的要求。这样看来，在基于距离或者相似度的聚类方法中，距离 或者相似度的选取本身就是一个很困难得事情。 近年来，以模型为基础的数据分析方法，得到了人们的关注。它的主要思想是假设 数据空间中的每一个数据都是产生于一个统一的模型【l4 1 。例如，当用某种概率密度模型 表示数据空间的时候，那么假设数据空间中的每一个数据都服从该概率分布。这种方法 在数据挖掘、模式识别等方面得到了广泛的应用，并且取得了很好的效果。在文本聚类 中也有很多的方法应用了这项技术：自组织特征映射( s e l f - o r g a n i z a t i o nf e a m r em a p ， s o m ) ；从神经网络的角度出发进行文本聚类；高斯混合模型【l5 1 ，混合多项式，这些方 法通过为簇对象建立某种模型，并且对模型进行优化来完成聚类。 大连理工大学硕士学位论文 ln 图2 3 概率模型 f i g 2 3p r o b a b i l i t ym o d e l 如图2 3 所示，右侧n 是要进行分析的数据集合，这个样本空间中包含n 个数据样 本 m 1 ，m e ，m 。) ，即前文中的模型，每一种类簇都来自这样一个模型。一般都是假设 属于同一种分布，只是这些分布的参数不同，根据计算每一个数据样本落在不同模型中 的概率来决定该样本应该属于哪一个簇，于是就建立了数据同概率模型之问的联系，也 就是图中两种空间之间的联线 1 6 , 1 7 。基于模型的方法从另一个角度出发，试图从有待聚 类的数据集中学习一组生成式的模型，这组模型中的每个子模型都是代表着某一个具体 的簇。模型可以用很多的形式进行表示，其中概率分布是一种典型的表示形式。在确定 了概率模型之后，需要用数学的方法使模型与数据拟合。目前，已经研究得出许多的概 率模型聚类技术，并且这些技术已经在各个不同的领域已经产生了很好的效果。 查询接口的聚类不同于其他文本聚类，它的特征稀疏的情况，针对该问题，利用传 统的基于距离的相似性方法效果不太理想【l8 1 ，本文通过对查询接口分布实验的发现，查 询接口的分布根据领域的不同很可能来自不同的模型，所以本文使用基于模型的思想， 对于每一个数据簇，使用一个概率模型来进行表示，这种表示方法从全局的角度表示了 一个簇的抽象结构，这样也就可以从全局的角度来对数据进行分析，从而达到更好的聚 类效果；再者，使用以模型为基础的聚类算法符合对查询接口聚类的情况。 2 2 深度网络站点发现 近年来互联网数据信息尤其是在线数据库越来越多地隐藏在w e b 查询接口后面， 想要获取深度网络信息的第一步就是要发现网络上的深度网络数据源，从而找到进入深 度网络的查询接口。即深度网络数据库的数据发现包括两个方面：首先需要找到w 西 数据库所在的网站；其次从获得的网站中找到表单，并且将那些可以与数据库交互，从 数据库中得到信息的查询接口从表单中分类出来。 基于查询接口特征的深度网络资源聚类分析 针对发现w c b 数据库所在的网站，想要比较全面而且准确的把它们从w e b 中搜索 出来是一件非常困难而又耗时的事情，这些自主的、相互独立的w e b 数据库分布在整 个w e b 的各个角落，虽然对w e b 数据库做了搜集与整理，但从表2 1 中可以看到只覆 盖了全部w e b 数据库的很少一部分；其次w e b 是动态的、不断变化的，w e b 数据库 也是如此，不断有新的产生和旧的消失，即使现存的w e b 数据库内容和规模也处于不 断变化之中，所以想要找到w c b 数据库的所有站点是很困难的。 表2 1 深度网络的目录覆盖率 t a b 2 1t h eo v e r l a pr a t eo f d e e pw e bd i r e c t o r y 针对这个问题，本文通过对深度网络的研究，总结出3 种发现w e b 数据的方法，帮 助检索者查找所需信息。 ( 1 ) 利用搜索引擎或者网络指南“间接”查找看不见的网络资源 由于查询接口存在于静态的页面中，因此可以被传统的搜索引擎爬取到。如果能够 利用成熟的传统搜索引擎完成对w e b 数据库的搜索是一种行之有效的办法。搜索引擎 获取页面唯一途径是提交关键词查询，而包含w e b 数据库查询接口的页面只占全部页 面很小的比例，如果提交的关键词不合理，会导致搜索到的页面结果集中所包含的查询 接口比例太小，使得不仅每次获得的w e b 数据库数量少，而且也会使筛选的代价过高。 因此设计合理的关键词查询是利用搜索引擎获取w 西数据库的关键问题。 本文发现一些著名的通用搜索引擎或网络指南，比如g o o g l e 和y a h o o ! 都提供了查 找数据库的功能。如果用户要查找有关某个主题的信息内容可以在搜索栏中输入主题 词，主题词后面再输入“d a t a b a s e ”。但是用这种方式迂回地查找“看不见的网站”通 常比较费时，所花精力也较多，而且通用搜索引擎或网络指南由于经费等各种原因，所 搜罗的专业数据库也不是很全面系统。因此，越来越多的网站和公司开始着手创建一种 新型的搜索工具，这种搜索工具专门针对“看不见的网站”，致力于查找网上专业数据 库中的深层信息内容，力图尽可能多地发掘出网络中不为一般人所知的有极高价值的信 息，为用户提供直接查找看不见的网络资源的手段。 ( 2 ) 利用专门的搜索工具 大连理工大学硕士学位论文 目前针对深度网络，出现了一种新的搜索工具，它就像检索者的向导一样，帮助其 在茫茫的“看不见的网站”中查询所需要的信息资源，下面举出几个比较有代表性的网 站的此类搜索工具。主要是b r i g h t p l a n e 和d e e p w e b 以及i n v i s i b l e w e b 这三家公司生产 相关产品。他们都采用半自动方式按照自己的分类方式将各个深度网络的