一种高效用项集并行挖掘算法

由于能反映用户的偏好,可以弥补传统频繁项集挖掘仅由支持度来衡量项集重要性的不足,高效用项集正在成为当前数据挖掘研究的热点。为使高效用项集挖掘更好地适应数据规模不断增大的实际需求,提出了一种高效用项集的并行挖掘算法PHUI-Mine。提出了记录挖掘高效用项集信息的DHUI-树结构,描述了DHUI-树的构造方法,论证了DHUI-树的动态剪枝策略。在此基础上,给出了高效用项集挖掘的并行算法描述。实验结果表明,PHUI-Mine算法具有较高的挖掘效率及较低的存储开销。     

基于R-list的Top-K高效用项集挖掘算法

针对现有的一阶段Top-K高效用项集挖掘算法挖掘过程中阈值提升慢,迭代时生成大量候选项集造成内存占用过多等问题,提出一种基于重用链表(R-list)的Top-K高效用挖掘算法RHUM。使用一种新的数据结构R-list来存储并快速访问项集信息,无需第2次扫描数据库进行项集挖掘。该算法重用内存以保存候选集信息,结合改进的RSD阈值提升策略对数据进行预处理,期间采用更严格的剪枝参数在递归搜索的过程中同时计算多个项集的效用来缩小搜索空间。在不同类型数据集中的实验结果表明:RHUM算法在内存效率方面均优于其他一阶段算法,且在K值变化时能保持稳定。     

基于数据索引结构的跨级高效用项集挖掘算法

针对现有的跨级高效用项集挖掘（HUIM）算法非常耗时且占用大量内存的问题，提出一种基于数据索引结构的跨级高效用项集挖掘算法（DISCH）。首先，为了高效存储和快速检索到搜索空间中的所有项集，拓展带有分类信息和索引信息的效用链表为数据索引结构（DIS）；然后，为了提高内存利用率，对不满足条件的效用链表所占的内存进行回收再分配；最后，在构建效用链表时使用提前结束策略，以减少效用链表的产生。基于真实零售数据集和合成数据集进行的实验结果表明，与CLH-Miner(Cross-Level High utility itemsets Miner)算法相比，DISCH在运行时间上平均降低了77.6%，同时在内存消耗上平均降低了73.3%，可见该算法能高效完成跨级高效用项集的搜索，并且降低算法的内存消耗。     

面向数据流的一个高效用项集挖掘算法

近年来,在数据流中进行高效用项集挖掘成为一个重要的研究课题。已存在的算法在挖掘过程中产生大量的候选项集,使用户很难从大量候选模式中筛选出有用的信息。针对这种情况,提出一个数据流高效用项集挖掘算法HUIDE(High-Utility Itemsets Over Data Streams)。算法首先综合考虑数据的信息特征,提出一种有效的效用度量方法。然后采用基于时间的滑动窗口技术更加准确地描述数据分布,构建一种树结构HUI-tree(High Utility Itemsets tree)。最后遍历构建的树结构HUI-tree挖掘高效用项集。在人工和真实数据流上的实验结果表明该算法通过扫描一次数据库获取挖掘结果,减少了候选项集的产生及时间和空间的消耗。该算法在数据流中能够有效地挖掘高效用项集。     

基于DBP的TOp-k高效用项集挖掘算法

针对Top-k高效用项集挖掘算法在挖掘过程中忽略内存管理的问题,提出基于DBP的Top-k高效用项集挖掘算法TKBPH(Top-k buffer pool high utility itemsets mining),采用数据缓冲池(DBP)结构存储效用链表,并由索引链表记录效用链表在DBP的位置.数据缓冲池根据挖掘过程情况在数据缓冲池尾部动态插入和删除效用链表,通过索引链表直接读取效用链表避免项集搜索时频繁的比较操作,有效减少内存空间和运行时间消耗.不同类型数据集上的实验结果表明,TKBPH算法在挖掘过程中执行速度更快、内存消耗更少.     

减少候选项集的数据流高效用项集挖掘算法

大数据环境下高效用项集挖掘算法中过多的候选项集极大地降低了算法的时空效率,提出了一种减少候选项集的数据流高效用项集挖掘算法。首先,通过数据流中当前窗口的一次扫描建立一个全局树,并降低全局树中头表入口与节点的冗余效用值;然后,基于全局树生成候选模式,基于增长算法降低局部树的候选项集效用;最终,从候选模式中选出高效用模式。基于真实数据流的实验结果表明,本算法的时空效率与内存占用比均优于其他数据流的高效用模式挖掘算法。     

