XML 数据挖掘之挖掘 XML 关联规则-白红宇

XML 数据挖掘之挖掘 XML 关联规则

阅读量：5135 次

发布时间：2019-06-13

本文共 6516 字，大约阅读时间需要 21 分钟。

本系列其他文章

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

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

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

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

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

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

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

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

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

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

展示了一个例子，其中每一个 <staff_member> 节点（这里是 John Brown 和 Mellisa White）都是一个事务，每一个<publi_what>、<publi_where> 和 <publi_when> 节点都是一个项。每个 staff_member 事务都在员工名字下包含一个或多个出版物。每个出版物包含一个 publi_what、publi_where 和 publi_when item。（查看。）

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

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

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

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

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

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

XML 关联规则示例 1

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

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

展示了本例中概念的表示：

上下文由所有 <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 找到的节点形成规则的主体。

XML 关联规则示例 2

您想要从关于学生和员工研究出版物的信息中发现关联规则。假设得到下面的规则：

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

展示了本例中的概念：

上下文由所有 <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 中找到的节点是规则的主体。

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

、和中的文档示例被认为是静态的，忽略元素 <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 文档。图中描述了在线商店 4 天不同的产品目录。由于购物网站上卖家和买家的活动（添加或删除产品、改变价格、更新详细信息，等等），每天的产品目录都不相同。（查看。）

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

本例中假设这一步在时间 T₀ 执行：

规则可接受的最小支持度和信任度被设置为 min_sup = 22%、min_conf = 30%、prov_sup = 18% 和 prov_ conf = 20%。

发现两个 XML 关联规则，如下所示：
- R_e = “当有随身听出售时，也有移动电话出售”，支持度 (R_e) = 25%，信任度 (R_e ) = 33%。
- R_p = “当有 bbq 工具套件出售时，也有工具箱出售”，支持度 (R_p) = 20%，信任度 (R_p) = 25%。

假设得到上面的规则一共挖掘了 20 个事务。

从上面的结果注意到：

R_e 是一个有效规则，因为 min_sup < 支持度 (R_e)，而且 min_conf < 信任度 (R_e)。

R_p 是一个临时规则，因为 prov_sup < 支持度 (R_p) < min_sup ，而且 prov_conf < 信任度 (R_p) < min_conf。

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

下一个任务是为文档 catalogue.xml 构建合并的更改 (consolidated delta)，并抽取更改集合 C₁（在 T₀ 和 T₁ 之间）、C₂（在 T₁ 和 T₂ 之间）和 C₃（在 T₂ 和 T₃ 之间）。展示了中 4 个文档版本的合并的更改。（查看。）关于如何构建合并的更改的更多详细信息，请参见。

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

更改集合	版本时间间隔	更改摘要
C₁	T₀ 到 T₁	价格 – 被修改产品 'mobile phone' 被删除价格 – 被删除
C₂	T₁ 到 T₂	产品 'suitcase' – 被插入价格 – 被修改状态 – 被修改
C₃	T₂ 到 T₃	名称 – 被修改产品 'mobile phone' – 被删除价格 - 被修改产品 'bbq set' – 被插入

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

中假设，得到 R_e 和 R_p 一共在更改之前挖掘了20 个事务 (D)。更改集合 C₁、C₂ 和 C₃ 包含 4 个事务。更改之后挖掘的新的事务总数 (D') 是 20 + 4 = 24。

有效规则 R_e 的新的支持度和信任度值使用中的步骤进行计算。（查看。）

临时规则 R_p 新的支持度和信任度值使用中的步骤进行计算。（查看。）

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

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