覆盖算法作为一种构造型分类建模算法,以其训练速度快、分类效果好而著称。在现今互联网时代,时常面对较大的数据集训练和分类的挑战,因此提升机器学习算法的训练速度和分类精度具有重要意义。本文主要研究覆盖算法CA(Covering Algorithm)的样本训练速度的提升和模型分类精度的提升,分别提出并行覆盖算法Parallel CA和叠覆盖算法OCA(Overlapped Covering Algorithm).虽然覆盖算法在训练小数据集时具有较快的速度,但是当数据集逐渐增大的时候,覆盖算法的训练速度会严重降低。并行覆盖算法Parallel CA可以利用并行计算机的优势在数据集较大的时候也能快速训练样本。叠覆盖算法的提出则是启发于计算机图形学中的形状颜色填充过程,它通过对样本的覆盖而不断地向周围扩展而达到整体覆盖模型与样本空间近似的作用,可以较好地提升模型的分类能力。本文的主要工作包括：1.通过对领域覆盖算法分析,发现其建立的模型能实现多类样本的分类实质上是因为领域覆盖算法求解的是多个二分类问题的集合。对任意一类样本的覆盖都只考虑覆盖同类样本而不覆盖异类样本,与异类样本的类别数无关。可以将所有的异类样本看作是一个等价类,它不影响当前类别样本的覆盖,因此任意一类样本的覆盖计算都是独立的子问题,与异类样本覆盖不构成依赖关系。子问题的独立性为并行算法的设计提供了理论基础。实验中利用三组公开的数据集对并行覆盖算法进行训练测试,在多核处理机上的实验结果证明并行的覆盖算法能成倍地提升样本的训练速度,且算法本身不依赖于特定的并行计算环境,也适用于分布式集群。2.覆盖算法建立分类模型的主要思想是“物以类聚”,通过覆盖中心和半径概括其附近的样本区域,最终整个样本集被若干个覆盖所泛化。本文从另外一个角度考虑,认为样本是对客观世界的抽象描述,它在空间中的分布具有一定的规律,覆盖则是某种程度上对样本空间分布的一种近似。覆盖的空间区域与样本的空间分布越近似,其对样本的分类效果越好。通过对同类覆盖是否可重叠的研究,总结出两种极端的覆盖方式：保守型覆盖和开放型覆盖。前者要求所有的覆盖必须相互独立,不允许重叠；后者允许同类覆盖之间相互重叠。保守型覆盖对样本具有较好的拟合性,对可识样本分类效果较好,但是模型中拒识区域较多；开放型覆盖中拒识区域较少,但是对于未知区域样本具有较高的误分类风险。综合对实验数据的分析,发现开放型覆盖具有较好的泛化能力,其分类能力略优于保守型覆盖。3.在分析保守型覆盖和开放型覆盖方式的基础上,我们提出叠覆盖算法。叠覆盖算法利用一个队列记录中间覆盖的样本,重复以队列中记录的样本作为覆盖中心做覆盖,不断向队列中加入新覆盖的样本,通过这种不断重叠的覆盖方式逐渐扩展覆盖空间而达到逼近原样本空间的效果。边缘样本的处理以及样本孤立点的处理进一步对叠覆盖算法做出优化。实验中同样利用公用数据集对算法进行验证,结果显示叠覆盖算法所求的模型对样本的分类具有较少的拒识样本数、分类精度高的特点,在部分数据集上分类效果显著提升。4.最后,我们在研究覆盖算法的基础上开发出一套完整的覆盖算法软件工具包,以供同行的研究者交流探讨。工具包实现了覆盖算法、叠覆盖算法,提供了算法的训练、测试、交叉验证和随机测试等功能。源代码公开,原生的C++程序既可以在windows平台也可以在Linux平台下编译运行,适用于不同平台下的研究人员。