本 XML 数据挖掘系列文章的第 3 部分将解释几个有关集群 XML 文档的概念，以及介绍在文档内容和结构随着时间发生变更时要执行的 XML 文档集群任务。在真实世界应用程序中，XML 文档从一个版本发展成另一个版本，其中要实现的变更数量是无法预测的。实现变更后，原始的集群解决方法就会遭到淘汰，这是非常正常的。为了克服这一点，本文将描述一种非冗余方法论，它可以在变更后重新计算 XML 文档的新集群。本文将提供详细的用例示例以帮助您了解该技术，以及如何将其技术应用到实践中。

背景概念

集群 是在密集数据集中寻找区域的一种数据挖掘任务（通常是使用距离度量实现的）。换句话说，集群 是对数据进行分区的一个流程，其方法是将相似的数据项分组到集中，称之为集群。

由于 XML 的分层结构，集群 XML 文档与集群其他数据集有所不同。已推出了若干个 XML 集群方法，比如使用结构的 XML 文档集群、语义 XML 集群、无模式 XML 文档集群和链接 XML 文档集群。您可以在本系列的 XML 数据挖掘，第 1 部分：考察几种 XML 数据挖掘方法 文章中阅读有关不同类型的 XML 集群的更多信息。本文主要关注于使用分层（基于距离）的 XML 集群技术通过结构来实现 XML 集群。

在基于距离集群技术中，来自给定集的每个对象都会首先分配到一个集群。接着，计算集群对之间的距离，并针对最靠近的（最相似的）集群进行分组以形成一个新的（更大的）集群。换句话说，与其他 XML 文档对相比，这两个 XML 文档更加相似，其之间的距离也更短；因此它们可以成为同一个集群的成员。

要例证 XML 文档相似性的概念，图 1 显示了三个 XML 文档，其中两个高度相似（即，文档 D_A 和 D_B），而文档 D_C 与 D_A 或 D_B 均没有相似点。文档 D_A 和 D_B 列出的是有关两个学生的信息，包括学年、学科与考试，以及学生的名字。文档 D_C 列出的是有关一本书的信息，其中包括标题、ISB 编号和两个作者的名字。

在 图 1，有关学生详细信息的任务查询均只适用于相应的文档（即 D_A 和 D_B），并不适用于其他包括不同信息的文档，比如 D_C。直观地说，文档 D_A 和 D_B 是分组在一个集群中，而 D_C 自身也形成了另一个单独的集群。

XML 文档和 XMLDelta 之间的距离

如果您将两个 XML 文档（D₁ 和 D₂）以及其表现看作两个树，那么这两个文档之间的距离 会记录为 d（D₁ 和 D₂），该距离是通过基本操作集（即插入、更新和删除）来进行确定的，这些操作拥有最少的总成本，并且可以将一个文档转换成另一个文档。

例如，要确定 图 1 中文档 D_A 和 D_B 之间的距离，您必须先查找可以将 D_A 转换至 D_B 的基本操作集（正向）；接着，查找可以将 D_B 转换成 D_A 的基本操作集（反向）。您要针对这两个操作集计算其成本；最后选择拥有最小总成本的集：

d(D_A --> D_B)={update(Student, John, Mary), update(year, 2, 3), insert(Exams), insert (Subject, Drama), insert (Subject, Music)} and d(D_B --> D_A)={ update(Student, John, Mary), update(year, 2, 3), delete(Exams), delete(Subject), delete(Subject)}

要计算每个操作集的最小成本，您要基于 XML 文档中的节点位置使用一个成本模型。（该模型的一个示例，请参阅 参考资料。）本示例中的成本是：

d (D_A --> D _B) = d (D_B --> D_A) = 5

在本示例，您可以选择其中一个操作集，因为他们拥有相同的总成本。

在动态（也称之为多版本）XML 文档的用例中，每一个新文档版本实际上是对先前文档版本进行某种程度的更新而产生的。该更新通常是通过在先前 XML 文档版本中混合应用基本操作所实现的（即，插入、更新和删除）。如果您将这些操作看为一个整体，他们就会形成一个所谓的 delta。 当您谈到 XML delta，您就会知道它指的是 XML 文档两个连续版本之间的差异。delta 的成本 是 delta 中列出的以及前面提及的操作组合的总成本。

回页首

集群动态（多版本）XML 文档

当您集群动态 XML 文档时，您拥有两个基本选项：

