基于唯一標(biāo)識(shí)符的小范圍均衡隨機(jī)抽取方法

陳慶榮，陳明哲

（1.西安航空學(xué)院計(jì)算機(jī)學(xué)院，陜西西安710077；2.西安電子工程研究所陜西西安710100）

隨著信息技術(shù)的快速發(fā)展，計(jì)算機(jī)技術(shù)在各方面的應(yīng)用日趨廣泛，各類應(yīng)用系統(tǒng)在生產(chǎn)運(yùn)營(yíng)中起到了至關(guān)重要的作用，在這些應(yīng)用系統(tǒng)中大量存在需要對(duì)候選數(shù)據(jù)進(jìn)行隨機(jī)抽取的操作。這些應(yīng)用系統(tǒng)在進(jìn)行隨機(jī)抽取操作的設(shè)計(jì)時(shí)大多采用直接使用某種隨機(jī)函數(shù)對(duì)候選數(shù)據(jù)進(jìn)行抽取的方法[1]，這種對(duì)候選數(shù)據(jù)隨機(jī)抽取的解決方法在候選數(shù)據(jù)量較大時(shí)基本可以保證抽取數(shù)據(jù)的均衡性，即每個(gè)候選數(shù)被抽中的次數(shù)基本相等。但是，當(dāng)候選數(shù)據(jù)量較小時(shí)，使用這種方法進(jìn)行候選數(shù)據(jù)的隨機(jī)抽取會(huì)導(dǎo)致數(shù)據(jù)抽取的不均衡，即在候選數(shù)較少時(shí)某些候選數(shù)被多次抽中，而其他候選數(shù)沒有被抽中或抽中次數(shù)較少的情況[2]。

本文通過對(duì)隨機(jī)抽取方法的研究和分析，在進(jìn)行小范圍候選數(shù)隨機(jī)抽取問題中提出了一種基于唯一標(biāo)識(shí)符的小范圍均衡抽取方法并加以實(shí)現(xiàn)，從而提高了小范圍候選數(shù)隨機(jī)抽取中抽取的均衡性并對(duì)此方法均衡性進(jìn)行了分析測(cè)試。

1 基于唯一標(biāo)識(shí)符的小范圍均衡隨機(jī)抽取方法

1.1 直接隨機(jī)抽取方法

方法的數(shù)理邏輯描述如下：

則f為由H到G的函數(shù)，并記作

f:H→G。

抽取方法說明：有n（n＜100）個(gè)候選數(shù)據(jù)的集合H，要隨機(jī)抽取其中的m（0＜m＜n）個(gè)數(shù)據(jù)生成結(jié)果集G，給集合H中的n個(gè)候選數(shù)據(jù)隨機(jī)生成唯一標(biāo)識(shí)符nid，從中取出前m個(gè)候選數(shù)生成結(jié)果集G。

1.2 基于唯一標(biāo)識(shí)符的小范圍均衡隨機(jī)抽取方法

方法的數(shù)理邏輯描述如下：

定義

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

均衡系數(shù)η（0＜η＜1），

均衡抽取數(shù)s（0＜s＜m），

抽取唯一標(biāo)識(shí)符集W={＜w1，w2，…，ws＞|w1，w2，…，ws∈H}，唯一標(biāo)識(shí)符抽取函數(shù)f1是由有序偶組成的集。f1的定義域 dom（f1）是集

dom（f1）=H；

函數(shù)f1的值域 ran（f1）是集

ran（f1）=W；

則f1為由H到W的函數(shù)，并記作

f1:H→W。

定義

已抽數(shù)據(jù)記錄集Y={＜y1，y2，…，yx|y1，y2，…，yx∈H}，已抽記錄集抽取函數(shù)f2是由有序偶組成的集。f2的定義域dom（f2）是集

dom（f2）=H；

函數(shù)f2的值域 ran（f2）是集

ran（f2）=Y；

則f2為由H到Y(jié)的函數(shù)，并記作

f2:H→Y。

定義

抽取中間集Z={z1，z2，…，zi|z1，z2，…，zi∈H并且z1，z2，…，zi?W}（i=m-s），抽取中間集函數(shù)f3是由有序偶組成的集。f3的定義域dom（f3）是集

dom（f3）=W-Y；

函數(shù)f3的值域 ran（f3）是集

ran（f3）=Z；

則f3為由H到Y(jié)的函數(shù)，并記作

f3:（W-H）→Z

定義

抽取結(jié)果集G={g1，g2，…，gm}，其中m＜n，則有G=W∪Z。

