apriori算法及其改进算法(编辑修改稿)

apriori算法及其改进算法(编辑修改稿)内容摘要：

科学系开放性实验结题报告 6 和最小支持度阈值 .置信度 和支持度大于相应阈值的规则称为强关联规则 , 反之称为弱关联规则 . 发现关联规则的任务就是从数据库中发现 那些 置信度 、支持度大小等于给定值的强壮规则 . 基于上述概念，我们可以很容易得到一些基本结论 : (1) K维数据项集 XK是频繁项集的必要条件是它所有 K1维子项集也为频繁项集， 记为 XK1 (2)如果 K 维数据项集 XK的任意一个 K1 维子集 XK1，不是频繁项集，则 K维数据项集 XK本身也不是最大数据项集。 (3) XK是 K 维频繁项集，如果所有 K1维 频繁项集集合 XK1中包含 XK 的 K1维子项集的个数小于 K，则 XK不可能是 K维最大频繁数据项集。 证明 : 很明显，数据项集 XK1:的 K1 维子项集的个数为 K1。 如果高频繁数据项集XK1，中包含 XK的 k，则存在 XK的 K1 维子项集不是频繁数据项集，由结论 (2)知 K 维数据项集本身也不是高频繁数据项集。 关联规则挖掘举例 一个超级市场的销售系统记录了顾客购物的情况。 表 31中记录了 5 个顾客的购物单。 表 31 记录号 所购物品清单 1 啤酒、尿布，婴儿爽身粉，面包，雨伞 2 尿布，婴儿爽身粉 3 啤酒、尿布，牛奶 4 尿布，啤酒，洗衣粉 5 啤酒，牛奶，可乐饮料 陕西理工学院数学与计算机科学系开放性实验结题报告 7 超市经理想知道商品之间的关联，要求列出那些同时购买的、且支持度≥40% （即在 5 行中至少出现两次）的商品名称。 KDD 系统通过特定算法（例如著名的 Apriori(验证 )算法及或改进算法）多次扫描数据库，依次得出如表 2 和表 3。 其中支持度 2/5 的项 ,如单项的 {面包 }， {雨伞 }和 双项中的 {尿布，牛奶 }等等已经略去，三项统计为空，其中只有 {啤酒，尿布 ,牛奶 }出现了一次 (表 31中 3 号记录 )，支持度小于 40%,略去。 单项统计 支持度 {啤酒 } 4/5 {尿布 } 4/5 {婴儿爽身粉 } 2/5 {牛奶 } 2/5 表 32 表 33 从单项统计中看出 80%的顾客买了啤酒、 80%的顾客买了尿布。 从双项统计中看出， 60%的顾客同时买了啤酒和尿布， 40%的顾客买了啤酒和牛奶， 40%的顾客买了尿布和爽身粉。 还可观察到买了啤酒顾客中又买了尿布的占 {啤酒，尿布 }/{啤酒 }=75% (称为置信度 )。 于是可得出下列六条规则 ,其中： s为支持度， c 为置信度。 R1：啤酒→尿布 ,S=60%， C=R2：尿布→啤酒 ,S=60%， C=R3：牛奶→啤酒 , S=40%， C=R4：啤酒→牛奶 , S=40%， C=R5：尿布→爽身粉。 S=40%， C=R6：婴儿爽身粉→尿布。 S=40%， C=双项统计 支持度 {啤酒，尿布 } 3/5 {啤酒，牛奶 } 2/5 {尿布，婴儿爽身粉 } 2/5 陕西理工学院数学与计算机科学系开放性实验结题报告 8 KDD 规则反映了物品之间的表面联系，不一定是现实世界的因果关系。 规则是死的，人是活的，运用之妙成乎于人。 例如， R6“婴儿爽身粉→尿布”有很高的置信度，是合理可理解的， R3有很高的置信度将提示进一 步的调查分析，本例中是因为训练资料太少引起的失真。 关联规则问题的分解 关联规则挖掘问题可分解为以下两个子问题 : 1. 找出事务数据库 D 中所有大于等于用户指定最小支持度的项目集 (itemset). 具有最小支持度的项目集称为最大项目集 .项目集的支持度指包含该项目集的数目 . 2. 利用最大项目集生成所需要的关联规则 对 每 一 最 大 项 目 集 A, 找到 A 的 所 有 非 空 子 集 a, 如 果 比 率support(A)/support(a)=minconfidence,就生 成关联规则 a=(Aa).support(A)/support(a) 即规则 a=(Aa)的 置信度 . 事实上 ,挖掘关联规则的整个执行过程中第一个子问题是核心问题 .当找到所有的最大项目集后 ,相应的关联规则将很容易生成 .在本文中将对关联规则的第一个问题进行探讨、研究。 4 Apriori 算法的描述 Apriori 算法的说明 在 Apriori 算法中 ,寻找最大项目集的基本思想是 : 算法需要对数据集进行多步处理 .第一步 ,简单统计所有含一个元素项目集出现的频率 ,并找出那些不小于最小支持度的项目集 , 即一维最大项目集 . 从第二步开始循环处理直到再没陕西理工学院数学与计算机科学系开放性实验结题报告 9 有最大项目集生成 . 循 环过程是 : 第 k 步中 , 根据第 k1 步生成的 (k1)维最大项目集产生 k 维侯选项目集 , 然后对数据库进行搜索 , 得到侯选项目集的项集支持度 , 与最小支持度比较 , 从而找到 k维最大项目集 . 为方便后文叙述，现约定如下 : ,每个项目用 TID,item来标识 , 这里 TID 表示相应事务的标识符 , item 则表示项目名称 . size. 当项目集的 size=k时 , 称该项目集为 kitemset(k 维项目集 ). 下文中遇到的以下符号 ,分别代表相应的内容 kitemset k 维项目集 Lk 具有最小支持度的最大 kitemset Ck 侯选的 kitemsets(潜在的最大项目集 ) Apriori 算法的描述 Apriori 算法的第一步是简单统计所有含一个元素的项集出现的频率 ,来决定最大的一维项目集 .在第 k步 ,分两个阶段 ,首先用一函数 sc_candidate(候选 ),通过第 (k1)步中生成的最大项目集 Lk1来生成侯选项目集 Ck. 然后搜索数据库计算侯选项目集 Ck的支持度 . 为了更快速地计算 Ck中项目的支持度 , 文 中使用函数 count_support 计算支持度 . Apriori 算法描述如下 (1) C1={candidate1itemsets}。 (2) L1={c∈ C1|≥ minsupport}。 (3) For(k=2,Lk1≠Φ ,k++) //直到不能再生成最大项目集为止 陕西理工学院数学与计算机科学系开放性实验结题报告 10 (4) Ck=sc_candidate(Lk1)。 //生成含 k个元素的侯选项目集 (5) for all transactions t∈ D //办理处理 (6) Ct=count_support(Ck,t)。 //包含在事务 t中的侯选项目集 (7) for all candidates c∈ Ct (8) =+1。 (9) next (10) Lk={c∈ Ck|≥ minsupport}。 (11) next (12) resultset=resultset∪ Lk 其中 , D 表示数据库。 minsupport 表示给定的最小支持度。 resultset 表示所有最大项目集 . Sc_candidate 函数 该函数的参数为 Lk1,即 : 所有最大 k1 维项目集 ,结果返回含有 k 个项目的侯选项目集 ,Ck是 k维最大项目集的超集 ,通过函数 count_support计算项目的支持度 ,然后生成 Lk. 该函数是如何完成这些功能的 , 详细说明如下 : 首先 , 通过对 Lk1 自连接操作生成 Ck39。 ,称 join(连接 )步 , 该步可表述为 : insert into Ck ,......, from Lk1P,Lk1Q =,......=, 若用集合表示 :Ck39。 ={X∪ X39。 |X,X39。 ∈ Lk1,|X∩ X39。 |=k2} 陕西理工学院数学与计算机科学系开放性实验结题报告 11 然后 ,是 prune(修剪 )步 ,即对任意的 c,c∈ Ck, 删除 Ck 中所有那些 (k1)维子集不在 Lk1 中的项目集 ,得到侯选项目集 : for all itemset c∈ Ck for all (k1)维子集 s of c if (s 不属于 Lk1) then delete c from Ck。 用集合表 示 :Ck=={X∈ Ck39。 |X 的所有 k1 维子集在 Lk1中 } 在此函数中需要说明以下几点 : (1) 最大项目集的子集必为最大项目集 . 这是该算法中隐含的最基本的一条性质 . 因为最大项目集定义为不小于最小支持度 (minsupport)的项目集 . 若。