基于BCU-Tree與字典的高效用挖掘快速脫敏算法

尹春勇，李 熒

（南京信息工程大學 計算機與軟件學院，南京 210044）

0 引言

數據挖掘［1］旨在從結構化或非結構化的數據中提取有用信息，并將其結構化以供人們使用。近年來，頻繁模式挖掘（Frequent Pattern Mining，FPM）［2］、關聯規則挖掘（Association Rule Mining，ARM）［3］、頻繁事件挖掘（Frequent Episode Mining，FEM）［4］和序列模式挖掘（Sequential Pattern Mining，SPM）［5］受到研究者們的廣泛關注。雖然這些技術被廣泛使用，但都忽略了項的效用［6-7］，例如：重要性、興趣、滿意度或風險等。一般來說，效用的隱含信息在生活中很常見。傳統的數據挖掘算法往往可能無法挖掘出對用戶真正重要的信息。因此，面向高效用模式挖掘（High-Utility Pattern Mining，HUPM）［8］的算法便由此出現。在HUPM 中，每個項的效用可以根據用戶的背景知識或者偏好進行預定義。

根據維基百科的介紹，在經濟學中，效用就是對某些商品（包括服務，即滿足人們需求的東西）偏好的度量，它代表消費者對商品的滿意程度。因此，效用是一種主觀衡量標準。在實踐中，效用的價值是由用戶根據他對特定領域知識的理解來分配的，這些知識由特定價值衡量，例如成本、利潤或審美價值。興趣度量可以分為客觀度量、主觀度量和語義度量［9-11］：客觀度量［11-12］僅基于數據本身，例如：模式挖掘中支持度或置信度；而主觀度量［13-14］考慮了用戶對該領域的認知，例如不了解、新穎；對于語義度量［8］考慮數據本身和用戶的期望，例如效用。因此，效用是對用戶偏好的定量表示，項集的有用性是根據其效用值來量化的。效用可以定義為衡量一個項集的有用（即有利可圖）程度［8，15］。

隱私保護效用挖掘（Privacy Preserving Utility Mining，PPUM）通過結合隱私保護數據挖掘（Privacy Preserving Data Mining，PPDM）和HUPM 來進行隱私保護。可以說PPUM 是PPDM 的一個子領域。隱私和效用是PPUM 中兩個相互對立的指標。隱私保護［16］通常使用的兩種方法是輸入隱私和輸出隱私。在效用挖掘前，輸入隱私會更改數據庫的內容（例如擾動［17-18］、k-匿名性［19］等）。在輸出隱私的情況下，數據庫的內容不會改變，而是讓數據僅供預期的人訪問（即安全多方計算［20］）。PPUM 使用了一些效用挖掘和隱私保護的技術，以最大限度地保留效用。

在已發表的絕大多數PPUM［21-26］研究中，隱藏敏感高效用項集（Sensitive High-Utility Itemset，SHUI）的主要思想是通過刪除某些事務或減少某些項的內部效用來擾亂原始數據庫。Yeh 等［21］首先提出了隱私保護效用挖掘策略，即優先隱藏高效用項（Hiding High Utility Item First，HHUIF）和最大敏感項集沖突優先（Maximum Sensitive Itemsets Conflict First，MSICF）算法。這兩種算法在每次迭代中都根據自己的標準修改包含敏感項集的數據庫事務，以將SHUI 的效用值降低到閾值以下。然而，這兩種算法在大數據集中，運行時間較長。因此，為了加快運行速度，Lin 等［22］提出了最大敏感效用-最大項效用（Maximum Sensitive Utility-MAximum item Utility，MSU-MAU）和最大敏感效用-最小項效用（Maximum Sensitive Utility-Minimum Item Utility，MSU-MIU）算法。該算法采用了投影機制來加速原始數據庫脫敏過程，旨在使用最大和最小效用的概念有效刪除SHUI 或減少其項的內部效用。Yun 等［23］提出了一種基于樹結構的快速擾動算法，即使用樹與表結構的快速擾動（Fast Perturbation Using Tree and

