FP-Growth(并发)

描述

在网上购物时，你有时会得到以下形式的建议:“购买X商品的顾客也购买了y商品。”此建议是关联规则的一个示例。为了得到它，你首先必须知道市场上哪些商品最常出现在顾客的购物篮中，在这里FP-Growth算法可以发挥作用。

FP-Growth算法是一种计算事务数据库中频繁共存项的高效算法。为了理解它是如何工作的，让我们从一些术语开始，以客户事务为例:

• 物品-在市场上出售的任何物品
• 篮子-客户选择的一个或多个项目的容器
• Itemset—在同一购物篮中一起出售的任何商品的子集
• 交易-在购买的那一刻，在单个购物篮里的全部物品
• 交易数据库-由商家记录的完整的购物篮/交易

在这里，“购物篮”和“交易”这两个词可以互换使用，因为我们将客户的购物篮与所购买的商品标识在一起。为了使这些定义具体化，请考虑以下事务数据库:

• Transaction1 = (product1, product2, product7)
• Transaction2 = (product2, product5, product7)
• Transaction3 = (product6, product7, product8, product9)
• Transaction4 = (product1, product3, product4, product6, product7)

游戏中有9种不同的道具可供出售，有4个篮子/交易，包含不同数量的道具。出现最频繁的项product7在事务数据库中出现了四次。以下每个项集出现两次:(product1, product7)， (product2, product7)， (product6, product7)。

可以有效地创建fp树数据结构，将数据压缩得如此之大，以至于在许多情况下，甚至大型数据库也可以放入主内存中。在上面的示例中，FP-tree的根旁将有最频繁出现的产品product7，其分支从product7到product1、product2和product6。如果我们坚持一个产品必须在事务数据库中出现不止一次，那么剩余的产品将被排除在fp树之外。乐鱼全站app下载事务数据库最初可能是一个4 x 9(事务x产品)数据表，其中有许多零条目，但现在它被简化为一个极简的树，只捕获相关的频率数据。乐鱼全站app下载

即使有一个有效的树结构，算法所考虑的项目集的数量也会变得非常大。通过参数的帮助项目集的最大数量，您可以在必要时减少运行时间和内存。

请记住，网上购物只是一个例子;FP-Growth算法可以应用于任何可以用项目、项目集和篮子/交易来表述的问题。该算法的典型设置是一个大型事务数据库(许多篮子)，每个篮子中只有少量的项目——与所有项目的集合相比很小。

• support =(一个项目或项目集在数据库中出现的次数)/(数据库中篮子的数量)

一般来说，“最小支持”的概念创建了一个界限，定义了项目集频繁出现或不频繁出现的含义。如果一个项目或项目集只出现在几个筐中，则通过参数将其排除最小的支持或最小频率．排除不经常出现的项和项集有助于压缩数据并提高结果的统计显著性。另一方面，如果最小的支持或最小频率设置过高，算法可能找不到零项集。因此，该操作符通过复选框提供了两种主要模式求最小项集数：

1.如果未选中，则使用固定的最小支持值，并且

2.如果选中，使用动态最小支持值，以确保结果包含最小数量的项集。

FP-Growth支持几种不同的输入数据格式。请注意以下要求:

• 在ExampleSet中，一个事务=一行。有关这些列的讨论，请参见下面。
• 所有项目的值必须是标称的
• 事务ID是可选的，如果存在，它应该具有“ID”角色，这样它就不会被标识为项。

对于列，在第二篇教程中说明了三种可用的输入格式，以及必要的预处理。以下是总结:

• 列中的项目列表:属于一个事务的所有项目以类似csv的格式显示在一个列中，由项目分隔符分隔。与CSV文件一样，条目可以加引号，并且可以使用转义字符。您可以修改项目名称。
• 分列项:属于一个事务的所有项显示在分列中。对于每个事务，第一个项目名称出现在第一列，第二个项目名称出现在第二列，依此类推。列数对应于具有最大项目数的篮子。缺少值表示没有项目。您可以修改项目名称。
• 虚拟编码列中的项目:所有项目集合中的每个项目都有自己的列，项目名称是列名。对于每笔交易，二值(true/false)表示该商品是否可以在购物篮中找到。如果您的数据是二项式的，但没有将值标识为true/false，则可能必须设置正值参数。