一种改进的加权随机抽样算法

摘要 为了构建传感器网络流数据的概要数据，给出一种改进的加权随机抽样算法：IWRS算法。该算法根据流数据变化的快慢程度，动态的对流数据加权，将权值做为数据项的键值，根据键值大小、skipping 因子、退避因子对流数据进行抽样，解决了现有的抽样算法生成的概要数据与原始数据偏离大小不确定以及数据稳定度低的时候生成概要数据效率不高问题。并将该算法应用到深海平台监测系统中，与其他抽样算法相比，该算法在数据变化稳定的情况下能快速的生成概要数据，当监测到数据变化剧烈时，动态改变抽样方式，抽取的概要数据精确性高。

关键词 流数据；概要数据；skipping因子；IWRS算法；退避因子

中图分类号 TP 302.1文献标识码Adoi:10.3969/j.issn.1003-6970.2011.01.004

An improved weighted random sampling algorithm

LIU Chang 1TANG Da 1

1(Computer Science and Technology School, Dalian University of Technology, Dalian 116023，China)

【Abstract 】To obtain the synopsis data of the data stream from the sensor networks, this paper provides an improved weighted random sampling algorithm:IWRS algorithm. A weight is assigned to data item dynamically acording to the change of data stream, and a key is assigned for each data item by its weight, then sample with the key,the skipping factor and retreat factor. This algorithm solves the problems of uncertain deviation between the original data and the sample data and the efficiency is low when the data is unstable. Finally, this algorithm is applied to Deep Sea Platform Monitoring System. Compared with other sampling algorithms, this method can produce synopsis data quickly when the data is stable,and change the sampling method dynamically when the data changes rapidly to decrease relative errors.

【Key words】data stream; synopsis data; skipping factor; IWRS algorithm; retreat factor

0 引言

深海平台监测系统主要由数据采集、数据分析、数据处理及评价体系四部分组成，从传感器网络上进行数据采集是系统最重要的部分。传感器网络上的应用对数据的管理与分析提出了新的要求，例如可以处理连续查询，快速响应用户查询等要求，其本质是对流数据[1]进行管理和分析。流数据是连续的、无界和随时间变化的。数据流上的查询通常是连续运行的，当新数据到达时增量式地返回结果，即长时间运行的、连续的、持久的查询。流数据的特点决定了其分析技术通常只能是一次处理,其算法应是单遍扫描(one-pass)。由于存储容量的有限性,不可能完整地保存全部流数据元素。在深海平台监测系统中,用户并不需要获得精确的查询值,仅仅需要一个近似结果即可。考虑设计一个远小于原数据流规模的结构,保存已流过数据的概要特征,方便数据流的查询及分析。因此,概要数据结构(synopsis data structure)[2]的设计成为数据流技术的热点研究问题之一。

1 概要数据构建技术

常用的概要数据构建技术包括抽样技术(sampling)[3,4]、直方图技术(histogram)[5]和小波技术(wavelet)[6]。直方图技术只能反应数据的分布特征，有些需要多次扫描数据集,不适合于数据流的查询，小波技术相对复杂，抽样方法是从数据集中抽取小部分数据代表整个数据集，并根据该样本集合获得查询结果。深海平台监测系统实时性高，且需要对历史数据进行查询，因此，抽样技术适合该系统。目前主要存在三种不同的抽样算法及其研究现状：

均匀抽样(uniform sampling)：数据集中各元素以相同的概率被选取到样本集合中。Vitter[3]提出水库抽样方法，令样本集合的容量为S，在任一时刻n,数据流中的元素都以S/n的概率被选取到样本集合中去。如果样本集合大小超出S，则从中随机去除一个样本。可以证明，各元素的入选几率相同。Gibbons[4]等人提出精确抽样方法，对于仅出现一次的元素，类似于水库抽样，仍然用元素代码表示；而对于多次出现的元素，则利用结构〈value, count〉表示，精确抽样方法比水库抽样方法更节约空间。

偏倚抽样(biased sampling)：不同元素的入选几率可能不同。Gibbons[4]等人提出计数抽样方法，该算法是精确抽样方法的一个变种，区别在于样本集合溢出时处理方式不同，能有效地获得数据集中的热门元素列表。

综合抽样：将均匀抽样和偏倚抽样结合起来。Efraimidis[7]等人认为均匀抽样以相同的概率对数据流中到达的数据元组进行随机抽样，没有考虑数据元组可能有不同重要性的情况。该文献改进了水库抽样算法，给出了加权抽样（Weighted Random Sampling）算法。Zhang Longbo[8]等人通过改进加权抽样算法,结合基本窗口技术，提出优先数随机抽样算法（PRS）,根据数据的权值和到达时间，计算其优先数，并根据优先数的大小决定其是否进入样本集以及样本集中被替换的数据元组，算法能够有效地处理过期数据元组问题。Hou Wei[9]等人在周期抽样的基础上提出一种针对多个相关数据流的概要数据生成算法，该算法在某种程度上能够防止多个数据流之间的多次连接操作，提高了抽样的效率。

