XX大学 本科生毕业毕业论文 题 目：基于关联规则的数据挖掘 学生姓名： 学 号： 专 业：数学与应用数学 班 级：级班 指导教师：副教授 基于关联规则的数据挖掘 摘 要 数据挖掘利用了统计学的抽样、估计和假设检验及人工智能、模式识别和机器学习的搜索算法、建模技术和学习理论等领域的思想。数据挖掘在这种具有固定形式的数据集上完成知识的提炼，最后以合适的知识模式用于进一步分析决策工作。 在数据挖掘所发现的知识模型中，关联规则模式是非常重要的一种，也是最活跃的一个分支。关联规则表示数据库中一组对象之间某种关联关系的规则。 本文通过Apriori算法，将收集来的历年全国各地区城镇居民食品消费情况进行数据挖掘，通过数据挖掘，找到频繁项集并得到关联规则。由关联规则进行相关分析，并将得出的分析结果应用到实际当中。 关键字：数据挖掘、关联规则、Apriori算法、食品消费分析 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；朗读 显示对应的拉丁字符的拼音 字典 1. 名词 1. summary 2. abstract 目 录 摘 要 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 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 参考文献 27 附 录 28 致 谢 32 第一章 引 言 数据挖掘（Data Mining，DM）又称数据库中的知识发现（Knowledge Discover in Database，KDD），是目前人工智能和数据库领域研究的热点问题，所谓数据挖掘是指从数据库的大量数据中揭示出隐含的、先前未知的并有潜在价值的信息的非平凡过程。 数据挖掘是一种决策支持过程，它主要基于人工智能、机器学习、模式识别、统计学、数据库、可视化技术等，高度自动化地分析企业的数据，做出归纳性的推理，从中挖掘出潜在的模式，帮助决策者调整市场策略，减少风险，做出正确的决策。 1.1 研究背景 自2000年以来，数据挖掘引起了信息产业界的极大关注，其主要原因是存在大量数据，可以广泛使用，并且迫切需要将这些数据转换成有用的信息和知识。获取的信息和知识可以广泛用于各种应用，包括商务管理，生产控制，市场分析，工程设计和科学探索等。 数据挖掘利用了统计学的抽样、估计和假设检验及人工智能、模式识别和机器学习的搜索算法、建模技术和学习理论等领域的思想。数据挖掘也吸纳了其他领域的思想，包括最优化、进化计算、信息论、信号处理、可视化和信息检索。其中的一些领域在数据挖掘中起到了重要的支撑作用。特别的，需要数据库系统提供有效的存储、索引和查询处理的支持。 广义上说，任何从数据库中挖掘信息的过程都叫做数据挖掘。从这点看来，数据挖掘就是BI（商业智能）。但从技术术语上说，数据挖掘(Data Mining)特指的是：源数据经过清洗和转换等成为适合于挖掘的数据集。数据挖掘在这种具有固定形式的数据集上完成知识的提炼，最后以合适的知识模式用于进一步分析决策工作。从这种狭义的观点上，我们可以定义：数据挖掘是从特定形式的数据集中提炼知识的过程。数据挖掘往往针对特定的数据、特定的问题，选择一种或者多种挖掘算法，找到数据下面隐藏的规律，这些规律往往被用来预测、支持决策。 自 60 年代以来，数据库和信息技术已经系统地从原始的文件处理进化到复杂的、功能强大的数据库系统。自70年代以来，数据库系统的研究和开发已经从层次和网状数据库发展到开发关系数据库系统、数据建模工具、索引和数据组织技术。 自 80 年代中期以来，数据库技术的特点是广泛接受关系技术，研究和开发新的、功能强大的数据库系统。这些使用了先进的数据模型，如扩充关系、面向对象、对象-关系和演绎模型。 图1.1 数据库技术的进化 1.1.1 数据挖掘与传统分析方法的区别 数据挖掘与传统的数据分析（如查询、报表、联机应用分析）的本质区别是数据挖掘是在没有明确假设的前提下去挖掘信息、发现知识。数据挖掘所得到的信息应具有先未知，有效和可实用三个特征。 先前未知的信息是指该信息是预先未曾预料到的，即数据挖掘是要发现那些不可能靠直觉发现的信息或知识，甚至是违背直觉的信息或知识，挖掘出的信息越是出乎意料，就可能越有价值。在商业应用中最典型的例子就是一家连锁超市通过数据挖掘发现了小孩尿布与啤酒之间的联系[1]。 1.2 数据挖掘的主要问题 由于强调数据挖掘的主要问题，考虑挖掘技术、用户界面、性能和各种数据类型。这些问题介绍如下： 1.2.1数据挖掘技术和用户界面问题 这反映所挖掘的知识类型、在多粒度上挖掘知识的能力、领域知识的使用、特定的挖掘和知识显示。 1.2.2 挖掘不同类型的知识问题 由于不同的用户可能对不同类型的知识感兴趣，数据挖掘系统应当覆盖广谱的数据分析和知识发现任务，包括数据特征、区分、关联、聚类、趋势、偏差分析和类似性分析。这些任务可能以不同的方式使用相同的数据库，并需要开发大量数据挖掘技术。 1.2.3 多个抽象层的交互知识挖掘问题 由于很难准确地知道能够在数据库中发现什么，数据挖掘过程应当是交互的。 1.2.4 数据挖掘结果的表示和显示问题 发现的知识应当用高级语言、可视化表示形式、或其它表示形式表示，使得知识易于理解，能够直接被人使用。如果数据挖掘系统是交互的，这一点尤为重要。这要求系统采用有表达能力的知识表示技术，如树、表、图、图表、交叉表、矩阵或曲线。 1.2.5处理噪音和不完全数据 存放在数据库中数据可能反映噪音、例外情况、或不完全的数据对象。这些对象可能搞乱分析过程，导致数据与所构造的知识模型过分适应。其结果是，所发现的模式的精确性可能很差。 1.2.6 模式评估——兴趣度问题 数据挖掘系统可能发现数以千计的模式。对于给定的用户，许多模式不是有趣的，它们表示平凡知识或缺乏新颖性。 1.2.7 性能问题 这包括数据挖掘算法的有效性、可规模性和并行处理。 1.2.8 数据挖掘算法的有效性和可规模性 为了有效地从数据库中大量数据提取信息，数据挖掘算法必须是有效的和可规模化的。 1.2.9 并行、分布和增量挖掘算法 许多数据库的大容量、数据的广泛分布和一些数据挖掘算法的计算复杂性是促使开发并行和分布式数据挖掘算法的因素。这些算法将数据划分成部分，这些部分可以并行处理，然后合并每部分的结果。 1.3 数据挖掘的研究方向 1) 数据输入形式的多样性 应用中经常需要对一些半结构化、非结构化的数据形式如文本、图形、数学公式、图像或WWW 资源进行挖掘操作, 但目前的数据挖掘工具一般只能提供对数值型的结构化数据的处理, 对数据中存在缺损或噪声的情况也没有有效的方法。 2) 数据挖掘算法的有效性与可测性 数据挖掘的对象向更大型的数据库、更高的维数和属性之间更复杂的关系方向发展。更多的记录和属性意味着更大、更高维的搜索空间, 从而导致组合爆炸; 属性之间的关系变得更为复杂如表现为层次结构, 会大大提高知识搜索的代价。从1个大型数据库中抽取知识的算法必须高效、可测量, 即数据挖掘算法的运行时间必须可预测, 且可接受, 指数和多项式算法等复杂性的算法不具有实用价值。目前的研究发展到用并行处理或抽样的方法处理大规模数据以获得较高的计算效率, 根据问题的定义和领域知识选择出需要的属性从而降低维数并有效处理属性之间的复杂关系等。 3) 用户参与和领域知识 有效的决策过程往往需要多次交互和多次反复, 使数据挖掘的结果准确地描述数据挖掘的要求, 并易于表达, 实现在多抽象层次上交互挖掘知识。目前许多知识发现系统和工具缺乏与用户的交互, 难以有效利用领域知识。 4) 证实技术的局限 数据挖掘使用特定的分析方法或逻辑形式发现知识, 如归纳方法。但系统可能无法去交互证实所发现的知识的正确或正确的程度, 使得发现的知识没有普遍性而不能成为有用的知识。 5) 知识的表达和解释机制 许多应用中重要的是用户能够理解发现的知识。这要求知识的表达不仅限于数字或符号, 而是更易于理解的方式, 如图形、自然语言和可视化技术等。同时, 只有当数据挖掘系统能提供更好的解释机制, 用户才能更有效地评价这些知识, 并且区分出哪些是真正有用的知识, 哪些只是常识性的知识或异常情况。 6) 知识的维护和更新 新的知识发现可能导致以前发现的知识失效, 因此知识需要动态维护和及时更新。目前研究采用增量更新的方法、数据快照和时间戳等方法来维护已有的知识。 7) 私有性和安全性 数据挖掘能从不同角度、不同抽象层次上观察数据, 将影响到数据挖掘的私有性和安全性。通过研究数据挖掘导致的数据非法侵入, 可改进数据库安全方法, 以避免信息泄露。 8) 支持的局限与其他系统的集成 目前的数据挖掘系统尚不能支持多种平台。一些产品是基于PC的, 一些是面向大型主机系统的, 还有一些是面向客户机ö服务器环境的。另外, 由于方法功能单一的发现系统的适应范围的限制, 要充分发挥系统的作用, 应该和数据库、知识库、专家系统、决策支持系统、可视化工具、网络技术等进行有机集成[5,6]。 1.4拟解决的问题 通过调查9类食品历年2000-2009年（2004年除外），各地区的人均食物消费情况，可以清楚的知道各地区人民的饮食习惯，对这些数据进行数据挖掘，得到相应的关联规则。依据得到的关联规则，可以建立相应的食品供给机制，提供合理的饮食建议，可以使人们在日常的饮食中吃的更健康。 本文通过对采集来的数据进行数据挖掘，运用apriori算法进行相关的挖掘，得到关联规则，并应用到实际。 1.5 本章小结 本章介绍了数据挖掘技术的研究意义及技术背景、数据挖掘的主要问题、论文选题的依据、数据挖掘的研究方向及我们所做论文的主要内容等。在当今社会，正处于信息爆炸的年代，怎样从众多的、无序、纷乱、复杂的信息中得到自己有用的信息，这就需要一定的信息处理能力。数据挖掘就是在这样的环境中得到完善和发展，数据挖掘技术融合了当今的许多学科的最新研究成果和技术而形成的一个具有自己特色的研究分支。可进行数据挖掘的项目极其丰富，进行数据挖掘的方法也有很多种，本文是对全国各地区历年对9类食品的消费情况进行数据挖掘，并得出相应的分析。 第二章 数据挖掘概念与技术 数据挖掘(Data Mining)：就是从存放在数据库，数据仓库或其他信息库中的大量的数据中获取有效的、新颖的、潜在有用的、最终可理解模式的非平凡过程。 数据挖掘涉及多学科技术的集成，包括数据库技术、统计、机器学习、高性能计算、模式识别、神经网络、数据可视化、信息提取、图像与信号处理和空间数据分析。 简单地说，数据挖掘是从大量数据中提取或“挖掘”知识。该术语实际上有点用词不当。注意，从矿石或砂子挖掘黄金称作黄金挖掘，而不是砂石挖掘。这样，数据挖掘应当更正确地命名为“从数据中挖掘知识”。“知识挖掘”是一个短术语，可能不能强调从大量数据中挖掘。毕竟，挖掘是一个很生动的术语，它抓住了从大量的、未加工的材料中发现少量金块这一过程的特点（图 2.1）。 通过数据挖掘，可以从数据库提取有趣的知识、规律、或高层信息，并可以从不同角度观察或浏览。发现的知识可以用于决策、过程控制、信息管理、查询处理、等等。因此，数据挖掘被信息产业界认为是数据库系统最重要的前沿之一，是信息产业最有前途的交叉学科。 2.1数据挖掘的任务 通常数据挖掘的任务可以分为预测和描述两大类。 预测任务是根据己知属性的值，推断特定的未知属性的值;被预测的属性一般称为目标变量，用于做预测的属性称为说明变量。预测分为针对离散的目标变量的分类任务和针对连续的目标变量的回归任务。 描述任务是刻画数据库中数据的一般特性，目标是以简洁概要的方式导出概括数据中潜在联系的模式。描述任务可以发现的模式有：概念描述(特征化和比较)、关联规则、聚类、异常等。 2.1.1 数据挖掘的职能 数据挖掘能做以下七种不同事情（分析方法） 分类（Classification） 估值（Estimation） 预言（Prediction） 相关性分组或关联规则（Affinity grouping or association rules） 聚集（Clustering） 描述和可视化（Description and Visualization） 复杂数据类型挖掘(Text, Web ,图形图像，视频，音频等) 以上七种数据挖掘的分析方法可以分为两类：直接数据挖掘；间接数据挖掘 1） 直接数据挖掘 目标是利用可用的数据建立一个模型，这个模型对剩余的数据，对一个特定的变量（可以理解成数据库中表的属性，即列）进行描述。 2）间接数据挖掘 目标中没有选出某一具体的变量，用模型进行描述；而是在所有的变量中建立起某种关系 。 分类、估值、预言属于直接数据挖掘；后三种属于间接数据挖掘 数据挖掘的范围非常广泛，可以是社会科学、经济学、商业数据、科学处理产生的数据和卫星观测得到的数据，它们的数据结构也各不相同，可以是层次的、网状的、关系的和面向对象的数据。 2.2 数据挖掘的对象 数据挖掘是一个以数据库、人工智能、数理统计、可视化四大支柱技术为基础，多学科交叉、渗透、融合形成的新的交叉学科，其研究内容十分广泛。目前存在很多数据挖掘方法或算法，因此有必要对这些方法进行分门别类。描述或说明一个算法涉及三个部分：输入、输出和处理过程。数据挖掘算法的输入是数据库，算法的输出是要发现的知识或模式，算法的处理过程则涉及具体的搜索方法。从算法的输入、输出和处理过程三个角度，我们可以确定这样几种分类标准：挖掘对象、挖掘方法、挖掘任务。 根据挖掘对象分，有如下若干种数据库或数据源:关系数据库、面向对象数据库、空间数据库、时态数据库、文本数据库、多媒体数据库、异质数据库、历史数据库，以及万维网(Web)。 根据挖掘方法分，可粗分为:统计方法，机器学习方法，神经网络方法和数据库方法。统计方法可细分为:回归分析，判别分析，聚类分析，探索性分析等。机器学习可细分为:归纳学习方法，基于范例学习，遗传算法等。神经网络方法可细分为:前向神经网络，自组织神经网络等。数据库方法主要是多维数据分析或OLAP方法，另外还有面向属性的归纳方法。 2.3 可数据挖掘的知识模型 根据挖掘任务分，数据挖掘主要发现以下五类知识: 1、广义型知识:根据数据的微观特性发现其表征的、带有普遍性的、较高层次概念的、中观或宏观的知识； 2、分类型知识:反映同类事物共同性质的特征型知识和不同事物之间差异性特征知识。用于反映数据的汇聚模式或根据对象的属性区分其所属类别； 3、关联型知识:反映一个事件和其他事件之间依赖或关联的知识，又称依赖关系。这类知识可用于数据库中的归一化，查询优化等； 4、预测型知识:通过时间序列型数据，有历史的和当前的数据去预测未来的情况。它实际上是一种以时间为关键属性的关联知识； 5、偏差型知识:通过分析标准类以外的特例，数据聚类外的离群值，实际观测值和系统预测值间的显著差别，来对差异和极端特例进行描述； 2.4 数据挖掘的技术 2.4.1 数据挖掘的方法 从不同的角度看, 数据挖掘技术有多种分类方法, 如根据发现的知识种类分类, 根据挖掘的数据库类型分类, 根据挖掘方法分类, 根据挖掘的途径分类, 根据所采用的技术分类等等。目前常用的数据挖掘技术内容包括如下: 1) 决策树方法 利用信息论中的互信息(信息增益) 寻找数据库中具有最大信息量的字段, 建立决策树的一个结点, 再根据字段的不同取值建立树的分支; 在每个分支子集中重复建立树的下层结点和分支的过程, 即可建立决策树。国际上最有影响和最早的决策树算法是Quiulan 研制的ID3 方法, 数据库越大它的效果越好。此后又发展了各种决策树方法, 如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个旧种群(父代) 选出生命力强的个体, 产生新种群(后代) 的过程。②交叉(重组)。选择2 个不同个体(染色体) 的部分(基因) 进行交换, 形成新个体。③变异(突变)。对某些个体的某些基因进行变异(1 变0, 0 变1)。这种遗传算法可以起到产生优良后代的作用。这些后代需满足适应度值, 经过若干代的遗传, 将得到满足要求的后代(问题的解)。遗传算法已在优化计算和分类机器学习方面显示了明显的优势。 7) 公式发现 在工程和科学数据库(由实验数据组成) 中, 对若干数据项(变量) 进行一定的数学运算, 求得相应的数学公式。比较典型的BACON 发现系统完成了对物理学中大量定律的重新发现。 其基本思想是: 对数据项进行初等数学运算(加、减、乘、除等) , 形成组合数据项, 若它的值为常数项, 就得到了组合数据项等于常数的公式。 8) 统计分析方法 在数据库字段项之间存在两种关系: 函数关系(能用函数公式表示的确定性关系) 和相关关系(不能用函数公式表示, 但仍是相关确定关系)。对它们的分析采用如下方法:回归分析、相关分析、主成分分析。 9) 模糊集方法 利用模糊集理论对实际问题进行模糊评判、模糊决策、模糊模式识别和模糊聚类分析。模糊性是客观存在的。系统的复杂性越高, 精确化能力就越低, 即模糊性就越强。这是Zadeh 总结出的互克性原理。 10) 可视化技术 可视化数据分析技术拓宽了传统的图表功能, 使用户对数据的剖析更清楚。例如, 把数据库中的多维数据变成多种图形, 这对揭示数据的状况、内在本质及规律性起了很大作用。 2.4.2 数据挖掘的步骤 一些人只是把数据挖掘视为数据库中知识发现过程的一个基本步骤。知识发现过程，由以下步骤组成： 1、数据清理（消除噪音或不一致数据）； 2、数据集成（多种数据源可以组合在一起）； 3、数据选择（从数据库中提取与分析任务相关的数据）； 4、数据变换（数据变换或统一成适合挖掘的形式；如，通过汇总或聚集操作）； 5、数据挖掘（基本步骤，使用智能方法提取数据模式）； 6、模式评估（根据某种兴趣度度量，识别提供知识的真正有趣的模式）； 7、知识表示（使用可视化和知识表示技术，向用户提供挖掘的知识）。 数据挖掘步骤可以与用户或知识库交互。有趣的模式提供给用户，或作为新的知识存放在知识库中。注意，根据这种观点，数据挖掘只是整个过程中的一步，尽管是最重要的一步，因为它发现隐藏的模式。 第三章 关联规则 3.1 由购物篮分析得到的关联规则 作为超市的一名销售经理，应该最想知道的是消费者购物的心里，消费者在购物时最想买到的物品，在买一件商品时会有这个商品会再买那种商品，也是哪几种商品会被消费者频繁购买？例如，在一家超市中，人们发现了一个特别有趣的现象：尿布与啤酒这两种风马牛不相及的商品居然摆在一起。但这一奇怪的举措居然使尿布和啤酒的销量大幅增加了。这可不是一个笑话，而是一直被商家所津津乐道的发生在美国沃尔玛连锁超市的真实案例。 原来，美国的妇女通常在家照顾孩子，所以她们经常会嘱咐丈夫在下班回家的路上为孩子买尿布，而丈夫在买尿布的同时又会顺手购买自己爱喝的啤酒。这个发砚为商家带来了大量的利润，但是如何从浩如烟海却又杂乱无章的数据中，发现啤酒和尿布销售之间的联系呢？这又给了我们什么样的启示呢？[3] “啤酒”和“尿布”两个看上去没联系的两种商品放在一起，却获得了丰厚的利润，这种现象就是卖场中商品直接的关联性，研究“啤酒和尿布”关联的方法就是购物篮分析。 3.2 关联规则的相关概念 在数据挖掘所发现的知识模型中，关联规则模式是非常重要的一种，也是最活跃的一个分支。关联规则表示数据库中一组对象之间某种关联关系的规则。 关联规则挖掘是指发现大量数据中项集之间有趣的关联或相关联系，关联规则问题由R.Agrawal等在1993年提出，随即引起了广泛的关注。许多研究者对关联规则挖掘问题进行了深入的研究，对最初的关联规则挖掘算法进行了改进和扩展。同时，关联规则的挖掘被应用到许多其它领域的数据库，取得了良好的挖掘效果。 3.2.1 关联规则的概念 设I={,,…, }是项的集合。设任务相关的数据D是数据库事务的集合，其中每个事务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是项目的集合），支持度定义为： confidence(AB)=P(B|A) （3.2） 即：每个发现模式都应当由一个表示其有效性或“值得信赖性”的确定性度量。对于关联规则AB（其中A和B是项目的集合），其确定性度量置信度定义为： 同时满足最小支持度阈值（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]。 项的集合称为项集，包含k个项的项集称为k-项集。 3.3 关联规则挖掘的过程及分类 3.3.1 关联规则的挖掘过程 关联规则的挖掘是一个两步的过程： 1）找出所有频繁项集：根据定义，这些项集出现的频繁性至少和预定义的最小支持度计数一样。 2）由频繁项集产生强关联规则：根据定义，这些规则必须满足最小支持度和最小置信度。 关联规则的第一阶段必须从原始资料集合中，找出所有高频项目组（Large Itemsets）。第二阶段是要产生关联规则（Association Rules）。从高频项目组产生关联规则，是利用前一步骤的频繁k-项集来产生规则，在最小置信度（Minimum Confidence）的条件下，若这一规则所求得的置信度满足最小置信度，则称此规则为关联规则[4]。 3.3.2 关联规则的分类 按照不同情况，关联规则可以进行分类如下： 1、基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。 布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系；而数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数值型关联规则中也可以包含种类变量。 2、基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。 在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次的；而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。 3、基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。 在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品；而在多维的关联规则中，要处理的数据将会涉及多个维。换成另一句话，单维关联规则是处理单个属性中的一些关系；多维关联规则是处理各个属性之间的某些关系。例如：啤酒=>尿布，这条规则只涉及到用户的购买的物品；性别=“女”=>职业=“秘书”，这条规则就涉及到两个字段的信息，是两个维上的一条关联规则。 3.4 关联规则的相关算法 3.4.1 Apriori算法 Apriori算法：使用候选项集找频繁项集 Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。 在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。 Apriori算法的基本思想是： 1、找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。 2、由频繁项集产生强关联规则，这些规则必须满足最小支持度和最小可信度。 3、使用第一步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递推的方法。 可能产生大量的候选集,以及可能需要重复扫描数据库，是Apriori算法的两大缺点。 3.4.2 基于划分的算法 基于划分的算法是由Savasere等人设计的。这个算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频集，然后把产生的频集合并，用来生成所有可能的频集，最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存，每个阶段只需被扫描一次。该算法是可以高度并行的，可以把每一分块分别分配给某一个处理器生成频集。算法的正确性是由每一个可能的频集，至少在某一个分块中保证是频繁项集。产生频集的每一个循环结束后，处理器之间进行通信来产生全局的候选k-项集。通常这里的通信过程是算法执行时间的主要瓶颈；而另一方面，每个独立的处理器生成频集的时间也是一个瓶颈。 3.4.3 FP-树频集算法 针对Apriori算法的固有缺陷，J. Han等提出了不产生候选挖掘频繁项集的方法：FP-树频集算法。采用分而治之的策略，在经过第一遍扫描之后，把数据库中的频集压缩进一棵频繁模式树（FP-tree），同时依然保留其中的关联信息，随后再将FP-tree分化成一些条件库，每个库和一个长度为1的频集相关，然后再对这些条件库分别进行挖掘。当原始数据量很大的时候，也可以结合划分的方法,使得一个FP-tree可以放入主存中。实验表明，FP-tree对不同长度的规则都有很好的适应性，同时在效率上较之Apriori算法有巨大的提高。 本文主要是应用Apriori算法，对本文中的是实例进行分析、研究。 第四章 Apriori算法 4.1 Apriori算法的定义及思想 Apriori 算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。算法的名字基于这样的事实：算法使用频繁项集性质的先验知识，正如我们将看到的。Apriori 使用一种称作逐层搜索的迭代方法，k-项集用于探索(k+1)-项集。 4.1.1 Apriori算法的基本思想 (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 。 根据逆反公理：即若一个集合不能通过测试，该集合所有超集也不能通过同样的测试。因此很容易确定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 算法采用的模式匹配方式，在检测大量的候选项集，特别是在挖掘长模式时，对数据库的重复扫描非常多，大量的时间消耗在内存与数据库中的数据的交换上[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设成一个很低的值，那么算法的效率就成了一个很难处理的问题。 第五章 应用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个数据。 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),1,0)” 依据同样的方法，向下拖拽，得到的就是符合“小于0.33的数值输出为：1，不符合的输出为：0”。在新的一列中输入“=IF(AND(C2>=0.33,C2<=0.48),1,0)”表示落在[0.33，0.48]区间的数值输出为：1，不在这个区间的数值为：0。把得到的结果存储到新的数据表格： 5.2.3 应用算法进行数据挖掘 应用MATLAB软件进行数据挖掘 通过File-Import Data将生成的布尔数据库导入到MATLAB中， 将导入到MATLAB中的Data文件，重命名为X， 在MATLAB中新建4个M文件：association_rules.m;subset.m;setsub.m;in.m，其中association_rules.m为主程序。 在command window窗口中分别输入： 得到的频繁2-项集为： 得到的频繁3-项集为： 得到的频繁4-项集为： 得到的频繁5项集： 5.2.4 结果分析 通过应用Apriori算法对历年各地区城镇居民的9种食品消费进行数据挖掘，得到最高频繁项为： 9 12 24 27 30 频繁项：9==豆制品的比例在[0.0033-0.0066]的范围； 12==油脂类的比例在[0.009-0.018]的范围； 24==菜类的比例在[0.034-0.047]的范围； 27==干鲜瓜果类的比例在[0.025-0.034]的范围； 30==奶及奶制品的比例在[0.01-0.02]的范围。 由这个结果可以知道豆制品、油脂类、菜类、干鲜瓜果类和奶及奶制品是城镇居民的日常主要消费食品。 以上5类食品中，我们可以看出，人们在购买食物的过程中会考虑到食物搭配的问题，例如：油脂类，它有油脂类点心、煎炸馅饼、油炸食品、油炸食品等其他高热量高脂肪油腻食品；干鲜瓜果类包括：山楂、西瓜、苹果、香蕉等干鲜水果。油脂类的购买范围是在[0.009-0.018]之间，在日常消费的比重中占的比例相对较低，而干鲜瓜果类[0.025-0.034]在日常消费的比重中占的比例在这5类食品中是最高的，这也说明：随着生活质量的提高，餐桌也变得丰富，人们在食品方面的消费观也有了改变，开始注重营养的均衡，饮食的多样性。 参考文献 1、杨会志. 数据挖掘的技术与商业定义及其研究对象[J].河北科技大学学报，2000年第21卷 第3期 总第54期 2、M.M. 盖伯 .科学的数据挖掘和知识发现（原则和基础）[J].国外科技新书评介.2010年第6期（总第278期） 3、高勇 著.啤酒与尿布-神奇的购物篮分析[M]. 清华大学出版社.2008 4、刘辉，胡大治.数据挖掘技术的研究与应用[J].华东理工大学学报(自然科学版)，2008年4月，34(2)：290-295. 5、Park J S, Ashok Savasere. An Effective Hash-based Algorithm for Mining Association Ules [A]. In: Heraklion·Proceedings of the ACM SIGMOD [C]. Greece: Ctete Press, 1995.175-186. 6、Han J. Mining Knowledge at Multiple Concept Levels [A]. In: Proceedings of the 4th International Conference on Information and Knowledge Management (CIKM ’95) [C]. Maryland: Baltimore Press, 1995.19-24. 7. 潘东静. 基于关联规则的数据挖掘研究[J] 枣庄师专学报，2001.10（5） 8、王雪岩. 关联规则挖掘算法的研究[D] . 哈尔滨工程大学硕士论文,2006. 9、陆丽娜, 陈亚萍, 魏恒义, 等. 挖掘关联规则中的Apriori算法的研究[J]. 小型微型计算机系统, 2000, 21 (9) ：940-943. 附 录 附录A：MATLAB主程序：association_rules.m 子程序1：subset.m 子程序2：setsub.m 子程序3：in.m 致 谢 四年的读书生活在这个季节即将划上一个句号，而于我的人生却只是一个逗号，我将面对又一次征程的开始。四年的求学生涯在师长、亲友的大力支持下，走得辛苦却也收获满囊，在论文即将付梓之际，思绪万千，心情久久不能平静。 伟人、名人为我所崇拜，可是我更急切地要把我的敬意和赞美献给一位平凡的人，我的导师-----王培吉老师。我不是您最出色的学生，而您却是我最尊敬的老师。您治学严谨，学识渊博，思想深邃，视野雄阔，为我营造了一种良好的精神氛围。授人以鱼不如授人以渔，置身其间，耳濡目染，潜移默化，使我不仅接受了全新的思想观念，树立了宏伟的学术目标，领会了基本的思考方式，从论文题目的选定到论文写作的指导，经由您悉心的点拨，再经思考后的领悟，常常让我有“山重水复疑无路,柳暗花明又一村”。 感谢我的爸爸妈妈，焉得谖草，言树之背，养育之恩，无以回报，你们永远健康快乐是我最大的心愿。在论文即将完成之际，我的心情无法平静，从开始进入课题到论文的顺利完成，有多少可敬的师长、同学、朋友给了我无言的帮助，在这里请接受我诚挚谢意！ 同时也感谢学院为我提供良好的做毕业论文的环境。 最后再一次感谢所有在毕业论文中曾经帮助过我的良师益友和同学，以及在论文中被我引用或参考的论著的作者。 本文档由香当网(https://www.xiangdang.net)用户上传
