Spark平台的分布式阶段自适应关联规则挖掘算法

为满足日益增长的海量数据挖掘需求,迫切需要设计一种能够在多台机器上运行的分布式关联规则挖掘算法。Apriori这种高度迭代算法在Hadoop平台上运行时每次迭代执行大量的磁盘I/O操作,大大影响并限制了算法的运行效率。本文利用Spark对分布式计算内置支持的特点,在Spark平台上设计并实现一种分布式关联规则挖掘算法,称为阶段式自适应挖掘算法(Staged Adaptive Apriori)。算法使用自适应的数据集部分处理的策略对频繁项集进行高效挖掘,在每次迭代前初步评估执行时间,并采用较为合适的方法来减少时间和空间的复杂性,是一种基于数据集性质的自适应关联规则挖掘算法。实验结果表明了算法的有效性。     

无线城市社团发现的研究——在Spark上利用改进关联规则实现社团发现的算法

社团发现算法存在生成结果冗余及时间复杂度高等问题,虽然关联规则是解决社团发现问题的有效方法,但面临大量迭代计算的瓶颈。针对上述问题进行了研究,提出了一种改进社团发现的SIACD算法。该算法引入MAC地址和布尔矩阵的概念对数据进行预处理,利用基于项数的布尔向量交运算改进Apriori算法,再基于Spark实现算法并行化计算,通过关联规则的方式挖掘无线社团数据。实验结果表明,SIACD算法解决了生成结果冗余、复杂度高、迭代计算等问题,提升了社团发现的挖掘速度,提高了对大数据的处理能力。     

SparkSql上自适应数据集的高效频繁集挖掘算法

针对基于Spark框架的关联规则算法存在I/O开销大、数据结构和挖掘频繁集方式单一、计算支持度的方式效率低等问题,提出基于SparkSql进行分布式编程的算法。将数据集加载到DataFrame,利用改进后的布隆过滤器高效存储频繁集挖掘过程中产生的项集,解决RDD内存资源和计算速度受限问题。基于先验定理对事务、项目和项集进行精简,同时提出用Sql语句对项集中项目对应事务集合求交集的方式计算项集支持度,提高计算支持度的效率。提出了两种迭代算法和自适应数据的选择条件,增强该算法对各种数据集的泛化性。进行多组实验,证明提出的算法总是自适应本次迭代数据的特点选择最优的迭代方法,同时具有较高并行算法性能,可以扩展到更大规模集群和数据;同基于Spark框架的关联规则算法YAFIM和R-Apriori进行对比,在每次迭代和总体运行计算效率上有更好的表现。     

基于二叉频繁模式树的医学图像关联规则挖掘

医学图像的数据量是相当巨大的,挖掘医学图像中数据的关联关系就需要一种适合挖掘海量数据的挖掘算法。针对基于频繁模式树FP_TREE的关联规则算法在挖掘海量数据时占用大量内存的缺点,提出了一种基于二叉频繁模式树(FP_BTREE)的关联规则算法。该算法采用二叉树存储数据的技术来映射数据库中数据,以减少对数据库的访问次数。而且根据内存具体情况可以先求出先建立的二叉频繁模式树的频繁模式。解决了占用大量内存的缺点,适合挖掘医学图像海量数据集。此算法也为多棵二叉频繁模式树的并行计算打下基础。最后应用此算法提取医学图像数据集中隐含的关联信息。     

面向微博的PageRank算法的改进与应用

从海量数据下的社会化网络中识别出各个领域下产出高质量内容的具有一定影响力的专家,进行具有针对性的广告推荐与决策支持,已经成为微博数据挖掘亟待解决的问题之一。从微博的用户特征和行为特征出发,确定了采集博文的规则与互动量计算公式,并应用PageRank算法对微博用户影响力计算时存在的数据陈旧性和主题不相关性的问题进行了改进,最后分别基于MapReduce和Spark的并行计算框架对算法进行了实现。实验结果表明,该挖掘方法具有较好的准确性,在Spark并行计算框架下表现出较高的性能,尤其适合大规模数据集的场景。     

基于MapReduce计算模型的并行关联规则挖掘算法研究综述

关联规则挖掘是最常用、最重要的数据挖掘任务之一,经典的关联规则挖掘算法有Apriori、FP-Growth、Eclat等。随着数据的爆炸式增长,传统的算法已不能适应大数据挖掘的需要,需要分布式、并行的关联规则挖掘算法来解决上述问题。MapReduce是一种流行的分布式并行计算模型,因其使用简单、伸缩性好、自动负载均衡和自动容错等优点,得到了广泛的应用。本文对已有的基于MapReduce计算模型的并行关联规则挖掘算法进行了分类和综述,对其各自的优缺点和适用范围进行了总结,并对下一步的研究进行了展望。     

Apriori算法中频繁项集挖掘实现研究

