面向隱私保護(hù)的數(shù)據(jù)挖掘和數(shù)據(jù)發(fā)布方法研究(童云海)

1、面向隱私保護(hù)的數(shù)據(jù)挖掘和數(shù)據(jù)發(fā)布方法研究Privacy Preserving Data Mining and Data PublishingMarch 2012Yunhai Tong（童云海）School of Electronics Engineering and Computer Science,Peking UniversityCCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用2討論內(nèi)容 面向隱私保護(hù)的數(shù)據(jù)挖掘方法 研究背景和問(wèn)題描述 體系架構(gòu)和評(píng)估體系 關(guān)聯(lián)規(guī)則挖掘中的隱私保護(hù)方法 面向隱私保護(hù)的數(shù)據(jù)發(fā)布方法 研究背景和問(wèn)題描述 面向微數(shù)據(jù)發(fā)布的身份保持的K-匿名CCF

2、YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用3隱私問(wèn)題的產(chǎn)生 信息技術(shù)的飛速發(fā)展讓各類數(shù)據(jù)的采集、存儲(chǔ)、使用變得方便快捷 醫(yī)院信息管理系統(tǒng)（電子病例） 人口管理系統(tǒng)（市民卡） 金融業(yè)務(wù)系統(tǒng)（銀行卡）病人基本信息、疾病信息、醫(yī)療服務(wù)與藥品購(gòu)買記錄市民家庭住址、收入狀況、個(gè)人愛(ài)好、犯罪記錄客戶私有信息及其交易行為CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用4數(shù)據(jù)分密碼學(xué)隱私保護(hù)方法的研究通過(guò)多用戶、多權(quán)限、多層次的資源訪問(wèn)控制策略，實(shí)現(xiàn)對(duì)隱私數(shù)據(jù)的安全存數(shù)據(jù)庫(kù)安全信息安全隱私保護(hù)統(tǒng)計(jì)學(xué)利用有效的加密算法對(duì)隱私數(shù)據(jù)進(jìn)行加密，再通過(guò)有效的解密算法實(shí)現(xiàn)數(shù)據(jù)的訪問(wèn)和使用析方

3、法通過(guò)數(shù)據(jù)干擾和查詢限制等方法，在不針對(duì)個(gè)體信息的條件下得到普遍的規(guī)律儲(chǔ)與訪問(wèn)CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用5數(shù)據(jù)挖掘中的隱私保護(hù)問(wèn)題 數(shù)據(jù)挖掘是從大量數(shù)據(jù)中抽取出新穎的、潛在有用的模式或者規(guī)則 關(guān)聯(lián)規(guī)則挖掘、分類、聚類、異常點(diǎn)分析 數(shù)據(jù)挖掘所關(guān)注信息和各類挖掘結(jié)果的隱藏性，使得人們對(duì)數(shù)據(jù)挖掘中的隱私保護(hù)問(wèn)題異常關(guān)注 解決數(shù)據(jù)挖掘中的隱私保護(hù)問(wèn)題成為研究的熱點(diǎn)CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用6 從大量數(shù)據(jù)中挖掘出來(lái)的模式或者規(guī)則，通常是針對(duì)綜合數(shù)據(jù)而非細(xì)節(jié)數(shù)據(jù) 是否可以在不精確訪問(wèn)原始數(shù)據(jù)詳細(xì)信息的條件下，挖掘出準(zhǔn)確的模式與規(guī)則

4、呢？隱私保護(hù)數(shù)據(jù)挖掘問(wèn)題的描述 原始數(shù)據(jù)中包含著數(shù)據(jù)所有者（或者第三方）的隱私信息，而挖掘者需要從中獲取有用的知識(shí)CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用7相關(guān)研究工作 IBM Almaden Research Center (Rakesh Agrawal)Privacy Preserving Data Mining, SIGMOD2000Privacy Preserving OLAP, SIGMOD2005 Stanford University (H. G. Molina & R. Motwani)Privacy & Databases, PORTI

5、A project with Yale & Microsoft Purdue University (Chris Clifton)Privacy Preserving Distributed Data Mining Syracuse University (Wenliang Du)Randomization approaches Chinese University of Hong KongPersonalized Privacy Preservation, SIGMOD2006 CMU、UIUC、Cornell、Texas A&M 等CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其

