郭宇紅,童云海,蘇燕青

1(國(guó)際關(guān)系學(xué)院 網(wǎng)絡(luò)空間安全學(xué)院,北京 100091)

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

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

(1) 相關(guān)工作

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

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

(2) 本文動(dòng)機(jī)

本文動(dòng)機(jī)來(lái)自于兩方面:一是文獻(xiàn)[13],二是客觀存在的不同人群隱私保護(hù)需求的差異性.

文獻(xiàn)[13]RE 算法認(rèn)為:“性別”“年齡”和“收入”等不同屬性的敏感度是不同的,應(yīng)設(shè)置不同的隨機(jī)化參數(shù),使其擁有不同的隱私保護(hù)度.既然不同屬性都需要不同保護(hù),那不同個(gè)體是否需要不同保護(hù)呢?

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

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

事實(shí)上,隱私保護(hù)的內(nèi)涵決定了其首要目標(biāo)是為個(gè)體提供其所要求的保護(hù),而差異化保護(hù)正體現(xiàn)了這一內(nèi)在目標(biāo).GR-PPFM 可在兼顧這種差異化保護(hù)要求的同時(shí),保證正常挖掘任務(wù)的執(zhí)行.實(shí)驗(yàn)結(jié)果表明:相對(duì)于已有單參數(shù)隨機(jī)化mask 方法,GR-PPFM 不僅能滿(mǎn)足不同群體多樣化的隱私保護(hù)需求,加強(qiáng)隨機(jī)化參數(shù)設(shè)置的靈活性,還能在整體隱私保護(hù)度相同情況下,提高挖掘結(jié)果準(zhǔn)確性.

1 問(wèn)題與架構(gòu)

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

Fig.1 Framework of GR-PPFM圖1 GR-PPFM 架構(gòu)

GR-PPFM 分3 個(gè)階段:(1) 數(shù)據(jù)分組;(2) 分組隨機(jī)化;(3) 在支持度重構(gòu)的基礎(chǔ)上,進(jìn)行頻繁模式挖掘.

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

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

(3) 第3 階段,頻繁模式挖掘者在服務(wù)器端,對(duì)隨機(jī)化后的數(shù)據(jù)集D′進(jìn)行挖掘,生成想得到的頻繁模式集.數(shù)據(jù)集D′由共同組成.為了保證從隨機(jī)化后的數(shù)據(jù)集能挖掘出正確的頻繁模式,以得到 正確的關(guān)聯(lián)分析結(jié)果,一個(gè)很重要的部件是結(jié)合隨機(jī)化模型參數(shù)進(jìn)行項(xiàng)集支持度的重構(gòu),第2.2 節(jié)討論支持度重構(gòu).

上述GR-PPFM 架構(gòu)中,被調(diào)查者本人對(duì)持有的數(shù)據(jù)隨機(jī)化,隨后將隨機(jī)化數(shù)據(jù)傳給頻繁模式挖掘服務(wù)器.

2 分組隨機(jī)化與挖掘方法

2.1 分組隨機(jī)化

GR-PPFM 分組隨機(jī)化的基本思想是由參與調(diào)查的個(gè)體自行決定對(duì)其數(shù)據(jù)的隱私保護(hù)級(jí)別和相應(yīng)的隨機(jī)化參數(shù),隱私保護(hù)級(jí)別差不多的分為一組,同一組內(nèi)共用同一個(gè)隨機(jī)化參數(shù),可表示為如下形式:

其中,原始事務(wù)集D由N個(gè)事務(wù)(個(gè)體)的m個(gè)項(xiàng)構(gòu)成二維N×m布爾矩陣(數(shù)值屬性可通過(guò)離散化變?yōu)榉诸?lèi)屬性,而分類(lèi)屬性又可變?yōu)椴紶枌傩?即一般數(shù)據(jù)都可變?yōu)槎S布爾矩陣形式).D1,D2,…,Dn為D中的n個(gè)數(shù)據(jù)分組,分組中的個(gè)體數(shù)占總個(gè)體數(shù)|D|=N的比例分別為w1,w2,…,wn(0＜wg＜1,g∈{1,...,n}).此n個(gè)數(shù)據(jù)分組分別以p1,p2,…,pn的概率進(jìn)行隨機(jī)化,生成隨機(jī)化后的數(shù)據(jù)分組,共同組成頻繁模式挖掘所用的事務(wù)集D′.每個(gè)Dg的隨機(jī)化都遵循單參數(shù)隨機(jī)化的基本過(guò)程,即:對(duì)該分組對(duì)應(yīng)的N×m矩陣中的所有0-1 元素,均以pg的概率取原值,以1-pg的概率取反.單參數(shù)隨機(jī)化使用隨機(jī)化參數(shù)p與1-p具有對(duì)等效果(隱私保護(hù)度和挖掘結(jié)果準(zhǔn)確性關(guān)于p=0.5 對(duì)稱(chēng),p=0.5 隱私保護(hù)能力最強(qiáng),但誤差無(wú)窮大),故以下假定隨機(jī)化參數(shù)均大于0.5.

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

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

