研究生論文--開題報告-基于隱私保護的多源數(shù)據(jù)挖掘高效算法研究__本科論文

1、研究生學位論文開題報告題目名稱：基于隱私保護的多源數(shù)據(jù)挖掘高效算法研究姓 名: 學 號: 專業(yè)名稱: 研究方向: 攻讀學位: 學 院: 導師姓名: 導師職稱:填表時間填表說明1. 開題報告是研究生培養(yǎng)的重要環(huán)節(jié)，研究生需在認真完成。2. 完成時間：碩士研究生的開題報告應于第三學期末前完成3. 打印要求：此表用A4紙雙面打印。4. 此表與中期考核審核表、成績單、實踐報告、學術(shù)活動列表等材料一起交于學院，參加中期考核13一、課題來源，國內(nèi)外研究現(xiàn)狀、水平及發(fā)展趨勢，選題的研究意義、目的，參考文獻（一）課題來源 1問題的提出數(shù)據(jù)挖掘，顧名思義即是從大型數(shù)據(jù)庫中提取人們感興趣的知識，這些知識是隱含的、

2、 事先未知的、潛在的、有用信息，提取的知識表示為概念、規(guī)則、規(guī)律、模式等形式。數(shù)據(jù)挖掘要處理的問題，就是在龐大的數(shù)據(jù)庫中尋找有價值的隱藏事件，加以分析，并將這些 有意義的信息歸納成結(jié)構(gòu)模式，提供給有關部門決策時參考。目前已經(jīng)提出的常用方法有關 聯(lián)規(guī)則、決策樹、聚類、神經(jīng)網(wǎng)絡等方法。然而，在對數(shù)據(jù)進行挖掘的時候，都不可避免的會出現(xiàn)敏感信息泄露的問題，隨著數(shù)據(jù) 挖掘技術(shù)的日益發(fā)展，數(shù)據(jù)隱私和信息安全逐漸引起人們的關注。為了保護數(shù)據(jù)的隱私，人 們不愿提供正確的信息給服務商，以免個人信息泄露造成不必要的麻煩，但是數(shù)據(jù)挖掘結(jié)果 準確的重要前提是提供的數(shù)據(jù)正確。由于數(shù)據(jù)挖掘主要任務是對匯總數(shù)據(jù)的模式開發(fā)，

3、這使 得構(gòu)造一個不需要訪問精確的單個信息而獲得準確的模式的挖掘技術(shù)成為可能。目前，基于 隱私保護的數(shù)據(jù)挖掘技術(shù)已經(jīng)成為一個新穎熱門的研究領域，國內(nèi)外已有很多成熟的研究算 法和技術(shù)。通過眾多文獻比對我們發(fā)現(xiàn)，目前已有的這些基于隱私保護的數(shù)據(jù)挖掘算法和技術(shù)大多 是針對單源數(shù)據(jù)庫進行挖掘和保護，而在實際應用中，有很多情況必須面對多個數(shù)據(jù)源。例 如，許多大型企業(yè)、跨國公司都擁有過個子公司，每個子公司都有自己相應的數(shù)據(jù)庫。這就 迫切需要數(shù)據(jù)庫挖掘系統(tǒng)具有針對多數(shù)據(jù)源進行挖掘和保護的能力。已有的國內(nèi)外文獻中， 針對多源數(shù)據(jù)進行挖掘的模型和算法已經(jīng)出現(xiàn)，但是基于隱私保護技術(shù)的多源數(shù)據(jù)挖掘研究 卻很少提及。這

4、可能是由于多源數(shù)據(jù)挖掘本身的技術(shù)局限性，導致在對多個數(shù)據(jù)源進行挖掘 時，泄露敏感信息都成為了不可避免的操作。因此，本文在對當前已有的多源序列模式挖掘 技術(shù)研究的基礎上，分析結(jié)合并行和隱私保護技術(shù)的特點，提出新的基于隱私保護的多源數(shù) 據(jù)挖掘高效算法，使得在多源環(huán)境下既可以高效率高準確度的挖掘出高投票率模式（全局模 式），又可以隱藏敏感序列模式，達到較好的隱私保護效果。（二）國內(nèi)外研究現(xiàn)狀、水平及發(fā)展趨勢1隱私保護技術(shù)的研究進展關于數(shù)據(jù)的隱私保護問題，首次是由Adam N等學者在Security-control methods forstatistical databases: A com par

5、ison study2文中提出，文章中提出了一種用擾動的方式來 解決數(shù)據(jù)的隱私保護。所謂“擾動”就是發(fā)布數(shù)據(jù)集失真，數(shù)據(jù)獲得者無法通過其他途徑構(gòu) 建出原始數(shù)據(jù)集，但是這個失真的數(shù)據(jù)集又仍然保持數(shù)據(jù)獲得者所希望保留的某種特性。基 于數(shù)據(jù)失真的技術(shù)還有隨機擾動、阻塞和凝聚等。目前常用的隱私保護技術(shù)大多都是以統(tǒng)計模型和概率模型為主理論，應用在較低層次的數(shù)據(jù)隱私保護。在分布式環(huán)境中，Clift on C等提出使用SMC （Secure Multi-party Computation）安全多方計算加密技術(shù)保證數(shù)據(jù)的通信安全 ,這種基于加密的隱私保護技術(shù)可適用于科學計算、分布式安全查詢、幾何計算、分布式數(shù)

