XML_数据相似度研究_第1页
XML_数据相似度研究_第2页
XML_数据相似度研究_第3页
XML_数据相似度研究_第4页
全文预览已结束

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

25 XML数据相似度研究 张丙奇白 硕赵章界 中国科学院计算技术研究所北京 100080 摘 要XML 数据的大量出现为信息检索数据挖掘智能信息处理提供了机遇和挑战而相似度计算是 XML 文档检索挖掘和深层次 智能处理的基础对相似度计算进行研究具有非常重要的意义在对 XML 数据特征进行深入分析的基础上提出了一种递归相似度计算 方法实验结果表明该方法具有较好的效果 关键词XML相似度语义递归算法VSM模型 A Recursive Method to Compute Similarity of XML Documents ZHANG Bingqi, BAI Shuo, ZHAO Zhangjie (Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080) AbstractThe quantity of XML data shared in the World Wide Web is increasing quickly and it offers both challenges and opportunities in information retrieval, data mining and intelligent information processing. As the basis of information retrieval, mining, and processing, accurate determination of similarity between XML documents is important and valuable. This paper provides a novel recursive method to get the similarity between XML documents according to the semantic and structural features of XML. It also provides experiments to show the comparison of the method against traditional methods and the results prove the method is highly effective. Key wordsXML; Similarity; Semantic; Recursive algorithm; VSM model 计 算 机 工 程 Computer Engineering 第31卷 第11期 Vol.31 11 2005年6月 June 2005 博士论文 文章编号10003428(2005)11002503 文献标识码A 中图分类号TP311.52 1 传统的相似度方法 传统的相似度算法都是扁平化的即表示对象的特 征是扁平的特征之间互相独立可以看成是笛卡尔多 元组的集合可以采用向量的方式进行计算和处理经典的 相似度计算方法有以下几种 1.1 Set/Bag模型 对象通过对象具有的特征集合来描述对象之间的相似 度通过描述对象的特征集合的交集表示 例如下面的 Jaccard 计算方法和 Dice计算方法1 设 XY 分别是两个对象的特征集合则对象之间的 Jaccard 相似系数为 | | ),( YX YX YXSimJdcc = Dice相似系数为 | |*2 ),( YX YX YXSimDice + = 其它相关的方法有 Inclusion 测度Overlap 系数等 1.2 VSM 模型 VSM 模型是信息检索和文本挖掘中常用的方法在这 里文本的每个特征被认为互相独立所有的特征形成一个 特征空间 每个特征通过一定的方法赋予权重 比如 TF-IDF 方法每个文本表示为特征空间上的一个向量相似度通过 计算特征向量在特征空间中的某种距离来度量采用余 弦度量的相似度定义为 它既能表示关系 对象等结构化的数据 也能表示 Web 这样的半结构 非结构 的数据具有“自描述”“树形结构”结构嵌套等特点 在数据交换和集成中得到大量应用下面是一个 XML 文档 (文档 1)示例 文档 1 论小说的写作 四川文艺出版社 人民中路 8 号巴金 四川成都 流沙河 四川金堂县 从上面的例子中可以看到文档 1 的根节点说明该 文档是关于书的下面有和 等节点的下面又有 等 节点XML 的这种树形结构是通过 Tag 的关系来表示的 2.2 对XML数据挖掘的研究 XML 数据的大量出现为数据挖掘和智能信息处理提供 了新的方向和挑战已引起很多研究者的关注文献2研究 了使用结构化向量表示 XML 文档以用于分类的问题XML 的每个节点是其父节点的一个特征每个特征又是一个向 量其特征为它的子节点文献3讨论了利用 XML 中的语 作者简介张丙奇(1972)男博士生主研方向网络网络信息 处理白 硕研究员博导赵章界博士生 定稿日期2004-04-10 E- mailzhangbq 26 义进行 XML 结构挖掘的问题文章中主要利用语义词典对 节点名称进行同义词扩充来计算节点之间的相似度矩阵通 过节点相似度矩阵和公共路径的数目计算 XML 结构相 似度 上面各种方法讨论的基本上是 XML 结构的相似度计 算 是针对 XML 的 Tag 或 Schema 的相似度比较 它们没有 考虑 XML 更复杂的结构如同一路径下同名子节点数量的 区分与处理 另外对 XML 所描述内容也没有更深的讨论 3 XML数据相似度算法 3.1 XML数据的特点与相似度计算的关系 XML 本身具有的“自描述”“树形结构”结构嵌套 特性使得 XML 数据的相似度计算与传统的扁平计算方 式不同这种不同主要基于以下几个方面 (1) 非叶子节点与叶子节点的特征表示不同 (2) 特征所在的节点不同表示的语义不同 (3) 同一路径下同名称子节点的数目对相似度计算的影响 (4) XML 的结构的层次性决定了 XML 相似度计算的递归性质 3.2 XML相似计算中特征的分类 XML 数据中节点有叶子节点和非叶子节点之分叶 子节点的特征由它的值表示而一个非叶子节点的所有子节 点构成了该节点的特征集合 根据子节点名称不同和同名子节点数目的不同把非叶 子节点的特征分为横向特征和纵向特征 纵向特征该节点的具有相同名称的子节点的集合 横向特征多个纵向特征形成的向量表示 图 1 表示了文档 1 对应的树形结构的子节点共有 3 类名称分别为标题出版社作者这 3 类节点 构成了的横向特征 每类节点的集合分别是一个纵向特 征其中名称为作者的纵向特征的子节点数是两个 图1 文档1对应的树形结构 3.3 XML结构化递归模型表示 通过对 XML 数据特征的分析我们采用结构化递归模 型表示 XML 数据 首先XML 数据可用它的根节点表示根节点又由它 的子节点表示节点分为非叶子节点和叶子节点非叶子节 点node定义为 ),( 21N hAtrrNodehAtrrNodehAtrrNodenode?= (1) 其中 i hAtrrNode表示 node 的同名子节点集合 , iii zNodeListnodeNameStructurehAtrrNode= (2) i zNodeList 是名称为 i nodeName的子节点集合 出版社出版社出版社=名字地点 电话 作者作者, , =姓名出 生地 3.4 XML相似度的计算方法 首先按照 3.3 节的描述将 XML 文档的根节点表示 成式(1)的形式其中每个元素如式2式3定义其 中每个非叶子节点又可按照式 1 表示 叶子节点按照式(4) 表示这样XML 文档表示成一个递归的向量 根据 XML 文档中节点类型和横纵特征的不同在相似 度计算中采用不同的方式 (1)叶子节点相似度的计算 叶子节点相似度的计算是整个 XML 数据相似度计算的基础由于 XML 可以描述各种类型的数据因 此应根据叶子节点的取值类型定义相应的计算方法这一点可参照 文献4中不同类型数据的处理方法 如对文本类型采用 VSM模型 (2) 非叶子节点相似度的计算node之间的相似度分别计算 向量中节点名称相同的hAtrrNodei的相似度node之间的相似度是 对应的各个 hAtrrNodei相似度的加权平均 同名hAtrrNodei纵向 之间的相似度计算方法hAtrrNodei 的相似度通过计算相应的纵向节点集合的相似度得到因为 纵向节点集合中的节点名称相同它们是无序而且平等的 两集合的任意两两元素之间都有相似度的计算但两集合之 间的相似度应满足一些直观的要求 (1)两个集合和它本身的 相似度为 1(2) 两个集合 AB A与 B 的相似度应等于 B 与 A 的相似度即满足对称性3) 假设两个集合都有 n 个 元素其中 mmn个元素相同又假设两个元素的相似 度只能是 0不同或 1 相同那么这两个集合的相似度 应该是 m/n 要计算两个集合的相似度最容易想到的方法是首先计 算两个集合的所有元素两两之间的相似度然后再进行加权 平均但该方法可能使一个集合和它本身的相似度不为 1 除非它的任意两元素之间的相似度都为 1这个结果是不符 合对相似度定义的要求的 我们采用如下方法计算纵向节点集合的相似度 (1)首先计算两个集合的所有节点两两之间的相似度 从所有 的相似度值中选择最大的一个将这个相似度值对应的两个节点对 应起来并累加该最大值 (2)从所有的相似度值中删去那些已经建立对应关系的节点的 相似度值 (3)重复上述步骤(1)和步骤(2)直到所有的相似度值都被删除 (4)没有建立起对应关系的节点与空元素对应 (5)求平均相似度累加的和除以对应元素个数返回 上述算法首先根据相似度的取值建立两个集合元素的 一一对应关系然后再计算两个集合的相似度集合的相似 度等于其元素对的相似度的加权平均因为集合的元素之间 都是平等的所以将所有的权值取成相同的于是集合的相 似度等于其元素对的相似度的算术平均 3.5 XML相似度的递归算法实现 上面介绍了 XML 数据中不同类型节点的处理方法整 个 XML 文档的处理通过对节点相似度的递归计算实现算 法如下 函数elementSimilarity :计算节点的相似度递归函数 输入 1 node 2 node / 两个 XML 节点 输出simValue / 1 node 2 node的相似度 横向结构 纵向结构 书 名字 地点电话 标题出版社作者 作者一 作者二 姓名 出生地 27 (1)如果 1 node 2 node的节点名称不同simValue0返回 (2)如果 1 node 2 node的类型是叶子节点 按照预先定义的叶 子节点相似度计算方法计算返回相应的相似度 (3)如果 1 node 2 node不是叶子节点设 simValue0 1)将 1 node 2 node 按照1表示成 ),( 112111N hAtrrNodehAtrrNodehAtrrNodenode?= ),( 122212M hAtrrNodehAtrrNodehAtrrNodenode?= 2)设 i1 3)从 2 node中找到节点名称等于 i hAtrrNode 1 的节点名称的 j hAtrrNode2 如果没有找到,转 f 4)按照 3.4 节介绍的纵向节点计算方法计算 i hAtrrNode1与 j hAtrrNode2 的相似度 通过递归调用 elementSimilarity 计算集合中 两两节点相似度 5)simValue 加上当前 i hAtrrNode1与 j hAtrrNode2 的相似度 6)i=i+1如果 i=N转 c否则到 g 7)simValue simValue / max(M,N)返回 3.6算法分析 上面介绍了计算 XML 文档相似度的递归算法算法的 目的是在计算相似度的过程中利用 XML 节点的语义信息和 结构的层次特征 首先在节点进行相似度比较时同层次上采用了扁 平 的方式只有同名称的子节点进行比较不同名称的 子节点之间相似度为 0这样考虑了 XML 的节点名称的 语义信息节点名称不同代表的语义不同同时计算中 也考虑了同名子节点的数量对节点相似度的影响 其次对于文档相似度的计算最终归结于叶子节点的 值 的相似度计算 考虑递归过程中横向特征的计算方法 是利用路径对可利用节点进行过滤最终只有相同路径的节 点才能进行相似度的比较叶子节点在文档中的层次和位置 影响了叶子节点对相似度的贡献 由此可见本文的递归算法既考虑了节点的语义信息 又考虑了 XML 的层次结构对相似度计算的作用所以本 文的递归算法的计算结果更加直观更真实可靠 4数据实验 我们从 Yahoo 网站的求职简历 ElectricalMechanical7 目录中下载了部分个人求职简历添加标签Education Work ExperienceSkill, Objective 等将 HTML 文件转换成 XML 比较本文提出的递归计算方法和传统方法计算相似度 的结果其中文档 16 属于 Electrical 目录712 属于 Mechanical目录 实验1 分别从相应的目录中抽取两个文档 利用本文的 递归方法计算这两个文档和所有文档的相似度对于叶子节 点相似度的计算按照文本进行处理采用 Set/Bag 模型中 Jaccard 系数相应的利用 Set/Bag 模型中 Jaccard 系数计 算这两个文档和所有文档间的相似度实验结果如图 23 图 2 以 Electrical 目录中文档 1 和 3 为基文档和所有文 档的相似度比较,上面两图是递归计算方法,叶子节点处理采 用 Set/Bag 模型中的 Jaccard 系数下面两图是采用 Set/Bag 模型中的 Jaccard 系数计算的整篇文档的相似度 图 3 以 Mechanical目录中文档 7 和 10 为基文档和所有 文档的相似度比较, 上面两图是递归计算方法叶子节点处 理采用 Set/Bag 模型中的 Jaccard 系数下面两图是采用 Set/Bag 模型中的 Jaccard 系数计算的整篇文档的相似度 图 3 是以 Mechanical目录中文档 7 和 10 为基文档的相 似度比较采用递归计算方法文档 710 与同类中文档的 相似度要大于与异类中文档的相似度而采用传统 Set/Bag 模型类别区分效果要差很多 图2 实验结果1 图3 实验结果2 实验2 递归计算方法中对于叶子节点的相似度采用 VSM 模型的 cosine 相似度计算方法相应的按照 VSM 模 型 cosine 相似度计算这两个文档和所有文档的相似度通过 对文档中的词汇进行停用词和 Stem 处理得到表示特征因 为文档较少特征的权重采用 DF实验结果如图 4图 5 图 4 以 Electrical 目录中文档 1 和 3 为基文档和所有文 档的相似度比较上面两图是递归计算方法叶子节点处理 采用 VSM 模型 下面两图是采用 VSM 模型计算的整篇文档 的相似度文档 图4 实验结果3 图 5 以 Mechanical目录中文档 8 和 10 为基文档和所有 文档的相似度比较, 上面两图是递归计算方法叶子节点处 理采用 VSM 模型 下面两图是采用 VSM 模型计算的整篇文 档的相似度文档 下转第 126 页 126 于 IPv6 为 7bit值ML=0 表示在部分 PLUT 中没有找到匹 配然后将输出的 N 个 ML 进行比较从而得到最长匹配 em=MLmax,及输出端口 M 2.2.3 IFPLUT 使用 TCAM 进行路由查找 执行快速查找表的常用设备为 TCAM 三重目录地址可 设定内存允许对路由表中的不同长度的元素进行比较 查找表规模的新近增加 迫使使用快速内存技术如 TCAM 的 费用变得昂贵起来 在本设计中 与整个查找表的规模相比 分配每个部分的内存模块是很小的如在平衡分配中为 N 分之一这减少了需要考虑 TCAM 指令多个同时输出的逻 辑复杂性因此使用 TCAM 就很容易了另一个使用 IFPLUT 的重要优势为我们在 TCAM 输出端口不需要优先 级编码器4(普通 TCAM 设计这是由于每个 PLUT 生成不 超过一个碰撞 排除了给予优先级的编码 由于相同的原因 不需要对每个 PLUT 的 TCAM 条目进行分类这将 TCAM 的更新复杂性大大减小为 O(1) 因为每一个新条目可增加到 TCAM 的任意位置由于使用 TCAM 的常规查找更新很慢 因此这可能是 IFPLUT 体系结构中使用 TCAM 的最大优势 2.2.4 使用 IFPLUT+TCAM 的实验结果 在本文的体系结构中最主要的两个时间开销1内 存查找2选择器时延我们使用 TCAM 内存模块作为 PLUT则第一步内存访问的时延为常数大约为 15ns 的迟延对于选择器部分产生主要的时间开销可用处理器 的比较指令来进行计算对于不同的 N 值16,32,64,128 将 N 从 16 翻倍到 32从 32 到 128不会以相同速度增加 最大迟延值得强调的是从 IPv4 到 IPv6 的迟延增加是可 以忽略的 这使本结构适合下一代数据包处理设备 当 PLUT 用 TCAM 来实现时迟延的增加是很小的即少于 10% 这使 IFPLUT 体系结构的迟延与 N 的扩展无关 这对于扩展 特性是非常重要的 从现在市场上考虑的 OC-192 线路接口卡如光 I/O 卡 可看出本体系结构的两个优势 OC-192 以 10Gbps 的速度运 行现在来讨论用 IFPLUT+TCAM 技术来处理 OC-192 的可 能性我们用处理器来模拟选择器可得到对于选择器和 TCAM 的大约时延分别 10ns 和 15ns 的时延这表示整个时 延为大约 25nsIFPLUT 每秒可处理 4 千万次查找假设数 据包平均为 125 字节这相当于 4 个 OC-192 的线路全部吞 吐量的线路速度 3 结论 本文通过对 IP 数据包的转发机制和路由查找算法的研 究设计出了一个基于 IFPLUT+TCAM 的网络安全设备的 IP 数据包转发方案并对设计的方案进行了实验通过将前 缀查找表分割为小表每一个表与一个输出端口相关联而实 现了路由查找并行进行因为 IFPLUT 的查找时间不依赖于 前缀长度 IFPLUT 具有可升伸缩性 可移植到 IPv6 IFPLUT 在均衡网络中可达到最高效率前缀在 PLUT 中的分布几乎 是相等的 参考文献 1 Asthana A, Delhp C, Jagdish H, et al. Design of a Gigabit IP Router. Technical Reprot 11251-911105-09TM, AT&T Bell Labs, 1991 2 Doeringer W, Karjoth G, Nassehi M. Routing on Longest Matching Prefixes. IEEE Trans. on Networking, 1996, 4(1): 86-97 3 McAulley A, Tsuchiya P, Wilson D. Fast Multi Level Hierarchical Routing Table Using Content-addressable Memory. US Patent 034444, 1995 4 Shah D, Gupta P. Fast Updating Algorithms for TCAMS. IEEE Micro, 2001-02 5 Akhbarizadeh M J, Nourani M. IP Packet Forwarding Technique Based on Partitioned Lookup Table. Center for Integrated Circuits & Systems, The University of Texas at Dallas Ri

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论