Table structures，FPUTT）算法，使用兩個表的遍歷來減小PPUM 的搜索空間。然而，盡管這些算法可以隱藏SHUI，但它們的運行時間都很長。因此本文提出了基于BCU-Tree 與字典（BCU-Tree and Dictionary，BCUTD）的高效用挖掘快速脫敏算法來解決在隱私保護效用挖掘中運行時間長、搜索空間大和副作用大等問題。

本文的主要貢獻有4 點：1）設計了一種新的樹結構BCUTree，這種樹結構采用了一種新穎的編碼模型。該編碼模型采用按位運算符來提取新的節點，與傳統的FPUTT-tree［23］相比，該樹的構建與空間搜索速度更快。2）BCU-Tree 采用了“集合枚舉樹”來生成敏感頻繁項，并儲存了每個項的效用值來減少效用計算次數，每個項的效用值只需一次更新，無需重復計算。3）該算法采用類似于字典的方式來保存敏感項集所在的所有事務TID，與FPUTT-tree 相比，能夠盡可能快地在BCU-Tree 中找到某個敏感項所在的所有事務TID，而無需對整個BCU-Tree 進行遍歷。4）將本文算法與HHUIF、MSICF、MSU-MIU、MSU-MAU、FPUTT 算法進行了廣泛、全面的實驗分析與對比，其中包括隱私保護性能、各種真實數據集的可擴展性和時間復雜度理論分析。

1 相關工作

1.1 高效用挖掘

近年來，高效用挖掘一直是數據挖掘領域中的一個研究重點。在過去的幾十年中，研究者提出了大量針對各種類型數據的高效用挖掘算法，包括交易數據、順序數據、情節數據和流數據。根據效用挖掘的原理和數據結構的不同，挖掘算法大致可以分為基于Apriori 方法、基于樹的方法、基于垂直或水平數據的方法和基于投影的方法。

在基于Apriori 方法中，Shen 等［27］提出了面向目標的基于效用關聯（Objective-Oriented utility-based Association，OOA）挖掘算法，該算法提出了一種基于效用約束的新剪枝策略，提高了OOA 挖掘效率；Yao 等［15］在算法中根據效用約束的幾個數學特性來尋找高效用項集（High-Utility Itemset，HUI）。總之，早期的所有效用挖掘算法都改進了Apriori 方法。它們的一個共同缺點是都需要生產大量候選項，因此這些改進方法面臨計算成本高和內存消耗大等問題。

為了避免基于Apriori 的逐級搜索的缺點，學者們提出了基于樹的方法。基于樹的效用挖掘算法靈感來自傳統的基于樹的頻繁模式挖掘算法［2］。Hu 等［28］提出了一種用于識別高效用項組合的頻繁項集挖掘算法。首先，該算法識別高效用組合，然后通過高收益分區樹找到HUI，其目標是找到滿足特定條件并最大化預定義目標函數的數據段和項目/規則組合。Ahmed 等［29］提出了三種新的樹結構來有效執行增量和交互式高效用模式挖掘。樹中的每個節點代表一個項集，并由項集的名稱、事務加權利用率（Transaction-Weighted Utilization，TWU）值和支持計數組成。Wu 等［30］提出了兩種新的剪枝策略，能避免訪問搜索空間中非必要節點；此外，通過多線程來處理大數據集，從而減少算法運行時間。

為了獲得比基于樹的效用挖掘方法更高的效率，研究者提出了一些使用具有單階段的垂直或水平數據結構挖掘高效用項集的算法，例如高效用模式挖掘（High-Utility Pattern Miner，HUP-Miner）算法［31］和高效的高效用項集挖掘（EFficient High-utility Itemset Mining，EFIM）算法［32］。除此以外，Gan 等［33］為評估模式在事務數據庫中的效用，擴展了占用度量，該算法通過效用、占用率和頻率來考慮用戶偏好，能夠挖掘出高質量項集，并無候選集生成。Wu 等［34］基于Hadoop 框架開發了一種高模糊效用模式挖掘算法，該算法無論是在單機還是大規模環境中都有著杰出的表現。

