CCTreeMiner：一个用于子树挖掘问题的算法

源代码已更新，请点击此处下载新版本。谢谢！ 

 

1. 引言

在本文中，我将介绍一种用于频繁子树挖掘问题的新算法以及该领域的基本概念。该算法名为 CCTreeMiner，于2009年在我的硕士论文中首次提出（用中文撰写，导师为刘力），它能够针对事务型、出现型或混合型阈值类型，挖掘有序或无序诱导子树模式的频繁、闭合或最大模式。主要贡献是：首先，引入了一种根出现匹配，它具有 Apriori 属性，用于基于出现的支持计数；其次，为闭合和最大树模式找到了一个充要条件。

2. 读者群体

本文的读者最好对子树挖掘问题有一些基本概念，至少熟悉树结构、子树、闭合子树、最大子树、支持度、前序表示、有序树等概念。

我尽力使本文易于阅读，但子树挖掘本身可能不是一个非常容易的问题，而且英语不是我的母语。因此，对于可能造成的任何困扰，我深表歉意：)

3. 背景

3.1 相关定义

以下是本文相关的一些重要概念。请注意，它们是非正式的，但对于有背景的人来说是提醒，对于没有背景的人来说是快速入门。

树: 树是无环连通图，由通过边连接的一组节点（或顶点）组成。 T主要有两种：有根树和无根树。有根树是结构良好的，即它包含一个唯一的根节点，该节点没有父节点。本文重点关注有根树。有关如何将无根树转换为（唯一的）有根树，请参见 Ruckert et al. [4], Nijssen et al. [3], and Chi et al. [1, 2] 。

父子关系: 如果存在一条从节点p开始指向节点c的边，则称节点p是节点c的父节点。

兄弟节点: 一个父节点可以有零个到多个子节点，同一父节点的所有子节点 构成兄弟节点集。

扇出: 一个节点的 扇出（或 度）是其子节点的数量。

叶子: 没有任何子节点的节点称为叶子。显然，叶子的度为零。

路径: 两个节点之间的路径是连接它们的边的集合。由于树不包含环，因此这条路径是唯一的。

祖先-后代关系: 一个节点的祖先是从根节点开始到该节点路径上的所有节点（不包括它本身），而一个节点的后代是那些以它为祖先的节点。

树的大小: 一棵树的大小是它包含的节点数。

树的深度: 一棵树的深度是从根节点开始的最长路径上的边数。

节点的深度: 节点的深度是根节点和该节点之间的边数。

有序和最右侧: 如果每组兄弟节点之间存在预定义的顺序，则称一棵树是有序的，即树中每个父节点的每个子节点相对于其兄弟节点都有一个预定义的位置，我们称位于最右侧的子节点为其父节点的最右侧子节点。相反，对于无序树，兄弟节点的位置无关紧要。

最右侧路径: 在有序树中，一个节点的最右侧路径（如果它不是叶子）是指向其最右侧子节点的路径，这条最右侧路径的叶子被称为该节点的最右侧叶子。

最右侧 叶子: 对于一棵树而言，其最右侧叶子被定义为其根节点的最右侧叶子。

树的前序字符串表示 (参见 Luccio et al. [9, 10]): 这种表示方法将一棵树映射到一个唯一的编码字符串。规则是，遵循前序遍历，在向前遍历时记录树的每个节点，并在回溯时标记每条边。

 

无序树的规范表示：对于要进行前序表示的无序树：任何兄弟节点之间的位置可能不同，结果是，具有不同位置的相同兄弟节点集可能为同一无序树生成不同的前序字符串表示。为了解决这个问题，我们需要选择一个唯一的表示来表示一个无序树。例如，我们可以使用字典序最大/最小的前序字符串来表示一个无序树。这种形式化的表示称为规范形式（参见Chi et al. [1]）。

 

3.2 频繁子树挖掘——问题

3.2.1 挖掘对象：频繁、闭合或最大

频繁子树挖掘问题通常可以表述为：给定一个树（也称为事务）数据库Tdb和一组约束（通常是最小出现次数），返回一个集合F，其中包含Tdb中所有满足这些约束的子树模式。广泛应用的约束是频率，定义如下。

 

