關(guān)聯(lián)規(guī)則隱藏算法綜述

包耕張玲樂(lè)

摘 要：近年來(lái)，數(shù)據(jù)挖掘備受青睞，它可以從大量數(shù)據(jù)集合中提取隱藏的知識(shí)。如何實(shí)現(xiàn)既找到數(shù)據(jù)中隱藏的知識(shí)，又不透露其中的敏感信息尤為關(guān)鍵。隱私保護(hù)數(shù)據(jù)挖掘（PPDM）能夠?qū)崿F(xiàn)對(duì)敏感信息的保護(hù)，關(guān)聯(lián)規(guī)則隱藏是PPDM技術(shù)中的一種，用來(lái)保護(hù)敏感性的關(guān)聯(lián)規(guī)則?？偨Y(jié)了關(guān)于隱私保護(hù)的數(shù)據(jù)挖掘方法并指出了其優(yōu)缺點(diǎn)，同時(shí)重點(diǎn)對(duì)關(guān)聯(lián)規(guī)則隱藏算法進(jìn)行了分析。

關(guān)鍵詞關(guān)鍵詞：數(shù)據(jù)挖掘；隱私保護(hù)；關(guān)聯(lián)規(guī)則隱藏

DOIDOI：10.11907/rjdk.162016

中圖分類(lèi)號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)文章編號(hào)：16727800（2016）011004602

0 引言

隱私保護(hù)數(shù)據(jù)挖掘在數(shù)據(jù)挖掘領(lǐng)域是一個(gè)富有成效的研究課題。PPDM的目的是通過(guò)各種方法轉(zhuǎn)換現(xiàn)有的數(shù)據(jù)集，甚至在挖掘的過(guò)程中，一些數(shù)據(jù)在某種程度上的機(jī)密性依然保持不變。在數(shù)據(jù)挖掘中，用戶給出數(shù)據(jù)并免費(fèi)使用他們自己的工具。因此，數(shù)據(jù)挖掘之前的隱私保護(hù)要應(yīng)用在用戶自己的數(shù)據(jù)上。鑒于此，需要開(kāi)發(fā)新的隱私保護(hù)控制系統(tǒng)，也即將這些數(shù)據(jù)集轉(zhuǎn)換成一個(gè)新的數(shù)據(jù)集來(lái)保護(hù)原始數(shù)據(jù)。提出關(guān)聯(lián)規(guī)則隱藏算法的目標(biāo)是為了保護(hù)一些特別的數(shù)據(jù)，使其在關(guān)聯(lián)規(guī)則隱藏算法的過(guò)程中不被發(fā)現(xiàn)。例如：政府想推出一些關(guān)于農(nóng)村地區(qū)發(fā)展的新計(jì)劃，農(nóng)村部門(mén)有關(guān)于農(nóng)民和勞動(dòng)的數(shù)據(jù)庫(kù)，他們想通過(guò)第三方分析這些數(shù)據(jù)，但是不能揭示農(nóng)村勞動(dòng)者的個(gè)人信息；又如：商店想要了解消費(fèi)者的購(gòu)物行為，該例中消費(fèi)者的數(shù)據(jù)不是很重要，但是從數(shù)據(jù)所分析出的結(jié)果需要得到保護(hù)。

數(shù)據(jù)挖掘是一種從海量信息中挖掘出有用信息的技術(shù)。在當(dāng)前社會(huì)，共享和發(fā)布信息已經(jīng)成為常見(jiàn)現(xiàn)象。然而，數(shù)據(jù)的搜集和分析會(huì)暴露個(gè)人隱私。目前，隱私保護(hù)數(shù)據(jù)挖掘已經(jīng)引起了廣泛關(guān)注，許多關(guān)于隱私保護(hù)的技術(shù)因此被提出。本文將討論不同的隱私保護(hù)技術(shù)及它們的優(yōu)缺點(diǎn)，并重點(diǎn)討論關(guān)聯(lián)規(guī)則挖掘算法。

