尹春勇，李 熒

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

0 引言

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

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

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

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

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

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

1 相關(guān)工作

1.1 高效用挖掘

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

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

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

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

1.2 隱私保護效用挖掘

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

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

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

2 預(yù)備知識

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

2.1 定義

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

表1 一個事務(wù)數(shù)據(jù)庫Tab.1 One transaction database

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

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

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

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

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

定義5在數(shù)據(jù)庫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事務(wù)Tj在數(shù)據(jù)庫D的效用是事務(wù)Tj中所有項im的效用之和，計算公式為：

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

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

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

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

2.2 問題陳述

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

定義10隱藏失?。℉iding Failure，HF）為脫敏后的數(shù)據(jù)庫中未能隱藏的SHUI，即脫敏過后仍出現(xiàn)在數(shù)據(jù)庫中的SHUI。定義為：

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

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

3 數(shù)據(jù)脫敏算法

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

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

3.1 構(gòu)建SI-table和BCU-Tree

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

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

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

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

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

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

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

除了構(gòu)建SI-table 以外，在掃描數(shù)據(jù)庫的同時，構(gòu)建了BCU-Tree，該樹的建立是基于位圖編碼，其相關(guān)定義如下。

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

表5 敏感事務(wù)表Tab.5 Sensitive transaction table

表6 敏感項計數(shù)表Tab.6 Counting table of sensitive items

定義15設(shè)L1是有序敏感項零向量，其中項集按對應(yīng)項的計數(shù)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 中，F(xiàn)1=｛A，B，C，D｝，L1=｛D，C，A，B｝，一個項集P=｛A，B，C｝可表示為P3=CAB，如圖2 所示。

圖2 L1向量Fig.2 L1 vector

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

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

定義18BCU-Tree 是一種樹，它的結(jié)構(gòu)類似于BMCtree［39］，樹結(jié)構(gòu)定義如下：1）它的根節(jié)點可以為?（表示沒有項），項前綴子樹作為根的子樹；2）項前綴子樹中的每個節(jié)點都持有一個項i(i∈L1)。如果這個節(jié)點的父節(jié)點代表一個項j，那么j?i（假設(shè)?i，i∈L1）。到達該節(jié)點的路徑部分由nodepath 表示；3）每個節(jié)點有5 個域：item-name、count、bitmap、children 和UI-list。item-name 表示一個項i(i∈L1)。count 表示包含項i的事務(wù)數(shù)。bitmap 保存L1（node-path）（定義15）。children 表示該節(jié)點的所有孩子節(jié)點。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 所示。

性質(zhì)1 BCU-tree 根節(jié)點的所有二進制位都是0。

性質(zhì)2 假設(shè)節(jié)點N有一個項i1，N.father是N的父節(jié)點。則節(jié)點N的二進制編碼計算如下：

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

圖3 BCU-TreeFig.3 BCU-Tree

圖4 字典表Fig.4 Dictionary table

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

算法2 創(chuàng)建BCU-Tree。

輸入 數(shù)據(jù)庫DB；

輸出 BCU-Tree（定義18）。

3.2 擾動BCU-Tree

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

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

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

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

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

算法3 擾動BCU-tree。

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

輸出 擾動后的BCU-Tree。

3.3 BCUTD算法

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

算法4 更新原始數(shù)據(jù)庫DB。

輸入 原始數(shù)據(jù)庫DB和BCU-Tree。

輸出 脫敏后DB。

4 實驗

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

表7 實驗數(shù)據(jù)集Tab.7 Experimental datasets

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

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

4.1 運行

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

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

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

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

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

4.2 副作用

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

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

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

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

本文將六種算法的Hiding Cost 在不同條件下進行對比，實驗結(jié)果如圖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 的副作用相對較小。隨著最小效用閾值的上升，所有算法的副作用都隨之下降，原因是當(dāng)數(shù)據(jù)集和敏感信息百分比相同時，隨著最小效用閾值的上升，需要隱藏的SHUI 數(shù)量變少，算法的計算復(fù)雜度降低，則隱藏成本也會減小。在圖10 中，與其他算法相比，BCUTD 在副作用方面仍然有更好的表現(xiàn)。當(dāng)數(shù)據(jù)集和最小效用閾值相同時，隨著敏感信息百分比的增加，所有算法的Hiding Cost 呈上升趨勢，這是因為需要隱藏的敏感信息越多，則算法產(chǎn)生的副作用也會增多?？偠灾?，本文提出的BCUTD 不僅運行時間更短，產(chǎn)生副作用也更小。

5 結(jié)語

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