基于相關反饋的時間序列相似性搜索

劉 琪,張鵬程,王繼民

(河海大學計算機與信息學院,江蘇 南京 211100)

0 引 言

數(shù)據挖掘是從大型數(shù)據庫的數(shù)據中提取人們感興趣的、隱含的和事先未知的知識的過程[1]?，F(xiàn)實中，絕大部分的數(shù)據都是時序數(shù)據，因此，從時序數(shù)據中挖掘潛在的有用知識具有重要的理論和實踐意義。時序數(shù)據就是帶有時間標簽的一系列觀測值，觀測值可能會隨時間變化而變化。針對時序數(shù)據的挖掘研究，主要包括時序數(shù)據的關聯(lián)、分類、聚類、序列模式挖掘、相似搜索以及預測，其中，相似性檢索是其他研究的重要基礎。相似性檢索由Agrawal[2]首次提出，廣義的相似性搜索是在時間序列數(shù)據集中發(fā)現(xiàn)相似的變化模式。例如，根據各種商品的銷售記錄，找出相似的商品銷售模式，幫助制定相似的銷售策略[3]；找出自然災害發(fā)生的相同前兆，實現(xiàn)對自然災害進行預報研究等[4]。

傳統(tǒng)時間序列相似性搜索，先提取數(shù)據特征以降低數(shù)據維度[5-7]，然后對特征數(shù)據建立索引[8-10]，最后基于相似性度量函數(shù)[11-13]，在索引結構中檢索與查詢序列相似的序列，并將結果展示給用戶。而實際應用中，用戶開始時可能并不能明確描述所要查詢的序列，因此一次檢索的結果往往不能滿足用戶的需求?；诜答伒牟呗允?，通過用戶對查詢結果的反饋來修正查詢系統(tǒng)，以提高查詢精度以及用戶的滿意度。

相關反饋技術最早應用于信息檢索領域，Keogh等人1998年在文獻[14]中首次將相關反饋引入到時間序列中，由用戶對查詢結果設置不同的權值，表示其與查詢序列相似或不相似程度的高低，通過反饋與給定序列疊加產生新的查詢序列，再次進行查詢。文獻[15]提出一種基于多樣化相關反饋的時間序列搜索方法，對用戶標注的相關序列采用MMR方法[16]保證查詢結果的多樣性，然后組合產生新查詢序列并再次進行檢索，通過查詢結果的多樣性保證出現(xiàn)貼近用戶意向的結果。

上述的幾種時間序列反饋方法均限于正相關反饋，忽略了負相關序列的價值。Wang等人[17]針對由于查詢主題較少造成查詢困難的情況，在文本檢索領域提出一種負相關反饋學習的方法，要求查詢結果向量不但要與查詢向量相似，同時要盡量與負相關向量不相似。Peltonen等人[18]提出了一種基于機器學習的負反饋信息檢索系統(tǒng)，允許用戶直接在交互式可視界面上進行正負反饋，研究表明負相關反饋同樣也可以提高檢索效率。本文在時間序列相似性領域，提出一種基于相關反饋的時間序列相似搜索方法。

1 基于相關反饋的時間序列相似性檢索

1.1 基于向量模型的反饋算法

基于向量模型的反饋算法一般通過查詢修改來實現(xiàn)，查詢修改由Van Rijsbergen在1986年首次在信息檢索領域提出[19]。通過對原查詢進行修改，并反饋給查詢系統(tǒng)重新查詢，以提高系統(tǒng)檢索性能，查詢擴展技術已經成為改善信息檢索的查全率和查準率的關鍵技術之一。

1)Rocchio算法。

經典的反饋算法是由Rocchio在SMART系統(tǒng)[20]中提出，其修改查詢向量的公式如下：

(1)

其中，qnew是新的查詢向量，q是原始向量，Dr是已知的相關文檔集合，Dnr是已知的不相關文檔集合，α，β及γ是三者的權重，能夠控制新的查詢向量和原始查詢向量之間的平衡，這些權值的最優(yōu)值可以憑經驗或對數(shù)據的認識進行賦值，也可以通過實驗確定。

2)Ide dec-hi算法。

(2)

