基于唯一标识符的小范围均衡随机抽取方法

陈庆荣，陈明哲

（1.西安航空学院计算机学院，陕西西安710077；2.西安电子工程研究所陕西西安710100）

随着信息技术的快速发展，计算机技术在各方面的应用日趋广泛，各类应用系统在生产运营中起到了至关重要的作用，在这些应用系统中大量存在需要对候选数据进行随机抽取的操作。这些应用系统在进行随机抽取操作的设计时大多采用直接使用某种随机函数对候选数据进行抽取的方法[1]，这种对候选数据随机抽取的解决方法在候选数据量较大时基本可以保证抽取数据的均衡性，即每个候选数被抽中的次数基本相等。但是，当候选数据量较小时，使用这种方法进行候选数据的随机抽取会导致数据抽取的不均衡，即在候选数较少时某些候选数被多次抽中，而其他候选数没有被抽中或抽中次数较少的情况[2]。

本文通过对随机抽取方法的研究和分析，在进行小范围候选数随机抽取问题中提出了一种基于唯一标识符的小范围均衡抽取方法并加以实现，从而提高了小范围候选数随机抽取中抽取的均衡性并对此方法均衡性进行了分析测试。

1 基于唯一标识符的小范围均衡随机抽取方法

1.1 直接随机抽取方法

方法的数理逻辑描述如下：

则f为由H到G的函数，并记作

f:H→G。

抽取方法说明：有n（n＜100）个候选数据的集合H，要随机抽取其中的m（0＜m＜n）个数据生成结果集G，给集合H中的n个候选数据随机生成唯一标识符nid，从中取出前m个候选数生成结果集G。

1.2 基于唯一标识符的小范围均衡随机抽取方法

方法的数理逻辑描述如下：

定义

候选集H={h1，h2，…，hn}，

均衡系数η（0＜η＜1），

均衡抽取数s（0＜s＜m），

抽取唯一标识符集W={＜w1，w2，…，ws＞|w1，w2，…，ws∈H}，唯一标识符抽取函数f1是由有序偶组成的集。f1的定义域 dom（f1）是集

dom（f1）=H；

函数f1的值域 ran（f1）是集

ran（f1）=W；

则f1为由H到W的函数，并记作

f1:H→W。

定义

已抽数据记录集Y={＜y1，y2，…，yx|y1，y2，…，yx∈H}，已抽记录集抽取函数f2是由有序偶组成的集。f2的定义域dom（f2）是集

dom（f2）=H；

函数f2的值域 ran（f2）是集

ran（f2）=Y；

则f2为由H到Y的函数，并记作

f2:H→Y。

定义

抽取中间集Z={z1，z2，…，zi|z1，z2，…，zi∈H并且z1，z2，…，zi∉W}（i=m-s），抽取中间集函数f3是由有序偶组成的集。f3的定义域dom（f3）是集

dom（f3）=W-Y；

函数f3的值域 ran（f3）是集

ran（f3）=Z；

则f3为由H到Y的函数，并记作

f3:（W-H）→Z

定义

抽取结果集G={g1，g2，…，gm}，其中m＜n，则有G=W∪Z。

抽取方法说明：有n（n＜100）个候选数据的集合H，要随机抽取其中的m（0＜m＜n）个数据生成结果集G；首先设置均衡系数η（0＜η＜1）和均衡抽取数s（0＜s＜m），给集合H中的n个候选数据随机生成唯一标识符nid，并按此标识符排序，同时从中取出前s个候选数生成集合W，按照已抽取数据记录集中抽取的数据已被抽取次数倒排序后生成已抽取数据记录集Y，在集合Y中去除集合W中的所有元素并抽取前m-s个候选数生成抽取中间集合Z，最后抽取的结果集G为W∪Z。首次进行小范围随机抽取时只需设置均衡系数η=1，均衡收取数s=m，给集合H中的n个候选数据随机生成唯一标识符nid，并按此标识符排倒序，同时从中取出前s个候选数即可生成抽取集合G。

2 方法测试

2.1 测试系统及方法

测试系统基于Java EE企业级开发标准设计和开发，采用面向对象的程序设计分别实现了直接随机抽取和基于唯一标识符的小范围均衡抽取。