數(shù)據(jù)挖掘可以在很短時(shí)間內(nèi)分析大量的信息，智能算法將一些敏感性和機(jī)密性的數(shù)據(jù)存儲(chǔ)在大量分支數(shù)據(jù)中。各種各樣的挖掘技術(shù)中也許包含很多關(guān)于個(gè)人和組織的敏感性信息。關(guān)聯(lián)規(guī)則挖掘就是從給出的數(shù)據(jù)中發(fā)現(xiàn)一些能夠滿足預(yù)先定義好的最低值和機(jī)密度的關(guān)聯(lián)規(guī)則。該問(wèn)題通常被分解為兩個(gè)子問(wèn)題：一是找出該項(xiàng)目中誰(shuí)的發(fā)生超出了預(yù)先定義的臨界值，這些被稱(chēng)為頻繁大項(xiàng)集；二是從這些大項(xiàng)集中產(chǎn)生關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則隱藏是指修改原始數(shù)據(jù)的過(guò)程，在該過(guò)程中，一些確定的敏感性關(guān)聯(lián)規(guī)則消失，但是并不影響數(shù)據(jù)和一些不敏感規(guī)則。

通過(guò)轉(zhuǎn)換將一些敏感性的數(shù)據(jù)隱藏起來(lái)的過(guò)程叫做數(shù)據(jù)清洗過(guò)程。為了進(jìn)行轉(zhuǎn)換，一個(gè)小數(shù)量的交易需要通過(guò)刪除一個(gè)或多個(gè)項(xiàng)目而發(fā)生改變，或者一些交易是通過(guò)將錯(cuò)的改為對(duì)的來(lái)添加噪聲數(shù)據(jù)集，發(fā)布的數(shù)據(jù)庫(kù)稱(chēng)為清潔數(shù)據(jù)庫(kù)。同時(shí)，該方法也稍微修改了一些數(shù)據(jù)，但是在實(shí)際應(yīng)用中非常容易被接受。

1 關(guān)聯(lián)規(guī)則隱藏算法相關(guān)技術(shù)

關(guān)聯(lián)規(guī)則隱藏算法阻止敏感性規(guī)則被公開(kāi)。其主要問(wèn)題歸納如下：給定一個(gè)事務(wù)數(shù)據(jù)庫(kù)X用最小機(jī)密度、最小支持度，以及一系列從數(shù)據(jù)庫(kù)X中挖掘出來(lái)的規(guī)則。一個(gè)R的子集RH為敏感性關(guān)聯(lián)規(guī)則，該子集不能被公開(kāi)。關(guān)聯(lián)關(guān)系隱藏的目的是將X轉(zhuǎn)換為X′，通過(guò)這些方法任何人將不會(huì)挖掘出屬于RH的規(guī)則，而且屬于R的不敏感規(guī)則也不會(huì)受到影響。

1.1 啟發(fā)式技術(shù)

啟發(fā)式技術(shù)解決如何確定合適的數(shù)據(jù)集對(duì)數(shù)據(jù)進(jìn)行轉(zhuǎn)換。啟發(fā)式技術(shù)的轉(zhuǎn)變方法既包括擾動(dòng)項(xiàng)，通過(guò)改變其屬性值完成（例如改變屬性值由1到0），還包括阻塞項(xiàng)，用“？”改變現(xiàn)存的屬性值。

1.1.1 基于擾動(dòng)的方法

基于數(shù)據(jù)擾動(dòng)提出對(duì)數(shù)據(jù)的啟發(fā)式修改，它將一個(gè)被選擇的屬性值由1改為0，因此敏感規(guī)則的支持度將會(huì)減少，發(fā)布數(shù)據(jù)的效應(yīng)將會(huì)達(dá)到最大。其關(guān)鍵的一步是借助于啟發(fā)式的思想如何將X變?yōu)閄，。