6、 據(jù)挖掘等應用。當前，關于SMC的研究主要集中在減低計算開銷、以SMC為工具解決問題以及優(yōu)化分布式計算協(xié)議。在國內(nèi)，關于隱私保護技術(shù)的研究主要集中在基于數(shù)據(jù)失真或數(shù)據(jù) 加密技術(shù)方面的研究，如基于隱私保護分類挖掘算法、關聯(lián)規(guī)則挖掘、分布式數(shù)據(jù)的隱私保 護協(xié)同過濾推薦、網(wǎng)格訪問控制等。（國內(nèi)研究現(xiàn)狀）對數(shù)據(jù)進行隱私保護，主要可分為在數(shù)據(jù)發(fā)布過程中和在數(shù)據(jù)挖掘過程中進行。目前已 有的針對數(shù)據(jù)發(fā)布的隱私保護技術(shù)已經(jīng)有很多，本文主要討論數(shù)據(jù)挖掘中的隱私保護技術(shù)。2、隱私保護數(shù)據(jù)挖掘的研究進展數(shù)據(jù)挖掘中的隱私保護主要考慮兩個方面的問題，一個是敏感的原始數(shù)據(jù)，一個是從數(shù) 據(jù)庫中提取出來的敏感知識。這兩種信息

7、都應當在挖掘的時候進行刪除，因為可能導致隱私 泄露問題。因此，隱私保護數(shù)據(jù)挖掘的主要目的就是用某種技術(shù)改進已有的數(shù)據(jù)挖掘算法來 修改原始數(shù)據(jù)，使得敏感的數(shù)據(jù)和知識不被泄露。目前，針對隱私保護數(shù)據(jù)挖掘的研究，國 外已經(jīng)有很多方法。文獻4采用數(shù)據(jù)擾亂技術(shù)，從訓練數(shù)據(jù)中重構(gòu)一個決策樹分類器從而解 決數(shù)據(jù)挖掘中隱私保護問題。文獻提出了一種基于隨機化的方法一一隨機響應技術(shù)，禾U用這種源于統(tǒng)計學研究中隱私保護的方法，來實現(xiàn)在不泄露隱私數(shù)據(jù)的情況下進行一定精度的 建模，文中主要探討了與ID3決策樹算法結(jié)合進行分類的方法。文獻6討論了一個利用不確定性符號進行數(shù)據(jù)阻塞并應用于關聯(lián)規(guī)則挖掘的具體例子，這種情況下支

8、持度和置信度分別 用支持度區(qū)間和置信度區(qū)間代替。文獻7提出一個利用添加噪聲數(shù)據(jù)對待挖掘數(shù)據(jù)庫進行有效分類的框架，滿足了對數(shù)據(jù)集中敏感信息方差和協(xié)方差的有效保護。對于如何很好的平衡 隱藏限制模式和揭露非限制模式，文獻8中提出了一個基于隱私保護的頻繁項集數(shù)據(jù)挖掘框架，對原始數(shù)據(jù)庫進行了一定程度的安全清洗。文獻9針對交易型數(shù)據(jù)庫，提出一個新的僅需要一遍掃描數(shù)據(jù)庫的算法對原始數(shù)據(jù)庫數(shù)據(jù)進行處理，使得既能達到保護隱私數(shù)據(jù)，又能 挖掘出準確的關聯(lián)規(guī)則，保留關聯(lián)規(guī)則挖掘的益處。由于在關聯(lián)規(guī)則挖掘中，很容易從非敏 感信息和原始未分類數(shù)據(jù)中推測出敏感信息，因此文獻10提出了一個新的算法來平衡關聯(lián)規(guī)則挖掘中的隱私

9、保護和知識發(fā)現(xiàn)。該算法對原始數(shù)據(jù)庫進行兩次掃描，不用考慮數(shù)據(jù)庫大 小和限制性關聯(lián)規(guī)則數(shù)目。針對分布式數(shù)據(jù)環(huán)境進行挖掘和隱私保護的研究是當前國內(nèi)主要熱門研究領域之一。 獻11中，從基于隨機擾動、基于安全多方計算以及基于限制查詢?nèi)齻€層次分類別討論了現(xiàn) 有的針對分布式隱私保護數(shù)據(jù)挖掘方法，對比各自優(yōu)缺點，總結(jié)未來發(fā)展方向。文獻12中,總結(jié)了在分布式數(shù)據(jù)庫特有環(huán)境下，如何解決數(shù)據(jù)安全性計算效率問題。文獻13中，結(jié)合隨機數(shù)生成器和RSA公鑰加密技術(shù)，提出了PPD-ARBSM算法。該算法引入數(shù)據(jù)挖掘服務器和密碼管理服務器，保證了敏感數(shù)據(jù)的安全性。文獻14中，針對分布式數(shù)據(jù)共享及計算中的隱私保護問題，提出了

10、一種適用于大規(guī)模分布式環(huán)境的隱私保護計算模型（PPCMLS）,該模型的核心為隱私安全模塊，將計算劃分為本地計算和全局計算。通過綜合運用同態(tài)加密、安 全點積協(xié)議、數(shù)據(jù)隨機擾亂算法等多種安全技術(shù)，在實現(xiàn)了多個節(jié)點在一個互不信任的分布 式環(huán)境下合作計算的同時，任何節(jié)點無法獲取其他節(jié)點的隱私信息及敏感中間計算結(jié)果。總 體而言，這些研究還都處于起步階段，具有廣闊的發(fā)展空間。文獻15中提出一種分布式匿名數(shù)據(jù)擾亂方法APM，該算法是匿名數(shù)據(jù)交換機制下的數(shù)據(jù)挖掘隱私保護方法，在高密度共謀攻擊的半誠實環(huán)境中有較好的魯棒性，與SMC相比具有顯著的效率優(yōu)勢和較高的靈活性和通用性，能應用于關聯(lián)規(guī)則挖掘和聚類等多種場合