6、在網(wǎng)絡(luò)信息安全中的應(yīng)用8架構(gòu)及其流程評(píng)估指標(biāo)體系架構(gòu)及其流程研究基礎(chǔ)有效處理方法關(guān)鍵技術(shù)評(píng)估指標(biāo)體系可靠保障數(shù)據(jù)挖掘算法成果體現(xiàn)數(shù)據(jù)處理強(qiáng) 相 關(guān) 的 隱 私 屬 性數(shù) 值 類 型 隱 私 數(shù) 據(jù)枚 舉 類 型 隱 私 數(shù) 據(jù)布 爾 類 型 隱 私 數(shù) 據(jù)特征重構(gòu)我們研究的重點(diǎn)內(nèi)容隱私保護(hù)的數(shù)據(jù)挖掘算法CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用9項(xiàng)目支持 國(guó)家自然科學(xué)基金項(xiàng)目 “面向隱私保護(hù)的數(shù)據(jù)挖掘方法研究” 北京市科學(xué)技術(shù)委員會(huì)博士論文資助項(xiàng)目 政府、金融、電信行業(yè)實(shí)際應(yīng)用項(xiàng)目CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用10數(shù)據(jù)挖掘中隱私保護(hù)方法的

7、架構(gòu)與流程 隱私數(shù)據(jù)處理方法的多樣性 數(shù)據(jù)變換、數(shù)據(jù)阻塞、數(shù)據(jù)歸并、數(shù)據(jù)交換、數(shù)據(jù)抽樣等 數(shù)據(jù)挖掘算法的多樣性 關(guān)聯(lián)規(guī)則挖掘、分類、聚類等 系統(tǒng)的簡(jiǎn)潔性和可操作性 支持海量隱私數(shù)據(jù)的分析與挖掘挖掘算法XM挖掘結(jié)果X11發(fā)布數(shù)據(jù)庫(kù)D數(shù)據(jù)處理隱私數(shù)據(jù)需要保護(hù)原始數(shù)據(jù)庫(kù)D CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用受到保護(hù)特征重構(gòu)隱私保護(hù)策略挖掘挖掘算法M算法調(diào)整結(jié)果X盡量接近數(shù)據(jù)特征FKD3 架構(gòu) Knowledge Discovery in Distorted Database隱私數(shù)據(jù)Knowledge Discovery in DatabaseCCF YOCSEF 報(bào)告會(huì)

8、：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用12KD3 架構(gòu)的工作流程1. 分析數(shù)據(jù)特征2. 確定保護(hù)策略（參數(shù)選擇）3. 進(jìn)行數(shù)據(jù)處理（參數(shù)使用）4. 調(diào)整挖掘算法（參數(shù)使用）5. 實(shí)施特征重構(gòu)（參數(shù)使用）6. 生成挖掘結(jié)果（參數(shù)使用）數(shù)據(jù)所有者數(shù)據(jù)挖掘者CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用13方法的評(píng)估指標(biāo)體系 有效的衡量標(biāo)準(zhǔn)和評(píng)價(jià)指標(biāo)體系，可以幫助用戶根據(jù)不同的數(shù)據(jù)特征和應(yīng)用需求，選擇出最合適的隱私保護(hù)技術(shù) 四個(gè)方面的評(píng)估指標(biāo)體系 隱私性 準(zhǔn)確性 高效性 適用性CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用14隱私性 方法對(duì)隱私信息的保護(hù)程度，可以用

9、被保護(hù)的隱私信息仍然被發(fā)現(xiàn)或者預(yù)測(cè)出來(lái)的可能性來(lái)衡量 分類屬性：隱私破壞系數(shù) BreachBreach = P真實(shí)數(shù)據(jù)所占的比例P真實(shí)數(shù)據(jù)被識(shí)別出來(lái)的概率P非真實(shí)數(shù)據(jù)所占的比例P非真實(shí)數(shù)據(jù)被識(shí)別出來(lái)的概率P非真實(shí)數(shù)據(jù)被還原的概率CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用15隱私性(續(xù)) 連續(xù)值屬性：隱私破壞區(qū)間寬度 BreachWidth 如果原始數(shù)據(jù) x 落到區(qū)間x1, x2上的概率為c%，則稱區(qū)間x1, x2是置信度為c%的隱私破壞區(qū)間，而該區(qū)間的寬度(x2x1)就定義了置信度為c%的隱私破壞區(qū)間寬度CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用16

