技術報告基于傅里葉變換和kNNI的周期性時序數(shù)據(jù)缺失值補全算法

1、計劃類別 項目編號 項目技術報告課題名稱 項目主持人 承擔單位 題目：基于傅里葉變換和kNNI的周期性時序數(shù)據(jù)缺失值補全算法在機器學習和數(shù)據(jù)挖掘過程中，數(shù)據(jù)缺失現(xiàn)象經(jīng)常發(fā)生。對缺失值的有效補全是數(shù)據(jù)預處理的重要組成部分，也是后續(xù)分析挖掘工作的基礎。最近鄰填充算法（kNNI）因其易于實現(xiàn)、計算方便和局部填充效果好等特性而被廣泛應用。但是，它并不涉及全局信息，因而當大段缺失值發(fā)生時，補全效果會有所降低，而對于具有周期成分的時序數(shù)據(jù)，其效果更是急劇下降。幸運的是，傅里葉變換能夠解析出周期數(shù)據(jù)中的不同周期成分，并能在此基礎上通過逆變換基本實現(xiàn)數(shù)據(jù)復原，只不過其局部復原能力較弱。因此，本文結合傅里葉變換

2、對周期性數(shù)據(jù)的全局復原能力和kNNI對局部數(shù)據(jù)的補全能力，提出了基于傅里葉變換的kNNI缺失值補全算法（FkNNI）。通過對大量模擬數(shù)據(jù)的測試結果表明，該算法比單純的kNNI算法的缺失值補全準確性有很大提升。關鍵詞：缺失值補全；最近鄰填充算法；周期數(shù)據(jù)；傅里葉變換Abstract：Data missing often occurs during the process of machine learning and data mining.Missing value imputation is an important part of data preprocessing and is als

3、o a basis for subsequent work of analysis and mining.The algorithm of k-Nearest Neighbor Imputation （kNNI） is a popular method frequently employed for missing value imputation because it is easy to implement，easy to calculate and effective for local data completion. However，it does not involve globa

4、l information， and as a result，its effect decreases somewhat when large fragments of missing values occur，especially when there are periodic components in the time series data.Fourier transform， however，is able to analyze the different periodic components in the periodic data，and to roughly restore

5、the data by inverse transform， with its local recovery ability weak only.Therefore，this paper proposes akNNI algorithm based on Fourier transform （FkNNI），combining the global recovery ability of Fourier transform and the local recovery ability of kNNI.Experimental testing results on a large amount o

6、f data indicate that the new algorithm is far more accurate than kNNI only.Keywords：missing value imputation；kNNI；cyclical data；Fourier transform1 引言（Introduction）人類自2010年便進入到大數(shù)據(jù)時代，大數(shù)據(jù)時代的來臨，給數(shù)據(jù)挖掘技術帶來了許多機遇與挑戰(zhàn)。如今，我們對大數(shù)據(jù)的研究不再采用抽樣調(diào)查的方法，而是對所有數(shù)據(jù)進行全面分析。大數(shù)據(jù)顯著的特點是種類多、流速快及數(shù)據(jù)量大，因此需要我們靈活運用數(shù)據(jù)挖掘技術對各種數(shù)據(jù)進行聚類、分類、分析，

7、以及對其趨勢進行預測。在數(shù)據(jù)挖掘和機器學習中，經(jīng)常會出現(xiàn)數(shù)據(jù)缺失的現(xiàn)象1。造成數(shù)據(jù)損失的原因有很多，如信息意外遺漏、無法獲取、系統(tǒng)實時性要求太高或收集代價太大等，都可能導致數(shù)據(jù)缺失。數(shù)據(jù)缺失會影響數(shù)據(jù)挖掘過程中抽取規(guī)則的準確性，甚至會導致建立錯誤的數(shù)據(jù)挖掘模型，目前常用的數(shù)據(jù)缺失值處理方法有如下三類：第一類方法直接刪除元組。這種方法簡單易行，若包含缺失值的元組在整體數(shù)據(jù)中所占比較小，則該方法非常有效。然而，當缺失值所占比例波動很大時，該方法會降低數(shù)據(jù)挖掘算法的質(zhì)量。同時，忽略的元組可能包含重要信息，使數(shù)據(jù)發(fā)生偏離，甚至得出錯誤的結論。第二類方法對數(shù)據(jù)進行推測和補齊。該方法一般基于統(tǒng)計學原理，用