基于项编码的分布式频繁项集挖掘算法

Apriori算法是解决频繁项集挖掘最常用的算法之一,但多轮迭代扫描完整数据集的计算方式,严重影响算法效率且难以并行化处理。随着数据规模的持续增大,这一问题日益严重。针对这一问题,提出了一种基于项编码和Spark计算框架的Apriori并行化处理方法——IEBDA算法,利用项编码完整保存项集信息,在不重复扫描完整数据集的情况下完成频繁项集挖掘,同时利用Spark的广播变量实现并行化处理。与其他分布式Apriori算法在不同规模的数据集上进行性能比较,发现IEBDA算法从第一轮迭代后加速效果明显。结果表明,该算法可以提高大数据环境下的多轮迭代的频繁项集挖掘效率。     

基于滑动窗口模型的数据流闭合高效用项集挖掘

从数据流中挖掘高效用项集是一项具有挑战性的任务,因为传入的数据必须在时间和存储内存约束下进行实时处理数据流挖掘通常会产生大量冗余的项集,为了减少这些无用的项集数量且保证无损压缩,需要挖掘闭合项集,它可以比全集高效用项集的集合小几个数量级.为了解决以上问题,提出一种基于滑动窗口模型的数据流闭合高效用项集挖掘(closed high utility itemsets mining over data stream based on sliding window model,CHUI_DS)算法.在 CHUI DS 中设计了 一种新的效用列表结构,该结构在提升批次插入和删除的速度方面非常有效此外,应用修剪策略来改进闭合项集挖掘过程,消除潜在的低效用候选对象.对真实数据集和合成数据集进行的广泛实验评估显示了该算法的效率以及可行性就速度而言,它优于先前提出的主要以批处理模式运行的算法.且它适用于不同大小的滑动窗口,在事务数量等方面具有较强的扩展性.     

基于快速高效用项集挖掘的大规模消息流预测算法研究与应用

为了提高大规模消息流话题预测的准确性与效率,提出基于高效用项集挖掘的消息流话题预测算法。计算时间窗口中词汇的内部效用与外部效用,根据会话内所有词汇的效用计算最小效用值;采用高效用项集挖掘算法产生候选话题模式集,随之提取最终的话题模式。为了提高高效用项集挖掘的时间效率与存储效率,设计三角项集效用树保存项集的效用信息,设计话题搜索树保存候选话题模式集。最终基于真实消息流数据集进行实验,结果显示该算法有效地提高了话题预测的准确率,并且实现了较快的响应时间。     

HHUIM：一种新的启发式高效用项集挖掘方法

针对基于启发式的高效用项集挖掘算法在挖掘过程中可能丢失大量项集的问题,提出一种新的启发式高效用项集挖掘算法HHUIM。HHUIM利用哈里斯鹰优化算法进行种群的更新,能够有效减少项集的丢失。提出并设计了鹰的替换策略,解决了搜索空间较大的问题,降低了适应度函数值低于最小效用阈值的鹰的数量。此外,提出存储回溯策略,可有效防止算法收敛过快达到局部最优。大量的实验表明,所提算法优于目前最先进的启发式高效用项集挖掘算法。     

基于Spark框架的FP-Growth大数据频繁项集挖掘算法

针对大数据中的频繁项集挖掘问题,提出一种基于Spark框架的FP-Growth频繁项集并行挖掘算法。首先,根据垂直布局思想将数据按照事务标识符垂直排列,以此解决扫描整个数据集的缺陷。然后,通过FP-Growth算法构建频繁模式树,并生成频繁1-项集。接着,通过扫描垂直数据集来计算项集的支持度,从而识别出非频繁项,并将其从数据集中删除以降低数据尺寸。最后,通过迭代过程来生成频繁 -项集。在标准数据集上的实验结果表明,该算法能够有效挖掘出频繁项集,在执行时间方面具有很大的优越性。     

基于存储改进的分区并行关联规则挖掘算法

