XML 数据挖掘,第 2 部分: 挖掘 XML 关联规则

从静态和动态 XML 文档发现关联规则

在本系列的第 2 部分中,学习从 XML 文档挖掘关联规则。从 XML 文档挖掘关联规则不同于从关系数据挖掘规则。由于语言的灵活性和层次化组织,信息可以不同的方式被结构化在 XML 中。本文还要介绍动态关联规则的观点。还将探究一种在底层 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 年 1 月 16 日

简介

XML 已经逐渐成为很多领域数据表示、存储和交换的语言选择。随着用 XML 表示的信息量的快速增加,人们在寻找解决 XML 文档存储和分析方面问题的适当技术。本系列的第 1 部分 “考察几种 XML 数据挖掘方法” 介绍了一些从 XML 文档挖掘隐含知识的技术。

本文中,学习发现 XML 关联规则(相对于从关系数据发现关联规则)。学习一种用于评估从及时改变内容的 XML 文档抽取出来的 XML 关联规则的有效性的技术。用几个例子来帮助说明二者的区别和新的 XML 数据挖掘技术。


从关系数据发现关联规则

第 1 部分讨论了关联规则,由 Agrawal 和 Srikant 在 1993 年针对关系数据而提出(参见 参考资料),以确定可从购物篮分析中的一组交易抽取出来的有趣关系。抽取这类知识的算法叫做 Apriori 算法。它采用支持度信任度概念,如下所示。

给定一组不同的商品 I 和一组交易 DD 中的任何交易 T 都只包含 I 中的商品,那么一个关联规则 R 隐含着 “X -> Y”,其中 XYI 中不相关的商品。如果 Ds% 的交易同时包含商品 XY,那么规则 RD 中具有支持度 s,而如果 Dc% 的交易包含 X 也包含 Y,它就具有信任度 c

例如,购物篮分析中的一个关联规则是 “购买产品 X 的用户也购买产品 Y,这发生在 s% 的交易中,具有 c% 信任度”。

关系方法中的事务和项

关联规则首先是针对关系数据提出来的。在这个上下文中,事务 是表中的一个记录, 是表中一个属性的值。所以,事务集合由一组记录给出,其中所有记录都共享相同的属性(即表中的列和字段)。

图 1 是一个表中事务集合的可视表示,其中的任务是挖掘一个关联规则作为两个项(属性)XY 的值之间的相互关系。样例事务集合展示了几个不分顺序包含 XY 的项。集合中的其他项要么包含 X,要么包含 Y

图 1. 关系方法中的事务集合和项
关系方法中事务集合和项的概念

从 XML 挖掘关联规则

从 XML 文档挖掘关联规则不同于从关系数据挖掘规则,因为信息可以用 XML 格式以不同的方式结构化。一般来说,发现 XML 关联规则意味着找到一个或多个 XML 文档子结构之间的关系。

针对 XML 关联规则的事务和项

挖掘静态 XML 关联规则中的当前工作使用 XML 数据的 事务 的概念。一个事务集合由通过在 XML 文档中查询特定路径形成的一系列复杂节点给出;单个复杂节点形成一个事务。项是简单节点,即事务节点的子节点。

在关系数据中,从一个表中抽取出来的事务总是包含固定数量的项:属性的数量或者表中存在的列数。根据文档中的嵌套层次以及它是否支持 XML 模式,一个 XML 事务可以具有不同数量的项。一个类似的看法是,XML 文档中所有嵌套的路径都是记录,从根开始。对于文档中的任何节点,每个子节点都被看作一个与相同深度的其他记录相关的记录,或者具有类似的标记(更多信息请参见 参考资料)。

图 2 展示了一个例子,其中每一个 <staff_member> 节点(这里是 John Brown 和 Mellisa White)都是一个事务,每一个 <publi_what><publi_where><publi_when> 节点都是一个项。每个 staff_member 事务都在员工名字下包含一个或多个出版物。每个出版物包含一个 publi_what、publi_where 和 publi_when item。(查看 图 2 中 XML 文档的文本版本。)

图 2. XML 文档中的事务和项
XML 文档中的事务和项的例子

XML 关联规则的上下文、主体和头部

XML 关联规则的上下文是指那些被实际挖掘的 XML 文档部分。有时候,不需要挖掘 XML 文档中包含的所有信息。因此,上下文选择 是指用户在 XML 事务集合上定义约束的能力。

图 3 展示了一个上下文选择的例子。只有代表在 2006 年之后出版了书籍的员工的事务被选择进行挖掘。在本例中,只有 Mellissa White 在 2006 年之后出版了书籍。

图 3. XML 文档中的上下文选择
XML 文档中的上下文选择的例子

如果一个 XML 关联规则是一个实质条件 X -> Y(类似于关系方法,但是介于两个 XML 复杂节点之间),那么 X 是该规则的主体Y 是它的头部。主体和头部总是根据规则的上下文来定义。类似地,规则的支持度和信任度只根据所定义的上下文来计算。

