XML关联规则扩展

1 概述

相对于关系数据库关联规则研究的日趋成熟，XML关联规则的研究则是一个新兴的热点。由于XML数据库结构的特殊性，XML关联规则的挖掘面临着更多的挑战，包括复杂的层次结构、节点在位置上的上下文关系等。

现有研究将子树作为XML关联规则的构成基础，频繁子树的挖掘则是获取XML关联规则的前提。频繁子树的挖掘过程可以分为两个过程，首先在有序的XML文档树中确定所有的频繁路径表达式，用于定位可能的频繁子树；然后以频繁路径表达式定位的节点为根节点，通过节点扩展的方法逐步生成频繁子树。

和经典关联规则相似，XML关联规则同样可以利用Apriori特性从挖掘的频繁子树中构造。除此之外，研究人员还研究了可定制的规则挖掘方法。例如通过扩展XQuery语句实现XML关联规则的挖掘；利用一种称为HoPS的分层数据结构避免挖掘过程中的多次文档扫描；使用模板来定义用户感兴趣的XML关联规则的方法，通过模板中变量的设置使挖掘的目标更具普遍性。

还有其它的一些挖掘方法，总的来说上述XML关联规则及其挖掘方法存在的一个共同问题是：仅限于挖掘单棵子树内部、确定的节点或子树间的关联关则，即要求规则的前、后件必须不重复的包含于同一棵子树中，并以该子树的统计计数作为度量规则兴趣度的基础。例如图1中，关联规则//Location/SB=>//Item/Fuel的前、后件都位于由路径表达式/AirForce/order确定的子树中(如图2(a)所示)。

这种方式下刻画的规则是十分有限的，更为普遍的是形如图2(b)所示的涉及多子树的XML关联规则。该规则的不同之处在于没有不重复包含规则前、后件的子树，作为度量规则兴趣度的前提。这也是现有XML关联规则挖掘方法所无法处理的。

针对上述问题，本文在单子树的XML关联规则的基础上，介绍一种一般化的、以查询模式为基础的扩展关联规则(eXtensible Association Rule, XAR)的刻画方法，通过该方法不仅可以描述单子树的XML关联规则，更能够解决多子树的XML关联规则的刻画问题，使关联规则能够涵盖数据之间更多、更有意义的关联关系。

2 XML查询模式

在XML数据库中，现有的XML关联规则挖掘方法利用统计出的规则前、后件所属的同一子树在XML数据库中出现次数，来作为度量规则兴趣度的基础。对于多子树的关联规则而言，由于不存在这样的一个基础，因此需要研究新的度量方法。

由XML查询表达式的定义可知，给定XML文档上的一个查询的查询结果是该文档中由路径表达式定位的、并且满足过滤条件的文档子树。令XQm(obj): con表示XML文档的一种查询模式，其中查询对象obj是路径表达式p₁, p₂, …, p_n的集合，查询条件con是选择运算r(aθb)的非空有限集合，对于查询条件中的任一选择运算r(aθb)，r对应于某路径表达式p_i，a对应于p_i的某一子表达式，b对应于相应的节点变量或常量。同一文档子树上的选择运算是逻辑上的“与”关系，不同子树必须能够通过各自的某个节点对应的同一变量或常量等值连接。

例1：建立在图1所示文档上的符合要求的XML查询模式。

XQm₁(p₁): p₁(//Location = SB)；XQm₂(p₁): p₁(//Item = Fuel)；

XQm₃(p₁): p₁(//Location = x), p₁(//Item = Fuel)；

XQm₄(p₂): p₂(//Location = x), p₂(//Aircraft = SSA)；

XQm₅(p₁, p₂): p₁(//Location = x), p₁(//Item = Fuel), p₂(//Location = x), p₂(//Aircraft = SSA)。

其中，p₁和p₂分别对应于路径表达式/AirForce/order和/AirForce/garrison。

在查询模式的连接上，关系查询模式涉及的关系实例之间只能通过属性实现等值连接，而对于XML查询模式，子树间的连接更加灵活，可以通过更低一层的子树或者叶节点来实现。

例2：例1中的XML查询模式XQm₃和XQm₄可以通过相同的子树//Location实现连接，XQm₅即为该连接处理的结果。

给定XML文档t上查询模式XQm的支持度的计算可以表示为Sup(XQm) = |XQm^A| / N，其中N的计算如下：|obj| = 1时，令p表示定位待查询子树的路径表达式，N = |{p(t)}|，其中{p(t)}表示文档t中所有以路径表达式p定位的文档子树的集合；|obj| > 1时，令p₁, p₂, …, p_n表示对应的路径表达式，则N = Max(|{p₁(t)}|, …, |{p_n(t)}|)。

例3：例1中的XML查询模式XQm₁-XQm₅的支持度分别为Sup(XQm₁) = 0.25，Sup(XQm₂) = 0.75，Sup(XQm₃) = 0.75，Sup(XQm₄) = 0.8，Sup(XQm₅) = 0.75。

同频繁项集相似，支持度不低于最小支持度阈值s_min的查询模式称为频繁查询模式，简称为频繁模式。

3 扩展XML关联规则

扩展关联规则由上述查询模式构成。若给定查询模式XQm和XQm'可以连接，则存在形如XQm=>XQm'的扩展关联规则。

支持度与置信度同样也是扩展关联规则的两个重要度量指标。对于规则XQm=>XQm'，其支持度s = Sup(XQm∪XQm')，置信度c = Sup(XQm∪XQm')/Sup(XQm)。同样，称该扩展关联规则是有意义的，当其支持度和置信度分别不低于指定的最小支持度阈值和最小置信度阈值，即s≥s_min并且c≥c_min。

上述定义要求构成规则的两个查询模式可以连接的原因在于实现多子树情况下XAR的支持度Sup(XQm₁∪XQm₂)的计算。显然，如果XQm₁和XQm₂涉及有相同的子树，则通过该子树上的与操作可以实现查询模式的连接；如果XQm₁和XQm₂涉及不同的子树，而两个子树中存在可以连接的变量，则查询模式亦可以通过该变量实现连接。

反映在实际的XML文档中，上述连接的结果是可以明确界定的公共子树，即为计算Sup(XQm₁∪XQm₂)的基础。除此之外，该支持度是无法计算的，这样的规则即便是得到了，由于其兴趣度的无法度量、缺乏基本的理论依据，因而也就是不可信的。

以此为基础，通过查询模式就可以方便的刻画各种形式的XML关联规则，拓展关联规则的刻画范围。下面结合1给出相应的示例。

例4：从图1可以得到以下部分的扩展关联规则：

①同一子树中的关联规则

XQm(/AirForce/order): /AirForce/order(//Location = SB) => XQm(/AirForce/order): /AirForce/order(//Item = Fuel) (s = 0.25, c = 1)

②不同子树中的关联规则

XQm(/AirForce/garrison): /AirForce/garrison(//Location = x), /AirForce/garrison (//Aircraft = SSA) => XQm(/AirForce/order): /AirForce/order (//Location = x), /AirForce /order (//Item = Fuel) (s = 0.75, c = 0.94)。

除了子树这一级别的粒度外，通过查询模式还可以进一步对规则的前、后件进行扩展，如森林。

从上述示例可以清晰看到扩展关联规则能够涵盖对经典关联规则的刻画，并且极大的对其进行了扩展，使得通过查询模式刻画的关联规则能够更加灵活的反映XML数据库中信息之间潜在的联系。