北京林業(yè)大學 信息學院，北京 100083

北京林業(yè)大學 信息學院，北京 100083

1 引言

數據流數據的處理近年來得到越來越廣泛的重視，其原因在于，隨著網絡技術的發(fā)展，在電子商務，網絡監(jiān)控，證券股票、無線通信網等等，數據流成為一種較為普遍的信息傳送方式。數據流是一組順序、大量、快速、連續(xù)到達的數據序列，是一種特殊的數據類型。由于數據流是連續(xù)到達且具有無限性，有限的處理機不可能保存數據的全部信息。另一方面，對于某些系統(tǒng)，比如對于設備或場景監(jiān)控的應用，這類數據往往呈現(xiàn)多點并發(fā)，流量巨大等特點，而且數據流的信息中往往含有大量的冗余，可能大多數情況下時間序列中的數據是有很強的關聯(lián)性的，甚至是相等的[1]。在保證數據精度的情況下，采用正確的方法對數據流進行描述，不僅是發(fā)現(xiàn)數據關聯(lián)的有效途徑，對于壓縮數據量，減少系統(tǒng)存儲壓力，加快數據查詢速度，也具有重要的意義。

目前，對于流數據處理普遍的做法是在存儲器中開辟一個滑動窗口來保存近期到達的數據流數據，以實時地支持查詢請求。隨著數據流不斷地流入滑動窗口，當滑動窗口數據已滿時，將會有部分舊數據從滑動窗口中流出。流出滑動窗口的這部分數據稱為歷史數據?；跀祿鳉v史數據的壓縮處理算法已經有了一些研究結果。這些研究方法都是基于抽樣的，但是在很多情況下，常常需要保存連續(xù)的數據[2]。因此，抽樣的方法并不能滿足這種需求。

工業(yè)上處理數據流的壓縮算法主要有旋轉門壓縮算法和死區(qū)限值壓縮算法。旋轉門壓縮算法是美國OSI軟件公司開發(fā)的PI實時數據庫系統(tǒng)（Plant Information System）采用的專利壓縮技術。旋轉門壓縮算法保存的是實際的數據，因此，要獲得數據的趨勢還必須經過二次處理才能得到。其次，旋轉門壓縮算法摒棄了一些數據，當這些數據需要恢復時，可能會遇到困難。死區(qū)限制壓縮算法僅僅保留大于死區(qū)限值的值，小于死區(qū)限值的值將會被舍棄，因此數據精度得不到保證。

針對以上算法的缺點，本文采用加權分段曲線擬合的方式對數據流歷史數據進行壓縮處理，同時采用k-means聚類算法對擬合結果進行聚類處理，找出數據的規(guī)律，并根據聚類的結果采用選擇合適窗口進行數據處理。這樣既實現(xiàn)了數據的壓縮處理，又可以隨時恢復壓縮的數據，并且擬合的結果可以作數據流的函數表達式，具有良好的優(yōu)點。本文最后通過實驗，分別對加權分段曲線擬合算法的擬合精度，壓縮率和實用性進行了測試，證明了算法的有效性。

2 加權最小二乘法曲線擬合

數據流是一組順序、大量、快速、連續(xù)到達的數據序列，與時間密切相關?？梢詫祿饕暈闊o限多重集合，集合中每個元素具有形式，其中s是一個元組，t為標識s的時間戳，t的取值可以是s進入數據流系統(tǒng)的時間或者數據源產生s的時間。將元組中的一維數據與時間取出來單獨考慮，則數據流是一個關于時間t的函數。因此可以采用曲線擬合的方法對數據流進行處理。

的求解方法。則根據不同的定義方法，則可能求解出無數條擬合曲線。對于求解出來的擬合曲線，并不要求其經過實驗數據中的每個數據點，而是希望曲線 y=φ(x)盡可能地靠近數據點，并且靠近的個數最多。設根據φ(x)算出第i點的函數值與實際值的誤差為εi：

最小二乘法曲線擬合是以“方差最小”為判斷依據的曲線擬合方法，即

