·360· 智能系统学报 第9卷 核函数Gram矩阵和距离矩阵：K、M 由MOA所生成的人工数据集被广泛用于大数据算 输出：更新后的核矩阵K 法有效性的评估工作中[56。基准数据集采用 1)初始化k。 UCI数据集[)中的数据集。实验中选取MOA提供 2)k1=(k(xo,x1),…,k(xo,xw) 的其中3个生成器生成不同的人工数据集，蕴含不 3)forj=1,…,Ndo 同的数据生成规律。表1和2分别展示了人工数据 4)k2=KG,·) 集和UCI基准数据集的主要信息。MOA序列生成 5)k=k-k (I+MK)Mk2 器生成的3个人工数据集，以数据记录生成时间顺 6)end for 序保存在3个单独的数据文件中，在线多核学习时 7)用k。更新矩阵K中的最后一行和最后一列 顺序读取文件中的数据进行训练和测试。2个UCI 8)return K 数据集中的数据随机重排之后按顺序读入。其中数 对于数据流在线核学习问题，采用FFO策略， 据集M1生成20份，规模从10°~2×10'，用于评估 即每次把当前的数据样本替换时间最长的数据样 数据集规模与CPU处理时间的增长关系。 本，因此算法3中不需要优先队列。 表1MOA实验数据集的主要信息 算法4半监督在线多核学习SSL-MKL Table 1 Details of MOA data sets 输入： 编号 生成器类型 大小 属性个数 初始训练数据集D。输入数据样本集，D={x,y:}, MI WaveForm 10°-2×10 21 x:是样本，y:是其标签 M2 RandomRBF 10 37 输出：更新后的核矩阵K M3 SEA Concepts 10° 3 1)初始化K 表2UCl实验数据集的主要信息 2)使用批处理算法由D。学习K Table 2 Details of UCI data sets 3)for each (x;,y;)in D 编号 数据集描述 大小 属性个数 4)if L;is not NULL then 5)Call算法1(x,y:) M4 Forest CoverType 581012 54 6)更新K M5 Poker-Hand 10 11 7)end if 在上述5个数据集上进行3组实验。第1组实 8)f静态大数据集then 验评估本文的半监督在线多核学习算法(semi-su- 9)Call算法2(K,D。,M,x,Lc,Q) pervised learning -multiple kernel learning,SSL- l0)else if数据流then MKL)的有效性，并与文献[17]中的批处理多核学 11)Cal算法3(K,Do,M,x:) 习算法及文献[9]、[18]中的有监督在线多核学习 12)end if 算法进行比较。第2组实验分析本文算法对不同规 13)更新K 模数据集处理的CPU运算时间增长与数据集大小 14)end for 之间的关系。第3组实验评估本文算法的迭代次数 15)return K 与学习器性能的变化关系，从而说明其收敛性能。 为了把在线多核学习和数据依赖进行结合，算 在3组实验中均采用参数随机的RBF核、多项 法每读入一个数据样本x,判断是否有标签，若有标 式核和三角函数核函数各100个，即m=300。第1 签，则先执行多核学习的权重值更新，再执行基于数 组实验采用如下设置：对比的一般核函数采用参数 据依赖的核修改：若没有标签，则仅执行核修改（算 随机的RBF核和多项式核，核学习器使用标准的 法2和算法3)。核修改是针对加权之后的核函数 SVM,只进行二类分类，并采用0-1损失函数评估 进行。算法4描述了2部分核学习的结合过程。 分类错误率。其中数据集M1的规模为10。在M 3实验结果及分析 和k。的更新算法中，限制其规模N为1000个样本。 在人工数据集和大数据学习的基准数据集上对 第1组实验评估SSL-MKL算法有效性并与有 本文算法进行有效性评估，并与现有的算法进行比 监督的在线核学习算法进行比较，同时引入一个非 较。人工数据集使用MOA[14的序列生成器自动生 在线学习的多核学习算法作为算法有效性的基线。 成，在实验中共生成了3个规模不同的人工数据集， 表3给出了对比算法的基本信息。核函数 Ｇｒａｍ 矩阵和距离矩阵： Ｋ、 Μ 输出：更新后的核矩阵 Ｋ １）初始化 ｋｘ０ ２） ｋ１ ＝ （ｋ（ｘ０ ，ｘ１ ），…，ｋ（ｘ０ ，ｘＮ）） ３）ｆｏｒ ｊ ＝ １，…，Ｎ ｄｏ ４） ｋ２ ＝ Ｋ（ｊ，·） ５） ｋｘ０ ＝ ｋ１ － ｋ Ｔ １ （Ｉ ＋ ＭＫ） －１Ｍｋ２ ６）ｅｎｄ ｆｏｒ ７）用 ｋｘ０ 更新矩阵 Ｋ 中的最后一行和最后一列 ８）ｒｅｔｕｒｎ Ｋ 对于数据流在线核学习问题，采用 ＦＩＦＯ 策略， 即每次把当前的数据样本替换时间最长的数据样 本，因此算法 ３ 中不需要优先队列。 算法 ４ 半监督在线多核学习 ＳＳＬ⁃ＭＫＬ 输入： 初始训练数据集 Ｄ０ 输入数据样本集， Ｄ ＝ ｛ｘｉ，ｙｉ｝ ， ｘｉ 是样本， ｙｉ 是其标签 输出：更新后的核矩阵 Ｋ １）初始化 Ｋ ２）使用批处理算法由 Ｄ０ 学习 Ｋ ３）ｆｏｒ ｅａｃｈ （ｘｉ，ｙｉ） ｉｎ Ｄ ４）ｉｆ Ｌｉ ｉｓ ｎｏｔ ＮＵＬＬ ｔｈｅｎ ５）Ｃａｌｌ 算法 １（ｘｉ，ｙｉ） ６）更新 Ｋ ７）ｅｎｄ ｉｆ ８）ｉｆ 静态大数据集 ｔｈｅｎ ９）Ｃａｌｌ 算法 ２（Ｋ，Ｄ０ ，Ｍ，ｘｉ，ＬＣ ，Ｑ） １０）ｅｌｓｅ ｉｆ 数据流 ｔｈｅｎ １１）Ｃａｌｌ 算法 ３（Ｋ，Ｄ０ ，Ｍ，ｘｉ） １２）ｅｎｄ ｉｆ １３）更新 Ｋ １４）ｅｎｄ ｆｏｒ １５）ｒｅｔｕｒｎ Ｋ 为了把在线多核学习和数据依赖进行结合，算 法每读入一个数据样本 ｘ ，判断是否有标签，若有标 签，则先执行多核学习的权重值更新，再执行基于数 据依赖的核修改；若没有标签，则仅执行核修改（算 法 ２ 和算法 ３）。 核修改是针对加权之后的核函数 进行。 算法 ４ 描述了 ２ 部分核学习的结合过程。 ３ 实验结果及分析 在人工数据集和大数据学习的基准数据集上对 本文算法进行有效性评估，并与现有的算法进行比 较。 人工数据集使用 ＭＯＡ ［１４］ 的序列生成器自动生 成，在实验中共生成了 ３ 个规模不同的人工数据集， 由 ＭＯＡ 所生成的人工数据集被广泛用于大数据算 法有效性的评估工作中［１５ ⁃ １６］ 。 基准数据集采用 ＵＣＩ 数据集［１９］中的数据集。 实验中选取 ＭＯＡ 提供 的其中 ３ 个生成器生成不同的人工数据集，蕴含不 同的数据生成规律。 表 １ 和 ２ 分别展示了人工数据 集和 ＵＣＩ 基准数据集的主要信息。 ＭＯＡ 序列生成 器生成的 ３ 个人工数据集，以数据记录生成时间顺 序保存在 ３ 个单独的数据文件中，在线多核学习时 顺序读取文件中的数据进行训练和测试。 ２ 个 ＵＣＩ 数据集中的数据随机重排之后按顺序读入。 其中数 据集 Ｍ１ 生成 ２０ 份，规模从 １０ ６ ～ ２ × １０ ７ ，用于评估 数据集规模与 ＣＰＵ 处理时间的增长关系。 表 １ ＭＯＡ 实验数据集的主要信息 Ｔａｂｌｅ １ Ｄｅｔａｉｌｓ ｏｆ ＭＯＡ ｄａｔａ ｓｅｔｓ 编号 生成器类型 大小 属性个数 Ｍ１ ＷａｖｅＦｏｒｍ １０ ６ ～ ２×１０ ７ ２１ Ｍ２ ＲａｎｄｏｍＲＢＦ １０ ６ ３７ Ｍ３ ＳＥＡ Ｃｏｎｃｅｐｔｓ １０ ６ ２５ 表 ２ ＵＣＩ 实验数据集的主要信息 Ｔａｂｌｅ ２ Ｄｅｔａｉｌｓ ｏｆ ＵＣＩ ｄａｔａ ｓｅｔｓ 编号 数据集描述 大小 属性个数 Ｍ４ Ｆｏｒｅｓｔ ＣｏｖｅｒＴｙｐｅ ５８１０１２ ５４ Ｍ５ Ｐｏｋｅｒ⁃Ｈａｎｄ １０ ７ １１ 在上述 ５ 个数据集上进行 ３ 组实验。 第 １ 组实 验评估本文的半监督在线多核学习算法（ ｓｅｍｉ⁃ｓｕ⁃ ｐｅｒｖｉｓｅｄ ｌｅａｒｎｉｎｇ ⁃ ｍｕｌｔｉｐｌｅ ｋｅｒｎｅｌ ｌｅａｒｎｉｎｇ， ＳＳＬ⁃ ＭＫＬ）的有效性，并与文献［１７］中的批处理多核学 习算法及文献［９］、［１８］中的有监督在线多核学习 算法进行比较。 第 ２ 组实验分析本文算法对不同规 模数据集处理的 ＣＰＵ 运算时间增长与数据集大小 之间的关系。 第 ３ 组实验评估本文算法的迭代次数 与学习器性能的变化关系，从而说明其收敛性能。 在 ３ 组实验中均采用参数随机的 ＲＢＦ 核、多项 式核和三角函数核函数各 １００ 个，即 ｍ ＝ ３００。 第 １ 组实验采用如下设置：对比的一般核函数采用参数 随机的 ＲＢＦ 核和多项式核，核学习器使用标准的 ＳＶＭ，只进行二类分类，并采用 ０－１ 损失函数评估 分类错误率。 其中数据集 Ｍ１ 的规模为 １０ ６ 。 在 Μ 和 ｋＤ 的更新算法中，限制其规模 Ｎ 为 １０００ 个样本。 第 １ 组实验评估 ＳＳＬ⁃ＭＫＬ 算法有效性并与有 监督的在线核学习算法进行比较，同时引入一个非 在线学习的多核学习算法作为算法有效性的基线。 表 ３ 给出了对比算法的基本信息。 ·３６０· 智 能 系 统 学 报 第 ９ 卷