EMASK算法優(yōu)化和改進

1、EMASK算法的優(yōu)化和改進學號:20091402118姓名:張鯤鵬導師:王 茜目錄 一、研究背景 二、MASK算法介紹 三、EMASK算法的主要思想 四、改進算法的思想 五、下一步工作計劃一、研究背景 隨著信息技術(shù),特別是網(wǎng)絡(luò)技術(shù)數(shù)據(jù)存儲技術(shù)和高性能處理器技術(shù)的飛速發(fā)展,海量數(shù)據(jù)的收集管理和分析變得越來越方便,知識發(fā)現(xiàn)和數(shù)據(jù)挖掘更是在一些深層次的應用中發(fā)揮了積極的作用.但與此同時,也帶來了隱私保護方面的諸多問題.例如,通過對醫(yī)院病人的病歷數(shù)據(jù)進行挖掘,可以發(fā)現(xiàn)各種疾病之間的關(guān)聯(lián). 所以,如何在數(shù)據(jù)挖掘過程中解決好隱私保護的問題,目前已經(jīng)成為數(shù)據(jù)挖掘界的一個研究熱點 。二、MASK算法介紹 MA

2、SK(Mining Associations with Secrecy Konstraints)算法由印度學者Rizvi在2002年提出的。 假定數(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 進行歪曲操作得到Y(jié)i = Xi XOR !ri ,其中!ri是ri 的補, ri 是滿足貝努利分布的隨機變量,分布律為p(ri=1)=p,p(ri=0)=1-p.由異或計算的

3、特點可知隨機向量X 經(jīng)過歪曲操作后,第i 個分量Xi 保持原值的概率為p ,取其相反值的概率為1- p。MASK算法所挖掘的數(shù)據(jù)集是真實數(shù)據(jù)集經(jīng)過概率變換形成的,所以需要重構(gòu)項集的真實支持度。設(shè)真實數(shù)據(jù)集對應的矩陣為 T , T 經(jīng)過歪曲變換后得到的矩陣為 D ,歪曲概率為p . T 的第 i 列中1的個數(shù)記為 ,0的個數(shù)為 , D 中第 i 列中1的個數(shù)為 ,0的個數(shù)為 其中 ， ， 解此方程組即可有歪曲矩陣D估算出真實矩陣1-項集的支持度 。Tc1TocDc1Dc0DTCMC1ppppM11TTTccC01DDDccC01Tc1n-項集的真實支持度的計算方法和單項集類似： ，其中 ，DTC

4、MC1DDDDcccCn0112.TTTTcccCn0112.MASK算法的實現(xiàn)基于經(jīng)典Apriori算法,即先產(chǎn)生頻繁1-項集,再產(chǎn)生頻繁k 項集,最后生成強關(guān)聯(lián)規(guī)則。MASK算法的優(yōu)點: 1、MASK算法的數(shù)據(jù)歪曲過程是在用戶機上完成的，不需要一個可信任的第三方，隱私度較高。 2、能夠保持高度隱私的同時獲得比較準確的挖掘結(jié)果。MASK算法缺點就是重構(gòu)原數(shù)據(jù)項的真實支持度的指數(shù)級的復雜度，執(zhí)行時間效率低下。三、EMASK算法的主要思想 基于MASK算法，大量改進的優(yōu)化算法相繼被提出。 Agrawal等人在此基礎(chǔ)上在2004年提出了MASK算法的改進算法,稱之為EMASK（Efficient

5、MASK）算法。 EMASK算法是公認的針對MASK算法的改進算法中改進的時間效率和空間效率非常有效的一種改進方法。EMASK算法的數(shù)據(jù)擾動過程與原MASK算法不同的地方在于，EMASK算法對“1”和“0”分別以不同的概率p,q進行擾動。以1-項集為例：其中因為用戶希望隱藏的信息數(shù)據(jù)項“1”明顯高于“0”，所以使用不同的參數(shù)擾動能提高數(shù)據(jù)的隱私保護程度。DTCMC1qpqpM11TTTccC01DDDccC01n-項集： ， ，在真實矩陣的歪曲過程中，某一真實數(shù)據(jù)項歪曲的概率實際上只和歪曲數(shù)據(jù)項中所包含的1和0的數(shù)量有關(guān)。例如在2-項集計算中，數(shù)據(jù)項“11”保持為“11”的概率為p*p，歪曲為

6、“00”的概率為(1-p)*(1-p)，歪曲為“01”和“10”的概率同為p*(1-p)。所以，真實矩陣和合成矩陣可以被簡化為DTCMC1DDDDcccCn0112.TTTTcccCn0112.DDDnDcccC01.TTTnTcccC01. 其中 為在真實矩陣中數(shù)據(jù)項中“1”的個數(shù)為 k的總數(shù)，例如在2-項集中， 表示真實矩陣中數(shù)據(jù)項“11”的個數(shù)， 表示數(shù)據(jù)項“01”和“10”的個數(shù)之和， 表示數(shù)據(jù)項“00”的個數(shù)。 概率矩陣: 經(jīng)過以上的處理后，真實矩陣和合成矩陣的階數(shù)相對原MASK算法就從 簡化為n+1，而概率矩陣M的階數(shù)從原算法的 縮減到 ，從而在求解M的逆矩陣過程中的時間復雜度由原

7、算法的O( )降到 O( )，明顯地改善了算法的時間執(zhí)行效率。TkcTc2Tc1Tc0n2nn22 n83n) 1() 1(nn)()(),min(), 0max(,)1 ()1 (kijiknkijnkjjinjikkkjjiqqCppCm四、改進算法的思想和實現(xiàn)四、改進算法的思想和實現(xiàn)雖然EMASK算法在求解逆矩陣過程中消除了原MASK算法的指數(shù)級的時間復雜度，但如果考慮到重構(gòu)原數(shù)據(jù)項支持度的特點，求逆過程中仍然有改善的空間。無論是MASK算法還是EMASK算法的實現(xiàn)都是基于經(jīng)典Apriori算法，即先產(chǎn)生頻繁1-項集，再產(chǎn)生頻繁n-項集，最后生成強關(guān)聯(lián)規(guī)則。前面說過超市購物籃數(shù)據(jù)的特點是

8、二維布爾稀疏矩陣，0的數(shù)量遠遠大于1，所以在數(shù)據(jù)重構(gòu)和挖掘過程中，考慮的重點是數(shù)據(jù)項為1的支持度和強關(guān)聯(lián)規(guī)則。MASK算法：EMASK算法：在重構(gòu)原數(shù)據(jù)項支持度的過程中，我們只需要找出真實矩陣中最頂端數(shù)據(jù)項（即數(shù)據(jù)全為1的數(shù)據(jù)項）的支持度即可。DDDTTTcccMcccnn011210112.DDDnTTTncccMccc01101.在EMASK算法中，按照上述要求將方程式有選擇性的展開，可以得到所以，我們在恢復n-項集真實支持度的計算只需要計算出M逆矩陣的第一行的概率集合已經(jīng)足夠。在這種情況下，求解一個n+1階M逆矩陣的過程實際上已經(jīng)退化為求解一個n+1項數(shù)據(jù)的數(shù)組，如此又能將求解概率矩陣的

9、逆矩陣的時間復雜度下降一個數(shù)量級。DDDnnTncccmmmc0100100.DnDnDnTncmcmcmc0010100.我們的改進算法的主要思想就是利用挖掘過程主要考慮頂端元組的特點，簡化求解概率矩陣逆矩陣的過程，達到改善執(zhí)行時間效率的目的。在原EMASK算法中采用高斯消元法求解概率矩陣的逆矩陣： ，其中 為M的伴隨矩陣， 為M的行列式。為了得到 ，需要計算 個n階行列式的值，其執(zhí)行時間效率為O( )。在改進的EMASK算法中，同樣采用高斯消元法求解逆矩陣，和原EMASK算法不同的是，我們只求解 的第一行的值，即求解伴隨矩 第一行的元組，需要計算n+1個n階行列式的值，其執(zhí)行的時間效率為O( )，和原EMASK算法相比，求解概率矩陣逆矩陣的時間復雜度下降了一個數(shù)量級。*11MMM*MM*M) 1() 1(nn3n1M2