11、。然而現(xiàn)有的隱私保護研究大都是在關聯(lián)規(guī)則方面，很少有針對序列模式方面。序列模式 挖掘包含時間因素，即每一個模式的元素之間存在先后順序關系，因此序列模式挖掘增加了 時間順序的因素，在某些情況下的應用能挖掘出關聯(lián)規(guī)則所無法挖掘的模式，提供更有效的 挖掘結(jié)果。本文提出的就是在多數(shù)據(jù)源環(huán)境下針對序列模式的數(shù)據(jù)挖掘算法，并盡可能的達 到隱私保護效果。目前國內(nèi)外研究中，針對序列模式的挖掘算法和模型已有一些。文獻16在假設參與方都是半誠實基礎上，強調(diào)了在一個類似二維站點的模式中隱私保護頻繁模式挖掘出現(xiàn)的問 題，提出一種基于半?yún)⑴c和不涉及加密的序列模式挖掘新方法。針對已有的序列模式挖掘方 法都是在數(shù)據(jù)庫數(shù)據(jù)不

12、發(fā)生任何改變的基礎上進行的。文獻17中基于數(shù)據(jù)可隨時更新的數(shù)據(jù)庫動態(tài)變化，提出一種新的改進的序列樹PS-tree,以解決改進的序列模式挖掘中出現(xiàn)的問題。文獻18利用密碼學中同態(tài)加密和數(shù)字信封技術(shù)來達到在多方參與中不共享隱私數(shù)據(jù)的 協(xié)同序列模式挖掘。文獻19以PrefixSpan算法為基礎，結(jié)合分布式計算的特點，研究并提出了一種分布式序列模式挖掘算法DSP （Distributed Seque ntial P attern Mi ning），并針對分布式環(huán)境下信息傳遞耗費大、任務可并行執(zhí)行等特點，對DSPM算法進行了進一步的改進。研究并提出了一種分布式序列模式挖掘的隱私保護算法CLSD（Curr

