MMD_2c_FrequentItemsets

The market-basket model

主要术语

items: things sold in supermarket buskets:each of which is s small set of items support:s, it means at least s baskets which contain sets of items(frequent items) in all baskets. confidence: (i,j) –> (i,j,k).后者比上前者的概率,可以认为是前者发生后后者发生的条件概率。

应用

规模

  • WalMart有100,000种商品,有1000,000,000个篮子。
  • Web有billion级的单词,有billion级的页面。

baskets 不能包含太多的items,因为每个basket的时间与其包含的item是quadratic的

Association Rules

概述

思路

  1. 先找满足概率大于cs的频繁项集C1
  2. 在从C1中删减元素E,使得删减后的集合C2满足概率大于s的要求
  3. 那么,C2->E就是一项满足支持度s与可信度c的规则

核心问题

如果找到满足概率大于p的所有频繁项集呢?

A:对每一个bucket遍历所有可能的pair。

思路: 1. 需要的频繁项集不会太多,所以一般专注于最容易出现的二项集合。 2. 注意单个basket不能有太多的item,否则算法对于单个basket的迭代时间是quartic的,但是可以有很多个basket。

计算模型

数据形式

IO分析

内存分析

算法

专注于二项集

Naive Algorithm

内存计数的两种形式

(i,j,n)的计数方式 还有(n)的计数方式

A-Prior Algorithm

monotonicity of frequent

sets only can be frequent only if the subsets are frequent.

So, at first, we find frequent items in 1, then find pairs in 2 using the information before.

Algo Intro

概述

图形

延伸到k

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏SimpleAI

令人困惑的TensorFlow【1】

我叫 Jacob,是 Google AI Resident 项目的研究学者。我是在 2017 年夏天加入该项目的,尽管已经拥有了丰富的编程经验,并且对机器学习的...

702
来自专栏计算机视觉与深度学习基础

HDU4405

以前不是太会求期望的题目,就是做出来的要是靠一知半解的YY出来,昨天多校又碰到了,于是彻底搞了一把,现在算是撸通了。 具体学习资料查看 http://blog....

1769
来自专栏我和未来有约会

[Silverlight动画]转向行为 - 避开行为

避开行为与寻找行为彻底相反。实际上,除了代码最后一行用相减代替了相加以外,其它都一样。 public void flee(Vector2D target) ...

1797
来自专栏极客猴

Django 学习笔记之模型高级用法(下)

除了抽象模型,在模型中定义的字段都会成为表中的列。如果我们需要给模型指定其他一些信息,例如排序方式、数据库表名等,就需要用到 Meta。Meta 是一个可选的类...

752
来自专栏漫漫深度学习路

pytorch学习笔记(六):自定义Datasets

什么是Datasets: 在输入流水线中,我们看到准备数据的代码是这么写的data = datasets.CIFAR10("./data/", transfor...

3407
来自专栏Python小屋

使用Python获取Excel文件中单元格公式的计算结果

假设有如下Excel文件,其中第二个WorkSheet中数据如下: ? 其中D列为公式,现在要求输出该列公式计算的数值结果,代码如下: ? 代码运行结果: ?...

2866
来自专栏瓜大三哥

基于FPGA的非线性滤波器(四)

基于FPGA的非线性滤波器(四) 之并行全比较排序模块设计 2.sort_2d模块设计 对于二维运算,采用同样的思路来处理,整个计算步骤如下: (1)计算一维行...

2069
来自专栏漫漫深度学习路

pytorch学习笔记(十三):backward过程的底层实现解析

博主水平有限,如有错误,请不吝指出。 pytorch源码注释,欢迎 pr,提 issue 和 star 当我们使用 pytorch 的 python 的接口编写...

32110
来自专栏ChaMd5安全团队

小姐姐教你做CTF逆向题:利用符号执行技术和约束求解器

0x00 前言 在CTF比赛中,逆向类题目常常以考察选手的逆向分析能力、算法分析能力角度出发,通过还原程序中的算法逻辑,从而获取flag。但是如果可以在程序执行...

75112
来自专栏Python中文社区

Python文档精要研读系列:hash函数

hash(object) Return the hash value of the object (if it has one). Hash values ar...

20910

扫码关注云+社区