隱私保護頻繁項集挖掘中的細粒度隨機化模型

郭宇紅 童云海

摘 ?要：已有的隨機化回答模型調(diào)控的數(shù)據(jù)范圍寬、粒度粗，對隱私數(shù)據(jù)的保護粒度缺乏靈活性，無法實現(xiàn)精細化、個性化、差異化的隱私保護。提出三類多參數(shù)隨機化回答模型，包括行多參、復(fù)合多參、分組多參共11種隨機化回答模型，給出了模型的分類框架和分類層次。細粒度多參數(shù)隨機化模型可實現(xiàn)精細化、個性化、差異化的隱私保護效果。

關(guān)鍵詞：隨機化回答;隱私保護;頻繁項集;敏感問題調(diào)查

中圖分類號：TP311 ? ? 文獻標(biāo)識碼：A

Abstract：The existing randomized response model regulates a wide range of data with coarse granularity and lacks flexibility in protecting privacy，unable to achieve fine，personalized and differentiated privacy protection.Three kinds，11 types of multi-parameter random response models are proposed，including row multi-parameter，compound multi-parameter and grouping multi-parameter.The classification framework and hierarchy of these models are given.The fine-grained multi-parameter randomized response models can realize fine，individualized and differentiated privacy protection effect.

Keywords：randomized response;privacy preserving;frequent item set;sensitivity survey

1 ? 引言（Introduction）

頻繁項集挖掘是數(shù)據(jù)挖掘中的一個重要分支，隨著人們對數(shù)據(jù)隱私和安全的日益關(guān)注，頻繁項集挖掘賴以生存的數(shù)據(jù)環(huán)境發(fā)生很大變化，表現(xiàn)在：（1）在數(shù)據(jù)收集階段，出于隱私的考慮，人們可能不再愿意提供真實的數(shù)據(jù)供分析使用，比如在線調(diào)查，一家藥品公司為了發(fā)現(xiàn)各種疾病之間的關(guān)聯(lián)關(guān)系，需要開展疾病的調(diào)查以收集數(shù)據(jù)，而調(diào)查者出于隱私的考慮不愿意提供數(shù)據(jù)或提供虛假數(shù)據(jù);（2）在企業(yè)試圖將頻繁模式挖掘任務(wù)外包給第三方，或多個企業(yè)合作進行頻繁模式挖掘而需共享數(shù)據(jù)時，出于客戶隱私和商業(yè)安全的考慮，在數(shù)據(jù)共享前需對數(shù)據(jù)進行預(yù)處理，以保護客戶隱私和隱藏一些敏感規(guī)則;（3）頻繁項集挖掘的科研人員對自己的算法進行測試時，難以得到真實數(shù)據(jù)作為benchmark。如何在基于隱私和安全考慮的環(huán)境中，很好地實施數(shù)據(jù)挖掘任務(wù)和各種應(yīng)用，是隱私保護數(shù)據(jù)挖掘要解決的問題[1-3]。

2 ? 相關(guān)工作（Related work）

隨機化[4，5]是目前隱私保護數(shù)據(jù)挖掘中運用的主要方法，包括隨機化干擾（randomized perturbation）和隨機化回答（randomized response）兩種模型。其中隨機化干擾模型主要用于數(shù)值數(shù)據(jù)，通過在原始數(shù)值數(shù)據(jù)上增加隨機干擾數(shù)實現(xiàn);隨機化回答模型主要用于分類數(shù)據(jù)，通過對分類屬性值在不同取值間作隨機變換實現(xiàn)，該模型最先由沃納提出[6]，被廣泛用于敏感性問題[7]的調(diào)查中。

