关联规则挖掘的橙色表现

Question

我正在使用 orangecontrib.associate.fpgrowth 进行关联规则挖掘。根据几个实验，似乎随着产品数量增加到 1000 以上，然后运行时间呈指数增长。但是，我不确定这是不是真的。算法的复杂性是否有任何近似值 and/or 对性能影响最大的参数（如产品数量？总交易数量？或其他？

Answer 1

关联规则生成算法一般"explode"相当快。 Rules-from-itemsets 操作，特别是，我认为类似于枚举幂集 (2ⁿ)。我自己无法进一步详细说明理论复杂性，但我认为给定支持/信心/平均的运行时间。交易规模阈值与其他地方的阈值相当：

import time

import numpy as np
from orangecontrib.associate.fpgrowth import frequent_itemsets,\
                                             association_rules

for n_trans in (100, 1000, 10000):
    for n_items in (10, 100, 1000):
        X = np.random.random((n_trans, n_items)) > .8

        t_start = time.clock()
        itemsets = dict(frequent_itemsets(X, .05))
        n_itemsets = len(itemsets)
        t_itemsets = time.clock() - t_start

        t_start = time.clock()
        rules = list(association_rules(itemsets, .01))
        n_rules = len(rules)
        t_rules = time.clock() - t_start

        print('{:5d} {:4d}   {:5.1f} ({:7d})   {:4.1f} ({:7d})'.format(
            n_trans, n_items, t_itemsets, n_itemsets, t_rules, n_rules))

输出：

  100   10     0.0 (     24)    0.0 (     28)
  100  100     0.1 (   1800)    0.0 (   3880)
  100 1000    43.3 ( 470675)   15.3 (2426774)
 1000   10     0.1 (     11)    0.6 (      2)
 1000  100     0.2 (    452)    0.0 (    704)
 1000 1000    33.5 (  35448)    0.8 (  68896)
10000   10     0.1 (     10)    0.0 (      0)
10000  100     2.6 (    100)    0.0 (      0)
10000 1000   180.8 (   1000)    0.0 (      0)

关联规则挖掘的橙色表现

Orange performance on Association rule mining

associations

orange