论文部分内容阅读
摘要： 现在全球经济发展正在进入信息经济时代，各种形式的信息大量地产生和收集导致了信息爆炸，如何采用基于关联规则的数据挖掘技术发现超市事务数据库中的关联规则是本文所研究和探讨的重点。
关键词： 数据挖掘 关联规则 超市事务数据库
1.引言
目前，在需要处理大数据量的科研领域中，数据挖掘受到越来越多的关注。我们可以利用数据挖掘技术从海量数据中发现有用信息，帮助商家了解客户以往的需求趋势，并预测未来，从而给商家带来巨大的利润。在数据挖掘领域，采用关联规则在大型事务数据库中进行数据挖掘是一个重要的研究内容。关联规则是美国IBM Almaden Research Center的Rabesh Agrawal等人于1993年首先提出的KDD研究中的一个重要课题。关联规则挖掘的一般对象是事务数据库，这种数据库的主要应用在零售业，比如超级市场的销售管理。关联规则就是发现事务数据库中不同商品（项）（Item，指事务中的内容，比如，面包、牛奶等都是项目）之间是否存在某种关联关系。通过这些规则找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响。发现这样的规则可以应用于商品货架设计、货存安排以及根据购买模式对用户进行分类。
2.关联规则描述
目前关联规则挖掘主要考虑支持度和置信度两个阈值。设X是项集，T是数据库DB中的任意一个记录。X的支持度是指支持X的记录数与全体记录数的比，Support（X）=|{T|
Y，T∈DB}|/|{T|T∪X
T。支持度可理解为在DB中随机抽取一个记录，该记录同时支持X和Y的概率。置信度可理解为在支持X的记录全体中随机取一个记录，该记录支持Y的概率。
3.发现关联规则的操作步骤
目前，由于条码技术的发展，顾客在超市中购买商品的信息可以很方便地被存放在数据库中，针对数据库中大量的数据，我们如何发现它们之间存在的关联是本文主要讨论的问题。关联规则的挖掘问题就是在超市事务数据库DB中找出具有用户给定的最小支持度和最小置信度的关联规则。关联规则的挖掘对市场调节和争取顾客方面的应用是极有价值的。因此，有必要采用快速算法从超市事务数据库中挖掘关联规则。由超市事务数据库发现关联规则挖掘可以分以下两步完成：
（1）找出超市事务数据库DB中所有大于等于用户指定最小支持度的项目集，具有最小支持度的项目集称为频繁项集。
（2）利用频繁项集生成所期望的关联规则，即这些规则必须满足最小支持度min_supp和最小置信度min_conf。
事实上，第一步的任务是迅速高效地找出超市事务数据库DB中全部频繁项集，数据挖掘所面临的最大的挑战是计算效率问题，解决这一问题的途径是产生高效的数据挖掘算法，但从超市事务数据库中产生频繁项集既费时又占用空间，所以说第一步是关联规则挖掘的核心问题，是衡量关联规则挖掘算法的标准。当找到所有的频繁项集后，相应的关联规则将很容易生成，目前大多数的关联规则挖掘算法研究是针对第一步而提出的，本文重点讨论第一个问题。
4.由超市事务数据库发现关联规则的总体设计
在现有的不少关联规则发现算法中，最著名的仍然是R.Agrawal本人在他自己的AIS算法基础上于1994年提出的Apriori算法，Apriori算法的基本思想是：利用“频繁项集的所有非空子集都必须也是频繁的”这一定理对事务数据库进行多遍扫描。
众所周知，对数据库的扫描伴随繁重的磁盘I/O任务，Apriori算法中，扫描次数较多，这样就大大限制了挖掘算法的速度。因此，在实际的应用中，减少对事务数据库的扫描次数，有效地减少数据的吞吐，将会有效提高算法的效率。为了高效率地在超市事务数据库中发现关联规则，本系统在Apriori算法的基础上采用基于划分的算法。该算法只对事务数据库DB扫描两次，大大减少了I/O操作，从而提高了算法的效率。
通过划分方法进行数据挖掘的过程总体设计包含三部分：
（1）在服务器端第一次扫描超市事务数据库中的表，按照超市事务数据库中不同项集的数量，以及兼顾客户端计算机硬件配置，对其进行数据分块，分块的大小选择要使得每个分块可以被放入主存。
（2）在各个客户端计算机上，利用并行技术分别访问服务器上的数据分块，求出各数据分块所对应的局部频繁项集，并将所求局部频繁项集存入服务器的一个指定表中。
（3）在服务器端，汇总各个分块数据生成的局部频繁项集，第二次扫描超市事务数据库中的总表，最终生成全局频繁项集。
一旦由超市事务数据库DB中的事务找出频繁项集，由它们产生强关联规则是直截了当的。所谓的强关联规则是指满足最小支持度和最小置信度的规则。
5.结论
利用并行处理的思想，划分的数据块分给多个处理机并行计算各数据块的局部频繁项集，然后各分块所求的局部频繁项集汇总到服务器上，再次扫描数据库最终求出全局频繁项集。这种将关联规则挖掘算法与并行处理相结合的方式能更大地提高算法的效率。今后，如何能够更有效地提高关联规则算法执行的效率，怎样设计更有效、更实用的算法，是我们需要进一步思考的问题。
关键词： 数据挖掘 关联规则 超市事务数据库
1.引言
目前，在需要处理大数据量的科研领域中，数据挖掘受到越来越多的关注。我们可以利用数据挖掘技术从海量数据中发现有用信息，帮助商家了解客户以往的需求趋势，并预测未来，从而给商家带来巨大的利润。在数据挖掘领域，采用关联规则在大型事务数据库中进行数据挖掘是一个重要的研究内容。关联规则是美国IBM Almaden Research Center的Rabesh Agrawal等人于1993年首先提出的KDD研究中的一个重要课题。关联规则挖掘的一般对象是事务数据库，这种数据库的主要应用在零售业，比如超级市场的销售管理。关联规则就是发现事务数据库中不同商品（项）（Item，指事务中的内容，比如，面包、牛奶等都是项目）之间是否存在某种关联关系。通过这些规则找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响。发现这样的规则可以应用于商品货架设计、货存安排以及根据购买模式对用户进行分类。
2.关联规则描述
目前关联规则挖掘主要考虑支持度和置信度两个阈值。设X是项集，T是数据库DB中的任意一个记录。X的支持度是指支持X的记录数与全体记录数的比，Support（X）=|{T|
Y，T∈DB}|/|{T|T∪XT。支持度可理解为在DB中随机抽取一个记录，该记录同时支持X和Y的概率。置信度可理解为在支持X的记录全体中随机取一个记录，该记录支持Y的概率。
3.发现关联规则的操作步骤
目前，由于条码技术的发展，顾客在超市中购买商品的信息可以很方便地被存放在数据库中，针对数据库中大量的数据，我们如何发现它们之间存在的关联是本文主要讨论的问题。关联规则的挖掘问题就是在超市事务数据库DB中找出具有用户给定的最小支持度和最小置信度的关联规则。关联规则的挖掘对市场调节和争取顾客方面的应用是极有价值的。因此，有必要采用快速算法从超市事务数据库中挖掘关联规则。由超市事务数据库发现关联规则挖掘可以分以下两步完成：
（1）找出超市事务数据库DB中所有大于等于用户指定最小支持度的项目集，具有最小支持度的项目集称为频繁项集。
（2）利用频繁项集生成所期望的关联规则，即这些规则必须满足最小支持度min_supp和最小置信度min_conf。
事实上，第一步的任务是迅速高效地找出超市事务数据库DB中全部频繁项集，数据挖掘所面临的最大的挑战是计算效率问题，解决这一问题的途径是产生高效的数据挖掘算法，但从超市事务数据库中产生频繁项集既费时又占用空间，所以说第一步是关联规则挖掘的核心问题，是衡量关联规则挖掘算法的标准。当找到所有的频繁项集后，相应的关联规则将很容易生成，目前大多数的关联规则挖掘算法研究是针对第一步而提出的，本文重点讨论第一个问题。
4.由超市事务数据库发现关联规则的总体设计
在现有的不少关联规则发现算法中，最著名的仍然是R.Agrawal本人在他自己的AIS算法基础上于1994年提出的Apriori算法，Apriori算法的基本思想是：利用“频繁项集的所有非空子集都必须也是频繁的”这一定理对事务数据库进行多遍扫描。
众所周知，对数据库的扫描伴随繁重的磁盘I/O任务，Apriori算法中，扫描次数较多，这样就大大限制了挖掘算法的速度。因此，在实际的应用中，减少对事务数据库的扫描次数，有效地减少数据的吞吐，将会有效提高算法的效率。为了高效率地在超市事务数据库中发现关联规则，本系统在Apriori算法的基础上采用基于划分的算法。该算法只对事务数据库DB扫描两次，大大减少了I/O操作，从而提高了算法的效率。
通过划分方法进行数据挖掘的过程总体设计包含三部分：
（1）在服务器端第一次扫描超市事务数据库中的表，按照超市事务数据库中不同项集的数量，以及兼顾客户端计算机硬件配置，对其进行数据分块，分块的大小选择要使得每个分块可以被放入主存。
（2）在各个客户端计算机上，利用并行技术分别访问服务器上的数据分块，求出各数据分块所对应的局部频繁项集，并将所求局部频繁项集存入服务器的一个指定表中。
（3）在服务器端，汇总各个分块数据生成的局部频繁项集，第二次扫描超市事务数据库中的总表，最终生成全局频繁项集。
一旦由超市事务数据库DB中的事务找出频繁项集，由它们产生强关联规则是直截了当的。所谓的强关联规则是指满足最小支持度和最小置信度的规则。
5.结论
利用并行处理的思想，划分的数据块分给多个处理机并行计算各数据块的局部频繁项集，然后各分块所求的局部频繁项集汇总到服务器上，再次扫描数据库最终求出全局频繁项集。这种将关联规则挖掘算法与并行处理相结合的方式能更大地提高算法的效率。今后，如何能够更有效地提高关联规则算法执行的效率，怎样设计更有效、更实用的算法，是我们需要进一步思考的问题。