在数据挖掘中，关联规则是发现知识的一种有效方法，而频繁项集的挖掘是关联规则中发现强规则的基础，其中连接与剪枝是逐层迭代求解k-项频繁集的核心算法。因此，文中主要介绍了基于连接与剪枝挖掘频繁项集的实现过程，并通过挖掘对传统购物篮数据中的频繁项集进行了验证，结果是一致的。算法的有效性也为进一步挖掘关联规则中的强规则提供了基础。     

基于Spark的并行频繁项集挖掘算法

关联规则挖掘是数据挖掘领域的重要研究方向之一。频繁项集的挖掘是关联规则挖掘的第一步,也是最重要的步骤。FP-Growth(Frequent Pattern-Growth)算法因其挖掘效率以及空间复杂度方面的优势被广泛应用于频繁项集挖掘任务中。面对海量数据,FP-Growth算法挖掘效率变得极低甚至失效。在Hadoop大数据平台上实现的基于MapReduce框架的并行FP-Growth算法——PFP算法解决在处理大规模数据时传统算法失效的问题,但是由于其将每次执行之后的中间结果输出到磁盘,降低算法执行效率。为提高并行FP-Growth算法执行效率,提出一种基于Spark的SPFPG算法。该算法运用负载均衡思想对分组策略进行改进,综合考虑分区计算量和FP-Tree规模两个因素,保证每个组之间负载总和近似相等。在Spark上实现FP-Growth算法——SFPG算法的基础上,实现优化后的SPFPG算法。实验结果表明,SPFPG算法相比SFPG算法挖掘效率更高,且算法具有良好的扩展性。     

基于OpenMP的Gibbs抽样正负关联规则算法研究

大数据集中挖掘正负关联规则是关联规则挖掘的重要研究内容。负关联规则挖掘存在挖掘关联规则数量多、难度大等问题,因此针对大数据集中挖掘正负关联规则提出一种基于OpenMP的Gibbs抽样正负关联规则挖掘算法。该算法通过Gibbs抽样从原始数据集中挖掘得到重要的关联规则,并在Gibbs抽样的转移概率计算部分利用OpenMP并行技术进行加速。在只挖掘重要正负关联规则的同时,缩短挖掘时间,有效提高正负关联规则挖掘的效率。在UCI蘑菇数据集中使用该算法,实验结果显示该算法在大数据集中具有较好的表现。     

Spark平台下的短文本特征扩展与分类研究

短文本分类经常面临特征维度高、特征稀疏、分类准确率差的问题。特征扩展是解决上述问题的有效方法,但却面临更大的短文本分类效率瓶颈。结合以上问题和现状,针对如何提升短文本分类准确率及效率进行了详细研究,提出了一种Spark平台上的基于关联规则挖掘的短文本特征扩展及分类方法。该方法首先采用背景语料库,通过关联规则挖掘的方式对原短文本进行特征补充;其次针对分类过程,提出基于距离选择的层叠支持向量机(support vector machine,SVM)算法;最后设计Spark平台上的短文本特征扩展与分类算法,通过分布式算法设计,提高短文本处理的效率。实验结果显示,采用提出的Spark平台上基于关联规则挖掘的短文本特征扩展方法后,针对大数据集,Spark集群上短文本特征扩展及分类效率约为传统单机上效率的4倍,且相比于传统分类实验,平均得到约15%的效率提升,其中特征扩展及分类优化准确率提升分别为10%与5%。     

改进的并行关联规则增量挖掘算法

针对大数据环境下基于Can树(canonical order tree)的增量关联规则算法存在树结构空间占用过大、频繁模式挖掘效率不佳以及MapReduce集群并行化性能不足等问题,提出了一种基于粗糙集和归并剪枝方法改进的并行关联规则增量挖掘算法MR-PARIRM(MapReduce-based parallel association rules incremental mining algo-rithm using rough set and merge pruning).首先,设计了一种基于粗糙集的相似项合并策略RS-SIM(rough set based similar item merge)对数据集的相似项进行合并处理,并根据合并后的数据进行Can树构造,从而降低树结构的空间占用;其次,提出了一种归并剪枝策略MPS(merge pruning strategy)对树结构中的传播路径进行修剪合并,通过压缩频繁模式搜索空间来加快频繁项挖掘;最后,通过动态调度策略DSS(dynamic scheduling strategy)对异构式MapReduce集群中的计算任务进行动态调度,实现了负载均衡,有效提升了集群的并行化运算能力.最终的实验仿真结果表明,MR-PARIRM在大数据环境下具有相对较好的性能表现,适用于对大规模数据进行并行化处理.     

A fast and low idle time method for mining frequent patterns in distributed and many-task computing environments

Association rules mining has attracted much attention among data mining topics because it has been successfully applied in various fields to find the association between purchased items by identifying frequent patterns (FPs). Currently, databases are huge, ranging in size from terabytes to petabytes. Although past studies can effectively discover FPs to deduce association rules, the execution efficiency is still a critical problem, particularly for big data. Progressive size working set (PSWS) and parallel FP-growth (PFP) are state-of-the-art methods that have been applied successfully to parallel and distributed computing technology to improve mining processing time in many-task computing, thereby bridging the gap between high-throughput and high-performance computing. However, such methods cannot mine before obtaining a complete FP-tree or the corresponding subdatabase, causing a high idle time for computing nodes. We propose a method that can begin mining when a small part of an FP-tree is received. The idle time of computing nodes can be reduced, and thus, the time required for mining can be reduced effectively. Through an empirical evaluation, the proposed method is shown to be faster than PSWS and PFP.     

