立即咨詢
您當前的位置:職稱驛站 > 論文 > 科技論文 > 電子技術論文職稱驛站24小時論文發表咨詢熱線:400-680-0558

基于時間序列的數據流可視化算法的實現與改進

職稱驛站所屬分類:電子技術論文發布時間:2019-06-27 10:17:05瀏覽:1

隨著信息技術尤其是物聯網等技術的發展,人們獲取數據的能力也取得了驚人的進展,大量需要處理的數據迅速涌現,形成無法估量的數據量。在源源不斷的數據流總挖掘有價值的信息已成為數據挖掘領域需要面對的新挑戰。

   隨著信息技術尤其是物聯網等技術的發展,人們獲取數據的能力也取得了驚人的進展,大量需要處理的數據迅速涌現,形成無法估量的數據量。在源源不斷的數據流總挖掘有價值的信息已成為數據挖掘領域需要面對的新挑戰。該文對Lucas Lucasa等人提出的時間可視圖思想進行了深入的研究,并逐步提出了兩種具體實現方法,將其應用在基于時間序列的數據流上,把數據流轉化成網絡圖,從而使得可以利用網絡圖的拓撲性質,對數據流做進一步的研究,例如相似性查詢和趨勢預測等。

大數據

  《大數據》編輯方針和業務范圍為:報道大數據技術應用領域中具有前瞻性、獨立性和創新性的產業與技術發展見解;產業的新研究應用成果與發展動態;關鍵技術、熱點的前沿性研究與應用;具有先進性和推廣價值的應用方案等,有效促進我國大數據技術研究與應用的交流,全方位展示我國大數據產業的發展、技術趨勢和創新應用成果,推動大數據產業的發展,使大數據技術真正應用于社會,服務于社會發展。

  1概述

  隨著硬件條件的飛速提升,以及物聯網技術的日新月異,需要處理的數據正以每天數以百萬計甚至沒有上限的速度增長。例如,電信部門的大型交換機每天可以記錄高達幾千萬條的通話記錄,裝有GPS部件的整個傳感器體系每天傳回的海平面高度數據可用TB計算。在這樣大的數據量基數和如此飛速的增長速度之下,如果我們仍然采用傳統數據庫的應用模式來處理數據,這種任務幾乎是不可能完成的。基于此種情況,數據流挖掘應運而生,此種解決方案的最大特點是,待處理的數據是以一種動態、流式的形式出現即數據流(data stream),對于數據流中的數據,我們只能按順序進行一次或有限次的訪問。目前,數據流尤其是數據流挖掘已成為業界研究熱點之一。

  2相關概念

  2.1數據流

  數據流就是數據量非常大的能夠持續到達的、潛在無限的大數據的有序序列。相對于傳統數據庫中的靜態數據,數據流有其特殊的特點:時效性、實時性、無限性和瞬時性等。所以,我們在對數據流做處理時,尤其要注意在時空上的限制,通常采用單一掃描的線性算法處理數據流中的數據,該算法中心思想是用精度換取時間,盡量一次性訪問數據即可獲得較優解和有價值信息。總而言之,數據流的處理算法對時間和空間復雜度都有很高的要求,本文將針對數據流下一個滑動窗口內的數據集或在流中隨機選取的數據集的處理算法的時空復雜度進行重點討論。

  2.2數據流挖掘研究現狀

  目前,在數據流挖掘方面成果顯著的主要有:數據流聚類、分類和頻繁模式挖掘。至今在數據流的可視化圖領域研究及成果并不顯著,在該領域進行深入研究將是一個新的突破點。

  2.2.1數據流聚類算法研究

  數據流可看作一個隨時間的進行而不斷變化的無限過程,其隱含的聚類可能隨著時間的動態變化而導致聚類質量降低。最近幾年以來,有眾多的學者對大規模數據集應用了一趟聚類算法,如Squeezer算法和BIRGH算法,這些算法也是可以應用于相應的數據流問題上,也有不少的學者針對數據的聚類提出相應的算法,典型的有STREAM算法和CluStream算法。

  2.2.2數據流分類挖掘算法研究

  在數據流分類方面成果顯著的主要是P.Domingos和G.Hulten的研究。在文獻中提出了一種改進的Hoeffding決策樹分類算法VFDT(Very Fast Decision Tree),這種算法類似于大多數的機器學習方案,同樣都是假設數據是從靜態分布中隨機獲取的,不能反映數據隨時間變化的趨勢。因此,P.Domingos和G.Huhen在研究中加入了滑動窗口技術,對VFDT算法進行了改進,提出了CVFDT(Concept-adapting Very Fast DecisionTree)算法,該算法僅保留了VFDT算法在速度和精度方面的優點,對數據產生過程中變化趨勢的檢測和響應做了改進,使得算法能夠更好地適應對高速時變流數據的分類。

  2.2.3數據流頻繁模式挖掘算法研究

  針對數據流的頻繁模式挖掘,文獻提出了基于FP-tree模型的有效算法FP-stream,該算法采用傾斜時間窗口技術維護頻繁模式用以解決時間敏感的問題。文獻提出了一種利用有限存儲空間通過一趟掃描來估計數據流中最大頻繁項集的算法,該算法采用了稱為“COUNT SKETCH”的數據結構,使其可以在流中對頻繁項集的頻率進行可靠的估計。

  2.3時間序列數據流

  要對數據流進行挖掘,首先要了解數據流模型刪。數據流D可看作是由連續不斷地到達的數據組成的動態增長的數據集,即D={a1,a2,…,ai,…,aj,…},其中ai為數據,如果j>i,則ai先于aj,到達;如果|j-i|=1,則ai與aj相鄰。根據ai的描述的不同,數據流模型可以分為以下3類:

  (1)時間序列數據流。用其來描述時間序列的數據。這里的ai可以定義為:ai=(i,Ii)其中,Ii為i時刻產生的數據。

  (2)Cash Register數據流。該模型應用較為普遍。這里的ai可以定義為:ai=(j,Ii)其中,Ii>=0為新產生的數據,很顯然有:ai[j]=ai-1[j],Ii。此時數據流中的多個數據項增量式的表達一個a[j]。

  (3)Turnstile數據流。這種模型可以記錄動態的插入和刪除操作。這里的ai可以定義為:ai=(j,Ui)其中,Ui可以大于0,也可以小于0,很顯然有a[j]=ai-1[j],Ui。此時,數據流中的多個數據項表達一個a[j].a[j]隨著數據的流入,可能會增加,也可能會減小。

  本文重點研究第一種數據流模型,即時間序列數據流模型的可視化,以下簡稱時間序列。

  2.4時間序列

  為了便于下面的描述和使用,這里對時間序列重新進行以下定義:數據流下的時間序列總是持續不斷的,為了便于分析我們把數據固定在一個滑動窗口內或者一個隨機選取的樣本數據集上,這樣可以把時間序列看成某一個時刻數據流的靜止狀態,然后對其進行快速處理以便于后續的分析工作。這樣的時間序列是由實數值和時間的二元對組成的有序集合,記為X={(xl,tl),(x2,t2),…,(xn,tn)},元素(xi,ti)表示時間序列在ti時刻的實數值為xi,且ti是嚴格遞增的。

  一般情況下,時間序列的時間間隔△t=ti-ti-1相等,可以看作tl=l,△t=1,此時時間序列可以簡記為X={x1,x2,…,xn},長度為n的時間序列X可以看作n維空間上的一個點。

  3時間序列的表示方法

  目前比較成熟的時間序列的表示方法有:離散傅里葉變換(Discrete Fourier Transform,DFT)、離散小波變換(DiscreteWavelet Transform,DWT)、分段線性表示((Piecewise LinearRepreseutation,PLR)、分段聚合近似(Piecewise Aggregate Ap-proximation,PAA)。

  4時間序列的可視化表示方法

  4.1可視化思想

  Lucas Lucasa等人在2008年提出了一種可視化思想,將時間序列轉化成一個無向網絡。這個網絡繼承了時間序列的屬性,將對時間序列的分析轉化成對網絡圖的分析。

  如圖1上半部分,在柱狀圖中給出了周期性時間序列的前二十個值,對應的數據值在柱狀圖上面給出。然后把它看作是一個地形,我們認為在一個柱的頂端能夠看到的其他柱之間是可連的,這樣就得到了一個連通圖。在這個圖中,經分析可知,相鄰的點一定可見,所以任意兩點之間都是經過一定的路徑連通的,如果兩個數據能夠連通,則這兩個數據的連線不能切斷任意其他兩個數據的連線。

  我們把這個思想加以推廣,然后將一系列的描述轉化成數學公式,可以得到如下的可視化標準:任意的兩個數據(xa,ta)和(xb,tb),對于位于他們中間的任一其他數據(xc,tc)滿足:

  4.2可視化實現算法之一VG(Visibility Graph)

  可視化思想中一個重點之處就在于它將時間序列的柱狀圖看成一個地形圖,用地形的高低起伏的觀點來看待問題,因為數據流時效性強,前面一直強調的問題就是我們在處理數據流數據時所用的算法時間復雜度一定要低,這樣我們就會考慮到,從第一個數據開始,它有可能看到的數據只能是從這個數據開始往后小于等于它的數據,如果遇到一個大于等于它的數據,就會對后面的數據有所遮擋,因此我們可以將所有的數據按照大小分段以后,再在段內利用以上斜率公式計算出兩點之間是否可連,這樣就不用計算任意兩個數據之間是否可連,只需計算一定范圍內有可能可連的那些點即可。這個思路存在一個問題,就是對于前面的數據來說,它看不到大于等于它的后面的數據,由于我們所轉化的網絡圖是無向的,所以后面可能會有某個值很大的數據能夠看見它。因此在此算法的結尾,我們將整個時間序列倒置,再進行一遍算法。如果數據集很大的話,即使這樣我們仍然覺得這個算法的計算量很合理,因為它不必計算任意兩對節點,會盡可能地節省一些時間。但是與此同時,它的空間復雜度會增加。具體算法步驟如下:

  %然后對X進行與Y相同的操作,篇幅有限,在此不一一贅述

  4.3可視化實現算法之二NVG(New Visibility Graph)

  忽視任何分段,直接利用斜率公式計算任意兩點之間是否相連,省去了最外面的兩層循環。這樣得出的算法看起來步驟簡單多了,由于少了循環的嵌套,我們可以推斷其空間復雜度明顯低于VG,但是我們仍然認為它的計算量是個可觀的數目,因此繼續對這兩個算法進行試驗比較。具體算法步驟如下:

  4.4實驗對比

  為了將問題盡量簡化,這里采用隨機序列進行試驗來比較兩種實現方法。最終得出如下的折線圖。從圖中可以明顯地看出幾乎在每個數據集下,NVG的時間復雜度都優于VG,并且比VG更加穩定。接下來我們將使用NVG方法對不同的序列進行轉化,并進一步分析。

  如下圖我們給出了實驗中選取的一部分隨機序列及其對應的隨機序列數據集的度分布。

  5通過網絡拓撲性質分析時間序列

  根據所得的無向網絡圖,我們可以得一些網絡拓撲性質,例如節點的度、網絡平均度、平均路徑長度、聚類系數和度分布等。這里我們以度分布為例,進行簡要分析。下面分別給出海浪高度時間序列、沿海海平面時間序列、布朗運動(Brown Motion)、康威運動(ConwaySeries)的時間變化曲線和其利用VG轉化成的網絡的度分布。

  從上圖我們可以看出不同的時間序列對應的網絡度分布不盡相同,它在一定程度上反映了不同時間序列之間的差異。但是如果仔細觀察2、3兩幅圖的話我們可以看出來他們之間比其他兩幅圖相似性更大,如果進一步分析的話我們可以得知布朗運動的度分布其實是滿足P(k)~k-α冪律分布的,通過進行冪律擬合甚至可以得到α的值,而1、4兩幅圖又滿足什么樣的規律呢,有待于進一步研究。

  6總結與展望

  雖然給出了時間序列轉化成網絡的方法但是主要的思想還是要研究用這個方法基于圖論對時間序列進行分析的可行性達到了一個什么樣的程度。通過上文不難看出,周期性的序列轉化成了規則的圖,隨機序列轉化成隨機圖,不規則序列轉化成了無標度網絡。文中給出的轉化方法只是針對無向無權重的網絡來進行的,如果換成有向網絡又該如何定義,權重大小又該如何取舍,這都將是接下來的研究重點。

  另外,前面已經指出時間序列僅僅是數據流模型的一種,這一方法是否適用于其他幾種模型還有待于進一步研究,總之,這一可視化思想為數據流挖掘研究提供了新的思想,開拓了新的領域。

《基于時間序列的數據流可視化算法的實現與改進》
  • 課教專著
  • 1
  • 2
  • 3
'); })(); 水果机在线客服