Apriori算法实验报告及程序

1、Apriori算法实验报告学号：姓名：专业：计算机应用技术教师：计算机学院目录1APRIORI实验 . .11.1实验背景 .11.1.1国内外研究概况 .11.1.2发展趋势 .11.2实验内容与要求 .11.2.1实验内容 .11.2.2实验要求 .11.2.3实验目的 .12 APRIORI算法分析与实验环境 .22.1APRIORI算法的描述 .22.2A算法的步骤 .2PRIORI2.3开发环境 .22.3.1软件环境 .22.3.2硬件环境 .32.4本章小结 .33算法的设计.43.1APRIORI算法整体框架 .43.2主要的数据结构与函数.43.2.1数据结构 .43.2.2

2、主要的程序 .53.2.3连接与剪枝操作 .53.3本章小结 .54数据库的设计与数据的来源.64.1正确性验证数据 . .64.2实验数据 .64.3本章小结 .75实验结果与性能分析 .85.1APRIORI实验界面 .85.2实验的正确性验证 .85.3实验性能分析 .95.3.1固定最小支持度改变数据量. 95.3.2固定数据量改变最小支持度. 105.3.3实验结果分析 .105.4 本章小结 .116 总结与体会 .121 Apriori实验1.1实验背景现在 ,数据挖掘作为从数据中获取信息的有效方法,越来越受到人们的重视。关联规则挖掘首先是用来发现购物篮数据事务中各项之间的有趣联

3、系。从那以后,关联规则就成为数据挖掘的重要研究方向 , 它是要找出隐藏在数据间的相互关系。目前关联规则挖掘的研究工作主要包括：Apriori算法的扩展、数量关联规则挖掘、关联规则增量式更新、无须生成候选项目集的关联规则挖掘、最大频繁项目集挖掘、约束性关联规则挖掘以及并行及分布关联规则挖掘算法等。关联规则的挖掘问题就是在事务数据库D 中找出具有用户给定的满足一定条件的最小支持度Minsup 和最小置信度Minconf的关联规则。国内外研究概况1993 年， Agrawal 等人首先提出关联规则概念，关联规则挖掘便迅速受到数据挖掘领域专家的广泛关注 . 迄今关联规则挖掘技术得到了较为深入的发展。A

4、priori算法是关联规则挖掘经典算法。针对该算法的缺点，许多学者提出了改进算法，主要有基于哈希优化和基于事务压缩等。发展趋势关联规则挖掘作为数据挖掘的重要研究内容之一 , 主要研究事务数据库、关系数据库和其他信息存储中的大量数据项之间隐藏的、有趣的规律。关联规则挖掘最初仅限于事务数据库的布尔型关联规则 , 近年来广泛应用于关系数据库 , 因此 , 积极开展在关系数据库中挖掘关联规则的相关研究具有重要的意义。 近年来 , 已经有很多基于 Apriori 算法的改进和优化。 研究者还对数据挖掘的理论进行了有益的探索，将概念格和粗糙集应用于关联规则挖掘中，获得了显著的效果。到目前为止，关联规则的挖

5、掘已经取得了令人瞩目的成绩，包括：单机环境下的关联规则挖掘算法；多值属性关联规则挖掘；关联规则更新算法；基于约束条件的关联规则挖掘；关联规则并行及分布挖掘算法等。1.2实验内容与要求实验内容编程实现Apriori算法：要求使a , b, c, d, e, f , g, h, i , j 10个项目随机产生数据记录并存入数据库。从数据库读取记录进行Apriori实验，获得频繁集以及关联规则，实现可视化。并用课堂上 PPT的实例测试其正确性。用实验要求1、程序结构：包括前台工具和数据库；2、设定项目种类为10个，随机产生事务，生成数据库；3、正确性验证（可用课堂上的例子）；4、算法效率的研究：在支

6、持度固定数据量不同的时候测量运行时间；在数据量固定，支持度不同的时候测量运行时间；5、注意界面的设计， 输入最小支持度和最小可信度，能够输出并显示频繁项目集以及关联规则。实验目的1、加强对Apriori算法的理解；2、锻炼分析问题、解决问题并动手实践的能力。2 Apriori算法分析与实验环境2.1 Apriori算法的描述Apriori 算法是一种找频繁项目集的基本算法。其基本原理是逐层搜索的迭代：频繁 K项 Lk 集用于搜索频繁 (K+1)项集 Lk+1，如此下去，直到不能找到维度更高的频繁项集为止。这种方法依赖连接和剪枝这两步来实现。算法的第一次遍历仅仅计算每个项目的具体值的数量，以确定

