動(dòng)態(tài)數(shù)據(jù)庫(kù)增量式挖掘算法及其應(yīng)用的研究.pdf

1、傳統(tǒng)的數(shù)據(jù)挖掘是從靜態(tài)的數(shù)據(jù)庫(kù)中發(fā)現(xiàn)知識(shí)。然而，數(shù)據(jù)倉(cāng)庫(kù)往往是動(dòng)態(tài)變化的，新的數(shù)據(jù)積累可能導(dǎo)致以前采用的挖掘算法所發(fā)現(xiàn)的知識(shí)失效，因此發(fā)現(xiàn)的知識(shí)或模式也需要?jiǎng)討B(tài)維護(hù)，及時(shí)更新。動(dòng)態(tài)數(shù)據(jù)庫(kù)與靜態(tài)數(shù)據(jù)庫(kù)挖掘的一個(gè)本質(zhì)區(qū)別在于人們對(duì)于新增的事務(wù)可能更感興趣。跟蹤這種動(dòng)態(tài)變化將使管理者在進(jìn)行決策時(shí)更加受益。增量算法是在已有的挖掘結(jié)果的基礎(chǔ)上，利用已經(jīng)獲得的知識(shí)對(duì)數(shù)據(jù)的增量部分進(jìn)行挖掘，而不是對(duì)數(shù)據(jù)增量后的整體數(shù)據(jù)庫(kù)進(jìn)行重新挖掘，從而大大節(jié)省知識(shí)

2、維護(hù)的開(kāi)銷。 Web日志中數(shù)據(jù)的規(guī)模往往很大，日志記錄每時(shí)每刻都在不停地產(chǎn)生，用戶的訪問(wèn)模式也隨之而變化，而這種用戶訪問(wèn)模式的變化趨勢(shì)對(duì)于網(wǎng)站管理者而言是非常重要的。由日志記錄構(gòu)成的數(shù)據(jù)庫(kù)就是典型的動(dòng)態(tài)數(shù)據(jù)庫(kù)，面對(duì)這種海量的動(dòng)態(tài)數(shù)據(jù)，需要尋找高效的增量挖掘算法，極大地降低平均搜索時(shí)間和空間，是十分迫切而且必要的。本文的研究正是針對(duì)海量的Web訪問(wèn)信息所構(gòu)成的數(shù)據(jù)庫(kù)的動(dòng)態(tài)特性而展開(kāi)，研究如何利用Web訪問(wèn)信息的動(dòng)態(tài)特性，尋找快速高

3、效的增量挖掘算法，重點(diǎn)研究Web挖掘中聚類、分類和關(guān)聯(lián)規(guī)則等若干關(guān)鍵問(wèn)題的理論和方法。 本文對(duì)動(dòng)態(tài)數(shù)據(jù)庫(kù)增量挖掘技術(shù)的國(guó)內(nèi)外研究狀況作了系統(tǒng)、全面的歸納、總結(jié)和分析，并對(duì)典型的應(yīng)用領(lǐng)域Web使用挖掘的研究現(xiàn)狀進(jìn)行了回顧。在此基礎(chǔ)上，重點(diǎn)研究了模糊層次聚類算法、神經(jīng)網(wǎng)絡(luò)聚類分類模型、基于聚類劃分的并行關(guān)聯(lián)規(guī)則挖掘方法以及它們的增量更新算法，主要貢獻(xiàn)和創(chuàng)新點(diǎn)如下： 1．利用模糊集合的理論，提出了基于模糊連接度的層次聚類算法F

4、HC。首先采用基本的劃分方法將大型數(shù)據(jù)集劃分成子類，然后分析子類間的連接模糊度，構(gòu)建子類模糊圖。通過(guò)對(duì)模糊圖進(jìn)行入截圖，得到模糊圖的連通分支，從而得到聚類結(jié)果。FHC算法能對(duì)任意形狀的簇進(jìn)行有效聚類。并將該方法與其他算法進(jìn)行了比較，無(wú)論在聚類質(zhì)量還是運(yùn)行時(shí)間上都具有優(yōu)勢(shì)，是一種快速高效的聚類方法。 2．對(duì)FHC算法進(jìn)一步擴(kuò)展，提出了該算法的增量挖掘方法IFHC和面向大型數(shù)據(jù)庫(kù)的分區(qū)聚類算法PFHC。IFHC通過(guò)對(duì)受影響的鄰域集合

