关联规则先天算法是什么?这个问题可能是我们日常学习或工作经常见到的。希望通过这个问题能让你收获颇深。下面是小编给大家带来的参考内容,让我们一起来看看吧!
理解关联规则先天算法:先天算法是第一个关联规则挖掘算法,也是最经典的算法,它利用逐层搜索的迭代方法找出数据库中项集的关系,以形成规则,其过程由连接【类矩阵运算】与剪枝【去掉那些没必要的中间结果】组成。
引用><强>理解关联规则先天算法:强>
<强>一、概念,强>
表1某超市的交易数据库
交易号TID
顾客购买的商品
交易号TID
顾客购买的商品T1
面包、奶油、牛奶、茶
T6
面包、茶T2
面包,奶油,牛奶
T7
啤酒、牛奶、茶
T3
蛋糕,牛奶
T8
面包、茶T4
牛奶、茶
T9
面包、奶油、牛奶、茶T5
面包,蛋糕,牛奶T10
面包、牛奶、茶
<强> 强> I={i1、i2…, im},是m个不同的项目的集合,每个反向称为一个<强> 强>我称为<强> 强> k的项集称为k -项集。引例中每个商品就是一个项目,项集为I={面包、啤酒、蛋糕、奶油、牛奶、茶},我的长度为6 .
<强> 强> <强> 强> T是项集我的一个子集。对应每一个交易有一个唯一标识交易号,记作TID。交易全体构成了<强> 强> D, D | |等于D中交易的个数。引例中包含10笔交易,因此| |=10。
<强> 强> X,设定计数(X ? T)为交易集D中包含X的交易的数量,则项集X的<强> 强>
支持(X)=count (X ? T)/D | |
X={面包、牛奶}出现在T1, T2, T5, T9和T10中,所以支持度为0。0.5。
<强> 强> <强> 强> SUPmin,代表了用户关心的关联规则的最低重要性。<强> SUPmin的项集称为频繁集强> k的频繁集称为k -频繁集。如果设定SUPmin为0.3,引例中{面包、牛奶}的支持度是0.5,所以是2 -频繁集。
<强> 强> <强> 强>
R: X ?Y
X ?我,Y ?我,并且X∩Y=?。表示项集X在某一交易中出现,则导致Y以某一概率也会出现。用户关心的关联规则,可以用两个标准来衡量:支持度和可信度。
R的X和Y的交易数与|D|之比。即:
support(X?Y)=count(X?Y)/|D|
X、Y同时出现的概率。关联规则的支持度等于频繁集的支持度。
R,X和Y的交易数与包含X的交易数之比。即:
confidence(X?Y)=support(X?Y)/support(X)
X,则交易包含Y的概率。一般来说,只有支持度和可信度较高的关联规则才是用户感兴趣的。
定义八:设定关联规则的最小支持度和最小可信度为SUPmin和CONFmin。规则R的支持度和可信度均不小于SUPmin和CONFmin ,则称为强关联规则。关联规则挖掘的目的就是找出强关联规则,从而指导商家的决策。
这八个定义包含了关联规则相关的几个重要基本概念,关联规则挖掘主要有两个问题:
- 找出交易数据库中所有大于或等于用户指定的最小支持度的频繁项集。
- 利用频繁项集生成所需要的关联规则,根据用户设定的最小可信度筛选出强关联规则。
目前研究人员主要针对第一个问题进行研究,找出频繁集是比较困难的,而有了频繁集再生成强关联规则就相对容易了。
二、理论基础
X是频繁集,那么它的非空子集都是频繁集
k-频繁集的项集X,X的所有k-1阶子集都肯定是频繁集,也就肯定可以找到两个k-1频繁集的项集,它们只有一项不同,且连接后等于X。这证明了通过连接k-1频繁集产生的k-候选集覆盖了k-频繁集。同时,如果k-候选集中的项集Y,包含有某个k-1阶子集不属于k-1频繁集,那么Y就不可能是频繁集,应该从候选集中裁剪掉。Apriori算法就是利用了频繁集的这个性质。
三、算法步骤:
交易ID
商品ID列表
T100
I1,I2,I5
T200
I2,I4
T300
I2,I3
T400
I1,I2,I4
T500
关联规则先天算法是什么