一種多數(shù)據(jù)流變化趨勢(shì)的同異反分析方法研究.pdf

1、隨著通信技術(shù)和傳感器技術(shù)的高速發(fā)展,在實(shí)時(shí)監(jiān)控和聯(lián)機(jī)分析等應(yīng)用領(lǐng)域產(chǎn)生了大量流數(shù)據(jù)。數(shù)據(jù)流挖掘技術(shù)的研究已成為當(dāng)前國際數(shù)據(jù)庫研究領(lǐng)域的一個(gè)熱點(diǎn)。數(shù)據(jù)流快速、持續(xù)、無限量等特點(diǎn),以及對(duì)數(shù)據(jù)流挖掘算法的單遍掃描、實(shí)時(shí)響應(yīng)等要求,對(duì)數(shù)據(jù)流挖掘技術(shù)的研究帶來了巨大挑戰(zhàn)。趨勢(shì)分析是數(shù)據(jù)流挖掘研究的重要內(nèi)容之一,其目的在于揭示數(shù)據(jù)流隨時(shí)間變化所呈現(xiàn)出的規(guī)律或趨勢(shì),有效的趨勢(shì)挖掘可用于被監(jiān)控對(duì)象的狀態(tài)評(píng)估、早期預(yù)警以及決策支持等。
　　 現(xiàn)有

2、的數(shù)據(jù)流趨勢(shì)分析幾乎都是關(guān)于單條數(shù)據(jù)流的研究內(nèi)容,如趨勢(shì)描述、趨勢(shì)提取和趨勢(shì)預(yù)測(cè)等,而關(guān)于多數(shù)據(jù)流趨勢(shì)分析的研究內(nèi)容并不多見。據(jù)此,本課題引入集對(duì)分析思想,對(duì)多數(shù)據(jù)流的變化趨勢(shì)進(jìn)行同異反分析,其實(shí)質(zhì)是變化趨勢(shì)的比較分析。
　　 本文對(duì)多數(shù)據(jù)流變化趨勢(shì)的同異反分析方法研究包括三個(gè)方面。首先,對(duì)峰值等概念作形式化描述,在此基礎(chǔ)上對(duì)峰值變化情況與原始數(shù)據(jù)變化情況的關(guān)系進(jìn)行研究,進(jìn)而以峰值數(shù)據(jù)作為同異反分析的基礎(chǔ)。其次,對(duì)集對(duì)分析中同、

3、異、反概念作出適合于數(shù)據(jù)流的具體定義,并根據(jù)同、異、反關(guān)系判斷數(shù)據(jù)流所屬的集對(duì)勢(shì)類型,用集對(duì)勢(shì)描述兩數(shù)據(jù)流變化趨勢(shì)之間1與1的關(guān)系,這是多數(shù)據(jù)流變化趨勢(shì)同異反分析方法的核心所在。最后,將具有相同集對(duì)勢(shì)的流構(gòu)成的集合定義為集對(duì)勢(shì)簇,并結(jié)合與集對(duì)勢(shì)簇相關(guān)的一系列概念,用于描述多數(shù)據(jù)流變化趨勢(shì)之間1與n的關(guān)系。
　　 為實(shí)現(xiàn)上述研究,適應(yīng)數(shù)據(jù)流快速處理的要求,本文提出四個(gè)算法。(1)在數(shù)據(jù)采集或預(yù)處理階段,提出用于從原始流中快速提取峰

4、值點(diǎn)序列的算法;(2)提出用于計(jì)算流對(duì)之間的集對(duì)勢(shì)的增量算法,該算法通過判斷基本窗口內(nèi)流之間的同異反關(guān)系實(shí)現(xiàn)集對(duì)勢(shì)的計(jì)算;(3)提出用于計(jì)算極大階強(qiáng)勢(shì)簇的算法,其基本思想是將極大階強(qiáng)勢(shì)簇的計(jì)算歸結(jié)為極大完全子圖的計(jì)算,該算法是對(duì)求解極大完全子圖的已有算法FMCSG的改進(jìn),改進(jìn)后的算法適用于頂點(diǎn)較多的圖的求解,并提高了時(shí)空效率;(4)提出用于計(jì)算極大強(qiáng)勢(shì)頻繁簇的算法,其基本思想是將極大強(qiáng)勢(shì)頻繁簇的計(jì)算歸結(jié)為頂點(diǎn)不變的特殊圖集的公共子圖的計(jì)