毕业论文--基于关联规则的数据挖掘.doc

内蒙古科技大学毕业论文 I 内蒙古科技大学 本科生毕业毕业论文 题 目 基于关联规则的数据挖掘 学生姓名 孙成伟 学 号 0710132133 专 业 数学与应用数学 班 级 2007 级 1 班 指导教师 王培吉 副教授 内蒙古科技大学毕业论文 I 基于关联规则的数据挖掘基于关联规则的数据挖掘 摘摘 要要 数据挖掘利用了统计学的抽样 估计和假设检验及人工智能 模式识别和 机器学习的搜索算法 建模技术和学习理论等领域的思想 数据挖掘在这种具 有固定形式的数据集上完成知识的提炼 最后以合适的知识模式用于进一步分 析决策工作 在数据挖掘所发现的知识模型中 关联规则模式是非常重要的一种 也是 最活跃的一个分支 关联规则表示数据库中一组对象之间某种关联关系的规则 本文通过 Apriori 算法 将收集来的历年全国各地区城镇居民食品消费情况 进行数据挖掘 通过数据挖掘 找到频繁项集并得到关联规则 由关联规则进 行相关分析 并将得出的分析结果应用到实际当中 关键字 数据挖掘 关联规则 关键字 数据挖掘 关联规则 Apriori 算法 食品消费分析算法 食品消费分析 内蒙古科技大学毕业论文 II Data mining based on association rules Abstract Using the statistical data mining the sampling estimation and hypothesis testing and artificial intelligence pattern recognition and machine learning search algorithm modeling technology and learning theory and other areas of thought Data mining in this has fixed forms of datasets finally complete knowledge refining in the proper knowledge model for further analysis and decision work In the knowledge models that data mining has found association rules mode is a very important kind it is also a branch of the most activities Association rules is the relationship between some of the rules in a group of objects in the database Through Apriori algorithm in this paper will collect of calendar year the national regions to urban residents food consumption data mining By data mining to find frequent Itemset and get association rules Correlation analysis by association rules and will the results of analysis in the practical application Key words Data Mining Association rules Apriori algorithm Food consumption analysis 内蒙古科技大学毕业论文 III 目目 录录 摘 要 I ABSTRACT II 目 录 II 第一章 引 言 1 1 1 研究背景 1 1 1 1 数据挖掘与传统分析方法的区别 3 1 2 数据挖掘的主要问题 3 1 2 1 数据挖掘技术和用户界面问题 3 1 2 2 挖掘不同类型的知识问题 3 1 2 3 多个抽象层的交互知识挖掘问题 3 1 2 4 数据挖掘结果的表示和显示问题 3 1 2 5 处理噪音和不完全数据 3 1 2 6 模式评估 兴趣度问题 4 1 2 7 性能问题 4 1 2 8 数据挖掘算法的有效性和可规模性 4 1 2 9 并行 分布和增量挖掘算法 4 1 3 数据挖掘的研究方向 4 1 4 拟解决的问题 5 1 5 本章小结 6 第二章 数据挖掘概念与技术 7 2 1 数据挖掘的任务 7 2 1 1 数据挖掘的职能 7 2 2 数据挖掘的对象 8 2 3 可数据挖掘的知识模型 9 2 4 数据挖掘的技术 9 内蒙古科技大学毕业论文 IV 2 4 1 数据挖掘的方法 9 2 4 2 数据挖掘的步骤 11 第三章 关联规则 13 3 1 由购物篮分析得到的关联规则 13 3 2 关联规则的相关概念 13 3 2 1 关联规则的概念 13 3 2 2 支持度与置信度 14 3 3 关联规则挖掘的过程及分类 15 3 3 1 关联规则的挖掘过程 15 3 3 2 关联规则的分类 15 3 4 关联规则的相关算法 16 3 4 1 Apriori 算法 16 3 4 2 基于划分的算法 16 3 4 3 FP 树频集算法 17 第四章 APRIORI 算法 18 4 1 APRIORI算法的定义及思想 18 4 1 1 Apriori 算法的基本思想 18 4 2 APRIORI算法的性质 18 4 3 APRIORI 算法的步骤 18 4 4 APRIORI算法的特点及局限性 19 4 5 APRIORI算法评价 20 第五章 应用 APRIORI 算法的实例分析 21 5 1 研究说明 21 5 2 研究方法 21 5 2 1 数据采集 21 5 2 2 数据处理 21 5 2 3 应用算法进行数据挖掘 23 5 2 4 结果分析 26 内蒙古科技大学毕业论文 V 参考文献 27 附 录 28 致 谢 32 内蒙古科技大学毕业论文 1 第第一一章章 引引 言言 数据挖掘 Data Mining DM 又称数据库中的知识发现 Knowledge Discover in Database KDD 是目前人工智能和数据库领域研究的热点问题 所谓数据挖掘是指从数据库的大量数据中揭示出隐含的 先前未知的并有潜在 价值的信息的非平凡过程 数据挖掘是一种决策支持过程 它主要基于人工智能 机器学习 模式识 别 统计学 数据库 可视化技术等 高度自动化地分析企业的数据 做出归 纳性的推理 从中挖掘出潜在的模式 帮助决策者调整市场策略 减少风险 做出正确的决策 1 1 研究背景研究背景 自 2000 年以来 数据挖掘引起了信息产业界的极大关注 其主要原因是存 在大量数据 可以广泛使用 并且迫切需要将这些数据转换成有用的信息和知 识 获取的信息和知识可以广泛用于各种应用 包括商务管理 生产控制 市 场分析 工程设计和科学探索等 数据挖掘利用了统计学的抽样 估计和假设检验及人工智能 模式识别和 机器学习的搜索算法 建模技术和学习理论等领域的思想 数据挖掘也吸纳了 其他领域的思想 包括最优化 进化计算 信息论 信号处理 可视化和信息 检索 其中的一些领域在数据挖掘中起到了重要的支撑作用 特别的 需要数 据库系统提供有效的存储 索引和查询处理的支持 广义上说 任何从数据库中挖掘信息的过程都叫做数据挖掘 从这点看来 数据挖掘就是 BI 商业智能 但从技术术语上说 数据挖掘 Data Mining 特 指的是 源数据经过清洗和转换等成为适合于挖掘的数据集 数据挖掘在这种 具有固定形式的数据集上完成知识的提炼 最后以合适的知识模式用于进一步 分析决策工作 从这种狭义的观点上 我们可以定义 数据挖掘是从特定形式 的数据集中提炼知识的过程 数据挖掘往往针对特定的数据 特定的问题 选 择一种或者多种挖掘算法 找到数据下面隐藏的规律 这些规律往往被用来预 测 支持决策 自 60 年代以来 数据库和信息技术已经系统地从原始的文件处理进化到 内蒙古科技大学毕业论文 2 复杂的 功能强大的数据库系统 自70年代以来 数据库系统的研究和开发已 经从层次和网状数据库发展到开发关系数据库系统 数据建模工具 索引和数 据组织技术 自 80 年代中期以来 数据库技术的特点是广泛接受关系技术 研究和开 发新的 功能强大的数据库系统 这些使用了先进的数据模型 如扩充关系 面向对象 对象 关系和演绎模型 图 1 1 数据库技术的进化 内蒙古科技大学毕业论文 3 1 1 11 1 1 数据挖掘与传统分析方法的区别数据挖掘与传统分析方法的区别 数据挖掘与传统的数据分析 如查询 报表 联机应用分析 的本质区别 是数据挖掘是在没有明确假设的前提下去挖掘信息 发现知识 数据挖掘所得 到的信息应具有先未知 有效和可实用三个特征 先前未知的信息是指该信息是预先未曾预料到的 即数据挖掘是要发现那 些不可能靠直觉发现的信息或知识 甚至是违背直觉的信息或知识 挖掘出的 信息越是出乎意料 就可能越有价值 在商业应用中最典型的例子就是一家连 锁超市通过数据挖掘发现了小孩尿布与啤酒之间的联系 1 1 2 数据挖掘的主要问题数据挖掘的主要问题 由于强调数据挖掘的主要问题 考虑挖掘技术 用户界面 性能和各种数 据类型 这些问题介绍如下 1 2 1 数据挖掘技术和用户界面问题数据挖掘技术和用户界面问题 这反映所挖掘的知识类型 在多粒度上挖掘知识的能力 领域知识的使用 特定的挖掘和知识显示 1 2 2 挖掘不同类型的知识问题挖掘不同类型的知识问题 由于不同的用户可能对不同类型的知识感兴趣 数据挖掘系统应当覆盖广 谱的数据分析和知识发现任务 包括数据特征 区分 关联 聚类 趋势 偏 差分析和类似性分析 这些任务可能以不同的方式使用相同的数据库 并需要 开发大量数据挖掘技术 1 2 3 多个抽象层的交互知识挖掘问题多个抽象层的交互知识挖掘问题 由于很难准确地知道能够在数据库中发现什么 数据挖掘过程应当是交互 的 1 2 4 数据挖掘结果的表示和显示问题数据挖掘结果的表示和显示问题 发现的知识应当用高级语言 可视化表示形式 或其它表示形式表示 使 得知识易于理解 能够直接被人使用 如果数据挖掘系统是交互的 这一点尤 为重要 这要求系统采用有表达能力的知识表示技术 如树 表 图 图表 交叉表 矩阵或曲线 1 2 5 处理噪音和不完全数据处理噪音和不完全数据 内蒙古科技大学毕业论文 4 存放在数据库中数据可能反映噪音 例外情况 或不完全的数据对象 这 些对象可能搞乱分析过程 导致数据与所构造的知识模型过分适应 其结果是 所发现的模式的精确性可能很差 1 2 6 模式评估模式评估 兴趣度问题兴趣度问题 数据挖掘系统可能发现数以千计的模式 对于给定的用户 许多模式不是 有趣的 它们表示平凡知识或缺乏新颖性 1 2 7 性能问题性能问题 这包括数据挖掘算法的有效性 可规模性和并行处理 1 2 8 数据挖掘算法的有效性和可规模性数据挖掘算法的有效性和可规模性 为了有效地从数据库中大量数据提取信息 数据挖掘算法必须是有效的和 可规模化的 1 2 9 并行 分布和增量挖掘算法并行 分布和增量挖掘算法 许多数据库的大容量 数据的广泛分布和一些数据挖掘算法的计算复杂性 是促使开发并行和分布式数据挖掘算法的因素 这些算法将数据划分成部分 这些部分可以并行处理 然后合并每部分的结果 1 3 数据挖掘的研究方向数据挖掘的研究方向 1 数据输入形式的多样性 应用中经常需要对一些半结构化 非结构化的数据形式如文本 图形 数 学公式 图像或WWW 资源进行挖掘操作 但目前的数据挖掘工具一般只能提 供对数值型的结构化数据的处理 对数据中存在缺损或噪声的情况也没有有效 的方法 2 数据挖掘算法的有效性与可测性 数据挖掘的对象向更大型的数据库 更高的维数和属性之间更复杂的关系 方向发展 更多的记录和属性意味着更大 更高维的搜索空间 从而导致组合 爆炸 属性之间的关系变得更为复杂如表现为层次结构 会大大提高知识搜索的 代价 从1个大型数据库中抽取知识的算法必须高效 可测量 即数据挖掘算法 的运行时间必须可预测 且可接受 指数和多项式算法等复杂性的算法不具有实 用价值 目前的研究发展到用并行处理或抽样的方法处理大规模数据以获得较 高的计算效率 根据问题的定义和领域知识选择出需要的属性从而降低维数并 内蒙古科技大学毕业论文 5 有效处理属性之间的复杂关系等 3 用户参与和领域知识 有效的决策过程往往需要多次交互和多次反复 使数据挖掘的结果准确地 描述数据挖掘的要求 并易于表达 实现在多抽象层次上交互挖掘知识 目前许 多知识发现系统和工具缺乏与用户的交互 难以有效利用领域知识 4 证实技术的局限 数据挖掘使用特定的分析方法或逻辑形式发现知识 如归纳方法 但系统 可能无法去交互证实所发现的知识的正确或正确的程度 使得发现的知识没有 普遍性而不能成为有用的知识 5 知识的表达和解释机制 许多应用中重要的是用户能够理解发现的知识 这要求知识的表达不仅限 于数字或符号 而是更易于理解的方式 如图形 自然语言和可视化技术等 同 时 只有当数据挖掘系统能提供更好的解释机制 用户才能更有效地评价这些知 识 并且区分出哪些是真正有用的知识 哪些只是常识性的知识或异常情况 6 知识的维护和更新 新的知识发现可能导致以前发现的知识失效 因此知识需要动态维护和及 时更新 目前研究采用增量更新的方法 数据快照和时间戳等方法来维护已有 的知识 7 私有性和安全性 数据挖掘能从不同角度 不同抽象层次上观察数据 将影响到数据挖掘的 私有性和安全性 通过研究数据挖掘导致的数据非法侵入 可改进数据库安全 方法 以避免信息泄露 8 支持的局限与其他系统的集成 目前的数据挖掘系统尚不能支持多种平台 一些产品是基于PC的 一些是 面向大型主机系统的 还有一些是面向客户机 服务器环境的 另外 由于方法 功能单一的发现系统的适应范围的限制 要充分发挥系统的作用 应该和数据库 知识库 专家系统 决策支持系统 可视化工具 网络技术等进行有机集成 5 6 1 4 拟解决的问题拟解决的问题 内蒙古科技大学毕业论文 6 通过调查 9 类食品历年 2000 2009 年 2004 年除外 各地区的人均食物消 费情况 可以清楚的知道各地区人民的饮食习惯 对这些数据进行数据挖掘 得到相应的关联规则 依据得到的关联规则 可以建立相应的食品供给机制 提供合理的饮食建议 可以使人们在日常的饮食中吃的更健康 本文通过对采集来的数据进行数据挖掘 运用 apriori 算法进行相关的挖掘 得到关联规则 并应用到实际 1 5 本章小结本章小结 本章介绍了数据挖掘技术的研究意义及技术背景 数据挖掘的主要问题 论文选题的依据 数据挖掘的研究方向及我们所做论文的主要内容等 在当今 社会 正处于信息爆炸的年代 怎样从众多的 无序 纷乱 复杂的信息中得 到自己有用的信息 这就需要一定的信息处理能力 数据挖掘就是在这样的环 境中得到完善和发展 数据挖掘技术融合了当今的许多学科的最新研究成果和 技术而形成的一个具有自己特色的研究分支 可进行数据挖掘的项目极其丰富 进行数据挖掘的方法也有很多种 本文是对全国各地区历年对 9 类食品的消费 情况进行数据挖掘 并得出相应的分析 内蒙古科技大学毕业论文 7 第第二二章章 数数据据挖挖掘掘概概念念与与技技术术 数据挖掘 Data Mining 就是从存放在数据库 数据仓库或其他信息库中 的大量的数据中获取有效的 新颖的 潜在有用的 最终可理解模式的非平凡 过程 数据挖掘涉及多学科技术的集成 包括数据库技术 统计 机器学习 高 性能计算 模式识别 神经网络 数据可视化 信息提取 图像与信号处理和 空间数据分析 简单地说 数据挖掘是从大量数据中提取或 挖掘 知识 该术语实际上有 点用词不当 注意 从矿石或砂子挖掘黄金称作黄金挖掘 而不是砂石挖掘 这样 数据挖掘应当更正确地命名为 从数据中挖掘知识 知识挖掘 是一个 短术语 可能不能强调从大量数据中挖掘 毕竟 挖掘是一个很生动的术语 它抓住了从大量的 未加工的材料中发现少量金块这一过程的特点 图 2 1 通过数据挖掘 可以从数据库提取有趣的知识 规律 或高层信息 并可 以从不同角度观察或浏览 发现的知识可以用于决策 过程控制 信息管理 查询处理 等等 因此 数据挖掘被信息产业界认为是数据库系统最重要的前 沿之一 是信息产业最有前途的交叉学科 2 1 数据挖掘的任务数据挖掘的任务 通常数据挖掘的任务可以分为预测和描述两大类 预测任务是根据己知属性的值 推断特定的未知属性的值 被预测的属性一 般称为目标变量 用于做预测的属性称为说明变量 预测分为针对离散的目标 变量的分类任务和针对连续的目标变量的回归任务 描述任务是刻画数据库中数据的一般特性 目标是以简洁概要的方式导出 概括数据中潜在联系的模式 描述任务可以发现的模式有 概念描述 特征化和 比较 关联规则 聚类 异常等 2 1 1 数据挖掘的职能数据挖掘的职能 内蒙古科技大学毕业论文 8 数据挖掘能做以下七种不同事情 分析方法 分类 Classification 估值 Estimation 预言 Prediction 相关性分组或关联规则 Affinity grouping or association rules 聚集 Clustering 描述和可视化 Description and Visualization 复杂数据类型挖掘 Text Web 图形图像 视频 音频等 以上七种数据挖掘的分析方法可以分为两类 直接数据挖掘 间接数据挖 掘 1 直接数据挖掘直接数据挖掘 目标是利用可用的数据建立一个模型 这个模型对剩余的数据 对一个特 定的变量 可以理解成数据库中表的属性 即列 进行描述 2 间接数据挖掘 间接数据挖掘 目标中没有选出某一具体的变量 用模型进行描述 而是在所有的变量中 建立起某种关系 分类 估值 预言属于直接数据挖掘 后三种属于间接数据挖掘 数据挖掘的范围非常广泛 可以是社会科学 经济学 商业数据 科学处 理产生的数据和卫星观测得到的数据 它们的数据结构也各不相同 可以是层 次的 网状的 关系的和面向对象的数据 2 2 数据挖掘的对象数据挖掘的对象 数据挖掘是一个以数据库 人工智能 数理统计 可视化四大支柱技术为 基础 多学科交叉 渗透 融合形成的新的交叉学科 其研究内容十分广泛 目前存在很多数据挖掘方法或算法 因此有必要对这些方法进行分门别类 描 述或说明一个算法涉及三个部分 输入 输出和处理过程 数据挖掘算法的输 入是数据库 算法的输出是要发现的知识或模式 算法的处理过程则涉及具体 的搜索方法 从算法的输入 输出和处理过程三个角度 我们可以确定这样几 种分类标准 挖掘对象 挖掘方法 挖掘任务 根据挖掘对象分 有如下若干种数据库或数据源 关系数据库 面向对象数 内蒙古科技大学毕业论文 9 据库 空间数据库 时态数据库 文本数据库 多媒体数据库 异质数据库 历史数据库 以及万维网 Web 根据挖掘方法分 可粗分为 统计方法 机器学习方法 神经网络方法和数 据库方法 统计方法可细分为 回归分析 判别分析 聚类分析 探索性分析等 机器学习可细分为 归纳学习方法 基于范例学习 遗传算法等 神经网络方法 可细分为 前向神经网络 自组织神经网络等 数据库方法主要是多维数据分析 或 OLAP 方法 另外还有面向属性的归纳方法 2 3 可数据挖掘的知识模型可数据挖掘的知识模型 根据挖掘任务分 数据挖掘主要发现以下五类知识 1 广义型知识 根据数据的微观特性发现其表征的 带有普遍性的 较高 层次概念的 中观或宏观的知识 2 分类型知识 反映同类事物共同性质的特征型知识和不同事物之间差异 性特征知识 用于反映数据的汇聚模式或根据对象的属性区分其所属类别 3 关联型知识 反映一个事件和其他事件之间依赖或关联的知识 又称依 赖关系 这类知识可用于数据库中的归一化 查询优化等 4 预测型知识 通过时间序列型数据 有历史的和当前的数据去预测未来 的情况 它实际上是一种以时间为关键属性的关联知识 5 偏差型知识 通过分析标准类以外的特例 数据聚类外的离群值 实际 观测值和系统预测值间的显著差别 来对差异和极端特例进行描述 2 4 数据挖掘的技术数据挖掘的技术 2 4 1 数据挖掘的方法数据挖掘的方法 从不同的角度看 数据挖掘技术有多种分类方法 如根据发现的知识种类分 类 根据挖掘的数据库类型分类 根据挖掘方法分类 根据挖掘的途径分类 根 据所采用的技术分类等等 目前常用的数据挖掘技术内容包括如下 1 决策树方法 利用信息论中的互信息 信息增益 寻找数据库中具有最大信息量的字段 建立决策树的一个结点 再根据字段的不同取值建立树的分支 在每个分支子集 中重复建立树的下层结点和分支的过程 即可建立决策树 国际上最有影响和 最早的决策树算法是 Quiulan 研制的 ID3 方法 数据库越大它的效果越好 此 内蒙古科技大学毕业论文 10 后又发展了各种决策树方法 如 IBL E 方法使识别率提高了 10 2 神经网络方法 它模拟人脑神经元结构 以 MP 模型和 Hebb 学习规则为基础 用神经网络 连接的权值表示知识 其学习体现在神经网络权值的逐步计算上 目前主要有 3 大类多种神经网络模型 前馈式网络 它以感知机 反向传播模型 函数型 网络为代表 可用于预测 模式识别等方面 反馈式网络 它以 Hopf ield 的 离散模型和连续模型为代表 分别用于联想记忆和优化计算 自组织网络 它以 ART 模型 Koholon 模型为代表 用于聚类 3 覆盖正例排斥反例方法 它是利用覆盖所有正例 排斥所有反例的思想来寻找规则 首先在正例集 合中任选一个种子 到反例集合中逐个比较 与字段取值构成的选择子相容则舍 去 相反则保留 按此思想循环所有正例种子 将得到正例的规则 选择子的合 取式 比较典型的算法有 M ichalsk i 的 AQ 11 方法 洪家荣改进的 AQ 15 方 法以及他的 A E5 方法 4 粗集 Rough Set 方法 在数据库中 将行元素看成对象 列元素看成属性 分为条件属性和决策属 性 等价关系 R 定义为不同对象在某个 或几个 属性上取值相同 这些满足 等价关系的对象组成的集合称为该等价关系 R 的等价类 条件属性上的等价类 E 与决策属性上的等价类 Y 之间有 3 种情况 下近似 Y 包含 E 上近似 Y 和 E 的交非空 无关 Y 和 E 的交为空 对下近似建立确定性规则 对上近似 建立不确定性规则 含可信度 对无关情况不存在规则 5 概念树方法 对数据库中记录的属性字段按归类方式进行抽象 建立起来的层次结构称 之为概念树 利用概念树提升的方法可以大大浓缩数据库中的记录 对多个属 性字段的概念树进行提升 将得到高度概括的知识基表 然后可再将它转换成规 则 6 遗传算法 这是模拟生物进化过程的算法 由 3 个基本算子组成 繁殖 选择 是从 1 个旧种群 父代 选出生命力强的个体 产生新种群 后代 的过程 交叉 重 内蒙古科技大学毕业论文 11 组 选择 2 个不同个体 染色体 的部分 基因 进行交换 形成新个体 变 异 突变 对某些个体的某些基因进行变异 1 变 0 0 变 1 这种遗传算法可以 起到产生优良后代的作用 这些后代需满足适应度值 经过若干代的遗传 将得 到满足要求的后代 问题的解 遗传算法已在优化计算和分类机器学习方面显 示了明显的优势 7 公式发现 在工程和科学数据库 由实验数据组成 中 对若干数据项 变量 进行一定 的数学运算 求得相应的数学公式 比较典型的 BACON 发现系统完成了对物 理学中大量定律的重新发现 其基本思想是 对数据项进行初等数学运算 加 减 乘 除等 形成组合 数据项 若它的值为常数项 就得到了组合数据项等于常数的公式 8 统计分析方法 在数据库字段项之间存在两种关系 函数关系 能用函数公式表示的确定性 关系 和相关关系 不能用函数公式表示 但仍是相关确定关系 对它们的分析 采用如下方法 回归分析 相关分析 主成分分析 9 模糊集方法 利用模糊集理论对实际问题进行模糊评判 模糊决策 模糊模式识别和模 糊聚类分析 模糊性是客观存在的 系统的复杂性越高 精确化能力就越低 即 模糊性就越强 这是 Zadeh 总结出的互克性原理 10 可视化技术 可视化数据分析技术拓宽了传统的图表功能 使用户对数据的剖析更清楚 例如 把数据库中的多维数据变成多种图形 这对揭示数据的状况 内在本质及 规律性起了很大作用 2 4 2 数据挖掘的步骤数据挖掘的步骤 一些人只是把数据挖掘视为数据库中知识发现过程的一个基本步骤 知识 发现过程 由以下步骤组成 1 数据清理 消除噪音或不一致数据 2 数据集成 多种数据源可以组合在一起 3 数据选择 从数据库中提取与分析任务相关的数据 内蒙古科技大学毕业论文 12 4 数据变换 数据变换或统一成适合挖掘的形式 如 通过汇总或聚集操 作 5 数据挖掘 基本步骤 使用智能方法提取数据模式 6 模式评估 根据某种兴趣度度量 识别提供知识的真正有趣的模式 7 知识表示 使用可视化和知识表示技术 向用户提供挖掘的知识 数据挖掘步骤可以与用户或知识库交互 有趣的模式提供给用户 或作为 新的知识存放在知识库中 注意 根据这种观点 数据挖掘只是整个过程中的 一步 尽管是最重要的一步 因为它发现隐藏的模式 内蒙古科技大学毕业论文 13 第第三三章章 关关联联规规则则 3 1 由购物篮分析得到的关联规则由购物篮分析得到的关联规则 作为超市的一名销售经理 应该最想知道的是消费者购物的心里 消费者 在购物时最想买到的物品 在买一件商品时会有这个商品会再买那种商品 也 是哪几种商品会被消费者频繁购买 例如 在一家超市中 人们发现了一个特 别有趣的现象 尿布与啤酒这两种风马牛不相及的商品居然摆在一起 但这一 奇怪的举措居然使尿布和啤酒的销量大幅增加了 这可不是一个笑话 而是一 直被商家所津津乐道的发生在美国沃尔玛连锁超市的真实案例 原来 美国的妇女通常在家照顾孩子 所以她们经常会嘱咐丈夫在下班回 家的路上为孩子买尿布 而丈夫在买尿布的同时又会顺手购买自己爱喝的啤酒 这个发砚为商家带来了大量的利润 但是如何从浩如烟海却又杂乱无章的数据 中 发现啤酒和尿布销售之间的联系呢 这又给了我们什么样的启示呢 3 啤酒 和 尿布 两个看上去没联系的两种商品放在一起 却获得了丰 厚的利润 这种现象就是卖场中商品直接的关联性 研究 啤酒和尿布 关联 的方法就是购物篮分析 3 2 关联规则的相关概念关联规则的相关概念 在数据挖掘所发现的知识模型中 关联规则模式是非常重要的一种 也是 最活跃的一个分支 关联规则表示数据库中一组对象之间某种关联关系的规则 关联规则挖掘是指发现大量数据中项集之间有趣的关联或相关联系 关联 规则问题由 R Agrawal 等在 1993 年提出 随即引起了广泛的关注 许多研究者 对关联规则挖掘问题进行了深入的研究 对最初的关联规则挖掘算法进行了改 进和扩展 同时 关联规则的挖掘被应用到许多其它领域的数据库 取得了良 好的挖掘效果 3 2 1 关联规则的概念关联规则的概念 内蒙古科技大学毕业论文 14 设 I 是项的集合 设任务相关的数据 D 是数据库事务的集 1i2imi 合 其中每个事务 T 是项的集合 使得 TI 每一个事务有一个标识符 称作 TID 设 A 是一个项集 事务 T 包含 A 当且仅当 A I 关联规则是形如 A B 的蕴涵式 其中 A I B I 并且 A B 3 2 2 支持度与置信度支持度与置信度 规则的支持度和置信度是两个规则兴趣度量值 它们分别表示发现规则的 有用性和确定性 规则 AB 在事务集 D 中出现 具有支持度 s 其中 s 是 D 中事务包含 A B 即 A 和 B 二者 的百分比 它是概率 P A B 规则 A B 在 事务集 D 中具有置信度 c 如果 D 中包含 A 的事务的同时也包含 B 的百分比是 c 这是条件概率 P B A 即是 support AB P A B 3 1 即 关联模式的支持度是模式为真的任务相关的元组 或事务 所占的百 分比 对于关联规则 AB 其中 A 和 B 是项目的集合 支持度定义为 元组总数 的元组数和包含 支持度 BA BA confidence AB P B A 3 2 即 每个发现模式都应当由一个表示其有效性或 值得信赖性 的确定性 度量 对于关联规则 AB 其中 A 和 B 是项目的集合 其确定性度量置信 度定义为 的元组数包含 的元组数和包含 置信度 A BA BA 同时满足最小支持度阈值 min sup 和最小置信度阈值 min conf 的规 则称作强规则 我们用 0 和 100 之间的值而不是用 0 到 1 之间的值表示支持 度和置信度 为挖掘有效的关联规则 必须给定最小支持度 min sup 和最小置信度 min conf 关联规则的挖掘问题就是在 D 中求解所有支持度和置信度均分别 超过 min sup 和 min conf 的关联规则 即要求解满足 support AB min sup 和 confidence AB min conf 的规则 AB 同时满足最小支持度阈值 min sup 和最小置信度阈值 min conf 的规则称为强规则 7 内蒙古科技大学毕业论文 15 项的集合称为项集 包含 k 个项的项集称为 k 项集 3 3 关联规则挖掘的过程及分类关联规则挖掘的过程及分类 3 3 1 关联规则的挖掘过程关联规则的挖掘过程 关联规则的挖掘是一个两步的过程 1 找出所有频繁项集 根据定义 这些项集出现的频繁性至少和预定义的 最小支持度计数一样 2 由频繁项集产生强关联规则 根据定义 这些规则必须满足最小支持度 和最小置信度 关联规则的第一阶段必须从原始资料集合中 找出所有高频项目组 Large Itemsets 第二阶段是要产生关联规则 Association Rules 从高频项目组产 生关联规则 是利用前一步骤的频繁 k 项集来产生规则 在最小置信度 Minimum Confidence 的条件下 若这一规则所求得的置信度满足最小置信 度 则称此规则为关联规则 4 3 3 2 关联规则的分类关联规则的分类 按照不同情况 关联规则可以进行分类如下 1 基于规则中处理的变量的类别 关联规则可以分为布尔型和数值型 布尔型关联规则处理的值都是离散的 种类化的 它显示了这些变量之 间的关系 而数值型关联规则可以和多维关联或多层关联规则结合起来 对 数值型字段进行处理 将其进行动态的分割 或者直接对原始的数据进行处 理 当然数值型关联规则中也可以包含种类变量 2 基于规则中数据的抽象层次 可以分为单层关联规则和多层关联规则 在单层的关联规则中 所有的变量都没有考虑到现实的数据是具有多个 不同的层次的 而在多层的关联规则中 对数据的多层性已经进行了充分的 考虑 3 基于规则中涉及到的数据的维数 关联规则可以分为单维的和多维的 内蒙古科技大学毕业论文 16 在单维的关联规则中 我们只涉及到数据的一个维 如用户购买的物品 而在多维的关联规则中 要处理的数据将会涉及多个维 换成另一句话 单 维关联规则是处理单个属性中的一些关系 多维关联规则是处理各个属性之 间的某些关系 例如 啤酒 尿布 这条规则只涉及到用户的购买的物品 性别 女 职业 秘书 这条规则就涉及到两个字段的信息 是两个维上 的一条关联规则 3 4 关联规则的相关算法关联规则的相关算法 3 4 1 Apriori 算算法法 Apriori 算法 使用候选项集找频繁项集 Apriori 算法是一种最有影响的挖掘布尔关联规则频繁项集的算法 其核 心是基于两阶段频集思想的递推算法 该关联规则在分类上属于单维 单层 布尔关联规则 在这里 所有支持度大于最小支持度的项集称为频繁项集 简称频集 Apriori 算法的基本思想是 1 找出所有的频集 这些项集出现的频繁性至少和预定义的最小支持度 一样 2 由频繁项集产生强关联规则 这些规则必须满足最小支持度和最小可 信度 3 使用第一步找到的频集产生期望的规则 产生只包含集合的项的所有 规则 其中每一条规则的右部只有一项 这里采用的是中规则的定义 一旦 这些规则被生成 那么只有那些大于用户给定的最小可信度的规则才被留下 来 为了生成所有频集 使用了递推的方法 可能产生大量的候选集 以及可能需要重复扫描数据库 是 Apriori 算法 的两大缺点 3 4 2 基基于于划划分分的的算算法法 基于划分的算法 是由 Savasere 等人设计的 这个算法先把数据库从逻辑 上分成几个互不相交的块 每次单独考虑一个分块并对它生成所有的频集 然后把产生的频集合并 用来生成所有可能的频集 最后计算这些项集的支 持度 这里分块的大小选择要使得每个分块可以被放入主存 每个阶段只需 内蒙古科技大学毕业论文 17 被扫描一次 该算法是可以高度并行的 可以把每一分块分别分配给某一个 处理器生成频集 算法的正确性是由每一个可能的频集 至少在某一个分 块中保证是频繁项集 产生频集的每一个循环结束后 处理器之间进行通信 来产生全局的候选 k 项集 通常这里的通信过程是算法执行时间的主要瓶颈 而另一方面 每个独立的处理器生成频集的时间也是一个瓶颈 3 4 3 FP 树频集算法树频集算法 针对 Apriori 算法的固有缺陷 J Han 等提出了不产生候选挖掘频繁项 集的方法 FP 树频集算法 采用分而治之的策略 在经过第一遍扫描之后 把数据库中的频集压缩进一棵频繁模式树 FP tree 同时依然保留其中的 关联信息 随后再将 FP tree 分化成一些条件库 每个库和一个长度为1 的 频集相关 然后再对这些条件库分别进行挖掘 当原始数据量很大的时候 也可以结合划分的方法 使得一个 FP tree 可以放入主存中 实验表明 FP tree 对不同长度的规则都有很好的适应性 同时在效率上较之Apriori 算法 有巨大的提高 本文主要是应用 Apriori 算法 对本文中的是实例进行分析 研究 内蒙古科技大学毕业论文 18 第四章第四章 Apriori 算法算法 4 1 Apriori 算法的定义及思想算法的定义及思想 Apriori 算法是一种最有影响的挖掘布尔关联规则频繁项集的算法 算法的 名字基于这样的事实 算法使用频繁项集性质的先验知识 正如我们将看到的 Apriori 使用一种称作逐层搜索的迭代方法 k 项集用于探索 k 1 项集 4 1 14 1 1 AprioriApriori 算法的基本思想算法的基本思想 1 首先 通过扫描数据集 产生一个大的候选数据项集 并计算每个候 选数据项发生的次数 然后基于预先给定的最小支持度生成频繁1 项集的集合 该集合记作L1 2 然后基于L1 和数据集中的数据 产生频繁2 项集L2 3 用同样的方法 直到生成频繁n 项集Ln 其中已不再可能生成满足最 小支持度的 N 1 项集 4 最后 从大数据项集中导出规则 为提高频繁项集逐层产生的效率 一种称作 Apriori 性质的重要性质用于 压缩搜索空间 4 2 Apriori 算法的性质算法的性质 为了提高按层搜索并产生相应频繁项集的处理效率 Apriori 算法利用了如 下一个重要性质来帮助有效缩小频繁项集的搜索空间 Apriori 性质 一个频繁项集中 任一子集也应是频繁项集 Apriori 性质是根据以下观察而得出结论 根据定义 若一个项集 I 不满 足最小支持度阈值s 那么该项集 I 就不是频繁项集 即P I s 若增加一个项A 到项集 I 中 那么所获得的新项集 I A在整个交易数据库所出现的次数也不 可能多于原项集 I 出现的次数 因此 I A 也不能是频繁的 即P I A s 根据逆反公理 即若一个集合不能通过测试 该集合所有超集也不能通过 内蒙古科技大学毕业论文 19 同样的测试 因此很容易确定Apriori 算法是正确的 4 3 Apriori 算法的步骤算法的步骤 第一步 初始化数据库 根据条件初始化数据库 扫描事务数据库 从中找 出所有的项集长度为 k 1 的项集 且支持度大于 s 形成频繁 1 项集 Lk 第二步 根据频繁 k 项集产生候选 k 十 1 项候选项集 Ck 1 如果 Ck 1 进入下一步 否则循环结束 第三步 扫描数据库 以确定每个候选项集的支持度 第四步 删除候选项中支持度小于 s 的候选项 形成 k 1 频繁项集 Lk 1 第五步 k k 1 转入第二步 Apriori 算法的第一步就是发现频繁 1 项集 L1 在第二至第五步 利用 Lk 1 产生 Ck以便获得 Lk 在这个过程产生相应的候选项集 然后利用 Apriori 算法 性质删除那些子集为非频繁项集的候选项集 一旦产生所有候选 就要扫描数 据库 由此求出每个候选项集的支持度 算法中的第三步 最终满足最小支持 度的候选项集组成了频繁项集 Lk 1 这样可以利用该过程来帮助从所获得频繁 项集中生成所有的关联规则 Apriori 过程完成两个操作 一是连接 二是剪枝操作 正如上面所介绍的 在连接过程中 Lk与 Lk连接以产生潜在候选项集 算法中的第二步 剪枝过程 中 算法中的第四步 利用 Apriori 性质删除候选项集中那些子集为非频繁项集的 项集 4 4 Apriori 算法的特点及局限性算法的特点及局限性 Apriori 算法利用候选项集和频繁项集的相互作用 得到了全部频集 并通 过对候选项集进行剪枝 大大地减少了候选项集的尺寸 获得了令人满意的结 果 然而 当面对挖掘对象具有繁多的频繁模式或者用户给定的最小支持度较 低时 Apriori 算法仍然有可能因为如下两个方面的巨大开销而面临困境 1 在处理候选项集方面 如果算法得到了大量的频繁1 项集 那么 在产 生候选项集时 会遇到大量候选项集难以处理的情况 所以 在有大量候选项 集产生的情况下 Apriori 算法基本无法运行 2 Apriori 算法采用的模式匹配方式 在检测大量的候选项集 特别是在 内蒙古科技大学毕业论文 20 挖掘长模式时 对数据库的重复扫描非常多 大量的时间消耗在内存与数据库 中的数据的交换上 8 4 5 Apriori 算法评价算法评价 在许多情况下 Apriori算法的候选产生检查方法大幅度压缩了候选项集的 大小 并导致很好的性能 然而 它有两种开销可能并非微不足道的 9 1 它可能产生大量候选项集 例如 如果有104个频繁1 项集 则需要产 107 个频繁2 项集 并累计和检查其频繁性 为发现长度为100的频繁模式 a1 a2 a100 则需产生多达约1030个候选 2 它可能需要重复的扫描数据库 通过模式匹配检查一个很大的候选集 合 为了提高Apriori 算法的效率 已经提出了许多Apriori 算法的变形 3 无法对稀有信息进行分析 由于频繁集的使用了参数min sup 所以就 无法对小于min sup的事件进行分析 而如果将min sup设成一个很低的值 那 么算法的效率就成了一个很难处理的问题 内蒙古科技大学毕业论文 21 第五章第五章 应用应用 Apriori 算法的实例分析算法的实例分析 居民在饮食方面的合理设置 对我们的生活质量起到重要的作用 合理的 饮食习惯 使我们身体健康 生活质量也有一定的提高 5 1 研究说明研究说明 通过对 2000 2009 年 2004 年除外 全国各地区城镇居民对淀粉及薯类 豆制品 油脂类 肉禽及制品 水产品类 菜类 干鲜瓜果类和奶及奶制品 9 类食品的消费情况及各地区城镇居民的历年人均收入及人均消费性支出进行统 计 并进行一系列的处理之后 进行相关的数据挖掘和关联规则分析 中国国家统计局组织实施全国及省 自治区 直辖市国民经济核算制度和 全国投入产出调查 并建立信息数据库 通过统计数据可以了解到一些相应的 信息 但是 将同一类型的数据结合到一起 获得的意义就会更大 本文就是 采用收集 9 类食品的相关数据 进行数据挖掘 得到关联规则 食品消费的相关性分析可以更加明确居民在食品购物方面的一些内在联系 为政府及商家提供了相关的销售意见 5 2 研究方法研究方法 首先 采集相关数据信息 其次 对数据进行处理 得到布尔数据库 第 三 应用 Apriori 算法对布尔数据库进行数据挖掘 得到关联规则 最后 对得 到的结果进行相关分析 5 2 1 数据采集数据采集 在中国国家统计局公布的 2000 2009 年统计年鉴中筛选出 淀粉及薯类 豆制品 油脂类 肉禽及制品 水产品类 菜类 干鲜瓜果类和奶及奶制品 9 类食品的消费情况及各地区城镇居民的历年人均收入和人均消费性支出 其中 包括 2000 2009 年 2004 年除外 的 9 年间的 31 个省 市 自治区的情况 得 到 31 个 省 市 自治区 9 年间 9 类食品的 279 9 个数据 内蒙古科技大学毕业论文 22 5 2 2 数据处理数据处理 首先 将得到九种食品的消费支出与全年的消费性支出比值及全年消费性 支出与人均收入的比值 得到的数值都为 0 1 之间的小数 其次 将上面得到的数值进行分区 将 9 类食品与消费性支出的比值等分 为 3 个区间 全年消费性支出与人均收入的比值等分为 4 个区间 应用 Excel 处理将比值落在对应区间的为 1 另外的几个区间则为 0 得到新的数据库 打开数据文件所在的 Excel 表格 在右边的空白出 N2 中输入 c2 d2 在 N2 中得到的就是消费性支出与工资的比例 将鼠标放在此时 N2 的黑色 框的右下角当鼠标是十字形时 向下拖拽 得到的就是 C 列与 D 列各行的比值 E 列之后是 E 列与 C 列的比值 将得到的结果重新存储到新的表格中 得到的 比例数据为 打开比例数据表格 同样是在右边的空白处 N2 输入 IF AND C2 0 33 C2 0 48 1 0 表示落在 0 33 0 48 区间的数值输出为 1 不在这个区间的数值为 0 把得到的结果存储到新的数据表格 5 2 3 应用算法进行数据挖掘应用算法进行数据挖掘 应用 MATLAB 软件进行数据挖掘 通过 File Import Data 将生成的布尔数据库导入到 MATLAB 中 内蒙古科技大学毕业论文 24 将导入到 MATLAB 中的 Data 文件 重命名为 X 在 MATLAB 中新建 4 个 M 文件 association rules m subset m setsub m in m 其中 association rules m 为主程 序 在 command window 窗口中分别输入 内蒙古科技大学毕业论文 25 得到的频繁 2 项集为 内蒙古科技大学毕业论文 26 得到的频繁 3 项集为 内蒙古科技大学毕