分組隨機化隱私保護頻繁模式挖掘*

郭宇紅,童云海,蘇燕青

1(國際關系學院 網絡空間安全學院,北京 100091)

2(北京大學 智能科學系,北京 100871)

頻繁模式挖掘應用廣泛,比如:醫學研究人員希望通過分析醫學普查數據,發現疾病間的關聯,獲取并發癥等病學知識[1]——例如患糖尿病的人通常伴隨著冠心病和高血壓.然而在數據普查時,出于隱私的考慮,許多人在提供個人數據時會感到不安,有時拒絕提供數據或提供假數據.如何在保護好個人數據隱私的同時實施頻繁模式、關聯規則等挖掘任務,是隱私保護數據挖掘(privacy preserving in data mining,簡稱PPDM)[2]要解決的重要問題,其目標是在不精確訪問個體隱私數據的情況下,仍能挖掘到精確的結果.

(1) 相關工作

隨機化回答RR(randomized response)最先由Warner 在1965 年針對二元敏感性問題調查提出[3],稱為沃納模型.文獻[4]提出了分層沃納模型,但分層沃納模型解決的仍是單屬性敏感問題的調查,且敏感屬性是二元變量.文獻[5]使用“風險-效用”映射(risk-utility,簡稱R-U)比較了不同的隨機化策略,提出了用于單一布爾屬性的最優隨機化策略.文獻[6]利用多目標優化方法,針對單一多元分類屬性,力圖尋找接近于最優隨機化的變換概率矩陣.文獻[7]提出了針對多個敏感屬性的隨機化回答技術.文獻[8]通過不相關問題隨機化回答技術估算多個混合類型敏感屬性的依賴關系,其中,混合類型敏感屬性包括你是否抽煙、是否有經濟負擔等二元分類屬性,還包括睡眠質量、手機對學業的影響度等量化數值屬性.Du 等人基于隨機化回答技術實現了布爾類型數據的隱私保護決策樹分類[9].不同文獻的區別包括屬性類型(二元、多元、量化數值)、屬性數量(單屬性、多屬性)、目標(簡單統計、相關性分析、決策樹)、隨機化問題(正/反問題、正/不相關問題)等.

隨機化回答是隱私保護頻繁模式和隱私保護關聯規則挖掘中的主要方法[10-14].文獻[10]提出了基于隨機化回答的隱私保護關聯規則挖掘方法mask(mining associations with secrecy konstraints),mask 隨機化過程只有一個參數p,其基本思想是:對布爾數據中所有的“1”“0”值,以p的概率保持不變,以1-p的概率取反.文獻[11]針對數據中“1”“0”敏感度不同的問題提出了emask 算法,該算法對“1”“0”設置兩個不同的隨機化參數p1和p2,emask 隨機化時,對所有的“1”值,以p1的概率保持不變,以1-p1的概率取反;而對“0”值,則以p2的概率保持不變,以1-p2的概率取反.從而使“1”“0”擁有不同的保護級別.文獻[12]對mask 支持度重構進行了性能優化,提出了mmask 算法.文獻[13,14]針對不同屬性需要不同保護的場景,提出了“非統一”參數的隱私保護關聯規則RE (recursive estimation)算法.文獻[15]提出了屬性分組的隨機化方法,實現隱私保護關聯規則挖掘.近些年流行的差分隱私保護[16-18]通過在數據分析過程或結果中添加隨機噪音,確保在數據庫中插入或刪除任意一條記錄都不會顯著影響數據分析結果,隨機化回答是差分隱私的一種變體[17].

(2) 本文動機

本文動機來自于兩方面:一是文獻[13],二是客觀存在的不同人群隱私保護需求的差異性.

文獻[13]RE 算法認為:“性別”“年齡”和“收入”等不同屬性的敏感度是不同的,應設置不同的隨機化參數,使其擁有不同的隱私保護度.既然不同屬性都需要不同保護,那不同個體是否需要不同保護呢?

AT&T 實驗室1999 年調查了Internet 用戶對隱私保護的態度,結果顯示[1]:17%的用戶對隱私保護極端重視,56%的用戶對隱私保護中度重視,其余27%的用戶對隱私保護不重視.以上事實說明,不同人群對隱私態度和對隱私信息的保護需求是有差異的.然而,已有的隱私保護頻繁模式挖掘方法沒有考慮不同人群的隱私保護需求差異性,在對個體數據隨機化時,運用統一的隨機化參數對所有人實施同等的保護,無法滿足個體對隱私的偏好和具體保護需求,造成的結果是對一部分人的隱私保護程度不足,而對另一部分人實施了過度保護.個性化隱私保護[18-21]應運而生.文獻[18]提出一種個性化的差分隱私保護系統.文獻[19]面向個性化的隱私保護數據發布.文獻[20]提出一種精細化的個性化隱私保護框架.文獻[21]提出一種個性化的隱私保護問題調查統計方法,與本文工作相似,它允許用戶抽取自己的概率對答案進行干擾.然而,文獻[21]的問題和應用場景與本文不同,文獻[21]針對在線問題調查,而非頻繁項集挖掘.

