负调查

项目源码

实验结果要求

模拟结果每一份分为如下几行:
第一行:正调查中每一选项对应人数比例
第二行:定项负调查算得结果
第三行:不定项的
第四行:定项方差(实验值)
第五行:不定项方差(实验值)
结果汇总到excel表格中
理论方差是直接算的
其中定项的可以按K选中不同的K多来几次
每一份在外面说明参与调查人数和选项个数
及正调查的比例生成方式(如均匀、正态、泊松、二项)
其中正态分布是连续的,可以按区间离散化,也可以用二项
泊松分布取前几个重新算一下比例就行

原理分析

定向负调查

基本模型moxing
$N$ 为总人数,$C$为选项个数。
$P_i$ 是正调查中选第$i$项的人数。
$R_i$ 是负调查中选第$i$项的人数。
k 是负调查中每个人选的选项个数。
$p_i$ 是正调查中选第$i$项的人数占总人数的比例。
$p_i = P_i \div N$
$\hat{p_i}$ 是正调查中选第$i$项的人数占总人数的比例的估计。

由于$N-P_i$个不选第$i$项的人无论选的是哪一项都不影响
1)他们负调查中选第i项的概率为 ${k \over C-1}$
2)他们各自的选择相互独立
所以 $R_i\sim{b(N-P_i,{k \over C-1})}$
所以 $E(R_i)=(N-P_i){k \over C-1}, D(R_i)=(N-P_i){k \over C-1}\left(1-{k \over C-1}\right)$
可知$\hat p_i$ 存在无偏估计 $\hat p_i=1-{(C-1)R_i \over Nk}$
$E( \hat p_i)=p_i, D(\hat p_i)={(C-1-k)(1-p_i) \over Nk}$
易知 $D_{1,kN} \ge D_{k,N}$

不定项负调查

$N$ 为总人数,$C$为选项个数。
$P_i$ 是正调查中选第$i$项的人数。
$R_{ij}$是负调查中在选$j$个负选项的条件下选第$i$个负项的人数。
$\lambda_j$是负调查中每个人选$j$个选项的概率。
$p_i$ 是正调查中选第$i$项的人数占总人数的比例。
$p_i = P_i \div N$
$\hat{p_i}$ 是正调查中选第$i$项的人数占总人数的比例的估计。

可以看出:
1) $R_{ij} \sim b(N-P_i, \lambda_j{j \over C-1})$ (*)
2) ${\sum_{i=1}^C R_{ij} \over j} \sim b(N, \lambda_j)$ (**)
所以由(**)式得
$\hat \lambda_j={\sum_{i=1}^CR_{ij} \over jN}$
$E(\hat\lambda_j)={1 \over N}N\lambda_j=\lambda_j$
$D(\hat\lambda_j)={1 \over N^2}N\lambda_j(1-\lambda_j)={1 \over N}\lambda_j(1-\lambda_j)$

每个用户选择负选项的个数k按指定概率分布即时生成($k \lt C-2$,k = C-1时认为隐私保护度为0,所以概率应设为0),将数据提交到服务器统计得到$R_i$数组
数据处理:先由公式$\lambda_j={\sum_{i=1}^C R_{ij} \over N \times j}={N_j \over N}$ 计算出$\lambda_j$ ,再由公式$\hat p_i=\sum_{j=1}^{C-2} \lambda_j(1-(C-1){R_{ij} \over \sum_{i=i}^CR{ij}})$ 计算出$\hat p_i$
注:$N_j$是选j个负选项的人数
理论方差如下:
mark

验证理论正确性

由中心极限定理:${\hat p_i-E(\hat p_i) \over \sqrt{D(\hat p_i)}}$近似服从$N(0,1)$
所以理论正确性的证明可以由置信区间有关理论给出
由正态分布表
mark
所以可以重复实验100次,统计对应量落在对应区间的次数,以验证理论正确性。

随机数算法

c: rand函数必须配合srand函数(以时间)“播种”,否则每次运行程序得到的都是相同的随机数。
需要注意的是用了srand后,第一次调用rand为所谓的“种子”,并非实际上的随机数,所以需要忽略第一次rand调用,之后才是真正的随机数
java就没这么多屁事了。。。

生成按照比例分布的随机数

算法如下

1
2
3
4
5
6
7
8
for(int i=1; i<C; i++){
usePossibility[i] = firstPossibility[i] + usePossibility[i-1];
}
double r = Math.random();
for(int i=0; i<C; i++){
if(r < firstPossibility[i]) return i;
}
return -1; //shouldn't reach here

