文档章节

weka实战004:fp-growth关联规则算法

brian_2017
 brian_2017
发布于 2017/01/17 09:47
字数 876
阅读 114
收藏 0

apriori算法的计算量太大,如果数据集略大一些,会比较慢,非常容易内存溢出。


我们可以算一下复杂度:假设样本数有N个,样本属性为M个,每个样本属性平均有K个nominal值。

1. 计算一项频繁集的时间复杂度是O(N*M*K)。

2. 假设具有最小支持度的频繁项是q个,根据它们则依次生成一项频繁集,二项频繁集,....,r项频繁集合,它们的元素数量分别是:c(q, 1), c(q,2), ...,c(q, r)。那么频繁集的数量是极大的,单机肯定不能支持,比如说,假设q=10000--其实很小,电商/零售商的数据比这大太多了--此时生成的二项频繁集合的元素数量是5千万,三项频繁集超过1000亿... 打住吧,不要再往下算了...

3. 如果transaction有100万个,这也不算多,但计算二项频繁集的关联规则就要扫描数据库100万*5千万。


所以快速算法是必须,否则搞不下去。


fp-growth就是一种快速算法,设计非常巧妙,它的流程是这样的:


1. 计算最小支持度频繁项,并按照支持度从大到小排列,形如{'f':100, 'c':84, 'd':75, 'a':43, 'q':19, ...}


2. 把transaction的所有记录,都按照最小支持度频繁项进行排列,如果没有某个频繁项,就空下来,于是,transaction就是如下的形式:

{'f', 'd', 'q', ....}  //前面是频繁项,后面是非频繁项

{'c', 'd', 'a', ...}

...


3. 然后,建立一个fp-tree,树结构:

    3.1 树的根节点是null

    3.2 把transaction的记录向树结构做插入:

        3.2.1 第一次插入{'f', 'd', 'q', ....},此时null的子节点没有'f',那就建立一个名为'f'的节点,将它的次数计为1,然后将这个transaction的id存储在节点。

        3.2.2 第二次插入{'c', 'd', 'a', ...},此时null的子节点没有'c',那就建立一个名为'f'的节点,将它的次数计为1,然后将这个transaction的id存储在节点。

        3.2.3 以此类推,继续插入其他所有记录,如果遇到节点已经存在,把节点次数+1,再把transaction加入到节点。

        3.2.4 当所有的transaction被加入到fp-tree之后,fp-tree的第一层子节点有若干个,就把所有transaction的第一个元素进行了分类。

        3.2.5 再按照这个方式,再对所有transaction的第二个元素进行分类,也就是在fp-tree的根节点的子节点进行上述3.2.1~3.2.3的操作。

        3.2.6 知道将所有transaction分到不在有符合最小支持度的元素为止。这样fp-tree就建成了。

    3.3 计算关联规则,这就是很简单啦,凡是需要计算的频繁项集合,都在fp-tree上按照支持度列出来了,从根节点挨个往下薅就行了,而且,再也不需要遍历所有的transaction了,计算量大大减少。

    3.4 fp-tree的结构,很容易拆分到并行或者分布式计算。


4. 实际上,在原作paper,构造fp-tree的方式和本文的方式略有差别,它是深度优先的,比如说,对第一个transaction是一次性建立'f'-->'d'-->'q'三个节点,然后计数,其他以此类推。本文的方式为了方便理解。








© 著作权归作者所有

brian_2017
粉丝 3
博文 61
码字总数 145216
作品 0
私信 提问
什么是关联分析?

引言: 在认识什么是关联分析之前。先了解一下关联分析能用来干什么吧: 演示样例1:例如以下是一个超市几名顾客的交易信息。 TID代表交易流水号。Items代表一次交易的商品。 我们对这个数据...

技术mix呢
2017/11/09
0
0
机器学习实战精读--------FP-growth算法

从数据集获取有趣信息的方法:常用的两种分别是频繁项集和关联规则。 FP-growth:虽然可以高效的发现频繁项集,但是不能用于发现关联规则。 FP-growth算法只需要对数据库进行两次扫描,速度要...

付炜超
2017/09/03
0
0
频繁项集与关联规则 FP-growth 的原理和实现

机器学习之手把手实现,第 2 部分 频繁项集与关联规则 FP-growth 的原理和实现 韩笑琳 2017 年 11 月 21 日发布 系列内容: 此内容是该系列 10 部分中的第 # 部分: 机器学习之手把手实现,第...

韩笑琳
2017/11/21
0
0
Spark数据挖掘-FPGrowth算法

Spark数据挖掘-FPGrowth算法 主要内容 什么是关联规则挖掘? 关联规则有哪些术语? 什么是FP-Growth算法? 1.1 FPGrowth算法 1.1.1 基本概念 关联规则挖掘的一个典型例子是购物篮分析。关联规...

clebeg
2015/11/03
688
0
Weka 中的算法名说明

数据输入和输出 WOW():查看Weka函数的参数。 Weka_control():设置Weka函数的参数。 read.arff():读Weka Attribute-Relation File Format (ARFF)格式的数据。 write.arff:将数据写入Weka ...

pior
2015/10/17
422
0

没有更多内容

加载失败,请刷新页面

加载更多

mysql概览

学习知识,首先要有一个总体的认识。以下为mysql概览 1-架构图 2-Detail csdn |简书 | 头条 | SegmentFault 思否 | 掘金 | 开源中国 |

程序员深夜写bug
今天
8
0
golang微服务框架go-micro 入门笔记2.2 micro工具之微应用利器micro web

micro web micro 功能非常强大,本文将详细阐述micro web 命令行的功能 阅读本文前你可能需要进行如下知识储备 golang分布式微服务框架go-micro 入门笔记1:搭建go-micro环境, golang微服务框架...

非正式解决方案
今天
6
0
前端——使用base64编码在页面嵌入图片

因为页面中插入一个图片都要写明图片的路径——相对路径或者绝对路径。而除了具体的网站图片的图片地址,如果是在自己电脑文件夹里的图片,当我们的HTML文件在别人电脑上打开的时候图片则由于...

被毒打的程序猿
今天
8
0
Flutter 系列之Dart语言概述

Dart语言与其他语言究竟有什么不同呢?在已有的编程语言经验的基础上,我们该如何快速上手呢?本篇文章从编程语言中最重要的组成部分,也就是基础语法与类型变量出发,一起来学习Dart吧 一、...

過愙
今天
5
0
rime设置为默认简体

转载 https://github.com/ModerRAS/ModerRAS.github.io/blob/master/_posts/2018-11-07-rime%E8%AE%BE%E7%BD%AE%E4%B8%BA%E9%BB%98%E8%AE%A4%E7%AE%80%E4%BD%93.md 写在开始 我的Arch Linux上......

zhenruyan
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部