本发明涉及数据挖掘和隐私保护领域，涉及一种关联元组数据的差分隐私发布方法及系统。
背景技术：
在数据驱动的应用场景中，比如基于位置的服务(lbs)、疾病监视和社交网络等场景中，元组数据是一种广泛存在的数据类型，元组数据共享对于数据所有者获得更好的服务是非常必要的。例如，在基于位置的应用中，用户将自身精确位置数据上传到服务提供商，以获得更好的导航服务；在疾病监测应用中，与医院共享个人身体监测数据可以帮助预防某些突发疾病。由此可见，元组数据共享在知识发现和获取方面具有非常重要的作用，但是，共享元组数据可能包含个人的敏感信息(例如，个人家庭住址和健康状况等)，直接发布个人元组数据可能会泄露个人的私人信息，出于隐私考虑，数据所有者可能不愿意发布其真实元组数据值。因此，如何保护元组数据的隐私是元组数据共享和挖掘的前提。
早期的隐私保护方案依赖于所设计算法的安全性保证，因此很难从理论上证明和分析安全性。为解决此问题，dwork提出的差分隐私具有扎实的数学基础，并使用参数量化隐私保护强度，是一种从数学上严格定义保护强度和数据可用性的隐私保护手段。由于差分隐私可以为隐私安全和数据可用性提供完整的数学保证，因此它已成为近年来的重要的隐私保护框架。
在实际应用中实现差分隐私时，dwork简化了真实数据的分布特征。差分隐私假定待保护数据集中的记录彼此独立，向待保护数据添加独立且均匀分布的拉普拉斯噪声，以确保满足差分隐私的定义。但是，此假设在相关元组数据中存在隐私保护强度低于设定值的问题。因此，尽管差分隐私在独立数据保护方面具有良好的性能，但在关联元组数据发布中无法实现预期的隐私保证。
为了弥补上述缺陷，使差分隐私适用于关联元组数据的保护，目前的研究者们主要从建立相关模型和变换模型两个角度进行改进。基于相关模型的思路是建立相关模型来描述关联元组之间的关系，进而计算出对删除保护记录的其他记录的影响。相关模型包括反映数据相关性的高斯模型、markov或bayesian模型等；基于变换模型的思路是将关联元组转换到独立域，并将独立同分布的拉普拉斯噪声添加到转换的系数中，然后进行逆变换以生成扰动结果。在这两种模型中，基于相关模型的方法通过增加噪声的大小来抵消隐私度的降低，但是较大的噪声会破坏数据的可用性；基于变换模型的方法虽然克服了基于相关模型方法的低效用缺点，但逆变换后的分布不是拉普拉斯形式，所以基于变换的方法可能无法严格满足差分隐私的定义。因此，现有的方法并没有彻底解决关联元组数据的差分隐私保护问题，仍面临着数据可用性较低和无法严格满足差分隐私定义的问题。
技术实现要素：
基于上述背景技术中提到的问题，本发明提供了一种关联元组数据的差分隐私发布方法及系统，用于解决现有利用差分隐私保护关联元组数据的发布方法中，面临的待保护元组数据相关而差分隐私生成的噪声独立导致的隐私保护强度降低的问题。
本发明采用的技术方案如下：
一种关联元组数据的差分隐私发布方法及系统，通过构造与原始待保护元组数据相关性一致的噪声元组，使噪声元组的相关性与待保护的原始元组数据的相关性一致，可以防止具有数据相关背景知识的对手发起的推理攻击，为相关元组数据提供差分隐私保证，同时不会增大噪声尺度。在具体实现时，本发明提出一种实用高效的迭代和更新机制，以生成与待保护元组数据相关性一致的噪声元组数据，叠加到待保护元组数据中发布。
本发明提供一种基于差分隐私的关联元组数据发布方法，包括以下步骤，
步骤s1，输入数据及参数初始化，包括以下子步骤：
步骤s1-1，对原始数据集进行数据清洗和归约，得到待保护关联元组数据集x＝{x1,x2,l,xn}；
步骤s1-2，读入待查询结果序列q＝{q1,q2,l,qn}；
步骤s1-3，根据待保护关联元组数据集x和查询序列q设置敏感度函数δf：δf＝sup||q(xk)-q(xu)||1
其中xk、xu是x中被查询的任意两个元组，xk∈x，xu∈x。根据用户个人隐私保护需求初始化隐私预算参数ε。
步骤s2，生成初始化噪声并扰动初始查询结果，包括以下子步骤：
步骤s2-1，令t＝1，根据拉普拉斯分布概率密度函数
步骤s2-2，扰动初始化查询结果q′1＝q1 y1；
步骤s3，根据新的查询函数生成满足特定自协方差矩阵的噪声并扰动查询结果，包括以下子步骤：
步骤s3-1，判断新的查询函数q2是否与上次的查询函数相同，若q2≠q1，跳转到步骤s4得到拉普拉斯噪声变量y2；若q2＝q2，则跳转到步骤s5得到拉普拉斯噪声变量y′2；
步骤s3-2，若q2≠q1，计算加扰查询结果q′2＝q2 y2；若q2＝q2，计算加扰查询结果q′2＝q2 y′2；
步骤s4，生成符合特定自协方差矩阵的拉普拉斯噪声变量，包括以下子步骤：
步骤s4-1，计算xk、xu的自协方差矩阵ck,u，生成均值为零、协方差矩阵等于自协方差矩阵ck,u的高斯变量gk,u；
步骤s4-2，生成概率密度函数为
步骤s4-3，将高斯变量和指数变量相乘得到广义拉普拉斯变量
步骤s5，更新拉普拉斯噪声变量，包括以下子步骤：
步骤s5-1，生成概率密度函数为
步骤s5-2，将高斯变量和指数变量相乘得到新的广义拉普拉斯变量
步骤s6，迭代处理所有查询直至查询函数序列处理结束，包括以下子步骤：
步骤s6-1，令t＝2,3,ln，依次按照步骤s3～s5生成噪声变量并扰动对应的查询结果，得到扰动后的查询结果q′2,l,q′n；
步骤s6-2，输出并发布扰动查询结果序列q′＝{q′1,q′2,l,q′n}。
另外，本发明提供一种关联元组数据的差分隐私发布系统，包括以下模块，
输入及参数初始化模块，用于输入数据及初始化参数，包括以下子单元：
第一单元，对原始数据集进行数据清洗和归约，得到待保护关联元组数据集x＝{x1,x2,l,xn}；
第二单元，读入待查询结果序列q＝{q1,q2,l,qn}；
第三单元，根据待保护关联元组数据集x和查询序列q设置敏感度函数δf：δf＝sup||q(xk)-q(xu)||1
其中，xk、xu是x中被查询的任意两个元组，xk∈x，xu∈x。然后根据用户个人隐私保护需求初始化隐私预算参数ε。
初始化噪声扰动模块，用于生成初始化噪声并扰动初始查询结果，包括以下子单元：
第一单元，令t＝1，根据拉普拉斯分布概率密度函数
第二单元，扰动初始化查询结果q′1＝q1 y1；
特定自协方差矩阵拉普拉斯噪声生成模块，用于根据新的查询函数来生成满足特定自协方差矩阵的噪声并扰动查询结果，包括以下子单元：
第一单元，判断新的查询函数q2是否与上次的查询函数相同，若q2≠q1，跳转到第三单元得到拉普拉斯噪声变量y2；若q2＝q2，跳转到拉普拉斯噪声更新模块得到拉普拉斯噪声变量y′2；
第二单元，若q2≠q1，计算加扰查询结果q′2＝q2 y2；若q2＝q2，计算加扰查询结果q′2＝q2 y′2；
第三单元，生成符合特定自协方差矩阵的拉普拉斯噪声变量，首先，计算xk、xu的自协方差矩阵ck,u，生成均值为零、协方差矩阵等于自协方差矩阵ck,u的高斯变量gk,u；然后生成概率密度函数为
拉普拉斯噪声更新模块，用于更新拉普拉斯噪声变量，包括以下子单元
第一单元，生成概率密度函数为
第二单元，将高斯变量和指数变量相乘得到新的广义拉普拉斯变量
迭代处理模块，用于迭代处理所有查询直至查询函数序列处理结束，包括以下子单元：
第一单元，令t＝2,3,ln，依次按照特定协方差矩阵拉普拉斯噪声生成模块和拉普拉斯噪声更新模块生成噪声变量并扰动对应的查询结果，得到扰动后的查询结果q′2,l,q′n；
第二单元，输出并发布扰动查询结果序列q′＝{q′1,q′2,l,q′n}。
本发明通过生成符合特定自协方差矩阵拉普拉斯噪声，首先生成初始化噪声并扰动初始化查询结果，然后根据新的查询函数生成满足特定自协方差矩阵的噪声并扰动查询结果，最后采用迭代机制处理所有查询直至查询函数序列处理完毕输出并发布扰动查询结果。
与现有技术相比，具有以下有益效果：
(1)噪声元组与原始元组数据相关性一致，可以防止具有数据相关背景知识的对手发起的推理攻击；
(2)利用迭代机制和更新机制，可以支持在面对大量重复查询时更新拉普拉斯噪声，在实际应用中具有更高的实用性；
本发明的实施过程及步骤，包括生成满足特定协方差的拉普拉斯噪声、更新机制、迭代机制的应用等，降低了计算复杂度，系统资源占用低，便于高效实施，具有重要的市场价值。
附图说明
本发明可以通过附图给出的非限定性实施例进一步说明；
图1是本发明实施例提供的总体方法流程图；
图2是本发明实施例提供的具体步骤流程图；
图3是本发明实施例提供的发布系统总体示意图；
具体实施方式
为了使本领域的技术人员可以更好地理解本发明，下面结合附图和实施例对本发明技术方案进一步说明。
实施例
以下将结合附图及实施例，对本发明的构思、具体结构及产生的技术效果作进一步说明，以充分地了解本发明的目的、特征和效果。
下面以某社交网站32,768名学生之间的友谊关系组成的关联元组数据为例，来阐述本发明具体的实施步骤，目标是发布由友谊关系组成的关联元组数据到第三方教育机构，以获得学生心理健康情况，同时保证发布的关联元组数据不能泄露单个同学的具体友谊关系。
本发明技术方案所提供方法可采用计算机软件技术实现自动运行流程，图1和图3是本发明实施例的总体方法流程图，参见图1，结合图2中发明实施例的具体步骤流程图，本发明提供的关联元组数据差分隐私发布方法的实施例具体步骤包括：
步骤s1，输入数据及参数初始化。
实施例中，记待保护关联元组数据集为某社交网站32,768名学生之间的友谊关系组成的关联元组数据集为x，包含32,768个元素，具体实施时待查询结果序列q可由本领域技术人员更具需求自行设定(例如本实施例设置查询序列q＝{q1,q2,l,q100})，具体实现如下：
步骤s1-1，对原始数据集进行数据清洗和归约，得到待保护关联元组数据集x＝{x1,x2,l,xn}；
实施例中，对某社交网络32,768名学生的友谊关系组成的原始数据集进行清洗和归约，得到待保护关联元组数据集x＝{x1,x2,l,x32768}；
步骤s1-2，读入待查询结果序列q＝{q1,q2,l,qn}；
实施例中，q＝{q1,q2,l,q100}，具体实施时由本领域技术人员自行设定查询结果序列；
步骤s1-3，根据待保护关联元组数据集x和查询序列q设置初始化敏感度函数δf：δf＝sup||q(xk)-q(xu)||1
其中，xk、xu是x中被查询的任意两个元组，xk∈x、xu∈x。根据个人隐私保护需求初始化隐私预算参数ε。
实施例中，敏感度函数δf经过计算为18，初始化隐私预算参数ε为1，具体实施时可由本领域技术人员自行设定隐私预算参数。
步骤s2，生成初始化噪声并扰动初始查询结果，包括以下子步骤：
步骤s2-1，令t＝1，根据拉普拉斯分布概率密度函数初始化生成拉普拉斯噪声
实施例中，初始化拉普拉斯噪声变量生成方式为：
步骤s2-2，扰动初始化查询结果q′1＝q1 y1；
实施例中，扰动初始化查询结果经计算得到q′1＝q1 0.65。
步骤s3，根据新的查询函数生成满足特定自协方差矩阵的噪声并扰动查询结果，包括以下子步骤：
步骤s3-1，判断新的查询函数q2是否与上次的查询函数相同，若q2≠q1，跳转到步骤s4得到拉普拉斯噪声变量y2；若q2＝q2，跳转到步骤s5得到拉普拉斯噪声变量y′2；
实施例中，若q2≠q1，则跳转到步骤s4，计算拉普拉斯噪声变量y2；其他q2＝q2，则跳转到步骤s5，计算拉普拉斯噪声变量y′2。
步骤s3-2，若q2≠q1，计算加扰查询结果q′2＝q2 y2；若q2＝q2，计算加扰查询结果q′2＝q2 y′2；
实施例中，加扰查询结果的计算方式为：当q2≠q1，q′2＝q2 y2，当q2＝q2，q′2＝q2 y′2。
步骤s4，生成符合特定自协方差矩阵的拉普拉斯噪声变量，包括以下子步骤：
步骤s4-1，计算xk、xu的自协方差矩阵ck,u，生成均值为零、协方差矩阵等于自协方差矩阵ck,u的高斯变量gk,u；
实施例中，先计算xk、xu的自协方差矩阵
步骤s4-2，生成概率密度函数为
实施例中，指数变量w的计算方式为：
步骤s4-3，将高斯变量和指数变量相乘得到广义拉普拉斯变量
实施例中，广义拉普拉斯变量的计算方式为：
步骤s5，更新拉普拉斯噪声变量，包括以下子步骤：
步骤s5-1，生成概率密度函数为
实施例中，指数变量w′的计算方式为：
步骤s5-2，将高斯变量和指数变量相乘得到广义拉普拉斯变量
实施例中，广义拉普拉斯变量的计算方式为：
步骤s6，迭代处理所有查询直至查询函数序列处理结束，
实施例中，重复步骤s3～s5，计算100个查询序列的加扰结果，直至所有查询函数序列处理完毕，进入步骤s6-2。
具体实现可设计为如下子步骤，
步骤s6-1，令t＝2,3,ln，依次按照步骤s3～s5生成噪声变量并扰动对应的查询结果，得到扰动后的查询结果q′2,l,q′n；
实施例中，在迭代处理步骤s3时，判断当前查询函数与下一查询函数会遇到相同与不相同两种情况，实施时可由本领域技术人员根据相邻两查询函数是否相同自行选择进入步骤s4或步骤s5，生成拉普拉斯变量。当前查询函数与下一查询函数相同时进入步骤s5计算更新的拉普拉斯噪声变量，当前查询函数与下一查询函数不相同时进入步骤s4生成符合特定协方差矩阵的拉普拉斯噪声变量。
本实施中，采用两种计算拉普拉斯噪声变量的方式，只需判断当前查询函数与下一查询函数是否相等，然后分别计算不同的拉普拉斯噪声变量，本实施例中，有一半的查询函数相同。
步骤s6-2，输出并发布扰动查询结果序列q′＝{q′1,q′2,l,q′n}。
实施例中，发布的是加噪处理后的某社交网站中由学生之间的友谊关系组成的关联元组数据集。实现从用户到数据分析者的数据变换。
具体实施时，本发明所提供方法可基于软件技术实现自动运行流程，也可采用模块化方式实现相应系统。
输入及参数初始化模块，用于输入数据及初始化参数，包括以下子单元：
第一单元，对原始数据集进行数据清洗和归约，得到待保护关联元组数据集x＝{x1,x2,l,xn}；
第二单元，读入待查询结果序列q＝{q1,q2,l,qn}；
第三单元，根据待保护关联元组数据集x和查询序列q设置初始化敏感度函数δf：δf＝sup||q(xk)-q(xu)||1，其中，xk、xu是x中被查询的任意两个元组，xk∈x、xu∈x。然后根据个人隐私保护需求初始化隐私预算参数ε。
初始化噪声扰动模块用于生成初始化噪声并扰动初始查询结果，包括以下子单元：
第一单元，令t＝1，根据拉普拉斯分布概率密度函数初始化生成拉普拉斯噪声：
第二单元，扰动初始化查询结果q′1＝q1 y1；
特定自协方差矩阵拉普拉斯噪声生成模块，用于根据新的查询函数来生成满足特定自协方差矩阵的噪声并扰动查询结果，包括以下子单元：
第一单元，判断新的查询函数q2是否与上次的查询函数相同，若q2≠q1，跳转到第三单元得到拉普拉斯噪声变量y2；若q2＝q2，跳转到拉普拉斯噪声更新模块得到拉普拉斯噪声变量y′2；
第二单元，若q2≠q1，计算加扰查询结果q′2＝q2 y2；若q2＝q2，计算加扰查询结果q′2＝q2 y′2；
第三单元，生成符合特定自协方差矩阵的拉普拉斯噪声变量，首先，计算xk、xu的自协方差矩阵ck,u，生成均值为零、协方差矩阵等于自协方差矩阵ck,u的高斯变量gk,u；然后生成概率密度函数为
拉普拉斯噪声更新模块，用于面对重复的查询函数时更新拉普拉斯噪声变量，包括以下子单元
第一单元，生成概率密度函数为
第二单元，将高斯变量和指数变量相乘得到广义拉普拉斯变量
迭代处理模块，用于迭代处理所有查询直至查询函数序列处理结束，包括以下子单元：
第一单元，令t＝2,3,ln，依次按照特定协方差矩阵拉普拉斯噪声生成模块和拉普拉斯噪声更新模块生成噪声变量并扰动对应的查询结果，得到扰动后的查询结果q′2,l,q′n；
第二单元，输出并发布扰动查询结果序列q′＝{q′1,q′2,l,q′n}。
本发明提供了本领域技术人员能够实现的技术方案。以上实施例仅供说明本发明之用，而非对本发明的限制，有关技术领域的技术人员，在不脱离本发明的精神和范围的情况下，还可以做出各种变换或变型，因此所有等同的技术方案，都落入本发明的保护范围。
1.一种关联元组数据的差分隐私发布方法，其特征在于：包括以下步骤，
步骤s1，输入数据及参数初始化；
步骤s2，生成初始化噪声并扰动初始查询结果；
步骤s3，根据新的查询函数生成满足特定自协方差矩阵的噪声并扰动查询结果；
步骤s4，生成符合特定自协方差矩阵的拉普拉斯噪声变量；
步骤s5，更新拉普拉斯噪声变量；
步骤s6，迭代处理所有查询直至查询函数序列处理结束。
2.根据权利要求1所述一种关联元组数据的差分隐私发布方法，其特征在于，所述步骤s1包括以下子步骤：
步骤s1-1，对原始数据集进行数据清洗和归约，得到待保护关联元组数据集x＝{x1,x2,l,xn}；
步骤s1-2，读入待查询结果序列q＝{q1,q2,l,qn}；
步骤s1-3，根据待保护关联元组数据集x和查询序列q设置敏感度函数δf：
δf＝sup||q(xk)-q(xu)||1
其中xk、xu是x中被查询的任意两个元组，xk∈x，xu∈x。根据用户个人隐私保护需求初始化隐私预算参数ε。
3.根据权利要求1所述一种关联元组数据的差分隐私发布方法，其特征在于，所述步骤s3包括以下子步骤：
步骤s3-1，判断新的查询函数q2是否与上次的查询函数相同，若q2≠q1，跳转到步骤s4得到拉普拉斯噪声变量y2；若q2＝q2，则跳转到步骤s5得到拉普拉斯噪声变量y′2；
步骤s3-2，若q2≠q1，计算加扰查询结果q′2＝q2 y2；若q2＝q2，计算加扰查询结果q′2＝q2 y′2。
4.根据权利要求1所述一种关联元组数据的差分隐私发布方法，其特征在于，所述步骤s4包括以下子步骤：
步骤s4-1，计算xk、xu的自协方差矩阵ck,u，生成均值为零、协方差矩阵等于自协方差矩阵ck,u的高斯变量gk,u；
步骤s4-2，生成概率密度函数为
步骤s4-3，将高斯变量和指数变量相乘得到广义拉普拉斯变量
5.根据权利要求1所述一种关联元组数据的差分隐私发布方法，其特征在于，所述步骤s5包括以下子步骤：
步骤s5-1，生成概率密度函数为
步骤s5-2，将高斯变量和指数变量相乘得到新的广义拉普拉斯变量
6.一种关联元组数据的差分隐私发布系统，其特征在于：包括以下模块，
输入及参数初始化模块，用于输入数据及初始化参数，包括以下子单元：
第一单元，对原始数据集进行数据清洗和归约，得到待保护关联元组数据集x＝{x1,x2,l,xn}；
第二单元，读入待查询结果序列q＝{q1,q2,l,qn}；
第三单元，根据待保护关联元组数据集x和查询序列q设置敏感度函数δf：
δf＝sup||q(xk)-q(xu)||1
其中，xk、xu是x中被查询的任意两个元组，xk∈x，xu∈x。然后根据用户个人隐私保护需求初始化隐私预算参数ε。
初始化噪声扰动模块，用于生成初始化噪声并扰动初始查询结果，包括以下子单元：
第一单元，令t＝1，根据拉普拉斯分布概率密度函数
第二单元，扰动初始化查询结果q′1＝q1 y1；
特定自协方差矩阵拉普拉斯噪声生成模块，用于根据新的查询函数来生成满足特定自协方差矩阵的噪声并扰动查询结果，包括以下子单元：
第一单元，判断新的查询函数q2是否与上次的查询函数相同，若q2≠q1，跳转到第三单元得到拉普拉斯噪声变量y2；若q2＝q2，跳转到拉普拉斯噪声更新模块得到拉普拉斯噪声变量y′2；
第二单元，若q2≠q1，计算加扰查询结果q′2＝q2 y2；若q2＝q2，计算加扰查询结果q′2＝q2 y′2；
第三单元，生成符合特定自协方差矩阵的拉普拉斯噪声变量，首先，计算xk、xu的自协方差矩阵ck,u，生成均值为零、协方差矩阵等于自协方差矩阵ck,u的高斯变量gk,u；然后生成概率密度函数为
拉普拉斯噪声更新模块，用于更新拉普拉斯噪声变量，包括以下子单元
第一单元，生成概率密度函数为
第二单元，将高斯变量和指数变量相乘得到新的广义拉普拉斯变量
迭代处理模块，用于迭代处理所有查询直至查询函数序列处理结束，包括以下子单元：
第一单元，令t＝2,3,ln，依次按照特定协方差矩阵拉普拉斯噪声生成模块和拉普拉斯噪声更新模块生成噪声变量并扰动对应的查询结果，得到扰动后的查询结果q′2,l,q′n；
第二单元，输出并发布扰动查询结果序列q′＝{q′1,q′2,l,q′n}。
技术总结