10、準(zhǔn)確性 應(yīng)用隱私保護(hù)方法之后的挖掘結(jié)果誤差，或有效信息損失和數(shù)據(jù)功能性損失的程度 原始數(shù)據(jù)與發(fā)布數(shù)據(jù)的內(nèi)在特征吻合程度 實(shí)際挖掘結(jié)果與真實(shí)結(jié)果之間的差異 重構(gòu)特征的誤差和方差分析CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用17高效性 方法所需的時(shí)間和空間代價(jià)，或?yàn)榱吮Ｗo(hù)隱私信息而額外花費(fèi)的時(shí)間和使用的空間 算法運(yùn)行的效率和資源使用情況 方法的整體性能 數(shù)據(jù)處理的性能 特征重構(gòu)的性能 針對(duì)發(fā)布數(shù)據(jù)進(jìn)行挖掘的性能 通過(guò)時(shí)間和空間計(jì)算復(fù)雜度來(lái)進(jìn)行評(píng)估CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用18適用性 方法適用于不同數(shù)據(jù)類型、不同數(shù)據(jù)挖掘算法和不同數(shù)據(jù)分布狀

11、況的能力 提高數(shù)據(jù)處理方法對(duì)各類數(shù)據(jù)挖掘算法的適用性水平，有助于提高數(shù)據(jù)挖掘中隱私保護(hù)方法的一致性和規(guī)范性水平 數(shù)據(jù)入侵者會(huì)試圖通過(guò)各種數(shù)據(jù)挖掘算法，來(lái)威脅隱私信息的安全，只有適用性強(qiáng)的通用方法，才能真正實(shí)現(xiàn)有效的隱私保護(hù)CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用19關(guān)聯(lián)規(guī)則挖掘中的隱私保護(hù)方法 在KD3架構(gòu)與流程的基礎(chǔ)上實(shí)現(xiàn) 提出了部分隱藏的隨機(jī)化回答（RRPH）方法 數(shù)據(jù)干擾和查詢限制的隱私保護(hù)策略相結(jié)合 布爾類型的數(shù)據(jù)處理和特征重構(gòu)方法 關(guān)聯(lián)規(guī)則挖掘中基于RRPH的隱私保護(hù)方法 相同時(shí)間和空間開(kāi)銷 更好的隱私保護(hù)程度 更高的挖掘結(jié)果準(zhǔn)確性算法CCF YOCSEF 報(bào)

12、告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用20D頻繁項(xiàng)集生成算法總體架構(gòu)隱私項(xiàng)需要保護(hù)原始事務(wù)集隱私項(xiàng)受到保護(hù)發(fā)布事務(wù)集D數(shù)據(jù)處理特征重構(gòu)RRPH方法關(guān)聯(lián)規(guī)則隱私保護(hù)頻繁項(xiàng)集支持度 生成計(jì)數(shù)算法調(diào)整統(tǒng)計(jì)學(xué)究成果 部分隱藏的隨機(jī)化回答（RRPH）方法 1 XCCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用21原始數(shù) 關(guān)處理后的數(shù)據(jù)均與相結(jié)合據(jù)直接相 引入 中的研提供的所有數(shù)據(jù)都是真實(shí)數(shù)據(jù)RRPH方法 現(xiàn)有的數(shù)據(jù)處理方法 數(shù)據(jù)干擾策略 查詢限制策略00 0 1 10 0 1 01 1 0 0 10 01 0 1 1 1 0 0 X 支持布爾類型的數(shù)據(jù)處理和特征重構(gòu) 0 0 1 0 X

13、 用于實(shí)現(xiàn)關(guān)聯(lián)規(guī)則挖掘中的隱私保護(hù) X 1 1 1 0CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用22RRPH的數(shù)據(jù)處理方法 隨機(jī)化參數(shù)，0p1, p2, p31，且 p1+p2+p3=1 對(duì) x0,1，令 r1=x, r2=1, r3=0，隨機(jī)函數(shù) r(x) 以概率 pj返回 rj 用向量 X=(x1, x2, ., xn)表示數(shù)據(jù)庫(kù) D 中的一條記錄，其中 xi0,1 用 Y=R(X) 生成隨機(jī)向量 Y=(y1, y2, ., yn)，其中 yi=r(xi)，分別以概率 p1, p2, p3 返回 xi, 1, 0 隨機(jī)向量 Y 在形式上與原始向量相同，作為處理后的數(shù)據(jù)