基于以上事實,本文在我們提出的PN/g模型[22]的基礎上,提出一種基于個體分組多參隨機化的隱私保護頻繁模式挖掘方法GR-PPFM(grouping-based randomization for privacy preserving frequent pattern mining).在GR-PPFM 架構中,當人們參與數據調查提交自己的數據時,可以根據各自偏好進行分組,每一組數據設置不同的隱私保護級別,進行差異化的隱私保護.本文是我們在文獻[22]工作的延續.文獻[22]針對PN/g模型,總人數為N,組數為g,每一分組的人數相同,均為N/g.文獻[22]通過簡單的例子,手工計算探索了支持度重構的可行性,但沒有公式推導、算法設計和實驗評價.此外,本文的分組隨機化是文獻[22]PN/g模型的更一般情況,分組內人數可以不同.本文理論上推導了支持度重構遞歸公式,基于遞歸公式設計了完整的分組隨機化隱私保護頻繁項集挖掘算法,并基于大規模合成和真實數據集,針對支持度重構誤差和隱私保護性能,與已有的mask,emask,RE 方法進行了實驗對比和評價,驗證了方法的有效性.

事實上,隱私保護的內涵決定了其首要目標是為個體提供其所要求的保護,而差異化保護正體現了這一內在目標.GR-PPFM 可在兼顧這種差異化保護要求的同時,保證正常挖掘任務的執行.實驗結果表明:相對于已有單參數隨機化mask 方法,GR-PPFM 不僅能滿足不同群體多樣化的隱私保護需求,加強隨機化參數設置的靈活性,還能在整體隱私保護度相同情況下,提高挖掘結果準確性.

1 問題與架構

基于分組隨機化的隱私保護頻繁模式挖掘GR-PPFM 的總體架構如圖1 所示,所解決的問題是:給定原始事務集D={D1,D2,…,Dn}和最小支持度閾值min_sup,如何利用M1,M2,…,Mn共n個隨機化模型,分別對D1,D2,…,Dn隨機化,以及如何對隨機化生成的事務集進行挖掘,得到跟集合F盡可能接近的頻繁項集集 合,其中,F為從D挖掘得到的頻繁項集集合.

Fig.1 Framework of GR-PPFM圖1 GR-PPFM 架構

GR-PPFM 分3 個階段:(1) 數據分組;(2) 分組隨機化;(3) 在支持度重構的基礎上,進行頻繁模式挖掘.

(1) 第1 階段,隱私保護者對參與敏感問題的調查者(即數據提供者),按其對個人數據的保護程度要求進行分組,保護要求相同的進入同一組.可以預先設置若干個保護級別,被調查者可根據個人偏好選擇一個合適的保護級別,一個級別對應一個分組.如圖1 所示,共有n個保護級別供用戶選擇,分組后形成了D1,D2,…,Dn共n組數據.假定隱私保護者已根據先驗知識,設計好若干個不同的隱私保護級別和對應的分組供被調查者選擇,并假設參與調查的個體對其隱私保護取向都比較明確,能夠通過引導選定其想要的保護級別和“找到隊伍”;

(2) 第2 階段,隱私保護者在客戶端運用隨機化模型,對分組后的數據分別進行隨機化,生成隨機化后的數據集.如圖 1 所示,利用M1,M2,…,Mn共n個隨機化模型,對D1,D2,…,Dn隨機化,生成相應的共n個隨機化數據集.具體的隨機化過程和參數設置在第2.1 節給出;

(3) 第3 階段,頻繁模式挖掘者在服務器端,對隨機化后的數據集D′進行挖掘,生成想得到的頻繁模式集.數據集D′由共同組成.為了保證從隨機化后的數據集能挖掘出正確的頻繁模式,以得到 正確的關聯分析結果,一個很重要的部件是結合隨機化模型參數進行項集支持度的重構,第2.2 節討論支持度重構.

上述GR-PPFM 架構中,被調查者本人對持有的數據隨機化,隨后將隨機化數據傳給頻繁模式挖掘服務器.

2 分組隨機化與挖掘方法

2.1 分組隨機化

GR-PPFM 分組隨機化的基本思想是由參與調查的個體自行決定對其數據的隱私保護級別和相應的隨機化參數,隱私保護級別差不多的分為一組,同一組內共用同一個隨機化參數,可表示為如下形式:

