• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    改進(jìn)DTW下界函數(shù)的距離度量方法研究

    2022-12-06 10:39:58龍英文殷煒宏
    關(guān)鍵詞:下界相似性度量

    王 超,龍英文,殷煒宏,黃 勃

    上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院,上海 201620

    時(shí)間序列數(shù)據(jù)通常出現(xiàn)在許多應(yīng)用領(lǐng)域,例如醫(yī)學(xué)的腦電波和心電數(shù)據(jù)[1]、氣象天文數(shù)據(jù)[2]、股票證券交易數(shù)據(jù)[3]和工業(yè)用電數(shù)據(jù)[4]等。盡管如今的數(shù)據(jù)庫隨著相關(guān)應(yīng)用的增加而持續(xù)增長,但一個(gè)普遍的需求是去找到時(shí)間序列之間的相似性[5]。作為一種度量?jī)蓚€(gè)序列相似程度的方法,時(shí)間序列相似性度量是時(shí)間序列異常檢測(cè)、聚類、分類、相關(guān)規(guī)則提取和模式識(shí)別等工作的重要子進(jìn)程[6]。因此,尋找一種合適的度量方法將會(huì)對(duì)后續(xù)的時(shí)間序列挖掘任務(wù)的效率和性能產(chǎn)生深遠(yuǎn)影響[7]。

    在相似性度量方法中,動(dòng)態(tài)時(shí)間彎曲(dynamic time warping,DTW)定義了序列之間最優(yōu)對(duì)齊匹配關(guān)系,并支持兩個(gè)不等長時(shí)間序列之間的相似性度量和時(shí)間軸的伸縮與彎曲。不同于歐氏距離(ED)“點(diǎn)對(duì)點(diǎn)”的線性映射匹配策略,且要求兩條時(shí)間序列的長度必須相等。DTW允許將向量分量與從完全對(duì)應(yīng)的位置“漂移”進(jìn)行比較,即非線性映射[8],用于尋求兩個(gè)序列間的最優(yōu)對(duì)齊方式,是一種常規(guī)的距離度量方法。

    DTW的距離度量效果影響著挖掘工作結(jié)果,許多研究者都將動(dòng)態(tài)時(shí)間彎曲的改進(jìn)工作作為主要研究任務(wù)。其改進(jìn)任務(wù)主要分為兩類[9]:(1)設(shè)計(jì)出滿足動(dòng)態(tài)時(shí)間彎曲下界要求的下界函數(shù);(2)針對(duì)動(dòng)態(tài)時(shí)間彎曲算法過程的改進(jìn)。

    相似性度量工作較多用到下界函數(shù),原始DTW距離度量的時(shí)間復(fù)雜度高,因此研究者提出利用DTW的下界,過濾掉不滿足相似性要求的序列,有效提高了時(shí)間序列相似性搜索的性能。為保證準(zhǔn)確高效的相似性度量,DTW下界距離應(yīng)滿足以下三個(gè)條件[10-11]:

    (1)有效性:下界距離度量的時(shí)間計(jì)算成本應(yīng)保持在低位值;

    (2)緊湊性:下界距離的度量結(jié)果應(yīng)盡可能接近DTW距離,即保證候選集在規(guī)定量級(jí)的情況下,從而減少后期再處理的工作量;

    (3)正確性:經(jīng)過下界距離函數(shù)篩選得到候選序列,必須包含所有滿足條件的序列,即不準(zhǔn)出現(xiàn)誤報(bào)、漏報(bào)現(xiàn)象。

    Yi[12]、Kim[13]、Keogh[14]等人分別提出支持DTW距離度量的邊界距離函數(shù)。LB_Yi是由Yi等人提出的首個(gè)針對(duì)DTW的低邊界函數(shù)。為了構(gòu)建DTW下界距離,該函數(shù)以一條時(shí)間序列作為基本度量序列,將另一條序列中小于基本度量序列的最小值點(diǎn)集和大于該基本序列最大值的點(diǎn)集作為特征,從而完成構(gòu)建。Kim等人提出了LB_Kim函數(shù),它比LB_Yi更接近真實(shí)DTW下界距離,其核心思想是:選出兩個(gè)序列的第一個(gè)序列特征值、最后一個(gè)序列特征值、最大值及最小值這4個(gè)特征值,然后計(jì)算對(duì)應(yīng)特征值的絕對(duì)差值,以最值作為邊界距離,構(gòu)建DTW下界距離函數(shù)。Keogh等人利用全局時(shí)間彎曲約束,構(gòu)造約束動(dòng)態(tài)彎曲路徑的上下邊界,并提出了下界距離函數(shù)LB_Keogh,它比LB_Kim和LB_Yi更接近真實(shí)DTW下界距離。

    Jeong、Sakurai分別針對(duì)算法過程進(jìn)行改進(jìn)。文獻(xiàn)[15]Jeong等人為了優(yōu)化動(dòng)態(tài)時(shí)間彎曲度量效果,提出了WDTW方法,通過賦予在距離矩陣中時(shí)間序列數(shù)據(jù)點(diǎn)的相位差高的元素更高的懲罰權(quán)重,避免了時(shí)間序列過度彎曲和不合理匹配的問題。而文獻(xiàn)[16]Sakurai等人利用early stopping,即提前終止思想,在計(jì)算累計(jì)矩陣時(shí),當(dāng)出現(xiàn)比當(dāng)前累積值大的單元格時(shí),終止該單元格后的行(或列)之后的所有單元格的計(jì)算,從對(duì)角線的新單元格開始計(jì)算,減少計(jì)算成本。

    文獻(xiàn)[17]Górecki等人將DTW和時(shí)間序列的一階導(dǎo)數(shù)相融合,即根據(jù)時(shí)間序列的一般形狀特征,提出一種新的距離度量方式DDDTW,該距離度量經(jīng)過實(shí)驗(yàn)證明取得了不錯(cuò)的效果。文獻(xiàn)[18]Górecki等人對(duì)上述方法做出進(jìn)一步改進(jìn),在上述研究成果的前提下結(jié)合時(shí)間序列特征的二階導(dǎo)數(shù),又進(jìn)而提出一種新的距離度量2DDDTW。該相似性度量方法與文獻(xiàn)[17]相比,分類效果有了更進(jìn)一步。

    文獻(xiàn)[19]晏臻等人提出一種改進(jìn)的基于下界函數(shù)的DTW相似性搜索方法——NLB-FDTW。該方法從下界函數(shù)入手,首先經(jīng)過序列標(biāo)準(zhǔn)化后,再采用LB_Kim對(duì)序列進(jìn)行首次下界函數(shù)過濾,篩選掉那些不相似的序列,然后再采用所提出的LB_Lweng方法進(jìn)行二次過濾,即采用LB_Lweng下界距離度量序列之間的相似距離,并初始化閾值ε,若LB_Lweng距離大于ε,則將該候選序列剔除相似候選序列集合,否則就將該序列加入到相似候選集中。最后,再從相似候選集中找出k個(gè)最為相似的序列進(jìn)行相似匹配。

    但到目前為止,已有的基于下界函數(shù)的DTW距離度量方法仍缺少良好的均衡性,即上述的現(xiàn)存研究方法雖然保證了算法的準(zhǔn)確性卻難以提高算法的時(shí)間效率,而有些方法降低了計(jì)算成本,卻無法保證度量的準(zhǔn)確性與穩(wěn)定性。

    針對(duì)上述問題,本文綜合考慮了度量的準(zhǔn)確性和時(shí)間效率,采用提前終止思想,找到一種基于DTW的下界距離函數(shù)。即在下界距離函數(shù)的基礎(chǔ)上,提出一種基于early stopping的DTW下界距離函數(shù)方法。進(jìn)而,通過實(shí)驗(yàn)對(duì)所提方法進(jìn)行計(jì)算效率、緊湊性和分類準(zhǔn)確性分析。

    1 相關(guān)定義

    定義1(時(shí)間序列)時(shí)間序列是一組由連續(xù)時(shí)間變量和對(duì)應(yīng)的特征值組成的有序集合[20],從時(shí)間序列的角度來看,每個(gè)數(shù)據(jù)單元可以被抽象成一個(gè)二元組(t,v),其中t為時(shí)間變量,v為特征值變量。定義時(shí)間序列X={x1=(t1,v1),x2=(t2,v2),…,xn=(tn,vn)},并滿足ti<ti+1(i=1,2,…,n-1),并且保證時(shí)間間隔固定,一般取Δt=ti+1-ti=1。此時(shí),將時(shí)間序列簡(jiǎn)記為:

    定義2(DTW距離)設(shè)時(shí)間序列S={s1,s2,…,sn},Q={q1,q2,…,qm},DTW距離實(shí)際上就是找到序列S與Q上每個(gè)點(diǎn)之間的對(duì)齊匹配關(guān)系[21],如圖1(a)所示,這種匹配關(guān)系可能有很多種,每一種匹配關(guān)系可以用一條彎曲路徑表示,如圖1(b)所示。也就是說,序列間的匹配關(guān)系與彎曲路徑是一一對(duì)應(yīng)的關(guān)系。

    圖1 彎曲路徑與點(diǎn)對(duì)點(diǎn)匹配結(jié)果Fig.1 Matching result of warping path and point-to-point

    為計(jì)算S和Q的DTW距離,需要構(gòu)造一個(gè)m×n的矩陣,其中:

    為向量點(diǎn)si和qj間的基距離,其中i=1,2,…,n,j=1,2,…,m,可根據(jù)不同情況選擇不同距離度量。本文將采用歐氏距離作為基距離,即l=2。為計(jì)算DTW(S,Q),需找到一條最優(yōu)的彎曲路徑,其中彎曲路徑W中的第k個(gè)元素定義為wk=()i,j k,由此可得:

    彎曲路徑長度滿足max(m,n)≤K≤m+n-1。

    彎曲路徑W必須滿足3個(gè)特性[22]:

    (1)邊界性:路徑起始于(s1,q1)、終止于(sm,qm),它表示兩個(gè)序列的起始點(diǎn)和終止點(diǎn)的對(duì)應(yīng)匹配;

    (2)連續(xù)性:彎曲路徑上的任意兩個(gè)相鄰元素wk(i,j),wk-1(i",j")需滿足0≤|i-i"|≤1,0≤|j-j"|≤1;

    (3)單調(diào)性:若(i,j)和(i",j")為路徑上前后相鄰的兩個(gè)點(diǎn),則要滿足i-i"≥0,j-j"≥0。

    在眾多彎曲路徑中找到唯一最優(yōu)的路徑,使得累積距離達(dá)到最小:

    為求式(4),則需要利用動(dòng)態(tài)規(guī)劃方法構(gòu)造一個(gè)代價(jià)矩陣γ。

    其中,i=1,2,…,n,j=1,2,…,m,γ(0,0)=∞,γ(i,0)=γ(0,j)=∞。那么,γ(i,j)可以看成是當(dāng)前元素的基距離值與3個(gè)元素累積距離值的最小值之和。最終得到的γ(n,m)就是DTW距離度量S和Q的最小累積代價(jià),即DTW(S,Q)=γ(n,m)。以此,便可找到最優(yōu)的彎曲路徑。

    定義3(下界函數(shù))對(duì)于時(shí)間序列的相似性度量[23],若單純使用DTW度量,時(shí)間復(fù)雜度會(huì)很高。出于計(jì)算成本的角度考慮,可以根據(jù)設(shè)定條件利用快速下界算法篩選出較為匹配的候選序列,之后再進(jìn)行下一步的精確度量,從而加快時(shí)間序列度量精度。因此,任意兩條時(shí)間序列距離值的特點(diǎn)是,一定小于等于這兩者之間的DTW距離,即LB(S,Q)≤DTW(S,Q),下一章在改進(jìn)DTW距離的同時(shí)也將證明該下界函數(shù)定理的合理性。

    2 基于DTW下界函數(shù)的提前終止算法

    2.1 彎曲路徑的全局約束

    為了提高相似性度量效率,采用全局約束來提高度量算法的效率成為了關(guān)鍵,也就是規(guī)定了某個(gè)待查詢序列的某個(gè)點(diǎn)與候選序列的約束范圍內(nèi)的幾個(gè)點(diǎn)進(jìn)行動(dòng)態(tài)匹配。設(shè)時(shí)間序列S、Q的彎曲路徑上的元素為wk=(i,j)k,那么彎曲路徑的全局約束可以理解為對(duì)wk中k的限制,即其邊界為j-r≤i≤j+r。r表示了序列上某點(diǎn)的彎曲路徑局限性。對(duì)帶狀約束Sakeo-Chiba來說,r的取值與i不相關(guān)聯(lián),如圖2(a);而對(duì)于平行四邊形約束Itakura-Parallelogram來說,r是關(guān)于i的函數(shù),如圖2(b)所示。本文將采用全局約束Sakeo-Chiba進(jìn)行相似性度量工作。

    圖2 兩種彎曲窗口Fig.2 Two warping windows

    2.2 基于early stopping的DTW距離度量

    提前終止(early stopping)算法原理較為簡(jiǎn)單易懂。其核心思想為:在本次的距離計(jì)算中,若累積距離值達(dá)到預(yù)期設(shè)定的閾值,則立即終止本次計(jì)算,并開始下一輪的距離計(jì)算,根據(jù)此原理來達(dá)到節(jié)約計(jì)算成本的效果。如在計(jì)算DTW累積矩陣的某行列單元格,可以不必計(jì)算整行或者整列單元格的累積距離,通過這種算法思想來減少計(jì)算成本。這種計(jì)算方式尤其應(yīng)用于高維距離計(jì)算效果更好[24]。

    性質(zhì)1假設(shè)時(shí)間序列S={s1,s2,…,sn},Q={q1,q2,…,qm},在累積距離矩陣M中,若能夠找到唯一的最佳彎曲路徑,并且這個(gè)最佳路徑上的累積距離之和為γ,那么有DTW(S,Q)≤γ。

    證明上一章提到過,在累積矩陣中,能夠找到一條最優(yōu)的彎曲路徑W=(w1,w2,…,wk,…,wK),彎曲路徑W中的第k個(gè)元素定義為wk=(i,j)k,使得由路徑W組最小,其中成的累積距離值即為兩個(gè)序列的點(diǎn)對(duì)基距離。由上一節(jié)DTW定義可得,DTW距離等于該最小累積距離之和,即DTW(S,Q=)

    接下來,將結(jié)合early stopping思想對(duì)DTW距離度量進(jìn)行改進(jìn)。

    基于early stopping的DTW改進(jìn)具體過程如算法1所示。首先給定兩個(gè)時(shí)間序列S、Q;然后,根據(jù)這兩個(gè)序列構(gòu)成的距離矩陣,計(jì)算出代價(jià)矩陣對(duì)應(yīng)元素單元格的累積距離γ(i,j),并與預(yù)設(shè)閾值ε作比較,若大于該閾值,則停止當(dāng)前元素之后的所有代價(jià)矩陣所在單元格行(或列)的累積距離計(jì)算,進(jìn)而根據(jù)其對(duì)角線的新的單元格繼續(xù)開始計(jì)算累積距離,直到最后一列停止,并輸出最優(yōu)累積距離值ES_DTW(S,Q)。通過該算法來減小搜索范圍,降低了距離度量的計(jì)算成本,同時(shí)也確保了原本DTW距離度量的精度。

    算法1基于early stopping的DTW算法(ESDTW)

    接下來,先參考一個(gè)例子來進(jìn)一步了解early stopping在DTW中發(fā)揮的作用。圖3是S、Q根據(jù)DTW距離度量計(jì)算構(gòu)成的代價(jià)矩陣,每個(gè)單元格表示對(duì)應(yīng)元素的累積距離大小。假設(shè)提前終止的閾值ε為26,由于γ(1,2)>ε,則第一列單元格中γ(1,3),γ(1,4)都將被排除在外,即不參與距離計(jì)算。同理,γ(2,2)=γ(3,2)=32>ε,則與之所在列的后續(xù)單元格代價(jià)距離都無需計(jì)算。最終,得到該代價(jià)矩陣的最優(yōu)解為γ(6,4)=28,即ESDTW(S,Q)=γ(6,4)=28。

    圖3 基于DTW距離度量的代價(jià)矩陣Fig.3 Cost matrix based on DTW distance measurement

    性質(zhì)2假設(shè)時(shí)間序列S={s1,s2,…,sn},Q={q1,q2,…,qm},在累積距離矩陣M中,該彎曲路徑上的累積距離之和為γ,若存在一條最優(yōu)路徑,那么有ESDTW(S,Q)≤γ。

    證明參考性質(zhì)1,由于ESDTW算法進(jìn)行距離度量的方法與DTW保持一致,那么,在累積矩陣中,同樣能夠形成一條最佳路徑W=(w1,w2,…,wk,…,wK),使得由路徑W組成的累積距離值最小,同理可得

    因此,同理可證ESDTW(S,Q)≤γ,即說明了ESDTW距離度量方法的有效性。

    Early stopping算法不僅能應(yīng)用于精確的DTW距離計(jì)算,也能在粗略的DTW距離計(jì)算中發(fā)揮作用,大大降低了計(jì)算成本,提高算法性能。

    2.3 下界函數(shù)方法分析

    文中之所以引入下界函數(shù),正因?yàn)閯?dòng)態(tài)時(shí)間規(guī)整算法原始時(shí)間復(fù)雜度過高,如果直接進(jìn)行兩序列之間的DTW距離度量,勢(shì)必會(huì)使得算法的整體的度量效率下降,使得后續(xù)的數(shù)據(jù)挖掘任務(wù)變得難以進(jìn)行下去[25]。下面將對(duì)下界函數(shù)進(jìn)行展開分析,并舉出代表性的下界函數(shù)方法。

    首先給出下界函數(shù)的定義為,假設(shè)存在一個(gè)對(duì)象O,且它的距離度量函數(shù)為M,若某個(gè)定義在對(duì)象域O上的函數(shù)為M",那么對(duì)于所有存在于對(duì)象域的參數(shù)值oi,oj,總有下列不等式:

    如果不等式恒成立,那么將上述M"函數(shù)稱之為M的下界函數(shù)。

    如果在度量?jī)蓚€(gè)時(shí)間序列時(shí),采用度量函數(shù)度量其相似度,在沒有下界函數(shù)參與的情況下,單單依靠距離度量函數(shù)只是機(jī)械化地將整個(gè)樣本序列的相似性度量執(zhí)行完,這種度量的效率較低,時(shí)間耗費(fèi)過大,若加入了下界函數(shù),則能夠在度量期間對(duì)超過某個(gè)預(yù)先設(shè)定的相似性度量閾值進(jìn)行比對(duì)判斷,若實(shí)際得到距離值比預(yù)設(shè)閾值大,那么認(rèn)定這兩條序列是不相似的,相應(yīng)地也就將其摒棄,也為后續(xù)度量節(jié)省了時(shí)間開銷。

    那么為了保證下界函數(shù)在距離度量函數(shù)運(yùn)行過程中能夠有效進(jìn)行,需滿足兩個(gè)必要條件:

    (1)盡量與真實(shí)距離度量函數(shù)得到的距離接近。因?yàn)橄陆缇嚯x函數(shù)只是真實(shí)距離度量函數(shù)的一個(gè)先行者,它需要盡可能幫助實(shí)際距離度量函數(shù)去篩選和過濾掉一些不相似序列,所以下界函數(shù)需要更加貼近真實(shí)的距離度量函數(shù)的邊界值,保證度量誤差在一個(gè)合理范圍內(nèi)。

    (2)滿足時(shí)間復(fù)雜度要求,盡可能在O(n)內(nèi)完成。即下界函數(shù)需要在線性時(shí)間內(nèi)完成度量,如果下界函數(shù)的時(shí)間復(fù)雜度超過了實(shí)際距離度量函數(shù)的計(jì)算耗時(shí),那么可以說此下界函數(shù)是無效的。

    如今的下界函數(shù)方法已有很多,典型的主要有:LB_Kim、LB_Yi和LB_Keogh。下面將重點(diǎn)介紹一下LB_Keogh下界函數(shù)。

    LB_Keogh的提出是為了針對(duì)DTW的耗時(shí)問題。該方法通過計(jì)算候選序列的邊界序列來組成動(dòng)態(tài)時(shí)間規(guī)整距離的下界。設(shè)候選序列Q={q1,q2,…,qn},將全局約束引入到彎曲路徑中,邊界約束為r,利用參數(shù)r定義兩個(gè)邊界序列U={u1,u2,…,un},L={l1,l2,…,ln},其中:

    U、L分別代表上邊界序列和下邊界序列,如圖4組成了上下包絡(luò)線與Q的位置關(guān)系,而被U、L包裹其中的區(qū)域,則稱之為封袋。

    圖4 查詢序列與其上線邊界序列Fig.4 Query sequence and its on-line boundary sequence

    其中,包絡(luò)線上界與下界的一個(gè)重要性質(zhì)為:

    進(jìn)而,得到動(dòng)態(tài)時(shí)間規(guī)整的下界函數(shù)LB_Keogh為:

    該下界函數(shù)可理解為候選序列C中沒有落入封袋的點(diǎn)與邊界線的距離之和,如圖5。

    圖5 下界距離LB_ESDTW的示意圖Fig.5 Schematic diagram of LB_ESDTW with lower bound distance

    2.4 基于ESDTW下界距離(LB_ESDTW)

    上文提出了一種改進(jìn)的DTW距離度量方法,即ESDTW,下面將給出該方法的下界距離。

    設(shè)長度為n的兩條時(shí)間序列Q、C,其邊界約束為j-r≤i≤j+r,則ESDTW的下界函數(shù)為:

    下面首先證明LB_ESDTW(Q,C)≤DTW(Q,C),即該下界函數(shù)滿足下界距離引理。

    證明在ESDTW度量中,假設(shè)Q,C的最佳彎曲路徑為W=(w1,w2,…,wk,…,wK),由上一節(jié)對(duì)ESDTW的證明可知,其中n≤K≤2n-1,則原命題可轉(zhuǎn)換為:

    不等式兩邊平方,得:

    對(duì)于式(11),不等式左側(cè)分為3種情況:

    當(dāng)ci>ui時(shí),不等式左側(cè)第i項(xiàng)為(ci-ui)2,不等式右側(cè)第i項(xiàng)基距離為D(wi)=(ci-qi)2。由于ui=max(qi-r:qi+r)且i-r≤j≤i+r,所以qj≤max(qi-r:qi+r),即qj≤ui;那么,不等式兩邊變形后為ci-ui≤ci-qj,又因?yàn)樽筮吅愦笥?,則不等式兩邊平方可得因此

    當(dāng)ci<li,同理可證(ci-li)2≤D(wi)。

    當(dāng)li≤ci≤ui時(shí),顯然有0≤(ci-qi)2=D(wi)。

    綜上所述,不等式(8)成立,即證明了LB_ESDTW(Q,C)≤DTW(Q,C),該下界距離是有效的。

    對(duì)于上述下界函數(shù),其計(jì)算方法與歐式距離類似,都是通過計(jì)算點(diǎn)對(duì)點(diǎn)距離的累積和,因此,在計(jì)算過程中達(dá)到下界函數(shù)的最優(yōu)解ε時(shí),往往會(huì)把序列點(diǎn)全部計(jì)算完畢才去判斷是否滿足最優(yōu)條件,這種計(jì)算方式會(huì)大大增加時(shí)間成本,往往是不必要的。在這里,同樣可以將early stopping算法用于下界函數(shù)來提高算法的時(shí)間效率,采用從左往右依次計(jì)算序列點(diǎn)之間的距離,若到達(dá)某序列點(diǎn)的距離之和超過了最優(yōu)解,則終止當(dāng)前序列計(jì)算,因?yàn)槌^該序列點(diǎn)的計(jì)算都將會(huì)比ε大,完成整個(gè)序列的下界函數(shù)計(jì)算變得沒有意義。

    如圖6,假設(shè)采用下界函數(shù)計(jì)算到第8個(gè)序列點(diǎn)時(shí),該點(diǎn)距離和已經(jīng)大于最優(yōu)解了,那么序列點(diǎn)8往后的序列點(diǎn)的計(jì)算都將失去意義,由此得出該測(cè)試序列與原始序列之間的相似度較低,可將其剔除。通過該方式能進(jìn)一步提高算法的運(yùn)行效率,從而降低時(shí)間成本。

    圖6 基于下界函數(shù)的提前終止方法Fig.6 Early termination method based on lower bound function

    2.5 算法分析

    下面給出基于DTW下界函數(shù)的提前終止算法(LB_ESDTW)。將改進(jìn)的ESDTW算法1與下界函數(shù)相結(jié)合,進(jìn)一步提高了算法的運(yùn)算效率,大大節(jié)省時(shí)間成本,同時(shí)也保證了后續(xù)算法相似性度量的準(zhǔn)確性。

    算法2基于DTW下界函數(shù)的提前終止算法(LB_ESDTW)

    算法LB_ESDTW在相似性距離度量方法DTW的基礎(chǔ)上采用了提前終止算法,同時(shí)在下界距離度量上也在局部增加了提前終止算法,這兩次的提前終止算法與下界距離相結(jié)合能夠提升算法效率。根據(jù)算法2的描述和式(11)的計(jì)算公式可以得出,長度為n的兩條時(shí)間序列Q、C進(jìn)行下界距離度量時(shí),其復(fù)雜度為O(n),內(nèi)部嵌套提前終止距離度量算法ESDTW,時(shí)間復(fù)雜度為O(m),其中m≤n,因而整體算法LB_ESDTW的時(shí)間復(fù)雜度大小為O(n×m)。而傳統(tǒng)的動(dòng)態(tài)時(shí)間規(guī)整算法(DTW)的時(shí)間復(fù)雜度則是O(n2),所以,本文算法的時(shí)間復(fù)雜度與DTW算法相比,則有不等式O(n×m)≤O(n2)恒成立。當(dāng)測(cè)試數(shù)據(jù)量較大時(shí),本文的度量算法在時(shí)間計(jì)算效率上與DTW算法相比將有明顯的優(yōu)勢(shì),即大大提高了算法的運(yùn)行效率,節(jié)約了時(shí)間成本。該方法對(duì)于分類數(shù)據(jù)維數(shù)的大小都能有良好的適應(yīng)性,不會(huì)因?yàn)闃颖緮?shù)據(jù)量大而限制算法的性能。

    3 實(shí)驗(yàn)與結(jié)果分析

    為了驗(yàn)證LB_ESDTW的有效性,本文將在特定的時(shí)間序列分類數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。對(duì)比實(shí)驗(yàn)的內(nèi)容主要針對(duì)算法的運(yùn)行時(shí)間測(cè)試、下界距離的緊湊性和算法的相似性度量準(zhǔn)確率這三部分進(jìn)行分析。

    3.1 實(shí)驗(yàn)數(shù)據(jù)集

    本文實(shí)驗(yàn)的實(shí)驗(yàn)數(shù)據(jù)集全部來源于Keogh等人提供的來自不同領(lǐng)域的用于時(shí)間序列分類、聚類UCR數(shù)據(jù)集。該數(shù)據(jù)集中包含了各個(gè)領(lǐng)域的不同數(shù)據(jù)集,里面包含預(yù)先處理好的訓(xùn)練集和測(cè)試集。本實(shí)驗(yàn)共選擇了15個(gè)數(shù)據(jù)集進(jìn)行算法性能測(cè)試,這15個(gè)數(shù)據(jù)集的具體特征如表1所示。

    表1 UCR數(shù)據(jù)集描述Table 1 Description of UCR data set

    3.2 實(shí)驗(yàn)設(shè)置

    在實(shí)驗(yàn)中,為了驗(yàn)證本文LB_ESDTW算法的性能,分別選取了DTW、LB_Keogh和WDTW三種不同的度量算法進(jìn)行對(duì)比實(shí)驗(yàn)。

    由于時(shí)間序列數(shù)據(jù)集來自不同領(lǐng)域,彼此的特征值取值范圍有一定差距,為了便于對(duì)比實(shí)驗(yàn),在采用線性分段算法之前首先對(duì)時(shí)間序列做規(guī)范化處理,將序列特征值規(guī)范化到[0,1]之間,其規(guī)范化公式如下:

    3.3 實(shí)驗(yàn)結(jié)果

    算法運(yùn)行在2.5 GHz CPU,8 GB內(nèi)存Windows系統(tǒng)的Python 3.5.1環(huán)境下。本文選取了UCR中的10個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn),每個(gè)算法均進(jìn)行100次實(shí)驗(yàn),結(jié)果取100次實(shí)驗(yàn)的平均值。

    由于本文采用Sakeo-Chiba全局約束進(jìn)行時(shí)間序列相似性度量實(shí)驗(yàn)。首先,為確定實(shí)驗(yàn)的具體全局約束參數(shù),將采用LB_ESDTW算法準(zhǔn)確率實(shí)驗(yàn)來選定具體的全局約束參數(shù)R。表2是在時(shí)間序列都為原始序列長度的情況下,且保證全局約束在10%≤R≤50%范圍內(nèi)進(jìn)行準(zhǔn)確率實(shí)驗(yàn)。目的是探究全局約束R取何值,時(shí)序的度量準(zhǔn)確率達(dá)到最高。其中,標(biāo)粗?jǐn)?shù)據(jù)是當(dāng)前數(shù)據(jù)集下得到的最高準(zhǔn)確率所對(duì)應(yīng)的全局約束。從表2列出的準(zhǔn)確率數(shù)據(jù)可以看出,在測(cè)試的15個(gè)數(shù)據(jù)集中,有4條數(shù)據(jù)集在R=10%時(shí)算法準(zhǔn)確率達(dá)到最優(yōu);有5條數(shù)據(jù)集在R=15%時(shí)算法準(zhǔn)確率達(dá)到最優(yōu);有4條數(shù)據(jù)集在R=20%時(shí)算法度量準(zhǔn)確率達(dá)到最優(yōu);有2條數(shù)據(jù)集在R=25%時(shí)算法準(zhǔn)確率達(dá)到最優(yōu)。綜合這15個(gè)數(shù)據(jù)集的算法準(zhǔn)確率來看,整體趨勢(shì)都是先逐漸上升到某個(gè)峰值(算法準(zhǔn)確率達(dá)到最高)再逐漸下降,且當(dāng)全局約束R越大,準(zhǔn)確率下降幅度也隨之變高。因此,根據(jù)這一參數(shù)特性,可以得出算法的全局約束參數(shù)值在10%≤R≤25%這一范圍內(nèi)能得到最優(yōu)準(zhǔn)確率。而在實(shí)驗(yàn)中,只需在算法中加一個(gè)記錄判斷環(huán)節(jié),即加一個(gè)for循環(huán)和if判斷得到當(dāng)前數(shù)據(jù)集下的全局約束最優(yōu)解。

    表2 全局約束下的LB_ESDTW算法準(zhǔn)確率Table 2 Accuracy of LB ESDTW algorithm under global constraints

    實(shí)驗(yàn)1算法的運(yùn)行時(shí)間分析

    在本實(shí)驗(yàn)中,選取UCR訓(xùn)練數(shù)據(jù)集中的CBF、ECGFiveDays、ECG200,Coffee這四個(gè)數(shù)據(jù)樣本的第一條樣本序列與測(cè)試序列進(jìn)行相似序列搜索的運(yùn)行時(shí)間的對(duì)比分析。通過分析上述四種算法在邊界約束r取不同值時(shí),即取序列長度壓縮率為10%~100%時(shí)的彎曲范圍,得到不同的運(yùn)行時(shí)間,從而得出各個(gè)算法的運(yùn)行效率。那么,邊界約束與彎曲范圍的關(guān)系為r=N×w×100%。其中,r為邊界約束,N是時(shí)間序列長度,w為彎曲范圍。由于r和w成正比,所以在本實(shí)驗(yàn)中,將采用彎曲范圍w與運(yùn)行時(shí)間t進(jìn)行實(shí)驗(yàn)分析。

    如圖7,分別在上述的三個(gè)數(shù)據(jù)樣本下進(jìn)行四種算法的彎曲范圍w和運(yùn)行時(shí)間t的對(duì)比實(shí)驗(yàn)。

    從圖7對(duì)比可以看出本文算法都有最低的時(shí)間消耗,即本文的LB_ESDTW算法在四種數(shù)據(jù)集下的運(yùn)行時(shí)間都為最短,從側(cè)面反映了該算法的運(yùn)行效率較高。

    圖7 不同彎曲范圍下的運(yùn)行時(shí)間Fig.7 Running time under different warping ranges

    實(shí)驗(yàn)2下界距離LB_ESDTW的緊致性分析

    算法的緊致性越好,說明下界距離更接近實(shí)際距離,使得在使用下界距離進(jìn)行相似性度量時(shí),得到的誤報(bào)序列更少,更精確地匹配到相似序列,同時(shí)保證了準(zhǔn)確率。本實(shí)驗(yàn)采用緊縮率和修剪率這兩個(gè)性能指標(biāo)來度量下界距離LB_ESDTW的緊致性。下界距離LB_ESDTW的緊縮率SESDTW定義為:

    修剪率P定義為:

    其中,N0為在下界距離LB_ESDTW的過濾篩選下得到的不需要與訓(xùn)練集樣本進(jìn)行相似性度量的序列數(shù)量,N為該數(shù)據(jù)集的總樣本序列數(shù)。

    本實(shí)驗(yàn)選取了上述15個(gè)UCR數(shù)據(jù)集進(jìn)行緊縮率分析。對(duì)同一數(shù)據(jù)集進(jìn)行多次緊縮率實(shí)驗(yàn)記錄并最終選取緊縮率SESDTW的平均值,具體實(shí)驗(yàn)結(jié)果如表3所示。

    表3 下界距離LB_ESDTW的緊縮率Table 3 Contraction rate of LB_ESDTW with lower bound distance

    本實(shí)驗(yàn)選取了其中的六個(gè)數(shù)據(jù)集對(duì)修剪率在邊界約束r取不同值時(shí)進(jìn)行分析,實(shí)驗(yàn)結(jié)果如圖8。

    圖8 下界距離LB_ESDTW的修剪率Fig.8 Pruning rate of LB_ESDTW with lower bound distance

    在第一個(gè)緊縮率實(shí)驗(yàn)中,下界算法LB_ESDTW在五個(gè)不同數(shù)據(jù)集下的緊縮率都在50%以上,也就證明了該下界距離算法的緊致性較好;在第二個(gè)修剪率實(shí)驗(yàn)上,該算法在距離閾值較小時(shí)的修剪率都能達(dá)到70%以上,而當(dāng)距離閾值逐漸增加,相應(yīng)的修剪率則隨之減小,由此得知下界距離LB_ESDTW的修剪率和距離閾值存在一定的關(guān)系,即當(dāng)距離閾值過大,超出了ESDTW距離時(shí),意味著該下界距離失去了原有的過濾篩選作用。綜上兩個(gè)對(duì)于緊湊性判斷標(biāo)準(zhǔn)的實(shí)驗(yàn)結(jié)果,能夠明顯看出該算法的緊湊性較好。

    實(shí)驗(yàn)3算法準(zhǔn)確率對(duì)比實(shí)驗(yàn)

    本實(shí)驗(yàn)中,將本文下界算法LB_ESDTW分別與其他相似性度量方法進(jìn)行算法的分類準(zhǔn)確率對(duì)比實(shí)驗(yàn),目的在于分析各算法之間的相似性度量準(zhǔn)確率,從而判斷本文所提算法的相似性度量性能。

    本實(shí)驗(yàn)采用上述15個(gè)不同領(lǐng)域的數(shù)據(jù)集進(jìn)行對(duì)比實(shí)驗(yàn)。進(jìn)行對(duì)比的相似性度量算法分別有ED、DTW、LB_Keogh、WDTW以及本文算法LB_ESDTW。同時(shí)保證這五個(gè)算法在不同數(shù)據(jù)集下的邊界約束r都是壓縮率在100%的彎曲路徑。

    表4給出了在上述描述的15個(gè)不同數(shù)據(jù)集下的各算法的相似性度量的分類準(zhǔn)確率。

    表4 算法度量的分類準(zhǔn)確率Table 4 Classification accuracy of similarity measure

    表4中用粗體表示的數(shù)據(jù)為算法在當(dāng)前數(shù)據(jù)集下獲得的最高分類準(zhǔn)確率。從表4的分類結(jié)果不難發(fā)現(xiàn),對(duì)于所選的15個(gè)數(shù)據(jù)集來說,其中LB_ESDTW算法在11個(gè)數(shù)據(jù)集的分類結(jié)果都優(yōu)于其他四種算法的分類結(jié)果,也表明了LB_ESDTW下界距離度量的分類性能較好。

    4 結(jié)束語

    本文給出了一種基于early stopping思想的DTW距離度量,即在計(jì)算兩個(gè)序列的距離時(shí),發(fā)現(xiàn)本次計(jì)算所積累的距離信息已經(jīng)足以判斷結(jié)果,則終止本次計(jì)算,大大降低了計(jì)算成本;并在下界距離函數(shù)LB_Keogh方法基礎(chǔ)之上,提出了一種基于DTW下界距離函數(shù)的提前終止算法,實(shí)現(xiàn)了算法在DTW距離度量和下界函數(shù)距離度量相融合的相似性度量,同時(shí)也提高了算法的適應(yīng)性。通過在UCR數(shù)據(jù)集上的三種對(duì)比實(shí)驗(yàn),表明其在時(shí)間計(jì)算成本低、算法的緊致性良好且算法的分類準(zhǔn)確率高的特點(diǎn)。本文已在大多數(shù)時(shí)間序列數(shù)據(jù)集下進(jìn)行實(shí)驗(yàn)論證,由于數(shù)據(jù)集的時(shí)效性和局限性,后續(xù)將通過更多不同領(lǐng)域的時(shí)序數(shù)據(jù)集來驗(yàn)證本文所提算法的有效性。同時(shí),為了能夠更好地平衡算法的度量準(zhǔn)確率和時(shí)間效率,接下來的工作主要是將時(shí)間序列的表示方法與相似性度量方法結(jié)合起來,并根據(jù)數(shù)據(jù)挖掘的任務(wù)需求,設(shè)計(jì)出針對(duì)不同場(chǎng)景的具有普適性的融合度量查詢系統(tǒng),如針對(duì)病人的心電數(shù)據(jù),設(shè)計(jì)一種實(shí)時(shí)在線的度量系統(tǒng);而針對(duì)股票趨勢(shì)的分析,則設(shè)計(jì)出一種預(yù)測(cè)度量系統(tǒng)模型,以此將本文度量方法在數(shù)據(jù)挖掘中的優(yōu)勢(shì)發(fā)揮到最大化。

    猜你喜歡
    下界相似性度量
    有趣的度量
    一類上三角算子矩陣的相似性與酉相似性
    模糊度量空間的強(qiáng)嵌入
    淺析當(dāng)代中西方繪畫的相似性
    迷向表示分為6個(gè)不可約直和的旗流形上不變愛因斯坦度量
    Lower bound estimation of the maximum allowable initial error and its numerical calculation
    低滲透黏土中氯離子彌散作用離心模擬相似性
    地質(zhì)異常的奇異性度量與隱伏源致礦異常識(shí)別
    矩陣Hadamard積的上下界序列
    最大度為10的邊染色臨界圖邊數(shù)的新下界
    成人毛片60女人毛片免费| 国产男人的电影天堂91| 黄色毛片三级朝国网站| 18禁动态无遮挡网站| 久久亚洲国产成人精品v| 天堂中文最新版在线下载| 蜜臀久久99精品久久宅男| 美女脱内裤让男人舔精品视频| 午夜免费男女啪啪视频观看| 能在线免费看毛片的网站| 最后的刺客免费高清国语| 精品一区二区三区视频在线| 精品人妻熟女av久视频| 人妻系列 视频| 18禁观看日本| 国产日韩欧美在线精品| 国产白丝娇喘喷水9色精品| 久久久亚洲精品成人影院| 日韩精品有码人妻一区| 2018国产大陆天天弄谢| 精品一区在线观看国产| 国产精品国产三级国产av玫瑰| 国产男人的电影天堂91| 久久午夜综合久久蜜桃| 啦啦啦视频在线资源免费观看| 大香蕉97超碰在线| 下体分泌物呈黄色| 亚洲高清免费不卡视频| av卡一久久| av一本久久久久| 黑人欧美特级aaaaaa片| 99九九在线精品视频| 免费日韩欧美在线观看| 国产精品蜜桃在线观看| 国产成人freesex在线| 在线观看免费日韩欧美大片 | 在线 av 中文字幕| 80岁老熟妇乱子伦牲交| 国产永久视频网站| 免费大片18禁| 超碰97精品在线观看| 亚洲无线观看免费| 秋霞伦理黄片| 亚洲精品乱码久久久久久按摩| 国产精品国产三级国产av玫瑰| av电影中文网址| 丝瓜视频免费看黄片| 大香蕉久久网| 亚洲av男天堂| 久久久久网色| 免费看不卡的av| 久久久亚洲精品成人影院| 国国产精品蜜臀av免费| 久久99热6这里只有精品| 国产又色又爽无遮挡免| 国产精品国产三级专区第一集| 激情五月婷婷亚洲| 香蕉精品网在线| 人妻制服诱惑在线中文字幕| 最黄视频免费看| 亚洲欧美日韩卡通动漫| 中文字幕人妻熟人妻熟丝袜美| 黑丝袜美女国产一区| 亚洲国产精品专区欧美| 中文乱码字字幕精品一区二区三区| 亚洲欧美色中文字幕在线| 欧美日韩一区二区视频在线观看视频在线| 久久人人爽人人爽人人片va| 秋霞在线观看毛片| 一个人看视频在线观看www免费| 日本av免费视频播放| 国产综合精华液| 国产乱来视频区| 亚洲无线观看免费| 国产伦精品一区二区三区视频9| 王馨瑶露胸无遮挡在线观看| 免费黄频网站在线观看国产| 久久久亚洲精品成人影院| 成人影院久久| 国产爽快片一区二区三区| 亚洲中文av在线| 成人黄色视频免费在线看| 亚洲精品久久午夜乱码| 十八禁高潮呻吟视频| 久久国产精品大桥未久av| 一级毛片 在线播放| 午夜福利影视在线免费观看| 欧美一级a爱片免费观看看| 高清黄色对白视频在线免费看| 国产精品免费大片| 国产精品久久久久久久久免| 精品国产一区二区三区久久久樱花| 日韩大片免费观看网站| 久久精品国产亚洲网站| 久久久久久久久久成人| 国产成人免费观看mmmm| 水蜜桃什么品种好| 国产探花极品一区二区| 一本色道久久久久久精品综合| 国产精品熟女久久久久浪| 久久狼人影院| 亚洲精品日韩av片在线观看| 国产精品久久久久成人av| 日韩精品免费视频一区二区三区 | 国产精品偷伦视频观看了| 天美传媒精品一区二区| 精品99又大又爽又粗少妇毛片| 亚洲经典国产精华液单| 日本猛色少妇xxxxx猛交久久| 最近2019中文字幕mv第一页| 日韩,欧美,国产一区二区三区| 一区二区av电影网| 最近手机中文字幕大全| 一区在线观看完整版| 一二三四中文在线观看免费高清| 天天影视国产精品| 亚洲精品,欧美精品| 国产高清有码在线观看视频| 自线自在国产av| 日本免费在线观看一区| 制服人妻中文乱码| 亚洲少妇的诱惑av| 91久久精品电影网| 啦啦啦视频在线资源免费观看| 精品人妻一区二区三区麻豆| 91久久精品电影网| 啦啦啦视频在线资源免费观看| 亚洲少妇的诱惑av| 这个男人来自地球电影免费观看 | .国产精品久久| 一本色道久久久久久精品综合| 亚洲欧美中文字幕日韩二区| 久久久久国产网址| 国产男人的电影天堂91| 特大巨黑吊av在线直播| 国产女主播在线喷水免费视频网站| 成人影院久久| 99热这里只有精品一区| 天天操日日干夜夜撸| 成人漫画全彩无遮挡| 欧美日韩亚洲高清精品| 永久免费av网站大全| 久久ye,这里只有精品| 飞空精品影院首页| 中文天堂在线官网| 久久国产亚洲av麻豆专区| 日本91视频免费播放| 22中文网久久字幕| 中文字幕av电影在线播放| 丁香六月天网| 成人毛片60女人毛片免费| 黑人欧美特级aaaaaa片| 国产深夜福利视频在线观看| 欧美xxⅹ黑人| 成人漫画全彩无遮挡| 九九爱精品视频在线观看| 免费观看av网站的网址| 中国国产av一级| 狠狠精品人妻久久久久久综合| 国产av码专区亚洲av| 蜜桃久久精品国产亚洲av| 看免费成人av毛片| av又黄又爽大尺度在线免费看| 99热6这里只有精品| 欧美激情极品国产一区二区三区 | 日日摸夜夜添夜夜爱| 亚洲国产毛片av蜜桃av| a级毛片在线看网站| 精品久久蜜臀av无| 777米奇影视久久| 日日摸夜夜添夜夜添av毛片| 最近中文字幕2019免费版| 欧美bdsm另类| 有码 亚洲区| 色婷婷久久久亚洲欧美| 亚洲不卡免费看| 一个人免费看片子| 热99久久久久精品小说推荐| 国产av码专区亚洲av| 男人操女人黄网站| 激情五月婷婷亚洲| 亚洲欧美一区二区三区国产| 在线观看人妻少妇| 看十八女毛片水多多多| 欧美日韩精品成人综合77777| 18禁在线播放成人免费| 最近的中文字幕免费完整| 欧美一级a爱片免费观看看| 人体艺术视频欧美日本| 亚洲伊人久久精品综合| 成人无遮挡网站| 欧美成人午夜免费资源| 亚洲av中文av极速乱| 精品少妇内射三级| 日韩成人伦理影院| 亚州av有码| 韩国av在线不卡| 国产高清不卡午夜福利| 校园人妻丝袜中文字幕| 亚洲国产毛片av蜜桃av| 午夜av观看不卡| 99久国产av精品国产电影| 尾随美女入室| 精品久久国产蜜桃| 国产色爽女视频免费观看| 街头女战士在线观看网站| 性色avwww在线观看| 国产不卡av网站在线观看| 成人国产麻豆网| 简卡轻食公司| 亚洲成人av在线免费| 91久久精品国产一区二区三区| 成年av动漫网址| a级毛片在线看网站| 男男h啪啪无遮挡| 午夜免费观看性视频| 免费播放大片免费观看视频在线观看| 韩国高清视频一区二区三区| 你懂的网址亚洲精品在线观看| 国产亚洲最大av| 极品少妇高潮喷水抽搐| 午夜日本视频在线| 免费日韩欧美在线观看| 黄色一级大片看看| 日韩强制内射视频| 黄色欧美视频在线观看| 少妇丰满av| 水蜜桃什么品种好| 国产免费福利视频在线观看| 精品少妇内射三级| 亚洲精品久久成人aⅴ小说 | 国产成人精品无人区| 九九爱精品视频在线观看| 不卡视频在线观看欧美| 欧美日韩精品成人综合77777| 欧美日韩视频高清一区二区三区二| 超碰97精品在线观看| 免费大片黄手机在线观看| 国产一区二区在线观看av| 99久久精品国产国产毛片| 丝瓜视频免费看黄片| 夫妻性生交免费视频一级片| 久久精品久久久久久噜噜老黄| 成人18禁高潮啪啪吃奶动态图 | 亚洲精品成人av观看孕妇| 久久久久久久久久久丰满| 色94色欧美一区二区| 亚洲国产av新网站| 人妻人人澡人人爽人人| 久久久久久久亚洲中文字幕| 我的老师免费观看完整版| 免费久久久久久久精品成人欧美视频 | 欧美精品高潮呻吟av久久| 大话2 男鬼变身卡| 精品久久国产蜜桃| 建设人人有责人人尽责人人享有的| 99re6热这里在线精品视频| 一区在线观看完整版| 大片免费播放器 马上看| 日日啪夜夜爽| 另类亚洲欧美激情| 免费人妻精品一区二区三区视频| 久久精品久久精品一区二区三区| 成人综合一区亚洲| 成人手机av| 精品久久久精品久久久| 成人午夜精彩视频在线观看| 国产精品国产三级专区第一集| 在线观看国产h片| 欧美 日韩 精品 国产| 不卡视频在线观看欧美| 黑人高潮一二区| 狂野欧美白嫩少妇大欣赏| 十八禁网站网址无遮挡| 国产伦精品一区二区三区视频9| 一本久久精品| 国产淫语在线视频| 国产精品国产三级专区第一集| 国精品久久久久久国模美| 精品亚洲成国产av| 欧美精品一区二区大全| 18禁在线播放成人免费| 熟妇人妻不卡中文字幕| 在线天堂最新版资源| 欧美少妇被猛烈插入视频| 亚洲国产欧美日韩在线播放| 黑丝袜美女国产一区| av一本久久久久| 精品99又大又爽又粗少妇毛片| 永久网站在线| 丰满乱子伦码专区| 久久久久久久国产电影| 欧美精品一区二区大全| 国产精品女同一区二区软件| 97在线人人人人妻| 精品人妻偷拍中文字幕| 人人澡人人妻人| 国产探花极品一区二区| 亚洲美女黄色视频免费看| 热re99久久国产66热| 精品亚洲成国产av| 亚洲av国产av综合av卡| 成人18禁高潮啪啪吃奶动态图 | 免费看不卡的av| 婷婷色麻豆天堂久久| 99九九线精品视频在线观看视频| 欧美 日韩 精品 国产| 国产高清不卡午夜福利| 国产国拍精品亚洲av在线观看| 少妇人妻精品综合一区二区| 久久久欧美国产精品| 国产极品天堂在线| 国产av国产精品国产| 91成人精品电影| 国产精品 国内视频| 黄片播放在线免费| 欧美成人午夜免费资源| 亚洲欧美精品自产自拍| 伦理电影免费视频| 日韩电影二区| 国产精品三级大全| 久久精品熟女亚洲av麻豆精品| 99热网站在线观看| 亚洲少妇的诱惑av| 色吧在线观看| tube8黄色片| 九九久久精品国产亚洲av麻豆| 美女视频免费永久观看网站| 哪个播放器可以免费观看大片| 三级国产精品片| 亚洲精品自拍成人| 免费黄色在线免费观看| 汤姆久久久久久久影院中文字幕| 一边摸一边做爽爽视频免费| 2022亚洲国产成人精品| 国产乱来视频区| 亚洲精品乱码久久久久久按摩| 简卡轻食公司| 91午夜精品亚洲一区二区三区| 一本一本综合久久| 满18在线观看网站| 五月天丁香电影| 亚洲欧美一区二区三区黑人 | 91久久精品国产一区二区成人| 99re6热这里在线精品视频| 制服人妻中文乱码| 久久久久久久久久成人| 久久精品久久精品一区二区三区| 国产成人精品福利久久| 国产成人免费无遮挡视频| 久久鲁丝午夜福利片| 综合色丁香网| 不卡视频在线观看欧美| 一二三四中文在线观看免费高清| 精品酒店卫生间| xxxhd国产人妻xxx| 看免费成人av毛片| 国产高清有码在线观看视频| 看十八女毛片水多多多| 欧美日韩国产mv在线观看视频| 女性生殖器流出的白浆| 久久午夜福利片| 日韩熟女老妇一区二区性免费视频| 日日爽夜夜爽网站| 国产男女超爽视频在线观看| av电影中文网址| 全区人妻精品视频| 久久久久网色| 亚洲精品亚洲一区二区| 韩国av在线不卡| av在线观看视频网站免费| 一边摸一边做爽爽视频免费| 欧美日韩在线观看h| 另类精品久久| 最新中文字幕久久久久| 国产深夜福利视频在线观看| 最近最新中文字幕免费大全7| 十八禁高潮呻吟视频| 亚洲av男天堂| 国产色婷婷99| √禁漫天堂资源中文www| 在线观看免费视频网站a站| √禁漫天堂资源中文www| 少妇被粗大的猛进出69影院 | 男男h啪啪无遮挡| 国产精品一区二区在线观看99| 丝袜美足系列| 亚洲第一区二区三区不卡| 春色校园在线视频观看| 人成视频在线观看免费观看| 99热全是精品| 欧美人与性动交α欧美精品济南到 | 久久久久精品久久久久真实原创| 老熟女久久久| 黑人高潮一二区| 国产色婷婷99| 久久ye,这里只有精品| 色5月婷婷丁香| 综合色丁香网| 亚洲成色77777| 性色avwww在线观看| 日本-黄色视频高清免费观看| 国产精品久久久久成人av| 高清黄色对白视频在线免费看| 黄色视频在线播放观看不卡| 亚洲av国产av综合av卡| 飞空精品影院首页| 少妇人妻久久综合中文| 美女中出高潮动态图| √禁漫天堂资源中文www| 80岁老熟妇乱子伦牲交| 色视频在线一区二区三区| 免费看光身美女| 美女福利国产在线| 一级毛片黄色毛片免费观看视频| 亚洲精品日本国产第一区| 欧美精品一区二区大全| 性色av一级| 哪个播放器可以免费观看大片| 熟妇人妻不卡中文字幕| 97超视频在线观看视频| 日韩一区二区视频免费看| 伦理电影免费视频| 日韩,欧美,国产一区二区三区| 日日爽夜夜爽网站| av.在线天堂| a 毛片基地| 日产精品乱码卡一卡2卡三| 热re99久久精品国产66热6| av福利片在线| 亚洲国产毛片av蜜桃av| 91久久精品国产一区二区三区| 国产精品99久久久久久久久| 热re99久久国产66热| 国产精品久久久久久久电影| 最近2019中文字幕mv第一页| 街头女战士在线观看网站| 午夜精品国产一区二区电影| 亚洲一级一片aⅴ在线观看| 成年女人在线观看亚洲视频| 97在线视频观看| 考比视频在线观看| 校园人妻丝袜中文字幕| 99国产综合亚洲精品| 一本一本综合久久| 亚洲精品,欧美精品| 国产欧美日韩一区二区三区在线 | 男女无遮挡免费网站观看| √禁漫天堂资源中文www| 91精品一卡2卡3卡4卡| 久久久久久久精品精品| 人体艺术视频欧美日本| 最黄视频免费看| 亚洲五月色婷婷综合| 亚洲熟女精品中文字幕| 乱人伦中国视频| 自拍欧美九色日韩亚洲蝌蚪91| av视频免费观看在线观看| 18禁在线播放成人免费| 欧美最新免费一区二区三区| 欧美日韩av久久| 欧美日韩一区二区视频在线观看视频在线| 五月天丁香电影| 只有这里有精品99| 99久久人妻综合| 啦啦啦在线观看免费高清www| 久久毛片免费看一区二区三区| av天堂久久9| 日日摸夜夜添夜夜添av毛片| 少妇猛男粗大的猛烈进出视频| 插逼视频在线观看| 亚洲五月色婷婷综合| 欧美bdsm另类| 欧美bdsm另类| 国产成人精品一,二区| 搡老乐熟女国产| av有码第一页| 老司机亚洲免费影院| freevideosex欧美| 高清毛片免费看| 国产一区亚洲一区在线观看| 亚洲精华国产精华液的使用体验| 热re99久久国产66热| 高清黄色对白视频在线免费看| 国产亚洲一区二区精品| 九九久久精品国产亚洲av麻豆| 精品亚洲成a人片在线观看| √禁漫天堂资源中文www| 国产成人freesex在线| 国产在视频线精品| 亚洲av中文av极速乱| 熟妇人妻不卡中文字幕| 国产精品免费大片| 看免费成人av毛片| 美女cb高潮喷水在线观看| 亚洲精品自拍成人| 亚洲不卡免费看| 国产男女内射视频| 黄色一级大片看看| 亚洲国产精品成人久久小说| 免费人妻精品一区二区三区视频| 国产欧美日韩一区二区三区在线 | 少妇的逼水好多| 免费观看无遮挡的男女| 欧美日韩一区二区视频在线观看视频在线| 国产日韩欧美视频二区| 亚洲av男天堂| 午夜免费观看性视频| 色视频在线一区二区三区| 插逼视频在线观看| 三级国产精品片| 搡女人真爽免费视频火全软件| 中文字幕久久专区| 日韩成人av中文字幕在线观看| 国产av精品麻豆| 欧美xxxx性猛交bbbb| 日韩伦理黄色片| 国产精品麻豆人妻色哟哟久久| 丰满迷人的少妇在线观看| 国产av精品麻豆| 简卡轻食公司| 国产黄频视频在线观看| 精品亚洲成国产av| 青青草视频在线视频观看| 国产av码专区亚洲av| 人妻系列 视频| 99热网站在线观看| 日日摸夜夜添夜夜添av毛片| 国产在视频线精品| 欧美日韩成人在线一区二区| 日本91视频免费播放| 99九九线精品视频在线观看视频| 久久久久久久久久人人人人人人| 久久精品国产亚洲网站| 十分钟在线观看高清视频www| 国产伦理片在线播放av一区| 一本大道久久a久久精品| av播播在线观看一区| 少妇精品久久久久久久| 久久久久久久精品精品| 亚洲精品aⅴ在线观看| 亚洲国产成人一精品久久久| 久久人人爽人人爽人人片va| 黄色一级大片看看| 日韩 亚洲 欧美在线| 最新中文字幕久久久久| 赤兔流量卡办理| 国精品久久久久久国模美| 久久久久久久久久人人人人人人| 我要看黄色一级片免费的| 婷婷色av中文字幕| av.在线天堂| 欧美 亚洲 国产 日韩一| 国产女主播在线喷水免费视频网站| 久久久久网色| 亚洲激情五月婷婷啪啪| 一边摸一边做爽爽视频免费| 欧美日韩视频精品一区| 狠狠精品人妻久久久久久综合| 最黄视频免费看| 中文字幕制服av| 一区二区三区精品91| 久久久久久人妻| 在线观看三级黄色| 高清视频免费观看一区二区| 黄片播放在线免费| 成人午夜精彩视频在线观看| 美女国产视频在线观看| 在线观看免费视频网站a站| 午夜激情久久久久久久| 高清毛片免费看| 亚洲色图 男人天堂 中文字幕 | 黄色怎么调成土黄色| 国产免费现黄频在线看| 日本欧美国产在线视频| 亚洲精品亚洲一区二区| 嘟嘟电影网在线观看| 日日撸夜夜添| 久久婷婷青草| 美女xxoo啪啪120秒动态图| 女人久久www免费人成看片| 久久午夜福利片| 精品人妻偷拍中文字幕| 国产亚洲一区二区精品| 最新中文字幕久久久久| 又黄又爽又刺激的免费视频.| 中文精品一卡2卡3卡4更新| 日韩在线高清观看一区二区三区| 精品少妇久久久久久888优播| 岛国毛片在线播放| 婷婷色综合www| 欧美精品人与动牲交sv欧美| 久久精品夜色国产| av免费观看日本| 久久久国产欧美日韩av| 一级a做视频免费观看| 亚洲精华国产精华液的使用体验| 国产亚洲最大av| 人人妻人人爽人人添夜夜欢视频| 美女福利国产在线| av网站免费在线观看视频| 国产精品蜜桃在线观看| 国产成人精品婷婷| 熟女av电影| 免费观看无遮挡的男女| 永久免费av网站大全| 国产精品一二三区在线看| 五月伊人婷婷丁香| 老熟女久久久| 美女国产视频在线观看| 国产淫语在线视频| 免费大片18禁| 老司机影院毛片| 国产精品一区www在线观看| 欧美日韩在线观看h|