（计算机应用技术专业论文）deep+web下不确定数据处理的研究.pdf

at h e s i sf o rt h ed e g r e eo fm a s t e ri nc o m p u t e r a p p l i c a t i o n1 c h n o l o g y s t u d y o np r o c e s s i n g u n c e r t a i nd a t ai nd e e pw e b b yg a oc o n g s u p e r v i s o r ：p r o f e s s o rs h e nd e r o n g o r t h e a s t e r nu n i v e r s i 锣 j u n e2 0 0 8 f 协 t - 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示 谢意。 y 学位论文作者签名：、匀籽 日期：加扩- 7 j 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 作者和导师同意网上交流的时间为作者获得学位后： 半年一一年口一年半口两年口 学位论文作者签名：高聪 签字日期：o 釉分7 7 导师签名：呻传孽 签字日期：跏8 7 i i 一 蜘 ， y 东北大学硕士学位论文摘要 d e e pw 曲下不确定数据处理的研究 摘要 随着w 曲相关技术的日益成熟和d e e pw 曲所蕴含信息量的快速增长，通过对w 曲 数据库的访问逐渐成为获取信息的丰要手段，对d e 印w 曲的研究也越来越受到人们的 关注。d e 印w 曲蕴藏了更加丰富，更加“专业 ( 专注于某一领域) 的信息。为了帮助 人们快速、准确地利用d e 印w 曲中的海量信息，数据集成成为d e 印w 曲研究领域的 一个重要方向。 在d e 印w 曲数据集成过程中，数据级、映射级、查询级都会产生不确定数据。首 先，由于系统处理的数据多种多样，有些数据本身就具有不确定性，并且从文本或半结 构化的数据源中抽取信息等技术都会产生不确定数据；其次，当数据源与中介模式进行 映射时，也很有可能产生不确定性的映射关系；最后，用户查询的关键字和结构化查询 内容之间对应关系也同样不确定。 面对海量的不确定数据，为了满足用户得到感兴趣的信息的要求，本文提出了在 d e 印w 曲下不确定数据的处理模型。即首先分析不确定数据的不同来源，对相似度计 算方法分类，选择合理的匹配相似度算法或语义相似度算法来得到属性值对应的概率 值。再利用数据挖掘相关知识来获得用户感兴趣的信息。关联规则挖掘是数据挖掘一个 重要的研究方向，目前大多数的算法集中于提高挖掘包含确定数据的事务频繁集效率。 本文改进经典的a p r i 耐和f p g r o w m 数据挖掘算法，得到u d a 埘o r i 算法和 u d f p g f o w t l l 算法进行不确定数据的处理。其中，u d a p r i o r i 算法是使用一种称作逐层 搜索的迭代方法，k 项集用于探索( k + 1 ) 项集。同时利用a 州o r i 性质的反单调性，压缩 运算的时间和空间。u d f p g r o w t h 算法继承了f p g r o 、砒算法，采用分而治之的策略。 该算法基本思想是将整个数据库压缩表示成树结构u d f p t r e e ，并将频繁模式挖掘过程 转化为递归产生条件子树的过程。 u d a p r i o r i 算法和u d f p g r o 、m 算法能高效挖掘不确定数据频繁集，发现不确定 数据之间的关联关系，为数据库中缺失的信息提供参考数据，为用户从未知到己知提供 更多信息。 关键词：d e 印w 曲；不确定数据；相似度算法；频繁集；u d a p r i o d ；u d f p g r o w m i i 一 r 1_j叫111 f 东北大学硕士学位论文abs仃act s t u d yo np r o c e s s i n gu n c e r t a i nd a t ai nd e e pw e b a b s t r a c t n o w a d a y s ，w i t ht h ed e v e l o p m e i l t o fw 曲t e c h n 0 1 0 9 ya i l dm er 印i dg r 0 叭ho fw 曲 d a t 吞b a s e s ，a c c e s s i n gw e _ bd a ta _ b a s ei st h em a i nm e t h o do fo b t a i n i n gi n f o 肌a t i o n t h e r e s e a r c h e so nd e 印w 曲i n c r e a s i n g l ya t t r a c tp e o p l e sa t t e i l t i o n d e 印w 曲d a t a b a s e sc o n t a i n m o r ea b u n d a n ta i l dm o r ep r o f e s s i o n a li n f o m a t i o n ( m a i n l yf o c u so nd o m a i n ) d a t ai n t e 黟a t i o n i su s o dt os a t i s 匆u s e r s r e q u i r eo fo b t a i n i n gi n f o m a t i o nr a p i d l y 狮dc o n c c t l y t i l e r ea r em a n ys i t u a t i o n si n v o l v i n gu n c e r t a i n t yi nt h ep r o c e s s e so fd a t ai n t e 伊a t i o ns u c h a sa t t r i b u t ev a l u e sm a p p i n g ，s c h e m am a t c h i n g ，k e y w o r d sq u e 巧a n ds oo n f i r s t l y 吼c e i t a i n d a t ac o u l db ep r o d u c e di i lm ep r o c e s so fi n f o m a t i o ne x t r a c t i o n 丘_ o mt 1 1 et e x to r s e m i s t n l c t 眦dd a t as o u r c e s s e c o n d l y m em a p p i n gr e l a t i o n sa r eu n c e r t a i nw h e i lm em e d i a t e m o d u l em a t c h i n gw i t h l ed a t as o u r c e s t h i r d l y ，t h er e l a t i o n s h i pb 酣e e nt h ek e y w o r d sa 1 1 d t h es 饥l c t l l r e dq u e 叫c o n t 即ti sa l s ou n c e r t a i n am o d u l ep r o c e s s i n g 眦c e r t a i nd a t ai nd e 印w 曲t os o l v et l l ep r o b l 锄i sp r o p o s e di nt h i s t h e s i s f i r s to fa l l ，d i f f 打e n ts i t u a t i o n sp r o d u c i n gu n c e r t a i nd a t aa i l ds i m i l a r i t ym e a s u r c sb a s e d o nm a t c h i n go rs e l l l a i l t i ca r e 锄a l y s e d t l l ee x i s t e n t i a lp r o b a b i l i t yi sc o m p u t e db yr e a s o n a b l e s i m i l a r i t ym e a s u r e s i i la d d i t i o n ，t h em o d u l ea d o p t s d a t am i n i n gm e t h o d st om i n et h e i n f o n n a t i o nw h i c ht h eu s e r si n t e r e s t e di 1 1 a s s o c i a t e dn l l e sm i n i n gh a sb e e na ni n l p o r t a n t s u 巧e c ta m o n gd a t am i n i n g g e n e r a l l y ，m o s t s t u d i e sf o c u so n i m p r o v i n ga l g o r i t h m i c e 佑c i e l l c yf o rf i n d i n g 行e q u e i l tp a t t e 订l sf 如m 仃a d i t i o n a lp r e c i s ed 撕b a u s e t h et r a d i t i o n a ld a t am i n i n ga 1 9 0 r i t h m sa p r i o r ia 1 1 df p - g r o w t ha r ci m p r 0 v e di nt l l et h e s i s u d a p r i o r ia l g o r i t h mu s e sa ni t e r a t i v ec a l c u l a t i o nm e t h o dl a y e rb yl a y e r t h ek i t 锄s e ti s u s e df o rc o m p u t i n g ( 1 ( + 1 ) - i t 锄s e t t h ep r o p e r t yc a l l e da n t i m o n o t o n ec o m p r e s s e st i m ea i l d f e d u c e ss p a c ec o m p l e x i t y u d - f p - g r o w c ha l g o d t l l l l lc o m p r e s s e st h ee i l t i r ed a t a b a s et oa 骶e - s t m c t u r cc a l l e du d f p 一仃e e f r e q u e n tp a t t e n lm i n i n gp r o c e s sw i l lb et r a l l s f 0 m e di n t o p r o d u c i n ga l l dm i n i n gs u b t r e er e c u r s i v e ly t h e 帆oa l g o r i t t u i l sm i n e 丘e q u e i l tp a t t e m se m c i e i l t l ya 1 1 dd i s c o v e 巧t h e 嬲s o c i a t i o nm l e s i n 缸a n s a c t i o nd a ta _ b a s ec o n t a i n i n gu n c e r t a i nd a t a t h er e s u l t sc o u l ds u p p l yt 1 1 el o s i n g i n f o m a t i o ni np r o f e s s i o n a ld a t a b a s ea i l dp r o v i d em o r eu s e 向l i n f o m a t i o nt ou s e r s k e yw o r d s ：d e 印w 曲；l l n c e r t a i nd a t a ；s i m i l 撕够m e a s u r e s ；舶q u e n tp a t t e h l s ；u d a p r i o r i ； u d f p g r o w t h i i i 一 、， q ， ? y l 髟 l 东北大学硕士学位论文目录 目录 独创性声明i 摘要i i a b s t r a c t i i i 第1 章绪论1 1 1 引言1 1 2 国内外研究现状2 1 3 本文要讨论的问题6 1 4 本文的组织结构6 第2 章相关知识介绍7 2 1d e 印w 曲介绍7 2 2 相似度度量方法8 2 2 1 基于字符匹配的相似度度量方法9 2 2 2 基于语义的相似度度量方法1 0 2 3 数据挖掘简介1 l 2 3 1 对不确定数据挖掘的必要性1 1 2 3 2 关联规则相关的算法1 1 2 4 本章小结1 2 第3 章d e e pw e b 下不确定数据处理模型1 3 3 1 研究不确定数据的必要性1 3 3 2d e 印w 曲数据集成结构1 4 3 3 数据集成中产生不确定的三个层次1 6 3 4d e 印w 曲下不确定数据的来源1 7 3 5d e 印w 曲下不确定数据处理模型。1 8 3 6 本章小结1 8 第4 章d e e pw e b 下不确定数据描述。1 9 一i v 东北大学硕士学位论文目录 4 1 不确定数据表示类型1 9 4 2 不确定数据的描述和分类1 9 4 3 基于字符匹配的不确定数据概率值计算方法2 0 4 3 1q 伊锄s 相似度度量方法2 0 4 3 2w h i r l 和q - 鲫n sw i t ht i d f 度量方法。2 0 4 3 3j a r o w i i l l ( 1 e rd i s t a l l c e 相似度度量方法2 1 4 4 基于语义不确定数据概率值计算方法2 2 4 5 本章小结2 3 第5 章不确定数据频繁集的挖掘2 5 5 1 相关概念2 5 5 2 挖掘关联规则经典算法2 6 5 2 1 经典的关联规则挖掘算法a p r i o r i 算法2 6 5 2 2 不产生候选集的挖掘算法f p g r o 、砒算法。3 1 5 3 基于不确定数据的关联规则算法3 5 5 3 1 不确定数据挖掘方法叫7 d a 研o r i 算法3 7 5 3 2 不确定数据挖掘方法u d f p g r o 叭h 算法4 1 5 4 本章小结4 6 第6 章算法实现和测试4 7 6 1u d - a p d o r i 算法与u d f p g r o 、础算法比较4 7 6 2 领域内参数的确定4 9 6 3 本章小结5 0 第7 章总结和展望5 l 7 1 总结51 7 2 展望51 参考文献5 3 致谢5 7 攻读硕士期间发表的论文5 8 一v 一 东北大学硕士学位论文第1 章绪论 第1 章绪论 1 1 引言 数据管理中的不确定问题并不是一个新兴问题，早在十几年前的论文中就对此有所 提及，例如上世纪八十年代末开始出现的概率数据库研究，这一研究认为元组在数据库 中的存在具有不确定性、属性值具有不确定性、查询应答也具有不确定性。但是，一直 以来，人们对不确定性问题认识不足，这也决定了人们对待不确定数据管理的态度，很 多研究工作虽然遇到了不确定性问题，但往往采取传统的“去除不确定性”方法避开对 不确定数据的管理。 近两年来，不确定性问题逐渐引起了人们的广泛关注和兴趣，人们开始承认数据不 确定性的本质，v l d b 、s i g m o d 等数据库领域重要国际会议上相继出现了这方面的相 关论文。数据管理中的不确定性问题引起了人们的普遍重视，成为一个新的研究焦点。 随着w b d d 、i d ew 曲的飞速发展，出现了越来越多的可以在线访问的数据库，我 们把这些数据库称作w 曲数据库。据统计，目前w 曲数据库的数量已经超过了4 5 万个， 在此基础上构成了d e 印w 曲。d e 印w 曲蕴藏了更加丰富，更加“专业( 专注于某一 领域) 的信息，其价值远远超过了仅由网页构成的s u m c ew 曲。但由于对w 曲数据库 的访问只能通过其提供的查询接口，因此很难被一般的搜索引擎获取到。基于d e 印w 曲 的大规模性、动态性以及异质性等特点，通过手工方式远远不能在效果和效率上满足用 户对信息获取的需要。为了帮助人们快速、准确地利用d e 印w 曲中的海量信息，研究 者们已经在d e 印w 曲数据集成方面展开了研究。在基于d e 印w 曲的数据集成的研究 中，不确定问题随之而来，面对海量的数据，面对在不同的处理过程中产生不确定性的 情况，为了满足人们获取专业知识的需求，可以运用数据挖掘知识来解决这类问题。近 几年来，随着对不确定数据的认识程度的不断加深以及数据挖掘技术的广泛应用，在 d e 印w 曲下对数据挖掘是不确定数据重要的应用之一。 关联规则挖掘是数据挖掘一个重要的研究方向。目前大多数的算法集中于提高挖掘 事务频繁集的效率，研究对象是传统的事务数据库，并且事务中的项被认为是确定精确 的。如果挖掘模型不能准确地描述或者没有充分考虑挖掘对象的不确定性，那么由挖掘 模型得到的结果是不可信的，甚至是错误的。 现实世界中存在大量的由各种原因引起的不确定数据。数据挖掘方法只有充分考虑 数据的不确定性，才能对数据去伪存真，才能得到基于不确定数据的准确反映客观事物 知识的挖掘模型。基于d e 印w 曲中数据的不确定性，属性值映射的不确定性，用户查 询的不确定性等特征，迫切需要将传统的数据挖掘方法进行改进，扩展算法处理数据的 一1 一 东北大学硕士学位论文第1 章绪论 范围，返回给用户更有效的信息，提高搜索的准确性。 1 2 国内外研究现状 数据中的不确定性主要是指不定性、不固定性、不可靠性、不可预知性、随机性、 意义含糊性、易变性、不完全性、未知然而有界性、不规则性等。不确定性可能由随机 因素的干扰和测量误差引起的，或者是对难以精确测量或者是不能测量参数作近似估计 引起的，也可能由牛产过程工作时间、条件、环境等变化引起的。 目前，对不确定性数据的研究己经引起了世界范围内的普遍关注。许多著名的大学 包括斯坦福大学、华盛顿大学和i b m 、微软等著名企业先后投入到该项研究之中，并针 对研究数据的类型和应用领域设计不同的系统。 b u r d i “1 2 ，3 1 等提出基于o l 廿( 联机分析处理) 处理不确定数据的方法，如图1 1 所示，利用o “心多维数据模型，将以前用维、度量表示的确定的数据推广到用多维区 域来表示不确定数据。在标准的o l a p 模型中，属性分为两类：维( d i m e n s i o n ) 和度量 ( m e a s u r e ) 。通过扩展模型用“度量”的值来展现不确定度，用“维 来展现精确程度。 另外，该模型通过区域的限制条件和选择合理的分配策略有效完成用户的查询请求。 ( ： 垒坐! 竺! 曼! ! 曼一二) a i i s e d 、h i c k c 巧f m ，7 一、 q 6 f 、! 乡 q7 fp 3 、 二二 q 8 图1 1o l 廿中的不确定数据 f i g 1 1u n c e n a i l ld a t ai no l a ps y s t e m 运用o l a p 处理不确定数据有三种分配策略：统一分配、基于计数分配、e m 分配 策略。 一2 一 画 面 东北大学硕士学位论文第1 章绪论 b u r d i c k 等又结合实际工程中需要，在用o l a p 模型处理不确定数据的基础上，考 察领域内的限制条件，以及元组的独立性问题。并在查询处理中，除去元组之间独立的 假设条件，将元组之间的非独立关系有效连接，并在返回查询结果时节省了不必要的开 销。 w i d o m 【4 ，5 ，6 7 ，8 1 等提出了嘣。系统，该系统中处理不确定数据是元组级别的，每个元 组由数据属性值( d a t a ) 、数据精确度( a c c u r a c y ) 和数据来源( 1 i n e a g e ) 三者共同表示。 同时创建啊q l 语句来支持用户查询请求。其中每一个属性值由多个可选择值 ( a l t e n l a t i v e ) 组成，每一个可选择值的精确度用概率值( c o n f ) 来表示。每一个表中含 有关于各个数据来源( 1 i n e a g e ) 的函数九( t ) ，该函数表示的是可选择值( a l t 锄a t i v e ) 的 所有可能的来源值的集合。 强o 0 n e 体系结构如图1 2 所示。该体系结构分为三层：用户管理层、h o 接口层、 底层的数据库管理系统层。用户管理层提供给用户可视化的图形界面以供用户输入查询 请求；啊。接口层将用户的查询请求进行重写和编译，转化为底层数据库能识别的标准 s q l 语句；底层的数据库管理系统层包含数据表、来源数据表( l i n e a g et a b l e ) 、o 元数据、嘣。存储进程等，共同处理通过上层重写编译的查询请求。当返回结果时，通 过上述三层结构再返回到嘶。浏览器中。 图1 2 n 胁o n e 体系结构 f i g 1 2a c h i t c c t i l 】孵o f t r i o - o n e 与传统的数据库管理系统相比，嘶o o n e 系统扩充了s q l 语言，并设计出嘶q l 语句。同时定义啊q l 语义、句法、查询形式等并能够高效地执行查询请求。强o o n e 系统查询结构如图1 3 所示。 一3 一 东北大学硕士学位论文第1 章绪论 啊q l 语句的创建语句形式是： c r e a tt r i ot a b l e t a b l en 锄e 】 啊q l 语句的基本查询形式是： s e l e c ta c t r - l i s t i n t on e w t a b l e 】 f r o mx 1 x 2 w h e r e p r e d i c a t e o o n e 系统的应用领域非常广泛。例如：科学数据管理，传感器数据管理，数据 复制，私有信息保护，近似查询处理，假设推理，在线查询处理等。 c 托a t et r i ot a b l et ( a ，b ) s e l e c t ci n t o 结果指针 浏览表 用户命令字串 查询来源 图1 3 t r i o o 舱查询系统 f i g 1 3 晡。一o n eq u e r ys y s t 锄 x i nd o n d 卅等首次明确定义了数据集成系统中存在的三个层次的不确定性问题，即： 数据级、映射级、查询级。并主要研究对异构数据源的数据进行集成时，中介模式与数 据源之间模式匹配的不确定性问题。异构数据源对同一事务的描述存在映射关系，而映 射的不确定影响着数据的不确定性。对映射关系分为表映射和元组映射两类，并从时间 复杂度上对两类情况进行了衡量。同时，创建了基于映射关系处理不确定数据的体系， 如图1 4 所示，该系统支持关键字查询，将关键字，解析成与源模式对应的结构化查询 子句，并能返回给用户t o p k 个查询结果。 针对媒介模式和源模式之间的映射关系，分为b y t a b l e 和b y - t l j p l e 两类。b y - t a b l e 是 指媒介模式和源模式之间的映射是基于t a b l e 级别的，t a b l e 之间按照同一的映射关系去映 射。b y 呻l e 是指媒介模式和源模式之间的映射是基于郇l e 级别的，t a b l e 之间按照不同 的映射关系去映射。如果运用b y - t a b l e 映射，时间复杂度是多项式级别，如果是b y 一呻l e 映射，时间复杂度是指数级别。 一4 一 东北大学硕士学位论文第1 章绪论 d 3 图1 4p - m a p p i n g 处理不确定数据结构 f i g 1 4a r c h i t e c t i l r eo fp m a p p i i l gp r d c e s s i n gu n c e r t a i nd a t a c h e n g 【1 0 ，1 1 ，1 2 】等研发的u d b m s 是处理连续变化的数据的数据库系统，该系统是基 于p o s t 黟e s q l8 0 实现的，主要应用于传感器领域。其功能特点：支持对指定的不确定 区间和该区间的概率密度函数进行查询；并扩展了s q l 查询语句。并针对查询是否基 于聚合进行了分类：基于数值的非聚合的查询类；基于实体的非聚合的查询类；基于实 体的聚合的查询类；基于数值的聚合的查询类。系统结构如图1 5 所示。 不确定数据类 图1 5u d b m s 系统框架 f 嘻1 5u - d b m ss y s t 锄触m e w o r k 其他的一些工作中虽然也提到了数据集成中不确定性问题，但大多数的作者还是仅 一5 一 东北大学硕士学位论文第1 章绪论 从数据集成过程中的具体任务考虑。g a l 【1 3 】提到了基于概率的语义映射，文中用半自动 方法得到了前k 个语义映射，并利用这前k 个映射的结果提高最终语义映射的准确率。 这一方法虽然考虑语义映射中的不确定性，但最终还是去除了语义映射的不确定性，选 择了一个最优的语义映射，并没有在整个数据集成系统中管理语义映射的不确定性，并 在此基础上产生查询应答。 上述相关工作可以看出，人们对不确定数据的认识不断加深，但是仍然有很多未知 的可拓展的研究领域。 1 3 本文要讨论的问题 本文以东北大学申请的国家自然科学基金“支持深层w 曲数据库网格的部分关键 技术研究”为背景，以不确定数据为基础，针对d e 印w 曲海量数据，结构类型多，接 口复杂等特点，结合用户在实际搜索中的需求，提出一个处理不确定数据的模型结构。 该模型结构在定义领域内基于d e 印w 曲挖掘不确定数据频繁集，借助返回的关联 规则填写数据库中缺失的数据，为用户从未知到已知提供较可靠的信息。 具体描述是用户对某数据库发出查询请求，经数据库内处理后不能给用户满意的答 案，结合到d e 印w e b 拥有海量的信息，将查询关键字和其他数据库中数据之间的匹配， 利用相似度算法来得到相关的不确定数据，再在一定的范围内进行数据挖掘，将关联规 则返回给用户，为用户提供较可信的结果。需要讨论和解决的问题包括：定义领域内不 确定数据类型以及来源的方式，选择有效的、准确的相似度算法，选择和改进不确定数 据的数据挖掘方法，以及评价返回查询结构的正确率等。 1 4 本文的组织结构 本文的章节组织如下： 第一章，介绍国内外当前对不确定数据研究的相关工作，以及本课题的研究背景和 研究内容。 第二章，介绍相关知识。 第三章，提出d e 印w 曲下不确定数据处理模型结构。 第四章，d e 印w 曲下处理不确定数据描述以及相似度算法的介绍。 第五章，回顾数据挖掘的经典算法a p r i o r i 算法和f p g r o 、砒算法，并改进成为能够 处理不确定数据的u d a 研o r i 算法和u d f p g r o w c l l 算法。 第六章，对比试验，分析数据，得出结论。 第七章，总结全文。 一6 一 东北大学硕士学位论文第2 章相关知识介绍 第2 章相关知识介绍 d e 印w 曲下处理不确定数据这一方向在近年来引起了学术界的极大关注，这是快 速增长的数据量和用户需求不断扩大的必然结果。在数据量增加的同时，信息量却日益 匮乏，数据挖掘有效解决这一矛盾。在对基于d e 印w 曲的不确定数据挖掘算法深入研 究之前，有必要对d e e pw 曲的概念和发展、d e 印w 曲中不确定性的产生、不确定数据 的相似度度量的计算方法、数据挖掘的由来和挖掘算法等常用技术问题进行较为全面的 了解，以期更加透彻地领悟不确定数据这一极具发展潜力的新兴领域，为本文的全面展 开做好铺垫。 2 1d e e pw 曲介绍 随着w o r l dw i d ew 曲的飞速发展，出现了越来越多的可以在线访问的数据库，我 们把这些数据库称作w 曲数据库。目前，人们已经习惯于通过搜索引擎从网上查找信 息。如果记录数为零，用户通常会使用更多的关键词，或者使用同义词、近义词来深化 检索。若仍没有结果，用户可能就会认为所需信息在网上并不存在，继而放弃查询。但 事实可能并非如此。人们所需的信息在网上可能是大量存在的，只是传统的搜索引擎无 法或者没有索引这些信息而已。记录这些信息的网页就是通常所指的看不见的网络，称 为d e 印w 曲。 具体来讲，如图2 1 所示，d e 印w 曲是指w 曲中可访问的在线数据库，这里简称 为w 曲数据库或w d b ，其内容存储在真正的数据库中。这些内容只有在被查询时才会 由w 曲服务器动态生成页面把结果返回给访问者，因此没有超链接指向这些页面，这 是和那些可以被直接访问的静态页面的根本区别。按照存储信息的结构化程度可以进一 步划分为结构化信息、文档信息和非文本文件，网上购物网站存储的信息属于结构化信 息，新闻网站存储的信息属于文档信息，二者因结构化程度的不同对其查询所应用的技 术也差别很大，而非文本文件，主要包括多媒体文件、图像文件、软件和特定格式的文 档( 比如p d f 文件) 。在一般的意义下，对d e e pw 曲信息的获取更关注的是对结构化 信息的获取，而不是文档或非文本文件。其原因不难理解，对结构化数据的集成更有意 义，可以采用的技术也更丰富。d e 印w 曲数据集成也主要是指对结构化信息的集成。 随着w 曲相关技术的日益成熟和d e 印w 曲所蕴含信息量的快速增长，通过对w e b 数据 库的访问逐渐成为获取信息的丰要手段，而对d e 印w 曲的研究也越来越受到人们的关 注。 但由于对w 曲数据库的访问只能通过其提供的查询接口，因此很难被一般的搜索 一7 一 东北大学硕士学位论文第2 章相关知识介绍 引擎获取到。由于d e e pw 曲的大规模性、动态性以及异质性等特点，通过手工方式远 远不能在效果和效率上满足用户对信息获取的需要。为了帮助人们快速、准确地利用 d e 印w e b 中的海量信息，研究者们已经在d e e pw 曲数据集成方面展开了研究。这逐渐 成为数据库领域的一个研究热点。研究者力图提出一种通用的集成方法，可以实现对现 实世界各个领域的d e 印w 曲数据的集成，并在查询接口集成和数据抽取等方面取得实 质性的进展。 在d e 印w 曲数据集成过程中，整个w e b 都充满着不确定性。比如在查询关键字和 数据源结构化查询结构匹配的过程中，可能有多种匹配方案；在数据源中可能含有不确 定数据同时返回的结果也含有不确定数据。可见，找到合理的获得不确定数据概率值的 方法十分重要，相似度计算可以解决这一问题。 图2 1d e e pw 曲搜索引擎和传统搜索引擎区别 f i g 2 11 1 1 ed i 艉r e n c eb e 觚c e i ld e 印w 曲s e a r c he n 西n ea n d 仃a d i t i o n a lw 曲s e a r c he n g i 鹏 2 2 相似度度量方法 不确定数据区别于传统的确定数据在于每个数据都伴随一个扩展的概率值。早在几 十年前的论文中就对此有所提及，例如上世纪八十年代末开始出现的概率数据库研究 【1 4 】，这一研究认为元组在数据库中的存在具有不确定性、属性值具有不确定性、查询应 答也具有不确定性。 相似度是指文本间、数据间或查询语句与文本间的匹配程度。在数据集成中，广泛 存在映射的关系，相似度计算也成为要点问题之一，同时又与不确定数据联系紧密。相 似度计算方法分为基于字符匹配的相似度度量方法和基于语义的相似度度量方法。本文 一8 一 东北大学硕士学位论文笫2 章相关知识介绍 约定，相似度的取值在 0 ，1 之间。当比较的两个概念完全相同的时候，其相似度为1 ； 反之，当比较的两个概念之间没有任何相似或联系的时候，其相似度为o ；在其他情况 下，即比较的两个概念之间有一定的相似和关联的情况下，其相似度在o 到1 之间。将 相似度度量方法进行分类：分别是基于字符匹配的相似度度量方法和基于语义的相似度 度量方法。 2 2 1 基于字符匹配的相似度度量方法 在d e 印w 曲的数据映射、模式匹配中，由于数据的拼写错误、缩写错误、关键词 顺序等情况产牛不确定数据。如：“s m i t h ”与“s m o t h ”、“4 4w 4 t hs t ”与“4 4w e s tf o u n h s 仃e e t ”、 “c o m p u t e rs c i e l l c ed 印a m n e n t ”与“d 印a n m e n to fc o m p u t e rs c i e n c e 等。另 外从非结构化、办结构化页面抽取数据时同样也存在相似度计算。 基于字符匹配的相似度度量分为字符串相似度计算和数字相似度计算。方法如图 2 2 所示。 图2 2 基于字符匹配的相似度计算方法 f i g 2 2s i i i l i l 撕t ) rm e t h o d sb a s e d0 nc h a r a c t e r sm a t c h 崦 ( 1 ) 字符串相似度度量方法 基于字母的e d i td i s t a l l c e 、a 伍n eg a pd i s t a i l c e 、s m i t l l w 缸e n t l 锄d i s t a l l c e 、j a r od i s t a i l c e 和q 一鲫nd i s t a n c e 以及基于t o k e n 的w h i r l 和q g r a m sw i mt i d f 度量方法【1 5 】。 e d i td i s t a l l c e 度量方法是用来处理字符串拼写错误的。编辑距离表示为达到两个 字符串的完全匹配，进行编辑操作，则字符串之间需转换的字母的最小值称为编辑距离。 一9 一 东北大学硕士学位论文 第2 章相关知识介绍 其中的编辑操作包括插入字母、删除字母和用不同的字母替换。 s m i m w 乱e m a i ld i s t a n c e 扩展了编辑距离，该方法在含有复杂前缀和后缀的字符 串匹配时表现良好的判断性能。 j a r 0d i s t a n c e 距离公式用来判断例如姓名属性这样的字符串，主要用于比较英文 形式书写名字中缩写的“姓”和“名 。 q 黟锄d i s t a i l c e 方法通过在字符串上作用一个预先设定的长度固定的滑动窗口， 对字符串分割，通过q 莎锄公式来判断字符串之间的差异程度。 w h i r l 方法把字符串分割成若干单元，为每个单元设置权重，再利用夹角余弦 公式计算相似程度。 q - 伊锄sw i i ht i d f 方法是将q 莎锄s 与w h i r l 两种度量方法结合，即将q 铲锄s 模式嵌套w h i r l 方法中，不再将记录分割成若- 下词，而是q 黟锄s 中滑动窗口的方法 应用于w h i r l 中。 ( 2 ) 数字相似度计算方法 对于数字相似度的判断目前还是运用字符串的方法，例如利用q 一黟锄s 方法判断数 字集合，数字区间之间的相似度。 2 2 2 基于语义的相似度度量方法 在d e 印w 曲数据集成中，异构数据库对同一实体的描述往往是不同的，这种差异 并不是匹配上的差异，而是体现在语义上。例如：“p r e s i d e n to f t h eu s ”与“g e o r g e 、m b u s h ”描述同一人；“d 印a i t u r e 与“l e a v i n g 舶m ”同样表示“离开。但如果用基于 词汇的相似度度量方法处理，结果一定是两者之间相似度值很小，所以基于语义的相似 度度量方法很有必要。 基于语义的相似度计算的研究策略是根据某种世界知识( 如o n t o l o g y ) 来计算1 6 1 。 主要基于按照概念间结构层次关系组织语义词典的方法，根据在这类语言学资源中概念 之间的上下位关系和同位关系来计算词语的相似度。例如选择利用语义词典如w | o r d n e t 、 h o w n e t 中的同义词或近义组成的树状层次体系结构，通过计算两个概念之间的信息熵 或语义距离，计算概念间语义相似度。 相似度计算主要应用于关键字查询、模式匹配、结果融合模块，即应用于将关键字 查询接口和结构化的查询接口之间的相似度度量：从集成查询接口到本地查询接口的相 似度度量；去除领域内重复记录等方面。 根据实际应用情况选择合适的有效的相似度算法，得出不确定数据的概率，为下一 步的数据挖掘提供数据源。 一1 0 一 东北大学硕士学位论文第2 章相关知识介绍 2 3 数据挖掘简介 为了让d e 印w 曲资源向用户开放，本文提出了将关联规则挖掘方法应用于w e b 数 据库的查询，即将对不确定数据挖掘产生的关联规则来服务于用户的查询。虽然d e 印 w 曲含有众多的数据资源，但是“数据丰富，信息贫乏”，特别是对不确定数据来说更 是如此。所以为了有效地利用数据，从数据中发掘对用户有价值的信息，达到为决策服 务的目的，应用数据挖掘这一技术。 2 3 1 对不确定数据挖掘的必要性 数据挖掘的主要任务就是从巨大的数据库中找出用户感兴趣的知识而且这些知识 是隐含的、事先未知的潜在的有用信息。数据挖掘的提出使人们认识到数据的真正价值， 即蕴含在数据中的知识和信息。帮助实现将“数据坟墓中的数据转化为知识财富。 现实世界中存在大量的由各种原因引起的不确定数据，比如在d e 印w 曲环境进行 数据集成时产生大量的不确定数据。数据挖掘方法只有充分考虑数据的不确定性，才能 对数据去伪存真，才能得到基于不确定数据的准确反映客观事物知识的挖掘模型。因此 对不确定数据的挖掘很有必要。 2 3 2 关联规则相关的算法 关联规则是数据挖掘的重要功能之一。关联规则( a s s o c i a t i o ni 沁1 e ) 的概念最早是 由a 蓼a w a l 首先提出的【1 7 1 。关联规则就是从大量的数据中挖掘出有价值的描述数据项之 间相互联系的有关知识。关联规则的一个典型例子是购物篮分析，例如“在购买面包和 黄油的顾客中有9 0 的顾客也购买了牛奶 ，这样的规则指导超市的