GR-PPFM 方法采用分組多參隨機(jī)化,允許對(duì)不同的人群使用不同的隨機(jī)化參數(shù),問(wèn)題和挑戰(zhàn)在于:

(1) GR-PPFM 對(duì)不同個(gè)體采取不同的隨機(jī)化參數(shù)后,能像單參數(shù)隨機(jī)化mask 一樣重構(gòu)出原始事務(wù)集中各項(xiàng)集的支持度嗎?如何重構(gòu)呢?第2.2 節(jié)針該問(wèn)題給出解決方法;

(2) GR-PPFM 能從個(gè)體分組多參隨機(jī)化模型中,得到真正的益處嗎?第3 節(jié)實(shí)驗(yàn)評(píng)價(jià)將針對(duì)該問(wèn)題作答.

2.2 支持度重構(gòu)

2.2.1 基本原理

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

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

估算出項(xiàng)集A的重構(gòu)支持計(jì)數(shù).而公式(1)中,為矩陣Pk的逆矩陣中的最后一行元素,為A的第j個(gè)子集在D′(I1…Ik)中的凈計(jì)數(shù)(即D′(I1…Ik)中恰等于第j個(gè)子集的事務(wù)數(shù)).因此,只要求出變換概率矩陣Pk,就可求得任意項(xiàng)集的重構(gòu)支持計(jì)數(shù)和支持度了.因?yàn)榍蟮肞k就可得到,進(jìn)而得到aij.

2.2.2 變換概率矩陣

根據(jù)文獻(xiàn)[22]表1,易推出單參數(shù)隨機(jī)化4-項(xiàng)集的變換概率矩陣,見(jiàn)表2.

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

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

例如表1 中的分組隨機(jī)化,事務(wù)“0000”轉(zhuǎn)變“0000”的概率為

而“0001”(對(duì)應(yīng)事務(wù){(diào)I4})轉(zhuǎn)變?yōu)椤?110”(對(duì)應(yīng)事務(wù){(diào)I1I2I3})的概率為

這樣便可得到4-項(xiàng)集{I1I2I3I4}對(duì)應(yīng)的16×16 變換概率矩陣P4中的所有元素,見(jiàn)表3.

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

在得到矩陣Pk后,就可根據(jù),求得k-項(xiàng)集A的支持計(jì)數(shù)了,其支持計(jì)數(shù)恰等于向量中的最后一個(gè)元素.

文獻(xiàn)[22]第3.3 節(jié)、第3.4 節(jié)給出了手工進(jìn)行支持度重構(gòu)的完整例子.

2.2.3 支持計(jì)數(shù)重構(gòu)遞歸公式

有兩種方法可加快求解整個(gè)項(xiàng)集空間的2m個(gè)項(xiàng)集支持度的計(jì)算過(guò)程:第1 種方法是根據(jù)求取2m個(gè)項(xiàng)集在D中的凈計(jì)數(shù),然后由項(xiàng)集的支持計(jì)數(shù)與凈計(jì)數(shù)的關(guān)系求得此2m個(gè)項(xiàng)集的支持計(jì)數(shù);第2 種方法是導(dǎo)出項(xiàng)集支持計(jì)數(shù)重構(gòu)遞歸公式,見(jiàn)后文公式(4),根據(jù)該遞歸公式只需2m次求解,便可求取整個(gè)項(xiàng)集空間的2m個(gè)項(xiàng)集的支持度.下面給出公式(4)的推導(dǎo)過(guò)程:

2.3 GR-PPFM挖掘方法

GR-PPFM 利用支持?jǐn)?shù)重構(gòu)遞歸公式(4),在頻繁項(xiàng)集生成算法Apriori 基礎(chǔ)上形成,支持?jǐn)?shù)重構(gòu)遞歸公式是算法的核心,Apriori 構(gòu)成了方法的主框架.

算法.分組隨機(jī)化隱私保護(hù)頻繁項(xiàng)集生成方法GR-PPFM.

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

輸出:從D′重構(gòu)出的頻繁項(xiàng)集集合.

3 實(shí)驗(yàn)評(píng)價(jià)