13、ent Least Sequences Delete），該方法通過刪除原始序列來降低敏感序列的支持數(shù)達到隱藏敏感信息的目的?；陔[私保護的序列模式挖掘算法研究目前還比較少，文獻20中首次提出了三個敏感序列隱藏算法一 MSA、MSRA和SDRF。這三種算法借鑒了關聯(lián)規(guī)則隱藏的思想，通過刪除 原始序列降低支持數(shù)的方式實現(xiàn)了敏感序列的隱藏。但MSA和MSRA算法在選擇被刪除序列時沒有做任何優(yōu)化，SDRF對候選刪除序列只進行了基本的篩選，仍存在刪除原始序列過多的問題，而且算法引入的預期最低支持度可能會導致敏感序列隱藏失敗情況的出現(xiàn)。已有的 這三種敏感序列隱藏算法均采用了預期最低支持度來保證敏感序列的隱

14、藏，它們在刪除過程 執(zhí)行之前就確定好了被刪除的原始序列，不能夠動態(tài)反映出已刪除序列對未刪除序列的影 響，沒有考慮先刪除序列對后刪除序列的影響，會刪除掉一些不必要刪除的序列。因此針對 這一特點，文獻21提出一種有效的敏感序列隱藏算法CLSDA （ current least sequences deletealgorithm ），該算法對候選序列加權(quán)，在刪除序列的過程中隨時更新權(quán)值，使用貪心算法獲得局部最優(yōu)解，盡可能減少對原始數(shù)據(jù)庫的改動。文獻22提出一種基于隱私保護的序列模式挖掘算法PP-SPM。算法以修改原始數(shù)據(jù)庫中的敏感數(shù)據(jù)來降低受限序列模式的支持度為原 則，首先構(gòu)建SPAM序列樹，根據(jù)一

15、定的啟發(fā)式規(guī)則，從中獲得敏感序列，再進一步在原始 數(shù)據(jù)庫中找到敏感數(shù)據(jù)，對其做布爾操作，實現(xiàn)數(shù)據(jù)庫的清洗。文獻23中提出一個基于數(shù)據(jù)清洗的敏感序列模式隱藏算法，該算法通過計算事務組影響權(quán)值，選取對非敏感序列模式 影響最小的事務組進行清洗，從而在確保隱藏敏感序列模式的同時，盡量減少對非敏感模式 集的影響。從以上兩個大的數(shù)據(jù)挖掘發(fā)展現(xiàn)狀分析，可以看到大多是針對單一數(shù)據(jù)源提出的各類算 法和技術(shù)，然而隨著互聯(lián)網(wǎng)信息的高度共享和實際應用的需求，多源數(shù)據(jù)挖掘已經(jīng)逐漸成為 數(shù)據(jù)挖掘領域新的進展方向，針對此領域的研究，將更好的應用于金融安全等各個行業(yè)和組 織。3、多源數(shù)據(jù)挖掘的研究進展目前對于多數(shù)據(jù)源數(shù)據(jù)挖掘

16、問題的研究，國內(nèi)外文獻中涉及的都比較少。對于多源數(shù)據(jù) 挖掘，為了有效從多數(shù)據(jù)庫挖掘全局序列，必須首先挖掘每個本地DB的信息，在本地層次上總結(jié)整合。一般情況下，多源數(shù)據(jù)挖掘可分三步進行：1）對多數(shù)據(jù)源進行分類；2）挖掘每個數(shù)據(jù)庫的知識；3）把同類數(shù)據(jù)庫挖掘到的知識進行合成。由于多源數(shù)據(jù)挖掘中必須面臨 眾多不同大小的數(shù)據(jù)集，文獻 24提出一個可供選擇的多源數(shù)據(jù)挖掘技術(shù)，僅選擇支持度大 于給定閾值的若干相關性大的數(shù)據(jù)庫進行挖掘搜索。該方法主要針對多源數(shù)據(jù)挖掘步驟中第 一步分類進行，有效的縮短了搜索代價。隨后，文獻25中又提出一種根據(jù)用戶查詢從多源數(shù)據(jù)庫中搜索用戶感興趣知識的方法，這一過程僅在被選擇數(shù)

17、據(jù)庫中進行挖掘檢索信息。以 上所采用的方法和技術(shù)構(gòu)成了目前已有的針對多源數(shù)據(jù)環(huán)境進行挖掘的主要模式，我們將其 稱為傳統(tǒng)的多源數(shù)據(jù)挖掘技術(shù)?？偨Y(jié)可知，其挖掘過程可分為三步進行：1）通過數(shù)據(jù)選擇從眾多數(shù)據(jù)庫中選擇其中有相關性的若干數(shù)據(jù)庫；2）利用數(shù)據(jù)合成技術(shù)將這些選中數(shù)據(jù)庫現(xiàn)有合為一個單一數(shù)據(jù)集；3）對這個巨大的單一數(shù)據(jù)集采用單源數(shù)據(jù)挖掘算法，得到最終的模 式集。文獻26介紹了一種將INLEN系統(tǒng)擴展到多源數(shù)據(jù)環(huán)境下進行知識發(fā)現(xiàn)的方式。 的并行挖掘技術(shù)有些也可以用來解決多源數(shù)據(jù)挖掘問題27-31。多源數(shù)據(jù)挖掘中的模式主要可分為四類：1）局部模式；2）高投票率模式，高投票率模式也就是通常所說的被用來

18、制定全局決策的全局模式；3）異常模式；4）支持模式。通過比較分析發(fā)現(xiàn)，傳統(tǒng)的多源數(shù)據(jù)挖掘技術(shù)對于鑒定多源數(shù)據(jù)庫中出現(xiàn)的兩類新的模式（高投票率模式和異常模式）非常不適用。因此，文獻32綜述性的闡述了多源數(shù)據(jù)挖掘中的若干問題和難點，介紹了多源數(shù)據(jù)挖掘和單源數(shù)據(jù)挖掘的差別，提出了針對多源數(shù)據(jù)挖掘的基礎框 架MDM和只在多數(shù)據(jù)源挖掘中才可挖掘出的具有深度意義的高投票率模式和異常模式的概 念。新型的多源數(shù)據(jù)挖掘框架MDM對傳統(tǒng)的多源數(shù)據(jù)挖掘過程的不足進行了改進，它更關注于局部模式分析。具體分三步進行：1）尋找全部數(shù)據(jù)庫的較好的分類；2）從局部模式中鑒定出兩種新模式類型：高投票率模式和異常模式；3）根據(jù)權(quán)

19、重合成局部模式。文獻33基于之前工作提出了從多個統(tǒng)計類和交易類數(shù)據(jù)庫中挖掘特性模式的方法。這一特性模式不 同于異常模式，它代表了所有局部數(shù)據(jù)庫中某一普遍模式。當前的局部模式分析可以從多源數(shù)據(jù)庫中發(fā)現(xiàn)高頻率的模式，但是仍然存在兩個關鍵問 題妨礙其擴展應用范圍：1）從因特網(wǎng)收集的數(shù)據(jù)質(zhì)量較低，無法區(qū)分是否為有用模式，且大多數(shù)據(jù)是不一致的，這就需要分布式數(shù)據(jù)挖掘技術(shù)來解決，并且必須在數(shù)據(jù)挖掘之前解決 數(shù)據(jù)不一致，于是提出了數(shù)據(jù)預處理的需求；2）多源數(shù)據(jù)庫中鑒定出潛在有用模式的有效算法仍未提出，傳統(tǒng)的多源數(shù)據(jù)挖掘是利用單源數(shù)據(jù)挖掘技術(shù)（即將從相關數(shù)據(jù)源中獲得的 所有數(shù)據(jù)全部聚集到一個大型數(shù)據(jù)集中進行挖

20、掘），這將破壞有用模式，并且利用局部模式分析時，將產(chǎn)生大量局部模式，時間空間消耗大。傳統(tǒng)的基于支持度的序列模式挖掘不能總 結(jié)出局部信息，效率較低。為了解決這一問題，文獻34中提出一個可選擇的本地挖掘方法在多DB中發(fā)現(xiàn)本地DB中的近似序列模式一一近似序列模式挖掘ApproxMAP算法。該算法的挖掘步驟是：根據(jù)相似度聚合序列；通過多序列比較從每個聚群中挖掘一致模式； 針對人造和真實數(shù)據(jù)進行試驗系統(tǒng)研究算法的性能。目前對于從多源數(shù)據(jù)庫中挖掘全局關聯(lián)規(guī)則的方法已經(jīng)有不少學者研究提出相關算法。 文獻35提出一種根據(jù)權(quán)重從不同數(shù)據(jù)來源數(shù)據(jù)庫中發(fā)掘合成高頻率關聯(lián)規(guī)則，文獻36是從多數(shù)據(jù)源中鑒定發(fā)現(xiàn)全局異常模

21、式。文獻37提出一種在多源數(shù)據(jù)挖掘庫中挖掘異常模式的有效策略，其挖掘時間復雜度和空間復雜度分別為20（m nl）和O（mnl），其中m代表數(shù)據(jù)庫分類個數(shù)，n代表每個分類中局部模式數(shù)，I代表分類中長度最長的數(shù)據(jù)庫的長度。國內(nèi)方面 對于多源數(shù)據(jù)挖掘的研究還很少，文獻38應用聚類思想，提出一種獨立于應用的數(shù)據(jù)庫分類方法，有效的在多源數(shù)據(jù)挖掘初始步驟將多數(shù)據(jù)庫合理劃分成若干類。文獻39主要針對多源數(shù)據(jù)挖掘中第三個步驟模式合成提出了一個新的算法，對多源數(shù)據(jù)先進行預處理，選取 有用規(guī)則，刪除掉冗余和噪聲之后，在利用各個規(guī)則的權(quán)值來合成多數(shù)據(jù)源中的關聯(lián)規(guī)則。 文獻40提出了一種基于聚類技術(shù)的多數(shù)據(jù)源記錄匹配

22、算法，該算法運用了專門針對大型數(shù) 據(jù)聚類的罩蓋聚類技術(shù)，大大減少了計算量，提高了多源環(huán)境下記錄匹配的效率。然而對于從多源數(shù)據(jù)庫中挖掘出全局序列模式的研究仍舊為空，因此這也是本文和今后 將要研究的重點所在。分析可知，已有的許多著名的序列模式挖掘算法，如GSP41、PrefixSpan42、SPADE43TSPAM44等，都能夠有效的挖掘出滿足最小支持度的序列模式。 可是當將這些算法移植到多源數(shù)據(jù)環(huán)境中后，由于序列模式大量積累產(chǎn)生的內(nèi)在局限性使得 這些算法對于多源數(shù)據(jù)庫并不適用。主要存在以下三方面問題：1 ）許多常規(guī)方法挖掘序列模式的完整集合，容易產(chǎn)生大量、瑣碎的短模式，近來挖掘相對緊湊的序列模式

23、表達式已經(jīng) 被逐漸提出45 ； 2）常規(guī)方法挖掘序列模式需要精確匹配，但實際中并不是所有客戶的購買 習慣都完全相同，必然在模式之間會存在一定差異度，若只進行精確匹配，很容易挖掘出大 量繁復的無可借鑒價值的短模式；3）僅支持度不能夠區(qū)分統(tǒng)計上顯著的模式和隨機事件，許多短模式均意外更改，這種機率發(fā)生比較頻繁。文獻33提出的一些諸如周期性、隨機依賴關系和模式等在多源數(shù)據(jù)庫中都是隱藏不可發(fā)現(xiàn)的，不能夠簡單的使用單一挖掘方法進 行。因此文獻34中提出了可借鑒的近似序列模式匹配算法，即將從各個局部數(shù)據(jù)庫中挖掘 出的局部模式做近似匹配，得到具有滿足一定支持度閾值的近似一致模式，以這個模式作為局部數(shù)據(jù)庫的代表

24、，來進而構(gòu)造全局模式。并在挖掘中得到高投票率模式和異常模式兩類有 用模式序列。文獻46提出一種針對多源數(shù)據(jù)環(huán)境的數(shù)據(jù)庫分類技術(shù)。文中將多數(shù)據(jù)庫中的 所有局部數(shù)據(jù)庫根據(jù)其兩兩之間的相似度劃分成若干聚類，再根據(jù)算法得到最優(yōu)分類。實驗 可知，相比較傳統(tǒng)的從每個局部數(shù)據(jù)庫中挖掘局部序列模式再進行合成的步驟而言，文中提 出的從這些分類中再進行局部序列模式挖掘，可以從很大程度上減少搜索代價。為了在多源 數(shù)據(jù)庫中挖掘出更加有價值的信息，發(fā)現(xiàn)高投票率模式和異常模式的局部模式合成技術(shù)已經(jīng) 在很多文獻中被提出，如前面提到的35,36,37等。綜上所述，對于多源數(shù)據(jù)挖掘的研究，未來的研究方向?qū)⒃谌绾卧u估全局序列模式

