數(shù)據(jù)流容錯挖掘算法研究.pdf

1、容錯數(shù)據(jù)挖掘最早是由C.Yang等人在2001年提出的,其基本思想是通過引入松弛條件、允許挖掘合理范圍內(nèi)的錯配、放松模式間的包含關(guān)系來挖掘真實世界數(shù)據(jù)集中有效的泛化知識,因其廣泛而實際的應(yīng)用前景引起了眾多學(xué)者的極大重視。隨著數(shù)據(jù)流應(yīng)用的不斷增多,研究數(shù)據(jù)流環(huán)境下的容錯挖掘算法受到了越來越多的關(guān)注,傳統(tǒng)基于嚴(yán)格匹配的數(shù)據(jù)挖掘技術(shù)難以實現(xiàn)對數(shù)據(jù)流環(huán)境下的容錯模式進(jìn)行有效挖掘,在這種背景下有必要研究高效的數(shù)據(jù)流容錯挖掘技術(shù)。目前關(guān)于容錯數(shù)據(jù)挖

2、掘的相關(guān)研究主要集中在容錯頻繁模式挖掘和容錯概要數(shù)據(jù)結(jié)構(gòu)構(gòu)造技術(shù)兩個方向。研究數(shù)據(jù)流環(huán)境下容錯挖掘算法的主要挑戰(zhàn)之一是來源于規(guī)模巨大的容錯搜索空間和數(shù)據(jù)流環(huán)境下對挖掘算法復(fù)雜性的嚴(yán)格要求之間的矛盾,構(gòu)造單次掃描、高壓縮的容錯概要數(shù)據(jù)結(jié)構(gòu)和增量的挖掘算法是有效的解決方法。本文將容錯概要數(shù)據(jù)結(jié)構(gòu)構(gòu)造技術(shù)作為研究工作的重點,在此基礎(chǔ)上實現(xiàn)數(shù)據(jù)流環(huán)境下的容錯挖掘算法,并且對相關(guān)的挖掘技術(shù)行了系統(tǒng)地探索。文章主要研究內(nèi)容如下:
　　 構(gòu)造

3、容錯前綴樹形概要數(shù)據(jù)結(jié)構(gòu)DSFT-tree來獲得含有錯配的頻繁項集,通過定義容錯界限來限定容錯程度,進(jìn)而實現(xiàn)可控容錯。利用位向量表達(dá)方法和結(jié)點指針技術(shù)提高容錯概要數(shù)據(jù)結(jié)構(gòu)的構(gòu)造效率。為了避免當(dāng)新的數(shù)據(jù)到達(dá)時樹形概要結(jié)構(gòu)的結(jié)點發(fā)生頻繁的分割、合并和交換計算,利用分支重構(gòu)技術(shù)以路徑為最小計算單位提高DSFT-tree的重構(gòu)效率。實驗結(jié)果表明DSFT-tree算法能夠?qū)哂腥蒎e特性的頻繁項集進(jìn)行高效壓縮,并且算法效率滿足數(shù)據(jù)流環(huán)境下對概要數(shù)據(jù)

4、結(jié)構(gòu)的時間復(fù)雜度和空間復(fù)雜度的要求。
　　 擴展定義容錯Top-K頻繁項集的概念并給出了相關(guān)性質(zhì),實現(xiàn)了數(shù)據(jù)流環(huán)境下的Top-K容錯頻繁模式挖掘算法,并對算法的復(fù)雜性進(jìn)行分析。擴展定義了容錯負(fù)關(guān)聯(lián)規(guī)則并證明了容錯正、負(fù)關(guān)聯(lián)規(guī)則之間的相關(guān)性,利用相關(guān)關(guān)系進(jìn)行冗余模式消解,快速剔除容錯頻繁模式挖掘過程中產(chǎn)生的無效短模式、冗余模式和重復(fù)表達(dá),提高容錯挖掘的有效性。提出容錯搜索空間邊界函數(shù)的形式,采用該方法有效縮小容錯所搜空間規(guī)模。

5、r>　　 相關(guān)研究已經(jīng)證明,通過有限次惰性提升可以構(gòu)造現(xiàn)有的所有小波函數(shù),利用提升小波的這一優(yōu)勢可以根據(jù)原始數(shù)據(jù)流的特性或應(yīng)用背景需要有針對性的構(gòu)造概要數(shù)據(jù)結(jié)構(gòu),使之能夠更好地實現(xiàn)對原始數(shù)據(jù)流的壓縮表達(dá)。提出基于相似性度量和提升小波技術(shù)的通用層次容錯小波概要數(shù)據(jù)結(jié)構(gòu)構(gòu)造算法HLSFTS,當(dāng)容錯等級為零時可以實現(xiàn)對原始數(shù)據(jù)流的無容錯表達(dá)。仿真實驗分析表明本文提出的HLSFTS算法具有容錯程度可控、單次掃描和壓縮率高等特點,是有效地小波概

6、要數(shù)據(jù)結(jié)構(gòu)構(gòu)造方法。
　　 研究基于二層框架的數(shù)據(jù)流容錯聚類算法FTGDStream,采用HLSFTS概要數(shù)據(jù)結(jié)構(gòu)和基于網(wǎng)格密度的聚類算法進(jìn)行數(shù)據(jù)流二層容錯聚類。利用數(shù)據(jù)流二層框架的靈活擴展性,采用HLSFTS概要數(shù)據(jù)結(jié)構(gòu)實現(xiàn)在線過程。基于網(wǎng)格密度的聚類算法能夠聚類任意形狀的數(shù)據(jù),但當(dāng)數(shù)據(jù)量較大的時候,因?qū)⒃紨?shù)據(jù)映射到網(wǎng)格的過程中需要處理的數(shù)據(jù)較多而造成算法效率下降,利用HLSFTS概要數(shù)據(jù)結(jié)構(gòu)的高壓縮特性與基于網(wǎng)格密度的聚類