频繁：一个子树的支持度（接下来讨论）是根据给定约束计算的值。如果一个子树模式的支持度满足约束，我们称其为频繁的。

频繁子树挖掘任务存在一些问题（参见Chi et al. [11]），因此有时会应用以下方法代替挖掘频繁子树。

 

闭合：如果一个频繁子树的任何超树都没有与它相同的支持度，则称该频繁子树是闭合的。

最大：如果一个频繁子树的任何超树都不是频繁的，则称该频繁子树是最大的。

为了区分Tdb中的树（事务）和F中的频繁子树（它们都是树），我们将事务称为文本树模式（简称文本树或文本模式），将频繁子树称为频繁树模式（频繁模式）。我们将大小为n的模式表示为n-模式。

3.2.2 子树类型

在继续之前，应解释不同类型的子树，一般而言，有三种

自下而上子树 (参见 Valiente [5]):

如果 Ts 是 T 的此类子树，则

1. Ts 的根 Rts 必须是 T 的节点 Nt；

2. 如果 T 中 Nt 有后代，则 Ts 中 Rts 将有相同的后代，不多不少。

3. 最后，Nt 的后代之间的所有父子关系也保留在 Ts 中 Rts 的后代中。

诱导子树 (参见 Chi [6]):

如果 Ts 是 T 的此类子树，则

1. Ts 的根 Rts 必须是 T 的节点 Nt；

2. 如果 Ts 中 Rts 的两个后代之间存在父子关系，则 T 中 Nt 的两个后代之间也必须存在相同的关系。

嵌入子树:

如果 Ts 是 T 的此类子树，则

1. Ts 的根 Rts 必须是 T 的节点 Nt；

2. 如果 Ts 中 Rts 的两个后代之间存在祖先-后代关系，则 T 中 Nt 的两个后代之间也必须存在相同的关系。

根据它们的定义，不难理解它们之间存在偏序关系：

自下而上子树意味着它也是一个诱导子树，而诱导子树意味着

它也是一个嵌入子树，但反过来可能不成立。

 

3.2.3 支持度定义

一般来说，有三种

基于事务的支持度：这种支持度类型提供事务级别阈值 s，并要求当且仅当子树在给定数据库中至少出现 s 个不同的事务时，该子树才是频繁的。

基于出现次数的支持度：在这种情况下，阈值是子树在给定数据库中出现的次数。

混合支持度：这种支持度类型是上述两种的结合：当且仅当子树模式满足基于事务的阈值和基于出现次数的阈值时，它才是频繁的。

3.2.4 基于出现次数的支持度的问题

根据向下闭包引理（也称为Apriori属性，参见Agrawal & Srikant [7]），频繁模式的每个子模式也是频繁的。然而，这在子树模式中不成立。

1. Apriori 属性不成立。

在以下示例中，模式A^只出现一次，但其超模式AB^^出现了3次：[0, 1]、[0, 1]和[0, 3]；其超模式AB^B^^也出现了3次：[0, 1, 2]、[0, 1, 3]和[0, 2, 3]。因此，Apriori属性被打破，该属性指出模式的支持度应大于或等于其任何超模式的支持度。

子树挖掘的主要问题之一是可能出现的候选子树模式数量的组合爆炸，我们必须找到巧妙的方法（几乎都是关于剪枝的）来减少枚举空间。

显然，如果 Apriori（反单调）属性失效，问题会更大，这意味着我们无法使用它进行剪枝。

 

2. 出现次数的计数问题。

不难看出，在这种情况下，超模式的数量是阶乘复杂度的。通常来说，如果算法的复杂度大于 O (10!)，您就必须仔细考虑其可行性。

3.2.5 根匹配出现

定义：模式P在树T中的任意两次出现都不应具有相同的根，对于那些具有相同根的出现，只有一个可以对基于根出现的支持度做出贡献。遵循此限制，向下闭包引理将得到保留。