其中,原始事務集D由N個事務(個體)的m個項構成二維N×m布爾矩陣(數值屬性可通過離散化變為分類屬性,而分類屬性又可變為布爾屬性,即一般數據都可變為二維布爾矩陣形式).D1,D2,…,Dn為D中的n個數據分組,分組中的個體數占總個體數|D|=N的比例分別為w1,w2,…,wn(0＜wg＜1,g∈{1,...,n}).此n個數據分組分別以p1,p2,…,pn的概率進行隨機化,生成隨機化后的數據分組,共同組成頻繁模式挖掘所用的事務集D′.每個Dg的隨機化都遵循單參數隨機化的基本過程,即:對該分組對應的N×m矩陣中的所有0-1 元素,均以pg的概率取原值,以1-pg的概率取反.單參數隨機化使用隨機化參數p與1-p具有對等效果(隱私保護度和挖掘結果準確性關于p=0.5 對稱,p=0.5 隱私保護能力最強,但誤差無窮大),故以下假定隨機化參數均大于0.5.

表1 給出了個體分組隨機化的例子.表的左邊為原始事務集,由10 個被調查者的4 個問題項(I1/I2/I3/I4)組成,10 個被調查者分為5 組,分別包含3 個、2 個、2 個、2 個、1 個被調查者.同一組內隱私保護需求相同,對應的隨機化參數分別為1,0.9,0.8,0.7,0.6.表的右邊為分組隨機化后的數據集,其中,前3 行為第1 組數據,這3 名被調查者完全不考慮隱私保護,愿意全部貢獻原始數據,隨機化概率參數p1=1;相反,由被調查者10 構成的第5 組數據非常在乎隱私,選擇的隨機化參數p5=0.6,其數據隨機化時以0.6 的概率保持不變,以0.4 的概率取反.得到的最后一條記錄中,有2 個值保持不變、2 個值取反.被調查者4-5,6-7,8-9 的隱私保護需求介于第1 組和第5 組之間,隨機化參數在0.6 到1 之間.

Table 1 Grouping randomization of with GR-PPFM method 表1 GR-PPFM 方法分組隨機化

GR-PPFM 方法采用分組多參隨機化,允許對不同的人群使用不同的隨機化參數,問題和挑戰在于:

(1) GR-PPFM 對不同個體采取不同的隨機化參數后,能像單參數隨機化mask 一樣重構出原始事務集中各項集的支持度嗎?如何重構呢?第2.2 節針該問題給出解決方法;

(2) GR-PPFM 能從個體分組多參隨機化模型中,得到真正的益處嗎?第3 節實驗評價將針對該問題作答.

2.2 支持度重構

2.2.1 基本原理

設I={I1,I2,...,Im}是一組項的集合,D={T1,T2,...,TN}為事務數據庫,其中,事務Tu(u∈{1,2,…,N})為I的子集.項集A?I的長度|A|是指A中項的個數,如果|A|=k,則稱A為k-項集.項集A在D中的支持計數(簡稱支持數)是指D中包含A的事務數,記作support_count(A)或SA,SA=|{Tu|A?Tu,Tu∈D}|.同時,將D中恰等于A的事務數,稱作項集A在D中的凈計數,記作CA,CA=|{Tu|A=Tu,Tu∈D}|.

假定A={I1,I2,…,Ik}為k-項集,根據mask 方法支持度重構原理,只要給出k-項集A的變換概率矩陣Pk=[pij],就可根據文獻[22]中的公式(3):

估算出項集A的重構支持計數.而公式(1)中,為矩陣Pk的逆矩陣中的最后一行元素,為A的第j個子集在D′(I1…Ik)中的凈計數(即D′(I1…Ik)中恰等于第j個子集的事務數).因此,只要求出變換概率矩陣Pk,就可求得任意項集的重構支持計數和支持度了.因為求得Pk就可得到,進而得到aij.

2.2.2 變換概率矩陣

根據文獻[22]表1,易推出單參數隨機化4-項集的變換概率矩陣,見表2.

Table 2 Transition probability matrix P4 of mask 表2 mask 變換概率矩陣P4

對于表1 的分組多參隨機化,如何求得變換概率矩陣P呢?文獻[22]的公式(5)給出了PN/g模型pij的計算公式.PN/g模型每個分組記錄數相同,而本文表1 每個分組記錄數不同,但仔細分析發現,文獻[22]的公式(5)同樣適用于分組記錄數不同的隨機化.不過,文獻[22]的公式(5)各組權重角標所用的組號i,容易 與pij中的角標i混淆,本文使用wg和pg,分別表示第g個分組所占的比例權重和對應的隨機化參數,得到GR-PPFM 方法中k-項集A對應的2k×2k變換概率矩陣Pk中的元素值:

例如表1 中的分組隨機化,事務“0000”轉變“0000”的概率為

