1.5米的床用多大的被芯:什么是 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进行挖掘得到的. Procedure 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())
{