1.1 研究目的及意义

随着互联网的快速发展，日常生活中人们接触到的信息量越来越大，当今社会已经进入信息爆炸时代，信息的收集和存储的需求量也越来越大，数据安全和隐私保护显得越来越重要。信息的表示方法对信息的使用有着重要的影响，信息的负表示是一种新的很有前景的数据安全和隐私保护方法。负调查是在信息负表示的基础上提出的。负调查可以在收集数据的同时有效保护参与调查人员的隐私，适合于敏感数据的收集。负调查的分布重建是负调查工作中最为关键的一部分，它主要用于从负调查结果中重建出有用的统计信息。

Esponda等人受生物免疫系统中免疫细胞通过“自我-非我”的机制识别细胞并进行匹配的思想提出了信息负表示[5]的概念。此后，基于信息负表示思想，学者们分别提出并研究了负数据库和负调查，其中负数据库用于存储数据，负调查用于收集数据。Esponda等人首先提出了负调查[5]的概念并将其应用于收集类别数据，该方法是一种新颖的并具有应用前景的隐私保护方法。在传统的调查方法中，参与者需要选择和问题相关的且符合实际情况的选项，传统的调查方法被称为正调查，符合实际情况的选项被称为正选项。敌手可以用窃听攻击等攻击方式获取在正调查中参与者的数据，从而推测出其隐私信息，导致隐私泄露。然而，在负调查中，参与者不需要选择真实的选项，而是在不符合自己实际情况的选项中选择一项，该类选项称为负选项。敌手在获取负调查中参与者的数据后很难推测出关于参与者的信息，因此，参与者的隐私可以得到保护。同时，当收集到的数据样本量足够时，数据收集者可以使用一些统计方法估算出正选项的分布，使得负调查的结果可以在实际生活中得到应用。

本课题拟在已有的负调查重建算法上进行优化，通过改进已有算法或提出新的算法，提高负调查重建的效率和精度，同时设计适用于任意的选择概率矩阵的重建算法。本课题的工作可以为负调查方面的研究提供有益的指导与帮助。

1.2 研究现状

目前为止，已有两种负调查方法被提出，分别为Esponda等人提出的均匀负调查(Uniform Negative Surveys, UNSs)[5]和Xie等人提出的高斯负调查(Gaussian Negative Surveys, GaussianNSs)[6]。在均匀负调查中，参与调查者以相同的概率从所有负选项中随机选择一个负选项报告给数据收集者；在高斯负调查中，如果正类别i与参与调查者的实际情况相符，那么参与调查者按照以正类别i为中心的高斯分布选择一个负类别J报告给数据收集者。

对于负调查结果估算正调查的算法，Esponda等人首先提出了NStoPS算法[5]，但是NStoPS算法计算出正调查结果中可能含有负值，这样的正调查结果不符合实际情况。在此方法上，Bao等人对其进行改进提出了NStoPS-Ⅰ和NStoPS-Ⅱ算法[1]，Zhao等人提出了NStoPS-BK算法[4]。与传统的由负调查结果估算正调查的算法NStoPS相比，NStoPS-Ⅰ，NStoPS-Ⅱ以及NStoPS-BK都能够消除正调查结果出现负值的情况，NStoPS-Ⅰ算法主要思想是利用正负调查结果之间满足的关系，采用迭代的方法估算出正调查的结果。NStoPS-Ⅱ算法是采用数值调整的方法，使结果更加合理。Bao所提出的两种算法各有特点，NStoPS-Ⅰ算法可扩展性更好，而NStoPS-Ⅱ算法时间复杂度更低。Zhao等人提出的NStoPS-BK算法引入了背景知识的概念，认为在真实的调查中通常有一些背景知识，合理的利用背景知识可以提高重建正调查结果的精度，该算法将背景知识考虑在内，实验证明NStoPS-BK得到的结果更为精准。然而这四种算法都是建立在均匀负调查的基础上实现的，如果选择概率不均匀，即选择概率是任意分布的情况下，算法并不适用。

负调查可以应用于很多的领域，例如James Horey等人将负调查应用于收集传感器网络中的匿名数据收集[11];Horey等人还将负调查应用于收集地理位置信息[13];Groat等人用负调查提高参与式感应应用中的隐私保护程度并提出了多维负调查[17]等等。

2. 研究的基本内容与方案

一、基本内容

1、 优化负数据到正数据的重建算法的效率和精度；