為最小。

在實際的應用中，并不是所有數據點的重要性都一樣，特別是曲線有突變的情況下，此時突變點的數據就顯得很重要。所以應對不同的數據點賦予不同的權值，重要的數據點賦予較大的權值，一般的數據點則賦予較小的權值。這種帶有權值的最小二乘法曲線擬合就是加權最小二乘法曲線擬合。加權最小二乘法曲線擬合函數是關于x的n次多項式：

它的系數可通過求解正規(guī)方程組得到。設權值為w，則相應的正規(guī)方程組為：

對于曲線擬合來說，除了要獲得擬合結果外，還需要對曲線擬合的結果進行精度的控制，即εi不能太大。根據文獻[3]，知道對于曲線擬合的精度與以下三個方面有關：分段擬合的段數、曲線擬合的階數以及數據點權值的分布。因此，為了獲得良好的精度，應當采用綜合各個因數進行分段擬合的方式。擬合的段數越多，在同一段中采用的擬合階數越高，段中數據點的權值分布越合理，則擬合精度越高。變階加權分段方式可以自動獲取最合適的數據點對數據流進行分段，并對分段后的數據采用合適的階數進行擬合，具有良好的性能。因此，本文采用變階加權分段方式對數據進行最小二乘曲線擬合，以提高曲線擬合的精度。

在曲線擬合的過程中，擬合窗口選擇越大，則數據處理的時間越長，擬合精度也會下降。但如果窗口選擇的長度過短則不能有效地把握數據流的趨勢。所以，采用合適的窗口大小可以降低數據處理的時間，其次可以根據數據的特點采用合適的分段對數據進行擬合，提高了數據擬合的精度。文獻[4]介紹了一種結合兩種方式的特點的窗口選擇方案，具有較好的性能。因此本文的窗口設置采用這種方式，即設定一個標準的數據窗口作為擬合處理的最小長度，同時設置一個較大的數據窗口作為擬合處理的極限長度。處理的過程如下：

（1）接受數據的流入，當數據的長度大于標準長度時，對數據進行曲線擬合，并求出擬合的最大誤差。

（2）若最大誤差小于設定的最大誤差限，則繼續(xù)接受數據，重復（1）步驟。否則，以最大誤差點作為數據分段點，對分段點前的數據擬合，將擬合結果保存；對分段點后的數據作為新的處理起點。

（3）當數據的長度大于極限長度時，對數據擬合，并將擬合結果保存，同時將下次讀入的數據作為新的處理起點，重復（1）步驟。

3 k-means聚類算法

聚類是一種將給定數據集按照一定的方式劃分成若干組或若干類的過程，使得同一類中的數據具有較高的相似性，而不同類的數據的相似性較低。采用聚類算法可以發(fā)現(xiàn)數據間內在的規(guī)律，為數據處理提供決策依據[5]。本文采用k-means聚類算法對擬合的結果進行聚類分析，獲得數據的內在規(guī)律。

k-means聚類算法的處理思路是給定一個數據樣本，用戶輸入要獲得聚類簇的個數k，將數據劃分為k個部分，然后通過更新簇的中心來調整劃分，當整體差異函數收斂的時候結束處理過程。聚類之間的差別是簇中心的表示方法，劃分調整策略和整體差異函數的定義。k-means聚類算法的處理流程如下：

（1）在樣本中任意選擇k個數據作為初始聚類中心。

（2）計算每個數據到這些聚類中心的距離，并根據最小距離對數據進行重新劃分。

（3）重新計算每個聚類的中心。

（4）循環(huán)第（2），（3）步直至聚類不再發(fā)生變化。

本文采用k-means聚類算法的目的是尋找數據流的規(guī)律，即通過對曲線擬合結果進行聚類，找出數據的周期。由于k-means聚類算法需要預先給定聚類的個數k并且對初值較為敏感，而對于數據流來說，并不知道給定的數據集劃分成幾個類別才合適，因此本文對k-means聚類算法作了一下改進，來滿足數據流的需要。具體做法是通過設定合適的初始距離來設定初始聚類中心，處理流程如下：

