论文研究-支持工作者位置隐私保护的众包质量控制模型.pdf

所需积分/C币:6 2019-09-20 20:02:09 833KB .PDF

论文研究-支持工作者位置隐私保护的众包质量控制模型.pdf,  新兴的基于位置众包,为了任务质量控制,要求工作者提交任务结果时向发布者公开位置信息.大量位置隐私的暴露,会增大工作者遭受攻击的风险.本文针对众包系统,提出基于空间和时间维度的模糊化方法,明显增加攻击者所获信息的不确定性,从而达到保护工作者位置隐私的目的.通过理论分析及实验测试,证明模糊化方法不会造成发布者质量控制能力的显著下降.
第8期 初翔,等:支持工作者位置隐私保护的众包质量控制模型 2049 时间模糊方法在移动通讯、传感设备等领域有着广泛的研究冏,然而这些成果无法直接应用于众包系统,第 3节将沿用现有方法的原理提出适用于众包系统的模糊化方法. 22众包质量控制 考虑一个典型的众包场景,称之为派对( party):1名任务发布者( requester)发布了m个众包任务(task) T(1≤i≤m),m名工作者( worker);(1≤j≤m)参与任务完成每个任务由m名工作者完成,每名工 作者完成m个任务,但同一任务一名工作者只完成一次.以矩阵Vmn={}表示工作者们提交的所有任 (vx=1)或者“否”(=0).二元模型上的研究结论不难扩展并应用于其它任务类型少∽,只需回答“是” 务结果,Vnx1={v;}表示每个仟务的正确结果.为简化问题,不妨假设T均为二元问题, 众包的质量控制问题定义如 定义2(众包质量控制):众包的质量控制问题就是,发布者如何根据工作者提交的结果Vmⅹn推断所有 任务的正确结果V×1 控制过程中需要排除两类因索对质量的千扰:欺骗类型的工作者( spammer)和工作者的误差率η.差异 距离法0可以检测随机类型的欺骗者, Kouritzinl等1提出的基于序列差异的方法同时适用于识别随机 和统一类型的欺骗者.这些方法可有效脩除众包过程中的 Spammer.而MⅤ算法和EM算法则是处理工作 者误差的重要方法.MV算法2将同一任务分配给多个工作者独立完成,将占多数的结果作为估计的正确 结果.EM算法13对多个工作者的误差率进行极大似然估计,不断循环期望( E-Step)和极大( M-Step)两 个步骤,直至结果收敛 3CQLP问题 虽然模糊化等噪声干扰方法能够保护位置隐私,但是 CAPTCHA项目研究证明,更多噪声必然加 重系统质量控制的负担.CQLP问题正是在隐私与质量之间寻找最佳平衡点,解决二者间的矛盾.在众包质 量控制问题(定义1)的基础上,CQIP问题额外考虑保护 Worker的位置隐私,具体定义如下: 定义3(CQLP):CQLP间题要求 Worker向 Requester发布混自噪声的位置信息.在此基础上,Re- quester从 Worker提交的回答Vnxn中推断所有任务的正确结果V×1. 31位置保护方法 在现行的众包系统中, Worker的位置隐私不加处理,连同任务结果一起提交给 Requester,典型派对的 工作原理如图1所示 -1发布任务 3质量控制 2仁务信息+位置隐私 发布者 工作者 图1现行的众包派对模型 图1系统的机制,致使 Requester掌握 Worker在某时刻的精确位置信息,当信息量积累到一定程度时, Worker很容易遭到位冒攻市.保护 Worker位置隐私的解决办法,是改变众包系统内信息流的传递机制,在 派对中引入众包平台角色,如图2.众包平台为可信的第三方,首先根据 Requester发布的任务制定 Worker 的位置隐私保扩策略图2中的活动2),后来对 Worker提交的位置隐私进行噪声干扰(活动5),并将受保 护的位置信息传递给 Requester(活动6 图3显示的是一个LBC仁务地图,m个任务地点P(1≤i≤m)分布在不同位置(P是任务T的正 确执行位置).利用Ⅴ orono图以任务点为初始点集,将地图划分为m个区域Az(1≤≤m),划分满足条 件:对于区域A2内的任意一点P,P2是距离最近的任务点,即 P-P|≤|P-P,VP∈A,p=1,2 假设工作者完成P点任务,在离开区域A前提交任务结果.以工作者提交一次任务的信息熵衡量众包 系统的隐私保护程度,信息熵越大,工作者所处位置的不确定性就越大,受保护程度越高.ω;在t时刻的位 置信息熵计算公式如下 2050 系统工程理论与实践 第36卷 2隐私保 护策略 众包平台 l发布仁务 接受任务 加入噪声 6受保护的位置信息 4(a)位置隐私 7质量控制 4(b)任务信息 发布者 工作者 图2改进的CQLP众包派对模型 A A 图3任务地图 ( uj)=>Plw, lics in Ai)log Plw; lics in Ai 以下的两种方式,分别对工作者位置信息的空间和时间属性执行噪声干扰,增大位置信息熵. (a)空间模糊法 基于图2所示的众包系统,空间模糊法的貝体描述如下: 工作者v;在t时刻完成任务12,向 Requester提交任务结果vj,并同时向众包平台提交位置信息 (y,mg,lat,t),众包平台根据经度和纬度(mg,lat)以及任务地图推断工作者所处的区域An,然后从任务 地图中其余的m-1个区域中随机挑选k-1个区域,连同An1一起传递给 Requester.其中,k称为模糊 系数,代表空间模糊程度.kⅠ时,不进行模糊处理,图2模型与图1模型一致:k=m时,模糊后的提交 位置可能位于地图的任意区域,保护敚昊等同于工作者未提交位置信息.k越大, Requester接收的信息熵越 大,工作者t时刻的真实位置越不确定,隐私保扩程度越高;被攻击风险越低.图4说明了众包平台使用空问 模糊法对工作者位置信息的处理过程. 区域识别→ 模糊 图4空间模糊过程 第8期 初翔,等:支持工作者位置隐私保护的众包质量控制模型 2051 b)时间模糊法 降低位置信息中时间戳的精度,同样能够减少工作者遭受位置隐私攻击的风险.例如,众包任务要求工 作者收集多地的高速公路的路况,如果工作者超速行驶并连续提交精确的位置信息,攻击者会感知到工作者 的超速行为.可行的隐私保护方法,是对(1)式中的时间戳进行模糊化处理,将精确时间替换为不影响众包 任务的时间区间,如图5所示,t∈[t1,t].事实上,任务发布者关心的“实时”路况,不必精确至秒、毫秒,通 常15分钟或30分钟的信息“延迟”是可接受的正是发布者对“延迟”的容忍度,为时间模糊法的隐私保护 提供了可行性 时间模糊 图5时间模糊过程 以表示 Worker的平均移动速度,即单位时间内可穿过任务地图的?个区域.根据(3)式,进行空间 与时间模糊处理后,CQLP模型中每个提交位置的平均信息熵由零増加为 It(ui=alt2-tillogk 32CQLP众包质量 欺骗类型的工作者( spammer)为了获取最大化的利益,会不认真地提交质量低下的任务结果;即使是勤 奋认真的工作者,也可能由于能力或意外而提交错误结果,存在一定的误差率.正是因为 Spammer和误差率 的存在,引发了众包任务的质量问题.CQLP众包质量控制模型的功能包括两个方面:筛除 Spammer和误 差率千扰下的正确结果佔计 1)筛除 Spammer 现行的LBC任务系统要求 Worker提交完成任务时的位置信息,日的在于通过比较位置信息与真实任 务地址识别并排除 Spanner.如果u;提交的任务中存在位置信息与真实地址不匹配的情形,则认为;是 spammer.假设提交任务时 Spammer的真实位置随机均匀分布于任务地图内.如果用图1系统模型,则 spammer完成1个任务并成功躲避系统 Spammer检测的平均概率为1/m,完成m个任务并躲避检测的 平均概率为1/mm.如果采用图2的CQLP模型, spammer完成1个任务并躲避检测的平均概率为k/m, 完成m个任务并躲避检测的平均概率为k"/m",尽管, Spammer的平均躲避概率增长k"倍,实际上,当 k≤m或m较大时,躲避概率k/mm依然接近于0. 综合以上分析,改进的(QIP模型,造成极少量 Spa.mmer以更高的概率逃避欺骗检测.结论1将从 理论角度说明,欺骗检测能力的降低不会显著影响众包的质量控制.为了证明结论1,首先提出并证明如下引 理: 引理1将少量错误结果混入质量较高的结果集,不会显著影响结果估计的准确率 对于一个二元众包任务,n名 Worker提交结果,平均误差率为n,n<0.5. requester基于多数投票方 法21,根据n个结果估计任务的正确结果,最终估计错误(正确结果为1估计为0;或正确结果为0,估 计为1)的后验概率为 ∑ 估计错误的概礻P随 Worker数量n指数下降,所以,当完成该任务的 Worker较多时,P超于0 P代表图1系统的错误概率,如果除了η个结果之外,再加入△n个错误结果,△n≤n,则根据m+△n 个回答任务结果,佔计错误的后验概率为 Cnn2(1-m)2—2 将(6)式与(5)式相减混入△n个镨误结果后,错误概率增大: △ ∑ 2052 系统工程理论与实践 第36卷 随着η増大,⑦)式右端指数下降并逼近0.以上分析表明,少量错淏结果并不会明显妨碍最终判断,因 此引理1成立 cLP位置隐私保护方法,可能致使少量 Spammer躲过系统检测,根据引理1,这些 Spammer冗乎不 可能干扰发布者对正确结果的估计.因此,通过理论分析,得到本文的一个主要结论 结论1CQLP隐私保护方法,不影响众包系统的质量控制能力 2)误差率和正确结果估计 LC方法13是质量控制问题中的经典方法.将工作者的误差率作为潜在变量,通过极大似然估计推断 误差率,从而估计众包任务的正确结果.n维向量mx1={m}是所有工作者的误差率,工作者按照一定 的误差率m完成任务,m=(q3,n2)m和m2相互独立分别表示正确结果为1”和“0”时w的误差率 P(v=02=1),m2=P(V=12=0) LC方法采用期望最大值算法(EM算法,首先使用MV算法以正确率(正确率+误差率=1)作为 权重估计每项任务的正确结果,然后更新每名工作者的误差率估计,并不断循环两个步骤,迭代过程中Q函 数逐渐收敛.与单纯的MⅤ算法相比,EM算法充分考虑了工作者的误差率因素,帮助发布者排除低质量的 工作者,具体步骤如下 (a)e-ste 定义m维向量1,2(1≤2≤m)表示任务的正确结果是1的后验概率,即 P(;=1Vm×n,m) 以正确率作为MV算法的权重初始化μ p) (10 pai+(1-p)bi 其中,t代表第t次迭代p为任务正确结果为1的期望概率,a;=I=1(1-n)(m)1-1,b=I=1(1 根据E-step中μ的期望,伟计p的值: ∑ (11) 计算极大似然估计,得到误差率变量的估计值: 7 7 采用如下Q函数 Q(p, I;)=>IA: log pai+(1-Hi)log(1-p)bi 13 判断Q函数是否收敛(ε为收敛阈值), lQ(p t+1) Q /Q((), 如果Q函数未收敛,返回 F-step,开始下一次迭代;否则返回佔计结果μ并结東算法 4实验与结果分析 结论1从理论角度证明,CQLP系统的质量控制水平接近于暴露 Worker位置隐私的现行众包系统.为 了更严谨地论证CQLP的控制质量,本节采用实验的方法,再次比较现行众包模型(模糊系数k=1)和 CQLP模型(k=5),同时加入不提交位置信息的情形(k=m)作为对比基准.实验数据,一方面来自本硏究 设计的人工实验“超市商品检查实验”,另一方面来自利用计算机的数值模拟 41超市商品检查实验 1)实验设计 招募5名志愿者作为众包 Worker.其中的4名 Worker被要求在7天时间内,检查某市的30家大型超 市是否在售某款饮料商品.每个检查任务要求在进入对应超市后的8分钟内完成,如果 Worker在限定时间 内没有找到指定商品, Worker以猜测的方式确定任务结果.结果提交要在工作者离开超市之前完成.“8分 第8期 初翔,等:支持工作者位置隐私保护的众包质量控制模型 2053 钟”规则,旨在制造不同工作者之间的误差率差异,检查效率高的工作者更可能在8分钟内完成任务,从而 更可能提交正确回答.此外,正确结果不同也可能引起误差率的不同.剩余的1名 Worker充当 Spammer, Spammer不会认真地去超市执行检查任务,而是在实验时间内在随机的30个地点提交30个检查任务结果 每天的8点至21点,30家超市均营业,所有任务均要求在该时间段内提交.实验组织者每天对30家超 市进行一轮排查,确保在实验期间该饮品的上架状态未发生改变.事实上,30家超市中的14家一直在销售 该饮品.实验结果,5名工作者共提交150个回答,其中的76个回答结果为“1”,即相应超市在售该饮品 2)结果分析 众包系统的质量控制水平以准确率( accuracy)指标衠量,所谓准确率是指通过统计方法所估计的正确结 果与真实结果的一致率.当任务T正确结果为“1”的后验概率μ>0.5时,估计=1、否则、估计z=0. 按任务地图实际尺寸估计,工作者在任务区域间移动的平均耗时为0.2小时,超市工作时间段为,21] 首先对位置信息采取模糊系数为k的空间模糊处理,然后,完成时间被模糊化,将位置时间戳去揮具体时间, 只保留结果提交的日期根据(3)式,表1得到三种模型下每次提交的位置平均信息熵.不难发现,CQLP模 型对位置信息稍加模糊处理(k=5).就产生明显的保护效果,工作者位置的不确定程度接近不提交位置信 息情形(k=m)的一半 表1模糊系数k对信息熵和准确率的影响 k=1 k=5 k=m 平均信息熵048910.34 准确率 0.930.9330.933 同时,表1还比较了三种模型对应的任务准确率.结果显示,虽然三者的任务发布者获得的位置信息量 不同,但却产生了相同的质量控制结果.该结果说明,在一些实际场景中,位置信息可能对质量控制没有明显 的帮助作用 然而,在误差率和 Spammer比率较高的情形下,情况完全不同.为此,随后的数值模拟实验将全面地比 较三种模型在不同参数组合下的准确率 4.2模拟实验 超市商品检查实验存在成本较高的缺点,无法以可接受成本构造所有实验参数组合下的测试数据集.基 于计算机的数值模拟实验,可解决测试成本问题,在短时问内以低成本,系统分析各实验参数对模型质量的 影响 1)测试数据集 通过变化任务数量m、工作者数量m、工作者误差”、 Spammer比率r等实验参数,生成一系列数据 集数据生成步骤包括:①生成所有任务的正确结果向量Wm×1,每个正确结果v;(1≤≤m)服从p=0.5 的伯努利分布,其中p是任务正确结果为“1”的概率.②生成所有工作者;(1≤j≤m)的任务结果,如 果n;是 Paillier,结果v;(1≤i≤m)服从伯努利分布B(1,0.5);否则,对=1和访=0的任务,ta 分别服从关于误差率(mm2)的伯努利分布B(1,1-m)和B(1,1-m2).③生成工作者的位置,如果;是 Spammer,从图3的m个区域中随机选择一个,作为结果的提交位置;否则,提交任务T对应的位置区域 2)结果分析 针对不同参数组合的测试数据集,图6(a)~(d)对比了三种众包模型的准确率图6(a)和(b)在较低的 误差率η=(0.2,0.2)和 Spa.mmer比率r=0.2实验设置下完成,无论任务和工作者数量如何变化,三种模 型质量始终接近.两图不同的是,任务数量变化不影响模型质量,而随着工作者数量的增大模型质量有所上 升.图6(c)和(d)表明,当η和r较低时,三种模型的准确率仍然很接近;但随着η和r的增大,k=m模 型的质量控制水平开始明显差于其余两种模型,而k=5的质量控制水平一直与k=1接近 图6的实验结果以及“超市商品检查实验”中的发现,有力地证明了:CQLP模型(k=5)与现行的众 包模型(k=1)相比,在有效控制众包质量的前提下,更有力地保护了工作者的位置隐私 2054 系统工程理论与实践 第36卷 任务 L作者 (a)任务量与准确率 (b)工作者数据与准确率 误差率 (c)误差率与准确率 d) Spammer比例与准确率 图6实验参数对众包质量的影响 5结束语 LBC任务使工作者位置隐私存在泄露风险,如果为保证隐私而不要求工作者提供位置信息会造成误差 率增大、欺诈者增多,影响众包项目的质量.CQLP模型识别隐私与质量的矛盾,提出了基于空间和时间模 糊的保护方法,是本文的主要贡献.而本文的主要研究内容,是通过理论和实验验证所提出方法不影响众包 的质量控制,保护方法能够很好地解决隐私与质量两方面的冋题. 大数据时代,隐私保护日益受到关注,但是,众包过程中的隐私泄露,尤其是LBC等新兴形式下的隐私 保护、尚未引起足够重视.隐私泄露风险的存在,可能成为阻碍众包模式发展的瓶颈.随着众包模式的成熟, 参与者隐私可能成为众包领域的研究热点 参考文献 1 Karger DR, Oh S, Shah D. Budgct-optimal task allocation for rcliablc crowdsourcing systcms[J. Opcrations Research,2014,62(1):1-24 2」 Howe J. The rise of crowdsourcing小」. Wired.2006,14(6):176-183 3 Varshney L R Privacy and reliability in crowdsourcing service delivery[Cl//2012 Service Research and Innovation Institute global con ference. 20122: 55-60. 4 Varshney L R, Vempaty A, Varshney P K. Assuring privacy and reliability in crowdsourcing with coding// Proceedings of the 2014 Information Theory and its Applications Workshop(ITA), 2014: 1-6 5 Hiroshi K, Hiromi A, Hisashi K. Preserving worker privacy in crowdsourcingJ. Data Mining and Knowledge Discovery,2014,28:1314-1335 6]王璐,孟小峰.位置大数据隐私保护研究综述[软件学报,2014(4):693-712 Wang L, Meng X F. Location privacy preservation in big data era: A survey[J. Journal of Software, 2014(4) 693-712 [7 Beresford A R, Stajano F. Location privacy in pervasive computing[J]. IEEE Pervasive Computing, 2003, 2(1) 46-55 第8期 初翔,等:支持工作者位置隐私保护的众包质量控制模型 2055 8 Dowri R. Local diffcrcntial perturbations: Location privacy under approximate knowledge attackers J. IEEE Transactions on Mobile Computing, 2013, 12(12): 2300-2372 9 Palanisamy B, Liu L. Mobimix: Protecting location privacy with mix-zones over road networks[Cl// Proceedings of the 27th International Conference on Data Engineering(ICDE), Hannover, 2011: 191-505 10张志强,逄居升,谢晓芹,等众包质量控制策咯及评估算法硏究J·计算机学报,2013.36(8):1636-1649 Zhang z Q, Pang j s, Xie X Q, et al. Research on crowdsourcing quality control strategies and evaluation algorithm[J. Chinese Journal of Computers, 2013, 36(8): 1636-1649 11 Kouritzin M A, Newton F, Orsten S, et al. On detecting fake coin Aip sequencesJ. Institute of Mathematical Statistics,2008,4:107-122 [12 Sheng V S, Provost. F, Ipeirotis P G. Get another label? Improving data quality and dat a. mining using multiple noisy labelers Cl// Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2008: 614-622 13 Dawid A P, Skene A M. Maximum likelihood estimation of observer error-rates using the EM algorithm[J Journal of the Royal Statistical Society, 1979, 28(1):20-28 14 Kolupaev A, Ogijenko J CAPTCHAs: Humans vs. bots[J. IEEE Security Privacy, 2008, 6(1):68-70 15]岳德君,于戈,申德荣等.基于投票致性的众包质量评估策略[J].东北大学学报(自然科学版),2014,35(8):1097 1101 Yuc D J, Yu G, Shon D R, ct al. Crowdsourcing quality cvaluation strategics based on voting consistency J Journal of Northeastern University(Natural Science), 2014, 35(8:1097-1101 [16 Dempster A P, Laird N M, Rubin D B. Maximum likelihood from incomplete data via the EM algorithm[J Journal of the Royal Statistical Society, Series B(Methodological): 1977, 39(1):1-38

...展开详情
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
最新资源