隐私保护分类数据挖掘研究

2008年 12月 第 27卷 4期 内 蒙 古 科 技 大 学 学 报 Journal of InnerMongolia University of Science and Technology December, 2008 Vol. 27, No. 4 　　文章编号 : 1004 - 9762 (2008) 04 - 0329 - 05 隐私保护分类数据挖掘研究 3 张晓琳 ,汤 　彪 (内蒙古科技大学 信息工程学院 ,内蒙古 包头 　014010) 关键词 :数据挖掘 ;隐私保护 ;判定树 ;随机扰动矩阵 中图分类号 : TP279 + . 2　　　文献标识码 : A 摘　要 :随着数据挖掘应用领域的扩大 ,隐私保护的数据挖掘技术研究变得越来越重要. 作为隐私保护数据挖掘的 主要类型 ———隐私保护的分类数据挖掘已经成为近年来数据挖掘领域的热点之一. 如何对原始数据进行变换 ,然 后在变换后的数据集上构造判定树是隐私保护分类数据挖掘研究的重点. 基于随机扰动矩阵提出一种隐私保护分 类挖掘算法.该 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 适用于字符型、布尔类型、分类类型和数字类型的离散数据 ,并且在隐私信息的保护度和挖掘 结果的准确度上都有很大的提高. Privacy preserving classif ication data m in ing research ZHANG Xiao2L in, TANG B iao ( Information Engineering School, InnerMongolia University of Science and Technology, Baotou 014010, China) Key words: data m ining; p rivacy p reserving; decision tree; random perturbation matrix Abstract:W ith the extension of the data m ining p ractical app lications, the research of the p rivacy p reserving data m ining technique be2 comes more and more important. A s the main type of the p rivacy p rotection data m ining, p rivacy p reserving classified data m ining has already become one of the hot spots in the field of data m ining in recent years. How to transform the p rim itive real data and then struc2 ture the decision tree based on the transformed data set is the key point of the p rivacy p reserving classified data m ining. A kind of p riva2 cy p reserving classified m ining algorithm was p roposed on the basis of the random perturbation matrix. This method is suitable to the character type, the Boolean type, the classified type, and the digital type. The p rotective degree of p rivate information and the accurate degree of the result of data m ining were imp roved to a great extent. 　　随着数据挖掘技术的不断发展 ,数据挖掘技术 在许多领域 (比如 :商务决策、科学和医学研究 )的 应用越来越深入. 在这些领域中 ,许多数据库中包含 个人的隐私信息 ,如果把这些数据库的真实数据直 接交给挖掘者 ,难免会泄露个人的隐私信息. 如何在 保护隐私的条件下得到准确的挖掘结果 ,就成了隐 私保护数据挖掘 ( PPDM )的主要研究方向. 目前 ,在 隐私保护的数据挖掘中 ,采用保护隐私信息的方法 有 :加随机偏移量 [ 1 ]、数据加密技术、多方安全计 算 [ 2 ]、随机响应技术 [ 3 ]等. Ship ra Agrawal[4 ]等人提出了一种高隐私度隐私保 护数据挖掘框架 ,该方法主要用于分布式数据库 ,给每 个客户端设置一个随机扰动矩阵 ,然后对这些矩阵求 期望矩阵 ,用这个期望矩阵和伪数据库来重建原数据 集的分布 ,这样大大降低了挖掘结果的准确度 ;葛伟 平 [ 5 ]提出隐私保护的数据挖掘方法 ,该方法采用单属3 收稿日期 : 2008 - 11 - 15 基金项目 :国家社会科学基金资助项目 ( 07XTQ003) ;内蒙古自然科学基金重点资助项目 作者简介 :张晓琳 (1966 - ) ,女 ,内蒙古包头人 ,内蒙古科技大学教授 ,博士 ,主要从事数据库理论与技术研究 1 内 蒙 古 科 技 大 学 学 报 2008年 12月 　第 27卷 第 4期 性随机矩阵对数据扰乱 ,通过生成的多属性联合矩阵 重建原始数据集分布 ,这样提高了挖掘结果的准确度 , 但是它对单属性随机矩阵没有要求 ,矩阵元素随机产 生 ,使的隐私保护度大大下降 ,并且在原数据集转变成 伪数据集后 ,会产生隐私破坏. 针对上述问题 ,本文提出一种基于随机扰动矩 阵的隐私保护分类挖掘的方法 ,该方法通过对原始 数据集预处理 ,使其适应于多种数据类型 ;给除 ID 属性外的每个属性都选择一个随机矩阵 ,增加了隐 私保护度 ;在选择单属性随机扰动矩阵时 ,引入 r2 amp lifying[ 6 ]方法防止隐私破坏 ;通过由单属性生成 的多属联合随机扰动矩阵来重建原数据集分布 ,增 加挖掘的准确性 ;在建立决策树时 ,使用了递归的方 法 ,减少大量的计算. 1　数据预处理 为了使该方法能够处理字符型、布尔类型、分类 类型和数字类型等离散型数据以及便于数据集转换 操作 ,因此要对原始数据集的数据进行预处理. 以 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 1为例 ,处理方法如下 : 表 1　训练数据集 Table 1　The tra in ing da ta set Day Outlook TemperatureHum idity W ind PlayTennis D1 Overcast Hot H igh W eak No D2 Overcast Hot H igh Strong No D3 Overcast Hot H igh M iddle No D4 Sunny Hot H igh W eak Yes D5 Sunny Hot H igh M iddle Yes D6 Rain M ild H igh W eak No D7 Rain M ild H igh M iddle No D8 Rain Hot Normal W eak Yes D9 Rain Cool Normal M iddle No D10 Rain Hot Normal Strong No D11 Sunny Cool Normal Strong Yes D12 Sunny Cool Normal M iddle Yes D13 Overcast M ild H igh W eak No D14 Overcast M ild H igh M iddle No D15 Overcast Cool Normal W eak Yes D16 Overcast Cool Normal M iddle Yes D17 Rain M ild Normal W eak No D18 Rain M ild Normal M iddle No D19 Overcast M ild Normal M iddle Yes D20 Overcast M ild Normal Strong Yes D21 Sunny M ild H igh Strong Yes D22 Sunny M ild H igh M iddle Yes D23 Sunny Hot Normal W eak Yes D24 Rain M ild H igh Strong No 　　通过查询找出每个属性 ( ID属性除外 )域的不 同值 ,例如 :表 1中属性 Outlook域的不同值为 { Sun2 ny, Overcast, Rain} ,属性 Temperature域的不同值为 {Hot,M ild, Cool}等 ,然后用自然数对这些不同的属 性值编码. 编码方法如表 2,训练数据集编码为表 3. 表 2　训练数据集属性域的编码表 Table 2　The cod ing table of a ttr ibute doma in of tra in ing da ta set A 编码 B 编码 C 编码 D 编码 E 编码 Sunny 1 Hot 1 H igh 1 W eak 1 Yes 1 Rain 2 M ild 2 Normal 2 Strong 2 No 2 Overcast 3 Cool 3 M iddle 3 　　注 : A为 Outlook ; B为 emperature; C为 Hum idity; D为 W ind; E 为 PlayTennis 表 3　训练数据集编码表 Table 3　The cod ing table of tra in ing da ta set Day Outlook Temperature Hum idity W ind PlayTennis D1 3 1 1 1 2 D2 3 1 1 2 2 D3 3 1 1 3 2 D4 1 1 1 1 1 D5 1 1 1 3 1 D6 2 2 1 1 2 D7 2 2 1 3 2 D8 2 1 2 1 1 D9 2 3 2 3 2 D10 2 1 2 2 2 D11 1 3 2 2 1 D12 1 3 2 3 1 D13 3 2 1 1 2 D14 3 2 1 3 2 D15 3 3 2 1 1 D16 3 3 2 3 1 D17 2 2 2 1 2 D18 2 2 2 3 2 D19 3 2 2 3 1 D20 3 2 2 2 1 D21 1 2 1 2 1 D22 1 2 1 3 1 D23 1 1 2 1 1 D24 2 2 1 2 2 033 张晓琳等 :隐私保护分类数据挖掘研究 2　原始数据集转换成伪数据集 2. 1　相关定义 (1)前验率 [4 ] (p rior p robability) :在不给任何客户 隐私信息情况下 ,隐私属性值在数据集中占的比率. (2)后验率 [ 4 ] ( posterior p robability) :在给定转 换率和隐私属性转换后的值 ,推出原数据集隐私属 性值的概率. (3)属性值支持计数 [ 5 ] : 设 {A1 , A2 , ⋯, Ak } 表 示数据 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 集 T的属性集 X, Y Α X, Y ≠ <, yi表示 Y 的一种取值 ,则定义 T中 Y属性集上的取值等于 yi 的记录个数为属性值 yi 的支持计数. (4) 隐私破坏 (p rivacy breach) :给定阈值前验 率α1 ,后验率α2. 属性 A的隐私信息值为 u, u转换后 值为 v,则 α1 - to - α2 隐私破坏为 : p[A ( u) ] ≤α1 and p[A ( u) /R ( u) = v ] ≥α2 , α2 - to - α1隐私破坏为 : p[A ( u) ] ≤α2 and p[A ( u) /R ( u) = v ] ≤α1. (5) r2amp lifying : Su为原始属性域 , Sv为扰乱后 的属性域.Π u1 , u2 ∈ S u: p[ u1 → v ]p[ u2 → v ] ≤ r ( r ≥ landϖ u: p[ u → v ] > 0, v ∈ S v) . 2. 2　选择单属性随机扰动矩阵 本文选择 r正定对称矩阵为单属性扰动矩阵.首先 要求用户给定阈值前验率α1和后验率α2 ,要求 0 <α1 <α2 < 1且α1 和α2 比较接近 (α2 - α1 < 0. 5). 在 α2 (1 - α1 ) α1 (1 - α2 ) > r≥1上随机取一个 r值 ,生成 任意属性 A的扰动矩阵如下 : A ij = rx　ifi = j x　o. w. wherex = 1 r + (│Su│ - 1) 　│Su│表示 A的域. A ij = r 1 1 ⋯ 1 r 1 ⋯ 1 1 r ⋯ ⋯ ⋯ ⋯ ⋯ , 矩阵 A ij的值 aij表示 p ( i → j) . 2. 3　由单属性随机矩阵生成多属性联合随 机扰动矩阵 2. 3. 1　生成多属性联合随机扰动矩阵思想 以生成两个属性联合扰动矩阵为例 ,说明生成 多属性联合随机扰动矩阵的思想. 设 A1属性有 n个不同的值 ,属性 A1的随机扰动 矩阵为 n阶方阵 R (A1 ) , A2属性有 m个不同的值 ,属 性 A2 的随机扰动矩阵为 m 阶方阵 R (A2 ) , 则生成 n3 m 阶属性 A1 , A2 联合扰动矩阵 R (A1 , A2 ) 思想 为 : R (A2 ) 中的每一个元素 aij 乘以 R (A1 ) 作为 R (A1 , A2 )中第 i个 n行 ,第 j个 n列的元素. 属性 A1 , A2随机扰动矩阵如图 1,属性 A1 , A2生成的联合扰动 矩阵如图 2. 图 1　属性 A1 , A2 随机扰动矩阵 F ig. 1　Random ized perturba tion ma tr ix of a ttr ibute A1 and A2 图 2　属性 A1 , A2 生成的联合扰动矩阵 F ig. 2　Un ion perturba tion ma tr ix genera ted by a ttr ib2 ute A1 and A2 2. 3. 2　多属性联合随机扰动矩阵性质 (1) 性质 1. 多属性联合随机扰动矩阵的逆等 于单属性的随机扰动矩阵逆的联合. 即 : P (A1 , A2 , ⋯, Ak ) - 1 = P (A - 11 , A - 12 , ⋯, A - 1k ) . (2) 性质 2 . T (A1 , A2 , ⋯, Ak ) 3 P (A1 , A2 , ⋯, Ak ) = D (A1 , A2 , ⋯, Ak ) . T (A1 , A2 , ⋯, Ak ) 表示原始数据中属性 {A1 , A2 , 133 内 蒙 古 科 技 大 学 学 报 2008年 12月 　第 27卷 第 4期 ⋯, Ak } 不同的联合值的支持计数组成行矩阵 , D (A1 , A2 , ⋯, Ak ) 表示变换后数据中属性 {A1 , A2 , ⋯, Ak } 不同的联合值的支持计数组成行矩阵 , P (A1 , A2 , ⋯, Ak ) 表示属性 {A1 , A2 , ⋯, Ak }多属性联 合随机扰动矩阵. 2. 4　隐私保护的扰乱方法 由于被挖掘的数据库为统计数据库 ,属性值为 离散型数据 ,所以属性数据域不大. 本文采用单属性 独立扰乱方法. 首先确定被扰动属性域 │su│,然后 通过下面的扰乱算法扰乱. 设 i为原属性值 , j为扰乱 后的属性值 ,则 i扰乱成 j的概率为该属性扰动矩阵 R (A ) 中元素 aij的值. 扰乱算法如下 : 输入 :属性 A编码后的数据域 S u 属性 A的扰动 R (A ) 输出 :扰动后属性 A的数据域 v[ n ] n = S u; fo r　i = 1 to n 　{ r = random (0, 1) ; / / r为 0到 1的随机数 　fo r　j = 1 to n 　　p ( j) = { a i1, a i2, ⋯, a ij}; / / P ( j) 为扰乱后数据为 j的概率函数 　　If ( F ( j - 1) < r < = F ( j) ) v[ i ] = j; / / F ( j) 为 p ( j) 的分布函数 　} 图 3　扰动算法 F ig. 3　Perturba tion a lgor ithm 3　隐私保护分类挖掘算法 3. 1　相关定义 (1) 熵 ( Entropy) :刻画任意样本集的纯度. 设 S 是 n个数据样本的集合 ,将样本集划分为 c个不同的 类 ci ( i = 1, 2, ⋯, c) ,每个类 ci 含有的样本数目为 ni ,则划分为 c个类信息的熵为 : E ( s) = - ∑ c i =1 pi log2 ( pi ) , 其中 , pi 为 S中的样本属于第 i类 ci的概率 ,即 pi = ni / n. (2) 信 息 增 益 Gain (S, A ) 定 义 为 : 其 中 Gain (S, A ) = E (S ) - E (S, A ) ,其中 E (S, A ) = ∑ v∈V a lues (A ) │Sv │ │S│ E ( sv ) V alues(A ) 为属性 A的所有不同值的集合 , sv是 S中属性 A的值为 v的样本子集 , s是 S中属性 A值为 v的样本集. 3. 2　建立决策树 分类挖掘中最为典型的分类方法是基于决策树 的分类方法 ,决策树 (Decision Tree)是一个类似于 流程图的树结构. 每个内部节点表示在一个属性上 的测试 ,每个分枝代表一个测试输出 ,而树的叶节点 代表类或类分布. 最顶端的节点是根节点. 本文采用 自上而下递归的方式构造决策树. 建立决策树的关键是在每个分支对应的数据集 上找信息增益最大的属性作为分支节点. 通过转变 后的数据集和多属性联合扰动矩阵求属性信息增益 的方法如下 : 设定一个数据集 S, S 的属性集为 {A1 , A2 , ⋯, Ak } ,其中 Ak 为标签属性. (1) 求根节点最大信息增益的属性. 通过公式 T (Ak ) 3 P (Ak ) = D (Ak ) 可以算出标 签属性 Ak 的熵 E (S ) . 通过公式 T (A, Ak ) 3 P (A, Ak ) = D (A, Ak )可以 算出每个属性的熵 E (S, A ) . 通过公式 Gain (S, A ) = E (S ) - E (S, A )求出该 属性的信息增益. (2) 已知 ,根节点为 A1 ,属性 A1 值为 a1 的数据 集为 S1 , 求 a1 分支上分裂节点最大信息增益的属 性. 通 过 公 式 T (A ( a1 ) , Ak ) 3 P (A ( a1 ) , Ak ) = D (A ( a1 ) , Ak ) , A1 ( a1 ) 表示属性 A1 的值为 a1 ,可以 算出在数据集 S1 标签属性 Ak 的熵 E (S1 ) . 通过公式 T (A1 ( a1 ) , A, Ak ) 3 P (A1 ( a1 ) , A, Ak ) = D (A1 ( a1 ) , A, Ak ) , A1 ( a1 ) 可以算出在数据集 S1 上每个属性的熵 E (S1 , A ) . 通过公式 Gain (S1 , A ) = E (S1 ) - E (S1 , A ) 求 出该属性的信息增益. (3)求下层节点同理. 直到生成的数据集中所 有记录的标签属性都相同或所有属性都被分裂过才 结束. 3. 3　决策树剪枝 当决策树创建时 ,由于数据中的噪声和孤立点 , 许多分支反映的是训练数据中的异常. 剪枝方法处 理这种过分适应问题. 通常 ,这种方法使用统计度 量 ,剪去最不可靠的分支 ,从而提高分类的速度和准 确度. 通常有两种剪枝方法 : (1)前剪枝算法是在树的生长过程完成前就进 行剪枝. 如 Friedman提出的限制最小节点大小的方 233 张晓琳等 :隐私保护分类数据挖掘研究 法 ,是当节点处的实例数目小于阈值 k时 ,就停止生 长该节点. (2)后剪枝算法是当决策树的生长过程完成后 再进行剪枝 ,它允许决策树过度生长 ,然后根据一定 的规则 ,减去决策树中那些不具有一般代表性的叶 节点或分支. 本文采用后剪技的方法. 3. 4　由决策树提取分类规则 决策树所表示的分类知识可以被抽取出来并以 IF2THEN形式的分类规则表示. 从决策树的根节点 到任何一个叶节点所形成的路径就构成了一条分类 规则 ,沿着决策树的一条路径所形成的属性值的合 取项就构成了分类规则的前件 (“ IF”部分 ). 叶节点 所标记的类别就构成了分类规则的后件 (“THEN” 部分 ) . 图 4是训练集 (表 1)生成的决策树. 图 4　训练数据集生成的决策树 F ig. 4　D ec ision tree genera ted by tra in ing da ta set 由决策树提取的规则为 : IF Outlook = Overcast AND Hum idity = H igh THEN PlayTennis =No. IF Outlook = Overcast AND Hum idity = Normal THEN PlayTennis = Yes. IF Outlook = Sunny THEN PlayTennis = Yes. IF Outlook = Rain AND Temperature = Hot AND W indy = Strong THEN PlayTennis =No. 　　 IF Outlook = Rain AND Temperature = Hot AND W indy =W eak THEN PlayTennis = Yes. IF Outlook = Rain AND Temperature = M ild THEN PlayTennis =No. IF Outlook = Rain AND Temperature = Cool THEN PlayTennis =No. 4　结论 隐私保护数据挖掘的好坏取决于对隐私信息的 保护程度和挖掘结果的准确度 ,大部分文献的方法 通过牺牲隐私度来换取高的准确度或者牺牲准确度 换取高的隐私度. 本文提出了一种基于随机扰动矩 阵的隐私保护分类挖掘方法 ,适用于字符型、布尔类 型、分类类型和数字类型的离散数据 ,在隐私信息的 保护程度和挖掘结果的准确度都取得了很好的效 果 ,计算量也大大降低. 参考文献 : [ 1 ] 　Agrawal R, Srikant R. Privacy2p reserving data m ining [A ]. the ACM SIGMOD Conference on Management of Data[ C ]. Dallas, Texas: ACM Press, 2000. 4392450. [ 2 ]　L indell Y, Pinkas B. Privacy p reserving data m ining[A ]. Annual International Cryp tology Conference [ C ]. Berlin: Sp ringer2Verlag, 2000. 36254. [ 3 ] 　Du W enliang, Zhan Zhiun. U sing random ized response techniques for p rivacy - p reserving data m ining[A ]. The 9 th ACM SIGKDD International Conference on Knowl2 edge D iscovery and Data M ining[ C ]. W ashington: ACM Press, 2003. 5052510. [ 4 ]　Agrawal S, Haritsa J R. A framework for high2accuracy p rivacy2p reserving M ining [ A ]. the 21 st International Conference on Data Engineering( ICDE) [ C ]. Tokyo, Ja2 pan: IEEE Computer Society , 2005. 1932204. [ 5 ]　葛伟平. 隐私保护的数据挖掘 [D ]. 上海 :复旦大学 , 2005. [ 6 ]　Evfim ievski A, Gehrke J, and Srikant R. L im iting p riva2 cy breaches in p rivacy p reserving data m ining[A ]. ACM PODS. conferencn [ C ]. San D iego, California: ACM Press, 2003. 2112222. 333