（1）設定初始距離。

（2）計算新數據到每個聚類中心的距離，若最小距離大于初始距離，則新數據為新聚類的中心，否則根據最小距離對數據進行劃分。

（3）重新計算每個聚類的中心。

（4）循環(huán)第（2），（3）步直至聚類不再發(fā)生變化。

（5）循環(huán)第（2）～（4）步直至數據全部處理完。

聚類算法處理需要大量的數據，所以，可以將數據緩存一段時間，待數據足夠多時，才采用算法進行處理。數據到聚類中心的距離為數據到聚類均值的歐氏距離。

4 原型實現(xiàn)

為了將數據流歷史數據合理地壓縮，同時最大限度地保留數據流的所有信息，本文通過實驗，找到了比較合理的算法：分段加權曲線擬合算法。首先采用加權分段曲線擬合算法對流數據進行擬合處理。同時采用k-means聚類算法對處理結果進行聚類分析，找出數據流的規(guī)律。若數據流是有規(guī)律的，則通過求出數據流的周期，然后采用合適的長度對數據進行擬合，并保存擬合結果。若數據流是沒有規(guī)律的，則加權分段曲線擬合處理結果也可以直接保存。

本文采用的方法如下：

（1）接受數據，采用加權分段曲線擬合算法對數據進行曲線擬合。

（2）當擬合結束時，求出最大擬合誤差。

（3）若最大擬合誤差大于閾值，則最大誤差數據的權值加1；否則，繼續(xù)接受數據進行擬合。

（4）若權值大于或等于最大權值，則將擬合階數加1；若擬合階數大于最大擬合階數，則以最大誤差點作為分段點。

（5）對分段的數據采用合適的階數進行曲線擬合，并將擬合結果保存。

（6）若臨時表中的數據大于最大個數，則將臨時表的數據進行曲線擬合，并將擬合結果保存。

（7）當擬合的結果足夠多時，采用k-means聚類算法對擬合結果中的參數進行聚類分析。

（8）若聚類分析結束后，聚類結果穩(wěn)定，則采用合適的長度對數據擬合，保存擬合結果。

下面給出了主要算法的描述，以下將以偽代碼的形式對本文的方法進行描述。具體偽代碼如下：

本文用聚類算法對擬合結果進行分析處理，主要是根據擬合的結果找出數據的規(guī)律，即找出數據的周期。假如數據是有周期的，則可以求出最佳的數據長度。將最佳數據長度設置為擬合窗口的長度，對數據進行擬合處理，得出的擬合結果，然后根據擬合結果對數據進行處理。

5 實驗及分析

為驗證文中方法的有效性，本文搭建了一個測試平臺對文中的方法進行了測試。測試平臺的硬件環(huán)境為Pentium?4 CPU 3.00 GHz 2.00 GB內存，軟件環(huán)境為Window XP下的Microsoft Visual Studio 2005及Microsoft SQL Server 2005。實驗數據集為采集的一類地理信息數據。

實驗1算法擬合精度驗證。采用變階加權分段曲線擬合算法對樣本數據進行測試。讀取的樣本數據為34個，最大誤差限設置為0.001，標準窗口大小設置為10，最大數據窗口大小設置為20，最大權值設為10，最大擬合階數設為3。擬合結果共分為4段，其中三階多項式的為3段，二階多項式的為1段，具體結果如下：

曲線擬合結果和原始數據的對比圖如圖1所示。

利用擬合后得到的結果，將原始數據還原。將還原的數據與原始數據對比，對比圖如圖1所示。從擬合結果上看，大部分數據都得到了很好的擬合，少部分數據出現(xiàn)了一些誤差，最大誤差出現(xiàn)在第26點，誤差為0.000 904 2，小于最大誤差限。對于數據流來說，已滿足數據處理精度的要求。