假设图 3 中事务的上下文被设置为包含所有在 2000 年而不是 2006 年之后出版了图书的员工。图 4 展示了该关联规则的主体和头部的一个例子,其中发现 <publi_what>(值 “Data mining book” 是规则主体)和 <publi_where>(值 “ABC publishing” 是规则头部)之间的一个虚构关系。

图 4. XML 文档中的主体和头部
XML 文档中的主体和头部的例子

XML 关联规则示例

图 5 展示了一个树型表示的示例 XML 文档 (department.xml)。文档包含了学生和员工的研究出版物,包括它们是什么出版物、、是何时何地出版的等方面的详细信息。对于挖掘 XML 关联规则的一般概念的这一讨论,我们假设 <from_date><to_date> 节点是空的,所以此 XML 文档是静态而不是动态的。

图 5. 树型表示的静态 XML 文档
树型表示的静态 XML 文档的例子

下面两个 XML 关联规则使用 图 5 中的文档举例说明了事务、项、上下文、主体和头部。

XML 关联规则示例 1
假设您想要从关于 2005 年之后出版的员工研究出版物的信息中发现关联规则。假设得到下面的规则:

“2005 年之后在 XYZ 杂志发表过作品的员工也在 ABC 领域具有项目。”

图 6 展示了本例中概念的表示:

  • 上下文由所有 <staff> 复杂节点给出,因为需求是挖掘员工出版物而不是学生出版物。
  • 上下文选择是指选择这样一些出版物记录,即其中 <publi_when> 的值大于 2005。
  • 每个 <staff> 节点都是一个事务;<staff> 节点是复杂节点,它还具有其他子节点。
  • 与研究出版物及项目相关的 <staff> 复杂节点的所有简单节点都是项 — 即以下路径中找到的节点:
    • staff/publication/publi_what
    • staff/publication/publi_where
    • staff/publication/publi_when
    • staff/project/name
    • staff/project/domain
    • staff/project/collab
  • 从路径 staff/publication/publi_where 找到的节点形成规则的头部。
  • 从路径 staff/project/domain 找到的节点形成规则的主体。
    图 6. 示例 1 中的 XML 关联规则概念
    示例 1 中的 XML 关联规则概念的可视表示
XML 关联规则示例 2
假设您想要从关于学生和员工研究出版物的信息中发现关联规则。假设得到下面的规则:

“在 ABC 出版社出版图书的学生也与研究项目中的员工合作。”

图 7 展示了本例中的概念:

  • 上下文由所有 <students><staff> 复杂节点给出,因为没有仅挖掘员工出版物或者仅挖掘学生出版物的需求。
  • 没有定义上下文选择,所以将考虑上面定义的整个上下文。
  • 每个 <personal> 复杂节点都是一个事务。
  • 与研究出版物及项目相关的 <student><staff> 复杂节点的所有简单节点都是以下路径中找到的项或节点:
    • student/publication/publi_what
    • student/publication/publi_where
    • student/publication/publi_when
    • staff/publication/publi_what
    • staff/publication/publi_where
    • staff/publication/publi_when
    • staff/project/name
    • staff/project/domain
    • staff/project/collab
  • 路径 student/publication/publi_where 中找到的节点是规则的头部。
  • 路径 staff/project/collab 中找到的节点是规则的主体。
    图 7. 示例 2 中的 XML 关联规则概念
    示例 2 中的 XML 关联规则概念的可视表示

如示例 12 所展示的,在从 XML 文档挖掘关联规则时,事务和项的概念很灵活。

图 5图 6图 7 中的文档示例被认为是静态的,忽略元素 <from_date><to_date>。假设这两个节点不为空,但是会基于 XML 文档的有效期而接收值。例如,每年可以创建一个新版本的 department.xml 文档。2007 年的版本可以具有 <from_date>01/01/2007</from_date><to_date>31/12/2007</to_date>。前面描述的关联规则将只对 2007 年有效。任何更老的规则(发现自以前年度版本的 XML 文档)可能与 2007 年的规则相同,也可能不相同。因此,发现自动态(多版本的) XML 文档的关联规则需要一种特定的方法,以判断它们在后续文档版本的有效性。这些规则叫做动态的,将在下一节中讨论。


动态 XML 关联规则

发现自初始版本动态 XML 文档的关联规则根据连续文档版本之间更改的数量和程度,在实际应用程序中会有波动。通过查看历史更改在初始规则上的影响,可以推断发现自动态 XML 文档的关联规则在一组更改之后的情况。

给定一组发现自初始版本的多版本 XML 文档的 XML 关联规则,任务是确定它们在文档发生很多更改之后将会如何。换句话说,问题是识别哪些初始规则仍然有效,哪些不再有效,或者在更改之后出现了哪些新规则。

此问题的一种解决方法是,在更改之后的文档版本上运行一个关联规则挖掘算法。但是,这种做法在很多情况下效率不高,比如说当版本之间的更改不是很多或者不太重要时,对初始关联规则没有明显的影响。当更改只导致规则的支持度和信任度升高或降低,而不影响总体有效性时,也属于这样的情况。您应该定期运行发现算法,但不是每次都能得到有用的结果。

