[發明專利]數據流關鍵模式挖掘的差分隱私保護方法

有效

• 申請號: 201711230632.7
• 申請日: 2017-11-29
• 公開（公告）號: CN107992769B
• 公開（公告）日: 2021-08-03
• 發明（設計）人: 王金艷;劉陳;傅星珵;李先賢
• 申請（專利權）人: 廣西師范大學
• 主分類號: G06F21/62
• 分類號: G06F21/62;G06F16/901;G06F16/903
• 代理公司: 桂林市持衡專利商標事務所有限公司 45107
• 代理人: 陳躍琳

1.數據流關鍵模式挖掘的差分隱私保護方法，其特征是，具體包括步驟如下：

步驟1.1、將窗口置于事務流的起始位置，獲得事務流的第一個窗口；

步驟1.2、將第一個窗口內的事務及第一個窗口之前的事務依次插入到樹中，得到原始樹T₁，并根據該原始樹T₁得到相應的項計數列表L₁；

步驟1.3、對項計數列表L₁中的項按照其計數使用確定順序和下降順序來進行調整，得到調整后的項計數列表L₁’；

步驟1.4、按照項計數列表L₁’去調整原始樹T₁，得到前綴樹T₁’；

步驟1.5、根據前綴樹T₁’根結點的孩子結點的個數，將前綴樹T₁’劃分為相應個數的子樹；

步驟1.6、對于每個子樹，遍歷該子樹的所有結點并對其計數添加第一層噪音，并從中選出噪音計數大于它所有孩子結點的計數的結點，再對這些結點的計數添加第二層噪聲，得到這些結點的噪聲計數；

步驟1.7、將噪聲計數疊加到項計數列表L₁’中，并對其中的項按照其計數使用確定順序和下降順序來進行調整，得到添加噪聲的項計數列表L₁”；

步驟1.8、根據項計數列表L₁”去調整前綴樹T₁’，得到滿足差分隱私的前綴樹T₁”；

步驟1.9、使用條件模式基和集合枚舉樹挖掘前綴樹T₁”，得到噪聲關鍵模式結果集O₁，并發布；

步驟2.1、將窗口向后移動一個窗格，獲得事務流的第q個窗口；將事務流的第q個窗口作為當前窗口，將事務流的第q-1個窗口作為前一窗口；將與第q個窗口最近的，并挖掘出了噪音關鍵模式結果集的窗口視為加噪窗口t，該加噪窗口t所挖掘出的噪音關鍵模式結果集O_t；

步驟2.2、把當前窗口之前的事務從前一窗口的前綴樹T_q-1”中去掉，并將當前窗口內的新加入的事務按照前一窗口的項計數列表L_q-1”的順序插入到前一窗口的前綴樹T_q-1”中，得到當前窗口的前綴樹T_q；根據當前窗口的前綴樹T_q得到當前窗口的項計數列表L_q；

步驟2.3、對當前窗口的項計數列表L_q中的項按照其計數使用確定順序和下降順序來進行調整，得到調整后的當前窗口的項計數列表L_q’；

步驟2.4、按照當前窗口的項計數列表L_q’去調整當前窗口的前綴樹T_q，得到再次調整后當前窗口的前綴樹T_q’；

步驟2.5、根據當前窗口的前綴樹T_q’根結點的孩子結點的個數，將當前窗口的前綴樹T_q’劃分為相應個數的子樹；

步驟2.6、對于每個子樹，遍歷該子樹的所有結點并對其計數添加第一層噪音，并從中選出噪音計數大于它所有孩子結點的計數的結點，再對這些結點的計數添加第二層噪聲，得到這些結點的噪聲計數；

步驟2.7、將噪聲計數疊加到當前窗口的項計數列表L_q’中，并對其中的項按照其計數使用確定順序和下降順序來進行調整，得到添加噪聲的當前窗口的項計數列表L_q”；

步驟2.8、根據當前窗口的項計數列表L_q”去調整當前窗口的前綴樹T_q’，得到滿足差分隱私的當前窗口的前綴樹T_q”；

步驟2.9、根據當前窗口的項計數列表L_q’去計算當前窗口的第一差異點dis1_q；并將當前窗口的第一差異點dis1_q與設定的第一差異閾值β1比較；dis1_q≤β1，則轉至步驟2.10；如果dis1_q＞β1，則轉至步驟2.12；

步驟2.10、使用條件模式基和集合枚舉樹挖掘當前窗口的前綴樹T_q’，得到準確的當前窗口的關鍵模式結果集X_q；

步驟2.11、根據當前窗口的關鍵模式結果集X_q和之前最近加噪窗口t所挖掘的噪音關鍵模式結果集O_t去計算當前窗口的第二差異點dis2_q；并將當前窗口的第二差異點dis2_q與設定的第二差異閾值β2比較；如果dis2_q≤β2，則將噪音關鍵模式結果集O_t發布；dis2_q＞β2，則轉至步驟2.12；

步驟2.12、使用條件模式基和集合枚舉樹挖掘當前窗口的前綴樹T_q”，得到當前窗口的噪聲關鍵模式結果集O_q，并發布；

上述q＝2，3，…，并且t≤q-1。