上述算法没有考虑流数据的变化特点，其中加权抽样算法能根据数据重要性进行抽样，但需要用户赋予数据一定的权值。在深海平台监测系统中，用户并不知道什么时候到来的数据重要，也就无法给这些数据赋予准确的权值，因此，抽取的概要数据与原始数据偏离大小不确定。通过计算数据的平均变化率在数据稳定度低的时候，算法的效率不高，为解决上述两个问题，本文给出一种改进的加权随机抽样算法:IWRS（Improved Weighted Random Sampling）算法，该算法根据时间序列数据流在不同时刻变化快慢程度，动态对流数据进行抽样，并且在数据变化剧烈的时候根据退避因子计算退避时间，在退避时间内部不计算数据的变化率，提高了抽样的效率。

2 IWRS算法

定义1数据变化率是某个元组相对于其相邻元组变化的大小。在时刻i的数据定义为 ，则该数据的数据变化率 为 。

定义2数据平均变化率是指在一段时间里的数据变化率的平均值。 的时间跨度周期里的数据平均变化率为 。

定义3skipping因子是基于数据平均变化率的函数。当数据流值变化很慢或变化不超过给定值 ，该时间段的元组标记值为true,否则为false。 函数具体定义如下:

定义4数据的稳定度是指在一个数据集中，稳定数据所占的比重，即 ，其中 表示稳定的数据总量， 表示数据总量。

定义5相对近似误差是指从生成的概要数据里查询得出的结果相对从原始数据里查询得出的结果的误差。

定义6退避因子是基于数据平均变化率的函数。当数据变化超过一定值，之后一段时间段将不计算其数据平均变化率。 函数定义如下：

以数据流 S为例描述IWRS算法，后面叙述用到的其他一些符号如表1所示。

当 时间跨度的数据到达时，通过计算它的平均数据变化率 来衡量数据流的变化剧烈程度，根据skipping因子的值决定是否跳跃 时间跨度的数据项。其基本思想是，若数据平均变化率不超过给定值，则滑过这些元组。若数据平均变化率超过给定值，则给这段数据项赋予相应的权值，数据变化越快，赋予的权值就越大。权值计算公式如下：

算法1IWRS算法具体如下：

输入：数据流S，T；

输出：概要数据集R；

(1).将当前0到 个数据项加入到概要数据集中；

(2).将当前概要数据集分为K 个基本窗口（s[0], s[1],…s[k-1]）， ；

(3).计算每个基本窗口的平均数据变化率 及权值 ；

(4).计算每个基本窗口的键值 ；

(5). ；

(6).while,重复步骤7-14；

(7). , 计算下一个 时间跨度数据平均变化率 ；

(8).if！=0

while ( )

j = j + 1；

重复10-13；

(9).if，跳跃 个时间跨度段，goto第14步；

(10).将 时间跨度的数据项读取到s[k]；

(11).查找所有基本窗口中键值最小的基本窗口，假设最小键值为MIN；

(12).计算 时间跨度的键值 ；

(13).if

将 时间跨度数据项替换最小键值的基本窗口；

(14).i = j + 1；

3 相关算法比较

目前面向带权值数据流上的随机抽样算法中，Zhang Longbo[8]等人提出了PRS算法，它在WRS算法的基础上进行了改进，该算法相对WRS算法提高了效率和精确度。但该算法随机生成权值，并根据权值大小进行抽样，因此，生成的概要数据与原始数据偏离大小不确定。本文给出的IWRS算法能自动监测流数据变化的快慢程度，动态改变抽样的方式，在实际的应用中，生成的概要数据精确度比PRS算法高，当数据稳定度低时采用退避方法，可以有效的提高效率。

在仿真实验中对PRS算法, IWRS算法所用时间，准确性进行了比较。测试环境为:操作系统 Windows XP, Dual-Core CPU:2.6GHz Pentium 4 PC,内存 1G。分别使用六种数据集D1,D2,D3,D4,D5,D6，其中D1的稳定度为0，D2的稳定度为10%，D3的稳定度为25%,D4的稳定度为50%，D5的稳定度为75%，D6的稳定度为100%。在PRS算法中用 random(0,10)分别为每个数据元组生成一个随机数作为其权值,然后分别在每个数据集上运行两种算法,最后求其算术平均值。在每次实验过程中数据总量为3万，抽取的样本的数量为5000，并使用固定的数据流速， 取0.0001， 取0.002， 取1。最后实验结果如图1和图2所示。

