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

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

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

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

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

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

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

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

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