[發明專利]時序數據的模體識別方法和裝置

在審

• 申請號: 201310681366.5
• 申請日: 2013-12-12
• 公開（公告）號: CN104714953A
• 公開（公告）日: 2015-06-17
• 發明（設計）人: 劉博;陳成;李建強
• 申請（專利權）人: 日本電氣株式會社
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京三高永信知識產權代理有限責任公司 11138
• 代理人: 張耀光

技術領域

本發明涉及時序數據分析領域，特別涉及一種時序數據的模體識別方法和裝置。

背景技術

隨著統計學的發展，越來越多的數據呈時序數據的形式。其中，時序數據是指按照時間順序記錄的數據。例如，股票市場的每日波動數據、每年的降雨量數據、每年的交通狀況數據等。在這些時序數據中，存在著一些重復出現的相似子序列，這些重復出現的相似子序列被稱為模體。由于時序數據中的模體對科學研究有十分重要的意義，因此，如何在大規模的時序數據中識別出模體，是研究時序數據問題的關鍵。

在現有的時序數據的模體識別方法中，常見的識別方法有兩種：精確識別方法和概率識別方法。對于精確識別方法，文章Exact?Discovery?of?Series?Motifs,A.Mueen.SIAM?International?Conference?on?Data?Mining-SDM,pp.473-484,2009提出掃描時序數據中所有的子序列，并計算掃描到的每兩個子序列之間的歐氏距離，進而將歐氏距離滿足條件的每兩個子序列作為從該時序數據中識別出的模體。

對于概率識別方法，文章Probabilistic?discovery?of?time?series?motifs,Chiu?B,Keogh?E,Lonardi?S,Proceedings?of?the?ACM?IGKDD?international?conference?on?Knowledge?discovery?and?data?mining.ACM,2003:493-498提出將時間序列劃分為一系列的數據子序列后，采用SAX（Symbolic?Aggregate?approXimation，符號集近似）方法將劃分后的數據子序列轉化為符號子序列，再對每個符號子序列進行隨機投影，記錄每個符號子序列與其他符號子序列在投影位置上具有相同符號的次數，將記錄的次數中達到一定閾值的次數所對應的數據子序列作為識別出的模體。

在實現本發明的過程中，發明人發現現有技術至少存在以下問題：

由于上述精確識別方法需要計算掃描到的每兩個數據子序列之間的歐氏距離，當掃描到的數據子序列的數量很大時，計算掃描到的每兩個數據子序列之間的歐氏距離的計算量很大，致使識別模體的速度較慢。

而上述概率識別方法通過符號化及隨機投影將時序數據進行了離散化和降維處理，導致一些可能成為模體的時序數據信息的丟失，并使得存在較大位移差且原本在需要分析的時序數據中重復出現的概率不高的數據子序列可能被識別為模體，因此，概率識別方法所識別出的模體的準確性不高；另外，當一個符號子序列與其他符號子序列在投影位置上具有相同符號的次數達到一定閾值時，對應的數據子序列才被識別為模體，導致與其他符號子序列在投影位置上具有相同符號的次數未達到閾值的有些模體無法被識別出來，因而通過概率識別方法識別出的模體數量有限，進一步降低了模體識別的準確性。

發明內容

為了解決現有技術的問題，本發明實施例提供了一種時序數據的模體識別方法和裝置。所述技術方案如下：

第一方面，提供了一種時序數據的模體識別方法，所述方法包括：

獲取需要分析的時序數據，將所述需要分析的時序數據分割成至少兩個數據子序列，并對每個數據子序列進行符號化處理，得到至少兩個符號子序列；

對所述符號子序列進行預設次數的隨機投影，并記錄投影的每個符號子序列與投影的其他符號子序列在投影位置上具有相同符號的次數；

計算記錄的次數中超過閾值的次數所對應的兩個數據子序列之間的距離，將距離小于第一預設距離的兩個數據子序列作為識別出的標準模體；

對每個預設范圍內的標準模體進行聚類，得到每個預設范圍內的一個中心數據子序列，并根據每個預設范圍內的標準模體與中心數據子序列計算每個預設范圍的方差；

縮小所述閾值，并計算記錄的次數中超過縮小后的閾值的次數所對應的兩個數據子序列與其所在預設范圍內的中心數據子序列之間的距離，將距離小于所在預設范圍的方差的數據子序列作為識別出的模體。

結合第一方面，在第一方面的第一種可能的實現方式中，所述得到至少兩個符號子序列之后，還包括：

將所述符號子序列中至少兩個連續的符號相同的符號子序列進行壓縮，得到壓縮符號子序列；

所述對所述符號子序列進行預設次數的隨機投影，包括：

對所述符號子序列中未壓縮的符號子序列進行預設次數的隨機投影。