25、挖掘 和如何在挖掘的同時保證隱私信息不被泄露?？紤]到真實的攜帶有用全局模式的序列數(shù)據(jù)在 眾多可得到數(shù)據(jù)中都是非常小的，即使在局部序列模式挖掘中其挖掘難度也是非常大的。因 此，未來對于全局挖掘算法的更加系統(tǒng)有效的評估方法還有待研究，并且對于如何從真實多 源數(shù)據(jù)庫中生成有用全局模式還有很大的研究空間。實際生活中，由于多數(shù)據(jù)源數(shù)據(jù)挖掘和 隱私保護同樣重要，因此更加需要在多源數(shù)據(jù)環(huán)境下保證數(shù)據(jù)安全，所以今后的研究重點將 在基于隱私保護技術(shù)的多源數(shù)據(jù)挖掘技術(shù)和方法領域展開。（三）選題的研究意義與目的隨著數(shù)據(jù)挖掘技術(shù)的日趨成熟，其應用范圍已逐漸從已有的單一數(shù)據(jù)源逐步向多數(shù)據(jù)源 發(fā)展。考慮單數(shù)據(jù)源和多數(shù)據(jù)源

26、差異，針對多源數(shù)據(jù)庫獨有特點提出的多源數(shù)據(jù)挖掘算法和 技術(shù)已經(jīng)是當前數(shù)據(jù)挖掘領域的一個新興研究熱點。然而，分析可知，當前已有的多源數(shù)據(jù) 挖掘算法技術(shù)主要存在以下兩方面空缺：一是這些已有算法大多是針對關聯(lián)規(guī)則提出的，對 于帶有時間順序的序列模式挖掘研究還較少，且只保證挖掘精度而未考慮挖掘速度；二是在 這些已有多源數(shù)據(jù)挖掘算法中幾乎沒有涉及考慮隱私保護問題。針對以上兩個特點，本文的 研究一方面著眼于將已有成熟的序列模式挖掘算法進行改進，結(jié)合并行技術(shù)設計研究多源環(huán) 境下高效、高準確度的序列模式挖掘模型和算法，另一方面考慮在多源數(shù)據(jù)挖掘有效高投票 率模式（全局模式）的同時，結(jié)合隱私保護技術(shù)，將敏感序列

