基于簇和閾值區間的高效關聯規則隱藏算法

牛新征 王崇屹 葉志佳 佘 堃

1(電子科技大學計算機科學與工程學院 成都 611731) 2(電子科技大學信息與軟件工程學院 成都 610054)

基于簇和閾值區間的高效關聯規則隱藏算法

牛新征1王崇屹1葉志佳1佘 堃2

1(電子科技大學計算機科學與工程學院 成都 611731)2(電子科技大學信息與軟件工程學院 成都 610054)

(xinzhengniu@uestc.edu.cn)

關聯規則隱藏是隱私保護數據挖掘(privacy-preserving data mining, PPDM)的一種重要方法.針對當前的關聯規則隱藏算法直接操作事務數據、I/O開銷較大的缺陷，提出一種基于FP-tree快速關聯規則隱藏的算法FP-DSRRC.算法首先對FP-tree的結構進行改進，增設事務編號索引并建立雙向遍歷結構，進而利用改進的FP-tree對事務信息進行快速處理，避免了遍歷原始數據集產生的大量I/O時間；然后通過建立和維護事務索引表實現對敏感項的快速查找，并基于分簇策略對關聯規則處理，以簇為單位進行敏感規則消除，同時采用規則支持度和置信度閾值區間的思想，減少了關聯規則隱藏處理對原始數據集的影響；最后通過實驗測試證明:相較于傳統關聯規則隱藏算法，FP-DSRRC算法在保證生成的數據集質量的同時，減少了50%～70%的算法執行時間，并在大規模真實數據集上有較好的可用性.

隱私保護；關聯規則隱藏；頻繁模式樹； 敏感規則； 數據清洗

隨著關聯規則技術的逐漸成熟以及大數據云計算的不斷發展，通過關聯規則能挖掘出的信息越來越多，其中可能包含了用戶的敏感數據和隱私信息[1].因此，Agrawal等人[2]在2000年提出的隱私保護數據挖掘(privacy-preserving data mining, PPDM)成為數據挖掘領域的研究重點，而關聯規則隱藏作為解決數據挖掘中隱私問題的一項關鍵技術也引起了國內外學者的重視.

關聯規則挖掘最初由Agrawal[3]在1993年提出，其目的是為了挖掘事務數據庫中各項集存在的價值關聯，為相關決策提供依據.對于一些包含敏感關聯規則的數據，在發布數據前修改原始數據集，從而達到隱藏敏感規則的目的，這個過程就是關聯規則隱藏.

1 相關工作

當前關聯規則隱藏技術大致可分為6種[4]：基于啟發式的方法(heuristic approach)、基于邊界的方法(border approach)、基于重構的方法(reconstruction approach)、基于加密的方法(cryptographic approach)、精確方法(exact approach)和基于混合的方法(hybrid techniques approach).

啟發式方法主要采用數據失真技術和數據阻塞技術，通過向原始事務數據庫中添加噪聲數據或將原敏感項集的某些屬性刪除，以達到降低敏感規則支持度或置信度的目的.在基于啟發式的關聯規則隱藏算法中，文獻[5]提出基于頻繁項集相交點陣(intersection lattice)的關聯規則隱藏算法(heuristic for confidence and support reduction based on intersection lattice, HCSRIL)，算法首先確定對原始數據庫影響最小的敏感規則，并求解最小的待修改事務數，在消除敏感規則的同時保留頻繁項集，通過以上步驟盡量降低修改敏感規則對原始數據庫產生的影響；文獻[6]提出一種基于數據失真技術的關聯規則隱藏算法(cuckoo optimization algorithm for the sensitive association rules hiding, COA4ARH)，該算法分別構造了3個適應度函數用于優化隱藏方案的選擇，并利用遷移函數避免陷入局部最優.

在利用減少敏感規則右項支持度的啟發式算法中，文獻[7]提出了DSRRC(decrease support of R.H.S item of rule clusters)算法，算法首次利用分簇和劃分敏感度的思想進行關聯規則隱藏，盡可能地減少算法執行對原事務數據集產生的影響，但是DSRRC算法需要對數據集進行多次排序且不能消除有多個右項的關聯規則，為了解決這個問題，文獻[8]提出了2個新算法：ADSRRC(advanced DSRRC)算法和RRLR(remove and reinsert L.H.S. of rule)算法，克服了這些問題.ADSRRC也是基于相同右項對敏感規則分簇，通過計算事務數據的敏感度并將其降序排序，消除對算法執行結果的影響，而RRLR算法能處理具有多個右項的規則的能力；文獻[9]提出的MDSRRC(modified DSRRC)算法通過每次刪除敏感度最高的敏感項保證修改后的事務數據集的質量，啟發式算法通常需要向原始數據庫中添加噪聲或刪除某些屬性，當敏感規則較多時對原始數據改動較大，同時在基于數據阻塞的方法中，由于項集的某些屬性被刪除，后續可能無法計算其支持度和置信度.

