數(shù)據(jù)集壓縮建模的研究*

王赫楠 孫艷秋 張柯欣

（遼寧中醫(yī)藥大學(xué)信息工程學(xué)院 沈陽 110847）

1 引言

在統(tǒng)計學(xué)研究中，數(shù)據(jù)序列數(shù)據(jù)挖掘是研究的重點之一［1～3］。它的研究對象是事物在不同時刻變化情況所形成的數(shù)據(jù)值。目前，各行業(yè)都存在海量的數(shù)據(jù)集。比如：醫(yī)療、金融、農(nóng)業(yè)等行業(yè)。通過對數(shù)據(jù)序列變化趨勢的分析和預(yù)測，揭示事物的內(nèi)在規(guī)律和關(guān)聯(lián)，是當(dāng)下數(shù)據(jù)集處理問題的主要方向。數(shù)據(jù)集的處理研究主要有以下幾個方面：數(shù)據(jù)序列的擬合［4～6］、數(shù)據(jù)序列的劃分［7～8］、數(shù)據(jù)序列的分類聚類［9～11］、數(shù)據(jù)序列的應(yīng)用研究［12～14］、數(shù)據(jù)序列的可視化研究。

數(shù)據(jù)集的壓縮以及奇異值點的識別是數(shù)據(jù)序列數(shù)據(jù)挖掘的研究重點。做好數(shù)據(jù)集的處理，是后續(xù)進(jìn)行數(shù)據(jù)分析和預(yù)測的根基。本文在分析了典型數(shù)據(jù)集處理模型的前提下，提出了數(shù)據(jù)集壓縮模型以及奇異值識別模型。數(shù)據(jù)集壓縮模型使用了自定義函數(shù)，符合數(shù)據(jù)集的時間局部性原理，考慮了數(shù)據(jù)集的時間特性，并且支持實時數(shù)據(jù)的處理問題。奇異值識別模型在原有模型的基礎(chǔ)上，對于一些關(guān)鍵奇異值數(shù)據(jù)的識別更具優(yōu)勢。

2 數(shù)據(jù)集壓縮模型

數(shù)據(jù)集壓縮是對數(shù)據(jù)結(jié)構(gòu)進(jìn)行優(yōu)化的一種非常重要的手段。幾年來，經(jīng)過計算機(jī)、數(shù)學(xué)等各方面研究人員的不斷探索，提出了很多消除數(shù)據(jù)冗余的方法，在數(shù)據(jù)處理、數(shù)據(jù)壓縮等方面取得了非常大的進(jìn)步。

原始數(shù)據(jù)集存放在一個n 維的向量中，數(shù)據(jù)集的數(shù)據(jù)量過大及維數(shù)過高，會對后期數(shù)據(jù)的整理及分析造成干擾。我們需要對數(shù)據(jù)進(jìn)行壓縮處理，既能用更少的數(shù)據(jù)來索引原始數(shù)據(jù)集，又能很好地反映原始數(shù)據(jù)集的趨勢變化，從而挖掘出研究者需要的有價值的信息。本文在分析了兩種典型的數(shù)據(jù)集壓縮方法的前提下，提出了一種新的數(shù)據(jù)集壓縮模型。

2.1 壓縮模型（一）

壓縮模型（一）將原始數(shù)據(jù)集劃分成若干段，在限制分段誤差的前提下，利用各段的均值來索引原始數(shù)據(jù)集，以此達(dá)到降維的目的。

這種方法作為數(shù)據(jù)降維的一種常用手段，非常的簡單。我們可以快速地對數(shù)據(jù)進(jìn)行壓縮處理。壓縮后的數(shù)據(jù)集是可以在一定程度上反映數(shù)據(jù)集的趨勢變化規(guī)律。但是我們在使用數(shù)據(jù)進(jìn)行挖掘有用價值信息的同時，還希望能對未來的趨勢進(jìn)行預(yù)測分析。并且數(shù)據(jù)集往往具有時間局部性，比如股票數(shù)據(jù)、生物醫(yī)藥數(shù)據(jù)、臨床數(shù)據(jù)等。我們所獲得的數(shù)據(jù)集中的數(shù)據(jù)，在分析當(dāng)前數(shù)據(jù)以及預(yù)測未來數(shù)據(jù)的影響是不一樣的。對于當(dāng)前數(shù)據(jù)來說，時間上越靠近的數(shù)據(jù)對于當(dāng)前數(shù)據(jù)的影響越大，時間上越遠(yuǎn)的數(shù)據(jù)對于當(dāng)前數(shù)據(jù)的影響越小。對于預(yù)測未來數(shù)據(jù)的走向也是同樣的原理。

