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

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

1 引言

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

目前，對(duì)于流數(shù)據(jù)處理普遍的做法是在存儲(chǔ)器中開(kāi)辟一個(gè)滑動(dòng)窗口來(lái)保存近期到達(dá)的數(shù)據(jù)流數(shù)據(jù)，以實(shí)時(shí)地支持查詢請(qǐng)求。隨著數(shù)據(jù)流不斷地流入滑動(dòng)窗口，當(dāng)滑動(dòng)窗口數(shù)據(jù)已滿時(shí)，將會(huì)有部分舊數(shù)據(jù)從滑動(dòng)窗口中流出。流出滑動(dòng)窗口的這部分?jǐn)?shù)據(jù)稱為歷史數(shù)據(jù)?；跀?shù)據(jù)流歷史數(shù)據(jù)的壓縮處理算法已經(jīng)有了一些研究結(jié)果。這些研究方法都是基于抽樣的，但是在很多情況下，常常需要保存連續(xù)的數(shù)據(jù)[2]。因此，抽樣的方法并不能滿足這種需求。

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

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

2 加權(quán)最小二乘法曲線擬合

數(shù)據(jù)流是一組順序、大量、快速、連續(xù)到達(dá)的數(shù)據(jù)序列，與時(shí)間密切相關(guān)?？梢詫?shù)據(jù)流視為無(wú)限多重集合，集合中每個(gè)元素具有形式，其中s是一個(gè)元組，t為標(biāo)識(shí)s的時(shí)間戳，t的取值可以是s進(jìn)入數(shù)據(jù)流系統(tǒng)的時(shí)間或者數(shù)據(jù)源產(chǎn)生s的時(shí)間。將元組中的一維數(shù)據(jù)與時(shí)間取出來(lái)單獨(dú)考慮，則數(shù)據(jù)流是一個(gè)關(guān)于時(shí)間t的函數(shù)。因此可以采用曲線擬合的方法對(duì)數(shù)據(jù)流進(jìn)行處理。

的求解方法。則根據(jù)不同的定義方法，則可能求解出無(wú)數(shù)條擬合曲線。對(duì)于求解出來(lái)的擬合曲線，并不要求其經(jīng)過(guò)實(shí)驗(yàn)數(shù)據(jù)中的每個(gè)數(shù)據(jù)點(diǎn)，而是希望曲線 y=φ(x)盡可能地靠近數(shù)據(jù)點(diǎn)，并且靠近的個(gè)數(shù)最多。設(shè)根據(jù)φ(x)算出第i點(diǎn)的函數(shù)值與實(shí)際值的誤差為εi：

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

為最小。

在實(shí)際的應(yīng)用中，并不是所有數(shù)據(jù)點(diǎn)的重要性都一樣，特別是曲線有突變的情況下，此時(shí)突變點(diǎn)的數(shù)據(jù)就顯得很重要。所以應(yīng)對(duì)不同的數(shù)據(jù)點(diǎn)賦予不同的權(quán)值，重要的數(shù)據(jù)點(diǎn)賦予較大的權(quán)值，一般的數(shù)據(jù)點(diǎn)則賦予較小的權(quán)值。這種帶有權(quán)值的最小二乘法曲線擬合就是加權(quán)最小二乘法曲線擬合。加權(quán)最小二乘法曲線擬合函數(shù)是關(guān)于x的n次多項(xiàng)式：

它的系數(shù)可通過(guò)求解正規(guī)方程組得到。設(shè)權(quán)值為w，則相應(yīng)的正規(guī)方程組為：

對(duì)于曲線擬合來(lái)說(shuō)，除了要獲得擬合結(jié)果外，還需要對(duì)曲線擬合的結(jié)果進(jìn)行精度的控制，即εi不能太大。根據(jù)文獻(xiàn)[3]，知道對(duì)于曲線擬合的精度與以下三個(gè)方面有關(guān)：分段擬合的段數(shù)、曲線擬合的階數(shù)以及數(shù)據(jù)點(diǎn)權(quán)值的分布。因此，為了獲得良好的精度，應(yīng)當(dāng)采用綜合各個(gè)因數(shù)進(jìn)行分段擬合的方式。擬合的段數(shù)越多，在同一段中采用的擬合階數(shù)越高，段中數(shù)據(jù)點(diǎn)的權(quán)值分布越合理，則擬合精度越高。變階加權(quán)分段方式可以自動(dòng)獲取最合適的數(shù)據(jù)點(diǎn)對(duì)數(shù)據(jù)流進(jìn)行分段，并對(duì)分段后的數(shù)據(jù)采用合適的階數(shù)進(jìn)行擬合，具有良好的性能。因此，本文采用變階加權(quán)分段方式對(duì)數(shù)據(jù)進(jìn)行最小二乘曲線擬合，以提高曲線擬合的精度。

