一種數(shù)據(jù)流頻繁閉合項集挖掘算法的研究.pdf

1、隨著信息技術(shù)的飛速發(fā)展，許多領(lǐng)域產(chǎn)生的數(shù)據(jù)是在時間維度上嚴格有序、在數(shù)值上不斷變化的無限的數(shù)據(jù)序列，由此產(chǎn)生數(shù)據(jù)流模型。數(shù)據(jù)流頻繁項集挖掘作為數(shù)據(jù)流挖掘的一個新興研究熱點，挖掘得到的項集與關(guān)聯(lián)規(guī)則的數(shù)量往往大得驚人，而且難以理解與運用，這就需要一種更先進的數(shù)據(jù)流頻繁項集挖掘技術(shù)的出現(xiàn)。數(shù)據(jù)流頻繁閉合項集挖掘技術(shù)應運而生。 CFI-Stream算法是一種在線挖掘最近的頻繁閉合項集的算法。分析該算法發(fā)現(xiàn)，它存在兩個極其影響算法性能的

2、問題：其一，該算法存在一個很大的性能瓶頸——遞歸調(diào)用Add函數(shù)，并且遞歸的深度和次數(shù)隨著事務長度的增加而呈指數(shù)級增長，這極大地影響了算法的時間和空間復雜度。其二，該算法中對于事務的最大項集及其子集的閉包檢查，每次都是全局遍歷，造成很多不必要的檢查，影響了時間效率。 針對上述兩個方面的問題，本論文提出一種新的頻繁閉合項集挖掘算法，采用有序字典序樹的數(shù)據(jù)結(jié)構(gòu)和差集結(jié)點的形式作為算法的數(shù)據(jù)結(jié)構(gòu)。采用分而治之的策略，對每一個分支進行獨立

3、的挖掘，從一個分支結(jié)束到轉(zhuǎn)向另一個分支時，會根據(jù)兩個分支之間的不同前綴，選擇合適的子集進行遞歸調(diào)用，大大的減少了遞歸的次數(shù)和深度。采用寬度優(yōu)先搜索和深度優(yōu)先搜索相結(jié)合的方法，其中，深度優(yōu)先搜索的策略能夠保證在進行交集運算的同時記住需要進行遞歸調(diào)用的子集，此子集在很大程度上縮短了長度，因為它省去了自根結(jié)點起的所有前綴的項目，只保留差集。實驗表明新的頻繁閉合項集挖掘算法在一定程度上降低了時空復雜度，尤其在稀疏型數(shù)據(jù)集環(huán)境下，該算法所體現(xiàn)的優(yōu)