1.2 隱私保護效用挖掘

效用挖掘的目的主要是挖掘不低于最小效用閾值的高效用項集，并發現用戶所感興趣的信息，但效用挖掘可能會泄露敏感數據。因此，在HUPM 中也存在隱私問題。在一些實際應用中，敏感的高效用模式（項集、序列、情節等）通常需要隱藏。因此，近年來PPUM 成為學者們研究的重點。

數據庫中某個項的效用定義為內部效用之和乘以其外部效用。一般來說，降低一個項的效用值有兩種方法：1）直接減少項的內部效用值；2）改變外部效用值來降低這個模式的價值。在真實的世界中，外部效用一般是固定的，不會發生變化，因此，減少項的內部效用更為合理。Yeh 等［21］提出了兩種新的算法HHUIF 和MSICF，除了隱藏敏感信息外，最大限度地減少了隱藏敏感項帶來的副作用。Yun 等［23］引入了一種新的樹結構來加快擾動過程，減小PPUM 的搜索空間。Lin 等［22］提出了MSU-MAU 和MSU-MIU 兩種算法來最小化在隱藏高效用敏感項集中帶來的副作用。Li 等［35］提出了一種基于整數線性規劃（Integer Linear Programming，ILP）的新算法來減少隱藏過程中產生的副作用，將隱藏高效用敏感項集過程描述為滿足約束條件的問題。Liu 等［24］在脫敏過程中，動態計算每個敏感項的沖突計數，從而選擇沖突計數最大的項進行脫敏。Liu 等［25］提出了三種啟發式隱私保護算法，即先選擇最大效用項、先選擇最小效用項和先選擇最小副作用項，該算法避免多次掃描數據庫，加快了脫敏過程。Jangra 等［26］提出了兩種敏感項的選擇方法，并通過最小化未命中成本來提高數據效用。

除了隱藏高效用項集，擴展這些算法以處理序列數據也是一項非常重要的任務。受基于項集的HHUIF 和MSICF 算法的啟發，Dinh 等［36］首先提出了隱藏高效用順序模式（Hiding High Utility Sequential Pattern，HHUSP）和最大順序模式沖突優先（Maximum Sequential Patterns Conflict First，MSPCF）算法來隱藏所有高效序列模式。為了克服HHUSP和MSPCF 的缺點，Quang 等［37］通過效用升序或者降序來減少執行時間和丟失成本，從而提高HHUSP 的性能。Le 等［38］提出了一種新穎結構隱藏效用鏈（Utility-Chain for Hiding，UCH）來加快脫敏過程，在運行時間、內存消耗和副作用方面有著杰出表現。

2 預備知識

為了更好地理解PPUM，本章介紹一些相關的預備知識，并簡要說明PPUM 問題。

2.1 定義

給定一個數據庫，表示為D=｛T1，T2，…，Tn｝，其中Tm(1 ≤m≤n) 表示一個事務。每個事務都是由有限個項集I={i1，i2，…，im}組成。例如表1 所示，I={A，B，C，D，E}，由項組成的集合叫作項集。r-項集表示包含r個項，如I={C，E}，叫作2-項集。

表1 一個事務數據庫Tab.1 One transaction database

定義1項的內部效用im(1 ≤m≤M)在事務Tn中，用q(im，Tn)表示，含義為Tn中im的數量，例如在表1 中，項C 的內部效用在T2中為2，即q（C，T2）=2。

定義2項的外部效用im用p（im）表示，例如項的重要性、利潤、網頁鏈接點擊次數。表2 給出了一個外部效用的例子，其中項C 的外部效用為1，即p（C）=1。

表2 項外部效用表Tab.2 External utility table of items

定義3在事務Tn中，項im的效用表示為u（im，Tn），計算公式如下：

其中X?Tn，否則u(X，Tn)=0。例如T2中項集AC 的效用根據式（2）計算為u(AC，T2)=u(A，T2)+u(C，T2)=1×5+2 ×1=7。由于事務T3中不含項集AC，則u（AC，T3）=0。

