（计算机软件与理论专业论文）基于web数据的距离函数研究.pdf

龋十w e b 数捌的距高函数研究 摘型 【摘要】 w e b 挖掘( w e bm i n i n g ) 是在i n t e r n e t 快速发展，网上信息急剧增加的背景下 发展起来的，它能够自动地从w e b 文档和服务中发现和抽取信息。如何有效地 量化对象或行为间相似性差别是w e b 挖掘中经常会遇到的问题。距离函数是量 化对象州差别常用的方法，它具有广泛的用途。 本文基于w e b 数据的特点，针对已有的距离函数不能体现语义、不满足度 量定义和不适于处理网页距离的缺陷，对集合距离函数和网页距离函数进行了研 究。主要工作成果为； 1 )提出了一种使用w e b 结构数据所蕴涵的语义信息来量化对象间差别的方 法。基于集合结构的对象特征模型，定义了一个量化语义相似性的核心概念 “最大相似宽度”，并从此概念出发，定义了三个语义距离函数；je m d 、 me m d 和xd i s t 。与已有的研究相比，特征项之间的语义关系表示结构从 有向根树扩展到了有向无环图。在关系表示结构是有向根树的条件下，这些 距离函数均满足度量定义，在提高搜索效率方面具有优势，弥补了以往研究 存在的缺陷。实验初步表明此类距离函数的在最近邻查询、差别分辨力和汁 算速度方面可与已有类似研究相媲美。 2 ) 根据网页的h t m l 编码和浏览器显示的特点，用“设计树”来表示网页， 抽取了内容、风格和布局等网页对象特征，提出了量化网页间相似度的内容 距离、风格距离和混合距离，使距离函数的结果更符合用户的直观映象。实 验初步证明本文提出的网页距离函数是简单有效的。 3 ) 利用定义的网页距离函数实现了一个实际的智能网页编辑工具 w e b c o m p o s e r 。该工具能利用基于案例的推理( c a s e b a s e dr e a s o n i n g ，c b r ) 技术 自动优化用户网页的编辑。网页距离函数在此将被用于网页案例的比较。 w e b c o m p o s e r 工具的开发和实际应用表明了网页距离函数的可行性。 关键词：距离函数、相似性、w e b 挖掘、数据挖掘、度量、网页距离、基于 案例的推理 中图法分类号：t p 3 1 1 苎! ! ! 塑型生些堕里墼垡塑 皇! ! 竖型 a b s t r a c t d i s t a n c ef u n c t i o ni sag e n e r a lm e t h o d o l o g yu s e dt oq u a n t f yt h ed i f f e r e n c eb e t w e e no b j e c t s h o wt om e a s u r et h es i m i l a r i t ya n dd i f f e r e n c e se f f e c t i v e l yb e t w e e no b j e c t so ra c t i v i t i e sw i t h c e r t a i nq u a n t i t yi sac o m m o np r o b l e m ，w h e nw e bm i n i n gi sp e r f o r m e d b a s e do nc h a r a c t e r i s t i c so f t h ew e bd a t a ，t h i sp a p e rm a k ec o t t e s p o n d i n gr e s e a r c ho ns e td i s t a n c ef u n c t i o na n dw e bp a g e s d i s t a n c ef u n c t i o n ，w i t hc o n s i d e r a t i o no nt h el i m i t a t i o no f e x i s t i n gd i s t a n c ef u n c t i o n s ，w h i c hc a n n o t b es a t i s f a c t o r i l yu t i l i z e do ns e m a n t i ci n f o r m a t i o n ，m e a s u r e m e n td e f i n i t i o n ，a n dw e bp a g e sd i s t a n c e d e a l i n gw i t h t h em a j o ra c h i e v e m e n to f t h i sp a p e ri s ： am e t h o d o l o g y , w h i c hi su s e dt om e a s u r et h ed i f f e r e n c e sb e t w e e no b j e c t sb ym e a n so f s e m a n t i ci n f o r m a t i o nc o n t a i n e di nt h ew e bs t r u c t u r e sd a t a , i sp r o p o s e d t h ed e f i n i t i o no f m a x i m u ms i m i l a r i t yw i d t h ，w h i c hi st h ec o r ec o n c e p to f t h em e a s u r e m e n to fs e m a n t i cs i m i l a r i t y , w a sw o r k e do u t ，w h i l s tm a n ys e m a n t i cd i s t a n c ef u n c t i o n sw e r ed e f i n e d w i t hc o n d i t i o n st h a tt h e r e l a t i o n s h i pr e p r e s e n t a t i o ns t r u c t u r ei sd i r e c t e dr o o tt r e e ，t h e s ed i s t a n c ef u n c t i o n sa r es a t i s f i e dw i t h m e a s u r e m e n td e f i n i t i o n 。a n dt a k ea d v a n t a g e so ni n c r e a s i n gt h es e a r c h i n gp e r f o r m a n c e ，w h i c h m a k eu pt h el i m i t a t i o no fa n c i e n tr e s e a r c h e x p e r i m e n t sp r o v e dt h es i m i l a r i t yo nt h ea s p e c t s ： n e a r e s tn e i g h b o rs e a r c h i n g , a b i l i t yo fd i f f e r e n c e sd i s t i n g u i s h i n g ，a n dc o m p u t i n gs p e e d ，b e t w e e n t h ep r o p o s e dm e t h o d sw i t hr e l a t i v er e s e a r c h a c c o r d i n gt ot h eh t m le n c o d i n ga n dt h ec h a r a c t e r i s t i c so fd i s p l a y i n gw i t hb r o w s e r so fw e b p a g e s ，c o n t e n td i s t a n c e ，s t y l ed i s t a n c e ，a n dt o t a ld i s t a n c et h a tu s e dt om e a s u r eo fs i m i l a r i t yo f w e bp a g e sw e r ep u tf o r w a r d ，i nw h i c hd e s i g nt r e ew a si n t r o d u c e dt od e n o t ew e bp a g e s ，a n dt h e c h a r a c t e r i s t i co b j e c t s ，s u c ha sc o n t e m , s t y l e ，a n dl a y o u t ，a r ee x t r a c t e di na d v a n c e t h ep r o p o s e d d i s t a n c e sm a k et h er e s u l t so fd i s t a n c ef u n c t i o n si nl i n ew i t hu s e r s i n t u i t i o n e x p e r i m e n t sg i v e p r o v eo nt h ec l e a r n e s sa n de f f e c t i v e n e s so f p r o p o s e dw e bp a g e sd i s t a n c ef u n c t i o n s as e to fp r a c t i c a li n t e l l i g e n tw e bp a g e se d i t i n gt o o lw a si m p l e m e n t e d ，n a m e dw e b c o m p o s e r , w h i c hi sb u i l to nt h eb a s i so f p r e d e f i n e dw e bp a g e sd i s t a n c ef u n c t i o n s i tb u i l tw i t ht h ec a s e b a s e d r e a s o n i n gt e c h n i q u e s t h ed e v e l o p m e n ta n dp r a c t i c a la p p l i c a t i o np r o c e d u r eo fw e b c o m p o s e rt o o l i n d i c a t et h ef e a s i b i l i t yo f t h ew e bp a g e sd i s t a n c ef u n c t i o n s k e yw o r d s ：d i s t a n c ef u n c t i o n ，m e a s u r e m e n t ，s i m i l a r i t y , w e bm i n i n g ，d a t am i n i n g ，w e b p a g ed i s t a n c e ，c a s e - b a s e dr e a s o n i n g 娃卜w e b 数据的距离函数研究 第j 章绪论 1 1 研究背景 1 1 1w e b 挖掘 第1 章绪论 在舅：联网技术的强力推动下， t x t e m e t 得到了极大的发展，w e b 已经成为全 球最大、最方便、最具价值的信息源。w e b 上包含的数据是海量的、异构的、动 态的，当中蕴含着具有巨大潜在价值的知识。人们迫切需要能够从w e b 上快速、 有效地发现资源和知识的工具，提高在w e b 上检索信息、利用信息的效率f l 0 9 ”。 自动从w e b 文档和服务中发现和抽取信息的w e b 挖掘( w e bm i n i n g ) 技术旧“妁j 己 经成为目日u 信息获取和数据挖掘研究的热点。国际上目前关注w e b 挖掘的知名 会议有i n t e m a t i o n a l c o n f e r e n e e o n w w w 、a c m k d d 、s i g l r 和w e b d b 等。 w e b 挖掘从数据挖掘( d a t am i n i n g ) 发展而来。数据挖掘也常被称为数据库中 的知识发现( k d d ：k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) ，是从大量的数据中提取隐 含的、事先未知的、并且潜在有用的知识的过程。它是多个研究领域的交汇点， 其中包括数据库技术，统计分析，机器学习和可视化技术等。数据挖掘的提出最 初是针对火型数据库的，但是从广义上讲，数据挖掘的对象不仅可以是数据库， 还可以是任何组织在一起的数据集合，文本、声音、图形、图像或w w w 信息 资源等半结构、无结构的数据形式都可成为数据挖掘处理的对象。 w e b 挖掘分可分成四个步骤：( 1 ) 数据收集，w e b 上的数据很丰富，收集地 点有多处，包括客户端、h t t p 代理端、w e b 服务器端、甚至底层网络通路。( 2 ) 数据预处理，即把原始数据转换成挖掘方法可用的数据，必要的时候还要把它存 储到特定的数据库中。( 3 ) 模式发现，即通过挖掘算法发现数据中隐含的有价值 的模式；( 4 ) 模式分析，对挖掘出的模式进行过滤或者解释，常用的方法包括兴 趣度和模式可视化。 1 1 2w e b 数据 对于w e b 挖掘的研究，需要处理w e b 上异质、海量、非结构化的信息。w e b 文档和服务包含的数据，常总称为“w e b 数据”。按 c o o l 0 0 的分类方法，w e b 数据主要分为三类： 娃十w e b 数姑的距离函数研究 第1 章绪论 内容数据( c o n t e n td a t a ) ：它是提供信息的主体，包括文本，声音，图 像，视频和元数据。内容数据主要以各种文档形式存在，譬如h t m l 文件 和其他各种非文本的媒体文件。内容数据的其他通俗的概念还有“w e b 文 档”或者“w e b 页面”( w e bp a g e ) 。 结构数据( s t r u c t u r ed a t a ) ：它是对内容数据进行组织而派生的数据。内 容数据大部分用h t m l 描述，超链接被广泛用于组织w e b 文档和w e b 文 档内部的数据实体。由此w e b 上就存在着由各种超链接形成的结构( 也包 含超链接的描述) 、文档内部的结构和文档u r l 中的目录路径结构等。此 w e b 结构又分为站点结构和站间结构两部分。 - 使用数据( u s a g ed a t a ) ：它是用户使用w e b 而衍生的数据。w e b 是一 个分层实现的交互式媒介，可在多个层面上记录和收集因用户访问而产生 的数据。典型的方法是在w e b 服务器端收集w e b 日志，它包含了大量通过 h t t p 协议传输的数据。 w e b 上信息的多样性决定了w e b 挖掘的多样性。根据使用的w e b 数据类型， w e b 挖掘分为三类【“8 0 0 】【。m o 】：w e b 内容挖掘( w e bc o n t e n tm i n g ) ，w e b 结构挖 掘( w e bs t r u c t u r em i n g ) 和w e b 使用挖掘( w e bu s a g em i n i n g ) 。 w e b 使用挖掘领域挖掘的对象主要是用户和会话，这些对象有多种不同的特 征模型，通常“项”是组成特征模型的主体，这些项可以是w e b 页面，产品或 者其他更抽象的概念。特征模型的差异主要体现在项问结构上，主要分为： a 集合：它是最简单的结构，用项在集合中的存在与否表示特征的有无。 b 向量：在此结构中每个项看成向量空间中的维，项的权重是对应维值。 它的一个缺点是不考虑项之间存在的时序关系。项的权重一般可以是时间或者频 率，也可只是0 或l ，代表特征有或没有。如果允许集合模型中的项带有权重， 则集合模型是向量模型的一种紧凑描述。 c 序列：此种模型考虑了项间存在的时序关系，把用户或会话的特征表示为 一条项的序列，其中每个项也可附带权重。 1 1 3 距离函数 如何有效地量化使用对象或行为问相似性差别是w 曲挖掘中经常会遇到的 问题。例如数据挖掘中的聚类f 6 “o + 9 2 】 k m m + 9 7 1 【3 m 9 扪、信息检索中的相似文档网页 查询 r b 9 9 】、协同过滤中相似用户的商品或网页推荐、c b r ( c a s e b a s e dr e a s o n i n g ) 中的相似案例查询等。 距离函数是用来量化对象间差别的方法。设使用n 个特征变量来描述对象， 那么我们就可以把每个特征看作n 维空问中的一个点，进而使用某种距离来表示 牡十w e b 数据的距离函数研究第t 章绪论 对象之n 帕q 相似性。距离值越大，则两个对象差别越大；距离值愈接近0 ，则对 象差别越小。距离函数最早应用于空间几何，最常用的距离函数就是度量空间两 点忙j 直线距离的欧几旱得距离函数。 量化对象之间的相似度差别除了可以使用距离函数之外，还常用相似性函 数。两个对象愈相似，则相似度值愈接近1 ；对象愈不相似，则相似度值愈接近 0 。这样就可以使用相似度值来刻画对象之问的相似性。 相似性函数和距离函数之间可相互转换。设f 是一个距离函数，值域在【o ，l 】 之间，0 表示两个对象相等，而1 表示两个对象完全不同，其他数值则表示介于 中间。它对应的相似性函数可以是：1 f ( ) 或者1 ( 1 + f ( ) ) 。 距离函数或相似度量被广泛应用与数据挖掘、信息检索、图像检索和模式识 别等领域，很多文献中都对此有过研究，究竞选用何种方法在不同场合有不同的 标准，但是应能充分表示出对象各个属性之间的差别。 1 2 研究意义 集合是对象特征表示的常用结构，集合的元素是与对象特征相关的项( 以p 简称项) ，它们可以是用户购买的商品，文档中的词，或是访问的w e b 页面。传 统的相似性差别量化方法( 例如基于集合交集的j a c e a r d 系数 r j 7 9 1 ) 均假设项只 有相等或不相等的精确关系，但是现实世界中，人们的判断存在模糊性。譬如“节 果”和“鸭梨”之间的关系就比“苹果”和“萨达姆”密切，而“萨达姆”应该 和“美国总统”关系更近一些。此类模糊性来源于人们拥有的各种领域知识。 w e b 环境中存在着丰富的数据，不乏蕴涵类似领域知识的结构数据。例如常 见的站点结构就包含了设计者对页面内容的分类知识，w e b 搜索引擎会对各种页 面按照某种分类法进行分类，电子商务站点会把总产品列表整理成在线分类目 录，w o r d n e t f e ”l 的电子词典，某个领域的本体知识或者w e b 站点结构。采用适 当的方法，能够从各种w e b 结构数据中抽取出体现项间语义关系的结构。利用 这些与项相关的语义信息可以更好地量化对象间的相似性差别。 此外在特征项很多地情况下，基于传统方法计算的相似性差别经常会变得 不明显，使得最近邻查询失去意义【b 0 2 。使用语义信息量化对象间的相似性差 别是缓解此类问题的一种有效方法。 量化对象间的相似性差别最终由距离函数或相似性函数来实现。在很多应 用中需要距离函数是一个度量( m e t r i c ) ( 度量的定义参见2 1 1 节) 。一般比较容 易找到一个距离函数满足度量定义中的前两个特性，但是找到函数满足三角不等 式特性却需要花一番周折。一个函数满足三角不等式的好处是能够提高搜索的效 皋十w e b 数据的距离函数研究 第1 章绪论 率【c ”mo 。j 。例如有对象x ，y ，z ，和满足三三角不等式的距离函数f 如果已经知 道f i x ，z ) 一f ( y ，z ) 大于某个数值k ，则有f ( x ，y ) f ( x ，z ) 一f ( w ，z ) k ，因此在不计算 x ，y 之阳j 距离值的情况下可直接推断f ( x ，y ) 的距离超过等于k 。因为f ( y z ) 可以 事先算好，所以搜索算法可依赖中间节点z 节省计算时间。 w e b ：的内容数据通常是由超文本标记语言h t m l 表示，通过浏览器来显 示的文档n “。网页在浏览器中将会咀一定的格式、布局和颜色显示出来。现有 的网页问相似度量的方法大都直接比较h t m l 编码的区别【g c ”0 0 2 l l y z o i 】【7 m o 丁0 3 】。 由了二h t m l 语言的灵活性，显示在浏览器中非常相似的网页他们的h t m l 文档 却并不一定相同，以不同顺序组合的h t m l 标记( t a g ) 可能会得到完全相同的显 示结果i y z o l l 。因此，直接用h t m l 文档来表示网页对象，并进行相似性比较是 不能合理反应人们的直观认识。 针对这些问题，本文研究如何把w e b 结构数据所蕴涵的领域知识自然嵌入 到对象差别的计算过程中，从而量化对象在语义上的差别。与已有的研究相比， 在语义结构是有向树的条件下，本文定义的集合距离函数均满足度量的三个特 性，在提高搜索的效率方面具有优势。同时，还研究如何根据网页在浏览器中显 示的特点，来更好的表示网页，并定义更合理的网页距离函数。本文提出了度量 网页差别的内容距离、风格距离和混合距离，使距离度量的结果更符合用户的直 观映象，并且利用定义的距离函数实现了一个实际的智能网页编辑t 具 w e b c o m p o s e r 。 1 3 本文工作 本文基于w e b 数据的特点，针对已有的距离函数不能体现语义、不满足度 量定义和不适于处理网页距离的缺陷，对集合距离函数和网页距离函数进行了研 究。研究内容和成果主要包括以下几个方面： 提出了一种基于w e b 结构数据所蕴涵的领域知识量化对象间差别的方法。 此方法针对基于集合结构的对象特征模型，定义了一个量化语义相似性的基础概 念“最大相似宽度”。定义了三个语义距离函数：je m d 、me m d 和xd i s t 。 与已有类似研究相比，特征项之间的语义关系表示结构从有向树扩展到了有向无 环图。在语义关系表示结构是有向树的条件下，这些距离函数均能满足三角不等 式特性，在提高搜索效率方面具有优势，弥补了以往研究存在的缺陷。实验初步 表明此类距离函数的在最近邻查询、差别分辨力和计算速度方面可与已有类似研 究相媲美。 根据网页的h t m l 编码和浏览器显示的特点，用内容、风格和布局这些特 4 螭卜w e b 数据的距离函数州究 第1 章绪论 征来表示网页，提出了度量网页差别的内容距离、风格距离和混合距离，使距离 函数的结果更符合用户的直观映象，便于找到同类十目似网页。实验初步证明本 节提出的刚页距离函数是简单有效的。 利用定义的网页距离函数实现了一个实际的智能网页编辑t 具 w e b c o m p o s e r 。它是一个基于案例推理技术( c a s e b a s e dr e a s o n i n g ，c b r ) 的自动网 页优化 i 具，网页距离在此将被用于网页案例的比较。w e b c o m p o s e r 工具的丌 发和实际应用表明了网页距离函数的可行性。 1 4 文章结构 本文共分为血章，每章的主要内容介绍如下。 第一章简要地介绍了基于w 曲数据的距离函数的发展背景；论述了本文的 立论意义：然后介绍了本文主要的研究内容及成果；最后，给出了本文的整体组 织结构。 第二章回顾了相关距离函数的发展。概要介绍了几种和本文研究相关的常规 距离和相似性函数；然后简单介绍了相关集合距离函数的研究，并详细介绍 p r a s a n n ag a n e s a n 等人f o o w 0 3 1 的相关工作；最后介绍了已往网页距离函数研究的 概况，和相关的直方图距离函数。 第二二章提出了一个基于集合特征模型的核心概念“最大相似宽度”，并在此 基础上描述了衍生的距离函数，最后还给出了距离函数在最近邻查询、差别分辨 力和计算速度方面的实验结果； 第四章介绍了同时考虑网页的h t m l 编码和显示外观的网页距离函数，并 概述了网页距离函数的应用实例：智能网页编辑工具w e b c o m p o s e r ，最后还给 出了实验证明。 第五章是讨论与小结部分，对本文的工作进行总结并指出了未来的研究方 向。 基卜w e b 数据的距离函数研究 第2 章距离函数的研究现状 第2 章距离函数的研究现状 本章先概要介绍了几种实际应用中最常用的常规距离和相似性函数。然后简 单介绍了集合距离函数相关研究，并详细介绍了p r a s a n n ag a n e s a n 等人l 。g w 0 3 1 的 研究，分析了他们提出的四个相似性函数的特性和存在的缺点。最后介绍了已律 网页距离函数研究的概况，和相关的直方图定义及常用的直方图间距离函数。 2 1 传统的距离和相似性函数 距离函数或相似性函数是量化对象差别或相似度的方法，它在计算机领域有 广泛的用途。下面将介绍最常用的距离函数和相似性函数。 2 1 1 距离函数 度量是距离函数的一个重要定义，它的定义如下： 定义2 1 ( 度量空间和度量) f s r s s l ：一个度量空间是一个集合s ，连同一个函数 d ：s s - - 啡负实数，使得任意的s b s 2 ，s 3 s ，满足： ( 1 ) 正定性：d ( s i ，s 2 ) o ，并且d ( s l ，s 2 ) = o ，当且仅当s i = s 2 1 ( 2 ) 对称性d ( s l ，s 2 ) 一d ( s 2 ，s 1 ) ； ( 3 ) 三角不等式d ( s l ，s 2 ) + d ( s 2 ，s 3 ) d ( s 1 ，s 3 ) ； 则函数d 称为s 上的一个度量。 从狭义上讲，距离函数必须满足度量的3 个条件正定性、对称性、三角 不定式才能被称为距离。但是有许多通常意义上的距离函数不能满足度量的 三角不等式条件，从广义的角度我们也称之为距离。 常用的距离函数有以下几种： 1 欧几垦得距离 在通常的二维和三维空间中，欧几里得距离是最常见的距离定义方式。所谓 的欧几里得距离就是通常所说的空间两点间的直线距离。假设有两个n 维对象x 和y ，它的欧几里得距离为： d ( x ，y ) - 7 ( x ，一z ) 2 ( 2 1 ) v ， 其中，x i 和y i 分别为x 和y 在i 维的值。 2 绝对值距离 6 坫卜w e b 数据的距离函数剐f 究 第2 章距离函数的研究现状 绝对值距离是另一个著名的距离公式，也称为曼哈坦( m a n h a t t a n f l k 离。其 定义如下： d ( x ， ，) = i 置一r i ( 2 2 ) 3 明考斯基( m i n k o w s k i ) e 离 明考斯基距离是绝对值距离和欧几里得距离的概化，它的定义如下： b ( ，y ) = ( i x , 一邛) “。 ( 2 3 ) 当q 取l ，2 ，无穷大时，则分别得到：( i ) 绝对值距离：( 2 ) 欧几晕得距离： ( 3 ) 切比雪夫( c h e b y s h e v ) 距离。 因为明氏距离直观，计算简便，是实际应用中采用最多的一类距离函数。值 得强调的是欧式距离的一个优点；当坐标轴进行正交旋转时，欧式距离保持不变。 因而如果对原坐标系进行平移和旋转处理后，样本集合仍然能够保持原来的相似 结构。而且明氏距离满足度量的3 个条件。 4 马氏f m a h a l a n o i s ) 距离 如果特征向量的各个分量间具有相关性或者具有不同的权重，可以采用马氏 距离来计算对象之间的相似度。马氏距离的定义如下： d ( x ，y ) = ( x y ) 。+ c “+ ( r y )( 2 4 ) 其中c 是特征向量的协方差矩阵，是总体分布的协差估计量。马氏距离是 明氏距离的改进，它对于一切线性变换是不变的。 当特征向量的各分量问没有相关性，马氏距离还可以进一步简化，因为这时 只需要计算每个分量的方差c 。简化后的马氏距离如下所示： d ( x ，炉兰掣 ( 2 5 ) 2 1 2 相似性度量 经常采用的相似性函数有以下两种； 1 j a c c a r d 系数 集合特征模型上常见的相似性度量是j a c c a r d 系数1 刚9 7 1 ，定义如下： s j a c c ( x y ) = 矧， ( 2 正) 其中x ，y 是两个集合。 y i a n 9 1 详细证明了1 j a c c a r d ( * ) 是一个度量。 另一种常用的d i c e 系数是从j a c c a r d 系数引申而来的，它的定义如下： s m x ，y ) 2 锗斜 。7 ) 2 余弦函数 璀十w e b 数据的距离函数研究 第2 章距离函数的f f j f 究见状 除了欧几早得距离，c o s i n e 函数也是经常使用的基于向量模型的相似性函 数舣孰氏艄，驴黼。 i 。f 一 擎”- 。擂h w ， ( 2 8 ) 其中x = ( 。l ，x 2 ，x n ) 。y 2 ( y l ，y 2 ，y 。) 。容易证明距离函数1 - c o s i n e ( * ) 除了定义2 1 中的( 1 ) 性质外，其余度量性质都满足。 2 2 集合距离函数的相关研究 本文中将研究基于w e b 结构数据定义的集合语义距离函数。在数据挖掘领 域内与本文研究直接相关的是概念层次的应用。概念层次可用于挖掘概化关联规 则s a 9 5 h f 9 5 和特殊的负关联规则8 0 “9 8 1 。在o l a p t 。s 9 3j 中通常基于概念层次提供 维的多层抽象，与之类似的是面向属性的归约技术( a t t r i b u t e o r i e n t e di n d u c t i o n ) i c c h g l l ，它也用概念层次概化数据。这些研究并不涉及如何基于概念层次或者站 点结构量化对象的相似性或差别。 o l f an a s r a o u i 等人使用f u z z y 聚集算法删o o 埽口遗传算法【n k 0 2 1 对w 曲同志会 话( 页面集合) 进行聚集。他们从w e b 站点结构中抽取有向树结构，存此基础上定 义页面问的相似性和页面集合问的距离函数。但是此距离函数会把两个相同的刈 象间的差别量化成一个任意的非0 值，而且它不满足三角不等式。p g a n e s a n 等 人i o g w 系统地研究了分类层次结构下各种相似性函数，提出了四种相似性函数 g c s m 、o g m 、b g m 和r g m ，后三者统称谱系函数。虽然实验结果表明谱系 函数的量化结果更贴近人的直觉，但是很难把它们转换成度量。 在图像领域早就有人使用图论的方法解决配对和相似性计算。 h a u s d o r f f l h k r 9 3 1 是一种反应点集之间差异的距离，它用极小点对的最大距离值来 表示两个点集问的距离。这种方法简单，而且符合度量的条件，但是对噪声和遮 挡非常敏感。y r u b n e r 等人 r t g 0 0 】提出e m d ( e a r t hm o v e rd i s t a n c e ) 距离函数，用 于计算图像特征分布的差别，此函数只适合处理局部匹配，不同的集合可能会得 出相等的结论。p g i a n n o p o u l o s 等人 铡”】基于e m d 的思想，提出了 p t d f p r o p o r t i o n a lt r a n s p o r t a t i o nd i s t a n c e ) 距离函数，它的一个缺陷是只考虑了集 合各项的分布是否相等，没有考虑权重总和上的差别。本文拓展了e m d 基于图 论的思想，提出了“最大相似宽度”的概念，它是传统集合交集的概念在语义环 境下的自然扩展，在此概念下可以衍生出一族距离函数，x d i s t 便是其中之。 在自然语言处理，信息检索领域也有一些基于层次结构数据和知识计算各种 实体间相似性的研究。 h s 9 8 】基于电子词典定义词间的语义距离和相似性。 堆 w e b 数据的跗离函数研究第2 章距离函数的研究耽状 w b 9 9 提出了基于多个不同的本体计算概念相似性的方法。y w 0 2 针对图结构 提出了计算对象问相关性的算法s i m r a n k 。但是上述研究并没有涉及计算集合问 相似度的问题。 其他相关的研究工作还有 lt o i v o n e n l “”9 5 j 和【g s g 9 9 】在规则聚类方面的研 究工作。这两种方法都提出了一种基于事务数据的集合问的距离。因为事务数据 中包含着用户并不知道的关联信息，所以此种距离函数很难贴近用户的直觉。 因为p r a s a n n ag a n e s a n 等人【( 珩w 0 3 l 也研究集合结构的语义距离函数，与本文 的研究有较大的相关性，因此下面将详细介绍他们定义的距离函数。 p r a s a r m ag a n e s a n 等人【o o w 0 3 1 研究了基于有向树语义结构对象相似性量化方 法，提出了四种相似性函数，分别是： ( 1 1 广义余弦函数g c s m ( g e n e r a l i z e dc o n s i n e s i m i l a r i t ym e a s u r e ) ( 2 ) o g m ( o p t i m i s t i cg e n e a l o g ym e a s u r e ) ( 3 ) b g m ( b a l a n c e dg e n e a l o g ym e a s u r e ) ( 4 ) r g m ( r e c u r s i v eg e n e a l o g ym e a s u r e ) 后三个函数计算原理类似，总称为谱系( g e n e a l o g y ) 十l l 似性函数。它们得出的 数值都在区间i o ，l 】中，0 表示完全不同，1 表示相等。下面给出这些函数的基于 语义路径的定义，并分析了相关性质。 这些函数针对的对象特征模型是项的“包”，即允许项在集合中重复。例如 a , a ，b ，b 便是一个含项a 和b 的包，包中不同的项组成的集合在本章中被称为包 的类集，例如 a ，a ，b ，b ) 的类集是 a ，b ) 。语义结构采用的是关系树，但是边的权重 均为1 ( 虽然p r a s a n n ag a n e s a n 等人在论文最后提到了边权重和有向图，但是没 有提出实际的计算方法) 。包中的项必须是基项，基项在关系树上有权重。本章 用w ( v ) 表示基项v 在关系树中的权重。原文用称之为“导出树( i n d u c e dt r e e ) ” 的结构描述包中各项在关系树中的位置。为了便于理解，此处用语义路径柬描述 单项在关系树中的位置，只在r g m 上使用导出树概念，它是多个语义路径聚合 而成的小关系树。图2 1 是语义路径的导出树的关系； 总严 食品 0 雩 聚合 。，一、 总类 食品 # 、 洒糖粜 白l 酒、巧乒力 0 、0 嵋矿口 包【，_ ，p l 在图4 1 ( a ) 中的语义路径 包( r l ，c t ) 的导出树 图2 1 ：语义路释和导出树 9 觥矗or甲。麒。觚o?甲， 挂fw e b 数据的距离函数研究第2 章距离函数的圳究现状 下面的定义均假设基于某个关系树g ，项间相似度计算使用函数1 。d l ( ) 和 l - d 2 ( ) ，分别记为s i r e l 和s i r e 2 。用v a 表示项v 属于包a 。 定义2 2 ( g c s m ) ：给定两个包a 和b ，它们的“内积”定义为： a b = w ( a ) w ( b ) s i m 2 ( a ，b ) 4 5 艉8 ( 2 9 ) g c s m 相似性函数定义为： ，、f 塞笔一爿，口皆非空g c s m b ( 爿，) = 而丽“。“ l 0 a ，口至少个为空 ( 2 1 0 ) g c s m 函数是一个对称的函数，可看成是c o s i n e 函数的扩展。和c o s i n e 函 数类似它不能保证当g c s m ( a ，b ) = 1 的时候必定有a = b 。最简单的例子是包f w l ， w i ，w i ，w i 和 w 1 的g c s m 值是l 。在本章中称此类现象为“比例匹配”。具体 解释为：设两个包a 和b ，它们的项个数( 包括重复的) 分别是7 1 和n ，a 和b 的类集足x ，每个项x e x 在a ，b 中的出现次数分别记为a ( x ) 和b ( x ) 。如果每个 项x e x ，a ( x ) m = b ( x ) n ，则称a 和b 在比例上等同。对于比例等同的两个包 g c s m 总能得出1 值。距离函数l g c s m ( , ) 不满足三角不等式。例如有二个包 a = w 1 ) ，b = w i ，p l ，c = p 1 ) 。1 * g c s m ( a ，b ) + 1 一g c s m ( b ，c ) = 2 - j ，那么就需要将 特征空问划分成若干个小的特征区间，每个小区间成为直方图的一个箱( b i n ) ，这 个过程称为分箱( b i n n i n g ) 。然后通过计算落在每个小区间内的特征数量和，可以 得到新的直方图。 颜色直方图( c o l o rh i s t o g r a m ) 是用来表达图像特征的最常用的手段，它表示 了图像中具有同颜色级别的象素的个数。r g b 空问是数字图象普遍采用的颜色 空间，根据颜色的三基色( r e d ，g r e e n ，b l u e ) 目力口原理而得到。从统计意义上讲， 颜色直方图反应了图像中各种颜色的分布比例。 l ，_ ，- ， l j lj j 哪， h l h 2 h 3 蚺十w e b 数据的距离函数研究第2 学距离函数的刖f 宄现状 图2 2 ：3 个直方图h l 、h 2 和h 3 上述的直方图方法会产生一定的问题。设想两幅图像的颜色直方图儿乎相 同。只是互相错开了一个箱( 如图2 2 所示) ，这时如果我们采用欧儿取得距离 计算两者的相似度，会得到很小的相似度值。为了克服这个缺陷，需要考虑到相 似但不相同的颜色之蒯的相似度。一种方法是采用二次式距离 1 0 k 8 9 。另一种方法 是对直方图事先进行平滑过滤，即每个箱中的特征对于相邻的几个箱也有贡献。 积累直方图( c u m u l a t i v eh i s t o g r a m ) 法就是常用的对直方图进行、f 滑的方法。 积累直方图的定义如下【8 0 9 5 】： i k d ( k ) = y ! ，n ， t = 0 ，1 ，一l( 2 1 3 ) 丁：o 其中各参数的含义同直方图的一样。图2 2 中3 个直方图的积累直方图如图 2 3 所示。这样，相似但不相同特征之间的相似度对直方图的相似度也有所贡献。 l 图2 3 ：h l 、h 2 年h 3 对应的积累直方图 常用的直方图之间距离度量有以下几种： a ) 绝对值距离和欧几里得距离 如果直方图的的各特征之问是正交无关的，而且各维度的重要程度相同，两 个直方图a 和日之间距离最常用绝对值距离或者欧几里得距离来度量。假设a 和口是两个含有个箱的直方图，则它们之间的绝对值距离可以表示为： q ( 一，b ) = = i a , 一e i ( 2 1 4 ) 类似地，欧几里得距离可以表示为： d 2 ( a ，b ) = 。n - 1 ( 4 一旦) 2 ( 2 1 5 ) b 1 直方图相交法 度量直方图距离的另一种方法是直方图相交( h i s t o g r a mi n t e r s e c t i o n ) 。假设彳 和b 是两个含有个箱的直方图，则它们之间的相交距离表示为： 一l m i n ( a , ，b j ) i ( a ，b ) = 幽 酉一 ( 2 1 6 ) 4 苎! ：! ! ! 塑型竺里塞里塑竺壅 竺! 皇墅堕里堑塑盟! i ! ! 鉴 c 1 二次式距离 对于基于颜色直方图的图像检索来说，二次式( q u a d r a t i cf o r m ) l e 离已被证明 比使用欧拉距离或是直方图相交距离更为有效。原因在于这种距离考虑到了不同 颜色之间存在的相似度，通过引入相似性矩阵w ，使其能够考虑到相似但不相同 的颜色问的相似性因素。两个直方图一和b 之间的二次式距离可以表示为： q ( a ，口) = ( 爿一b ) 7 w ( a 一口) ( 2 1 7 ) 其中w = 【w 。， ，w 。表示直方图中下标为i 和j 的两个箱之间的相似度。这样， 颜色直方图本身就包含了不同颜色之间的相似性因素，因此可以直接地使用欧拉 距离或直方图相交距离。 皋十w e b 数蜊的蹦离函数研究第3 章基于w e b 结构数据的语义距离函数 第3 章基于w e b 结构数据的语义距离函数 本章研究如何把相关的领域知识嵌入到对象差别计算的过程中，量化对象在 语义。卜的差别。与以往的研究相比，本章把项间的关系表示结构从有向根树扩展 到了更加复杂的有向无环图。在此基础上，提出了一个量化对象间语义差别的距 离函数xd i s t ，它基于图论中的运输问题模型量化两个对象之间的差别，并且 允许用户根据应用要求的不同，通过参数调整