基于海量数据挖掘的分类算法研究

摘要

分类作为数据挖掘领域中最为活跃的分支之一，被广泛的应用于模式识别、图像识别、机器学习等领域。而且，分类在现实社会生活、生产实践中也有着广泛的应用场景，比如医疗图像识别、垃圾邮件过滤等。然而，随着大数据时代的到来，数据被迅速的生产和累计，TB级甚至 PB级的数据在分类应用场景中逐渐成为了普遍的问题。海量的数据虽然使得数据系统的模式更加的完备，但是也带来了更多的冗余和噪声，分类任务的执行时间也急剧增加。在这样一种背景下，更高的准确率已经不再是人们唯一追求的目标，如何在不影响算法现有分类准确率的情况下，提高算法的执行效率，似乎已经成为了算法研究者们新的关注的焦点。
　　Hadoop是通过借鉴Google的分布式文件系统GFS和并行计算框架MapReduce的思想，成功克隆出的一个开源的分布式系统。它使得基于集群的并行计算思想迅速的在数据计算领域得到发展和普及。同时也开启了将运行在单节点环境下的数据挖掘算法向集群环境上迁移并并行化执行的浪潮。
　　首先，本篇论文充分利用 KNN分类算法基于局部信息对测试样本进行分类的特性，结合聚类算法，通过裁剪与测试样本无关的训练样本，有效的降低了KNN算法的计算开销，达到提升KNN分类算法效率和性能的目的。然后借助与MapReduce并行计算模型，设计并实现了一个并行的基于聚类的 KNN分类器，并成功完成了在Hadoop集群上的运行与一系列的性能测试。其次，本文通过对朴素贝叶斯分类算法流程进行任务分解，实现了一个基于MapReduce模型的并行化的朴素贝叶斯分类器。但是，在具体的实践过程中发现，数据的离散化成为了并行化朴素贝叶斯分类器的性能瓶颈。因此，为了打破这一瓶颈，同样借助于MapReduce模型，设计并实现了基于熵的数据离散化算法。使得并行化的朴素贝叶斯分类器在进行海量数据分类时，拥有更高的效率。实验表明，无论是基于聚类的并行化KNN分类算法还是并行化朴素贝叶斯分类算法（采用并行的数据离散化方法进行离散化处理），都能够带来较大的性能提升和良好的扩展性。在一定程度上能够满足人们对海量数据分类的性能要求。