XML 数据挖掘,第 3 部分: 集群 XML 文档以改善数据挖掘

评估对动态 XML 文档集群所做的更改,以加快数据挖掘

与从 XML 文档中挖掘关联规则的任务相似,由于 XML 格式的特定结构、灵活性,以及层次结构组织,集群 XML 文档与集群关系型数据有很大的差别。在关于 XMl 数据挖掘系列文章的第 3 部分中,我们将了解 XML 数据挖掘中集群 XML 文档这一主要的任务。

Laura Irina Rusu, PhD MACS CP, 开发团队主管,DW 和 BI 顾问, Computershare Technology Services Australia, La Trobe University Australia

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



2012 年 6 月 25 日

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

背景概念

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

集群技术

在集群度量或空间数据方面已经作了大量的研究,并且提出了若干个算法类型。其中的一些算法如下:

  • 分区算法 (Partitioning algorithms)
  • 分层聚类算法 (Hierarchical algorithms)
    • 单链接算法 (Single-link clustering),也称为最小距离方法
    • 全链接集群 (Complete-link clustering),也称为最大距离方法
    • 平均法链接集群 (Average-link clustering)
  • 基于密度的算法 (Density-based algorithms)

要了解有关具体技术的详细资料,请参阅 参考资料

由于 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 文档的示例
图表显示了相似和不相似 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 中列出的以及前面提及的操作组合的总成本。


集群动态(多版本)XML 文档

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

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

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

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

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

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

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


案例研究

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

清单 1. 用于动态集群案例研究的 XML 文档示例(D1
<?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 日分别对第二个和第三个客户再登记了一次交易。结果,文档 D2 和 D3 分别拥有新版本(即 D*2 和 D*3)(见 清单 2)。

清单 2. 两个连续版本的 XML 文档示例(D2
<?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 显示了变更前后该案例研究中的第三个文档(即 D3 和 D*3)。

清单 3. 两个连续版本的 XML 文档示例(D3
<?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. XML 文档 D1 和 D2 间的初始对距离
d (D1 --> D2)
Update (<name>, 'cust1', 'cust2')
Update (<street>, 'street1', 'street2')
Update (<city>, 'city1', 'city2')
Update (<bank_account>, 'BA1', 'BA2')
Update (<BSB>, 'BSB1', 'BSB2')
Update (<acc_name>, 'ACC1', 'ACC2')
Update (<amount>, '100', '200')
Insert (<balance>, '1000')
d (D1 --> D2) = 8

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

表 2. XML 文档 1 和 D3 间的初始对距离
d (D1 --> D3)
Update (<name>, 'cust1', 'cust3')
Update (<street>, 'street1', 'street3')
Update (<city>, 'city1', 'city3')
Delete (<deposit>)
Delete (<bank_account>, 'BA1')
Delete (<BSB>, 'BSB1')
Delete (<acc_name>, 'ACC1)
Delete (<amount>, '100')
Insert (<withdrawal>)
Insert (<bank_account>, 'BA3')
Insert (<BSB>, 'BSB3')
Insert (<acc_name>, 'ACC3')
Insert (<amount>, '50')
d (D1 --> D3) = 13

正如您看到的,D1 和 D2 间的初始距离是最小的。

表 3. XML 文档 D2 和 D3 间的初始对距离
d (D2 --> D3)
Update (<name>, 'cust2', 'cust3')
Update (<street>, 'street2', 'street3')
Update (<city>, 'city2', 'city3')
Delete (<deposit>)
Delete (<bank_account>, 'BA2')
Delete (<BSB>, 'BSB2')
Delete (<acc_name>, 'ACC2')
Delete (<amount>, '200')
Delete (<balance>, '1000')
Insert (<withdrawal>)
Insert (<bank_account>, 'BA3')
Insert (<BSB>, 'BSB3')
Insert (<acc_name>, 'ACC3')
Insert (<amount>, '50')
d (D2 --> D3) = 14

根据简单的分层集群方法 (hierarchical clustering method),文档 D1 和 D2 会分组在同一个集群中(CBC1,其中 BC 代表 before changes),而 D3 会形成一个独立的集群(即 CBC2)。

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

图 3. 案例研究中的初始集群构成
图表显示案例研究中的初始集群构成

第 2 部分:再次评估距离

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

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

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

表 4. XML 文档 D2 中包含在 delta 的操作
Δ(D2 --> D*2)
Update (<trans_date>, '01/01/2008', '15/01/2008')
Delete <deposit>)
Delete (<bank_account>, 'BA2')
Delete (<BSB>, 'BSB2')
Delete (<acc_name>, 'ACC2')
Delete (<amount>, '200')
Delete (<balance>, '1000')
Insert (<withdrawal>)
Insert (<bank_account>, 'BA2')
Insert (<BSB>, 'BSB2')
Insert (<acc_name>, 'ACC2')
Insert (<amount>, '400')
Insert (<balance>, '800')

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

表 5. XML 文档 D3 中包含在 delta 的操作
Δ(D3 --> D*3)
Update (<trans_date>, '01/01/2008', '15/01/2008')
Insert (<balance>, '500')

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

  • d'(D1 --> D*2), using d(D1 --> D2) and Δ(D2 --> D*2)
  • d'(D1 --> D*3) using d(D1 --> D3) and Δ(D3 --> D*3)
  • d'(D*2 --> D*3) using d(D2 --> D3), Δ(D2--> D*2) and Δ(D3 --> D*3)

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

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

图 4. 直观表示变更后计算新距离 d' (D1-->D*2) 的流程
直观表示变更后计算新距离 d'(D1 -->D*2) 的流程

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

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

图 5. 直观表示变更后计算新距离 d' (D1-->D*3) 流程
直观表示变更后计算新距离 d'(D1 -->D*3) 流程

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

图 6. 直观表示变更后计算新距离 d'(D*2 --> D*3) 流程
直观表示变更后计算新距离 d'(D*2 -->D*3) 流程

基于所获得的结果,图 7 显示变更后的新集群构成。注意,该集群已经发生变更,并且现在新版本的文档 D2 和 D3 形成了一个集群,而文档 D1(未发生变更)自己形成一个单独的集群。

图 7. 变更后的集群构成
变更后的集群构成的图表

结束语

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

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

参考资料

学习

获得产品和技术

讨论

条评论

developerWorks: 登录

标有星(*)号的字段是必填字段。


需要一个 IBM ID?
忘记 IBM ID?


忘记密码?
更改您的密码

单击提交则表示您同意developerWorks 的条款和条件。 查看条款和条件

 


在您首次登录 developerWorks 时,会为您创建一份个人概要。您的个人概要中的信息(您的姓名、国家/地区,以及公司名称)是公开显示的,而且会随着您发布的任何内容一起显示,除非您选择隐藏您的公司名称。您可以随时更新您的 IBM 帐户。

所有提交的信息确保安全。

选择您的昵称



当您初次登录到 developerWorks 时,将会为您创建一份概要信息,您需要指定一个昵称。您的昵称将和您在 developerWorks 发布的内容显示在一起。

昵称长度在 3 至 31 个字符之间。 您的昵称在 developerWorks 社区中必须是唯一的,并且出于隐私保护的原因,不能是您的电子邮件地址。

标有星(*)号的字段是必填字段。

(昵称长度在 3 至 31 个字符之间)

单击提交则表示您同意developerWorks 的条款和条件。 查看条款和条件.

 


所有提交的信息确保安全。


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=10
Zone=XML
ArticleID=822607
ArticleTitle=XML 数据挖掘,第 3 部分: 集群 XML 文档以改善数据挖掘
publish-date=06252012