本文最后更新于720 天前,其中的信息可能已经过时,如有错误请发送邮件到big_fw@foxmail.com
Apriori-基于频繁项集的数据关联规则挖掘算法
Apriori-基于频繁项集的数据关联规则挖掘算法
算法目的
已知:数据集,其中每一个对应个变量(即个统计指标),如果该变量的取值满足设定的条件,则在该变量上可转化为分类数据或示性数据。
待求:数据集的频繁项集和关联规则(用于分析原始数据和推断新的数据)
算法文字步骤
第一步:输入数据集。
第二步:确定数据集中所包含的项集,并具体化到每一个数据点(即每一个中所包含的变量示性情况)。
第三步:进行第一次迭代,把每个项集中的项目单独扫描统计(即某个项在多少个数据点中出现),将每个项都作为候选项集的成员,并计算每个项的支持度。
第四步:设定最小支持度,根据候选项集的成员、支持度和最小支持度,采用扫描过滤的方式获得候选项集,候选项集需满足所有真子集的支持度都最小支持度。
第五步:保持最小支持度不变,重复进行第四步,直到没有办法再合并(即候选项集无法满足条件),形成新的候选项集,此时输出最终的频繁项集结果,并给出关联规则。
算法计算步骤
第一步:输入数据集,设定个变量的示性规则(项集),得到如下的矩阵形式:
其中是第个数据点关于第个变量的示性值,可以用来表示,即表示不满足这个变量的条件,表示满足(这种情况常见于数值型数据分类化)如果第个变量已经是分类变量,则可以用分类变量自带的分类来表示.
第二步:根据原始项集情况,生成候选项集,并设定最小支持度为。即对所有项集中的所有项进行扫描,单独统计,形成下面的列表形式:
第三步:根据最小支持度,进行过滤,并合并过滤后的各项,得到候选项集,候选项集需满足所有真子集的支持度都最小支持度(如过滤后保留了项1、项3等,合并项1和项3得到候选项集中的一个项目项1,项3,并检查该项目所有真子集项1、项3、项1,项3的支持度是否都最小支持度。
第四步:保持最小支持度不变,重复第三步的操作,一直采用这种方式合并,直到无法进一步合并(即合并后的项集中的所有元素都不能满足生成条件“所有真子集的支持度都最小支持度”)
第五步:输出第四步中最终得到的项集,即为频繁项集。
第六步:从频繁项集中挖掘关联规则,按下面两个环节进行:
1. 对于每个频繁项集,产生其所有的非空子集。
2. 对于的每个非空子集,如果(表示最小置信度),则输出关联规则。
第七步:循环第六步直到挖掘出所有需要的关联规则,并输出最终的结果。