2.2 壓縮模型（二）

文獻(xiàn)［15］在對數(shù)據(jù)進(jìn)行壓縮的同時，考慮到了數(shù)據(jù)序列的時間局部性原理。提出了時間影響因子的概念。模型同時使用均值和影響因子，來對數(shù)據(jù)進(jìn)行壓縮。

從上面計算均值時的變量設(shè)定可以看出，在進(jìn)行建模時，不是將壓縮起始點放在數(shù)據(jù)集的開始端點，而是放在了數(shù)據(jù)集的終端。這是因為如果把起始端放在數(shù)據(jù)集的開始端點，會導(dǎo)致在計算影響因子參數(shù)數(shù)值時，反復(fù)重復(fù)的計算過程。為了避免這個問題，該方法將壓縮起始點放在了數(shù)據(jù)集的終端。此方法確實考慮了數(shù)據(jù)序列的時間局部性原理，但是由于壓縮過程中，對數(shù)據(jù)集是采用自底向上的壓縮方式，不利于處理動態(tài)增長的數(shù)據(jù)問題。

2.3 壓縮模型（三）

針對于以上兩種常見的數(shù)據(jù)壓縮模型的優(yōu)缺點，本文提出了壓縮模型（三）。模型既考慮了數(shù)據(jù)的壓縮要求，同時也兼顧了數(shù)據(jù)集的時間局部性原理。模型的關(guān)鍵在如何選取合適的函數(shù)，使得壓縮的模型既能反應(yīng)原始數(shù)據(jù)的形態(tài)特征，又能兼顧到時間局部性。

函數(shù)的選取：如圖1 所示，所選取的函數(shù)，函數(shù)值應(yīng)在（0～1）之間且是遞增的。

圖1 可選函數(shù)模型

具體算法如下：

壓縮模型（三）既可以從數(shù)據(jù)集的開始端點進(jìn)行建模，也可以從數(shù)據(jù)集的尾端開始建模。可以實時在線進(jìn)行建模原始數(shù)據(jù)集，方法簡單易用。

2.4 實驗結(jié)果

軟件環(huán)境：Windows 操作系統(tǒng)，內(nèi)存4G，64 位操作系統(tǒng)，JAVA語言。

數(shù)據(jù)來源：本實驗使用“Time Series Classification Website”提供的數(shù)據(jù)集。

表1 數(shù)據(jù)集1

表2 數(shù)據(jù)集2

表3 數(shù)據(jù)集3

對于三種數(shù)據(jù)壓縮模型，我們采用壓縮后的兩點數(shù)據(jù)距離與原始數(shù)據(jù)的距離差異來進(jìn)行衡量，如壓縮后的前后兩點數(shù)據(jù)距離小于某一給定值，而原始數(shù)據(jù)兩點間的距離卻大于此值，對于此類情況統(tǒng)計后，作為三種模型壓縮效果的比較。

計算公式：壓縮出錯統(tǒng)計=出錯數(shù)／總查詢量；在以上提到的標(biāo)準(zhǔn)數(shù)據(jù)集中的部分實驗結(jié)果如圖2所示。

圖2 三種壓縮模型出錯統(tǒng)計圖

從實驗數(shù)據(jù)可以看出，壓縮模型（三）在三類數(shù)據(jù)集的統(tǒng)計中，明顯比其他兩種模型出錯量要小。而且相對于壓縮模型（一），壓縮模型（三）考慮了數(shù)據(jù)集的時間局部性原理，而對于壓縮模型（二），壓縮模型（三）還同時兼顧了數(shù)據(jù)序列的動態(tài)變化情況，對于實時的數(shù)據(jù)集能更好地進(jìn)行處理。

3 奇異值識別模型

數(shù)據(jù)集中的數(shù)據(jù)千變?nèi)f化，有些數(shù)據(jù)值頻繁出現(xiàn)，表現(xiàn)了數(shù)據(jù)集的基本趨勢變化，而有些數(shù)據(jù)雖然不頻繁出現(xiàn)，但在數(shù)據(jù)的分類聚類、決策分析中更能提供有用的價值，這類數(shù)據(jù)我們稱之為奇異值。如何能有效地挖掘出奇異值，對于數(shù)據(jù)集的處理和分析都有非常重要的意義。從于樂軍［16］等發(fā)表相關(guān)數(shù)據(jù)序列奇異點數(shù)據(jù)識別以來，相關(guān)研究備受關(guān)注。兩種典型的奇異點識別模型如下。

