fptree算法

1. FP-growth的算法思想

基本举郑思路：不断地迭代FP-tree 的构正镇颂造和投影过程
算法描述如下：
1、对于每个频繁项，构造它的条件投影数据库和投影FP-tree。
2、对每个新构建的FP-tree重复这个过旅桐程，直到构造的新FP-tree为空，或者只包含一条路径。
3、当构造的FP-tree为空时，其前缀即为频繁模式；当只包含一条路径时，通过枚举所有可能组合并与此树的前缀连接即可得到频繁模式。

2. 什么是 fptree 算法

FP—tree由标记为“null”的一个根节点(root)、作为根节点之子节点的项前缀子树(item prefix subtrees)的集合、和—个频陆缺繁项头表(frequent item header table)所组成。
项前缀子树中的每个节点包含3个域：item_name,count和node_link。item _name记录了该节点所代表的项的名字。count记录了所在路径代表的事务中达到此节点的事务个数。 node_link指向下一个具有同样的item_name域的节点，如果没有这样一个节点，则其值被置为null。
频繁项头表包含两个域：Item_name和head of node_link. head of node_link指向FP—tree中具有相同Item_name的第一个节点。
根据FP_tree 的定义，我们得到FP_tree的构造方法
2 FP—tree的生成
FP—tree是通过两次扫描事务集建立的.
(1)扫描陵瞎事务集D，获得D中所包含的全部频繁项集合F，及它们各自的支持度。对F中的频繁项按其支持度降序排序,结果记为L；
(2)创建FP—tree的根节点T，以“null”标(3) 记；然后对D中的每个事务Trans进行如下操作：根据L中的顺序，选出并排序Trans的频繁项．设排序后的频繁项表为[x|P]，其中x是第一个频繁项。而P是剩余的频繁项:调用insert—tree([x|P]，T)：insert—tree([x|P]，T)过程执行情况如下：如果T有子女N并使得N.item_name=x.item_name，则N的计数增加1；否则创建一个新节点N，将其计数设置为1，链接到它的父节点T、、并且通过节点链结构将其链接到具有相同item_name的节点；如果P非空，递归地调用INSERT—tree(P，N)。在事务集再次扫描完毕时，一个完全的FP—tree就建成了。
3 频繁模式的挖掘
FP—tree被建立后，频繁模式是采用下面的FP—growth方法对FP—tree进行挖掘得到的. Procere FP_growth(Tree，α)／／tree为α的条件模式树，α为后缀项(集)
{ if Tree 仅含一条路径P then
for 路径P中节点的每个组合(记作?) do
产生模式?Uα、并且把它的支持度supcoun指定为?中节点的最小支持度
else for 对Tree的头表从表尾到表头的每一个表项（记为α1）do {
产生一个模式?＝α1Uα，其支持度计数supcount=α1．supcount：
创建?的条件模式基，然后构造?的条件模式树FP—tree? ；
if FP—tree ?= !Φ then 调用FP_growth(FP—tree?、?)}
从算法2、3中，我们可以看出FP—growth挖掘过程是一种分而治之的过程。而且，即使数据库可能产生指数级大量的频繁模式，FP—tree的规模还是很小，不会呈指数级增长。例如，对于一个长度为100的频繁模式“a1，…，a100”，FP—tree只会生成唯一一条长度为100的路径，如“a1a2…a100”。而且，FP—growth算法可以导出所有的大约1030个频繁模式(如果时间允许的话)，如“a1, a2,..，a1a2，…，a1a2a3：，…，a1…a100”。
3.程序实现
程序在定义数据结构和实现算法的时候主要考虑一下因素。
首先速度。速度问题在频繁集产生的算法中应该是比较重要的.因为它们常常涉及大量数据的处理.因此在程序中许多需要排序的数据结构都使用了平衡树,这是一种高效的对全序元素的组织方式。
其次,空间。同样因为要处理大量的数据,所以对内存的管理要尤其严格,如果出现内存泄漏将是很麻烦的事情。
第三，编程风格的考虑.要尽量采用通用化的代码.因为对于一个比较大的系统来说，任何一个小的部分都应该清楚明白,便于别人阅读和修改。
基于上面三点尺悉空，在对程序的数据结构的定义和算法的实现的时候大量采用了C++的标准模板库(STL,Standard Template Library).这是基于以下的事实,关联规则的挖掘所涉及到的数据结构和基本算法都是以往的常用数据结构和算法,如向量类,集合类,快速排序算法等.而STL正是包含了这样许多通用的数据结构和基本算法的库。
例如,在STL中有一大类模板叫容器模板(container),简单的说就是包含了许多元素的类的模板,象vector,array,set等就属于容器模板.对于这些模板中的元素的访问都可以通过它们的遍历子,用完全一致的方式进行.请看下面两段程序清单：
void print(FreqSet* pSet){
FreqSet_Iter fit;
for(fit=pSet->begin();fit!=pSet->end();fit++){
printf("%s %d \n",(*fit).second.name,(*fit).second.count);
}
}
void print(Table* pTable){
Table_Iter tit;

for(tit=pTable->begin();tit!=pTable->end();tit++){
printf("%s %d \n",(*tit).name,(*tit).count);
}
}
这两个函数的作用是在调试的时候分别打印出频繁集pSet和头表pTable中的元素。
尽管pSet的类FreqSet是由map模板生成的,pTable的类Table是由multiset生成的,但对它们的元素的访问形式几乎一模一样都是利用相应的遍历子.涉及的函数名也很相似.其实,所有的容器模板都定义了函数begin()和end()代表元素列表的起始和结束.另外还有大量的具有相同名字和类似功能的函数,方便了我们对数据结构的管理。
在选择数据库访问方式的时候,用了最近比较流行的ADO方式,它比ODBC更加灵活,速度也有改善.对网络数据库的支持也很好。
对应于算法描述中所出现的各个对象分别定义了一些数据结构，仅以trans为例说明
class Trans:public std::vector<Item>
{
public:
int TID;
Trans(){TID=0;};
Trans(int t){
TID=t;
}
bool operator==(const Trans& right);
bool operator<(const Trans& right);
}
typedef Trans::iterator Trans_Iter;
Trans类对应于交易对象(Transaction).对它的定义利用了STL中的vector模板,把它定义为一个以Item为元素的向量.把它定义为向量,是因为后来需要对其中的元素进行排序,向量可以使用快速排序。
这个Trans 类身肩两任,它不仅代表事务对象,还在最后的结果输出中还被用来存放频繁集。
Trans_Iter是Trans类的遍历子.在以后使用STL容器模板定义的类都会有一个与之相对应的遍历子,不再赘述。
作者根据算法用 Vsual C++编写了程序，程序己在机器上调试通过（运行环境为： Windows Xp、Vsual C++ 6．0）．为节约篇幅，并且方便用户阅读，作者列出了部分关键程序清单
//根据条件模式库来生成用于构建条件树的频繁项
void FPTree::BuildCPTree(long p_Frequnce)
{
std::vector<std::vector<associate> >::iterator it_CPBase=m_CPBase.begin();
std::vector<associate>::iterator it_vector,it_temp1;
std::map<std::string,int> Item_include;//包含非频繁的项的集合
std::map<std::string,int>::iterator it_map,it_temp;
std::string l_string;
long Frequnce=p_Frequnce;
bool flag=true;
int l_test;
//统计每个项目的频繁度
for (;it_CPBase!=m_CPBase.end();it_CPBase++)
{
it_vector=(*it_CPBase).begin();

while (it_vector!=(*it_CPBase).end())
{
l_string=(*it_vector).chr;
l_test=(*it_vector).num;

if (Item_include.count(l_string))
{
Item_include[l_string]+=(*it_vector).num;
l_test=Item_include[l_string];
}
else
Item_include[l_string]=(*it_vector).num;

it_vector++;
}
}
//除去map中的非频繁项
bool flag1=true;
it_map=Item_include.begin();

while ((it_map!=Item_include.end())&& flag1)
{
l_string=it_map->first;
l_test=it_map->second;
if (it_map->second < Frequnce)
{
it_temp=it_map;
it_map++;
Item_include.erase(it_temp);

if (it_map==Item_include.end())
flag1=false; }
else
it_map++;
}
if (!Item_include.empty())
{

3. FP-growth算法的 java 实现源码

http://portal.acm.org/citation.cfm?id=1133907 这里有PDF下载 源代码： http://www.programsalon.com/view/downloads36/sourcecode/math/112919/fpgrowth/fptree.cpp__.htm 或 http://www.programsalon.com/downloads67/sourcecode/math/detail243513.html

4. 模式挖掘（一）：频繁项集挖掘算法Apriori和FP Tree

Apriori是最常用的频繁项集挖掘算法，其计算逻辑简单易于直观理解。在实际应用中举例，其易于从大量订单数据中获取频繁出现的组合项集，以便于输出计算单元之间的关联度，从而给组套销售、上架摆放等提供建议。下面介绍下工作中总结的知识，和需要避开的问题。

以订单数据为例。在大量的订单中，如何评价某一商品组合对的出现频繁？其组合出现的次数多于其它组合吗。若订单覆盖的商品品类丰富，那么需求量不高的品类的组合便会被淹没在快消品的组合里。所以在Apriori中有从三个不同的角度评价频繁项集，描述元素关联关系的指标：支持度、置信度、提升度。

在Apriori中有三个维度的频繁项集的指标： 支持度 、 置信度 、 提升度 。下面以二元的组合举例说明。
支持度：

置信度：

提升度：

5. 关联分析的关联分析的方法

Apriori算法是挖掘产生布尔关联规则所需频繁项集的基本算法，也是最着名的关联规则挖掘算法之一。Apriori算法就是根据有关频繁项集特性的先验知识而命名的。它使用一种称作逐层搜索的迭代方法，k—项集用于探索（k+1）—项集。首先，找出频繁1—项集的集合．记做L1，L1用于找出频繁2—项集的集合L2，再用于找出L3，如此下去，直到不能找到频繁k—项集。找每个Lk需要扫描一次数据库。
为提高按层次搜索并产生相应频繁项集的处理效率，Apriori算法利用了一个重要性质，并应用Apriori性质来帮助有效缩小频繁项集的搜索空间。
Apriori性质：一个频繁项集的任一子集也应该是频繁项集。证明根据定义，若一个项集I不满足最小支持度阈值min_sup，则I不是频繁的，即P（I）<min_sup。若增加一个项A到项集I中，则结果新项集（I∪A）也不是频繁的，在整个事务数据库中所出现的次数也不可能多于原项集I出现的次数，因此P（I∪A）<min_sup，即（I∪A）也不是频繁的。这样就可以根据逆反公理很容易地确定Apriori性质成立。
针对Apriori算法的不足，对其进行优化：
1）基于划分的方法。该算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频繁项集，然后把产生的频繁项集合并，用来生成所有可能的频繁项集，最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存，每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频繁项集至少在某一个分块中是频繁项集保证的。
上面所讨论的算法是可以高度并行的。可以把每一分块分别分配给某一个处理器生成频繁项集。产生频繁项集的每一个循环结束后．处理器之间进行通信来产生全局的候选是一项集。通常这里的通信过程是算法执行时间的主要瓶颈。而另一方面，每个独立的处理器生成频繁项集的时间也是一个瓶颈。其他的方法还有在多处理器之间共享一个杂凑树来产生频繁项集，更多关于生成频繁项集的并行化方法可以在其中找到。
2）基于Hash的方法。Park等人提出了一个高效地产生频繁项集的基于杂凑（Hash）的算法。通过实验可以发现，寻找频繁项集的主要计算是在生成频繁2—项集Lk上，Park等就是利用这个性质引入杂凑技术来改进产生频繁2—项集的方法。
3）基于采样的方法。基于前一遍扫描得到的信息，对它详细地做组合分析，可以得到一个改进的算法，其基本思想是：先使用从数据库中抽取出来的采样得到一些在整个数据库中可能成立的规则，然后对数据库的剩余部分验证这个结果。这个算法相当简单并显着地减少了FO代价，但是一个很大的缺点就是产生的结果不精确，即存在所谓的数据扭曲（Dataskew）。分布在同一页面上的数据时常是高度相关的，不能表示整个数据库中模式的分布，由此而导致的是采样5%的交易数据所花费的代价同扫描一遍数据库相近。
4）减少交易个数。减少用于未来扫描事务集的大小，基本原理就是当一个事务不包含长度为志的大项集时，则必然不包含长度为走k+1的大项集。从而可以将这些事务删除，在下一遍扫描中就可以减少要进行扫描的事务集的个数。这就是AprioriTid的基本思想。 由于Apriori方法的固有缺陷．即使进行了优化，其效率也仍然不能令人满意。2000年，Han Jiawei等人提出了基于频繁模式树（Frequent Pattern Tree，简称为FP-tree）的发现频繁模式的算法FP-growth。在FP-growth算法中，通过两次扫描事务数据库，把每个事务所包含的频繁项目按其支持度降序压缩存储到FP—tree中。在以后发现频繁模式的过程中，不需要再扫描事务数据库，而仅在FP-Tree中进行查找即可，并通过递归调用FP-growth的方法来直接产生频繁模式，因此在整个发现过程中也不需产生候选模式。该算法克服了Apriori算法中存在的问颢．在执行效率上也明显好于Apriori算法。

6. FP-tree的算法思想 举例实现算法

该算法只进行2次数据库扫描.它直接压缩数据库成一个频繁模式树,作后通过这课树生成关联规则.
算法关键步骤蚂指弯:第一步是逗碰利用事物数据库中的数据构造FP-tree;第二闷闷步是从FP_tree中挖掘频繁模式.