實驗2算法的壓縮效率驗證。本實驗采用的測試樣本數據大小為48.5 kb，分別采用加權分段曲線擬合壓縮算法和旋轉門壓縮算法對測試樣本進行壓縮，算法的數據精度設定為0.003。其中，旋轉門壓縮算法的存儲字段為序號（No），系統(tǒng)編號（SystemId），時間（Time），數據值（Data）。加權分段曲線擬合壓縮算法的參數設置為，最大權值為5，最大階數為4，標準窗口設置為15，最大窗口設置為20。存儲的字段為序號（No），系統(tǒng)編號（SystemId），開始時間（StartTime），參數 1（A0），參數2（A1），參數3（A2），參數4（A3），參數5（A4），擬合個數（Num）。壓縮結果如表1所示。

表1 兩種算法壓縮對比

從處理結果上看，采用合適的階數，合適的窗口大小，在同樣的壓縮精度下，加權分段曲線擬合壓縮算法壓縮率要比旋轉門壓縮算法高。由于本文方法的參數存儲較多，所以，在復雜變化，規(guī)模較大的數據描述中，才能更加體現(xiàn)優(yōu)勢。

實驗3對有一定周期性數據的處理。采用的樣本數據具有一定的周期性，大小為22.8 kb。樣本數據的散點圖如圖2所示。旋轉門壓縮算法的存儲字段為序號（No），系統(tǒng)編號（SystemId），時間（Time），數據值（Data）。本文算法的參數設置為：最大權值為10，最大階數為4，標準窗口設置為20，最大窗口設置為30。存儲的字段為序號（No），系統(tǒng)編號（SystemId），開始時間（StartTime），參數1（A0），參數 2（A1），參數 3（A2），參數4（A3），參數5（A4），擬合個數（Num）。

圖1 曲線擬合對比圖

圖2 聚類數據源散點圖

加權分段曲線擬合后數據共分為20段，聚類的初始距離設為0.003，聚類結果共分為2類，每類的段數為：10，10。通過計算得到數據的周期為40。壓縮數據精度設置為0.003，分別采用旋轉門壓縮算法，不考慮聚類時的本文算法及考慮聚類時的本文方法對數據壓縮處理，處理結果如表2所示。從處理結果上看，考慮聚類時本文方法的壓縮率要比旋轉門壓縮算法及不考慮聚類時本文算法的壓縮率要高。

表2 3種不同方法壓縮率比較

6 結論

本文提出了一種新的存儲數據流的處理方法。通過實驗1，采用變階加權分段曲線擬合算法對擬合精度進行了驗證。實驗2通過對比采用加權分段曲線擬合壓縮算法和旋轉門壓縮算法來驗證了本文算法的壓縮效率。實驗3中加入了周期數據的因素，考慮到了聚類，并對測試數據進行實驗對比，得出聚類對周期數據壓縮效率有所提高的結論。綜上，從實驗結果來看，通過設置合適的參數，在同樣的壓縮精度下，加權分段最小二乘算法曲線擬合具有很好的擬合精度及壓縮率。若同時采用k-means聚類算法，并且處理的數據是周期性時，數據壓縮效果將會更加顯著。由于存儲的是數據流的曲線擬合結果，所以可以獲得數據流的規(guī)律，解決了抽樣方法不能有效獲得數據流規(guī)律的問題。通過采用加權最小二乘法對緩存數據流進行分段曲線擬合，并結合聚類算法進行分析處理，可以很好地實現(xiàn)數據的壓縮存儲。

本文提出的方法具有較好的可行性。在現(xiàn)實處理中，數據流的數據可能是周期性的，也可能是非周期性的。對于周期性的數據，本文方法只存儲少量的數據，與實際相符。對于非周期的數據，本文方法擬合的結果可以直接作為壓縮結果保存，避免了再次壓縮處理。但本文也有不足的地方，如方法只能擬合一維數據；曲線擬合的階數，窗口大小等參數需要設置恰當，才能得到較好的壓縮率；聚類算法中的初始距離需要人為設定，對于不熟悉數據特性的人員來說，聚類的結果可能得不到理想的數據。這些也是本文以后需要努力改進的地方。

