一种基于Spark的频繁项集快速挖掘算法

如何在海量数据集中提高频繁项集的挖掘效率是目前研究的热点.随着数据量的不断增长,使用传统算法产生频繁项集的计算代价依然很高.为此,提出一种基于Spark的频繁项集快速挖掘算法(fast mining algorithm of frequent itemset based on spark,Fmafibs),利用位运算速度快的特点,设计了一种新颖的模式增长策略.该算法首先采用位串表达项集,利用位运算来快速生成候选项集;其次,针对超长位串计算效率低的问题,考虑将事务垂直分组处理,将同一事务不同组之间的频繁项集通过连接获得候选项集,最后进行聚合筛选得到最终频繁项集.算法在Spark环境下,以频繁项集挖掘领域基准数据集进行实验验证.实验结果表明所提方法在保证挖掘结果准确的同时,有效地提高了挖掘效率.

基于垂直频繁模式树带有负载均衡的分布关联规则挖掘算法

大数据时代,开展面向海量、分布数据的知识发现研究成为学界和业界关注的热点,而负载均衡问题是开发分布式挖掘算法必须考虑的重要因素之一。为此,提出了一种基于垂直频繁模式树带有负载均衡的分布关联规则挖掘算法,算法采用垂直频繁模式树存储项及其关联而无需对局部挖掘结果进行合并,减少了通信量,简化了处理流程。同时所提出的算法采用混合体系结构即中心站点按照局部站点的处理能力分配任务,实现了负载均衡,提升了算法的性能。实验结果表明所提算法切实可行并具有较高效率。

一种不确定性数据频繁模式的垂直挖掘算法

由于数据的不确定性,传统频繁模式挖掘方法难以适用到不确定性数据中.针对不确定性数据的特点,把挖掘确定性数据频繁模式的经典垂直挖掘算法Eclat算法扩展到不确定性数据中,提出了UP-Eclat算法.该算法分别对Tid集和项集搜索树进行扩展:把原来只有一个id域的Tid扩展成两个域,即id域和概率域;用扩展后的Tid集代替原来的Tid集,生成扩展后的项集搜索树.扩展后的Tid集可以表示不确定性数据,然后利用扩展后的项集搜索树进行频繁模式挖掘.通过实验与分析,UP-Eclat算法可行,高效.

用垂直数据格式构建FP增长树的算法

目前FP增长树的建立采用的是事务-项目集数据格式,即水平数据格式,扫描数据库需要2次。采用垂直数据格式,即项目-事务集数据格式,按照最小事务项目表优先的原则投影事务-项目以建立FP增长树,扫描数据库仅需1次。设计了独特的垂直项目头表独特的存储结构,便于垂直数据的存储、事务的投影、FP树的建立和垂直数据的增量更新。

一种挖掘不确定数据最大模式的深度优先算法

不确定性数据挖掘是数据挖掘领域的研究热点,但其应用于最大频繁项集的算法较少。根据不确定数据挖掘的特点,把挖掘确定性数据最大频繁模式的Gen Max算法扩展到不确定数据中,提出一种U-Gen Max算法。对Tid集进行扩展,在id域的基础上增加概率域,实现垂直数据格式转换。在频繁项集判断方面加入前置判断来剪枝非频繁项集,相比直接计算置信度的方式,降低了计算量。基于栈式结构给出多步回退剪枝新策略,从而避免Gen M ax算法只能单步回退的缺陷。实验结果证明,该算法计算性能良好,可适用于各种情况下的稀疏数据集与支持度较高情况下的稠密数据集。

垂直模式类高效用模式挖掘的改进算法

由于高效用模式挖掘较为复杂,提高其挖掘算法的效率是数据挖掘的研究热点。HUP-miner算法是典型的基于垂直模式类的高效用模式挖掘算法,虽然能够有效地减少效用列表的总个数,但对于项集的划分,效用列表需要更多的空间。针对该问题,在HUI-miner算法的基础上充分考虑了1-扩展集中项集的关联性,减少了效用列表个数,提出了改进的IHUI-miner算法。实验结果表明,改进算法IHUI-miner在时间效率和减少效用列表的个数上都优于HUP-miner与HUI-miner算法。