Apriori算法实验报告材料及程序.pdf

《Apriori算法实验报告材料及程序.pdf》由会员分享，可在线阅读，更多相关《Apriori算法实验报告材料及程序.pdf（32页珍藏版）》请在三一文库上搜索。

1、实用文案 标准文档 Apriori算法实验报告 学号： 姓名： 专业：计算机应用技术 教师： 计算机学院 实用文案 标准文档 目录 1 APRIORI实验 . . 1 1.1实验背景 . 1 1.1.1 国内外研究概况 . 1 1.1.2 发展趋势 . 1 1.2实验内容与要求 . 1 1.2.1 实验内容 . 1 1.2.2 实验要求 . 1 1.2.3 实验目的 . 2 2 APRIORI算法分析与实验环境 3 2.1APRIORI算法的描述. 3 2.2APRIORI算法的步骤. 3 2.3开发环境 . 3 2.3.1 软件环境 . 3 2.3.2 硬件环境 . 4 2.4本章小结 .

2、4 3 算法的设计. 5 3.1APRIORI算法整体框架. 5 3.2主要的数据结构与函数 . 5 3.2.1 数据结构 . 5 3.2.2 主要的程序 . 6 3.2.3 连接与剪枝操作 . 6 3.3本章小结 . 6 4 数据库的设计与数据的来源 7 4.1 正确性验证数据. . 7 4.2实验数据 . 7 4.3本章小结 . 8 5 实验结果与性能分析 . 9 5.1APRIORI实验界面. 9 5.2实验的正确性验证 . 9 5.3实验性能分析 10 5.3.1 固定最小支持度改变数据量 10 5.3.2 固定数据量改变最小支持度 11 5.3.3 实验结果分析 11 5.4本章小结

3、 12 6 总结与体会 13 实用文案 标准文档 1 Apriori实验 1.1 实验背景 现在, 数据挖掘作为从数据中获取信息的有效方法, 越来越受到人们的重视。 关联 规则挖掘首先是用来发现购物篮数据事务中各项之间的有趣联系。从那以后 , 关联规则 就成为数据挖掘的重要研究方向, 它是要找出隐藏在数据间的相互关系。目前关联规则 挖掘的研究工作主要包括：Apriori算法的扩展、数量关联规则挖掘、关联规则增量式 更新、无须生成候选项目集的关联规则挖掘、最大频繁项目集挖掘、约束性关联规则挖 掘以及并行及分布关联规则挖掘算法等。关联规则的挖掘问题就是在事务数据库D中找 出具有用户给定的满足一定条

4、件的最小支持度Minsup 和最小置信度 Minconf 的关联规 则。 1.1.1 国内外研究概况 1993年，Agrawal 等人首先提出关联规则概念，关联规则挖掘便迅速受到数据挖掘 领域专家的广泛关注 . 迄今关联规则挖掘技术得到了较为深入的发展。Apriori算法是关 联规则挖掘经典算法。针对该算法的缺点，许多学者提出了改进算法，主要有基于哈希 优化和基于事务压缩等。 1.1.2 发展趋势 关联规则挖掘作为数据挖掘的重要研究内容之一, 主要研究事务数据库、 关系数据 库和其他信息存储中的大量数据项之间隐藏的、有趣的规律。关联规则挖掘最初仅限于 事务数据库的布尔型关联规则, 近年来广泛应

5、用于关系数据库, 因此, 积极开展在关 系数据库中挖掘关联规则的相关研究具有重要的意义。近年来 , 已经有很多基于 Apriori 算法的改进和优化。研究者还对数据挖掘的理论进行了有益的探索，将概念格和粗糙集 应用于关联规则挖掘中，获得了显著的效果。到目前为止，关联规则的挖掘已经取得了 令人瞩目的成绩，包括：单机环境下的关联规则挖掘算法；多值属性关联规则挖掘；关 联规则更新算法；基于约束条件的关联规则挖掘；关联规则并行及分布挖掘算法等。 1.2 实验内容与要求 1.2.1 实验内容 编程实现 Apriori算法：要求使用 a, b, c,d, e, f , g, h, i , j 10 个项目

