基于粗集與位陣的關(guān)聯(lián)規(guī)則挖掘算法研究.pdf

1、作為數(shù)據(jù)庫研究領(lǐng)域中的熱點，數(shù)據(jù)庫中的知識發(fā)現(xiàn)(簡稱KDD)正在受到越來越多的關(guān)注。它被定義為在數(shù)據(jù)中尋找正確的、有趣的、潛在有用的并最終可以理解的模式。對關(guān)聯(lián)規(guī)則的挖掘在許多數(shù)據(jù)挖掘任務(wù)中都有重要作用，有著廣泛的應(yīng)用范圍。隨著被挖掘的數(shù)據(jù)集在大小和復(fù)雜度上的飛速增長，研究高效可伸縮的挖掘算法對保證系統(tǒng)的可伸縮性和交互性至關(guān)重要。 關(guān)聯(lián)規(guī)則挖掘算法使用格理論中的組合特性來將原始問題分解為許多更小的互相獨立的問題。最有名的和最有影

2、響力的算法包括Apriori算法和FP-growth算法。 粗集理論根據(jù)對一個系統(tǒng)的觀察和測量所得的現(xiàn)實數(shù)據(jù)信息，從分類的觀點，以集合近似、近似分類與不可分辨的概念為基礎(chǔ)，通過知識約簡從中發(fā)現(xiàn)、推理知識和分辨系統(tǒng)的特點、過程、預(yù)測系統(tǒng)的結(jié)果等。DM_R算法嘗試利用粗集理論中關(guān)于等價類的概念，針對單維布爾關(guān)聯(lián)規(guī)則問題提出的一種挖掘算法，并利用興趣度對規(guī)則進行評價。DM_R算法借助不可分辨關(guān)系的概念，將事務(wù)數(shù)據(jù)庫按照交易集合劃分等價

3、類。該算法從k-候選項集中可以直接產(chǎn)生k-頻繁項集，同時還可以生成(k+1)-候選項集而無需搜索數(shù)據(jù)庫，因此DM_R算法只需在生成1-候選項集時對數(shù)據(jù)庫進行一次搜索，這會大大減少計算時間。 通過對各項交易設(shè)定不同的MIF值，用戶可以靈活控制不同的關(guān)聯(lián)規(guī)則的最小支持度閾值，可以發(fā)現(xiàn)包含非頻繁交易的具有較低支持度的關(guān)聯(lián)規(guī)則以及具有較高支持度的包含頻繁交易的關(guān)聯(lián)規(guī)則，同時又不會引入過多無意義規(guī)則。 由于現(xiàn)實世界事務(wù)數(shù)據(jù)庫中，數(shù)

4、據(jù)是隨時間的變化而變化的，當前已發(fā)現(xiàn)的最大頻繁項集可能不再生效，而新的有效最大頻繁項集有待于重新去發(fā)現(xiàn)。因此，迫切需要設(shè)計高效的算法來管理、維護和更新已挖掘出來的最大頻繁項集。目前國內(nèi)外在對這一問題的相關(guān)研究中提出了Pincer Search、IUA、FIUA、FUFIA、FUMFIA等算法，這些算法主要是針對頻繁模式樹來進行單雙向剪枝與重構(gòu)，需要額外的存貯空間和較大的運算開銷。 對此，本文提出了一種增量式更新最大頻繁項集算法F