如何加速基于仅生成结果（右侧）是数据集的一个元素的关联规则的 Apriori 框架？

Question

我有一个包含 600 000 行和 15 列的 csv 文件 "Col1, Col2 ... COl15"。我想生成关联规则，其中只有右侧只有来自 col15 的值。我正在使用 here

的先验实现

它以这种方式计算每个项目集的 minSupport：

oneCSet = returnItemsWithMinSupport(itemSet,
                                        transactionList,
                                        minSupport,
                                        freqSet)
    print "reached line 80"
    currentLSet = oneCSet
    k = 2
    while(currentLSet != set([])):
        print k
        largeSet[k-1] = currentLSet
        currentLSet = joinSet(currentLSet, k)
        currentCSet = returnItemsWithMinSupport(currentLSet,
                                                transactionList,
                                                minSupport,
                                                freqSet)
        currentLSet = currentCSet
        k = k + 1

def returnItemsWithMinSupport(itemSet, transactionList, minSupport, freqSet):
        """calculates the support for items in the itemSet and returns a subset
       of the itemSet each of whose elements satisfies the minimum support"""
        _itemSet = set()
        localSet = defaultdict(int)
        #print itemSet

        for item in itemSet:
            #print "I am here", list(item)


            for transaction in transactionList:
                if item.issubset(transaction):
                    freqSet[item] += 1
                    localSet[item] += 1
        print "Done half"
        for item, count in localSet.items():
            support = float(count)/len(transactionList)

            if support >= minSupport:
                _itemSet.add(item)

        return _itemSet

但是对于我拥有的许多行，这会花费很多时间，因为我希望 RHS 被限制为仅具有来自特定列（Col15）的值，我可以通过某种方式削减来加快实现速度吗减少频繁项集？另一种方法是在最后过滤规则，但它具有相同的时间复杂度。或者有其他一些 implementation/library 可以帮助我加快速度吗？

Answer 1

没有。没有办法加快先验框架的复杂性，以生成仅以数据集的一个特定元素作为结果的关联规则。但是你可以稍微加快计算时间。

先验框架包括两个步骤。第一步是生成频繁项集。第二步是生成这些频繁项集的关联规则。为了加快框架的速度，研究关联规则的生成几乎没有用处。先验算法的大部分复杂性在于频繁项集的提取。

先验算法提取频繁项集的方式如下：

统一所有项目
获取所有 1 个长度的频繁项集的 uniquify 项
将那些 1 个长度的频繁项集合并为 2 个长度的项集
获取这 2 个长度的项集所有 2 个长度的频繁项集
将这n个长度的频繁项集合并为n+1个长度的项集
得到这n+1个项集的所有n+1个频繁项集
重复5.和6.直到n+1个组合项集中没有频繁项集出来

在那些生成的 n+1 长度频繁项集中生成了关联规则。关联规则的生成相当简单：

将频繁项集组合成关联规则
根据置信度检查生成的关联规则
如果关联规则高于置信度，则它是强关联规则，因此是有效的关联规则

假设是所有生成的关联规则的结果的数据集元素在下面称为 x。

为了加快计算速度，第一步是将步骤1中频繁项集的抽取简化。在步骤 1.2 中是要从 1 长度频繁项集的结果集中删除的 1 长度频繁项集 {(x)}。如果元素在步骤 1.2 中没有被提取为频繁项集，则算法应该停止。因为这样就不可能有关联规则作为结果。一个关联规则由n个长度的频繁项集组成。

因此第1步频繁项集提取的结果只包含n个长度的频繁项集，这些频繁项集适合作为关联规则的前件，而后件只能是{(x)}。这些是那些不包含 {(x)} 的频繁项集。这节省了计算时间，因为有一个长度为 1 的频繁项集，如果该项集是频繁项集，则要合并其中的 n 个长度项集并根据支持度检查。

为了加快计算速度的第二步是将step 2的关联规则的生成简化。在步骤 2.1 中仅生成关联规则，其结果为 {(x)}。可以形成关联，例如将频繁项集提取的结果并将每个频繁项集作为前件与{（x）}作为关联规则的结果组合起来。因此，关联规则需要 ({(n 长度频繁项集)} -> {(x)}).

但要真正加快计算速度，请使用另一种算法来提取频繁项集。 fp-growth 算法已经快了一种方式。提取频繁项集的最快算法是最新的 prepost+ 算法。

一个整洁的 python 库，其中包含用于提取频繁项集的算法 one。

tl;dr：复杂性保持不变。可以改进计算时间。总体而言，应该使用另一种更快的算法而不是像 fp-growth 这样的先验算法。

Answer 2

根据第 15 列中的值拆分您的数据集，这将是您右侧的 RHS。因此，如果您在该列中有 5 个不同的值，那么您现在将获得 5 个数据集。每个删除最后一列，现在是常量。
仅在其他列上计算频繁项集（非关联规则），通过 Apriori 在每个子集（快点！）。但是您仍然需要比您链接的随机 github 版本更好的实现。只需要FIM，不需要规则！
将带有分区键的频繁项集组成一个关联规则，(FIS -> RHS) 并像关联规则一样使用您的首选指标进行评估。

这要快很多，因为它不会生成跨越多个 col15 键的频繁项集。在每个分区中，所有剩余数据都与您的 objective 相关。此外，它还适用于 未修改 Apriori FIM 生成。

如何加速基于仅生成结果（右侧）是数据集的一个元素的关联规则的 Apriori 框架？

How to Speed Up the Apriori Framework Based On to Generate Only Association Rules Which Consequents (Right Hand Side) Are One Element of the Data Set?

python

machine-learning

data-mining

apriori