27、模式進行隱藏，達到既從多源 數(shù)據(jù)環(huán)境中挖掘有用序列模式，又在一定程度上進行敏感信息保護的目的。(四) 參考文獻1 Jiawei Han, Micheline Kamber. Data Mining Concept and Techniques. 數(shù)據(jù)挖掘概念與技術(shù)M.北京：機械 工業(yè)出版社,2001.2 Adam N, Wortmann J. Security-control methods for statistical databases:A comp arison studyA. ACMCom pu ting Surveys, 1989, 21(4) :515-556.3 Clifton

28、 C, Kantaricioglou M. Tools for privacy preserving distributed data miningA. ACM SIGKDDEx plorations, 2002, 4(2):28-34.4 R.Agrawal, R.Srikant. P rivacy -p reserving data-miningC. /P roceedings of ACM SIGMOD on Management ofData. Dallas,2000:439-450.5 W.Du, Z.Zhan. Using randomized respo nse techniqu

29、es for p rivacy -p reserving data miningC. /P roceedings ofThe 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington DC,2003:505-510.6 Yucel Saygin, Vassilios S.Verykios, Ahmed K.Elmagarmid. Privacy p reserving association rule miningC./P roceedings of the 12th I

30、nternational Worksh op on Research Issues in Data Engineering. 2002:151-158.7 Md. Zahidul Islam, Ljiljana Brankovic. A Framework for P rivacy P reserving Classification in Data MiningC./P roceedings of the second worksh op on Australasian information security, Data Mining and Web Intelligence, and S

31、oftware Internationalisation - V olume 32, P ages 163-168.8 SRM Oliveira, OR Za? ane. Privacy Preserving Frequent Itemset MiningC. /Proceedings of the IEEEinternational conference on Privacy security and data mining - V olume 14, Pages 43-54.9 SRM Oliveira, OR Za? ane. Protecting Sensitive Knowledge

32、 By Data SanitizationC. /Proceedings of the 3th IEEE International Conference on Data Mining(ICDM03), pages 613-616. Nov 2003.10 SRM Oliveira, OR Za? ane. Algorithms for Balancing Privacy and Knowledge Discovery in Association Rule11121314MiningC. /P roceedings of the 7th International Database Engi

33、neering and App lications Symp osium, p ages 54-63. July 2003.劉英華，楊炳儒等.分布式隱私保護數(shù)據(jù)挖掘研究J.計算機應用研究.2011,28(10):3607-3609. 張宏壯，王建民.分布式數(shù)據(jù)庫保持隱私挖掘方法 J.計算機工程與設計.2008, 29(14):3684-3686. 桂瓊，程小輝，饒建輝.基于RSA的隱私保護關聯(lián)規(guī)則挖掘算法J.計算機工程.2009, 35(17):138-140.余智欣，黃天戍等.一種新型的分布式隱私保護計算模型及其應用J.西安交通大學學報.2007,41(8):955-958.馬進，李鋒等.分

34、布式數(shù)據(jù)挖掘中基于擾亂的隱私保護方法J.浙江大學學報.2010,44(2):276-282.1516 Ada Wai-Chee Fu, Raymond Chi-Wing Wong, Ke Wang. Privacy -P reserving Frequent P attern Mining AcrossP rivate DatabsesC. /P roceedings of the 5th IEEE International Conference on Data Mining(ICDMO5).Houston. 2005.17 Jen-Wei Huang, Chi-Yao Tseng, Jia

35、n-Chih Ou, Ming-Syan Chen. On P rogressive Sequential P atternMiningC. /CIKM 06. Virginia. 2006.18 Justin Zhan. P rivacy -P reserving Collaborative Sequential Pattern MiningJ. ACM. 2006(06):12-22.192021常鵬.基于隱私保護的分布式序列模式挖掘算法研究D.江蘇：江蘇大學碩士學位論文，2008.陳肇勳.序列模式探勘的隱私保護D.中國臺灣：靜宜大學碩十學位論文，2006.朱玉全，胡天寒，陳耿，常鵬.序列

36、模式挖掘中的隱私保護方法研究J.計算機應用研究.222009,26:2489-2491.燕彩榮，朱明，史有群.基于隱私保護的序列模式挖掘J.小型微型計算機系統(tǒng).2008,7(7):1241-1244.23華蓓，鐘誠等.通過計算影響權(quán)值實現(xiàn)敏感序列模式隱藏J.小型微型計算機系統(tǒng).2010,8(8):1647-1651.24 H. Liu, H. Lu, J. Yao. Identifying Relevant Databases for Multi-database MiningC. / Proceedings ofP acific-Asia Conference on Knowledge Di

37、scovery and Data Mining, pages 210-221, 1998.25 J. Yao, H. Liu. Searching Mult iple Databases for Interesting CompI exesC. /P roceedings of PAKDD, p ages198-210, 1997.26 J. Ribeiro, K. Kaufman, L. Kerschberg. Knowledge discovery from mult iple databasesC. /P roceedings ofKDD95, pages 240-245. 1995.2