8、不同的算法對缺失值進行填充，常見的數(shù)據(jù)補齊算法有：平均值（或中位數(shù)）填充、特殊值填充、熱卡填充、人工填充、k-最近鄰法、回歸和EM算法等。第三類方法不做任何處理，但并不影響挖掘方法正常運行。該方法指直接在包含缺失值的數(shù)據(jù)集上進行數(shù)據(jù)挖掘，常見的方法有貝葉斯網(wǎng)絡和人工神經(jīng)網(wǎng)絡等1。很多研究表明，采用合適的算法針對特定的數(shù)據(jù)類型的數(shù)據(jù)集，能夠產(chǎn)生較好的填充效果。本文的研究對象是時序數(shù)據(jù)缺失值的填充方法。與一般數(shù)據(jù)不同，時序數(shù)據(jù)一般來說具有明顯的趨勢性和周期性，其全局特點非常明顯。也就是說，某個時間點的數(shù)據(jù)不但與其鄰近數(shù)據(jù)有明顯的關系，它與全局數(shù)據(jù)都有關聯(lián)。因此，我們不但要采納局部數(shù)據(jù)補全的優(yōu)秀補全

9、算法，也要考慮具有全局數(shù)據(jù)處理能力的補全算法，并希望把它們有機結合。基于這樣的思想，本文在kNNI2算法的基礎上提出了基于周期頻譜分析的缺失值補全算法，并在模擬數(shù)據(jù)和真實數(shù)據(jù)上進行了驗證。 本文的整體結構如下：第2部分介紹了相關的工作，包括線性擬合算法、傅里葉變換和kNNI算法算法等，第3部分介紹了FkNNI算法的基本框架，第4部分是實驗結果和結論。2 相關工作（Related work）缺失值補全算法的核心目標是提取數(shù)據(jù)間的相關關系，并以此為基礎建立模型，按照模型填充和補全缺失的數(shù)據(jù)。但時序周期數(shù)據(jù)之間的關系非常復雜，涉及數(shù)據(jù)的線性趨勢，也就是數(shù)據(jù)隨時間變化而在總體趨勢上的線性增長或減少的趨

10、勢。另外一個關系是數(shù)據(jù)隨時間呈現(xiàn)的周期規(guī)律，并且這種周期在大多數(shù)情況下并不是單一周期，而是若干個周期的合成。因此，需要用傅里葉變換等工具發(fā)現(xiàn)其周期成分，也就是頻譜分析。數(shù)據(jù)間的第三個關系是局部數(shù)據(jù)的相似性，也就是相鄰數(shù)據(jù)間的值的差別不會很大。因此，以下將從線性趨勢、周期規(guī)律和局部關系三個方面，介紹缺失值補全的已有的基礎和成果。2.1 線性擬合如果離散函數(shù)值f1，f2，fn中有k個值缺失，則可以利用非缺失的n-k個值進行線性擬合，得到式（1）所示的公式。然后，對缺失的k個值，逐一代入式（1）中，所獲得的線性函數(shù)值就是需要補全的值。線性擬合所得的公式（1）不但可以用于補全缺失數(shù)據(jù)，也可以在整體數(shù)據(jù)

11、上進行消除其增加或減少的趨勢。例如，如果離散函數(shù)值f1，f2，fn線性擬合所得到的線性擬合公式為式（1），那么把所有的離散值減去該公式對應的函數(shù)值就可以得到另外一組函數(shù)值g1，g2，gn，這組函數(shù)值具有良好的性質(zhì)：其均值是0，其線性擬合公式中參數(shù)a和b的值都是0，因而比原數(shù)據(jù)更適合采用傅里葉變換等的操作。因此，線性擬合操作及基于此的平移旋轉工作往往是其它操作的基礎。2.2 傅里葉變換分析傅里葉變換（Fourier Transform）是一種線性積分變換4，通過它可以把信號從時間域變換到頻率域，進而研究信號的頻譜結構和變化規(guī)律。它在物理學、信號處理、統(tǒng)計學、聲學、光學等領域都有著廣泛的應用。很多

