關(guān)聯(lián)規(guī)則中簡潔頻繁項(xiàng)集的挖掘方法研究.pdf

1、面對存儲(chǔ)數(shù)據(jù)的爆炸性增長，知識發(fā)現(xiàn)和數(shù)據(jù)挖掘應(yīng)運(yùn)而生。它能從大量、不完全、有噪聲的實(shí)際數(shù)據(jù)中，有效提取隱含在其中的、事先未知但又潛在有用的知識，并能夠?yàn)槲覀兊默F(xiàn)實(shí)決策過程提供支持。 關(guān)聯(lián)規(guī)則的挖掘是數(shù)據(jù)挖掘的重要任務(wù)之一，頻繁模式挖掘作為關(guān)聯(lián)規(guī)則挖掘的重要步驟，被廣泛應(yīng)用在相關(guān)性分析、序列模式、顯露模式、最長模式等許多重要數(shù)據(jù)挖掘任務(wù)中，得到了深入研究，并出現(xiàn)了有效挖掘方法。然而新的數(shù)據(jù)形態(tài)向傳統(tǒng)挖掘方法提出了新的挑戰(zhàn)，這主要表

2、現(xiàn)在：(1)數(shù)據(jù)量巨大。面對大規(guī)模數(shù)據(jù)，傳統(tǒng)算法不能夠有效處理。(2)挖掘結(jié)果龐大，難于被用戶接受和處理。挖掘結(jié)果的單位空間包含信息量較少，浪費(fèi)了大量空間，并影響了處理效率。(3)對于流數(shù)據(jù)不能實(shí)時(shí)有效處理。流數(shù)據(jù)是動(dòng)態(tài)的，而且頻繁更新，挖掘過程需要不斷進(jìn)行，以更新當(dāng)前的挖掘結(jié)果。傳統(tǒng)方法不能實(shí)現(xiàn)快速更新，滿足這種實(shí)時(shí)需求。選擇更加簡潔有效的數(shù)據(jù)表示方法和挖掘方法依然是此類挖掘任務(wù)的重要因素。 針對上述問題，本文針對基于頻繁模式

3、簡潔形式進(jìn)行關(guān)聯(lián)規(guī)則的挖掘問題進(jìn)行深入研究，提出新的有效方法。主要工作包括： (1)針對頻繁模式簡潔表示形式提取過程復(fù)雜問題，重新考察頻繁模式表示方法中存在的冗余，以及使用在同一個(gè)項(xiàng)集中項(xiàng)之間的關(guān)聯(lián)關(guān)系對存在的冗余進(jìn)行界定的問題。根據(jù)界定冗余的方法對搜索空間進(jìn)行分析，把項(xiàng)之間的關(guān)聯(lián)和搜索空間的剪枝結(jié)合起來。提出關(guān)聯(lián)后綴剪枝方法，利用項(xiàng)關(guān)聯(lián)后綴對冗余進(jìn)行標(biāo)識，使得對搜索空間進(jìn)行的提前剪枝成為了可能。 (2)在頻繁模式關(guān)聯(lián)上

4、界的挖掘中整合關(guān)聯(lián)后綴剪枝方法，對挖掘的搜索空間進(jìn)行剪枝。FP-樹結(jié)構(gòu)的路徑表示了項(xiàng)之間的關(guān)聯(lián)關(guān)系，通過對項(xiàng)關(guān)聯(lián)后綴進(jìn)行處理，標(biāo)示冗余的搜索空間，使得挖掘的搜索空間提前剪枝。不僅避免了維護(hù)大量中間結(jié)果所需的較大內(nèi)存空間以及由此引發(fā)的進(jìn)行的大規(guī)模超集判斷，并可直接生成頻繁集的閉模式表示方法。避免了通過在內(nèi)存中保留所有挖掘的中間結(jié)果，同時(shí)使處理過程更加簡潔高效。 (3)具有反單調(diào)性的Geneiator項(xiàng)集更適合具有反單調(diào)約束的具體應(yīng)

5、用問題處理。研究了頻繁項(xiàng)集關(guān)聯(lián)下界的挖掘問題，提出深度優(yōu)先進(jìn)行挖掘Generator表示的方法，在挖掘過程中根據(jù)多項(xiàng)關(guān)聯(lián)關(guān)系進(jìn)行剪枝，使得剪枝后的項(xiàng)集大部分為Generator項(xiàng)集。使用后綴剪枝方法對非 Generator項(xiàng)集進(jìn)行二次剪枝，從而有效生成頻繁項(xiàng)集的Generator表示方法。同時(shí)還發(fā)現(xiàn)被剪枝部分仍能為進(jìn)一步的挖掘進(jìn)行引導(dǎo)。 (4)驗(yàn)證了基于Generator的關(guān)聯(lián)規(guī)則和基于閉模式的關(guān)聯(lián)規(guī)則的簡潔性。提出在深度優(yōu)先的

6、挖掘頻繁模式的過程中，直接枚舉出基于以上簡潔形式的關(guān)聯(lián)規(guī)則的方法。使挖掘頻繁模式簡潔表示的過程與生成關(guān)聯(lián)規(guī)則的過程結(jié)合起來，對搜索空間進(jìn)行剪枝。 (5)針對流數(shù)據(jù)，提出基于最近數(shù)據(jù)動(dòng)態(tài)維護(hù)Generator簡潔表示的方法，以及如何繼承以往數(shù)據(jù)挖掘結(jié)果的問題。通過合理選擇處于頻繁和非頻繁、Generator項(xiàng)集和非Generator項(xiàng)集之間的邊界項(xiàng)集，以跟蹤由于數(shù)據(jù)更新引起的挖掘結(jié)果的改變，而不需保存所有頻繁項(xiàng)集和非頻繁集。同時(shí)根