• 选项 A。传统方法（选项 A）很简单。当一个或多个文档发生变更，该选项就会比较集里每对 XML 文档以重新计算所有 XML 文档中的新距离。很显然，该选项成本很高，因为应用到文档的变更级别并不太明显。因此，如果 XML 文档的一个版本与其之前的版本只有稍微的差别或完全无差别，那么对他们进行比较就会涉及到多余和没必要的工作。
• 选项 B。该选项是本文中详细介绍的一个选项。它使用了之前为每对 XML 文档计算的距离（即实现任何变更前文档之间的距离）以及这段时间中发生的变更集。图 2 显示了有关选项 B 中涉及的步骤概要。
  
  图 2. 根据变更评估动态 XML 文档之间距离的步骤概要
  
  
  

您可以将用在 图 2 选项 B 中的方法论分成两个主要部分：

• 第 1 部分：初始计算距离。注意，该阶段为一次性，不可重复性。主要步骤包含：
  1. 确定并存储每对 XML 文档之间的距离。
  2. 计算并存储使用两种方向（即正向和反向）转换每对文档的最小成本。
• 第 2 部分：再次评估距离。您可以计划安排该阶段，以便在每次变更后定期运行或在您需要知道两个文档之间最新距离时运行。这些步骤包含：
  1. 获取在 第 1 部分 或在最新运行的 第 2 部分 中计算的距离矩阵。
  2. 获取最新获知的距离时间戳与当前时间戳之间的变更集。
  3. 将之前或初始的距离、拥有最小成本的转换方向（正向和反向）以及文档间的变更集包含进方程式中，重新计算每个距离。

在此阶段，很清楚，该流程的 第 2 部分 中最关键步骤是重新计算数据集中每对 XML 文档版本的新距离。对于需要重新评估距离的任何两个给定的 XML 文档，会存在两种不同的情景：

• 仅一个文档发生对变更
• 两个文档都发生对变更

对于每个情景，都需要更深一步考虑应用到文档的操作类型；然而，本文对此将不再进行详细的讨论。您可以在 参考资料 中查找更多相关的信息和详细说明。

回页首

案例研究

本示例使用的 XML 文档代表银行中的客户交易。银行为每一个在该银行开户的客户创建一个 XML 文档，然后该银行再在每次登记新交易时创建一个新版本的 XML 文档。每个版本都拥有一个交易日期，可通过元素 >_date< 来显示。假设，在 2008 年 1 月 1 日存在三个客户的三个文档（即文档 D₁、D₂ 和 D₃）。清单 1 显示文档 D₁。

				
 
<?xml version="1.0" encoding="UTF-8"?> 
<customer> 
    <name>cust1</name> 
    <street>street1</street> 
    <city>;city1</city> 
    <transaction> 
        <trans_date>01/01/2008</trans_date> 
        <deposit> 
            <bank_account>BA1</bank_account>>
            <BSB>BSB1</BSB>
            <acc_name>ACC1</acc_name>
            <amount>100</amount>
        </deposit> 
    </transaction> 
</customer> 

接着，在 2008 年 1 月 15 日分别对第二个和第三个客户再登记了一次交易。结果，文档 D₂ 和 D₃ 分别拥有新版本（即 D^*₂ 和 D^*₃）（见 清单 2）。

				
 
<?xml version="1.0" encoding="UTF-8"?> 
<customer> 
    <name>cust2</name> 
    <street>street2</street> 
    <city>city2</city> 
    <transaction> 
        <trans_date>01/01/2008</trans_date> 
        <deposit 
            ><bank_account>BA2</bank_account> 
            <BSB>BSB2</BSB> 
            <acc_name>ACC2</acc_name> 
            <amount>200</amount> 
            <balance>1000</balance> 
        </deposit> 
    </transaction> 
</customer> 
******************************************************************************* 
<?xml version="1.0" encoding="UTF-8"?> 
<customer> 
    <name>cust2</name> 
    <street>street2</street> 
    <city>city2</city> 
    <transaction> 
        <trans_date>15/01/2008</trans_date> 
        <withdrawal> 
            <bank_account>BA2</bank_account> 
            <BSB>BSB2</BSB> 
            <acc_name>ACC2</acc_name> 
            <amount>400</amount> 
            <balance>800</balance> 
        </withdrawal> 
    </transaction> 
</customer> 

清单 3 显示了变更前后该案例研究中的第三个文档（即 D₃ 和 D^*₃）。

				
 
