Tag Archives | frequent pattern

Data Ming 笔记频繁项之FP-growth

一、概述

Apriori 算法一个Breadth-first (i.e., level-wise) search,需要产生大量的candidates的项集。而FPGrowth Approach (J. Han, J. Pei, and Y. Yin, SIGMOD’ 00)是一个Depth-first search,可以避免产生大量的项集。
主要思路是:从局部的频繁项中从短的频繁项得到长的频繁项。
比如,在数据集DB中发现,“abc”是一个频繁项,即DB|abc,考察含有该频繁项的子项时发现d是该频繁项中的一个局部频繁项,则abcd也是一个频繁项。

二、算法步骤

基本思想 (分治):用FP-tree递归增长频繁集
方法
  1. 对每个项,生成它的 条件模式库, 然后是它的 条件 FP-tree
  2. 每个新生成的条件FP-tree,重复这个步骤
  3. 直到结果FP-tree[......]

阅读全文

Tags: , ,

Comments { 0 }

Data Mining 笔记FP高级

关于频繁项的高级探索。

@todo 完整笔记

 

[caption id="attachment_931" align="alignnone" width="763"]Pattern Mining: A Road Map Pattern Mining: A Road Map[/caption]

[slideonline id=9179]

Tags: , ,

Comments { 0 }

Data Mining 笔记关联规则之Apriori算法笔记

一、前言
上篇文章中对频繁项和关联规则做了一般性描述。知道关联规则的挖掘其实就是从事务、关系数据中发现频繁项集、再考察项之间的关联。
项集itemset生成是一个很费力力气的事情,如果事务中有d项待考察,则理论上会有2^d个candidate itemset。
generate-itemset

实际上并不是并不是所有的都candidate itemsets都需要考察。因为频繁项集有这样的性质

  • ?性质1:频繁项集的子集必为频繁项集。
  • ?性质2:非频繁项集的超集一定是非频繁的。

?二、Apriori算法

Apriori算法运用性质1,通过已知的频繁项集构成长度更大的项集,并将其称为潜在频繁项集。潜在频繁k项集的集合Ck?是指由有可能成为频繁k项集的项集组成的集合。以后只需计算潜在频繁项集的支持度,而不必计算所有不同项集的支持度,因此在一定程度上减少了计算量。

[......]

阅读全文

Tags: , , ,

Comments { 1 }

Data Mining 笔记频繁项&关联规则

一、关联规则介绍

关联规则反映一个事物与其它事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系,那么,其中一个事物发生就能够预测与它相关联的其它事物的发生。经典范例:购物篮(Market Basket)分析。通过发现顾客放入购物篮中商品之间的同现关系来分析顾客的购买习惯,从而实现商品的交叉销售和推荐。?

Implication means co-occurrence, not causality!蕴含意味着同现而非因果关系!

二、频繁项Frequent Itemset 术语

先看Frequent Itemset 频繁项集术语解释:
  • 事务集合:所有事务集合T={t1,t2,…, tN} ,如用户的购买日志。
  • 项集itemset:一个活多个项的集合? ? ? ? ? ? ?如购买日志中用户可以买的商品的集合。
  • k-items[......]

阅读全文

Tags: , , ,

Comments { 0 }