3.1 實(shí)驗(yàn)數(shù)據(jù)

分別用人工合成購(gòu)物籃數(shù)據(jù)集、真實(shí)購(gòu)物籃數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)評(píng)價(jià).

人工合成購(gòu)物籃數(shù)據(jù)集.人工合成購(gòu)物籃數(shù)據(jù)集D由IBM Almaden 生成器生成,生成器參數(shù)為T(mén)=3,I=4,|D|=100K,N=10,即事務(wù)平均長(zhǎng)度為3,頻繁項(xiàng)集的平均長(zhǎng)度為4,總事務(wù)數(shù)為100K,總項(xiàng)數(shù)為10.直接生成的數(shù)據(jù)集為項(xiàng)集形式,可將其轉(zhuǎn)化為0,1 布爾表示的數(shù)據(jù)集;

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

3.2 實(shí)驗(yàn)方法

? 第1 步,挖掘原始數(shù)據(jù)集D.

針對(duì)多個(gè)不同的最小支持度閾值,分別運(yùn)用Apriori 算法對(duì)數(shù)據(jù)集D進(jìn)行挖掘,記錄每次挖掘得到的所有頻繁項(xiàng)集和其支持?jǐn)?shù).

? 第2 步,生成分組多參數(shù)隨機(jī)化數(shù)據(jù)集.

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

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

? 第3 步,生成單參數(shù)隨機(jī)化數(shù)據(jù)集.

為便于同單參數(shù)mask 方法對(duì)比,對(duì)數(shù)據(jù)集D進(jìn)行單參數(shù)隨機(jī)化干擾,生成mask 方法所用的單參數(shù)隨機(jī)數(shù) 據(jù)集,隨機(jī)化概率p設(shè)置為多參數(shù)隨機(jī)化的平均概率,即:

? 第4 步,挖掘隨機(jī)化數(shù)據(jù).

針對(duì)多個(gè)不同的最小支持度閾值,分別運(yùn)用Apriori 算法以及帶有支持?jǐn)?shù)重構(gòu)的GR-PPFM 方法,對(duì)第3 步生成的多參數(shù)隨機(jī)化數(shù)據(jù)集D′進(jìn)行挖掘,記錄每次挖掘得到的所有頻繁項(xiàng)集和其支持?jǐn)?shù).同時(shí),運(yùn)用Apriori 算 法和mask 方法,對(duì)第4 步生成的單參數(shù)隨機(jī)化數(shù)據(jù)集挖掘,記錄挖掘得到的頻繁項(xiàng)集和對(duì)應(yīng)的支持?jǐn)?shù).

? 第5 步,計(jì)算分析誤差.

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

Table 4 Randomization parameter settings of dataset D表4 數(shù)據(jù)集D 的隨機(jī)化模型參數(shù)設(shè)置

3.3 結(jié)果分析

本節(jié)對(duì)實(shí)驗(yàn)結(jié)果分析,考察不同方法挖掘結(jié)果的誤差隨項(xiàng)集長(zhǎng)度k、最小支持度閾值min_sup 的變化情況,并對(duì)不同方法的誤差進(jìn)行對(duì)比.其中,圖2 為合成數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果,圖3 為真實(shí)數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果.

3.3.1 誤差與項(xiàng)集長(zhǎng)度的關(guān)系

3.3.1.1 支持度誤差

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

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

(2) 誤差隨頻繁項(xiàng)集長(zhǎng)度k的變化:

a.理論上,從k-項(xiàng)集的支持度重構(gòu)遞歸公式(4)分析,k-項(xiàng)集的重構(gòu)支持度依賴(lài)于該k-項(xiàng)集的所有子集的重構(gòu)支持度,作為一個(gè)遞歸的過(guò)程,的支持度依賴(lài)于,依此類(lèi)推.這種遞歸依賴(lài)關(guān)系將導(dǎo)致誤差的級(jí)聯(lián)傳導(dǎo),使誤差從1-項(xiàng)集逐漸向上層傳遞和累積,因此直觀上,k越大,理論偏差也越大;

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

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

Fig.2 Experiment error of mask,and GR-PPFM on synthetic data圖2 mask、GR-PPFM 在人工合成數(shù)據(jù)中的實(shí)驗(yàn)誤差

Fig.3 Experiment error of mask and GR-PPFM on real-world data圖3 mask 與GR-PPFM 在真實(shí)數(shù)據(jù)中的實(shí)驗(yàn)誤差

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

3.3.1.2 項(xiàng)集身份誤差

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

