第9卷第3期 智能系统学报 Vol.9 No.3 2014年6月 CAAI Transactions on Intelligent Systems Jun.2014 D0:10.3969/j.issn.1673-4785.201403067 网络出版地址：http://www.enki..net/kcms/doi/10.3969/j.issn.16734785.201403067.html 面向大数据流的半监督在线多核学习算法 张钢，谢晓珊，黄英，王春茹 (广东工业大学自动化学院，广东广州510006) 摘要：在机器学习中，核函数的选择对核学习器性能有很大的影响，而通过核学习的方法可以得到有效的核函数。 提出一种面向大数据流的半监督在线核学习算法，通过当前读取的大数据流片段以在线方式更新当前的核函数。 算法通过大数据流的标签对核函数参数进行有监督的调整，同时以无监督的方式通过流形学习对核函数参数进行 修改，以使得核函数所体现的等距面尽可能沿着数据的某种低维流形分布。算法的创新性在于能同时进行有监督 和无监督的核学习，且不需要对历史数据进行再次扫描，有效降低了算法的时间复杂度，适用于在大数据和高速数 据流环境下的核函数学习问题，其对无监督学习的支持有效解决了大数据流中部分标记缺失的问题。在MOA生成 的人工数据集以及UC大数据分析的基准数据集上进行算法有效性的评估，其结果表明该算法是有效的。 关键词：大数据流：在线多核学习：流形学习：数据依赖核：半监督学习 中图分类号：TP18文献标志码：A文章编号：1673-4785(2014)03-0355-09 中文引用格式：张钢，谢晓珊，黄英，等.面向大数据流的半监督在线多核学习算法[J].智能系统学报，2014,9(3)：355-363. 英文引用格式：ZHANG Gang,XIE Xiaoxian,HUANG Ying,etal.An online multi-kernel learning algorithm for big data[J】 CAAI Transactions on Intelligent Systems,2014,9(3):355-363. An online multi-kernel learning algorithm for big data ZHANG Gang,XIE Xiaoshan,HUANG Ying,WANG Chunru (School of Automation,Guangdong University of Technology,Guangzhou 510006,China) Abstract:In machine learning,a proper kernel function affects much on the performance of target learners.Commonly an effective kernel function can be obtained through kernel learing.We present a semi-supervised online multiple ker- nel algorithm for big data stream analysis.The algorithm learns a kernel function through an online update procedure by reading current segments of a big data stream.The algorithm adjusts the parameters of currently learned kemel function in a supervised manner and modifies the kemel through unsupervised manifold learning,so as to make the contour sur- faces of the kemel along with some low dimensionality manifold in the data space as far as possible.The novelty is that it performs supervised and unsupervised leaming at the same time,and scans the training data only once,which reduces the computational complexity and is suitable for the kernel learning tasks in big datasets and high speed data streams. This algorithm's support to the unsupervised learning effectively solves the problem of label missing in big data streams. The evaluation results from the synthetic datasets generated by MOA and the benchmark datasets of the big data analysis from the UCI data repository show the effectiveness of the proposed algorithm. Keywords:big data stream;online multi-kemel learning;manifold learning;data-dependent kernel;semi-supervised learning 随着信息技术的快速发展和大规模应用，数据 收稿日期：2014-03-25.网络出版日期：2014-06-14. 的生成速度及存储规模也在快速增长，特别是Wb 基金项目：国家自然科学基金资助项目(81373883) 通信作者：张钢.E-mail:px@gut.edu.cn.. 页面、社交网络及物联网的普及和应用，使人们所要
第 ９ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．９ №．３ ２０１４ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１４ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１４０３０６７ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｏｉ ／ １０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３４７８５．２０１４０３０６７．ｈｔｍｌ 面向大数据流的半监督在线多核学习算法 张钢，谢晓珊，黄英，王春茹 （广东工业大学 自动化学院，广东 广州 ５１０００６） 摘 要：在机器学习中，核函数的选择对核学习器性能有很大的影响，而通过核学习的方法可以得到有效的核函数。 提出一种面向大数据流的半监督在线核学习算法，通过当前读取的大数据流片段以在线方式更新当前的核函数。 算法通过大数据流的标签对核函数参数进行有监督的调整，同时以无监督的方式通过流形学习对核函数参数进行 修改，以使得核函数所体现的等距面尽可能沿着数据的某种低维流形分布。 算法的创新性在于能同时进行有监督 和无监督的核学习，且不需要对历史数据进行再次扫描，有效降低了算法的时间复杂度，适用于在大数据和高速数 据流环境下的核函数学习问题，其对无监督学习的支持有效解决了大数据流中部分标记缺失的问题。 在 ＭＯＡ 生成 的人工数据集以及 ＵＣＩ 大数据分析的基准数据集上进行算法有效性的评估，其结果表明该算法是有效的。 关键词：大数据流；在线多核学习；流形学习；数据依赖核；半监督学习 中图分类号： ＴＰ１８ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１４）０３⁃０３５５⁃０９ 中文引用格式：张钢，谢晓珊，黄英，等． 面向大数据流的半监督在线多核学习算法［Ｊ］． 智能系统学报， ２０１４， ９（３）： ３５５⁃３６３． 英文引用格式：ＺＨＡＮＧ Ｇａｎｇ，ＸＩＥ Ｘｉａｏｘｉａｎ，ＨＵＡＮＧ Ｙｉｎｇ， ｅｔ ａｌ． Ａｎ ｏｎｌｉｎｅ ｍｕｌｔｉ⁃ｋｅｒｎｅｌ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｂｉｇ ｄａｔａ ［ Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１４， ９（３）： ３５５⁃３６３． Ａｎ ｏｎｌｉｎｅ ｍｕｌｔｉ⁃ｋｅｒｎｅｌ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｂｉｇ ｄａｔａ ＺＨＡＮＧ Ｇａｎｇ， ＸＩＥ Ｘｉａｏｓｈａｎ， ＨＵＡＮＧ Ｙｉｎｇ， ＷＡＮＧ Ｃｈｕｎｒｕ （Ｓｃｈｏｏｌ ｏｆ Ａｕｔｏｍａｔｉｏｎ， Ｇｕａｎｇｄｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， Ｇｕａｎｇｚｈｏｕ ５１０００６， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｉｎ ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ， ａ ｐｒｏｐｅｒ ｋｅｒｎｅｌ ｆｕｎｃｔｉｏｎ ａｆｆｅｃｔｓ ｍｕｃｈ ｏｎ ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｔａｒｇｅｔ ｌｅａｒｎｅｒｓ． Ｃｏｍｍｏｎｌｙ ａｎ ｅｆｆｅｃｔｉｖｅ ｋｅｒｎｅｌ ｆｕｎｃｔｉｏｎ ｃａｎ ｂｅ ｏｂｔａｉｎｅｄ ｔｈｒｏｕｇｈ ｋｅｒｎｅｌ ｌｅａｒｎｉｎｇ． Ｗｅ ｐｒｅｓｅｎｔ ａ ｓｅｍｉ－ｓｕｐｅｒｖｉｓｅｄ ｏｎｌｉｎｅ ｍｕｌｔｉｐｌｅ ｋｅｒ⁃ ｎｅｌ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｂｉｇ ｄａｔａ ｓｔｒｅａｍ ａｎａｌｙｓｉｓ． Ｔｈｅ ａｌｇｏｒｉｔｈｍ ｌｅａｒｎｓ ａ ｋｅｒｎｅｌ ｆｕｎｃｔｉｏｎ ｔｈｒｏｕｇｈ ａｎ ｏｎｌｉｎｅ ｕｐｄａｔｅ ｐｒｏｃｅｄｕｒｅ ｂｙ ｒｅａｄｉｎｇ ｃｕｒｒｅｎｔ ｓｅｇｍｅｎｔｓ ｏｆ ａ ｂｉｇ ｄａｔａ ｓｔｒｅａｍ． Ｔｈｅ ａｌｇｏｒｉｔｈｍ ａｄｊｕｓｔｓ ｔｈｅ ｐａｒａｍｅｔｅｒｓ ｏｆ ｃｕｒｒｅｎｔｌｙ ｌｅａｒｎｅｄ ｋｅｒｎｅｌ ｆｕｎｃｔｉｏｎ ｉｎ ａ ｓｕｐｅｒｖｉｓｅｄ ｍａｎｎｅｒ ａｎｄ ｍｏｄｉｆｉｅｓ ｔｈｅ ｋｅｒｎｅｌ ｔｈｒｏｕｇｈ ｕｎｓｕｐｅｒｖｉｓｅｄ ｍａｎｉｆｏｌｄ ｌｅａｒｎｉｎｇ， ｓｏ ａｓ ｔｏ ｍａｋｅ ｔｈｅ ｃｏｎｔｏｕｒ ｓｕｒ⁃ ｆａｃｅｓ ｏｆ ｔｈｅ ｋｅｒｎｅｌ ａｌｏｎｇ ｗｉｔｈ ｓｏｍｅ ｌｏｗ ｄｉｍｅｎｓｉｏｎａｌｉｔｙ ｍａｎｉｆｏｌｄ ｉｎ ｔｈｅ ｄａｔａ ｓｐａｃｅ ａｓ ｆａｒ ａｓ ｐｏｓｓｉｂｌｅ． Ｔｈｅ ｎｏｖｅｌｔｙ ｉｓ ｔｈａｔ ｉｔ ｐｅｒｆｏｒｍｓ ｓｕｐｅｒｖｉｓｅｄ ａｎｄ ｕｎｓｕｐｅｒｖｉｓｅｄ ｌｅａｒｎｉｎｇ ａｔ ｔｈｅ ｓａｍｅ ｔｉｍｅ， ａｎｄ ｓｃａｎｓ ｔｈｅ ｔｒａｉｎｉｎｇ ｄａｔａ ｏｎｌｙ ｏｎｃｅ， ｗｈｉｃｈ ｒｅｄｕｃｅｓ ｔｈｅ ｃｏｍｐｕｔａｔｉｏｎａｌ ｃｏｍｐｌｅｘｉｔｙ ａｎｄ ｉｓ ｓｕｉｔａｂｌｅ ｆｏｒ ｔｈｅ ｋｅｒｎｅｌ ｌｅａｒｎｉｎｇ ｔａｓｋｓ ｉｎ ｂｉｇ ｄａｔａｓｅｔｓ ａｎｄ ｈｉｇｈ ｓｐｅｅｄ ｄａｔａ ｓｔｒｅａｍｓ． Ｔｈｉｓ ａｌｇｏｒｉｔｈｍ’ｓ ｓｕｐｐｏｒｔ ｔｏ ｔｈｅ ｕｎｓｕｐｅｒｖｉｓｅｄ ｌｅａｒｎｉｎｇ ｅｆｆｅｃｔｉｖｅｌｙ ｓｏｌｖｅｓ ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ｌａｂｅｌ ｍｉｓｓｉｎｇ ｉｎ ｂｉｇ ｄａｔａ ｓｔｒｅａｍｓ． Ｔｈｅ ｅｖａｌｕａｔｉｏｎ ｒｅｓｕｌｔｓ ｆｒｏｍ ｔｈｅ ｓｙｎｔｈｅｔｉｃ ｄａｔａｓｅｔｓ ｇｅｎｅｒａｔｅｄ ｂｙ ＭＯＡ ａｎｄ ｔｈｅ ｂｅｎｃｈｍａｒｋ ｄａｔａｓｅｔｓ ｏｆ ｔｈｅ ｂｉｇ ｄａｔａ ａｎａｌｙｓｉｓ ｆｒｏｍ ｔｈｅ ＵＣＩ ｄａｔａ ｒｅｐｏｓｉｔｏｒｙ ｓｈｏｗ ｔｈｅ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ． Ｋｅｙｗｏｒｄｓ：ｂｉｇ ｄａｔａ ｓｔｒｅａｍ； ｏｎｌｉｎｅ ｍｕｌｔｉ⁃ｋｅｒｎｅｌ ｌｅａｒｎｉｎｇ； ｍａｎｉｆｏｌｄ ｌｅａｒｎｉｎｇ； ｄａｔａ⁃ｄｅｐｅｎｄｅｎｔ ｋｅｒｎｅｌ； ｓｅｍｉ⁃ｓｕｐｅｒｖｉｓｅｄ ｌｅａｒｎｉｎｇ 收稿日期：２０１４⁃０３⁃２５． 网络出版日期：２０１４⁃０６⁃１４． 基金项目：国家自然科学基金资助项目（８１３７３８８３）． 通信作者：张钢． Ｅ⁃ｍａｉｌ：ｉｐｘ＠ ｇｄｕｔ．ｅｄｕ．ｃｎ． 随着信息技术的快速发展和大规模应用，数据 的生成速度及存储规模也在快速增长，特别是 Ｗｅｂ 页面、社交网络及物联网的普及和应用，使人们所要
·356· 智能系统学报 第9卷 存储、处理和分析的数据规模以指数方式递增。如 存，算法通过对当前输入的样本进行分析，同步更新 谷歌搜索引擎在2008年索引的网页个数突破1万 学习器，其中神经网络中的感知器模型就是在线学 亿个，沃尔玛最近构建的一个数据仓库的数据规模 习的经典例子6。由于在线学习不用保存以往的 达到4PB。在此背景下对大数据的分析和挖掘成 数据样本，或仅需保存以往数据样本的某种充分统 为当前的热点研究主题。从算法的层面来看，大 计量，十分适合大数据分析的应用场景。对于超大 数据的机器学习和分析挖掘问题，主要存在以下的 型数据集，以顺序方式输入模型，并同步更新学习 问题： 器：对高速数据流，在线学习可以实现数据的边输入 1)数据规模巨大，体现在数据记录个数及维度 边学习，使学习器模型能够反映出最近一段时间的 上，对于很多大数据分析问题，即使是多项式时间复 输入数据规律并进行有效预测。 杂度的机器学习算法也不能在人们可接受的时间内 本文研究大数据环境下的在线核学习(online 得到结果。 kernel learning)算法。与传统在线学习不同，本文 2)由于数据集比计算机内存大，导致无法在训 的工作主要针对大数据流中的核函数学习问题，算 练学习器时加载整个训练集，或是出于应用环境的 法并不直接通过数据样本的分析对学习器进行更 限制，在训练学习器时不能获取整个数据集，数据记 新，而是通过在线学习以迭代的方式确定一个最适 录可能按某种速率到来，而且数据产生的规律性会 用于当前数据产生规律的核函数。本文认为，核函 随着时间变化而有所改变。 数的学习比直接训练学习器有更广泛的适用性，一 要解决问题1)，主要从2个途径去考虑，其一 个合适的核函数可以被嵌入到各种不同核学习器的 是降低现有分析算法的时间复杂度，采取一些近似 训练过程，也可以直接用于核主成份分析(kernel 算法，在复杂度和精度方面取得折衷，如Yang等) PCA)、相关性分析(kernel CCA)或聚类分析等领 提出了一种决策树快速增量学习方法，通过对决策 域。因此，一个有效适用于大数据环境下的核学习 树的属性选择指标进行近似，使算法能适用于数据 算法有重要应用价值。 流和超大型数据集，其性能和普通版本的决策树相 目前被公开报道的在线核学习研究工作并不 比并没有明显的下降：Jordan[)对大数据统计推断 多，虽然核学习被广泛用于机器学习的不同应用领 进行了回顾，并针对大数据分而治之的算法提出了 域，但核函数的学习问题由于其对分析目标的间接 2种设计方法，其中重采样策略是对完整训练集的 性影响，在大数据分析和挖掘领域中并没有被充分 近似，而分治策略把大数据集数据间的相互关系限 研究，因此研究大数据环境下的核函数学习问题对 制在较小的范围内，最终目的是降低算法的复杂度： 其他大数据机器学习任务有重要的基础性意义。 其二是对现有算法进行修改，转化为可以并发/并行 本文提出一种适用于大数据流的在线核学习算 计算的版本，并利用云计算开发工具，如MapReduce 法，在现有多核学习框架中结合数据依赖核的构建 编写可以在云计算平台上运行的程序，通过计算云 方法，同时进行有监督学习和无监督学习，对于高速 的强大运算能力，使算法能在可接受的时间内解决 数据流中的有标记数据使用一种类似感知器训练的 大数据分析问题，如Acar等f)在MapReduce框架中 学习策略进行有监督核函数学习，对于所有数据 实现了自适应计算的数据流分析算法，通过维护一 (包括有标记和无标记数据)进行基于数据依赖核 个数据表跟踪数据集不同部分计算之间的依赖关 的核函数更新策略，实质上进行一种无监督学习，不 系，当需要更新时仅需考虑有关联的部分数据，算法 需要存储和重新扫描历史数据，仅需通过选择的方 有相对较佳的运行效率：Ai等)设计了面向数据 式维持一个样本工作集，在读取新的数据样本时能 流的相关分析和关联规则挖掘的云计算算法，能够 以较低的时间复杂度直接更新当前的核函数，适用 以批处理和在线的方式把相关分析和关联规则挖掘 于大数据环境下的核学习问题，特别是高速大数据 的任务透明分配到计算云的不同部分，同时计算然 流中标记缺失的情形。 后再进行整合。 1在线核学习的相关工作 对于问题2)，目前主要解决思路是设计出以往 机器学习和挖掘算法的在线学习版本。在线学习原 核函数学习问题是机器学习研究中的一个分支方 是机器学习的一个研究分支，其目标数据样本以顺 向，通过机器学习的方法学习一个针对特定应用背景 序的方式输入学习器，且不对历史数据样本进行保 的核函数，能够大幅提高训练学习器的效果。Gonen
存储、处理和分析的数据规模以指数方式递增。 如 谷歌搜索引擎在 ２００８ 年索引的网页个数突破 １ 万 亿个，沃尔玛最近构建的一个数据仓库的数据规模 达到 ４ ＰＢ。 在此背景下对大数据的分析和挖掘成 为当前的热点研究主题［１］ 。 从算法的层面来看，大 数据的机器学习和分析挖掘问题，主要存在以下的 问题： １）数据规模巨大，体现在数据记录个数及维度 上，对于很多大数据分析问题，即使是多项式时间复 杂度的机器学习算法也不能在人们可接受的时间内 得到结果。 ２）由于数据集比计算机内存大，导致无法在训 练学习器时加载整个训练集，或是出于应用环境的 限制，在训练学习器时不能获取整个数据集，数据记 录可能按某种速率到来，而且数据产生的规律性会 随着时间变化而有所改变。 要解决问题 １），主要从 ２ 个途径去考虑，其一 是降低现有分析算法的时间复杂度，采取一些近似 算法，在复杂度和精度方面取得折衷，如 Ｙａｎｇ 等［２］ 提出了一种决策树快速增量学习方法，通过对决策 树的属性选择指标进行近似，使算法能适用于数据 流和超大型数据集，其性能和普通版本的决策树相 比并没有明显的下降；Ｊｏｒｄａｎ ［３］ 对大数据统计推断 进行了回顾，并针对大数据分而治之的算法提出了 ２ 种设计方法，其中重采样策略是对完整训练集的 近似，而分治策略把大数据集数据间的相互关系限 制在较小的范围内，最终目的是降低算法的复杂度； 其二是对现有算法进行修改，转化为可以并发／ 并行 计算的版本，并利用云计算开发工具，如 ＭａｐＲｅｄｕｃｅ 编写可以在云计算平台上运行的程序，通过计算云 的强大运算能力，使算法能在可接受的时间内解决 大数据分析问题，如 Ａｃａｒ 等［４］在 ＭａｐＲｅｄｕｃｅ 框架中 实现了自适应计算的数据流分析算法，通过维护一 个数据表跟踪数据集不同部分计算之间的依赖关 系，当需要更新时仅需考虑有关联的部分数据，算法 有相对较佳的运行效率；Ａｒｉ 等［５］ 设计了面向数据 流的相关分析和关联规则挖掘的云计算算法，能够 以批处理和在线的方式把相关分析和关联规则挖掘 的任务透明分配到计算云的不同部分，同时计算然 后再进行整合。 对于问题 ２），目前主要解决思路是设计出以往 机器学习和挖掘算法的在线学习版本。 在线学习原 是机器学习的一个研究分支，其目标数据样本以顺 序的方式输入学习器，且不对历史数据样本进行保 存，算法通过对当前输入的样本进行分析，同步更新 学习器，其中神经网络中的感知器模型就是在线学 习的经典例子［６］ 。 由于在线学习不用保存以往的 数据样本，或仅需保存以往数据样本的某种充分统 计量，十分适合大数据分析的应用场景。 对于超大 型数据集，以顺序方式输入模型，并同步更新学习 器；对高速数据流，在线学习可以实现数据的边输入 边学习，使学习器模型能够反映出最近一段时间的 输入数据规律并进行有效预测。 本文研究大数据环境下的在线核学习（ ｏｎｌｉｎｅ ｋｅｒｎｅｌ ｌｅａｒｎｉｎｇ） 算法。 与传统在线学习不同，本文 的工作主要针对大数据流中的核函数学习问题，算 法并不直接通过数据样本的分析对学习器进行更 新，而是通过在线学习以迭代的方式确定一个最适 用于当前数据产生规律的核函数。 本文认为，核函 数的学习比直接训练学习器有更广泛的适用性，一 个合适的核函数可以被嵌入到各种不同核学习器的 训练过程，也可以直接用于核主成份分析（ ｋｅｒｎｅｌ ＰＣＡ）、相关性分析（ ｋｅｒｎｅｌ ＣＣＡ） 或聚类分析等领 域。 因此，一个有效适用于大数据环境下的核学习 算法有重要应用价值。 目前被公开报道的在线核学习研究工作并不 多，虽然核学习被广泛用于机器学习的不同应用领 域，但核函数的学习问题由于其对分析目标的间接 性影响，在大数据分析和挖掘领域中并没有被充分 研究，因此研究大数据环境下的核函数学习问题对 其他大数据机器学习任务有重要的基础性意义。 本文提出一种适用于大数据流的在线核学习算 法，在现有多核学习框架中结合数据依赖核的构建 方法，同时进行有监督学习和无监督学习，对于高速 数据流中的有标记数据使用一种类似感知器训练的 学习策略进行有监督核函数学习，对于所有数据 （包括有标记和无标记数据）进行基于数据依赖核 的核函数更新策略，实质上进行一种无监督学习，不 需要存储和重新扫描历史数据，仅需通过选择的方 式维持一个样本工作集，在读取新的数据样本时能 以较低的时间复杂度直接更新当前的核函数，适用 于大数据环境下的核学习问题，特别是高速大数据 流中标记缺失的情形。 １ 在线核学习的相关工作 核函数学习问题是机器学习研究中的一个分支方 向，通过机器学习的方法学习一个针对特定应用背景 的核函数，能够大幅提高训练学习器的效果。 Ｇöｎｅｎ ·３５６· 智 能 系 统 学 报 第 ９ 卷
第3期 张钢，等：面向大数据流的半监督在线多核学习算法 ·357. 等)回顾了目前的主要多核学习算法，指出大多数算 面向大数据的多核学习算法 法所得到核函数组合对学习器的影响差别不大，但是 在学习算法的时间复杂度及核函数组合的稀疏性方面 首先形式化描述多核学习问题，然后再给出带 却有很大差异，这种差异性在处理大数据的多核学习 有数据依赖的多核学习问题，并给出在线学习版本 问题时必须考虑。他们的工作表明通过非线性和数据 的算法。核学习所解决的问题是直接从训练数据集 依赖的方式进行核函数的组合具有更好的性能，数据 (有标记或无标记)中学习参数化或半参数化的核 依赖的核函数修正方式适合于高速无标记的数据流， 函数，使其能充分反映数据所蕴含的分布规律。给 这是本文在线核学习方法的一个出发点。Orabona 定一系列的训练样本D,={(x,y:)Ii=1,2,…, 等[劉提出了一种多核学习的快速算法，能够通过参数 n},其中x:为属性集，y:∈{-1，+1}为分类标记 控制所生成核的稀疏程度，算法即使在待组合的核数 给定一个包含m个基本核函数的集合K={k(·, 量很大的情况下仍然能够快速收敛，且模型训练的时 ·):X×X→R,j=1,2,…,m,学习一组非负权值 间复杂度仅是训练样本的线性函数。该工作大大减轻 u=山1，山2，…，山，∑4=1，使核学习器在测试 了核学习的算法复杂度，并能控制核的稀疏和与数据 集上的分类错误最小化。由于权值非负，根据核函 拟合的程度，有很重要的理论和应用价值。但该工作 数的性质可知，核函数的凸组合仍为一个有效的核 并不完全适用于大数据，特别是高速数据流，其原因是 函数。该问题可以形式化描述为 它并非一种增量更新算法，而是一种批处理的优化方 min::fIa+C∑fx,)) (1) 法。此外，该方法是一种有监督的核学习方法，并不能 式中：l为Hinge Loss损失函数，定义为l(a,b)= 处理无标记的数据样本，而在大数据流中数据样本的 max(0,1-ab),Hx为核函数K所张成的希尔伯特 标记缺失十分常见，因此核学习器的无监督学习能力 空间，C控制模型复杂度与损失惩罚比重的参数。 非常重要。 求解该优化问题的时间复杂度比较高，这是由于其 针对数据流学习和模型的增量更新问题，研究 中包含2步优化，第1步选择一个“，确定一个核函 者们对在线学习进行了深入研究，其中值得关注的 研究工作是Jim等)提出的在线核学习框架，他们 数K=∑uk,从而确定了H:第2步在H,中寻找 i=1 系统地提出了在线多核学习问题理论及其算法。针 最简单的且在当前训练集中正确率最高（由C控 对核函数和核学习器的增量更新问题，他们提出了 制)的学习器f,这2个目标分别对应式(1)中的2 使用确定和随机2种方法进行更新，其中随机更新 项。若核函数确定，则寻找满足2个条件的f的问 需要结合一定的采样策略进行。他们的工作对于基 题可以直接求解，如SVM模型则属于此种情况。但 本核函数较多的情况下是有效的，但仅在有监督学 若核函数是通过参数“来对若干基核函数进行加权 习中进行研究，即遇到一个新的样本，若当前模型分 组合，要求最优的“和f,则问题变得很有挑战性， 类正确，则不进行更新动作，否则按照一定的策略更 特别是在大数据学习环境中，此类问题基本上不可 新模型。该方法并不直接适用于大数据流环境下的 能在可接受的时间内求得最优解。 多核学习问题，其主要问题是它不能适应数据流产 若通过限制基本核函数的个数或“中各分量的 生规律变化的情况，且当某些数据缺少标签时模型 取值范围，则会牺牲多核学习的优势，且没有从根本 无法有效处理。 上解决多核学习的问题。可以认为，在没有更好的 本文认为要解决此问题需要同时考虑数据标签 求解算法的情况下，在线学习对上述问题是一种较 和数据的空间分布，使用增量学习的方法同步更新 好的求解策略。 模型，这也是在当前很多大数据学习算法中所采用 2.1在线多核学习 的策略。如Qim等[1o]提出了一种适用于云计算增 为了进行在线学习，需要重新考虑式(1)。Jin 量梯度下降算法，解决大数据环境下带线性约束的 等的工作表明，当所学习的核函数为某个基本核 凸优化问题。Yang等)提出了决策树的增量学习 函数集合的线性组合时，式(1)的最优化问题可以 近似算法，可以在没有历史训练数据的情况下通过 转化为如下问题：先求出每个核函数k:在各自张成 在线学习的方式直接更新决策树模型。但这些工作 的希尔伯特空间H,上最优的f,然后寻找一组权 均是直接针对学习器进行增量更新，其方法并不直 值“，使这些f的组合最优，在寻找最优的过程中同 接适用于本文的核函数学习问题。 步更新权值和∫。换句话说，若核函数的组合为线
等［７］回顾了目前的主要多核学习算法，指出大多数算 法所得到核函数组合对学习器的影响差别不大，但是 在学习算法的时间复杂度及核函数组合的稀疏性方面 却有很大差异，这种差异性在处理大数据的多核学习 问题时必须考虑。 他们的工作表明通过非线性和数据 依赖的方式进行核函数的组合具有更好的性能，数据 依赖的核函数修正方式适合于高速无标记的数据流， 这是本文在线核学习方法的一个出发点。 Ｏｒａｂｏｎａ 等［８］提出了一种多核学习的快速算法，能够通过参数 控制所生成核的稀疏程度，算法即使在待组合的核数 量很大的情况下仍然能够快速收敛，且模型训练的时 间复杂度仅是训练样本的线性函数。 该工作大大减轻 了核学习的算法复杂度，并能控制核的稀疏和与数据 拟合的程度，有很重要的理论和应用价值。 但该工作 并不完全适用于大数据，特别是高速数据流，其原因是 它并非一种增量更新算法，而是一种批处理的优化方 法。 此外，该方法是一种有监督的核学习方法，并不能 处理无标记的数据样本，而在大数据流中数据样本的 标记缺失十分常见，因此核学习器的无监督学习能力 非常重要。 针对数据流学习和模型的增量更新问题，研究 者们对在线学习进行了深入研究，其中值得关注的 研究工作是 Ｊｉｎ 等［９］ 提出的在线核学习框架，他们 系统地提出了在线多核学习问题理论及其算法。 针 对核函数和核学习器的增量更新问题，他们提出了 使用确定和随机 ２ 种方法进行更新，其中随机更新 需要结合一定的采样策略进行。 他们的工作对于基 本核函数较多的情况下是有效的，但仅在有监督学 习中进行研究，即遇到一个新的样本，若当前模型分 类正确，则不进行更新动作，否则按照一定的策略更 新模型。 该方法并不直接适用于大数据流环境下的 多核学习问题，其主要问题是它不能适应数据流产 生规律变化的情况，且当某些数据缺少标签时模型 无法有效处理。 本文认为要解决此问题需要同时考虑数据标签 和数据的空间分布，使用增量学习的方法同步更新 模型，这也是在当前很多大数据学习算法中所采用 的策略。 如 Ｑｉｎ 等［１０］ 提出了一种适用于云计算增 量梯度下降算法，解决大数据环境下带线性约束的 凸优化问题。 Ｙａｎｇ 等［２］ 提出了决策树的增量学习 近似算法，可以在没有历史训练数据的情况下通过 在线学习的方式直接更新决策树模型。 但这些工作 均是直接针对学习器进行增量更新，其方法并不直 接适用于本文的核函数学习问题。 ２ 面向大数据的多核学习算法 首先形式化描述多核学习问题，然后再给出带 有数据依赖的多核学习问题，并给出在线学习版本 的算法。 核学习所解决的问题是直接从训练数据集 （有标记或无标记）中学习参数化或半参数化的核 函数，使其能充分反映数据所蕴含的分布规律。 给 定一系列的训练样本 ＤＬ ＝ ｛（ｘｉ，ｙｉ） ｜ ｉ ＝ １，２，…， ｎ｝， 其中 ｘｉ 为属性集， ｙｉ ∈｛ － １， ＋ １｝ 为分类标记， 给定一个包含 ｍ 个基本核函数的集合 Ｋｍ ＝ ｛ｋｊ（·， ·）：Ｘ × Ｘ → Ｒ，ｊ ＝ １，２，…，ｍ｝ ，学习一组非负权值 ｕ ＝｛ｕ１ ，ｕ２ ，…，ｕｍ ，∑ｉ ｕｉ ＝ １｝ ，使核学习器在测试 集上的分类错误最小化。 由于权值非负，根据核函 数的性质可知，核函数的凸组合仍为一个有效的核 函数。 该问题可以形式化描述为 ｍｉｎｆ∈ＨＫ ‖ｆ‖２ ＨＫ ＋ Ｃ∑ ｎ ｉ ＝ １ ｌ（ｆ（ｘｉ），ｙｉ） （１） 式中： ｌ 为 Ｈｉｎｇｅ Ｌｏｓｓ 损失函数，定义为 ｌ（ａ，ｂ） ＝ ｍａｘ（０，１ － ａｂ） ， ＨＫ 为核函数 Ｋ 所张成的希尔伯特 空间， Ｃ 控制模型复杂度与损失惩罚比重的参数。 求解该优化问题的时间复杂度比较高，这是由于其 中包含 ２ 步优化，第 １ 步选择一个 ｕ ，确定一个核函 数 Ｋ ＝∑ ｍ ｉ ＝ １ ｕｉ ｋｉ ，从而确定了 ＨＫ ；第 ２ 步在 ＨＫ 中寻找 最简单的且在当前训练集中正确率最高（由 Ｃ 控 制）的学习器 ｆ ，这 ２ 个目标分别对应式（１）中的 ２ 项。 若核函数确定，则寻找满足 ２ 个条件的 ｆ 的问 题可以直接求解，如 ＳＶＭ 模型则属于此种情况。 但 若核函数是通过参数 ｕ 来对若干基核函数进行加权 组合，要求最优的 ｕ 和 ｆ ，则问题变得很有挑战性， 特别是在大数据学习环境中，此类问题基本上不可 能在可接受的时间内求得最优解。 若通过限制基本核函数的个数或 ｕ 中各分量的 取值范围，则会牺牲多核学习的优势，且没有从根本 上解决多核学习的问题。 可以认为，在没有更好的 求解算法的情况下，在线学习对上述问题是一种较 好的求解策略。 ２．１ 在线多核学习 为了进行在线学习，需要重新考虑式（１）。 Ｊｉｎ 等［９］的工作表明，当所学习的核函数为某个基本核 函数集合的线性组合时，式（１）的最优化问题可以 转化为如下问题：先求出每个核函数 ｋｉ 在各自张成 的希尔伯特空间 Ｈｋｉ 上最优的 ｆ ｉ ，然后寻找一组权 值 ｕ ，使这些 ｆ ｉ 的组合最优，在寻找最优的过程中同 步更新权值和 ｆ ｉ 。 换句话说，若核函数的组合为线 第 ３ 期 张钢，等：面向大数据流的半监督在线多核学习算法 ·３５７·
.358 智能系统学报 第9卷 性时，在线多核学习问题可以两步求解，先使用基础 有标记数据样本：(x,y) 的训练集为每一个核函数训练一个学习器，之后使 输出：更新后的权重u 用这些学习器进行在线学习，每读入一个训练样本 1)y·=sign(w·F(x) 时，根据当前的加权组合学习器对当前训练样本的 2)ify'=y then 输出结果，使用一种策略更新该核函数的权值和所 3)p=0 对应的单个学习器，则最优的核函数为各个核函数 4)else 使用该最优权值的加权组合体。即式(1)可以转化 5)9=1 为以下问题： 6)end if 7)fori=1,2,…,mdo min max uJieHK,ac[0,C]Ti= ：fs+ 8)p=p(min(e,-yf(x)+0.5)) ∑a,(1-y∑uf(x)） (2) 9)u:=u:B”/更新u 10)f:=f+pyk(x,·) 11)end for 图1描述了上述求解过程的主要步骤。 12)return u 基本训练集 算法1在输人有标记数据样本时，同时更新核权 学习器训练 m个学习器 权重u 重和每个核所对应的学习器。当样本被当前学习器分 核函数集K 初始化 类正确时，p为0，此时不执行更新动作：若分类错误， 读入样本 是否有标记 Y更新权重 则减少该学习器的权重，见算法1的第8)和第9)行。 输出 核函数 第lO)行根据Representer定理对每个核所对应的最优 学习器进行调整。最大错误容忍水平e控制以多大的 数据依赖更新组合学习器 力度去惩罚被学习器错分的样本。 由于仅对训练数据集进行一次扫描，算法1并 多核在线学习 不能达到离线批处理学习器的性能。但可依据感知 图1多核在线学习算法的主要框架 器训练过程对算法1的收敛性分析如下。算法第 Fig.1 The main framework of online multiple kernel 10)行对各个f进行更新，且各个f相互独立，相当 learning 于m个独立的感知器训练过程，当输入样本线性可 对式(2)进行分析可知，由于各个f之间没有 分时，各个f可以收敛于当前训练集下的最优学习 关联，因此f的最优值可以单独求出，再用类似感知 器，进而确定其最优组合：当输入样本线性不可分 器的权值更新算法求解最优的组合权值u。由Re- 时，其收敛性依赖于各个学习器的核函数，一般情况 presenter定理可知，使式(2)最优的f方必定满足 下并不收敛于最优解，但实验部分的第4组实验说 f)=(,) 明经过一段时间后学习器的性能会趋于稳定，逼近 (3) i=1 一个可接受的较优解。 式(3)给出了一种在线学习f的方法，当读入一个 2.2基于数据依赖的核函数修改 训练样本时，先判断f能否给出正确的标签，然后采 数据依赖核[]是一种无监督的核函数学习方 用f=f+yk,(x,·)更新，其中p为指示函数，当 法，实质是对核函数在训练样本集上的值进行修改， 对x正确分类时其值为1，反之为0。Jin等在文献 使其所反映的在可见数据样本上的距离更加符合数 [9]中实现了上述思想。算法1描述了整个过程。 据样本点的空间分布，而不考虑样本标签。它可以 算法1在线多核学习 对任意现有核函数根据可见的数据样本进行修改， 输入 实质是对由核函数所诱导的希尔伯特空间的内积进 核函数集合：Kn={k1,k2,…,km} 行修改。首先给出数据依赖核的主要结论，然后 初始化学习器：F={fif,…fm} 再提出针对大数据和高速数据流的数据依赖核在线 更新因子：B∈(0,1) 核学习算法。 最大分类错误的容忍水平：e 给定一个核函数k和一个数据集D={x1,x2, 当前的权重向量：u ,xn},记k=(k(x:,x),…,k(,xn)）,M=
性时，在线多核学习问题可以两步求解，先使用基础 的训练集为每一个核函数训练一个学习器，之后使 用这些学习器进行在线学习，每读入一个训练样本 时，根据当前的加权组合学习器对当前训练样本的 输出结果，使用一种策略更新该核函数的权值和所 对应的单个学习器，则最优的核函数为各个核函数 使用该最优权值的加权组合体。 即式（１）可以转化 为以下问题： ｍｉｎ ｕ，ｆ ｉ∈ＨＫ ｉ ｍａｘ α∈［０，Ｃ］ Ｔ∑ ｍ ｉ ＝ １ ｕｉ ‖ｆｉ‖２ ＨＫ ｉ ＋ ∑ Ｔ ｔ ＝ １ αｉ（１ － ｙｔ∑ ｍ ｉ ＝ １ ｕｉ ｆ ｉ（ｘｔ）） （２） 图 １ 描述了上述求解过程的主要步骤。 图 １ 多核在线学习算法的主要框架 Ｆｉｇ．１ Ｔｈｅ ｍａｉｎ ｆｒａｍｅｗｏｒｋ ｏｆ ｏｎｌｉｎｅ ｍｕｌｔｉｐｌｅ ｋｅｒｎｅｌ ｌｅａｒｎｉｎｇ 对式（２）进行分析可知，由于各个 ｆ ｉ 之间没有 关联，因此 ｆ ｉ 的最优值可以单独求出，再用类似感知 器的权值更新算法求解最优的组合权值 ｕ 。 由 Ｒｅ⁃ ｐｒｅｓｅｎｔｅｒ 定理可知，使式（２）最优的 ｆ ｉ 必定满足 ｆ ｉ（·） ＝ ∑ ｎ ｊ ＝ １ αｊ ｙｊ ｋｉ（ｘｊ，·） （３） 式（３）给出了一种在线学习 ｆ ｉ 的方法，当读入一个 训练样本时，先判断 ｆ ｉ 能否给出正确的标签，然后采 用 ｆ ｉ ＝ ｆ ｉ ＋ φｙｘ ｋｉ（ｘ，·） 更新，其中 φ 为指示函数，当 ｆ ｉ 对 ｘ 正确分类时其值为 １，反之为 ０。 Ｊｉｎ 等在文献 ［９］中实现了上述思想。 算法 １ 描述了整个过程。 算法 １ 在线多核学习 输入： 核函数集合： Ｋｍ ＝ ｛ｋ１ ，ｋ２ ，…，ｋｍ ｝ 初始化学习器： Ｆ ＝ ｛ｆ １ ，ｆ ２ ，…，ｆｍ ｝ 更新因子： β ∈ （０，１） 最大分类错误的容忍水平： ｅ 当前的权重向量： ｕ 有标记数据样本： （ｘ，ｙ） 输出：更新后的权重 ｕ １） ｙ ∗ ＝ ｓｉｇｎ（ｗ Ｔ·Ｆ（ｘ）） ２）ｉｆ ｙ ∗ ＝ ｙ ｔｈｅｎ ３） φ ＝ ０ ４）ｅｌｓｅ ５） φ ＝ １ ６）ｅｎｄ ｉｆ ７）ｆｏｒ ｉ ＝ １，２，…，ｍ ｄｏ ８） ｐ ＝ φ（ｍｉｎ（ｅ， － ｙｆ Ｔ ｉ （ｘ） ＋ ０．５）） ９） ｕｉ ＝ ｕｉβ ｐ ／ ／ 更新 ｕ １０） ｆｉ ＝ ｆｉ ＋ φｙｋｉ（ｘ，·） １１）ｅｎｄ ｆｏｒ １２）ｒｅｔｕｒｎ ｕ 算法 １ 在输入有标记数据样本时，同时更新核权 重和每个核所对应的学习器。 当样本被当前学习器分 类正确时， φ 为 ０，此时不执行更新动作；若分类错误， 则减少该学习器的权重，见算法 １ 的第 ８）和第 ９）行。 第 １０）行根据 Ｒｅｐｒｅｓｅｎｔｅｒ 定理对每个核所对应的最优 学习器进行调整。 最大错误容忍水平 ｅ 控制以多大的 力度去惩罚被学习器错分的样本。 由于仅对训练数据集进行一次扫描，算法 １ 并 不能达到离线批处理学习器的性能。 但可依据感知 器训练过程对算法 １ 的收敛性分析如下。 算法第 １０）行对各个 ｆ ｉ 进行更新，且各个 ｆ ｉ 相互独立，相当 于 ｍ 个独立的感知器训练过程，当输入样本线性可 分时，各个 ｆ ｉ 可以收敛于当前训练集下的最优学习 器，进而确定其最优组合；当输入样本线性不可分 时，其收敛性依赖于各个学习器的核函数，一般情况 下并不收敛于最优解，但实验部分的第 ４ 组实验说 明经过一段时间后学习器的性能会趋于稳定，逼近 一个可接受的较优解。 ２．２ 基于数据依赖的核函数修改 数据依赖核［１１］ 是一种无监督的核函数学习方 法，实质是对核函数在训练样本集上的值进行修改， 使其所反映的在可见数据样本上的距离更加符合数 据样本点的空间分布，而不考虑样本标签。 它可以 对任意现有核函数根据可见的数据样本进行修改， 实质是对由核函数所诱导的希尔伯特空间的内积进 行修改［１２］ 。 首先给出数据依赖核的主要结论，然后 再提出针对大数据和高速数据流的数据依赖核在线 核学习算法。 给定一个核函数 ｋ 和一个数据集 Ｄ ＝ ｛ｘ１ ，ｘ２ ， …， ｘｎ ｝ ， 记 ｋｘｉ ＝ （ｋ（ｘｉ，ｘ１ ），…，ｋ（ｘｉ，ｘｎ ）） ， Ｍ ＝ ·３５８· 智 能 系 统 学 报 第 ９ 卷
第3期 张钢，等：面向大数据流的半监督在线多核学习算法 ·359· (∑，W,-W)',k关于D的Gam矩阵记为kn, 算M和k。的时间复杂度为O(N2)。 W,=RBF(x,x),x:,x∈D。则可以通过式(4)的 一个重要问题是LRU和FIFO中对输入样本的 方式对核函数k进行修改，使其等距线沿D进行分 时间属性记录，对LRU还有聚类意义下最近被使用 布： 样本的判断。本文首先用聚类的方式产生数据集D kp(a,b)=k(a,b)-ki (I+MKp)Mk (4) 的r个簇，应用在线聚类的方式更新这r个簇，替换 其中a和b为任意2个训练样本，M是一个在原点 样本时每次从最久没有被更新过的簇中随机选取一 对称的距离矩阵，按文献[12]的方法用图拉普拉斯 个样本进行替换，使用一个长度为r优先队列记录 矩阵计算得到。整个过程中并没有考虑数据的标 每个簇最近被访问的情况。对于FIFO策略，不需 签，仅是通过考虑数据的密度分布，对原有核函数的 要优先队列，每次把新加入的样本放在最下行和最 值进行修改。 右列，然后去掉第1行第1列即可。算法2和算法3 式(4)的计算需要离线批量进行，且计算的时 分别描述了静态大数据集和流数据集2种情况下的 间复杂度较高，具体而言，式(4)在修改数据样本α 数据依赖核的在线学习过程。 和b的核函数值时要计算k。和k。,即a和b与当前 算法2使用一个优先队列记录样本簇最近被访 可见数据集的核函数k值。当可见数据不变时，M 问的情况，认为一个簇中的样本被访问过一次，则该 和k。这两项只需计算一次，但对数据流而言，M和 簇最近被访问过，核矩阵的更新从第7至10行，需 k。是在不断变化的。但可以肯定的一点是，对于大 要对所有样本扫描一次，时间复杂度是0(W2),优 规模数据集和数据流，直接计算整个数据集的M和 先队列的操作需要O(),其中r为簇的个数，判断 k。在计算资源上并不现实。 x。属于哪个簇的粗糙算法需要O()时间，整体的 因此考虑M和k。的在线更新策略，采用限制 时间复杂度为0(N2)。 M和k。的规模为N×N,则必须有D中的数据样本 算法2大数据集的数据依赖核在线学习 替换策略。借鉴操作系统中内存页面的调度算法， 输入： 对静态的大数据集应用类似近期最少使用(least re- 数据样本集：D={x1,x2,…,xx} cently used,LRU)的样本更新策略)，而对于高速 当前输入样本：x。 数据流应用先进先出(first in first out,FIFO)更新策 核函数Gram矩阵和距离矩阵：K、M 略[3]，其中LRU是替换最近一段时间没有被使用 样本空间聚类分布：Lc 过的样本，由于样本各不相同，本文采用聚类意义下 记录簇最近访问的优先队列：Q 的样本使用统计。这两种策略的合理性基于以下分 输出：更新后的核矩阵：K 析。对于静态大数据集，虽然数据是顺序地输入到 1)r=clus(Lc,xo）/查找样本xo的簇号 学习器中，但其数据到达顺序和时序不相关，因此不 2)根据r更新优先队列Q 能使用与时间密切相关的FIFO策略，而采用LRU 3)把x。加到簇r中 策略较为合理：对于数据流，其数据生成规律有可能 4)在优先队列Q的队尾所示的簇中随机去掉 随时间变化而变化，因此替换存在时间最长样本的 一个样本 FIFO策略是合理的。同时，数据依赖核是通过对数 5)初始化k。 据的分布估计对核函数进行修改，计算这种分布需 6)令k1=(k(x0,x1),…,k(x0,xx)) 要对一定规模的数据点进行分析，因此维持一个工 7)forj=1,…,Ndo 作集M是必须的，它可被看作一个缓存，反映近一 8)k2=K(G,·) 段时间的数据分布规律。这种限制工作集大小的更 9)kko=k:-kI (I+MK)-Mk, 新策略有一定的局部性，但在有限的计算和存储资 10)end for 源下是折衷的策略。 11)用k,更新矩阵K中关于x的一行和一列 算法维持一个不考虑标签的样本集D并进行 12)return K 在线更新。k。和k6的计算步聚是先查表k。,若不命 算法3流数据集的数据依赖核在线学习 中再计算，时间复杂度为O(N)。对于M和k。,替 输入： 换样本之后需要重新计算一行，然后更新一行和一 数据样本集D={x1,xw 列，因此其时间复杂度也为O(N)。算法初始时计 当前输入样本：xo
（∑ｉ Ｗｉｊ － Ｗ） ｐ ， ｋ 关于 Ｄ 的 Ｇｒａｍ 矩阵记为 ｋＤ ， Ｗｉｊ ＝ ＲＢＦ（ｘｉ，ｘｊ） ， ｘｉ，ｘｊ ∈ Ｄ 。 则可以通过式（４）的 方式对核函数 ｋ 进行修改，使其等距线沿 Ｄ 进行分 布： ｋＤ（ａ，ｂ） ＝ ｋ（ａ，ｂ） － ｋ Ｔ ａ （Ｉ ＋ ＭＫＤ） －１Ｍｋｂ （４） 其中 ａ 和 ｂ 为任意 ２ 个训练样本， Μ 是一个在原点 对称的距离矩阵，按文献［１２］的方法用图拉普拉斯 矩阵计算得到。 整个过程中并没有考虑数据的标 签，仅是通过考虑数据的密度分布，对原有核函数的 值进行修改。 式（４）的计算需要离线批量进行，且计算的时 间复杂度较高，具体而言，式（４）在修改数据样本 ａ 和 ｂ 的核函数值时要计算 ｋａ 和 ｋｂ ，即 ａ 和 ｂ 与当前 可见数据集的核函数 ｋ 值。 当可见数据不变时， Ｍ 和 ｋＤ 这两项只需计算一次，但对数据流而言， Ｍ 和 ｋＤ 是在不断变化的。 但可以肯定的一点是，对于大 规模数据集和数据流，直接计算整个数据集的 Ｍ 和 ｋＤ 在计算资源上并不现实。 因此考虑 Ｍ 和 ｋＤ 的在线更新策略，采用限制 Ｍ 和 ｋＤ 的规模为 Ｎ × Ｎ ，则必须有 Ｄ 中的数据样本 替换策略。 借鉴操作系统中内存页面的调度算法， 对静态的大数据集应用类似近期最少使用（ｌｅａｓｔ ｒｅ⁃ ｃｅｎｔｌｙ ｕｓｅｄ， ＬＲＵ）的样本更新策略［１３］ ，而对于高速 数据流应用先进先出（ｆｉｒｓｔ ｉｎ ｆｉｒｓｔ ｏｕｔ， ＦＩＦＯ）更新策 略［１３］ ，其中 ＬＲＵ 是替换最近一段时间没有被使用 过的样本，由于样本各不相同，本文采用聚类意义下 的样本使用统计。 这两种策略的合理性基于以下分 析。 对于静态大数据集，虽然数据是顺序地输入到 学习器中，但其数据到达顺序和时序不相关，因此不 能使用与时间密切相关的 ＦＩＦＯ 策略，而采用 ＬＲＵ 策略较为合理；对于数据流，其数据生成规律有可能 随时间变化而变化，因此替换存在时间最长样本的 ＦＩＦＯ 策略是合理的。 同时，数据依赖核是通过对数 据的分布估计对核函数进行修改，计算这种分布需 要对一定规模的数据点进行分析，因此维持一个工 作集 Ｍ 是必须的，它可被看作一个缓存，反映近一 段时间的数据分布规律。 这种限制工作集大小的更 新策略有一定的局部性，但在有限的计算和存储资 源下是折衷的策略。 算法维持一个不考虑标签的样本集 Ｄ 并进行 在线更新。 ｋａ 和 ｋｂ 的计算步聚是先查表 ｋＤ ，若不命 中再计算，时间复杂度为 Ｏ（Ｎ） 。 对于 Ｍ 和 ｋＤ ，替 换样本之后需要重新计算一行，然后更新一行和一 列，因此其时间复杂度也为 Ｏ（Ｎ） 。 算法初始时计 算 Ｍ 和 ｋＤ 的时间复杂度为 Ｏ（Ｎ ２ ） 。 一个重要问题是 ＬＲＵ 和 ＦＩＦＯ 中对输入样本的 时间属性记录，对 ＬＲＵ 还有聚类意义下最近被使用 样本的判断。 本文首先用聚类的方式产生数据集 Ｄ 的 ｒ 个簇，应用在线聚类的方式更新这 ｒ 个簇，替换 样本时每次从最久没有被更新过的簇中随机选取一 个样本进行替换，使用一个长度为 ｒ 优先队列记录 每个簇最近被访问的情况。 对于 ＦＩＦＯ 策略，不需 要优先队列，每次把新加入的样本放在最下行和最 右列，然后去掉第 １ 行第 １ 列即可。 算法 ２ 和算法 ３ 分别描述了静态大数据集和流数据集 ２ 种情况下的 数据依赖核的在线学习过程。 算法 ２ 使用一个优先队列记录样本簇最近被访 问的情况，认为一个簇中的样本被访问过一次，则该 簇最近被访问过，核矩阵的更新从第 ７ 至 １０ 行，需 要对所有样本扫描一次，时间复杂度是 Ｏ（Ｎ ２ ） ，优 先队列的操作需要 Ｏ（ｒ） ，其中 ｒ 为簇的个数，判断 ｘ０ 属于哪个簇的粗糙算法需要 Ｏ（ｒ） 时间，整体的 时间复杂度为 Ｏ（Ｎ ２ ） 。 算法 ２ 大数据集的数据依赖核在线学习 输入： 数据样本集： Ｄ ＝ ｛ｘ１ ，ｘ２ ，…，ｘＮ｝ 当前输入样本： ｘ０ 核函数 Ｇｒａｍ 矩阵和距离矩阵： Ｋ、Μ 样本空间聚类分布： ＬＣ 记录簇最近访问的优先队列： Ｑ 输出： 更新后的核矩阵： Ｋ １） ｒ ＝ ｃｌｕｓ（ＬＣ ，ｘ０ ） ／ ／ 查找样本 ｘ０ 的簇号 ２） 根据 ｒ 更新优先队列 Ｑ ３） 把 ｘ０ 加到簇 ｒ 中 ４） 在优先队列 Ｑ 的队尾所示的簇中随机去掉 一个样本 ５） 初始化 ｋｘ０ ６） 令 ｋ１ ＝ （ｋ（ｘ０ ，ｘ１ ），…，ｋ（ｘ０ ，ｘＮ）） ７） ｆｏｒ ｊ ＝ １，…，Ｎ ｄｏ ８） ｋ２ ＝ Ｋ（ｊ，·） ９） ｋｋ０ ＝ ｋ１ － ｋ Ｔ １ （Ｉ ＋ ΜＫ） －１Μｋ２ １０）ｅｎｄ ｆｏｒ １１） 用 ｋｘ０ 更新矩阵 Ｋ 中关于 ｘ０ 的一行和一列 １２） ｒｅｔｕｒｎ Ｋ 算法 ３ 流数据集的数据依赖核在线学习 输入： 数据样本集 Ｄ ＝ ｛ｘ１ ，…ｘＮ｝ 当前输入样本： ｘ０ 第 ３ 期 张钢，等：面向大数据流的半监督在线多核学习算法 ·３５９·
·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给出了对比算法的基本信息
核函数 Ｇｒａｍ 矩阵和距离矩阵： Ｋ、 Μ 输出：更新后的核矩阵 Ｋ １）初始化 ｋｘ０ ２） ｋ１ ＝ （ｋ（ｘ０ ，ｘ１ ），…，ｋ（ｘ０ ，ｘＮ）） ３）ｆｏｒ ｊ ＝ １，…，Ｎ ｄｏ ４） ｋ２ ＝ Ｋ（ｊ，·） ５） ｋｘ０ ＝ ｋ１ － ｋ Ｔ １ （Ｉ ＋ ＭＫ） －１Ｍｋ２ ６）ｅｎｄ ｆｏｒ ７）用 ｋｘ０ 更新矩阵 Ｋ 中的最后一行和最后一列 ８）ｒｅｔｕｒｎ Ｋ 对于数据流在线核学习问题，采用 ＦＩＦＯ 策略， 即每次把当前的数据样本替换时间最长的数据样 本，因此算法 ３ 中不需要优先队列。 算法 ４ 半监督在线多核学习 ＳＳＬ⁃ＭＫＬ 输入： 初始训练数据集 Ｄ０ 输入数据样本集， Ｄ ＝ ｛ｘｉ，ｙｉ｝ ， ｘｉ 是样本， ｙｉ 是其标签 输出：更新后的核矩阵 Ｋ １）初始化 Ｋ ２）使用批处理算法由 Ｄ０ 学习 Ｋ ３）ｆｏｒ ｅａｃｈ （ｘｉ，ｙｉ） ｉｎ Ｄ ４）ｉｆ Ｌｉ ｉｓ ｎｏｔ ＮＵＬＬ ｔｈｅｎ ５）Ｃａｌｌ 算法 １（ｘｉ，ｙｉ） ６）更新 Ｋ ７）ｅｎｄ ｉｆ ８）ｉｆ 静态大数据集 ｔｈｅｎ ９）Ｃａｌｌ 算法 ２（Ｋ，Ｄ０ ，Ｍ，ｘｉ，ＬＣ ，Ｑ） １０）ｅｌｓｅ ｉｆ 数据流 ｔｈｅｎ １１）Ｃａｌｌ 算法 ３（Ｋ，Ｄ０ ，Ｍ，ｘｉ） １２）ｅｎｄ ｉｆ １３）更新 Ｋ １４）ｅｎｄ ｆｏｒ １５）ｒｅｔｕｒｎ Ｋ 为了把在线多核学习和数据依赖进行结合，算 法每读入一个数据样本 ｘ ，判断是否有标签，若有标 签，则先执行多核学习的权重值更新，再执行基于数 据依赖的核修改；若没有标签，则仅执行核修改（算 法 ２ 和算法 ３）。 核修改是针对加权之后的核函数 进行。 算法 ４ 描述了 ２ 部分核学习的结合过程。 ３ 实验结果及分析 在人工数据集和大数据学习的基准数据集上对 本文算法进行有效性评估，并与现有的算法进行比 较。 人工数据集使用 ＭＯＡ ［１４］ 的序列生成器自动生 成，在实验中共生成了 ３ 个规模不同的人工数据集， 由 ＭＯＡ 所生成的人工数据集被广泛用于大数据算 法有效性的评估工作中［１５ ⁃ １６］ 。 基准数据集采用 ＵＣＩ 数据集［１９］中的数据集。 实验中选取 ＭＯＡ 提供 的其中 ３ 个生成器生成不同的人工数据集，蕴含不 同的数据生成规律。 表 １ 和 ２ 分别展示了人工数据 集和 ＵＣＩ 基准数据集的主要信息。 ＭＯＡ 序列生成 器生成的 ３ 个人工数据集，以数据记录生成时间顺 序保存在 ３ 个单独的数据文件中，在线多核学习时 顺序读取文件中的数据进行训练和测试。 ２ 个 ＵＣＩ 数据集中的数据随机重排之后按顺序读入。 其中数 据集 Ｍ１ 生成 ２０ 份，规模从 １０ ６ ～ ２ × １０ ７ ，用于评估 数据集规模与 ＣＰＵ 处理时间的增长关系。 表 １ ＭＯＡ 实验数据集的主要信息 Ｔａｂｌｅ １ Ｄｅｔａｉｌｓ ｏｆ ＭＯＡ ｄａｔａ ｓｅｔｓ 编号 生成器类型 大小 属性个数 Ｍ１ ＷａｖｅＦｏｒｍ １０ ６ ～ ２×１０ ７ ２１ Ｍ２ ＲａｎｄｏｍＲＢＦ １０ ６ ３７ Ｍ３ ＳＥＡ Ｃｏｎｃｅｐｔｓ １０ ６ ２５ 表 ２ ＵＣＩ 实验数据集的主要信息 Ｔａｂｌｅ ２ Ｄｅｔａｉｌｓ ｏｆ ＵＣＩ ｄａｔａ ｓｅｔｓ 编号 数据集描述 大小 属性个数 Ｍ４ Ｆｏｒｅｓｔ ＣｏｖｅｒＴｙｐｅ ５８１０１２ ５４ Ｍ５ Ｐｏｋｅｒ⁃Ｈａｎｄ １０ ７ １１ 在上述 ５ 个数据集上进行 ３ 组实验。 第 １ 组实 验评估本文的半监督在线多核学习算法（ ｓｅｍｉ⁃ｓｕ⁃ ｐｅｒｖｉｓｅｄ ｌｅａｒｎｉｎｇ ⁃ ｍｕｌｔｉｐｌｅ ｋｅｒｎｅｌ ｌｅａｒｎｉｎｇ， ＳＳＬ⁃ ＭＫＬ）的有效性，并与文献［１７］中的批处理多核学 习算法及文献［９］、［１８］中的有监督在线多核学习 算法进行比较。 第 ２ 组实验分析本文算法对不同规 模数据集处理的 ＣＰＵ 运算时间增长与数据集大小 之间的关系。 第 ３ 组实验评估本文算法的迭代次数 与学习器性能的变化关系，从而说明其收敛性能。 在 ３ 组实验中均采用参数随机的 ＲＢＦ 核、多项 式核和三角函数核函数各 １００ 个，即 ｍ ＝ ３００。 第 １ 组实验采用如下设置：对比的一般核函数采用参数 随机的 ＲＢＦ 核和多项式核，核学习器使用标准的 ＳＶＭ，只进行二类分类，并采用 ０－１ 损失函数评估 分类错误率。 其中数据集 Ｍ１ 的规模为 １０ ６ 。 在 Μ 和 ｋＤ 的更新算法中，限制其规模 Ｎ 为 １０００ 个样本。 第 １ 组实验评估 ＳＳＬ⁃ＭＫＬ 算法有效性并与有 监督的在线核学习算法进行比较，同时引入一个非 在线学习的多核学习算法作为算法有效性的基线。 表 ３ 给出了对比算法的基本信息。 ·３６０· 智 能 系 统 学 报 第 ９ 卷
第3期 张钢，等：面向大数据流的半监督在线多核学习算法 ·361. 表3实验对比算法的基本信息 训练数据。因此可以接受在线学习方法性能稍差于 Table 3 Details of evaluation methods for comparison 批处理方法。但批处理方法难以处理大规模的数据 编号 参考文献 数据集 描述 集，正如本组实验的第2部分即将展示的（图3），这 采用感知器与Hedge算 正是在线学习方法的优势[02]。下面给出F1、2 法融合的在线核学习算 与SSL-MKL在M4和M5整个数据集上的结果。训 [17] 全部 法，优化过程采用随机 练集与测试集的规模按原数据集大小的3：7，对于 梯度下降法 SSL-MKL采用转导学习的方式[22】，即把整个测试 在线多核学习算法，其 集作为无标记集。同样对数据集进行10次随机划 F2 [9] 全部 基本原理同算法1，但 分，记录每次分类正确率并计算方差，图3给出了在 权重更新策略不同 数据集M4和M5上算法正确率的比较结果。 3 [18] M4、M5 批处理多核学习算法 0.8i F1与F2可以在5个实验数据集上运行，F3不 0.6 能运行在数据流集上，即只能在M4和M5上运行， F 因此可以把M1、M2、M3与M4、M5分别进行比较。 SSL-MKL 由于算法F3无法直接处理M4和M5这样大规 0.2 模的数据集，只能采用随机抽样的方法，限制训练集 的大小才可以使用批处理算法。本组实验对训练数 M M 据集进行无回放抽样，抽样规模为10000。其余2 数据集 个算法也在此抽样数据集上进行性能测试，对本文 图3M4和M5的实验结果（完整数据集） 的SSL-MKL算法，从测试数据集中抽取同样规模的 Fig.3 Evaluation results of M4 and M5(full data set size) 数据集作为算法的无标记数据。考虑到抽样的随机 从图3中可看出，由于有完整的训练集，各个算 性，对批处理核学习进行10次抽样训练并记录10 法的正确率相比图2有所提升。SSL-MKL算法相 次的分类正确率的平均值。图2展示了在M4和 比F1和F2的提升幅度比限制规模数据集时更大， M5上的实验结果。 表明数据依赖核对于数据分布的估计能够提升核函 0.8f 数的性能。 最后给出数据流集(M1、M2、M3)的测试结果。 0.6 F 测试过程是把训练样本按其顺序号依次输入学习模 解 ■F2 0.4 ■F 型进行训练：在接受测试样本时，SSL-MKL同时进 ■SSL-MKL 行无监督学习，而1和F2,则仅输出测试结果。由 0.2 于数据集有顺序，截取前面的30%作为训练集，后 面70%作为测试集。表4给出了实验中各算法在数 M M 数据集 据集上正确率的比较。 图2M4和M5的实验结果（限制数据集规模） 表4各算法在流数据集上正确率的比较 Fig.2 The main framework of online multiple kernel Table 4 Accuracy comparison on stream data sets learning M1 M2 M3 从图2中可以看到，SSL-MKL不比F3差太多， F1 0.731 0.788 0.775 但比F1和F2好，表明SSL-MKL对于规模受限制的 F2 0.742 0.781 0.770 数据集的性能较有监督的在线核学习算法(F1和 SSL-MKL 0.768 0.796 0.802 F2)好，归功于SSL-MKL算法中的无监督学习对最 终学习器性能提升的贡献，说明整个半监督学习框 从表4中可知SSL-MKL算法在3个数据集上 架的有效性。另一方面，注意到3个在线算法的性 都有最好的表现。第2组实验分析本文算法对不同 能均不如批处理算法F3,这是可以理解的，因为在 规模数据集处理的CPU运算时间增长与数据集大 线学习算法每次仅能“看到”当前的训练样本，且基 小之间的关系。为了精确控制实验数据集的规模， 本上不存储(SSL-MKL算法中的工作集仅是有限度 本组实验使用了20种规模依次等距递增的M1数 存储)，批处理方法在整个训练期间能访问所有的 据集（以10为递增单位），记录了F2和SSL-MKL
表 ３ 实验对比算法的基本信息 Ｔａｂｌｅ ３ Ｄｅｔａｉｌｓ ｏｆ ｅｖａｌｕａｔｉｏｎ ｍｅｔｈｏｄｓ ｆｏｒ ｃｏｍｐａｒｉｓｏｎ 编号 参考文献 数据集 描述 Ｆ１ ［１７］ 全部 采用感知器与 Ｈｅｄｇｅ 算 法融合的在线核学习算 法，优化过程采用随机 梯度下降法 Ｆ２ ［９］ 全部 在线多核学习算法，其 基本原理同算法 １，但 权重更新策略不同 Ｆ３ ［１８］ Ｍ４、Ｍ５ 批处理多核学习算法 Ｆ１ 与 Ｆ２ 可以在 ５ 个实验数据集上运行，Ｆ３ 不 能运行在数据流集上，即只能在 Ｍ４ 和 Ｍ５ 上运行， 因此可以把 Ｍ１、Ｍ２、Ｍ３ 与 Ｍ４、Ｍ５ 分别进行比较。 由于算法 Ｆ３ 无法直接处理 Ｍ４ 和 Ｍ５ 这样大规 模的数据集，只能采用随机抽样的方法，限制训练集 的大小才可以使用批处理算法。 本组实验对训练数 据集进行无回放抽样，抽样规模为 １００００。 其余 ２ 个算法也在此抽样数据集上进行性能测试，对本文 的 ＳＳＬ⁃ＭＫＬ 算法，从测试数据集中抽取同样规模的 数据集作为算法的无标记数据。 考虑到抽样的随机 性，对批处理核学习进行 １０ 次抽样训练并记录 １０ 次的分类正确率的平均值。 图 ２ 展示了在 Ｍ４ 和 Ｍ５ 上的实验结果。 图 ２ Ｍ４ 和 Ｍ５ 的实验结果（限制数据集规模） Ｆｉｇ．２ Ｔｈｅ ｍａｉｎ ｆｒａｍｅｗｏｒｋ ｏｆ ｏｎｌｉｎｅ ｍｕｌｔｉｐｌｅ ｋｅｒｎｅｌ ｌｅａｒｎｉｎｇ 从图 ２ 中可以看到，ＳＳＬ⁃ＭＫＬ 不比 Ｆ３ 差太多， 但比 Ｆ１ 和 Ｆ２ 好，表明 ＳＳＬ⁃ＭＫＬ 对于规模受限制的 数据集的性能较有监督的在线核学习算法（ Ｆ１ 和 Ｆ２）好，归功于 ＳＳＬ⁃ＭＫＬ 算法中的无监督学习对最 终学习器性能提升的贡献，说明整个半监督学习框 架的有效性。 另一方面，注意到 ３ 个在线算法的性 能均不如批处理算法 Ｆ３，这是可以理解的，因为在 线学习算法每次仅能“看到”当前的训练样本，且基 本上不存储（ＳＳＬ⁃ＭＫＬ 算法中的工作集仅是有限度 存储），批处理方法在整个训练期间能访问所有的 训练数据。 因此可以接受在线学习方法性能稍差于 批处理方法。 但批处理方法难以处理大规模的数据 集，正如本组实验的第 ２ 部分即将展示的（图 ３），这 正是在线学习方法的优势［２０⁃２１］ 。 下面给出 Ｆ１、Ｆ２ 与 ＳＳＬ⁃ＭＫＬ 在 Ｍ４ 和 Ｍ５ 整个数据集上的结果。 训 练集与测试集的规模按原数据集大小的 ３：７，对于 ＳＳＬ⁃ＭＫＬ 采用转导学习的方式［２２⁃２３］ ，即把整个测试 集作为无标记集。 同样对数据集进行 １０ 次随机划 分，记录每次分类正确率并计算方差，图 ３ 给出了在 数据集 Ｍ４ 和 Ｍ５ 上算法正确率的比较结果。 图 ３ Ｍ４ 和 Ｍ５ 的实验结果（完整数据集） Ｆｉｇ．３ Ｅｖａｌｕａｔｉｏｎ ｒｅｓｕｌｔｓ ｏｆ Ｍ４ ａｎｄ Ｍ５ （ｆｕｌｌ ｄａｔａ ｓｅｔ ｓｉｚｅ） 从图 ３ 中可看出，由于有完整的训练集，各个算 法的正确率相比图 ２ 有所提升。 ＳＳＬ⁃ＭＫＬ 算法相 比 Ｆ１ 和 Ｆ２ 的提升幅度比限制规模数据集时更大， 表明数据依赖核对于数据分布的估计能够提升核函 数的性能。 最后给出数据流集（Ｍ１、Ｍ２、Ｍ３）的测试结果。 测试过程是把训练样本按其顺序号依次输入学习模 型进行训练；在接受测试样本时，ＳＳＬ⁃ＭＫＬ 同时进 行无监督学习，而 Ｆ１ 和 Ｆ２，则仅输出测试结果。 由 于数据集有顺序，截取前面的 ３０％作为训练集，后 面 ７０％作为测试集。 表 ４ 给出了实验中各算法在数 据集上正确率的比较。 表 ４ 各算法在流数据集上正确率的比较 Ｔａｂｌｅ ４ Ａｃｃｕｒａｃｙ ｃｏｍｐａｒｉｓｏｎ ｏｎ ｓｔｒｅａｍ ｄａｔａ ｓｅｔｓ Ｍ１ Ｍ２ Ｍ３ Ｆ１ ０．７３１ ０．７８８ ０．７７５ Ｆ２ ０．７４２ ０．７８１ ０．７７０ ＳＳＬ⁃ＭＫＬ ０．７６８ ０．７９６ ０．８０２ 从表 ４ 中可知 ＳＳＬ⁃ＭＫＬ 算法在 ３ 个数据集上 都有最好的表现。 第 ２ 组实验分析本文算法对不同 规模数据集处理的 ＣＰＵ 运算时间增长与数据集大 小之间的关系。 为了精确控制实验数据集的规模， 本组实验使用了 ２０ 种规模依次等距递增的 Ｍ１ 数 据集（以 １０ ６ 为递增单位），记录了 Ｆ２ 和 ＳＳＬ⁃ＭＫＬ 第 ３ 期 张钢，等：面向大数据流的半监督在线多核学习算法 ·３６１·
·362· 智能系统学报 第9卷 算法的核学习时间，图4给出了运行时间对比。 结束语 30*10 SSL-MKL 大数据环境下的多核学习问题是大数据机器学 20 习的一个基础性问题，比单纯通过改进训练算法效 率构建学习器有更重要的意义。本文提出了一种适 用于大数据环境下的在线多核学习算法，考虑了数 10 15 20*10 据的有监督信息以及数据的空间分布，并应用数据 依赖核的构建方法，对所学习得到的核函数进行无 数据集规模 监督修正，使其具有更好的泛化能力。算法基于在 图4不同数据集规模下的算法运行时间比较 线学习的框架进行增量学习，仅需对训练数据进行 Fig4 CPU Time comparison for different data set sizes 一次扫描，就可以更新核函数，并不需要对历史数据 从图4中可以看出，SSL-MKL算法的运算时间 进行保存。算法适用于高速数据流，以及训练数据 与数据集的规模成线性关系，并且SSL-MKL算法的 规模很大以致不能全部加载到内存中的情形。在由 有监督学习部分的复杂性与算法F2同阶，从图4中 著名的大数据流分析工具MOA生成的人工数据集 可以看出其运算时间的增长率与数据集规模有较好 和UCI的大数据集上进行算法有效性评估，表明了 的线性关系，具有较好的可扩展性，能适用于更大规 本文方法能学习得到与数据集规律相一致的核函 模的数据集的分析和应用问题。 数，在分类器上有较好的效果，且本文算法是一种在 第3组实验评估算法SSL-MKL的迭代次数与 线学习算法，支持数据增量更新。此外，本文的算法 学习器性能的变化关系，从而说明其收敛性。设置 能同时处理有标记和无标记数据，对于数据概念标 测试集为整个数据集的5%，通过随机有回放抽取 记稀疏的高速数据流可以进行半监督学习，有很好 的方式生成。训练集为整个数据集的30%，与第1 的扩展性。 组实验相同。每输入5%的训练数据，运行一次测 试并记录结果。上述过程重复10次取平均正确率。 参考文献： 并以F3在限制数据集规模的实验（第1组）中的正 [1]GOPALKRISHNAN V,STEIER D,LEWIS H,et al.Big 确率作为基线进行对比。图5给出了在M4数据集 data,big business:bridging the gap[C]//Proceedings of 上算法正确率迭代收敛性的实验结果。 the Ist International Workshop on Big Data,Streams and 0.8 Heterogeneous Source Mining:Algorithms,Systems,Pro- gramming Models and Applications.Beijing,China,2012: 0.6 7-11. 0.4 SSL-MKL [2]YANG H,FONG S.Incrementally optimized decision tree 0.2 for noisy big data[C]//Proceedings of the Ist International Workshop on Big Data,Streams and Heterogeneous Source 00.050.100.150.200.250.300.35 Mining:Algorithms,Systems,Programming Models and 输入训练样本比例 Applications.Beijing,China,2012:36-44. 图5算法正确率的收敛性 [3]JORDAN M I.Divide-and-conquer and statistical inference Fig.5 The convergence of accuracy of the proposed al- for big data C//Proceedings of the 18th ACM SIGKDD in- gorithm ternational conference on Knowledge discovery and data 在图5中，F3表示离线批处理核学习方法得到 mining.Beijing,China,2012:4-4. 的核函数在SVM上的测试正确率曲线，SSL-MKL代 [4]ACAR U A,CHEN Y.Streaming big data with self-adjus- 表本文方法。每输入一个样本算法1就会运行一 ting computation[C]//Proceedings of the 2013 Proceedings 次，核函数同时更新一次。从图5中可以看出，在开 of the 2013 Workshop on Data driven Functional Program- 始阶段，仅需读入少量样本(5%)，SSL-MKL的正确 ming.Rome,Italy,2013:15-18. 率会大幅上升，随后会比较稳定收敛于一个较优的 [5]ARI I,CELEBI O F,OLMEZOGULLARI E.Data stream analytics and mining in the cloud [C]//Proceedings of the 值。当输入数据的内在生成规律相对稳定时，SSL- 2012 IEEE 4th International Conference on Cloud Compu- MKL对核函数的更新会在一段时间内（如图5中输 ting Technology and Science.Washington,DC,USA, 入15%数据之后)稳定下来，从而产生较稳定的测 2012:857-862. 试结果。 [6]AGMON S.The relaxation method for linear inequalities
算法的核学习时间，图 ４ 给出了运行时间对比。 图 ４ 不同数据集规模下的算法运行时间比较 Ｆｉｇ．４ ＣＰＵ Ｔｉｍｅ ｃｏｍｐａｒｉｓｏｎ ｆｏｒ ｄｉｆｆｅｒｅｎｔ ｄａｔａ ｓｅｔ ｓｉｚｅｓ 从图 ４ 中可以看出，ＳＳＬ⁃ＭＫＬ 算法的运算时间 与数据集的规模成线性关系，并且 ＳＳＬ⁃ＭＫＬ 算法的 有监督学习部分的复杂性与算法 Ｆ２ 同阶，从图 ４ 中 可以看出其运算时间的增长率与数据集规模有较好 的线性关系，具有较好的可扩展性，能适用于更大规 模的数据集的分析和应用问题。 第 ３ 组实验评估算法 ＳＳＬ⁃ＭＫＬ 的迭代次数与 学习器性能的变化关系，从而说明其收敛性。 设置 测试集为整个数据集的 ５％，通过随机有回放抽取 的方式生成。 训练集为整个数据集的 ３０％，与第 １ 组实验相同。 每输入 ５％的训练数据，运行一次测 试并记录结果。 上述过程重复 １０ 次取平均正确率。 并以 Ｆ３ 在限制数据集规模的实验（第 １ 组）中的正 确率作为基线进行对比。 图 ５ 给出了在 Ｍ４ 数据集 上算法正确率迭代收敛性的实验结果。 图 ５ 算法正确率的收敛性 Ｆｉｇ．５ Ｔｈｅ ｃｏｎｖｅｒｇｅｎｃｅ ｏｆ ａｃｃｕｒａｃｙ ｏｆ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌ⁃ ｇｏｒｉｔｈｍ 在图 ５ 中，Ｆ３ 表示离线批处理核学习方法得到 的核函数在 ＳＶＭ 上的测试正确率曲线，ＳＳＬ⁃ＭＫＬ 代 表本文方法。 每输入一个样本算法 １ 就会运行一 次，核函数同时更新一次。 从图 ５ 中可以看出，在开 始阶段，仅需读入少量样本（５％），ＳＳＬ⁃ＭＫＬ 的正确 率会大幅上升，随后会比较稳定收敛于一个较优的 值。 当输入数据的内在生成规律相对稳定时，ＳＳＬ⁃ ＭＫＬ 对核函数的更新会在一段时间内（如图 ５ 中输 入 １５％数据之后）稳定下来，从而产生较稳定的测 试结果。 ４ 结束语 大数据环境下的多核学习问题是大数据机器学 习的一个基础性问题，比单纯通过改进训练算法效 率构建学习器有更重要的意义。 本文提出了一种适 用于大数据环境下的在线多核学习算法，考虑了数 据的有监督信息以及数据的空间分布，并应用数据 依赖核的构建方法，对所学习得到的核函数进行无 监督修正，使其具有更好的泛化能力。 算法基于在 线学习的框架进行增量学习，仅需对训练数据进行 一次扫描，就可以更新核函数，并不需要对历史数据 进行保存。 算法适用于高速数据流，以及训练数据 规模很大以致不能全部加载到内存中的情形。 在由 著名的大数据流分析工具 ＭＯＡ 生成的人工数据集 和 ＵＣＩ 的大数据集上进行算法有效性评估，表明了 本文方法能学习得到与数据集规律相一致的核函 数，在分类器上有较好的效果，且本文算法是一种在 线学习算法，支持数据增量更新。 此外，本文的算法 能同时处理有标记和无标记数据，对于数据概念标 记稀疏的高速数据流可以进行半监督学习，有很好 的扩展性。 参考文献： ［１］ＧＯＰＡＬＫＲＩＳＨＮＡＮ Ｖ， ＳＴＥＩＥＲ Ｄ， ＬＥＷＩＳ Ｈ， ｅｔ ａｌ． Ｂｉｇ ｄａｔａ， ｂｉｇ ｂｕｓｉｎｅｓｓ： ｂｒｉｄｇｉｎｇ ｔｈｅ ｇａｐ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １ｓｔ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ ｏｎ Ｂｉｇ Ｄａｔａ， Ｓｔｒｅａｍｓ ａｎｄ Ｈｅｔｅｒｏｇｅｎｅｏｕｓ Ｓｏｕｒｃｅ Ｍｉｎｉｎｇ： Ａｌｇｏｒｉｔｈｍｓ， Ｓｙｓｔｅｍｓ， Ｐｒｏ⁃ ｇｒａｍｍｉｎｇ Ｍｏｄｅｌｓ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ． Ｂｅｉｊｉｎｇ， Ｃｈｉｎａ， ２０１２： ７⁃１１． ［２］ＹＡＮＧ Ｈ， ＦＯＮＧ Ｓ． Ｉｎｃｒｅｍｅｎｔａｌｌｙ ｏｐｔｉｍｉｚｅｄ ｄｅｃｉｓｉｏｎ ｔｒｅｅ ｆｏｒ ｎｏｉｓｙ ｂｉｇ ｄａｔａ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １ｓｔ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ ｏｎ Ｂｉｇ Ｄａｔａ， Ｓｔｒｅａｍｓ ａｎｄ Ｈｅｔｅｒｏｇｅｎｅｏｕｓ Ｓｏｕｒｃｅ Ｍｉｎｉｎｇ： Ａｌｇｏｒｉｔｈｍｓ， Ｓｙｓｔｅｍｓ， Ｐｒｏｇｒａｍｍｉｎｇ Ｍｏｄｅｌｓ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ． Ｂｅｉｊｉｎｇ， Ｃｈｉｎａ， ２０１２： ３６⁃４４． ［３］ＪＯＲＤＡＮ Ｍ Ｉ． Ｄｉｖｉｄｅ⁃ａｎｄ⁃ｃｏｎｑｕｅｒ ａｎｄ ｓｔａｔｉｓｔｉｃａｌ ｉｎｆｅｒｅｎｃｅ ｆｏｒ ｂｉｇ ｄａｔａ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １８ｔｈ ＡＣＭ ＳＩＧＫＤＤ ｉｎ⁃ ｔｅｒｎａｔｉｏｎａｌ ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｋｎｏｗｌｅｄｇｅ ｄｉｓｃｏｖｅｒｙ ａｎｄ ｄａｔａ ｍｉｎｉｎｇ． Ｂｅｉｊｉｎｇ， Ｃｈｉｎａ， ２０１２： ４⁃４． ［４］ＡＣＡＲ Ｕ Ａ， ＣＨＥＮ Ｙ． Ｓｔｒｅａｍｉｎｇ ｂｉｇ ｄａｔａ ｗｉｔｈ ｓｅｌｆ⁃ａｄｊｕｓ⁃ ｔｉｎｇ ｃｏｍｐｕｔａｔｉｏｎ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２０１３ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２０１３ Ｗｏｒｋｓｈｏｐ ｏｎ Ｄａｔａ ｄｒｉｖｅｎ Ｆｕｎｃｔｉｏｎａｌ Ｐｒｏｇｒａｍ⁃ ｍｉｎｇ． Ｒｏｍｅ， Ｉｔａｌｙ， ２０１３： １５⁃１８． ［５］ＡＲＩ Ｉ， ＣＥＬＥＢＩ Ｏ Ｆ， ＯＬＭＥＺＯＧＵＬＬＡＲＩ Ｅ． Ｄａｔａ ｓｔｒｅａｍ ａｎａｌｙｔｉｃｓ ａｎｄ ｍｉｎｉｎｇ ｉｎ ｔｈｅ ｃｌｏｕｄ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２０１２ ＩＥＥＥ ４ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｌｏｕｄ Ｃｏｍｐｕ⁃ ｔｉｎｇ Ｔｅｃｈｎｏｌｏｇｙ ａｎｄ Ｓｃｉｅｎｃｅ． Ｗａｓｈｉｎｇｔｏｎ， ＤＣ， ＵＳＡ， ２０１２： ８５７⁃８６２． ［６］ ＡＧＭＯＮ Ｓ． Ｔｈｅ ｒｅｌａｘａｔｉｏｎ ｍｅｔｈｏｄ ｆｏｒ ｌｉｎｅａｒ ｉｎｅｑｕａｌｉｔｉｅｓ ·３６２· 智 能 系 统 学 报 第 ９ 卷
第3期 张钢，等：面向大数据流的半监督在线多核学习算法 ·363. [J].Canadian Journal of Mathematics,1954,6(3):393- USA,2011:591-599. 404」 [17]FRANCESCO O,LUO Jie,BARBARA C.Multi kerel [7]GONEN M,ALPAYD E.Multiple kernel learning algo- learning with online-batch optimization[J].Joural of Ma- rithms [J].Journal of Machine Learning Research,2011 chine Learning Research,2012(13):227-253. (12):2211-2268. [18]STEVEN C H,RONG Jin,ZHAO Peilin,et al.Online [8 ORABONA F,JIE L,CAPUTO B.Multi kernel learning multiple kernel classification [J].Machine Learning, with online-batch optimization [J].Journal of Machine 2013,90(2):289-316. Learning Research,2012(13):227-253. [l9]UCI数据集：htp:/archive.ics.uci.edu/ml/[EB/OL]. [9]JIN R,HOI S C H,YANG T,et al.Online multiple kernel [2014-03-18]. learning:algorithms and mistake bounds[J].Algorithmic [20]YANG Haiqin,MICHAEL R L,IRWIN K.Efficient online Learning Theory,2010(6331):390-404. learning for multitask feature selection[J].ACM Transac- [10]QIN C,RUSU F.Scalable I/O-bound parallel incremental tions on Knowledge Discovery from Data,2013,7(2):6- gradient descent for big data analytics in GLADE[C]// 27. Proceedings of the Second Workshop on Data Analytics in [21]CHEN Jianhui,LIU Ji,YE Jieping.Learning incoherent the Cloud.New York,USA.2013:16-20. sparse and low-rank patterns from multiple tasks[J].ACM [11 SINDHWANI V,NIYOGI P,BELKIN M.Beyond the Transactions on Knowledge Discovery from Data,2012,5 point cloud:from transductive to semi-supervised learning (4):22-31. [C]//Proceedings of the 22nd International Conference [22]HONG Chaoqun,ZHU Jianke.Hypergraph-based multi-ex- on Machine Learning.Bonn,Germany,2005:824-831. ample ranking with sparse representation for transductive [12]李宏伟，刘扬，卢汉清，等.结合半监督核的高斯过程 learning image retrieval [J].Neurocomputing,2013 分[J].自动化学报，2009,35(7)：888-895. (101):94-103. LI Hongwei,LIU Yang,LU Hanqing,et al.Gaussian [23]YU Jun,BIAN Wei,SONG Mingli,et al.Graph based processes classification combined with semi-supervised ker- transductive learning for cartoon correspondence construc- nels[J].Acta Automatica Sinica,2009,35(7):888-895. tion[J].Neurocomputing,2012(79):105-114. [13]邹恒明.计算机的心智：操作系统之哲学原理[M].北 作者简介： 京：机械工业出版社，2012：100-102. 张钢，男，1979年生，讲师，博士研 [14]BIFET A,HOLMES G,KIRKBY R,et al.MOA:massive 究生，CCF会员。主要研究方向为机器 online analysis[J].Journal of Machine Learning Research, 学习、数据挖掘和生物信息学，参与国 2010(11):1601-1604. 家自然科学基金项目1项，广东省自然 [15]KREMER H,KRANEN P,JANSEN T,et al.An effective 科学基金团队项目1项，获得软件著作 evaluation measure for clustering on evolving data streams 权2项，专利4项。发表学术论文40余 [C]//Proceedings of the 17th ACM SIGKDD International 篇，其中被SCI检索3篇，EI检索20余篇， Conference on Knowledge Discovery and Data Mining.San Diego,California,USA,2011:868-876. [16]BIFET A,HOLMES G,PFAHRINGER B,et al.Mining 谢晓珊，女，1990年生，硕士研究 frequent closed graphs on evolving data streams[C]//Pro- 生，发表学术论文3篇，主要研究方向 ceedings of the 17th ACM SIGKDD International Confer- 为机器学习、数据挖掘、模式识别和生 ence on Knowledge Discovery and Data Mining.San Diego, 物医学图像处理
［Ｊ］． Ｃａｎａｄｉａｎ Ｊｏｕｒｎａｌ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ， １９５４， ６（３）： ３９３⁃ ４０４． ［７］ ＧＯＮＥＮ Ｍ， ＡＬＰＡＹＤ Ｅ． Ｍｕｌｔｉｐｌｅ ｋｅｒｎｅｌ ｌｅａｒｎｉｎｇ ａｌｇｏ⁃ ｒｉｔｈｍｓ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ Ｒｅｓｅａｒｃｈ， ２０１１ （１２）： ２２１１⁃２２６８． ［ ８］ ＯＲＡＢＯＮＡ Ｆ， ＪＩＥ Ｌ， ＣＡＰＵＴＯ Ｂ． Ｍｕｌｔｉ ｋｅｒｎｅｌ ｌｅａｒｎｉｎｇ ｗｉｔｈ ｏｎｌｉｎｅ⁃ｂａｔｃｈ ｏｐｔｉｍｉｚａｔｉｏｎ ［ Ｊ ］． Ｊｏｕｒｎａｌ ｏｆ Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ Ｒｅｓｅａｒｃｈ， ２０１２（１３）： ２２７⁃２５３． ［９］ＪＩＮ Ｒ， ＨＯＩ Ｓ Ｃ Ｈ， ＹＡＮＧ Ｔ， ｅｔ ａｌ． Ｏｎｌｉｎｅ ｍｕｌｔｉｐｌｅ ｋｅｒｎｅｌ ｌｅａｒｎｉｎｇ： ａｌｇｏｒｉｔｈｍｓ ａｎｄ ｍｉｓｔａｋｅ ｂｏｕｎｄｓ ［ Ｊ］． Ａｌｇｏｒｉｔｈｍｉｃ Ｌｅａｒｎｉｎｇ Ｔｈｅｏｒｙ， ２０１０（６３３１）： ３９０⁃４０４． ［１０］ＱＩＮ Ｃ， ＲＵＳＵ Ｆ． Ｓｃａｌａｂｌｅ Ｉ／ Ｏ⁃ｂｏｕｎｄ ｐａｒａｌｌｅｌ ｉｎｃｒｅｍｅｎｔａｌ ｇｒａｄｉｅｎｔ ｄｅｓｃｅｎｔ ｆｏｒ ｂｉｇ ｄａｔａ ａｎａｌｙｔｉｃｓ ｉｎ ＧＬＡＤＥ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｓｅｃｏｎｄ Ｗｏｒｋｓｈｏｐ ｏｎ Ｄａｔａ Ａｎａｌｙｔｉｃｓ ｉｎ ｔｈｅ Ｃｌｏｕｄ． Ｎｅｗ Ｙｏｒｋ， ＵＳＡ， ２０１３： １６⁃２０． ［１１］ ＳＩＮＤＨＷＡＮＩ Ｖ， ＮＩＹＯＧＩ Ｐ， ＢＥＬＫＩＮ Ｍ． Ｂｅｙｏｎｄ ｔｈｅ ｐｏｉｎｔ ｃｌｏｕｄ： ｆｒｏｍ ｔｒａｎｓｄｕｃｔｉｖｅ ｔｏ ｓｅｍｉ⁃ｓｕｐｅｒｖｉｓｅｄ ｌｅａｒｎｉｎｇ ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２２ｎｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ． Ｂｏｎｎ， Ｇｅｒｍａｎｙ， ２００５： ８２４⁃８３１． ［１２］李宏伟， 刘扬， 卢汉清， 等． 结合半监督核的高斯过程 分［Ｊ］． 自动化学报， ２００９， ３５（７）： ８８８⁃８９５． ＬＩ Ｈｏｎｇｗｅｉ， ＬＩＵ Ｙａｎｇ， ＬＵ Ｈａｎｑｉｎｇ， ｅｔ ａｌ． Ｇａｕｓｓｉａｎ ｐｒｏｃｅｓｓｅｓ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｃｏｍｂｉｎｅｄ ｗｉｔｈ ｓｅｍｉ⁃ｓｕｐｅｒｖｉｓｅｄ ｋｅｒ⁃ ｎｅｌｓ［Ｊ］． Ａｃｔａ Ａｕｔｏｍａｔｉｃａ Ｓｉｎｉｃａ， ２００９， ３５（７）： ８８８⁃８９５． ［１３］邹恒明． 计算机的心智：操作系统之哲学原理［Ｍ］． 北 京： 机械工业出版社， ２０１２： １００⁃１０２． ［１４］ＢＩＦＥＴ Ａ， ＨＯＬＭＥＳ Ｇ， ＫＩＲＫＢＹ Ｒ， ｅｔ ａｌ． ＭＯＡ： ｍａｓｓｉｖｅ ｏｎｌｉｎｅ ａｎａｌｙｓｉｓ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ Ｒｅｓｅａｒｃｈ， ２０１０（１１）： １６０１⁃１６０４． ［１５］ＫＲＥＭＥＲ Ｈ， ＫＲＡＮＥＮ Ｐ， ＪＡＮＳＥＮ Ｔ， ｅｔ ａｌ． Ａｎ ｅｆｆｅｃｔｉｖｅ ｅｖａｌｕａｔｉｏｎ ｍｅａｓｕｒｅ ｆｏｒ ｃｌｕｓｔｅｒｉｎｇ ｏｎ ｅｖｏｌｖｉｎｇ ｄａｔａ ｓｔｒｅａｍｓ ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １７ｔｈ ＡＣＭ ＳＩＧＫＤＤ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ａｎｄ Ｄａｔａ Ｍｉｎｉｎｇ． Ｓａｎ Ｄｉｅｇｏ， Ｃａｌｉｆｏｒｎｉａ， ＵＳＡ， ２０１１： ８６８⁃８７６． ［１６］ＢＩＦＥＴ Ａ， ＨＯＬＭＥＳ Ｇ， ＰＦＡＨＲＩＮＧＥＲ Ｂ， ｅｔ ａｌ． Ｍｉｎｉｎｇ ｆｒｅｑｕｅｎｔ ｃｌｏｓｅｄ ｇｒａｐｈｓ ｏｎ ｅｖｏｌｖｉｎｇ ｄａｔａ ｓｔｒｅａｍｓ［Ｃ］ ／ ／ Ｐｒｏ⁃ ｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １７ｔｈ ＡＣＭ ＳＩＧＫＤＤ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒ⁃ ｅｎｃｅ ｏｎ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ａｎｄ Ｄａｔａ Ｍｉｎｉｎｇ． Ｓａｎ Ｄｉｅｇｏ， ＵＳＡ， ２０１１： ５９１⁃５９９． ［１７］ ＦＲＡＮＣＥＳＣＯ Ｏ， ＬＵＯ Ｊｉｅ， ＢＡＲＢＡＲＡ Ｃ． Ｍｕｌｔｉ ｋｅｒｎｅｌ ｌｅａｒｎｉｎｇ ｗｉｔｈ ｏｎｌｉｎｅ⁃ｂａｔｃｈ ｏｐｔｉｍｉｚａｔｉｏｎ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｍａ⁃ ｃｈｉｎｅ Ｌｅａｒｎｉｎｇ Ｒｅｓｅａｒｃｈ， ２０１２（１３）： ２２７⁃２５３． ［１８］ ＳＴＥＶＥＮ Ｃ Ｈ， ＲＯＮＧ Ｊｉｎ， ＺＨＡＯ Ｐｅｉｌｉｎ， ｅｔ ａｌ． Ｏｎｌｉｎｅ ｍｕｌｔｉｐｌｅ ｋｅｒｎｅｌ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ［ Ｊ ］． Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ， ２０１３， ９０（２）： ２８９⁃３１６． ［１９］ＵＣＩ 数据集：ｈｔｔｐ： ／ ／ ａｒｃｈｉｖｅ． ｉｃｓ． ｕｃｉ． ｅｄｕ ／ ｍｌ ／ ［ ＥＢ／ ＯＬ］． ［２０１４⁃０３⁃１８］． ［２０］ＹＡＮＧ Ｈａｉｑｉｎ， ＭＩＣＨＡＥＬ Ｒ Ｌ， ＩＲＷＩＮ Ｋ． Ｅｆｆｉｃｉｅｎｔ ｏｎｌｉｎｅ ｌｅａｒｎｉｎｇ ｆｏｒ ｍｕｌｔｉｔａｓｋ ｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ［ Ｊ］． ＡＣＭ Ｔｒａｎｓａｃ⁃ ｔｉｏｎｓ ｏｎ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ｆｒｏｍ Ｄａｔａ， ２０１３， ７（２）： ６⁃ ２７． ［２１］ＣＨＥＮ Ｊｉａｎｈｕｉ， ＬＩＵ Ｊｉ， ＹＥ Ｊｉｅｐｉｎｇ． Ｌｅａｒｎｉｎｇ ｉｎｃｏｈｅｒｅｎｔ ｓｐａｒｓｅ ａｎｄ ｌｏｗ⁃ｒａｎｋ ｐａｔｔｅｒｎｓ ｆｒｏｍ ｍｕｌｔｉｐｌｅ ｔａｓｋｓ［Ｊ］． ＡＣＭ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ｆｒｏｍ Ｄａｔａ， ２０１２， ５ （４）： ２２⁃３１． ［２２］ＨＯＮＧ Ｃｈａｏｑｕｎ， ＺＨＵ Ｊｉａｎｋｅ． Ｈｙｐｅｒｇｒａｐｈ⁃ｂａｓｅｄ ｍｕｌｔｉ⁃ｅｘ⁃ ａｍｐｌｅ ｒａｎｋｉｎｇ ｗｉｔｈ ｓｐａｒｓｅ ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ｆｏｒ ｔｒａｎｓｄｕｃｔｉｖｅ ｌｅａｒｎｉｎｇ ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ ［ Ｊ ］． Ｎｅｕｒｏｃｏｍｐｕｔｉｎｇ， ２０１３ （１０１）： ９４⁃１０３． ［２３］ ＹＵ Ｊｕｎ， ＢＩＡＮ Ｗｅｉ， ＳＯＮＧ Ｍｉｎｇｌｉ， ｅｔ ａｌ． Ｇｒａｐｈ ｂａｓｅｄ ｔｒａｎｓｄｕｃｔｉｖｅ ｌｅａｒｎｉｎｇ ｆｏｒ ｃａｒｔｏｏｎ ｃｏｒｒｅｓｐｏｎｄｅｎｃｅ ｃｏｎｓｔｒｕｃ⁃ ｔｉｏｎ［Ｊ］． Ｎｅｕｒｏｃｏｍｐｕｔｉｎｇ， ２０１２（７９）： １０５⁃１１４． 作者简介： 张钢，男，１９７９ 年生，讲师，博士研 究生，ＣＣＦ 会员。 主要研究方向为机器 学习、数据挖掘和生物信息学，参与国 家自然科学基金项目 １ 项 ，广东省自然 科学基金团队项目 １ 项，获得软件著作 权 ２ 项，专利 ４ 项。 发表学术论文 ４０ 余 篇，其中被 ＳＣＩ 检索 ３ 篇，ＥＩ 检索 ２０ 余篇， 谢晓珊，女，１９９０ 年生，硕士研究 生，发表学术论文 ３ 篇，主要研究方向 为机器学习、数据挖掘、模式识别和生 物医学图像处理。 第 ３ 期 张钢，等：面向大数据流的半监督在线多核学习算法 ·３６３·