38、7 J. Chattratichat, etc. Large scale data mining: challenges and respo nsesC. /P roceedings of InternationalConference on Knowledge Discovery and Data Mining, pages 143-146. 1997.28 D. Cheung, J. Han, V. Ng and C. Wong. Maintenance of discovered association rules in large databases: anincremental up

39、 dating techniqueC. /P roceedings of International Conference on Data Engineering, p ages106-114. 1996.29 A. P rodromidis, S. Stolfo. Pru ning meta-classifiers in a distributed data mining systemC. /P roceedings of the1st National Conference on New Information Technologies, pages 151-160. 1998.30 A.

40、 P rodromidis, P. Chan, and S. Stolfo. Meta-learning in distributed data mining systems: Issues andapp roachesJ. In Advances in Distributed and Parallel Knowledge Discovery, H. Kargupta and P. Chan (editors), AAAI/MIT P ress, 2000.31 T. Shintani, M. Kitsuregawa. Parallel mining algorithms for genera

41、lized association p atterns with classificationhierarchyC. / Proceedings of ACM SIGMOD, pages 25-36. 1998.32 S. Zhang, X. Wu, and C. Zhang. Multi-Database MiningJ. In IEEE Comp utational Intelligence Bulletin 2(1):pages 5-13. June 2003.33 N. Zhong, Y . Yao, and S. Ohsuga. Peculiarity oriented multi-

42、database miningC. /Proceedings of PKDD,p ages 136-146. 1999.34 HC Kum, JH Chang, W Wang. Sequential P attern Mining in Multi-Databases via Mult ip le AlignmentJ. DataMining and Knowledge Discovery,12, pages 151-180, 2006.35 X. Wu and S. Zhang. Synthesizing High-Frequency Rules from Different Data So

43、urcesJ. IEEE Trans.Knowledge Data Engineering 15(2): pages 353-367. 2003.36 C. Zhang, M. Liu, W. Nie, and S. Zhang. Identifying Global Exce ptional P atterns in Multi-database MiningJ.In IEEE Comp utational Intelligence Bulletin 3(1): pages 19-24. Feb 2004.37 S. Zhang, C. Zhang, and J. X. Yu. An eff

44、icient strategy for mining exce ptions in multi-databasesJ. In383940Information System 165(1-2): pages 1-20. 2004.唐懿芳，牛力，鐘智.多數(shù)據(jù)庫挖掘中獨立于應用的數(shù)據(jù)庫分類研究J.廣西師范大學學報(自然科學版).2003,21(4):32-36.唐懿芳，牛力，張師超.多數(shù)據(jù)源挖掘中的模式合成技術(shù)J.菏澤師專學報.2002,24(2):1-4.唐懿芳，鐘達夫，嚴小衛(wèi).基于聚類模式的多數(shù)據(jù)源記錄匹配算法J.小型微型計算機.2005,26(9):1546-1550.41 R. Srikan

45、t and R. Agrawal. Mining sequential p atterns: Generalizations and p erformance imp rovementsC./P roceedings of the 6th Intl. Conf Extending Database Technology (EDBT), pages 3-17. Mar 1996.42 J. Pei, J. Han, et al. PrefixS pan: Mining sequential p atterns efficiently by p refix -p rojected p attern

46、 growthC./P roceedings Of International Conference on Data Engineering (ICDE), pages 215-224. April 2001.43 M. J. Zaki. Efficient enumeration of frequent sequencesC. /P roceedings of the 7th International ConferenceInformation and Knowledge Management, p ages 68-75. Nov 1998.44 J. Ayres, J. Flannick

47、, J. Gehrke, T. Yiu. Sequential p attern mining using a bitma p rep resentationC./P roceedings of the ACM International Conference on Knowledge discovery and data mining (SIGKDD),pages 429-435. July 2002.45 X. Yan, J. Han, and R. Afshar. CloS pan: Mining Closed Sequential P atterns in Larege Dataset

48、sC./P roceedings of the 3rd SIAM International Conference on Data Mining (SDM), pages 166-177, San Fransico.CA, 2003.46 X. Wu, C. Zhang, and S. Zhang. Database classification for multi-database miningJ. In Information System30(1): pages 71-88. 2005.二、研究內(nèi)容（解決的問題），獨創(chuàng)或新穎之處，擬采取的研究方法，預期成果，論文框架（一）研究內(nèi)容（解決的

49、問題）1. 研究內(nèi)容與目標（1）對已有的序列模式數(shù)據(jù)挖掘算法和多源數(shù)據(jù)挖掘算法進行研究，分析單源和多源數(shù) 據(jù)環(huán)境中數(shù)據(jù)存儲形式及模式的區(qū)別、傳統(tǒng)多源數(shù)據(jù)挖掘過程中的局限性，根據(jù)局部模式平 均支持度、模式全局支持度，預期最低支持度等參數(shù)，提出一種新的適用于多源數(shù)據(jù)環(huán)境下 的高投票率模式（全局模式）挖掘模型。（2）在（1）的基礎之上，綜合考慮多源序列模式數(shù)據(jù)挖掘特點和并行技術(shù)特點，研究 算法的并行化方案，設計一種高效率、可擴展性好的多源數(shù)據(jù)環(huán)境下高投票率模式（全局模 式）挖掘的算法。（3）在（1）（ 2）的基礎上，結(jié)合隱私保護技術(shù)，根據(jù)局部模式平均支持度、模式全局 支持度、敏感模式支持事務組、非敏