θ-,θ+隨k變化規(guī)律與ρ隨k變化規(guī)律的相似性是容易理解的,因?yàn)樽犯菰?項(xiàng)集支持度大小決定了項(xiàng)集作為頻繁項(xiàng)集還是非頻繁項(xiàng)集的身份,項(xiàng)集支持度誤差從最深層次反映了隨機(jī)化過(guò)程對(duì)于數(shù)據(jù)的影響,項(xiàng)集身份誤差是項(xiàng)集支持度誤差的外在表現(xiàn).

3.3.2 誤差與支持度閾值的關(guān)系

3.3.2.1 支持度誤差

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

(1) 橫向比較:橫向比較圖2(d)、圖3(d)可發(fā)現(xiàn):誤差大小關(guān)系跟圖2(a)、圖3(a)一致,仍是GR-PPFM＜mask.說(shuō)明在整體隱私保護(hù)度相同時(shí),多參數(shù)隨機(jī)化方法GR-PPFM 的挖掘結(jié)果優(yōu)于單參數(shù)mask 方法;

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

3.3.2.2 項(xiàng)集身份誤差

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

3.3.3 支持度重構(gòu)與不重構(gòu)誤差對(duì)比

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

Fig.4 Error of support reconstruction vs.non-reconstruction圖4 支持度重構(gòu)與不重構(gòu)誤差對(duì)比

圖4(a)、圖4(c)針對(duì)IBM Almaden 生成器生成的數(shù)據(jù),可發(fā)現(xiàn)支持度不重構(gòu)的誤差遠(yuǎn)遠(yuǎn)大于重構(gòu)誤差.說(shuō)明數(shù)據(jù)經(jīng)隨機(jī)化后,項(xiàng)集的支持度已發(fā)生顯著變化,直接從隨機(jī)化后的數(shù)據(jù)得到的挖掘結(jié)果已遠(yuǎn)遠(yuǎn)偏離從原始數(shù)據(jù)挖掘得到的結(jié)果,必須通過(guò)支持度重構(gòu)恢復(fù)原數(shù)據(jù)庫(kù)中各項(xiàng)集的支持度,以得到跟原數(shù)據(jù)盡可能相近的挖掘結(jié)果.

圖4(b)、圖4(d)針對(duì)真實(shí)購(gòu)物籃數(shù)據(jù),可發(fā)現(xiàn)當(dāng)頻繁項(xiàng)集長(zhǎng)度不大時(shí),不重構(gòu)的誤差遠(yuǎn)遠(yuǎn)大于重構(gòu)誤差;但當(dāng)頻繁項(xiàng)集長(zhǎng)度較大時(shí)(單參數(shù)隨機(jī)化后k=4,5,分組隨機(jī)化k=5),不重構(gòu)的誤差反而小于重構(gòu)的誤差.說(shuō)明對(duì)于高階項(xiàng)集重構(gòu)的誤差大,這跟之前分析的誤差隨k增大而增大的規(guī)律一致.綜合圖4,針對(duì)分組隨機(jī)化,對(duì)于低階項(xiàng)集(k＜5)使用重構(gòu)支持度,對(duì)于高階項(xiàng)集(k≥5)使用不重構(gòu)支持度.

3.3.4 隱私保護(hù)對(duì)比

下面分析兩種方法的隱私保護(hù)性能,從隱私保護(hù)度(定量)、個(gè)體隱私保護(hù)差異性和暴露的信息(定性)等方面進(jìn)行對(duì)比.本文隱私保護(hù)性能考慮的場(chǎng)景是敏感問(wèn)題調(diào)查或購(gòu)物時(shí),對(duì)于敏感問(wèn)題回答為“是”和“購(gòu)買(mǎi)”敏感物品的保護(hù),不考慮對(duì)于敏感問(wèn)題回答為“否”和“不購(gòu)買(mǎi)”敏感物品的保護(hù).并假定被調(diào)查者運(yùn)用隨機(jī)化裝置給出了真實(shí)的回答,購(gòu)物數(shù)據(jù)提供者對(duì)數(shù)據(jù)進(jìn)行了相應(yīng)的隨機(jī)化變換.

3.3.4.1 隱私保護(hù)度

文獻(xiàn)[10]將單參數(shù)隨機(jī)化mask 的隱私保護(hù)度privacy定義為1-R(p),其中,R(p)=aR1(p)+(1-a)R0(p).其中,R1(p)表示原始數(shù)據(jù)庫(kù)中的“1”能從隨機(jī)化后的數(shù)據(jù)庫(kù)中被還原的概率,R0(p)表示原始數(shù)據(jù)庫(kù)中的“0”能從隨機(jī)化后的數(shù)據(jù)庫(kù)中被還原的概率,a為隱私保護(hù)權(quán)重.本文隱私保護(hù)場(chǎng)景只考慮敏感問(wèn)題回答為“是”和“購(gòu)買(mǎi)”敏感物品記錄的保護(hù),即對(duì)如表1 所示的0-1 購(gòu)物籃數(shù)據(jù),只考慮“1”值的保護(hù).設(shè)保護(hù)權(quán)重系數(shù)a=1,則隱私保護(hù)度公式為

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

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

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

