隱私保護(hù)頻繁項(xiàng)集挖掘中的分組隨機(jī)化模型

郭宇紅， 童云海

(1. 國際關(guān)系學(xué)院 信息科技學(xué)院， 北京 100091；2. 北京大學(xué) 智能科學(xué)系， 北京 100871)

數(shù)據(jù)挖掘能從大量數(shù)據(jù)中發(fā)現(xiàn)新穎的、潛在有用的、可被用戶理解的知識(shí)，成為一種有效的分析決策手段，在企事業(yè)中得到廣泛應(yīng)用.頻繁項(xiàng)集挖掘是數(shù)據(jù)挖掘中的一個(gè)重要分支，能從大量數(shù)據(jù)中發(fā)現(xiàn)有趣的關(guān)聯(lián)關(guān)系.有效的數(shù)據(jù)分析需要有大量真實(shí)的數(shù)據(jù)做基礎(chǔ)，而人們對數(shù)據(jù)隱私和安全問題的日益關(guān)注，使得在數(shù)據(jù)收集階段中，出于隱私的考慮，人們可能不再愿意提供真實(shí)的數(shù)據(jù)供分析使用.因此，如何在基于隱私和安全考慮的環(huán)境中，很好地實(shí)施數(shù)據(jù)挖掘任務(wù)和各種應(yīng)用，是隱私保護(hù)數(shù)據(jù)挖掘要解決的問題[1-3].

隨機(jī)化[4-5]是目前隱私保護(hù)數(shù)據(jù)挖掘中運(yùn)用的主要方法，基本思想是通過向原始數(shù)據(jù)中加入噪音的方式來對數(shù)據(jù)作干擾以達(dá)到隱私信息的保護(hù)，同時(shí)數(shù)據(jù)的統(tǒng)計(jì)性質(zhì)在隨機(jī)干擾后的數(shù)據(jù)中保持不變,以獲取正確的挖掘結(jié)果,包括隨機(jī)化干擾和隨機(jī)化回答兩種模型.其中,隨機(jī)化干擾模型主要用于數(shù)值數(shù)據(jù)，通過在原始數(shù)值數(shù)據(jù)上增加隨機(jī)干擾數(shù)實(shí)現(xiàn)；隨機(jī)化回答模型主要用于分類數(shù)據(jù)，通過對分類屬性值在不同取值間作隨機(jī)變換實(shí)現(xiàn)，該模型最先由沃納提出[6]，被廣泛用于敏感性問題的調(diào)查中.在隱私保護(hù)頻繁模式挖掘[7-11]、隱私保護(hù)關(guān)聯(lián)規(guī)則挖掘[12-14]的應(yīng)用方面，文獻(xiàn)[14]通過數(shù)據(jù)干擾和支持度重構(gòu)實(shí)現(xiàn)了隱私數(shù)據(jù)保護(hù)的關(guān)聯(lián)規(guī)則挖掘；文獻(xiàn)[15]對MASK(mining associations with secrecy Konstraints)算法進(jìn)行了擴(kuò)展，提出“特定于符號(hào)(1和0)”的隨機(jī)化過程和相應(yīng)的eMASK算法；文獻(xiàn)[16]提出“非統(tǒng)一”參數(shù)的隨機(jī)化過程和相應(yīng)的項(xiàng)集支持度遞歸估計(jì)RE(recursive estimation)算法；文獻(xiàn)[17]對MASK算法在支持度重構(gòu)復(fù)雜度方面進(jìn)行了優(yōu)化，提出了mMASK算法.

上述隨機(jī)化回答模型在隱私保護(hù)頻繁項(xiàng)集挖掘中取得很大進(jìn)展，但存在以下2點(diǎn)問題.1) 隨機(jī)化模型類型單一，隨機(jī)化參數(shù)調(diào)控的數(shù)據(jù)范圍寬、粒度粗，對隱私數(shù)據(jù)保護(hù)粒度的控制缺乏靈活性.2) 已有模型沒有考慮不同個(gè)體隱私保護(hù)需求的差異性，而這種需求在現(xiàn)實(shí)應(yīng)用中是客觀存在和急需解決的.針對以上問題，本文在沃納模型、單參數(shù)等隨機(jī)化模型的基礎(chǔ)上，提出個(gè)體分組多參隨機(jī)化模型PN/g，并結(jié)合例子對水平分組隨機(jī)化的支持度重構(gòu)方法進(jìn)行了探索.