为了对比在小范围候选数中进行随机抽取的效果，系统可以设置候选数个数、每次抽取候选数个数、抽取次数等信息，可以分别选用直接随机抽取和基于唯一标识符的均衡抽取两种抽取方法，后者抽取前系统还需设置均衡系数，抽取结果分别存入数据库，并以图表的形式统计显示两种抽取方法抽取的结果，从而可以比较直观的对比两种抽取方法的均衡性优劣。

2.2 方法测试及结果分析

2.2.1 测试1

系统设置50个候选数，每次抽取5个，连续抽取5次，分别使用直接随机抽取方法和基于唯一标识符的小范围均衡抽取方法，将使用两种方法下被抽取的候选数进行统计并生成对应的统计图及统计表，分别如图1、表1、图2、表2所示。

2.2.2 测试2

系统设置50个候选数，每次抽取10个，抽取5次，分别使用直接随机抽取方法和基于唯一标识符的小范围均衡抽取方法，将两种方法下被抽取的候选数进行统计并生成统计图及统计表，分别如图3、表3、图4、表4所示。

2.2.3 结果分析

在以上设置的两种测试条件下，对相同测试数据按照直接随机抽取的方法和基于唯一标识符的小范围均衡随机抽取的方法得到的抽取结果统计分析可以得到以下结果。

图1 直接抽取结果统计图

表1 直接抽取结果统计表

图2 小范围均衡随机抽取结果统计图

表2 小范围均衡随机抽取结果统计表

图3 直接抽取结果统计图

表3 直接抽取结果统计表

图4 小范围均衡随机抽取结果统计图

表4 小范围均衡随机抽取结果统计图

测试1条件下，使用直接随机抽取的方法，50个候选数，未被抽中的候选数占总候选数的64%，候选数被抽中的最高频率为3。被抽中的25个候选数中，被抽取过1次的占48%，2次的占20%，3次的占4%。而基于唯一标识符的小范围均衡随机抽取方法，未被抽中的候选数占总候选数的54%，候选数被抽中的最高频率为2，被抽中的25个候选数中，被抽取过1次的占84%，2次的占8%。从数据分析可以看出，直接随机抽取方法未抽中的候选数和抽取的最高频率要高于基于唯一标识符的小范围均衡随机抽取方法；而基于唯一标识符的小范围随机抽取方法下被抽取过1次的候选数多于直接随机抽取方法。

测试2条件下，使用直接随机抽取的方法，50个候选数，未被抽中的候选数占总候选数的28%，候选数被抽中的最高频率为3，被抽中的50个候选数中，被抽取过1次的占50%，2次的占16%，3次的占6%。而基于唯一标识符的小范围均衡随机抽取方法，未被抽中的候选数占总候选数的2%，候选数被抽中的最高频率为2，被抽中的50个候选数中，被抽取过1次的占96%，2次的占2%。依据数据分析，直接随机抽取方法未抽中的候选数及抽取最高频率均高于基于唯一标识符的小范围均衡随机抽取的方法；而基于唯一标识符的小范围均衡随机抽取方法下被抽取过1次的候选数则明显多于直接随机抽取方法。

通过对测试1和测试2条件下，按照设定的抽取范围和抽取次数，使用直接随机抽取的方法抽取结束后两种测试情况下的数据分析均可看出候选数被抽中次数不均衡，且候选数中未被抽取到的情况较多；而通过对基于唯一标识符的小范围均衡随机抽取方法在两种测试情况下数据分析，抽取结束后候选数被抽中的次数较直接随机抽取均衡性改善很多，候选数未被抽到的情况大为减少，大部分候选数均可被抽到。

从实验数据范围、抽取次数及抽取结果的统计分析可以看出，在小范围候选数随机抽取时采用基于唯一标识符的均衡抽取方法得到的抽取结果的均衡性明显优于直接随机抽取的方法。同时在测试中，可以依据候选数的特点设置均衡系数以达到小范围数据随机抽取的均衡性达到在最优。

3 结束语

小范围候选数随机抽取是很多应用系统功能中需要实现的一项功能，直接使用各类随机数的方法直接来处理小范围数据的随机抽取问题，会因候选数据量较小导致随机数抽取均衡性较差，即就是某些候选数被抽中的次数明显多于其他候选数，导致随机抽取失去随机意义。通过均衡测试系统的验证可以看出：基于唯一标识符的小范围均衡随机抽取方法，利用设置均衡系数η及相关抽取集合依照此方法进行的相应变换，使得小范围候选数随机抽取的均衡性有了很大的改善，为小范围数据随机抽取提供了均衡性能良好的实用方法。