论文部分内容阅读
随着信息技术的快速发展,人们收集、存储和传输数据的能力不断提高,各类应用领域产生海量的数据,数据挖掘与机器学习成为了数据分析和知识发现的重要工具。频繁模式挖掘是数据挖掘的基本问题,具有广泛的应用前景。传统的静态数据以及数据流频繁模式挖掘方法中,事务数据中的每个项都被看作是同等重要的,然而在实际应用中,特定的项或模式由于用户对其兴趣度不同,可能比其他项或模式更加重要。因此可以在挖掘过程中给每个项赋予不同的权值来体现它们不同的重要性,这就是加权频繁模式挖掘问题。虽然静态数据集上的加权频繁模式挖掘研究逐渐展开,但在数据流上的加权频繁模式挖掘尚处于起步阶段,是一个新的研究问题,随着流数据广泛出现在各类应用中,数据流上的加权频繁模式挖掘、闭合加权频繁模式挖掘、Top-K加权频繁模式挖掘也将成为研究的热点问题。
基于机器学习的预测方法能有效解决传统预测方法的局限性,在各个领域都有广泛的应用前景。我们研究了基于机器学习的预测技术在并行与分布式领域的应用,主要解决了多核下MPI最优运行时参数预测以及网格工作流活动性能预测问题。我们提出的方法具有一定的通用性,可以推广和应用到并行与分布式计算其他预测问题的研究中。
本文的贡献和具有创新性的工作如下:
1.首先提出了数据流加权频繁模式挖掘这一研究问题。为了保持加权频繁模式挖掘中的“向下闭合”特性,我们提出并证明了一种新的修订权值定义方法。在设计了一种新的SWFP结构来压缩存储数据流滑动窗口内加权频繁模式的基础上,我们设计并实现了基于滑动窗口的数据流加权频繁模式挖掘算法DS_SWFP。当流数据流过时,本算法仅对数据进行单遍扫描,并将数据包含的模式信息及权重信息增量更新到SWFP结构中。我们研究了两种剪枝策略来定期删除模式树中的非频繁模式,以便有效压缩存储空间。最后通过实验验证了算法的快速、有效和时空需求稳定性。
2.研究了大规模数据流上的闭合加权频繁模式挖掘技术。首先讨论并证明了闭合约束与加权约束的结合顺序问题,并在此基础上提出了一种新的算法DS CWFP。该算法以滑动窗口中的基本窗口为计算单位,先挖掘当前基本窗口中的局部潜在闭合加权频繁项集,在删除了过期窗口对滑动窗口的影响后,将局部闭合加权频繁项集及其子集按一定的规则动态更新到滑动窗口的全局DSCWFP结构中。复合的DSCWFP结构用来记录数据流加权频繁模式的动态变化并同时保存业已发现的闭合加权频繁模式结果,降低了维护多个模式树的空间开销以及由于数据流数据不断变化带来的维护复杂度。同时在挖掘过程中,我们采用了项合并、子项集剪枝等策略。对多个合成以及真实的数据集实验结果显示:DS CWFP算法仅需对流数据进行单遍扫描,并能够在有限的存储空间中高速挖掘数据流滑动窗口中的闭合加权频繁模式,具有较高的时空效率。
3.设计实现一种基于机器学习的通用的多核环境下MPI运行时参数优化模型,能自动为给定软、硬件结构的多核机群下的MPI程序预测接近最优的运行时参数组合。采用了两种标准的机器学习技术:决策树和人工神经网络来构建预测模型。实验证明,基于REPTree的预测模型和基于ANN的预测模型得到的优化运行时参数产生的加速比平均达到实际最大加速比的90%以上。
4.提出了一种基于机器学习的网格工作流活动性能预测方法。我们综合运用机器学习技术中的贝叶斯网络与神经网络技术,设计并实现了一种二层混合贝叶斯-神经网络预测模型,来对网格下的工作流活动的执行时间进行建模和预测。贝叶斯网络用来快速、可靠地构建各种影响因素之间连接关系的概率模式,并发现影响执行时间的不同因素间的潜在关系。神经网络利用构建的模型以及不同因素间的概率分布关系,提供高效和准确的预测。四个真实的工作流应用实验结果说明了我们方法的有效性。
针对数据流加权频繁模式挖掘,我们进行了一系列实验研究,对本文算法的性能进行了测试,并和已有的有关算法进行了比较。实验表明,我们的算法有效地实现了相关的数据流加权频繁模式挖掘任务。同时我们提出的基于机器学习的建模和预测方法可以推广到其他类型的并行或分布式应用的预测问题中,能有效缩短模型训练时间并提高预测精度。