定義5在數據庫D中，u（X）表示項集X的效用，計算公式為：

例如，項集AC 的效用在表1 中的效用為u(AC)=u(AC，T2)+u(AC，T5)+u(AC，T7)+u(AC，T8)=1×5+2 ×1+3×5+10×1+6×5+9×1+1×5+2×1=78。

定義6事務Tj在數據庫D的效用是事務Tj中所有項im的效用之和，計算公式為：

例如T2在數據庫D的效用為tu（T2）=1×5+2×1+2×2=11。

定義7TU表示D中所有事務效用tu（Ti）之和，即數據庫總效用，計算公式為：

定義8效用是用來評估項集的重要性或者價值，它是一種直觀的度量單位。最小效用閾值是用戶用來確定項目集是否有利用價值的標準。用δ來表示最小效用閾值，該閾值為常數，一般由用戶自己設置，即δ=c(0 ≤c≤TU)。

定義9高效用項集是指項集X的效用不小于最小效用閾值δ，即IH=｛X?I，u（X）≥δ｝，例如假定δ=44 時，u（AC）=78≥44，則AC 為高效用項集。

2.2 問題陳述

一個事務數據庫D，有一組集合H滿足最小效用閾值的HUI。定 義S=｛S1，S2，…，Sn｝是SHUI 的集合，則集合NS（=H-S）是一組非敏感HUI。PPUM 的目的是隱藏敏感項集S，使S中的每個Sm效用值都小于最小效用閾值δ。主要方法就是修改敏感項集Sm中項的數量值（內部效用）來降低Si的效用，但盡可能地保留NS，從而使隱私保護帶來的副作用降到最低。脫敏后的數據庫為D'，從D'中挖掘HUI，用H'表示。通常，PPUM 算法的流程為：1）對數據庫D應用效用挖掘算法，獲取所有的HUI；2）在數據發布前，確定所有的敏感項；3）使用隱私保護算法，來隱藏所有SHUI，并使算法的副作用最小化。PPUM 算法的性能指標用以下方式來衡量。

定義10隱藏失敗（Hiding Failure，HF）為脫敏后的數據庫中未能隱藏的SHUI，即脫敏過后仍出現在數據庫中的SHUI。定義為：

定義11丟失成本（Missing Cost，MC）為缺失的HUI，即不敏感但在脫敏后會隱藏的HUI。定義為：

定義12人工成本（Artificial Cost，AC）為在脫敏過程之前不是HUI，但在脫敏數據庫后成為HUI 的項集，這就是H'和H之間的區別。定義為：

3 數據脫敏算法

本文提出的BCUTD 算法的基本思想是保留數據表每行中的SHUI，并通過這些SHUI 建立SI-table，該表存儲了高效用敏感項集及該項集所在的所有事務TID。根據所有敏感項集中項出現的次數建立BCU-Tree，并存儲該項所在數據表中信息，包括TID、內部效用和外部效用。遍歷SI-table，選擇最大效用的項，通過字典表查找并更改該項對應BCU-Tree節點的相關信息，使該敏感項集效用低于用戶自定義閾值。只需一次遍歷BCU-Tree，修改原始數據庫中的數據表信息來達到數據庫脫敏效果。BCUTD 算法的整個流程如圖1所示。

圖1 BCUTD算法的整體流程Fig.1 Overall flow of BCUTD algorithm

3.1 構建SI-table和BCU-Tree

作為BCUTD 算法的初始步驟，構建高效用敏感項集表SI-table 和BCU-Tree 查找樹結構。數據持有者在共享數據時，第三方可以通過數據挖掘來發現有用信息，然而這些信息可能是敏感的，如果被不信任的第三方獲取，則可能造成一定的損失。因此SI-table 用來存儲由數據持有者指定的SHUI。為了減少在數據擾動過程中大量掃描數據庫，計算項的效用值，建立BCU-Tree 查找樹，并生成字典表指向該查找樹，來減少擾動的時間和CPU 計算次數。

