0 引言

大数据^[1]指的是数据规模庞大到无法通过目前的技术、方法和理论, 在可以容忍的时间内对其进行获取、管理、处理的数据, 其具有数据体量大、数据类型多样、价值密度低等特点.随着大数据时代的到来, 传统的串行计算方法已经不能满足数据挖掘工作者的需要, 在并行框架下进行大规模数据挖掘已成为一种趋势.目前, 机器学习算法常用的并行框架有Hadoop^[2]、Spark^[3]以及MPI(message passing interface)^[4].文献[5]分别实现了Hadoop和Spark版本的Apriori算法, 实验结果表明Spark较Hadoop在I/O上时间开销更低，效率更高, 文献[6]将SVM和kNN分别在Spark和MPI/OpenMP上并行, 证明了MPI/OpenMP比Spark具有更高效率.

在数据的规模不断增大的同时, 数据的表现形式也愈加丰富, 而传统的监督学习认为每个样本只有一个标签, 不能准确地表述事物的复杂语义.多标签学习^[7]认为每个样本可能包含一个或多个标签, 具有多个标签的样本能够更好地表现事物语义信息的多样性.多个标签的引入虽然增强了样本的表达能力, 却也不可避免地使相应的学习任务变得更加困难.与单标签学习相比, 多标签学习中标签集合的数目随标签个数的增加呈指数级增长, 导致了其输出空间较大, 从而增加了学习的难度.ML-kNN(multi-label k-nearest neighbor)^[8]是一种基于kNN(k-nearest neighbor)和贝叶斯理论的多标签学习算法, 算法分别统计待预测样本k近邻中每个标签的信息, 并利用最大后验概率准则进行预测. ML-kNN也是多标签学习算法中的第一个惰性学习算法^[8], 其同时继承惰性学习和贝叶斯方法的优势^[7]：决策的边界可以通过调整待预测样本的邻居个数而调整；计算每个类别的先验概率可有效缓解不平衡问题.此外, ML-kNN还具有算法简洁、分类准确率高等特点, 因而被广泛使用.然而, 当数据规模庞大时, ML-kNN算法由于自身的时间复杂度较高而不能高效地对其进行处理, 本文基于MPI编程模型将ML-kNN并行化, 以提升ML-kNN的效率, 节约硬件成本.这也是首次将MPI并行计算框架应用到了多标签学习领域, 通过与传统的串行ML-kNN的对比实验, 验证了本文提出方法的可行性和有效性.值得一提的是, 在对数据集的划分时, 本文提出的方法不仅可以将数据集以样本为单位划分, 也能以特征为单位划分, 这使得在处理高维数据的时候, 本文的方法具有更大的优势.

1 ML-kNN算法

设$\mathscr{X} $为特征空间, $\mathscr{Y}$是有限个标签的集合.对于任一样本x(x∈ $\mathscr{X} $), 其标签的集合$Y\subseteq \mathscr{Y} $, ${{{\vec{y}}}_{x}} $为样本x的类别向量, 向量中的元素为${{{\vec{y}}}_{x}} $(l)(l∈$\mathscr{Y}$), 若l∈$\mathscr{Y}$, 则${{{\vec{y}}}_{x}} $(l)的值为1, 否则为0.此外, 定义N(x)为样本x在训练集中的k近邻的集合, 其中样本之间相似度用欧氏距离度量, 则成员统计向量$ {{{\vec{C}}}_{x}}\left( l \right)$被定义为样本x的k近邻中标签为l的样本的个数.对于测试样本t, $ H_{1}^{l}$表示事件样本t含有标签l；$ H_{0}^{l}$则表示事件样本t不含标签l; $ E_{j}^{l}$ (j∈{0, 1, …, k})表示事件在样本t的k近邻中, 恰好有j个样本含有标签l.利用最大化后验概率准则(maximum a posteriori, MAP), 测试样本t的标签向量${{{\vec{y}}}_{t}} $为

$ {{{\vec{y}}}_{x}}\left( l \right)=\text{arg}\ \text{ma}{{\text{x}}_{b\in \{0, 1\}}}P(H_{b}^{l}|E_{{{{\vec{C}}}_{t}}(l)}^{l}), l\in \mathscr{Y}. $

(1)

设训练集样本个数为m, 特征空间维度为d, 标签空间维度为n, ML-kNN算法训练阶段的时间复杂度为O(m²d+nmk), 测试阶段的时间复杂度为O(md+nk)^[7].

2 ML-kNN的并行 2.1 数据集的划分