6、随机产生数据记录并存入数据库。从数据库读取记录进行 Apriori实验，获得频繁集以及关联规则，实现可视化。并用课堂上PPT的实例测试其 正确性。 1.2.2 实验要求 1、程序结构：包括前台工具和数据库； 2、设定项目种类为 10个，随机产生事务，生成数据库； 3、正确性验证（可用课堂上的例子） ； 4、算法效率的研究：在支持度固定数据量不同的时候测量运行时间；在数据量固 定，支持度不同的时候测量运行时间； 5、注意界面的设计，输入最小支持度和最小可信度，能够输出并显示频繁项目集 以及关联规则。 实用文案 标准文档 1.2.3 实验目的 1、加强对 Apriori算法的理解； 2、锻炼分析问

7、题、解决问题并动手实践的能力。 实用文案 标准文档 2 Apriori算法分析与实验环境 2.1 Apriori算法的描述 Apriori算法是一种找频繁项目集的基本算法。其基本原理是逐层搜索的迭代：频 繁 K项 Lk 集用于搜索频繁 (K+1)项集 Lk+1，如此下去，直到不能找到维度更高的频繁 项集为止。这种方法依赖连接和剪枝这两步来实现。算法的第一次遍历仅仅计算每个项 目的具体值的数量，以确定大型l 项集。随后的遍历，第k 次遍历，包括两个阶段。首 先，使用在第 (k-1) 次遍历中找到的大项集Lk-1 和产生候选项集 Ck。接着扫描数据库， 计算 Ck中候选的支持度。用Hash树可以有

8、效地确定Ck中包含在一个给定的事务t 中 的候选。如果某项集满足最小支持度, 则称它为频繁项集。 2.2 Apriori算法的步骤 步骤如下 : 1、设定最小支持度s 和最小置信度 c； 2、Apriori算法使用候选项集。 首先产生出候选的项的集合, 即候选项集 , 若候选项 集的支持度大于或等于最小支持度, 则该候选项集为频繁项集； 3、在 Apriori算法的过程中 , 首先从数据库读入所有的事务, 每个项都被看作候选 1- 项集, 得出各项的支持度 , 再使用频繁 1-项集集合来产生候选 2-项集集合 , 因为先验原 理保证所有非频繁的1- 项集的超集都是非频繁的； 4、再扫描数据库

9、, 得出候选 2-项集集合 , 再找出频繁 2-项集, 并利用这些频繁 2-项 集集合来产生候选3-项集； 5、重复扫描数据库 , 与最小支持度比较 , 产生更高层次的频繁项集, 再从该集合里产 生下一级候选项集 , 直到不再产生新的候选项集为止。 2.3 开发环境 2.3.1 软件环境 (1)编程软件： Jdk 开发包 +eclipse集成开发环境 Eclipse 是一个开放源代码的、基于Java 的可扩展开发平台。就其本身而言，它 只是一个框架和一组服务，用于通过插件组件构建开发环境。幸运的是，Eclipse 附带 了一个标准的插件集，包括Java 开发工具（ Java Developme

10、nt Kit，JDK ） 。 (2)数据库软件： SQL Server 2008 SQL Server 2008 在 Microsoft的数据平台上发布，可以组织管理任何数据。可以 将结构化、半结构化和非结构化文档的数据直接存储到数据库中。可以对数据进行查询、 搜索、同步、报告和分析之类的操作。数据可以存储在各种设备上，从数据中心最大的 服务器一直到桌面计算机和移动设备，它都可以控制数据而不用管数据存储在哪里。 (3)办公软件： Excel 2010 Excel是一款试算表办公 软件。它是微软办公套装软件office的重要的组成部分， 它是集统计分析、数据处理和辅助决策等功能于一身，现在金融、

11、统计财经、管理等众 多领域广泛应用。 本实验主要用来为固定数据量改变最小支持数以及固定最小支持数改 变数据量两种情况进行时间分析提供可视化图表。 实用文案 标准文档 2.3.2 硬件环境 装有 Windows 7 旗舰版电脑。 2.4 本章小结 本章的内容主要是为了引出本实验的主要算法以及对算法的实现环境做了介绍。 实用文案 标准文档 3 算法的设计 3.1 Apriori算法整体框架 Apriori 开始 定义 minsup、minconf K=1,产生C1 扫描数据库，产生 L1 生成1项频繁项目集 由Lk连接，剪枝产生 Ck+1 Ck为空 生成关联规则 生成频繁项目集 扫描，产生 Lk+