到目前为止，基于我有限的知识和信息，我不知道是否还有其他人已经为基于出现的支持度定义了这样的计数规则。因此，目前，我将其描述为本文中我的工作贡献。

在下文中，当我们说到“出现”时，我们指的是基于根的出现。

4. CCTreeMiner

CC 代表连接与组合。

4.1 机制

CCTreeMiner 受到以下观察的启发

1. 任何根节点的扇出为n的有根树模式都可以分解为n个不同的子树模式，每个模式具有相同的根，且扇出为1。

2. 任何此类分解后的子模式，如果大小大于2，可以进一步分解为两个子模式：一个以相同根为根的2-模式，其唯一子节点为叶子；以及一个以该单个子节点为根的子树模式。

3. 递归重复步骤1和2，最终以自上而下的方式，原始模式将被分解为一组2-模式。

按照相反的操作，任何大于或等于2的树模式都可以通过自下而上的方式由一组2-模式构建。这是 CCTreeMiner 背后的主要思想。以下是算法使用的一些定义。

给定树数据库Tdb和阈值限制

F：频繁子树模式的集合。

Fn：频繁n-模式的集合。

F2Di：频繁2-模式的集合，其中每个模式在深度i处至少出现一次。

FDi：频繁模式的集合，其中每个模式在深度i处至少出现一次。

RDi：频繁模式的集合，其中每个模式在深度i处至少出现一次，且其根节点的扇出为1。

在下文中，当我们说深度为i的模式时，我们的意思是该模式在i处至少出现一次，这进一步意味着该出现模式的根节点的深度为i。

4.2 伪代码

4.3 超模式扩展

在CCTreeMiner中，有两种扩展超模式的方法：组合和连接。

4.3.1 组合

给定一个共享相同根的n-模式Px和一个m-模式Py，可以通过组合Px和Py的根来生成一个大小为n + m – 1的新模式Pxy。

在深度 i 执行组合之前需要准备的材料是 RDi，它作为一个种子集合，用于生成所有在 i 处出现过的频繁模式。枚举策略是深度优先：一个频繁模式将进一步扩展，直到其所有新发现的超模式都已完全扩展。换句话说，如果发现一个新的频繁模式 f，则 f 将与 RDi 中的每个项组合，以形成可能的新模式。

我不会在这里正式证明它，但：首先，在深度i处任何大于2的模式都是通过根将RDi中的某些模式组合而成的，这意味着它可以通过深度遍历RDi来生成；其次，对非频繁模式进行剪枝，这意味着在任何非频繁模式处停止进一步的遍历迭代，并防止无限遍历；第三，如果在深度i处一个模式是非频繁的，那么它在深度i处的所有超模式也都是非频繁的，因此剪枝它不会让我们丢失任何频繁模式。因此，在深度i处的组合可以生成所有在深度i处至少出现一次的频繁模式，并且所有频繁子树模式都可以通过CCTreeMiner生成。

4.3.2 连接

给定一个叶子为 l 的 2-模式 P2 和一个根为 l 的 n-模式 P，可以通过连接 P2 的叶子和 P 的根来生成一个新的 (n + 1)-模式 Pnew。

连接所需准备的材料是 F2Di 和 FDi+1。连接方法将枚举 F2Di 中每个频繁的 2-模式与 FDi+1 中的频繁模式，以生成所有可能的超模式并计算它们的支撑度。事实上，通过在深度 i 的所有频繁 2-模式和在深度 i+1 的所有频繁模式之间进行枚举，将生成 RDi，作为下一轮组合迭代的输入。

引理 1：一个频繁模式 P 是闭合的，当且仅当至少存在一个与其不匹配的出现。

引理 1 是显而易见的；它实际上是闭合子树的定义。问题是如何在算法中满足这个条件。方法如下

引理 1.1：在深度 i 处连接后，对于模式 T，如果 T 没有出现匹配，并且 T 在深度 i + 1 处有出现，则 T 是闭合的。

引理 1.2：在深度 i 处连接后，对于闭合模式 M，如果其在 i 以上（不包含 i）的出现次数小于支持度阈值，则 M 是最大的。

