-
2019-04-28 17:46:46
设有A,B,C,D,E五人从事J1,J2,J3,J4,J5五项工作,每人只能从事一项,他们的效益如下。
每人选择五项工作中的一项,在各种选择的组合中,找到效益最高的的一种组合输出。
#include<stdio.h> #include<stdlib.h> int MansToJobs[6][6]={ {0,0,0,0,0,0}, {0,13,11,10,4,7}, {0,13,10,10,8,5}, {0,5,9,7,7,4}, {0,15,12,10,11,5}, {0,10,11,8,8,4} }; //前面代表人名,后面代表工作量 int TheBestResultOfDistribution[6]={0}; //选择时的临时储存 int BossWantIt[6]={0}; //最优解的储存和上面一样都是下标代表工作序号,内容代表工作者 int BestRecord=0,NowadayRecord=0; //工作总量储存:BestRecord是最优解的储存,NowadayRecord是临时储存 int search(int n){ //第几个人 int i,j; for(i=1;i<=5;i++){ //第几个工作 if(TheBestResultOfDistribution[i]==0){ //如果此工作没人干 TheBestResultOfDistribution[i]=n; //交给此人 NowadayRecord+=MansToJobs[n][i]; //记录工作总情况 if(n==5){ //如果已经有了5个选择 if(NowadayRecord>BestRecord){ //如果这一次的总工作量大于上一次记录的最多的 BestRecord=NowadayRecord; for(j=1;j<=5;j++) BossWantIt[j]=TheBestResultOfDistribution[j]; } }else search(n+1); TheBestResultOfDistribution[i]=0; NowadayRecord-=MansToJobs[n][i]; } } } int main(){ int i; search(1); for(i=1;i<=5;i++) printf("The job:%d give the guy:%d\n",i,BossWantIt[i]); printf("total:%d",BestRecord); system("pause"); return 0; }
更多相关内容 -
第五章-博弈论之组合拍卖(Combinatorial Auctions)
2019-02-26 17:54:22增加组合拍卖,Ascending Auctions,是组合拍卖的其中的一种拍卖方案,其基本流程为:平台公布各产品价格,这些产品的价格最初设定为零或者很小的值,并且投标人通过在 当前价格下对他们最愿意获得的商品集合 进行...【前言】最近几年,随着计算机学科的强势崛起,计算机这一学科逐渐的渗入到经济学中,以网络新经济学为代表的交叉学科开始走向舞台的中心。很多计算机网络方面的专家学者开始依靠博弈论解决在一定的规则下该网络中“用户最大化收益”的问题。当然,不仅仅是计算机网络,有很多其他方面的也有应用。就笔者本人来看,我们团队研究的就是依靠博弈论解决网络中用户的选择什么样的策略能够保证自己获得最大的收益,与此同时,该网络中的每个个体的收益都能同时达到最大化。组合拍卖就是博弈论中很经典的一种拍卖理论,那么组合博弈是什么呢?具体的应用场景是什么呢?有哪些核心的算法?如何保证博弈论中最经典的“纳什均衡”呢?下面我们就来一一了解。
1.组合拍卖的基本介绍
计算机科学的很大一部分以及经济学的很大一部分可能被视为解决“分配问题”,我们应该如何根据已有资源的不同可能用途进行分配。假设我们有一个不可分割的资源,两个玩家希望使用它,那么谁应该得到它?当然,这个问题用简单的拍卖理论就可以解决。那么继续拓展,如果有多个资源,并且多个资源之间可能存在依赖关系,那么对于青睐这些资源的用户而言,购买多个相互关联的资源的性价比可能要优于单独的购买一个资源,对于平台而言的话,也可能会利益最大化。那么,如何分配这一系列相互关联的资源就是一个问题了,组合拍卖就诞生了!
2.增价组合拍卖
增加组合拍卖,Ascending Auctions,是组合拍卖的其中的一种拍卖方案,其基本流程为:平台公布各产品价格,这些产品的价格最初设定为零或者很小的值,并且投标人通过在当前价格下对他们最愿意获得的商品集合进行竞标。然后,拍卖师通过以某种增价机制来反复更新用户间重叠产品的价格,直到达到所有投标人获得自己愿意获得的商品的集合为止,平台就公布最终的成交的价格和获胜投标者。这种拍卖方式很受欢迎,因为他可以使得用户和平台“双赢”。
3.增价组合拍卖的两种算法设计
(1)Ascending Item-Price Auctions
该种拍卖机制的主要流程是:每一个Item逐步增加其价格,保持暂定分配,直到另一个投标人暂停持有的Item为止。 直观地说,在这一点上,需求等于供给。
图1.Ascending Item-Price Auctions 算法流程设计 针对上述算法,存在了下面的例子,读者可根据该例子对算法进行具体的解析:
图2. 上述拍卖的典型例子 (2)Ascending Bundle-Price Auctions
该种拍卖机制的主要流程是:在该种拍卖方式中,用户最大化自己的利益是前提,多个想依赖的Item结合形成Bundle,用户青睐的是其中的一个Bundle,但是在具体增价的过程中还是以单个Item为基础进行增价,最终的流程参考一下算法:
图3.Ascending Bundle-Price Auctions算法设计 针对上述算法,存在了下面的例子,读者可根据该例子对算法进行具体的解析:
图4.Ascending Bundle-Price Auctions应用举例 上述问题增加的前提是用户都想利益最大化,想以最低的价格获取自己青睐的商品集,但是我们的机制设计是要满足尽可能多的用户的需求,故得到最终的结论。
4.写在最后
本文是题主主要研究博弈论,看到该部分内容的时候,觉得收获颇多。故再次将其展示与博客,为了让大家更多的了解博弈论的真面目,另外一方面也会在后来做该方面工作的时候可以继续去补充,希望能和大家共勉,一起去贡献出更精彩的博客!
注:文章内容引用列表:
1.Lavi R. Algorithmic game theory[J]. Computationally-efficient approximate mechanisms, 2007: 301-330.
题主只是一个入门的小学生,希望大家多多指教!如果该帖子确实能解决您的问题,望多多留言,谢谢!
-
详细总结组合排列的十余种算法实现
2020-02-10 22:37:51排列组合的问题,如果没有合适的算法去解决,时间复杂度会相当的大,毕竟阶乘的时间复杂度不仅让人头大,也让他计算机欲罢不能,而且我们遇到排列组合的相关问题的概率相当的大,所以非常有必要掌握...目录
•写在前面
排列组合的问题,如果没有合适的算法去解决,时间复杂度会相当的大,毕竟阶乘的时间复杂度不仅让人头大,也让他计算机欲罢不能,而且我们遇到排列组合的相关问题的概率相当的大,所以非常有必要掌握排列组合相关的算法,碰到很多问题,我们心里就有些底气了。我这里例举几种算法,其中想要特别强调二进制的相关解法,非常有趣。
•问题引入
我们把实际问题抽象一下,就是从一个集合中取出任意元素,形成唯一的组合。如 [a,b,c] 可组合为 [a]、[b]、[c]、[ab]、[bc]、[ac]、[abc]。我们既然说的是排列组合,当然就有区分这个集合里面,是否存在重复的元素的问题,如 [a,a,b,c] 可组合为 [a]、[b]、[c]、[ab]、[aa]、[bc]、[ac]、[abc]、[aab]等等。针对是否存在重复的元素问题,我们自然需要不同的解决方案,不过有些方法思路存在共性,接下来我们以不同算法为基础,结合不同的问题进行讲解,完成思路的理解(我们的重点是思路,有了思路,实现代码的时候就简单多了)。这里我们抛出一个问题,即如下
给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。 说明:解集不能包含重复的子集。 输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
我们先按照不含重复元素来进行思考,然后附上含重复元素的思路。
•暴力枚举
对于这种排列组合的问题,首先想到的当然是穷举。由于排列的要求较少,实现更简单一些,如果我先找出所有排列,再剔除由于位置不同而重复的元素,即可实现需求。假设需要从 [A B C D E] 五个元素中取出所有组合,那么我们先找出所有元素的全排列,然后再将类似 [A B] 和 [B A] 两种集合去重即可。当然,我们可以在枚举的时候进行一些剪枝,即在枚举个过程中进行一些判断,也可以当做一种优化。总结就是,逐个枚举,空集的幂集只有空集,每增加一个元素,让之前幂集中的每个集合,追加这个元素,就是新增的子集。还是不知道啥意思?没关系,我么来看思路和代码实现,这里我们分为两种枚举方式。
循环枚举
循环枚举的思路其实特别简单(暴力的思路就是人类的直觉,思路当然简单啦,哈哈哈),我们先创建结果集(res),然后往结果集里面添加一个空集,现在完成结果集的初始化之后(初始化的结果集中只有一个空集),我们开始在集合(nums)中开始循环遍历所有的元素,每次遍历一个元素,我们就把这个元素添加在当前结果集的每一个子集后,并形成新的子集,添加到结果集中,思路非常的简单暴力,代码吐下:
public static List<List<Integer>> enumerate(int[] nums) { List<List<Integer>> res = new ArrayList<List<Integer>>(); res.add(new ArrayList<Integer>()); for (Integer n : nums) { int size = res.size(); for (int i = 0; i < size; i++) { List<Integer> newSub = new ArrayList<Integer>(res.get(i)); newSub.add(n); res.add(newSub); } } return res; }
递归枚举
递归枚举的总体思路和循环枚举一致,只不过我们的实现方式是使用递归,代码的变化其实就是把循环枚举里面的最外面那层遍历集合(nums)的循环,使用递归来代替,很简单的,看代码你就明白了。
public static void recursion(int[] nums, int i, List<List<Integer>> res) { if (i >= nums.length) return; int size = res.size(); for (int j = 0; j < size; j++) { List<Integer> newSub = new ArrayList<Integer>(res.get(j)); newSub.add(nums[i]); res.add(newSub); } recursion(nums, i + 1, res); }
回溯枚举
回溯枚举就和上面的两种枚举思路有点不一样了,这种枚举思路就好像是我们人的思路,进行一个一个拼凑,只要符合我们子集的条件,就将这个子集添加进结果集,代码如下:
public static void backtrack(int[] nums, int i, List<Integer> sub, List<List<Integer>> res) { for (int j = i; j < nums.length; j++) { if (j > i && nums[j] == nums[j - 1]) continue; sub.add(nums[j]); res.add(new ArrayList<Integer>(sub)); backtrack(nums, j + 1, sub, res); sub.remove(sub.size() - 1); } }
•深度优先搜索
集合中每个元素其实就两种状态,就是选和不选,我们通过这两种状态,可以构成了一个满二叉状态树,比如,左子树是不选,右子树是选,从根节点、到叶子节点的所有路径,构成了所有子集。可以有前序、中序、后序的不同写法,结果的顺序不一样。本质上,其实是比较完整的中序遍历。我这样光说,可能比较抽象,我这里通过画的一张中序遍历的图进行讲解,如下。
前序遍历
public static void preOrder(int[] nums, int i, ArrayList<Integer> subset, List<List<Integer>> res) { if (i >= nums.length) return; subset = new ArrayList<Integer>(subset); res.add(subset); preOrder(nums, i + 1, subset, res); subset.add(nums[i]); preOrder(nums, i + 1, subset, res); }
中序遍历
public static void inOrder(int[] nums, int i, ArrayList<Integer> subset, List<List<Integer>> res) { if (i >= nums.length) return; subset = new ArrayList<Integer>(subset); inOrder(nums, i + 1, subset, res); subset.add(nums[i]); res.add(subset); inOrder(nums, i + 1, subset, res); }
后序遍历
public static void postOrder(int[] nums, int i, ArrayList<Integer> subset, List<List<Integer>> res) { if (i >= nums.length) return; subset = new ArrayList<Integer>(subset); postOrder(nums, i + 1, subset, res); subset.add(nums[i]); postOrder(nums, i + 1, subset, res); res.add(subset); }
•字典序
如果你足够理解了前面的思路,其实你应该会发现前面本质思路可以分为两类,暴力、递归、回溯一类,以及深度优先搜索一类,分类的依据是什么呢?其实就是思考的角度不一样,前面的那一类,我们思考的对象是每个子集,我们对每个子集进行相关算法的实现,而深度优先搜索开始,我们将关注的点放在集合(nums)中的每个元素的状态,我们集合中的每个元素在子集中只有两个状态,也就是存在和不存在。现在我们将关注的点转到了元素的状态上,即01状态,上面的深度优先搜索的实现只是一个过渡,本质上和递归等效率差不了多少,因为01状态是二进制的天下,我们自然使用二进制来代替,效率很高。利用二进制的思想去解决这个问题,就很简单了,值得一提的是,我们在使用二进制思想解决问题的时候,并不一定说使用位运算,而这里要讲的字典序,就不适用位运算来实现二进制思路。为了更好的理解思路,我们暂时先将问题简化为:
给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
算法其实非常的直观,不过有一个值得注意的是,我们在子集的最后需要放一个标志位(也就是所说的哨兵),在每次循环的时候,我们只要找到nums中的第一个满足 nums[j] + 1 != nums[j + 1]的元素,并将其加一nums[j]++ 以转到下一个组合。这种思想代替了位运算,完成了二进制的实现
public List<List<Integer>> combine(int n, int k) { LinkedList<Integer> nums = new LinkedList<Integer>(); for(int i = 1; i < k + 1; ++i) nums.add(i); nums.add(n + 1); List<List<Integer>> output = new ArrayList<List<Integer>>(); int j = 0; while (j < k) { output.add(new LinkedList(nums.subList(0, k))); j = 0; while ((j < k) && (nums.get(j + 1) == nums.get(j) + 1)) nums.set(j, j++ + 1); nums.set(j, nums.get(j) + 1); } return output; }
•二进制位运算
很多算法都能通过位运算巧秒地解决,其优势主要有两点:一者位运算在计算机中执行效率超高,再者由于位运算语义简单,算法大多直指本质。组合算法也能通过位运算实现,而且代码实现之后,简直令人回味无穷。我们将问题回归到最开始的问题,现在我们假设,从 M 个元素中取任意个元素形成组合,组合内元素不能重复、元素位置无关。我们使用状态的思想,对于每个元素来说,要么被放进组合,要么不放进组合。每个元素都有这么两种状态。我们这里举个例子,如果从 5 个元素中任意取 N 个元素形成组合的话,用二进制位来表示每个元素是否被放到组合里,就是:
每种组合都可以拆解为 N 个二进制位的表达形式,而每个二进制组合同时代表着一个十进制数字,所以每个十进制数字都就能代表着一种组合。十进制数字的数目我们很简单就能算出来,从00000... 到 11111... 一共有种,排除掉全都不被放进组合这种可能,结果有几种。
public List<List<String>> combination(String[] m) { List<List<String>> result = new ArrayList<>(); for (int i = 1; i < Math.pow(2, m.length) - 1; i++) { List<String> eligibleCollections = new ArrayList<>(); for (int j = 0; j < m.length; j++) { if ((i & (int) Math.pow(2, j)) == Math.pow(2, j)) { eligibleCollections.add(m[j]); } } result.add(eligibleCollections); } return result; }
当然,还想更秀操作一点,我们在第一和二层循环那里,使用位移运算,来完成与运算,本质是一样的,代码如下
public static List<List<Integer>> binaryBit(int[] nums) { List<List<Integer>> res = new ArrayList<List<Integer>>(); for (int i = 0; i < (1 << nums.length); i++) { List<Integer> sub = new ArrayList<Integer>(); for (int j = 0; j < nums.length; j++) if (((i >> j) & 1) == 1) sub.add(nums[j]); res.add(sub); } return res; }
当然,如果我们还有一种稍微绕一点点的二进制实现方式,就是数1的个数,这种思路有点绕,不过不管怎么样都还是二进制的一种实现方式,带着二进制的特色,我这里就大概的提一下数二进制中1的个数的实现方式,具体的问题解决代码,感兴趣的可以自己去实现以下,数二进制中1的个数的代码如下,想要关于数二进制的个数的其他算法,可以看我另一篇文章
int BitCount1(unsigned int n) { unsigned int c =0 ; // 计数器 for (c =0; n; n >>=1) // 循环移位 c += n &1 ; // 如果当前位是1,则计数器加1 return c ; }
•带重复数字
我们在集合中带有重复数字,这样的集合和不带重复数字有什么区别呢?我们按照这个思路,其实可以使用不重复数字的求解方式,在求解带重复数字集合的过程中,进行去重即可。有了这种思路,我们去设计算法其实就不难了,在暴力、递归、回溯、深搜的方法中,我们很容易的将算法进行改进,我在这里就不多提了,这里要说的是二进制的算法改进。你仔细想一下我们怎么样才能在二进制的算法中进行相应的去重,这其实不容易想到的。
我们来假设nums中有[1,2,3],那么它的结果集以及对应的二进制形如下面这这样
1 2 3 0 0 0 -> [ ] 0 0 1 -> [ 3] 0 1 0 -> [ 2 ] 0 1 1 -> [ 2 3] 1 0 0 -> [1 ] 1 0 1 -> [1 3] 1 1 0 -> [1 2 ] 1 1 1 -> [1 2 3]
但是如果有了重复数字,很明显就行不通了。例如对于 nums = [ 1 2 2 2 3 ]。
1 2 2 2 3 0 1 1 0 0 -> [ 2 2 ] 0 1 0 1 0 -> [ 2 2 ] 0 0 1 1 0 -> [ 2 2 ]
上边三个数产生的数组重复的了。三个中我们只取其中 1 个,取哪个呢?我们仔细想一下应该好想到,就是我们只要去重复数字的开头的序列就可以了,比如重复了三个2,那么我们只要分别取一个2开头即“2”,两个2开头即“22”以及三个2开头即“222”就可以了,这样就可以避免重复,更形象的解释,我们举个五个2的例子,然后例举出他们不重复的序列,像下面这样
2 2 2 2 2 1 0 0 0 0 -> [ 2 ] 1 1 0 0 0 -> [ 2 2 ] 1 1 1 0 0 -> [ 2 2 2 ] 1 1 1 1 0 -> [ 2 2 2 2 ] 1 1 1 1 1 -> [ 2 2 2 2 2 ]
那么这个时候,我们就可以将问题转成,我们怎么去取不同个数的2在一起,其实仔细思考也不难理解,我们只要对二进制稍微研究一下就知道了,我们先拿两个2来举例子,在五位二进制中,有两个2开头的二进制序列有哪些?
2 2 2 2 2 1 1 0 0 0 -> [ 2 2 ] 1 0 1 0 0 -> [ 2 2 ] 0 1 1 0 0 -> [ 2 2 ] 0 1 0 1 0 -> [ 2 2 ] 0 0 0 1 1 -> [ 2 2 ]
上面所有两个2的情况,我们只需要去其中一种,那么我们应该取哪种?怎么取呢?这个时候我们观察一下他们是否存在不同点,而且其中存在一个和其他情况都不同的形式,我们来看一下出现了重复数字,并且当前是 1 的前一个的二进位。
对于 1 1 0 0 0 ,是 1。 对于 1 0 1 0 0 , 是 0。 对于 0 1 1 0 0 ,是 0。 对于 0 1 0 1 0 ,是 0。 对于 0 0 0 1 1 ,是 0。
可以看到只有第一种情况对应的是 1 ,其他情况都是 0。其实除去从开头是连续的 1 的话,就是两种情况。第一种就是,占据了开头,类似于这种 10...1....。第二种就是,没有占据开头,类似于这种 0...1...。这两种情况,除了第一位,其他位的 1 的前边一定是 0。所以的话,我们的条件是看出现了重复数字,并且当前位是 1 的前一个的二进位。有了这种思路,我们只需要在不重复的代码中,进行一个判断就可以了,代码如下
public static List<List<Integer>> binaryBit(int[] nums) { List<List<Integer>> res = new ArrayList<List<Integer>>(); for (int i = 0; i < (1 << nums.length); i++) { List<Integer> sub = new ArrayList<Integer>(); boolean illegal=false; for (int j = 0; j < nums.length; j++) if (((i >> j) & 1) == 1) { if(j>0&&nums[j]==nums[j-1]&&(i>>(j-1)&1)==0){ illegal=true; break; }else{ sub.add(nums[j]); } } if(!illegal){ res.add(sub); } } return res; }
•总结
二进制是真的很美妙,我们的很多问题都可以通过二进制来解决,所以我们需要慢慢适应并融入二进制的世界,思考问题的角度和 思路也将变得更加开阔。
-
【差分隐私组合定理,直方图,列联表代码实现】差分隐私代码实现系列(五)
2021-12-06 16:44:02差分隐私代码实现系列(五)写在前面的话回顾差分隐私的属性(Properties of Differential Privacy)顺序组成(Sequential composition)平行组合(Parallel Composition)直方图(Histograms)列联表(Contingency ...差分隐私代码实现系列(五)
写在前面的话
书上学来终觉浅,绝知此事要躬行。
回顾
1、与 k k k-Anonymity不同,差分隐私是算法的属性,而不是数据的属性。也就是说,我们可以证明算法满足差分隐私。
2、随机函数 F F F中的随机性应该是"足够的",以便从 F F F观察到的输出不会揭示 x x x或 x ′ x' x′中哪一个是输入。
3、当 ϵ \epsilon ϵ越小时,数据效用越低,隐私保护程度越高;当 ϵ \epsilon ϵ越大时,数据效用越高,隐私保护程度越低。
4、普遍的共识是 ϵ \epsilon ϵ应该在1左右或更小,并且 ϵ \epsilon ϵ的值高于10可能对保护隐私没有多大作用 ,但这个经验法则可能会变得非常保守。
5、拉普拉斯机制不会拒绝被确定为恶意的查询,相反,它增加了足够的噪音,恶意查询的结果对对手毫无用处。
讲完了拉普拉斯,我们来看看差分隐私的组合定理~
差分隐私的属性(Properties of Differential Privacy)
由差分隐私的定义,所产生的差分私有机制的三个重要属性。
这些属性将帮助我们设计满足差分隐私的有用算法,并确保这些算法提供准确的答案。
这三个属性是:
1、顺序组成(Sequential composition)
2、平行组合(Parallel composition)
3、后处理(Post processing)
顺序组成(Sequential composition)
差分隐私的第一个主要性质是顺序组合,它限制了在同一输入数据上发布多个差私有机制结果的总隐私成本。
形式上,差分隐私的顺序组合定理说:
如果 F 1 ( x ) F_1(x) F1(x)满足 ϵ 1 \epsilon_1 ϵ1-差异隐私
并且 F 2 ( x ) F_2(x) F2(x)满足 ϵ 2 \epsilon_2 ϵ2-差分隐私
则释放两个结果的机制 G ( x ) = ( F 1 ( x ) , F 2 ( x ) ) G(x) = (F_1(x), F_2(x)) G(x)=(F1(x),F2(x))满足 ϵ 1 + ϵ 2 \epsilon_1+\epsilon_2 ϵ1+ϵ2-差分隐私。
顺序组合是差分隐私的重要属性,因为它可以设计出多次查阅数据的算法。
当对单个数据集执行多个单独的分析时,顺序组合也很重要。
因为它允许个人通过参与所有这些分析来约束他们产生的总隐私成本。
顺序组合给出的隐私成本的界限是一个上限,两个特定的差异隐私机制的实际隐私成本可能小于此,但永远不会比这个更大。
如果我们检查来自一个将两个差分隐私结果平均在一起的机制的输出分布,那么 ϵ \epsilon ϵ的"相加"原则是有意义的。
上例子!
import pandas as pd import numpy as np import matplotlib.pyplot as plt plt.style.use('seaborn-whitegrid') epsilon1 = 1 epsilon2 = 1 epsilon_total = 2 # satisfies 1-differential privacy def F1(): return np.random.laplace(loc=0, scale=1/epsilon1) # satisfies 1-differential privacy def F2(): return np.random.laplace(loc=0, scale=1/epsilon2) # satisfies 2-differential privacy def F3(): return np.random.laplace(loc=0, scale=1/epsilon_total) # satisfies 2-differential privacy, by sequential composition def F_combined(): return (F1() + F2()) / 2
如果我们绘制
F1
和F2
,我们会看到它们的输出的分布看起来非常相似。# plot F1 plt.hist([F1() for i in range(1000)], bins=50, label='F1'); # plot F2 (should look the same) plt.hist([F2() for i in range(1000)], bins=50, alpha=.7, label='F2'); plt.legend();
如果我们绘制F1
和F3
,我们看到输出的分布看起来F3
比F1
的分布**“更尖锐更瘦窄”**。# plot F1 plt.hist([F1() for i in range(1000)], bins=50, label='F1'); # plot F3 (should look "pointier") plt.hist([F3() for i in range(1000)], bins=50, alpha=.7, label='F3'); plt.legend();
因为它的 ϵ \epsilon ϵ越高,意味着隐私性越低,因此获得的结果与真实答案越相近。
如果我们绘制F1
和F_combined
,我们会看到输出F_combined
的分布较于F1
"更尖锐更瘦窄"。# plot F1 plt.hist([F1() for i in range(1000)], bins=50, label='F1'); # plot F_combined (should look "pointier") plt.hist([F_combined() for i in range(1000)], bins=50, alpha=.7, label='F_combined'); plt.legend();
这意味着它的答案比
F1
的答案更准确。虽然只是做了一个平均的操作,但是结果告诉我们它的 ϵ \epsilon ϵ必须更高(即它产生的隐私比 ) 要高。
那么F3
和F_combined
呢?回想一下,这两种机制的 ϵ \epsilon ϵ值是相同的 - 两者的 ϵ \epsilon ϵ均为 2。它们的输出分布应该看起来相同。# plot F3 plt.hist([F3() for i in range(1000)], bins=50, label='F3'); # plot F_combined (should look "pointier") plt.hist([F_combined() for i in range(1000)], bins=50, alpha=.7, label='F_combined'); plt.legend();
事实上,F3
看起来"更尖锐更瘦窄"!为什么会发生这种情况?请记住,顺序组合在几个版本的总 ϵ \epsilon ϵ上的上限,但是实际上对隐私的实际累积影响可能较低,并不与总 ϵ \epsilon ϵ上的上限效果一致。
在这种情况下,实际的隐私损失似乎略低于由顺序组合确定的上限 ϵ \epsilon ϵ。
总的来说顺序组合是控制总隐私成本的一种非常有用的方法,我们将看到它以许多不同的方式使用,但请记住,它不一定是一个确切的边界。
平行组合(Parallel Composition)
差分隐私的第二个重要性质称为并行组合。
并行组合可以看作是顺序组合的替代方案,第二种计算多个数据发布的总隐私成本边界的方法。
并行组合基于将数据集拆分为不相交的块,并在每个块上单独运行差异私有机制的想法。
由于块是不相交的,因此每个个体的数据只出现在一个块中 。因此,即使总共有 k k k块,该机制也会对每个个体的数据运行一次。
正式一点说:
如果 F ( x ) F(x) F(x)满足 ϵ \epsilon ϵ-差分隐私,我们将数据集 X X X拆分为 k k k不相交的块,使得 x 1 ∪ . . . ∪ x k = X x_1 \cup ... \cup x_k = X x1∪...∪xk=X
然后,释放所有结果的机制 F ( x 1 ) , . . . , F ( x k ) F(x_1), ..., F(x_k) F(x1),...,F(xk)满足 ϵ \epsilon ϵ-差分隐私
这是一个比顺序组合更好的绑定。由于我们运行 F F F k k k次,顺序组合会说此过程满足 k ϵ k\epsilon kϵ-差分隐私。
并行组合允许我们说总隐私成本只是 ϵ \epsilon ϵ。
正式定义与我们的直觉相匹配,如果数据集中的每个参与者都向 X X X贡献了一行,则此行将恰好出现在块之一 x 1 , . . . , x k x_1, ..., x_k x1,...,xk中。这意味着 F F F只会"看到"这个参与者的数据一次,这意味着 ϵ \epsilon ϵ的隐私成本适合该个人。由于此属性适用于所有个人,因此每个人的隐私成本为 ϵ \epsilon ϵ。
直方图(Histograms)
在我们的上下文中,直方图是对数据集的分析,该数据集根据其中一个数据属性的值将数据集拆分为"条柱",并计算每个条柱中的行数。
例如,直方图可能会计算数据集中达到特定教育水平的人数。
adult = pd.read_csv("adult_with_pii.csv") adult['Education'].value_counts().to_frame().head(5)
直方图对于差分隐私特别有趣,因为它们会自动满足并行组合。直方图中的每个"条柱"都由数据属性的可能值定义(例如,
'Education' == 'HS-grad'
)。单个行不可能同时具有属性的两个值,因此以这种方式定义条柱可以保证它们不相交。
因此,我们已经满足了并行组合的要求,并且我们可以使用差分私有机制来释放所有"条柱"计数,总隐私成本仅为 ϵ \epsilon ϵ。
epsilon = 1 # This analysis has a total privacy cost of epsilon = 1, even though we release many results! f = lambda x: x + np.random.laplace(loc=0, scale=1/epsilon) s = adult['Education'].value_counts().apply(f) s.to_frame().head(5)
列联表(Contingency Tables)
列联表或交叉制表(通常缩写为交叉表)就像一个多维直方图。
它计算数据集中具有特定值的行的频率,这些行一次具有多个属性。
在分析数据时,列联表经常用于显示两个变量之间的关系。
例如,我们可能希望查看基于教育水平和性别的计数:
关于pandas中crosstab的用法pd.crosstab(adult['Education'], adult['Sex']).head(5)
就像我们之前看到的直方图一样,数据集中的每个人都只参与此表中出现的一个计数。对于在构建列联表时考虑的任何一组数据属性,任何单个行都不可能同时具有多个值。
因此,在这里使用并行组合也是安全的。
python中的apply(),applymap(),map() 的用法和区别ct = pd.crosstab(adult['Education'], adult['Sex']) f = lambda x: x + np.random.laplace(loc=0, scale=1/epsilon) ct.applymap(f).head(5)
还可以生成包含 2 个以上变量的列联表。但是,请考虑每次添加变量时会发生什么:每个计数都倾向于变小。直观地说,当我们将数据集拆分为更多块时,每个块中的行数都会减少,因此所有计数都会变小。
这些缩小的计数会对我们从中计算出的差分隐私结果的准确性产生重大影响。
如果我们从信号和噪声的角度来考虑事物,那么大量的计数代表一个强信号,它不太可能被相对较弱的噪声(就像我们上面添加的噪声)干扰太多,因此即使在添加噪声之后,结果也可能是有用的。
然而,一小段计数代表一个微弱的信号,可能与噪声本身一样弱,并且在我们添加噪声后,我们将无法从结果中推断出任何有用的东西。
因此,虽然并行组合似乎为我们提供了"免费"的东西(以相同的隐私成本获得更多结果),但事实并非如此。
并行组合只是沿着不同的轴移动准确性和隐私之间的权衡,当我们将数据集拆分为更多块并发布更多结果时,每个结果都包含较弱的信号,因此准确性较低。
后处理(Post-processing)
这个想法很简单:通过以某种方式对数据进行后处理,不可能逆转差异隐私提供的隐私保护。
正式一点说:
如果 F ( X ) F(X) F(X)满足 ϵ \epsilon ϵ-差分隐私,则对于任何(确定性或随机化)函数 g g g, g ( F ( X ) ) g(F(X)) g(F(X))满足 ϵ \epsilon ϵ-差分隐私。
后处理属性意味着对差分私有机制的输出执行任意计算始终是安全的,不存在逆转该机制提供的隐私保护的危险。
特别是,可以执行后处理,这可能会减少噪声或改善机制输出中的信号。
例如,对于不应返回负结果的查询,将负结果替换为零。之前在差分隐私群里看到一个小伙伴弄电影评分的差分隐私,说是出现负数怎么办。就是利用后处理设为0就好,结果还是满足差分隐私的。
事实上,许多复杂的差分私有算法利用后处理来减少噪声并提高结果的准确性。
后处理属性的另一个含义是,差分隐私提供了对基于辅助信息的隐私攻击的抵抗力。
例如,函数 g g g可能包含有关数据集元素的辅助信息,并尝试使用此信息执行链接攻击。
后处理属性表示,无论 g g g中包含的辅助信息如何,此类攻击的有效性都受到隐私参数 ϵ \epsilon ϵ的限制。
总结
1、顺序组合给出的隐私成本的界限是一个上限,两个特定的差异隐私机制的实际隐私成本可能小于此,但永远不会比这个更大。
2、实际的隐私损失似乎略低于由顺序组合确定的上限 ϵ \epsilon ϵ。
3、如果数据集中的每个参与者都向 X X X贡献了一行,则此行将恰好出现在块之一 x 1 , . . . , x k x_1, ..., x_k x1,...,xk中。这意味着 F F F只会"看到"这个参与者的数据一次,这意味着 ϵ \epsilon ϵ的隐私成本适合该个人。由于此属性适用于所有个人,因此每个人的隐私成本为 ϵ \epsilon ϵ。
4、单个行不可能同时具有属性的两个值,因此以这种方式定义直方图中条柱可以保证它们不相交。
5、对于在构建列联表时考虑的任何一组数据属性,任何单个行都不可能同时具有多个值。因此,在这里使用并行组合也是安全的。
6、执行后处理,这可能会减少噪声或改善机制输出中的信号。
-
行测技巧:排列组合之“环形排列”问题
2021-01-30 18:33:34原标题:行测技巧:排列组合之“环形排列”问题在公考学习备考中排列组合一直是大家比较头疼的题目,很多同学在高中时就对这种题目望而却步,其实排列组合题目虽然比较难,但是这类题目却可以总结出多种不同的题型,... -
实验一 组合逻辑电路的设计与测试
2021-04-20 01:12:14目录一、实验预习要求二、实验目的三、实验原理四、实验设备与器件五、实验内容与步骤六、实验报告要求 一、实验预习要求 1、熟悉所用器件的引脚排列图。 2、根据实验内容要求设计出相应的组合逻辑电路,写出设计... -
组合关系和聚合关系.
2020-12-19 12:16:301组合关系和聚合关系浙江广播电视大学章一鸣(2004年10月14日)一、组合关系和和聚合关系的提出组合关系和聚合关系是现代语言学中的一个基本原理。《语言学纲要》上说:“符号和符号组合起来的关系称为符号的组合关系... -
《人机交互技术》 第五章 界面设计
2018-06-19 14:36:43第五章 界面设计 1.用户界面(第一版P58) 根据表现形式,用户界面可以分为命令行界面、图形界面和多通道用户界面。 命令行界面 Command Line Interface CLI 用户输入文本命令,系统以文本的形式表示对... -
组合、聚合、继承详解
2019-05-07 16:41:24大部分的初学者只知道java中两个类之间可以是继承与被继承的关系,可是事实上,类之间的关系大体上存在五种—继承(实现)、依赖、关联、聚合、组合。 接下来,简单的分析一下这些关系。 继承(实现) 对于类来说... -
机器学习中的数学(五):模型组合(Model Combining)之Boosting与Gradient Boosting
2019-06-12 20:08:58组合的方式很多,随机化(比如random forest),Boosting(比如GBDT)都是其中典型的方法,今天主要谈谈Gradient Boosting方法(这个与传统的Boosting还有一些不同)的一些数学基础,有了这个数学基础,上面的应用... -
重新认识java(四) — 组合、聚合与继承的爱恨情仇
2017-01-21 11:25:50有人学了继承,认为他是面向对象特点之一,就在所有能用到继承的地方使用继承,而不考虑究竟该不该使用,无疑,这是错误的。那么,究竟该如何使用继承呢? -
Java代码复用的三种常用方式:继承、组合和代理
2018-12-08 08:55:30这句话很通顺,没什么问题,但问题在于很多人并不清楚“复用”是什么。就好像我说“沉默王二是一个有趣的程序员”,唉,沉默王二是谁? 我们需要来给“复用”下一个定义。复用,说白了就是重复使用。 举个例子,... -
BRINSON理论 - 投资组合表现的决定因素
2019-01-31 11:34:57组合除了第五年相对于基准亏损17.86%,基本上在每年都能获得超额收益,最多的一年是第十年,获得了10.18%。 然后按照表3的计算方法,可以分别得到每年的择时(Timing)、股票选择(Security selection)和两者的... -
排列组合解析与例题总结
2017-07-27 17:44:06解:8人排前后两排,相当于8人坐8把椅子,可以把椅子排成一排.个特殊元素有A42种,再排后4个位置上的特殊元素丙有A41种,其余的5人在5个位置上任意排列有A55种,则共有种A42*A41*A55 一般地,元素分成多排的排列问题,... -
数字电路实验一 组合逻辑电路的设计预实验报告
2021-07-13 14:52:31数字电路实验一 组合逻辑电路的设计 ---用与非门74LS00,74...用74LS00和74LS20设计制作一个三人表决电路(即3个人中有2人及以上同意就通过)。请:a 写出真值表 b 化简 c 得出最简逻辑式,d 画出逻辑图。 思考... -
知识图谱第5享:公安五要素简介
2019-11-10 15:24:27混迹于公安行业的日子深深地记住了公安五要素:人、事、地、物、组织。近期,有同事对“公安行业五要素到底是什么”提出了疑问,于是,结合文献和经验认知梳理如下理解: 公安五要素,通常是指刑事案件的构成要素,... -
写给人类的机器学习 五、强化学习
2017-10-22 22:59:27五、强化学习 原文:Machine Learning for Humans, Part 5: Reinforcement Learning 作者:Vishal Maini 译者:飞龙 协议:CC BY-NC-SA 4.0 探索和利用。马尔科夫决策过程。Q 学习,策略学习和深度强化... -
组合最优化——期末总结
2019-12-25 00:20:441、组合最优化:又称为离散最优化通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等。可用数学模型表述为: min f(x) s.t. g(x)≥0, x ∈ D 2、组合最优化问题:在给定有限集合的所有具备某些特性... -
《快速掌握PyQt5》第十五章 组合框QGroupBox和工具箱QToolBox
2018-09-14 14:41:01第十五章 组合框QGroupBox和工具箱QToolBox 15.1 QGroupBox 15.2 QToolBox 15.3 小结 就跟分类一样,我们可以把相同的控件放在一起,也可以把达到某项功能所需要的一些控件放在一起等等,合理运用这两个控件可以... -
Python程序设计实验五
2020-11-21 02:53:21实验五Python组合数据类型一、实验目的(1)理解3类基本组合数据类型;(2)掌握列表的使用;(3)掌握字典的使用。二、实验内容1、随机密码生成。编写程序,在26个字母大小写和9个数字组成的列表中随机生成10个8位... -
算法基础:用递归解决排列组合问题
2018-03-19 21:43:59全排列的两种情况探索 关于全排列的问题,这次讨论两种情况 首先是第一种的不重复的全排列,例如将12345这个数字的所有排法全部...//六个国家,抽五个人 int a[6]={4,2,2,1,1,3} ; fd(a,0,ans,0,n); return 0; } -
软核科普系列:用python帮你建立自己的投资组合
2020-04-13 13:44:08听说金融量化很火,作为码农圈和金融圈的跨圈层...大部分人可能在主观上可以回答第一个问题,但对于每个资产的投资比例具体是多少,是否有一套可量化的方法在背后呢?码哥今天就带大家用python套用经典的马科维兹-均... -
K线形态识别—多K线之买入型多日K线组合
2021-11-16 09:43:52在使用低位连阳K线组合时要注意以下的要点: 低位连阳K线组合要求每根小阳线当天最大涨幅最好不超过3%,五根小阳线可以是横盘震荡排列,也可以略微向右上方倾斜。但不允许五根小阳线排列向右下方倾斜。 低位横盘止跌... -
【游戏开发实战】下载原神模型,PMX转FBX,导入到Unity中,卡通渲染,绑定人形动画(附Demo工程)
2021-11-17 09:14:483、卡通渲染 卡通渲染不像 PBR那样有标准流程和衡量准则,可以说卡通渲染是人们主观审美 + 现实环境抽象的结合,不同人对卡通渲染的理解理念不同,不过随着卡通渲染的不断发展,也形成了一套固定思路。 3.1、简单... -
【信息系统项目管理师】第二十一章 项目组合管理(考点汇总篇)
2019-03-01 10:22:30【信息系统项目管理师】第二十一章 项目组合管理(考点汇总篇) -
K线形态识别—三K线之买入型三日K线组合
2021-11-13 21:05:27一旦多方炮K线组合明显确认,不管是空仓者还是刚被震出仓者,均可立即半仓介人,另外半仓可以在该股的价格创出新高后再次介人。 四、平底镊子线 平底镊子线通常在股价下跌的底部区域出现,其K线组合的形状像把倒... -
组合数学——计数原理和计数公式
2018-02-26 19:30:25无重复的排列组合 排列 从nnn个不同元素中取m(m≤n)m(m≤n)m(m\leq n)个不同的元素,按照一定的顺序排成一列,叫做从nnn个不同元素取出的一个排列。 这个排列中没有重复元素,所以叫无重复的排列。记作AmnAnmA_... -
1.4怎样有效地找到组合特征?(机器学习面试)
2020-06-16 11:41:4104 组合特征 场景描述 上一节介绍了如何利用降维方法来减少两个高维特征组合后需要学习的参 数。但是在很多实际问题中,我们常常需要面对多种高维特征。如果简单地两两 组合,依然容易存在参数过多、过拟合等问题,... -
(转载)依赖、关联、聚合、组合
2018-09-06 16:26:57五、组合关系(Composition) 组合关系(Composition): 也是整体与部分的关系,但是整体与部分不可以分开. • 组合关系(Composition)也表示类之间整体和部分的关系,但是组合关系中部分和整体具有统一...