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

郭宇紅 童云海

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

關鍵詞：隨機化回答;隱私保護;頻繁項集;敏感問題調查

中圖分類號：TP311 ? ? 文獻標識碼：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）

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

2 ? 相關工作（Related work）

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

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

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

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

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

不同于單參數隨機化，多參數隨機化用多個概率參數對數據進行隨機化。其思想是對數據中的不同元素設置不同的隱私保護級別，不同的隱私保護級別對應不同的隨機化參數，由參與調查的個體自行決定對其不同數據元素的隱私保護級別和相應的隨機化參數。根據不同屬性取值、不同屬性和不同個體可以有以下幾種多參數隨機化模型。為簡單起見，假設參與調查的個體總數為N，每個個體對應m個需要保護的屬性，屬性取值均為布爾值“1”“0”，由這N個個體的m個布爾屬性組成需要保護的、二維布爾矩陣表示的數據表D。（事實上，數值類型屬性可以通過離散化轉變為多元分類屬性，即枚舉屬性，而多元分類屬性又可以轉變為布爾屬性，即一般的數據都可以轉變為二維布爾矩陣形式）

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

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

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

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

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

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

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

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

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

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

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

3.4 ? 復合多參隨機化模型

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

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

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

3.5 ? 分組多參隨機化模型

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

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

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

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

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

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

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

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

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

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

4 ? 結論（Conclusion）

本文針對頻繁項集挖掘中的隱私保護問題，其主要貢獻在于：（1）拓展和豐富了已有的三種簡單、粗粒度隨機化模型（P、P2、Pm模型），提出了三大類細粒度隨機化模型，共11種，具體包括：一種行多參隨機化模型（PN），四種復合多參隨機化（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模型的支持度重構方法，是否能推導出該方法所對應的支持計數重構公式和支持度重構偏差公式，是否能設計相應算法實驗驗證方法的有效性需要進一步研究;（2）這11種細粒度隨機化模型的支持度重構方法尚屬空白，對此內容研究將極大豐富隱私保護頻繁模式挖掘方法;（3）能否將各種隨機化模型應用到分類、聚類等

挖掘任務，并構造與之適應的特征重構方法，也值得研究。

參考文獻（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].統計與信息論壇，2012，27（09）：3-7.

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

[9] Sun CJ，Fu Y，Zhou JL，et al.Personalized privacy-preserving frequent itemset mining using randomized response[J].The Scientific World Journal，2014.

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

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

[12] 邢歡.基于隱私保護的關聯規則挖掘研究[D].南京郵電大學，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-），女，博士，副教授.研究領域：數據挖掘，推薦系統.

童云海（1971-），男，博士，教授.研究領域：數據挖掘，聯機分析處理.