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

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

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

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