Agrawal and Srikant使用數(shù)據(jù)擾動(dòng)技術(shù)來(lái)改變數(shù)據(jù)，這樣可以根據(jù)原始數(shù)據(jù)的相似值獲得改變過(guò)的數(shù)據(jù)版本，同樣挖掘規(guī)則也相應(yīng)地改變?yōu)橄嗨频耐诰蛞?guī)則。這個(gè)重建的分布用來(lái)構(gòu)造一個(gè)新的模型。

本文提出了5種算法，所有這些算法都是基于擾動(dòng)技術(shù)，其中3種是隱藏一些關(guān)聯(lián)規(guī)則，剩下的兩種是隱藏大項(xiàng)集。這5種算法都用到了參數(shù)，具有有效性。由于首先要根據(jù)它們的種類(lèi)隱藏關(guān)聯(lián)規(guī)則，因而副作用也很明顯。

文獻(xiàn)[1]力求在隱私數(shù)據(jù)和公開(kāi)數(shù)據(jù)中達(dá)到平衡，即盡量減少關(guān)于消除事項(xiàng)的相互影響，并且盡量減少偶然和替代事項(xiàng)。其效應(yīng)是測(cè)量隱藏在修改過(guò)程中產(chǎn)生副作用的無(wú)敏感規(guī)則的數(shù)量。

1.1.2 基于阻塞的方法

通過(guò)用一個(gè)問(wèn)號(hào)或者一個(gè)真值替代一個(gè)確定的數(shù)據(jù)來(lái)減少敏感規(guī)則的支持度和置信度，該方法已經(jīng)在實(shí)施。最小的支持度和最小的置信度相應(yīng)地改變成一個(gè)最小的支持區(qū)間和最小的置信區(qū)間。如果一個(gè)敏感規(guī)則的支持度和/或者置信度在該區(qū)間，則并不違反數(shù)據(jù)的機(jī)密性。

Yucel Saygin使用一些分塊來(lái)擾動(dòng)關(guān)聯(lián)規(guī)則。當(dāng)一些原始數(shù)據(jù)的值被一些不知道的值替換之后，就難以界定敏感關(guān)聯(lián)規(guī)則的支持度和置信度。Yucel Saygin在其論文中通過(guò)一些例子，在關(guān)聯(lián)規(guī)則挖掘中使用不確定的符號(hào)，也即用支持區(qū)間和置信區(qū)間來(lái)代替支持度和置信度。

Xiao X[2]提出了一個(gè)新的個(gè)人匿名概念的概括性框架，該框架是為了確保普遍性來(lái)滿足每個(gè)人的要求。它提供了關(guān)于隱私保護(hù)不同大小的數(shù)據(jù)表的記錄。Liu Mingetal基于（I，k）匿名化模型提出了個(gè)人匿名模型。

1.2 基于重建的關(guān)鍵規(guī)則

最近提出的許多關(guān)于隱私保護(hù)的問(wèn)題是通過(guò)在一個(gè)總體水平上來(lái)擾動(dòng)數(shù)據(jù)和重建分支，也即該算法先用在擾動(dòng)數(shù)據(jù)上，然后用在重建分支上。重建方法和數(shù)據(jù)類(lèi)型不同，相應(yīng)的算法也不同。

Agrawal用貝葉斯定義的算法進(jìn)行分支重建。Agrawal對(duì)于重建關(guān)聯(lián)規(guī)則提出了一個(gè)統(tǒng)一的隨機(jī)選擇的算法。本文在貝葉斯的基礎(chǔ)上作了改進(jìn)，在（期望最大化）EM算法的幫助下進(jìn)行重建。

1.2.1 數(shù)據(jù)重建方法

