[發明專利]一種面向差分隱私保護的頻繁項集挖掘方法

有效

• 申請號: 201811276452.7
• 申請日: 2018-10-30
• 公開（公告）號: CN109409128B
• 公開（公告）日: 2022-05-17
• 發明（設計）人: 楊庚;蔣辰;白云璐;徐亞紅
• 申請（專利權）人: 南京郵電大學
• 主分類號: G06F21/62
• 分類號: G06F21/62
• 代理公司: 南京縱橫知識產權代理有限公司 32224
• 代理人: 董建林;姚蘭蘭

1.一種面向差分隱私保護的頻繁項集挖掘方法，其特征在于，包括以下步驟：

步驟1：基于預設的數據集D＝{T₁,T₂…T_m}，項集域A＝{i₁,i₂…i_n}，使用Apriori算法計算出所有項集的支持度，從中挑選出頻繁項集；

步驟2：統計數據集中各條事務的長度并計算截斷長度L，根據所述截斷長度L截斷數據集；

步驟3：計算頻繁項集包含項的個數上限m和頻繁項個數λ，根據λ值構造頻繁項組成的集合F；

步驟4：構造最大頻繁項集MFI集合B及候選項集集合C；

步驟5：使用最大頻繁項集集合B對候選項集集合C中的項集進行加噪；

步驟6：使用初始最大頻繁項集集合B計算得到各個候選項集的支持度，計算與真實支持度的誤差之和E；遍歷集合B，尋找B_i、B_j∈B，B_i、B_j是B中的兩個最大頻繁項集；合并B_i、B_j后的集合為B′，若使用B′對候選項集進行加噪產生的誤差和小于E，則用B′取代B并且更新誤差之和E的值；當誤差之和E不再減小時停止迭代并輸出結果；

步驟2中，所述截斷長度L的統計向量{z₁,z₂…z_n}，z_i為數據集中長度為i的事務的個數，i＝1,……,n，對向量添加噪聲

其中，所述噪聲函數為雙邊幾何分布，ε為隱私預算；雙邊幾何分布概率密度函數如下：

將所述截斷長度L設置為滿足式(3)的值

2.根據權利要求1所述的面向差分隱私保護的頻繁項集挖掘方法，其特征在于，步驟2中，根據所述截斷長度L截斷數據集具體方法如下：

遍歷數據集D，對任意事務T_i∈D，|T_i|表示T_i包含項的個數，若|T_i|＞L，則只保留T_i中支持度前L大的項，剔除其余的項；若|T_i|≤L，則不對T_i進行變動。

3.根據權利要求2所述的面向差分隱私保護的頻繁項集挖掘方法，其特征在于，步驟3中，計算向量y_i(D)表示長度為i的項集中支持度最大的取值，τ表示第k頻繁項集的支持度，使用打分函數為-|y_i(D)-τ|的指數機制從中挑選出m的值；表示向下取整；

計算向量{x₁(D),x₂(D)…x_n(D)}，x_i(D)表示第i頻繁項的支持度，使用打分函數為-|x_i(D)-τ|的指數機制從[1,2...n]中挑選出λ的值；

所有項按支持度由大到小排序，前λ個項組成集合F。

4.根據權利要求3所述的面向差分隱私保護的頻繁項集挖掘方法，其特征在于，所述指數機制描述如下：

設定輸出域為O，r表示從輸出域中所選擇的輸出項，定義一個打分函數u(D,r)，用來衡量輸出結果為r時的準確度，則算法K輸出為r的概率表示如下：

其中，Δu表示打分函數的敏感度，r_i表示輸出域O中的一個輸出項。

5.根據權利要求1所述的面向差分隱私保護的頻繁項集挖掘方法，其特征在于，步驟4具體步驟如下：

初始化所述最大頻繁項集MFI集合B和候選項集集合C為空集，再定義一個空集S；

先將F中的所有項添加到集合C中，接著以深度遍歷的方式從F中挑選項，并將挑選出的項添加到集合S中構成新集合S‘；若S‘仍然是頻繁的，繼續從F中挑選項；若不是，將S添加到MFI集合B中，并將S的子集添加到集合C中，回溯到上一個結點。