在隱私保護頻繁模式挖掘[8-11]、隱私保護關(guān)聯(lián)規(guī)則挖掘[12，13]方面，文獻[13]提出基于隨機化回答的mask/MASK（Mining Associations with Secrecy Konstraints）方法，通過數(shù)據(jù)干擾和支持度重構(gòu)實現(xiàn)了隱私數(shù)據(jù)保護的關(guān)聯(lián)規(guī)則挖掘，mask方法中隨機化參數(shù)只有一個，所有的數(shù)據(jù)元素受控于此唯一的參數(shù)。文獻[14]對mask算法進行了擴展，提出“特定于符號（1和0）”的隨機化過程（symbol-specific distortion）和相應(yīng)的emask算法，emask對“1”“0”設(shè)置兩個不同的隨機化參數(shù)，使它們擁有不同的隱私保護級別。文獻[15]提出“非統(tǒng)一”（non-uniform）參數(shù)的隨機化過程和相應(yīng)的項集支持度遞歸估計RE（Recursive Estimation）算法，RE在隨機化過程中對不同屬性設(shè)置不同的隨機化參數(shù)，使不同屬性可以擁有不同的隱私保護級別。文獻[16]對mask算法在支持度重構(gòu)復(fù)雜度方面進行了優(yōu)化，提出了mmask算法。文獻[17]使用“風(fēng)險-效用”映射（Risk-Utility，R-U）比較了不同的隨機化策略，并提出了用于布爾數(shù)據(jù)和分類數(shù)據(jù)的最優(yōu)隨機化策略，同emask一樣，針對布爾數(shù)據(jù)的隨機化采用兩個隨機化參數(shù)。

上述隨機化回答模型在隱私保護頻繁項集挖掘中，取得了很大進展，但存在以下問題。（1）隨機化模型類型單一，隨機化參數(shù)調(diào)控的數(shù)據(jù)范圍寬、粒度粗，對隱私數(shù)據(jù)保護粒度的控制缺乏靈活性。（2）已有模型沒有考慮不同個體隱私保護需求的差異性，而這種需求在現(xiàn)實應(yīng)用中是客觀存在和急需解決的。

針對以上問題，本文在沃納模型、單參數(shù)等隨機化模型的基礎(chǔ)上，提出三類細粒度的隨機化回答模型：個體多參隨機化模型、復(fù)合多參隨機化模型、分組多參隨機化模型。個體多參隨機化模型，面向不同個體需要不同保護的多樣化隱私保護需求問題，可為不同個體設(shè)置不同的隨機化參數(shù);復(fù)合多參隨機化模型，組合已有的單一型隨機化模型，使隨機化參數(shù)控制的數(shù)據(jù)范圍更加細致;分組多參隨機化模型，可對數(shù)據(jù)按不同方式分組，使隨機化參數(shù)對于數(shù)據(jù)粒度的控制更加靈活。本文給出了隨機化模型的分類框架和分類層次。本文旨在為隨機化回答模型在敏感問題調(diào)查、隱私保護頻繁項集挖掘的應(yīng)用提供一個概覽，推動隱私保護頻繁項集挖掘方法的進一步研究。

3 ?多參數(shù)隨機化模型 （Multi-parameter random response models）

不同于單參數(shù)隨機化，多參數(shù)隨機化用多個概率參數(shù)對數(shù)據(jù)進行隨機化。其思想是對數(shù)據(jù)中的不同元素設(shè)置不同的隱私保護級別，不同的隱私保護級別對應(yīng)不同的隨機化參數(shù)，由參與調(diào)查的個體自行決定對其不同數(shù)據(jù)元素的隱私保護級別和相應(yīng)的隨機化參數(shù)。根據(jù)不同屬性取值、不同屬性和不同個體可以有以下幾種多參數(shù)隨機化模型。為簡單起見，假設(shè)參與調(diào)查的個體總數(shù)為N，每個個體對應(yīng)m個需要保護的屬性，屬性取值均為布爾值“1”“0”，由這N個個體的m個布爾屬性組成需要保護的、二維布爾矩陣表示的數(shù)據(jù)表D。（事實上，數(shù)值類型屬性可以通過離散化轉(zhuǎn)變?yōu)槎嘣诸悓傩裕疵杜e屬性，而多元分類屬性又可以轉(zhuǎn)變?yōu)椴紶枌傩?，即一般的?shù)據(jù)都可以轉(zhuǎn)變?yōu)槎S布爾矩陣形式）

3.1 ? 二元隨機化模型（簡稱P2模型）

這是最簡單的多參數(shù)隨機化模型，在該模型中，設(shè)置有兩個不同的隨機化參數(shù)p1和p2，對值“1”和“0”區(qū)別對待，p1和p2分別決定了對“1”和“0”的兩個不同的隱私保護級別。隨機化過程為：對于D中取值為“1”的元素，以p1的概率保持不變，以1-p1的概率取反;對于D中取值為“0”的元素以p2的概率保持不變，1-p2的概率取反。