12、1 Apriori 结束 是 否 图 3.1 Apriori实验流程图 3.2 主要的数据结构与函数 3.2.1 数据结构 class Transaction public int pid; public String itemset; 该类表示表中的一条记录。 class Dao 实用文案 标准文档 public ArrayList Query(String sql) 该类用于访问数据库操作。 class Kfp public char kfpstr=new charApriori.ITEMSIZE; public int index=-1; public int support=0; pu

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

14、l：临时存储频繁项目的集合，存储连接后的结果 ArrayList SureFpset：保存频繁 k 项集 ArrayList SureFpsetPrio：保存频繁 k-1 项集 ArrayList notFpList：保存一定不是频繁项目的集合，用于剪枝 HashMap KfpSuppor:频繁项目集及其对应的支持数 HashMap guanlianguize:关联规则及其置信度 3.2.3 连接与剪枝操作 对于连接操作的两个字符串(长度为 k) ，它们必须有 k-1 个相同的字符才能做连接 操作。 例如:abc 和 abd可以连接成 abcd，abd 和 bcd 可以连接成 abcd，而 a

15、bc 和 ade 就 不可以做连接操作。整个连接过程类似归并排序中的归并操作 对于任一频繁项目集的所有非空子集也必须是频繁的，反之，如果某个候选的非空 子集不是频繁的，那么该候选集肯定不是频繁的，将其剪枝。 3.3 本章小结 本章主要介绍了算法设计的整体流程并且也对主要程序和操作作了简要的说明。 实用文案 标准文档 4 数据库的设计与数据的来源 本实验的数据均存储于数据库中。数据库yuzm中共产生 6 张表。表 test 为测试用 表，用于程序的正确性验证。还有5 张表存储随机产生的实验数据。其中数据库的结构 如下图所示。 图 4.1 数据库结构 4.1 正确性验证数据 表 test 为 PP

16、T上的实例，用于正确性验证。数据的item 个数为 5，其中的九行数 据均由 SQL语句产生，表的每一行都是一个“0” “1”的字符串，字符串长度等于商品 种类，其中“ 0”表示该商品不存在，“1”表示该商品存在。表的全部数据如图4.2 。 图 4.2 表 test 4.2 实验数据 5 张表是通过算法随机产生的具有不同数据量的数据集，假设商品种类为 10 种，表 的每一行都是一个“ 0” “1”的字符串，字符串长度等于商品种类，其中“0”表示该商 品不存在， “1”表示该商品存在。其中表data1 共随机产生 1 万行数据，表 data2 产生 实用文案 标准文档 5 万行数据，表 data

17、3 产生 25万行数据，表 data4 产生 50 万行数据，表 data5 产生 75 万行数据。部分数据如图4.3 。 图 4.3 实验用表（部分） 4.3 本章小结 本章主要对数据库的设计与数据来源做出了说明。 实用文案 标准文档 5 实验结果与性能分析 5.1 Apriori实验界面 其中可信度可自由设置，默认为0.7 。而支持度记为最小支持度与数据量的比例。 实验数据可以下拉选择6 张表中的任意一张。如下图所示： 图 5.1 实验界面 5.2 实验的正确性验证 运行程序，我们选择表test ，即可进行正确性验证，实验结果如下图： 实用文案 标准文档 图 5.2 正确性验证 最终实验结

18、果与 ppt 的结果相吻合，表明程序编写正确。 5.3 实验性能分析 为了对本程序的实验进行性能分析，我们分别采用固定数据量改变最小支持数以及 固定最小支持数改变数据量两种情况进行时间分析, 其中最小置信度设为0.7 不变。 5.3.1 固定最小支持度改变数据量 设支持度为 0.2 ，最小可信度为 0.7 。具体实验数据量与执行时间如下： 表 5.1 数据量对性能的影响 数据量（万行）1 5 25 50 75 时间（秒）48.2 128.2 366.9 623.4 1032.3 实用文案 标准文档 图 5.3 数据量对性能的影响 5.3.2 固定数据量改变最小支持度 设实验数据量固定改变最小支