而“0001”(對應事務{I4})轉變為“1110”(對應事務{I1I2I3})的概率為

這樣便可得到4-項集{I1I2I3I4}對應的16×16 變換概率矩陣P4中的所有元素,見表3.

Table 3 Transition probability matrix P4 of GR-PPFM 表3 GR-PPFM 變換概率矩陣P4

在得到矩陣Pk后,就可根據,求得k-項集A的支持計數了,其支持計數恰等于向量中的最后一個元素.

文獻[22]第3.3 節、第3.4 節給出了手工進行支持度重構的完整例子.

2.2.3 支持計數重構遞歸公式

有兩種方法可加快求解整個項集空間的2m個項集支持度的計算過程:第1 種方法是根據求取2m個項集在D中的凈計數,然后由項集的支持計數與凈計數的關系求得此2m個項集的支持計數;第2 種方法是導出項集支持計數重構遞歸公式,見后文公式(4),根據該遞歸公式只需2m次求解,便可求取整個項集空間的2m個項集的支持度.下面給出公式(4)的推導過程:

2.3 GR-PPFM挖掘方法

GR-PPFM 利用支持數重構遞歸公式(4),在頻繁項集生成算法Apriori 基礎上形成,支持數重構遞歸公式是算法的核心,Apriori 構成了方法的主框架.

算法.分組隨機化隱私保護頻繁項集生成方法GR-PPFM.

輸入:分組多參隨機化數據D′;分組比例和隨機化參數(pg,wg)(g=1,…,n);最小支持度閾值min_sup;

輸出:從D′重構出的頻繁項集集合.

3 實驗評價

3.1 實驗數據

分別用人工合成購物籃數據集、真實購物籃數據集進行實驗評價.

人工合成購物籃數據集.人工合成購物籃數據集D由IBM Almaden 生成器生成,生成器參數為T=3,I=4,|D|=100K,N=10,即事務平均長度為3,頻繁項集的平均長度為4,總事務數為100K,總項數為10.直接生成的數據集為項集形式,可將其轉化為0,1 布爾表示的數據集;

真實購物籃數據.真實購物籃數據集D為某食品超市的購物數據basket.txt,事務平均長度為3,總事務數940,總項數為 11,包括fruitveg,freshmeat,dairy,cannedveg,cannedmeat,frozenmeal,beer,wine,softdrink,fish,confectionery.該數據可從以下網址獲取:https://download.csdn.net/download/lol000/8693253(2020 年2 月).

3.2 實驗方法

? 第1 步,挖掘原始數據集D.

針對多個不同的最小支持度閾值,分別運用Apriori 算法對數據集D進行挖掘,記錄每次挖掘得到的所有頻繁項集和其支持數.

? 第2 步,生成分組多參數隨機化數據集.

對數據集D進行分組多參數隨機化干擾,生成干擾后的數據集D′.具體地講,對數據集D按行分為Group1～ Group5 共5 組數據,這5 組數據所占的比例分別為w1=30%,w2=20%,w3=20%,w4=20%,w5=10%,對應的隨機化參數分別為p1=1,p2=0.9,p3=0.8,p4=0.7,p5=0.6.即:第1 組數據保持不變;第2 組數據以0.9 的概率保持原來的值,以0.1 的概率取反;第3 組～第5 組數據分別以0.8,0.7,0.6 的概率保持原值,以0.2,0.3,0.4 的概率取反.直觀地,數據集D對應的分組多參隨機化模型參數設置見表4.

以上5 組數據所占比例,大致依據本文開始提到的AT&T 實驗室1999 年隱私態度調查報告中不同用戶的比例和進一步細分.隱私保護級別設置大致遵從國家保密局2007 年6 月22 日頒布的《信息安全等級保護管理辦法》中的五級分類.表4 中:1 級表示信息密級為公開,不需保護;2 級表示信息密級為限制,需弱保護;3 級表示信息密級為秘密,需保護;4 級表示信息密級為機密,需強保護;5 級表示信息密級為絕密,需特別強的保護.5 級分類不僅考慮了信息保護需求的差異性,同時級數設置較少易于管理,實際中也可根據需要進一步分級細化.

? 第3 步,生成單參數隨機化數據集.

為便于同單參數mask 方法對比,對數據集D進行單參數隨機化干擾,生成mask 方法所用的單參數隨機數 據集,隨機化概率p設置為多參數隨機化的平均概率,即:

? 第4 步,挖掘隨機化數據.

針對多個不同的最小支持度閾值,分別運用Apriori 算法以及帶有支持數重構的GR-PPFM 方法,對第3 步生成的多參數隨機化數據集D′進行挖掘,記錄每次挖掘得到的所有頻繁項集和其支持數.同時,運用Apriori 算 法和mask 方法,對第4 步生成的單參數隨機化數據集挖掘,記錄挖掘得到的頻繁項集和對應的支持數.

