·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存储、处理和分析的数据规模以指数方式递增。 如 谷歌搜索引擎在 ２００８ 年索引的网页个数突破 １ 万 亿个，沃尔玛最近构建的一个数据仓库的数据规模 达到 ４ ＰＢ。 在此背景下对大数据的分析和挖掘成 为当前的热点研究主题［１］ 。 从算法的层面来看，大 数据的机器学习和分析挖掘问题，主要存在以下的 问题： １）数据规模巨大，体现在数据记录个数及维度 上，对于很多大数据分析问题，即使是多项式时间复 杂度的机器学习算法也不能在人们可接受的时间内 得到结果。 ２）由于数据集比计算机内存大，导致无法在训 练学习器时加载整个训练集，或是出于应用环境的 限制，在训练学习器时不能获取整个数据集，数据记 录可能按某种速率到来，而且数据产生的规律性会 随着时间变化而有所改变。 要解决问题 １），主要从 ２ 个途径去考虑，其一 是降低现有分析算法的时间复杂度，采取一些近似 算法，在复杂度和精度方面取得折衷，如 Ｙａｎｇ 等［２］ 提出了一种决策树快速增量学习方法，通过对决策 树的属性选择指标进行近似，使算法能适用于数据 流和超大型数据集，其性能和普通版本的决策树相 比并没有明显的下降；Ｊｏｒｄａｎ ［３］ 对大数据统计推断 进行了回顾，并针对大数据分而治之的算法提出了 ２ 种设计方法，其中重采样策略是对完整训练集的 近似，而分治策略把大数据集数据间的相互关系限 制在较小的范围内，最终目的是降低算法的复杂度； 其二是对现有算法进行修改，转化为可以并发／ 并行 计算的版本，并利用云计算开发工具，如 ＭａｐＲｅｄｕｃｅ 编写可以在云计算平台上运行的程序，通过计算云 的强大运算能力，使算法能在可接受的时间内解决 大数据分析问题，如 Ａｃａｒ 等［４］在 ＭａｐＲｅｄｕｃｅ 框架中 实现了自适应计算的数据流分析算法，通过维护一 个数据表跟踪数据集不同部分计算之间的依赖关 系，当需要更新时仅需考虑有关联的部分数据，算法 有相对较佳的运行效率；Ａｒｉ 等［５］ 设计了面向数据 流的相关分析和关联规则挖掘的云计算算法，能够 以批处理和在线的方式把相关分析和关联规则挖掘 的任务透明分配到计算云的不同部分，同时计算然 后再进行整合。 对于问题 ２），目前主要解决思路是设计出以往 机器学习和挖掘算法的在线学习版本。 在线学习原 是机器学习的一个研究分支，其目标数据样本以顺 序的方式输入学习器，且不对历史数据样本进行保 存，算法通过对当前输入的样本进行分析，同步更新 学习器，其中神经网络中的感知器模型就是在线学 习的经典例子［６］ 。 由于在线学习不用保存以往的 数据样本，或仅需保存以往数据样本的某种充分统 计量，十分适合大数据分析的应用场景。 对于超大 型数据集，以顺序方式输入模型，并同步更新学习 器；对高速数据流，在线学习可以实现数据的边输入 边学习，使学习器模型能够反映出最近一段时间的 输入数据规律并进行有效预测。 本文研究大数据环境下的在线核学习（ ｏｎｌｉｎｅ ｋｅｒｎｅｌ ｌｅａｒｎｉｎｇ） 算法。 与传统在线学习不同，本文 的工作主要针对大数据流中的核函数学习问题，算 法并不直接通过数据样本的分析对学习器进行更 新，而是通过在线学习以迭代的方式确定一个最适 用于当前数据产生规律的核函数。 本文认为，核函 数的学习比直接训练学习器有更广泛的适用性，一 个合适的核函数可以被嵌入到各种不同核学习器的 训练过程，也可以直接用于核主成份分析（ ｋｅｒｎｅｌ ＰＣＡ）、相关性分析（ ｋｅｒｎｅｌ ＣＣＡ） 或聚类分析等领 域。 因此，一个有效适用于大数据环境下的核学习 算法有重要应用价值。 目前被公开报道的在线核学习研究工作并不 多，虽然核学习被广泛用于机器学习的不同应用领 域，但核函数的学习问题由于其对分析目标的间接 性影响，在大数据分析和挖掘领域中并没有被充分 研究，因此研究大数据环境下的核函数学习问题对 其他大数据机器学习任务有重要的基础性意义。 本文提出一种适用于大数据流的在线核学习算 法，在现有多核学习框架中结合数据依赖核的构建 方法，同时进行有监督学习和无监督学习，对于高速 数据流中的有标记数据使用一种类似感知器训练的 学习策略进行有监督核函数学习，对于所有数据 （包括有标记和无标记数据）进行基于数据依赖核 的核函数更新策略，实质上进行一种无监督学习，不 需要存储和重新扫描历史数据，仅需通过选择的方 式维持一个样本工作集，在读取新的数据样本时能 以较低的时间复杂度直接更新当前的核函数，适用 于大数据环境下的核学习问题，特别是高速大数据 流中标记缺失的情形。 １ 在线核学习的相关工作 核函数学习问题是机器学习研究中的一个分支方 向，通过机器学习的方法学习一个针对特定应用背景 的核函数，能够大幅提高训练学习器的效果。 Ｇöｎｅｎ ·３５６· 智 能 系 统 学 报 第 ９ 卷