文獻[14]對[13]提出的單參數(shù)隨機化模型和對應(yīng)的mask算法進行了擴展，提出了“特定于符號（1和0）”的隨機化過程和相應(yīng)的emask算法，其中的“特定于符號”的隨機化過程對應(yīng)于上述兩參數(shù)隨機化模型。通過對“1”“0”設(shè)置兩個不同的隨機化參數(shù)，并對p1和p2進行認真選擇和調(diào)節(jié)，emask可以在獲得滿意的隱私保護性、挖掘結(jié)果準(zhǔn)確性的同時，提高頻繁項集挖掘的時間性能。

3.2 ? 列多參隨機化模型（簡稱Pm模型）

列（屬性）多參隨機化模型，對不同屬性（列）設(shè)置不同的隱私保護級別，假定有m個屬性A1…Am，則設(shè)置p1…pm共m個隨機化參數(shù)。隨機化過程為：對于屬性Ai所在列中的所有數(shù)據(jù)元素，以pi的概率取原值，以1-pi的概率取反。

列多參模型主要基于以下事實：通常人們對數(shù)據(jù)中的不同屬性有不同的隱私關(guān)注度。反映在敏感問題問卷調(diào)查中，不同的問題其敏感度是有差別的，例如，對于“你是否喝過酒”“你是否抽過煙”和“你是否吸過毒”三個問題，其敏感度和需要的隱私保護級別是不一樣的。再比如“性別”“年齡”和“收入”三個屬性的敏感度和需要的保護級別也是不同的。文獻[15]針對該類場景，即“不同屬性需要不同保護”的關(guān)聯(lián)規(guī)則挖掘進行了研究，提出了“非統(tǒng)一”參數(shù)的隨機化過程和對應(yīng)的項集支持度遞歸估計RE算法。其中“非統(tǒng)一”參數(shù)的隨機化對應(yīng)于上述列多參隨機化模型。RE方法通過允許不同屬性擁有不同的隱私級別，即對不同屬性設(shè)置不同的隨機化參數(shù)，可以提高支持度估計的精確性。

3.3 ? 行多參隨機化模型（簡稱PN模型）

行（個體）多參隨機化模型，對不同個體設(shè)置不同的隱私保護級別。假定有N個個體I1…IN，則設(shè)置p1…pN共N個隨機化參數(shù)。隨機化過程為：對于個體Ii所在行中的所有數(shù)據(jù)元素，以pi的概率取原值，以1-pi的概率取反。

列多參模型雖然解決了縱向“不同屬性需要不同保護”的隱私保護需求問題，但沒有解決“不同個體需要不同保護”的隱私保護需求問題。

事實上，通常不同的人對數(shù)據(jù)（即便是同樣的數(shù)據(jù)）會有不同的隱私關(guān)注度，這來自個人對事物的主觀態(tài)度和意愿。反映在調(diào)查問卷中，不同的人對問題（即便是對同一個問題）的敏感度是有差異的，例如，對于同樣的調(diào)查問題“你是否吸過毒”，吸毒者張三、李四和王五的反應(yīng)態(tài)度可能會截然不同。張三對此問題并不敏感，表示十分愿意真實地做出回答和貢獻其個人對此問題的數(shù)據(jù);李四對此問題的敏感度模棱兩可，表示愿意以60%的概率貢獻其真實數(shù)據(jù);王五對此問題非常敏感，完全不愿意泄露對此問題的個人信息。同樣，對于“年齡”屬性，女性比男性可能更敏感，造成問卷調(diào)查中，女性組對于男性組更難于接受此項調(diào)查。這些例子均表明不同的個體會有不同的隱私保護要求和偏好。

