CCTreeMiner：子树挖掘问题的算法 V2
本文是我之前的文章《CCTreeMiner：子树挖掘问题的算法》的续篇。我修复了一些错误并进行了一些改进。同时，我还想进一步阐述这个算法。
前进
距离上一篇文章发布已经过去一年了，我从一开始就知道它可能包含错误，但令人震惊的是错误竟然如此之多。
现在，在中国春节期间，利用空闲时间，我对代码进行了重构。希望一切顺利。
以下是此新版本的一些截图。如果您在该领域有一定的经验，我想您不会对这些图片所要表达的内容感到陌生。无论如何，请下载并运行它。
我建议您对子树挖掘有一定的基本了解。如果不是，这里有一个简要描述：
给定一组有限的树，找出那些*相当*频繁出现的子树。
例如，在上图所示的树中，子树（模式）A,B,^ 在给定的树中出现了许多次（这里可以看到 5 次）；子树挖掘就是找出这样的子树。
然而，其中涉及许多问题。
对于本文，如果您非常了解相关术语，例如频繁、闭合、最大、诱导、嵌入、前序表示、文本树、模式树、有序树、规范形式等等，那将更好。否则，您可能想阅读我之前的文章，特别是引用的参考文献。我还找到了一本对这个问题进行了详细讨论的优秀书籍，名为《数据挖掘复杂结构》（Mining of Data with Complex Structures），作者是 Fedja Hadzic、Henry Tan 和 Tharam S. Dillon。
*****************************
现在我们开始。
为什么我们需要频繁子树挖掘？
以下内容摘自维基百科。
频繁子树挖掘有用的领域往往涉及数据实体之间复杂的关联：例如，XML 文档的分析通常需要频繁子树挖掘。另一个有用的领域是 Web 使用挖掘问题：由于用户访问网站时的行为可以以多种不同的方式记录和分类，因此需要使用频繁子树挖掘来分析复杂的树形数据库。其他频繁子树挖掘有用的领域包括计算生物学、RNA 结构分析、模式识别、生物信息学以及 KEGG GLYCAN 数据库的分析。
接下来，我将继续我之前的文章，并进一步解释 CCTreeMiner 算法背后的思想。
模式生成
如何生成新模式？
1. 除了 1P 或 2P 之外，每个 PatternTree 都是通过连接或组合由其父模式创建的。
2. 1-模式和 2-模式是通过扫描输入事务数据库生成的。
频繁性判断
给定一种支持类型，如何确定一个模式是否频繁？
首先，计算事务支持和根节点出现支持。
对于 Frequent-1s 和 Frequent-2s，它们的根节点出现次数和事务出现次数是通过扫描输入事务数据库计算的。对于任何大于 2 的模式，在连接（连接或组合）其父模式时计算这两种支持。
其次，根据支持类型评估频率。如果一个模式是频繁的，那么
- 事务支持：其事务出现次数（事务支持）应大于或等于事务阈值。
- 根节点出现支持：其根节点出现次数（根节点出现支持）应大于或等于根节点出现阈值。
- 混合支持：两种出现次数都应大于或等于各自的阈值。
闭合与最大模式判断
根据定义，一个模式的闭合属性取决于给定的支持类型和涉及的两种匹配。请参见下表（注意：出现匹配意味着事务匹配）
|
支持类型
|
具有根节点出现匹配
|
具有事务匹配
|
闭合？
|
|
事务
|
是
|
--
|
否
|
|
|
否
|
是
|
否
|
|
|
--
|
否
|
是
|
|
根节点出现
|
是
|
--
|
否
|
|
|
否
|
是
|
是
|
|
|
--
|
否
|
是
|
|
混合
|
是
|
--
|
否
|
|
|
否
|
是
|
否
|
|
|
--
|
否
|
是
|
因此，问题在于找出模式是否具有任何事务匹配或根节点出现匹配。
对于 Frequent-1 模式，它们的事务匹配或根节点出现匹配将针对其父模式（至少一个，最多两个）从 Frequent-2 集合中进行评估：
- 如果没有频繁的父 2-模式，则它是最大的，否则它不是最大的。
- 事务支持：如果在父 2-模式集合中没有事务匹配，则它是闭合的，否则它不是闭合的。
- 根节点出现支持：如果在父 2-模式集合中没有出现匹配，则它是闭合的，否则它不是闭合的。
- 混合支持：它不应有任何来自父 2-模式集合的匹配才能被认为是闭合的，如果有，则不是闭合的。
如何确定一个频繁模式（大于 1）不是闭合的或不是最大的？
对于任何大于 1 的模式，当它与另一个父模式通过连接或组合连接以生成子模式（一个父模式）时，
如果子模式不频繁，则无法确定任何内容。
否则，如果这个子模式是频繁的，那么需要进一步进行两项操作：
- 首先，父模式至少有一个频繁的父模式，并且它们两者都不能是最大的。
- 其次，应根据所需的支持类型，检查它们与子模式的事务匹配和出现匹配，以确定它们是否不闭合。
- 如果支持类型是事务支持，并且它具有任何匹配（事务匹配或根节点出现匹配），那么它不是闭合的。
- 如果支持类型是根节点出现支持，并且它具有根节点出现匹配，那么它不是闭合的。
- 如果支持类型是混合支持，那么任何匹配都会使其不闭合。
如何确定一个模式*是*闭合的？
对于一个模式，我们可以确保它是闭合的，如果没有任何相关的匹配（参见上表）可能被发现，更具体地说，在 CCTreeMiner 中：
- 对于根节点出现匹配，如果一个模式在深度 *i+1* 处至少有一个根节点出现，并且在深度 *i* 处进行了连接操作后，如果其闭合属性仍然未知（换句话说，没有检测到根节点出现匹配），那么将无法进一步发现任何根节点出现匹配。
- 对于事务匹配，当一个模式被生成以形成一个父模式时，如果它们具有相同的事务支持，则确定匹配。
如何确定一个模式*是*最大的？
首先，对于一个模式，我们可以确保它是最大的，如果无法进一步生成任何频繁的父模式，但如何做到呢？
在 CCTreeMiner 的机制下，并且在深度 *i* 的每次连接之后，对于一个在深度 *i* 处没有找到父模式的闭合模式：
- 如果支持类型是事务支持，并且其在深度 *i* 以上（不包括 *i*）的事务出现次数小于阈值，那么它是最大的。
- 如果支持类型是出现支持，并且其在深度 *i* 以上（不包括 *i*）的根节点出现次数小于阈值，那么它是最大的。
- 如果支持类型是混合支持，并且其在深度 *i* 以上（不包括 *i*）的根节点出现次数小于阈值，那么它是最大的。
挖掘闭合或最大模式时存在一个问题
然而，在闭合或最大模式的情况下存在一个问题。
假设我们在组合后得到两个根节点出现匹配的模式：**F** 和 **F'**，其中 **F'** 是 **F** 的父模式；假设 **F'** 是最大的，而 **F** 除了 **F'** 之外没有频繁的父模式。参见下文：
**F** : A,B,C,^,^,D,^,^
**F'**: A,B,C,^,^,D,E,^,^,^
根据 CCTreeMiner 的扩展机制，**F'** 是通过 A,B,C,^,^,^ 和 A,D,E,^,^,^ 的组合生成的，而 **F** 是通过 A,B,C,^,^,^ 和 A,D,^,^ 的组合生成的；
**F** 和 **F'** 都无法进一步扩展。这对 **F'** 来说没问题，如果需要，它将被标记为闭合和最大，因为它没有可以由它生成的父匹配模式或父频繁模式。麻烦的是，**F** 在相同条件下也将被标记为闭合和最大，这是错误的。
同样，这个缺陷是由算法内部的父模式扩展机制（在具有相同深度出现次数的频繁模式之间进行枚举）引入的。通过组合生成父模式的方式不是唯一的，任何两个子模式都可以，但只选择一对进行匹配测试。
为了弥补这一点，必须在每次组合步骤后添加一个额外的操作，用于检查新组合模式之间的祖先-后代关系，以防止此错误，因此引入了一个新问题，即确定树模式之间的祖先-后代关系实际上是子树同构问题。
子树同构
问题定义：给定树 **S** 和 **L**，找到 **L** 的一个子树，该子树与 **S** 同构，或确定不存在这样的子树。
老实说，我目前不知道这个问题（再次强调，我是在业余时间研究）最高效的算法，部分原因在于涉及的数据结构（CCTreeMiner 采用前序表示作为模式树的形式），部分原因是我无法在技术论坛上找到任何有价值的信息（也许这不是我们经常遇到的常见问题）。我根据对问题的观察实现了一个子树同构算法。此算法不保证正确性，但我也认为如果它不正确，我将感到非常惊讶。
该算法以递归方式完成工作，以下是简要描述：
算法的输入是两棵树的前序列表和回溯符号。然后，它以并行方式递归枚举两棵树，以检查并尝试在与较小的树一致的序列中虚拟地构建匹配节点的列表，直到找到完整的匹配或达到不可能存在同构的条件。好吧，英语不是我的母语，我很抱歉这个含糊的描述，请阅读代码。相关类是*SubtreeIsomorphism*。
我认为这个递归算法肯定已经被某人介绍过了，只是我不知道它的名字。有人能告诉我吗？
此方法的 time complexity 为 O(Size(**S**) * Size(**L**))。这远非理想，等有时间我会改进它。无论如何，它现在能用了。
剪枝
如何剪枝那些无法进一步生成父频繁模式的模式？
在深度 *i* 连接之后，对于任何在深度 *i*+1 处连接的模式，如果其在深度 *i*+1 以上（需要 *i*+1）的支持（根据给定的支持类型为事务支持、根节点出现支持或两者兼有）不满足阈值，那么它可以被移除，因为深度 *i* 以下的出现次数无法进一步生成（为父模式的支持做出贡献），而深度 *i* 及以上的部分不足以构成任何父频繁模式。算法的机制保证了这一点。
在闭合或最大模式且不想要频繁模式时如何剪枝？
有时，挖掘完整的频繁模式集是不可行的，但挖掘闭合或最大模式则可行。我将稍后讨论原因。
以下剪枝方法是我迄今为止能想到的。
在任何给定深度的每次组合回合的输入是仅包含以下类型的模式的集合：其根节点有单个子节点，并且它在该深度必须有一个出现。我将这些模式称为种子（因为大于 2 且在该深度至少出现一次的所有频繁模式都可以通过组合某些种子模式的根节点来生成）。
种子模式的根节点出现由其根节点标识，然而（由于树的性质）它可能有一个或多个最右出现，由其最右叶子（或叶子）标识。
剪枝策略：如果一个种子模式具有任何根节点出现匹配，并且它们的最右出现次数之间的差值小于阈值，那么它可以被移除。
顺便说一句，由最右叶子标识的出现可以共享同一个根节点，从而破坏了 Apriori 性质。这就是我引入基于根节点的出现定义的原因。
再次，为什么有时我们需要闭合或最大模式而不是频繁模式？
正如我在之前的文章中所述，当文本树的大小变得过大时，挖掘完整的频繁模式集是不可行的。
让我们看看一个文本树中可能包含多少诱导子树模式。
在这里，我们用 **r** 作为根节点表示一个树 **Tr**。
对于一个非空文本树 **Tr**，
如果 **Tr** 只有一个节点，则子树的上界（最大数量）为 1；
如果 **Tr** 有多个节点，假设 **r** 有 *n* 个子节点（表示为 **r**i，*i* = 0, 1, … *n*-1），那么 **Tr** 的上界是 1 加上（**r**i 可以为空）以 **r**i 为根的子树的数量加上每个 **r**i 的上界之积。
计算包含根节点的子树数量的方法是：
如果 **Tr** 只有一个节点（根节点），则包含的子树数量为 1；
否则，它是
树的递归性很强。
我们考虑一个满二叉树，见下图。
| 深度 | 诱导子树数量的上界 |
| 1 | 1 |
| 2 | 6 |
| 3 | 37 |
| 4 | 750 |
| 5 | 459,829 |
| 6 | 210,067,308,558 |
| ... | … 真的很大！ |
请注意，这只是诱导子树的结果；当涉及嵌入式子树时，情况会更糟。现在您明白了原因。
顺便说一句，当文本树中的每个节点都唯一时，会达到上界。当文本树中的每个节点都相同时，也有一个下界。
用于计算最大子树数量的代码已提供，并封装在一个名为*SubTreeNumberPredictor*的类中，我在单元测试中使用它来检查挖掘频繁子树的功能。
希望我分析的正确，希望我的代码能工作。
此版本增加了或更改了什么？
- 树可视化：您可以以图形方式查看文本树或模式树，而不是它们的 preorder 字符串。
- 出现可视化：您可以以图形方式查看模式的出现及其寄生文本树。
- 实现了一个子树同构算法。
- Bug 修复：一些不闭合或不最大的模式被错误分类，因为之前的子树同构方法不正确。
- 更改了 CCTreeMiner 的实现结构。
- 添加了一些单元测试（哦！单元测试！像浪花、树叶、云朵一样将我托起！我跌落在 BUG 的荆棘上，我流血！ :)）。
这花费了我无数个休息时间来分析和实现这个算法，因为我的工作与数据挖掘无关。但看到它终于起作用了，这是值得的。
它可能有用的，可能包含错误，可以改进，如果您发现了问题，请告诉我，我将不胜感激。