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