隱私保護數據挖掘算法MASK的改進

王 茜，張鯤鵬

(重慶大學計算機學院，重慶 400044)

近年來隨著數據挖掘技術的發展，數據隱私保護逐漸引起人們普遍的關注［1－2］。Rizvi S J等［3］于 2002年提出了基于隨機擾動的 MASK(mining associations with secrecy konstraints)算法。該方法很好地解決了在保持高度隱私的同時獲得較為準確的挖掘結果的問題，但該算法運行的時間效率較低。武振華等［4］在此基礎上改進了MASK算法。稱之為XMASK算法［4］，該算法利用分治策略簡化求解逆矩陣的過程，從而提高了算法的運行效率。本文提出一種基于XMASK算法的改進算法。復雜度分析和實驗結果都表明本文提出的算法在保證隱私度和準確度不變的同時明顯提高了運行的時間效率。

1 MASK算法和XMASK算法

MASK算法由Rizvi提出。假定數據集為超市購物數據籃，所挖掘的數據集可以看作由0和1組成的二維稀疏布爾矩陣，1表示購買某件商品，0表示沒有購買。為了保護輸入數據集的隱私性，MASK算法采用概率歪曲的方法對原始數據集進行擾亂操作。一個0－1數據庫元組可以看成一個隨機向量X={Xi}，Xi=0或者1。對Xi進行歪曲操作得到 Yi=XiXOR，其中是 ri的補，ri是滿足貝努利分布的隨機變量，分布律p(ri=1)=p，p(ri=0)=1－p。由異或計算的特點可知隨機向量X經過歪曲操作后，第i個分量Xi保持原值的概率為p，取其相反值的概率為1－p。

MASK算法所挖掘的數據集是真實數據集經過概率變換形成的，所以需要重構項集的真實支持度。設真實數據集對應的矩陣為T，T經過歪曲變換后得到的矩陣為D，歪曲概率為p。T的第i列中1的個數記為，0的個數為，D中第 i列中1的個數為，0的個數為。由前面的概率歪曲過程可知:

所以

n－項集的真實度估算方法跟單項集類似，方法如下:

由于MASK算法重構數據項真實支持度的指數級復雜度，使得該算法運行的時間效率較差。基于MASK算法，大量改進的算法被提出。武振華等于2008年提出一種基于MASK的改進算法XMASK。

XMASK改進算法在求解M－1的過程中，利用低階與高階M中所存在的遞歸關系從而使重構數據項支持度的時間復雜度由原來的O(8n)降低為O(2n)，使得算法在時間性能上提高了2個數量級，大大提升了算法的執行效率，是一種非常有效的改進。

2 新的優化方法

XMASK改進算法在求解概率矩陣方面很有效，但是當求解概率矩陣的時間復雜度降低到一定的數量級后，在重構數據項真實支持度時對歪曲矩陣中各個組合的計數過程的指數級時間復雜度仍然制約著算法的執行效率。

2.1 新算法的描述

MASK算法的實現基于經典Apriori算法，先產生頻繁1－項集，再產生頻繁k－項集，最后生成強關聯規則。與經典Apriori算法不同的是項集的計數問題。MASK算法需要從歪曲后的數據集估算真實數據集中項集的支持度，例如對于2－項集，原始項集11歪曲后會變為00，01，10，11中的一種，所以要得到真實2－項集的支持度需要考慮4種變化情況。而對于k－項集，就需要考慮2k種變化情況，由此可見MASK算法在對扭曲矩陣各個組合進行計數的開銷也是十分巨大的。

MASK算法所挖掘的數據集是二維稀疏布爾矩陣，而在對歪曲項集的實際計數過程中不難發現，由于布爾數據集的特性，各數據集的計數并不是毫無關聯的，例如在二次頻繁集{A、B}的計算中，只需查詢出A、B取值全為1，即11的個數，其余取值組合則可以表示為

其中A、B的取值可以在之前的1－項集挖掘中得到，而在 n次頻繁集的計算中，可將此規則歸納為［5］:

