(1.College of Mathematics and Computer Science,Fuzhou University,Fuzhou 350108,China; 2.Department of Computer Engineering,Zhicheng College of Fuzhou University,Fuzhou 350108,China)
备注
针对数据挖掘中经典的Apriori算法在计算频繁项目集时需消耗大量的时间缺点,文中利用多线程并行计算的特点,提出了基于线程并行计算的Apriori算法,该算法是将统计候选项目个数的任务交给多线程来执行,从而达到减少Apriori算法的运行时间。通过实验数据分析,该算法对减少Apriori算法的运行时间有很大的提高。
Considering the Apriori data mining algorithm in the classic calculation of frequent itemsets requires a lot of time,using characteristics of multi-threaded parallel computing,thread is proposed based on the Apriori algorithm of parallel computing,this algorithm is to hand the task of statistics of the number of candidate item over to multi-thread to execute,so as to reduce the running time of the Apriori algorithm.Through the analysis of the experimental data,the algorithm has improved greatly to reduce the running time of the Apriori algorithm.
引言
数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据中提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程[1]。其中关联规则是数据挖掘研究中的一个重要方向,经典的关联规则挖掘算法是由美国学者由R.Agrawal等人于1993年提出的Apriori算法,它的基本思想是利用已知的(K-1)维频繁项集来生成K维频繁项集,在生成K维频繁项集时,需要多次扫描数据库,这样就使得Apriori算法的效率低下,近年来许多学者也提出一些对Apriori算法的改进[2-6],文献[3]提出3种优化方法是采用修改剪枝的策略,文献[4]采用布尔矩阵来记录事物和项集信息,从而减少扫描数据库的次数,文献[5]采用新的数据结构即将水平结构变成项目事物垂直对应关系的数据结构,从而达到减少频繁项目集的运算,文献[6]是利用Apriori性质来减少计算频繁项目集的运行时间。文中利用多线程并行运算的特点,提出了基于线程并行计算方法,对Apriori算法做了一些改进,减少了Apriori算法的运行时间,提高了运行效率。
1 基本概念
1.1 线程线程(thread),有时被称为轻量级进程(Lightweight Process,LWP),是程序执行流的最小单元。一个标准的线程由线程ID、当前指令指针、寄存器集合和堆栈组成。线程是进程中的一个实体,是被系统独立调度和分派的基本单位,线程自己不拥有系统资源,只拥有一点在运行中必不可少的资源,但它可与同属一个进程的其它线程共享进程所拥有的全部资源。一个线程可以创建和撤销另一个线程,同一进程中的多个线程之间可以并发执行。
1.2 并行计算并行计算(Parallel Computing)是指同时使用多种计算资源解决计算问题的过程,是提高计算机系统计算速度和处理能力的一种有效手段。它的基本思想是用多个处理器来协同求解同一问题,即将被求解的问题分解成若干个部分,各部分均由一个独立的处理机来并行计算。并行计算系统既可以是专门设计的、含有多个处理器的超级计算机,也可以是以某种方式互连的若干台的独立计算机构成的集群。通过并行计算集群完成数据的处理,再将处理的结果返回给用户。
2 Apriori算法的简介
Apriori算法是最有影响的挖掘布尔关联规则频繁项目集的经典算法。该算法的核心思想是采用逐层递推的方法,首先扫描数据库,产生频繁项目集1项集L1,如果L1非空,则由L1产生长度为2的候选项集合C2,然后对数据库中的每一个事务t,求出t在C2中的全部子集Ct,对于Ct中的每一个长度2的候选项集c,令c的计数加1,扫描数据库,筛选出候选项集合C2中所有计数满足于给定了最小支持度的项集组成了长度为2的频繁项集合L2,重复以上步骤,直到没有频繁项集合产生为止。在产生频繁项集合的过程中,为了提高效率及减少搜索空间,Apriori算法利用下面两个重要的性质来进行连接和剪枝的。
性质1 任何一个K维频繁项目集它的所有非空子集也必须是频繁项目集;
性质2 若一个候选K维项目集合的(K-1)维子集不在(K-1)维频繁项目集中,则候选K项目集也不可能是频繁的,即任何一个集合不是频繁项目集,则它的超集也不可能是频繁的。
虽然有以上2个重要的性质,但Apriori算法确有以下的不足之处
1)对数据库的扫描次数过多。即每生成一个候选项集合时,就要对数据库进行扫描一次;
2)Apriori算法可能产生大量的候选项集合;
3)在频繁项集合长度变大的情况下,运行时间将显著增加。
3 算法改进描述
设数据库D有n条记录,每条记录都由一个或者多个的项构成的。在上面的Apriori算法描述中,频繁项目集是从候选项目集通过扫描数据库统计各个项集的个数是否满足于给定的最小支持度来获取的。本算法的改进就是在统计项目集支持度时利用了线程并行计算方法来计算。在统计k阶项集时候,主程序不直接计算项集的个数,而是把计算的任务分配给线程,让线程计算,最后把各个线程的计算结果返回给主程序。主程序分配任务主要是把根据线程的个数t,把数据库D的n条记录尽量的平均分成t份。每个线程就会分到数据库D的一部分数据,同时也把k阶项集传递给线程。每个线程根据传递的项集X和数据库D(t),计算该项集X在数据库D(t)的出现的次数count(t)。线程计算完后,会将该项集X在该数据库D(t)的次数存在一个变量。主程序在开启多个线程后,会一直等待所有的线程都执行结束,然后把各个线程计算的线程的次数全部加起来,就是全部数据库D的次数。
算法描述如下
主程序(创建线程,并处理线程结果的部分)
Begin
Int count=0;
//某个项集在数据库中的总次数
List threads;
//存放计算支持度的线程的list集合
For from 0 to threads的大小
//获得第i个线程thread(i)
//把分割数据库给第i个线程thread(i)
//启动第i个线程
End for
//监听每一个线程的结束,把每一个线程的次数进行统计
For from 0 to threads的大小
count=count +threads[i].count;
End for
End
创建线程的程序
Begin
//输入的项集v
Int count=0;
For from 1 to 数据库D(k)
If第i条记录 包括v
count=count +1;
End if
End for
Return count;
End
4 实验结果的分析
为了验证此算法性能,以经典Apriori算法作为实验对比算法进行性能分析。实验环境是:CPU为Intel(s)2.5 GHz,1 GB内存和Windows XP操作系统,程序用JAVA语言来实现的,测试的数据库记录有8 400条左右。表1是在同一个支持度的情况下,经典Apriori算法与基于线程的Apriori算法运行时间的对比。
表1 经典Apriori算法和线程Apriori算法的对比
Tab.1 Comparison of the classical Apriori algorithm with thread Apriori algorithm在时间上采用线程的Apriori算法用了24.96 s的时间,相比于正常的Apriori算法的43.27 s将近少了快19 s的时间,随着线程的增加发现时间没有太大的变化。而图1是分别采用不同的支持度情况下,经典Apriori算法与线程Apriori算法的时间消耗对比情况,从图中可以看出经典算法的时间消耗总是比改进的算法的要大,几乎所有时刻两者时间的消耗都成两倍的差别。同时这个结果也间接证明了Apriori算法的主要时间消耗是在支持度计算的时候。
图1 经典Apriori算法和线程Apriori算法的比较
Fig.1 Comparison of the classical Apriori algorithm with thread Apriori algorithm在这里使用的是线程来达到并行计算,在实际运用中,可以用真实的计算机来代替线程,真正进行并行计算。将任务分配到各个计算机中,然后将结果汇总。
5 结 语
通过对经典Apriori算法及其缺点的分析,结合多线程并行计算方法的特点,提出了基于线程并行计算的Apriori算法,该算法主要利用多线程并行运行来减少Apriori算法运行的时间,并给出改进算法的完整描述。通过对实验数据的分析,证明改进后的算法在运行时间上大大优于原来的算法,提高了Apriori算法的运行效率。利用多线程进行模拟多处理器的并行计算,并没有通过真正的多台计算机实现并行运行。
- [1] Han J,Kamber M.Data mining:concepts and techniques[M].San Mateo,CA:Morgan Kaufmann,2000.
- [2] LIU Yian,YANG Bin.Research of an improved Apriori algorithm in mining association rules[J].Journal of Computer Applications,2007,27(2):418-420.
- [3] 徐章艳,刘美玲,张师超,等.Apriori算法的三种优化方法[J].计算机工程与应用,2004,40(36):190-192.
- [4] 钱光超,贾瑞玉,张 然,等.Apriori算法的一种优化方法[J].计算机工程,2008,34(23):196-198.
- [5] 李云峰,陈建文,程代杰.关联规则挖掘的研究及对Apriori算法的改进[J].计算机工程与科学,2002,24(6):65-68.
- [6] 崔贯勋,李 梁,王柯柯,等.关联规则挖掘中Apriori算法的研究与改进[J].计算机应用,2010,30(11):2 952-2 955.
- [7] 兰 天,杨君锐.一种关联规则增量更新算法[J].西安科技大学学报,2009,29(1):113-116.
- [8] 李 航,刘宗田,陈慧琼.挖掘关联规则的并行算法[J].小型微型计算机系统,2002,23(10):1 231-1 234.
- [9] 尚学群,沈均毅.并行关联规则挖掘综述[J].计算机工程,2004,30(14):1-3.
- [10]范丽君.相关规则并行算法的改进[J].兰州大学学报,2004,40(6):43-46.