然而，到目前為止，還沒有文獻對“不同個體需要不同保護”的隱私保護頻繁模式挖掘（或關(guān)聯(lián)規(guī)則挖掘）問題做研究。現(xiàn)有的隱私保護關(guān)聯(lián)規(guī)則挖掘解決方案都是獨立于個體的，即默認所有個體的隱私保護要求都相同，沒有尊重不同個體的主觀意愿。在提倡“以客戶為中心”“以人為本”“尊重用戶偏好”“強調(diào)個性化服務(wù)”的人本時代，如何能在獲取相關(guān)信息的同時，盡可能地為不同的個體提供定制的隱私保護服務(wù)，滿足不同個體的多樣化隱私保護要求，是隱私保護的數(shù)據(jù)發(fā)布、數(shù)據(jù)分析和數(shù)據(jù)挖掘必須解決和亟待解決的問題。本章將結(jié)合上面所提出的行多參隨機化模型，設(shè)計與之相對應(yīng)的項集支持度估算方法，通過允許不同個體擁有不同的隱私級別，實現(xiàn)頻繁模式挖掘中的個性化隱私保護。

3.4 ? 復(fù)合多參隨機化模型

上述三種基本的多參隨機化模型P2、Pm、PN可相互交叉組合，產(chǎn)生P2×m、P2×N、Pm×N和P2×m×N共四種復(fù)合的多參數(shù)隨機化模型（腳標(biāo)表示隨機化參數(shù)個數(shù)），不同模型中隨機化參數(shù)所控制的范圍或粒度不同。

三種基本多參隨機化模型中，二元隨機化P2模型中的一個隨機化參數(shù)控制一類取值，只對“1”和“0”區(qū)分，保護粒度最粗;Pm模型中的一個隨機化參數(shù)控制一列，對每列作區(qū)分;PN模型中的一個參數(shù)控制一行，對每行作區(qū)分。

四種復(fù)合多參隨機化模型中，P2×m模型的每列有兩個隨機化參數(shù)（稱其為二元隨機化列），一個控制該列中的“1”，一個控制該列中的“0”，對“1”“0”和列同時作區(qū)分;P2×N模型中的每行有兩個隨機化參數(shù)（稱其為二元隨機化行），分別控制該行中的“1”和“0”，對“1”“0”和行同時作區(qū)分;而Pm×N模型有m×N個隨機化參數(shù)，每個參數(shù)控制一個數(shù)據(jù)單元，對行和列同時區(qū)分;P2×m×N模型有2×m×N個隨機化參數(shù)，每一個數(shù)據(jù)單元上有兩個隨機化參數(shù)（稱其為二元隨機化數(shù)據(jù)單元），該模型對取值、行、列同時作區(qū)分，保護粒度最細。

3.5 ? 分組多參隨機化模型

在細粒度的隱私保護隨機化模型中，若保護粒度太細，隨機化參數(shù)太多，并且存在多個屬性的敏感度相當(dāng)，或參與調(diào)查的多個個體的隱私保護要求差不多，則可按屬性垂直分組或按個體水平分組，進行分組隨機化，使同一組內(nèi)共用一個隨機化參數(shù)，形成分組多參隨機化模型。將按個體、屬性分組結(jié)合到以上Pm、PN和P2×m、P2×N、Pm×N模型中（注：P2模型不涉及個體、屬性，不可分組），可派生出下面六種分組多參隨機化模型：

Pm/g模型：屬性分組多參隨機化模型，m個屬性被分為若干組，每組一個隨機化參數(shù)，每個隨機化參數(shù)控制組中的多列。若等分時每組包含g列，則組數(shù)和隨機化參數(shù)個數(shù)為m/g。

PN/g模型：個體分組多參隨機化模型，N個個體被分為若干組，每組一個隨機化參數(shù)，每個隨機化參數(shù)控制組中的多行。若等分時每組包含g行，則組數(shù)和隨機化參數(shù)個數(shù)為N/g。

P2×m/g模型：二元屬性分組多參隨機化模型，m個二元隨機化的列垂直分為m/g組，每組有兩個隨機化參數(shù)，一個控制該組中的“1”，一個控制該組中的“0”。

P2×N/g模型：二元個體分組多參隨機化模型，N個二元隨機化的行水平分為N/g組，每組有兩個隨機化參數(shù)，一個控制該組中的“1”，一個控制該組中的“0”。

Pm/g×N/g模型：行、列交叉分組多參隨機化模型，簡稱分塊多參隨機化模型。二維矩陣在行列方向同時分組后，被分為m/g×N/g塊，每塊一個隨機化參數(shù)。

