论文部分内容阅读
支持向量机(Support Vector Machine,SVM)是基于统计学习理论提出的经典学习算法,具有理论基础完善、泛化性能好、可以解决高维非线性问题等优点,被广泛应用于图像处理、文本分类、语音识别、异常检测等诸多分类预测领域。传感器网络监测、故障预测、入侵检测等在线分类预测问题日益增多,不同于传统的批处理,流数据具有数据量大、实时到达、动态变化等特点,传统批处理的SVM算法无法直接满足流处理需求,研究面向数据流的SVM算法对在线分类预测问题具有重要的意义和实用价值。由于数据量巨大,串行算法难以满足实时高效的要求,因此需要通过分布并行来提高算法执行效率。然而,SVM因计算复杂度高、参数耦合度高等特点,使得分布式SVM面临着效率较低、加速比提升有限等问题。为了满足不同地区对数据中心的动态访问需求,为用户提供更高效优质的服务,以及提高数据中心可靠性,越来越多的跨区域数据中心被建立部署。由于跨数据中心数据处理面临着通信成本高、网络环境不稳定、隐私保护等问题,如何实现低通信开销、避免传输原始数据的跨数据中心算法成为亟待解决的问题。本文从单节点、多节点、跨数据中心三个层次,针对数据流环境下,SVM算法的时间开销和通信开销等问题进行研究,主要工作如下:在单节点层次,SVM增量学习通常利用历史数据与新数据共同作为增量学习训练集更新模型。在数据流环境下,数据实时到达,数据量无界,使用传统方法进行增量学习时,支持向量会不断积累,增加增量学习过程的时间开销。为此,本文提出了一种保留部分支持向量的增量式SVM算法(Reserving Partial Support Vectors Incremental Learning Algorithm,PSVIL)。首先,根据支持向量到分类超平面的距离,将支持向量分成若干组,根据各组支持向量数量比例,计算各组应选取支持向量的数量。然后,各组内通过最大化向量间距之和的方法,选取尽可能分散的支持向量。各组选取的支持向量合并为历史向量的一个子集,该子集代表历史信息参与模型更新。最后将历史支持向量子集与新数据混合,构成增量学习训练集,训练新的模型,完成模型的更新。实验结果表明,该算法准确率与传统算法相差0.1%以内,平均时间开销降低68%。在多节点层次,现有分布式SVM算法通常将新数据随机分散至各节点,在各节点内使用分组数据与全局支持向量训练局部模型,然后将各节点训练得到的局部支持向量汇总到全局节点,作为全局节点的训练集训练全局模型。然而这种方法获得的加速比较低。因此,本文提出一种均匀数据划分的分布式SVM算法(Uniform Data Partitioning Distributed SVM Algorithm,UDPSVM)。该算法首先将新数据和历史支持向量分别划分到各节点,在各节点内使用新数据子集和历史支持向量子集训练局部模型,然后将各节点局部模型的参数进行汇总得到全局模型。新数据的划分首先使用K-means算法将各类别数据进行聚类,然后将每簇数据平均分散至各节点,使各节点的新数据分布与新数据全集近似。历史支持向量的划分首先根据支持向量到分类超平面的距离进行分组,然后将各分组的支持向量平均分散至各节点,使各节点的历史支持向量到分类超平面的距离分布与历史支持向量全集近似。通过上述数据划分方式,各节点数据分布与全局近似,因此各节点训练的局部模型近似全局模型,通过将局部模型的参数进行平均,得到全局模型。实验结果表明,该算法准确率与现有算法相差0.1%以内,加速比提高2-8倍。在跨数据中心层次,针对将原始数据汇总到单数据中心造成的通信开销高的问题,本文提出一种跨数据中心的分布式SVM算法(Geo-Distributed SVM,GDSVM)。各数据中心单独训练局部模型,然后将各局部模型进行加权平均得到全局模型,每个数据中心都保存全局模型。在数据分类阶段,新到达的数据直接在本地进行分类,保存部分新数据并打标签,然后分别计算全局模型和局部模型的准确率。在增量学习阶段,各数据中心交换局部分类准确率,根据各局部模型的分类准确率调整其在全局模型中的权重。该算法避免了大规模原始数据传输,降低通信成本。实验结果表明,该算法准确率与将原始数据汇总到单数据中心处理的方式相差0.5%以内,平均通信量降低52%。