數(shù)據(jù)流相似性查詢及模式挖掘研究.pdf

1、隨著數(shù)據(jù)挖掘研究領(lǐng)域的不斷拓寬和研究?jī)?nèi)容的不斷深入，人們發(fā)現(xiàn)應(yīng)用中越來(lái)越多的數(shù)據(jù)是以流的形式產(chǎn)生的，例如網(wǎng)絡(luò)流，網(wǎng)頁(yè)點(diǎn)擊流，交通流以及傳感器網(wǎng)絡(luò)數(shù)據(jù)等等。分析和挖掘這類數(shù)據(jù)日益成為一個(gè)熱點(diǎn)問(wèn)題。其中，分析流數(shù)據(jù)間的相似性和模式發(fā)現(xiàn)成為重要的研究?jī)?nèi)容。研究數(shù)據(jù)流的相似性查詢對(duì)于完善數(shù)據(jù)流查詢、改進(jìn)數(shù)據(jù)流系統(tǒng)等都有著重要的應(yīng)用價(jià)值，并且對(duì)于在數(shù)據(jù)流上進(jìn)行分類、聚類等也有著指導(dǎo)意義。當(dāng)前在數(shù)據(jù)流環(huán)境下相似性查詢和模式發(fā)現(xiàn)的研究工作沒(méi)有充分考慮

2、數(shù)據(jù)流數(shù)據(jù)自身的特點(diǎn)，往往假定內(nèi)存空間無(wú)限或者不滿足增量更新。另一方面，據(jù)我們所知，目前還沒(méi)有相關(guān)工作系統(tǒng)地解決相似性查詢的問(wèn)題。
　　 基于此，本文著重研究數(shù)據(jù)流環(huán)境下相似性查詢及模式發(fā)現(xiàn)問(wèn)題，主要包括如下三個(gè)關(guān)鍵方面：
　　 (1)基于Lp距離，提出系統(tǒng)解決數(shù)據(jù)流環(huán)境下相似性查詢的技術(shù)。
　　 在數(shù)據(jù)流環(huán)境下，基于Lp距離函數(shù)，本文系統(tǒng)的提出了一個(gè)解決相似性查詢的框架，用以解決數(shù)據(jù)流環(huán)境下相似性查詢。在充分分

3、析數(shù)據(jù)流數(shù)據(jù)的特點(diǎn)后，提出一種新穎的數(shù)據(jù)結(jié)構(gòu)SDS-Tree(the Same-DirectedSlope Tree)來(lái)分層表示數(shù)據(jù)流對(duì)象，實(shí)現(xiàn)對(duì)原始數(shù)據(jù)流的表示?；贚p距離，本文證明SDS-Tree的有效性，并且進(jìn)一步給出一個(gè)相似性判別中更為有效的粒度?；谟行У腟DS-Tree結(jié)構(gòu)，文章分別給出有效處理單一固定窗口下的相似性查詢算法ASQFSW(Algorithm for SimilarityQueries in Fixed Sl

4、iding Window)以及滑動(dòng)窗口下的增量相似性查詢算法IASQSW(Incremental Algorithm for Similarity Queries in SlidingWindows)。特別，IASQSW算法找到了窗口滑動(dòng)時(shí)數(shù)據(jù)流數(shù)據(jù)變化的一個(gè)上界，根據(jù)該上界，算法只需更新有限的SDS-Tree結(jié)點(diǎn)，就能夠完成窗口滑動(dòng)時(shí)的相似性查詢。詳細(xì)的理論分析以及大量的實(shí)驗(yàn)評(píng)估表明，我們給出的技術(shù)和方法顯著優(yōu)于目前的研究方法。

5、>　　 (2)針對(duì)Lp距離無(wú)法解決時(shí)間彎曲的現(xiàn)象，為提高在數(shù)據(jù)流環(huán)境下相似性查詢的準(zhǔn)確度，提出了基于DTW距離的相似性查詢的技術(shù)。
　　 在數(shù)據(jù)流環(huán)境下，使用Lp距離無(wú)法解決時(shí)間彎曲現(xiàn)象。為提高在一些應(yīng)用場(chǎng)合中相似性匹配的準(zhǔn)確度，基于DTW距離，提出了一個(gè)解決相似性查詢的算法ESDS(Estimating Similarity On Data Streams)。算法根據(jù)數(shù)據(jù)流數(shù)據(jù)的變化特性提出了數(shù)據(jù)分段的思想，每段數(shù)據(jù)僅用三個(gè)

6、數(shù)值(最大值，最小值和差異值)來(lái)表示原始數(shù)據(jù)流的特性。為保證數(shù)據(jù)特征提取的有效性，根據(jù)數(shù)據(jù)變化的規(guī)律，提出了振蕩數(shù)據(jù)的概念，并給出了判斷數(shù)據(jù)流中是否存在振蕩數(shù)據(jù)的算法judgeSurge。為保證對(duì)振蕩數(shù)據(jù)的處理不會(huì)影響到數(shù)據(jù)流的特性，進(jìn)一步提出了有效振蕩和最大有效振蕩幅度的概念，設(shè)計(jì)了求解有效振蕩數(shù)據(jù)的算法judgeValidSurge和求解最大有效振蕩幅度的算法calMaxScope。算法基于特征數(shù)據(jù)，設(shè)計(jì)了新的DTW距離函數(shù)，基于動(dòng)

7、態(tài)規(guī)劃算法，設(shè)計(jì)了在數(shù)據(jù)流環(huán)境下進(jìn)行相似性判別的算法ESDS。詳細(xì)的理論分析以及大量的實(shí)驗(yàn)評(píng)估表明，文章給出的技術(shù)和方法具有很高的準(zhǔn)確度和效率。
　　 (3)針對(duì)Web流數(shù)據(jù)，設(shè)計(jì)了兩個(gè)Web流模式挖掘算法。
　　 數(shù)據(jù)流間的相似性查詢?cè)赪eb數(shù)據(jù)流中有重要的應(yīng)用價(jià)值。文章首先分析了Web流數(shù)據(jù)的特征，然后著重研究了Web流數(shù)據(jù)的模式發(fā)現(xiàn)問(wèn)題。在充分分析經(jīng)典算法WAP-mine的缺陷后，首先針對(duì)WAP樹結(jié)構(gòu)設(shè)計(jì)了一個(gè)自頂

8、向下挖掘的算法TD-WAP-mine。算法避免了在挖掘頻繁模式過(guò)程中每次需要構(gòu)造大量中間數(shù)據(jù)，而直接對(duì)原始的WAP樹進(jìn)行挖掘，節(jié)省了生成中間數(shù)據(jù)的代價(jià)，在支持度比較小或者原始Web流數(shù)據(jù)過(guò)于大的情況下，TD-WAP-mine表現(xiàn)出更好的性能。其次，針對(duì)WAP樹存在數(shù)據(jù)冗余情況，提出了壓縮WAP樹的概念，在不影響挖掘結(jié)構(gòu)的前提下，設(shè)計(jì)了壓縮WAP樹算法，并且直接對(duì)WAP樹投影，設(shè)計(jì)了一個(gè)自頂向下的挖掘算法TAM-WAP，在大規(guī)模實(shí)驗(yàn)集上的