? 第5 步,計算分析誤差.

對比第4 步的挖掘結果,計算分析mask 方法、GR-PPFM 方法的挖掘結果誤差,包括項集支持度相對誤差ρ、項集身份誤差θ-和θ+.其中,ρ反映頻繁項集在隨機化數據中重構后的支持度與其在原數據中的實際支持度間的相對誤差;θ-表示頻繁項集丟失率,衡量原先頻繁而被錯誤識別為不頻繁的項集占原頻繁項集總數的比例;θ+表示頻繁項集增加率,衡量原先不頻繁而被錯誤識別為頻繁的項集占原頻繁項集總數的比例.具體公式見文獻[1].

Table 4 Randomization parameter settings of dataset D表4 數據集D 的隨機化模型參數設置

3.3 結果分析

本節對實驗結果分析,考察不同方法挖掘結果的誤差隨項集長度k、最小支持度閾值min_sup 的變化情況,并對不同方法的誤差進行對比.其中,圖2 為合成數據上的實驗結果,圖3 為真實數據上的實驗結果.

3.3.1 誤差與項集長度的關系

3.3.1.1 支持度誤差

圖2(a)給出了針對合成數據,當最小支持度閾值min_sup=0.1%時,mask 和本文GR-PPFM 方法的平均支持度相對誤差ρ隨頻繁項集長度k的變化曲線.圖3(a)給出了針對真實數據,當min_sup=1%時,ρ隨k的變化曲線.

(1) 橫向比較:很明顯,本文提出的多參數隨機化GR-PPFM 的誤差小于單參數隨機化mask 方法.說明了在 整體隱私保護度相同的情況下(實驗中,mask 的隨機化參數p等于多參數隨機化的平均概率),GR-PPFM 挖掘結果好于mask;

(2) 誤差隨頻繁項集長度k的變化:

a.理論上,從k-項集的支持度重構遞歸公式(4)分析,k-項集的重構支持度依賴于該k-項集的所有子集的重構支持度,作為一個遞歸的過程,的支持度依賴于,依此類推.這種遞歸依賴關系將導致誤差的級聯傳導,使誤差從1-項集逐漸向上層傳遞和累積,因此直觀上,k越大,理論偏差也越大;

b.觀察圖2(a)發現,平均支持度相對誤差隨k大體呈現先上升、后下降的趨勢.在頻繁5-項集處,平均支持度誤差最大,5-項集之前誤差隨k的增加而增大,5-項集之后誤差大致平緩下降.為什么圖中的誤差在頻繁5-項集后會出現回落呢?回到ρ的計算公式,不難發現,ρ計算的是頻繁項集的平均支持度相對誤差,這意味著ρ與最小支持閾值min_sup 緊密相關.因為min_sup 不同,其劃定的某個長度的頻繁項集集合F也就不同,造成該集合的平均支持度誤差ρ也會不同.這表明,F對應的ρ值會因特定數據的偏斜和最小支持度閾值min_sup 的不同而出現偶然變大變小的情況.因為F中即使出現1 個誤差特別大或特別小的項集,就能顯著改變F的平均支持度誤差ρ值,尤其當F中的項集個數較少時.

圖2(a)中,在min_sup=0.1%時,原始數據對應的頻繁1-項集集合、2-項集集合、…、8-項集集合的項集個數依次為10,44,112,160,125,40,8,1.其中,頻繁4 項集的個數最多(這是IBM Almaden 生成器生成的數據集特征決定的,因為選取的參數指定了生成數據集的頻繁項集的平均長度為4),而頻繁6-項集、7-項集和8-項集集合的個數較少,尤其是頻繁8-項集集合,只有1 個項集,因此其平均支持度誤差的偶然性就較大,這也是圖中5-項集以后誤差回落的原因.當F中的項集個數較多時,偶然性因素會被淹沒,誤差大小會順從一般的規律隨項集長度的增加而增大.事實上,實驗中發現:當設置min_sup=0.001%時,即只要出現1 次的項集就為頻繁項集(因為實驗所用的數據集D的大小為100 000)時,所測得的ρ正是按項集長度的遞增而遞增的.因為此時每一級長度對應的頻繁項集個數都較多,平均誤差隨項集長度的變化能呈現理論分析的規律.

Fig.2 Experiment error of mask,and GR-PPFM on synthetic data圖2 mask、GR-PPFM 在人工合成數據中的實驗誤差

Fig.3 Experiment error of mask and GR-PPFM on real-world data圖3 mask 與GR-PPFM 在真實數據中的實驗誤差

圖3(a)測得的ρ正是按項集長度的遞增而遞增的,同理論分析一致.