7、大型l 项集。随后的遍历，第k 次遍历，包括两个阶段。首先，使用在第(k-1) 次遍历中找到的大项集Lk-1和产生候选项集 Ck。接着扫描数据库，计算Ck 中候选的支持度。用Hash 树可以有效地确定Ck 中包含在一个给定的事务t 中的候选。如果某项集满足最小支持度,则称它为频繁项集。2.2 Apriori算法的步骤步骤如下 :1、设定最小支持度s 和最小置信度c；2、 Apriori算法使用候选项集。首先产生出候选的项的集合大于或等于最小支持度, 则该候选项集为频繁项集；3、在 Apriori算法的过程中 , 首先从数据库读入所有的事务, 即候选项集 , 若候选项集的支持度, 每个项都被看作

8、候选1- 项集 , 得出各项的支持度 , 再使用频繁 1- 项集集合来产生候选 2- 项集集合 , 因为先验原理保证所有非频繁的 1-项集的超集都是非频繁的；4、再扫描数据库 , 得出候选 2- 项集集合 , 再找出频繁 2- 项集 , 并利用这些频繁 2- 项集集合来产生候选 3- 项集；5、重复扫描数据库 , 与最小支持度比较 , 产生更高层次的频繁项集 , 再从该集合里产生下一级候选项集 , 直到不再产生新的候选项集为止。2.3开发环境软件环境(1) 编程软件： Jdk 开发包 +eclipse 集成开发环境Eclipse是一个开放源代码的、基于Java 的可扩展开发平台。就其本身而言，

9、它只是一个框架和一组服务，用于通过插件组件构建开发环境。幸运的是，Eclipse附带了一个标准的插件集，包括 Java 开发工具（ Java Development Kit， JDK）。(2) 数据库软件： SQL Server 2008SQL Server 2008在 Microsoft的数据平台上发布，可以组织管理任何数据。可以将结构化、半结构化和非结构化文档的数据直接存储到数据库中。可以对数据进行查询、搜索、同步、报告和分析之类的操作。数据可以存储在各种设备上，从数据中心最大的服务器一直到桌面计算机和移动设备，它都可以控制数据而不用管数据存储在哪里。(3) 办公软件： Excel 201

10、0Excel是一款试算表办公 软件。它是微软办公套装软件office的重要的组成部分，它是集统计分析、数据处理和辅助决策等功能于一身，现在金融、统计财经、管理等众多领域广泛应用。本实验主要用来为固定数据量改变最小支持数以及固定最小支持数改变数据量两种情况进行时间分析提供可视化图表。硬件环境装有 Windows 7旗舰版电脑。2.4本章小结本章的内容主要是为了引出本实验的主要算法以及对算法的实现环境做了介绍。3 算法的设计3.1 Apriori算法整体框架Apriori 开始定义 minsup、minconfK=1, 产生 C1扫描数据库，产生 L1生成 1项频繁项目集由Lk 连接，剪枝产生 C

11、k+1Ck为空是Apriori 结束图 3.1 Apriori3.2主要的数据结构与函数数据结构class Transactionpublic int pid;public String itemset;该类表示表中的一条记录。生成关联规则生成频繁项目集扫描，产生 Lk+1否实验流程图class Daopublic ArrayList<Transaction> Query(String sql)该类用于访问数据库操作。class Kfppublic char kfpstr=new charApriori.ITEMSIZE;public int index=-1;public int

12、 support=0;public boolean isfp=true;该类代表一个频繁项目。主要的程序Java 中最常用的集合类是List和 Map。 List的具体实现包括ArrayList和 Vector，它们是可变大小的列表，比较适合构建、存储和操作任何类型对象的元素列表。List适用于按数值索引访问元素的情形。HashMap： Map 接口的常用实现类，系统<key,value>当成一个整体进行处理，系统总是根据Hash 算法来计算<key,value>的存储位置，这样可以保证能快速存、取Map的<key,value>对。ArrayList<

13、Transaction> alTransactions：保存表中的所有记录ArrayList<Kfp> alKfpsl：临时存储频繁项目的集合，存储连接后的结果ArrayList<Kfp> SureFpset：保存频繁k 项集ArrayList<Kfp> SureFpsetPrio：保存频繁k-1 项集ArrayList<String> notFpList：保存一定不是频繁项目的集合，用于剪枝HashMap<String, Integer> KfpSuppor:频繁项目集及其对应的支持数HashMap<String,Dou