1 沃納模型

沃納模型是最初由Warner在1965年針對“吸毒問題的調(diào)查”一類敏感問題提出的，可應(yīng)用于單一屬性敏感性問題的統(tǒng)計(jì)學(xué)調(diào)查和分析.在“吸毒問題的調(diào)查”這類問題中，調(diào)查者想要知道一定人群中吸毒者的比例，但當(dāng)面對“你是否曾經(jīng)吸過毒”這類敏感問題的回答時(shí)，被調(diào)查者(尤其是吸毒者)很可能不愿意回答，或者給出一個(gè)虛假的回答.針對這類問題，沃納模型給出了解決辦法.

該模型在調(diào)查中設(shè)計(jì)下面兩個(gè)對立的問題供被調(diào)查者回答:1) 你是否吸過毒；2) 你是否沒吸過毒.同時(shí)，分給每個(gè)被調(diào)查者一個(gè)隨機(jī)數(shù)生成裝置，被調(diào)查者可根據(jù)生成的隨機(jī)數(shù)的不同，選擇回答第1個(gè)問題，還是第2個(gè)問題.比如調(diào)查者可以跟被調(diào)查者事先約定:當(dāng)生成的隨機(jī)數(shù)小于p時(shí)，選第1個(gè)問題回答；大于等于p時(shí)，選第2個(gè)問題回答；無論選哪個(gè)問題，都要作出真實(shí)的回答.

(1)

2 單參數(shù)隨機(jī)化模型

現(xiàn)有隱私保護(hù)數(shù)據(jù)挖掘方法所使用的隨機(jī)化回答技術(shù)，是在沃納模型的基礎(chǔ)上形成的.沃納模型只能用于單一敏感性問題的調(diào)查和分析，其核心思想是在保護(hù)個(gè)體數(shù)據(jù)隱私的同時(shí)，能求得單一屬性上的統(tǒng)計(jì)值.對于頻繁模式挖掘而言，其對應(yīng)的數(shù)據(jù)通常會(huì)有多個(gè)屬性項(xiàng)，頻繁模式挖掘的目標(biāo)則是通過對項(xiàng)集支持度的計(jì)算，發(fā)現(xiàn)在總體樣本中所占比例較高的項(xiàng)集(即頻繁項(xiàng)集).因此，對隱私保護(hù)頻繁模式挖掘，其目標(biāo)是在保護(hù)個(gè)體隱私的同時(shí)，求取多屬性上的統(tǒng)計(jì)值——項(xiàng)集支持度.沃納模型中的公式只能解決隱私保護(hù)場景下1-項(xiàng)集支持度的計(jì)算.文獻(xiàn)[14]提出的MASK方法解決了隱私保護(hù)場景下k-項(xiàng)集的支持度計(jì)算問題，從而很好地解決了隱私保護(hù)頻繁模式挖掘問題，其原理如下.

1) 隨機(jī)化過程.假定用二維0-1矩陣表示原始事務(wù)集D，“1”和“0”分別表示對應(yīng)的項(xiàng)出現(xiàn)和不出現(xiàn)在事務(wù)中，則單參數(shù)隨機(jī)化對于D中任意元素v∈{0,1}，以p的概率取原值v，以1-p的概率取1-v，生成隨機(jī)化事務(wù)集D′.p稱作隨機(jī)化參數(shù)，p值越高，生成的D′中保留越多的原值v.