5、進(jìn)行分析，高效地處理動(dòng)態(tài)增量數(shù)據(jù)。PFHC針對(duì)密度不均勻區(qū)域或者大型數(shù)據(jù)集合對(duì)于內(nèi)存容量不足的需求而提出的基于數(shù)據(jù)分區(qū)的模糊層次聚類算法，實(shí)驗(yàn)結(jié)果表明了這兩種算法作為對(duì)FHC算法的擴(kuò)充，具有很好的聚類效果。 3．結(jié)合自適應(yīng)諧振理論和競(jìng)爭(zhēng)型神經(jīng)網(wǎng)絡(luò)的特點(diǎn)，提出了一種新型的基于競(jìng)爭(zhēng)型神經(jīng)網(wǎng)絡(luò)的SIN模型，該方法綜合了自適應(yīng)諧振理論和競(jìng)爭(zhēng)型神經(jīng)網(wǎng)絡(luò)的特點(diǎn)，并在隱含層采用了Hebb學(xué)習(xí)規(guī)則進(jìn)行神經(jīng)元的側(cè)學(xué)習(xí)，既能保證原有記憶不受影響，又

6、能對(duì)新的信息加以記憶，同時(shí)又克服了ART網(wǎng)絡(luò)對(duì)噪音敏感的缺點(diǎn)，具有在線學(xué)習(xí)的功能，能夠?qū)崿F(xiàn)動(dòng)態(tài)數(shù)據(jù)的聚類。 4．傳統(tǒng)的對(duì)傳網(wǎng)絡(luò)模型和學(xué)習(xí)算法中，隱含層神經(jīng)元個(gè)數(shù)過(guò)多將產(chǎn)生死神經(jīng)元，過(guò)少又使得競(jìng)爭(zhēng)層不穩(wěn)定，網(wǎng)絡(luò)功能退化。針對(duì)這個(gè)缺陷，提出了一種自適應(yīng)地確定隱含層神經(jīng)元個(gè)數(shù)的ASCPN網(wǎng)絡(luò)模型和學(xué)習(xí)算法，使得競(jìng)爭(zhēng)層中每一個(gè)神經(jīng)元節(jié)點(diǎn)都能充分發(fā)揮作用，使得網(wǎng)絡(luò)能實(shí)現(xiàn)運(yùn)用最少的神經(jīng)元，達(dá)到要求的性能。并在競(jìng)爭(zhēng)層采用軟競(jìng)爭(zhēng)機(jī)制，在一定程度

7、上克服了初始權(quán)值選取敏感的問(wèn)題，雖然競(jìng)爭(zhēng)層的權(quán)向量計(jì)算比CPN復(fù)雜，但是泛化能力顯著提高，與其他的基于軟競(jìng)爭(zhēng)的算法相比，收斂速度快，模擬精度高，能更好地逼近模擬函數(shù)，提高了網(wǎng)絡(luò)的使用效率，使得網(wǎng)絡(luò)的性能得到很大的提高。 5．提出了基于聚類劃分的最大頻繁項(xiàng)集挖掘算法PARUC和它的動(dòng)態(tài)增量更新方法IPARUC算法。FP-tree是一種快速有效的關(guān)聯(lián)規(guī)則挖掘方法，它采用建立FP-tree的方法將信息集中到壓縮樹(shù)上，不需要產(chǎn)生候選項(xiàng)集

8、。該方法使用最不頻繁的項(xiàng)作后綴，大大降低了搜索開(kāi)銷。但是，面對(duì)海量數(shù)據(jù)，構(gòu)造基于內(nèi)存的FP-tree是不現(xiàn)實(shí)的，而且很難實(shí)現(xiàn)增量數(shù)據(jù)的挖掘。我們采用快速聚類的方法對(duì)海量數(shù)據(jù)進(jìn)行劃分，使得劃分后每部分?jǐn)?shù)據(jù)具有一定程度的相似性，從而壓縮局部FP-樹(shù)。同時(shí)對(duì)FP-tree的構(gòu)造算法進(jìn)行改進(jìn)，通過(guò)節(jié)點(diǎn)交換的方式壓縮樹(shù)的規(guī)模，以達(dá)到最佳壓縮效果。并討論了在增量情況下的最大頻繁項(xiàng)集的動(dòng)態(tài)更新方法，采用“剪枝-交換-接回”的方法解決新事務(wù)的插入問(wèn)題。