面向監測數據壓縮的自適應SDT算法

張宗華，葉志佳，牛新征

（1.國家電網公司北京電力醫院信息通訊部，北京 100073；2.電子科技大學計算機科學與工程學院，四川 成都 611731）

面向監測數據壓縮的自適應SDT算法

張宗華1，葉志佳2，牛新征2

（1.國家電網公司北京電力醫院信息通訊部，北京 100073；2.電子科技大學計算機科學與工程學院，四川 成都 611731）

為降低IT運維系統的實時監測數據量、提高數據存儲效率，提出一種自適應的旋轉門算法（adaptive swinging door trending，ASDT）。針對傳統SDT算法存在抗噪性弱、參數選取困難等缺陷，ASDT首先通過最小二乘平滑處理，減小噪聲數據對SDT趨勢判斷的影響；然后通過改進死區限值過濾算法，對經平滑處理后的數據進行壓縮；最后基于相鄰壓縮區間標準差變化，自適應調整壓縮精度參數。實驗結果表明：在保證數據保真度的前提下，ASDT的仿真數據和真實數據上的壓縮比分別提高60%和24%以上。

數據壓縮；旋轉門算法；平滑處理；自適應調整

0 引 言

隨著企業信息化建設的不斷推進和完善，計算機軟硬件系統的運行維護已經成為了各行業普遍關注的問題。而IT運維工作中一項重要的內容是對主機設備的運行狀態以及網絡負載等信息進行實時監控和記錄，以實現異常情況的及時告警、故障診斷以及數據挖掘等功能[1]。因此，為確保海量數據能實時存儲，并盡可能降低數據的存儲容量，提高存儲效率，需要對數據進行快速有效地壓縮處理。

現有的數據壓縮技術包括基于小波變換的壓縮[2]、基于字典的壓縮[3]、基于統計的壓縮[4]等。而在實時數據庫領域，由于原始數據量大，數據的變化較平穩，且能容忍部分數據損失，通常采用有損壓縮算法以獲取更高的壓縮比。旋轉門趨勢 （swinging door trending，SDT）算法[5]是一種用于實時數據庫中的有損壓縮算法，被廣泛應用于實時數據壓縮。然而，傳統SDT算法的壓縮率和信息損失率受壓縮精度參數ΔE的影響較大，并且該算法在數據中有噪聲的情況下，壓縮性能較低。為了解決該問題，文獻[6]提出一種結合異常壓縮（exception compression，EC）和旋轉門的算法，一定程度地改善了算法的壓縮性能，但該算法中的壓縮參數需要根據專業背景和歷史數據的統計分析來確定。文獻[7]針對SDT算法受參數影響較大的問題，提出一種基于標準差的容差動態調整的改進算法，然而該算法沒有考慮噪聲數據的影響。文獻[8]提出一種基于有效估算的旋轉門算法，能有效提高數據壓縮率并降低壓縮時間，但其仍未考慮噪聲數據的影響，且該算法通過構造最大平行四邊形選取關鍵點容易造成趨勢特征的損失。

針對現有研究中存在的問題，結合運維監測數據變化平穩的特點，本文提出首先利用最小二乘法對原始數據進行平滑處理，減小噪聲數據對壓縮性能產生的影響；然后結合死區限值過濾對數據進行壓縮；最后通過比較相鄰區間的數據波動，動態調整壓縮參數。

1 SDT算法

SDT算法基本原理如圖1所示，對于t0~t5的原始數據，首先將初始點a存儲，并以距離a點ΔE的上下兩點作為支點，建立兩扇虛擬的門。當處理到b點時門是閉合的，隨著壓縮的進行，兩扇門會分別旋轉著打開，并且一旦打開就不能再閉合。只要兩扇門的內角和＜180°，即門未平行時，就將數據點舍棄。當兩扇門內角和≥180°時（如圖1中的d點），停止操作，存儲前一數據點（c點），并以該點開始后續的壓縮。圖1中的原始數據經SDT算法壓縮后變為a、c、e 3個點，并且相鄰數據點間用線段連接。解壓時，通過線性插值還原被壓縮的點。

經典SDT算法存在以下不足：1）在監測數據的采集過程中，可能存在由意外誤差導致的噪聲數據。而噪聲會造成SDT算法對數據的變化趨勢判斷錯誤，從而降低了算法的壓縮率。2）算法中參數ΔE的選取較困難，需要依賴先驗知識。ΔE過小會保留較多的無用數據點，降低壓縮率；而ΔE過大會使某些關鍵數據點被舍棄，還原后的數據精度較差。在經典SDT算法中，ΔE由用戶預設并在整個壓縮過程中固定不變，參數取值會對算法性能產生很大影響。

