关键字 |
| Apriori，并行处理，Java并发库 |
介绍 |
| 数据挖掘是一种用于从数据仓库中发现隐藏的有用信息的技术。频繁模式挖掘是数据挖掘的一项重要技术。频繁项目集是事务数据集中频繁一起出现的项目集。在大型事务数据集中开发可扩展的频繁项集挖掘方法是一个巨大的挑战。频繁模式挖掘最早由Agrawal等人以关联规则挖掘的形式提出，用于市场篮子分析。Apriori算法有一个有趣的向下闭包性质，在频繁的k-项集中:只有当k-项集的所有子项集都是频繁的[2]时，k-项集才是频繁的。自Apriori算法提出以来，人们对Apriori算法进行了广泛的改进或扩展。 |
相关工作 |
| Apriori是Agrawal等人提出的最流行的频繁项集生成挖掘算法。Park JS等[8]提出了并行分布式关联挖掘算法，以解决顺序算法的可扩展性问题。Rakesh Agrawal提出的计数分布和数据分布并行关联算法，John C.Shafer提出的[9]。张DW等[10]提出了高效有效的分布式算法FDM (Fast distributed Mining，快速分布式挖掘)来挖掘关联规则，提出了局部和全局强大的剪枝技术来提高性能。Li Liu2等[11]利用缓存意识的FP-array和无锁数据平铺并行化机制设计了FP-Tree的多核处理器优化算法。 |
先验的算法 |
| Apriori算法主要集中于根据用户定义的minSup[2]发现频繁项集。当项集的支持度大于或等于minSup阈值时，称为频繁项集;否则，它是一个非频繁项集。在第一步中，Apriori算法构造并计算所有1项集。(k-itemset是包含k个项的项集。)在找到所有频繁的1-项集后，算法将频繁的1-项集相互连接，形成候选2-项集。Apriori扫描事务数据集并计算候选2项集，以确定哪个2项集是频繁的。其他的通道是相应的。频繁(k-1)项集被连接成k个项集，这些项集的前k-1项是相同的。Apriori去除一些k项集，这些(k-1)项集至少有一个非频繁子集。 All remaining k-itemsets constitute candidate k-itemsets. The process is reiterated until no more candidates can be generated [2, 3]. Pseudo code of Apriori algorithm is given below [4]. |
| Ck:大小为k的候选项集 |
| Lk:大小为k的频繁项集 |
| L1 ={频繁项}; |
| 对于(k = 1;路! =Φ;开始吧 |
| Ck+1 = Lk生成的候选; |
| 对于数据集中的每个事务t做 |
| 增加Ck+1中包含在t中的所有候选项的计数 |
| Lk+1 = Ck+1中min_support的候选人 |
| 结束 |
| return Uk Lk; |
| Apriori算法使用闭包属性显著减少了候选项集的大小。但是，它可以生成大量的候选项集，并且多次扫描数据库，这是一个耗时且降低性能的过程。有时，对于从大型事务数据集生成频繁的项集，Apriori是挂起的。在可扩展的多核处理器并行计算中使用Apriori算法可以克服这一问题。 |
使用Java并发库进行并行计算 |
| 并行计算利用了系统可用的多核处理器，减少了执行时间，提高了性能[5,6]。多核处理器实现多处理的消息传递或共享内存内核间通信方法。任何可以线程化的应用程序都可以有效地映射到多核，但是使用多核处理器所获得的性能改进取决于程序中可以并行化的部分[5]。 |
| Java提供了多线程特性，允许在不同线程同时执行的情况下编写并发应用程序。Java并发框架是一个库，用于创建并发应用程序。它有助于线程化任务，特别是在多核系统上。concurrent包定义了执行器框架，提供了自己的线程管理和调度方案。Executor分离任务执行和提交，并提供用于线程生命周期监视和控制的钩子。Callable、Future、Executer、ExecuterService和ScheduledExecutorService是并发框架环境[7]的主要接口。 |
| •可调用接口类似于可运行接口，但不同之处在于call()方法返回一个值，而run()方法不返回值。 |
| Future表示异步计算的结果。有几种方法可以检查计算是否完成、等待计算完成、获取计算结果和取消计算。 |
| Executor是object用来执行提交任务的接口。该接口将任务提交与任务执行分离，并使用它来代替显式地创建线程。例如，在下面的代码中，DirectExecutor以串行方式执行任务，而ThreadPerTaskExecutor在单独的线程中执行每个任务。在这两种情况下，任务提交是类似的。 |
| ExecutorService是一个Executor，提供了一些方法来管理终止(关闭)，任务跟踪和返回任务的Future，可以用来取消执行，等待完成，跟踪任务的进度。 |
| ScheduledExecutorService是一个ExecutorService，它允许调度命令在延迟后运行，或定期执行。 |
多核处理先验算法 |
| 步骤1:从事务性数据集生成唯一的项集(第一个候选集)。 |
| 步骤2:使用Executors对象创建多个线程(等于计算机中的处理器数量)。 |
| 步骤3:提交CompletionService对象中的每个项目集以获得支持计数。 |
| 步骤4:计算支持计数值并存储在变量中。 |
| 步骤5:计算支持计数后，使用minSup值生成频繁项集。 |
| 步骤6:通过增加一项来准备一个新的候选项集。 |
| 步骤7:重复步骤5到步骤6，直到频繁项集为空。 |
| 步骤8:结束。 |
仿真结果 |
| 为了评价Apriori算法和并行Apriori算法的性能，我们在两个不同的数据集上进行了实验。Dataset-1有3000条事务记录，Dataset-2有10000条事务记录。算法针对具有不同minSup值的事务性数据集文件运行。要求用Java编写程序文件。算法运行在配置为Intel Core i5 3.20GHz (Four processor)、4GB RAM和3MB Cache的多核处理器计算机上。表1显示了结果度量;total需要两个具有不同minSup值的事务数据集的执行时间。 |
| 图1展示了不同minSup值为250、350、450和550时Dataset-1需要执行的算法结果的比较(秒)。从图1可以看出，并行Apriori算法比简单Apriori算法花费的时间更少。 |
| 图2展示了不同minSup值为700、900、1100和1300时Dataset-2需要执行的算法结果的比较(以秒为单位)。从图2可以看出，并行Apriori算法比简单Apriori算法花费的时间更少。 |
结论 |
| 本文提出了一种利用Java并发包实现并行计算的Apriori算法。我们在一个多核处理器上运行算法，使用不同的minSup和两个数据集。我们测量了简单和并行Apriori算法在多核处理器上的性能。并行计算的Apriori算法比简单的Apriori算法花费的时间更短。 |
表格一览 |
 |
| 表1 |
|
|
数字一览 |
 |
 |
| 图1 |
图2 |
|
|
参考文献 |
- Agrawal R, Imielinski T, Swami A，“大型数据库中项目集之间的关联规则挖掘”，1993acmsigmoddata management国际会议论文集(SIGMOD ' 93)，第207-216页，1993。
- Agrawal R, SrikantR，“挖掘关联规则的快速算法。见:1994年超大数据库国际会议论文集(VLDB ' 94)，第487-499页，1994。
- 张进臣，李玉江，李正山，“一种有效的关联规则增量挖掘算法”，第15届数据工程研究问题国际研讨会论文集:流数据挖掘和应用，2005
- 韩佳伟，《数据挖掘:概念与技术(第二版)》，ISBN 13: 978-1-55860-901-3, Elsevier, 2006
- Gene Amdahl，“实现大规模计算能力的单处理器方法的有效性”。国际学术会议论文集，第483 - 485页，1967。
- 阿。王志强，王志强，“基于OpenMP并行化的并行化算法”，计算机工程学报，第4期，2012。
- http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/package-summary.html, Java™平台的并发包API规范，标准版。
- 陈淑娟，陈淑娟，俞世平，“基于并行挖掘的关联规则挖掘方法”，第四届信息与知识管理国际学术会议论文集，pp 31-36, 1995
- 刘志刚，“关联规则的并行挖掘:设计、实现与经验”，计算机科学与技术学报，pp: 962-969, 1996。
- 张韩杰，吴维，傅安，傅勇，“一种快速分布式关联规则挖掘算法”，1996年并行与分布式信息系统国际会议论文集，pp 31-44, 1996。
- 刘莉，1，张益民1，唐志忠，“基于多核处理器的频繁项集挖掘优化”，VLDB =07，奥地利，2007。
|
菜单