2) 支持度重構(gòu).假定A={I1,I2,…,Ik}為k-項(xiàng)集，A中的項(xiàng)可能全部或部分出現(xiàn)在D的事務(wù)T中.A∩T共有2k種可能的取值，每一種取值對應(yīng)了A的一個(gè)子集fi(i∈{0,1,…,2k-1})，并假設(shè)在二維0-1矩陣表示D時(shí)，i的k位二進(jìn)制數(shù)字恰好對應(yīng)fi的從I1到Ik的k項(xiàng)0-1序列.即

同時(shí)，假定Cfi,Afi表示D(I1…Ik)中僅包含fi而不包含補(bǔ)集Afi中的任何項(xiàng)的事務(wù)數(shù)(fi在D(I1…Ik)中的凈計(jì)數(shù)).即D中對應(yīng)A的k列0-1序列等于fi的事務(wù)數(shù).當(dāng)A在上下文中明確時(shí)，Cfi,Afi簡記為Cfi.Cf0,Cf1,…,Cf2k-1(簡記為C0,C1,…,C2k-1)構(gòu)成向量CA，即CA=[C0,C1,…,C2k-1]T；相應(yīng)地，C′f表示D′中僅包含f的事務(wù)數(shù)，向量C′A=[C′0,C′1,…,C′2k-1]T.則CA和C′A的期望值存在如下關(guān)系，即

E(C′A)=P·CA.

(2)

式(2)中：P=[pi,j]為隨機(jī)化概率參數(shù)p構(gòu)成的2k×2k變換矩陣，pi,j表示D中僅包含fi(fi?A)的事務(wù)(即對應(yīng)的從I1到Ik的k項(xiàng)0-1序列恰好為i的k位二進(jìn)制值的事務(wù))轉(zhuǎn)換成D′中僅包含fj(fj?A)的事務(wù)的概率.若i和j對應(yīng)的k位二進(jìn)制0-1串中值相同的位數(shù)為r，則pi，j=pr(1-p)k-r(0≤r≤k).為便于理解，給出單參數(shù)隨機(jī)化中3-項(xiàng)集的變換概率矩陣，如表1所示.

表1 單參數(shù)隨機(jī)化中3-項(xiàng)集的變換概率矩陣Tab.1 Transition probability matrix of 3-itemset in single-parameter randomization

(3)

式(3)兩邊同除以事務(wù)總數(shù)∣D∣，可得MASK方法對項(xiàng)集A的重構(gòu)支持度,即

(4)

以上即為單參數(shù)隨機(jī)化MASK方法在隱私保護(hù)頻繁模式挖掘中的工作原理.該方法能保證在不訪問原始數(shù)據(jù)D的情況下，從隨機(jī)化后的數(shù)據(jù)集D′中估算出各項(xiàng)集的原始支持計(jì)數(shù)和支持度，從而得到頻繁項(xiàng)集和關(guān)聯(lián)規(guī)則挖掘結(jié)果.

單參數(shù)隨機(jī)化模型的缺點(diǎn)是，所有數(shù)據(jù)元素的隱私保護(hù)程度和最終挖掘結(jié)果的準(zhǔn)確性全都受控于單一的隨機(jī)化參數(shù)p.這不僅忽視不同數(shù)據(jù)元素隱私保護(hù)需求的差異性，使隱私數(shù)據(jù)不能得到充分有效的保護(hù)，而且挖掘結(jié)果的準(zhǔn)確性也不理想.挖掘結(jié)果受p的制約很大，p一旦確定，挖掘結(jié)果就確定，挖掘結(jié)果準(zhǔn)確性上沒有任何可調(diào)控的余地；而同時(shí)對隱私的保護(hù)也顯得過于魯棒、不夠精準(zhǔn)和粒度過粗.

3 分組多參隨機(jī)化PN/g模型

3.1 PN/g基本思想

