丹追兵_新浪博客

随机数发生器的基本原理：下一个随机数 = 数学函数(前若干个随机数)

评价一个随机数发生器的好坏：

线性同余发生器(Linear Congruential Generator)

目前主流的随机数发生器之一，1951年由Lehmer提出。从名字可以看出公式，即一个线性函数再取余：

第i个随机数 = (a*第i-1个随机数 + c)(mod m)

随机数的取值范围是[0,m-1]，将其除以m，就可以得到[0,1)之间的随机数。

全周期定理：满足以下条件时随机数发生序列具有全周期性质

本文所采用图片均来自清华大学计算机系王建勇老师的课程《数据挖掘：原理与算法》

http://dbgroup.cs.tsinghua.edu.cn/wangjy/DM/DataMining.html

(Han, Pei and Yin @SIGMOD'00)

Apriori算法的一个主要瓶颈在于，为了获得较长的频繁模式，需要生成大量的候选短频繁模式。FP-Growth算法是针对这个瓶颈提出来的全新的一种算法模式。目前，在数据挖掘领域，Apriori和FP-Growth算法的引用次数均位列三甲。

FP的全称是Frequent Pattern，在算法中使用了一种称为频繁模式树（Frequent Pattern Tree）的数据结构。FP-tree是一种特殊的前缀树，由频繁项头表和项前缀树构成。所谓前缀树，是一种存储候选项集的数据结构，树的分支用项名标识，树的节点存储后缀项，路径表示项集。

FP-tree的生成方法：