并行关联规则挖掘综述

关联规则发现作为数据挖掘的重要研究内容，在许多实际领域内得到了广泛的应用。因为在挖掘过程中涉及到大量的数据和计算，高性能计算成为大规模数据挖掘应用的一个重要组成部分。该文介绍了当前并行关联规则挖掘方面的研究进展，对一些典型算法进行了分析和评价，从并行度、负载平衡以及和数据库的集成等方面展望了并行关联规则挖掘的研究方向。     

基于Spark的分布式数字信号处理算法库设计

传统的基于DSP与FPGA的数字信号处理技术更加适用于实时信号处理,且受到数据规模和频率分辨率的限制,使得其不适于进行大规模数据下的离线式数据处理、分析与挖掘的应用.目前工业大数据分析平台可以采用Spark作为实时信号处理和离线信号处理加速的计算引擎,但该分析平台缺少适用于分布式并行计算引擎的数字信号处理等数学计算的解决方案.基于此,本文提出了基于Spark的分布式数字信号处理算法库,为面向分析的工业大数据应用场景提供支撑.本文介绍了该算法库的架构设计,并以FFT算法和DFT算法为例介绍了传统数字信号处理算法在Spark下的分布式实现,最后对算法库进行了正确性测试和性能分析.结果表明该算法库能够正确完成数字信号处理的功能,同时可以满足工业大数据分析平台对于大规模数据集进行数字信号处理的需求.     

HFIM: a Spark-based hybrid frequent itemset mining algorithm for big data processing

Frequent itemset mining is one of the data mining techniques applied to discover frequent patterns, used in prediction, association rule mining, classification, etc. Apriori algorithm is an iterative algorithm, which is used to find frequent itemsets from transactional dataset. It scans complete dataset in each iteration to generate the large frequent itemsets of different cardinality, which seems better for small data but not feasible for big data. The MapReduce framework provides the distributed environment to run the Apriori on big transactional data. However, MapReduce is not suitable for iterative process and declines the performance. We introduce a novel algorithm named Hybrid Frequent Itemset Mining (HFIM), which utilizes the vertical layout of dataset to solve the problem of scanning the dataset in each iteration. Vertical dataset carries information to find support of each itemsets. Moreover, we also include some enhancements to reduce number of candidate itemsets. The proposed algorithm is implemented over Spark framework, which incorporates the concept of resilient distributed datasets and performs in-memory processing to optimize the execution time of operation. We compare the performance of HFIM with another Spark-based implementation of Apriori algorithm for various datasets. Experimental results show that the HFIM performs better in terms of execution time and space consumption.     

粒子群优化算法在关联规则挖掘中的研究综述

关联规则挖掘是数据挖掘中的重要领域,考虑到当前数据的大规模、高维度、模态多样及类型复杂等特性,传统关联规则挖掘算法已无法适应大数据的需求,粒子群优化算法作为一种高效的智能优化算法,为其提供了一种全新的解决方案,近年来被广泛应用于该领域.首先对粒子群优化算法的基本原理及关联规则的基本概念进行了详细介绍,回顾了粒子群优化算...     

基于垂直数据分布的大型稠密数据库快速关联规则挖掘算法

为进一步解决对大型事务数据库进行关联规则挖掘时产生的CPU时间开销大和I/O操作频繁的问题,给出了一种基于垂直数据分布的改进关联规则挖掘算法,称为VARMLDb算法。该算法首先有效地把数据库分为内存可以满足要求的若干划分,然后结合有向无环图和垂直数据形式diffse、差集来存储和计算频繁项集,极大地减少了存储中间结果所需的内存大小,解决了传统垂直数据挖掘算法对稠密数据库挖掘效率低下的问题,使该算法可有效地适用于大型稠密数据库的关联规则挖掘。整个算法吸取CARMA算法的优势,只需扫描两次数据库便可完成挖掘过程。实验结果表明该算法是正确的,在大型稠密数据库中,VARMLDb算法具有较高的执行效率。     

基于FIUT的并行频繁项集增量更新算法

针对目前大数据快速增加的环境下,海量数据的频繁项集挖掘在实际中所面临的增量更新问题,在频繁项超度量树算法（frequent items ultrametric trees,FIUT）的基础上,引入MapReduce并行编程模型,提出了一种针对频繁项集增量更新的面向大数据的并行算法。该算法通过检查频繁超度量树叶子节点的支持度来确定频繁项集,同时采用准频繁项集的策略来优化并行计算过程,从而提高数据挖掘效率。实验结果显示,所提出的算法能快速完成扫描和更新数据,具有较好的可扩展性,适合于在动态增长的大数据环境中进行关联规则相关数据挖掘。