[發(fā)明專利]實時數(shù)據(jù)流模式識別應(yīng)用的數(shù)據(jù)補全方法

有效

• 申請?zhí)枺?/td>: 201410737932.4
• 申請日: 2014-12-05
• 公開（公告）號: CN104484673B
• 公開（公告）日: 2017-10-20
• 發(fā)明（設(shè)計）人: 呂建;汪亮;陶先平
• 申請（專利權(quán)）人: 南京大學(xué)
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 南京蘇高專利商標(biāo)事務(wù)所(普通合伙)32204
• 代理人: 李玉平

技術(shù)領(lǐng)域

本發(fā)明涉及一種針對實時數(shù)據(jù)流模式識別應(yīng)用的數(shù)據(jù)補全方法，屬于計算機應(yīng)用領(lǐng)域，針對實時數(shù)據(jù)流采集與傳輸中常見的因設(shè)備性能限制、網(wǎng)絡(luò)通信質(zhì)量波動等原因造成的數(shù)據(jù)缺失問題，結(jié)合在線實時模式識別應(yīng)用的特性，實現(xiàn)了一種高效的數(shù)據(jù)補全方法。

背景技術(shù)

隨著物聯(lián)網(wǎng)相關(guān)技術(shù)，如無線傳感器網(wǎng)絡(luò)、可穿戴式感知和計算設(shè)備的快速發(fā)展，計算機系統(tǒng)能夠不斷地獲取外部環(huán)境感知數(shù)據(jù)并進行處理。這些由大量傳感器節(jié)點不間斷感知到的數(shù)據(jù)通過無線網(wǎng)絡(luò)等傳輸手段實時匯總到處理節(jié)點，就形成了潛在無窮的實時數(shù)據(jù)流。這些實時數(shù)據(jù)流經(jīng)過處理后，能夠通過模式識別等技術(shù)，從中提取出擁有高抽象層次的、豐富語義的、有用的信息，來服務(wù)于人類。

由于無線網(wǎng)絡(luò)傳輸?shù)牟豢煽啃浴挼木窒扌浴⒏黝悅鞲衅鞫〞r睡眠等原因，處理節(jié)點接收到的實時數(shù)據(jù)流往往存在數(shù)據(jù)的缺失。而與實時數(shù)字信號處理和流媒體播放類應(yīng)用不同，模式識別算法旨在從底層數(shù)據(jù)流中抽取出有用的特征，從而識別出具有高抽象層次、豐富語義的、有用的信息。數(shù)據(jù)補全方法是模式識別應(yīng)用中應(yīng)對數(shù)據(jù)缺失問題的重要技術(shù)，傳統(tǒng)的方法往往采用在缺失處填入固定默認值、或最近的一次獲得的數(shù)據(jù)的方式來對缺失數(shù)據(jù)進行補全。但是由于這種方法沒有很好地契合模式識別類應(yīng)用的特點，因此其效果往往不是特別顯著。

發(fā)明內(nèi)容

發(fā)明目的：為了克服傳統(tǒng)方法數(shù)據(jù)補全效果差的不足，本發(fā)明從針對實時流數(shù)據(jù)的模式識別類應(yīng)用的特點出發(fā)，提出了一種使用在線緩存數(shù)據(jù)的、低冗余、高效的數(shù)據(jù)補全方法。在高效的同時，該數(shù)據(jù)補全方法對輸入數(shù)據(jù)特征、后續(xù)模式識別方法和其它系統(tǒng)組件實現(xiàn)方案不作任何預(yù)設(shè)，能夠無縫、透明地插入和拔出應(yīng)用系統(tǒng)數(shù)據(jù)處理流程，靈活滿足不同應(yīng)用場景的需求。

從一般意義上說，模式識別類應(yīng)用具有以下三個特點：1)對數(shù)據(jù)缺失敏感：數(shù)據(jù)缺失造成的信息丟失，會對特征提取的質(zhì)量造成嚴重影響，進而影響模式識別算法的準(zhǔn)確性；2)從模式識別結(jié)果角度看，數(shù)據(jù)具有本地化特性：高層抽象信息表現(xiàn)為包含豐富語義信息的類別，與實時原始數(shù)據(jù)不同，類別的變化頻率相對緩慢，因此，在考慮數(shù)據(jù)對應(yīng)的類別時，呈現(xiàn)出本地化的特性(即，數(shù)據(jù)所對應(yīng)的類別在一段時間內(nèi)不改變)；3)冗余信息價值不大：重復(fù)的、冗余的數(shù)據(jù)對于提取有用特征的價值不大。