3.3.1.2 項集身份誤差

圖2(b)、圖3(b)和圖2(c)、圖3(c)給出了項集身份誤差隨頻繁項集長度k的變化情況,可以看出:(1) 分組隨機化GR-PPFM 方法誤差小于單參數隨機化mask 方法;(2) 項集身份誤差隨k的變化跟圖2(a)、圖3(a)中支持度誤差ρ隨k的變化情況相近,誤差大致隨k增大而增大.

θ-,θ+隨k變化規律與ρ隨k變化規律的相似性是容易理解的,因為追根溯源,項集支持度大小決定了項集作為頻繁項集還是非頻繁項集的身份,項集支持度誤差從最深層次反映了隨機化過程對于數據的影響,項集身份誤差是項集支持度誤差的外在表現.

3.3.2 誤差與支持度閾值的關系

3.3.2.1 支持度誤差

圖2(d)給出了合成數據所有頻繁項集(從頻繁1-項集到頻繁8-項集,k=ALL)的平均支持度相對誤差ρ隨最小支持度閾值min_sup 的變化曲線.圖3(d)給出了真實數據上ρ隨min_sup 的變化曲線.

(1) 橫向比較:橫向比較圖2(d)、圖3(d)可發現:誤差大小關系跟圖2(a)、圖3(a)一致,仍是GR-PPFM＜mask.說明在整體隱私保護度相同時,多參數隨機化方法GR-PPFM 的挖掘結果優于單參數mask 方法;

(2) 誤差隨支持度閾值min_sup 的變化:觀察曲線隨min_sup 的變化可發現,平均支持度誤差隨支持度閾值的增大而減小.說明隨著支持度閾值的增大,挖掘結果越好.原因是什么呢?由于支持度相對誤差等于絕對誤差與原始支持度值的比值,假定項集I1和I2的絕對誤差相等,則項集I1和I2的相對誤差完全取決于其原支持度值:原支持度值越大,其相對誤差越小;原支持度值越小,其相對誤差越大.當支持度閾值增大時,其對應的頻繁項集集合F中各項集的支持度相對越大,造成F中各項集的平均支持度相對誤差越小,誤差隨min_sup 的變化呈現圖2(d)、圖3(d)中的趨勢.

3.3.2.2 項集身份誤差

圖2(e)、圖3(e)和圖2(f)、圖3(f)給出了項集身份誤差隨支持度閾值min_sup 的變化情況.可看出,項集身份誤差隨min_sup 的變化跟圖2(d)、圖3(d)支持度誤差ρ隨min_sup 的變化情況大體相近,其基本規律:(1) 大多數情況下,分組隨機化GR-PPFM 方法的誤差小于單參數隨機化mask 方法;(2) 誤差隨min_sup 增大而減小.θ-,θ+隨min_sup 變化規律與ρ隨min_sup 變化規律相似.

3.3.3 支持度重構與不重構誤差對比

通常,數據隨機化后,由于數據被擾亂,項集的支持度將發生變化,若直接從隨機化后的數據挖掘,不進行支持度重構,項集的支持度跟原始支持度比究竟會發生多大的變化呢?圖4(a)～圖4(d)分別給出了實驗中針對合成數據和真實數據、單參數隨機化mask(隨機化概率p=0.84)支持度重構與不重構的誤差對比及分組隨機化GR-PPFM 支持度重構與不重構誤差對比.圖4 中,合成數據、真實數據設置的最小支持度閾值分別為0.1%,1%.

Fig.4 Error of support reconstruction vs.non-reconstruction圖4 支持度重構與不重構誤差對比

圖4(a)、圖4(c)針對IBM Almaden 生成器生成的數據,可發現支持度不重構的誤差遠遠大于重構誤差.說明數據經隨機化后,項集的支持度已發生顯著變化,直接從隨機化后的數據得到的挖掘結果已遠遠偏離從原始數據挖掘得到的結果,必須通過支持度重構恢復原數據庫中各項集的支持度,以得到跟原數據盡可能相近的挖掘結果.

圖4(b)、圖4(d)針對真實購物籃數據,可發現當頻繁項集長度不大時,不重構的誤差遠遠大于重構誤差;但當頻繁項集長度較大時(單參數隨機化后k=4,5,分組隨機化k=5),不重構的誤差反而小于重構的誤差.說明對于高階項集重構的誤差大,這跟之前分析的誤差隨k增大而增大的規律一致.綜合圖4,針對分組隨機化,對于低階項集(k＜5)使用重構支持度,對于高階項集(k≥5)使用不重構支持度.

3.3.4 隱私保護對比

