数据挖掘关联规则文献综述

毕业论文综述

Apriori算法综述

系 别：软件学院 专 业：10软件工程

姓 名：傅昱 学 号：320107101147

摘要：本文介绍了关联规则中Apriori算法的研究情况，关联规则挖掘的Apriori算法是数据库挖掘的最经典算法并得到广泛应用，在介绍关联规则挖掘和Apriori算法的基础上指出传统算法应用中衡量标准的不足，并指出了Apriori算法在实际中的应用领域，展望了关联规则中Apriori算法的未来研究方向[1]。

关键字：数据挖掘；关联规则；Apriori算法；综述

一、引言

数据挖掘是从大量的数据中挖掘哪些令人感兴趣的、有用的、隐含的、先前未知的和可能有用的模式或知识[2] 。关联规则挖掘首先是用来发现购物篮数据事务中各项之间的有趣联系。从那以后，关联规则就成为数据挖掘的重要研究方向，它是要找出隐藏在数据间的相互关系。定义为，设I={I1，I2…Im}是m个不同项的项集，X∈I，Y∈I，并且x和Y是不相交的项集，即X∩Y=Φ[3,11]。关联规则挖掘问题首先是由R．Agrawal等人于1993年提出的，而后又进一步提出了著名的Apriori算法，该算法的主要思想是首先寻找给定数据集中的频繁项集，然后通过频繁项集生成强关联规则"[4]。

二、 Apriori算法的起源和概念

Apriori算法是由Rakesh Agrawal和RnamakrishnanSrikant在1994年提出的关联规则的经典算法，它是所有关联规则挖掘算法的核心。[5,9,10]Apriori算法将关联规则挖掘划分为两个子问题：1)在事务集D中寻找满足所有最小支持度阈值min_sup的频繁项集。2)利用频繁项集来生成所有满足最小置信度阈值rain—conf的关联规则。其中的子问题。1是Apriori算法所要解决的核心问题。Apriori算法主要通过迭代的方法来求出事务集D中所有的频繁项集[6]。

Apriori算法是一种以概率为基础的具有影响的挖掘布尔型关联规则频繁项集的算法。它利用逐层搜索的迭代方法找f“数据库中项口的关系，以形成规则，其过程由连接(类矩阵运

[7]算)与剪枝(去掉那些没必要的中问结果)组成。该算法中项集(Itemset)的概念即为项的集合。

包含K个项的集合为k项集。项集的出现频率是包含项集的事务数，称为项集的频率。如果项集满足最小支持度，则称它为频繁项集。频繁k项集的集合计作b。

Apriori算法利用连接和剪枝两个步骤寻找出事务之间的强关联规则从而在商品零售业、网站开发、医学领域、金融投资业、图书管理系统等大型数据库中得到广泛的应用。

三、 Apriori算法的应用

1、农业病虫害分析

随着科技的快速发展，自然环境遭到不同程度的破坏，致使各种害虫繁衍很快，但不同的害虫对环境的要求是不一样的，有的适合在温度较低的环境里生存，有的则适合在较高温度的环境里生存，还有其它各种不同的生存环境。为了了解各种害虫的不同生理特点，更好的灭虫，可以对各种害虫的数量和生存的环境条件做一下分析。[13]Apriori算法能很好的解决这一问题。例如对水稻二化螟害虫的分析，能根据环境的变化，更好地消灭害虫。

2、试卷成绩分析

将关联规则Apriori算法应用于试卷成绩分析中，首先对数据进行预处理，然后使用

毕业论文综述

Apriori算法挖掘学生各科目试卷成绩的优良影响关系，最终产生关联规则，用以指导学生的学习及今后的工作[14]。

3、英语教师课堂话语分析

为在教学过程中提高学生认知和语言习得能力，运用关联规则的经典挖掘算法州耐研究英语教师口语语料分布特点，建立教师提问语、指令语和母语使用之间的关联性，并结合Bloom的认知发展类型理论分析学习者思维变化能力与人的认知能力之间的关系。

4、电子商务中的应用

随着数据库技术的迅速发展以及数据库管理系统的广泛应用，电子商务网站积累的数据越来越多，面对海量的存储数据，如何从中发现有价值的信息或知识是一项非常艰巨的任务。

[15]关联规则的发现是数据挖掘中最成功和最重要的一项任务，它的目标是发现数据集中所有的频繁模式。

5、科学数据分析

在地球科学数据分析中，关联模式可以揭示海洋、陆地和大气过程之问的有意义的关系。这些信息能够帮助地球科学家更好的理解地球系统中不同的自然力之间的相互作用。

四、针对Apriori算法的优化策略

Apriori算法的计算复杂度受以下几个因素的限制 1)最小支持度阈值和最小置信度阈值；2)项数(维度)；3)事务数；4)事务的平均宽度。

在实际应用中，发现Apriori算法存在如下一些主要的缺陷1)频繁的扫描数据库；2)不适用于稠密集的关联规则挖掘；3)可能生成的关联规则过于庞大。近年来，不少学者针对Apriori算法的缺陷对算法提出不同的改进策略，概括起来主要有以下的几类：1)基于逆向运算的优化策略怕2)基于哈希表的优化策略3)基于划分的优化策略4)基于事务压缩的优化策略5)基于采样的优化策略6)基于数据库结构变换的优化策略[16,23,26]。

1、几个特性

特性1任何频繁项目集的所有非空子集也是频繁的，非频繁项目集的超集是非频繁的。证明见文献见[17]。

特性2如某事务项目数小于肛频繁项同集的项同个数，则在更新频繁项目集时可以不扫描。

证明3 因为 …… 此处隐藏：2705字，全部文档内容请下载后查看。喜欢就下载吧 ……