基于邊界的方法以貪心方式選擇對邊界影響最小的數據清洗策略，文獻[10]提出一種基于阻塞的關聯規則隱藏算法(border rule based blocking algorithm, BRBA).該算法基于邊界規則篩選合適的事務數據進行清洗，通過安全邊界策略(safety margin)降低所有敏感規則的支持度或置信度，最小化敏感規則隱藏對其他非敏感規則的影響.

基于精確方法的思想是把數據清洗當成一種原子操作，這類算法可以使消除敏感規則后的數據庫沒有任何影響，但是需要多次選擇、比較，相比啟發式算法時間開銷巨大.文獻[11]提出的關聯規則隱藏算法無需修改頻繁項集支持度，而是提出一個代表規則(representative rule, RR)的概念.通過運用代表規則，算法無需訪問主數據庫就能推斷出敏感規則，其基本思路是改變數據項所在的位置，而不是將其從事務數據庫中刪除.這種策略的優點在于算法不會對頻繁項集的支持度和數據庫規模產生影響，然而該算法無法保證敏感規則的置信度小于閾值.文獻[12]將敏感規則消除問題抽象為多目標優化問題，并采用遺傳進化理論進行優化求解.該算法在快速隱藏敏感規則的同時，對原事務數據庫的修改幅度較小，然而該算法會對非敏感規則產生較大的丟失率，并且查找待刪除項的過程復雜度較高.

基于重構的方法首先執行數據失真處理，然后重構數據分布.文獻[13]提出一種基于重構的算法，首先通過頻繁項集挖掘算法找到所有頻繁項集及其對應的支持度，再將敏感規則從頻繁項集中刪除到支持度之下，然后利用這些不包含敏感規則的頻繁項集去構建一棵FP-tree[14]，這樣關聯規則隱藏的問題就轉化成了反向頻繁項集挖掘問題(inverse frequent set mining, IFM)[15]，最后通過反向頻繁項集挖掘算法生成不包含敏感規則的數據庫.

基于數據加密的方法通過對敏感數據進行加密編碼，文獻[16]提出結合RSA公鑰加密和偽隨機數生成器技術，對隱私數據進行加密保護.但是對于規模較大的數據集，該算法計算過程較復雜，實用性較差.

基于混合的方法采用多種技術的融合進數據保護.文獻[17]結合2種啟發式算法，分別從降低敏感規則的支持度和置信度入手，兼顧2種算法的優勢.但該算法僅僅是2種算法的簡單疊加，未能針對不同數據特點自適應選擇處理算法，并且該算法同樣具有啟發式算法對原始數據影響較大的缺陷.

通過對現有工作的分析可以看出，現有的關聯規則隱藏技術主要存在3個問題：

1) 現有的關聯規則隱藏技術往往直接對原事務數據集進行操作，當事務數據集規模較大時，對數據的遍歷處理會導致嚴重的I/O開銷，時間效率低下.

2) 現有的算法僅僅著眼于最大限度消除敏感規則，但缺乏對非敏感規則的保護，從而導致經過關聯規則消除的數據集規則丟失率和數據損失度較高.

3) 通過人為向原事務數據集中增添項集或規則來隱藏敏感規則的方案，將破壞非敏感規則從而導致錯誤的挖掘結果.總之，當前的關聯規則隱藏算法未能在敏感消除和數據質量之間做到很好的權衡.

關聯規則隱藏的前提條件是進行頻繁項集挖掘，找到所有關聯規則，但是現有算法都割裂了關聯規則隱藏和頻繁項集挖掘之間的聯系，多次遍歷和修改原始數據集導致了大量的I/O時間.針對傳統關聯規則隱藏算法效率較低以及對原始數據集影響較大的缺陷，本文提出一種FP-DSRRC(FP-tree DSRRC)算法，利用一棵改進的FP-tree，使得頻繁項集挖掘和關聯規則隱藏2個過程都在FP-tree上進行操作，并結合基于啟發式和基于邊界的關聯規則隱藏方法，使算法既快速又高效.

