听从建议，看了下Poisson Process，发现第N个人的等待时间T的概率分布就是Gamma Distribution……等待时间的Expectation就是n/lamda.... 之后没瞅数据脑残的就开始code，用Gradient Descent求出了LMS情况下的Lamda……果然效果很烂。。。回去瞅了一眼数据，n和T之间的关系非常惨淡，至少不是一个简单的反比函数能解决的。。。
略脑残，就当练习code了…………
Towards Proximity Pattern Mining in Large Graphs
实际上，proximity pattern是itemset和graph之间的一个折衷。再求frequent itemset的时候，各个transaction之间是没有什么structure上的联系的。而frequent subgraph的定义不够elastic，这样可能会忽略一些可能有用的pattern，同时也使mining过程变得困难，例如子图同构测试就是个瓶颈。proximity pattern是这两者之间的一个新的pattern种类。它是attributed graph 上的一种pattern，大概可以理解这种图是transaction之间有了边的一种图，每个transaction是图中的node，每个node中有很多items，即attributes。
Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach∗
FP-Tree是一个frequent itemset mining的算法。首先来说一下frequent itemset的相关内容。
Frequent itemset就是说在一个transaction数据库中(每个transaction由若干个item组成)，我们要找出现频率大于某个人们所期望的值e的itemset。
通常的方法有Apriori这类的，它需要按一定规律去产生candidate itemset，然后挨个检验看是不是frequent的。这种方法显然比较耗时，虽然在这个过程中那个“一定规律”起到了比较强的搜索空间的剪枝作用。同时重复性扫描数据库和进行pattern matching的工作也是十分耗时的。这里要说一下这个“一定规律”，他一般都是基于以下这个observation：
Itemset A是itemset B的子集，那么如果A是infrequent的，那么B也是infrequent的，这个很显然，用反证法非常容易就能证明。利用这一点就可以砍掉很多itemset了。
然而，重新分析我们所面临的问题，我们不难发现，我们所关心的信息只有frequency，那么有没有什么方法可以对数据库进行一定的预处理，忽略一些无关信息，利用某种数据结构来对整个数据库中的数据重新存储，以达到减少存储空间，同时还能便于mining frequent itemset呢？
一些基本的想法可以很轻松的想到：
基于以上，可以发现，一个前缀树prefix-tree是个好选择，如果我们将每个transaction中的items按照之前扫描数据库时获得的item频降序的顺序用来代表这个transaction，那么就可以用prefix-tree进行存储了。过程如下：
关于insert(string, T)，这是一个递归函数
为了便于表述，我们将string定义为这个形式(p|P)，p是string的首个item，P是剩余的items的string，我们将p和T的children做比较，如果
(1) 存在T.child.itemname= p.itemname，给T.child.count加一，那么调用insert(P, T.child)
(2) 否则，我们给T新建一个child，并让此child.itemname = p，child.count=1， 然后调用insert(P, T.child)
直到string为空。
这样就将所有数据及频率存储在这个prefix-tree中了。
下面将要讲述如何进行mining。
实际上在上面的建树过程中，还有一个小细节没有做，那就是在新生成一个node的时候，都要将以前的和这个node代表相同item的nodes链接起来，也就是，树中的代表相同item的nodes会形成一个链表，这些链表的表头存在一起，并且是按照这个表所链接的item的频率的降序顺序排列的。
这么做的原因是为了mine的工作。
下面简单叙述mine的过程：
假定threshold是3，从链表表头的表的最后一位的那个item开始，比如这个item是p，此时实际上我们要找的是以p为后缀的frequent pattern。显然p自身肯定就是一个frequent pattern了，否则它不会被留到现在。然后我们找寻树中从root到各个node.itemname=p的path，对于这个path我们复制下来重新处理一下。因为现在要找的是以p作为suffix的frequent pattern，所以之前的nodes的count要进行修正，对于任意获得的path上的node，他的count都应该和这个path上的代表p的node的count一致。这个很显然，比如一条从root到item为p的node的path上有a，它的count是4，而这条path上代表p的node.count =2，那么显然a只同时和p出现了2次。。。举例来说，有如下3条path{a5,b5,d3,p3} {c3,b2,p1} {d4,b2,p2},修改后的path应为{ a3,b3,d3 } {c1,b1}和{d2,b2}，此时我们将这3个path可以视为三个transaction，然后构建一个FP-subtree出来，然后重复上述工作进行mine。在mine这棵FP子树的时候，c的frequency不满足threshold会被删掉，最后frequency最小的是a，frequency是3，显然a是一个合格的pattern，而实际上，我们获得的总体的那个frequenct pattern，是{ap}，因为这个是以p为pattern suffix下的subtree。如此递归下去即可。
然后接着从链表表头的表的倒数第二个item开始mine，比如这个item是 a，此时要挖掘的就是以a为pattern suffix的pattern，此时p显然也就不用考虑了，因为任何一条树中的path，其中点的排列顺序都是一致的，是按照这个item的总频率降序排列的，对于a的挖掘，其过程和前面一样。
有一种特殊的FP-tree形态是可以简化mine的过程的，如图：
如图(a)所示，这个tree的从root到c:7是一条简单的单链，这样就可以更加轻松地处理了，处理方式是将这个tree分成两棵树，第一棵树如(b)所示，由于是单链，我们只需要枚举abc的排列组合即可，组合出的pattern的frequency显然等于pattern中的item的最小frequency。我们称这部分获得的frequent pattern的集合为A。另一部分如图(c)所示，我们给它建了一个伪root，然后正常进行挖掘，得到的frequent pattern为集合B。此时还有一部分frequent pattern还没有考虑，这部分可以用A X B来获得，也是很显然的，frequency等于X积时较小的frequency部分的frequency。
l 不确定图：一个边的存在性和点得存在性都被赋予了概率值的图
l Support of (S): 图集合D中包含特定图S的图的比例
l Frequent定义：一个图S是frequent的，需满足：support(S) ≥ϕ
l ϕ-frequent probability: 某特定图S是不确定图集合D中的图的子图的比例≥ϕ的概率，即
Pr(support(S) ≥ϕ)
l 问题定义：
给定一个不确定图集合D和0< ϕ, τ<1，找到所有的图S，S满足：
Pr(support(S) ≥ϕ) ≥τ
l 所有子图都只考虑联通的
l Labeled graph：每个点都给予标记，当做不同的点，对于一个n个点得标记图，可能存在2^(n*(n-1)/2)中构造。
l #P-hard：http://www.jiahenglu.net/blog/5.html此文介绍的不错，作者是人大的一个大牛貌似，再就是wikipedia了.NP问题常常是问有没有，而#P是问有多少，所以#P更复杂。引用一句“#P-complete 问题在不确定数据管理需要计算概率的时候是非常常见的”
l 一个不确定图G，它可以被看做一个随机变量，有很多可能取值，这些值得类型就是确定图。所以G在这些可能取值的确定图的集合上就有一个概率分布(probability distribution)。
l 在上一篇Dr.Zou的论文中讨论的是expected support(S)
l 近期有许多不确定itemset的挖掘算法，但是在针对某个item判断是否frequent的问题上，是可以多项式时间完成，但是计算某个graph的ϕ-frequent probability却是#P-hard的。
l 想要找到所有Pr(support(S) ≥ϕ) ≥τ的图，就找到所有可能的子图S，挨个判断它是否满足Pr(support(S) ≥ϕ) ≥τ，这个枚举所有图的过程就用那个minimum DFS code tree来做就可以。判断某图是否Pr(support(S) ≥ϕ) ≥τ过程由于是#P-hard，所以找一个渐进算法来干掉它。
l 这个渐进算法能做到如下程度：
n 找到所有Pr(support(S) ≥ϕ) ≥τ的子图
n 同时容忍混入一些τ-ε≤Pr(support(S) ≥ϕ) <τ的子图
