基本概念
和Apriori算法相比,FP-growth算法只需要对数据库进行两次遍历,从而高效发现频繁项集。
FP-growth算法是基于Apriori原理的,通过将数据集存储在FP(Frequent Pattern)树上发现频繁项集,但不能发现数据之间的关联规则。FP-growth算法只需要对数据库进行两次扫描,而Apriori算法在求每个潜在的频繁项集时都需要扫描一次数据集,所以FP-growth算法是高效的。其中算法发现频繁项集的过程是:
(1)构建FP树;
(2)从FP树中挖掘频繁项集。
构建FP树
FP表示的是频繁模式,其通过链接来连接相似元素,被连起来的元素可以看成是一个链表。将事务数据表中的各个事务对应的数据项按照支持度排序后,把每个事务中的数据项按降序依次插入到一棵以 NULL为根节点的树中,同时在每个结点处记录该结点出现的支持度。
FP-growth算法的流程为:首先构造FP树,然后利用它来挖掘频繁项集。在构造FP树时,需要对数据集扫描两边,第一遍扫描用来统计频率,第二遍扫描至考虑频繁项集。
从FP树中挖掘频繁项集
在构建了FP树之后,就可以抽取频繁项集了,这里的思想和Apriori算法大致类似,首先从氮元素项集合开始,然后在此基础上逐步构建更大的集合。大致分为三个步骤:
(1)从FP树中获得条件模式基;
(2)利用条件模式基,构建一个条件FP树;
(3)迭代重复(1)和(2),直到树包含一个元素项为止。
首先,获取条件模式基。条件模式基是以所查找元素项为结尾的路径集合,表示的是所查找的元素项与树根节点之间的所有内容。
其次,构建条件模式基。对于每一个频繁项,都需要创建一棵条件FP树,使用创建的条件模式基作为输入,采用相同的建树代码来构建树,相应的递归发现频繁项、发现条件模式基和另外的条件树。