以自下而上的方式递归地进行组合和连接，如果一个频繁模式有任何超模式（无论是出现匹配的还是非出现匹配但频繁的），它应该已经在之前的组合或连接步骤中被发现；如果不是，则该模式应分别是闭合的或最大的（我在我的中文论文中已经证明了这一点，希望没有错误）。如果目标是闭合或最大模式，CCTreeMiner 中使用了引理 1.1 和 1.2。

4.4 剪枝

4.4.1 频繁子树挖掘任务的剪枝

如前所述，Tdb 以自下而上的方式扫描，从倒数第二个深度一直到0。在此过程中，任何未扩展的模式只有在找到其第一次（最深处）出现时才会被生成并进行频率测试。算法运行时，生成的任何模式的出现分为两组，根据 CurrentDepth 的值进行区分：一组大于或等于 CurrentDepth，另一组不大于或不等于。后一组（比 CurrentDepth 更深的出现集）在生成任何新的超模式时将不予考虑（新意味着它在 CurrentDepth 以下没有任何出现，否则它应该已经被生成，因此不应被称为新模式），因为遵循组合步骤中的深度优先枚举，它们都应该已经生成。因此，对于任何要生成的新模式，其支持度的上限由前一组的大小（大于或等于 CurrentDepth 的出现次数）决定，这个大小被称为 RemainingSupport。此外，当给定 CurrentDepth 并且对于任何频繁模式，如果其剩余支持度小于阈值，则可以对其进行剪枝。

4.4.2 闭合和/或最大子树挖掘任务的剪枝

如果一个频繁模式具有出现匹配，则无法扩展它来生成任何闭合超模式。当情况是闭合或最大模式时，使用此策略进行剪枝。

5. 实验

到目前为止还没有。我不是全职研究员，我利用业余时间思考并编写 CCTreeMiner 的代码。我一直无法将 CCTreeMiner 与其他算法进行比较，因为学习它们和研究代码需要大量时间。

无论如何，提供了一个森林（Tdb）生成器，您可以进行实验。如果您能向我展示您的结果（如果有的话），我将不胜感激。我将很快讨论森林生成器以及如何使用代码。

6. 结论

本文旨在解释 CCTreeMiner 的机制，这是一种处理子树挖掘问题的方法。它首先介绍了该领域的相关概念，然后是 CCTreeMiner 的独特材料。它解释了基本思想、枚举方法和剪枝策略。它讨论了闭合子树和最大子树的充分必要条件以及如何应用它们。此外，还引入了基于根的出现，这使得基于出现的支持度计数变得可行。

6.1 其他优点

该算法还有其他优点

首先，CCTreeMiner 只扫描一次Tdb，并且不需要将整个数据库加载到内存中。

其次，对于任何要生成以进行支持度测试的模式，它必须在Tdb中至少出现一次。

第三，对于每一轮迭代，新模式的增加量不受1的限制，这与大多数其他方法不同。

最后，CCTreeMiner 不是解决特定子树挖掘问题的特定算法，而是一个框架。除了诱导子树（本文的重点）之外，它还可以（至少我现在非常确定）挖掘自下而上和嵌入式子树类型。这三种类型都可以针对事务型、出现型（基于根）或混合型阈值类型的频繁、闭合或最大有序或无序子树模式。挖掘自下而上和嵌入式子树的可能性将在下一节讨论。

7. 接下来做什么？

正如我所提到的，CCTreeMiner 是一个框架。但如果它只能处理诱导子树，那它的声明就会显得苍白无力。在本节中，我将讨论挖掘自下而上和嵌入子树类型的可行性。

7.1 自底向上子树

当且仅当其前序表示的索引数量等于其文本树中根的后代数量时，一个出现才是自下而上的。对于自下而上子树模式，其所有出现都应该是自下而上的。基于 CCTreeMiner 的机制应用这些检查并不难。由于自下而上树是一种诱导树，因此它们的剪枝策略是相同的。

7.2 嵌入子树