本文主要貢獻有3個方面：

1) 改進經典的FP-tree結構，添加事務索引表將算法對FP-tree的修改映射到數據集中.同時算法直接在FP-tree上操作避免了遍歷原始數據集產生的時間代價，通過FP-tree的頭表信息、節點間域信息可以快速確定敏感事務編號，減少了查找開銷.

2) 采用啟發式方法，通過將敏感規則分簇，使得單次敏感項的刪除影響到多個敏感規則，減少了對原數據集的修改.

3) 基于規則支持度和置信度閾值區間的思想，通過將敏感項按影響度大小排序，優先刪除對原數據集影響較小的項，保證了數據集質量的同時顯著提升算法效率.

2 問題描述

2.1 關聯規則挖掘

關聯規則挖掘的目的是從事務數據庫DB中找出支持度和置信度閾值區間內的強關聯規則[18].具體而言，支持度大于最小支持度閾值MST，并且置信度大于最小置信度閾值MCT的規則才被認為是強關聯規則.

設I={i1,i2,…,in}是全部項的集合，其中ik(k=1,2,…,n)為不同的項，令事務數據庫DB=(T1,T2,…,Tn)，則Ti稱為1條事務，其是由若干個項組成的項集.

定義1. 支持度.是項集X支持的事務T在事務數據庫DB中出現的百分率，即：

(1)

定義2. 關聯規則.是指形如X→Y的蘊含式，X和Y分別是關聯規則的先導(left-hand-side, L.H.S.)和后繼(right-hand-side, R.H.S.)，也叫左項集和右項集，且X∩Y≠?.關聯規則X→Y的支持度為項集X∪Y在DB出現的百分率，即:

(2)

關聯規則X→Y的置信度為項集X∪Y在項集X出現的百分率，即:

(3)

2.2 關聯規則隱藏

定義3. 敏感規則SR.是不符合用戶安全策略的關聯規則集合，即需要隱藏的關聯規則.

定義4. 關聯規則隱藏.是指通過關聯規則隱藏算法將原始數據庫DB轉換成1個新的事務數據庫DB′，DB′中不包含給定的敏感規則SR.

關聯規則隱藏算法通常應該滿足3個條件：

1)DB′中不包含任何給定敏感規則SR；

2)DB′中應該包含所有DB原來的非敏感規則；

3)DB′中不包含任何人為產生的新規則.

尋找一種滿足關聯規則隱藏的全部條件的算法已經被證明是一種NP-hard問題.一般采用HF(hiding failure)，MS(missing cost)，AP(artificial patterns)這3個指標來衡量一個關聯規則隱藏算法和關聯規則算法對原數據集的影響.

1)HF表示敏感規則的隱藏失敗率：

(4)

HF越低表明關聯規則隱藏效果越好.

2)MC表示規則丟失率：

(5)

MC越低表明DB′的質量越高.

3)AP表示人為規則產生率：

(6)

AP越低表明DB′中人為產生的規則越少.

3 FP-DSRRC算法

FP-DSRRC算法的流程圖如圖1所示.算法首先將事務數據庫DB的信息壓縮到一棵改進的FP-tree上，并通過FP-Growth[14]算法挖掘出所有強關聯規則.將強關聯的敏感規則按敏感項分簇，以簇為單位消除所有敏感規則，當所有簇都消除完畢后，將FP-tree還原成一個不包含敏感規則的數據庫DB′.

Fig. 1 FP-DSRRC algorithm process圖1 FP-DSRRC算法流程

3.1 改進的FP-tree及其性質

相對于經典的FP-tree樹[14]，本文的FP-tree樹添加了1個事務索引表用于標識每一條事務的編號，用于關聯規則隱藏過程中事務的索引和新數據庫的重構.這樣通過FP-tree每個節點到根節點有唯一路徑.并且相對于經典的FP-tree是從節點到根單向遍歷的，本文的FP-tree建樹時保留了節點的Child域，使得該FP-tree是雙向可遍歷的.改進的FP-tree具體構成如下：

1) 由1個樹根Root及其頻繁項子樹、1個頻繁項頭表和1個事務索引表組成；

2) 頻繁項子樹的每一個項節點用Order，Count，Child，Parent，Sibling，Link六個域組成；

3) 頻繁項頭表由Count域和Link域構成；

4) 事務索引表中每個表項由Index域和Length域構成.

改進的FP-tree如圖2所示，構成的事務數據為ABC，A，B三條數據.