14、記錄被加入到數(shù)據(jù)庫(kù) D 中p1xp21p30CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用 p2p1 序號(hào)XAYA映射概率123400110101p1+p3p2p3p1+p2隱私保護(hù)的頻繁項(xiàng)集生成算法 1-項(xiàng)集的支持度計(jì)算 表示項(xiàng) A 在 D 中的支持度 表示項(xiàng) A 在 D 中的支持度 (p1 p2)(1)p2 p1 p22323mij tmax(0,i jk)C j(p1 p2)t p3Ck j p2CC=MC，C 1Ck C ，C 1CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用24k-項(xiàng)集的支持度計(jì)算 A=i1, i2, , ik 是一個(gè) k-項(xiàng)集 恰

15、好包含 A 中 j 項(xiàng)的 D 中事務(wù) T（共 Cj個(gè)）經(jīng)過(guò) RRPH 方法處理，變成為恰好包含 A 中 i 項(xiàng)的 D 中事務(wù) T（共 Ci 個(gè)）的概率 mij都相等，M=mij是(k+1)(k+1)矩陣C0 C0 Ck 當(dāng) M 可逆時(shí)，令 M-1=aij，則項(xiàng)集 A 的支持度計(jì)數(shù)為Ck ak,0C0 ak,1C1 ak,kCk ititjtmin(i, j) t(p1 p3)ki jtBreach1= p p+(1-p)(1-p)1= p (1 p)CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用25RRPH方法的隱私性分析 在真實(shí)數(shù)據(jù)所占的比例相同，都為 p 的情況下 MAS

16、K方法VLDB2002，隨機(jī)化參數(shù)為 p， Breach1 Breach2= 當(dāng)時(shí)，Breach1 Breach2p1 2p21 2( 2p1)( 2p1)(p 1)p 12p3 2p2 p1p1120 p 22,(p ),(p )p (1 p2)2p1p2n (2p 1) 4p 4np (2p 1)26 MASK 方法 RRPH 方法 取 p1=p，p2=p3，則 當(dāng)RRPH方法的準(zhǔn)確性分析121 (1 p)2p1 1 12p(1 p)n(2p1)2Var( 1) 2 p2p1 2np1 2 2p1(1 p1)np1 2Var( 2) (1 p)(1 p)4np2p2(1 p2)np1 2V

17、ar( 2) 1 和 2 都是 的無(wú)偏估計(jì)量，而)122,(p (1 p)( 3p 1)2 21 p21 p pVar( 1)Var( 2) 13 p 1時(shí)，Var( 1) Var( 2)CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用平均項(xiàng)集度誤差（）CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用2520151050實(shí)驗(yàn)結(jié)果300.10.20.3 0.35 0.4 0.45 0.49 0.51 0.55 0.6 0.65 0.70.80.9MASKRRPH隨機(jī)化參數(shù) p MASK方法的誤差變化比較大當(dāng) p 接近 0 或 1 時(shí)，挖掘結(jié)果比較準(zhǔn)確在 p 從 0

18、 或 1 接近 0.5 的過(guò)程中，挖掘結(jié)果準(zhǔn)確性顯著下降 RRPH方法的誤差變化相對(duì)比較平穩(wěn)隨著 p 值從 0 增加到 1，挖掘結(jié)果的準(zhǔn)確性不斷提高2727CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用28RRPH方法的優(yōu)勢(shì) 當(dāng)時(shí)，RRPH 方法比 MASK 方法同時(shí)具有更好的隱私性和更高的準(zhǔn)確性 權(quán)衡數(shù)據(jù)的隱私性和挖掘結(jié)果的準(zhǔn)確性，我們建議在區(qū)間0.35, 0.6上選取隨機(jī)化參數(shù) p 的值，來(lái)使用RRPH方法進(jìn)行隱私保護(hù)的關(guān)聯(lián)規(guī)則挖掘1213 p CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用29樸素貝葉斯分類中的隱私保護(hù)方法 在KD3架構(gòu)與流程的基礎(chǔ)上實(shí)

19、現(xiàn) 擴(kuò)展的部分隱藏隨機(jī)化回答（ERRPH）方法 RRPH方法在數(shù)據(jù)類型上的擴(kuò)展 枚舉類型的數(shù)據(jù)處理和特征重構(gòu)方法 轉(zhuǎn)換的隨機(jī)化回答（TRR）方法 數(shù)值類型的數(shù)據(jù)處理和特征重構(gòu)方法 分類挖掘中基于ERRPH和TRR的隱私保護(hù)方法 實(shí)現(xiàn)了完整的樸素貝葉斯分類算法 同時(shí)支持分類屬性和連續(xù)值屬性的數(shù)據(jù)CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用30討論內(nèi)容 面向隱私保護(hù)的數(shù)據(jù)挖掘方法 研究背景和問(wèn)題描述 體系架構(gòu)和評(píng)估體系 關(guān)聯(lián)規(guī)則挖掘中的隱私保護(hù)方法 面向隱私保護(hù)的數(shù)據(jù)發(fā)布方法 研究背景和問(wèn)題描述 面向微數(shù)據(jù)發(fā)布的身份保持的K-匿名CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)