14、ble> guanlianguize:关联规则及其置信度连接与剪枝操作对于连接操作的两个字符串( 长度为 k) ，它们必须有k-1个相同的字符才能做连接操作。例如 :abc 和 abd 可以连接成 abcd，abd 和 bcd 可以连接成 abcd，而 abc 和 ade 就不可以做连接操作。整个连接过程类似归并排序中的归并操作对于任一频繁项目集的所有非空子集也必须是频繁的，反之，如果某个候选的非空子集不是频繁的，那么该候选集肯定不是频繁的，将其剪枝。3.3本章小结本章主要介绍了算法设计的整体流程并且也对主要程序和操作作了简要的说明。4 数据库的设计与数据的来源本实验的数据均存储于数据库

15、中。数据库 yuzm中共产生 6 张表。表 test 为测试用表，用于程序的正确性验证。还有 5 张表存储随机产生的实验数据。其中数据库的结构如下图所示。图 4.1数据库结构4.1 正确性验证数据表 test为 PPT 上的实例，用于正确性验证。数据的item个数为 5，其中的九行数据均由SQL语句产生，表的每一行都是一个“0”“ 1”的字符串，字符串长度等于商品种类，其中“0”表示该商品不存在， “ 1”表示该商品存在。表的全部数据如图4.2 。图 4.2表 test4.2实验数据5 张表是通过算法随机产生的具有不同数据量的数据集，假设商品种类为10 种，表的每一行都是一个“ 0”“ 1”的

16、字符串，字符串长度等于商品种类，其中“0”表示该商品不存在，“ 1”表示该商品存在。其中表data1 共随机产生1 万行数据，表data2 产生 5 万行数据，表data3 产生 25 万行数据，表data4 产生 50 万行数据，表data5 产生 75 万行数据。部分数据如图4.3 。图 4.3实验用表（部分）4.3本章小结本章主要对数据库的设计与数据来源做出了说明。5 实验结果与性能分析5.1 Apriori实验界面其中可信度可自由设置，默认为 0.7 。而支持度记为最小支持度与数据量的比例。实验数据可以下拉选择 6 张表中的任意一张。如下图所示：图 5.1实验界面5.2实验的正确性验证

17、运行程序，我们选择表test ，即可进行正确性验证，实验结果如下图：图 5.2 正确性验证最终实验结果与 ppt 的结果相吻合，表明程序编写正确。5.3实验性能分析为了对本程序的实验进行性能分析，我们分别采用固定数据量改变最小支持数以及固定最小支持数改变数据量两种情况进行时间分析, 其中最小置信度设为0.7 不变。5.3.1 固定最小支持度改变数据量设支持度为 0.2 ，最小可信度为 0.7 。具体实验数据量与执行时间如下：表 5.1数据量对性能的影响数据量（万行）15255075时间（秒）48.2128.2366.9623.41032.3图 5.3数据量对性能的影响固定数据量改变最小支持度设

18、实验数据量固定改变最小支持度，具体如下所示：表 5.2最小支持度对性能的影响最小支持度0.150.200.250.300.35时间（秒 / 1万）175.64914.28.55.2时间（秒 / 5万）294.1128.258.841.525.7时间（秒 / 25 万） 531.3366.9246.5185.6154.0图 5.4最小支持度对性能的影响实验结果分析由以上实验我们可以看出，实验时间会随着数据量的增大而增大，并且随着最小支持度的增大而减小。并且他们之间的变化类似于某种指数函数的变化趋势。Apriori的时间主要消耗在4 个方面：1、利用 K 频繁集连接产生K+1 候选集时，判断连接的

19、条件时比较的次数太多。假设项集个数为m的频繁集合Lk，判断连接条件时比较的时间复杂度为O（ K*m2）。而且本实验的m都很大；2、对 Ck 中任意的一个c 的 k 个（ k-1 ）子集是否都在Lk-1 中。在平均情况下，对所有候选项集需要扫描次数为|Ck|*|Lk-1|*k/2；3、为了得到所有的候选频集的支持度，需要扫描N 次；4、扫描一次数据库需时间O（k|T| ）。 |T| 为交易数量，k 交易长度k5.4本章小结Apriori算法因自身需要多次扫描数据库，并且经过复杂的连接剪枝操作而产生大量候选集以及进行大量的模式匹配计算的缺陷，使得其在 I/O 上的花费时间很多，从而导致算法的效率不

