1 挖掘关联规则的基本概念
1.1 关联规则挖掘问题的形式化描述 设I=｛i 1 ，i 2 ，...i m ｝是由m个不同的项目组成的集合，给定一个事务数据库D，其中的每一个事务T是I中一组项目的集合，即TI，T有一个唯一的标识符TID。若项集XI且XT，则事务T包含项集X。一条关联规则就是形如X⌒Y的蕴含式，其中XI，YI，X∩Y=。关联规则XY成立的条件是:（1）它具有支持度s，即事务数据库中至少有s%的事务包含X∪Y;（2）它 具有置信度c，即在事务数据库D中包含X的事务至少有c%同时也包含Y。关联规则的挖掘问题就是在事务数据库D中找出具有用户给定的最小支持min_sup和最小置信度min_conf的关联规则。 数据挖掘研究院
1.2 常用的概念 项的集合称为项集（itemset），包含k个项的项集称为k-项集。项集的出现频率是包含项集的事务数，简称为项集的频率、支持计数或计数。项集满足最小支持度min_sup，即项集的出现频率大于或等于min_sup与D中事务总数的乘积。如果项集满足最小支持度，则称它为频繁项集（frequent itemset）。频繁k-项集的集合通常记作L k 。1.3 挖掘关联规则问题可以分解为以下两个子问题 （1）找出所有频繁项集:根据定义，这些项集出现的频繁性至少和预定义的最小支计数一样;（2）频繁项集产生强关联规则:根据定义，这些规则必须满足最小支持度和最小置信度。 数据挖掘研究院
2 Apriori算法介绍 数据挖掘研究院
在关联规则挖掘中最著名的算法便是Apriori算法。Apriori算法主要工作在于寻找频繁项集。通过先计算所有的候选1-项集的集合C 1 。找出所有的频繁1-项集L 1 。然后根据频繁1-项集L 1 确定候选2-项集的集合C 2 。从C 2 中找出所有的频繁2-项集L 2 。再根据频繁2-项集L 2 确定候选3-项集的集合C 3 。从C 3 中找出所有的频繁3-项集L 3 。如此下去直到不再有候选项集。算法:Apriori
输入:数据库D;最小支持度阈值min_sup。输出:Result=D中的所有频繁项集。方法:
Result:=｛｝;k:=1;
C 1 :=所有的1-项集;
While（Ck）do 为每一个Ck中的项集生成一个计数器; for（i=1;i;i++） begin
对第i个记录T支持的第一个Ck中的项集，其计数器加1; end;
Lk:=Ck中满足min_sup的全体项集; Result:=Result∪Lk;
Ck+1:=所有的（k+1）-项集中满足其k-子集都在Lk里的全体; k:=k+1;enddo