Fig. 2 Improved FP-tree圖2 改進的FP-tree

構建FP-tree先從原始數據集DB中讀取所有事務，按照頻繁項的支持度遞減排序并編號，生成1個項序轉換表；然后再次讀取DB，逐一將事務按照項序轉換表排序后插入FP-tree中，并更新事務索引表.通過FP-Growth[14]算法可以挖掘出所有頻繁項集并生成所有強關聯規則，建樹算法和挖掘頻繁項集算法可以參考文獻[19]，本文的建樹方式相對于文獻[19]保留了Child域和Sibling域，并添加了1個事務索引表.

為了直觀展示建樹的過程，給出1組精簡的數據集TestDB，設定MST=1/3，MCT=0.6.根據頻繁項集進行項序轉換，A,B,C,D,E的序號分別為3,0,1,2,4，其中序號表示項的支持度，序號越小，支持度越高.篩選后的事務項集表如表1所示：

Table 1 Test Data and the Index after Transforming表1 測試數據集TestDB以及項序轉換后的索引

建立FP-tree，為了保持圖的簡潔，未畫出Child域和Sibling域，FP-tree建立后如圖3所示.

Fig. 3 Construct FP-tree圖3 建立FP-tree

綜上所述，改進的FP-tree有3個性質：

性質1. 對于形如X→Y的規則，根據項序轉換表找出{X，Y}中項序最大的項a，通過對所有的節點a向上遍歷可知當前路徑是否支持該規則，然后根據事務索引表快速確定哪些事務支持該規則.

性質2. 由于FP-tree保留了Child和Sibling域，可雙向遍歷，FP-tree可以根據事務索引表取出某條事務，對該事務進行修改后插回FP-tree中，而不影響其他事務.

性質3. 通過遍歷事務索引表并統計每個節點到根節點的唯一路徑可以快速將FP-tree還原成事務數據庫.

采用FP-Growth算法對圖3中的FP-tree進行頻繁項集挖掘，可以得到表2的結果，表現形式為(頻繁項集：支持數).

Table 2 Frequents Itemsets of TestDB表2 TestDB的頻繁項集表

3.2 敏感規則消除

為了盡可能減少對原事務數據庫的修改，需要盡量減少敏感項的刪除，因此本算法的核心思想是通過FP-tree快速定位待刪除的事務，并盡量使單次刪除可以同時作用于多個敏感規則.算法用敏感度來確定刪除的順序，設敏感規則SR包含敏感項si1,si2,…,sin，多個敏感規則可劃分為簇SC={SR1,SR2,…,SRm}.則項敏感度isk定義為sik在敏感規則簇SC中出現的總次數：

(7)

其中,Num(i,k)表示敏感規則SRi中敏感項sik的數量.規則敏感度定義為規則中項敏感度之和：

(8)

類似地，簇敏感度定義為簇中規則的敏感度之和：

(9)

算法根據待隱藏的敏感規則的待刪除項分簇.形如X→Y的敏感規則，當有多個右項時，選擇具有最大項敏感度ismax的作為待刪除項；若敏感度相同，則待刪除項選取支持度最大的項.將具有相同待刪除項的規則歸為同一個簇，然后以簇為單位消除所有的敏感規則，最后重構1個新的事務數據庫DB′.

對于表1中的TestDB數據集，假設敏感規則為SR={E→C,A→B,A→BD}，則可以得到敏感項的敏感度為A：2，B：2，C：1，D：1，E：1，對于敏感規則A→BD，有2個后項B和D，選擇敏感度高的項即項B作為刪除項，因此敏感規則集可以分為2個簇，然后計算當前敏感度最高的簇中敏感規則的較小刪除數，并通過FP-tree快速確定支持敏感規則的事務索引.

以敏感規則A→B為例，將其支持度降低到MST之下需要刪除2個后項，將其置信度降低到MCT之下需要刪除1個后項，所以敏感規則A→B的最小刪除數為1.根據項序轉換表，項A的序號比B大，所以通過頻繁項頭表的項A出發，經過的每一個節點A同時向根節點查找，如果路徑經過節點B說明當前路徑支持該敏感規則，即通過該節點A的事務都支持敏感規則A→B，得到事務T1，T4，T8，T9支持A→B.具體過程如圖4所示.圖4中帶灰度的節點為路徑支持敏感規則的敏感節點，而帶灰度的事務索引為支持該敏感規則的敏感事務索引，敏感規則分簇后如表3所示：

