動態(tài)數(shù)據(jù)庫中頻繁模式的增減量維護.pdf

1、在過去的二十多年里，隨著數(shù)據(jù)庫技術(shù)的迅速發(fā)展以及數(shù)據(jù)庫管理系統(tǒng)的廣泛應(yīng)用，人們收集數(shù)據(jù)的能力有了巨大的提高，積累的數(shù)據(jù)越來越多。海量的數(shù)據(jù)背后隱藏著許多重要的、有趣的信息，人們希望能夠?qū)ζ溥M行更高層次的分析，以便發(fā)現(xiàn)有用的知識，從而更好地利用這些數(shù)據(jù)，為管理者提供強有力的決策支持。傳統(tǒng)的數(shù)據(jù)統(tǒng)計分析方法已經(jīng)不能夠滿足目前的需要，于是數(shù)據(jù)挖掘技術(shù)便應(yīng)運而生了。 數(shù)據(jù)挖掘（Data Mining），也稱為數(shù)據(jù)庫中的知識發(fā)現(xiàn)，是指從大

2、量的、不完全的、有噪聲的、模糊的數(shù)據(jù)中抽取出潛在的、有效的、新穎的、有用的和最終可以理解和運用的知識的過程。它是涉及數(shù)據(jù)庫、計算理論、人工智能、統(tǒng)計理論、認知科學(xué)等眾多學(xué)科的一門交叉學(xué)科，能夠?qū)?shù)據(jù)進行關(guān)聯(lián)分析、分類、聚類、預(yù)測、孤立點分析、演變分析。盡管數(shù)據(jù)挖掘技術(shù)誕生不久，但它廣泛的應(yīng)用前景和巨大的魅力，吸引了眾多學(xué)者極大的研究熱情和產(chǎn)業(yè)界人士的廣泛關(guān)注。 關(guān)聯(lián)分析是數(shù)據(jù)挖掘中最重要的研究領(lǐng)域之一。Agrawal等于1993

3、年首先提出了挖掘顧客交易數(shù)據(jù)庫中項集間的關(guān)聯(lián)規(guī)則問題。以后眾多的研究人員對關(guān)聯(lián)規(guī)則的挖掘問題進行了大量的研究，他們的工作包括對原有的算法進行優(yōu)化，如引入隨機采樣、并行的思想等，以提高算法挖掘規(guī)則的效率，對關(guān)聯(lián)規(guī)則的應(yīng)用進行推廣。一般而言，從數(shù)據(jù)庫中發(fā)現(xiàn)頻繁模式是關(guān)聯(lián)分析的核心任務(wù)，因為從頻繁模式生成關(guān)聯(lián)規(guī)則只是一個簡單的計算問題。 運動是自然界永恒的真理。我們所獲得的數(shù)據(jù)也是在動態(tài)地改變著。相應(yīng)的，我們運用數(shù)據(jù)挖掘技術(shù)從數(shù)據(jù)中獲

4、得的知識也要隨著數(shù)據(jù)的改變而改變，以反映出新的趨勢。增量算法能夠通過處理新增加的數(shù)據(jù)來滿足對原有知識的更新、加強的需要，這種方法避免了對整個數(shù)據(jù)集重新進行挖掘。1989年，Paul Utgoff等人提出了決策樹的增量更新算法ID5R,使得著名的決策樹算法ID3能夠根據(jù)動態(tài)增加的實例對整個樹的結(jié)構(gòu)進行調(diào)整。關(guān)聯(lián)規(guī)則的增量挖掘算法FUP和FUP2[5,21]是由David W. Cheung等人于1996，1997年提出的。它們采用類似于A

5、priori[12]算法的“產(chǎn)生-驗證”候選集的方法，對新增加的數(shù)據(jù)集進行多遍掃描并結(jié)合原有的頻繁項集，最后生成更新后的頻繁項集。基于滑動窗口的增量式關(guān)聯(lián)規(guī)則算法SWF[6]使用了新穎的方法：在候選2項集的基礎(chǔ)上一次性生成所有的候選K（K>2）項集，然后再驗證這些候選集，使得掃描數(shù)據(jù)庫的次數(shù)減少到兩次。類似的，增量算法的思想也被研究者運用到其它方面，產(chǎn)生了增量聚類算法等。 現(xiàn)有的增量式算法FUP，SWF在一定程度上解決了模式的增

6、量更新問題，但是對于減量問題（即一部分數(shù)據(jù)從數(shù)據(jù)集中刪除后，原數(shù)據(jù)集中的模式的更新問題）則沒有進行專門的研究和論述。眾所周知，現(xiàn)代數(shù)據(jù)庫的動態(tài)更新不僅包括數(shù)據(jù)的增加，也包括數(shù)據(jù)的刪除和更改（可以看作“先刪除-后增加”的一種特殊情況），因此，模式的減量更新維護也是一個值得研究的問題。然而，現(xiàn)有的增量式算法都存在一定的局限性，例如，F(xiàn)UP要對數(shù)據(jù)庫進行多遍掃描；SWF的“一次生成所有候選”的策略對于用IBM Quest project數(shù)據(jù)生

7、成器生成的模擬交易數(shù)據(jù)集存在著過度擬合現(xiàn)象，而在真實數(shù)據(jù)集上的效率則要低得多。 另一方面，動態(tài)數(shù)據(jù)庫的增減量挖掘也會涉及到一個重要的問題：什么時候該對數(shù)據(jù)庫進行增減量挖掘？David W.Cheung等人于1998年提出了DELI[42]算法，該算法利用集合對稱差原理定義了一個可信度因子（certainty factor）來確定什么時候該對數(shù)據(jù)庫進行更新。然而該算法會對數(shù)據(jù)庫進行多遍掃描，降低了效率。同時，為了計算可信度因子，D

8、ELI使用了抽樣技術(shù)，從而不可避免的產(chǎn)生False Negative和False Positive的問題。 基于以上討論，本文主要的研究工作如下： ·用模態(tài)邏輯對關(guān)聯(lián)規(guī)則分析中的概念進行了規(guī)范化的描述。 ·提出了一種針對動態(tài)數(shù)據(jù)庫的減量模式更新算法DUA。 ·分析了增量式算法SWF對于模擬數(shù)據(jù)庫的過度擬合問題，提出了一種高效的剪枝策略，并給出了頻繁模式的高效增減量算法EDUA，EDUA-O

9、。 ·研究了數(shù)據(jù)庫中項集的分布，并提出一種基于Kolmogolov-Smirnov統(tǒng)計分布檢驗的數(shù)據(jù)庫更新策略（算法KSDM）。 為了證明所提出的算法和策略的有效性，我們在模擬的和真實的數(shù)據(jù)集上進行了大量的實驗。實驗結(jié)果表明，所提出的DUA算法優(yōu)于Apriori算法，能夠快速地對數(shù)據(jù)庫進行減量更新；KSDM策略能夠根據(jù)數(shù)據(jù)庫的動態(tài)增減情況及時對整個數(shù)據(jù)庫進行更新，避免了頻繁更新數(shù)據(jù)庫的開銷。相對于FUP，F(xiàn)U