[發明專利]一種基于鏈式可重寫窗口的數據流在線預測方法

在審

• 申請號: 201310229090.7
• 申請日: 2013-06-09
• 公開（公告）號: CN103279679A
• 公開（公告）日: 2013-09-04
• 發明（設計）人: 盧曉偉;張清
• 申請（專利權）人: 浪潮電子信息產業股份有限公司
• 主分類號: G06F19/00
• 分類號: G06F19/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及計算機技術領域,具體地說是一種基于鏈式可重寫窗口的數據流在線預測方法。?

背景技術

數據流處理模型

數據流是連續到達的、潛在無限的數據項的有序序列，這些數據或其摘要信息只能按照順序存取并被讀取一次或有限次。目前，數據流研究領域存在多種數據流模型，不同的數據流模型有不同的適用范圍。根據對數據流的描述方式不同，可將數據流模型分為如下三類：

①?時間序列模型。在時間序列數據流模型中，數據流元素按照下標排序。典型的時間序列數據流模型中數據流元素是形如(時間，元素值)的二元組，時間為離散值并在數據流中按增量排序，例如每分鐘的海股票交易所成交量；

②?現金記錄模型。該數據流模型類似于收款機記錄，數據項值大于等于0，并且數據項只添加不刪除的數據；

③?十字轉門模型。該數據流模型類似于十字轉門，可以隨時進行數據項的動態刪除和插入操作。

本發明中預測算法處理的數據流都是以時間序列模型表示的，因為后面兩種模型表示的數據流都可轉換為時間序列模型。?

由于數據流潛在無限長性，在處理數據流時，并不能將數據流所有數據項作為處理對象，而只能根據需求選取某個時間范圍內數據流元素進行處理。按數據流元素選取的時間范圍的不同，可將數據流模型分為：?

①?滑動窗口模型?；瑒哟翱趯Υ翱谄瘘c和終點都沒有明確給定，只明確給定窗口的長度。窗口保持一定長度在數據流上滑動，處理的數據流范圍就由該窗口確定，隨著窗口的滑動不斷地把得到的結果輸出。滑動窗口的長度既可由一個時間區間確定，也可由窗口所包含數據流元素個數確定；

②?界標模型。界標模型有固定起點，而另一端則隨著數據流新數據項的到達不斷后移，處理的數據流數據范圍從某固定的時間戳到當前時間；

③?快照模型?？煺漳Ｐ陀泄潭ǖ钠瘘c和終點，處理的數據流數據范圍限制在兩個預先設定的時間戳之間。

以上數據流模型只是最基本的數據流模型，隨著對數據流認識的深入，一些新的數據流模型被抽象出來，如分布流模型等等，拓展數據流研究和應用范圍。?

數據流的基本處理技術

由于數據流數據潛在無限長性，而數據流處理系統的內存等計算資源有限，為了盡量減少算法的時間和空間的開銷，現有各種數據挖掘算法都首先應采用一些基本數據流處理技術減少數據流算法處理的數據量。通過對許多數據流挖掘算法的分析，總結了數據流基本處理技術，如下：

?(1)?采樣。采樣是一種使用了很長時間的統計技術，指以一定概率決定數據項是否被處理的過程，是從數據集中抽取部分能代表數據集基本特征的數據樣本。經過采樣處理后，數據流挖掘算法就不需要處理全部數據流元素而是數據流的采樣樣本。采樣處理會引入誤差，雖然在某些情況可確定采樣過程引入誤差的置信區間，但是很多情況下，采樣方法不能得到可靠的近似保障；

(2)?直方圖。直方圖使用分箱近似數據分布，是一種常用的數據歸約形式。直方圖技術是一種將大數據集分割成多個連續不相交的子集，或稱為桶。桶放在水平軸上，而桶的高度(或面積)是桶所代表的值的平均頻率。直方圖可直觀表示大數據集的輪廓，已經使用了一個世紀多，應用比較廣泛。根據桶的劃分不同，直方圖被分為：

①?等寬直方圖：等寬直方圖要求每個桶的寬度區間是一個常數，主要用于數據分布均勻數據集的描述；

②等高直方圖：等高直方圖要求劃分數據集時使每個桶的頻率基本相等；

③?V-最優直方圖：在桶個數給定時，V-最優直方圖具有最小方差。直方圖方差是每個桶代表數據的加權和，其中權等于桶中值的個數；

④?另外還有指數、壓縮等直方圖，其中V-最優直方圖比較精確和實用。對于近似稀疏和稠密數據，以及高傾斜和一致數據，直方圖是高度有效的；

(3)?傅立葉變換和小波技術。這兩種方法都是基于變換，都是通用信號處理技術；?

①?傅立葉變換。傅立葉變換是一種可以保持信號能量的正交變換，可將輸入信號變換成一系列傅立葉系數，并且少數幾個傅立葉系數擁有信號大部分能量，因此選擇少數幾個傅立葉系數可近似還原信號，這樣可用少數幾個傅立葉系數近似表示原信號，減少需要處理數據量，提高計算效率。但傅立葉變換是一種純頻域分析方法，反映的是信號在全局上的整體頻率特征，而不能提供任何局部上的頻域特征；