王 茜，張鯤鵬

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

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

1 MASK算法和XMASK算法

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

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

所以

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

由于MASK算法重構(gòu)數(shù)據(jù)項真實支持度的指數(shù)級復(fù)雜度，使得該算法運行的時間效率較差?；贛ASK算法，大量改進的算法被提出。武振華等于2008年提出一種基于MASK的改進算法XMASK。

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

2 新的優(yōu)化方法

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

2.1 新算法的描述

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

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

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

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

2.2 完整的改進算法的實現(xiàn)

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

3 實驗及結(jié)果分析

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

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

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

圖1 3種算法的比較

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

4 結(jié)束語

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

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

［2］陳曉明，李軍懷，彭軍，等.隱私保護數(shù)據(jù)挖掘算法綜述［J］.計算機科學(xué)，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］黃毅群，盧正鼎，胡和平，等.分布式環(huán)境下保持隱私的關(guān)聯(lián)規(guī)則挖掘算法［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.