基于Spark的Top-k对比序列模式挖掘
发布时间：2021-11-12 23:56
对比序列模式（distinguishing sequential pattern,DSP）指在目标类序列集合中频繁出现,而在非目标类序列集合中不频繁出现的序列.对比序列模式能够描述2个序列集合间的差异,有着广泛的应用,例如:构建序列分类器,识别DNA序列的生物特征,特定人群行为分析.与挖掘满足支持度阈值要求的对比序列模式相比,挖掘对比度top-k对比序列模式能避免用户设置不恰当的支持度阈值.因而,更易于用户使用.但是现有的top-k对比序列模式挖掘算法难以处理大规模序列数据.对此,设计了一种基于Spark的top-k对比序列模式并行挖掘算法,称为SP-kDSP-Miner.此外,为了提高SP-kDSPMiner的效率,针对Spark结构的特点,设计了候选模式生成策略和若干剪枝策略,以及候选模式对比度的并行计算方法.通过在真实数据集与合成数据集上的实验,验证了SP-kDSP-Miner的有效性、执行效率和可扩展性.
【文章来源】：计算机研究与发展. 2017,54(07)北大核心EICSCD
【文章页数】：13 页
【部分图文】：
图２集合枚举树示例Ｆｉｇ．２Ａｎｅｘａｍｐｌｅｏｆａｓｅｔｅｎｕｍｅｒａｔｉｏｎｔｒｅｅ
列模式集合Ｃｌ生成长度为ｌ＋１的候选对比序列模式集合Ｃｌ＋１．步骤②利用剪枝策略２，移除不可能成为ｔｏｐ－ｋ对比序列模式的候选模式．步骤③～⑦生成长度为ｌ＋１的候选对比序列模式．步骤⑧返回利用算法１生成的候选对比序列模式集合．算法１的算法复杂度为Ｏ（｜Ｃｌ｜），其中｜Ｃｌ｜是长度为ｌ的候选对比序列模式的个数．Ｆｉｇ．３ＣｏｎｔｒａｓｔｃａｌｃｕｌａｔｉｏｎｐｒｏｃｅｓｓｉｎＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ图３ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ中对比度计算过程３．２对比度并行计算ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ使用Ｓｐａｒｋ分布式框架将大规模数据分片并读入计算节点，然后各计算结点获取１４５７张鹏等：基于Ｓｐａｒｋ的Ｔｏｐ－ｋ对比序列模式挖掘
Ｍｉｎｅｒ的执行效率，本文使用ｋＤＳＰ－Ｍｉｎｅｒ进行对比．与ｋＤＳＰ－Ｍｉｎｅｒ一样，ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ需要设定的参数为γ与ｋ．图４～５展示了参数对ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ算法的影响．因为ｋＤＳＰ－Ｍｉｎｅｒ算法难以适用于大规模序列数据集，所以只对ＡＢＣ－２与Ａｃｔｉｎ两个序列集进行了实验．进行此实验时，ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ算法用到Ｓｐａｒｋ集群的４个节点，ｋＤＳＰ－Ｍｉｎｅｒ所用线程数为５．图４展示了当设置ｋ＝１０时，间隔约束γ对算法执行效率的影响，并与ｋＤＳＰ－Ｍｉｎｅｒ进行了比较．随着间隔约束的范围增大，候选元素之间有效的组合变多，ｋＤＳＰ－Ｍｉｎｅｒ与ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ运行时间都会随之增加．相较于ｋＤＳＰ－Ｍｉｎｅｒ，ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ变化趋势缓慢一些．因为间隔约束的范围比较小，候选模式少，Ｓｐａｒｋ集群计算能力没有被充分利用．并且ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ在计算对比度过程中，设计了减枝策略３，降低了计算量．总体来说，对于任意的间隔约束γ，具有集群优势的ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ执行时间较ｋＤＳＰ－Ｍｉｎｅｒ更短，并且随着间隔约束γ的范围变大，ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ所用集群的计算能力被充分利用，执行效率会有一定程度提高．图５展示了当设置γ＝［０，２］时ｋ值对算法执行效率的影响，并与ｋＤＳＰ－Ｍｉｎｅｒ进行了比较．随着ｋ值增大，ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ与ｋＤＳＰ－Ｍｉｎｅｒ执行时间
【参考文献】：
期刊论文
[1]带间隔约束的Top-k对比序列模式挖掘[J]. 杨皓,段磊,胡斌,邓松,王文韬,秦攀. 软件学报. 2015(11)
[2]FSMBUS:一种基于Spark的大规模频繁子图挖掘算法[J]. 严玉良,董一鸿,何贤芒,汪卫. 计算机研究与发展. 2015(08)
本文编号：3491893
【文章来源】：计算机研究与发展. 2017,54(07)北大核心EICSCD
【文章页数】：13 页
【部分图文】：
图２集合枚举树示例Ｆｉｇ．２Ａｎｅｘａｍｐｌｅｏｆａｓｅｔｅｎｕｍｅｒａｔｉｏｎｔｒｅｅ
列模式集合Ｃｌ生成长度为ｌ＋１的候选对比序列模式集合Ｃｌ＋１．步骤②利用剪枝策略２，移除不可能成为ｔｏｐ－ｋ对比序列模式的候选模式．步骤③～⑦生成长度为ｌ＋１的候选对比序列模式．步骤⑧返回利用算法１生成的候选对比序列模式集合．算法１的算法复杂度为Ｏ（｜Ｃｌ｜），其中｜Ｃｌ｜是长度为ｌ的候选对比序列模式的个数．Ｆｉｇ．３ＣｏｎｔｒａｓｔｃａｌｃｕｌａｔｉｏｎｐｒｏｃｅｓｓｉｎＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ图３ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ中对比度计算过程３．２对比度并行计算ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ使用Ｓｐａｒｋ分布式框架将大规模数据分片并读入计算节点，然后各计算结点获取１４５７张鹏等：基于Ｓｐａｒｋ的Ｔｏｐ－ｋ对比序列模式挖掘
Ｍｉｎｅｒ的执行效率，本文使用ｋＤＳＰ－Ｍｉｎｅｒ进行对比．与ｋＤＳＰ－Ｍｉｎｅｒ一样，ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ需要设定的参数为γ与ｋ．图４～５展示了参数对ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ算法的影响．因为ｋＤＳＰ－Ｍｉｎｅｒ算法难以适用于大规模序列数据集，所以只对ＡＢＣ－２与Ａｃｔｉｎ两个序列集进行了实验．进行此实验时，ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ算法用到Ｓｐａｒｋ集群的４个节点，ｋＤＳＰ－Ｍｉｎｅｒ所用线程数为５．图４展示了当设置ｋ＝１０时，间隔约束γ对算法执行效率的影响，并与ｋＤＳＰ－Ｍｉｎｅｒ进行了比较．随着间隔约束的范围增大，候选元素之间有效的组合变多，ｋＤＳＰ－Ｍｉｎｅｒ与ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ运行时间都会随之增加．相较于ｋＤＳＰ－Ｍｉｎｅｒ，ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ变化趋势缓慢一些．因为间隔约束的范围比较小，候选模式少，Ｓｐａｒｋ集群计算能力没有被充分利用．并且ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ在计算对比度过程中，设计了减枝策略３，降低了计算量．总体来说，对于任意的间隔约束γ，具有集群优势的ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ执行时间较ｋＤＳＰ－Ｍｉｎｅｒ更短，并且随着间隔约束γ的范围变大，ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ所用集群的计算能力被充分利用，执行效率会有一定程度提高．图５展示了当设置γ＝［０，２］时ｋ值对算法执行效率的影响，并与ｋＤＳＰ－Ｍｉｎｅｒ进行了比较．随着ｋ值增大，ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ与ｋＤＳＰ－Ｍｉｎｅｒ执行时间
【参考文献】：
期刊论文
[1]带间隔约束的Top-k对比序列模式挖掘[J]. 杨皓,段磊,胡斌,邓松,王文韬,秦攀. 软件学报. 2015(11)
[2]FSMBUS:一种基于Spark的大规模频繁子图挖掘算法[J]. 严玉良,董一鸿,何贤芒,汪卫. 计算机研究与发展. 2015(08)
本文编号：3491893
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/3491893.html
