论文部分内容阅读
数据规约技术的目标是在不影响后续挖掘效果的前提下,缩减数据集合的规模,进而提高后续挖掘的性能,是知识发现过程中预处理数据的一个重要步骤。实例选取作为数据规约中的一类重要算法,通过移除集合中的噪声和冗余数据,来精简数据集合,提高数据质量。面对现实应用中日益增长的数据量,在小型集合中能取得很好效果的实例选取算法面对大规模数据集合不再适用。受“分而治之”思想的启发,研究人员提出了若干分布式实例选取算法。这些算法将数据集合划分成不相关的若干部分,分别运行实例选取算法,最后将结果进行合并。由于各计算节点缺少数据的全局信息,会引入噪声和冗余数据,影响规约效果。为此,本文设计了一种新型的分布式实例选取框架,使得各计算节点能充分利用数据集合的全局信息。针对不同的应用需求,我们基于此框架设计了两种分布式实例选取算法,并基于MapReduce计算模型进行了原型实现。主要工作有以下几个方面:1、设计了一种新型的分布式实例选取框架。在分析已有算法不足的基础上,提出新的分布式并行框架。该框架将选取能代表集合数据信息的小部分数据分配到各计算节点,从而保证信息的全局性,改善已有算法准确度下降、可扩展性能差等问题,并对适用于此框架的实例选取算法进行分析。2、针对原始数据集合中的数据冗余问题,在所提出的框架基础上设计了一种新的分布式实例选取算法。该算法能生成一致性子集并与其串行版本产生相同的结果,且与输入数据顺序无关。基于MapReduce计算模型进行了算法原型实现(FCNN-MR),并在一个小型数据集合(Page-blocks)和两个大型数据集合(Poker-hand和Mnist)上进行测试,相比于已提出的分布式算法,具有更好的规约效率和准确率。3、针对原始数据集合中噪声和冗余数据并存的问题,基于随机爬山算法的思想设计了一种新的分布式实例选取算法。该算法利用遗传变异的特性不断提高选取数据子集的质量,最终达到精简数据集合的目的。算法基于MapReduce计算模型进行了原型实现(RMHC-MR),并在三个数据集合上进行测试,实验结果表明算法能有效移除噪声和冗余,具有良好的规约效率和准确率。