基于APRIORI算法的关联规则挖掘系统的设计与实现

基于APRIORI算法的关联规则挖掘系统的设计与实现 毕业设计(论文) 基于Apriori算法的关联规则挖掘系统的设计与实现 论文作者姓名: 申请学位专业: 申请学位类别: 指导教师姓名,职称,: 论文提交日期: 基于Apriori算法的关联规则挖掘系统的设计与实现 摘 要 随着信息时代的发展，信息量呈几何级数增长，人们发现从这些海量信息中获取有用的信息越来越困难，要找出信息背后隐藏的规律更是不可想象。数据挖掘就是从大量数据中获取有用信息的一门新技术，关联规则挖掘是数据挖掘中的一种。本文详细论述了基于Apriori算法的关联规则挖掘系统的设计开发过程。系统基于经典的Apriori算法，对事务数据库进行了位图矩阵转换，大大提高了搜索效率，并能分别挖掘频繁项集和关联规则。 论文组织如下:首先介绍了数据挖掘的产生、定义和应用;接着阐述了关联规则挖掘的基本概念;然后对系统的需求进行了，并提出设计;紧接着是系统的具体实现;最后对系统进行了测试，将系统用于挖掘中药方剂库中的药对药组，验证了系统的正确性和实用性。 关键词:数据挖掘;关联规则;Apriori算法 The Design and Implementation of Association Rules Mining System based on Apriori Arithmetic Abstract With the development of the information era, the quantity of information increases in the way of geometric series, and people find that it is more and more difficult to obtain valuable informatin and it is incogitable to find out the rules hiding in the information. Data mining is a new technology to mine valuable informatin from abundant data, and association rules mining is a method of data mining. This paper elaborates on the process of the design and development of association rules mining system based on Apriori . The system is based upon classical Apriori arithmetic, and converts chinese medicine prescriptions database to a bitmap matrix, which greatly enhances the efficiency of search, and can mine frequent items and association rules respectively. The paper is organized as following: Firstly, introduces the generation, definition and application of data mining; Secondly, sets forth the conception of association rules mining; Thirdly, analyzes the demand of the system, and propses the design project and implements the system; Finally, gives a test to mine chinese medicine groups from a chinese medicine prescriptions data, which proves the system valid and applicable. Key words: Data mining; Apriori; Chinese traditional medicine 目录 论文总页数:27页 1引言 ................................................................................................................................................ 2 2数据挖掘概述 ................................................................................................................................ 2 2.1数据挖掘的产生 ................................................................................................................... 2 2.2数据挖掘的定义 ................................................................................................................... 2 2.3 数据挖掘的应用 .................................................................................................................. 53关联规则挖掘 ................................................................................................................................ 5 3.1基本概念 ............................................................................................................................... 5 3.2购物篮分析 ........................................................................................................................... 6 3.3Apriori经典算法 ................................................................................................................... 7 4需求分析和设计方案 .................................................................................................................... 9 4.1需求分析 ............................................................................................................................... 9 4.2设计方案 ............................................................................................................................... 9 5基于Apriori算法的关联规则挖掘系统 .................................................................................... 11 5.1数据挖掘在中药方剂研究中的应用 ................................................................................. 11 5.2基于Apriori算法的关联规则挖掘系统的实现 ............................................................... 12 5.2.1连接数据库 .................................................................................................................... 12 5.2.2位图矩阵的建立 ............................................................................................................ 13 5.2.3频繁项集 ........................................................................................................................ 14 5.2.4关联规则 ........................................................................................................................ 16 6系统测试 ...................................................................................................................................... 20 6.1系统的使用 ......................................................................................................................... 20 6.2对显示数据的解释 ............................................................................................................. 23 6.3分析 ..................................................................................................................................... 24 结 论 ......................................................................................................................................... 25 参考文献 ......................................................................................................................................... 25 致 谢 ......................................................................................................................................... 27 声 明 ......................................................................................................................................... 28 1引言 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数据越来越多。激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行更高层次的分析，以便更好地利用这些数据。目前的数据库系统可以高效地实现数据的录入、查询、统计等功能，但无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋势。缺乏找出数据背后隐藏的知识的手段，导致了“数据爆炸但知识贫乏”的现象。于是数据挖掘技术应运而生，并显示出强大的生命力。数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。它使人类分析问和发现知识能力得到了延伸。 2数据挖掘概述 2.1数据挖掘的产生 随着信息时代的发展，信息量呈几何级数增长，然而用于对这些数据进行分析处理的工具却很少，人们拥有了海量的数据的同时却苦于信息的缺乏。而激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行更高层次的分析，以便更好地利用这些数据。目前的数据库系统可以高效地实现数据的录入、查询、统计等功能，但无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋势。缺乏挖掘数据背后隐藏的知识的手段，导致了“数据爆炸但知识贫乏”的现象。信息爆炸是一把双刃剑:巨量的信息既是最重要的财富，又是最危险的杀手。巨量信息也导致决策与理解危机。面对“人人被数据淹没，人们却饥饿于知识”的挑战，数据挖掘和知识发现技术应运而生，并得以蓬勃发展，越来越显示出其强大的生命力。 数据挖掘是信息技术自然演化的结果。演化过程的见证是数据库业界开发以下功能:数据收集和数据库创建，数据管理(包括数据存储和检索，数据库事务处理)，以及数据分析与理解(涉及数据仓库和数据挖掘)。例如，数据收集和数据库创建机制的早期开发已成为稍后数据存储和检索、查询和事务处理有效机制开发的必备基础。随着提供查询和事务处理的大量数据库系统广泛付诸实践，数据分析和理解自然成为下一个目标。 2.2数据挖掘的定义 数据挖掘是从大量数据中提取或“挖掘”知识。具体来说，数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。 人们把原始数据看作是形成知识的源泉，就像从矿石中采矿一样。原始数据有结构化的，如关系数据库中的数据，也有半结构化的，如文本、图形、图像数 据，甚至是分布在网络上的异构型数据。发现知识的方法可以是数学的，也可以是非数学的;可以是演绎的，也可以是归纳的。发现了的知识可以被用于信息管理、查询优化、决策支持、过程控制等，还可以用于数据自身的维护。因此，数据挖掘是一门很广义的交叉学科，它汇聚了不同领域的研究者，尤其是数据库、人工智能、数理统计、可视化、并行计算等方面的学者和工程技术人员。 数据挖掘使用复杂的统计分析和建模技术来揭示企业数据库中隐藏的模式与关系——而这些模式是有可能被普通的方法所忽略的。数据挖掘从数据的分析入手、帮助决策，能从数据中寻找有价值的规律的技术。同时它也代表一个分析过程，我们具体化为方法学。实际上，数据库中的知识发现是一门交叉性学科，涉及到机器学习、模式识别、统计学、智能数据库、知识获取、数据可视化、高性能计算、专家系统等多个领域。从数据库中发现出来的知识可以用在信息管理、过程控制、科学研究、决策支持等许多方面。 特别要指出的是，数据挖掘技术从一开始就是面向应用的。它不仅是面向特定数据库的简单检索查询调用，而且要对这些数据进行微观、中观乃至宏观的统计、分析、综合和推理，以指导实际问题的求解，企图发现事件间的相互关联，甚至利用已有的数据对未来的活动进行预测。 许多人把数据挖掘视为另一个常用的术语数据库中的知识发现或KDD (knowledge discovery in databases)的同义词。而另一些人只是把数据挖掘视为数据库中知识发现过程的一个基本步骤。知识发现过程如图1所示，由以下步骤组成: 1) 数据清理(消除噪声或不一致数据) 2) 数据集成(多种数据源可以组合在一起) 3) 数据选择(从数据库中检索与分析任务相关的数据) 4) 数据变换(数据变换或统一成适合挖掘的形式，如通过汇总或聚集操作) 5) 数据挖掘(基本步骤，使用智能方法提取数据模式) 6) 模式评估(根据某种兴趣度度量，识别出真正有 趣的模式) 7) 知识表示(使用可视化和知识表示技术，向用户提供挖掘的知识) 图1 知识发现过程 虽然数据挖掘是知识发现过程的一个步骤，然而，在产业界、媒体和数据库研究界，“数据挖掘”比较长的术语“数据库中知识发现”更流行。目前比较公认的定义是Fayyad等给出的:KDD是从数据集中识别出有效的、新颖的、潜在有用的以及最终可理解模式的高级处理过程。这里的高级处理过程是指一个多步骤的处理过程，多步骤之间相互影响、反复调整，形成一种螺旋式的上升过程。而数据挖掘则指的是从存放在数据库、数据仓库或其他信息库中的大量数据中挖掘有趣知识的过程。数据挖掘其实是知识发现的核心部分，而知识发现是在积累了大量数据后，从中识别出有效的、新颖的、潜在的、有用的及最终可以理解的知识，人们利用这些知识改进工作，提高效率和效益。 KDD是一门交叉学科，涉及到人工智能、机器学习、模式识别、统计学、智能数据库、知识获取、数据可视化、专家系统等多个领域。数据挖掘算法的好坏将直接影响到所发现知识的好坏。数据挖掘的任务是从数据中发现模式。 虽然数据挖掘是知识发现过程的一个步骤，然而，在产业界、媒体和数据库研究界，“数据挖掘”比较长的术语“数据库中知识发现”更流行。目前比较公认的定义是Fayyad等给出的:KDD是从数据集中识别出有效的、新颖的、潜在有用的以及最终可理解模式的高级处理过程。这里的高级处理过程是指一个多步骤的处理过程，多步骤之间相互影响、反复调整，形成一种螺旋式的上升过程。而数据挖掘则指的是从存放在数据库、数据仓库或其他信息库中的大量数据中挖掘有趣知识的过程。其实数据挖掘是知识发现的核心部分，而知识发现是在积累了大量数据后，从中识别出有效的、新颖的、潜在的、有用的及最终可以理解的知识，人们利用这些知识改进工作，提高效率和效益。 KDD是一门交叉学科，涉及到人工智能、机器学习、模式识别、统计学、智能数据库、知识获取、数据可视化、专家系统等多个领域。数据挖掘算法的好坏将直接影响到所发现知识的好坏。数据挖掘的任务是从数据中发现模式。 2.3 数据挖掘的应用 数据挖掘可以应用在各个不同的领域。电讯公司和信用卡公司是用数据挖掘检测欺诈行为的先行者。保险公司和证券公司也开始采用数据挖掘来减少欺诈。医疗应用是另一个前景广阔的产业:数据挖掘可以用来预测外科手术、医疗试验和药物治疗的效果。零销商更多的使用数据挖掘来决定每种商品在不同地点的库存，通过数据挖掘更灵活的使用促销和优惠券手段。制药公司通过挖掘巨大的化学物质和基因对疾病的影响的数据库来判断哪些物质可能对治疗某种疾病产生效果。 以下为数据挖掘的一些成功案例:(1)加拿大BC省电话公司要求加拿大Simon Fraser大学KDD研究组根据其拥有的十多年的客户数据，总结、分析并提出新的电话收费和管理办法，制定既有利于公司又有利于客户的优惠政策。(2)美国著名的国家篮球队NBA的教练，利用IBM公司提供的数据挖掘工具临场决定替换队员。大约20个NBA球队使用了IBM公司开发的数据挖掘应用软件Advanced Scout系统来优化他们的战术组合。例如Scout就因为研究了魔术队队员不同的布阵安排，在与迈阿密热队的比赛中找到了获胜的机会。(3)国外使用数据挖掘技术，对西药的新药开发研究也早已利用数据挖掘技术。我国在中药的数据挖掘技术上已步入起步阶段。 3关联规则挖掘 关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。随着大量数据不停地收集和存储，许多业界人士对于从他们的数据库中挖掘关联规则越来越感兴趣。从大量商务事务记录中发现有趣的关联关系，可以帮助许多商务决策的制定，如分类设计、交叉购物和促销分析。 关联规则挖掘的一个典型例子是购物篮分析。该过程通过发现顾客放入其购物篮中不同商品之间的联系，分析顾客的购买习惯。通过了解哪些商品频繁地被顾客同时购买，这种关联的发现可以帮助零售商制定营销策略。例如，如果顾客购买牛奶的同时也购买面包(和什么类型的面包)的可能性有多大,通过帮助零售商有选择地经销和安排货架，这种信息可以引导销售。例如，将牛奶和面包尽可能放近一些，可以进一步刺激一次去商店同时购买这些商品。 3.1基本概念 设I={i1,i2,…,im}是项的集合。设任务相关的数据D是数据库事务的集合，其中每个事务T是项的集合，使得T,I。每个事务有一个标示符，称作TID。设A是一个项集，事务T包含A当且仅当 A,T。关联规则是形如A,B的蕴涵式， ,,其中AI，BI，并且A?B=,。如果D中有s%的事务包含A?B，则称关联规则A,B在事务数据库D中具有大小为s%的支持度，它是概率P(A?B)。如 果D中包含项目集A的事务中有c%的事务同时也包含项目集B，则称规则A,B在事务数据库D中具有大小为c%的置信度，它是条件概率P(B|A)。即: support(A,B)= P(A?B) confidence(A,B)=P(B|A) 如果不考虑关联规则的支持度和置信度，在事务数据库中可以发现无穷多的规则。事实上，满足一定的支持度和置信度的关联规则才是有意义的。因此，需要给定两个阈值:最小支持度(min_sup)和最小置信度(min_conf)。同时满足最小支持度阈值和最小置信度阈值的规则称作强规则。为方便计，我们用0%和100%之间的值而不是用0到1之间的值表示支持度和置信度。 项的集合称为项集(itemset)。包含k个项的项集称为k-项集。项集的出现频率是包含项集的事务数，简称为项集的支持计数。如果项集满足最小支持度，则称它为频繁项集(frequent itemset)。频繁k-项集的集合通常记作Lk。 3.2购物篮分析 先看看购物篮分析，这是一个引发关联规则挖掘的典型例子。 例1 超市的经理想了解顾客的购物习惯。例如，想知道“哪些商品组合常常被顾客同时购买,”为回答这一问题，可以在超市的事务数据库上运行购物篮分析。分析结果可以帮助超市经理设计不同的商品布局。一种策略是:将经常一块购买的商品放近一些，以便进一步刺激这些商品一起销售。例如，如果顾客购买牛奶也倾向于同时购买面包，那么将牛奶和面包摆放得近一点，可能有助于增加二者的销售。另一种策略是:将牛奶和面包分别放在超市的进、出口，可能诱发买这些商品的顾客一路挑选其他商品。例如，顾客在买了牛奶之后，去找面包，路上看到水果，可能会决定也买一些水果。购物篮分析也可以帮助超市规划什么商品降价出售。如果顾客趋向于同时购买数字彩电和DVD机，数字彩电降价出售可能既促使购买数字彩电，又促使购买DVD机。 想象全域是超市中可利用的商品的集合，则每种商品有一个布尔变量，表示该商品的有无。每个篮子则可用一个布尔向量表示。可以分析布尔向量，得到反映商品频繁关联或同时购买的购买模式。这些模式可以用关联规则的形式表示。例如，购买牛奶也趋向于同时购买面包可以用以下关联规则表示: 牛奶,面包 [support= 2% ,confidence= 60% ] 规则的支持度和置信度是两个规则兴趣度度量，它们分别反映发现规则的有用性和确定性。上一条关联规则的支持度2%意味分析中的全部事务的 2%同时购买牛奶和面包。置信度60%意味购买牛奶的顾客60%也购买面包。如果关联规则满足最小支持度阈值和最小置信度阈值，则被认为是有趣的。这些阈值可以由用户或领域专家设定。 3.3Apriori经典算法 下面介绍形式最简单的关联规则挖掘方法。这种关联规则是单维、单层、布尔关联规则，如前面讨论的购物篮分析。 关联规则的挖掘分两步: 1) 找出所有频繁项集:根据定义，这些项集出现的频繁性至少和预定义的最小支持计数一样。 2) 由频繁项集产生强关联规则:根据定义，这些规则必须满足最小支持度和最小置信度。 也可以使用附加的兴趣度度量。这两步中，第二步最容易。挖掘关联规则的总体性能由第一步决定。 Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。算法的名字基于频繁项集性质的先验知识，正如我们将看到的。Apriori使用逐层搜索的迭代方法，k-项集用于探索(k+1)-项集。首先，找出频繁1-项集的集合。该集合记作L1。L1用于找频繁2-项集的集合L2，而L2用于找L3，如此下去，直到不能找到频繁 k-项集。找每个Lk需要一次数据库扫描。 为提高频繁项集逐层产生的效率，一种称作Apriori性质的重要性质用于压缩搜索空间。我们先介绍该性质，然后用一个例子解释它的使用。 Apriori性质:频繁项集的所有非空子集都必须也是频繁的。Apriori性质基于如下观察:根据定义，如果项集I不满足最小支持度阈值min_sup，则I不是频繁的，即P(I)规范

编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载