另一個(gè)數(shù)據(jù)重組方法是將原始數(shù)據(jù)擱置一邊，開(kāi)始于消除所謂的“知識(shí)數(shù)據(jù)”。新的被公開(kāi)的數(shù)據(jù)由經(jīng)過(guò)消除的知識(shí)數(shù)據(jù)而重建。Chen首次提出了基于約束基礎(chǔ)的轉(zhuǎn)換項(xiàng)目，即Lattice Mining procedure （CIILM），用于隱藏經(jīng)常性的敏感項(xiàng)目，它們的數(shù)據(jù)重建是基于子項(xiàng)目集。另一個(gè)隱私保護(hù)方法是與逆頻繁項(xiàng)目集挖掘相關(guān)聯(lián)，也即從給出的頻繁數(shù)據(jù)中推出原始數(shù)據(jù)，這是由Mielikainen提出的。

1.2.2 FP樹(shù)方法

FP方法在文獻(xiàn)[3]中被提出，是基于重組技術(shù)的逆頻繁項(xiàng)目集挖掘。有3個(gè)步驟：①用頻繁項(xiàng)目挖掘算法產(chǎn)生從數(shù)據(jù)D形成的支持項(xiàng)；②將消除算法超過(guò)頻繁項(xiàng)目從FS中得到FS，；③從FS中獲得公開(kāi)數(shù)據(jù)D。

1.3 基于密碼基礎(chǔ)的技術(shù)

不同的組織希望交換它們的數(shù)據(jù)，但是不能暴露其敏感信息。因此，在交換信息時(shí)使用一些保密規(guī)則。

1.3.1 垂直分區(qū)的分布式數(shù)據(jù)

該算法是根據(jù)“安全和”的概念而提出，安全和是指節(jié)點(diǎn)之間的安全計(jì)算，每個(gè)分項(xiàng)目的支持度之和將要被計(jì)算。

文獻(xiàn)[4]討論了各種各樣的隱私保護(hù)的分解方法，包括安全和、安全聯(lián)合、交集的安全大小以及數(shù)積等。文獻(xiàn)[5]討論了如何使用分級(jí)點(diǎn)來(lái)計(jì)算頻繁項(xiàng)目，它使用線形的算法技術(shù)來(lái)計(jì)算兩個(gè)向量的分節(jié)點(diǎn)。

1.3.2 水平分區(qū)的分布式數(shù)據(jù)

衡量全局頻繁項(xiàng)集，確保不揭露網(wǎng)站信息，只找到在網(wǎng)站上支持度的安全值。支持度高過(guò)閾值就是全局頻繁項(xiàng)集。

Shaofei Wu提出了一種算法來(lái)保持隱私保護(hù)和知識(shí)挖掘之間的平衡。該解決方法在挖掘階段后使用了一個(gè)過(guò)濾器來(lái)隱藏一些被發(fā)現(xiàn)的規(guī)則。在使用該算法之前，要建立數(shù)據(jù)結(jié)構(gòu)和敏感規(guī)則的有效模型。

Chirag N. Modi提出相應(yīng)算法以阻止一些通過(guò)不安全的媒介來(lái)獲得隱私的方法。

1.4 精確方法

這些方法跟隨著隱藏進(jìn)程，作為一個(gè)約束滿意度問(wèn)題已經(jīng)被二進(jìn)制整數(shù)程序設(shè)計(jì)（BIP）解決。它們給出了很好的解決方法，但遭受了從高時(shí)間復(fù)雜度到CSP。

Gkoulalas and Verykios針對(duì)找到一個(gè)隱藏規(guī)則問(wèn)題的最佳解決方法提出了相應(yīng)建議。該隱藏問(wèn)題在盡量減少原始數(shù)據(jù)甚至是消除數(shù)據(jù)之間的距離。

文獻(xiàn)[6]基于邊界值的方法，提出了解決隱藏敏感頻率項(xiàng)集問(wèn)題的最佳方法。隱藏敏感頻率項(xiàng)是通過(guò)綜合擴(kuò)展原始數(shù)據(jù)集生成數(shù)據(jù)集。擴(kuò)展原始數(shù)據(jù)來(lái)隱藏?cái)?shù)據(jù)敏感項(xiàng)被證明是對(duì)于解決擴(kuò)展隱藏問(wèn)題的最佳解決方法。