SI-table 用來保存高效用敏感項集和所在的事務TID，相關定義如下：

定義13設原始數據庫D，SHUI 是用戶指定的高效用敏感項集。只需掃描數據庫D一次，便可創建SI-table，其中每個敏感項集si∈I，SI-table 定義如下：

SI-table 包括兩個字段：SI 和TIDs。例如，通過效用挖掘算法，得到表3 所示的高效用項集，指定其中的｛ACD｝、｛BD｝、｛CD｝為高效用敏感項集。

表3 高效用項集Tab.3 High-utility itemsets

通過一次遍歷表1 中的事務，建立如表4 所示的SItable。SI-table 用來構建BCU-Tree 及樹的擾動。通過SItable，可以減少掃描數據庫次數，無需像HHUIF 和MSICF［21］那樣，分別處理每個敏感高效用項集。創建SI-table 的算法如算法1 所示。

表4 敏感項集表Tab.4 SI-table

除了構建SI-table 以外，在掃描數據庫的同時，構建了BCU-Tree，該樹的建立是基于位圖編碼，其相關定義如下。

定義14設?關系為?i1，i2∈F1（敏感項集合），當且僅當num（i2）≥num（i1）時，i2?i1。其中num表示該項出現的次數。為了簡要說明，本文以表1 為例，去除其中的非敏感項，得到了表5 中數據。對表5 中每個敏感項出現的次數進行統計，得到了表6，因此敏感項｛A，B，C，D｝的?關系為D?C?A?B。

表5 敏感事務表Tab.5 Sensitive transaction table

表6 敏感項計數表Tab.6 Counting table of sensitive items

定義15設L1是有序敏感項零向量，其中項集按對應項的計數num（a）以非降序排序，其中a是一個項。在本研究中，L1表示為L1=[i0，i1，…，inf -1]，其中nf=| |F1（敏感項集合）且inf -1?… ?i1?i0。因此，一個k-項集P表示為Pk=ik…i2i1或Pk=ikPk -1，其中ik?…?i2?i1并且Pk -1=ik -1…i2i1。例如表6 中，F1=｛A，B，C，D｝，L1=｛D，C，A，B｝，一個項集P=｛A，B，C｝可表示為P3=CAB，如圖2 所示。

圖2 L1向量Fig.2 L1 vector

定義16設Pk=ikPk-1(2 ≤k)，則Pk'表 示Pk'=?ikPk-1，其中?ik表示不存在項ik。

定義17?i∈L1，index表示為i在L1中的索引，圖2 展示了表6 中每個項的索引。

定義18BCU-Tree 是一種樹，它的結構類似于BMCtree［39］，樹結構定義如下：1）它的根節點可以為?（表示沒有項），項前綴子樹作為根的子樹；2）項前綴子樹中的每個節點都持有一個項i(i∈L1)。如果這個節點的父節點代表一個項j，那么j?i（假設?i，i∈L1）。到達該節點的路徑部分由nodepath 表示；3）每個節點有5 個域：item-name、count、bitmap、children 和UI-list。item-name 表示一個項i(i∈L1)。count 表示包含項i的事務數。bitmap 保存L1（node-path）（定義15）。children 表示該節點的所有孩子節點。UI-list 由Tk、q（i，Tk）和u（i，Tk）組成。每個UI-list 按Tk升序排列，用符號表示為：｛（T1，q（i1，T1），u（i1，T1）），（T2，q（i2，T2），u（i2，T2）），…，（Tk，q(ik，Tk)，u（ik，Tk））｝，如圖2 所示。

性質1 BCU-tree 根節點的所有二進制位都是0。

性質2 假設節點N有一個項i1，N.father是N的父節點。則節點N的二進制編碼計算如下：