3)負反饋。

上述的2種反饋算法都較大程度地依賴正相關反饋，當查詢主題較為困難即正相關樣本很少或沒有時，難以發(fā)揮作用。Wang等人[17]針對這種較為極端的情況提出了一種負相關反饋的算法，該算法通過分別建立正查詢(依據查詢向量進行相似性度量)和負查詢(由負相關向量組成查詢向量，并依據它進行相似度量)，最后通過組合得到相似程度。如公式(3)所示，其中D表示待查文檔向量，Q表示原始查詢向量也是正查詢向量，S(Q,D)為正查詢的相似結果，Qneg表示負查詢向量，S(Qneg,D)為負查詢的相似結果，Scombine(Q,D)為最終的Q和D相似程度。由該公式可以看出要想D和Q相似程度高，則D必須遠離Qneg。

Scombine(Q,D)=S(Q,D)-β×S(Qneg,D)

(3)

1.2 基于相關反饋的時間序列相似性查詢方法

上述的前2種反饋都是將正負反饋融合在一起創(chuàng)建新查詢向量，這樣并沒有充分利用負反饋序列的價值，而且容易對初始查詢向量進行過多的更改，本文在時間序列相似性領域引入上述的負反饋策略，提出一種基于相關反饋的時間序列相似搜索方法，將正反饋和負反饋分開進行。用戶對查詢結果標注出正相關的序列以及負相關的序列，通過正相關序列修改查詢序列進行查詢擴展，通過負反饋分別建立正查詢和負查詢，最后通過組合得出最終的相似度，并按照相似度排序展示給用戶。主要包括：1)修改查詢序列；2)正查詢和負查詢組合。

1.2.1 查詢序列修改

時間序列相似性檢索也是一種信息檢索，因此，可以通過修改查詢序列來使得查詢結果更加全面，由于Rocchio算法是較為成熟可用的查詢修改公式，本文采用公式(1)作為查詢序列修改的原型公式。通常用戶給的初始查詢序列是能表達其大部分意圖，查詢序列修改僅做一些微調，因此為了保證修改后的查詢序列與原序列不會偏離很大，故將α取值為1。本文中負相關序列用于調整結果序列與查詢序列的相似度，不參與組合產生新查詢序列，因此將γ取為0。在本文中用qnew表示新的查詢序列，q為舊的查詢序列，si表示相關序列(本文中認為用戶所有的標注都是正確標注)。此時公式(1)變形為：

(4)

因為si是正相關序列，即用戶感興趣的序列，所以得到的序列qnew從理論上來說也應該是用戶滿意的序列。

算法1查詢修改算法

輸入：查詢序列q，權重α,β，正相關序列集Sr=(s1,s2,…,sn)

輸出：新的查詢序列qnew

1 sr=s1//初始化sr

2 for j=1 to m do //設數(shù)據集中各序列均是m維的向量

3 begin

4 for i=2 to n do

5 begin //將相關序列集合同一維數(shù)據相加取平均值存到序列sr

6 sr[j]=(1/i)*(sr[j]+si[j])； //初始sr[j]表示序列sr中第j維的數(shù)據

7 end

8 qnew[j]=α*q[j]+β*sr[j]；

9 end

1.2.2 正負查詢組合

正查詢是依據新的查詢序列進行相似性度量，負查詢就是由負相關序列組成一個查詢序列，并依據它在數(shù)據集中查詢相似序列。相似度量公式如下：

Sc(qnew,si)=Sim(qnew,si)-λSim(qneg,si)

(5)

其中,qneg是負相關序列組成的查詢序列，λ為控制負相關序列影響大小的參數(shù)。λ取值可以根據經驗設定或者通過實驗確定最優(yōu)的取值。Sc(qnew,si)代表si與qnew最終的相似程度。Sim(qnew,si)即序列si與查詢序列qnew的相似程度。由該公式可知，要想Sc(qnew,si)的值高，要么Sim(qnew,si)的值高，即qnew與si的相似程度高；要么Sim(qneg,si)的值低，即qneg與si的相似程度低。

算法2正負查詢組合

