频繁模式挖掘

在很多时候我们会关注两个或多个对象同时出现的频率,这些相关性往往意味着某种行为特征。例如我们可以根据网站的日志找到网站中某些的网页经常被用户访问到,这些频繁性提供了用户浏览习惯的线索,有助于提高浏览的体验。其中非常典型的应用就是购物篮分析(market basket analysis)可以通过用户经常购买的物品集合找到人们经常一起买的物品集合。之后可以提取出这些物品的关联规则(association rule)比如可以发现啤酒和尿布经常会被人组合购买,从而将这些物品放在邻近的地方销售会有更好的效果。

伯努利变量

伯努利变量其实和one-hot1一样,根据标签的数量建立一个one-hot向量,X为一个定义域为{a1,a2,,am}的类别属性。可以将X建模为一个m维的随机变量X=(A1,A2,,Am)T,其中每一个Ai是一个参数为pi(代表观察到符号ai)的伯努利变量。因为是表示属性,所以一次只能取一个值。若X=ai,则X=ei,其中ei是第i个标准基向量的eiRm

(1)ei=(0,,0i1,1,0,,0mi)T

m维随机伯努利变量X的值域由m个不同的向量值{e1,e2,,em}构成,且X的概率质量函数为:

(2)P(X=ei)=f(ei)=pi

项繁集和事务标识符集

I={x1,x2,,xm}为一组称为项(item)的元素集合例如超市中售卖的所有产品的集合。集合XI称为项集。一个基数为k或者大小为k的项集称为k项集,用I(k)表示所有k项集。

T={t1,t2,,tn}为另一个所谓的事务标识符(tid)构成的集合。事务(transaction)是一个形如t,X的元组,其中tT是一个独一无二的标识符,X是一个项集。事务的集合T可以代表超市中的所有客户等。方便起见可以用t来表示一个t,X

一个二元数据库D表示了事务标识符集和项集之间的二元关系。

title:一个样例数据库

支撑集和频繁项集

数据集D的一个项集X的支撑(support),表示为sup(X,D),即D中所有包含X的事务的数目:

sup(X,D)=∣{tt,i(t)DXi(t)}∣=∣t(X)

X的相对支撑(relative support)即包含X的事务的比例:

rsup(X,D)=sup(X,D)D

它是对包含X的项的联合概率的一个估计。

关联规则

关联规则(association rule)是一个表达式X s,c Y,其中X,YIXY=。此处用XY表示项XY。规则的支撑是指XY同时出现的事务的总数:

s=sup(XY)=∣t(XY)∣=sup(XY)

规则的相对支撑(relative support)定义为XY同时出现的事务的比例,它提供了对XY的联合概率的估计:

rsup(XY)=sup(XY)D=P(XY)

一条规则的置信度(confidence)是一个事务包含X的情况下也包含Y的条件概率:

c=conf(XY)=P(YX)=P(XY)P(X)=sup(XY)sup(X)

根据规则支撑和置信度的定义,可以观察到,为了生成频繁且高置信度的关联规则,首先要枚举所有的频繁项集及其支撑值。

暴力枚举

首先要做候选生成,因为一个集合I2I个子集也就有2I个可能的频繁项集。所以可以用前缀树通过BFS或者DFS来枚举项集。

然后要完成支撑计算,这一步计算每一个候选模式X的支撑,并且判断它是否为频繁的。

title:项集格栅和基于前缀的搜索树(加粗部分)

但是这种方式的计算复杂度太大,支撑的计算在最坏的情况下需要O(ID)的时间。由于一共有O(2I)个可能的候选,暴力枚举的复杂度为O(ID2I)。这种复杂度在现实中是不可接受的。

逐层的方法:Apriori算法

根据两个依据进行剪枝:

  1. X是频繁的,则其任意子集YX也是频繁的
  2. X不是频繁的,则任意超集YX都不是频繁的




Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • Extend LLMs Context Window
  • Introduction to LLMs
  • MST-Analysis
  • 搜索技巧
  • Word 排版技巧