抽取方法說明：有n（n＜100）個(gè)候選數(shù)據(jù)的集合H，要隨機(jī)抽取其中的m（0＜m＜n）個(gè)數(shù)據(jù)生成結(jié)果集G；首先設(shè)置均衡系數(shù)η（0＜η＜1）和均衡抽取數(shù)s（0＜s＜m），給集合H中的n個(gè)候選數(shù)據(jù)隨機(jī)生成唯一標(biāo)識(shí)符nid，并按此標(biāo)識(shí)符排序，同時(shí)從中取出前s個(gè)候選數(shù)生成集合W，按照已抽取數(shù)據(jù)記錄集中抽取的數(shù)據(jù)已被抽取次數(shù)倒排序后生成已抽取數(shù)據(jù)記錄集Y，在集合Y中去除集合W中的所有元素并抽取前m-s個(gè)候選數(shù)生成抽取中間集合Z，最后抽取的結(jié)果集G為W∪Z。首次進(jìn)行小范圍隨機(jī)抽取時(shí)只需設(shè)置均衡系數(shù)η=1，均衡收取數(shù)s=m，給集合H中的n個(gè)候選數(shù)據(jù)隨機(jī)生成唯一標(biāo)識(shí)符nid，并按此標(biāo)識(shí)符排倒序，同時(shí)從中取出前s個(gè)候選數(shù)即可生成抽取集合G。

2 方法測(cè)試

2.1 測(cè)試系統(tǒng)及方法

測(cè)試系統(tǒng)基于Java EE企業(yè)級(jí)開發(fā)標(biāo)準(zhǔn)設(shè)計(jì)和開發(fā)，采用面向?qū)ο蟮某绦蛟O(shè)計(jì)分別實(shí)現(xiàn)了直接隨機(jī)抽取和基于唯一標(biāo)識(shí)符的小范圍均衡抽取。

為了對(duì)比在小范圍候選數(shù)中進(jìn)行隨機(jī)抽取的效果，系統(tǒng)可以設(shè)置候選數(shù)個(gè)數(shù)、每次抽取候選數(shù)個(gè)數(shù)、抽取次數(shù)等信息，可以分別選用直接隨機(jī)抽取和基于唯一標(biāo)識(shí)符的均衡抽取兩種抽取方法，后者抽取前系統(tǒng)還需設(shè)置均衡系數(shù)，抽取結(jié)果分別存入數(shù)據(jù)庫(kù)，并以圖表的形式統(tǒng)計(jì)顯示兩種抽取方法抽取的結(jié)果，從而可以比較直觀的對(duì)比兩種抽取方法的均衡性優(yōu)劣。

2.2 方法測(cè)試及結(jié)果分析

2.2.1 測(cè)試1

系統(tǒng)設(shè)置50個(gè)候選數(shù)，每次抽取5個(gè)，連續(xù)抽取5次，分別使用直接隨機(jī)抽取方法和基于唯一標(biāo)識(shí)符的小范圍均衡抽取方法，將使用兩種方法下被抽取的候選數(shù)進(jìn)行統(tǒng)計(jì)并生成對(duì)應(yīng)的統(tǒng)計(jì)圖及統(tǒng)計(jì)表，分別如圖1、表1、圖2、表2所示。

2.2.2 測(cè)試2

系統(tǒng)設(shè)置50個(gè)候選數(shù)，每次抽取10個(gè)，抽取5次，分別使用直接隨機(jī)抽取方法和基于唯一標(biāo)識(shí)符的小范圍均衡抽取方法，將兩種方法下被抽取的候選數(shù)進(jìn)行統(tǒng)計(jì)并生成統(tǒng)計(jì)圖及統(tǒng)計(jì)表，分別如圖3、表3、圖4、表4所示。

2.2.3 結(jié)果分析

在以上設(shè)置的兩種測(cè)試條件下，對(duì)相同測(cè)試數(shù)據(jù)按照直接隨機(jī)抽取的方法和基于唯一標(biāo)識(shí)符的小范圍均衡隨機(jī)抽取的方法得到的抽取結(jié)果統(tǒng)計(jì)分析可以得到以下結(jié)果。

圖1 直接抽取結(jié)果統(tǒng)計(jì)圖

表1 直接抽取結(jié)果統(tǒng)計(jì)表

圖2 小范圍均衡隨機(jī)抽取結(jié)果統(tǒng)計(jì)圖

表2 小范圍均衡隨機(jī)抽取結(jié)果統(tǒng)計(jì)表

圖3 直接抽取結(jié)果統(tǒng)計(jì)圖

表3 直接抽取結(jié)果統(tǒng)計(jì)表

圖4 小范圍均衡隨機(jī)抽取結(jié)果統(tǒng)計(jì)圖

表4 小范圍均衡隨機(jī)抽取結(jié)果統(tǒng)計(jì)圖

