抽样算法范文（精选6篇）
抽样算法 第1篇
深海平台监测系统主要由数据采集、数据分析、数据处理及评价体系四部分组成, 从传感器网络上进行数据采集是系统最重要的部分。传感器网络上的应用对数据的管理与分析提出了新的要求, 例如可以处理连续查询, 快速响应用户查询等要求, 其本质是对流数据[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的数据定义为t i.x, 则该数据的数据变化率i为 (ti.x-ti-1.x) /ti-1.x|。
定义2数据平均变化率是指在一段时间里的数据变化率的平均值。t的时间跨度周期里的数据平均变化率为
定义3 skipping因子是基于数据平均变化率的函数。当数据流值变化很慢或变化不超过给定值ξ, 该时间段的元组标记值为true, 否则为false。skipping (t) 函数具体定义如下:
定义4数据的稳定度是指在一个数据集中, 稳定数据所占的比重, 即s=ds/da, 其中ds表示稳定的数据总量, da表示数据总量。
定义5相对近似误差是指从生成的概要数据里查询得出的结果相对从原始数据里查询得出的结果的误差。
定义6退避因子是基于数据平均变化率的函数。当数据变化超过一定值, 之后一段时间段将不计算其数据平均变化率。retreat (t) 函数定义如下:
以数据流S为例描述IWRS算法, 后面叙述用到的其他一些符号如表1所示。
当t时间跨度的数据到达时, 通过计算它的平均数据变化率来衡量数据流的变化剧烈程度, 根据skipping因子的值决定是否跳跃t时间跨度的数据项。其基本思想是, 若数据平均变化率不超过给定值, 则滑过这些元组。若数据平均变化率超过给定值, 则给这段数据项赋予相应的权值, 数据变化越快, 赋予的权值就越大。权值计算公式如下:
将权值作为数据项的键值, 键值计算公式如下:
则公式可以转化如下:
代入公式 (1) 可得:
算法1 IWRS算法具体如下:
输入:数据流S, T;
输出:概要数据集R;
(1) .将当前0到w个数据项加入到概要数据集中;
(2) .将当前概要数据集分为K个基本窗口 (s[0], s[1], …s[k-1]) , K=T/Δt;
(3) .计算每个基本窗口的平均数据变化率及权值wi;
(4) .计算每个基本窗口的键值xi;
(5) .i=w+1;
(6) .while i
(7) .j=i, 计算下一个Δt时间跨度数据平均变化率;
(9) .if skipping (Δt) ==true, 跳跃Δt个时间跨度段, goto第14步;
(10) .将Δt时间跨度的数据项读取到s[k];
(11) .查找所有基本窗口中键值最小的基本窗口, 假设最小键值为MIN;
(12) .计算Δt时间跨度的键值xi;
(13) .if xi>MIN-ε
将Δt时间跨度数据项替换最小键值的基本窗口;
(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, r取1。最后实验结果如图1和图2所示。
与PRS算法相比, 在数据变化比较稳定的时候, IWRS算法在保证正确性的情况下能较快的生成概要数据, 当监测到数据变化剧烈的时候, 该算法能动态改变抽样的方式, 生成概要数据的准确性比PRS算法高。而在深海平台监测系统等实际应用中, 剧烈变化的数据的准确性对数据分析很重要。因此, 该算法能很好的用在深海平台监测系统等实际应用中。
4 结论
本文总结和分析构建概要数据的几种抽样方法, 给出一种改进的加权随机抽样算法:IWRS算法。该算法解决了现有抽样算法生成的概要数据与原始数据偏离大小不确定以及数据稳定度低的时候生成概要数据效率不高问题。在深海平台监测系统等实际的应用中, 流数据变化时而缓慢, 时而剧烈, 该算法能根据这种变化特点动态的对数据进行抽样, 与其他抽样算法相比, 该算法效率高, 相对误差小。在实验的过程中, 退避因子的选取值对稳定度低的概要数据的生成有很大影响, 今后将进一步退避因子的选取问题。
参考文献
[1]BABCOCK B, BABU S, DATAR M, et al.Models and issues in data streams[C]//Proceedingsofthetwenty-firstACMSIGACT-SIGMOD-SIGA RT 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 the1998ACM 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 the2007ACM symposium on Applied computing.New York:ACM, 2007:453-456.
业务培训，引领人口抽样 第2篇
前期核查：火眼金睛查不同
只有开展高质量的培训，才能提高调查数据的质量。其中建筑物核实和小区图绘制工作布置会尤为关键。通常来说，这方面的年度变动不大，但并不能因此认为没有变化。区县人口抽样调查办公室要在布置会前将被抽中的调查小区的2010年《普查小区图》和2011年《调查小区图》收集到一起，并把其复印下来作为本年的《调查小区图底样》，通过比对，及时了解年度变化，以便更准确地把握被抽中调查小区的新动态。
随后，被抽中的社区组织人员需要根据下发的《建筑物变动清单》和《调查小区图底样》进行实地踏查，明确调查小区的边界范围。根据小区边界的变化、建筑物的增减变动及基本信息变化完成《调查小区图底样》与《建筑物变动清单》的核查修改。
后续培训：七十二变应万变
摸底、入户登记、编码等后续环节培训内容较为复杂，参训人员较多，因此相关培训在十月上旬进行较为合适。届时，可组织局队工作人员、指导员、调查员采取集中授课和分组研讨的方式，并配合考试测验，进行业务培训。
在讲解摸底工作任务、工作步骤的同时，笔者认为有三个方面的问题需要强调：一是调查员每进入一户，都需要巧妙地询问本户和邻居出生、死亡情况，避免出生、死亡人口的漏登等情况；二是要及时更新小区图，发挥地图效用，小区图的边界若与六普边界不一致则需要及时上报，由区人口抽样调查办公室实地勘察后再做决定。三是摸底收尾阶段，先由调查员自行查遗补漏，再以社区为单位采取“对比分析”和“经验分析”等方法，结合部门资料、普查数据和2011年度人口抽样调查数据进行分析评估。
一种基于遗传算法的数据抽样方法 第3篇
1 算法设计
通过贝叶斯分类器的数据实例过滤器算法，选择实例用抽样分类测试作实例子集的评价指标，使用数据集的子集构建分类器，对原始数据集随机抽样，选一个测试用子集，再使用该分类器对其测试，最后通过映射调整分类的正确率，作为子集的质量标准。本文使用最优保存遗传算法 (MOSGAS) ，可以证明[4]满足公式 (1) 的定义，即最优保存简单遗传算法具有全局收敛性。即可证明算法从任意状态出发，都收敛到最大值概率1，所以选用最优保存遗传算法作为数据抽样的搜索方法。
通过学习子集DS建立一个分类器函数CF后，建立随机测试集TS (大小为TSN) ，数据子集的质量f (DS) 表示为公式 (2) ， (3) 所示。公式 (2) 中的F函数是用来评价单个实例的分类效果， (3) 则是对F函数值进行统计的函数。
对原始数据集进行测试耗时巨大，所以随机抽取样本数据，抽样测试设定样本大小，方便控制运行时间，对抽样数据多次运行，保证数据测试结果更逼真。算法步骤如下： (1) 获取原始数据集; (2) 初始化种群; (3) 初始化当前世代的随机抽样测试样本; (4) 对当前种群中的个体进行评估; (5) 对评估值映射调整; (6) 保留最优秀个体; (7) 使用适应度比例方法选择个体，进行交叉联合和变异; (8) 判断是否达到结束条件，若没有则返回3; (9) 选择最优个体，返回数据子集。
2 实验结果和分析
在Weka系统上实现算法，使用UCI数据集验证。选取较大规模的数据集对算法进行测试验证。使用GAIS指代本算法。使用的数据集如表1所示。
把数据集分为中型和大型数据集。对中型数据集，做10%，30%，50%抽样构建分类器，以原始数据集测试，比较是否使用抽样算法的分类精度。分类性能比较的折线图如 (图1) 所示。
从图1看到，GAIS对中型数据进行抽样有良好性能，相对原始数据可保证分类精度不下降。3 0%和5 0%抽样的分类精度折线基本重合，即抽样基本等效。对大型数据集进行1%，3%，5%抽样，用原数据集建立分类器，进行10重交叉验证如图2所示。从图2看到，对大型数据集，使用极少样本可达到非常接近，甚至超出使用原始数据集的分类精度。这说明对大型数据集，选择一个最优的子集可以提高分类算法的效率和精度。
3 结论及展望
使用遗传算法进行搜索方法，随机抽样分类测试作为评价函数的实例过滤器算法，可以有效地降低数据集的规模，同时保证使用经过过滤的数据集建立的分类器的性能，比原始的数据集建立的分类器的性能要高。而且对于大部分数据集可有效地增加分类器的分类精度。
摘要：朴素贝叶斯分类器是一种基于独立假设的贝叶斯定理的简单概率分类器, 依靠精确的自然概率模型, 在有监督学习的样本集中能获取得非常好的分类效果。本文以朴素贝叶斯分类器为基础, 提出一种最优保存简单遗传算法为搜索方法, 随机抽样分类测试作为适应性函数来设计实现实例选择算法。实验表明, 该抽样方法在不降低朴素贝叶斯分类器精度的前提下明显降低计算代价, 对部分数据集还可有效地提高分类器的分类精度。
关键词：贝叶斯分类器,数据质量,实例选择,数据挖掘
参考文献
[1]I.H.Witten, E.Frank.董琳, 邱泉, 于晓峰等译.数据挖掘实用机器学习技术[M].北京:机械工业出版社, 2005.
[2]N.Friedman, M.Goldszmidt.Building Classifiers using BayesianNetworks.In proceedings of Thirteenth National Conference onArtificial Intelligence (AAAI) .VOL.2, 1996.pp.1277-1284.
[3]F.Ros, S.Guillaume, M.Pintore, J.R.Chretien.Hybrid genetic algo-rithm for dual selection.Springer London, 2007.
下半场,人口抽样上演 第4篇
知己知彼，赢得先机
顺义区李桥镇头二营村位于首都机场三号航站楼附近，机场周边的单位多且以本村租户为主。2010年10月中旬，当获知其即将拆迁的消息后，很多租户相继搬走。自2011年4月以来，仅一路之隔的马路对面即国门商务区又开始筹备建筑工程项目，冷清的村子一下子又热闹了起来。家家户户住满了施工队的工人，经常是小屋子里搭着一个大通铺，上下两层都住满了施工的工人。
2011年10月人口抽样调查摸底时，李桥镇头二营村调查户数从2010年的92户增加到200户，且大多是集体户。最大的一间院落被房主分割成60户，所住工人将近300人。由于房屋搭建格局的不合理，清点起来困难很大，尤其是需要登记两班倒的工人。因此，一天下来登记不了多少调查户，有时把一个调查户的情况都登记齐全至少也需要三四次。
创新方法，初战告捷
知己知彼后，为确保调查登记质量，摸底期间，顺义统计局相关领导和工作人员来到调查小区，与镇、村三级人员共同商讨对策并亲自挂帅。2011年11月2日上午，面对这一全区最大的调查小区，国家统计局顺义调查队队长张自林、顺义统计局副局长于淑萍率队到小区参加登记。
针对实际问题，顺义统计局队采取了四项措施。一是克服畏难情绪。此次进行入户调查的调查员大多为刚参加工作的“80后”姑娘，她们从未经历过如此复杂的调查环境，要想顺利完成入户调查工作就必须在心理上战胜难题。为此，局队领导几次进入调查小区，与调查员见面交谈，了解情况，让调查员感到区、镇两级领导就在自己身边。二是争取多方支持。争取市局领导的支持，人口处副处长岳卫红、普查中心副主任郭庚等同志都亲临调查现场指导入户登记工作；争取村委会的支持，村委会选调年轻的男同志作为陪调员，配合调查员入户登记；争取派出所和镇流动人口管理办公室的支持，他们提供流动人口的相关数据，并对重点院落进行治安管理；争取施工单位支持，找到工程项目负责人，再落实到各施工队的负责人，以配合入户登记工作和站点申报。三是组织有力的调查队伍。面对庞大的被调查对象，其他小区登记工作完成后，全部调查力量转入李桥镇调查小区进行统一调配。同时，区、镇两级人口抽样调查办公室选派最好的业务骨干进行现场指导，达到登一户，成功一户。四是创新工作方法。采取入户登记和设站登记相结合的方式，在工人人数较多的院落里设登记点，事先将各房屋进行编号，并张贴所编号码，将调查表内的主要问题发到各包工队负责人手中并向工人传达要调查的内容，然后由各屋的工人收齐屋内居住人员的身份证到登记点申报。
精锐尽出、战将列阵，戮力同心、创新方法……经过奋战，李桥镇头二营村第005调查小区共登记1090人、364户，其中家庭户278户，集体户86户。
网络测量中一种基于阈值的抽样算法 第5篇
1 阈值抽样方法
阈值抽样是一种流抽样方法,它针对的是大容量而且个体间差异比较大的情况下所采用的抽样方法。这种方法首先根据样本容量的大小和所有个体的性质计算出一个阈值,然后根据这个阈值来决定每个个体是否被选中,进而从样本空间来估计总体空间的一些统计量。阈值抽样不是一种基本的抽样方法,而且是偏倚抽样,即每个个体抽取的概率可能不同。具体地讲,xi表示个体i的大小,表示n个个体的大小,属性为x的个体被抽样的概率为p(x),z表示计算所得的阈值,那么
因此,阈值的选取是一个关键问题。在个数为n的总体空间中,目标样本空间大小为M,表示n个个体的大小,阈值与集合以及M的取值有关。样本个数的期望值,如果其中有一个z*,使得Nz*=M,那么z*就是我们想要的阈值。
该文采用求根算法[4]来求出等式Nz=M的解。定义,给定集合X={x1,…,xn}和目标样本量大小M,有,即是Nz为用阈值z从X中得到的抽样的期望值。我们的目标是找到z*=Z(X,M),使得。
注意到对于z≤min X,有Nz(X)=|X|,而且Nz(X)对于z≥min X严格递减。所以,假设M≤|X|,z*是唯一确定的。
我们的基本思想是选一些z,来比较Nz和M。
如果Nz=M,就得到z;
如果Nz
如果Nz>M,得z
如果z>z*,我们希望在X
为了定义递归,我们定义Nz(X,B)=B/z+Nz(X),也定义z*=Z(X,B,M)使得。那么Nz(X,0)=Nz(X),Z(X,0,M)=Z(X,M)。
如果B>0,Nz(X,B)在B>0时严格递增,所以z*总是唯一的。这个导致了下面
Z(X,B,M)唯一性的假设:B>0和M<|X|。
引理1[4]:如果Nz(X,B)
引理2[4]:如果Nz(X,B)>M,那么Z(X,B,M)=Z(X
上述原理在接下来的迭代算法中有具体应用,前提是B>0和M<|X|。
求根算法[4]如下:
假设B>0和M<|X|,
1)If X=∅,return B M.
2)任意选择一个z,满足z∈X,
如果阈值抽样的目的是抽取大流,式(1-1)中的个体x就可以表示为每个流字节大小,然后按照前面所述的算法求出所需的抽样率进行抽样。如果阈值抽样的目的是抽取小流(为了检测网络中的异常流量),这与阈值抽样的侧重抽取大流的初衷相悖。所以我们将流的分组数取倒数,将取倒数后得到的值作为个体x的属性值,这样抽样得到的是取倒数后得到的样本,其实就是原样本中的小流。除了加上取倒数这一步外,其他步骤(包括阈值的计算)都与原阈值抽样完全相同。而且,这样得到的小流样本量也会严格控制在原先给定的样本量内。
2 实验分析
该文将利用网络的实际流量数据对两种阈值抽样方法进行验证。首先是基于大流的阈值抽样方法进行验证。实验的数据来源于国内大学校园网(SMU Campus)互联网出口链路上在2008年4月24日生成的Netflow数据。这份数据中包含了76,764,321条流记录和2,638,589个源地址。我们以15分钟作为间隔,把一天的流数据按照时间序列分成96(24×4)份,对每份流数据分别根据两种抽样率1/512和1/1024计算阈值,每种抽样率在当天计算得出96个阈值。然后在相应的时间间隔内按照该阈值进行抽样。
现在我们来发掘当日流数据中流入目标IP主机流量最大的前200位主机。从抽样得到的样本流中,将目标IP地址相同的流记录合并,从而得知流量最大的目标IP主机。我们将得到的结果与抽样前的实际结果进行比较。
图1和图2是将流入目标IP主机流量的实际流量与阈值抽样后估计的流量进行比较的结果。横坐标轴表示了流量最大的前200名主机实际排列顺序,而纵坐标轴表示了通过阈值抽样后流量最大的前200名主机的排列顺序。图1和图2的区别是,图1的抽样率为1/512,图2的抽样率为1/1024。
图中的虚线表表示了±5%的误差上界和下界。显然,估计点越集中在对角线的两边,即分布在两个虚线中间,即表示估计得越准确。图1和图2中也可以看出抽样后流量排序估计过高了还是估计过低。对于给定的抽样率1/512或1/1024,落入Area I的点表示抽样后主机的流量排序名次估计过高了,即主机流量的实际排名小于抽样后的排名。同样,落入Area II的点表示抽样后主机的流量排序名次过低了,即主机流量的实际排名高于抽样后的排名。我们可以看到图1和图2很少有点落入Area I和Area II,表明了主机流量排名顺序在抽样后变化不大。
在这里,为了和阈值抽样比较,我们采用简单随机抽样抽样方法1/512和1/1024两种抽样率对同一数据进行抽样。图3和图4的分别显示了这种抽样方法的实验结果。由于抽样后结果相差比较大,我们只列出实际流量前120位抽样后的变化情况。
从图3和图4中可以看出,简单随机抽样后的结果明显不如阈值抽样,即使当抽样率为1/512。因此,基于大流的阈值抽样方法在抽样中抓住了更多的大流。
下面我们来通过实验验证基于小流的阈值抽样方法。我们用求根算法算出阈值抽样的阈值,再用阈值抽样抽取出样本,在这个样本上找出扫描主机。由Netflow产生的流数据中已经有包数这一项,所以我们抽样的属性就是包数。在本次实验中,我们分析了实际国内大学校园网(SMU Campus)互联网出口链路上2008年5月7日生成的Netflow数据,在这一天内,主机地址为192.168.2.48发动了对网段136.56.45.53到136.56.44.86的扫描。实验的具体过程如下,首先对这些数据进行抽样率为1/512的基于小流的阈值抽样。阈值抽样选出我们认为需要重点分析的数据,然后计算每个源IP地址的目标IP地址的熵和目标端口的熵,最后再对所得的熵进行排序。在这里,我们只需要知道那些熵较大的IP地址就很有可能是扫描主机,表1列出了IP地址的熵值最大的前9位主机。
从表1中,我们可以找出扫描主机的IP地址192.168.2.48,它的熵值较大,这也就说明我们的方法是有效的。IP地址192.168.2.48的熵在表格2-1中,正如我们期望的,因为扫描主机只扫描一个端口,所以对应端口的熵为0,然而对于与目标IP的熵却明显很大。熵最大的几台主机都有可能是扫描,而网络中本来就存在着正常扫描应用,如P2P应用等,但网络中的正常扫描连接的是多个IP地址对应着多个端口。在本次实验中,192.168.2.48这台主机扫描了很多IP地址,而只扫描一个端口,这就有可能是恶意扫描。通过这个实验可以看出即使是在抽样率1/512下,基于小流的阈值抽样也能观测到网络中的异常流量。
3 结束语
该文介绍了一种阈值抽样算法,并采用一种迭代方法来计算阈值,并用一步迭代加快收敛速度,求得一个满足的阈值z*。通过实验验证了阈值抽样的特点,即重视权重大的个体,同时也适当考虑权重小的个体比重。在获取网络中大流量主机方面,在同样抽样率条件下,阈值抽样比简单随机抽样有更高的准确性。阈值抽样另一个优点是能够有效的控制目标样本的容量M,在网络流量出现异常情况下能够提高资源的合理利用率。
摘要：在高速网络环境下,网络测量通常采用抽样技术。论文介绍了一种阈值抽样方法,根据不同的网络测量应用,选择不同的权重个体进行阈值计算,然后进行抽样。在阈值求解方面,介绍了一种求根算法,通过迭代方法来快速计算阈值。实验结果表明阈值抽样方法能够满足流量测量和网络安全检测两个方面的应用需求。
关键词：网络测量,抽样,端口扫描
参考文献
[1]Fang Wenjia,Larry P.Inter-AS Traffic Patterns and Their Implications[C]//Proceedings of IEEE GLOBECOM.USA:IEEE,1999:1859-1868.
[2]Cristian E,George V.New directions in traffic measurement and accounting[C]//Proceedings of the 2002 conference on Applications,technologies,architectures,and protocols for computer communications.New York:ACM,2002:323–336.
[3]Xu K,Zhang Z L,Bhattacharyya S.Profiling Internet Backbone Traffic:Behavior Models and Applications[C]//SIGCOMM'05:Pro ceedings of the 2005 conference on Applications,technologies,architectures,and protocols for computer communications.New York:ACM,2005:169-180.
谈谈抽样方案的设计与选择 第6篇
一、抽样方案的设计
例1从含有200个个体的总体中抽取10个人样。请用系统抽样方法抽取，并写出抽样过程。
思路分析：由于总体容量恰好能被样本容量整除，所以分段间隔k=200:10=20，可以按照系统抽样方法的四个步骤抽取样本。
解：第一步：将200个个体随机编号，编号为001，002，…，200。
第二步：将编号按顺序每20个为一段，分成10段。
第三步：在第一段001，002，…，020这20个编号中用简单随机抽样法抽出一个号码(如005)作为起始号码。
第四步：将编号为005，025，045，…，185的个体抽出，就组成了容量为20的样本。
解后反思：当总体容量较大，样本容量也较大时，宜采用系统抽样法抽样。本题是系统抽样方法的应用，要理解系统抽样的概念及方法，系统抽样抽取多少个个体就需要将总体分成多少段，不要把分段间隔与分组数相混淆。解题时要注意分隔间距应均匀，等间距分段且段数与样本数一致。
例2某市政府机关有在编人员100人，其中副处级以上干部15人，一般干部65人，工人20人。上级机关为了解政府机构改革的意见，要从中抽取一个容量为20的样本，用分层抽样的方法抽取样本，并写出过程。
思路分析：由于个体间存在较大差异，应采取分层抽样。分层抽样中各层要抽取的个体数与各层的个体数成比例，确定各层抽取的个体数之后，可采用简单随机抽样或系统抽样在各层中抽取个体。
解：(1)由于所取的个体差别较大，应采用分层抽样方法。
因为100:20=5，所以15:5=3，65:5=13，20:5=4。所以从副处级以上干部中抽取3人，从一般干部中抽取13人，从工人中抽取4人。
(2)副处级以上干部与工人人数较少，将他们分别按1～15编号与l～20编号，然后采用抽签法分别抽取3人和4人。
(3)对一般干部65人采用00，01，…，64编号，然后用随机数表法抽取13人。
这样就得到了容量为20的样本。
解后反思：本题采用分层抽样，根据个体的差异适当分层后，各层的选取将根据具体情况选择简单随机抽样或系统抽样。分层抽样中各层所取样本数与各层个体数之比都相等，要掌握好分层抽样的特点及适用范围。
二、抽样方法的选择
例3某公司甲、乙、丙、丁四个地区分别有150个、120个、180个、150个销售点。公司为了调查产品销售的情况，需从这600个销售点中抽取一个容量为100的样本，记这项调查为(1)；在丙地区中有20个特大型销售点，要从中抽取7个调查其收入和售后服务情况，记这项调查为(2)。则完成(1)。(2)这两项调查宜采用的抽样方法依次是()。
A.分层抽样，系统抽样
B.分层抽样，简单随机抽样
c.系统抽样，分层抽样
D.简单随机抽样，分层抽样
思路分析：因为样本来自甲、乙、丙、丁四个地区，地区的差异影响着销售量，所以(1)应采取分层抽样。因为总体数20较小且没有较大差别，样本容量为7也较小，所以(2)应采用简单随机抽样。
解：由上面分析，可知选B。
解后反思：本题是对抽样方法的选择和应用的考查，解题时要依据分层抽样和简单随机抽样的特点进行分析。简单随机抽样、系统抽样、分层抽样三种抽样的区别与联系一定要熟练掌握。解题过程中应注意语言叙述的完整性。
例4某县一中教职工140人，其中教师98人，教辅行政人员28人，总务后勤人员14人。教师节为参加县政府组织的座谈会，要从中抽取一个容量为20的样本。以下的抽样方法中，依次是简单随机抽样，系统抽样，分层抽样顺序的是()。