50、感模式權(quán)值和事務組影響權(quán)值等參數(shù)，研究適用于多源 數(shù)據(jù)環(huán)境下的敏感序列模式隱藏方法，設計實現(xiàn)基于隱私保護的多源數(shù)據(jù)挖掘模型和算法，使得算法既能快速高效挖掘出全局序列模式，又能很好的隱藏敏感序列模式。2. 待解決的關鍵技術(shù)問題（1）分析考慮單源和多源兩種數(shù)據(jù)環(huán)境的主要區(qū)別，結(jié)合現(xiàn)有多源環(huán)境下序列模式挖 掘算法，根據(jù)局部模式平均支持度、模式全局支持度、預期最低支持度等參數(shù)，提出新的加 入并行思想的快速高效的多源數(shù)據(jù)環(huán)境下全局序列模式挖掘模型。（2 ）結(jié)合相關數(shù)據(jù)清洗技術(shù)，在對多源數(shù)據(jù)進行挖掘的初始步驟之前，考慮如何消除 各個數(shù)據(jù)庫中低于最低支持度的子模式和異常模式，得到“干凈”數(shù)據(jù)庫。（3）充分利

51、用多源序列模式數(shù)據(jù)挖掘特點和并行技術(shù)，設計更加高效的在多源環(huán)境下 挖掘全局序列模式的算法?？紤]在對數(shù)據(jù)庫進行劃分過程中采用何種技術(shù)以達到劃分效果和 速度最好。（4）如何在快速高效挖掘從多源數(shù)據(jù)環(huán)境中挖掘出全局序列模式的同時，隱藏支持敏感項集的敏感序列模式。根據(jù)局部模式平均支持度、模式全局支持度、敏感模式支持事務組、 非敏感模式權(quán)值和事務組影響權(quán)值等參數(shù)，設計多源環(huán)境下敏感序列模式隱藏模型。（5）在多源序列模式挖掘初始數(shù)據(jù)清洗時以何種策略刪除支持敏感序列模式的部分或 者全部敏感項集，并在挖掘之后各個局部模式進行合成步驟時如何解決合成過程再次出現(xiàn)敏 感序列的情況。（二）獨創(chuàng)或新穎之處（1）在考慮單

52、源與多源兩種數(shù)據(jù)環(huán)境的主要不同基礎上研究高效的多源環(huán)境下高投票 率模式（全局模式）挖掘技術(shù)。（2）對多源數(shù)據(jù)挖掘中數(shù)據(jù)清洗和數(shù)據(jù)庫分類過程耗時較大情況下，充分考慮多源數(shù) 據(jù)庫分布存儲特性，通過設計有效方法在共享存儲機器系統(tǒng)上進行并行執(zhí)行清洗和分類過程 來提高算法的挖掘效率。（3）根據(jù)局部模式平均支持度、模式全局支持度、敏感模式支持事務組、非敏感模式 權(quán)值和事務組影響權(quán)值等參數(shù)，研究提出基于隱私保護的多源數(shù)據(jù)挖掘模型，設計實現(xiàn)高效 和高保護精度的多源環(huán)境下敏感序列隱藏算法。（三）擬采取的研究方法（1）對已有的單源環(huán)境下的序列模式挖掘算法、多源數(shù)據(jù)挖掘算法進行研究和分析， 針對多源數(shù)據(jù)環(huán)境特點，借

53、鑒已有的多源序列模式挖掘算法，對其進行并行化，設計多源全 局序列模式挖掘模型，使得在保證挖掘準確度的同時盡可能提高挖掘速度。（2）利用并行技術(shù)，在已設計出的多源序列模式挖掘模型基礎上，研究設計高效率、 可擴展性好的多源全局序列模式挖掘算法。通過挖掘準確度和挖掘速度與已有算法進行對比 實驗分析。（3）結(jié)合隱私保護技術(shù)，根據(jù)局部模式平均支持度、模式全局支持度、敏感模式支持 事務組、非敏感模式權(quán)值和事務組影響權(quán)值等參數(shù)，設計針對多源數(shù)據(jù)挖掘的敏感序列隱藏 模型。（4）針對敏感序列和多源數(shù)據(jù)環(huán)境特性，研究提出適用于多源數(shù)據(jù)環(huán)境下的基于隱私 保護技術(shù)的敏感序列模式隱藏算法。結(jié)合單源隱私保護數(shù)據(jù)挖掘算法有

54、效性的評估指標（隱 藏失敗率、誤隱藏率、偽模式率）來評估本文提出的多源環(huán)境下基于隱私保護的序列模式挖 掘算法。（5）在多核計算機、LinUX操作系統(tǒng)上，采用 C語言和OpenMP并行編程的方法實現(xiàn)所提出的基于隱私保護的多源數(shù)據(jù)挖掘高效算法，利用IBM公司的人工數(shù)據(jù)生成器 AssocGen自動生成若干包含不同序列模式和最小支持度的數(shù)據(jù)庫數(shù)據(jù)作為實驗數(shù)據(jù)進行實驗，記錄實驗結(jié)果，與已有多源序列模式挖掘算法進行算法速度和準確度比較，并根據(jù)隱私保護數(shù)據(jù)挖 掘算法的若干評估指標進行實驗性能測試與分析評估算法對于敏感模式的隱藏情況。（四）預期成果（1）根據(jù)局部模式平均支持度、模式全局支持度、預期最低支持度等參數(shù)，建立適用 于多數(shù)據(jù)源環(huán)境下的全局序列模式挖掘數(shù)學模型，旨在保證高準確度挖掘的前提下更快速的