圖1 SDT算法原理

2 自適應SDT壓縮算法

本文在經典SDT算法的基礎上做出改進，使其獲得更優的壓縮性能，以更好地滿足IT運維系統中對監測數據壓縮的需求，主要改進思路如下：

1）數據預處理。針對數據監測過程中由測量誤差等因素引起的噪聲數據，對原始數據進行最小二乘平滑處理，減小噪聲數據對SDT算法的干擾，使后續的壓縮能更準確地判斷數據變化的趨勢。

2）數據壓縮。為了進一步減少監測數據量，提高存儲效率，采用改進死區限值算法對數據初步壓縮，再由SDT算法進一步壓縮。提高總體壓縮比，并減少SDT算法處理的數據量。

3）參數自適應調整。基于監測數據總體變化平穩的特點，在每次數據壓縮完成后，根據數據波動的變化，自適應調整壓縮精度參數，使其與數據的特性匹配，以取得更優的壓縮性能。

2.1 最小二乘平滑

基于監測數據變化平穩的特點，本文通過對原始數據進行平滑處理來降低噪聲數據對壓縮性能的影響。常用的數據平滑技術有回歸分析[9]、最小二乘平滑[10]、小波變換[11]等。本文采用基于最小二乘定理的五點三次平滑算法對數據進行處理。

對于相鄰的5個原始數據點（ti-2，yi-2），（ti-1，yi-1），…，（ti+2，yi+2），可用曲線y=α0+α1t+α2t2+α3t3進行擬合，并由最小二乘法原理可求出系數。五點三次平滑公式如下：

式中：Y——原始數據向量；

Ys——平滑后的數據向量，分別表示5個連續的數據值；

A——五階系數矩陣，可由最小二乘定理計算得出。

2.2 改進死區限值過濾

數據經平滑處理后，削弱了噪聲對壓縮算法的影響，接下來就可以進行數據的壓縮。為了進一步提高SDT算法的壓縮率，本文采用改進的死區限值算法[12]對平滑處理后的數據進行初步過濾，再利用SDT算法二次壓縮的兩級壓縮策略。死區限值算法的基本思路如圖2所示。

圖2 死區限值壓縮原理

在初始數據點a設置ΔE′的限值區間，依次對后續數據進行壓縮。若數據點在此死區內，則舍棄，否則進行存儲。如圖2所示，t4時刻的b點在此區間之外，故存儲b點，并以該點設置死區繼續對后續數據進行壓縮。

由上述原理可知，死區壓縮算法本質是上下斜率均為0時的SDT算法，其限值參數ΔE′同樣存在選取困難的缺陷：ΔE′設置偏大可能造成有效數據的丟失，增大壓縮誤差；偏小則會記錄過多冗余數據，降低壓縮比。基于此，本文將死區壓縮參數ΔE′與SDT精度參數ΔE設置為相等，并同時進行后續的動態調整。

2.3 壓縮參數自適應調整

SDT算法的壓縮精度參數ΔE需要預先設定，并且在壓縮過程中固定不變。而在實際的運維系統中，數據的特性是時變的，加上先驗知識的缺失，很容易造成ΔE與數據的失配。

在IT運維系統中，監測數據的變化一般比較平穩，因此，在一定時間范圍內，可以利用前一區間的數據波動情況預測下一區間的情況。數據的離散程度一般用標準差表示，記為σ

式中：yi——數據值；

μ——y的平均值；

n——數據總數。

則相鄰壓縮區間的波動變化可用下式計算：

式中σi、σi-1分別表示第i和i-1次壓縮的數據標準差。

最終，動態調整ΔE的值

式中：τ——數據波動變化的容差系數，是決定對ΔE進行調整的閾值；

F（w）——動態調幅系數，根據本區間與前一區間數據的波動變化情況動態確定ΔE的調整幅度。

分析可知：當|w-1|≤τ時，說明數據的波動變化不明顯，無需對ΔE調整；當|w-1|＞τ時，說明數據的波動變化較大，應調整ΔE。由于調幅函數F（w）關于（1，1）中心對稱，且單調遞增，當w＜1時，F（w）＜1，數據波動變得平緩，為了取得更高的壓縮比，則減小ΔE；當w＞1時，F（w）＞1，增大ΔE以取得更低的壓縮誤差。

本文的調幅系數F（w）在w=1兩側一階導數不斷增大，使F（w）的變化更為快速，從而能更及時地調整ΔE使之適應數據波動變化。