19、持度，具体如下所示： 表 5.2 最小支持度对性能的影响 最小支持度0.15 0.20 0.25 0.30 0.35 时间（秒 / 1 万） 175.6 49 14.2 8.5 5.2 时间（秒 / 5 万） 294.1 128.2 58.8 41.5 25.7 时间（秒/ 25 万） 531.3 366.9 246.5 185.6 154.0 图 5.4 最小支持度对性能的影响 5.3.3 实验结果分析 由以上实验我们可以看出，实验时间会随着数据量的增大而增大，并且随着最小支 实用文案 标准文档 持度的增大而减小。并且他们之间的变化类似于某种指数函数的变化趋势。Apriori的 时间主要消耗

20、在 4 个方面： 1、利用 K频繁集连接产生K+1候选集时，判断连接的条件时比较的次数太多。假 设项集个数为m的频繁集合 Lk，判断连接条件时比较的时间复杂度为O （K*m2 ） 。而且 本实验的 m都很大； 2、对 Ck中任意的一个 c 的 k 个（k-1 ）子集是否都在 Lk-1 中。在平均情况下，对 所有候选 k 项集需要扫描次数为 |Ck|*|Lk-1|*k/2； 3、为了得到所有的候选频集的支持度，需要扫描N次； 4、扫描一次数据库需时间O （k|T| ） 。|T| 为交易数量， k 交易长度 5.4 本章小结 Apriori算法因自身需要多次扫描数据库，并且经过复杂的连接剪枝操作而

21、产生大 量候选集以及进行大量的模式匹配计算的缺陷，使得其在I/O 上的花费时间很多，从而 导致算法的效率不是太高。 实用文案 标准文档 6 总结与体会 通过本次实验，让我明白了什么是Apriori算法和数据之间的关联性，Apriori算 法是一种最有影响的挖掘布尔关联规则频繁项集的算法，为以后进步学习数据挖掘知识 打下了良好的基础。同时我也更加深刻理解了Apriori算法的原理及其实现的内部细节， 同时通过实现这一经典的数据挖掘算法，也让我更深刻的体会到数据挖掘对于知识发现 的重要性，尽管实现了算法，但其中可能还有可以改进的地方，尤其是程序的运行效率 方面。 Apriori算法实验不仅使得我对

22、该算法的理解更加上升了一个层次，同时也使得 我更加了解了 java 编程语言，使用更加得心应手。 import java.awt.BorderLayout; import java.awt.Font; import java.awt.GridLayout; import java.awt.Panel; import java.awt.TextArea; import java.awt.TextField; import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import java.util.Array

23、List; import java.util.HashMap; import java.util.Iterator; import java.util.Set; import javax.swing.JButton; import javax.swing.JComboBox; import javax.swing.JFrame; import javax.swing.JLabel; import javax.swing.JPanel; import javax.swing.JTextField; import org.omg.CORBA.PUBLIC_MEMBER; public class

24、Apriori extends 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; JLab

25、el c1=null; JLabel c2=null; JLabel 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=

26、null; TextArea textArea=null; int fpstep=1; int fpindex=0; Dao dao=null; double MinSupport=0.20; double MinConfi=0.70; double DateSize=9.0; ArrayList alTransactions=null; ArrayList alKfps=null; ArrayList notFpList=null; ArrayList SureFpset=null; ArrayList SureFpsetPrio=null; 实用文案 标准文档 HashMap KfpSup