Table 3 Divide Sensitive Rules into Clusters表3 敏感規則分簇

Fig. 4 Find transaction index which supports A→B圖4 查找支持A→B的事務索引

對表3中選擇敏感度最大的簇即Cluster1進行敏感規則隱藏，對敏感事務的支持規則數進行計數，得到T1：2，T8：2，T9：2，T4：1，選擇長度最小的事務T9進行刪除，刪除節點后的FP-tree如圖5所示，此時敏感規則A→B和A→BD的delete count都減1變成0，將A→B和A→BD從Cluster1刪除，此時Cluster1所有敏感規則已經隱藏完畢，重新挖掘FP-tree中的頻繁項，得到新的頻繁項集后則處理其他的簇.

Fig. 5 FP-tree after deleting node B圖5 刪除節點B后的FP-tree

3.3 FP-DSRRC算法描述

FP-DSRRC算法的偽代碼如算法1所示.

算法1. FP-DSRRC算法.

輸入：原事務數據庫DB、最小支持度閾值MST、最小置信度閾值MCT、敏感規則集SR；

輸出：消除敏感規則的事務數據庫DB′.

① 根據DB和MST建立FP-tree；

② 利用FP-Growth挖掘頻繁項集，根據MCT計算強關聯規則AR；

③ 根據定義5計算敏感度；

④ For eachsr∈SR

⑤ 根據定義6確定待刪除項；

⑥ 將SR根據待刪除項分簇得到Clusters；

⑦ End For

⑧ For eachc∈Clusters

⑨ 根據定義5計算簇敏感度；

⑩ End For

算法1中行①～③首先建立FP-tree，通過挖掘頻繁項集得出強關聯規則集合，進而計算其敏感度；隨后，行④～確定各敏感規則1的待刪除項，并根據待刪除項分簇，同時將簇進行降序排序；算法行～，對所有劃分出的簇按照簇敏感度進行關聯規則消除，并維護事務索引表；最后，行當所有敏感簇處理完畢后，根據事務索引表生成消除敏感規則的事務數據庫DB′.

4 實驗及結果分析

4.1 TestDB數據集

對于2.1節表1中給出的精簡數據集TestDB，利用FP-DSRRC算法處理后的結果如表4所示：

Table 4 New Dataset DB′ after Hiding Sensitive Rules表4 消除敏感規則后的DB′

由表1和表4中的數據，采用式(3)可分別求得敏感規則的置信度，則對于原始事務數據庫DB中，E→C為0.75，A→B為0.67，A→BD為0.67；而經過FP-DSRRC算法處理后生成的事務數據庫DB′中，E→C為0.50，A→B為0.50，A→BD為0.50，置信度均得以減少到MCT之下，消除了敏感規則的強關聯性.

4.2 真實數據集

為了驗證算法的高效性，實驗將FP-DSRRC，DSRRC[7]，ADSRRC[8]，MDSRRC[9]在真實數據集下進行測試對比.實驗環境在AMD A6-3420 1.5 GHz CPU和8 GB內存的計算機上，操作系統為Windows 10，開發語言Java.本實驗采用的數據集是數據挖掘中的2個經典數據集Chess和Mushroom[20].其中，Chess數據集包含74個項，共3 196條事務記錄，其平均長度為37，比較稠密；Mushroom數據集含有119個項，共8 124條記錄，其平均長度為23，比較稀疏，數據集信息如表5所示.Chess數據集的MST和MCT分別設置為90%和80%，Mushroom數據集的MST和MCT分別設置為30%和60%，隨機選擇一定數量的規則作為敏感規則，對比不同算法之間的HF，MC，AP運行時間Runtime指標.

Table 5 Details of Chess and Mushroom表5 Chess和Mushroom數據集信息

4種算法都采用刪除敏感項的方式來減小敏感規則的支持度或置信度，所以理論上敏感規則都可以被隱藏，在2個數據集上的實驗也證明了這4種算法的隱藏失敗率HF=0.

圖6展示了4種算法在Chess和Mushroom數據集上消除敏感規則后的規則丟失率MC.由于Chess數據集較稠密而Mushroom數據集較稀疏，Chess數據集中頻繁項的支持度也較大，所以當刪除部分敏感項后，4種算法在Chess數據集比Mushroom數據集有更低的規則丟失率.

Fig. 6 Missing cost圖6 規則丟失率

