Python基础原理：FP-growth算法的构建

开辟者大年夜赛路演 | 12月16日，技巧立异，北京不见不散

和Apriori算法比拟，FP-growth算法只须要对数据库进行两次遍历，大年夜而高效发明频繁项集。对于搜刮引擎公司而言，他们须要经由过程查看互联网上的用词，来找出经常在一块出现的词。是以就须要可以或许高效的发明频繁项集的办法，FP-growth算法就可以完成此重担。

FP-growth算法是基于Apriori道理的，经由过程将数据集存储在FP（Frequent Pattern)树上发明频繁项集。

FP-growth算法只须要对数据库进行两次扫描，而Apriori算法在求每个潜在的频繁项集时都须要扫描一次数据集，所以说FP-growth算法是高效的。

FP算法发明频繁项集的过程是：

结合Apriori算法中最小支撑度的阈值，在此将最小支撑度定义为3，结合上表中的数据，那些不知足最小支撑度请求的将不会涌如今最后的FP树中。

(1)构建FP树；

(2)大年夜FP树中发掘频繁项集

FP表示的是频繁模式，其经由过程链接来连接类似元素，被连起来的元素可算作是一个链表

将事务数据表中的各个事务对应的数据项，按照支撑度排序后，把每个事务中的数据项按降序依次插入到一棵以 NULL为根节点的树中，同时在每个结点处记录该结点出现的支撑度。

假设存在的一个事务数据样例为,构建FP树的步调如下：

据此构建FP树，并采取一个头指针表来指向给定类型的第一个实例，快速拜访FP树中的所有元素，构建的带头指针的FP树如图：

结合绘制的带头指针表的FP树，对表中数据进行过滤，排序如下：

在对数据项过滤排序了之后，就可以构建FP树了，大年夜NULL开端，向个中赓续添加过滤排序后的频繁项集。过程可表示为：

如许，FP树对应的数据构培养建好了，如今就可以构建FP树了，FP树的构建函数拜见Python源代码。

在运行上例之前还须要一个真正的数据集，结合之前的数据自定义数据集。如许就构建了FP树，接下来就是应用它来进行频繁项集的发掘。

【编辑推荐】

【义务编辑：武晓燕 TEL：（010）68476606】

　　推荐阅读

　　你试过C语言和Python一起混合编程吗？两者相加不是已经无敌了！

开辟者大年夜赛路演 | 12月16日，技巧立异，北京不见不散C说话是编程说话的祖母，然则跟着一代一代的编程说话长大年夜，所以祖母也是会拍在沙岸上的，很多小小伙伴应当都邑学过或者懂得C说话，因闻敉件>>>详细阅读

地址：http://www.17bianji.com/lsqh/39688.html