P2×m/g×N/g模型：二元行、列交叉分組多參隨機化模型，簡稱二元分塊多參隨機化模型。二維矩陣在行列方向同時分組后，被分為m/g×N/g塊，每塊兩個隨機化參數(shù)，一個控制該塊中的“1”，一個控制該塊中的“0”。

圖1給出了隨機化模型的分類框架、分類層次。該分類框架主要依據(jù)隨機化過程是否根據(jù)取值、屬性和個體的不同作了區(qū)分。依此分類框架構(gòu)成的隨機化模型分類層次中，最上端的P模型是最簡單的單參數(shù)隨機化模型，該模型不區(qū)分1—0取值、不區(qū)分行和列，以統(tǒng)一的隨機化參數(shù)對一個二維的數(shù)據(jù)表進行隨機化干擾。位于第二層的是三種基本的多參隨機化模型P2、Pm、PN模型，分別對1—0取值、列和行作區(qū)分，并繼承了P模型的基本隨機化過程：以p的概率取原值，以1-p的概率取反。位于第三、第四層的是四種復(fù)合的多參數(shù)隨機化模型P2×m、P2×N、Pm×N和P2×m×N，由相應(yīng)的基本多參隨機化模型交叉組合而產(chǎn)生。六種分組多參隨機化模型未在圖中列出，實際上每個分組隨機化模型都可看作是相應(yīng)模型的特例，比如Pm/g模型可看作是Pm模型在某些列隨機化參數(shù)相等時的特例。

沿分類層次，越往上模型越簡單、隨機化參數(shù)越少，同一層次中，越往左模型越簡單、隨機化參數(shù)越少。且上層模型可看作是下層模型在某些隨機化參數(shù)相等時的特例，比如最上端的、最簡單的單參數(shù)隨機化P模型，可看作是最下端的多參數(shù)隨機化P2×m×N模型在所有2×m×N個隨機化參數(shù)都相等時的特例。

目前，研究者已先后提出了跟單參數(shù)隨機化P模型、二元隨機化P2模型、屬性多參隨機化Pm模型（圖1左上角）分別相匹配的mask、emask和RE三種項集支持度重構(gòu)算法，用以解決隱私保護的頻繁模式挖掘問題。對于除這三種模型外的其他幾種較為復(fù)雜、保護粒度較細的隨機化模型（圖1右下角），還沒有相關(guān)的研究，而這幾種細粒度隨機化模型的研究以及與之相適應(yīng)的項集支持度重構(gòu)算法的設(shè)計，對于進一步加強隨機化過程參數(shù)設(shè)置的靈活性、增強隱私保護挖掘方法的隱私保護性和提高隱私保護挖掘結(jié)果的準(zhǔn)確性，都將有積極的推動作用。同時，圖1右下角與“N”相關(guān)的四個模型在個性化方向的擴展，可作為個性化隱私保護方法研究的一個新起點。

4 ? 結(jié)論（Conclusion）

本文針對頻繁項集挖掘中的隱私保護問題，其主要貢獻在于：（1）拓展和豐富了已有的三種簡單、粗粒度隨機化模型（P、P2、Pm模型），提出了三大類細粒度隨機化模型，共11種，具體包括：一種行多參隨機化模型（PN），四種復(fù)合多參隨機化（P2×m、P2×N、Pm×N和P2×m×N），六種分組多參隨機化模型（Pm/g、PN/g、P2×m/g、P2×N/g、Pm/g×N/g、P2×m/g×N/g）;（2）給出了隨機化模型的分類框架、分類層次。

作為個性化隱私保護頻繁項集挖掘的一個研究分支，還有很多工作值得今后探索。（1）針對PN/g模型的支持度重構(gòu)方法，是否能推導(dǎo)出該方法所對應(yīng)的支持計數(shù)重構(gòu)公式和支持度重構(gòu)偏差公式，是否能設(shè)計相應(yīng)算法實驗驗證方法的有效性需要進一步研究;（2）這11種細粒度隨機化模型的支持度重構(gòu)方法尚屬空白，對此內(nèi)容研究將極大豐富隱私保護頻繁模式挖掘方法;（3）能否將各種隨機化模型應(yīng)用到分類、聚類等