注:firstPossibility为预设概率数组,包含被调查者选择每个选项的概率;

生成预设概率

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
public static void setFirstPossibility(int j, PossibilityK psbk, PossibilityN psbn){
if(j == 1){ //等差概率
for(int i=1; i<=C; i++){
firstPossibility[i]=2*(double)i/(double)(C*(C+1));
}
firstPossibility[0] = 1;
psbk.setFirstPossibility(firstPossibility);
psbn.setFirstPossibility(firstPossibility);
}
else if(j == 2){ //随机概率
double sum=0;
for(int i = 1; i <= C; i++){
firstPossibility[i] = (double)(int)(Math.random()*99+1);
sum += firstPossibility[i];
}
for (int i = 1; i <= C; i++){
firstPossibility[i] /= sum;
}
firstPossibility[0] = 1;
psbk.setFirstPossibility(firstPossibility);
psbn.setFirstPossibility(firstPossibility);
}
else if(j == 3){ //手动输入
System.out.print("输入1-C个正选项的概率:");
Scanner input = new Scanner(System.in);
double sum = 0;
for(int i = 1; i <=C; i++){
firstPossibility[i] = input.nextDouble();
sum += firstPossibility[i];
}
if(sum != 1){
System.out.println("预设概率之和不为一");
input.close();
return;
}
input.close();
firstPossibility[0] = 1;
psbk.setFirstPossibility(firstPossibility);
psbn.setFirstPossibility(firstPossibility);
}
else if(j == 4){ //均匀分布
for(int i = 1; i <=C; i++){
firstPossibility[i] = 1/(double)C;
}
firstPossibility[0] = 1;
psbk.setFirstPossibility(firstPossibility);
psbn.setFirstPossibility(firstPossibility);
}
else if(j == 5){ //泊松分布
double sum = 0;
for(int t=1; t<=C; t++){
int factorial = 1;
for(int i=1; i<=t; i++){
factorial *= i;
}
firstPossibility[t] = ((Math.pow(3, t) * Math.exp(-3)) / factorial);
sum += firstPossibility[t];
}
for(int i=0; i<C; i++){
firstPossibility[i+1] /= sum;
}
firstPossibility[0] = 1;
psbk.setFirstPossibility(firstPossibility);
psbn.setFirstPossibility(firstPossibility);
}
else if(j == 6){ //二项分布
double sum = 0;
for(int i=0; i<C; i++){
firstPossibility[i+1] = binomial(C, i, 0.5); //p = 0.5
sum += firstPossibility[i+1];
}
for(int i=0; i<C; i++){
firstPossibility[i+1] /= sum;
}
firstPossibility[0] = 1;
psbk.setFirstPossibility(firstPossibility);
psbn.setFirstPossibility(firstPossibility);
}
else if(j == 7){ //正态分布

firstPossibility[0] = 1;
psbk.setFirstPossibility(firstPossibility);
psbn.setFirstPossibility(firstPossibility);
}
}

R语言随机数生成函数

1
2
3
4
5
6
7
8
9
10
rnorm(n, mean=0, sd=1)   #正态分布
rexp(n, rate=1) #指数
rgamma(n, shape, rate=1, scale=1/rate) #r 分布
rpois(n, lambda) #泊松
rt(n, df, ncp) #t 分布
rf(n, df1, df2, ncp) #f 分布
rchisq(n, df, ncp=0) #卡方分布
rbinom(n, size, prob) #二项分布
rweibull(n, shape, scale=1) #weibull 分布
rbata(n, shape1, shape2) #bata 分布runif(n,min=0,max=1) #均匀分布

(虽然实验中并没有用到orz3333)

实验方法及部分源码

mark