根據定義18 及性質1、性質2，本文構建了BCU-Tree，詳細描述見算法2。以表1 為例，其BUC-Tree 的構建結果如圖3。除此以外，在文獻［23］中，作者構建了FPUTT-tree 樹，BCU-Tree 與之相比，構建速度更快，作者使用Header Table來指向FPUTT-tree 節點，在擾動樹的過程中，需要多次遍歷樹，來尋找最大效用敏感項。而本文基于字典的思想，提出了字典表，在擾動的過程中，無需遍歷樹，只需要查找字典表，找到對應的敏感項，該敏感項指向BUC-Tree 中包含該項的所有節點。以圖3 為例，創建的字典表見圖4。

圖3 BCU-TreeFig.3 BCU-Tree

圖4 字典表Fig.4 Dictionary table

字典表由兩個域組成，即index（定義17）和bitmap 節點。每個bitmap 節點指向對應BCU-Tree 中的節點編碼。例如｛B｝在圖3 中的所有節點為1011 和1111。具體算法描述見算法2。

算法2 創建BCU-Tree。

輸入 數據庫DB；

輸出 BCU-Tree（定義18）。

3.2 擾動BCU-Tree

本節詳細描述擾動BCU-Tree 的過程。擾動的目的是通過減小SHUI 的內部效用，使它們的效用值低于δ。其中敏感項集按效用值進行降序排列，因為敏感項集的效用越高，它對其他項集的影響就越大。如果優先處理與其他敏感項集重疊的項目較多的某個敏感項集，則后續步驟可以更有效地執行，因為具有更大影響的敏感項集提前降低了稍后處理的敏感項集的效用。

在擾動過程中，無需遍歷BCU-Tree，只需要訪問字典表，查找到該樹中對應的所有節點。在之前的算法中，對數據庫采取多次掃描。除此以外，為了解決這個問題，文獻［23］中提出了FPUTT-tree 結構，來減少脫敏過程中對數據庫的多次掃描。然而，FPUTT-tree 存在一個缺陷，在擾動過程中，需要多次遍歷FPUTT-tree，來查找最大效用敏感項，這浪費了很多時間。除此以外，先前的工作需要多次重復計算節點效用值，為了解決這個缺陷，本文提出了新的算法，建立字典表，在擾動的過程中，無需再遍歷BCU-Tree，只需查找對應項，便可快速定位到所有節點。每個樹節點保存了u（i，Tk）效用值，所有敏感項效用只需計算一次，只有在脫敏的過程中，才需要修改一次效用值。

在算法3 中，首先，將SI-table 中的SI 按照效用進行降序排列（1）行）。遍歷每個敏感項集，計算需要減少的總效用（2）～4）行）。遍歷敏感項集的每個項，根據圖4 字典表選擇具有最大效用的項（5）～13）行）。如果最大項效用不大于要減小的效用，將該項的內部效用修改為0；否則根據公式（18）～19）行）計算需要修改的值。

例1 在表3 中，假設專家指定｛ACD｝、｛BD｝、｛CD｝為高效用敏感項集，其中u（ACD）=131，u（BD）=153，u（CD）=173。將這些敏感項集按效用進行降序排列。遍歷SI-table 的SI，使每個SI 效用值都小于閾值δ。本文設δ=102，則需要修改的總效用targetUtil=u(CD)-δ=173-102=71。根據字典表（圖4）選擇｛CD｝最大效用項，按順序遍歷｛CD｝，找到最大效用值，并保存在target中。首先訪問C，根據字典表，index=2，定位到0011 節點，根據節點UI-list 中的效用值，可以直接找到C 項的最大效用為（T5，10，10），并保存在target中。接著訪問｛CD｝中的D 項，根據字典表，index=3，定位到0001 節點，根據其UI?list中的效用值，更新target=D（T4，9，54）。根據算法3（14）～19）行）公式，因為54

圖6 擾動后的BCU-TreeFig.6 BCU-Tree after disturbance

算法3 擾動BCU-tree。

輸入 SI-table 和δ（定義8）；

輸出 擾動后的BCU-Tree。

3.3 BCUTD算法

