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

法律

本课件包括：演示文稿，示例，代码，题库，和声音等，小象学院拥有完全知识的权利；只限于善意学习者在本课程使用，不得在课程范围外向任何第散播。任何其他人或机构不得盗版、创意，

保留一切通过法律、仿造其中的者的权利。

课程咨询：小象：ChinaHadoop互联网新技术教育领航者基于SPARK的机器学习——FP-GROWTH美团网顾互联网新技术教育领航者序列模式挖掘简介序列模式的概念最早是由Agrawal和Srikant

。：大型连锁超市的交易数据有一系列的用户事务数据库，每一条记录包括用户的ID，事务发生的时间和事务涉及的项目。如果能在其中挖掘涉及事务间关联关系的模式，即用户几次

行为间的联系，可以采取更有针对性的

措施。互联网新技术教育领航者事务数据库实例例：一个事务数据库，一个事务代表一笔交易，一个单项代表交易的商品，单项属性中的数字

记录的是商品ID互联网新技术教育领航者序列数据库一般为了方便处理，需要把数据库转化为序列数据库。方法是把用户ID相同的记录合并，有时每个事务的发

生时间可以忽略，仅保持事务间的偏序关系互联网新技术教育领航者问题定义项集(Itemset)是所有在序列数据库出现过的单项组成的集合例：对一个用户

记录的序列数据库来说，项集包含用户的所有商品，一种商品就是一个单项。通常每个单项有一个唯一的ID，在数据库中记录的是单项的ID互联网新技术教育领航者问题定义元素(Element)可表示为(x1x2…xm)，xk(1<=k<=m)为不同的单项。元素内的单项不考虑顺序关系，一般默认按照ID的字典序排列．在用户事务数据库里，一个事务就是一个元素。互联网新技术教育领航者问题定义序列(Sequence)是不同元素(Element)的有序排列，序列s可以表示为s=<s1s2…sl>，sj(1<=j<=l)为序列s的元素一个序列包含的所有单项的个数称为序列的长度。长度为l的序列记为l-序列互联网新技术教育领航者问题定义例：一条序列<(10,20)30(40,60,70)>有3个元素，分别是（10

20），30，（40

60 70

）；3个事务的发生时间是由前到后。这条序列是一个6-序列。互联网新技术教育领航者问题定义数据库是由一个个交易组成，一个交易是一个item的set；支持度(共现频次)是出现该patter的交易个数频繁集合FP：其支持度超过门限互联网新技术教育领航者类Apriori算法该类算法基于Apriori理论，即序列模式的任一子序列也是序列模式。算法首先自底向上的根据较短的序列模式生成较长的候选序列模式，然后计算候选序列模式的支持度。典型的代表有GSP算法,spade算法等。互联网新技术教育领航者FP-tree：出发点只关心频繁集合，所以需要一次遍历进行第一次筛选为了避免频繁去遍历数据库，需要对频繁数据进行压缩对于有交集的交易数据，是否可以充分前缀信息互联网新技术教育领航者FP-tree1、数据预处理互联网新技术教育领航者FP-tree1、成成树NullF

:

1C

:

1a

:

1m

:

1p

:

1互联网新技术教育领航者FP-tree1、成成树NullF

:

2C

:

2a:

2m

:

1p

:

1b

:

1m

:

1互联网新技术教育领航者FP-tree1、成成树NullF

:

3C

:

2a:

2m

:

1p

:

1b

:

1m

:

1b

:

1互联网新技术教育领航者FP-tree1、成成树NullF

:

3C

:

2a:

2m

:

1p

:

1b

:

1m

:

1b

:

1c

:

1b

:

1p

:

1互联网新技术教育领航者FP-tree1、成成树NullF

:

4C

:

3a:

3m

:

2p

:

2b

:

1m

:

1b

:

1c

:

1b

:

1p

:

1互联网新技术教育领航者FP-treeheader

table。每个链表包含相同item节点互联网新技术教育领航者FP-tree

建树方法1、遍历一遍数据库，筛选频繁item并计算他们的支持度，按序排列每个交接set互联网新技术教育领航者FP-tree

建树方法，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-tree包含了频繁模式挖掘的全部信息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的Pattern都能通过i的headerTable

获得互联网新技术教育领航者FP-tree

in

miningNodeP:条件模式基：Mining结果互联网新技术教育领航者FP-tree

in

miningNodem:条件模式基：条件FP-tree:Mining结果互联网新技术教育领航者FP-tree

in

mining互联网新技术教育领航者FP-tree

in

miningNodeb:条件模式基：条件FP-tree:Mining结果互联网新技术教育领航者FP-tree

in

miningNodea:条件模式基：Mining结果互联网新技术教育领航者序列数据库互联网新技术教育领航者FP-tree

in

miningLamma

3.1：a的条件模式基中b的支持度等于a,b的支持度Corollary

3.1a,b是频繁模式，等价于b在条件模式基上是频繁模式根据这条性质，可以吧k-长频繁模式的挖掘转换成k个1-长频繁模式的挖掘，从而不需要产生任何候选set的组合互联网新技术教育领航者FP-tree

in

miningLemma

3.1：a的条件模式基中b的支持度等于a,b的