现实世界中运转的许多复杂系统如基因表达、风险评估、经济预测等都可以抽象为特定的预测问题,而这些预测问题的高效解决将对社会的生产生活产生重大意义.机器学习作为一种解决这些复杂预测问题的重要方法,它能够通过从经验中不断学习来提高其自身的学习与预测能力.现阶段,随着信息技术的迅猛发展与各领域大数据的爆发,很多实际应用中的数据规模都呈现出爆炸式增长.数据的大规模性使得已有机器学习方法在解决预测问题时面临巨大挑战.因此,研究高效的机器学习算法具有重要实际应用价值和理论意义.有监督学习是机器学习中应用最为丰富、内容最广泛的部分,如何高效地在大规模数据上训练泛化性能强的学习器是机器学习研究领域面临的关键问题之一.为此,本文以数据划分与数据压缩为研究基础,针对面向海量数据如何提升学习算法的执行效率问题开展了系统研究.主要研究成果如下:(1)针对支持向量机面对大规模数据训练效率较低的问题,借鉴于分而治之的思想,提出了一个基于局部几何信息的高效支持向量机算法.对于给定的大规模数据集,基于支持向量机算法中决策函数由少数支持向量确定的特点,利用线性投影来探究当前数据中的分类决策边界,并深入分析了如何对数据进行划分、划分后子集上的分类器的训练以及分类器的融合三个核心问题,构造了一个高效的支持向量机算法.实验结果表明,该算法获得了比已有的三个代表性算法更高的执行效率.(2)针对现有的基于数据划分的k-近邻分类加速算法缺乏理论分析的问题,本文利用优化理论给出了相应的机理分析.根据k-近邻分类算法的局部性特点,将寻找k个近邻的过程转化为一个优化问题,并给出了原始优化问题与使用数据划分优化问题在最优解下目标函数差异的估计.在此基础上提出利用K-means聚类减小此差异,进而设计了基于K-means聚类的k-近邻分类加速算法.本文提出的数据划分对算法泛化性能影响的估计进一步夯实了基于数据划分的加速学习算法理论基础.(3)针对k-近邻算法因存储所有训练实例而导致其预测效率较低的问题,本文借鉴样本表征整体的思想,分别提出了基于数据压缩的高效k-近邻分类和高效k-近邻回归算法.通过探索训练实例在输入空间中的分布,构造了一个数据分层机制,并结合随机抽样的特点提出了一个基于分层抽样的高效k-近邻分类算法;基于k-近邻回归算法的局部性特点,构造了单个实例对回归模型贡献的度量,并给出了识别噪声实例和冗余实例的判定准则,在此基础上建立了删除噪声实例和冗余的实例的有效机制.实验结果表明,本文提出的数据压缩算法获得了比已有的五个的代表性压缩算法更低的实例存储率.(4)针对Logistic回归算法的训练过程因数据规模巨大而导致其计算梯度效率低的问题,基于统计学习理论,提出了一个基于按需抽样的Logistic回归加速算法.依据优化学习理论,给出了确保样本集上的梯度估计所在方向是使得目标函数下降的方向的准则.在此基础上,借助于分而治之的思想,将满足此准则的多元估计问题转化为若干个一元估计问题,设计了一个依据已抽样样本集信息的自适应确定样本量的按需抽样算法,且理论上证明了此算法得到的梯度估计以很大的概率确保是当前目标函数下降的方向.此算法克服了随机抽样需要事先确定样本量的难题,并加深了基于随机抽样的加速学习算法的理论研究.本文针对传统机器学习算法面向大规模数据执行效率较低的问题,基于数据划分与数据压缩,提出了一系列高效的加速学习算法.相关实验结果验证了提出算法的有效性与高效性,并为智能信息处理提供了新的技术支撑.