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

在審

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

本發(fā)明涉及一種基于模式關(guān)聯(lián)分析的實(shí)值時(shí)間序列規(guī)則發(fā)現(xiàn)方法和裝置。該方法包括以下步驟：1)針對一個(gè)或多個(gè)實(shí)數(shù)值的目標(biāo)時(shí)間序列，利用主題發(fā)現(xiàn)技術(shù)從中自動(dòng)提取多種長度的主題模式；2)針對每一對主題模式，根據(jù)其在時(shí)間序列中出現(xiàn)的位置以及間隔，分析兩者之間的配對關(guān)系；3)根據(jù)一對主題模式的配對結(jié)果，對該對主題模式所構(gòu)成的候選規(guī)則進(jìn)行評分，并選擇評分超過預(yù)設(shè)的閾值的候選規(guī)則作為規(guī)則。該裝置包括主題模式發(fā)現(xiàn)模塊、主題模式關(guān)聯(lián)分析模塊和規(guī)則評分模塊。本發(fā)明能夠高效地自動(dòng)提取蘊(yùn)含有意義信息的模式；可以根據(jù)使用者需求調(diào)整模式的偏好；通過模式間的關(guān)聯(lián)關(guān)系能夠找到有一定關(guān)聯(lián)關(guān)系規(guī)則，避免了無效規(guī)則。

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

本發(fā)明涉及一種實(shí)值時(shí)間序列規(guī)則發(fā)現(xiàn)方法，屬于時(shí)間序列數(shù)據(jù)挖掘領(lǐng)域，具體涉及一種基于模式關(guān)聯(lián)分析的實(shí)值時(shí)間序列規(guī)則發(fā)現(xiàn)方法和裝置。

背景技術(shù)

隨著傳感器和物聯(lián)網(wǎng)技術(shù)的發(fā)展，我們可以輕松地感知收集信息空間和物理空間中對象的感知數(shù)據(jù)。這些數(shù)據(jù)往往隨時(shí)間采樣得到，天然形成了實(shí)值時(shí)間序列數(shù)據(jù)。由于感知對象之間往往存在著關(guān)聯(lián)關(guān)系，這些關(guān)系也會(huì)相應(yīng)地體現(xiàn)在它們的時(shí)間序列數(shù)據(jù)上。這種時(shí)間序列上存在的關(guān)聯(lián)關(guān)系稱之為規(guī)則。挖掘這些規(guī)則能夠發(fā)掘數(shù)據(jù)背后對象間的相互作用關(guān)系，有助于理解對象間的關(guān)聯(lián)關(guān)系。此外，利用這些規(guī)則也可以實(shí)現(xiàn)預(yù)測等任務(wù)。

1998年Das等人最早提出了一種針對實(shí)值時(shí)間序列數(shù)據(jù)規(guī)則發(fā)現(xiàn)的方法。該方法首先利用子序列聚類符號(hào)化原始的實(shí)值時(shí)間序列，然后基于J-measure為所有可能的規(guī)則進(jìn)行評分，最終選擇分高的作為規(guī)則。然而，這種方法理論上雖然可行，但是在實(shí)際使用中子序列聚類會(huì)丟失原始時(shí)間序列中的大量信息，導(dǎo)致最終找到的規(guī)則完全無法使用。

2015年，Yekta等人在KDD數(shù)據(jù)挖掘會(huì)議上提出了一種基于子序列劃分的規(guī)則發(fā)現(xiàn)方法。該方法假定規(guī)則位于時(shí)間序列的子序列中，然后把子序列切分為兩段，前段是規(guī)則的前件，而后段則是規(guī)則的后件。為了快速定位規(guī)則可能存在的子序列，該方法進(jìn)一步采用了主題發(fā)現(xiàn)(motif discovery)技術(shù)，把主題子序列作為待切分的目標(biāo)子序列，從而加快規(guī)則的發(fā)現(xiàn)過程。然而，規(guī)則前件和后件之間通常會(huì)存在一定的時(shí)間間隔，這種基于切分的方法會(huì)把間隔中的子序列劃分到規(guī)則的前件或后件當(dāng)中，從而使得規(guī)則不準(zhǔn)確。除此之外，這一方法也無法應(yīng)用于多時(shí)間序列的情景。

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

本發(fā)明主要是解決現(xiàn)有技術(shù)所存在的問題，提出了一種基于模式關(guān)聯(lián)分析的實(shí)值時(shí)間序列規(guī)則發(fā)現(xiàn)方法和裝置。利用該方法，可以自動(dòng)地從實(shí)數(shù)值時(shí)間序列中提取有意義的關(guān)聯(lián)規(guī)則，進(jìn)而可以實(shí)現(xiàn)數(shù)據(jù)的理解或預(yù)測。

本發(fā)明的上述技術(shù)問題主要是通過下述技術(shù)方案得以解決的：

一種基于模式關(guān)聯(lián)分析的實(shí)值時(shí)間序列規(guī)則發(fā)現(xiàn)方法，包括：

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

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

規(guī)則評分步驟，根據(jù)一對主題模式的配對結(jié)果，對該對主題模式所構(gòu)成的候選規(guī)則進(jìn)行評分，根據(jù)評分高低排列候選規(guī)則，根據(jù)實(shí)際應(yīng)用問題設(shè)定閾值，選擇評分超過閾值的候選規(guī)則作為最終規(guī)則。

優(yōu)化的，上述的一種基于模式關(guān)聯(lián)分析的時(shí)間序列規(guī)則發(fā)現(xiàn)方法，所述主題模式發(fā)現(xiàn)步驟中，所述主題發(fā)現(xiàn)技術(shù)基于MK算法：

給定主題模式長度參數(shù)m，用長為m的滑動(dòng)窗口提取目標(biāo)時(shí)間序列的全部子序列，選擇其中一個(gè)子序列作為參考點(diǎn)，記為s₀，計(jì)算其他子序列到該子序列的z變換后的歐氏距離，z變換和歐氏距離的具體公式是(1)、(2)，其中s表示一個(gè)子序列，mean(s)表示子序列s的平均值，std(s)表示子序列s的標(biāo)準(zhǔn)差。