1.1.6 大数据适应度分析

关联规则挖掘在商业、科学等领域有很多成功的应用案例。在学术界，过去十几年里，科研人员研究出了一些适用于大数据环境下的并行的数据挖掘算法。然而，当前占领主要市场的商业数据挖掘系统或工具包都尚未提供并行数据挖掘工具或分布式数据挖掘工具，包括SAS EnterpriseMiner、IBM Inelligent Miner、SPSS Clementine等。实际上，这些系统无法解决超大数据集的挖掘任务，更无法提供实时分析的功能。

近年来，一种低价格、低功耗、高并发度的并行体系结构——CUDA（Compute Unified Device Architecture）正在蓬勃发展。CUDA是NVIDIA公司在其图形处理单元（GPU）基础上开发的支持通用并行计算的软硬件架构。GPU强大的计算能力和低廉的价格使得算法在大数据下的应用成为可能。

中国科学院大学刘莹等人[8]提出并实现了GUCAS-CU-Miner[9-10]，其中，提出了3项GPU并行实现技术。基于这3项技术，利用CUDA实现了Apriori、K-means和KNN。实验表明，GUCAS-CU-Miner在GPU+CPU的异构并行计算平台中的性能均优于GPU Miner和fast-KNN。在Apriori算法中，产生候选项集过程的任务是连接两个频繁（k−1）-项集，然后剪切掉不可能频繁的k-项集。显然，连接两个频繁项集的任务在不同的线程之间是独立的，所以这个过程适合被并行化。如图1-2所示，在这个核里，二维网格被划分成多个二维线程块，每个线程块由多个线程组成。每个线程比较两个频繁（k−1）-项集，如果两者拥有共同的（k-2）前缀，则生成一个k-候选项集。注意：图1-2中，线程网格被载入后，分离线（即图1-2中虚线）下部的线程块将立刻从执行中退出，因为它们与分离线之上的部分相同。

图1-2 产生候选项核函数的线程划分

在Apriori算法中，通过扫描交易数据库，计算支持度程序记录一个候选项集出现的次数。由于每个候选项集的计数与其他项集的计数相对独立，同样适合于多线程并行。多线程的划分如图1-3所示，其中，每个线程负责一个候选集，通过扫描数据库中的所有项计算它的支持度。线程网格和线程块的维度均定为1[9-10]。

图1-3 计算支持度核函数的线程划分