机器学习讲义spark-mllib第三节ver1

1、法律声明本课件包括：演示文稿，示例，代码，题库，视频和声音等，小象学院拥有完全知识产权的权利；只限于善意学习者在本课程使用，不得在课程范围外向任何第三方散播。任何其他人或机构不得盗版、复制、仿造其中的创意，我们将保留一切通过法律手段追究违反者的权利。课程详情请咨询微信公众号：小象新浪微博：ChinaHadoop基于SPARK的机器学习FP-GROWTH美团网 顾立宏序列模式挖掘简介序列模式的概念最早是由Agrawal和Srikant 提出的。动机：大型连锁超市的交易数据有一系列的用户事务数据库，每一条记录包括用户的ID，事务发生的时间和事务涉及的项目。如果能在其中挖掘涉及事务间关联关系的模式，

2、即用户几次购买行为间的联系，可以采取更有针对性的营销措施。事务数据库实例例：一个事务数据库，一个事务代表一笔交易，一个单项代表交易的商品，单项属性中的数字记录的是商品ID序列数据库一般为了方便处理，需要把数据库转化为序列数据库。方法是把用户ID相同的记录合并，有时每个事务的发生时间可以忽略，仅保持事务间的偏序关系问题定义项集(Itemset)是所有在序列数据库出现过的单项组成的集合例：对一个用户购买记录的序列数据库来说，项集包含用户购买的所有商品，一种商品就是一个单项。通常每个单项有一个唯一的ID，在数据库中记录的是单项的ID问题定义元素(Element)可表示为(x1x2xm)， xk(1

3、= k = m)为不同的单项。元素内的单项不考虑顺序关系，一般默认按照ID的字典序排列在用户事务数据库里，一个事务就是一个元素。问题定义序列(Sequence)是不同元素(Element)的有序排列，序列s可以表示为s = ，sj(1 = j = l)为序列s的元素一个序列包含的所有单项的个数称为序列的长度。长度为l的序列记为l-序列问题定义例：一条序列有3个元素，分别是（10 20），30，（40 60 70 ）；3个事务的发生时间是由前到后。这条序列是一个6-序列。问题定义数据库是由一个个交易组成，一个交易是一个item的set；支持度(共现频次)是出现该patter的交易个数频繁集合 F

4、P：其支持度超过门限 类Apriori算法该类算法基于Apriori理论，即序列模式的任一子序列也是序列模式。算法首先自底向上的根据较短的序列模式生成较长的候选序列模式，然后计算候选序列模式的支持度。典型的代表有GSP算法, spade算法等。FP-tree：出发点只关心频繁集合，所以需要一次遍历进行第一次筛选为了避免频繁去遍历数据库，需要对频繁数据进行压缩对于有交集的交易数据，是否可以充分前缀信息FP-tree1、数据预处理FP-tree1、成成树NullF : 1C : 1a : 1m : 1p : 1FP-tree1、成成树NullF : 2C : 2a : 2m : 1p : 1b :

5、 1m : 1FP-tree1、成成树NullF : 3C : 2a : 2m : 1p : 1b : 1m : 1b : 1FP-tree1、成成树NullF : 3C : 2a : 2m : 1p : 1b : 1m : 1b : 1c : 1b : 1p : 1FP-tree1、成成树NullF : 4C : 3a : 3m : 2p : 2b : 1m : 1b : 1c : 1b : 1p : 1FP-treeheader table。每个链表包含相同item节点FP-tree 建树方法1、遍历一遍数据库，筛选频繁item并计算他们的支持度， 按序排列每个交接setFP-tree 建

6、树方法2、创建根节点null的树T； 遍历每个交易数据，记为p|P,调用insert_tree（p|P, T）; 如果T的孩子N与p item一致：N的cnt+1， 否则创建node N，cnt=1, 父节点是T； 如果P非空，调用 insert_tree(P,N)FP-tree 建树方法算法需要遍历两边数据库：1、筛选频繁item2、构建fp-tree插入交易数据的复杂度是O（|交易|）FP-tree 建树方法Lemma 2.1： 给定交易数据库DB和支持度s， FP-tree包含了频繁模式挖掘的全部信息FP-tree 建树方法Lemma 2.1： 给定交易数据库DB和支持度s， FP-tr

7、ee包含了频繁模式挖掘的全部信息Lemma 2.2: 树的size bounded 频繁item数量 树的高度bounded 频繁集合的最大长度FP-tree 建树方法需要注意第一点并不是说树的size等于频繁Item数量：每个交易里的item最多贡献树里的一个node，最差的情况是交易set没有交集，树的size等于数据库size，但这种情况几乎不会出现，否则不存在频繁集合挖掘FP-tree的局限FP-tree保证了Mining数据的压缩性， 但是能保证挖掘过程的效率吗？频繁集的组合问题如何解决？FP-tree in miningProperty 3.1： 所有包含item i的Patter

8、n都能通过i的headerTable 获得FP-tree in miningNode P:条件模式基：Mining结果FP-tree in miningNode m:条件模式基：Mining结果条件FP-tree:FP-tree in miningFP-tree in miningNode b:条件模式基：Mining结果条件FP-tree:FP-tree in miningNode a:条件模式基：Mining结果序列数据库FP-tree in miningLamma 3.1： a的条件模式基中 b的支持度等于a,b的支持度Corollary 3.1 a,b是频繁模式，等价于b在条件模式基上是频繁模式根据这条性质，可以吧k-长频繁模式的挖掘转换成k个1-长频繁模式的挖掘，从而不需要产生任何候选set的组合FP-tree in miningLemma 3.1： a的条件模式基中 b的支持度等于a,b的支持