27、port=null; ArrayList alsurekfpstr=null; HashMap guanlianguize=null; ArrayList 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); JPanel up_up=new JPanel(new GridLayout(1, ITEMSIZE); /TextFie

28、ld textFieldName=new TextFieldITEMSIZE; /for(int i=0;i(); notFpList=new ArrayList(); SureFpset=new ArrayList(); SureFpsetPrio=new ArrayList(); dao=new Dao(); KfpSupport=new HashMap(); alsurekfpstr=new ArrayList(); guanlianguize=new HashMap(); isaddarrStrings=new ArrayList(); alTransactions=dao.Query

29、(“select * from “+table); this.DateSize=alTransactions.size(); public void ShowkFp(ArrayList SureFpset) int steptemp=fpstep; textArea.append(“频繁“+(steptemp)+“项集rn“); /System.out.println(); for(int i=0;i SureFpset) textArea.append(“关联规则 rn“); Set keys=(Set) SureFpset.keySet(); for(String keyString:ke

30、ys) textArea.append(keyString+“-“+SureFpset.get(keyString)+“rn“) ; public void DataMine() int fpsteptemp=0; if(fpstep = 1) for(int i=0;i alStrings=subSet.displaySubSet1(string.toCharArray(); int p=0; for(;p aList=s.SubSet3(kfpchararr,kfpstr.length(); for(int j=0;j MinConfi) String temp=kfpstr1+“-“+g

31、uizetemp; guanlianguize.put(temp,support1/support2); ShowkFp2(guanlianguize); alsurekfpstr.clear(); guanlianguize.clear(); public Kfp Joint(Kfp k1,Kfp k2) Kfp resultKfp=new Kfp(); int temp_len=k1.index+1; char temp1=new chartemp_len; char temp2=new chartemp_len; for(int i=0;i alStrings1=s.SubSet2(te

32、mp1,fpstep); ArrayList alStrings2=s.SubSet2(temp2,fpstep); char result=new chartemp_len+1; boolean flag=false; for(int i=0;i temp2q) resultj+=temp2q; q+; if(p != temp1.length q+; p+; if(p != temp1.length SubSet suSet=new SubSet(); alListsunset=suSet.displaySubSet(of1char, fpstep); for(int p=0;p alTr

33、ansactions=null; public static String driver = “com.microsoft.sqlserver.jdbc.SQLServerDriver“; public static String url = “jdbc:sqlserver:/localhost:1433;DatabaseName=yuzm;integratedSecurity=TRUE; “; /public static String user = “root“; /public static String password = “root“; public Dao() try / 加载驱

34、动程序 Class.forName(driver); / 连续数据库 conn = DriverManager.getConnection(url); if(conn = null) System.out.println(“fail connect to the Database!“); catch(Exception e) e.printStackTrace(); public ArrayList Query(String sql) try statement =(Statement) conn.createStatement(); rs = statement.executeQuery(s

35、ql); alTransactions=Query(rs); catch (SQLException e) e.printStackTrace(); 实用文案 标准文档 return alTransactions; private ArrayList Query(ResultSet rs) ArrayList alTransactions=new ArrayList(); try int pid_index=rs.findColumn(“id“); int item_index=rs.findColumn(“item“); while(rs.next() Transaction t=new T

36、ransaction(); int pid=rs.getInt(pid_index); String itemset=rs.getString(item_index); t.pid=pid; t.itemset=itemset; alTransactions.add(t); ; catch (Exception e) e.printStackTrace(); finally try rs.close(); catch (SQLException e) e.printStackTrace(); return alTransactions; public Transaction Query() T

37、ransaction t=new Transaction(); return t; 实用文案 标准文档 public void CloseConnection() try conn.close(); catch (SQLException e) e.printStackTrace(); import java.util.ArrayList; class SubSet public ArrayList displaySubSet(char setN,int fpstep) ArrayList alStrings=new ArrayList(); int length = setN.length;

38、 int i; for (i = 0; i = fpstep) alStrings.add(strtemp); return alStrings; public ArrayList displaySubSet1(char setN) ArrayList alStrings=new ArrayList(); int length = setN.length; 实用文案 标准文档 int i; for (i = 0; i SubSet2(char setN,int fpstep) ArrayList alStrings=new ArrayList(); int length = setN.leng

39、th; int i; for (i = 0; i SubSet3(char setN,int fpstep) ArrayList alStrings=new ArrayList(); int length = setN.length; int i; for (i = 0; i (1 length); i+) 实用文案 标准文档 String strtemp=“; for (int j = 0; j length; j+) if (i if(strtemp.length() fpstep return alStrings; class Transaction public int pid; public String itemset; class Kfp public char kfpstr=new charApriori.ITEMSIZE; public int index=-1; public int support=0; public boolean isfp=true;