图1算法所用时间的比较

Fig. 1Comparison of efficiency

图2算法相对误差的比较

Fig. 2Comparison of accuracy

与PRS算法相比，在数据变化比较稳定的时候，IWRS算法在保证正确性的情况下能较快的生成概要数据，当监测到数据变化剧烈的时候，该算法能动态改变抽样的方式，生成概要数据的准确性比PRS算法高。而在深海平台监测系统等实际应用中，剧烈变化的数据的准确性对数据分析很重要。因此，该算法能很好的用在深海平台监测系统等实际应用中。

4 结论

本文总结和分析构建概要数据的几种抽样方法，给出一种改进的加权随机抽样算法：IWRS算法。该算法解决了现有抽样算法生成的概要数据与原始数据偏离大小不确定以及数据稳定度低的时候生成概要数据效率不高问题。在深海平台监测系统等实际的应用中，流数据变化时而缓慢，时而剧烈，该算法能根据这种变化特点动态的对数据进行抽样，与其他抽样算法相比，该算法效率高，相对误差小。在实验的过程中，退避因子的选取值对稳定度低的概要数据的生成有很大影响，今后将进一步退避因子的选取问题。

参考文献

[1] BABCOCK B, BABU S, DATAR M, et al. Models and issues in data streams[C]//Proceedingsofthetwenty-firstACMSIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. New York: ACM, 2002:1-16.

[2] GIBBONS P B, MATIAS Y. Synopsis data structures for massive data sets [J]. Dimacs Series in Discrete Mathematics and Theoretical Computer Science, 1999:39-70.

[3] VITTER J S. Random sampling with a reservoir[J].ACM Trans on Mathematical Software, 1985, 11(1): 37-57.

[4] GIBBONS P B, MATIAS Y. New sampling-based summary statistics for improving approximate query answers [C]//Proceedings of the 1998 ACM SIGMOD international conference on Management of data. New York: ACM, 1998:331-342.

[5] GIBBONS P B, MATIAS Y,POOSALA V.Fast incremental maintenance of approximate histograms [J]. ACM Transactions on Database Systems, 2002, 27(3): 261-298.

[6] MATIAS Y,VITTER J S,WANG M.Wavelet-based histograms for selectivity estimation [J]. ACM SIGMOD Record, 1998, 27(2):448-459.

[7] EFRAIMIDIS P S ,SPIRAKIS P G. Weighted random sampling with a reservoir [J]. Information Processing Letters, 2006, 97(5):181~185.

[8] ZHANG Longbo, LI Zhanghuai, ZHAO Yiqiang, et al. A priority random sampling algorithm for time-based sliding windows over weighted streaming data[C]//Proceedings of the 2007 ACM symposium on Applied computing. New York: ACM, 2007:453-456.

[9] HOU Wei, YANG Bingru, WU Chensheng, et al. RedTrees: A relational decision tree algorithm in streams [J]. Expert Systems with Applications, 2010, 37(9):6265-6269.

作者简介: 刘畅(1986－),男,硕士研究生,主要研究领域为数据流管理系统;唐达(1961－),男,在读博士生,副教授,主要研究领域为数据流管理系统.

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文

2011年《软件》物联网的关键理论与技术专题内容:

1. 物联网体系结构理论与模型：层次化可扩展的物联网体系结构、物联网中网元的异构系统互连模型、网络动态行为机理模型、物联网性能评价体系及度量模型等；

2. 物联网网络融合与自治机理理论与技术：面向IP体系演进的网络融合及命名与寻址架构、面向Post-IP的融合网络体系架构、物联网自治域内数据汇聚与交换技术、物联网自治区域动态管理；

3. 物联网信息整合与交互的理论和方法：不确定信息整理与融合理论、网元之间信息交互模型和方法；

4. 物联网软件建模理论与设计方法：面向物联网典型应用的软件建模和分析技术、面向物联网的软件编程模型及其支撑平台技术、支持物联网信息编程模型的中间件平台技术；

5. 物联网服务提供机理和方法：物联网的服务模型、物联网服务需求的多维获取、形式规约与动态演化、物联网服务动态构建及适配机理技术、服务质量的动态保障方法；

6. 物联网的安全与隐私技术：物联网信息交互的隐私保护方法、基于安全多方计算的物联网隐私保护技术、物联网安全体系架构、物联网信息的完整性、机密性技术、物联网元的容侵容错协议；

7. 物联网应用系统技术：基于物联网的相关“感知”技术，如智能电网技术、智能交通技术、智能建筑技术等。

8. RFID自动识别技术：包括安全测评指标体系、基准测试床、符合性测试方法、攻击性测试方法、安全绩效评估方法等。

来稿注明“物联网专题”， 录用后免收版面费。 欢迎踊跃投稿 ：