12、時序數(shù)據(jù)雖然看似雜亂無章，并不能觀察到其周期，其實很可能是由多個周期控制的規(guī)律性極強的數(shù)據(jù)。傅里葉定理表明，對于任何連續(xù)記錄的時間序列或信號，都可用無限疊加的不同頻率的正交的正弦波信號表示。因此可將時間序列進行傅里葉變換，計算序列的周期特征并進行頻譜分析，進而通過逆變換，對序列做進一步的分析處理。在傅里葉逆變換過程中需要兩個條件，一個是每個正弦波的振幅，另一個是每個正弦波的相位差。因此通過傅里葉變換，我們把看似雜亂無章的信號考慮成由一定振幅、相位、頻率的基本正弦信號組合而成，傅里葉變換的目的就是找出這些基本正弦信號中振幅較大的頻率，從而找出主要的頻率。根據(jù)原信號的不同類型，我們可以把傅立葉變換

13、分為四種類別5，6：（1）非周期性連續(xù)信號：傅立葉變換。（2）周期性連續(xù)信號：傅立葉級數(shù)。（3）非周期性離散信號：離散時域傅立葉變換。（4）周期性離散信號：離散傅立葉變換。四種原信號的圖例如圖1所示。對于時間序列而言，該函數(shù)的值越越大，則說明函數(shù)與原始數(shù)據(jù)集越貼近，因此選用結果較大的正弦函數(shù)用來進行疊加處理。如果通過傅里葉變換的結果如圖2所示，那么對周期性離散信號，原始數(shù)據(jù)值f（i）（圖中用虛線表示）和我們進行擬合的函數(shù)在該點的值sin（i）（圖中用實線表示）的貼合程度決定了擬合度的好壞。式（5）中的k的選擇要根據(jù)傅里葉變換的實際情況，就是取周期性非常顯著的幾個頻率，最小取1，最大一般可以取到

14、7，通常是取2至4，圖2中的逼近函數(shù)的k取1。2.3 kNNI算法k近鄰算法（kNN）是一種理論比較成熟的、且最簡單的分類算法之一。它操作簡單，時間復雜度低，用于缺失值補全時，其插補精度高，因此被廣泛運用于機器學習的眾多領域。它可以作為分類算法，其思路為：如果一個樣本在特征空間中的k個最相似的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別。該算法基本流程如圖3所示。kNN算法還可以用于回歸，其原理是在樣本附近取k個樣本，將這些樣本某屬性的平均值賦給該樣本，將不同距離的鄰居對該樣本產(chǎn)生的影響賦予不同的權值。就可以得到該樣本的屬性。k近鄰填充算法（k-Nearest Neighbor Imp

15、utation Method， kNNI）是kNN算法在缺失值補全領域的應用8。通過kNNI來進行缺失值填充的核心思想是計算缺失數(shù)據(jù)項到各個完全數(shù)據(jù)集的距離，選取距離該缺失數(shù)據(jù)項的k個最近鄰數(shù)據(jù)作為基礎和依據(jù)，把它們加權，用來進行缺失值填充。kNNI算法在缺失值補全時依然有一些不足之處，例如，（1）當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的k個鄰居中大容量類的樣本占多數(shù)。（2）計算量較大，每一個待分類的樣本都要計算它到全體已知樣本的距離，才能求得它的k最近鄰點。（3）由kNNI算法選擇的最近鄰居可能導致具有不同方向的偏好，使得分類結果

16、失效。針對這些問題，目前許多可行的解決方法，如采用與距離相關的權值的方法或事先對已知樣本點進行剪輯，去除對分類作用不大的樣本等9。如圖4所示，若原始數(shù)據(jù)點集在處數(shù)據(jù)值缺失，那么kNNI算法即為，選取落在其左右一段等距的區(qū)間內(nèi)的原始數(shù)據(jù)點，將這些點的值取均值，即認為該值就是處數(shù)據(jù)的缺失值。如前文所述，kNNI算法由于很多優(yōu)秀的性質(zhì)而被廣泛采用。然而，kNNI算法的填充準確性很大程度上依賴于k值的選擇。而通常k的值要通過遍歷才能最終確定，這需要大量的計算投入10。3 算法框架（Algorithm framework） 缺失值補全算法的實質(zhì)是通過數(shù)據(jù)間內(nèi)在的關系，發(fā)現(xiàn)其中的模型和規(guī)律，從而從未缺失的