? 當(dāng)s0=0 時(shí),數(shù)據(jù)是全0 數(shù)據(jù),R1(p)=0,隱私保護(hù)度最高,為1.

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

定義1(最低隱私保護(hù)度minPrivacy).分組隨機(jī)化中,隱私保護(hù)度最小的分組對(duì)應(yīng)的隱私保護(hù)度.公式為

定義2(最高隱私保護(hù)度maxPrivacy).分組隨機(jī)化中,隱私保護(hù)度最大的分組對(duì)應(yīng)的隱私保護(hù)度.公式為

定義3(平均隱私保護(hù)度avgPrivacy).分組隨機(jī)化中,多個(gè)分組隱私保護(hù)度的平均值稱(chēng)為平均隱私保護(hù)度.計(jì)算公式為

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

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

Table 5 Privacy of GR-PPFM vs.mask表5 GR-PPFM 與mask 方法隱私保護(hù)性能對(duì)比

單參數(shù)隨機(jī)化mask 僅對(duì)應(yīng)一個(gè)隱私保護(hù)度,實(shí)驗(yàn)中,單參數(shù)mask 方法的隨機(jī)化概率p=0.84,分組多參隨機(jī) 化的平均概率=0.84,兩者相等.因此,單參數(shù)隨機(jī)化的隱私保護(hù)度與分組隨機(jī)化的整體隱私保護(hù)度相同,合成 數(shù)據(jù)是32.4%,真實(shí)數(shù)據(jù)是43.4%.

3.3.4.2 隱私保護(hù)差異性

除定量考察隱私保護(hù)度外,還可定性分析兩種方法對(duì)個(gè)體隱私保護(hù)的差異性及為支持度重構(gòu)需暴露的信息的差異.GR-PPFM 對(duì)個(gè)體實(shí)施有差異的保護(hù),而mask 實(shí)施無(wú)差異的保護(hù).

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

兩種方法的隱私保護(hù)度、隱私保護(hù)差異性和為支持度重構(gòu)需要暴露的信息見(jiàn)表5,其中,D′表示D隨機(jī)化后 的全部數(shù)據(jù),表示D中以pg的概率隨機(jī)化后的第g組數(shù)據(jù),其占全部數(shù)據(jù)的比例為wg.實(shí)驗(yàn)中,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 拓展實(shí)驗(yàn)

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

Fig.5 Support error of GR-PPFM/emask/RE on real-world basket data圖5 GR-PPFM/emask/RE 在真實(shí)購(gòu)物數(shù)據(jù)中的支持度誤差

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

4 總結(jié)與展望

已有以mask 為代表的隱私保護(hù)頻繁模式挖掘方法,在對(duì)數(shù)據(jù)隨機(jī)化時(shí),采用統(tǒng)一的隨機(jī)化參數(shù),對(duì)所有個(gè)體實(shí)施同等、無(wú)差異的保護(hù).考慮到不同人群對(duì)隱私保護(hù)需求的差異性,本文提出一種基于分組隨機(jī)化的隱私保護(hù)頻繁模式挖掘GR-PPFM 方法.針對(duì)GR-PPFM,探索了支持度重構(gòu)方法以及與之相適應(yīng)的頻繁模式挖掘算法,實(shí)現(xiàn)了粗粒度的個(gè)性化隱私保護(hù)頻繁模式挖掘.實(shí)驗(yàn)結(jié)果表明:

(1) 在整體隱私保護(hù)度相同情況下,分組隨機(jī)化GR-PPFM 挖掘結(jié)果準(zhǔn)確性高于整體單參數(shù)隨機(jī)化mask;

(2) 分組隨機(jī)化對(duì)不同人群實(shí)行有差異的保護(hù),個(gè)體隱私保護(hù)度更強(qiáng),為支持度重構(gòu)暴露的信息更少;

(3) 支持度重構(gòu)誤差隨項(xiàng)集長(zhǎng)度的增大而增大、隨支持度閾值的增大而減小,支持度重構(gòu)誤差遠(yuǎn)遠(yuǎn)小于直接挖掘不重構(gòu)的誤差.

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

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