本節首先介紹修改原始數據庫算法（算法4），然后介紹BCUTD 算法的整個流程。與之前相關工作相比，在擾動原始數據庫時，無需多次訪掃描數據庫，只需遞歸遍歷擾動后的BUC-Tree 一次，修改對應節點數據庫D 的內部效用值，如算法4 中的描述。在BCUTD 算法中，首先訪問原始數據庫，建立SI-table 及L1。然后根據3.1 節構建BCU-Tree 和字典表。接著遍歷SI-table 的敏感項，根據3.2 節的介紹，擾動BUC-Tree。最后根據算法4，遞歸遍歷擾動后的BUC-Tree，修改原始數據庫對應項的效用值。具體算法描述見算法5。

算法4 更新原始數據庫DB。

輸入 原始數據庫DB和BCU-Tree。

輸出 脫敏后DB。

4 實驗

為了評估BCUTD 算法的性能，本文在多個數據集上進行大量實驗。本實驗包含4 個數據集，數據集的特征如表7 所示，數據集可從一個開源數據挖掘框架庫（http：//www.philippe-fournier-viger.com/spmf/）獲得。密度（Density）表示數據集稀密程度，計算公式如下：

表7 實驗數據集Tab.7 Experimental datasets

其中：平均長度（AvgLen）表示事務平均長度；Itemcount表示項數量。

除了在不同數據集上進行實驗外，本文還與先前算法進行比較，例如：HHUIF 和MSICF［21］、MSU-MAU 和MSU-MIU［40］、FPUTT［23］。在接下來的實驗中，本文采用不同的閾值δ和敏感信息在高效用項集中的百分比來進行上述的對比實驗。本實驗中的敏感項集從HUI 中隨機選擇，挖掘HUI 算法使用的是ULB-Miner（Utility-List Buffer Miner）［41］。因為實驗用的數據集不包含內部效用和外部效用，因此，本實驗采用Ge 等［42］提出的均勻分布為事務中每個項分配內部效用值，并采用Tassa［43］提出的高斯分布生成與每個唯一項對應的外部效用。實驗在Intel core i7 CPU和16 GB內存的Windows 10環境下運行，所有算法采用Python 3.0編程語言實現。

4.1 運行

本節介紹了六種算法在不同的數據集、不同最小效用閾值和不同敏感信息百分比下的運行效果比較，如圖7、8所示。

圖7 不同最小效用閾值下的算法運行時間比較Fig.7 Comparison of algorithm running time under different minimum utility thresholds

在圖7 中可以看出，隨著最小效用閾值的增加，算法的運行時間基本呈下降趨勢。因為隨著最小效用閾值的增加，則挖掘出來的HUI數量將減少，隱藏相應百分比的SHUI數量將會減少，從而導致算法的運行時間下降。然而，在同一數據集中，當敏感信息百分比相同時，在不同的最小效用閾值下，數據集的SHUI 隨機選擇。由于不同閾值下的SHUI 隨機，每個敏感高效用項集中需要脫敏的項數越多，則算法耗費的時間越長。除此以外，不同的敏感高效用項集所在的事務也有區別。包含該敏感項集的事務數量越多，則算法需要脫敏的時間越長。相反地，如果隨機選擇的敏感項集項數越少，包含該敏感項集的事務數越少，則算法所耗費的時間越短。正是因為在同一數據集中，隨著閾值的改變，SHUI 的隨機選擇才導致了同一算法的運行時間會隨著閾值改變產生波動，但仍然不影響算法的整體趨勢。在接下來的實驗中，造成算法運行時間及隱藏成本趨勢波動的原理基本與此類似。例如圖7 中的t20i6d100k 數據集，算法HHUIF、MSICF、MSU-MAU 和MSU-MIU 在閾值分別為0.32、0.33、0.34 時，總體呈上升趨勢。產生該現象是因為隨機選擇的敏感項集中，需要脫敏項集的項數較多，包含該敏感項集的事務數較多，才導致了這些波動。但仍然不影響算法運行時間隨著效用閾值的增加而整體下降的趨勢。在數據集和最小效用閾值相同的情況下，本文提出的BCUTD 算法要明顯優于其他五種算法。與HHUIF、MSICF、MSU-MAU 和MSU-MIU 算法相比，本文算法運行速度提升了2～5 倍。與FPUTT 算法相比，本文算法運行速度提升了0.5～2 倍。在保護效用挖掘的隱私下，不僅要減少隱私保護算法帶來的副作用，更要考慮算法的運行時間。在數據集較大的情況下，算法的運行時間與較小的數據集相比，運行時間是它幾十倍甚至上百倍。如果因為減少副作用而消耗大量的時間，也是不可取的，由此可見，本文提出的BCUTD 算法的重要性。在圖8 中，隨著敏感信息百分比的增加，不同算法的運行時間總體呈上升趨勢。因為當數據集和最小效用閾值相同時，隨著敏感信息百分比的增加，SHUI 數量變多。則算法需要擾動的時間也就越長。在數據集和敏感百分比相同的情況下，BCUTD算法的表現要更為顯著。