17、數(shù)據(jù)和規(guī)律出發(fā)，推測出缺失的數(shù)據(jù)。我們需要處理的數(shù)據(jù)是生態(tài)監(jiān)測領域的通量塔檢測數(shù)據(jù)，包含了水中的氧氣含量、二氧化碳含量、碳通量等的時序數(shù)據(jù)，這些數(shù)據(jù)呈現(xiàn)出明顯的趨勢性和周期性，而且周期性多以天和年為主要周期成分。因此，對于其中的缺失值補全，需要同時考慮趨勢性和周期性，同時也要考慮近鄰數(shù)據(jù)與缺失數(shù)據(jù)之間的相似關系。對一個時序數(shù)據(jù)序列，F(xiàn)kNNI填充算法主要經(jīng)過如下幾個主要步驟：步驟1，通過線性擬合，計算出如式（1）所示的擬合公式。步驟2，在原始數(shù)據(jù)的基礎上，減去式（1）計算所得的模型值。此時，所有時序數(shù)據(jù)的平均值是0，且其線性擬合直線就是x軸本身。步驟3，通過式（4）所示的離散傅里葉變換，得到不

18、同周期的正弦函數(shù)對應的系數(shù)（振幅），并找到最主要的幾個周期，也就是發(fā)現(xiàn)其主要的頻譜。步驟4，按照式（5）把缺失值所在的時間點的數(shù)據(jù)補全為傅里葉逆變換的函數(shù)值。步驟5，利用式（1）把補全的數(shù)據(jù)復原為帶線性趨勢的數(shù)據(jù)，這部分是傅里葉變換所得的補全值。步驟6，用kNNI算法，對鄰近非缺失的值進行加權平均，也得到一個補全數(shù)據(jù)，這是kNNI所得的補全值。步驟7，把第5步和第6步所得數(shù)據(jù)進行線性加權，如果是大段缺失，則對第5步所得的補全值占有更大的比重；如果是單點缺失，則要提高kNNI所得補全值的比重。線性組合方式如式（6）所示。其中，在0和1之間，是合成的補全值，和分別是傅里葉變換補全值和kNNI補全值

19、。由于新提出的算法框架是基于數(shù)據(jù)的全局關系（傅里葉變換和線性趨勢所描述的關系）和局部關系（kNNI所描述的關系）兩個方面，因此稱之為FkNNI。4 實驗結果與結論（Experimental results and conclusions）我們采用的原始數(shù)據(jù)是通量塔的時序數(shù)據(jù)及相關模擬數(shù)據(jù)，在數(shù)據(jù)中人為去除一些數(shù)據(jù)，形成缺失值，然然后逐步采用第3部分給出的算法框架，得相應的補全值。把原始去除的數(shù)據(jù)與補全數(shù)據(jù)相比較，便可得到對對補全算法的精確性的度量。實驗和結果通量塔獲取的原始的時序數(shù)據(jù)如圖5所示，其中橫軸表示時間，縱軸是時序數(shù)據(jù)的觀測值。為了測試缺失值填補的精確性，我們事先去除掉一部分數(shù)據(jù)作為缺

20、失值。然后進行FkNNI的第三步驟，根據(jù)式（4），得到振幅比較高的一組基，用于疊加合成最終的函數(shù)。需要求得的是每個正弦波的幅度，以及每個正弦波之間的相位差。而通量塔中的時間序列間間隔為30分鐘，因此正弦波的周期取30分鐘的倍數(shù)。根據(jù)式（4）求前幾個具有最大振幅的周期，得到的實際擬合函數(shù)為若在時間序列上，時刻的數(shù)據(jù)值發(fā)生了缺失，上文中基于離散傅里葉變換求得的函數(shù)在該時刻的函數(shù)值設為，利用kNNI算法，取左右各100分鐘的時間間隔，將落在該區(qū)間內(nèi)的原始數(shù)據(jù)值取均值得到結果為，根據(jù)式（6），利用FkNNI算法計算時刻缺失的數(shù)據(jù)值為兩個補全值的線性組合。式（6）中的，若經(jīng)傅里葉變換后得到的函數(shù)周期性較

