随着数据挖掘的迅猛发展,大数据广泛存在于工程应用之中,如互联网数据、医疗数据和图像数据等。这些海量数据的到来使得预测通常变得更加精确。与此同时,它们也带来了一系列的科学挑战,例如存储瓶颈、算法的可拓展性和可解释性等。在大数据时代背景下,我们需要开发高效的机器学习算法来克服海量数据所带来的挑战。我们熟知分类问题在数据挖掘中是一项十分重要的任务,也是机器学习领域中重要的研究内容之一。它在我们现实生活中的应用也非常广泛,比如垃圾邮件识别、手写数字识别、人脸识别、语音识别和推荐系统等。现有可扩展性的分类算法主要包括分布式SVM、局部化SVM等。虽然这些分类方法可以有效降低SVM的计算复杂度,但是它们的性能对所涉及的参数较为敏感,因此它们需要精细的参数选择策略,这通常会在训练过程中带来巨大的计算量。此外,这些分类算法中大多数都缺乏对泛化能力的理论验证。因此,开发具有理论保证的可扩展性分类算法不仅具有重要的科学价值,而且对于当前大数据背景下的算法研究具有重要的实际意义。本文主要聚焦于具有可扩展性的分类算法研究。区别于支持向量机(SVM)的最大边际原理,本文提出了一种新的高效分类算法,称为快速多项式核分类算法(FPC),来克服算法的可拓展性和存储瓶颈所带来的挑战,并提出其相应的分布式版本用于处理具有更大数据规模或在分布式数据环境下的分类任务。本文的主要贡献如下:(1)我们主要利用多项式核构造出合适的特征映射将数据投影到具有“适度维度”的特征空间,并采用带有乘子的交替方向方法(ADMM)来快速求解相应的分类模型,从而提出快速多项式核分类算法。(2)从理论上,我们在常见的噪声假设下建立算法相应的学习率。(3)从实验上,我们进行了一系列的仿真实验和实际数据实验来体现算法的有效性并验证相应的理论。实验结果表明,FPC算法可显著降低现有学习算法的计算负担和存储内存,但几乎不降低其泛化能力。此外,一系列的实验结果表明所提算法的分布式版本能够进一步有效处理具有更大数据规模或在分布式环境下的分类任务。