论文部分内容阅读
共享知识挖掘是指通过学习不同事物之间的共享知识，将学习到的知识应用到未知事物来加快认知未知事物。目前，已经有学者对共享知识挖掘进行了研究，并提出了共享挖掘算法。但是现有的共享挖掘算法都是串行的挖掘算法，只能处理小规模的数据集，已经无法满足数据急剧增长的需求。为此，本文主要针对共享知识挖掘算法的并行化做了一系列的研究，主要工作和贡献包括以下几点：（1）针对大数据集中共享知识串行挖掘算法效率低下的问题，通过引入云计算技术和决策树挖掘算法的并行思想，提出一种基于hadoop的并行共享决策树挖掘算法(PSDT)，该算法基于MapReduce并行模型，采用传统的属性表结构实现共享决策树挖掘过程中的属性并行性和节点并行性；同时，利用MapReduce模型独特的排序机制实现了预排序属性表的并行处理。实验结果表明，相比串行的共享决策树挖掘算法（SDT），并行的PSDT算法能够处理更大规模的数据，具有良好的可扩展性；在处理较大规模的数据集时，PSDT算法的运行效率明显高于SDT算法。(2)针对Hadoop集群的性能瓶颈——I/O，从减少I/O的角度出发，采用“CPU换I/O”策略，提出了一种新颖的混合数据结构。基于混合数据结构的并行共享决策树挖掘算法（HPSDT），在计算分裂指标阶段使用属性表结构进行并行计算，在分裂阶段采用数据记录结构进行分裂。相比传统的属性表结构，混合数据结构既减少了数据冗余又简化了分裂过程，大大减少了I/O操作。数据分析表明，HPSDT算法简化了分裂过程，其I/O操作是PSDT的0.34左右。实验结果表明，HPSDT具有良好的并行性和扩展性。(3)在分析比较HPSDT挖掘算法和PSDT挖掘算法时间性能的基础上，进行试验验证。实验结果表明，对于同一数据集，HPSDT挖掘算法的时间性能要优于PSDT挖掘算法。在数据集的大小为917M时，PSDT与HPSDT的运行时间比率即达到了2.45，并且随着数据集的增大，HPSDT的优越性愈加明显。