[發(fā)明專利]一種基于模式關聯(lián)分析的實值時間序列規(guī)則發(fā)現(xiàn)方法和裝置

在審

• 申請?zhí)枺?/td>: 201810241305.X
• 申請日: 2018-03-22
• 公開（公告）號: CN108647223A
• 公開（公告）日: 2018-10-12
• 發(fā)明（設計）人: 王亞沙;何遠舵;彭廣舉;初旭;王江濤
• 申請（專利權）人: 北京大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京君尚知識產(chǎn)權代理事務所(普通合伙) 11200
• 代理人: 邱曉鋒

1.一種基于模式關聯(lián)分析的實值時間序列規(guī)則發(fā)現(xiàn)方法，其特征在于，包括以下步驟：

1)針對一個或多個實數(shù)值的目標時間序列，利用主題發(fā)現(xiàn)技術從中自動提取多種長度的主題模式；

2)針對每一對主題模式，根據(jù)其在時間序列中出現(xiàn)的位置以及間隔，分析兩者之間的配對關系；

3)根據(jù)一對主題模式的配對結果，對該對主題模式所構成的候選規(guī)則進行評分，并選擇評分超過預設的閾值的候選規(guī)則作為規(guī)則。

2.如權利要求1所述的方法，其特征在于，步驟1)所述主題發(fā)現(xiàn)技術基于MK算法，提取主題模式的步驟包括：

1-1)給定主題模式長度參數(shù)m，用長為m的滑動窗口提取目標時間序列的全部子序列，選擇其中一個子序列作為參考點，計算其他子序列到該子序列的z變換后的歐氏距離；

1-2)將得到的歐式距離按照從小到大排列，然后計算相鄰兩點的到參考點距離的差；按距離差從小到大的順序計算相應兩點的真實距離，并記錄當前最小值，當該最小值小于當前待計算的兩點相對距離的差時，停止計算，當前最小值所對應的兩個子序列則是主題模式。

3.如權利要求2所述的方法，其特征在于，步驟1)在應用MK算法時，排除時間窗口相鄰的子序列，其方法是：設置一個排除區(qū)間，該排除區(qū)間的長度是子序列長度的一半，即m/2，當兩個子序列的起始位置之差小于m/2時，這兩個子序列的真實距離記為正無窮。

4.如權利要求2所述的方法，其特征在于，步驟1)在應用MK算法之前，對不感興趣的子序列進行過濾；通過度量子序列是否有意義來判斷是否為感興趣的子序列，度量子序列是否有意義的公式是：

其中Roughness(s)表示時間序列子序列s的曲折程度，曲線越曲折，該值越大；該公式假設時間序列所描述的對象沒有事件發(fā)生時，感知信號是平坦的，而當有意義事件發(fā)生時，感知信號是曲折的。

5.如權利要求2所述的方法，其特征在于，步驟1)在應用MK算法時，一次只找到屬于同一個主題中的最近的兩個子序列，然后尋找其他同樣屬于該主題的子序列；找到同屬于同一個主題的子序列之后，進一步尋找相同長度的其他主題的子序列。

6.如權利要求5所述的方法，其特征在于，所述尋找其他同樣屬于該主題的子序列的方法是：

給定一個范圍參數(shù)R，R＞1，記兩個已經(jīng)找到的子序列為s₁,s₂，考慮滿足如下公式中任意一個的子序列s：

遍歷這些子序列，計算它們到s₁或s₂的真實距離，如果該距離滿足以下公式，則將這些子序列加入該主題的子序列中，

7.如權利要求5所述的方法，其特征在于，所述尋找相同長度的其他主題的子序列，結合MK算法和過濾，當找到一個主題的全部子序列之后，將這些子序列過濾掉，然后對剩余子序列重新利用MK算法。

8.如權利要求1所述的方法，其特征在于，步驟2)通過計算以下兩個優(yōu)化問題來分析一對主題模式的配對關系，其中x_i,j是待關聯(lián)的兩個主題中第i個子序列和第j個子序列的關聯(lián)關系，取值是1或0；1代表兩者存在配對關系，0代表兩者不存在配對關系；w_i,j為這兩個子序列之間的時間間隔；

第一個優(yōu)化問題：

x_i,j∈{0,1}；

第二個優(yōu)化問題：

x_i,j∈{0,1}，

∑x_i,j＝p；

其中，第一個優(yōu)化問題試圖尋找盡可能多的配對數(shù)目，記求解該問題能夠找到最多配對數(shù)目是p；然后求解第二個優(yōu)化問題，該問題試圖尋找配對個數(shù)是p時，平均時間間隔最小的配對情形。