流数据分类是流数据挖掘中一个非常重要的任务,该任务旨在从连续不断到达的流式数据中增量学习一个从输入变量到类标变量的映射函数,以便对随时到达的新样本进行准确分类。在线学习范式,作为一种增量式的机器学习技术,是流数据分类的有效工具。近年来随着大规模应用的兴起,在线学习范式开始受到广泛关注和应用。本文重点研究面向高维和演化流数据分类的在线学习算法,具体地,针对高维流数据展现的“维度诅咒”挑战和演化流数据存在的“概念漂移”挑战,本文分别研究了在线特征选择算法、稀疏在线学习算法和资源高效的在线集成算法。本文的主要工作及其创新点包括:1.提出了两个基于自适应次梯度方法的在线特征选择算法,算法基于l0的截断方法取得稀疏性,在评估特征重要性时,既考虑了特征在当前预测模型中的权重,又考虑了特征在历史预测序列中出现的频率。与需要通过精细调节l1正则化参数来控制特征选择数目的l1正则化方法相比,所提算法通过将所需预算作为输入参数,易于控制特征选择的数目。对两个算法进行了详细的悔恨分析,并在6个高维数据集上验证了所提算法相比于目前先进的在线特征选择算法和基于l1正则化的稀疏在线学习算法的性能优势。2.分析了演化环境中3个经典的梯度下降算法的shifting悔恨界,证明步长的选择对于梯度下降算法的概念漂移适应能力有重要影响。具体地,使用不变的步长调度比使用递减的步长调度算法能取得更好的概念漂移适应性,为该理论分析提供了实验上的证据支持。基于上述理论和实验分析的结果,提出了一个稀疏近似线性分类算法,该算法使用不变的步长调度以便具有更好的漂移适应性,在每轮学习中,算法首先执行一个梯度下降得到一个中间解,然后在中间解附近找到一个最稀疏的新解,这涉及到求解一个非凸的优化问题,证明该优化问题可以通过一个简单的贪心截断方法高效求解。一个截断误差参数可以控制中间解和新解之间的远近程度,从而控制模型的稀疏度从无稀疏性到完全稀疏性连续变化。给出并分析了所提算法的shifting悔恨界,并通过大量实验证明所提算法相比于先进的稀疏在线学习算法在高维的稳态流数据和演化流数据上均具有优越性。3.提出了一个资源高效的在线集成分类算法,该算法使用在线的核SVM算法—BPegasos作为组件分类器来解决高维流数据上的可扩展性问题和每个概念中的小样本问题,并通过充分利用BPegasos的特点来更好地处理各种类型的概念漂移。具体地,通过使用不同预算大小的BPegasos来构建多样性的组件,并为每个组件分类器配备了一个漂移检测器来监测和评估组件最新的性能,当漂移检测器检测到某些组件的性能发生严重退化时,就触发一个漂移警报,集成算法因此开始进行组件结构调整,将当前组件中性能最差的组件及其漂移检测器重启,使得最差的组件可以在最新的数据上重新开始学习。最后,在高维流数据上的实验表明所提集成算法相比于目前最先进的Hoeffding树集成算法在序列准确率和资源利用效率上都具有优势,在大量合成和真实的具有概念漂移的数据集上,当所有对比的集成算法都使用BPegasos作为组件分类器时,所提算法也表现出显著更好的能力处理各种类型的概念漂移。