标签:
fpgrowth |
分类: 数据挖掘 |
FP树构造
FP Growth算法利用了巧妙的数据结构,大大降低了Aproir挖掘算法的代价,他不需要不断得生成候选项目队列和不断得扫描整个数据库进行比对。为了达到这样的效果,它采用了一种简洁的数据结构,叫做frequent-pattern tree(频繁模式树)。下面就详细谈谈如何构造这个树,举例是最好的方法。请看下面这个例子:
http://s9/middle/68ffc7a44ae528c122f48&690
这张表描述了一张商品交易清单,abcdefg代表商品,(ordered)frequent items这一列是把商品按照降序重新进行了排列,这个排序很重要,我们操作的所有项目必须按照这个顺序来,这个顺序的确定非常简单,只要对数据库进行一次扫描就可以得到这个顺序。由于那些非频繁的项目在整个挖掘中不起任何作用,因此在这一列中排除了这些非频繁项目。我们在这个例子中设置最小支持阈值(minimum support threshold)为3。
我们的目标是为整