3.1 識別模型（一）

如圖3所示數(shù)據(jù)序列：

圖3 數(shù)據(jù)序列簡化模型1

L（（l1，t1），（l2，t2），（l3，t3），（l4，t4），（l5，t5），（l6，t6），（l7，t7），（l8，t8），（l9，t9），（l10，t10））。

識別模型（一）識別奇異點的規(guī)則如下。

如圖3，L 共包含有10 個數(shù)據(jù)點的數(shù)據(jù)序列。若時間間隔相同，數(shù)據(jù)序列可記為L（l1，l2，l3，l4，l5，l6，l7，l8，l9，l10）。在10 個數(shù)據(jù)值中，l2＜l3＜l4，l8＜l9＜l10，則認(rèn)為l3 和l9 為奇異值點保留。l3＞l4＞l5，l5＞l6=l7，l7＞l8＞l9，則l4，l6，l8 不是奇異值。最終保留奇異值點L（l3，l9）。

以圖3 為例，最終保留的奇異值點可以很好地反映數(shù)據(jù)集L 的走勢變化，此方法簡單易用。但隨著數(shù)據(jù)量的不斷增大，識別模型（一）不能有效地去除噪聲。無法有效識別奇異值，濾掉冗余數(shù)據(jù)。為了更好地去掉一些噪聲數(shù)據(jù)，可以對識別模型（一）進(jìn)行改進(jìn)，如圖4所示。

圖4 中，l2，l3，l4 按照識別模型（一），符合選取的奇異點條件。但是有些奇異點頻繁出現(xiàn)，并不能表現(xiàn)數(shù)據(jù)集的主要特性，屬于冗余數(shù)據(jù)。排除這類冗余數(shù)據(jù)可以考察該奇異點保持的時間（即該奇異點前后兩個奇異點所占的時間段）與數(shù)據(jù)集總長度的比值，即T1/Length，T2/Length，若T1/Length ＜β（給定的閾值），刪除奇異點l2，若T2/Length＞β（給定的閾值），保留奇異點l3。閾值的設(shè)定需根據(jù)數(shù)據(jù)集的實際長度和所在知識領(lǐng)域進(jìn)行設(shè)定，一般小于1。

圖4 數(shù)據(jù)序列簡化模型2

改進(jìn)的識別模型（一），可以有效地去除數(shù)據(jù)集中的噪音數(shù)據(jù)，但也容易忽略一些表現(xiàn)數(shù)據(jù)集主要特性的數(shù)據(jù)。

3.2 識別模型（二）

部分?jǐn)?shù)據(jù)集中的數(shù)據(jù)，雖然不滿足識別模型（一）的奇異值條件，但是也決定了數(shù)據(jù)集在某一時間段內(nèi)的趨勢變化，應(yīng)該作為奇異值被識別，如圖5所示。

l1，l2，l3分別為某數(shù)據(jù)集的三個連續(xù)時間點的數(shù)據(jù)。l1＞l2＞l3，按照識別模型（一），l2 不是奇異值數(shù)據(jù)點。但是按照整個數(shù)據(jù)形態(tài)的走向，從t2時刻的l2數(shù)據(jù)點開始，整個數(shù)據(jù)集不再按照原來趨勢下降了，而是進(jìn)入了一個緩慢下降區(qū)間。而這一變化正是從l2數(shù)據(jù)點開始的，那么l2數(shù)據(jù)點也應(yīng)該是一個奇異點。杜奕等［17］提出，可以用距離來選取奇異值點。如圖5 所示，若|d2-（d1+d3）/2|＞λ（給定的閾值，根據(jù)實際情況調(diào)節(jié)），則l2被作為奇異值點。

圖5 數(shù)據(jù)集的簡化模型3

該方法綜合了以上兩種方法的優(yōu)點，同時又考慮了奇異值點的特殊情況，在消除冗余數(shù)據(jù)的同時，也能抓住一些表現(xiàn)數(shù)據(jù)集關(guān)鍵特性的奇異值數(shù)據(jù)。這里λ閾值的設(shè)定需要根據(jù)實際情況考慮。

3.3 識別模型（三）

本文在綜合了以上幾種識別模型的基礎(chǔ)上，提出了一種新的奇異值識別模型。如圖6所示。