為了使ΔE在調整過程中不至于過大或過小，算法需設定其上下限值ΔEmax和ΔEmin。ASDT算法的總體流程為：對于輸入的原始數據序列Y=（ti，yi），首先初始化其上下斜率。若算法首次執行，則初始化ΔE為（ΔEmax+ΔEmin）/2，并保存第1個點。隨后，對原始數據進行五點三次平滑，并利用死區限值過濾對平滑后的數據初步壓縮，同時結合SDT算法做進一步壓縮。最后，利用式（2）計算本壓縮區間的數據波動，并根據式（4）自適應地調整ΔE。

3 實驗結果與分析

為了驗證本文提出的ASDT算法的有效性，本文分別基于仿真數據和真實數據在Matlab平臺上進行壓縮測試，并與傳統SDT算法進行對比。同時，為了驗證ASDT的可拓展性，對不同規模數據的壓縮時間進行測試。

3.1 評價指標

本文借鑒文獻[13]，采用壓縮比CR和均方根誤差RMSE作為壓縮算法的性能評價指標。計算如下：

式中：n——原始數據點數；

m——壓縮后數據點數；

yi——第i個時間點的原始數據；

高壓縮比、低均方根誤差的有損壓縮算法性能更優越。

3.2 仿真數據測試

仿真數據的生成，本文借鑒文獻[14]的方法，采用正弦波信號疊加噪聲的形式來模擬真實監測數據。其函數表達式如下：

式中：N（p，t）——噪聲信號，由Matlab自帶的高斯白噪聲生成函數wgn[15]產生；

p——噪聲強度參數，p值越大，噪聲數據對壓縮性能的影響越大。

為了測試ASDT算法對含噪數據的壓縮性能，本文令p從1增長至10，分別測試ASDT和SDT的算法性能。角頻率ω取0.001，采樣周期為2，采樣區間為[0，2000π]，這是為了模擬真實監測數據變化平緩，采樣頻繁的特點。SDT算法ΔE=0.02，ASDT算法ΔEmax= 0.04，ΔEmin=0，τ=0.1。實驗結果如表1、圖3所示。

由表1及圖3（a）的結果可知，隨著噪聲強度的增大，ASDT和SDT的壓縮比均有不同程度的減小。盡管如此，ASDT的壓縮比一直高于SDT，最低時仍為3.25，相比于SDT提高了60%以上。這是由于噪聲數據的頻繁抖動使SDT算法不能正確預測數據的走勢，從而過多記錄了無用信息。而ASDT算法由于對原始數據進行了平滑處理，減輕了噪聲的影響，使壓縮算法能更準確的把握數據的關鍵趨勢，大大減少歸檔點數。同時，采用死區限值過濾進一步增大了壓縮比。

ASDT在壓縮比方面比SDT取得更好的性能，但這并不意味著它是以損失數據精度為代價。由表1和圖3（b）可以看出，ASDT和SDT的均方根誤差基本相同，這是由于ASDT能根據相鄰區間數據波動的變化趨勢動態調整精度參數ΔE，從而使壓縮誤差維持在合理的水平。

ASDT和SDT重構后的數據如圖4所示，自上而下分別為原始數據、SDT以及ASDT。從圖可看到SDT算法受噪聲影響較大，而ASDT能更好地抵抗噪聲數據的干擾，忽略頻繁抖動的無關信息存儲，識別數據變化的關鍵趨勢。

3.3 真實數據測試

本文的真實數據來自某IT運維系統中磁盤使用率的監測數據，包括10個不同時間段采集的數據，采樣周期為2s，每個時間段采樣點均為2000以上。本文中SDT算法ΔE=0.5，ASDT的ΔEmax=1.0，ΔEmin=0，其他參數均與仿真數據實驗中一致。實驗結果如圖5 所示。

表1 仿真數據測試結果

圖3 仿真數據測試結果

由圖5（a）可知，ASDT在真實數據集上依然獲得了較高的壓縮比，最低時為9.49，對比SDT至少提升了24%。同時，由圖5（b）可知，ASDT的均方根誤差基本與SDT持平，取得了良好的數據保真度。真實數據集上的實驗結果再次證明本文提出的ASDT算法的性能更優。

3.4 可擴展性分析

為了驗證ASDT算法的可擴展性，對不同規模的數據進行壓縮時間的測試。數據的生成方式與3.2節相同，數據規模為10n，n∈[2，8]。對于每個n，分別測試10次取平均值。實驗結果如表2所示。

從表中結果可以看出，ASDT算法壓縮時間和重構時間隨著數據規模的增長大致呈線性增長，證明ASDT具有良好的可擴展性。同時，從表2可知，當數據規模為108時，ASDT的壓縮時間和重構時間分別為138.04s和507.34s，對較大規模的數據也具有良好的處理能力。

圖4 重構數據對比（p=1）

圖5 真實數據測試結果

表2 可擴展性實驗結果

4 結束語