21、好，則取較大值，反之取較小值。為了驗證補全效果，我們隨機去除5個時間點的數(shù)據(jù)，人為造成數(shù)據(jù)缺失。這5個時間點如表1的第1列所示，缺失前的真實值在表格的第2列。通過kNNI算法和FkNNI算法得到的模型值和分別在表格的第3列和第4列。從表1可以看出，用新算法FkNNI得到的模型值比kNNI要更接近原始值。事實上，kNNI補全值的平均誤差為1.2363，而FkNNI補全值的平均誤差只有0.3562，具有一定的優(yōu)勢。通過表1中的對比，我們可以看出kNNI算法和FkNNI算法在對單點的缺失進行補全的時候，都有一定的準確性。但是影響通量塔中的數(shù)據(jù)的因素很多，難免會出現(xiàn)整段缺失的現(xiàn)象，此時，如果對這一段中

22、所有缺失的點都采用kNNI算法進行補全的話，這一段上的補全的值大致相同，這與實際數(shù)據(jù)就會相差甚遠。所以此時我們將采用FkNNI算法，來較好的復原一段丟失的數(shù)據(jù)。由于我們采用等間隔采樣的數(shù)據(jù)，因此，對于大段缺失的數(shù)據(jù)，我們利用缺失點為中心的區(qū)間內(nèi)的非缺失點作為補全的基礎。也就是說，計算某個缺失值時所采用的兩邊的非缺失點的數(shù)量很有可能不一樣多。表2中的數(shù)據(jù)去除了第71至75個時刻之間的所有值作為缺失值。表2的第2、3、4列分別是原始值，kNNI補全的模型值和FkNNI補全的模型值。從表2可以看出，F(xiàn)kNNI的模型值比kNNI的模型值與原始值之間要相似得多。事實上，kNNI的模型值的平均誤差是5.0

23、212，而FkNNI的模型值的平均誤差是1.0430，平均誤差非常顯著地降低。從表1和表2中的模型比較可以看出，F(xiàn)kNNI算法在缺失值補全的精度上要優(yōu)于kNNI算法，并且對大段缺失這種優(yōu)勢更加明顯。對于含有峰值的大段缺失，kNNI算法不能復原任何峰值，但FkNNI具備復原峰值或逼近峰值等能力。5 結論（Conclusions）采用數(shù)據(jù)挖掘算法對數(shù)據(jù)進行挖掘并從中發(fā)現(xiàn)知識的前提是具有較高質(zhì)量的數(shù)據(jù)。然而，由于種種因素，在實際應用中采集的數(shù)據(jù)通常都會出現(xiàn)缺失。缺失值補全具有重要的理論和實踐意義。通過對時序數(shù)據(jù)的觀察和分析，我們認為時序數(shù)據(jù)間的關系主要由三個方面構成：鄰近數(shù)據(jù)的相似性、數(shù)據(jù)的線性趨勢

24、和數(shù)據(jù)的周期規(guī)律?；诖?，本文提出了基于傅里葉變換的和kNNI的缺失值補全算法FkNNI，準確把握了數(shù)據(jù)間的內(nèi)在關系規(guī)律，使得數(shù)據(jù)補全的準確性有了較大提升；尤其是在大段數(shù)值缺失時，該算法的補全優(yōu)勢就更為明顯。這為綜合利用數(shù)據(jù)的全局和局部關系信息提供了新的思路。 參考文獻（References）1 Tutunji，Tarek A.Parametric System Identification Using Neural NetworksJ.Applied Soft Computing Journal，2016，47（1）： 251-261.2 Jianxin WANG，et al.Imputating Missing Values with Distance-and Density-Weighted and Quadrant-Based Nearest NeighborsJ.Journal of Computational Information Systems，2015，11（18）：6605-6612.3 Tao Zhou，Akil Narayan，ZhiqiangXu.Multivariate Discrete