輸入：查詢序列qnew，負相關序列qneg，數(shù)據集S=(s1,s2,…,sn)以及參數(shù)β

輸出：數(shù)據集S中序列si與查詢序列qnew的相似度Sc(qnew,si)

1 for i=1 to n do

2 begin

3 計算si與qnew的相似程度Sim(qnew,si)；

4 計算si與qneg的相似程度Sim(qneg,si)；

5 計算組合相似度Sc(qnew,si)=Sim(qnew,si)-λSim(qneg,si)

6 end

在算法中主要需要解決的問題是,確定si與負相關序列的相似程度Sim(qneg,si)。本文提出了2種策略，一種是單負相關反饋模型，另一種是多負相關反饋模型。

1)單負相關反饋模型。

2)多負相關反饋模型。

查詢結果中的負相關序列可能包含多個類別，單負反饋將所有負相關序列合并為一個負相關序列，不能體現(xiàn)不同類別的負相關序列的差異。多負相關模型先對負相關序列進行聚類，并將每一類合并成一個序列，然后再分別進行負查詢。假設聚為m類，每類序列合并得到qneg1′，qneg2′，…，qnegm′，分別計算qneg1′，qneg2′，…，qnegm′和序列集中的序列si的相似程度，選擇其中最為相似的一組，記為max(Sim(qneg,si))。公式(5)則變形為下列公式：

Sc(qnew,si)=Sim(qnew,si)-λmax(Sim(qneg,si))

(6)

2 實驗驗證與分析

2.1 實驗數(shù)據與方法

本文采用UCR數(shù)據集[22]中的17組子數(shù)據集進行實驗，每個數(shù)據集中所有序列都已經被標注類別。UCR數(shù)據集中標注的類別是分類得來的，而分類是根據它們的相似程度進行，因此，在同一個類別的序列是具有一定相似性的。各子數(shù)據集的信息如表1所示。

表1 各子數(shù)據集特點

序號數(shù)據集名稱類別數(shù)大小序號數(shù)據集名稱類別數(shù)大小1ChlorineConcentration338402StarLightCurves383263Two＿Patterns440004Trace41005OliveOil4306Haptics53087Beef5308OSUleaf62429Synthetic＿control630010InlineSkate755011Fish717512Lighting777313MedicalImages1076014SwedishLeaf1562515WordsSynonyms2563816Adiac373911750words50455

本文針對每個子數(shù)據集分別進行5種相似查詢，即無反饋、基于Rocchio算法反饋、基于Ide dec-hi算法反饋以及基于單負反饋和多負反饋，采用歐氏距離作為相似度量函數(shù)?；赗occhio算法相關反饋查詢中，α取值為1，β，γ從0到1以步長0.1遞增；基于Ide dec-hi算法反饋的α取值為1，β，γ從0到1以步長0.1遞增；單負反饋以及多負反饋各數(shù)據集正負查詢組合中α取值為1，β，λ從0到1以步長0.1遞增，在多負反饋中，針對負相關序列的聚類處理，直接根據負相關序列的類別，將類別相同的序列作為同一類。

(7)

本文中R取1～10，計算該查詢序列對應的P-R值，形成對應P-R曲線，但由于數(shù)據集較多生成的圖也較多，為更方便展示，采用各組數(shù)據集的P-R均值進行衡量。在帶反饋的查詢中，針對每個查詢序列，共進行3輪查詢，前兩輪各返回10個結果序列，并根據結果序列的類別與查詢序列類別是否相同，判斷其為正、負相關序列，第三輪時，采用與無反饋查詢相同的方法計算子數(shù)據集的P-R均值。

2.2 實驗結果分析

表2～表5顯示的是4種反饋查詢中，各子組數(shù)據集對應的最優(yōu)P-R均值以及參數(shù)值表，其中maxAv_p表示的是最優(yōu)P-R均值。

表2 單負反饋各子數(shù)據集最優(yōu)P-R均值以及對應β，λ值

