MMD_2c_FrequentItemsets

• The market-basket model
  • 主要术语
  • 应用
  • 规模
• Association Rules
  • 概述
  • 思路
  • 核心问题
  • 计算模型
    • 数据形式
    • IO分析
    • 内存分析
  • 算法
    • 专注于二项集
    • Naive Algorithm
    • 内存计数的两种形式
• A-Prior Algorithm
  • monotonicity of frequent
  • Algo Intro
    • 概述
    • 图形
    • 延伸到k

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

这里写图片描述