不定项部分代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
public void setSecondLast2Possibility() {
if(firstPossibility[0] == 0){
System.out.println("未初始化预设概率");
return;
}
int key2=0; //用户的正选项索引
int key3; //随机生成负选项索引
// 收集数据
for(int i = 0; i < M; i++){
key2 = randomC[i];
secondPossibility[key2] += 1;
if(key2 == 0){
System.out.println("error!");
return;
}
//依概率分布随机选取n值
n = randomN[i];
int spy = n;
lambda_j[n-1] += 1;
//模拟不定项选
key3 = key2;
int[] keys = new int[n+1]; //虽然用户选择了n个负选项,但用于确定key3取值范围的keys容量还要加一个正选项
keys[0] = key3;
for(int m = 0; m < n; m++){
while(n_keyIn(key3,keys)){
key3 = (int)(Math.random()*10*C%C+1);
}
addKey(key3,keys);
R_ij[key3-1][n-1] += 1;
}
}
// 服务端数据处理
for(int i = 1; i <= C; i++){
secondPossibility[i] /= (double)M;
}
for(int i = 0; i < C-2; i++){
lambda_j[i] /= (double)M;
}
for(int j=0; j<C-2; j++){
for(int i=0; i<C; i++){
sum_R_ij[j] += R_ij[i][j];
}
}
for(int i=1; i<=C; i++){
for(int j=0; j<C-2; j++){
last2Possibility[i] += lambda_j[j]*(1-(C-1)*((double)R_ij[i-1][j]/(double)sum_R_ij[j]));
}
}
}

public void showDpossibility(){ //计算方差
double sum_lambda_j_2 = 0;
double sum_lambda_j_frac_j = 0;
for(int i=0; i<C-2; i++){
sum_lambda_j_2 += lambda_j[i] * lambda_j[i];
sum_lambda_j_frac_j += lambda_j[i] / (double)(i+1);
}
System.out.println("方差(理论值):");
for (int i = 1; i <= C; i++)
{
Dpossibility[i] = (1-sum_lambda_j_2+(1-last2Possibility[i])*((C-1)*sum_lambda_j_frac_j+sum_lambda_j_2-2)) / M;
System.out.print(Dpossibility[i]+"\t");
}System.out.println();
double DpossibilityN[] = new double[C+1];
System.out.println("方差(实验值):");
for (int i = 1; i <= C; i++)
{
DpossibilityN[i] = (last2Possibility[i] - secondPossibility[i]) * (last2Possibility[i] - secondPossibility[i]);
System.out.print(DpossibilityN[i]+"\t");
}System.out.println();
}

实验结果

单选负调查

mark

多选与不定项负调查

mark

验证理论正确性

mark

过程概要 & 结过分析

本发明的实验共包含7个实验程序开发测试阶段,每个阶段在一个程序中进行。

  1. 第一阶段(RandomNumberTest)为随机数测试,后面任意阶段若需要进行随机数的测试则集中在此测试程序中添加代码进行测试
  2. 第二阶段(Test1)为单选负调查使用概率叠加和矩阵求逆两种算法的测试,两种方法都能精准得估算出正选项的概率分布
  3. 第三阶段(Test2)为多选负调查测试,同样能准确的估计出正选项的概率分布
  4. 第四阶段(Test3)为不定项负调查测试,将选择数量的概率分布加入实验内容,同时添加了各种分布的预设概率框架
  5. 第五阶段(Test4)重构实验框架,合并定项负调查和不定项负调查,同时将选项和选择数量的随机数生成模块分离出来以便用同一组数据比较两种方法
  6. 第六阶段(Test5)将实验方差分配到每个选项,便于比较理论方差和实验方差,添加重复试验模块,发现实验方差平均值与理论方差十分接近,同时多选负调查的估算结果比定项负调查略为精确
  7. 第七阶段(Test5)添加代码运用中心极限定理重复试验严格验证理论正确性

结语

科创发明的理论及实验成果由本科创团队研究所得:朱友文教授负责项目指导,刘鼎铭负责数学理论研究及算法和公式的提出和初步实现,本人负责编写程序深入实验验证理论成果及梳理工作,李佳慧负责答辩内容小组讨论及联系导师等具体事宜,姚远忱负责答辩及专利申请书内容。

×

纯属好玩

扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦

文章目录
  1. 1. 项目源码
    1. 1.1. 实验结果要求
    2. 1.2. 原理分析
      1. 1.2.1. 定向负调查
      2. 1.2.2. 不定项负调查
      3. 1.2.3. 验证理论正确性
    3. 1.3. 随机数算法
      1. 1.3.1. 生成按照比例分布的随机数
      2. 1.3.2. 生成预设概率
      3. 1.3.3. R语言随机数生成函数
    4. 1.4. 实验方法及部分源码
    5. 1.5. 实验结果
      1. 1.5.1. 单选负调查
      2. 1.5.2. 多选与不定项负调查
      3. 1.5.3. 验证理论正确性
    6. 1.6. 过程概要 & 结过分析
    7. 1.7. 结语