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

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

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

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

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

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

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

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

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

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