手机版

主页 > 文库下载 > 实用文档 > 内容

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

发布时间：2024-10-11 来源：未知

小中大

字号：

毕业论文综述

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 因为在扫描k候选项集时，如果被扫描源项目集的项目个数小于k，则不可能该项目集能对此k频繁项目集有支持。

特性4如果肛频繁项目集Lk中的单个项目I的个数小于k，则I不可能包含在频繁k+l项同集中。证明见文献[3,18]。

2、优化策略

(1)压缩数据库事务集。

优化1：产生一项数据库D的每个事务的项目计数项mun，每次扫描计数前比较mun与k，如果mun小于k，则可以忽略扣描本事务，同时置mun=0。

优化2：候选项计数过程中，如果数据库D的某事务及其项目子集末被计数，则置删：mun=0。

(2)提高剪枝效率。

优化3：首次支持度裁减后，比较非频繁项口集项目

数和频繁项目集项目，取小值集进行剪枝操作[24,26]。

五、结束语

关联规则挖掘是当前数据挖掘领域的主要研究课题。本文对关联规则挖掘中经典算法Apriori算法从数据事务压缩及提高剪枝效率方面进行了改进，一定程度上提高了关联规则的挖掘效率。软件回归测试的关键是测试用例的优化选择[21,29]。文中借用数据挖掘中的规则分类技术给出一种等价类划分方法，主要介绍了在回归测试中利用基于决策树规则的分类技

毕业论文综述

术来划分等价类的方法模型。可借由此方法编程实现测试用例的自动生成工具。[18,30]该方法模型采用基于规则的排序策略对决策树规则进行排序，按分类规则将测试用例划分为若干个等价类，然后在每个类中选择少数有代表性的测试用例进行测试，测试成本，实现最小回归测试集的生成。

参考文献：

[1] 康敏砀，张安．改进的Apfiofi数据挖掘算法的应用[J]．火力与指挥控制，2009，34(10)：111—114．

[2]Agmwal R lmielinski T，Swami A．Mining associationroles between sets of items in large database[J]．In Proc．ACM SIl2VIOD Intl．Conf．Management of Data，1993，l(1)'207-216．

[3]徐章艳，刘美玲，张师超，等．Apriori算法的三种优化方法[J]．计算机工程与应用，2004，40(36)：190—193．

[4]柴华昕。王勇．Apriori挖掘频繁项目集算法的改进[J]．计算机工程与应用。2007，43(24)：158-161．

[5]谭俊璐，武建华．基于决策树规则的分类算法研究[J]．计算机工程与设计，2010，31(5)：1017-1019．

[6] Chen Leida．Data mining methods，applications，tools[J]．Information System Management，2000，17(1)：65-70．

[7] 马菁，顾景文．决策树在软件测试用例生成中的应用[J]．计算机技术与发展，2008，18(2)：66—69．

[8]Han Jiawei，Kamber M．数据挖掘：概念与技术[M]．北京：机械工业出版社，2008．

[9]Tan Pangning，Steinbach M，Kumar V．数据挖掘导论[M]．北京：人民邮电出版社，2006：127—136．

[10]王小丽，段永颢．软件回归测试用例选取方法研究[J]．空间控制技术与应用，2010，36(3)：47—49．

[11]曾强，洪玫，杨吴苏，等．软什回归测试中的自动化测试生成方法[J]．计算机应用研究，2009，26(6)：2349—2351．

[12] 杨修国等;浅谈数据挖掘与图书管理. [J]《科学咨询》;2008年:7~9

[13] 张志山；关联规则挖掘在图书馆管理系统中的研究与应用.[D] 广东工业大学；2009年:3~9

[14] 李秋丹;数据挖掘相关算法的研究与平台实现[D];大连理工大学;2004年:176~193