Array ( [article_id] => 158 [article_title] => FP—tree [article_keyword] => FP—tree,FP—tree算法原理,FP—tree算法用途 [article_description] => 频繁模式增长算法（Frequent-pattern growth, FP-Growth）是一种挖掘频繁项集的方法。 [article_detail] => 一种挖掘频繁项集的方法。 [article_content] => <div class="rightwrap collegeDetail"> <h1 class="algorithmName"> FP—tree </h1> <div class="clearfix topcontent"> <p> 机器学习是一门多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。主要研究计算机怎样模拟或实现人类的学习行为，以获取新的知识和技能，重新组织已有的知识结构，不断的改善自身的性能。 </p> <p> 机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。这些算法是一类能从数据中自动分析获得规律，并利用规律对未知数据进行预测的算法。简而言之，机器学习主要以数据为基础，通过大数据本身，运用计算机自我学习来寻找数据本身的规律，而这是机器学习与统计分析的基本区别。 </p> <p> 机器学习主要有三种方式：监督学习，无监督学习与半监督学习。 </p> <p> （1）监督学习：从给定的训练数据集中学习出一个函数，当新的数据输入时，可以根据函数预测相应的结果。监督学习的训练集要求是包括输入和输出，也就是特征和目标。训练集中的目标是有标注的。如今机器学习已固有的监督学习算法有可以进行分类的，例如贝叶斯分类，SVM，ID3，C4.5以及分类决策树，以及现在最火热的人工神经网络，例如BP神经网络，RBF神经网络，Hopfield神经网络、深度信念网络和卷积神经网络等。人工神经网络是模拟人大脑的思考方式来进行分析，在人工神经网络中有显层，隐层以及输出层，而每一层都会有神经元，神经元的状态或开启或关闭，这取决于大数据。同样监督机器学习算法也可以作回归，最常用便是逻辑回归。 </p> <p> （2）无监督学习：与有监督学习相比，无监督学习的训练集的类标号是未知的，并且要学习的类的个数或集合可能事先不知道。常见的无监督学习算法包括聚类和关联，例如K均值法、Apriori算法。 </p> <p> （3）半监督学习：介于监督学习和无监督学习之间,例如EM算法。 </p> <p> 如今的机器学习领域主要的研究工作在三个方面进行：1）面向任务的研究，研究和分析改进一组预定任务的执行性能的学习系统；2）认知模型，研究人类学习过程并进行计算模拟；3）理论的分析，从理论的层面探索可能的算法和独立的应用领域算法。 </p> </div> <div class="lemma_catalog clearfix"> <h2 class="block_title"> 目录 </h2> <div class="lemma_list"> <a href="#a_2">1、算法描述</a><a href="#a_6">2、算法背景</a><a href="#a_8">3、相关应用</a><a href="#a_11">4、参考资料</a><a href="#a_15">5、实例</a><a href="#a_27">6、输入输出</a><a href="#a_30">7、相关条目</a><a href="#a_32">8、优缺点</a> </div> </div> <a name="a_2"></a><a class="para_title"><span class="number">一</span>算法描述</a> <p> 频繁模式增长算法（Frequent-pattern growth, FP-Growth）是一种挖掘频繁项集的方法。 </p> <p> FP-Growth算法采用分治策略，将提供频繁项集的数据库压缩到一颗频繁模式树（Frequent-pattern tree, FP-tree）上，但仍保留项集的关联信息，通过不断地迭代FP-tree的构造和投影过程来发现频繁模式。 </p> <p> FP-Growth算法将发现长频繁模式的问题转化为递归搜索一些较短模式，然后连接最不频繁项作为后缀；它是Apriori算法的优化处理，克服了Apriori算法在过程中重复地扫描数据库和产生大量的候选项集的问题。 </p> <a name="a_6"></a><a class="para_title"><span class="number">二</span>算法背景</a> <p> 2000年,HAN提出了一个称为FP-tree的算法。该算法只进行2次数据库扫描。它直接将数据库压缩成一个频繁模式树，之后通过这课树生成关联规则，该算法解决了其他关联算法繁琐的产生频繁项集过程。 </p> <a name="a_8"></a><a class="para_title"><span class="number">三</span>相关应用</a> <p> 频繁模式增长算法采用分治策略，挖掘全部的频繁项集但不产生候选。该算法应用广泛，如可用在保险领域、生物学领域、地震研究等领域中。 </p> <p> 具体的如可用于消费市场价格分析，猜测顾客的消费习惯；网络安全领域中的入侵检测技术；可用在用于高校管理中，根据挖掘规则可以有效地辅助学校管理部门有针对性的开展贫困助学工作；也可用在移动通信领域中，指导运营商的业务运营和辅助业务提供商的决策制定等。 </p> <a name="a_11"></a><a class="para_title"><span class="number">四</span>参考资料</a> <p> 1 R. Agrawal and R. Srikant. Fast algorithms for mining association rules. In VLDB’94, pages487–499, 1994 </p> <p> 2 R. C. Agarwal, C. C. Aggarwal. Depth first generation of long patterns. KDD’00, pages 108–118, 2000 </p> <p> 3 马克威分析系统使用教程，http://www.tenly.com </p> <a name="a_15"></a><a class="para_title"><span class="number">五</span>实例</a> <p> 假设下表为某商店的事务数据库D，数据库有9个事务，即 D =9，使用FP-tree算法寻找D中的频繁项集。 </p> <table class="college_table"> <tbody> <tr class="thead"> <td> TID </td> <td> 商品ID的列表 </td> </tr> <tr> <td> T100 </td> <td> I1，I2，I5 </td> </tr> <tr> <td> T200 </td> <td> I2，I4 </td> </tr> <tr> <td> T300 </td> <td> I2，I3 </td> </tr> <tr> <td> T400 </td> <td> I1，I2，I4 </td> </tr> <tr> <td> T500 </td> <td> I1，I3 </td> </tr> <tr> <td> T600 </td> <td> I2，I3 </td> </tr> <tr> <td> T700 </td> <td> I1，I3 </td> </tr> <tr> <td> T800 </td> <td> I1，I2，I3，I5 </td> </tr> <tr class="lasttr"> <td> T900 </td> <td> I1，I2，I3 </td> </tr> </tbody> </table> <p> 首先第一次扫描数据库，导出所有的1项频繁项集和支持度的计数，假设最小支持度计数为2。频繁项的集合按支持度计数递减排序，将结果记为L，则L={{I2:7},{I1:6},{I3:6},{I4:2},{I5:2}}。然后FP-tree的构造如下： </p> <p> 创建根节点，初始用“NULL”标记。第二次扫描数据库D，每个事务中的项按L中的次序处理（即按递减支持度计数排序）并对每个事物创建一个分支。例如，扫描第一个事务“T100:I1,I2,,I5”包含三项，导致构造树的包含三个节点的第一个分枝&lt;I2:1&gt;,&lt;I1:1&gt;,&lt;I5:1&gt;，其中I2作为根的子女链接到根，I1链接到I2，I5链接到I1。第二个事务T200按L的次序包含项I2和I4，它导致一个分枝，其中I2链接到根，I4链接到I2。然而该分支应当与T100已存在的路径共享前缀I2，这样我们将节点I2的计数增加1.并创建一个新节点&lt;I4:1&gt;作为&lt;I2:2&gt;的子女链接。一般的，当为一个事物考虑增加分枝时，沿共同前缀上的每个节点的计数增加1，为在前缀之后的项创建节点和链接。 </p> <p> 构造树结构之后，对树的挖掘总结如下： </p> <table class="college_table"> <tbody> <tr class="thead"> <td> 项 </td> <td> 条件模式基 </td> <td> 条件FP树 </td> <td> 产生的频繁模式 </td> </tr> <tr> <td> I5 </td> <td> {{I2 </td> <td> I1:1}},{{I2 </td> <td> I1 </td> </tr> <tr> <td> I3:1}} </td> <td> &lt;I2:2,I1:2&gt; </td> <td> {I2 </td> <td> I5:2},{I1 </td> </tr> <tr> <td> I5:2},{I2 </td> <td> I1 </td> <td> I5:2} </td> <td> I4 </td> </tr> <tr> <td> {{I2 </td> <td> I1:1}},{{I2:1}} </td> <td> &lt;I2:2&gt; </td> <td> {I2 </td> </tr> <tr> <td> I4:2} </td> <td> I3 </td> <td> {{I2 </td> <td> I1:2}},{{I2:2}},{{I1:2}} </td> </tr> <tr> <td> &lt;I2:4,I1:2&gt;&lt;I1:2&gt; </td> <td> {I2 </td> <td> I3:4},{I1 </td> <td> I3:4},{I2 </td> </tr> <tr class="lasttr"> <td> I1 </td> <td> I3:2} </td> <td> I1 </td> <td> {{I2:4}} </td> </tr> </tbody> </table> <p> 首先考虑I5，它是L中的最后一项，而不是第一个。I5出现在树的两个分枝，这些分枝的路径为&lt;I2,I1,I5:1&gt;和&lt;I2,I1,I3,I5:1&gt;，因此，考虑I5为后缀，它对应的两个前缀路径为&lt;I2,I1:1&gt;和&lt;I2,I1,I3:1&gt;，形成I5的条件模式基。它的条件FP树只包含单个路径&lt;I2:2,I1:2&gt;,不包含I3，这是因为它小于最小支持度计数2。该路径产生频繁模式的所有组合为：{I2,I5:2},{I1,I5:2},{I2,I1,I5:2}。 </p> <p> I4的两个前缀路径形成的条件模式基{{I2,I1:1}},{I2:1}，产生单节点的条件FP树&lt;I2:2&gt;，并导出一个频繁模式{I2 I4:2}。注意，尽管I5跟在第一个分枝中的I4之后，但没必要在分析过程中包含I5，因为涉及I5的频繁模式在考察I5时已经分析过。 </p> <p> 与上述分析类似，I3的条件模式基{{I2,I1:2}},{I2:2},{I1:2}。它的条件FP树有两个分枝&lt;I2:4,I1:2&gt;和&lt;I1:2&gt;,它产生模式集：{I2 I3:4},{I1 I3:4},{I2 I1 I3:2},最后，I1的条件模式基为{{I2,4}},它的FP树只包含一个节点&lt;I2:4&gt;,产生一个频繁模式{I2,I1:4}。 </p> <a name="a_27"></a><a class="para_title"><span class="number">六</span>输入输出</a> <p> 输入数据类型：数值型数据 </p> <p> 输出结果：得到所有的频繁模式 </p> <a name="a_30"></a><a class="para_title"><span class="number">七</span>相关条目</a> <p> Apriori算法、频繁项集、规则 </p> <a name="a_32"></a><a class="para_title"><span class="number">八</span>优缺点</a> <p> 优点：在发现频繁模式时，不会产生候选集，从而提升算法的速度 </p> <p> 缺点：整体上FP-tree算法在空间消耗挺大 </p> </div> [is_show] => 1 [cat_id] => 67 [article_img] => [article_order] => 1 [article_time] => 1481347387 [isdel] => 0 )
FP—tree

FP—tree

机器学习是一门多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。主要研究计算机怎样模拟或实现人类的学习行为，以获取新的知识和技能，重新组织已有的知识结构，不断的改善自身的性能。

机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。这些算法是一类能从数据中自动分析获得规律，并利用规律对未知数据进行预测的算法。简而言之，机器学习主要以数据为基础，通过大数据本身，运用计算机自我学习来寻找数据本身的规律，而这是机器学习与统计分析的基本区别。

机器学习主要有三种方式：监督学习，无监督学习与半监督学习。

（1）监督学习：从给定的训练数据集中学习出一个函数，当新的数据输入时，可以根据函数预测相应的结果。监督学习的训练集要求是包括输入和输出，也就是特征和目标。训练集中的目标是有标注的。如今机器学习已固有的监督学习算法有可以进行分类的，例如贝叶斯分类，SVM，ID3，C4.5以及分类决策树，以及现在最火热的人工神经网络，例如BP神经网络，RBF神经网络，Hopfield神经网络、深度信念网络和卷积神经网络等。人工神经网络是模拟人大脑的思考方式来进行分析，在人工神经网络中有显层，隐层以及输出层，而每一层都会有神经元，神经元的状态或开启或关闭，这取决于大数据。同样监督机器学习算法也可以作回归，最常用便是逻辑回归。

（2）无监督学习：与有监督学习相比，无监督学习的训练集的类标号是未知的，并且要学习的类的个数或集合可能事先不知道。常见的无监督学习算法包括聚类和关联，例如K均值法、Apriori算法。

（3）半监督学习：介于监督学习和无监督学习之间,例如EM算法。

如今的机器学习领域主要的研究工作在三个方面进行：1）面向任务的研究，研究和分析改进一组预定任务的执行性能的学习系统；2）认知模型，研究人类学习过程并进行计算模拟；3）理论的分析，从理论的层面探索可能的算法和独立的应用领域算法。

目录

1、算法描述2、算法背景3、相关应用4、参考资料5、实例6、输入输出7、相关条目8、优缺点
一算法描述

频繁模式增长算法（Frequent-pattern growth, FP-Growth）是一种挖掘频繁项集的方法。

FP-Growth算法采用分治策略，将提供频繁项集的数据库压缩到一颗频繁模式树（Frequent-pattern tree, FP-tree）上，但仍保留项集的关联信息，通过不断地迭代FP-tree的构造和投影过程来发现频繁模式。

FP-Growth算法将发现长频繁模式的问题转化为递归搜索一些较短模式，然后连接最不频繁项作为后缀；它是Apriori算法的优化处理，克服了Apriori算法在过程中重复地扫描数据库和产生大量的候选项集的问题。

二算法背景

2000年,HAN提出了一个称为FP-tree的算法。该算法只进行2次数据库扫描。它直接将数据库压缩成一个频繁模式树，之后通过这课树生成关联规则，该算法解决了其他关联算法繁琐的产生频繁项集过程。

三相关应用

频繁模式增长算法采用分治策略，挖掘全部的频繁项集但不产生候选。该算法应用广泛，如可用在保险领域、生物学领域、地震研究等领域中。

具体的如可用于消费市场价格分析，猜测顾客的消费习惯；网络安全领域中的入侵检测技术；可用在用于高校管理中，根据挖掘规则可以有效地辅助学校管理部门有针对性的开展贫困助学工作；也可用在移动通信领域中，指导运营商的业务运营和辅助业务提供商的决策制定等。

四参考资料

1 R. Agrawal and R. Srikant. Fast algorithms for mining association rules. In VLDB’94, pages487–499, 1994

2 R. C. Agarwal, C. C. Aggarwal. Depth first generation of long patterns. KDD’00, pages 108–118, 2000

3 马克威分析系统使用教程，http://www.tenly.com

五实例

假设下表为某商店的事务数据库D，数据库有9个事务，即 D =9，使用FP-tree算法寻找D中的频繁项集。

TID 商品ID的列表
T100 I1，I2，I5
T200 I2，I4
T300 I2，I3
T400 I1，I2，I4
T500 I1，I3
T600 I2，I3
T700 I1，I3
T800 I1，I2，I3，I5
T900 I1，I2，I3

首先第一次扫描数据库，导出所有的1项频繁项集和支持度的计数，假设最小支持度计数为2。频繁项的集合按支持度计数递减排序，将结果记为L，则L={{I2:7},{I1:6},{I3:6},{I4:2},{I5:2}}。然后FP-tree的构造如下：

创建根节点，初始用“NULL”标记。第二次扫描数据库D，每个事务中的项按L中的次序处理（即按递减支持度计数排序）并对每个事物创建一个分支。例如，扫描第一个事务“T100:I1,I2,,I5”包含三项，导致构造树的包含三个节点的第一个分枝<I2:1>,<I1:1>,<I5:1>，其中I2作为根的子女链接到根，I1链接到I2，I5链接到I1。第二个事务T200按L的次序包含项I2和I4，它导致一个分枝，其中I2链接到根，I4链接到I2。然而该分支应当与T100已存在的路径共享前缀I2，这样我们将节点I2的计数增加1.并创建一个新节点<I4:1>作为<I2:2>的子女链接。一般的，当为一个事物考虑增加分枝时，沿共同前缀上的每个节点的计数增加1，为在前缀之后的项创建节点和链接。

构造树结构之后，对树的挖掘总结如下：

项 条件模式基 条件FP树 产生的频繁模式
I5 {{I2 I1:1}},{{I2 I1
I3:1}} <I2:2,I1:2> {I2 I5:2},{I1
I5:2},{I2 I1 I5:2} I4
{{I2 I1:1}},{{I2:1}} <I2:2> {I2
I4:2} I3 {{I2 I1:2}},{{I2:2}},{{I1:2}}
<I2:4,I1:2><I1:2> {I2 I3:4},{I1 I3:4},{I2
I1 I3:2} I1 {{I2:4}}

首先考虑I5，它是L中的最后一项，而不是第一个。I5出现在树的两个分枝，这些分枝的路径为<I2,I1,I5:1>和<I2,I1,I3,I5:1>，因此，考虑I5为后缀，它对应的两个前缀路径为<I2,I1:1>和<I2,I1,I3:1>，形成I5的条件模式基。它的条件FP树只包含单个路径<I2:2,I1:2>,不包含I3，这是因为它小于最小支持度计数2。该路径产生频繁模式的所有组合为：{I2,I5:2},{I1,I5:2},{I2,I1,I5:2}。

I4的两个前缀路径形成的条件模式基{{I2,I1:1}},{I2:1}，产生单节点的条件FP树<I2:2>，并导出一个频繁模式{I2 I4:2}。注意，尽管I5跟在第一个分枝中的I4之后，但没必要在分析过程中包含I5，因为涉及I5的频繁模式在考察I5时已经分析过。

与上述分析类似，I3的条件模式基{{I2,I1:2}},{I2:2},{I1:2}。它的条件FP树有两个分枝<I2:4,I1:2>和<I1:2>,它产生模式集：{I2 I3:4},{I1 I3:4},{I2 I1 I3:2},最后，I1的条件模式基为{{I2,4}},它的FP树只包含一个节点<I2:4>,产生一个频繁模式{I2,I1:4}。

六输入输出

输入数据类型：数值型数据

输出结果：得到所有的频繁模式

七相关条目

Apriori算法、频繁项集、规则

八优缺点

优点：在发现频繁模式时，不会产生候选集，从而提升算法的速度

缺点：整体上FP-tree算法在空间消耗挺大