20、信息安全中的應(yīng)用31數(shù)據(jù)發(fā)布中的隱私保護(hù) 核心問(wèn)題：在保護(hù)隱私的前提下，發(fā)布較為準(zhǔn)確的數(shù)據(jù) 統(tǒng)計(jì)數(shù)據(jù)庫(kù)把數(shù)據(jù)發(fā)布分為三種類型 微數(shù)據(jù)：指包含個(gè)體信息的數(shù)據(jù)； 聚集數(shù)據(jù)：指匯總之后的各項(xiàng)分類的統(tǒng)計(jì)數(shù)據(jù)； 其他統(tǒng)計(jì)數(shù)據(jù)：包括其他各種類型的總體描述，比如回歸因子、相對(duì)指數(shù)等。CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用32我們研究的重點(diǎn) 微數(shù)據(jù)發(fā)布場(chǎng)景 分析單一個(gè)體對(duì)應(yīng)多個(gè)記錄的情況，提出了身份保持的匿名模型 分析動(dòng)態(tài)數(shù)據(jù)發(fā)布的場(chǎng)景和隱私推理途徑，提出了t-rotation模型處理動(dòng)態(tài)數(shù)據(jù) 聯(lián)機(jī)分析處理(OLAP)中的數(shù)據(jù)保護(hù) 基于度量的OLAP數(shù)據(jù)隱私保護(hù)方法 基于維度的OLA

21、P數(shù)據(jù)隱私保護(hù)方法CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用33問(wèn)題提出 很多部門和單位（例如：醫(yī)院）需要發(fā)布一些數(shù)據(jù)表。包含個(gè)體信息的表稱為微數(shù)據(jù)（microdata） 微數(shù)據(jù)是記錄個(gè)人信息的數(shù)據(jù) 身份標(biāo)識(shí)屬性（Individually Identifying Attribute ，簡(jiǎn)稱ID ）：記錄了可以唯一識(shí)別個(gè)人的取值，比如身份證號(hào)、電話號(hào)碼、姓名等信息 準(zhǔn)標(biāo)識(shí)屬性（Quasi-identifiers，簡(jiǎn)稱QI）：記錄了對(duì)個(gè)人的一些類型屬性的取值，比如性別、所在的郵政編碼、出生日期等 敏感屬性（Sensitive Attribute，簡(jiǎn)稱ST）：記錄了個(gè)人不愿為人

22、所知的取值信息，比如個(gè)人收入、所患病癥等CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用34問(wèn)題提出：微數(shù)據(jù)發(fā)布場(chǎng)景 為了提供研究，醫(yī)院發(fā)布了一個(gè)病人情況表 簡(jiǎn)單的方法：去掉“身份標(biāo)識(shí)屬性”publishCCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用35連接推理發(fā)布表Quasi-identifier (QI) attributes選民登記表An adversaryCCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用36連接推理 Swe00的研究表明，87的美國(guó)人口信息可以通過(guò)性別、出生日期、5位郵政編碼進(jìn)行個(gè)人重建 我們研究了寧波城區(qū)中的居民數(shù)據(jù)，

