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

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

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

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