设特征空间$\mathscr{X}$是d维实数向量空间R^d, 标签集合$\mathscr{Y}$可以映射到一个n维实数向量空间Rⁿ, 训练集D由m个样本组成, 则训练集D中样本特征的集合可由m行d列的矩阵M_m×d表示, 样本标签的集合可由m行n列的矩阵L_m×n表示.对于矩阵M, 将其以样本和特征为单位近似均匀划分成p×q个子矩阵.为了阐述的方便, 定义每个子矩阵为一个特征数据块, 在同一列的特征数据块组成一个特征数据列, 在同一行的特征数据块组成一个特征数据行.对于每一个特征数据块, 为其分配一个独有的进程, 并将该特征数据块和标签矩阵L传入该进程.

2.2 先验概率的计算

求取先验概率的核心是对训练集标签信息的统计, 即对于每个标签统计其正类样本和负类样本的个数.首先将标签信息以样本为单位近似均匀划分为p×q个子集, 每个进程仅需统计其中的一个子集, 再通过全归约求和操作, 每个进程即可得到整个训练集标签信息的统计结果.最后, 对于每个进程, 根据统计结果计算先验概率, 计算方法与串行的一致.

2.3 k近邻的求取

由于在数据分割时, 不仅将训练集以样本为单位进行了划分, 还将训练集以特征为单位进行了划分, 使得原始的ML-kNN算法中的欧氏距离在并行中不适用, 同时为了充分利用矩阵运算的优势提升效率, 故将欧氏距离在求取k近邻的情况下等价为

$ Dist\left( {\mathit{\boldsymbol{a, b}}} \right) = \sqrt {\left( {\mathit{\boldsymbol{a - b}}} \right){{\left( {\mathit{\boldsymbol{a - b}}} \right)}^{\rm{T}}}} \Leftrightarrow \left( {\mathit{\boldsymbol{a - b}}} \right){\left( {\mathit{\boldsymbol{a - b}}} \right)^{\rm{T}}} \Leftrightarrow \mathit{\boldsymbol{a}}{\mathit{\boldsymbol{a}}^{\rm{T}}} - 2\mathit{\boldsymbol{a}}{\mathit{\boldsymbol{b}}^{\rm{T}}} + \mathit{\boldsymbol{b}}{\mathit{\boldsymbol{b}}^{\rm{T}}}\\ \Leftrightarrow \mathit{\boldsymbol{b}}{\mathit{\boldsymbol{b}}^{\rm{T}}} - 2\mathit{\boldsymbol{a}}{\mathit{\boldsymbol{b}}^{\rm{T}}}, $

(2)

其中：a为当前样本的特征向量；b为目标样本的特征向量.改进后的距离公式允许特征向量a、b同时截断为多个子向量，并分别计算距离后再累加.利用此性质, k近邻的求取步骤如下：首先，将每个特征数据列对应的进程划分为一个独立的通信域, 通信域内互相广播传递计算距离所需的特征数据块, 进而利用公式(2)求取该特征子集下的样本与样本间的距离.其次，在所有通信域完成距离计算后, 对于每个特征数据行对应的所有进程进行归约求和操作, 归约求和的结果将以样本为单位近似均匀地分配到特征数据行对应的各个进程.由公式(2)的性质可知, 部分特征下的距离在归约求和之后即为在所有特征下完整的距离.最后，由于每个进程中均有部分归约求和的结果, 且归约求和的结果为该进程中分配的样本到其他样本的完整距离, 故对于每个进程, 利用所分配样本的距离信息进行k近邻的求取.

2.4 后验概率的求取

求取后验概率的核心是近邻标签信息的统计, 即对某个样本统计其近邻中含有标签l(l∈ $ \mathscr{Y}$)的个数以及不含有标签l的个数.由于在k近邻的求取步骤中, 每个进程已将分配到的样本子集的k近邻求出, 故只需在此基础上对近邻的标签信息做统计, 然后将统计结果进行全归约求和操作, 每个进程即可得到整体的近邻标签信息统计结果.最后, 对于每个进程, 根据总的标签信息统计结果计算出后验概率.

3 实验与结果分析 3.1 性能指标

基于MPI将ML-kNN算法并行化并未对其精度产生任何影响, 故本实验仅从效率的角度考虑运行时间和加速比两项.运行时间指的是训练模型和分类的总时间, 不包括读取数据集的时间.加速比用于度量并行算法运行时间和串行算法运行时间的关系, 其公式为Speedup=base_line/parallel_time, 其中：base_line为串行程序运行时间；parallel_time为并行程序运行时间.加速比Speedup越大, 并行的效果越好.

3.2 数据集