23、得到了類似的結(jié)論 78的人口可以通過(guò)出生日期和6位郵政編碼唯一確定 58的人口可以通過(guò)出生日期和5位郵政編碼唯一確定CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用37問(wèn)題定義(1) 設(shè)數(shù)據(jù)集的模式：T=ID1，IDr，QI1，QIs，ST1，STt IDi (i=1，2，r)：身份標(biāo)識(shí)屬性 QIj (j=1，2，s)：準(zhǔn)標(biāo)識(shí)屬性 STk (k=1，2，t)：敏感屬性 為了保護(hù)個(gè)人隱私，發(fā)布數(shù)據(jù)集需要設(shè)定一個(gè)隱私保護(hù)需求 為了達(dá)到隱私保護(hù)需求，需要對(duì)數(shù)據(jù)集T中的元組t進(jìn)行轉(zhuǎn)化得到t，設(shè)轉(zhuǎn)化函數(shù)為fCCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用38問(wèn)題定義(2)

24、 對(duì)轉(zhuǎn)化函數(shù)f 設(shè)t=( d1，dr，q1，qs，s1，st)，f把t轉(zhuǎn)化為t( d1，dr，q1，qs，s1，st)，即t=f(t)。 通常在微數(shù)據(jù)發(fā)布處理方法中，f并不修改敏感屬性的取值，即sk=sk，(k=1，2，t) 對(duì)于需要處理的數(shù)據(jù)集T，轉(zhuǎn)化函數(shù)f把T轉(zhuǎn)化為發(fā)布數(shù)據(jù)集PT，其中PT=f(t)|tT。轉(zhuǎn)化后( q1，qs)取值相同的那些元組形成一個(gè)QI分組。 為了盡量準(zhǔn)確地評(píng)價(jià)發(fā)布數(shù)據(jù)，需要建立評(píng)價(jià)指標(biāo)，設(shè)為CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用39問(wèn)題定義(3) 隱私保護(hù)的數(shù)據(jù)發(fā)布問(wèn)題可以表示為一個(gè)四元組PPDP=（T，f，） T是需要發(fā)布的數(shù)據(jù)集，發(fā)布的

25、數(shù)據(jù)集為PTf(t)|tT 是隱私保護(hù)需求f 是轉(zhuǎn)化函數(shù) 是對(duì)發(fā)布數(shù)據(jù)集的評(píng)價(jià)結(jié)果 隱私保護(hù)的數(shù)據(jù)發(fā)布問(wèn)題就是在滿足隱私保護(hù)需求的前提下，最大化數(shù)據(jù)有效性指標(biāo) 實(shí)現(xiàn)隱私信息的合理保護(hù)和獲得數(shù)據(jù)信息的最大效用抑制隱私保護(hù)需求評(píng)價(jià)指標(biāo)CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用記錄處理k-匿名l-多樣化(,k)-匿名背景知識(shí)隱私攻擊待發(fā)布表中間表屬性處理發(fā)布表外部表40處理的基本框架概化有損分解CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用41相關(guān)研究工作 隱私保護(hù)需求k-anonymity (TKDE01)l-diversity (ICDE06)(,k)-a

26、nonymity (KDD06)t-closeness (ICDE07)個(gè)性化隱私 (SIGMOD06) 轉(zhuǎn)化方法單維概化 (TKDE01)多維概化 (ICDE06)有損連接 (VLDB06)空間索引 (VLDB07,VLDB07)CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用42相關(guān)研究工作 評(píng)價(jià)指標(biāo) 概化比例DR (KDD02) 可識(shí)別性DM (ICDE05) 確定性代價(jià)NCP (KDD06) 隱私攻擊 Minimality Attack (VLDB07) Privacy Skyline (VLDB07)CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用43

27、隱私保護(hù)需求 研究者提出了多種隱私保護(hù)需求 k-anonymity：每個(gè)QI分組中至少包含k個(gè)元組 l-diversity：每個(gè)QI分組中的敏感屬性至少有l(wèi)個(gè)不同的取值 (,k)-anonymity：每個(gè)QI分組中的每個(gè)敏感屬性取值的概率不超過(guò),并且每個(gè)QI分組中至少包含k個(gè)元組 t-closeness 4 QI 分組CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用44anonymous）QI 屬性ST屬性隱私保護(hù)需求：k-anonymity 具有相同的準(zhǔn)標(biāo)識(shí)屬性組(QI)的元組至少有k個(gè)（2-CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用45數(shù)據(jù)轉(zhuǎn)化方法：概