下面分析兩種方法的隱私保護性能,從隱私保護度(定量)、個體隱私保護差異性和暴露的信息(定性)等方面進行對比.本文隱私保護性能考慮的場景是敏感問題調查或購物時,對于敏感問題回答為“是”和“購買”敏感物品的保護,不考慮對于敏感問題回答為“否”和“不購買”敏感物品的保護.并假定被調查者運用隨機化裝置給出了真實的回答,購物數據提供者對數據進行了相應的隨機化變換.

3.3.4.1 隱私保護度

文獻[10]將單參數隨機化mask 的隱私保護度privacy定義為1-R(p),其中,R(p)=aR1(p)+(1-a)R0(p).其中,R1(p)表示原始數據庫中的“1”能從隨機化后的數據庫中被還原的概率,R0(p)表示原始數據庫中的“0”能從隨機化后的數據庫中被還原的概率,a為隱私保護權重.本文隱私保護場景只考慮敏感問題回答為“是”和“購買”敏感物品記錄的保護,即對如表1 所示的0-1 購物籃數據,只考慮“1”值的保護.設保護權重系數a=1,則隱私保護度公式為

假定隨機化概率為p,項的平均支持度為s0,R1(p)的計算公式為

根據公式(5)、公式(6)的分析,隱私保護度1-R1(p)跟p(p＞0.5)和s0均成反比.說明隨機化概率越大,項的平均支持度越高,隱私保護度越低;反之亦然.極端地,當p=1 時,數據完全保持不變,R1(p)=1,隱私保護度最低,為0.

? 當s0=1 時,數據是全1 數據,R1(p)=1,隱私保護度也是最低,為0.此時,無論p取多少,“1”均能從隨機化后的數據中被還原,隨機化均無法保護數據;

? 當s0=0 時,數據是全0 數據,R1(p)=0,隱私保護度最高,為1.

對于分組隨機化,由于不同分組隨機化概率p不同,所以不同分組的隱私保護度也不同.假定wg為第g個分組個體數占總個體數的比例,pg為第g個分組對應的隨機化概率,R1(pg)為第g個分組中的“1”能從隨機化后的數據庫中被還原的概率,privacy(g)=1-R1(pg)為第g個分組對應的隱私保護度.對于分組隨機化,在已知每個分組對應的隨機化概率的條件下,定義如下4 個隱私保護度:最低隱私保護度、最高隱私保護度、平均隱私保護度、整體隱私保護度.

定義1(最低隱私保護度minPrivacy).分組隨機化中,隱私保護度最小的分組對應的隱私保護度.公式為

定義2(最高隱私保護度maxPrivacy).分組隨機化中,隱私保護度最大的分組對應的隱私保護度.公式為

定義3(平均隱私保護度avgPrivacy).分組隨機化中,多個分組隱私保護度的平均值稱為平均隱私保護度.計算公式為

定義4(整體隱私保護度overallPrivacy).將分組隨機化的平均概率代入公式(5),求得的隱私保護度稱為 整體隱私保護度.計算公式為

實驗中,IBM Almaden 生成器生成的合成數據中,項的平均支持度s0=40.69%;真實數據中,項的平均支持度s0=27.08%.項的平均支持度s0取決于原數據,事實上,由于原數據是無法知道的,真實的s0無從得知,實際中,可通過先驗知識或抽樣估計s0值,也可通過重構得到的項的平均支持度代替s0值.將s0和p1=1,p2=0.9,p3=0.8,p4=0.7,p5=0.6,=0.84 代入公式(5)～公式(10),可分別求得合成數據和真實數據分組隨機化時,在已知每個分組對應的 隨機化概率的條件下,GR-PPFM 對應的最低隱私保護度、最高隱私保護度、平均隱私保護度和整體隱私保護度,結果見表5.

Table 5 Privacy of GR-PPFM vs.mask表5 GR-PPFM 與mask 方法隱私保護性能對比

單參數隨機化mask 僅對應一個隱私保護度,實驗中,單參數mask 方法的隨機化概率p=0.84,分組多參隨機 化的平均概率=0.84,兩者相等.因此,單參數隨機化的隱私保護度與分組隨機化的整體隱私保護度相同,合成 數據是32.4%,真實數據是43.4%.

3.3.4.2 隱私保護差異性

除定量考察隱私保護度外,還可定性分析兩種方法對個體隱私保護的差異性及為支持度重構需暴露的信息的差異.GR-PPFM 對個體實施有差異的保護,而mask 實施無差異的保護.

從個體對應的隨機化概率是否暴露給挖掘者來分析.在分組隨機化GR-PPFM 方法中,為了進行支持度重構,挖掘者只需要知道個體大致使用了哪些隨機化參數以及相應的個體比例,而不需要知道具體的個體與使用的隨機化參數的確切對應關系.但mask 支持度重構需要知道p,由于所有的個體都使用了同樣的p,所以挖掘者確切知道每個個體與隨機化參數的對應關系,即任意指定一個個體,挖掘者都能確切知道該個體使用了什么樣的參數進行了隨機化變換.