由于FP-DSRRC算法將敏感規則分簇后，按簇為單位消除敏感規則，每次選擇刪除的事務都盡可能支持多個敏感規則，從而使事務刪除過程對原始數據集修改較小.從圖6可以看出隨著敏感規則數的增加，所刪除的敏感項也越多，規則丟失率也隨之增加，但FP-DSRRC在較稠密和較稀疏的數據集上的規則丟失率都低于其他算法.

Fig. 7 Artificial patterns圖7 規則產生率

圖7展示了4種算法在Chess和Mushroom數據集上消除敏感規則后的人為規則產生率AF，4種算法均通過刪除敏感項改變敏感項的支持度和與其關聯的頻繁項集支持度，所以都不產生太多的人為規則.從圖7可以看出，隨著越多的敏感項被刪除，4種算法產生的人為規則都在增加，但總體都處于一個較低的水平.在AP這項指標上，FP-DSRRC算法與MDSRRC算法接近，優于DSRRC和ADSRRC算法.

Fig. 8 Runtime of hiding sensitive rules on Chess and Mushroom圖8 Chess和Mushoom數據集上消除敏感規則的運行時間

圖8展示了4種算法在Chess和Mushroom數據集上的運行時間Runtime，這也是FP-DSRRC算法相對于其他3種算法提升最顯著的指標，由于FP-DSRRC算法自始至終都通過維護一棵FP-tree而避免了對原事務數據庫的重復遍歷，并且在每次消除簇后直接利用FP-Growth重新挖掘關聯規則，減少了大量的I/O時間.當數據集較大時，FP-DSRRC算法的執行效率優勢就越明顯，因為數據集越大，遍歷數據集所需要的I/O時間就越多，而FP-DSRRC算法只需要通過FP-tree的節點信息就能快速確定事務的索引及敏感度.從圖8可以看出在2個數據集上FP-DSRRC的運行效率都高于其他3種算法，并且在更大的Mushroom數據集上優勢越明顯，而且隨著敏感規則數的增加，FP-DSRRC的優勢會越來越大.

4.3 大型數據集

為了驗證算法的可用性，實驗在2個較大的數據集Retail和BMS-Webview-2[20]上進行測試.Retail數據集由一個比利時零售超市匿名捐贈用于科研分析，數據集包含5 133個顧客對16 469種商品的88 163條購買記錄.由于人們購買那些必備商品、常用商品的頻率遠遠高于那些冷門商品，所以整個數據集呈現出稀疏、不均勻的特點.BMS-Webview-2數據集由是一個電子商務網站對點擊流量的統計，包含77 512條記錄，數據集的總項數較少，平均事務長度較短.Retail和BMS-Webview-2數據集的詳細信息如表6所示：

Table 6 Detail of Retail and BMS-Webview-2表6 Retail和BMS-Webview-2數據集挖掘結果

我們設置Retail數據集的MST=1%，MCT=20%；BMS-Webview-2數據集的MST=0.5%，MCT=10%，由于數據集較大，DSRRC算法、ADSRRC算法和MDSRRC算法需要頻繁對原事務數據庫進行I/O，時間上已經變的不可控，即這些算法已經不適用于這個大數據集，所以我們給出HCSRIL算法[5]、COA4ARH算法[6]和FP-DSRRC算法在2個數據集上的運行時間對比，實驗依舊隨機選取一定數量的強關聯規則作為敏感規則.

圖9展示了3種算法在2個數據集上的運行時間，隨著敏感規則數的增加，算法的執行時間也隨之增加.由于COA4ARH算法通過迭代選擇最優敏感項消除策略，且一般需要迭代10次以上才能獲得較好的效果，當數據集較大時單次迭代時間較長，故該算法運行時間最長；HCSRIL算法先評估所有敏感項對頻繁項集的影響，然后逐條消除敏感規則，而FP-DSRRC算法通過分簇方式可同時對多條敏感規則進行消除，故其執行時間比HCSRIL算法短.由于BMS-Webview-2數據集的密度較低，數據項也較少，所以3種算法在BMS-Webview-2數據集下的運行時間比Retail數據集要長.

Fig. 9 Runtime of hiding sensitive rules on Retail and BMS-Webview-2圖9 Retail和BMS-Webview-2數據集上消除敏感規則的運行時間