在曲線擬合的過(guò)程中，擬合窗口選擇越大，則數(shù)據(jù)處理的時(shí)間越長(zhǎng)，擬合精度也會(huì)下降。但如果窗口選擇的長(zhǎng)度過(guò)短則不能有效地把握數(shù)據(jù)流的趨勢(shì)。所以，采用合適的窗口大小可以降低數(shù)據(jù)處理的時(shí)間，其次可以根據(jù)數(shù)據(jù)的特點(diǎn)采用合適的分段對(duì)數(shù)據(jù)進(jìn)行擬合，提高了數(shù)據(jù)擬合的精度。文獻(xiàn)[4]介紹了一種結(jié)合兩種方式的特點(diǎn)的窗口選擇方案，具有較好的性能。因此本文的窗口設(shè)置采用這種方式，即設(shè)定一個(gè)標(biāo)準(zhǔn)的數(shù)據(jù)窗口作為擬合處理的最小長(zhǎng)度，同時(shí)設(shè)置一個(gè)較大的數(shù)據(jù)窗口作為擬合處理的極限長(zhǎng)度。處理的過(guò)程如下：

（1）接受數(shù)據(jù)的流入，當(dāng)數(shù)據(jù)的長(zhǎng)度大于標(biāo)準(zhǔn)長(zhǎng)度時(shí)，對(duì)數(shù)據(jù)進(jìn)行曲線擬合，并求出擬合的最大誤差。

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

（3）當(dāng)數(shù)據(jù)的長(zhǎng)度大于極限長(zhǎng)度時(shí)，對(duì)數(shù)據(jù)擬合，并將擬合結(jié)果保存，同時(shí)將下次讀入的數(shù)據(jù)作為新的處理起點(diǎn)，重復(fù)（1）步驟。

3 k-means聚類算法

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

k-means聚類算法的處理思路是給定一個(gè)數(shù)據(jù)樣本，用戶輸入要獲得聚類簇的個(gè)數(shù)k，將數(shù)據(jù)劃分為k個(gè)部分，然后通過(guò)更新簇的中心來(lái)調(diào)整劃分，當(dāng)整體差異函數(shù)收斂的時(shí)候結(jié)束處理過(guò)程。聚類之間的差別是簇中心的表示方法，劃分調(diào)整策略和整體差異函數(shù)的定義。k-means聚類算法的處理流程如下：

（1）在樣本中任意選擇k個(gè)數(shù)據(jù)作為初始聚類中心。

（2）計(jì)算每個(gè)數(shù)據(jù)到這些聚類中心的距離，并根據(jù)最小距離對(duì)數(shù)據(jù)進(jìn)行重新劃分。

（3）重新計(jì)算每個(gè)聚類的中心。

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

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

（1）設(shè)定初始距離。

（2）計(jì)算新數(shù)據(jù)到每個(gè)聚類中心的距離，若最小距離大于初始距離，則新數(shù)據(jù)為新聚類的中心，否則根據(jù)最小距離對(duì)數(shù)據(jù)進(jìn)行劃分。

（3）重新計(jì)算每個(gè)聚類的中心。

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

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

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

4 原型實(shí)現(xiàn)

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

本文采用的方法如下：

（1）接受數(shù)據(jù)，采用加權(quán)分段曲線擬合算法對(duì)數(shù)據(jù)進(jìn)行曲線擬合。

（2）當(dāng)擬合結(jié)束時(shí)，求出最大擬合誤差。

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

（4）若權(quán)值大于或等于最大權(quán)值，則將擬合階數(shù)加1；若擬合階數(shù)大于最大擬合階數(shù)，則以最大誤差點(diǎn)作為分段點(diǎn)。

（5）對(duì)分段的數(shù)據(jù)采用合適的階數(shù)進(jìn)行曲線擬合，并將擬合結(jié)果保存。

（6）若臨時(shí)表中的數(shù)據(jù)大于最大個(gè)數(shù)，則將臨時(shí)表的數(shù)據(jù)進(jìn)行曲線擬合，并將擬合結(jié)果保存。

（7）當(dāng)擬合的結(jié)果足夠多時(shí)，采用k-means聚類算法對(duì)擬合結(jié)果中的參數(shù)進(jìn)行聚類分析。

（8）若聚類分析結(jié)束后，聚類結(jié)果穩(wěn)定，則采用合適的長(zhǎng)度對(duì)數(shù)據(jù)擬合，保存擬合結(jié)果。

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

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

5 實(shí)驗(yàn)及分析

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

