孫紀(jì)舟 李建中

摘 要： 精確度是數(shù)據(jù)科學(xué)領(lǐng)域研究的重要方面，對(duì)后續(xù)數(shù)據(jù)處理等過(guò)程都有至關(guān)重要的影響。利用多個(gè)傳感器返回的多個(gè)時(shí)間序列可提升時(shí)間序列數(shù)據(jù)的精確度，稱為不確定時(shí)間序列，這多個(gè)時(shí)間序列樣本在真實(shí)數(shù)據(jù)上下隨機(jī)波動(dòng)。已有關(guān)于時(shí)間序列的研究大多直接在不確定時(shí)間序列上提出新算法，其缺點(diǎn)是算法復(fù)雜度通常較高，直接對(duì)不確定時(shí)間序列進(jìn)行清洗，獲得盡可能接近真實(shí)的數(shù)據(jù)有重要意義。本文提出基于能量過(guò)濾的方法對(duì)不確定時(shí)間序列進(jìn)行清洗，實(shí)驗(yàn)結(jié)果表明與已有方法相比，本文方法在效果和效率上都更優(yōu)。

關(guān)鍵詞： 不確定時(shí)間序列;能量過(guò)濾;數(shù)據(jù)清洗

文章編號(hào)：2095-2163（2019）04-0001-06 中圖分類號(hào)：TP391.41 文獻(xiàn)標(biāo)志碼：A

0 引 言

時(shí)間序列數(shù)據(jù)在日常生活和工業(yè)生產(chǎn)中無(wú)處不在，例如氣象學(xué)中的溫度、濕度、風(fēng)速、PM2.5;醫(yī)學(xué)中的心跳、血壓、體溫;以及經(jīng)濟(jì)學(xué)中的股票指數(shù)、恩格爾系數(shù)以及其它描述宏觀經(jīng)濟(jì)形勢(shì)的指數(shù)等。這些數(shù)據(jù)都是隨時(shí)間變化的數(shù)值型數(shù)據(jù)。由于環(huán)境干擾、傳感器的精度不夠、獲取數(shù)據(jù)時(shí)的舍入等原因，時(shí)間序列數(shù)據(jù)通常是不精確的，距離真實(shí)數(shù)據(jù)總有一些誤差。而這些誤差往往給人們的日常生活、醫(yī)療中的病情診斷及監(jiān)控以及政府部門(mén)的決策等帶來(lái)負(fù)面影響。

為了盡可能降低誤差帶來(lái)的影響，常用的解決方法就是對(duì)同一時(shí)間序列數(shù)據(jù)采集多個(gè)樣本，每個(gè)樣本都在真實(shí)數(shù)據(jù)周圍隨機(jī)的上下波動(dòng)，對(duì)這些樣本求平均值，或者直接在這些樣本上設(shè)計(jì)新算法，都能在一定程度上解決誤差帶來(lái)的影響。求平均值的方法最簡(jiǎn)單快速，但結(jié)果精確度不夠高;設(shè)計(jì)新算法的思路能夠獲得更高的精度，但往往有著很高的時(shí)間復(fù)雜度。

結(jié)合時(shí)間序列平滑的特性以及隨機(jī)噪聲的波動(dòng)特性，本文給出一種基于能量過(guò)濾的時(shí)間序列清洗算法。根據(jù)給定的時(shí)間序列樣本，計(jì)算出數(shù)據(jù)中噪聲所占能量的比重，根據(jù)這個(gè)比重找出一個(gè)頻率閾值，并將傅里葉變換之后高于該閾值的部分過(guò)濾掉，所得結(jié)果更加平滑且接近真實(shí)數(shù)據(jù)，在Top-k查詢問(wèn)題上和已有算法做了實(shí)驗(yàn)對(duì)比，結(jié)果顯示在效果上本文算法較好，而時(shí)間效率上本文算法遠(yuǎn)遠(yuǎn)優(yōu)于已有算法。

1 問(wèn)題描述

1.1 時(shí)間序列

1.2 不確定時(shí)間序列

在很多實(shí)際情況中，收集到的數(shù)據(jù)往往是不精確的，比如采集溫度數(shù)據(jù)的傳感器，本身有一定的誤差，為降低誤差，對(duì)同一時(shí)刻的數(shù)據(jù)收集多個(gè)數(shù)據(jù)樣本，以提高測(cè)量精度。 因此本文給出的不確定時(shí)間序列模型描述如下：

（1）不同時(shí)刻值的誤差是獨(dú)立同分布的隨機(jī)變量;

1.3 不確定時(shí)間序列的清洗

關(guān)于不確定時(shí)間序列的已有研究中，都致力于提出新的模型和算法對(duì)不確定時(shí)間序列數(shù)據(jù)進(jìn)行搜索、聚類和Top-k查詢等。而相關(guān)問(wèn)題在確定時(shí)間序列上的研究已經(jīng)十分成熟，為了使這些方法能夠直接用在不確定時(shí)序數(shù)據(jù)上，本文主要研究如何對(duì)不確定數(shù)據(jù)進(jìn)行清洗（或者還原），使之變?yōu)楸M可能接近真實(shí)數(shù)據(jù)的確定時(shí)間序列。下面給出不確定時(shí)間序列的清洗問(wèn)題。