同時，我們通過Retail數據集和BMS-Webview-2數據集測試算法的內存開銷，實驗結果如圖10所示.BMS-Webview-2數據集由于事務平均長度較小，項的總個數也較少，所以在相同事務數量的時候，算法執行的內存消耗較在Retail數據集時低.隨著事務數量的增加，算法所需內存的增長率在不斷變小，這是因為算法很好地利用了FP-tree本質上是一棵前綴樹的性質，事務在插入FP-tree前進行了項序轉換并按序號排序，所以越頻繁的項總是在前面.隨著FP-tree節點的不斷增加，FP-tree會包含更多的頻繁的項序，這時有相同前綴的事務就可以只修改節點的計數值而不是耗費內存去創建1個新的節點.總體來說，FP-DSRRC算法在面對這些較大的數據集上仍然有較好的可用性.

Fig. 10 Memory consumption in Retail圖10 Retail數據集上的內存開銷

5 結束語

通過FP-tree，將關聯規則隱藏的2個步驟頻繁項集挖掘和消除關聯規則結合起來，提出了一種兼數據集質量和運行效率的算法FP-DSRRC，通過對敏感規則進行簇劃分，以簇為單位進行敏感規則隱藏，并通過計算敏感規則的最小刪除數和統計事務的敏感規則支持數保證了清理后數據集的質量，降低了關聯規則隱藏對原事務數據庫的影響，顯著提升了算法運行效率.

[1]Chong Zhihong, Ni Weiwei, Liu Tengteng, et al. A privacy-preserving data publishing algorithm for clustering application[J]. Journal of Computer Research and Development, 2010, 47(12): 2083-2089 (in Chinese)(崇志宏, 倪巍偉, 劉騰騰, 等. 一種面向聚類的隱私保護數據發布方法[J]. 計算機研究與發展, 2010, 47(12): 2083-2089)

[2] Agrawal R, Srikant R. Privacy-preserving data mining[C] //Proc of the 2000 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2000: 439-450

[3] Agrawal R. Mining association rules between sets of items in large databases[C] //Proc of the 1993 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 1993: 207-216

[4] Refaat M, Aboelseoud H, Shafee K, et al. Privacy preserving association rule hiding techniques: Current research challenges[J]. International Journal of Computer Applications, 2016, 136(6): 11-17

[5] Le H Q, Arch-Int S, Nguyen H X, et al. Association rule hiding in risk management for retail supply chain collaboration[J]. Computers in Industry, 2013, 64(7): 776-784

[6] Afshari M H, Dehkordi M N, Akbari M. Association rule hiding using cuckoo optimization algorithm[J]. Expert Systems with Applications, 2016, 64: 340-351

[7] Modi C N, Rao U P, Patel D R. Maintaining privacy and data quality in privacy preserving association rule mining[C] //Proc of the 2nd Int Conf on Computing Communication and Networking Technologies. Piscataway, NJ: IEEE, 2010: 1-6

[8] Shah K, Thakkar A, Ganatra A. Association rule hiding by heuristic approach to reduce side effects & hide multiple RHS items[J]. International Journal of Computer Applications, 2012, 45(1): 1-7

[9] Domadiya N H, Rao U P. Hiding sensitive association rules to maintain privacy and data quality in database[C] //Proc of the 3rd Int Advance Computing Conf (IACC). Piscataway, NJ: IEEE, 2013: 1306-1310

[10] Peng Cheng, Ivan L, Li Li, et al. BRBA: A blocking-based association rule hiding method[C] //Proc of the 13th AAAI Conf on Artificial Intelligence (AAAI’16). Berlin: Springer, 2016: 4200-4201

[11] Jain D, Khatri P, Soni R, et al. Hiding sensitive association rules without altering the support of sensitive items[C] //Proc of the 2nd Int Conf on Computer Science and Information Technology. Berlin: Springer, 2012: 500-509

[12] Cheng Peng, Pan Jeng-Shyang, Lin Chunwei. Use EMO to protect sensitive knowledge in association rule mining by removing items[C] // Proc of the 2014 IEEE Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2014: 65-66

[13] Guo Yuhong. Reconstruction-based association rule hiding[C] //Proc of ACM SIGMOD 2007. Berlin: Springer, 2007: 51-56

[14] Han Jiawei, Pei Jian, Yin Yiwen. Mining frequent patterns without candidate generation[C] //Proc of the 2000 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2000: 1-12

[15] Ainen T M. On inverse frequent set mining[C] //Proc of Workshop on Privacy Preserving Data Mining. Piscataway, NJ: IEEE, 2003: 18-23

[16] Gui Qiong, Cheng Xiaohui, Rao Jianhui. Privacy preserva-tion association rules mining algorithm based on RSA[J]. Computer Engineering, 2009, 35(17): 138-140 (in Chinese)(桂瓊, 程小輝, 饒建輝. 基于RSA的隱私保護關聯規則挖掘算法[J]. 計算機工程, 2009, 35(17): 138-140)

