[發(fā)明專利]一種多度量時(shí)間序列相似分析方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310508432.9
• 申請(qǐng)日: 2013-10-24
• 公開（公告）號(hào): CN103577562A
• 公開（公告）日: 2014-02-12
• 發(fā)明（設(shè)計(jì)）人: 王繼民;朱躍龍;李士進(jìn);萬定生;馮鈞
• 申請(qǐng)（專利權(quán)）人: 河海大學(xué)
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 南京蘇高專利商標(biāo)事務(wù)所(普通合伙) 32204
• 代理人: 李玉平

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

本發(fā)明涉及一種多度量時(shí)間序列相似分析方法，尤其是能夠進(jìn)行多度量組合的k-近鄰相似時(shí)間序列分析的方法，屬于數(shù)據(jù)挖掘技術(shù)領(lǐng)域。

背景技術(shù)

時(shí)間序列相似性查找就是在時(shí)間序列數(shù)據(jù)庫中查找和發(fā)現(xiàn)與給定模式相似的時(shí)間序列，查找相似子序列的過程在實(shí)際問題中經(jīng)常遇到，例如，在人類的基因組計(jì)劃中，從DNA基因序列中查找出與給定的基因片段相似的子片段，根據(jù)遺傳的相似性進(jìn)行研究；根據(jù)各種商品的銷售記錄，找出具有相似的商品銷售模式，根據(jù)相似產(chǎn)品的銷售模式來制定相似的銷售策略等；找出自然災(zāi)害發(fā)生的相同前兆，從而對(duì)預(yù)報(bào)自然災(zāi)害進(jìn)行決策研究；在水文領(lǐng)域，找出與當(dāng)前洪水過程相似的歷史洪水過程，回答防汛指揮中經(jīng)常會(huì)想到的“當(dāng)前水文過程與歷史上哪一時(shí)期的水文過程類似”等問題。

相似性搜索在1993年由R.Agrawal首次提出，他是時(shí)間序列預(yù)測(cè)、分類、聚類以及序列模式挖掘等等的重要基礎(chǔ)。時(shí)間序列相似性查找與傳統(tǒng)的精確查詢不同，由于時(shí)間序列在數(shù)值上具有連續(xù)性以及有不同的噪聲影響，因此，大部分情況下不需要時(shí)間序列很精確匹配。另一方面是時(shí)間序列相似性查詢不是針對(duì)時(shí)間序列中的某個(gè)具體的數(shù)值，而根據(jù)給定的查詢序列來找查找是在一段時(shí)間內(nèi)具有相似形態(tài)特征和變化趨勢(shì)的時(shí)間序列。在時(shí)間序列相似性搜索中，需解決的問題包括時(shí)間序列特征提取、時(shí)間序列索引以及相似度量等。針對(duì)相似度量，研究人員提出了各種度量方法，如歐氏距離及其基于Lp準(zhǔn)則的變種、動(dòng)態(tài)時(shí)間彎曲距離（Dynamic?Time?Warping，DTW）、編輯距離（Edit?Distance,ED）、模式距離(Pattern?Distance,PD)、以及最長(zhǎng)公共子串（Longest?Common?Subsequence,LCSS）等。

目前時(shí)間序列相似性搜索大多采用單一相似度量來評(píng)價(jià)序列之間的相似性，每個(gè)相似度量只從某個(gè)角度評(píng)價(jià)序列之間的相似程度，如，模式距離、斜率距離等從序列形態(tài)角度考慮相似，歐式距離則從序列取值的實(shí)際大小考慮相似，動(dòng)態(tài)時(shí)間彎曲DTW可以忽略序列在時(shí)間上的扭曲。在實(shí)際使用時(shí)發(fā)現(xiàn)，往往運(yùn)用單一的相似度量模型，不能同時(shí)從多個(gè)角度對(duì)時(shí)間序列相似性進(jìn)行多角度評(píng)價(jià)，反饋的結(jié)果往往不準(zhǔn)確，不能滿足用戶對(duì)時(shí)間序列相似性的綜合評(píng)價(jià)。模式識(shí)別與機(jī)器學(xué)習(xí)研究領(lǐng)域，有一個(gè)很重要的問題就是多分類器的組合問題，目前眾多的研究表明，多分類器組合能獲得比單個(gè)基分類器更好的效果，多個(gè)分類器組合在一起的決策結(jié)果，往往比單個(gè)分類器給出決策結(jié)果更有說服力，它可以集中各個(gè)基分類器的優(yōu)點(diǎn)，從而更好的引導(dǎo)我們的進(jìn)行決策。在時(shí)間序列相似性分析研究領(lǐng)域，多度量組合進(jìn)行相似性分析目前文獻(xiàn)較少。Fabris?F提出一種基于權(quán)重的多度量時(shí)間序列相似性分析[Fabris?F,Drago?I,F?M.A?multi-measure?nearest?neighbor?algorithm?for?time?series?classification.Advances?in?Artificial?Intelligence–IBERAMIA2008.Springer?Berlin?Heidelberg,2008:153-162.]，采用啟發(fā)式搜索確定各度量的權(quán)重，相似距離為各度量距離的加權(quán)和，該方法需要花費(fèi)大量時(shí)間尋求最優(yōu)的權(quán)重向量，同時(shí)需要預(yù)先確定訓(xùn)練集。本發(fā)明借鑒BORDA計(jì)數(shù)法并對(duì)其進(jìn)行改進(jìn)，提出帶優(yōu)勢(shì)權(quán)重的多分類器組合法，然后對(duì)多相似度量產(chǎn)生的候選相似序列（子序列）進(jìn)行組合排序，以獲取最終的相似序列（子序列）。

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

發(fā)明目的：本發(fā)明提供一種多度量時(shí)間序列相似性分析方法，提高時(shí)間序列相似性分析的效率。

為了實(shí)現(xiàn)上述目的，本發(fā)明借鑒BORDA計(jì)數(shù)法并對(duì)其進(jìn)行改進(jìn)，提出帶優(yōu)勢(shì)權(quán)重的多分類器組合法以適應(yīng)對(duì)各單一相似度量的相似序列（子序列）進(jìn)行組合排序的需求，并在此基礎(chǔ)上提供了一種多度量時(shí)間序列k-近鄰分析方法。時(shí)間序列相似性分析從被查詢的對(duì)象來分可以包括全序列查詢（Whole?Match）和子序列查詢（Subsequence?Match）。全序列查詢，即待查時(shí)間序列中包括多個(gè)等長(zhǎng)或不等長(zhǎng)的時(shí)間序列，指定查詢序列，從待查序列中查找與查詢序列相似的序列。子序列查詢，即從一個(gè)長(zhǎng)的待查時(shí)間序列中查找與指定查詢序列相似的子序列，結(jié)果包括各相似子序列在待查序列中的偏移位置。本發(fā)明的多度量時(shí)間序列相似性分析方法適用于全序列和子序列的k-近鄰查詢。

技術(shù)方案：一種多度量時(shí)間序列相似分析方法，包括以下步驟：