本文主要是介绍weka实战004:fp-growth关联规则算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
apriori算法的计算量太大,如果数据集略大一些,会比较慢,非常容易内存溢出。
我们可以算一下复杂度:假设样本数有N个,样本属性为M个,每个样本属性平均有K个nominal值。
1. 计算一项频繁集的时间复杂度是O(N*M*K)。
2. 假设具有最小支持度的频繁项是q个,根据它们则依次生成一项频繁集,二项频繁集,....,r项频繁集合,它们的元素数量分别是:c(q, 1), c(q,2), ...,c(q, r)。那么频繁集的数量是极大的,单机肯定不能支持,比如说,假设q=10000--其实很小,电商/零售商的数据比这大太多了--此时生成的二项频繁集合的元素数量是5千万,三项频繁集超过1000亿... 打住吧,不要再往下算了...
3. 如果transaction有100万个,这也不算多,但计算二项频繁集的关联规则就要扫描数据库100万*5千万。
所以快速算法是必须,否则搞不下去。
fp-growth就是一种快速算法,设计非常巧妙,它的流程是这样的:
1. 计算最小支持度频繁项,并按照支持度从大到小排列,形如{'f':100, 'c':84, 'd':75, 'a':43, 'q':19, ...}
2. 把transaction的所有记录,都按照最小支持度频繁项进行排列,如果没有某个频繁项,就空下来,于是,transaction就是如下的形式:</
这篇关于weka实战004:fp-growth关联规则算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!