實(shí)驗(yàn)1算法擬合精度驗(yàn)證。采用變階加權(quán)分段曲線擬合算法對(duì)樣本數(shù)據(jù)進(jìn)行測(cè)試。讀取的樣本數(shù)據(jù)為34個(gè)，最大誤差限設(shè)置為0.001，標(biāo)準(zhǔn)窗口大小設(shè)置為10，最大數(shù)據(jù)窗口大小設(shè)置為20，最大權(quán)值設(shè)為10，最大擬合階數(shù)設(shè)為3。擬合結(jié)果共分為4段，其中三階多項(xiàng)式的為3段，二階多項(xiàng)式的為1段，具體結(jié)果如下：

曲線擬合結(jié)果和原始數(shù)據(jù)的對(duì)比圖如圖1所示。

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

實(shí)驗(yàn)2算法的壓縮效率驗(yàn)證。本實(shí)驗(yàn)采用的測(cè)試樣本數(shù)據(jù)大小為48.5 kb，分別采用加權(quán)分段曲線擬合壓縮算法和旋轉(zhuǎn)門壓縮算法對(duì)測(cè)試樣本進(jìn)行壓縮，算法的數(shù)據(jù)精度設(shè)定為0.003。其中，旋轉(zhuǎn)門壓縮算法的存儲(chǔ)字段為序號(hào)（No），系統(tǒng)編號(hào)（SystemId），時(shí)間（Time），數(shù)據(jù)值（Data）。加權(quán)分段曲線擬合壓縮算法的參數(shù)設(shè)置為，最大權(quán)值為5，最大階數(shù)為4，標(biāo)準(zhǔn)窗口設(shè)置為15，最大窗口設(shè)置為20。存儲(chǔ)的字段為序號(hào)（No），系統(tǒng)編號(hào)（SystemId），開(kāi)始時(shí)間（StartTime），參數(shù) 1（A0），參數(shù)2（A1），參數(shù)3（A2），參數(shù)4（A3），參數(shù)5（A4），擬合個(gè)數(shù)（Num）。壓縮結(jié)果如表1所示。

表1 兩種算法壓縮對(duì)比

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

實(shí)驗(yàn)3對(duì)有一定周期性數(shù)據(jù)的處理。采用的樣本數(shù)據(jù)具有一定的周期性，大小為22.8 kb。樣本數(shù)據(jù)的散點(diǎn)圖如圖2所示。旋轉(zhuǎn)門壓縮算法的存儲(chǔ)字段為序號(hào)（No），系統(tǒng)編號(hào)（SystemId），時(shí)間（Time），數(shù)據(jù)值（Data）。本文算法的參數(shù)設(shè)置為：最大權(quán)值為10，最大階數(shù)為4，標(biāo)準(zhǔn)窗口設(shè)置為20，最大窗口設(shè)置為30。存儲(chǔ)的字段為序號(hào)（No），系統(tǒng)編號(hào)（SystemId），開(kāi)始時(shí)間（StartTime），參數(shù)1（A0），參數(shù) 2（A1），參數(shù) 3（A2），參數(shù)4（A3），參數(shù)5（A4），擬合個(gè)數(shù)（Num）。

圖1 曲線擬合對(duì)比圖

圖2 聚類數(shù)據(jù)源散點(diǎn)圖

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

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

6 結(jié)論

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

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

一種新的數(shù)據(jù)流在線壓縮存儲(chǔ)方法

馮秀蘭，張 帆

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

針對(duì)當(dāng)前數(shù)據(jù)流采用的抽樣存儲(chǔ)方法忽略了對(duì)數(shù)據(jù)流歷史數(shù)據(jù)的分析處理與存儲(chǔ)管理的問(wèn)題，提出一種新的存儲(chǔ)數(shù)據(jù)流的方法。在滿足數(shù)據(jù)精度的情況下，采用加權(quán)最小二乘法對(duì)緩存數(shù)據(jù)流進(jìn)行分段曲線擬合，對(duì)擬合結(jié)果進(jìn)行聚類分析。根據(jù)聚類分析結(jié)果，采用合適的窗口對(duì)數(shù)據(jù)進(jìn)行分段曲線擬合，利用擬合結(jié)果預(yù)測(cè)數(shù)據(jù)流的趨勢(shì)。將預(yù)測(cè)結(jié)果與實(shí)際數(shù)據(jù)比較，根據(jù)比較結(jié)果采用不同的方法存儲(chǔ)。實(shí)驗(yàn)結(jié)果表明，提出的方法具有良好的性能，能夠滿足不同的處理需求。

曲線擬合；數(shù)據(jù)流；聚類算法；最小二乘法

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—），女，副教授，主要研究方向?yàn)閿?shù)據(jù)流挖掘、計(jì)算機(jī)網(wǎng)絡(luò)；張帆（1986—），男，碩士，主要研究方向?yàn)閿?shù)據(jù)流挖掘。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

◎圖形圖像處理◎