20、是太高。6 总结与体会通过本次实验，让我明白了什么是Apriori算法和数据之间的关联性，Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法，为以后进步学习数据挖掘知识打下了良好的基础。同时我也更加深刻理解了Apriori算法的原理及其实现的内部细节，同时通过实现这一经典的数据挖掘算法，也让我更深刻的体会到数据挖掘对于知识发现的重要性，尽管实现了算法，但其中可能还有可以改进的地方，尤其是程序的运行效率方面。Apriori算法实验不仅使得我对该算法的理解更加上升了一个层次，同时也使得我更加了解了java 编程语言，使用更加得心应手。public class Apriori exte

21、nds JFrame implements ActionListener /public static int ITEMSIZE=10;public final int FRAMEWIDTH=800;public final int FRAMEHEIGHT=600;/JPanel up=null;JPanel up_up=null;TextField textFieldName=null;JPanel up_down=null;JPanel up_down_left=null;JLabel conflabel=null;JLabel c1=null;JLabel c2=null;JLabel

22、c3=null;JLabel c4=null;JLabel c5=null;JLabel c6=null;JLabel c7=null;JLabel c8=null;JTextField conf=null;JLabel supportlabel=null;JTextField support=null;JPanel up_down_right=null;JComboBox jComboBoxDateSize=null;/下拉框JButton jButtonMine=null;JPanel down=null;TextArea textArea=null;int fpstep=1;int fp

23、index=0;Dao dao=null;double MinSupport=0.20;double MinConfi=0.70;double DateSize=9.0;ArrayList<Transaction> alTransactions=null;ArrayList<Kfp> alKfps=null;ArrayList<String> notFpList=null;ArrayList<Kfp> SureFpset=null;ArrayList<Kfp> SureFpsetPrio=null;HashMap<String,