數(shù)據(jù)集L（（l1，t1），（l2，t2），（l3，t3），（l4，t4），（l5，t5）），若時間間隔相同數(shù)據(jù)集可記為L（l1，l2，l3，l4，l5），根據(jù)識別模型（一），先選出符合條件的奇異值數(shù)據(jù)。但有些數(shù)據(jù)雖不滿足模型（一），但是仍然反映了數(shù)據(jù)值的主要趨勢變化，如何選取此類奇異值數(shù)據(jù)。本文提出以下方案，如圖6中l(wèi)2，以l2為基準(zhǔn)做一條平行于x軸的直線，l2的前后臨點l1，l3 位于橫線的兩側(cè)，此時我們考察，若|（l3-l2）/（t3-t2）-（l2-l1）/（t2-t1）|＞=ε，則l2作為奇異值數(shù)據(jù)點被識別；如圖6 中l(wèi)4，以l4 為基準(zhǔn)做一條平行于x軸的直線，l4 的前后臨點l3，l5 位于橫線的同側(cè)，此時我們考察，若|（l4-l3）/（t4-t3）|＞=ε，或者|（l5-l4）/（t5-t4）|＞=ε，則l4作為奇異值點被識別。

圖6 數(shù)據(jù)集的簡化模型4

本文提出的識別模型（三），在改進(jìn)的識別模型（一）的基礎(chǔ)上，對于特殊奇異值數(shù)據(jù)，提出了一種新的識別方法。該模型能更加有效地識別奇異值數(shù)據(jù)，并能更好地反映數(shù)據(jù)集的形態(tài)變化。

3.4 實驗結(jié)果及分析

本實驗所用數(shù)據(jù)集為2.4小節(jié)中所提供的數(shù)據(jù)集。

表4 數(shù)據(jù)集1

表5 數(shù)據(jù)集2

表6 數(shù)據(jù)集3

實驗方案：選取的奇異值數(shù)量基本一致的情況下，比較奇異值模型與原數(shù)據(jù)集差異情況。

奇異值數(shù)量的變化使用壓縮率進(jìn)行衡量。例如，原數(shù)據(jù)集數(shù)據(jù)個數(shù)為α1，選取的奇異值數(shù)據(jù)個數(shù)為α2，壓縮率=（1-α2/α1）*100%。

結(jié)果分析：

實驗中使用了奇異值識別模型（一），改進(jìn)的模型（一），識別模型（二）以及本文中提出的識別模型（三）進(jìn)行實驗。

如圖7，四種模型在數(shù)據(jù)集1 上的差異情況比較結(jié)果，壓縮率基本相近分別為91%，92%，92%，92%。

圖7 四種模型與原數(shù)據(jù)集的差異比較圖（數(shù)據(jù)集1）

如圖8，四種模型在數(shù)據(jù)2 上的差異情況比較結(jié)果，壓縮率基本相近分別為53%，65%，68%，70%。

圖8 四種模型與原數(shù)據(jù)集的差異比較圖（數(shù)據(jù)集2）

如圖9，四種模型在數(shù)據(jù)集3 上的差異情況比較結(jié)果，壓縮率基本相近分別為78%，92%，91%，92%。

圖9 四種模型與原數(shù)據(jù)集的差異比較圖（數(shù)據(jù)集3）

根據(jù)以上三個圖的比較，在壓縮率基本相近的情況下，差異情況的比較結(jié)果，模型（二）與模型（三）明顯優(yōu)于模型（一）以及改進(jìn)的模型（一）。模型（二）與模型（三），在差異情況基本相近的情況下，模型（三）的壓縮率要優(yōu)于模型（二）。因此，根據(jù)實驗結(jié)果可以得知，本文提出的模型（三）無論從壓縮率還是差異情況的比較，都要優(yōu)于其他三種識別模型。

4 結(jié)語

本文針對于目前各行業(yè)大數(shù)據(jù)背景，分析了數(shù)據(jù)集處理的現(xiàn)狀。在分析了幾種已有模型的基礎(chǔ)上，提出兩種數(shù)據(jù)處理模型，數(shù)據(jù)壓縮模型（三）以及奇異值數(shù)據(jù)識別模型（三）。經(jīng)實驗證明，本文提出的兩種模型，在數(shù)據(jù)壓縮以及奇異值數(shù)據(jù)識別研究中是要優(yōu)于已有的幾種模型。但是，對于奇異值識別模型（三），如何選取合適的ε值，來優(yōu)化壓縮率以及差異值等指標(biāo)，是今后需要研究的方向。