[1]Saito T，Kida T，Arimura H.An efficient algorithm for complex pattern matching over continuous data streams based on bit-parallel method[C]//IEEE International Workshop on Databases for Next Generation Researchers.[S.l.]：IEEE Press，2007：13-18.

[2]Parpinelli R S.Data mining with an ant colony optimization algorithm[J].IEEE Transactions on Evolutionary Computation，2002，6（4）：321-322.

[3]Bristol E H.Swinging door trending：adaptive trend recording[C]// ISA National Conference Proceedings，1990：749-754.

[4]Araru A，Babu S，Widom J.An abstract semantics and concrete language for continuous queries over and relations[EB/OL]. [2011-04-12].http：//dbpubs.Stanford.edu/pub/2002-57.

[5]Kang J，Naughton J，Viglas S.Evaluating window joins over unbounded stream[C]//The 19th Int’l Conf on Data Engineering，Bangalore，India，2003.

[6]Golab L，Ozsu M T.Processing sliding window multi-joins in continuous queries overdata streams，Tech Rep：CS-2003-01[R].[S.l.]：Waterloo University，2003.

[7]Zhu Y，Shasha D.StatStream：statistical monitoring of thousands of data streams in real time[C]//The 28th Int’l Conf on Very Large Data Bases.Hong Kong：[s.n.]，2002.

[8]Datar M，Gionis A，Indyk P，et al.Maintaining stream statistics over sliding windows[C]//The 13th Annual ACM SIAM Symp on DiscreteAlgorithms，San Francisco，California，2002.

[9]Ziv J，Lempel A.A universal algorithm for sequential data compression[J].IEEE Transactionson Information Theory，1977，23（3）：337-343.

一種新的數據流在線壓縮存儲方法

馮秀蘭，張 帆

FENG Xiulan,ZHANG Fan

School of Infomation Science and Technology,Beijing Forestry University,Beijing 100083,China

The sampling storage method which is used in the current data stream ignores the historical data for the analysis of data stream processing and storage management issues.For the problem,this paper presents a new processing method based on curve fitting.A weighted least-square principle is used to fit the cached stream data and better model description is obtained.The fitting results are analyzed by clustering algorithm,which serves as a classifier for polynomial fitting parameters.According to the clustering result,the appropriate window size will be given to fit the periodic stream data.Comparing the forecast result with the actual data,different methods are adopted to store data according to the comparison result.The experimental results indicate that the proposed method has good performance,can meet different processing requirements.

curve fitting;data stream;clustering algorithm;least-square principle

針對當前數據流采用的抽樣存儲方法忽略了對數據流歷史數據的分析處理與存儲管理的問題，提出一種新的存儲數據流的方法。在滿足數據精度的情況下，采用加權最小二乘法對緩存數據流進行分段曲線擬合，對擬合結果進行聚類分析。根據聚類分析結果，采用合適的窗口對數據進行分段曲線擬合，利用擬合結果預測數據流的趨勢。將預測結果與實際數據比較，根據比較結果采用不同的方法存儲。實驗結果表明，提出的方法具有良好的性能，能夠滿足不同的處理需求。

曲線擬合；數據流；聚類算法；最小二乘法

A

TP311

10.3778/j.issn.1002-8331.1109-0269

FENG Xiulan,ZHANG Fan.New method for data streams compress and storage online.Computer Engineering and Applications,2013,49（11）：140-144.

馮秀蘭（1955—），女，副教授，主要研究方向為數據流挖掘、計算機網絡；張帆（1986—），男，碩士，主要研究方向為數據流挖掘。E-mail：zhangfan0755@163.com

2011-09-14

2011-11-08

1002-8331（2013）11-0140-05

CNKI出版日期：2012-01-16 http://www.cnki.net/kcms/detail/11.2127.TP.20120116.0927.042.html

◎圖形圖像處理◎