不同于單參數(shù)隨機(jī)化，多參數(shù)隨機(jī)化用多個(gè)概率參數(shù)對數(shù)據(jù)隨機(jī)化.其思想是對數(shù)據(jù)中的不同元素設(shè)置不同的隱私保護(hù)級別，不同的隱私保護(hù)級別對應(yīng)不同的隨機(jī)化參數(shù)，由參與調(diào)查的個(gè)體自行決定對其不同數(shù)據(jù)元素的隱私保護(hù)級別和相應(yīng)的隨機(jī)化參數(shù).參與調(diào)查的多個(gè)個(gè)體的隱私保護(hù)要求差不多，則可按個(gè)體水平分組隨機(jī)化，使同一組內(nèi)共用一個(gè)隨機(jī)化參數(shù)，而每個(gè)隨機(jī)化參數(shù)控制組中的多行.假設(shè)參與調(diào)查的個(gè)體總數(shù)為N，若等分時(shí)，每組包含g行，則組數(shù)和隨機(jī)化參數(shù)個(gè)數(shù)為N/g，就形成分組多參隨機(jī)化模型.

3.2 PN/g模型舉例

為簡單起見，假定屬性取值均為布爾值“1”和“0”.由這N個(gè)個(gè)體的布爾屬性組成需要保護(hù)的、二維布爾矩陣表示的數(shù)據(jù)表D.事實(shí)上，數(shù)值類型屬性可以通過離散化轉(zhuǎn)變?yōu)槎嘣诸悓傩?，即枚舉屬性，而多元分類屬性又可以轉(zhuǎn)變?yōu)椴紶枌傩?，即一般的?shù)據(jù)都可以轉(zhuǎn)變?yōu)槎S布爾矩陣形式.

個(gè)體分組隨機(jī)化的例子，如表2所示.表2中：TID為事務(wù)標(biāo)識(shí)號(hào);左邊為原始事務(wù)集D，由10個(gè)被調(diào)查者的3個(gè)問題項(xiàng)(I1/I2/I3)組成，10個(gè)被調(diào)查者兩兩一組，同一組內(nèi)共用同一個(gè)隨機(jī)化參數(shù).對這五組數(shù)據(jù)分別隨機(jī)化后，生成的隨機(jī)化數(shù)據(jù)集如表2右邊3列數(shù)據(jù)所示.在表2中，由個(gè)體1和2構(gòu)成的第1組數(shù)據(jù)選擇的隨機(jī)化概率參數(shù)p1=1，隨機(jī)化過程對該組數(shù)據(jù)以1的概率保持為真，以0的概率取反，得到的第1組隨機(jī)化數(shù)據(jù)完全保持不變.表明該組中的個(gè)體完全不顧及隱私，愿意完全真實(shí)地貢獻(xiàn)其數(shù)據(jù).相反的，由個(gè)體9和10構(gòu)成的第5組數(shù)據(jù)選擇的隨機(jī)化參數(shù)p5=0.6，隨機(jī)化過程對該組數(shù)據(jù)以0.6的概率保持為真，以0.4的概率取反，得到的第5組隨機(jī)化數(shù)據(jù)中有3個(gè)值保持不變，3個(gè)值被打亂取反.表明該組中的個(gè)體相對比較在乎隱私，只肯貢獻(xiàn)非常有限的數(shù)據(jù).

表2 數(shù)據(jù)集D分組隨機(jī)化PN/g模型Tab.2 Grouping randomization model of PN/g on dataset D

3.3 PN/g模型支持度重構(gòu)

分組多參隨機(jī)化時(shí)，需要求得變換概率矩陣P和進(jìn)行支持度重構(gòu).文中計(jì)算P中元素pi，j的基本思想是:D分組隨機(jī)化為D′作為整體來看時(shí)，項(xiàng)集fi轉(zhuǎn)變?yōu)閒j的概率為各個(gè)分組將項(xiàng)集fi轉(zhuǎn)變?yōu)閒j的概率之和.相應(yīng)地，k-項(xiàng)集A對應(yīng)的2k×2k變換概率矩陣Pk中的元素值為

(5)

例如表2中的分組多參隨機(jī)化中，事務(wù)“000”轉(zhuǎn)變“000”的概率為

而“000”轉(zhuǎn)變?yōu)椤?11”(即空集轉(zhuǎn)變?yōu)槭聞?wù){(diào)I1I2I3})的概率為

這樣便可得到3-項(xiàng)集{I1I2I3}對應(yīng)的8×8變換概率矩陣P3中的所有元素.

