（计算机软件与理论专业论文）基于遗传算法的xml文档聚类的研究与应用.pdf

巾山大学硕士学位论文基于遗传算法的x m l 文档聚类的研究与应用 基于遗传算法的x m l 文档聚类的研究与应用 专业：计算机软件与理论 硕士生：黄启辉 指导教师：高集荣副教授 摘要 x m l 作为一种w e b 上通用的数据表示和交换格式，在互联网高速发展的今 天得到了越来越多的应用。与h t m l 相比，x m l 具有更大的灵活性。它不仅可 以用来标记无结构的文本信息，还可以标记高度结构化的规则数据( 如数据库中 的数据) 。但同时，这种灵活性也给x m l 的查询处理带来了新的问题。随着w e b 上x m l 数据的快速增长，如何帮助用户快速有效地检索大量的x m l 数据，得到 想要的信息，便成为亟待解决的课题。 一般来说，文档聚类是一种帮助人们检索信息的有效手段。与普通文本文档 相比，x m l 具有自描述性、半结构化、层次性等特点，本身带有一定的结构和 语义信息，这些特点更使得x m l 文档聚类成为了检索x m l 文档信息的有效手段。 事实上，国内外对此已做过不少研究，本文在以前学者研究的基础上提出了 一种新的基于遗传算法进行x m l 文档聚类的方法。首先，遗传算法可以用于聚 类操作并能取得良好效果，已经得到证明，但如何将该算法的思想应用到x m l 文档聚类中还没有相关研究。本文针对x m l 文档可以表示成文档结构树这一特 性，提出了一种新的基于树的层次结构的二进制位图索引编码方案，并相应建立 了一系列有助于遗传操作( 选择、交叉、变异) 的位图运算。其次，x m l 文档 聚类的关键点是文档间相似性的度量，本文在综合考虑了x m l 文档树层次、深 度这些特性的基础上，将其与遗传算法交叉算子、变异算子的设置相结合，提出 了一种新的基于遗传算法的x m l 聚类算法。最后，在研究遗传算法的变异过程 时，本文针对x m l 特性提出了一种动态选择变异位置的策略，从而有助于算法 更快地寻找到全局最优解或准最优解。 最后，本文从实践的角度通过实验对比分析，验证了算法的可行性和高效性。 关键字：x m l ；聚类；遗传算法 中山大学硕士学位论文基于遗传算法的x m l 文档聚类的研究与应用 t h er e s e a r c ha n da p p l i c a t i o no fc l u s t e r i n gx m ld o c u m e n t s b a s e do ng e n e t i ca l g o r i t h m m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：h u a n gq i h u i s u p e r v i s o r ：a s s o c i a t ep r o f e s s o rg a oj i r o n g a b s t r a c t a sac o m m o nd a t ar e p r e s e n t a t i o na n de x c h a n g ef o r m a t so nt h ew e b ，x m lh a s b e e nu s e dm o r ea n dm o r ef r e q u e n t l yt o d a ya l o n gw i t ht h er a p i dd e v e l o p m e n to ft h e i n t e m e t c o m p a r e dw i t hh t m l ，x m l h a sg r e a t e rf l e x i b i l i t y i tn o to n l yc a nb eu s e d t ot a gt h et e x to fu n s t r u c t u r e di n f o r m a t i o nb u ta l s oc a nb eu s e dt om a r kh i g h l y s t r u c t u r e dd a t a ( e g d a t ai nt h ed a t a b a s e ) a tt h es a m et i m e ，h o w e v e r , t h ef l e x i b i l i t yo f x m lh a sb r o u g h tn e wp r o b l e m sa b o u tt h ex m lq u e r y i n g w i t ht h er a p i dg r o w t ho f x m ld a t ao nt h ew e b ，h o wt oh e l pu s e r sq u i c k l ya n de f f i c i e n t l ys e a r c hal a r g en u m b e r o fx m ld a t aa n dg e tt h ei n f o r m a t i o nt h e yw a n ti sb e c o m i n ga nu r g e n tp r o b l e mt ob e s o l v e d i ng e n e r a l ，c l u s t e r i n gi sa l le f f e c t i v ew a yt oh e l pp e o p l e g e ti n f o r m a t i o n c o m p a r e dw i t ho r d i n a r yt e x td o c u m e n t s ，s e l f - d e s c r i p t i v e ，s e m i s t r u c t u r e d a n d h i e r a r c h i c a la r ec h a r a c t e r i s t i c so fx m l ，w h i c hh a sac e r t a i nd e g r e eo fs t r u c t u r ea n d s e m a n t i ci n f o r m a t i o ni t s e l t h e s ef e a t u r e sm a k ex m ld o c u m e n tc l u s t e r i n gb e c o m e a ne f f e c t i v ew a yt os e a r c hi n f o r m a t i o ni nx m ld o c u m e n t s i nf a c t ，m a n yr e s e a r c h e sh a v eb e e nd o n ea th o m ea n da b r o a d ，t h i sp a p e rp r e s e n t s an e w a l g o r i t h mo fc l u s t e r i n gx m l d o c u m e n t sb a s e do ng e n e t i ca l g o r i t h m f i r s to fa l l ， i th a sb e e np r o v e dt h a tt h eg e n e t i ca l g o r i t h mc a nb eu s e dt oc l u s t e ra n dc a na c h i e v e g o o dr e s u l t s ，b u tb o w t ou s et h ei d e ao fg at os o l v et h ep r o b l e mo fc l u s t e r i n gx m l d o c u m e n t sh a sn o tb e e nr e s e a r c h e d d u et ot h ef a c tt h a tx m ld o c u m e n tc a nb e e x p r e s s e da st h ed o mt r e e ，t h i sp a p e rp r e s e n t san e wb i n a r yb i t m a pi n d e xe n c o d i n g s c h e m eb a s e do nt h eh i e r a r c h ys t r u c t u r eo ft h et r e e ，a n da c c o r d i n g l yas e r i e so fb i t m a p c o m p u t i n g a b o u t g e n e t i co p e r a t i o n s ( s e l e c t i o n , c r o s s o v e r , m u t a t i o n ) w i l l b e n t 巾山大学硕士学位论文 基于遗传算法的x m l 文档聚类的研究与应用 e s t a b l i s h e d s e c o n d l y , a st h ek e yo fx m ld o c u m e n tc l u s t e r i n gi st h em e a s u r eo f s i m i l a r i t yb e t w e e nd o c u m e n t s ，t a k i n gi n t oa c c o u n tt h el e v e l , d e p t ho fx m l d o c u m e n t t r e ea n dc r o s s o v e ro p e r a t o r , m u t a t i o no p e r a t o ri nt h eg e n e t i ca l g o r i t h m , t h i sp a p e r p r e s e n t st h ea l g o r i t h mo fc l u s t e r i n gx m ld o c u m e n t sb a s e do ng e n e t i ca l g o r i t h m f i n a l l y , t h r o u g hs t u d y i n gt h ep r o c e s so fm u t a t i n gi nt h eg e n e t i ca l g o r i t h m , t h i sp a p e r p r e s e n t st h ed y n a m i cs e l e c t i o ns t r a t e g yo fm u t a t i v ep o s i t i o ns ot h a tt h eg l o b a lo p t i m a l o rq u a s i - o p t i m a ls o l u t i o nc a nb ef o u n d i nt h ee n d ，w ep r o v et h a tt h em e t h o dp r o p o s e di nt h i sp a p e ri sf e a s i b l ea n dh i g h l y e f f e c t i v et h r o u g he x p e r i m e n t a la n a l y s i s k e y w o r d s ：x m l ，c l u s t e r i n g ，g e n e t i ca l g o r i t h m i v 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 煎窟雄 日期： d 7 年，月2 乙日 使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名：贡名翠 日期： 哆年歹月z z - 日 翩虢鞠季 r 期：9 7 年j 月日 中山大学硕士学位论文基于遗传算法的x m l 文档聚类的研究与应用 1 1 研究背景 第1 章绪论 随着网络和信息技术的发展，特别是w e b 技术在各个领域的广泛应用，数 据在w e b 环境下如何有效的表示、存储和交换逐渐成为有待解决的重要问题。 上世纪9 0 年代初，超文本标记语言( h y p e r t e x tm a r k u pl a n g u a g e ，h t m l ) 凭 借自身语法简单、平台无关等特性逐渐成为w e b 文档的标准语言，为网络环境 中数据的表示、存储发挥了重要的作用，然而，该语言也有很多弊端，一方面， 由于语法的简洁严谨，无法满足对w e b 文档新标记的需求，缺乏灵活性和可扩 展性，在需求广泛的w e b 应用中已显得捉襟见肘；另一方面，h t m l 难以实现 自动的数据交换，它的标记只能控制文档的显示，而不能描述数据的内容，而这 一点恰恰是数据检索、电子商务应用所必须的。于是，可扩展标记语言( e x t e n s i b l e m a r k u pl a n g u a g e ，x m l ) 便应运而生。x m l 是i n t e m e t 环境中跨平台的、依赖 于内容的技术，它本身就是为了存储和交换数据而存在的，而且允许使用者自定 义标记，较于h t m l 具有更好的灵活性和可扩展性。这些优点，很快使得x m l 成为了网络环境中数据表示和交换的标准。 由于x m l 具有灵活性、可扩展性、自描述性等良好特性，在网络和数据库 领域得到了大量应用，如何帮助用户快速有效地检索大量的x m l 数据，得到想 要的信息，便成为急需解决的课题。然而，x m l 不同于以往的w e b 文档表示形 式，它标记灵活、类型多样，一些传统的信息检索算法由于不能识别它特有的结 构和内容特征而并不适用于x m l 。 当今，数据挖掘领域的聚类分析已经成为了处理和管理数据的重要手段，并 应用于各式各样的数据类型。所谓聚类，就是根据数据元素之间的相似度将元素 集合进行划分，使得相同类的元素相似度尽可能的大，不同类的元素相似度尽可 能的小。通过对x m l 文档进行合适的聚类操作，不仅可以获得x m l 的文档类 型定义( d o c u m e n tt y p ed e f i n i t i o n ，d t d ) 等特征信息，还可以帮助将对x m l 的检索精确定位到某一类别当中，提高搜索效率。 由于x m l 的特殊性，给这一领域的研究带来了不小的挑战。比如说，x m l 中山大学硕士学位论文基丁遗传算法的x m l 文档聚类的研究与应用 不仅包含数据的内容信息，更主要的是包含了结构信息；在逻辑结构方面，x m l 通常表示成树形结构，而不是常见的数据的离散结构或线性结构；在表现形式上， x m l 的标记是灵活的，没有严格的语法约束。这些都造成了在度量x m l 相似 性方面传统的一些聚类算法或者根本不适用，或者不能取得良好的聚类效果。因 此，如何寻找一种合适的聚类算法来处理x m l 文档，已经成为国内外研究的一 个热点问题。 1 2 国内外研究现状 由上面分析可知，对于x m l 的聚类操作其关键点是x m l 文档之间相似性 的度量，关于这方面的研究可以追溯到上世纪8 0 年代t a i 等人基于树的编辑距 离来度量两棵树的相似度【l 】，它对x m l 相似度的度量提供了很大的借鉴意义。 然而，这种基于树的模型较复杂，在处理大量x m l 文档时，需要遍历每棵x m l 树的所有节点，时间开销较大，并且对于文档中大量重复的元素不能很好的处理 【2 】 o 上世纪9 0 年代末到本世纪初，伴随着x m l 在数据交换和存储领域的广泛 应用，一些学者针对x m l 等具有半结构化特性的文档进行了较深入的研究 3 1 1 4 5 1 。s a e h i n d r aj o s h i 等人提出了基于d o m 树路径相似性的x m l 相似度计算 方法【6 】，处理该模型相对于直接处理树模型要简单一些，且时间复杂度较低，然 而作者并没有考虑树的层次权重对相似性度量的影响，而且在进行路径比较时采 用路径的完全匹配，这样在相似性度量的精确度上就要受到影响。x c l u s t i v 将传 统的层次聚类算法应用到x m l 的聚类问题中去，主要利用x m l 中元素的相似 性，如元素的结构、语义和上下文信息，但它的缺点是并没有充分利用x m l 含 有的结构化信息，仍然局限在某些元素的匹配上。s - g r a c ee 8 】将x m l 转化为结 构图的形式，通过计算两个图之间边的匹配关系来度量x m l 之间的相似性，在 某些情况下能得到比基于树的编辑距离的方法更好的结果，但该方法的主要缺点 是算法复杂度高，至少为o ( n 3 ) 。文献 9 】也是采用图匹配的方法来计算x m l 文 档和它对应的d t d 之间的结构相似度，该方法的缺点是必须获得x m l 文档的 d t d 信息，但在现实应用中，d t d 并不总是能够得到的。 还有很多学者将数据挖掘中的其它方法运用到x m l 的相似性度量以及聚类 2 中山大学硕士学位论文基于遗传算法的x m l 文档聚类的研究与应用 问题中去，如基于频繁结构的x m l 聚类研究【1 0 】【i i 】【1 2 】【1 3 】，基于x m ls c h e m a 的 聚类研究【1 4 】【1 5 】【1 6 】等等。随着近些年来对智能算法研究的深入，许多学者利用智 能算法来解决聚类问题，并取得了较好的成果，如蚁群算法【1 7 】【1 引、自组织神经 网络【1 9 】【2 0 1 等等。遗传算法【2 1 】【2 2 】作为一种具有自组织和自适应能力的求解全局最 优解的优化算法，在诸多领域都有所应用，聚类的最优化求解问题【2 3 】【2 4 1 1 2 5 】【2 6 1 当 然也不例外。以上成果对研究如何快速和有效的进行x m l 文档的聚类提供了很 大的参考价值和借鉴意义。 1 3 论文的主要工作 本文首先简要介绍了x m l 的相关概念及数据挖掘中的聚类分析方法，重点 研究了当前针对x m l 的聚类算法。文章中首先分析了x m l 聚类的特殊性，在 综合了以往学者关于这方面研究成果的基础上，结合x m l 的特性和遗传算法在 寻找全局最优解方面的优势，提出了一种基于遗传算法的x m l 聚类方法。 本文的主要工作包括以下几个方面： 1 ) 研究了数据挖掘中聚类技术的发展现状，重点研究了x m l 本身的特性和常 见聚类方法的理论基础及优缺点，借鉴了已有的x m l 聚类算法的思想和处理方 法并分析了其中的不足。 2 ) 要进行x m l 的聚类分析首先要针对x m l 特点选择一种合适的编码方案， 本文在借鉴了基于e p a t h 路径和位图索引这两种编码方案的基础上，提出了一种 新的基于树的层次结构的x m l 位图索引编码方法并定义了一组与之相关的操 作。 3 ) 基于上面的x m l 编码方式和对遗传算法的研究基础，本文提出了一种基于 遗传算法的x m l 聚类方法，从结构的角度对文档的相似性进行度量，在求得相 似度的情况下利用遗传算法对文档进行聚类操作。 4 ) 遗传算法涉及三大遗传操作选择、交叉、变异，本文针对x m l 的特性 和基本遗传算法的一些弊端，提出了一种适用于x m l 的动态确定个体变异位置 的策略，从而可以更快地寻找到全局最优解或准最优解。 中山大学硕士学位论文基丁二遗传算法的x m l 文档聚类的研究与应用 1 4 论文的结构组织 本文共分八章，其内容安排如下： 第一章绪论，介绍论文的研究背景和目前针对x m l 聚类分析技术的国内 外研究现状，并给出本文的主要工作和结构安排。 第二章x m l 与聚类分析，介绍了x m l 语言的概念、特性及其相关技术， 接着介绍了聚类分析的概念、作用和分类以及判断聚类优良性的标准，并对几种 经典的聚类算法( 如k - m e a n s 等) 给出了简要介绍。 第三章x m l 的聚类研究，介绍了x m l 聚类的特殊性以及判断x m l 聚类 结果是否有效的标准，并介绍了有关x m l 聚类研究方法的分类，详细介绍了基 于编辑距离的x m l 聚类方法和基于e p a t h 、位图索引的x m l 表示方法，本文借 鉴这两种方法的思想提出了一种新的基于树的层次结构的x m l 位图索引表示方 法，该方法可以有效的表达x m l 的特性并能为后面用到的遗传算法的三大操作 提供便利。 第四章遗传算法简介，在这一章中，主要是为下文需要用到的遗传算法进 行简要的介绍，做好理论铺垫。涉及的内容包括遗传算法的概念、特点、基本思 想以及主要构成要素，在本章最后总结了基本遗传算法的主要缺陷，从而可以在 后面的实际应用中对基本遗传算法的某些步骤加以改进。 第五章基于遗传算法的x m l 聚类，这是本文的核心部分，通过前面的概 述和研究提出了一种基于遗传算法的x m l 聚类算法并给出了算法的详细步骤， 这其中包括遗传算法的编解码方式，适应度函数的确定，选择、交叉、变异三大 遗传操作的详细阐述，算法终止条件的确定等等。针对x m l 的特性，本文通过 对遗传算法的“选择操作引入“精英选择策略”，根据个体与种群适应度的相 对关系动态确定“变异操作中的变异位置，有效的规避了基本遗传算法在处理 x m l 问题上的一些弊端。 第六章算法模块设计与实现，在这一章中，基于前面的分析，给出了一个 完整的实现基于遗传算法的x m l 聚类的算法模型，建立了相应的数据结构，并 对算法的一些重点步骤给出了伪码表示。 第七章实验与结果分析，在这一章中，对本文提出的x m l 聚类算法做了 实验验证，从对比分析的结果上，可以看出本文算法的有效性和优越性。 4 中山大学硕士学位论文 基于遗传算法的x m l 文档聚类的研究与应用 第八章结束语，总结全文，并针对该课题未来的研究方向做了展望。 1 5 本章小结 本章主要介绍了x m l 在数据表示、存储、交换领域的广泛应用和重要地位， 指出了由于x m l 自身的一些特点使得x m l 的检索成为一个难点，需要使用聚 类这种数据挖掘手段对x m l 进行有效的处理，接着重点介绍了国内外对于x m l 聚类的研究现状，并分析了现有研究存在的一些问题和不足，最后介绍了本文所 做的主要工作和文章的组织结构。 5 中山大学硕士学位论文基丁遗传算法的x m l 文档聚类的研究与应用 第2 章x m l 与聚类分析 2 1x m l 语言及其相关技术 2 1 1x m l 语言 x m l 2 7 1 ( e x t e n s i b l em a r k u pl a n g u a g e ，可扩展标记语言) 的出现是与i n t e r n e t 的迅速发展和w e b 技术的广泛应用密不可分的。由于传统h t m l 的局限性，使 它并不能满足大规模w e b 应用所需的可扩展性、结构化和数据交换的要求。为 此，w 3 c ( 万维网联盟) 的一个工作组于1 9 9 6 年着手设计一个可以满足当时 w e b 应用的新语言，也就是后来的x m l ，该组织于1 9 9 8 年2 月正式发布了 x m l l 0 标准。 x m l 是s g m l ( t h es t a n d a r dg e n e r a l i z e dm a r k u pl a n g u a g e ，标准通用标记 语言) 的一个优化子集，在s g m l 中，定义了独立于平台的文本文档的格式、 索引和链接信息以及描述文档结构的标签，而著名的h t m l 就是它在w e b 环境 下描述超文本信息的重要应用。但是，由于h t m l 这种标记语言在设计时过多 的考虑了w e b 数据的外观表现，而忽略了存储和交换结构化数据的应用，并且 过于严谨的语法和有限的标记导致了扩展性较差，不能满足现今大规模w e b 应 用的需求。同h t m l 一样，x m l 也是一种元标记语言，也是采用了d t d 的语 言标准，然而，其本身与h t m l 有很大的区别，主要表现在以下四个方面【2 7 】： 1 可扩展性 h t m l 不允许用户自行定义文档的结构和属性，而x m l 则允许用户按需创 建新的标记，以便更好地从语义上修饰数据。这种可扩展性一方面使得x m l 文 档的可读性更好，另一方面也方便了不同领域内的数据交换和共享。 图2 1 是一个描述一台电脑配置信息的x m l 文档，其中的 、 、 等都是用户自定义的有意义的标记信息。在x m l 文档中， 开始标记名 和结束标记名 之间的内容被称为“元素”，去掉开 始标记和结束标记后的部分被称为“元素内容 ，其中元素内容也可以包含新的 标记也就是子标记，比如图2 1 中的 和 就是作为 的 6 中山大学硕士学位论文基于遗传算法的x m l 文档聚类的研究与虑用 子标记而存在的。此外，在x m l 的开始标记中还可以包含标记的属性，比如图 2 1 中的 ，属性的出现可以理解为不含子标记的元素。 h p a 【d 7 2 0 0 16 0 k i n g s t o n e 30 0 0 叫c o m p u t e r 图2 1x m l 文档实例 2 结构化 h t m l 不支持深层的结构描述，而x m l 可以将自身的结构信息组织到任意 复杂的程度。一个x m l 文档通常是按照层次结构的关系来组织信息的，而其中 嵌套的标记就表达了文档的结构。使用标记来描述文档结构有两个前提条件：一 是标记要能反映文档内容的逻辑关系；二是标记要和它描述的信息相分离。x m l 中的数据是采用“树”结构来表达自身信息的。图2 1 中的x m l 文档表示成树 状结构如图2 2 所示： 图2 - 2x m l 文档树 x m l 表示成树结构后具有了一般树结构明显的层次关系，x m l 中嵌套的父 7 中山大学硕+ 学位论文基丁遗传算法的x m l 文档聚类的研究弓应用 子标记被描述成了树中的父子节点，x m l 中不包含子结构的标记在树中则以叶 节点的形式出现。另外，x m l 中的属性也可以认为是在树中没有子女的叶子节 点。本文后面的聚类分析都是基于x m l 这种树结构的特性来展开论述的。 3 自描述性 x m l 通常都包含一个描述自身属性和类型的文件，称作文档类型定义 ( d o c u m e n tt y p ed e f i n i t i o n ，d t d ) 。d t d 是一个a s c i i 文件，后缀名是d t d ， 在其中包含了对x m l 文档格式的描述，比如x m l 中的元素的定义规则、元素 之间的逻辑关系、元素可以使用的属性等等。d t d 主要具有两个作用，一方面 它提供了对x m l 的校验机制，通过比较x m l 与d t d 来确认x m l 是否符合规 范，是否是有效的x m l ，元素和标记的使用是否正确等等；另一方面，d t d 提 供给应用程序一个数据交换的格式和标准，不同组织和团体只要约定好d t d 格 式并用它来生成x m l ，这个x m l 就可以在不同的应用程序环境下实现数据交 换，从而实现了资源和信息共享。 4 强化的w w w 表现能力 x m l 较传统h t m l 的表现力更加丰富，文档显示可以根据用户的要求而改 变。x m l 只规定了信息的内容，而没有规定信息如何表达，这实际上正是x m l 的长处，将内容与形式相分离。用户可以编辑和使用合适的样式表x s l ( e x t e n s i b l es t y l es h e e tl a n g u a g e ，可扩展样式表语言) 和c s s ( c a s c a d i n gs t y l e s h e e t s ，层叠样式表) ，来将数据按照需要呈现到浏览器中。 2 1 2x m l 的相关技术 x m l 的相关技术规范主要有d o m 、x l i n k 、x m ls c h e m a 等。 d o m d o m 2 7 1 是d o c u m e n to b j e c tm o d e l ( 文档对象模型) 的缩写，它提供了一组 与浏览器、操作系统平台、语言无关的访问页面的接口( a p i ) ，以便程序和脚 本能够动态访问和修改x m l 文档的内容、结构、样式，这为应用程序开发者提 供了方便。d o m 是基于文档的树状结构的，它提供了用来表示x m l 文档的标 准对象以及存取和操纵它们的标准接口。 8 中山大学硕士学位论文基于遗传算法的x m l 文档聚类的研究与应用 d o m 的优点是这个模型是基于基本的树形数据结构的，在解析x m l 文档 时将整个文档信息存储于内存中，使用常用的树形数据结构的操作来访问节点， 简单易用并且具有丰富的a p i 。但它的缺点也很明显，由于需要将整个x m l 存 储在内存中，当文档很大时，会导致处理效率较低，解析速度慢，内存占用量过 高。 x l i i l l ( 相对于h t m l 中提供的超链接，x m l 中提供了一种更为强大和灵活的链接 设置，不仅支持h t m l 的单向链接，还支持多方向、多目的的链接，它就是 x l i n k 2 7 1 。在h t m l 中，使用 标记来指示链接，而在x m l 中，用户可以根 据需要在同一文档中加入不同的具有自己特有属性的链接元素，外部应用程序可 以根据元素及属性名或者通过“x l i n k ：的标记来识别链接。 x m ls c h e m a x m ls c h e m a 2 8 1 类似于前面提到的d t d ，它的作用和d t d 一样，都是用于 规定x m l 中的内容及语义，提供对x m l 文档的约束校验机制。但是d t d 仅从 结构上对x m l 加以约束，而x m ls c h e m a 在d t d 的基础上又提供了一组补充 规则，还从数据结构、数据类型、属性等多个方面对x m l 加以约束，形成了更 加严格的约束校验机制。另外，x m ls c h e m a 本身就是一个x m l 文档，可以采 用d t d 进行描述，采用常用的x m l 解析方法进行处理。 2 2 聚类分析 2 2 1 聚类概念及其作用 所谓聚类，很难给它一个确切而科学的定义，这里给出e v e r i t t 在1 9 7 4 年给 聚类下的定义【2 9 】：聚类是将一组数据分为多个聚簇，相同聚簇内的数据尽可能 的相似，不同聚簇内的数据尽可能的不相似；同一个聚簇内的点与点的距离要小 于不同聚簇内点与点的距离；一个聚簇也可以描述为相对密集的多维空间中点集 的会聚，它通过相对稀疏的点集与其它的聚簇相分离。 上述概念只是对聚类的定性描述，概括说来，也就是“物以类聚，人以群分， 要想将聚类用于科学计算，还要给出它的定量描述，其中关键点是如何定义数据 9 中山大学硕士学位论文基于遗传算法的x m l 文档聚类的研究与应用 与数据之间的距离或者叫做相似度的问题，这也是众多聚类研究的关键点所在。 在定义好了相似度的情况下，r n 空间的聚类问题数学表示形式如下【3 0 】： 将r n 空间中的n 个点划分成k 类，其中令p = p l ，p 2 ，p 3 ，p 。) 代表n 个点构 成的集合，s l ，s 2 ，s 3 ，s k 代表k 个划分的集合，则满足： ( 1 ) s i m ，i = l ，2 ，3 ，k ( 2 ) s i n s j = ，i , j 2 1 ，2 ，3 ，k i j 七 ( 3 ) us ，= p i = l 聚类是数据挖掘和模式识别等领域研究的重要内容，在识别数据的结构特征 方面发挥着重要作用。从机器学习的角度讲，聚类是个无监督的学习过程。所谓 无监督学习是相对于有监督学习而言的，有监督学习指的是已经具备了一定的先 验知识，是在已经指定了分类标记的训练集的基础上进行学习。而聚类则是在没 有先验知识也就是在没有输入训练集的情况下让计算机自己学习，由于它不需要 先验知识，因此常常作为其他数据挖掘任务( 如分类、关联规则等) 的预处理步 骤。 2 2 2 聚类算法的分类 不同的聚类算法适合不同的待聚类数据集，没有一种聚类算法是对任何具有 不同结构的多维数据集都普遍适用的口。因此，针对不同类型的数据集应当选 用适合它的聚类算法。 评判一个聚类算法好坏的标准主要有如下几点：1 、是否能用于处理大数据 量；2 、是否能用于处理不同的数据类型；3 、对初始数据的输入顺序是否敏感； 4 、是否能处理不同形状的聚簇；5 、对于脏数据和离群点是否敏感等等。 聚类算法有多种分类方法，本文将聚类算法大致分为如下几类：基于划分的 聚类算法，基于层次的聚类算法，基于密度和网格的聚类算法，其他聚类算法等。 1 基于划分的聚类算法 该算法首先创建k 个划分，也就是指定k 个聚类数目，通过反复迭代运算， 将数据从一个划分移到另一个划分中，直到待聚类数据收敛或者达到规定阈值。 典型的基于划分的聚类算法有：k - m e a n s ，k - m o d e s ，f c m 等。 1 n 中山大学硕士学位论文基丁遗传算法的x m l 文档聚类的研究与应用 下面以经典的k - m e a n s 算法为例简要描述该算法的基本思想。 m a c q u e e n 于1 9 6 7 年首次提出了k 均值聚类算法( k - m e a n s 算法) ，直至今 日，仍然被许多聚类任务所采用，并且由它衍生出了很多其他的经典聚类算法。 k - m e a n s 算法的核心思想是接受一个聚簇数量参数k ，然后通过一个距离函 数的度量，经过若干次迭代将n 个待聚类数据划分到k 个聚簇中，聚类目标是使 得类内元素相似度尽可能大，类间元素相似度尽可能小。 k - m e a n s 算法的工作过程是【3 0 】： 从n 个对象中随机选定k 个对象作为初始的聚类中心( c l ，c 2 , c 3 ，c k ) 。 将剩余的每一个对象x i 找到与它距离最近的聚类中心c m ，并将它划分到 c m 中去。 根据当前c m 中包含的对象的数据更新聚类中心为c m 。 不断重复上述过程直到某个阶段c m _ c m 或者达到某个规定阈值为止。 此时更新后得到的聚类中心就代表了最终的划分。 k - m e a n s 算法的一个关键点是对象之间距离的定义，一般是取对象与相应聚 类中心的欧氏距离作为测度标准。 k - m e a n s 算法的优点是【3 2 1 ：聚类收敛速度快，对大型数据集分类的时间复杂 度为o ( t k m n ) ，其中t 为迭代的次数，k 为聚类个数，n 为待聚类对象的个数，m 为聚类对象属性的维数。 它的缺点是容易收敛于局部最优解而得不到全局最优解，并且只适用于凸型 的数值型数据的聚类。 2 基于层次的聚类算法 基于层次的聚类算法一般分为两类，自下而上的聚类方法和自上而下的聚类 方法。所谓自下而上的层次聚类方法就是将待聚类的每一个数据看作初始化的一 个聚簇，通过计算两个聚簇之间的相似度，不断合并相似的聚簇，直到所有数据 都在一个聚簇中或者达到某一结束条件。而自上而下的层次聚类方法则与之相 反，初始化时是将所有数据看作都属于一个聚簇，通过不断分裂直到达到一个结 束条件为止，这个结束条件可以是达到了预期的聚簇数目或者是聚簇内数据的相 似度超过了某一阈值。 传统的层次聚类算法由于时间复杂度较大，一般只适用于小数据量的聚类操 中山大学硕士学位论文基于遗传算法的x m l 文档聚类的研究与应用 作。为弥补不足，基于层次的聚类算法常常与其他算法相结合。典型的这类方法 包括： b i r c h ( b a l a n c e di t e r a t i v er e d u c i n ga n dc l u s t e r i n gu s i n gh i e r a r c h i e s ) 方法【3 3 】，即基于层次的平衡迭代消减聚类法。该算法适用于大数据量的情况， 并且对于增量或动态聚类也非常有效。其基本思想简单说来就是动态的构造一棵 聚类特征树，在树中用一个聚类特征三元组来描述一个聚簇的信息，通过多次迭 代不断地插入和分裂叶子节点来进行聚类。 c u r e ( c l u s t e r i n gu s i n gr e p r i s e n t a t i v e s ) 方法【3 4 1 ，即使用代表点的聚类 方法。它的优点是时间复杂度较低，能处理非球形的聚类数据，对大型数据也有 良好的伸缩性。该算法采用了一种介于质心方法和代表点方法之间的中间策略， 它不像k - m e a n s 一样仅用质心来代表聚簇，而是在每一个聚簇中都选择固定数 目的代表点来表示。聚簇的代表点是这样产生的：首先从一个聚簇中选择若干个 较为分散的点作为该聚簇的代表点，然后按照一个指定的压缩函数将它们压缩到 聚簇的中心，并以各个聚簇的中心为基准衡量不同聚簇之间的距离，进行多次迭 代，每次将距离最近的两个聚簇合并起来。 3 基于密度和网格的聚类算法 基于密度和网格的聚类算法是一类重要的聚类算法，特别在处理空间信息的 领域内有着广泛的应用。与传统的聚类算法不同，基于密度的聚类算法将密度值 作为聚类的准则，通过将密度足够大的区域聚集成类来发现任意形状的聚簇。基 于网格的聚类方法是用矩形块将待聚类的数据空间划分为若干个网格，聚类操作 以网格为单位进行而不是像传统的聚类操作那样以单一数据为单位进行，可以有 效的对大数据量进行聚类操作。 d b s c a n 算法【3 5 】是一个典型的基于密度的聚类算法，该算法首先要声明 这样几个定义- e 邻居，中心记录，直接密度可达，密度可达，密度相连。所 谓e 邻居( e - n e i g h b o r ) ，指的是对于给定记录，距离其半径为e 的记录称为该记录 的e 邻居；中心记录( c e n t e rr e s u l t ) 指当一个记录的e 邻居的数目超过一个最小值 m i n p o i n t s 时，称该记录为一个中心记录；直接密度可达( d i r e c t l yd e n s i t y - r e a c h a b l e ) 的定义是如果i 是一中心记录，j 是i 的e 邻居，则称j 对于i 是直接密度可达的； 如果存在一个链p l ，p 2 ，p 3 ，p 4 p n ，且有p i + 1 对于p i ( i = l ，2 n - i ) 是直接密度可达的， 1 2 中山大学硕士学位论文基于遗传算法的x m l 文档聚类的研究与应用 则有p 。对于p l 是密度可达i 拘( d e n s i t y r e a c h a b l e ) ；如果i 和j 对于记录k 都是密度 可达的，则称i 和j 是密度相连的( d e n s i t y - c o n n e c t e d ) 。 d b s c a n 算法的基本过程是：首先扫描数据集中所有的点，计算每一个点 的e 邻居的数目，如果e 邻居的数目超过了一个设定最小值m i n p o i n t s ，就称该 点为一个中心记录，这样就形成了一个含有该中心记录的聚簇，然后寻找该中心 记录的密度可达的点并将它们合并到该聚簇中去，这样多次迭代直到没有出现新 的聚簇合并时为止。 s t i n g 算法【3 6 1 是一个有代表性的基于网格的聚类算法，它将数据空间划 分为多个网格，每个网格中记录了该网格所包含数据的一些统计信息，如数据点 的数目、均值、方差、最小值、最大值等等，然后以网格为单位进行聚类操作。 使用网格方法的优点是减少了处理项的数目，从原来的以数据点为单位变成以网 格为单位进行处理，适合大规模数据的聚类操作。 4 其他聚类算法 随着智能算法的提出和发展，近几年涌现出了许多基于智能算法的聚类新算 法，比如基于粒子群的聚类算法、基于模拟退火的聚类算法、量子聚类算法等等。 2 3 本章小结 本章主要分为两部分，一部分主要介绍了x m l 的概念、发展历史及特点， 并简要概括了一些与x m l 相关的技术规范，如d o m 、x l i n k 、x m ls c h e m a 等； 另一部分则主要介绍了数据挖掘领域有关聚类的概念及聚类算法的分类，并对每 一类的几个有代表性的算法进行了简要的综述。 中山大学硕士学位论文基于遗传算法的x m l 文档聚类的研究与应用 第3 章x m l 的聚类研究 3 1x m l 聚类的研究背景 x m l 作为一种w e b 上通用的数据表示和交换格式，具有很大的灵活性和适 用性，x m l 文档的聚类逐渐成为检索大量x m l 文档的有效处理手段。 x m l 文档的聚类研究，其核心问题是x m l 文档之间的相似性度量，由于 x m l 中不仅包含了元素的语义信息，也包含了元素与元素之间的结构信息，因 此，过去学者们的研究也都是围绕这两方面来展开论述的。然而，2 0 0 6 年，澳 大利亚昆士兰大学r i c h in a y a k 教授发表在i e e e 上的一篇文章( ( i n v e s t i g a t i n g s e m a n t i cm e a s u r e si nx m lc l u s t e r i n g ) ) 3 7 】已经证明了语义相似性的度量在x m l 聚类中并不起主要作用，实验数据表明，在考虑了语义相似性的情况下，x m l 的聚类效果并没有多大的提高，而由于需要频繁查询w o r d n e t 词典，算法的时 间开销显著增大。因此，本文的研究重点也放在如何从结构的角度度量x m l