測(cè)試1條件下，使用直接隨機(jī)抽取的方法，50個(gè)候選數(shù)，未被抽中的候選數(shù)占總候選數(shù)的64%，候選數(shù)被抽中的最高頻率為3。被抽中的25個(gè)候選數(shù)中，被抽取過1次的占48%，2次的占20%，3次的占4%。而基于唯一標(biāo)識(shí)符的小范圍均衡隨機(jī)抽取方法，未被抽中的候選數(shù)占總候選數(shù)的54%，候選數(shù)被抽中的最高頻率為2，被抽中的25個(gè)候選數(shù)中，被抽取過1次的占84%，2次的占8%。從數(shù)據(jù)分析可以看出，直接隨機(jī)抽取方法未抽中的候選數(shù)和抽取的最高頻率要高于基于唯一標(biāo)識(shí)符的小范圍均衡隨機(jī)抽取方法；而基于唯一標(biāo)識(shí)符的小范圍隨機(jī)抽取方法下被抽取過1次的候選數(shù)多于直接隨機(jī)抽取方法。

測(cè)試2條件下，使用直接隨機(jī)抽取的方法，50個(gè)候選數(shù)，未被抽中的候選數(shù)占總候選數(shù)的28%，候選數(shù)被抽中的最高頻率為3，被抽中的50個(gè)候選數(shù)中，被抽取過1次的占50%，2次的占16%，3次的占6%。而基于唯一標(biāo)識(shí)符的小范圍均衡隨機(jī)抽取方法，未被抽中的候選數(shù)占總候選數(shù)的2%，候選數(shù)被抽中的最高頻率為2，被抽中的50個(gè)候選數(shù)中，被抽取過1次的占96%，2次的占2%。依據(jù)數(shù)據(jù)分析，直接隨機(jī)抽取方法未抽中的候選數(shù)及抽取最高頻率均高于基于唯一標(biāo)識(shí)符的小范圍均衡隨機(jī)抽取的方法；而基于唯一標(biāo)識(shí)符的小范圍均衡隨機(jī)抽取方法下被抽取過1次的候選數(shù)則明顯多于直接隨機(jī)抽取方法。

通過對(duì)測(cè)試1和測(cè)試2條件下，按照設(shè)定的抽取范圍和抽取次數(shù)，使用直接隨機(jī)抽取的方法抽取結(jié)束后兩種測(cè)試情況下的數(shù)據(jù)分析均可看出候選數(shù)被抽中次數(shù)不均衡，且候選數(shù)中未被抽取到的情況較多；而通過對(duì)基于唯一標(biāo)識(shí)符的小范圍均衡隨機(jī)抽取方法在兩種測(cè)試情況下數(shù)據(jù)分析，抽取結(jié)束后候選數(shù)被抽中的次數(shù)較直接隨機(jī)抽取均衡性改善很多，候選數(shù)未被抽到的情況大為減少，大部分候選數(shù)均可被抽到。

從實(shí)驗(yàn)數(shù)據(jù)范圍、抽取次數(shù)及抽取結(jié)果的統(tǒng)計(jì)分析可以看出，在小范圍候選數(shù)隨機(jī)抽取時(shí)采用基于唯一標(biāo)識(shí)符的均衡抽取方法得到的抽取結(jié)果的均衡性明顯優(yōu)于直接隨機(jī)抽取的方法。同時(shí)在測(cè)試中，可以依據(jù)候選數(shù)的特點(diǎn)設(shè)置均衡系數(shù)以達(dá)到小范圍數(shù)據(jù)隨機(jī)抽取的均衡性達(dá)到在最優(yōu)。

3 結(jié)束語

小范圍候選數(shù)隨機(jī)抽取是很多應(yīng)用系統(tǒng)功能中需要實(shí)現(xiàn)的一項(xiàng)功能，直接使用各類隨機(jī)數(shù)的方法直接來處理小范圍數(shù)據(jù)的隨機(jī)抽取問題，會(huì)因候選數(shù)據(jù)量較小導(dǎo)致隨機(jī)數(shù)抽取均衡性較差，即就是某些候選數(shù)被抽中的次數(shù)明顯多于其他候選數(shù)，導(dǎo)致隨機(jī)抽取失去隨機(jī)意義。通過均衡測(cè)試系統(tǒng)的驗(yàn)證可以看出：基于唯一標(biāo)識(shí)符的小范圍均衡隨機(jī)抽取方法，利用設(shè)置均衡系數(shù)η及相關(guān)抽取集合依照此方法進(jìn)行的相應(yīng)變換，使得小范圍候選數(shù)隨機(jī)抽取的均衡性有了很大的改善，為小范圍數(shù)據(jù)隨機(jī)抽取提供了均衡性能良好的實(shí)用方法。