多维演化数据流核密度估计

多维演化数据流核密度估计 2011 年 9 月 计 算 机 工 程第 37 卷 第 17 期 September 2011 Computer Engineering Vol.37 No.17 文献标识码:A 中图分类号:N945 文章编号:1000—3428(2011)17—0046—03 ?软件技术与数据库? 多维演化数据流核密度估计 罗 剑 (浙江经济职业技术学院数字信息技术学院，杭州 310018) 摘 要:将面向大规模数据集的基于网格重心的分箱核密度估计理论扩展到数据流应用领域，在引入密度衰减技术的基础上，指出对于演化数据流以网格重心取代网格离散数据点集合的分箱核密度估计方法的近似误差是可控的，由此构造多维演化数据流核密度估计算法。实 验结果表明，该方法在保持足够计算精度的同时能够精确捕获数据流的实时演化行为。 关键词:核密度估计;数据流;演化;分箱规则;网格 Kernel Density Estimation for Multidimensional Evolution Data Stream LUO Jian (School of Digital Information Technology, Zhejiang Technology Institute of Economy, Hangzhou 310018, China) 【Abstract】The binned density estimation which is designed for very large datasets and based on the gravity center of the data points in a grid is extended to data stream applications. When introducing a density decaying scheme, it is revealed that the closeness of such estimators which substitutes the center of a grid with the gravity center of the data points is bounded. As a result, an algorithm for multidimensional evolution data streams is proposed. Experimental results show the algorithm can capture the evolving behaviors of the data stream in real time with enough accuracy. 【Key words】kernel density estimation; data stream; evolution; binning rule; grid DOI: 10.3969/j.issn.1000-3428.2011.17.014 1 概述 2 相关工作 随着实时监视系统、通信网络、互联网信息传输和商业 2.1 M 核算法[3]金融市场等动态环境的快速发展，产生了大量数据。这 些数 M 核算法是最早提出核合并思想的数据流核密度估计 据以不同的更新速率连续地流入和流出计算机系统，形成多算法，使用高斯函数作为基核函数，每M个 核维护一个四元 种形态的数据流。与传统数据集不同，数据流是按时间顺序 组<均值，窗宽，数量，相邻核合并代价>，它的初始窗宽的、快速变化的、海量的和潜在无限的，构造 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 和处理数 和 数量被设置为1 。随着数据流的快速到达，M 核的个数[1]据流的算法应该满足如下的准则:(1)处理数据流中数据记 不断 增加，最终等于系统设定的最大M值。 为了保证 M 核录的时间必须固定和短暂;否则算法不可能跟上数据接收的 个数不 频率。(2)无论算法面对多少数据量，必须使用固定大小的内 再增加，系统将 2 个具有最小代价函数(merge_cost)值的相邻存空间。(3)只可能对数据进行一次扫描，因为在大多数应用 中无法得到历史数据，或者是访问历史数据代价太(4大)。能 M 核合并以容纳新的M 核。代价函数以均值和窗宽为未知参 够在处理的任何阶段输出可用结果，而非等到处理完所有数 数，利用单纯形法计算得到函数最小值，同时也决定了合并 据后才输出结果，因为也许永远到不了流数据的尽头。(5)当 后 M 核的均值和窗宽。核密度估计由全M体 个核函数利用 流数据的模型发生变化时，计算结果要及时调整以反映数据 单点重采样策略累加得到。 的变化。传统的数据分析算法无法实现面向数据流的计算时 2.2 聚类核算法 文献[4]发展了核合并的思想，提出聚类核间和存储空间要求，需要开发专门的流数据处理和分析算法。 的概念。每个 时间和空间的限制决定了算法需要在计算结果的精度和整体 聚类核维护一个四元组<均值，窗宽，统计量，相邻核合并代 性能之间取得平衡，同时拥有尽可能小的近似误差。由于数 据流可以看成是随时间不断变化的无限过程，其隐含的信息 价>。窗宽设置遵循正态尺度规则(normal reference rule)。每 随时间动态变化，如形状的变化、位置的转移、新类的出现、 个聚类核四元组中的“统计量”是一个多元组，除了包含旧类的消失等，即数据流处于演化的过程中。因此，在处理 其 合并的核数量，还有根据不同重采样策略而设置的统计[2]演化数据流时，要注意历史数据重要性的度量。 信息。 由于聚类核算法使用数学表达式更为简明的 核密度估计是由给定样本点集合求解随机变量分布密度 Epanechnikov核 , 函数的非参数估计方法，具有渐进无偏性、均方相合性、依 在 1 维条件下能够按照两合并核间的不同距离长度推导出代概率一致收敛性等良好特性。本文研究多维演化数据流核密 价函数的多项式计算公式，确保在常数时间内计算出代价函 度估计，通过了解数据集的密度分布，为密度聚类、离群点 检测等应用提供必要的条件和手段。 数最小值。 作者简介:罗 剑(1971,)，男，高级工程师、副教授、硕士，主研 无论是 M 核算法还是聚类核算法，都是依托有限的内存方向:数据库知识发现，网格计算 收稿日期:2011-03-17 E-mail:luojian1018@sohu.com 空间处理数据流无限到达的计算策略，需要1 维核按照均对 对于每个到达的数据X ，赋予它一个随时间减少的密度相关 值排序，在多维空间中无法精确排序且均面临巨大的数值计 系数。如果X 在时刻 t到达，既它的时间戳 T X , t，则定 ， ， c c t T ， X ， t t算开销，不适合推广到多维数据流2 。种算法都可以视为 c 义随后某时刻 t 时 X 的密度相关系数 D X , t , ， , ， ， ， ， 1 维“动态网格”的应用，所谓动态指的是每个合并核的分 其中， ， 称为衰减因子，且 ， 0，1。令 E g , t 代表在时刻 t，， ， ， 组宽度由代价函数决定，随核合并的过程动态变化。这 种策 或之前进入网格g 的数据集合。 略增加了计算开销，对于合并误差最小化是有益的。此外，[7] 定义 3(网格密度)对于网格 g，在一个给定的时刻 t，g2 种算法都提到了数据流的演化，但是没有给出实验结果。 的网格密度定义为所有进入其中的数据的密度相关系数之 [5]类似的算法还有 LR-KDE，可以根据数据分布密度的差异 和，即 g 在时刻 t 的密度为: 自适应地调整不同区域的窗宽。 (8) D g , t , D X , t ， ， ， ， X E， g ,t ， 3 算法分析 [7] 上述讨论表明将“动态网格”思想应用于多维数据流处定理 2假设网格 g 在时刻 t 有新数据到达，上一个数n 理是不合适的，难以满足数据流在线计算的要求且缺乏必要 据的到达时刻为 t，则 g 在 t的密度公式为: l n t t的策略。考虑固定网格宽度，以等宽网格为处理单元统计数 n l D g , t , ， D g , t ， 1(9) ， ， ， ， n l 据流在线信息，进而给出全局密度分布。在实现的过程中网 定理 2 揭示了网格中经过时间演化的数据个数(密度)， 格计算的近似误差是必须考虑的重要因素。 它的值一般不是整数。 限于篇幅下面3.1 基于网格重心的简单分箱核密度估计 在传统的面向的定理均略去证明。 大规模数据集的核密度估计应用中，基于 定义 4(网格密度平方) 对于网格 g，在一个给定的时 [6]网格重心的简单分箱核密度估计可以有效地降低近似计算 刻 t，g 的网格密度平方定义为所有进入其中的数据的密度相 带来的误差，有如下的结论: 关系数平方之和，即g 在时刻 t 的密度平方为: d 2 2 定义 1 设向量 X, X ,…, X 为空间R 上的独立同分布 1 2 n Dg, t , DX , t (10) ， ， ， ， X E， g ,t ， 随机变量，其分布密度函数f ( X ) 的核密度估计定义为:定理 3 假设网格 g 在时刻 t有新数据到达，上一个数据 nn 1 ˆ f ( X ) , KX X (1) ， ， d ,h i 的到达时刻为 t，则 g 在 t的密度平方公式为: n i,1 l n 2t t ，， 2 2 其中:n l D g t, , ， D g ,t ， 1 (11) ， ， ， ， nld d KX , Kx, K xh/h(2) ， ， ， ， ， ， 定理 4(网格衰减线性和 LS ) 假设网格 g 在时刻 t有新d ,h h i ii i n i i,1 i,1 数据到达，上一个数据的到达时刻 t为， t时刻的网格衰减 l l K ,为一维基核函数。特别地，采用d 维相同窗宽高斯核，， 线性和为L S g, t，则 g 在 t的网格衰减线性和公式为:， ， 函l n t t d d 2 n l (12) LS g, t, ， LS g , t， X 2数构造的 R上的核密度函数具有如下形式:， ， ， ， x x ， ， n l ti x x n ， ， i i ,1 d d d 222 h 2 h K X X , 2πh , 2πh (3) e ， ， e ， ， ， ， d ,h i 向量 LS g, t可以看作是给不同时刻映射到网格内的数， ， n i,1 d 据点赋不同的权重得到的加权累计值，总的权重D 是g , t 。 ， ， 定义 2 给定空间R 中的数据集X , X ,…, X 和简单分 n 1 2 n d 定义 5(网格数据重心) 令网格g 在 t时刻的数据重心为 n 箱函数族 WX ,, , J , j, j,…, j Z ，其中， , 为网， ， ， ， ,, J 1 2 d 向量 X g , t，则:， ， n 格 宽度，以: n X g , t, LS g , tD g , t(13) ， ， ， ， ， ， n n n N , WX ,, (4) ， ，J J i i,1 定理 5(网格数据重心不变性) 假设网格在时刻 t 或之前 l n 1 (5) X , N X ,, XW ， ， J J J i i 有数据到达，随后直 到t 时刻都没有数据到达，则网格数 据n i,1 重心保持不变，即:分别表示中心在g , j, , j, ,…, j, 点的网格所包含的数， ， j 12d 据 X g , t, X g, t(14) ， ， ， ， n l 点数和数据中心，称: 1 d定理 6 假设网格 g 在时刻 t有新数据到达，上一个数据 f X , nN K,(6) n ， ， X X X R ， ， J d ,h J dJ Z 的到达时刻为 t， t时刻的网格衰减平方和为SS g , t，网 ， ， l l l 为基于网格重心的分箱核密度估计。格平方衰减线性和为DS g , t，则 g 在 t的网格衰减平方和 ， ， l n [6] 定理 1设基核函数 K ,存在连续的二阶导数，则，， 公式为: 有: d 12 2 2 4 4 1 ˆ ,, ,,KK， , , (7) E d f f ? n ， ， ， ， ，， ，， ， ， ， hh R2， ， 2 t t n l ,(15) SS g, t , ， SS g, t ， X ， ， ， ， n l t n定d,理 1 表明基于网格重心的分箱核密度估计与逐点计算 , 网格平方衰减线性和公式为:的最优核密度估计相比，误差在可控的范围内，且与数据点 2t t ，，n l , , DS g t, ， DS g t， X (16) ， ， ， ， n l tn 数 n、网格宽度 , 有关。当n 较大且网格宽度 , 较小时， 定义 6(网格数据方差) 设 X, X ,…, X 是网格 g 在 t, , 1 2 m n分 时刻或之前到达的所有数据，令网g格 在 t时刻的数据方差 ˆ n 箱密度估计f 可以较好地拟合核密度估计f获 得满意的近似精度。对于数据流而言，以网格重心取代网格内离散数据2 点集合的分箱核密度估计方法需要进一步考虑数据演化对近 为 , g, t ，根据样本方差定义，结合时间演化衰减因素和， ， n 似误差的影响。也就是说随着数据流的演化过程，定理 1 描 定理 5，有: 述的误差界不应该发散。 2 m1 2 2 , g, t ,(17) , DX , t X X g , t ， ， ， ， ， ， n n i n i 3.2 演化数据流的统计特征 为了考查数据流的演化时间特i,1D g , t ， ， n ，， 征，捕获动态改变的信息， 定理 7 网格数据方差为: 计算机工 程48 2011 年 9 月 5 日 [7]1 人工合成数据集如图1( a)所示，包含4 个图形对象51 K 和2 , g, t, [SS g, t 2 , LS g , t， ， ， ， ， ， n n n 均匀分布的随机噪声6 KB，共 57 KB 的数据量。为了测试算n ,D g , t 2 ， ， DS g , t / D g , t ， LS g , t ， ， ， ， ， ， 法捕获数据演化过程的能力，4将 个图形对象依次排序生成， n n n 2 ,2 以 1 KB/s 的速率抵达。在 t1=6, t2=12, t3=23(单位为秒)绘制 (18) Dg, t / D g , t ]， ， ， ， ，， n n 核密度估计的二维等高线，如1图(b )~图 1(d)所示，图中清晰 定理 8(网格数据方差衰减性) 假设网格在时刻 t或之前 l 地呈现了演化的进程。 有数据到达，随后直 到t时刻都没有数据到达，则网格数 据n 方差随时间持续衰减，即:2 t t2 n l , g, t , ， , g , t (19) ， ， ， ， n l 定理 5 和定理8 表明，随着时间的推移网格内的历史数 据逐步衰减退化。在没有新数据到达的前提下，数据重心保 持不变而方差持续衰减，意味着演化数据向其重心不断倾斜。 因此，对于演化衰减数据流而言，以网格数据重心取代网格 内离散数据点集合的分箱核密度估计方法的近似误差是可控 (a)57 KB 数据分布 (b)t1=6 的核密度估计等高线 的，定理 1 描述的误差界不会发散。 3.3 算法实现 预处理将数据归一化为[0,1)区间，用连续的从0 开始的 1 维正整数依次代表d 维网格编号，将d 维网格存储在一颗 高度平衡的红黑树内，每个树节点表征一个网格。算法分在 线和离线计算两部分。假设在一个时刻只有一个数据到达， 在线部分将到达数据映射入对应网格树节点，维护一个网格 (c)t2=12的核 密度估计等高线 (d)t3=23的核 密度估计等高线 特征向量三元组< D g, t, LS g, t, t>，其中， t为上次更 ， ， ， ， n n l l 图 1 演化进程 新时刻。根据定理2 和定理 4，上述三元组可以通过简单的 动态刷新实现。离线部分在观测时间点以所有数据网格的重 为了考察算法的精度，在数据演化衰减的条件下，固定心为采样点进行单点重采样，基核函数为高斯函数，则每个 核函数窗宽=0.025，将在线计算的核密度估计结果与离线逐 网格在 t时刻的核密度公式为: n 点计算的核密度估计值进行比较，测量两者的均方误差: 2 40 000 1 ，t， n n， ， ， ， n ˆ CK X , D g , t , X X g , t ,MSE n ,X f X (22) f ， ，， ， ， ， ， ， ， ， ， ， ， ，， ， g n d ,h n 40 000 i,1 d 2K 12 x x g ,t ， ， ，， i i n 并得到图 2 的结果。可以看出M，SE 的值在 10数量级。随i,1 d 2(20) 2 h D g , t , 2πh e， ， ， ， n 着数据量的增加，维持在恒定的数值范围内。 多维演化数据流核密度估计计算公式为: ，t， ，t， n n (21) f X , CK X g, t D ， ， ， ， ， ，g n g Dg g Dg ， ， ， ， 其中， D g 为数据网格集合。， ， 有关噪声抑制策略参考文献[7]，其中定义了稀疏网格演 化为密度网格或密度网格退化为稀疏网格的最小时间 gap， 不再赘述。算法实现步骤描述如下: start_proceduret =0; 为数据网 格初始化红黑树; while 数 据流到达 do 读 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 X = ， x , x ,…, x ， ; 1 2 d 将 X 映射到网格 g; if(红黑树不包含g ) then 把 g 插入红黑树; 图 2 演化过程中均方误差测量精度 更新 g 的特征向量三元组; 5 结束语 if t mod gap==0 then 从红黑树中删除噪声网格; 核密度估计是统计学非参数估计理论中一类重要的实现， t ， if t mod 观测间隔==0 then 计算 f (X) ;技术，将其应用于数据流领域为进一步分析数据流行为提供 //观测间隔>gap 了坚实的基础。为了实现多维数据流快速处理的要求，本文 t=t+1;利用网格重心合并衰减数据点，提出动态维护网格时序的数 end while 据流核密度估计算法。另外，网格重心单点重采样技术虽然 end_procedur拥有一定的精度，但比较逐点最优核密度估计仍然存在系统 e 误差。如何针对数据流分布情况引入误差补偿机制，减少系 统误差以及将估计结果作为依据，并结合 DENCLUE 算法的 4 实验结果 思想实现数据流的密度聚类都是下一步研究的方向。 算法在主频2 GHz、内存 2 GB 的 Pentium E5200 PC 上 (下转第 60 页) 执行，操作系统Wi ndows XP SP2。编程语言c#. net2008，利 用 Matlab R2009b 作为图形用户接口。设置衰减因， 子= 0.998，网格宽度 , =0.05，核函数窗宽= , /2=0.025。采用 函数分别进行映射，每次得到的值V为[k ]，根据 V[k]将 Bloom 函数的个数取到最优时(本文算法中 Hash 函数个数取 Hash filter 中相对应的位置1 ，接收节点会进行相同的操作，将自4 )，Bloom Filter只需要取 到1 .44×n Byte 就能标识 n 个节点。 己的邻居列表里的 SP 的 IP 地址分别通过 k 和 Hash 函数进行 而基于链表结构的一致性分发报文的字节数近似于节点 映射，分别得到V [k]’，若发现Bloo m filter 中 V[k]’所对应的 的 位值全为 1，则认为该邻居已经接收到更新信息，若不全 0，为 4 倍。 则认为该邻居未接收到，便向该邻居转发更新消息。基于 Bloom filter 的一致性消息报文结构如1图 所 示。 „ 0 1 0 m ID Style Update Message 图 1 基于 Bloom filter的 一致性消息报文结构 前 m 位由简单的0 /1 组成的位数组，通过某几位同时为 1，来表示某个S P 的存在，m 由每次分发的节点个数n、要 求的假阳性错误概率e 和使用的 Hash 函数个数来共同决定。 ID 表示的是报文的发送者的全I网D 号。Style 表示更新消息 图 3 采用 Bloom filter与 传统链表结构的报文开销比较 的类型，仅用来发布全局资源知名度信息Updat。e Message 6 结束语 表示具体的更新消息内容。 本文研究了基于CD N 和 P2P 的流媒体网络中的资源知5 算法仿真 名度生成与分发算法，提出基于全局资源变化率的资源知名 实验利用 BRITE 生成器产生节点规模N= 150、平均度为 度生成算法与基于 Bloom filter 的一致性分发算法，能够较好 d=5 的底层P2 P 网络拓扑，所有节点的资源存放策略和热点 地反映现实网络的动态变化，估测误差较小，在报文的开销 程度均服从 Zipf 分布，系统更新周期设定为1 h 。图 2 为在 上远小于传统分发算法，降低了网络负担，为减少网络中节 节点规模N =150 的网络模型下，分别利用GA B 算法和本文 点间消息的冗余分发提供了保证。本文的资源知名度生成与 算法进行全局资源变化率的估测，其结果与实际变化率之间 分发算法还可应用于其他混合 P2P 网络及自组织网络的一致 的估测误差。可以看出，采用 GAB 算法进行资源知名度估测 性维护中，具有较好的实用性。 时，其误差是近似单调递增的，估计误差大于实际的变化 参考文献率， 所估计的资源知名度严重偏离实际的网络变化。而采 用本文 算法进行资源知名度估测时，整体的估测误差远小于 [1] 王煜坤. 基于 CDN 和 P2P 技术的流媒体系统 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 [J]. 现代计算 GAB 算法，且当网络的变化率小5于0% 时，其估测误差近似机: 专业版, 2009, (3): 179-181. 于 0。 Zaharia M, Keshav S. Gossip-based Search Selection in Hybrid [2] Peer-to-Peer Networks[C]//Proc. of IPTPS’06. Santa Barbara, USA: [s. n.], 2006. 王新生, 龚 华, 郭松梅, 等. 混合 P2P 系统中散播自适应算法 [3] 的改进[J]. 计算机工程, 2009, 35(6): 94-96. 施晓秋. 非集中式 P2P 系统中资源搜索与现存问题分析[J]. [4] 计算机工程, 2007, 33(5): 91-93. Saroiu S, Gummadi P K, Gribble S D. A Measurement Study of 图 2 本文算法与 GAB 算法的估测误差比较 [5] Peer-to-Peer File Sharing Systems[C]//Proc. of MMCN’02. 图 3 为采用传统的链表结构进行一 致性分发和采用 San Jose, USA: [s. n.], 2002. Bloom Filter 进行一致性分发的报文开销比 较。假设允许的最 编辑 顾姣健 大错误概率为 e，需要利用Bloo m Filter标 识 n 个节点，在 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (上接第 48 页) Streaming Data[C]//Proc. of Int’l Conf. on Management of Data. 参考文献 Delhi, India: [s. n.], 2006. Domingos P, Hulten G. Catching Up with the Data: Research [1] Boedihardjo A. A Framework for Estimating Complex Probability [5] Issues in Mining Data Streams[C]//Proc. of IEEE Workshop on Density Structures in Data Streams[C]//Proc. of the 17th ACM Research Issues in Data Mining and Knowledge Discovery. [S. l.]: Conf. on Information and Knowledge Management. Napa Valley, IEEE Press, 2001. USA: [s. n.], 2008. [2] 蔡春丽, 王惠玲, 孙延明. 进化数据流中基于密度的聚类算 [6] 李存华, 孙志挥, 陈 耿, 等. 核密度估计及其在聚类算法构法[J]. 计算机工程, 2009, 35(9): 57-59. 造中的应用[J]. 计算机研究与发展, 2004, 41(10): 1712-1719. Zhou Aoying, Cai Zhiyuan, Li Wei. M-Kernel Merging: Towards [3] Li Tu, Chen Yixin. Stream Data Clustering Based on Grid Density Density Estimation over Data Streams[C]//Proc. of the 8th Int’l [7] and Attraction[J]. ACM Transactions on Knowledge Discovery Conf. on Database Systems for Advanced Applications. Kyoto, Japan: [s. n.], 2003. from Data, 2009, 3(3): 12-14. Heinz C, Seeger B. Towards Kernel Density Estimation over 编辑 陈 文 [4]