通过考虑更改对初始有效规则的影响,可以确定一组更改之后的新的有效的 XML 关联规则,无需在最终的版本上重新运行完整的关联规则发现算法。图 8 展示了用于本例的动态 XML 文档。图中描述了在线商店 4 天不同的产品目录。由于购物网站上卖家和买家的活动(添加或删除产品、改变价格、更新详细信息,等等),每天的产品目录都不相同。(查看 图 8 的文本版本。)

图 8. 4 个连续版本的动态 XML 文档
4 个连续版本的动态 XML 文档示例

本例的目的是展示挖掘 XML 动态关联规则的步骤 — 而不是展示如何挖掘初始 XML 规则(更改之前的)。可以使用任何特定于 XML 的关联规则算法从现有文档挖掘初始规则。

步骤 1. 准备

本例中假设这一步在时间 T0 执行:

  • 规则可接受的最小支持度和信任度被设置为 min_sup = 22%、min_conf = 30%、prov_sup = 18% 和 prov_ conf = 20%。
  • 发现两个 XML 关联规则,如下所示:
    • Re = “当有随身听出售时,也有移动电话出售”,支持度 (Re) = 25%,信任度 (Re ) = 33%。
    • Rp = “当有 bbq 工具套件出售时,也有工具箱出售”,支持度 (Rp) = 20%,信任度 (Rp) = 25%。
  • 假设得到上面的规则一共挖掘了 20 个事务。

从上面的结果注意到:

  • Re 是一个有效规则,因为 min_sup < 支持度 (Re),而且 min_conf < 信任度 (Re)。
  • Rp 是一个临时规则,因为 prov_sup < 支持度 (Rp) < min_sup ,而且 prov_conf < 信任度 (Rp) < min_conf。

您想要在 4 天之后检查规则 Re 和 Rp 的有效性,购物网站的产品目录在这期间发生了变化,如 图 8 中所示。

步骤 2. 基于关联规则挖掘版本

下一个任务是为文档 catalogue.xml 构建合并的更改 (consolidated delta),并抽取更改集合 C1(在 T0 和 T1 之间)、C2(在 T1 和 T2 之间)和 C3(在 T2 和 T3 之间)。图 9 展示了 图 8 中 4 个文档版本的合并的更改。(查看 图 9 的文本版本。)关于如何构建合并的更改的更多详细信息,请参见 参考资料

图 9. 图 8 中 XML 文档版本的合并的更改
图 8 中 XML 文档版本的合并的更改

表 1 展示了合并的更改中包含的文档更改。注意,随着特定产品的删除或添加,Product 发生了更改。

表 1. 本例中动态 XML 文档的更改
更改集合版本时间间隔更改摘要
C1T0 到 T1价格 – 被修改
产品 'mobile phone' 被删除
价格 – 被删除
C2T1 到 T2产品 'suitcase' – 被插入
价格 – 被修改
状态 – 被修改
C3T2 到 T3名称 – 被修改
产品 'mobile phone' – 被删除
价格 - 被修改
产品 'bbq set' – 被插入

为了清晰起见,本例中只有 4 个版本。自然,上面所述步骤中合并的更改的使用更加适用于有更多版本时。

步骤 1 中假设,得到 Re 和 Rp 一共在更改之前挖掘了20 个事务 (D)。更改集合 C1、C2 和 C3 包含 4 个事务。更改之后挖掘的新的事务总数 (D') 是 20 + 4 = 24。

有效规则 Re 的新的支持度和信任度值使用 图 10 中的步骤进行计算。(查看 图 10 的文本版本。)

图 10. 有效关联规则新的支持度和信任度的计算
本例中有效关联规则新的支持度和信任度的计算

临时规则 Rp 新的支持度和信任度值使用 图 11中的步骤进行计算。(查看 图 11 的文本版本。)

图 11. 临时关联规则新的支持度和信任度的计算
本例中临时关联规则新的支持度和信任度的计算

图 10图 11 中的结果所示,规则 Re 不再有效,因为它的新支持度 (12.5%) 低于所需的最小支持度,甚至低于临时水平。对规则 Rp 可以观察到相同的行为,它之前是临时的,但是现在有了新的支持度 (16.66%),低于临时支持度水平。但是,规则 Rp 的信任度水平 (23.5%) 高于临时信任度水平。


结束语

本文中的例子很小,没有涵盖实际挖掘应用程序中的所有情况。但是,它展示了如何应用所提议的框架来确定在已挖掘的 XML 文档发生更改之后的基于版本的关联规则。

本文中学习了进行 XML 数据挖掘以从 XML 文档发现关联规则时所使用的几个概念。看到了静态 XML 关联规则的一些例子。还简单了解了一个动态 XML 关联规则的例子,其中底层的 XML 文档是多版本的,一个版本与另一个版本之间都有不定数量的更改。

请期待本系列的第 3 部分,将会探究集群多版本的 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=787686
ArticleTitle=XML 数据挖掘,第 2 部分: 挖掘 XML 关联规则
publish-date=01162012