<?xml version="1.0" encoding="UTF-8"?> 
<customer> 
    <name>cust3</name> 
    <street>street3</street> 
    <city>city3</city> 
    <transaction> 
        <trans_date>01/01/2008</trans_date> 
        <withdrawal> 
            <bank_account>BA3</bank_account> 
            <BSB>BSB3</BSB> 
            <acc_name>ACC3<acc_name> 
            <amount>50</amount> 
        </withdrawal>
    </transaction> 
</customer>
******************************************************************************* 
<?xml version="1.0" encoding="UTF-8"?> 
<customer> 
    <name>cust3</name> 
    <street>street3</street> 
    <city>city3</city> 
    <transaction> 
        <trans_date>15/01/2008</trans_date> 
        <withdrawal> 
            <bank_account>BA3</bank_account> 
            <BSB>BSB3</BSB> 
            <acc_name>ACC3</acc_name> 
            <amount>50</amount> 
            <balance>500</balance>
        </withdrawal> 
    </transaction>
</customer>

该研究用案的目标是展示，2006 年 1 月 1 日所创建的初始集群在 2008 年 1 月 15 日登记客户新交易后如何发生变更。

第 1 部分：初始的距离计算

正如前面所谈及的，此阶段计算了变更集前文档之间的距离，以确定初始集群构成。借以本例，假设每个基本操作拥有一个相当于 1 的成本。

表 1、表 2 和 表 3 显示了该研究案例中每对文档所需的操作和距离（即操作的总成本）。

对于 表 1、表 2 和 表 3 中的可追踪性，会忽略为每个节点附加的惟一标识符，并列出操作及其相应值。

正如您看到的，D₁ 和 D₂ 间的初始距离是最小的。