利用此公式，對于任意K次候選頻繁項集，只需要在歪曲數據集合中查詢一次取值全為1的項集個數，其他組合的個數可通過利用之前在項集挖掘中得到的頻繁項集取值全為1的計數，并結合此公式求得。在挖掘過程中，通過哈希鏈表來存儲各取值全為1的項集的個數以供后續的挖掘使用。這樣就可以顯著減小算法在歪曲數據集中計數過程的開銷。

2.2 完整的改進算法的實現

改進的算法在XMASK算法的基礎上，增加函數cal(A，p)用于計算項集A在歪曲矩陣中的計數，哈希鏈表hashtab在存儲頻繁項集在歪曲矩陣中取值均為1的個數。下面是改進算法的實現過程:

3 實驗及結果分析

為了驗證改進算法的性能，通過實驗將原MASK算法與XMASK算法進行比對。本實驗的硬件環境為聯想B3電腦，配置為Pentium?Dual-Core CPU E63002.80GHz處理器和2G內存，操作系統為Windows XP，開發工具為Visual C++6.0。

實驗采用的數據集由IBM Almaden generator生成。數據集的參數設定為T12I5D100KN0.02，表示數據集中的數據的平均長度為12，頻繁項集的平均長度為5，數據集總共有100000個數據，屬性的總個數為20。

在實驗中，數據庫以參數p=0.8進行扭曲，最小支持度min_sup為10%，運行結果見圖1。

圖1 3種算法的比較

由實驗結果可知:當n≥5的時候，3種算法的運行時間差別不大;當n=6的時候，XMASK算法與改進后的算法的執行效率比原MASK算法提升了3到4倍;當n≥7時，原MASK算法的執行效率急劇退化，而XMASK算法與改進算法仍然保持了良好的執行效果;當n的階數提升至8和9的時候，改進算法的運行時間僅為0.768 s和5.143 s，相對于XMASK 算法的1.563 s和13.259 s，執行時間效率提升了2到3倍。這樣的實驗結果表明，本文改進后的算法在時間性能上明顯優于原MASK算法和XMASK算法。

4 結束語

本文針對MASK算法執行效率低下的問題，基于XMASK算法提出了新的改進算法，利用布爾數據集的特性，通過已知項求解未知項的方法降低了對扭曲數據集的訪問次數，使算法在時間效率上得到顯著的提高。最后，通過實驗證明了改進后的MASK算法具有更高的時間效率。

［1］Verykios V S，Bertino E，Fovino I N，et al.State-of-the-Art in privacy preserving datamining［J］.SIGMOD Record，2004，33(1):50 －57.

［2］陳曉明，李軍懷，彭軍，等.隱私保護數據挖掘算法綜述［J］.計算機科學，2007，34(6):183 －186.

［3］Rizvi S，Haritsa J R.Maintaining Data Privacy in Association Rule Mining［C］//Proc.of 28thInt.Conf.On Very Large Databases，USA:［s.n.］，2002.

［4］武振華，劉山，崔健國.基于分治策略的MASK算法的改進［J］.微計算機信息，2009(36):78－80.

［5］Agrawal R，Imielinski T，Swami A.Mining association rules between sets of items in large databases［C］//Proc.Of ACM SIGMOD Intl.Conf.On management of data.USA:［s.n.］，1993.

［6］Agrawal S，Krishnan V，Haritsa J R.On addressing efficiency concerns in privacy-preserving minning［M］//Lee Y J，Li J Z，Whang K Y，et al.Proc.of the 9thIntl.Conf.On Database Systems for Advanced Applications.LNCX 2973.Jeju Island:Springer-Verlag，2004:113－124.

［7］黃毅群，盧正鼎，胡和平，等.分布式環境下保持隱私的關聯規則挖掘算法［J］.計算機工程，2006，32(13):12－14.

［8］Alexey Pryakhin，Matthias Schubert，Arthur Zimek，et al.Future trends in data mining［J］.Data Min Knowl Disc，2007，15:87 －97.