Apriori算法实验报告及程序62.docx
《Apriori算法实验报告及程序62.docx》由会员分享，可在线阅读，更多相关《Apriori算法实验报告及程序62.docx（41页珍藏版）》请在冰点文库上搜索。
Apriori算法实验报告及程序62
Apriori算法实验报告
学号：
姓名：
专业：
计算机应用技术
教师：
计算机学院
1Apriori实验
1.1实验背景
现在,数据挖掘作为从数据中获取信息的有效方法,越来越受到人们的重视。
关联规那么挖掘首先是用来发现购物篮数据事务中各项之间的有趣联系。
从那以后,关联规那么就成为数据挖掘的重要研究方向,它是要找出隐藏在数据间的相互关系。
目前关联规那么挖掘的研究工作主要包括：
Apriori算法的扩展、数量关联规那么挖掘、关联规那么增量式更新、无须生成候选工程集的关联规那么挖掘、最大频繁工程集挖掘、约束性关联规那么挖掘以及并行及分布关联规那么挖掘算法等。
关联规那么的挖掘问题就是在事务数据库D中找出具有用户给定的满足一定条件的最小支持度Minsup和最小置信度Minconf的关联规那么。
国内外研究概况
1993年，Agrawal等人首先提出关联规那么概念，关联规那么挖掘便迅速受到数据挖掘领域专家的广泛关注.迄今关联规那么挖掘技术得到了较为深入的开展。
Apriori算法是关联规那么挖掘经典算法。
针对该算法的缺点，许多学者提出了改良算法，主要有基于哈希优化和基于事务压缩等。
开展趋势
关联规那么挖掘作为数据挖掘的重要研究内容之一,主要研究事务数据库、关系数据库和其他信息存储中的大量数据项之间隐藏的、有趣的规律。
关联规那么挖掘最初仅限于事务数据库的布尔型关联规那么,近年来广泛应用于关系数据库,因此,积极开展在关系数据库中挖掘关联规那么的相关研究具有重要的意义。
近年来,已经有很多基于Apriori算法的改良和优化。
研究者还对数据挖掘的理论进行了有益的探索，将概念格和粗糙集应用于关联规那么挖掘中，获得了显著的效果。
到目前为止，关联规那么的挖掘已经取得了令人瞩目的成绩，包括：
单机环境下的关联规那么挖掘算法；多值属性关联规那么挖掘；关联规那么更新算法；基于约束条件的关联规那么挖掘；关联规那么并行及分布挖掘算法等。
1.2实验内容与要求
1.2.1实验内容
编程实现Apriori算法：
要求使用‘a’,‘b’,‘c’,‘d’,‘e’,‘f’,‘g’,‘h’,‘i’,‘j’10个工程随机产生数据记录并存入数据库。
从数据库读取记录进行Apriori实验，获得频繁集以及关联规那么，实现可视化。
并用课堂上PPT的实例测试其正确性。
1.2.2实验要求
1、程序结构：
包括前台工具和数据库；
2、设定工程种类为10个，随机产生事务，生成数据库；
3、正确性验证〔可用课堂上的例子〕；
4、算法效率的研究：
在支持度固定数据量不同的时候测量运行时间；在数据量固定，支持度不同的时候测量运行时间；
5、注意界面的设计，输入最小支持度和最小可信度，能够输出并显示频繁工程集以及关联规那么。
1.2.3实验目的
1、加强对Apriori算法的理解；
2、锻炼分析问题、解决问题并动手实践的能力。
2Apriori算法分析与实验环境
2.1Apriori算法的描述
Apriori算法是一种找频繁工程集的根本算法。
其根本原理是逐层搜索的迭代：
频繁K项Lk集用于搜索频繁（K+1）项集Lk+1，如此下去，直到不能找到维度更高的频繁项集为止。
这种方法依赖连接和剪枝这两步来实现。
算法的第一次遍历仅仅计算每个工程的具体值的数量，以确定大型l项集。
随后的遍历，第k次遍历，包括两个阶段。
首先，使用在第（k-1）次遍历中找到的大项集Lk-1和产生候选项集Ck。
接着扫描数据库，计算Ck中候选的支持度。
用Hash树可以有效地确定Ck中包含在一个给定的事务t中的候选。
如果某项集满足最小支持度,那么称它为频繁项集。
2.2Apriori算法的步骤
步骤如下:
1、设定最小支持度s和最小置信度c；
2、Apriori算法使用候选项集。
首先产生出候选的项的集合,即候选项集,假设候选项集的支持度大于或等于最小支持度,那么该候选项集为频繁项集；
3、在Apriori算法的过程中,首先从数据库读入所有的事务,每个项都被看作候选1-项集,得出各项的支持度,再使用频繁1-项集集合来产生候选2-项集集合,因为先验原理保证所有非频繁的1-项集的超集都是非频繁的；
4、再扫描数据库,得出候选2-项集集合,再找出频繁2-项集,并利用这些频繁2-项集集合来产生候选3-项集；
5、重复扫描数据库,与最小支持度比拟,产生更高层次的频繁项集,再从该集合里产生下一级候选项集,直到不再产生新的候选项集为止。
2.3开发环境
软件环境
（1）编程软件：
Jdk开发包+eclipse集成开发环境
Eclipse是一个开放源代码的、基于Java的可扩展开发平台。
就其本身而言，它只是一个框架和一组效劳，用于通过插件组件构建开发环境。
幸运的是，Eclipse附带了一个标准的插件集，包括Java开发工具〔JavaDevelopmentKit，JDK〕。
（2）数据库软件：
SQLServer2021
SQLServer2021在Microsoft的数据平台上发布，可以组织管理任何数据。
可以将结构化、半结构化和非结构化文档的数据直接存储到数据库中。
可以对数据进行查询、搜索、同步、报告和分析之类的操作。
数据可以存储在各种设备上，从数据中心最大的效劳器一直到桌面计算机和移动设备，它都可以控制数据而不用管数据存储在哪里。
（3）办公软件：
Excel2021
Excel是一款试算表办公软件。
它是微软办公套装软件office的重要的组成局部，它是集统计分析、数据处理和辅助决策等功能于一身，现在金融、统计财经、管理等众多领域广泛应用。
本实验主要用来为固定数据量改变最小支持数以及固定最小支持数改变数据量两种情况进行时间分析提供可视化图表。
硬件环境
装有Windows7旗舰版电脑。
2.4本章小结
本章的内容主要是为了引出本实验的主要算法以及对算法的实现环境做了介绍。
3算法的设计
3.1Apriori算法整体框架
图3.1Apriori实验流程图
3.2主要的数据结构与函数
3.2.1数据结构
classTransaction
{
publicintpid;
publicStringitemset;
}
该类表示表中的一条记录。
classDao
{
publicArrayListQuery（Stringsql）
}
该类用于访问数据库操作。
classKfp
{
publiccharkfpstr[]=newchar[Apriori.ITEMSIZE];
publicintindex=-1;
publicintsupport=0;
publicbooleanisfp=true;
}
该类代表一个频繁工程。
3.2.2主要的程序
Java中最常用的集合类是List和Map。
List的具体实现包括ArrayList和Vector，它们是可变大小的列表，比拟适合构建、存储和操作任何类型对象的元素列表。
List适用于按数值索引访问元素的情形。
HashMap：
Map接口的常用实现类，系统当成一个整体进行处理，系统总是根据Hash算法来计算的存储位置，这样可以保证能快速存、取Map的对。
ArrayListalTransactions：
保存表中的所有记录
ArrayListalKfpsl：
临时存储频繁工程的集合，存储连接后的结果
ArrayListSureFpset：
保存频繁k项集
ArrayListSureFpsetPrio：
保存频繁k-1项集
ArrayListnotFpList：
保存一定不是频繁工程的集合，用于剪枝
HashMapKfpSuppor:
频繁工程集及其对应的支持数
HashMapguanlianguize:
关联规那么及其置信度
3.2.3连接与剪枝操作
对于连接操作的两个字符串（长度为k），它们必须有k-1个相同的字符才能做连接操作。
例如:
abc和abd可以连接成abcd，abd和bcd可以连接成abcd，而abc和ade就不可以做连接操作。
整个连接过程类似归并排序中的归并操作
对于任一频繁工程集的所有非空子集也必须是频繁的，反之，如果某个候选的非空子集不是频繁的，那么该候选集肯定不是频繁的，将其剪枝。
3.3本章小结
本章主要介绍了算法设计的整体流程并且也对主要程序和操作作了简要的说明。
4数据库的设计与数据的来源
本实验的数据均存储于数据库中。
数据库yuzm中共产生6张表。
表test为测试用表，用于程序的正确性验证。
还有5张表存储随机产生的实验数据。
其中数据库的结构如下列图所示。
图4.1数据库结构
正确性验证数据
表test为PPT上的实例，用于正确性验证。
数据的item个数为5，其中的九行数据均由SQL语句产生，表的每一行都是一个“0〞“1〞的字符串，字符串长度等于商品种类，其中“0〞表示该商品不存在，“1〞表示该商品存在。
表的全部数据如图4.2。
图4.2表test
4.2实验数据
5张表是通过算法随机产生的具有不同数据量的数据集，假设商品种类为10种，表的每一行都是一个“0〞“1〞的字符串，字符串长度等于商品种类，其中“0〞表示该商品不存在，“1〞表示该商品存在。
其中表data1共随机产生1万行数据，表data2产生5万行数据，表data3产生25万行数据，表data4产生50万行数据，表data5产生75万行数据。
局部数据如图4.3。
图4.3实验用表〔局部〕
4.3本章小结
本章主要对数据库的设计与数据来源做出了说明。
5实验结果与性能分析
Apriori实验界面
其中可信度可自由设置，默认为0.7。
而支持度记为最小支持度与数据量的比例。
实验数据可以下拉选择6张表中的任意一张。
如下列图所示：
图实验界面
5.2实验的正确性验证
运行程序，我们选择表test，即可进行正确性验证，实验结果如下列图：
图正确性验证
最终实验结果与ppt的结果相吻合，说明程序编写正确。
5.3实验性能分析
为了对本程序的实验进行性能分析，我们分别采用固定数据量改变最小支持数以及固定最小支持数改变数据量两种情况进行时间分析,其中最小置信度设为0.7不变。
固定最小支持度改变数据量
设支持度为0.2，最小可信度为0.7。
具体实验数据量与执行时间如下：
表5.1数据量对性能的影响
数据量〔万行〕
1
5
25
50
75
时间〔秒〕
48.2
128.2
366.9
623.4
1032.3
图5.3数据量对性能的影响
固定数据量改变最小支持度
设实验数据量固定改变最小支持度，具体如下所示：
表5.2最小支持度对性能的影响
最小支持度
时间〔秒/1万〕
49
时间〔秒/5万〕
294.1
128.2
58.8
41.5
25.7
时间〔秒/25万〕
图5.4最小支持度对性能的影响
由以上实验我们可以看出，实验时间会随着数据量的增大而增大，并且随着最小支持度的增大而减小。
并且他们之间的变化类似于某种指数函数的变化趋势。
Apriori的时间主要消耗在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交易长度
本章小结
Apriori算法因自身需要屡次扫描数据库，并且经过复杂的连接剪枝操作而产生大量候选集以及进行大量的模式匹配计算的缺陷，使得其在I/O上的花费时间很多，从而导致算法的效率不是太高。
6总结与体会
通过本次实验，让我明白了什么是Apriori算法和数据之间的关联性，Apriori算法是一种最有影响的挖掘布尔关联规那么频繁项集的算法，为以后进步学习数据挖掘知识打下了良好的根底。
同时我也更加深刻理解了Apriori算法的原理及其实现的内部细节，同时通过实现这一经典的数据挖掘算法，也让我更深刻的体会到数据挖掘对于知识发现的重要性，尽管实现了算法，但其中可能还有可以改良的地方，尤其是程序的运行效率方面。
Apriori算法实验不仅使得我对该算法的理解更加上升了一个层次，同时也使得我更加了解了java编程语言，使用更加得心应手。
orderLayout;
importjava.awt.Font;
importjava.awt.GridLayout;
importjava.awt.Panel;
importjava.awt.TextArea;
importjava.awt.TextField;
importjava.awt.event.ActionEvent;
importjava.awt.event.ActionListener;
importjava.util.ArrayList;
importjava.util.HashMap;
importjava.util.Iterator;
importjava.util.Set;
importjavax.swing.JButton;
importjavax.swing.JComboBox;
importjavax.swing.JFrame;
importjavax.swing.JLabel;
importjavax.swing.JPanel;
importjavax.swing.JTextField;
importorg.omg.CORBA.PUBLIC_MEMBER;
publicclassAprioriextendsJFrameimplementsActionListener
{
//////////////////////////////////////////////////////
publicstaticintITEMSIZE=10;
publicfinalintFRAMEWIDTH=800;
publicfinalintFRAMEHEIGHT=600;
///////////////////////////////////////////////////////
JPanelup=null;
JPanelup_up=null;
TextFieldtextFieldName[]=null;
JPanelup_down=null;
JPanelup_down_left=null;
JLabelconflabel=null;
JLabelc1=null;
JLabelc2=null;
JLabelc3=null;
JLabelc4=null;
JLabelc5=null;
JLabelc6=null;
JLabelc7=null;
JLabelc8=null;
JTextFieldconf=null;
JLabelsupportlabel=null;
JTextFieldsupport=null;
JPanelup_down_right=null;
JComboBoxjComboBoxDateSize=null;//下拉框
JButtonjButtonMine=null;
JPaneldown=null;
TextAreatextArea=null;
intfpstep=1;
intfpindex=0;
Daodao=null;
doubleMinSupport=0.20;
doubleMinConfi=0.70;
doubleDateSize=9.0;
ArrayListalTransactions=null;
ArrayListalKfps=null;
ArrayListnotFpList=null;
ArrayListSureFpset=null;
ArrayListSureFpsetPrio=null;
HashMapKfpSupport=null;
ArrayListalsurekfpstr=null;
HashMapguanlianguize=null;
ArrayListisaddarrStrings=null;
int[][]AuxArr=null;
publicstaticvoidmain（String[]args）
{
AprioriA=newApriori（）;
}
publicApriori（）
{
JPanelup=newJPanel（newGridLayout（2,1））;
JPanelup_up=newJPanel（newGridLayout（1,ITEMSIZE））;
//TextFieldtextFieldName[]=newTextField[ITEMSIZE];
//for（inti=0;i//{
//textFieldName[i]=newTextField（）;
//up_up.add（textFieldName[i]）;
//}
c1=newJLabel（"数"）;
up_up.add（c1）;
c2=newJLabel（"据"）;
up_up.add（c2）;
c3=newJLabel（"挖"）;
up_up.add（c3）;
c4=newJLabel（"掘"）;
up_up.add（c4）;
c5=newJLabel（"实"）;
up_up.add（c5）;
c6=newJLabel（"验"）;
up_up.add（c6）;
c7=newJLabel（"--------"）;
up_up.add（c7）;
c8=newJLabel（"Apriori"）;
up_up.add（c8）;
up_down=newJPanel（newGridLayout（1,2））;
up_down_left=newJPanel（newGridLayout（1,4））;
conflabel=newJLabel（"可信度：
"）;
conf=newJTextField（）;
conf.setText（"0.7"）;
supportlabel=newJLabel（"支持度：
"）;
support=newJTextField（）;
support.setText（"0.2"）;
up_down_left.add（conflabel）;
up_down_left.add（conf）;
up_down_left.add（supportlabel）;
up_down_left.add（support）;
up_down_right=newJPanel（newGridLayout（1,2））;
jComboBoxDateSize=newJComboBox（）;//下拉框
jComboBoxDateSize.addItem（"test"）;
jComboBoxDateSize.addItem（"data1"）;
jComboBoxDateSize.addItem（"data2"）;
jComboBoxDateSize.addItem（"data3"）;
jComboBoxDateSize.addItem（"data4"）;
jComboBoxDateSize.addItem（"data5"）;
jComboBoxDateSize.addActionListener（this）;
jButtonMine=newJButton（"开始挖掘"）;
jButtonMine.addActionListener（this）;
up_down_right.add（jComboBoxDateSize）;
up_down_right.add（jButtonMine）;
up_down.add（up_down_left）;
up_down.add（up_down_right）;
up.add（up_up）;
up.add（up_down）;
down=newJPanel（newBorderLayout（））;
textArea=newTextArea（）;
//textArea.setFont（newFont（Font.DIALOG,Font.ITALIC,20））;
textArea.setFont（newFont（Font.DIALOG,Font.PLAIN,20））;
down.add（textArea）;
this.setLayout（newBorderLayout（））;
this.setSize（FRAMEWIDTH,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.FRAMEWIDTH,this.FRAMEHEIGHT-100）;
this.add（down）;
this.setVisible（true）;
}
publicvoidInitDate（Stringtable）
{
fpstep=1;
AuxAr
升级会员 