24、 Integer> KfpSupport=null;ArrayList<String> alsurekfpstr=null;HashMap<String,Double> guanlianguize=null;ArrayList<String> isaddarrStrings=null;int AuxArr=null;public static void main(String args)Apriori A=new Apriori();public Apriori()JPanel up=new JPanel(new GridLayout(2, 1);JP

25、anel up_up=new JPanel(new GridLayout(1, ITEMSIZE);/TextField textFieldName=new TextFieldITEMSIZE;/for(int i=0;i<ITEMSIZE;i+)/ textFieldNamei=new TextField();/ up_up.add(textFieldNamei);/c1=new JLabel("数 ");up_up.add(c1);c2=new JLabel("据 ");up_up.add(c2);c3=new JLabel("挖 &

26、quot;);up_up.add(c3);c4=new JLabel("掘 ");up_up.add(c4);c5=new JLabel("实 ");up_up.add(c5);c6=new JLabel("验 ");up_up.add(c6);c7=new JLabel("-");up_up.add(c7);c8=new JLabel("Apriori");up_up.add(c8);up_down=new JPanel(new GridLayout(1, 2);up_down_left=ne

27、w JPanel(new GridLayout(1, 4);conflabel=new JLabel("可信度：");conf=new JTextField();conf.setText("0.7");supportlabel=new JLabel("支持度：");support=new JTextField();support.setText("0.2");up_down_left.add(conflabel);up_down_left.add(conf);up_down_left.add(supportlabe

28、l);up_down_left.add(support);up_down_right=new JPanel(new GridLayout(1, 2);jComboBoxDateSize=new JComboBox();/下拉框jComboBoxDateSize.addItem("test");jComboBoxDateSize.addItem("data1");jComboBoxDateSize.addItem("data2");jComboBoxDateSize.addItem("data3");jComboBo

29、xDateSize.addItem("data4");jComboBoxDateSize.addItem("data5");jComboBoxDateSize.addActionListener(this);jButtonMine=new JButton("开始挖掘 ");jButtonMine.addActionListener(this);up_down_right.add(jComboBoxDateSize);up_down_right.add(jButtonMine);up_down.add(up_down_left);up_

30、down.add(up_down_right);up.add(up_up);up.add(up_down);down=new JPanel(new BorderLayout() ;textArea=new TextArea();/textArea.setFont(new Font(Font.DIALOG,Font.ITALIC , 20); textArea.setFont(new Font(Font.DIALOG,Font.PLAIN , 20); down.add(textArea);this.setLayout(new BorderLayout();this.setSize(FRAMEW

31、IDTH, FRAMEHEIGHT);this.setLocation(100, 100);this.setSize(this.FRAMEWIDTH, this.FRAMEHEIGHT);this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);this.setTitle("Apriori");/up.setSize(this.FRAMEWIDTH, 100);this.add(up,BorderLayout.NORTH);/down.setLocation(0, 100);/down.setSize(this.FRAMEWID

32、TH, this.FRAMEHEIGHT-100);this.add(down);this.setVisible(true);public void InitDate(String table)fpstep=1;AuxArr=new intITEMSIZE+1ITEMSIZE+1;alKfps=new ArrayList<Kfp>();notFpList=new ArrayList<String>();SureFpset=new ArrayList<Kfp>();SureFpsetPrio=new ArrayList<Kfp>();dao=new

33、 Dao();KfpSupport=new HashMap<String, Integer>();alsurekfpstr=new ArrayList<String>();guanlianguize=new HashMap<String,Double>();isaddarrStrings=new ArrayList<String>();alTransactions=dao.Query("select * from "+table);this.DateSize=alTransactions.size();public void

34、ShowkFp(ArrayList<Kfp> SureFpset)int steptemp=fpstep;textArea.append("频繁 "+(steptemp)+"项集 rn");for(int i=0;i<SureFpset.size();i+)Kfp k=SureFpset.get(i);int tempindex=k.index;String string=String.copyValueOf(k.kfpstr, 0, +tempindex);int support=KfpSupport.get(string);text

35、Area.append(string+"-"+support+"-"+support/DateSize+"rn");public void ShowkFp2(HashMap<String,Double> SureFpset)textArea.append("关联规则 rn");Set<String> keys=(Set<String>) SureFpset.keySet();for(String keyString:keys)textArea.append(keyString+&

36、quot;-"+SureFpset.get(keyString)+"rn");public void DataMine()int fpsteptemp=0;if(fpstep = 1)for(int i=0;i<Apriori.ITEMSIZE;i+)Kfp kfp=new Kfp();kfp.kfpstr+kfp.index=(char) ('a'+i);kfp.support=0;kfp.isfp=false;alKfps.add(kfp);DealSupport();SaveNotFpBySupport();SaveSureFp();S

37、howkFp(alKfps);fpstep+;while(!alKfps.isEmpty()alKfps.clear();for (int i = 0; i < SureFpset.size(); i+)Kfp k1 = SureFpset.get(i);for (int j = i + 1; j < SureFpset.size(); j+)Kfp k2 = SureFpset.get(j);Kfp resultKfp = Joint(k1, k2);int tempindex=resultKfp.index;Stringstring=String.copyValueOf(res

38、ultKfp.kfpstr,0,+tempindex);if(string.charAt(0) = 0)continue;SubSet subSet= new SubSet();ArrayList<String>alStrings=subSet.displaySubSet1(string.toCharArray();int p=0;for(;p<alStrings.size();p+)String string2=alStrings.get(p);if(notFpList.contains(string2)break;if(p != alStrings.size()conti

39、nue;if (!isaddarrStrings.contains(string) isaddarrStrings.add(string);alKfps.add(resultKfp);SureFpsetPrio.clear();for(int i=0;i<SureFpset.size();i+)SureFpsetPrio.add(SureFpset.get(i);Guanlianguize();SureFpset.clear();DealSupport();SaveNotFpBySupport();/ Cut();if (!alKfps.isEmpty()SaveSureFp();Sho

40、wkFp(SureFpset);fpstep+;public void Guanlianguize()for(int i=0;i<SureFpsetPrio.size();i+)Kfp k=SureFpsetPrio.get(i);int len = k.index;String string=String.copyValueOf(k.kfpstr, 0, len+1);if(!alsurekfpstr.contains(string)alsurekfpstr.add(string);SubSet s=new SubSet();for(int i=0;i<alsurekfpstr.size();i+)String kfpstr=alsurekfpstr.get(i);char kfpchararr=kfpstr.toCharArray();ArrayList<String> aList=s.SubSet3(kfpchararr,kfpstr.length(); for(int j=0;j<aList.size();j+)String guizetemp=""String kfpstr1=aList.get(j);char kfpchararr1=kfpstr1.toCharArray();int index