2 關(guān)聯(lián)規(guī)則隱藏目的

2.1 隱藏目的

（1）如果預(yù)先定好了原始數(shù)據(jù)的支持度和置信度的閾值，則敏感性規(guī)則不能被挖掘出來(lái)，如果這些數(shù)據(jù)在同樣或更高的閾值內(nèi)被挖掘，那么它可以公布其轉(zhuǎn)換過(guò)的數(shù)據(jù)。這要求轉(zhuǎn)換過(guò)的數(shù)據(jù)不包含敏感性規(guī)則。

（2）在給定的支持度和置信度內(nèi)如果能挖掘到原始數(shù)據(jù)不敏感的規(guī)則，那么對(duì)于轉(zhuǎn)換過(guò)的數(shù)據(jù)在同樣支持度和置信度或者更高的值內(nèi)，也應(yīng)該被挖掘出。另一個(gè)要求是在轉(zhuǎn)換數(shù)據(jù)時(shí)不能丟失規(guī)則。

（3）不能有錯(cuò)誤的規(guī)則，錯(cuò)誤的規(guī)則指原始數(shù)據(jù)中不存在的規(guī)則。

2.2 挖據(jù)算法目標(biāo)

隱私保護(hù)挖掘算法應(yīng)該做到：①個(gè)人敏感信息需要被維護(hù)；②對(duì)于不敏感數(shù)據(jù)的使用不妥協(xié)；③沒(méi)有一個(gè)指數(shù)計(jì)算的復(fù)雜性。

2.3 關(guān)聯(lián)規(guī)則隱藏發(fā)展方向

關(guān)聯(lián)規(guī)則隱藏有兩個(gè)主要方向：①在原始數(shù)據(jù)中隱藏一些特別的關(guān)聯(lián)規(guī)則；②從原始數(shù)據(jù)挖掘出一些頻繁項(xiàng)，即隱藏這些特別的頻繁項(xiàng)，即確保從敏感規(guī)則在公開(kāi)的數(shù)據(jù)里變得無(wú)關(guān)緊要。

3 結(jié)語(yǔ)

在共享環(huán)境下，關(guān)聯(lián)規(guī)則隱藏用處極大。本文提出了一種分類(lèi)的隱私保護(hù)關(guān)聯(lián)規(guī)則挖掘方法，并進(jìn)行了詳細(xì)分析?，F(xiàn)有方法僅提供了隱藏敏感知識(shí)的近似解，如何找到數(shù)據(jù)庫(kù)信息披露的精確解還有待進(jìn)一步研究。

參考文獻(xiàn)：

[1] S R M OLIVEIRA，O R ZAIANE，Y SAYGIN.Secure association rule sharing， advances in knowledge discovery and data mining[C].Sydney：Proceedings of the 8th PacificAsia Conference（PAKDD2004），2004：7485.

[2] S OLIVEIRA，O ZAIANE.Algorithms for balancing privacy and knowledge discovery in association rule mining[C].Hong Kong：Proceedings of 7th international database engineering and applications symposium （IDEAS03），2003.

[3] YONGCHENG LUO，YAN ZHAO，JIAJIN LE.A Survey on the privacy preserving algorithm of association rule mining[C].International Society for EighteenthCentury Studies，2009：241245.

[4] CHRIS CLIFTON，MURAT KANTARCIOGLOU，XIADONGLIN，et al.Tools for privacy preserving distributed data mining[J].SIGKDD Explorations，2002，4（2）：17.

[5] IOANNIDIS I，GRAMA A，ATALLAH M.A secure protocol for computing dotproducts in clustered and distributed environments[C].Proceedings of International Conference on Parallel Processing，2002：379384.

[6] GKOULALAS DIVANIS，V S VERYKIOS.Exact knowledge hiding through database extension[J].IEEE Transactions on Knowledge and Data Engineering，2009，21（5）：699713.

（責(zé)任編輯：孫 娟）