随机投影技术数据挖掘隐私的保护方法

黄取治

(福建师范大学信息技术学院，福建　福州350007)



随机投影技术数据挖掘隐私的保护方法

黄取治

(福建师范大学信息技术学院，福建福州350007)

摘要：为确保隐私保护数据挖掘中所存在的维数灾难问题得到有效解决，文章提出了将基于随机投影技术的一种数据挖掘隐私保护法。这种方法对攻击者能够以随机投影矩阵推测的方式重建原始数据进行了综合考虑，首先将安全子空空间概念提出来，再构建安全子空间映射，在低失真嵌入实现的同时，能够有效确保数据安全。通过实验证明，在对数据隐私予以保护的前提下，这种方法为数据质量提供有效保障。

关键词：数据挖掘;随机投影技术;隐私保护

由于迅猛发展的信息技术，使得相关企业机构能够收集有效的个人与组织信息，进而实施数据分析及挖掘，以此为机构带来更多科研及商业价值。然而，在数据分布过程中，人工普查数据、医疗数据及交易数据等很多个人隐私信息均存在隐私泄露的问题[1]。

1相关概念

1.1　随机投影

1.2　通用哈希函数

由均匀分布的哈希函数族中将一个哈希函数随机选取出来，是通用哈希函数理念的主要内容，基于给定输入，对哈希函数随机选择后，在已知概率范围中得出相同哈希值，即：从哈希函数族H中，通过随机选择的方式给定一个哈希值y与哈希函数h，使其满足y=h(x)的x值是均匀分布的。

2安全子空间方法

3实验分析

3.1　实验数据与环境

实验对三个数据集进行选取，这三个数据集中，有两个选于UCI学习数据库,即：arr hythmia数据集、arcene数据集，其中arcene数据集中含有1000个属性与900个样本，这一数据集本身属于二分类问题。此外，arr hythmia数据集中有279个属性与453个样本。三个数据集中，还有一个数据集为Reuters-5topic，此为RCVI数据集子集。本实验将320个实例选取出来，在将非关键词汇去除后，将4186个属性整理出来[4]。具体实验环境：4GB内存，intelcorei5处理器，MicrosoftWindows7，1TB硬盘,对matlab测试(32位)予以使用。

3.2　实验结果

首先对比传统高斯随机投影和安全子空间法对内积保护程度和原始数据间距离，评估在数据可用性领域两种方法的性能，再选取选取K-均值聚类算法与支持向量机分算法实施测试，对在数据挖掘应用方面两者的有效性进行评估，通过原始数据挖掘精度与隐私保护后挖掘精度比值对其有效性进行度量，如果原始数据和隐私保护数据上两者的挖掘结果精度分别为C0、Cp,则数据有效性Qc=Cp/Co.

哈希函数在实验中通过乘法通用哈希，假设A={a∣a([2l],a∈奇数},那么，该通用哈希函数族：H={ha︱a(A},该公式中，ha(x)=div2l-m(axmod2l),如果d为偶数，则l=log2d,如果dw为奇数，那么l=log2(d+1)；如果k∈偶数，那么m=log2k,如果K∈奇数，那么m=log2(k+1),其中k表示子空间维数,d表示原始数据维数,div取商整数部分，mod为模运算。

1、实验一：内积和欧式距离

本实验对arcene数据集进行选取，因为矩阵随机生成，所以实验各运行大约10次，选取误差平均值，不同投影维数下，内积与欧式距离两者相对误差见图1，从中可知，安全子空间对内积与欧式距离的保护大致和高斯投影等同，而且具有越大的投影维数，其结果与高斯投影越接近，且投影维数越大，相对误差也就越低，如果投影维数为3000，那么相对误差就会降低0.2%。由此充分表明安全子空间在合理、有效投影维数内能够确保数据可用性[5]。

2、实验二：聚类

通过Reuters-5topic数据集与K均值算法对聚类中安全子空间有效性进行测试，分别对数据转换后聚类精度与原始数据聚类精度进行测试，假设K均值算法K=5,以欧式距离作为相似度度量距离，聚类精度在各投影维数下见表1,在投影维数大约是原始数据维数1/2时，投影数据聚类结果和实际聚类相接近，通过对比显示，该实验数据具有比较高的数据集维数，具有越高的原始维数，那么安全子空间法就具有越好的应用效果。

表1　各投影维数下聚类准确率

4结语

文章基于随机投影技术的一种数据挖掘隐私保护法提出来，并将安全子空间映射与安全子空间的概念提出来，并创建安全子空间映射，通过投影转换来保护原始数据，利用哈希技术对投影矩阵予以加密生成，从数学角度证明了安全子空间法本身所具有的有效性，并将相关理论依据提供出来，在高位数据挖掘处理过程中，这种方法可以对隐私问题进行更好的保护，能够有效确保数据安全。

参考文献：

[1]张锋,孙雪冬,常会友等·两方参与的隐私保护协同过滤推荐研究[J].电子学报,2009,37(1):84-89.

[2]李光,王亚东·一种改进的基于奇异值分解的隐私保持分类挖掘方法[J].电子学报,2012,40(4):739-744.

[3]CC Aggarwal, P S Yu·A General Survey of Privacy-preservingData Mining Models and Algorithms [M] .NewYork:Springer US, 2008：11-52 .

[4]SLee , M G Genton , R B Arellano-Valle .Perturbation of numericalconfidential data via skew-t distributions[J].ManagementScience , 2010, 56(2):318-333.

[5] M Dietzfelbinger , T Hagerup , J Katajainen, M Penttonen.Areliable randomized algorithm for the closest-pair problem[J].Journal of Algorithms,1997,25(1):119 -120.

(责任编辑：王德红)

Research on Protection Method of Privacy Random Projection Based on Data Mining Technology

Huang Quzhi

(Information Technology College, Fujian Normal University, Fuzhou350007, Fujian, China)

Abstract：In order to ensure the privacy of data mining in the presence of the curse of dimensionality issues are effectively addressed, this article will dig Privacy Protection Act proposed is based on a random data projection technology. In this way the attacker can be presumed in a random manner as the projection matrix to reconstruct the original data were taken into account, first, the proposed concept of the security sub-blank space, and then build the security sub-space mapping, while embedded achieve low distortion, it is possible to ensure an effective data security. Through experiments proved to be protected under the premise of data privacy, this method provides effective protection for data quality.

Key words:data mining;stochastic projection technology;privacy protection

中图分类号：TP311

文献标识码：A

文章编号：1673-9507(2015)01-0129-02

作者简介：黄取治(1982.09~)，福建师范大学信息技术学院讲师。研究方向：计算机数据挖掘。

收稿日期：2014-11-30