lptree
最近在男票的要求下看了下lptree，lptree用于找频繁模式，下文记录下自己对lptree的理解，用于下次接着学习(未完成)。
频繁模式定义
定义：若a，b都是集合中的元素，若a，b一起出现的次数大于阈值，则认为a，b是一个频繁模式。如在所有商品集合中，裙子和衬衫一起买的次数大于阈值，则认为｛裙子，衬衫｝是一个频繁模式。
举例说明lptree作用
给定一个数据库D，D包含每条购买记录T，I是商品集合，I={i1,i2,……},存在一个阈值minsup,出现次数大于等于minsup的I的子集即为频繁模式。
Example:
D包含以下购买记录
T1={i1,i2,i5}
T2={i3,i5,i4}
T3={i1,i2,i4}
T4={i3,i6}
I={i1,i2,i3,i4,i5,i6}，设minsup=2,
则｛i1｝出现2次，等于minsup，｛i1,i2｝出现2次为频繁模式，等等。
LPtree算法的目的即为输出所有频繁模式。
LPtree的数据结构组成
headerlist:包括每个商品名称，每个商品出现次数，和节点链接
lpn:一条购买记录对应一个lpn，lpn存储每条购买记录的频繁项信息和父亲节点
bnl：包含父子关系，即含有分支的节点和他们的孩子节点信息
数据结构具体介绍
lpn: lpn={father,<i1,sup,l,b>,<i2,sup,l,b>,<i3,sup,l,b>……}
其中father为父亲节点，i1为该购买记录第一个商品名称，sup为该商品出现次数，
l为该商品下一次出现的位置，b用来标志是否有孩子节点
bnl: bnl用于管理父子关系，bnl={<Pi,j->Pm,n,Pl,k>,<Ps,d->Pf,g >……}，
其中Pi,j即为第i个lpn的第j个节点，Pi,j->Pm,n,Pl,k即为Pi,j有两个孩子节点，分别为Pm,n,Pl,k
headerlist: headerlist={<i1,3,p1,1>……}，即为i3商品出现了3次，
第一次出现为p1,1位置，即第一个lpn的第一个节点，并且headerlist的排序按照出现次数从大到小排列。
构造方法
1.首先读取购买记录，得到所有的商品｛a,b,c,d,e,f,g,h｝及他们的出现次数，
因为h的出现次数为2，小于minsup，则直接删除，其他的按照出现次数从大到小组成headerlist，
此时headerlist的节点链接为空。
2.将所有的购买记录按照headerlist排序，
并删除掉headerlist中不存在的商品（即出现次数小于minsup的商品）
3.遍历排序后的购买记录，创建根节点，并根据第一条购买记录创建第一个lpn，
即为上图所示的LPN1，大小为（该记录购买商品个数+1），LPN1的父亲节点指向根，
并在bnl中插入一条记录Proot->P1,1，此时根据lpn={father,
<i1,sup,l,b>,<i2,sup,l,b>,<i3,sup,l,b>……}，lpn中每个商品节点的sup都为1，
l即节点链接为空，b即孩子节点标志为false。同时更新headerlist的nodelink部分。
4.接着处理第二条记录，共用重合的e节点，并在e节点后面创建孩子节点，产生LPN2，
此时e的sup+1,同时相应的更新BNL和headelist及原有的LPN.
通过上述方法，遍历完所有的购买记录及构造成完整的lptree。
注意：若之前插入购买记录｛e,c｝,当有记录｛e,c,f｝插入时，不需要增加新的lpn，
只需产生一个新的更大的lpn，把原来的内容迁移过来再在下面插入f节点。
或者如果使用的是可变长数组，则在原来的基础上向下添加。
寻找频繁模式的方法lpgrowth
构造好lptree后，则需要根据lptree通过lpgrowth算法找到所有的频繁模式，伪代码如下：
