1、數(shù)據(jù)流是近年來產(chǎn)生的一種新型數(shù)據(jù)模型，廣泛出現(xiàn)在多種應(yīng)用領(lǐng)域，如Web點(diǎn)擊流分析、交通流量監(jiān)控與管理、電力供應(yīng)管理與預(yù)測(cè)、傳感器網(wǎng)絡(luò)數(shù)據(jù)分析、電信數(shù)據(jù)管理、金融服務(wù)、商業(yè)交易管理和分析等。數(shù)據(jù)流模型不同于傳統(tǒng)的數(shù)據(jù)庫模型，具有快速、實(shí)時(shí)、連續(xù)、無界等特點(diǎn)，由此決定了數(shù)據(jù)流的查詢或挖掘算法與基于傳統(tǒng)的數(shù)據(jù)庫的挖掘技術(shù)有顯著的區(qū)別，其算法應(yīng)是單遍掃描（one-pass）的。由于存貯容量的有限性，不可能完整地保存全部數(shù)據(jù)流元素。一種有效的方法

2、是設(shè)計(jì)一個(gè)遠(yuǎn)小于原數(shù)據(jù)流規(guī)模的結(jié)構(gòu)，保存已流過數(shù)據(jù)的概要特征，用于數(shù)據(jù)流的查詢處理及分析，因而挖掘結(jié)果通常是近似的。鑒于數(shù)據(jù)流的高速性和連續(xù)性，數(shù)據(jù)流算法應(yīng)是動(dòng)態(tài)增量的，亦必須是高時(shí)空效率的?，F(xiàn)有的數(shù)據(jù)庫挖掘技術(shù)已不再適合數(shù)據(jù)流環(huán)境。因此，流數(shù)據(jù)環(huán)境下的數(shù)據(jù)挖掘研究具有更大的機(jī)遇和挑戰(zhàn)性。 論文針對(duì)數(shù)據(jù)流挖掘分析處理中的幾個(gè)基本問題進(jìn)行了探討和研究，主要內(nèi)容如下： 1．動(dòng)態(tài)增量地挖掘數(shù)據(jù)流界標(biāo)窗口的top-K頻繁模式。挖

3、掘top-K頻繁模式在現(xiàn)實(shí)生活中有重要應(yīng)用，為此我們研究有效算法TOPSIL-Miner動(dòng)態(tài)增量地挖掘數(shù)據(jù)流界標(biāo)窗口的top-K頻繁模式。設(shè)計(jì)了存儲(chǔ)流數(shù)據(jù)摘要信息的概要結(jié)構(gòu)TOPSIL-Tree以及動(dòng)態(tài)記錄挖掘相關(guān)信息的樹層最大支持度表MaxSL、項(xiàng)目序表OIL、候選結(jié)果集TOPSET和最小支持度表MinSL等概要結(jié)構(gòu)，并分析了與這些數(shù)據(jù)結(jié)構(gòu)相關(guān)的挖掘特性，在此基礎(chǔ)上研究挖掘算法的若干優(yōu)化措施。并對(duì)算法的誤差上界進(jìn)行了理論分析研究。算法

4、具有較高的時(shí)空效率和精確度。 2．高效挖掘數(shù)據(jù)流滑動(dòng)窗口top-K頻繁Ⅳ模式集?；瑒?dòng)窗口模型因其更關(guān)注最近到達(dá)的流數(shù)據(jù)，所以有很高的實(shí)用價(jià)值。在基于滑動(dòng)窗口的數(shù)據(jù)流挖掘分析中，不但要及時(shí)地增量地處理源源不斷到來的流數(shù)據(jù)，而且還要考慮過期數(shù)據(jù)的處理，因而比基于界標(biāo)窗口的挖掘技術(shù)具有更大的挑戰(zhàn)性。提出了有效挖掘數(shù)據(jù)流滑動(dòng)窗口top-K頻繁N模式集的近似算法TOPSIS。采用批處理的方法，將滑動(dòng)窗口劃分為若干基本窗口作為處理單元。設(shè)計(jì)

5、概要結(jié)構(gòu)TOPSIS-Tree和RELIS分別存儲(chǔ)和記錄流數(shù)據(jù)的摘要信息和當(dāng)前滑動(dòng)窗口的挖掘結(jié)果，并設(shè)計(jì)了三種優(yōu)化策略用以提高算法的時(shí)空效率：（1）滑動(dòng)窗口更新時(shí)剪枝最新基本窗口的無功節(jié)點(diǎn)；（2）挖掘過程中動(dòng)態(tài)提升支持度閾值；（3）啟發(fā)式自適應(yīng)調(diào)整剪枝閾值。同時(shí)，對(duì)算法在挖掘頻繁模式產(chǎn)生的支持度誤差進(jìn)行了理論分析。算法具有較好的適應(yīng)性和可伸縮性，用戶可以根據(jù)需要，通過調(diào)整功用參數(shù)在執(zhí)行效率和結(jié)果精度方面取得均衡。 3．有效挖掘數(shù)

6、據(jù)流滑動(dòng)窗口top-K閉合頻繁模式。閉合頻繁模式是頻繁模式的精確簡潔表示，能夠唯一地確定所有的頻繁模式及其支持度，并且在數(shù)目上往往比頻繁模式小幾個(gè)數(shù)量級(jí)。研究了一種有效挖掘數(shù)據(jù)流滑動(dòng)窗口top-K閉合頻繁模式的近似算法TCIS。設(shè)計(jì)了一種新的壓縮前綴擴(kuò)展樹結(jié)構(gòu)TCIS-Tree，該結(jié)構(gòu)不僅存儲(chǔ)當(dāng)前滑動(dòng)窗口的概要數(shù)據(jù)信息，而且還記錄了業(yè)已發(fā)現(xiàn)的候選閉合模式信息。在TCIS-Tree的更新和挖掘過程中，采用數(shù)據(jù)過濾、啟發(fā)式動(dòng)態(tài)調(diào)整剪枝閾值、

7、挖掘閾值等若干優(yōu)化措施，有效地提高算法的時(shí)空效率。結(jié)合TCIS-Tree采用一種二級(jí)哈希結(jié)構(gòu)快速地進(jìn)行模式的閉合性判別。有效地實(shí)現(xiàn)了滑動(dòng)窗口top-K閉合模式的挖掘。 4．?dāng)?shù)據(jù)流分位數(shù)查詢。分位數(shù)是數(shù)據(jù)集合的一個(gè)重要統(tǒng)計(jì)量。設(shè)計(jì)了一個(gè)基于規(guī)范數(shù)直方圖的概要結(jié)構(gòu)——Nord Histogram，并在此基礎(chǔ)上實(shí)現(xiàn)了數(shù)據(jù)流分位數(shù)查詢的單遍掃描近似算法NORMAL，其時(shí)間和空間復(fù)雜度均線性于概要結(jié)構(gòu)中桶的個(gè)數(shù)，與數(shù)據(jù)流的長度無關(guān)，因而具