本 XML 数据挖掘系列文章的第 3 部分将解释几个有关集群 XML 文档的概念，以及介绍在文档内容和结构随着时间发生变更时要执行的 XML 文档集群任务。在真实世界应用程序中，XML 文档从一个版本发展成另一个版本，其中要实现的变更数量是无法预测的。实现变更后，原始的集群解决方法就会遭到淘汰，这是非常正常的。为了克服这一点，本文将描述一种非冗余方法论，它可以在变更后重新计算 XML 文档的新集群。本文将提供详细的用例示例以帮助您了解该技术，以及如何将其技术应用到实践中。
背景概念
集群 是在密集数据集中寻找区域的一种数据挖掘任务（通常是使用距离度量实现的）。换句话说，集群 是对数据进行分区的一个流程，其方法是将相似的数据项分组到集中，称之为集群。
由于 XML 的分层结构，集群 XML 文档与集群其他数据集有所不同。已推出了若干个 XML 集群方法，比如使用结构的 XML 文档集群、语义 XML 集群、无模式 XML 文档集群和链接 XML 文档集群。您可以在本系列的 XML 数据挖掘，第 1 部分：考察几种 XML 数据挖掘方法 文章中阅读有关不同类型的 XML 集群的更多信息。本文主要关注于使用分层（基于距离）的 XML 集群技术通过结构来实现 XML 集群。
在基于距离集群技术中，来自给定集的每个对象都会首先分配到一个集群。接着，计算集群对之间的距离，并针对最靠近的（最相似的）集群进行分组以形成一个新的（更大的）集群。换句话说，与其他 XML 文档对相比，这两个 XML 文档更加相似，其之间的距离也更短；因此它们可以成为同一个集群的成员。
要例证 XML 文档相似性的概念，图 1 显示了三个 XML 文档，其中两个高度相似（即，文档 DA 和 DB），而文档 DC 与 DA 或 DB 均没有相似点。文档 DA 和 DB 列出的是有关两个学生的信息，包括学年、学科与考试，以及学生的名字。文档 DC 列出的是有关一本书的信息，其中包括标题、ISB 编号和两个作者的名字。
图 1. 相似和不相似 XML 文档的示例
在 图 1，有关学生详细信息的任务查询均只适用于相应的文档（即 DA 和 DB），并不适用于其他包括不同信息的文档，比如 DC。直观地说，文档 DA 和 DB 是分组在一个集群中，而 DC 自身也形成了另一个单独的集群。
XML 文档和 XMLDelta 之间的距离
如果您将两个 XML 文档（D1 和 D2）以及其表现看作两个树，那么这两个文档之间的距离 会记录为 d（D1 和 D2），该距离是通过基本操作集（即插入、更新和删除）来进行确定的，这些操作拥有最少的总成本，并且可以将一个文档转换成另一个文档。
例如，要确定 图 1 中文档 DA 和 DB 之间的距离，您必须先查找可以将 DA 转换至 DB 的基本操作集（正向）；接着，查找可以将 DB 转换成 DA 的基本操作集（反向）。您要针对这两个操作集计算其成本；最后选择拥有最小总成本的集：
d(DA --> DB)={update(Student, John, Mary), update(year, 2, 3), insert(Exams), insert (Subject, Drama), insert (Subject, ">Music)} and d(DB --> DA)={ update(Student, John, Mary), update(year, 2, 3), delete(Exams), delete(Subject), delete(Subject)}
要计算每个操作集的最小成本，您要基于 XML 文档中的节点位置使用一个成本模型。本示例中的成本是：
d (DA --> D B) = d (DB --> DA) = 5
在本示例，您可以选择其中一个操作集，因为他们拥有相同的总成本。
在动态（也称之为多版本）XML 文档的用例中，每一个新文档版本实际上是对先前文档版本进行某种程度的更新而产生的。该更新通常是通过在先前 XML 文档版本中混合应用基本操作所实现的（即，插入、更新和删除）。如果您将这些操作看为一个整体，他们就会形成一个所谓的 delta。当您谈到 XML delta，您就会知道它指的是 XML 文档两个连续版本之间的差异。delta 的成本 是 delta 中列出的以及前面提及的操作组合的总成本。