28、化 概化關(guān)系D ：設(shè)兩個(gè)域Di，Dj，|Dj| |Di|，Dj稱為Di的一個(gè)概化，如果對(duì)任何一個(gè)diDi，都存在djDj，dj是di的概化。CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用46數(shù)據(jù)轉(zhuǎn)化方法：有損分解 有損分解 設(shè)數(shù)據(jù)表T，屬性集AGID QI ST，其中GID屬性用于記錄每個(gè)元組分組之后的分組標(biāo)號(hào)，QI是準(zhǔn)標(biāo)識(shí)屬性集合，ST是敏感屬性集合。 將表T分解為兩個(gè)表STT和QIT進(jìn)行發(fā)布 QITGID QI STTGID ST23M 1pneumonia35591dyspepsia6565QIT表47有損分解方法 發(fā)布表變成兩張表，類標(biāo)識(shí)屬性表(QIT)和敏感屬性表（

29、STT）Count2221221Age Sex23 M27355961MMMF13000590001200054000656570FFF250002500030000gastritisSTT表AgeZipcode11000DiseaseGroup-ID DiseaseSex ZipcodeGroup-ID1100027M 1M 11M 21300059000120001dyspepsia dyspepsiapneumonia2 bronchitispneumonia flu61F 2F 2F 2540002500025000flugastritisflu70F30000bronchitisMi

30、crodataCCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用47CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用48身份保持的匿名 現(xiàn)有的匿名方法只考慮每個(gè)個(gè)體只出現(xiàn)一次的情況不考慮身份標(biāo)識(shí)屬性，直接刪除大量信息損失,只保留QI與ST的關(guān)系，沒(méi)有保留ST之間的關(guān)系可能帶來(lái)部分元組敏感屬性的隱私保護(hù)度降低CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用49身份保持的匿名 四元組PPDP=（T，f，）中，設(shè)t=( d1，dr，q1，qs，s1，st) 現(xiàn)有方法中，f把t轉(zhuǎn)化為t(q1，qs，s1，st) 身份保持的匿名中，t( d，q1，qs，s1

31、，st)，其中d是重編碼后的身份屬性取值，多個(gè)身份屬性只保留一個(gè)即可。 身份保持的匿名 考慮了單一個(gè)體出現(xiàn)多次的情況 提高信息有效性，保留QI與ST的關(guān)系以及ST之間的關(guān)系 是現(xiàn)有方法的一般形式CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用50隱私保護(hù)需求 身份保持的隱私保護(hù)需求 Identity-reserved k-anonymity：每個(gè)準(zhǔn)標(biāo)識(shí)屬性分組中至少有k個(gè)不同的個(gè)體 Identity-reserved (k,l)-anonymity：每個(gè)準(zhǔn)標(biāo)識(shí)屬性分組中至少有k個(gè)不同的個(gè)體，并且敏感屬性取值不少于l個(gè) Identity-reserved (,)-anonymit

32、y：每個(gè)準(zhǔn)標(biāo)識(shí)屬性分組中任何個(gè)體所占頻率不超過(guò)，每個(gè)敏感屬性取值頻率不超過(guò)CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用51數(shù)據(jù)轉(zhuǎn)化方法 屬性處理方法 原有的方法就是簡(jiǎn)單刪除身份屬性 對(duì)身份屬性進(jìn)行處理 選擇一個(gè)身份屬性進(jìn)行隨機(jī)化重編碼 刪除其他身份屬性 匿名實(shí)現(xiàn)方法 概化 有損分解CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用52數(shù)據(jù)轉(zhuǎn)化方法：概化 單維全子樹(shù)重編碼不要求同一屬性的取值概化到相同層次 提出一種自底向上的全子樹(shù)重編碼算法檢查所有元組，將滿足匿名要求的元組添加上分組標(biāo)號(hào)選擇一個(gè)準(zhǔn)標(biāo)識(shí)屬性進(jìn)行概化，檢查還沒(méi)有分組的元組，將滿足匿名要求的元組添加上組標(biāo)號(hào)這一過(guò)程重復(fù)下去，直到所有元組都被添加了組標(biāo)號(hào)或者剩余元組的數(shù)目達(dá)不到匿名要求（比如當(dāng)k=7時(shí)，剩余5個(gè)元組）對(duì)于這些剩余的元組，進(jìn)行遷移和合并的方法進(jìn)行處理CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用53要求身份保持的2-匿名要求身份保持的（0.5,0.5）-匿名CCF YOCSEF 報(bào)告會(huì)：數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息安全中的應(yīng)用54數(shù)據(jù)轉(zhuǎn)