根据简单的分层集群方法 (hierarchical clustering method），文档 D₁ 和 D₂ 会分组在同一个集群中（C^BC₁，其中 BC 代表 before changes），而 D₃ 会形成一个独立的集群（即 C^BC₂）。

图 3 显示了第 1 阶段未尾的集群构成。虚线指示文档 D₂ 和 D₃ 拥有新版本，并且您想要确定变更后的新集群。这将会带您进入下一个阶段的方法中。

第 2 部分：再次评估距离

正如前面所提及的，您可以在变更集影响集群 XML 文档后在必要时应用此阶段。

首先，您必须获取两个文档版本间的变更集 (deltas)。在这种情况下，是 Δ(D₂ -->D^*₂) 和 Δ(D₃ -->D^*₃)。那么，这些 deltas 将会被应用来确定变更后 XML 文档的新距离。

表 4 显示了 Δ(D₂ -->D^*₂) 的操作集。

表 5 显示 Δ(D₃ -->D^*₃) 的操作集。

在您确定了包含在 delta 中的操作后，下一步是根据旧距离与 delta 重新计算每个新距离。换句话说，您要重新计算下列距离：

• d'(D₁ --> D^*₂), using d(D₁ --> D₂) and Δ(D₂ --> D^*₂)
• d'(D₁ --> D^*₃) using d(D₁ --> D₃) and Δ(D₃ --> D^*₃)
• d'(D^*₂ --> D^*₃) using d(D₂ --> D₃), Δ(D₂--> D^*₂) and Δ(D₃ --> D^*₃)

在重新估算这些距离时，会对一些操作进行匹配，并且会找到替换操作，例如，如果操作 Update (<amount>, '100', '200') 与 Delete (<amount>, '200') 相匹配，那么 replacement 操作就是 Delete (<amount>, '100')。换句话说，在 XML 文档中应用两个匹配的操作所产生的结果与在同一个初始 XML 文档应用替换操作所产生的结果相同。要查找有关如何定义匹配和替换操作的更多细节，请参阅 参考资料。

图 4 直观表示如何为 d'(D₁ -->D^*₂) 计算最后成本。

在此情况下，11 个操作无法与其他操作相匹配，所以他们会计算其自己的成本，8 个操作由 4 个补充操作进行替换，2 个操作相互颠倒。因此，参与这新距离中的所有操作的各个成本的总和是 11 + 4 + 0 = 15。因此，新距离 d'(D₁ -->D^*₂) = 15。

使用相似的逻辑，计算距离 d'(D₁ -->D^*₃)。图 5 显示所涉及的操作。

重新评估距离的最后一步是计算 d'(D^*₂ --> D^*₃)。图 6 显示所涉及的操作。

基于所获得的结果，图 7 显示变更后的新集群构成。注意，该集群已经发生变更，并且现在新版本的文档 D₂ 和 D₃ 形成了一个集群，而文档 D₁（未发生变更）自己形成一个单独的集群。

回页首

结束语

本文描述了使用基于距离的技术来集群动态 XML 文档的方法。具体来说，它描述了一种方法，可允许您在初始文档发生变更后确定动态 XML 文档版本之间的距离。该方法即节省时间又节约成本，因为他极大地减少了 XML 文档发生变更后重新计算距离和重新估算集群所需操作的数量。

出于本文和研究案例的目的，有意使用简单和版本数量较少的 XML 文档。对于更加复杂的文档，您可以遵循相同步骤，使用更多的版本，和区别更大的版本。

参考资料

学习

• XML 数据挖掘，第 1 部分：考察几种 XML 数据挖掘方法：在本系列的第 1 部分中，首先介绍了从 XML 文档挖掘隐含知识。学习了挖掘数据、信息的层次结构以及元素之间的关系。
  
  
• XML 数据挖掘，第 2 部分：挖掘 XML 关联规则：研究 XML 数据挖掘，XML 数据分析的一方面。在由 3 部分组成的此系列文章的第 2 部分，您将了解静态和动态 XML 关联规则，以及在挖掘 XML 文档发生变更时如何创建基于版本的关联规则。
  
  
• Intelligent Dynamic XML Documents Clustering [L.I. Rusu、W. Rahayu 和 D. Taniar，发表于 International Conference on Advanced Information Networking and Applications (AINA 2008) 第 22 届会议，IEEE Computer Society，日本冲绳]：查看一种有效的方法，能够让您在重新评估更改后的集群化动态 XML 文档间的成对距离时避开多余计算。
  
  
• Storage Techniques for Multi-versioned XML Documents [L.I. Rusu、W. Rahayu 和 D. Taniar，发表于International Conference on Database Systems for Advanced Applications (DASFAA 2008) 第 13 届会议，印度新德里]：阅读并评估动态 XML 文档的四种存储方法。
  
  
• Partitioning Methods for Multi-version XML Data Warehouses [L.I. Rusu、W. Rahayu 和 D. Taniar，发表于 Distributed and Parallel Databases，25(1-2)，Springer，2009 年 4 月]：探索如何构建一个使用多种分区技术的 XML 数据仓库模式，并评估 XML 数据仓库的各种查询类型。
  
  
• XML 新手入门：获得学习 XML 所需的资源。
  
  
• developerWorks XML 技术专区：寻找提高您在 XML 领域技能所需的资源，包括 DTD、模式和 XSLT。参见 XML 技术文档库 获取广泛的技术文章和技巧、教程、标准和 IBM 红皮书。
  
  
• IBM XML 认证：了解如何才能成为一名 IBM 认证的 XML 和相关技术的开发人员。
  
  
• developerWorks 技术活动 和 网络广播：随时关注这些活动中的技术。
  
  
• Twitter 上的 developerWorks：现在就加入并关注 developerWorks 推文。
  
  
• developerWorks 播客：聆听针对软件开发人员的有趣的访谈和讨论。
  
  
• developerWorks 演示中心：观看面向初学者的产品安装和设置演示，以及为经验丰富的开发人员提供的高级功能。
  
  

获得产品和技术

• IBM 产品评估试用版软件：下载或 IBM SOA 人员沙箱，并开始使用来自 DB2®、Lotus®、Rational®、Tivoli® 和 WebSphere® 的应用程序开发工具和中间件产品。
  
  

讨论

• developerWorks 概要信息：现在就创建您的概要信息并 建立关注清单。
  
  
• XML 专区讨论论坛：参与任何一个 XML 相关的讨论。
  
  
• developerWorks 中文社区：查看开发人员推动的博客、论坛、组和维基，并与其他 developerWorks 用户交流。
  
  

关于作者

Laura Rusu 于 2009 年在澳大利亚墨尔本拉筹伯大学完成了她的计算机科学博士学位，研究的课题是 XML 数据仓库和挖掘。她在许多 国际性会议 上提出了好几种创新的 XML 数据仓库和挖掘技术，还在同行认可的国际刊物上发表过论文。她编写了 mining association rules from XML documents 书中的一章，还编辑了一本关于 data mining and warehousing technologies 的书。Laura 具有学院、研究和 IT 行业等各种角色的经验。

为本文评分

评论

回页首

内容

• 背景概念
• 集群动态（多版本）XML 文档
• 案例研究
• 结束语
• 参考资料
• 关于作者
• 评论