[17] Domadiya N H, Rao U P. A hybrid technique for hiding sensitive association rules and maintaining database quality[C] //Proc of the 1st Int Conf on Information and Communication Technology for Intelligent Systems. Berlin: Springer, 2016: 359-367

[18] Shen Yan, Song Shunlin, Zhu Yuquan. Mining algorithm of association rules based on disk table resident FP-TREE[J]. Journal of Computer Research and Development, 2012, 49(6): 1313-1322 (in Chinese)(申彥, 宋順林, 朱玉全. 基于磁盤表存儲FP-TREE的關聯規則挖掘算法[J]. 計算機研究與發展, 2012, 49(6): 1313-1322)

[19] Niu Xinzheng, Yang Jian, She Kun. Algorithm of frequent itemsets mining based on array prefix-trees[J]. Journal of Chinese Computer Systems, 2014, 35(8): 1693-1698 (in Chinese)(牛新征, 楊健, 佘堃. 基于數組前綴樹的頻繁項集挖掘算法[J]. 小型微型計算機系統, 2014, 35(8): 1693-1698)

[20] Philippe F. SPMF: A Java open-source data mining library[DB/OL]. [2016-07-16]. http://www.philippe-fournier-viger.com/spmf/index.php?link=datasets.php

AnEfficientAssociationRuleHidingAlgorithmBasedonClusterandThresholdInterval

Niu Xinzheng1, Wang Chongyi1, Ye Zhijia1, and She Kun2

1(SchoolofComputerScienceandEngineering,UniversityofElectronicScienceandTechnologyofChina,Chengdu611731)2(SchoolofInformationandSoftwareEngineering,UniversityofElectronicScienceandTechnologyofChina,Chengdu610054)

Association rules hiding is a very important method of privacy-preserving data mining (PPDM). Because the current association rules hiding algorithm operates the transaction database directly, it leads to a lot of I/O overhead. To solve this problem, we put forward a quick association rules hiding algorithm based on FT-tree, called FP-DSRRC. Firstly, the algorithm improves the structure of FP-tree by adding an index to the transaction number and establishing the bidirectional traverse structure. Then FP-DSRRC uses the improved FP-tree to quickly handle transaction data set, avoiding a large number of I/O overhead caused by traversal the raw transaction data set. Furthermore, FP-DSRRC finds the sensitive items quickly by building and maintaining a transaction index table, and then handles the association rules based on the clustering strategy. We eliminate the sensitive rules by clusters, and reduce the negative influence caused by association rules hiding progress to the original data set by adopting the idea of rule support and confidence degree interval at the same time. Finally, the experiment shows that compared with traditional association rules hiding algorithm, the executive time of FP-DSRRC has been decreased by 50%～70% while guaranteeing the quality of general data, moreover, FP-DSRRC has better availability on a large-scale real data set.

privacy preservation; association rule hiding; FP-tree; sensitive rule; data sanitization

2016-08-16；

2017-01-06

國家自然科學基金項目(61300192)；國家科技支撐計劃基金項目(2013BAH33F02)；中央高?；究蒲袠I務費專項資金項目(ZYGX2014J052)；四川省科技支撐計劃基金項目(2015GZ0096)；成都市科學技術局軟科學研究項目(2015-RK00-00046-ZF)；四川省公安廳科研項目(2015SCYYCX06)；四川省自貢市公安局項目

This work was supported by the National Natural Science Foundation of China (61300192), the National Key Technology Research and Development Program of China (2013BAH33F02), the Fundamental Research Funds for the Central Universities (ZYGX2014J052), the Key Technology Research and Development Program of Sichuan Province (2015GZ0096), the Soft Science Research Project of Chengdu Science and Technology Bureau (2015-RK00-00046-ZF), Scientific Research Project of Sichuan Provincial Public Security Department (2015SCYYCX06), and the Project of Public Security Bureau of Zigong City, Sichuan Province.

TP301.6

NiuXinzheng, born in 1978. PhD, associate professor. Senior member of CCF. His main research interests include data mining and information security.

WangChongyi, born in 1995. Master candidate. His main research interests include social network and data mining.

YeZhijia, born in 1993. Master candidate. His main research interest include big data and social network.

SheKun, born in 1969. Professor and PhD supervisor of University of Electronic Science and Technology of China. His main research interests include information security and big data.