2 基于能量過(guò)濾的清洗方法

由于數(shù)據(jù)點(diǎn)之間的相關(guān)性在頻域表現(xiàn)比較明顯，因此本文考慮在頻域進(jìn)行降維，從而達(dá)到清洗數(shù)據(jù)的目的。其直觀思想是，時(shí)間序列數(shù)據(jù)在頻域上分布極不均勻。即有些頻率上的數(shù)據(jù)分布很集中（高能區(qū)域），而有些頻率上只有很少數(shù)據(jù)信息（低能區(qū)域），而不確定數(shù)據(jù)中的噪聲在各個(gè)頻率上的分布相對(duì)均勻。因此，在低能區(qū)域，噪聲數(shù)據(jù)占據(jù)主導(dǎo)地位，直接將其舍棄掉雖然會(huì)丟失一部分有用信息，但同時(shí)丟掉了更多的垃圾信息，使得整體的數(shù)據(jù)質(zhì)量得到提升。 該方法的優(yōu)點(diǎn)主要包括：

（1）大大減少了數(shù)據(jù)量，每個(gè)時(shí)間點(diǎn)的數(shù)據(jù)由m維降低到1維，并且在頻域上只需要保留很少的數(shù)據(jù)（例如在實(shí)驗(yàn)中，長(zhǎng)度為2 k的數(shù)據(jù)在頻率域只需要保留100個(gè)左右的數(shù)據(jù)點(diǎn)）;

（2）大大提升了數(shù)據(jù)質(zhì)量，通過(guò)自適應(yīng)的選取一個(gè)能量閾值，本文的方法能夠去掉盡可能多的噪聲，保留盡可能多的有用信息，從而使最終的估計(jì)結(jié)果盡可能地接近真實(shí)數(shù)據(jù)，實(shí)驗(yàn)部分也對(duì)此進(jìn)行了驗(yàn)證。

2.1 離散傅里葉變換

即在某個(gè)頻率上，臟數(shù)據(jù)的能量的期望等于真實(shí)數(shù)據(jù)能量期望與噪聲能量期望之和。

2.3 噪聲能量的估計(jì)

由于不同時(shí)刻的數(shù)據(jù)都是由同一個(gè)傳感器收集的，因此不同時(shí)刻的隨機(jī)噪聲也是獨(dú)立同分布的。每個(gè)時(shí)刻有m個(gè)樣本，均由隨機(jī)變量s+Ns中采樣得到，其中s是真實(shí)值但未知，隨機(jī)變量Ns是傳感器的隨機(jī)誤差。由于s是常數(shù)不影響方差，因此s+Ns和Ns的方差相等，由概率論知識(shí)可知，m個(gè)樣本的樣本方差是對(duì)s+Ns方差的無(wú)偏估計(jì)，即是對(duì)Ns方差的無(wú)偏估計(jì)。 由于時(shí)間序列很長(zhǎng)，因此在每個(gè)時(shí)間點(diǎn)上的數(shù)據(jù)估計(jì)Ns并求平均，根據(jù)大數(shù)定律容易得出，如此求得的方差幾乎等于傳感器隨機(jī)誤差的方差：

2.4 算法

至此，可給出基于能量過(guò)濾的時(shí)間序列清洗算法：

3 實(shí)驗(yàn)驗(yàn)證

最后在真實(shí)數(shù)據(jù)集和合成數(shù)據(jù)集上對(duì)本文算法和其它算法做一對(duì)比。

3.1 實(shí)驗(yàn)環(huán)境

本文算法代碼用JAVA語(yǔ)言實(shí)現(xiàn)，硬件環(huán)境是主頻3.60GHz的8核Intel i7處理器，內(nèi)存大小為8GB，硬盤(pán)大小1TB的臺(tái)式機(jī)，底層操作系統(tǒng)是Windows 7。

3.2 實(shí)驗(yàn)數(shù)據(jù)

本實(shí)驗(yàn)采用的數(shù)據(jù)集為UCR數(shù)據(jù)集，UCR是時(shí)間序列數(shù)據(jù)研究中最常用的數(shù)據(jù)集，樣本及噪聲的生成均采用文獻(xiàn)[1]中的方法。

3.3 算法對(duì)比

本實(shí)驗(yàn)主要與一個(gè)最近的關(guān)于不確定時(shí)間序列數(shù)據(jù)上Top-k查詢的算法[1]Holistc-PkNN做對(duì)比。該算法解決的問(wèn)題是，給定一個(gè)不確定時(shí)間序列數(shù)據(jù)集，研究如何從該數(shù)據(jù)集中快速找出與查詢序列Q距離最近的不確定時(shí)間序列。該方法是針對(duì)不確定時(shí)間序列上的老問(wèn)題設(shè)計(jì)的新算法，其最大缺點(diǎn)是雖然設(shè)計(jì)了很多提高性能的優(yōu)化技術(shù)，但時(shí)間開(kāi)銷依然很高。