apriori算法报告

实验设计报告实验设计报告 课程名称 数据挖掘数据挖掘 题目名称 apriori算法实验报告算法实验报告 学生学院 管理学院管理学院 专业班级 1010 信息管理与信息系统 信息管理与信息系统 4 4 学号与姓名 3210004981 3210004981范美红范美红 32100049823210004982 黄嘉贤黄嘉贤 32100049833210004983 黎玉莲黎玉莲 32100049843210004984 梁茹梁茹 32100049853210004985 林嘉欣林嘉欣 指导教师 刘国胜 2013 年 05 月 04 日 apriori 算法实验报告算法实验报告 一 实验目的一 实验目的 通过实验 加深数据挖掘中一个重要方法 关联分析的认识 其经典算法为 Apriori 算法 了解影响 Apriori 算法性能的因素 掌握基于 Apriori 算法理论的关联分 析的原理和方法 二 实验内容二 实验内容 对一数据集用 Apriori 算法做关联分析 用 matlab 实现 三 方法手段三 方法手段 关联规则挖掘的一个典型例子是购物篮分析 因为该问题源于研究顾客事务数据库 以确定购买商品之间的相关性 条码技术的进步使得零售商们可以收集和存储大量销售数 据 这些数据被称为购物篮数据 关联规则挖掘可以在包含这些数据项的大型集中发现有 趣的关联和相关联系 关联规则展示在给定数据集中频繁一起出现的属性值条件 关联规则是描述数据库中数据项之间存在的潜在关系的规则 形式为 其中 是数据库中的数据项 1212 mn AAABBB 1 2 i A im 1 2 j Ajn 数据项之间的关联规则即根据一个事务中某些项的出现 可推导出另一些项在同一事务中也 出现 四 四 Apriori 算法算法 Apriori 算法是发现关联规则领域的经典算法 该算法将发现关联规则的过程分为两 个步骤 第一步通过迭代 检索出事务数据库中的所有频繁项集 即支持度不低于用户设 定的阈值的项集 第二步利用频繁项集构造出满足用户最小信任度的规则 具体做法就是 首先找出频繁1 项集 记为 L1 然后利用 L1来产生候选项集 C2 对 C2 中的项进行判定挖掘出 L2 即频繁2 项集 不断如此循环下去直到无法发现更多的频繁 k 项集为止 每挖掘一层 Lk就需要扫描整个数据库一遍 五 实验结果五 实验结果 test txt 格式及内容如下 实验结果如下 六 实验总结六 实验总结 Apriori 算法可以很有效地找出数据集中存在的关联规则且能找出最大项的关联规则 但从以上的算法执行过程可以看到 Apriori 算法的缺点 第一 在每一步产生侯选项目集时循环产生的组合过多 没有排除不应该参与组合的元 素 第二 每次计算项集的支持度时 都对数据库 D 中的全部记录进行了一遍扫描比较 如 果是一个大型的数据库的话 这种扫描比较会大大增加计算机系统的 I O 开销 而这种代 价是随着数据库的记录的增加呈现出几何级数的增加 因此人们开始寻求一种能减少这种 系统 1 O 开销的更为快捷的算法 七 实验程序七 实验程序 apriori01 m function y0 apriori01 x0 pre sup conf gain APRIORI Summary of this function goes here arg x0 元数据 arg pre Ln 1 的候选项集 arg sup 支持度 整型 arg conf 置信度 arg gain 频繁候选项集数组 y0 最后的返回值 m n size x0 当候选项集为空时 也利用元数据排列出第一个候选项集 需要用到的方法 if isempty pre pre eye n end c d size pre 对候选项集进行支持度统计 num zeros c 1 建立统计的数组 为 c 行 1 列 每一行对应每一个候选项集的统计数 for i 1 c count 0 for j 1 m 统计方法 候选项集减去元数据的每一行 如果是包含在元数据中 则 all 函数会等于 1 temp x0 j pre i if all temp 0 1 count count 1 end end 对每一个候选项集进行统计 num i count end 由频繁项集推出下一候选项集 next for k 1 c if num k sup 支持度判定 gain gain pre k 先将上一候选项集中符合支持度的加入 gain 候选项集数组 for l k 1 c if num l sup x1 和 x2 可以连接的条件 if sum abs pre l pre k 2 temp pre l pre k 这里对于生成的下一候选项集进行数值处理 把加完之后大于 1 的全部变为 1 方便后续计算 a b size temp for h 1 b if temp h 1 temp h 1 end end 候选项集数组 next next next temp end end end end end 去除重复的行 next unique next rows 如果 next 下一候选项集为空 则结束 if isempty next y0 gain return end 递归调用 y0 apriori01 x0 next sup conf gain apriori02 m function y0 apriori02 x0 pharse c d size x0 gain count for e 1 c every x0 e 推导强规则 l w size every tag find every 0 m n size tag if n 1 for i 1 n 1 对于每一条关联产品计算出所有可能的排列组合 temp nchoosek tag i a b size temp for x 1 a line every for y 1 b line 1 temp x y 1 end 统计置信度 count count conf every line pharse 加到关联关系后面一列 gain gain line end end gain unique gain rows end end x y size gain 按置信度排序 y0 sortrows gain count y 1 conf m function y0 conf x0 x1 M 统计每一个关联关系的置信度 CONF Summary of this function goes here Detailed explanation goes here m n size M a b size x1 for u 1 b if x1 1 u 1 x1 1 u 0 end if x1 1 u 1 x1 1 u 1 end end 对候选项集进行支持度统计 num 0 count 0 count2 0 for j 1 m 统计方法 候选项集减去元数据的每一行 如果是包含在元数据中 则 all 函数