兩種方法的隱私保護度、隱私保護差異性和為支持度重構需要暴露的信息見表5,其中,D′表示D隨機化后 的全部數據,表示D中以pg的概率隨機化后的第g組數據,其占全部數據的比例為wg.實驗中,p1=1,p2=0.9,p3=0.8,p4=0.7,p5=0.6;w1=0.3,w2=0.2,w3=0.2,w4=0.2,w5=0.1.

3.4 拓展實驗

為進一步探究本文工作GR-PPFM 與其他相關工作的效能差異,本節設計實驗對GR-PPFM,emask 和RE 這3 種算法進行對比.GR-PPFM 按行分組隨機化,emask 對0,1 分別隨機化,RE 按列分組隨機化,實驗數據采用第3.1 節提到的真實購物籃數據,GR-PPFM 采用第3.2 節實驗方法第2 步使用的分組比例和相應的隨機化參數設 置,平均隨機化概率=0.84.Emask 設置兩個隨機化參數:p1=0.6,p0=0.9,即:對所有的“1”值,以0.6 的概率保持不 變,以0.4 的概率取反;而對“0”值,則以0.93 的概率保持不變,以0.07 的概率取反.由于“1”和“0”在數據中的占比 分別為72.9%和27.1%,平均隨機化概率=0.6×72.9%+0.93×27.1%=0.84.RE 將購物籃數據中的11 種商品分為 3 組:(1) fruitveg,freshmeat,dairy;(2) cannedveg,cannedmeat,frozenmeal,beer,wine;(3) softdrink,fish,confectionery.第(1)組～第(3)組隨機化參數分別設為0.68,0.84,1,平均隨機化概率=(3×0.68+5×0.84+3×1)/11=0.84.3 種方法的 平均隨機化概率均為0.84,保證三者的整體隱私保護度相同.圖5 給出了GR-PPFM,emask 和RE 這3 種方法在整體隱私保護度相同的情況下挖掘結果的差異.

Fig.5 Support error of GR-PPFM/emask/RE on real-world basket data圖5 GR-PPFM/emask/RE 在真實購物數據中的支持度誤差

圖5(a)為支持度閾值1%時,支持度相對誤差隨挖掘出的頻繁項集長度變化的比較;圖5(b)為支持度誤差隨最小支持度閾值變化的比較.可以看出:在整體隱私保護度相同情況下,本文提出的個體分組隨機化GR-PPFM的誤差均小于相關工作提到的0,1 差異隨機化emask 方法及屬性分組隨機化RE 方法.

4 總結與展望

已有以mask 為代表的隱私保護頻繁模式挖掘方法,在對數據隨機化時,采用統一的隨機化參數,對所有個體實施同等、無差異的保護.考慮到不同人群對隱私保護需求的差異性,本文提出一種基于分組隨機化的隱私保護頻繁模式挖掘GR-PPFM 方法.針對GR-PPFM,探索了支持度重構方法以及與之相適應的頻繁模式挖掘算法,實現了粗粒度的個性化隱私保護頻繁模式挖掘.實驗結果表明:

(1) 在整體隱私保護度相同情況下,分組隨機化GR-PPFM 挖掘結果準確性高于整體單參數隨機化mask;

(2) 分組隨機化對不同人群實行有差異的保護,個體隱私保護度更強,為支持度重構暴露的信息更少;

(3) 支持度重構誤差隨項集長度的增大而增大、隨支持度閾值的增大而減小,支持度重構誤差遠遠小于直接挖掘不重構的誤差.

本文的貢獻在于,基于不同人群隱私保護需求不同的事實,提出了分組多參數隨機化的數據保護方式;給出了分組隨機化的支持度重構方法以及與之相適應的頻繁模式挖掘算法,實現了粗粒度的個性化隱私保護頻繁模式挖掘;實驗分析比較了分組多參數隨機化和單參數隨機化兩種方法的效果.

GR-PPFM 方法可廣泛應用于社會、經濟生活中涉及隱私的敏感性問題的調查和關聯分析任務.未來工作包括:(1) 探索誤差隨分組參數w、隨機化概率參數p和數據集大小參數|D|的變化情況;(2) 本文只通過實驗證實了分組隨機化GR-PPFM 方法的可行性及相對于單參數隨機化mask 方法的優越性,能否從理論上導出兩種方法k-項集的支持度重構偏差公式,并證明GR-PPFM 方法的優越性值得探究;(3) 能否將分組隨機化模型應用到其他類型的個性化隱私保護挖掘算法,如分類、聚類[23],并構造與之適應的特征重構方法,也是十分值得期待的研究工作.