本文提出一種精度自適應調整的SDT算法-ASDT，基于最小二乘原理，對原始數據進行平滑處理，減小噪聲數據對壓縮性能的影響，使算法能更準確地判斷數據的關鍵趨勢，提高壓縮比；結合死區限值算法實現初步壓縮，進一步增大壓縮比；最后基于數據波動變化對壓縮精度參數動態調整。實驗結果表明，ASDT在保持低壓縮誤差的前提下，有效提高了壓縮比，并且具有低復雜度和良好的可擴展性。

[1]韓學奇，王鋒.IT運維數據展示系統的研究和實現[J].計算機科學，2012，39（S2）：232-235.

[2]NING J，WANG J，GAO W，et al.A Wavelet-based data compression technique for smart grid[J].IEEE Trans actions on Smart Grid，2011，2（1）：212-218.

[3]BRISABOA N R，CANOVAS R，CLAUDE F，et al. Compressed string dictionaries[J].Computer Science，2011（6630）：136-147.

[4]KAVOUSIANOS X，KALLIGEROS E，NIKOLOS D. Optimal selective huffman coding for test-data compression[J].IEEE Transactions on Computers，2007，56（8）：1146-1152.

[5]BRISTOL E H.Swinging door trending：adaptive trend recording[C]∥Proceedings of the ISA National Conference.New York：ISA，1990：749-753.

[6]ZHANG F，CHENG L，LI X，et al.Application of a real-time data compression and adapted protocol technique for WAMS[J].IEEE Transactions on Power Systems，2015，30（2）：653-662.

[7]于松濤，王曉琨，趙利強，等.基于容差動態調整的旋轉門（SDT）改進算法[J].北京化工大學學報（自然科學版），2013，40（3）：109-113.

[8]馬發勇，厲啟鵬，馬志斌，等.電力調度SCADA系統中歷史數據壓縮及存儲策略[J].電網技術，2014，38（4）：1109-1114.

[9]韋玉春，王國祥，程春梅.水面光譜數據的核回歸平滑去干擾分析[J].南京師范大學學報（自然科學版），2010，33（3）：97-102.

[10]楊正舉，劉洛琨，錢學鋒，等.基于最小二乘平滑算法的時變信道盲辨識[J].計算機工程與設計，2013，34（1）：59-65.

[11]LI X，LI Y，HAN X，et al.Application of fuzzy wavelet transform to smooth Wind/PV hybrid power system output with battery energy storage system[J].Energy Procedia，2011，12（39）：994-1001.

[12]徐慧.實時數據庫中數據壓縮算法的研究[D].杭州：浙江大學，2006.

[13]曲奕霖，王文海.用于過程數據壓縮的自控精度SDT算法[J].計算機工程，2010，36（22）：40-42.

[14]寧海楠.一種基于SDT算法的新的過程數據壓縮算法[J].計算機技術與發展，2010，20（1）：25-28.

[15]MathWorks中國.Generate white Gaussian noise-Matlab wgn[EB/OL].http：∥cn.mathworks.com/help/comm/ref/wgn. html?searchHighlight=wgn，2016.

（編輯：劉楊）

Adaptive SDT algorithm for monitoring data compression

ZHANG Zonghua1，YE Zhijia2，NIU Xinzheng2
（1.Ministry of Information and Communication，Beijing Electric Power Hospital，State Grid Corporation of China，Beijing 100073，China；2.School of Computer Science and Engineering，University of Electronic Science and Technology of China，Chengdu 611731，China）

To reduce the amount of monitoring data of IT operation and maintenance system and improve the efficiency of data storage，an adaptive SDT algorithm named adaptive swinging door trending（ASDT）was proposed.To address problems such as the weak resistance to noise and the difficulty of parameter selection of traditional SDT algorithm，ASDT firstly adopts least-squares to smooth the original data to reduce the influence of noise to SDT trend judgment;then，it combines with improved boxcar-back slope algorithm to compress the data after smoothing;finally，it adjusts the parameters of compression accuracy adaptively based on the changes of standard deviation of adjacent interval.Results of experiments conducted on the simulation data and real data show that on the premise of guaranteeing the data fidelity，ASDT’s compression ratio is increased by over 60%and 24%respectively.

data compression；SDT algorithm；smoothing；adaptive adjustment

A

：1674-5124（2017）02-0104-05

10.11857/j.issn.1674-5124.2017.02.021

2016-06-17；

：2016-07-20

國家自然科學基金項目（61300192）；中央高校基本科研業務費項目（ZYGX2014J052）；北京電力醫院一體化運維監控與管理項目（HW2015000759）

張宗華（1977-），男，四川成都市人，工程師，碩士，研究方向為電力信息化研究與建設。