分組隨機(jī)化PN/g模型變換概率矩陣P3,如表3所示.表3中：矩陣P3中的某一元素表示某個(gè)項(xiàng)集隨機(jī)化后轉(zhuǎn)變?yōu)榱硪粋€(gè)項(xiàng)集的概率.

表3 分組隨機(jī)化PN/g模型變換概率矩陣P3Tab.3 Transition probability matrix P3 in grouping randomization of PN/g model

(6)

3.4 PN/g模型支持度重構(gòu)示例分析

表4給出了表2數(shù)據(jù)集D對應(yīng)的項(xiàng)集空間中，所有項(xiàng)集的重構(gòu)支持計(jì)數(shù)和重構(gòu)誤差.從表4可看出：7個(gè)項(xiàng)集支持計(jì)數(shù)重構(gòu)總誤差為-1.92，平均每個(gè)項(xiàng)集的支持計(jì)數(shù)重構(gòu)誤差為-0.27.即相對原數(shù)據(jù)，每個(gè)項(xiàng)集支持計(jì)數(shù)估計(jì)值比真實(shí)值少了0.27.該誤差較小，驗(yàn)證了文中所提PN/g模型支持度重構(gòu)方法的可行性和有效性.

表4 PN/g和MASK支持計(jì)數(shù)重構(gòu)對比Tab.4 Support count reconstruction comparison of PN/g and MASK

3.5 與MASK方法對比

(7)

對比原始支持計(jì)數(shù)發(fā)現(xiàn)，相對于文中所提PN/g模型，MASK方法僅在支持計(jì)數(shù)低的項(xiàng)集I1I2I3上，重構(gòu)支持計(jì)數(shù)誤差絕對值(0.26)更小，而在支持計(jì)數(shù)相對高的其他項(xiàng)集上，PN/g模型的重構(gòu)誤差絕對值小于或等于MASK，這意味著對頻繁項(xiàng)集挖掘，PN/g模型在頻繁項(xiàng)集的支持度重構(gòu)上將更為準(zhǔn)確.由表4可知：整個(gè)項(xiàng)集空間支持計(jì)數(shù)重構(gòu)的總誤差和平均誤差絕對值也小于MASK.這進(jìn)一步驗(yàn)證了文中所提PN/g模型用于隱私保護(hù)頻繁項(xiàng)集挖掘的有效性,即PN/g模型不僅能實(shí)現(xiàn)差異化的隱私保護(hù)，且能以小的誤差重構(gòu)頻繁項(xiàng)集的支持度.同時(shí)，相對單參數(shù)隨機(jī)化MASK，多參數(shù)隨機(jī)化PN/g模型能在平均隱私保護(hù)度相同情況下，以更小的誤差重構(gòu)頻繁項(xiàng)集的支持度，從而提高頻繁項(xiàng)集挖掘的準(zhǔn)確性.

4 結(jié)論

針對頻繁項(xiàng)集挖掘中的隱私保護(hù)問題，提出個(gè)體分組多參隨機(jī)化PN/g模型，給出其在隱私保護(hù)頻繁項(xiàng)集挖掘中的支持度重構(gòu)方法.最后，通過示例驗(yàn)證了支持度重構(gòu)方法的可行性和有效性.

作為個(gè)性化隱私保護(hù)挖掘的初步嘗試，還有如下一些工作需要進(jìn)一步探究.1) 針對PN/g模型的支持度重構(gòu)方法，理論推導(dǎo)出該方法所對應(yīng)的支持計(jì)數(shù)重構(gòu)公式和支持度重構(gòu)偏差公式.2) 設(shè)計(jì)相應(yīng)算法和基于大數(shù)據(jù)集進(jìn)一步驗(yàn)證方法的有效性，特別是挖掘結(jié)果的準(zhǔn)確性.3) 基于新的頻繁項(xiàng)集挖掘算法[18]，設(shè)計(jì)與之相適應(yīng)的、更高效的隱私保護(hù)頻繁項(xiàng)集挖掘算法.