根據(jù)以上三個特點，我們確定了針對模式識別應(yīng)用的數(shù)據(jù)補全算法需求，提出了利用歷史數(shù)據(jù)進行補全的方法，提出了相應(yīng)的完整性指標(biāo)和抗冗余的數(shù)據(jù)補全算法。具體來說，本發(fā)明所提出的針對實時流數(shù)據(jù)模式識別應(yīng)用的數(shù)據(jù)補全方法，包含一個運行時在線數(shù)據(jù)緩存，一項數(shù)據(jù)完整性指標(biāo)、和一個基于滑動窗口的迭代式抗冗余數(shù)據(jù)補全算法。該數(shù)據(jù)補全方法對于模式識別應(yīng)用的其他組件透明，可以方便地應(yīng)用于已部署的系統(tǒng)中增強系統(tǒng)的抗數(shù)據(jù)丟失能力，也可以在需要時隨時關(guān)閉而不影響系統(tǒng)其他組件的正常運行。

技術(shù)方案：一種實時數(shù)據(jù)流模式識別應(yīng)用的數(shù)據(jù)補全方法，其具體過程包含以下步驟：

1)數(shù)據(jù)源連續(xù)產(chǎn)生數(shù)據(jù)形成輸入數(shù)據(jù)流，設(shè)數(shù)據(jù)率已知為每秒r個采樣值(r根據(jù)應(yīng)用場景確定，為正實數(shù))，輸入數(shù)據(jù)存儲于運行時在線數(shù)據(jù)緩存，記緩存的數(shù)據(jù)為D；

2)以當(dāng)前時刻t為起點，使用大小為w秒(w根據(jù)應(yīng)用場景確定，為正實數(shù))的滑動窗口在緩存的數(shù)據(jù)中向前截取一段D[t-w,t]作為當(dāng)前窗口數(shù)據(jù)；

3)在當(dāng)前窗口數(shù)據(jù)D[t-w,t]的基礎(chǔ)上，結(jié)合已知數(shù)據(jù)源的數(shù)據(jù)率r、滑動窗口大小w，計算數(shù)據(jù)完整性指標(biāo)c；

4)若當(dāng)前窗口數(shù)據(jù)D[t-w,t]的完整性指標(biāo)c不達標(biāo)，則從前一個窗口的數(shù)據(jù)D[t-2w,t-w]中以最小冗余為原則，選取數(shù)據(jù)補充填入當(dāng)前窗口D[t-w,t]，若補全后完整性指標(biāo)c達到標(biāo)準(zhǔn)則算法結(jié)束，否則迭代執(zhí)行本步驟直至完整性指標(biāo)c達到標(biāo)準(zhǔn)或窮盡緩存中的所有數(shù)據(jù)。

其中，步驟1)的具體過程為：

1.1)創(chuàng)建動態(tài)大小的在線運行時緩存D；

1.2)將數(shù)據(jù)源產(chǎn)生的數(shù)據(jù)存入D，并按照數(shù)據(jù)獲取時間遞增排序；

1.3)根據(jù)上層模式識別應(yīng)用的需求，定義D中緩存數(shù)據(jù)最長的保留時間為h秒(h為w的整數(shù)倍)，以避免緩存過于陳舊的數(shù)據(jù)。

其中，步驟2)的具體過程為：

2.1)根據(jù)上層模式識別應(yīng)用的需求，定義滑動窗口的大小w秒為合理的數(shù)據(jù)在時間上的分片粒度；

2.2)以當(dāng)前時刻t為起點，向前回溯讀取緩存D中以t-w時刻開始到t時刻結(jié)束的一段數(shù)據(jù)D[t-w,t]作為當(dāng)前滑動窗口的數(shù)據(jù)。

其中，步驟3)的具體過程為：