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

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

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

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

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

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

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