针对现有算法存储结构简单、生成大量冗余的候选集、时间和空间复杂度高,挖掘效率不理想的情况,为了进一步提高关联规则算法挖掘频繁集的速度,优化算法的执行性能,提出基于内存结构改进的关联规则挖掘算法。该算法基于Spark分布式框架,分区并行挖掘出频繁集,提出在挖掘过程中利用布隆过滤器进行项目存储,并对事务集和候选集进行精简化操作,进而达到优化挖掘频繁集的速度、节省计算资源的目的。算法在占用较少内存的条件下,相比于YAFIM和MR-Apriori算法,在挖掘频繁集效率上有明显的提升,不但能较好地提升挖掘速度,降低内存的压力,而且具有很好的可扩展性,使得算法可以应用到更大规模的数据集和集群,从而达到优化算法性能的目的。     

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

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

一种基于Spark框架的并行FP-Growth挖掘算法

Apriori和FP-Growth算法是频繁模式挖掘中的经典算法,由于Apriori存在更多缺陷,因此FP-Growth是单机计算环境下比较高效的算法。然而,对于非并行计算在大数据时代遇到的瓶颈,提出一种基于事务中项间联通权重矩阵的负载平衡并行频繁模式增长算法CWBPFP。算法在Spark框架上实现并行计算,数据分组时利用负载均衡策略,存入分组的数据是相应频繁项的编码。每个工作节点将分组数据中每一个事物中项的联通信息存入一个下三角联通权重矩阵中,使用被约束子树来加快每个工作节点挖掘频繁模式时创建条件FP-tree的速度,再用联通权重矩阵避免每次挖掘分组中频繁模式时对条件模式基的第一次扫描。由于联通权重矩阵和被约束子树的结合应用于每一个工作节点的FP-tree挖掘过程,因此提升了并行挖掘FP-tree性能。通过实验表明,所提出的并行算法对大的数据有较高性能和可扩展性。     

基于Spark平台城市出租车乘客出行特征分析

从海量出租车GPS轨迹数据中挖掘和分析城市出租车乘客的出行特征,可以为城市交通管理者和出租车行业管理者在城市交通规划与管理、城市交通流均衡与车辆调度等方面提供决策依据.基于Spark大数据处理分析平台,选择YARN作为资源管理调度系统,采用HDFS分布式存储系统,对出租车GPS轨迹数据进行挖掘.给出了基于Spark平台的出租车乘客出行特征的挖掘方法,包括出租车乘客出行距离分布、出租车使用时间分布及出租车出行需求.实验结果表明,基于Spark平台分析方法能够快速且准确的分析出出租车乘客出行特征.     

基于Spark的油藏数据挖掘与分析

为了方便油藏数据特征的分析和石油的勘探开发过程,本文利用Spark并行计算框架分析油藏数据,并通过数据挖掘算法分析油藏属性之间的潜在关系,对油藏的不同层段进行了分类和预测.本文的主要工作包括：搭建Spark分布式集群和数据处理、分析平台,Spark是流行的大数据并行计算框架,相对传统的一些分析方法和工具,可以实现快速、准确的数据挖掘任务;根据油藏数据的特点建立多维异常检测函数,并新增渗孔比判别属性Pr;在处理不平衡数据时,针对逻辑回归分类提出交叉召回训练模型,并优化代价函数,针对决策树,提出KR-SMOTE对小类别样本进行过采样扩充,这两种方法都可以有效处理数据不平衡问题,提高分类精度.     

流数据Top-K关键字查询算法

基于Spark Streaming计算框架的分布式Top-K关键字查询是统计流数据中所有关键字的热点研究问题。多数研究通过限定存储空间来实现Top-K关键字查询,并假设关键字集合已知。针对这个问题,提出一种可应用于关键字集合未知情况的分布式Top-K关键字查询算法,根据监测到的关键字动态地调整存储空间,通过更新策略的优化提升其精度。实验结果表明,该算法的性能在关键字集合未知的情况下比现有算法更优。     

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

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

一种基于Spark的不确定数据集频繁模式挖掘算法

如何在海量不确定数据集中提高频繁模式挖掘性能是目前研究的热点.传统算法大多是以期望、概率或者权重等单一指标为数据项集支持度，在大数据背景下，同时考虑概率和权重支持度的算法难以兼顾其执行效率.为此，本文提出一种基于Spark的不确定数据集频繁模式挖掘算法（UWEFP），首先，为了同时兼顾数据项的概率和权重，计算一项集的最大概率权重值并进行剪枝；然后，为了减少对数据集的多次扫描，结合Spark框架的优点，设计了一种具有FP-tree特征的新颖的UWEFP-tree结构进行模式树的构建及挖掘；最后在Spark环境下，以UCI数据集进行实验验证.实验结果表明本文的方法在保证挖掘结果的同时，提高了效率.