在嵌入子树类型的情况下，向下闭包引理对于根出现匹配也是可行的。至于组合，作用是相同的。但对于连接，原始的父子关系应扩展为祖先-后代关系：频繁2-模式的出现的叶子可以连接到它的任何后代。要知道一个节点是否是后代，我们可以使用范围（详情请参见Zaki [8]）。

所以，接下来我将尝试重构代码，并将自下而上和嵌入式添加到工具箱中。

8. 使用代码

CCTreeMiner 的输入包含两部分：一组参数和一个树数据库。

所需的参数包括子树类型、支持度类型、排序和阈值。我已经将这些参数封装到一个类中，我相信使用它不会有太多问题，但您肯定应该事先了解它们的含义。

输入数据库是文本树（或事务）的集合，它们应该采用 CCTreeMiner 所要求的正确前序表示。您的事务类和节点类应分别实现 ITextTree 接口和 ITreeNode 接口。

// A set of ITextTrees with ITreeNodes as vertices (preorder represented) is what needed by// CCTreeMiner.

public interface ITreeNode : IComparable<ITreeNode>
{
    //...
}

public interface ITextTree
{
    //...
}

我写了一个演示，展示了如何操作。在这个演示中，我的事务实例是从文本文件转换而来的，其中每一行都是文本树的前序字符串表示，每个节点只是一个字母。但是，如果您的领域问题比字母更复杂，那么您将不得不开发自己的转换器，因为无法预测您特定的领域问题（没有水晶球）。为了更清楚地说明，转换器应该能够构建您的事务中每个节点之间正确的先行关系。

public class MyTree : ITextTree
{ 
    // ...
}

public class MyTreeNode : ITreeNode
{
    //...
}

使用代码很简单

List<ITextTree> myForest = new List<ITextTree>();

// Add trees (transactions) to your forest. 

CCTreeMiner ccTreeMiner = new CCTreeMiner();
MiningParams param = new MiningParams(/* Your parameters here. */);

ccTreeMiner.Mine(myForest, param);

// Wait and check the results if every thing went well.

参考文献

[1] Chi, Y., Yang, Y., Muntz, R. R.: 使用规范形式挖掘频繁有根树和自由树，UCLA 计算机科学系技术报告 CSD-TR No. 030043。

[2] Chi, Y., Yang, Y., Muntz, R. R.: HybridTreeMiner: 一种利用规范形式挖掘频繁有根树和自由树的高效算法，第16届科学和统计数据库管理国际会议 (SSDBM'04)，2004年6月。

[3] Nijssen, S., Kok, J. N.: 频繁结构挖掘的快速启动可以改变一切，2004年国际知识发现与数据挖掘会议 (SIGKDD'04) 论文集，2004年8月。

[4] Ruckert, U., Kramer, S.: 图数据中的频繁自由树发现，ACM 应用计算研讨会数据挖掘专题 (SAC'04)，2004年。

[5] Valiente, G.: 树和图上的算法，Springer，2002年。

[6] Chi, Y., S. Nijssen, R. R. Muntz, J. N. Kok / 频繁子树挖掘概述。

[7] Agrawal, R., Srikant, R.: 挖掘顺序模式。在第11届数据工程国际会议（台湾台北，1995年3月6-10日）论文集上发表的论文

[8] Zaki, M. J.: 在森林中高效挖掘频繁树，2002年国际知识发现与数据挖掘会议 (SIGKDD'02) 论文集，2002年7月。

[9] Luccio, F., Enriquez, A. M., Rieumont, P. O., Pagli, L.: 次线性时间精确有根子树匹配，技术报告 TR-01-14，比萨大学，2001年。

[10] Luccio, F., Enriquez, A. M., Rieumont, P. O., Pagli, L.: 无序带标签树的自下而上子树同构，技术报告 TR-04-13，比萨大学，2004年。

[11] Chi, Y., Yang, Y., Xia, Y., Muntz, R. R.: CMTreeMiner: 挖掘闭合和最大频繁子树，第八届亚太知识发现与数据挖掘会议 (PAKDD'04)，2004年5月。

历史

1. 首次发布：2014年4月9日。