圖8 不同敏感信息百分比下的算法運行時間比較Fig.8 Comparison of algorithm running time under different sensitive information percentages

無論是圖7 還是圖8，數據集的事務數越少，則算法的運行時間就越少，例如foodmart 和t25i10d10k 數據集。相較于其他兩個數據集而言，它們事務數只有幾千條，因此運行的時間也相對短一點。從表7 中的數據集密度可以看出，無論數據集密集或稀疏，BCUTD 算法都有良好的可擴展性，運行效果要明顯優于其他五種算法。

4.2 副作用

本節介紹了所有算法在副作用方面的實驗結果，討論的副作用包括隱藏失敗、丟失成本和人工成本（見3.2 節）。

受進化算法［44］的啟發，本文定義了一個具有多個閾值的函數Hiding Cost，來衡量隱私保護中產生副作用的程度。

定義19隱藏成本（Hiding Cost）定義如下：

其中：HF為隱藏失敗，MC為丟失成本，AC為人工成本（見3.2 節）；w1、w2、w3是由用戶定義的每個副作用的相對權重且w1+w2+w3=1。

本文將六種算法的Hiding Cost 在不同條件下進行對比，實驗結果如圖9 和圖10 所示。

圖9 不同最小效用閾值下的算法Hiding Cost比較Fig.9 Comparison of algorithm Hiding Cost under different minimum utility thresholds

圖10 不同敏感信息百分比下的算法Hiding Cost比較Fig.10 Comparison of algorithm Hiding Cost under different sensitive information percentages

從圖9 可以看出，在不同的最小效用閾值下，相較于其他算法，BCUTD 的副作用相對較小。隨著最小效用閾值的上升，所有算法的副作用都隨之下降，原因是當數據集和敏感信息百分比相同時，隨著最小效用閾值的上升，需要隱藏的SHUI 數量變少，算法的計算復雜度降低，則隱藏成本也會減小。在圖10 中，與其他算法相比，BCUTD 在副作用方面仍然有更好的表現。當數據集和最小效用閾值相同時，隨著敏感信息百分比的增加，所有算法的Hiding Cost 呈上升趨勢，這是因為需要隱藏的敏感信息越多，則算法產生的副作用也會增多。總而言之，本文提出的BCUTD 不僅運行時間更短，產生副作用也更小。

5 結語

近年來，高效用挖掘一直受到商業和工業的追捧。但隨著人們隱私意識的提高，高效用挖掘帶來潛在的隱私泄露問題引起了研究者們的關注。簡要來說，PPUM 就是隱藏敏感高效用項集，當商家共享數據時，其隱藏的敏感信息能不被第三方所挖掘。本文提出了隱私保護效用挖掘算法BCUTD，試圖在保護隱私的同時，提高算法的運行效率。本文采用了BCU-Tree 和字典表，來提高脫敏效率。通過大量實驗分析和對比，該算法在運行時間和隱私保護副作用上，都有著杰出的表現。在未來的研究中，減少隱私保護效用挖掘的執行時間和內存計算成本，依然是研究者們值得關注的問題。例如：設計新穎的修剪策略，減少搜索空間；開發保證最小副作用的快速近似算法，與啟發式算法相結合，求得近似解。