大部分人都理解错了的FPgrowth算法
摘要 韩家炜教授等人提出FP-growth(Frequent Pattern growth)算法是频繁模式(Frequent Pattern, FP)挖掘领域的经典算法，其高效性能的背后是强大的信息压缩树——频繁模式树(Frequent Pattern Tree, FPTree)，但在构建FPTree的过程中很容易忽略一些关键的步骤，如正确的频繁模式顺序(Frequent Pattern Ordering, FPO)和排序结果的稳定性，这篇文章从原论文出发，分析当前网络上高点击量的复现文章的不当之处，给出一个较为合理的复现方法。
引言
FP-growth算法由韩家炜[1]等人于2000年提出，其中FPTree是使得这一算法相比Aprioris等算法较为高效的关键数据结构，FPTree将数据库中的所有事务(Transactions)高度压缩成树的路径，所有的频繁项(Frequent Items, FIs)都成为树的一个节点，每个节点都拥有相应的计数，代表该FI在数据库中出现的次数，其中叶子节点的计数等于前向遍历路径中的FIs出现在数据库中的次数。因此所有的挖掘工作都以最初的FPTree为中心展开，而在构建一棵FPTree时，核心步骤在于对每一条事务进行降序排序。但是，在这一过程中要保证FIs出现顺序的一致性，否则树的结构是不唯一的，那么挖掘的结果就会产生偏差。 这是大部分人在复现的时候容易忽略的一个点，而另外一种情况出现在流行机器学习畅销书 《Machine Learning in Action》(译为：机器学习实践)中，该书的FP-growth的实现版本结果存在随机性。 在网络上我选取了两篇点击量较高的FP-growth的复现文章：
这两篇文章相似程度极高，且都是参考了《Machine Learning in Action》这一书。可见这一错误传播的广泛程度。本文使用的数据集与FP-growth原论文使用的数据集相同，即：
图1: 数据集取自Han J et al.[1]
正确的FPTree如下图所示：
图2: 正确的FPTree取自Han J et al.[1]
之后在所提到的复现文章提供的算法上运行图1的数据集，分析他们的不足之处。另外，本文所使用的Python语言版本为3.7.6。
注： 本文对于所提到的书籍或文章均无恶意，仅从良性学术交流的目的出发，互相学习。由于本人才疏学浅，文中难免出现不妥之处，烦请各位雅正。
他们错在哪？
从前文中，我们知道FPTree的正确性取决于正确顺序的FIs，图1左边为原始数据库中的事务，假定最小支持度(minimum support)为3，那么在第一次扫描数据库之后可以得到如下的FIs:
$$ \langle (f:4) , (c:4) , (a:3) , (b:3) , (m:3) , (p:3) \rangle $$
之后根据FIs的出现次数以降序排序，但是真的这样就可以的到与图1右边一致的排序结果了吗？我们分别以直接降序排序的方法和文章[1,2]所提供的算法来对比测试一下。
使用直接降序排序方法得出结果：
直接排序的结果中$T200, T500$与图1中的结果有较大出入，而这样的排序结果产生的FPTree如下图所示：
图3: 直接降序排序产生的FPTree
显然这样的FPTree是无法得出正确的结果的。这种方法忽略了生成FPTree的两个重要环节，在原论文中描述如下:
(3) If multiple transactions share an identical frequent item set, they can be merged into one with the number of occurrences registered as count. It is easy to check whether two sets are identical if the frequent items in all of the transactions are sorted according to a fixed order.
(4) If two transactions share a common prefix, according to some sorted order of frequent items, the shared parts can be merged using one prefix structure as long as the count is registered properly. If the frequent items are sorted in their frequency descending order, there are better chances that more prefix strings can be shared.
规则(3)阐述的是如果多个事务共享同一个FIs，那么应该让他们的顺序保持一致，以图1的例子来说，$T100, T500$实质是共享FIs的，那么它们应该都表示成$f,c,a,m,p$。而规则(4)则是说如果两个事务拥有同样的前缀，那么在降序排序的情况下，它们的前缀也应高保持一致，以图1来说，$T100, T200$是有共同前缀$f,c$，此时应该保持前缀是一致的，即都应该以$f,c$为前缀。
下面分别讨论文章[1,2]的做法，由于文章[1,2]均参考了《Machine Learning In Action》，自然不会犯直接排序这样的低级错误，但是它所提供的算法真的就完美吗？
文章1所提供的排序代码：
文章2所提供的排序代码：
可以看出两者的排序思想是一致的(因此结果只需给出其中一个的即可)，下图展示排序结果：
图4: 不稳定的排序结果
图3中展示两次运行的结果，它们虽然符合了规则(3)(4)的要求，但是两次排序的结果截然不同，这样的结果在Apriori这样的算法中没什么影响，但是在FPTree这样对顺序敏感的结构中却是致命的，这样会导致两棵完全不同的FPTree，进而有不同的Conditional Pattern Base和Conditional Pattern Tree。其原因是它们都是用了frozenset的数据结构，如下图所示：
图5: 不稳定的Frozenset
可以看到两次frozenset的存储结果是不一致的，因为frozenset并不稳定，详情可以见 StackOverflow: 3812429。这样的做法到底对结果的影响有多大？我们评估一下这两个算法的结果，如下图所示：
图6: 不稳定的FI
图5展示的结果中，$a,m$两次排序由于随机性所得出来的FIs完全不一致，而在原论文中正确的FIs如下图所示：
图7: 原论文中的结果
且不论是哪一次的运行结果中以$m$为后缀的FIs都没有包括$a$， 这是一个比较意外的事情，也许是在使用不同语言所提供的数据结构时作者没有考虑清楚，但其思想还是值得学习的。为了完全复现原文的结果，我的一个不成熟的想法是，抛弃set这种方便但不稳定的结构，换成list或者tuple。
一个不成熟的尝试
这里我使用的比较笨拙的方法实现规则(3)(4)，对于规则(3)我们只需要检查当前的FIs是否与已存在的路径有完全相同的元素，如果是，则用后者替换即可保证一致性，否则不做任何处理：
其中self.__order_frequent_itemsets就是一个已经存在在FPTree中的FIs数组。而对于规则(4)的处理则比较麻烦，因为检查前缀是一个计算复杂度较高的任务，而且原论文中也没有特别清晰的说明前缀的具体定义，如$f,c,a,m,p$与$c,f,a,b,m$，前者$f,c$可以是后者的一个前缀，而$f,c,a,m$同样也可以作为后者的前缀，并且它们符合计数排序的规则，但是两者的排序结果截然不同。因此我这里考虑的是以$support \; count$为分割标准，如对于$c,f,a,b,m$而言，$f,c$的$support \; count$都为4，而$a,b,m$都为3，但我们不考虑最后一层，因为它们都可能成为叶子节点。因此可以以如下方式实现：
其中self.__fitemsets是一个存储FIs计数的字典。然后我们在构建树的过程中按照以下方式即可既保证一致性也保证稳定性：
最后运行图1的数据集可以得出与原论文一致的FPTree结构：
图8: 本文算法执行的结果
本文实验代码可在附录中下载。
结论
FPTree是非常强大的事务信息压缩结构，其思想贡献以远超FP-growth本身，但FPTree却是对顺序极其敏感，因此在复现的过程中希望各位读者要多加留心，而对于文章[1,2]所提供的算法存在的结果随机性问题，从目前的分析来看的确存在的，而原因可能是多样的，但是如果这样的方法一旦被放入开源框架中危害则是巨大的，所以希望相关的从业人员能够提供更多的改进建议。本文可能还有其他的不当之处，还是烦请各位读者能够慷慨赐教，感谢！
参 考 文 献
[1] Han, J., Pei, J., & Yin, Y. (2000). Mining frequent patterns without candidate generation. ACM sigmod record, 29(2), 1-12.
附 录
继续阅读：大部分人都理解错了的FPgrowth算法引言
FP-growth算法由韩家炜[1]等人于2000年提出，其中FPTree是使得这一算法相比Aprioris等算法较为高效的关键数据结构，FPTree将数据库中的所有事务(Transactions)高度压缩成树的路径，所有的频繁项(Frequent Items, FIs)都成为树的一个节点，每个节点都拥有相应的计数，代表该FI在数据库中出现的次数，其中叶子节点的计数等于前向遍历路径中的FIs出现在数据库中的次数。因此所有的挖掘工作都以最初的FPTree为中心展开，而在构建一棵FPTree时，核心步骤在于对每一条事务进行降序排序。但是，在这一过程中要保证FIs出现顺序的一致性，否则树的结构是不唯一的，那么挖掘的结果就会产生偏差。 这是大部分人在复现的时候容易忽略的一个点，而另外一种情况出现在流行机器学习畅销书 《Machine Learning in Action》(译为：机器学习实践)中，该书的FP-growth的实现版本结果存在随机性。 在网络上我选取了两篇点击量较高的FP-growth的复现文章：
这两篇文章相似程度极高，且都是参考了《Machine Learning in Action》这一书。可见这一错误传播的广泛程度。本文使用的数据集与FP-growth原论文使用的数据集相同，即：
图1: 数据集取自Han J et al.[1]
正确的FPTree如下图所示：
图2: 正确的FPTree取自Han J et al.[1]
之后在所提到的复现文章提供的算法上运行图1的数据集，分析他们的不足之处。另外，本文所使用的Python语言版本为3.7.6。
注： 本文对于所提到的书籍或文章均无恶意，仅从良性学术交流的目的出发，互相学习。由于本人才疏学浅，文中难免出现不妥之处，烦请各位雅正。
他们错在哪？
从前文中，我们知道FPTree的正确性取决于正确顺序的FIs，图1左边为原始数据库中的事务，假定最小支持度(minimum support)为3，那么在第一次扫描数据库之后可以得到如下的FIs:
$$ \langle (f:4) , (c:4) , (a:3) , (b:3) , (m:3) , (p:3) \rangle $$
之后根据FIs的出现次数以降序排序，但是真的这样就可以的到与图1右边一致的排序结果了吗？我们分别以直接降序排序的方法和文章[1,2]所提供的算法来对比测试一下。
使用直接降序排序方法得出结果：
直接排序的结果中$T200, T500$与图1中的结果有较大出入，而这样的排序结果产生的FPTree如下图所示：
图3: 直接降序排序产生的FPTree
显然这样的FPTree是无法得出正确的结果的。这种方法忽略了生成FPTree的两个重要环节，在原论文中描述如下:
(3) If multiple transactions share an identical frequent item set, they can be merged into one with the number of occurrences registered as count. It is easy to check whether two sets are identical if the frequent items in all of the transactions are sorted according to a fixed order.
(4) If two transactions share a common prefix, according to some sorted order of frequent items, the shared parts can be merged using one prefix structure as long as the count is registered properly. If the frequent items are sorted in their frequency descending order, there are better chances that more prefix strings can be shared.
规则(3)阐述的是如果多个事务共享同一个FIs，那么应该让他们的顺序保持一致，以图1的例子来说，$T100, T500$实质是共享FIs的，那么它们应该都表示成$f,c,a,m,p$。而规则(4)则是说如果两个事务拥有同样的前缀，那么在降序排序的情况下，它们的前缀也应高保持一致，以图1来说，$T100, T200$是有共同前缀$f,c$，此时应该保持前缀是一致的，即都应该以$f,c$为前缀。
下面分别讨论文章[1,2]的做法，由于文章[1,2]均参考了《Machine Learning In Action》，自然不会犯直接排序这样的低级错误，但是它所提供的算法真的就完美吗？
文章1所提供的排序代码：
文章2所提供的排序代码：
可以看出两者的排序思想是一致的(因此结果只需给出其中一个的即可)，下图展示排序结果：
图4: 不稳定的排序结果
图3中展示两次运行的结果，它们虽然符合了规则(3)(4)的要求，但是两次排序的结果截然不同，这样的结果在Apriori这样的算法中没什么影响，但是在FPTree这样对顺序敏感的结构中却是致命的，这样会导致两棵完全不同的FPTree，进而有不同的Conditional Pattern Base和Conditional Pattern Tree。其原因是它们都是用了frozenset的数据结构，如下图所示：
图5: 不稳定的Frozenset
可以看到两次frozenset的存储结果是不一致的，因为frozenset并不稳定，详情可以见 StackOverflow: 3812429。这样的做法到底对结果的影响有多大？我们评估一下这两个算法的结果，如下图所示：
图6: 不稳定的FI
图5展示的结果中，$a,m$两次排序由于随机性所得出来的FIs完全不一致，而在原论文中正确的FIs如下图所示：
图7: 原论文中的结果
且不论是哪一次的运行结果中以$m$为后缀的FIs都没有包括$a$， 这是一个比较意外的事情，也许是在使用不同语言所提供的数据结构时作者没有考虑清楚，但其思想还是值得学习的。为了完全复现原文的结果，我的一个不成熟的想法是，抛弃set这种方便但不稳定的结构，换成list或者tuple。
一个不成熟的尝试
这里我使用的比较笨拙的方法实现规则(3)(4)，对于规则(3)我们只需要检查当前的FIs是否与已存在的路径有完全相同的元素，如果是，则用后者替换即可保证一致性，否则不做任何处理：
其中self.__order_frequent_itemsets就是一个已经存在在FPTree中的FIs数组。而对于规则(4)的处理则比较麻烦，因为检查前缀是一个计算复杂度较高的任务，而且原论文中也没有特别清晰的说明前缀的具体定义，如$f,c,a,m,p$与$c,f,a,b,m$，前者$f,c$可以是后者的一个前缀，而$f,c,a,m$同样也可以作为后者的前缀，并且它们符合计数排序的规则，但是两者的排序结果截然不同。因此我这里考虑的是以$support \; count$为分割标准，如对于$c,f,a,b,m$而言，$f,c$的$support \; count$都为4，而$a,b,m$都为3，但我们不考虑最后一层，因为它们都可能成为叶子节点。因此可以以如下方式实现：
其中self.__fitemsets是一个存储FIs计数的字典。然后我们在构建树的过程中按照以下方式即可既保证一致性也保证稳定性：
最后运行图1的数据集可以得出与原论文一致的FPTree结构：
图8: 本文算法执行的结果
本文实验代码可在附录中下载。
结论
FPTree是非常强大的事务信息压缩结构，其思想贡献以远超FP-growth本身，但FPTree却是对顺序极其敏感，因此在复现的过程中希望各位读者要多加留心，而对于文章[1,2]所提供的算法存在的结果随机性问题，从目前的分析来看的确存在的，而原因可能是多样的，但是如果这样的方法一旦被放入开源框架中危害则是巨大的，所以希望相关的从业人员能够提供更多的改进建议。本文可能还有其他的不当之处，还是烦请各位读者能够慷慨赐教，感谢！
参 考 文 献
[1] Han, J., Pei, J., & Yin, Y. (2000). Mining frequent patterns without candidate generation. ACM sigmod record, 29(2), 1-12.
附 录