數(shù)據集名稱maxAv＿pβλ數(shù)據集名稱maxAv＿pβλChlorineConcentration0．8810．71Trace0．6980．90．7StarLightCurves0．9270．81Beef0．4700．80．9Two＿Patterns0．9590．91Fish0．8930．90．8Synthetic＿control0．9620．60．3Adiac0．6300．70．5MedicalImages0．8050．90．950words0．6620．90．7WordsSynonyms0．7110．90．7Haptics0．5650．81InlineSkate0．4530．70．6OliveOil0．8720．70．5SwedishLeaf0．8660．80．8OSUleaf0．7280．80．8Lighting70．6850．90．8

表3 多負反饋各子數(shù)據集最優(yōu)P-R均值以及對應β，λ值

數(shù)據集名稱maxAv＿pβλ數(shù)據集名稱maxAv＿pβλChlorineConcentration0．8440．70．3Trace0．7000．90．1StarLightCurves0．9150．91Beef0．4490．80．2Two＿Patterns0．9530．71Fish0．8880．70．5Synthetic＿control0．9670．80．5Adiac0．6480．90．5MedicalImages0．8170．80．350words0．6850．80．1WordsSynonyms0．7250．80．1Haptics0．5400．90．5InlineSkate0．4500．90．1OliveOil0．8710．80．5SwedishLeaf0．8710．90．7OSUleaf0．7170．70．3Lighting70．6990．90．1

表4 基于Ide dec-hi算法反饋各子數(shù)據集最優(yōu)P-R均值以及對應β，γ值

數(shù)據集名稱maxAv＿pβγ數(shù)據集名稱maxAv＿pβγChlorineConcentration0．7520．70．7Trace0．6770．60．4StarLightCurves0．8930．90．6Beef0．4320．80．6Two＿Patterns0．9910．90．7Fish0．8710．90．4Synthetic＿control0．9470．60．5Adiac0．6220．80．6MedicalImages0．76110．350words0．67310．2WordsSynonyms0．7120．91Haptics0．5300．60．4InlineSkate0．4260．70．2OliveOil0．8430．70．4SwedishLeaf0．8160．90．7OSUleaf0．6960．80．5Lighting70．6590．80．5

表5 基于Rocchio算法反饋各子數(shù)據集最優(yōu)P-R均值以及對應β，γ值

數(shù)據集名稱maxAv＿pβγ數(shù)據集名稱maxAv＿pβγChlorineConcentration0．7520．70．7Trace0．6430．90．5StarLightCurves0．8720．90．7Beef0．3950．80．6Two＿Patterns0．9730．80．6Fish0．8340．90．4Synthetic＿control0．9320．90．3Adiac0．5780．80．5MedicalImages0．71610．450words0．6590．90．4WordsSynonyms0．6860．90．8Haptics0．4790．70．3InlineSkate0．4030．70．3OliveOil0．8150．80．5SwedishLeaf0．7610．80．6OSUleaf0．6350．90．3Lighting70．6200．70．7

圖1為17組不同數(shù)據集的5種方法的P-R均值結果圖。從圖1中可以看出，在這些數(shù)據集中有反饋的相似性搜索性能比無反饋的相似性搜索的性能都要好，本文提出的單負反饋和多負反饋明顯比基于Rocchio算法反饋檢索性能好，同時也比基于Ide dec-hi算法反饋檢索性能好，這可能是因為本文對初始查詢序列僅做微調并且充分利用負相關序列；而單負反饋和多負反饋這兩者之間效果差別較小。在置信度0.05下，Wilcoxon符號秩和檢驗顯示p=0.97583(雙側檢驗)，表示針對17組子數(shù)據集，單負反饋和多負反饋查詢性能基本相同。

圖1 各組數(shù)據集P-R均值指標結果

但是從圖2加上分類數(shù)來看，可以看出當分類數(shù)比較小的時候，使用了單負相關反饋的模型比多負相關反饋模型好，當分類數(shù)較多時，多負相關反饋的模型比單負相關反饋的模型結果好。這可能是因為單負反饋模型簡單地將各負相關序列當成一個類別來處理所導致的：在負相關序列較集中時即類別較少時，求均值所得到的結果能較好地代表各負相關序列的特性；在負相關序列較為分散時即類別較多時，求均值所得到的結果并不能很好地代表各負相關序列的特性。

圖2 各組數(shù)據集P-R均值指標結果以及分類數(shù)