本文选用的数据集来源于Mulan官网的多标签数据集.实验将从样本数量、特征数量两个维度验证并行算法的性能, 故选取的数据集如表 1所示.此外, 由于在实验中调用了开源库, 为了避免开源库对稀疏数据优化减少实际的计算量, 从而产生实验误差, 故对于稀疏表示的数据集EUR-Lex和rcv1v2, 将其去稀疏化并转化为完整表示的数据集.

3.3 实验环境

本实验使用的MPI编程环境是由11台服务器搭建的真实物理集群, 串行实验的运行环境和单服务器配置相同.服务器的处理器为Intel Xeon E5-2620，使用的操作系统为CentOS 6.5，MPI的版本为3.1.4，GCC版本为4.4.7.

3.4 实验内容与结果分析

本实验主要目的是验证基于MPI并行化后的ML-kNN算法在大规模数据集上的适应能力，以及不同数据划分方式对效率的影响, 故实验中不考虑k值对ML-kNN算法的影响, 实验中默认取值为10.首先, 基于多标签学习开源库Mulan实现了传统的ML-kNN算法，基于C++线性代数开源库Armadillo实现了改进的ML-kNN算法, 以测试串行的ML-kNN算法在不同数据集上的效率以及本文提出的改进算法对算法效率的影响.表 2描述了基于Mulan的串行算法和基于Armadillo的改进算法在表 1所述4个数据集上的运行时间.

实验结果表明: 1)当数据集的规模上升至十万级、特征维度上百时, 串行的ML-kNN算法很难在可接受的时间内将数据处理下来. 2)改进后的ML-kNN算法具有更高的效率, 在数据规模较大时有更明显的效果, 其原因在于改进后的ML-kNN算法编写时使用了C++线性代数开源库Armadillo, 在k近邻的求取时能够更加充分地利用缓存, 而k近邻的求取是ML-kNN算法时间开销最大的部分, 故提升效果较为明显.此外, C++语言更偏向于底层, 相比Java语言效率更高.

其次, 本实验测试了并行后的ML-kNN算法在使用不同的计算资源情况下的性能.表 3和表 4描述了并行算法在表 1所述的4个数据集上的运行时间以及加速比.其中p和q分别为特征数据块的列数和行数, Speedup为并行ML-kNN算法相对改进后的串行ML-kNN算法的加速比.由于本实验是考察算法在不同计算资源上的性能, 为了保持统一, 故将数据集均以样本为单位切分.

实验结果表明: 1)程序的运行时间会随着计算资源的增加而减少, 这种减少的程度会随着计算资源的增加逐渐变缓.其原因是, 随着节点数的增加, 通信需要的时间将逼近甚至超过计算所需时间. 2)通过对比表 3和表 4可知, 当数据集特征维度较高时, 仅以样本为单位划分数据集对整体效率的提升不大, 其原因将在后续实验中进行分析. 3)根据Amdahl定律^[9], 最理想的并行结果为加速比等于所用核心个数.而本实验中出现加速比大于所使用核心个数的原因是, 在串行代码中, 计算样本间的距离采用的是向量的运算, 当训练集数据量较大时, 随之增长的计算量会造成在cache中大量的数据替换, 导致cache命中率降低, 从而运行效率较低.而在并行算法中, 为了进一步提升算法的效率, 使用了矩阵运算替换部分向量计算, 减少了计算量, 增加了cache命中率, 因而能够充分利用缓存进一步提升效率.值得一提的是, 如果直接在串行算法中使用矩阵运算替换向量运算可能会导致单机内存不足的问题.以NUS-WIDE-bow数据集为例, 如果直接使用矩阵运算的方式计算训练集的近邻矩阵, 需要占用大约195 G的内存. 4)基于Mulan的串行ML-kNN算法和本文提出的并行ML-kNN算法在表 1所述4个数据集上的输出结果是一致的, 验证了本文对ML-kNN算法的改进以及并行化并未影响ML-kNN算法的精度.

最后, 本实验测试了在计算资源相同的情况下, 不同数据切分方式对并行ML-kNN算法性能的影响.实验结果表明:在计算资源一定的情况下, 相比单一的以样本为单位划分数据集, 本文提出方法不仅可以将数据集以样本为单位划分, 也能以特征为单位划分, 这使得在处理高维数据的时候, 本文方法具有更大的优势.

4 总结

本文提出了一种基于MPI编程模型的ML-kNN算法并行方法.在保证ML-kNN算法精度不受损的情况下, 改进了ML-kNN算法并提升了算法的效率.实验结果表明, 本文提出的方法可以灵活针对数据集的特点改变数据集的切分方式, 在大规模数据集上适应性更强.因此, 本文的方法是可行且高效的.