挖掘任務(wù)，并構(gòu)造與之適應(yīng)的特征重構(gòu)方法，也值得研究。

參考文獻（References）

[1] Kenthapadi K，Mironov I，Thakurta AG.Privacy-preserving data mining in industry[C].In：Proc.of the Web Conference 2019-Companion of the World Wide Web Conference （WWW '19），2019：1308-1310.

[2] Li YL，Miao，CL，Su L，et al.An efficient two-layer mechanism for privacy-preserving truth discovery[C].In：Proc.of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining （KDD '18）.ACM，New York，NY，USA，2018：1705-1714.

[3] Teo SG，Cao JN，Lee VCS.DAG：A general model for privacy-preserving data mining[J].IEEE Transactions on Knowledge and Data Engineering，2018，Article in Press.

[4] Bullek B，Garboski S，Darakhshan JM，et al.Towards understanding differential privacy：when do people trust randomized response technique？[C].In：Proc.of the 2017 CHI Conference on Human Factors in Computing Systems （CHI '17）.ACM，New York，NY，USA，2017：3833-3837.

[5] Aldà F and Simon HU.Randomized response schemes，privacy and usefulness[C].In：Proc.of the 2014 Workshop on Artificial Intelligent and Security Workshop （AISec '14）.ACM，New York，NY，USA，2014：15-26.

[6] Warner SL.Randomized response：A survey technique for eliminating evasive answer bias[J].The American Statistical Association，1965，60（309）：63-69.

[7] 陳光慧，韓兆洲.基于隨機化回答模型的最低工資敏感性問題研究[J].統(tǒng)計與信息論壇，2012，27（09）：3-7.

[8] 郭宇紅，童云海，唐世渭，等.帶學(xué)習(xí)的同步隱私保護頻繁模式挖掘[J].軟件學(xué)報，2011，22（08）：1749-1760.

[9] Sun CJ，F(xiàn)u Y，Zhou JL，et al.Personalized privacy-preserving frequent itemset mining using randomized response[J].The Scientific World Journal，2014.

[10] 許勝之.滿足差分隱私保護的頻繁模式挖掘關(guān)鍵技術(shù)研究[D].北京郵電大學(xué)，2016.

[11] 蔣辰，楊庚，白云璐，等.面向隱私保護的頻繁項集挖掘算法[J].信息網(wǎng)絡(luò)安全，2019（04）：73-81.

[12] 邢歡.基于隱私保護的關(guān)聯(lián)規(guī)則挖掘研究[D].南京郵電大學(xué)，2016.

[13] Rizvi SJ，Haritsa JR.Maintaining data privacy in association rule mining[C].In：Proc.of the 28th Int' l Conf.on Very Large Data Bases （VLDB '02）.Morgan Kaufmann，2002：682-698.

[14] Agrawal S，Krishnan V，Haritsa J.On addressing efficiency concerns in privacy preserving mining[C].In：Proc.of the 9th Int' l Conf.on Database Systems for Advanced Applications （DASFAA' 04）.LNCS 2973，Springer-Verlag，2004：113-124.

[15] Xia Y，Yang Y，Chi Y.Mining association rules with non-uniform privacy concerns[C].In：Proc.of the 9th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery（DMKD '04）.ACM Press，2004：27-34.

[16] Andruszkiewicz P.Optimization for mask scheme in privacy preserving data mining for association rules[C].In：Proc.of Int' l Conf.Rough Sets and Emerging Intelligent Systems Paradigms（RSEISP '07）.LNAI 4585，Springer-Verlag，2007：465-474.

[17] Huang ZL，Du WL，Teng ZX.Searching for better randomized response schemes for privacy-preserving data mining[C].In：Proc.of the 11th European Conference on Principles and Practice of Knowledge Discovery in Databases （PKDD '07）.LNCS 4702，Heidelberg：Springer-Verlag，2007：487-497.

作者簡介：

郭宇紅（1979-），女，博士，副教授.研究領(lǐng)域：數(shù)據(jù)挖掘，推薦系統(tǒng).

童云海（1971-），男，博士，教授.研究領(lǐng)域：數(shù)據(jù)挖掘，聯(lián)機分析處理.