第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
（∑ｉ Ｗｉｊ － Ｗ） ｐ ， ｋ 关于 Ｄ 的 Ｇｒａｍ 矩阵记为 ｋＤ ， Ｗｉｊ ＝ ＲＢＦ（ｘｉ，ｘｊ） ， ｘｉ，ｘｊ ∈ Ｄ 。 则可以通过式（４）的 方式对核函数 ｋ 进行修改，使其等距线沿 Ｄ 进行分 布： ｋＤ（ａ，ｂ） ＝ ｋ（ａ，ｂ） － ｋ Ｔ ａ （Ｉ ＋ ＭＫＤ） －１Ｍｋｂ （４） 其中 ａ 和 ｂ 为任意 ２ 个训练样本， Μ 是一个在原点 对称的距离矩阵，按文献［１２］的方法用图拉普拉斯 矩阵计算得到。 整个过程中并没有考虑数据的标 签，仅是通过考虑数据的密度分布，对原有核函数的 值进行修改。 式（４）的计算需要离线批量进行，且计算的时 间复杂度较高，具体而言，式（４）在修改数据样本 ａ 和 ｂ 的核函数值时要计算 ｋａ 和 ｋｂ ，即 ａ 和 ｂ 与当前 可见数据集的核函数 ｋ 值。 当可见数据不变时， Ｍ 和 ｋＤ 这两项只需计算一次，但对数据流而言， Ｍ 和 ｋＤ 是在不断变化的。 但可以肯定的一点是，对于大 规模数据集和数据流，直接计算整个数据集的 Ｍ 和 ｋＤ 在计算资源上并不现实。 因此考虑 Ｍ 和 ｋＤ 的在线更新策略，采用限制 Ｍ 和 ｋＤ 的规模为 Ｎ × Ｎ ，则必须有 Ｄ 中的数据样本 替换策略。 借鉴操作系统中内存页面的调度算法， 对静态的大数据集应用类似近期最少使用（ｌｅａｓｔ ｒｅ⁃ ｃｅｎｔｌｙ ｕｓｅｄ， ＬＲＵ）的样本更新策略［１３］ ，而对于高速 数据流应用先进先出（ｆｉｒｓｔ ｉｎ ｆｉｒｓｔ ｏｕｔ， ＦＩＦＯ）更新策 略［１３］ ，其中 ＬＲＵ 是替换最近一段时间没有被使用 过的样本，由于样本各不相同，本文采用聚类意义下 的样本使用统计。 这两种策略的合理性基于以下分 析。 对于静态大数据集，虽然数据是顺序地输入到 学习器中，但其数据到达顺序和时序不相关，因此不 能使用与时间密切相关的 ＦＩＦＯ 策略，而采用 ＬＲＵ 策略较为合理；对于数据流，其数据生成规律有可能 随时间变化而变化，因此替换存在时间最长样本的 ＦＩＦＯ 策略是合理的。 同时，数据依赖核是通过对数 据的分布估计对核函数进行修改，计算这种分布需 要对一定规模的数据点进行分析，因此维持一个工 作集 Ｍ 是必须的，它可被看作一个缓存，反映近一 段时间的数据分布规律。 这种限制工作集大小的更 新策略有一定的局部性，但在有限的计算和存储资 源下是折衷的策略。 算法维持一个不考虑标签的样本集 Ｄ 并进行 在线更新。 ｋａ 和 ｋｂ 的计算步聚是先查表 ｋＤ ，若不命 中再计算，时间复杂度为 Ｏ（Ｎ） 。 对于 Ｍ 和 ｋＤ ，替 换样本之后需要重新计算一行，然后更新一行和一 列，因此其时间复杂度也为 Ｏ（Ｎ） 。 算法初始时计 算 Ｍ 和 ｋＤ 的时间复杂度为 Ｏ（Ｎ ２ ） 。 一个重要问题是 ＬＲＵ 和 ＦＩＦＯ 中对输入样本的 时间属性记录，对 ＬＲＵ 还有聚类意义下最近被使用 样本的判断。 本文首先用聚类的方式产生数据集 Ｄ 的 ｒ 个簇，应用在线聚类的方式更新这 ｒ 个簇，替换 样本时每次从最久没有被更新过的簇中随机选取一 个样本进行替换，使用一个长度为 ｒ 优先队列记录 每个簇最近被访问的情况。 对于 ＦＩＦＯ 策略，不需 要优先队列，每次把新加入的样本放在最下行和最 右列，然后去掉第 １ 行第 １ 列即可。 算法 ２ 和算法 ３ 分别描述了静态大数据集和流数据集 ２ 种情况下的 数据依赖核的在线学习过程。 算法 ２ 使用一个优先队列记录样本簇最近被访 问的情况，认为一个簇中的样本被访问过一次，则该 簇最近被访问过，核矩阵的更新从第 ７ 至 １０ 行，需 要对所有样本扫描一次，时间复杂度是 Ｏ（Ｎ ２ ） ，优 先队列的操作需要 Ｏ（ｒ） ，其中 ｒ 为簇的个数，判断 ｘ０ 属于哪个簇的粗糙算法需要 Ｏ（ｒ） 时间，整体的 时间复杂度为 Ｏ（Ｎ ２ ） 。 算法 ２ 大数据集的数据依赖核在线学习 输入： 数据样本集： Ｄ ＝ ｛ｘ１ ，ｘ２ ，…，ｘＮ｝ 当前输入样本： ｘ０ 核函数 Ｇｒａｍ 矩阵和距离矩阵： Ｋ、Μ 样本空间聚类分布： ＬＣ 记录簇最近访问的优先队列： Ｑ 输出： 更新后的核矩阵： Ｋ １） ｒ ＝ ｃｌｕｓ（ＬＣ ，ｘ０ ） ／ ／ 查找样本 ｘ０ 的簇号 ２） 根据 ｒ 更新优先队列 Ｑ ３） 把 ｘ０ 加到簇 ｒ 中 ４） 在优先队列 Ｑ 的队尾所示的簇中随机去掉 一个样本 ５） 初始化 ｋｘ０ ６） 令 ｋ１ ＝ （ｋ（ｘ０ ，ｘ１ ），…，ｋ（ｘ０ ，ｘＮ）） ７） ｆｏｒ ｊ ＝ １，…，Ｎ ｄｏ ８） ｋ２ ＝ Ｋ（ｊ，·） ９） ｋｋ０ ＝ ｋ１ － ｋ Ｔ １ （Ｉ ＋ ΜＫ） －１Μｋ２ １０）ｅｎｄ ｆｏｒ １１） 用 ｋｘ０ 更新矩阵 Ｋ 中关于 ｘ０ 的一行和一列 １２） ｒｅｔｕｒｎ Ｋ 算法 ３ 流数据集的数据依赖核在线学习 输入： 数据样本集 Ｄ ＝ ｛ｘ１ ，…ｘＮ｝ 当前输入样本： ｘ０ 第 ３ 期 张钢，等：面向大数据流的半监督在线多核学习算法 ·３５９·