3 結束語

本文結合時間序列的特點，提出了基于相關反饋的時間序列相似性搜索方法，與已有相似性搜索方法相比，在進行相似性搜索時充分利用了負相關序列，解決了查詢過程中用戶難以參與搜索過程以及難以查找到使用戶滿意的序列問題。實驗數(shù)據表明，該方法提高了查詢的準確率和查全率。

[1] 王雅軒,頊聰. 數(shù)據挖掘技術的綜述[J]. 電子技術與軟件工程, 2015(8):204-205.

[2] Agrawal R, Faloutsos C, Swami A N. Efficient similarity search in sequence databases[C]// Proceedings of the 4th International Conference on Foundations of Data Organizations and Algorithms. 1993:69-84.

[3] 羅洪奔. 基于灰色-ARIMA的金融時間序列智能混合預測研究[J]. 財經理論與實踐, 2014,35(2):27-34.

[4] 朱躍龍,李士進,范青松,等. 基于小波神經網絡的水文時間序列預測[J]. 山東大學學報(工學版), 2011,41(4):119-124.

[5] 李正欣,郭建勝,惠曉濱,等. 基于共同主成分的多元時間序列降維方法[J]. 控制與決策, 2013(4):531-536.

[6] 李海林. 時間序列數(shù)據挖掘中的特征表示與相似性度量方法研究[D]. 大連:大連理工大學, 2012.

[7] 肖瑞. 不確定性時間序列的降維與相似性匹配研究[D]. 上海:東華大學, 2014.

[8] 李正欣,張鳳鳴,李克武,等. 一種支持DTW距離的多元時間序列索引結構[J]. 軟件學報, 2014,25(3):560-575.

[9] 戴珂. 基于線性散列索引的時間序列查詢方法研究[J]. 軟件工程師, 2016,19(8):1-8.

[10] Zhang Qiang, Zhao Zheng. Z Tree: An index structure for high-dimensional data[J]. Computer Engineering, 2007,33(15):49-51.

[11] 肖瑞,劉國華. 基于趨勢的時間序列相似性度量和聚類研究[J]. 計算機應用研究, 2014,31(9):2600-2605.

[12] 張海濤,李志華,孫雅,等. 新的時間序列相似性度量方法[J]. 計算機工程與設計, 2014,35(4):1279-1284.

[13] Goldin D Q, Millstein T D, Kutlu A. Bounded similarity querying for time-series data[J]. Information & Computation, 2004,194(2):203-241.

[14] Keogh E J, Pazzani M J. An enhanced representation of time series which allows fast and accurate classification, clustering and relevance feedback[C]// Proceedings of the 4th International Conference on Knowledge Discovery & Data Mining. 1998:239-241.

[15] Eravci B, Ferhatosmanoglu H. Diversity based relevance feedback for time series search[J]. Proceedings of the VLDB Endowment, 2013,7(2):109-120.

[16] Carbonell J, Goldstein J. The use of MMR, diversity-based reranking for reordering documents and producing summaries[C]// Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. 1998:335-336.

[17] Wang Xuanhui, Fang Hui, Zhai Chengxiang. A study of methods for negative relevance feedback[C]// International ACM SIGIR Conference on Research and Development in Information Retrieval. 2008:219-226.

[18] Peltonen J, Strahl J, Floréen P. Negative relevance feedback for exploratory search with visual interactive intent modeling[C]// Proceedings of the 22nd International Conference on Intelligent User Interfaces. 2017:149-159.

[19] Van Rijsbergen C J. A new theoretical framework for information retrieval[J]. ACM Sigir Forum, 1986,21(1-2):23-29.

[20] Rocchio J J. Relevance feedback in information retrieval[M]// The SMART Retrieval System: Experiments in Automatic Document Processings. 2000:313-323.

[21] Ide E. New experiments in relevance feedback[M]// The SMART Retrieval System: Experiments in Automatic Document Processings. 2000.

[22] Chen Yanping, Keogh E, Hu Bing, et al. The UCR Time Series Classification Archive[EB/OL]. http://www.cs.ucr.edu/～eamonn/time_series_data/, 2017-06-10.