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

    海量時空軌跡的梯形帶相似聚類

    2018-03-27 01:23:57孫衛(wèi)真林秋慧趙秋香
    小型微型計算機系統(tǒng) 2018年2期
    關(guān)鍵詞:海量相似性梯形

    孫衛(wèi)真,林秋慧,向 勇,趙秋香

    1(首都師范大學(xué) 信息工程學(xué)院 計算機科學(xué)與技術(shù)系,北京 100048) 2(清華大學(xué) 計算機科學(xué)與技術(shù)系 網(wǎng)絡(luò)所,北京 100084) 3(山東省 濟(jì)寧市第一中學(xué) 高中數(shù)學(xué)組,山東 濟(jì)寧 272000)

    1 引 言

    由于GPS設(shè)備的逐漸普及,基于位置服務(wù)[1]的廣泛應(yīng)用等,位置信息的獲取變得愈加便捷.毫無疑問,這些數(shù)據(jù)的匯集將是海量的、個體連續(xù)的.個體連續(xù)的位置信息數(shù)據(jù)按照采樣時刻連接而成后,可以得到該運動對象的時空軌跡.海量的時空軌跡背后隱藏的信息帶動了軌跡挖掘的發(fā)展,目前的應(yīng)用范圍涵蓋了包括交通監(jiān)管、人類行為、動物遷徙、自然風(fēng)暴預(yù)測等等[2].因此,分析并聚類實時的海量時空軌跡數(shù)據(jù),獲取典型的軌跡模式是非常有必要的.

    然而,存儲開銷大、計算強度高、聚類幾何特征保留不完整等問題,是海量時空軌跡數(shù)據(jù)的聚類目前所面臨的主要挑戰(zhàn)[3,4].目前國內(nèi)外在軌跡聚類方面的研究中,主要有以下幾個方向[6]:基于數(shù)據(jù)的稀疏度、基于空間劃分、基于興趣點以及基于軌跡的幾何特征等.其中,基于數(shù)據(jù)的稀疏度的方法,屬于數(shù)據(jù)挖掘的通用方法[7],但時間與空間復(fù)雜度都很高,不適用于海量時空軌跡的聚類;而基于空間劃分的方法,計算量相對較小,一般會結(jié)合LCSS方法并在明確的應(yīng)用場景下使用[6,8];基于興趣點劃分的方法準(zhǔn)確度較差,且在興趣點較多的地區(qū),軌跡的校準(zhǔn)與劃分將存在一定困難[9].而基于軌跡幾何特征方法的文獻(xiàn)則相對較少,其中,文獻(xiàn)[10]提出了一種基于結(jié)構(gòu)相似度的軌跡聚類算法,與軌跡的幾何特征有一定的的相關(guān)性,但其對原始軌跡的要求較高.Lee等人[2]在2007年提出了一種新的基于幾何形狀的聚類擬合軌跡的方法,其方法解決了復(fù)雜軌跡之間的比較問題,但是對軌跡進(jìn)行了近似描述,從而造成了軌跡的局部幾何特征丟失.

    此外,實時海量的時空軌跡數(shù)據(jù)的聚類分析,還需考慮聚類的存儲與計算壓力的問題[11],目前已有的解決時效性問題的主要方法集中在對聚類前的軌跡數(shù)據(jù)進(jìn)行簡化[12,13].現(xiàn)有的軌跡數(shù)據(jù)的簡化算法主要分為兩種[12]:一是局部軌跡數(shù)據(jù)簡化,二是整體軌跡數(shù)據(jù)簡化.局部軌跡數(shù)據(jù)的簡化主要針對待處理點,綜合分析并處理與鄰域點間的簡化關(guān)系,如距離閾值的過濾方法等[14].而整體的軌跡簡化大致包括如下四種經(jīng)典的算法[3]:自頂向下(Top-Down,TD)[15]、自下而上、滑動窗口、開放窗口(Opening Window,OW).其中,OW算法的窗口大小是動態(tài)調(diào)整的,該算法適用于實時的流式軌跡數(shù)據(jù).然而經(jīng)典的OW算法在特殊軌跡的處理上并不理想,其一,其簡化后的軌跡保留的拐角信息點過少[12],導(dǎo)致減少了一些更準(zhǔn)確的軌跡行進(jìn)可能;其二,軌跡點過于密集時,其動態(tài)滑動窗口過長,從而明顯增加計算量.余超等在文章[16]中提出的角度可變的滑動窗口算法,能夠在轉(zhuǎn)角較大的情況下保留部分拐角軌跡點.而TD算法對于處理有規(guī)律且比較直的密集軌跡點時,效率非常高,可以彌補OW算法的不足.其經(jīng)典方法有道格拉斯普克(Douglas-Peucher,DP)[4,13]算法,比較常見的有針對既定路線或網(wǎng)格的軌跡簡化[5,17].

    以上的文獻(xiàn)分析可以看出,實時海量時空軌跡聚類的首要問題是由于幾何特征丟失導(dǎo)致的聚類不準(zhǔn)確性[10].聚類的準(zhǔn)確性取決于相似性度量方法,現(xiàn)有的軌跡間相似性度量方法主要集中在軌跡間距離上.如圖1所示,軌跡1、2與軌跡1、3的歐氏距離和是相同的,即相似度一致,然而軌跡1與軌跡2的幾何形狀特征明顯不一致,這無法達(dá)到相似性度量的準(zhǔn)確性預(yù)期.此外,簡化應(yīng)當(dāng)能夠保留必要的軌跡數(shù)據(jù)特征,而現(xiàn)有的軌跡數(shù)據(jù)簡化方法不能直接應(yīng)用到這一場景中.因此,有必要設(shè)計一種海量時空軌跡聚類的算法,用以保留必要的軌跡幾何特征,并兼顧時效性和準(zhǔn)確性的問題.

    圖1 歐式距離相似度不準(zhǔn)確性Fig.1 Inaccuracy of Euclidean distance similarity

    針對海量時空軌跡的聚類,本文將貫徹時效性和準(zhǔn)確性兩大原則進(jìn)行闡述分析.首先,為減小計算量和存儲開銷,本文引入了一種綜合的軌跡簡化策略,不僅充分考慮了軌跡的時間和空間要素,更加入了軌跡的形狀特征因素.著眼于簡化后的時空軌跡數(shù)據(jù)的幾何特征,在前期的工作[18]中,我們結(jié)合計算幾何的方法對軌跡進(jìn)行擴(kuò)展,選擇了計算復(fù)雜度較低的軌跡梯形帶,定義了軌跡間的相似性度量方法.該方法可以在多項式時間內(nèi)計算軌跡范圍,并判斷在不同時間跨度上的軌跡間相似性,在此基礎(chǔ)上,本文提出了海量時空軌跡的梯形帶相似聚類算法.該方法利用線性線段落在軌跡形成的梯形范圍內(nèi)長度和本身長度的比值定義相似,在充分考慮軌跡幾何特征的條件下,能夠較為快速地獲取時空軌跡的有效聚類結(jié)果.最后,經(jīng)海量真實時空軌跡數(shù)據(jù)測試集(北京市2010年04月06日出租車數(shù)據(jù))測試,本文方法能快速并合理保留細(xì)節(jié)特征地進(jìn)行軌跡數(shù)據(jù)簡化,準(zhǔn)確有效地聚類同類軌跡并獲取合理的軌跡模式.

    2 軌跡相似性度量

    相似性度量作為軌跡聚類的標(biāo)準(zhǔn),給出的定義越契合實際,軌跡聚類的效果也越好.此前的工作中,為減小計算量,采用梯形帶的方式簡化了時空軌跡帶[18].眾所周知,聚類后的軌跡簇一般是分區(qū)域的,那些區(qū)域可大可小,形狀不一.分在一個簇中的軌跡定義為相似的,相對于簇而言,這些軌跡是細(xì)小的.將軌跡簇類比于時空軌跡的梯形帶,那么相似于該梯形帶的軌跡也是細(xì)小的.因此,如圖2所示,假設(shè)存在一個軌跡梯形帶,令其他的軌跡均與軌跡帶的中心軌跡進(jìn)行相似度匹配,即可得到有效的軌跡聚類,其直觀的度量標(biāo)準(zhǔn)為落在軌跡帶中軌跡長度與軌跡原長度的比值.

    圖2 軌跡的梯形帶擴(kuò)展及相似性示意Fig.2 Trapezoidal belt of trajectory and similarity diagram

    經(jīng)過以上論證,為更準(zhǔn)確的描述軌跡間相似性,本文將在已有研究的基礎(chǔ)上,增加軌跡的幾何特征因素,提出如下的軌跡相似性度量模型.

    2.1 時空軌跡的定義

    運動對象的時空軌跡是由一系列采樣點,按照采樣時刻的順序連接而成的.傳統(tǒng)的軌跡描述方法[19]主要利用二維空間坐標(biāo),其缺點是,軌跡分類局限性較大,且無法非常準(zhǔn)確地描述一條軌跡.為提高軌跡聚類的有效性,參考文獻(xiàn)[20]的做法,利用運動物體的特定編號、空間坐標(biāo)、速度、方向等信息共同描述一條軌跡.

    定義1.時空軌跡:一條時空軌跡可以表示為

    Tr={(id,pi)|pi=(xi,yi,ti,vi,di),i=1,2,…,n}

    (1)

    其中,id表示軌跡Tr的特定編號,也即唯一標(biāo)識,pi表示軌跡的第個采樣點,n表示軌跡的采樣點個數(shù),(xi,yi)表示第i個采樣點的二維空間坐標(biāo),(ti,vi,di)分別表示軌跡Tr在第i個采樣點位置的時間信息、速度信息和方向信息.

    定義2.原始軌跡:原始數(shù)據(jù)經(jīng)過實時預(yù)處理后,按軌跡編號形成了一條條連續(xù)的軌跡.

    (2)

    定義3.軌跡模式:代表一組軌跡,初始聚類時,取原始軌跡中的一條經(jīng)準(zhǔn)確簡化而成.在類中軌跡達(dá)到一定量時,擬合這類軌跡并簡化,得到新的更合理的軌跡模式.

    (3)

    其中simiID為與該軌跡模式相似的原始軌跡的相似度similarity與oriID對的集合,初始為?.

    2.2 時空軌跡梯形帶

    定義4.時空軌跡梯形帶:表示如下

    (4)

    2.3 軌跡相交判斷

    避免完全不可能相交的兩軌跡段進(jìn)行軌跡相似計算,能夠有效減少計算量,通過判定構(gòu)成軌跡段的基于坐標(biāo)系的最小矩形是否相交,能夠粗略地判定軌跡段是否相交.

    定義5.相交粗判:設(shè)有兩點(xn,yn)、(xn+!,yn+1),則兩點構(gòu)成的基于坐標(biāo)系的最小矩形為R,可以表示成R((xmin,ymin),(xmax,ymax)),其中(xmin,ymin)是R左下角點,(xmax,ymax)是的右上角點.

    (5)

    2.4 軌跡相交長度

    1978年,Cyrus&Beck[21]提出了一種判斷直線與凸多邊形相交測試的算法—Cyrus&Beck裁剪算法(以下簡稱CB算法),其算法的復(fù)雜度為O(n).如圖3所示,除重合外,線段與多邊形相交主要有以下4種情況.

    圖3 CB算法求解相交長度Fig.3 CB algorithm for intersection length

    本文采用了增加重合情況的算法,用以計算軌跡段與梯形帶的相似長度.

    LenCB(Apexi,pjpj+1)

    (6)

    2.5 軌跡的相似性計算

    為衡量時空軌跡的幾何相似性,在判定軌跡段與軌跡帶的相交情況后,利用軌跡段落在軌跡帶中的長度與軌跡段自身原長的比值,可以描述為軌跡的幾何相似性.

    定義7.基于梯形帶的軌跡相似性:原始軌跡Tro與軌跡模式Trm產(chǎn)生的梯形帶Tp進(jìn)行匹配,有軌跡段RIi-j=1.說明兩者可能相交,并可能產(chǎn)生軌跡段相似長度.則軌跡Tro與Trm的擴(kuò)展梯形帶Tp的基于梯形帶的軌跡相似度(Trapezoidal Belt Based Similarity, TBST)可以表示為:

    (7)

    3 軌跡間的相似聚類算法

    為實時處理海量真實的時空軌跡數(shù)據(jù),通過對數(shù)據(jù)進(jìn)行預(yù)處理,完成了清潔可用數(shù)據(jù)的獲取.為了保證實時海量時空軌跡聚類的時效性和準(zhǔn)確性,針對軌跡數(shù)據(jù)存在大量密集點和直線軌跡點等特征,提出了海量時空軌跡的梯形帶相似聚類算法(Feature Preserved-Trapezoidal Belt,FP-TB),它包含2個階段.其一是綜合的特征保留簡化算法,它在保證能夠保留軌跡幾何特征的條件下,盡可能地進(jìn)行數(shù)據(jù)存儲量的壓縮,并以不增加時間開銷為目的.其二是時空軌跡的梯形帶相似聚類算法,它在更優(yōu)的時間內(nèi)獲取更具價值的軌跡模式.下面將進(jìn)行更為具體的描述.

    3.1 必要的軌跡簡化策略

    基于海量實時時空軌跡的時效性和準(zhǔn)確性的需求,本文在前述內(nèi)容的基礎(chǔ)上,為較快壓縮數(shù)據(jù)量、保留細(xì)節(jié)特征時盡量減少銳角并快速處理較長的密集軌跡點,在軌跡數(shù)據(jù)簡化方面,制定整體軌跡數(shù)據(jù)簡化為主,局部軌跡數(shù)據(jù)簡化為輔的綜合軌跡壓縮算法,以達(dá)到快速并合理保留軌跡特征地進(jìn)行軌跡數(shù)據(jù)壓縮.

    其中,局部鄰域點簡化(Neighborhood Points Compression,NPC)的核心思想在于,綜合分析待處理點與鄰域點,較快壓縮數(shù)據(jù)量.而整體軌跡數(shù)據(jù)簡化的算法又包含有兩種,一種是帶銳角限制的開窗算法(Angle Limited Opening Window,ALOW),用于整體的動態(tài)簡化并保留一些較為特殊的軌跡局部特征;另一種是針對擁有大量較為筆直的軌跡點,利用DP算法直接進(jìn)行軌跡簡化.實時動態(tài)簡化以NPC算法為第一道關(guān)卡,ALOW算法為主要的簡化方法,在點閾值達(dá)到一定程度時再觸發(fā)DP算法,三者相輔相成.以下是詳細(xì)的算法描述.

    算法1.綜合的特征保留簡化算法(Feature Preserved Simplification,F(xiàn)P).

    輸入:原始軌跡Tro,局部簡化閾值SUBSIMPTHR,整體簡化閾值SIMPTHR,長直軌跡點閾值PTTHR

    輸出:簡化后的軌跡Trosimp

    算法步驟:

    1)initialize(SUBSIMPTHR,SIMPTHR,PTTHR);//初始簡化閾值

    2)copyInfo(Tro,Trosimp)//復(fù)制軌跡基本信息到簡化軌跡中

    3)addp1toTrosimp//將軌跡起始點放入簡化軌跡中

    4)for(next= 1;next≤n;next++){

    5)for(i= 1;i≤n-next;i++){ //NPC算法

    6)if(Dist(pnext,pnext+i)>SUBSIMPTHR){

    7) delete {pnext+1,pnext+i-1} fromTro;

    8)break;

    9) }

    10) }

    11) countDP = 0;//用于觸發(fā)DP算法的flag

    12)for(j= 1;j≤n-next-i;j++){//ALOW算法

    13) LPDist=

    Dist(Line(pnext,pnext+i+j),pnext+i+K),K∈[0,j);

    14)if(LPDist

    15) countDP++;

    16)else{

    17) Kmax=MAX(LPDist);//當(dāng)有距離超過SIMPTHR時,選擇距離最大的浮動點

    18)Qobt=FIRSTAngle(∠pbeforepnextpnext+i+Q>90°)

    ‖MAXAngle(∠pbeforepnextpnext+i+Q>90°),

    Q∈[Kmax,0]

    //注意向前浮動

    19) addpnext+i+QobttoTrosimp;//浮動點放入簡化軌跡

    20)next=next+i+Qobt,countDP=0;

    21) }

    22)if(countDP ≥PTTHR){

    23) //超過軌跡點閾值PTTHR,觸發(fā)DP算法.

    24) addpnext+i+jtoTrosimp;

    25) dpLine(pnext,pnext+i+j);

    26) countDP=0,next=next+i+j;

    27) }

    28) }

    29)}

    30)returnTrosimp;

    算法1是一個特征保留的軌跡簡化算法,它首先選擇從待簡化的原始軌跡Tro中,取第一個點作為簡化軌跡Trosimp的起始點,其后續(xù)進(jìn)入的每一個點,均先與前一個簡化后的點進(jìn)行NPC算法,再按照如下的ALOW算法簡化軌跡段.

    前一條簡化后的軌跡段末端點作為起始點,從該點開始處理后面連續(xù)的n(n>=3)個點,第n個點設(shè)為浮動點:過起始點和浮動點做一條直線,分別計算中間n-2個點到直線的距離LPDist,若所有距離均小于距離閾值,則下一個數(shù)據(jù)點設(shè)為浮動點,計數(shù);否則,選取與直線距離最大的點作為浮動點,進(jìn)行“浮動點前移”:從該浮動點向前到起始點的下一點,依次作為浮動點計算三個點之間的夾角,利用函數(shù)FIRSTAngle選取浮動點,該浮動點是第一個和起始點間的軌跡段與前一條軌跡段成鈍角的點,將該浮動點加入到簡化軌跡Trosimp中,并成為下一個起始點;若所有兩軌跡段間的夾角都不大于90°,則利用函數(shù)MAXAngle選取與前一條軌跡段成最大角的浮動點加入到簡化軌跡Trosimp中,作為下一次循環(huán)的起始點.

    當(dāng)在ALOW算法簡化過程中的計數(shù)超過閾值時,觸發(fā)DP算法函數(shù)dpLine,將所有當(dāng)前未處理的點取出,并將首尾兩點存入簡化軌跡Trosimp中,連接這兩點,計算中間所有點到該線的距離,若超過閾值,則將距離最大的點存入Trosimp中;連接首尾兩點,得到兩條直線,重復(fù)前述步驟,直到所有點到直線的距離均不超過閾值為止.

    該算法得到的簡化軌跡,通過NPC算法減小了OW算法的繁復(fù)計算壓力,利用DP算法的優(yōu)勢緩解了OW算法在處理長直軌跡點時的計算壓力,銳角特性的加入,則使得最終得到的簡化軌跡保留了一定的細(xì)節(jié)特征,能有效地應(yīng)用于實際場景中,同時為后續(xù)的聚類分析減小了較大的工作量.

    3.2 海量時空軌跡的梯形帶相似聚類

    本文的相似性度量標(biāo)準(zhǔn),基于軌跡的幾何特征,在擴(kuò)展簡化后的軌跡模式Trm為梯形帶后,采用原始軌跡Tro落在軌跡模式Trm中的軌跡相似長度和,與原始軌跡Tro的長度比值來進(jìn)行定義.這種方法,彌補了歐氏距離對軌跡幾何特征的忽略,解決了采用多邊形重合面積比定義相似性的不穩(wěn)定問題.基于此,軌跡便能夠得到較好的聚類,并能夠得到更能代表聚類軌跡特征的軌跡模式.具體算法如下:

    算法2.海量時空軌跡的梯形帶相似聚類算法(Trapezoidal Belt Based Clustering,TB).

    輸入:原始軌跡集合I={Troi,i=1,2,…,k},其中原始軌跡為實時增加的;軌跡模式集合Q={Trmi,i=1,2,…,s},初始為空集?,隨聚類的進(jìn)行而增長;相關(guān)參數(shù):軌跡帶寬度WIDTH,相似度閾值SIMILARTHR

    輸出:軌跡模式類集合Q

    算法步驟:

    1)initialize(WIDTH,SIMILARTHR);//初始梯形帶寬度、相似度閾值

    2)Q=?;//初始化軌跡模式類集合Q為空集

    3)for(eachTrokin theI){ //遍歷集合的原始軌跡

    4)if(Q==?){

    5) createNewTrm(Tro,Trm);//生成第一條軌跡模式Trm

    6) addTrmtoQ;//將Trm加入到軌跡模式類集合Q中

    7) }

    8)else{

    9) similarflag=false;

    10)for(eachTrmsin theQ){ //遍歷集合Q的軌跡模式

    11) creatApex(Trms,WIDTH);//依據(jù)軌跡帶寬度生成軌跡模式梯形帶

    13)if(TBBS>SIMILARTHR){

    14) add(TBBS,ido)tosimiID;//維護(hù)當(dāng)前Trm的simiID

    15) similarflag=true;

    16) }

    17) }

    18)if(similarflag ==false){

    19) createNewTrm(Tro,Trm);

    20) addTrmtoQ;//將Trm加入到軌跡模式類集合Q中

    21) }

    22) }

    23)}

    算法2在初始時,初始化軌跡模式集合Q為空集,相關(guān)參數(shù)的梯形帶寬度WIDTH和相似度閾值SIMILARTHR.對所有在原始軌跡集合I中的所有原始軌跡,與所有在軌跡模式集合Q中的每一條軌跡模式進(jìn)行相似度計算.首先生成簡化后的軌跡模式梯形帶,采用前述的相似性度量模型,計算兩軌跡間的相似度TBBS的值.繼而判斷當(dāng)相似度的值大于相似度閾值SIMILARTHR時,認(rèn)為該原始軌跡Tro與當(dāng)前Trm相似,維護(hù)當(dāng)前Trm的simiID集合,從而達(dá)到聚類效果.最后,若當(dāng)前軌跡模式集合Q中沒有任何一條軌跡模式Trm與該原始軌跡Tro相似的話,依據(jù)該原始軌跡Tro生成一條軌跡模式Trm并參與后續(xù)計算.

    從此處可以看出,軌跡模式所含數(shù)據(jù)點越多,則軌跡模式段越多,軌跡模式所對應(yīng)的梯形帶中所含梯形越多,這樣,計算原始軌跡在梯形帶內(nèi)的長度時,計算量就會越大,所以,軌跡模式是簡化后的軌跡,而且,簡化后的軌跡做軌跡模式與原始軌跡計算的相似度和未簡化前的軌跡做軌跡模式與原始軌跡計算相似度,兩者相似度相差不大,而前者的計算量則較后者大大減小了.

    3.3 算法時間復(fù)雜性分析

    在給出具體算法的基礎(chǔ)上,分析算法的時間復(fù)雜度是很有必要的.通過時間復(fù)雜度的分析,能夠進(jìn)一步的改進(jìn)和優(yōu)化算法的結(jié)構(gòu),以達(dá)到更加實時高效的目的.

    算法1是一個綜合特征保留的軌跡簡化算法,為了追求最好的效率,可能需要反復(fù)執(zhí)行,反復(fù)對軌跡點進(jìn)行簡化,進(jìn)而減少軌跡點的數(shù)量,對m條軌跡,其執(zhí)行次數(shù)為O(m).對每個被保留的軌跡點而言,需要在其他剩余的軌跡點中,尋找下一個被保留點,候選的軌跡點共有O(n)個.因此,每次執(zhí)行的算法時間復(fù)雜度最差為O(n2),最好的情況為O(log2n),其中n表示軌跡集合中軌跡的數(shù)量.

    算法2是海量時空軌跡的梯形帶相似聚類算法,針對算法1產(chǎn)生的軌跡集合形成的原始軌跡,其軌跡的平均長度為O(n-1),對于每個軌跡點,需要在m條軌跡模式中進(jìn)行相似度擬合,因此,算法2的時間復(fù)雜度為O(n-1)O(m).

    其中,算法2由于原始軌跡的個數(shù)是實時增加的,其執(zhí)行的效率主要取決于在聚類過程中形成的軌跡模式條數(shù),當(dāng)軌跡模式較少,其執(zhí)行效率較高,反之,執(zhí)行效率降低.目前本算法對待軌跡模式的增加主要取決于軌跡間相似度的閾值,后續(xù)將會基于此進(jìn)行有效的改進(jìn).

    以上分析可知,本文提出的FP-TB算法,在計算軌跡相似性時,增加了特征保留的軌跡點簡化,減少了大量的軌跡點,其對較為筆直和密集軌跡點的簡化大大提高了軌跡的簡化執(zhí)行效率,利用這些簡化后的軌跡點進(jìn)行相似度計算,充分減少了計算量.增加的軌跡幾何形狀的因素,則使得本算法所得的軌跡聚類結(jié)果更加準(zhǔn)確.

    4 測試與性能分析

    在實驗部分,采用真實數(shù)據(jù)擴(kuò)展的數(shù)據(jù)集對算法的可用性進(jìn)行分析.其中真實數(shù)據(jù)集為2010年04月06日的30382520條北京市出租車數(shù)據(jù),通過過濾得到較為清潔的數(shù)據(jù),并在此基礎(chǔ)上利用空車與重車標(biāo)志位分割軌跡,共得到可用軌跡35380條.使用該數(shù)據(jù)集的優(yōu)勢在于,它包含大量的軌跡信息,包括軌跡的速度、角度、時間、位置信息、軌跡標(biāo)識、類別信息等,并且這些軌跡信息都是真實的,其軌跡出現(xiàn)的情況均為真實應(yīng)用環(huán)境的情形,能夠驗證本文所述方法的真實有效性.

    實驗的硬件環(huán)境為:服務(wù)器端Ubuntu 14.04,內(nèi)存2.00GB,數(shù)據(jù)庫端為Windows 7系統(tǒng),安裝Oracle DB 11g,算法實現(xiàn)代碼為C++,并均在服務(wù)器終端進(jìn)行測試運行.

    4.1 軌跡簡化的實驗結(jié)果

    4.1.1 軌跡簡化算法的幾何特征保留情況

    本文提出的特征保留的軌跡簡化算法FP,其主要目標(biāo)是在不影響軌跡簡化速率的基礎(chǔ)下,盡可能多的保留原始軌跡的有效特征.以較小的空間開銷,保留更多的軌跡特征,其軌跡的可用性越高,反之亦然.在該算法中,有三個閾值需要確定,其中僅有SIMPTHR閾值是與簡化效果密切相關(guān)的距離閾值.

    由于其距離閾值所針對的點均為地圖上的點,而就中國的情況而言,緯度范圍從3°51′N至53°33′N,跨度較大,因此不適合在任意緯度指定固定的閾值.為了獲取更為合理的閾值,在指定閾值時,以千米km為單位,指定閾值為αkm,則不同緯度的緯度閾值由以下公式(8)換算得到:

    (8)

    下面的實驗結(jié)果展現(xiàn)了在不同α值決定的SIMPTHR閾值下,本文算法FP與OW算法所得的簡化軌跡的對比結(jié)果.

    圖4-圖6中虛線均代表原始軌跡,共17個點,左圖的實線為OW算法簡化后的軌跡,右圖實線則是本文算法FP簡化后的軌跡.如圖5所示,在本文的算法中,在保留了原始軌跡中的第8個點之后,若利用OW算法則下一個點為第10個點(即左圖算法中保留的第6個點),由于第8個點和前一個被保留點所成的線段與第8、10個點所成的線段夾角為銳角,本文的算法利用“浮動點前移”,到第9個點(即右圖中保留的第7個點),使得兩者之間的夾角不是銳角.利用OW算法簡化后的軌跡均含有1個銳角,而本文算法FP簡化后的軌跡則不含銳角,且簡化結(jié)果較為穩(wěn)定.

    圖4 值為0.01km時OW與FP的簡化效果Fig.4 Simplified results of OW and FP at α=0.01km

    圖5 值為0.02km時OW與FP的簡化效果Fig.5 Simplified results of OW and FP at α=0.02km

    圖6 值為0.03km時OW與FP的簡化效果Fig.6 Simplified results of OW and FP at α=0.03km

    縱向比較圖4、圖5、圖6可知,隨著α值為0.01km、0.02km、0.03km,OW算法僅在值較小時才能保留原始軌跡的幾何特征,而本文的算法FP,則能夠在較大范圍內(nèi)均保持簡化后的原始軌跡不失真.因此,本文算法FP較OW算法在實際應(yīng)用中更為廣泛.

    4.1.2 執(zhí)行時間比較

    本文所使用的真實的出租車數(shù)據(jù)集中,存在個體連續(xù)的大量密集點、較長時間的直線行駛和部分大型立交橋的轉(zhuǎn)彎行駛軌跡點,因此該簡化算法主要基于以上的數(shù)據(jù)特征進(jìn)行.描述的是,在使用α=0.02km時,OW、ALOW以及本文所述的FP簡化算法,在壓縮率及執(zhí)行時間方面的表現(xiàn).其中,簡化的總點數(shù)W為3651685個點,形成了35380條原始軌跡.

    結(jié)合上述實驗一及表1數(shù)據(jù)可以得到,本文的綜合特征保留算法FP的簡化較OW算法能夠保留更多原始軌跡的特征點,約多了6.75%.由于壓縮率數(shù)值越大,壓縮后的軌跡點所需的存儲空間也越大,而本文算法FP較OW算法的整體壓縮率增加了2.01%,存儲空間開銷隨之增大,但這一比例屬于存儲的可接受范圍.而對比ALOW算法,本文算法FP保留的軌跡點總數(shù)約少了2.36%,整體壓縮率減少了0.77%.這一差異性是由于NPC及DP算法的簡化造成的,而在執(zhí)行時間減少諸多的情況下,這一情況基本可以忽略.

    表1 各簡化算法的壓縮率及執(zhí)行時間Table 1 Compression rate and execution time of each algorithm

    通過觀察表1可以發(fā)現(xiàn),同等實驗條件下,純粹的ALOW算法由于其時間復(fù)雜性較OW算法高,其運行時間較OW算法高出約13%.對于海量的軌跡數(shù)據(jù)而言,時間上的開銷是較難容忍的,因此需要對ALOW算法做進(jìn)一步的改進(jìn).同樣地,從上表也可以看出,本文的FP算法較OW算法的運行時間縮短了約25.82%,較純粹的ALOW算法的執(zhí)行時間縮短了約34.17%.這主要是因為NPC和DP算法有效地簡化和壓縮了這些增長的密集點和長直點,減小了ALOW以及OW算法的窗口,迭代次數(shù)隨之減少,執(zhí)行的時間自然減少.以上數(shù)據(jù)結(jié)果說明,增加了NPC算法和DP算法來進(jìn)行執(zhí)行效率上的改進(jìn)結(jié)果是卓有成效的,達(dá)到了縮短執(zhí)行時間的目的.因此本文提供的FP算法是有效的,且更為高效的.

    4.2 軌跡聚類的實驗結(jié)果

    4.2.1 梯形帶寬度width對軌跡間相似的影響

    本文提出的海量時空軌跡的梯形帶相似聚類算法FP-TB中,閾值width是影響軌跡間相似判斷的主要因素.下面是實驗獲取的某一類軌跡模式聚類的實驗結(jié)果,展現(xiàn)了在不同的width取值下,本文算法FP-TB在同一類軌跡中,其平均相似度的變化.

    圖7 不同width下同類軌跡的平均相似度Fig.7 Average similarity of similar trajectories under different width

    其中灰色底帶表示軌跡模式,黑色線條表示與之相似的原始軌跡,閾值width是影響梯形帶的半帶寬.

    圖7(a)顯示的是width=0.04km時,直線型軌跡的其中一類所有相似軌跡與軌跡模式的相似度平均值,其相似度平均值顯示為0.765518.圖7(b)顯示的是width=0.05km時,直線型軌跡的其中一類所有相似軌跡與軌跡模式的相似度平均值,其相似度平均值顯示為0.818084.

    根據(jù)以上的實驗結(jié)果,橫向比較圖7(a)與圖7(b)不難得出,隨著梯形半帶寬width值的增大,其聚類的軌跡相似度平均值也隨之增大,這說明類中的原始軌跡與軌跡模式的相似度也是增大的.這是符合前文所述相似性度量的結(jié)果,因此本文提供的FP-TB算法的相似性度量模型是行之有效的,且能準(zhǔn)確有效的進(jìn)行各類軌跡的聚類.

    4.2.2 軌跡聚類結(jié)果及執(zhí)行時間的比較分析

    本文所用的真實出租車數(shù)據(jù)集,具有幾何走勢明顯的特征,對于這類軌跡,其主要目標(biāo)是盡可能保證軌跡聚類的準(zhǔn)確性,并挖掘出有價值的軌跡模式信息.本文從35380條原始軌跡中進(jìn)行挖掘,其獲取的軌跡模式較多,下面將舉例給出直線型軌跡模式和環(huán)型軌跡模式的聚類結(jié)果,以驗證聚類的有效性,其梯形帶寬度width=0.05km,軌跡的相似度閾值SIMILARTHR=0.65.

    圖8 不同類型的軌跡聚類結(jié)果Fig.8 Clustering results of different types of trajectories

    圖8顯示的是根據(jù)本文所給的相似性度量模型,對原始軌跡集合進(jìn)行聚類后所得的不同類型的軌跡模式.圖8(a)顯示的是簡單的直線型軌跡模式,其基本呈直線走勢,表明了所有與該直線型軌跡模式相似的原始軌跡的平均相似度為0.716002.參照北京市地圖可以發(fā)現(xiàn),該軌跡模式表示去往首都機場的機場線路徑,說明在一天內(nèi),出租車去往首都機場的出行頻次是較高的.圖8(b)顯示的則是環(huán)型軌跡模式,其走勢為閉合的環(huán)線,圖中表明所有與該環(huán)型軌跡模式相似的原始軌跡的平均相似度為0.770505.該軌跡模式表示由西便門橋、右安門橋、左安門橋、東便門橋所形成的環(huán)線,并去往雙井橋附近.該區(qū)域有較多辦公大樓,屬于出租車司機的長期巡客區(qū)域,而雙井附近有較多居民區(qū),因此這一路線也是出租車經(jīng)常會走的路線.這些軌跡模式均符合北京市的實際交通路況,說明本文的相似性度量模型對于各類軌跡模式均是有效的,而環(huán)型軌跡中保留的部分拐角信息,則是出于幾何特征保留的考慮,由此可見,該聚類結(jié)果具備準(zhǔn)確性.

    此外,為定量比較聚類結(jié)果的執(zhí)行時間,做了如下的幾組實驗來驗證.其中軌跡模式A、B分別是軌跡模式A′、B′簡化后的軌跡,與之聚類的原始軌跡為簡化后的35380條出租車軌跡.

    通過3.3的算法分析可知,本文所述的FP-TB算法其執(zhí)行效率主要取決于軌跡模式的條數(shù)和單條軌跡模式的段數(shù),其中軌跡模式條數(shù)主要由原始軌跡數(shù)據(jù)集決定.由表2可以看出,相同的軌跡在簡化前后聚類所得的原始軌跡集合相差不大,其平均相似度的差別亦不大.而簡化后的軌跡聚類時間大約都減少了50%,其中軌跡模式A較軌跡模式A′的聚類執(zhí)行時間減少了52.2732%,軌跡模式B較軌跡模式B′的聚類執(zhí)行時間減少了59.5798%.

    表2 FP-TB算法與僅TB的聚類方法的執(zhí)行時間比較Table 2 Comparison of the execution time between FP-TB and TB clustering method

    綜合在真實數(shù)據(jù)集上的實驗測試可以發(fā)現(xiàn),本文提出的FP-TB算法可用性較高,并在考慮到軌跡幾何特征后,能夠在不影響執(zhí)行時間的情況下保留重要的原始軌跡特征.在此基礎(chǔ)上,通過提出的相似性度量模型,計算原始軌跡落在軌跡模式梯形帶內(nèi)的長度總和與原始軌跡線段的長度和之比定義相似性,對原始軌跡進(jìn)行準(zhǔn)確聚類,這一聚類方法能夠有效地對包括直線型與環(huán)型交叉等各類軌跡進(jìn)行聚類,且執(zhí)行時間較不經(jīng)過處理直接進(jìn)行聚類的方法快了近50%.因此,本文提出的FP-TB聚類算法是行之有效的.

    5 結(jié)束語

    本文在分析了海量時空軌跡數(shù)據(jù)的空間和時間特性后,考慮到已有的聚類算法在計算軌跡相似性時忽略了軌跡的幾何特征對聚類結(jié)果的影響,導(dǎo)致獲取的軌跡模式的部分重要細(xì)節(jié)特征失真的問題,針對出租車數(shù)據(jù)特征進(jìn)行的軌跡挖掘,提出了FP-TB算法.第一階段的FP算法從存儲效率和保留簡化后的細(xì)節(jié)特征出發(fā),制定了整體簡化為主,局部簡化為輔的軌跡簡化方案.第二階段的TB算法,增加軌跡幾何特征的影響因素,提出了一種新的相似性度量模型.并以此為主要依據(jù)并通過一定的相似度閾值準(zhǔn)確篩選和挖掘相似的時空軌跡簇,進(jìn)行海量時空軌跡的聚類分析.通過真實軌跡數(shù)據(jù)集上的實驗可以看出,本文算法在保留更多的軌跡原始特征的情況下,能夠準(zhǔn)確有效地聚類同類軌跡以獲取典型的出租車行駛軌跡;而對不同類的軌跡,其執(zhí)行效率均有不同程度的提升,因此具有更高的實際意義.

    在未來的研究工作中,我們將考慮在聚類過程中軌跡模式的局部增刪與軌跡模式本身的動態(tài)調(diào)整,以獲取更切合實際的軌跡模式,減小計算開銷.

    [1] Gruteser M,Grunwald D.Anonymous usage of location-based services through spatial and temporal cloaking[C].Proceedings of the 1st International Conference on Mobile Systems,Applications and Services,ACM,2003:31-42.

    [2] Lee J G,Han J,Whang K Y.Trajectory clustering:a partition-and-group framework[C].ACM SIGMOD International Conference on Management of Data,ACM,2007:593-604.

    [3] Keogh E,Chu S,Hart D,et al.An online algorithm for segmenting time series[C].Data Mining,ICDM 2001,Proceedings IEEE International Conference on.IEEE,2001:289-296.

    [4] Meratnia N,Rolf A.Spatiotemporal compression techniques for moving point objects[C].International Conference on Extending Database Technology,Springer Berlin Heidelberg,2004:765-782.

    [5] Muckell J,Hwang J H,Lawson C T,et al.Algorithms for compressing GPS trajectory data:an empirical evaluation[C].Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems,ACM,2010:402-405.

    [6] Su H,Zheng K,Wang H,et al.Calibrating trajectory data for similarity-based analysis[C].Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data,ACM,2013:833-844.

    [7] Simoudis E,Livezey B K,Kerber R G.Method for generating predictive models in a computer system:U.S.Patent 5,692,107[P].1997-11-25.

    [8] Su H,Zheng K,Huang J,et al.Calibrating trajectory data for spatio-temporal similarity analysis[J].The VLDB Journal,2015,24(1):93-116.

    [9] Fu Z,Hu W,Tan T.Similarity based vehicle trajectory clustering and anomaly detection[C].Image Processing,2005.ICIP,IEEE International Conference on.IEEE,2005,2:II-602.

    [10] Yuan Guan,Xia Shi-xiong,Zhang Lei,et al.Trajectory clustering algorithm based on structural similarity[J].Journal on Communications,2011,32(9):103-110.

    [11] Thuraisingham B,Khan L,Clifton C,et al.Dependable real-time data mining[C].Eighth IEEE International Symposium on Object-Oriented Real-Time Distributed Computing,IEEE Computer Society,2005:158-165.

    [12] Chen Y,Jiang K,Zheng Y,et al.Trajectory simplification method for location-based social networking services[C].Proceedings of the 2009 International Workshop on Location Based Social Networks,ACM,2009:33-40.

    [13] Douglas D H,Peucker T K.Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[J].Cartographica:The International Journal for Geographic Information and Geovisualization,1973,10(2):112-122.

    [14] Tobler W R.Numerical map generalization,and notes on the analysis of geographical distributions[M].Department of Geography,University of Michigan,1966.

    [15] Hershberger J E,Snoeyink J.Speeding up the douglas-peucker line-simplification algorithm[M].University of British Columbia,Department of Computer Science,1992.

    [16] Yu Chao,Guo Qing,Xie Wen-jun,et al.A method of fast geomagnetic matching based on orientation alterable sliding window[J].Computer Simulation,2015,32(3):86-89.

    [17] Yu J,Chen G,Zhang X,et al.An improved Douglas-peucker algorithm aimed at simplifying natural shoreline into direction-line[C].Geoinformatics(GEOINFORMATICS),2013 21st International Conference on.IEEE,2013:1-5.

    [18] Zhao Qiu-xiang.Trajectory clustering algorithm based on trapezoid belt similarity measure[D].Beijing:Graduate School of Beijing Normal University,2015.

    [19] Hwang J R,Kang H Y,Li K J.Spatio-temporal similarity analysis between trajectories on road networks[C].International Conference on Conceptual Modeling,Springer Berlin Heidelberg,2005:280-289.

    [20] Hu Hong-yu.Research on methods for traffic event recognition based on video processing[D].Changchun:Jilin University,2010.

    [21] Cyrus M,Beck J.Generalized two-and three-dimensional clipping[J].Computers & Graphics,1978,3(1):23-28.

    附中文參考文獻(xiàn):

    [10] 袁 冠,夏士雄,張 磊,等.基于結(jié)構(gòu)相似度的軌跡聚類算法[J].通信學(xué)報,2011,32(9):103-110.

    [16] 余 超,郭 慶,謝文俊,等.地磁導(dǎo)航基于方向可變滑動窗口快速匹配方法[J].計算機仿真,2015,32(3):86-89.

    [18] 趙秋香.基于梯形帶相似性度量的軌跡聚類算法[D].北京:北京師范大學(xué),2015.

    [20] 胡宏宇.基于視頻處理的交通事件識別方法研究[D].長春:吉林大學(xué),2010.

    猜你喜歡
    海量相似性梯形
    玩轉(zhuǎn)梯形
    幼兒100(2023年37期)2023-10-23 11:38:58
    一類上三角算子矩陣的相似性與酉相似性
    一種傅里葉域海量數(shù)據(jù)高速譜聚類方法
    梯形達(dá)人
    淺析當(dāng)代中西方繪畫的相似性
    河北畫報(2020年8期)2020-10-27 02:54:20
    海量快遞垃圾正在“圍城”——“綠色快遞”勢在必行
    一類變延遲中立型微分方程梯形方法的漸近估計
    梯形
    啟蒙(3-7歲)(2017年6期)2017-11-27 09:34:55
    一個圖形所蘊含的“海量”巧題
    低滲透黏土中氯離子彌散作用離心模擬相似性
    露出奶头的视频| 亚洲综合色网址| 99精品久久久久人妻精品| e午夜精品久久久久久久| 久久人妻av系列| 美国免费a级毛片| 女性被躁到高潮视频| 欧美日韩亚洲高清精品| 亚洲av成人av| 久久精品亚洲av国产电影网| 多毛熟女@视频| 一级毛片精品| 不卡一级毛片| 久久中文看片网| 黄频高清免费视频| 黄色a级毛片大全视频| 大香蕉久久成人网| 看免费av毛片| av网站在线播放免费| 可以免费在线观看a视频的电影网站| 777米奇影视久久| 大片电影免费在线观看免费| 极品人妻少妇av视频| 黄色片一级片一级黄色片| 很黄的视频免费| 少妇的丰满在线观看| 十分钟在线观看高清视频www| 精品国产一区二区久久| 精品熟女少妇八av免费久了| e午夜精品久久久久久久| 日本撒尿小便嘘嘘汇集6| 丝袜美足系列| 高清av免费在线| 99热网站在线观看| 成年人黄色毛片网站| 一区在线观看完整版| 一进一出抽搐动态| 午夜福利在线观看吧| 国产伦人伦偷精品视频| 亚洲伊人色综图| 999久久久国产精品视频| 村上凉子中文字幕在线| 亚洲视频免费观看视频| 久久性视频一级片| 免费一级毛片在线播放高清视频 | 久久精品亚洲av国产电影网| 欧美最黄视频在线播放免费 | 99久久人妻综合| 国产精品免费一区二区三区在线 | 免费观看精品视频网站| 性少妇av在线| 国产单亲对白刺激| 岛国毛片在线播放| 日本精品一区二区三区蜜桃| 国产精品一区二区在线观看99| 村上凉子中文字幕在线| 日日爽夜夜爽网站| 国产成人免费无遮挡视频| 日日摸夜夜添夜夜添小说| 看片在线看免费视频| 在线国产一区二区在线| 成人永久免费在线观看视频| 777久久人妻少妇嫩草av网站| 丰满饥渴人妻一区二区三| 免费在线观看影片大全网站| 极品少妇高潮喷水抽搐| 两个人免费观看高清视频| 亚洲熟妇熟女久久| 亚洲成人国产一区在线观看| 国产免费av片在线观看野外av| 天堂√8在线中文| 亚洲熟妇中文字幕五十中出 | 午夜免费成人在线视频| 亚洲精品在线观看二区| 少妇粗大呻吟视频| 亚洲成人免费av在线播放| 成年动漫av网址| 黄片小视频在线播放| 人人妻人人澡人人爽人人夜夜| 欧美老熟妇乱子伦牲交| 久久精品aⅴ一区二区三区四区| 大香蕉久久网| 亚洲精品乱久久久久久| 激情在线观看视频在线高清 | 精品一区二区三区av网在线观看| 超碰97精品在线观看| 亚洲成av片中文字幕在线观看| 青草久久国产| 男男h啪啪无遮挡| 亚洲伊人色综图| 色94色欧美一区二区| а√天堂www在线а√下载 | 女人被狂操c到高潮| 亚洲一区高清亚洲精品| 极品人妻少妇av视频| 日韩成人在线观看一区二区三区| 久久人人97超碰香蕉20202| 国产xxxxx性猛交| 一区福利在线观看| 天堂√8在线中文| 国产成人精品无人区| a级毛片在线看网站| 欧美色视频一区免费| 久久香蕉激情| 国产精品av久久久久免费| 黄片大片在线免费观看| 很黄的视频免费| 中出人妻视频一区二区| 国产97色在线日韩免费| 免费在线观看亚洲国产| 天天操日日干夜夜撸| 亚洲色图 男人天堂 中文字幕| 狠狠狠狠99中文字幕| 久久精品亚洲av国产电影网| 亚洲精品自拍成人| 99热网站在线观看| av一本久久久久| 黄色丝袜av网址大全| 国产一区有黄有色的免费视频| 在线视频色国产色| 亚洲美女黄片视频| 欧美精品高潮呻吟av久久| av在线播放免费不卡| 午夜免费观看网址| 视频区欧美日本亚洲| 高清黄色对白视频在线免费看| 老汉色av国产亚洲站长工具| 后天国语完整版免费观看| 国产1区2区3区精品| 男人舔女人的私密视频| 老鸭窝网址在线观看| 亚洲欧洲精品一区二区精品久久久| 丰满饥渴人妻一区二区三| 成人免费观看视频高清| 国产激情久久老熟女| 一边摸一边做爽爽视频免费| 男女床上黄色一级片免费看| 满18在线观看网站| 欧美乱妇无乱码| 18禁裸乳无遮挡免费网站照片 | 亚洲av成人不卡在线观看播放网| 亚洲伊人色综图| 久久久久精品人妻al黑| 日本vs欧美在线观看视频| 天天躁日日躁夜夜躁夜夜| 欧美精品高潮呻吟av久久| 18禁裸乳无遮挡免费网站照片 | avwww免费| 这个男人来自地球电影免费观看| 午夜日韩欧美国产| 久久国产精品男人的天堂亚洲| 大型av网站在线播放| e午夜精品久久久久久久| 多毛熟女@视频| 亚洲一区二区三区不卡视频| 国产精品免费视频内射| 亚洲精品在线美女| avwww免费| 欧美日韩成人在线一区二区| 亚洲午夜理论影院| 国产高清激情床上av| 我的亚洲天堂| 老熟妇仑乱视频hdxx| videosex国产| 国内久久婷婷六月综合欲色啪| 国产无遮挡羞羞视频在线观看| 色94色欧美一区二区| 久久久国产一区二区| 国产99白浆流出| 一二三四社区在线视频社区8| 久久亚洲真实| 欧美成狂野欧美在线观看| 丰满人妻熟妇乱又伦精品不卡| 久久人人爽av亚洲精品天堂| 午夜福利影视在线免费观看| 国产精品香港三级国产av潘金莲| 欧洲精品卡2卡3卡4卡5卡区| 在线观看66精品国产| 深夜精品福利| 狂野欧美激情性xxxx| 黑人巨大精品欧美一区二区mp4| 亚洲成人国产一区在线观看| 男女免费视频国产| 亚洲国产欧美一区二区综合| 老司机午夜十八禁免费视频| 丰满人妻熟妇乱又伦精品不卡| 国产1区2区3区精品| 成人影院久久| 亚洲色图综合在线观看| 成年版毛片免费区| 国产亚洲一区二区精品| 伊人久久大香线蕉亚洲五| a级片在线免费高清观看视频| 男女下面插进去视频免费观看| 成人18禁高潮啪啪吃奶动态图| 亚洲 国产 在线| 一夜夜www| 久久午夜综合久久蜜桃| 精品亚洲成国产av| 欧美日韩视频精品一区| av电影中文网址| 免费日韩欧美在线观看| 身体一侧抽搐| 国产淫语在线视频| 久久人妻福利社区极品人妻图片| 国产欧美日韩一区二区精品| av天堂久久9| 黑人巨大精品欧美一区二区mp4| 日韩免费av在线播放| 精品午夜福利视频在线观看一区| 丝袜美足系列| 精品亚洲成a人片在线观看| 国产欧美亚洲国产| 国产成人一区二区三区免费视频网站| 欧美 亚洲 国产 日韩一| 午夜精品国产一区二区电影| 在线观看www视频免费| 在线观看免费高清a一片| 久久国产精品人妻蜜桃| 欧美乱码精品一区二区三区| 麻豆成人av在线观看| 丰满的人妻完整版| 午夜福利,免费看| 天天躁日日躁夜夜躁夜夜| 国产有黄有色有爽视频| 大香蕉久久网| av超薄肉色丝袜交足视频| 99香蕉大伊视频| 熟女少妇亚洲综合色aaa.| 欧美日韩精品网址| 老司机影院毛片| 在线播放国产精品三级| 99国产极品粉嫩在线观看| 嫁个100分男人电影在线观看| netflix在线观看网站| 他把我摸到了高潮在线观看| 在线av久久热| 999久久久国产精品视频| 中亚洲国语对白在线视频| 国产成人精品久久二区二区免费| 十八禁网站免费在线| 校园春色视频在线观看| 久久久久久久国产电影| 欧美亚洲 丝袜 人妻 在线| av电影中文网址| 人妻一区二区av| 久久ye,这里只有精品| 亚洲欧美日韩另类电影网站| 国产成人精品久久二区二区91| 女人被狂操c到高潮| 一二三四在线观看免费中文在| 黄色视频,在线免费观看| 最新美女视频免费是黄的| 丁香欧美五月| 很黄的视频免费| 妹子高潮喷水视频| 国产精品久久视频播放| 曰老女人黄片| 午夜亚洲福利在线播放| 99精品在免费线老司机午夜| 国产一卡二卡三卡精品| 国产精品欧美亚洲77777| 人人妻,人人澡人人爽秒播| 亚洲人成电影观看| 成年版毛片免费区| 国产成人精品久久二区二区91| 精品高清国产在线一区| 黄片小视频在线播放| 成熟少妇高潮喷水视频| 丝瓜视频免费看黄片| 这个男人来自地球电影免费观看| 欧美精品亚洲一区二区| 精品福利永久在线观看| 亚洲国产精品合色在线| 亚洲性夜色夜夜综合| 一级毛片女人18水好多| 亚洲成人国产一区在线观看| 久久久久精品国产欧美久久久| 搡老岳熟女国产| 美女 人体艺术 gogo| 精品一区二区三区视频在线观看免费 | 国产成人免费观看mmmm| 老熟妇仑乱视频hdxx| 18禁裸乳无遮挡免费网站照片 | 高清视频免费观看一区二区| 欧美大码av| 日韩 欧美 亚洲 中文字幕| 日韩一卡2卡3卡4卡2021年| 亚洲精品在线美女| 午夜福利在线观看吧| 亚洲va日本ⅴa欧美va伊人久久| 人人妻人人澡人人爽人人夜夜| 午夜免费鲁丝| 亚洲久久久国产精品| 国产片内射在线| 无遮挡黄片免费观看| 无人区码免费观看不卡| ponron亚洲| a在线观看视频网站| 欧美日韩av久久| 国产伦人伦偷精品视频| 又黄又粗又硬又大视频| 亚洲性夜色夜夜综合| 中文字幕av电影在线播放| 欧美黄色片欧美黄色片| 国产在线精品亚洲第一网站| 国产免费av片在线观看野外av| 动漫黄色视频在线观看| 亚洲一码二码三码区别大吗| 国产免费男女视频| 中文字幕人妻丝袜制服| 天天躁日日躁夜夜躁夜夜| 女人久久www免费人成看片| 91大片在线观看| 日韩 欧美 亚洲 中文字幕| 欧美黄色淫秽网站| 国产在线一区二区三区精| 亚洲色图 男人天堂 中文字幕| 亚洲欧美日韩另类电影网站| 久久精品成人免费网站| 下体分泌物呈黄色| 最近最新中文字幕大全免费视频| 欧美日韩瑟瑟在线播放| 男女免费视频国产| 亚洲午夜精品一区,二区,三区| 99精国产麻豆久久婷婷| 国产亚洲精品一区二区www | 亚洲五月色婷婷综合| 亚洲精品中文字幕一二三四区| 久久国产亚洲av麻豆专区| 国产欧美日韩精品亚洲av| 欧美久久黑人一区二区| 黄片小视频在线播放| 黄色丝袜av网址大全| 国产高清激情床上av| 久久久国产一区二区| 国产精品久久久av美女十八| 老司机午夜十八禁免费视频| 国产日韩欧美亚洲二区| 亚洲精品乱久久久久久| 波多野结衣av一区二区av| 精品国产一区二区久久| 日本五十路高清| 精品国产一区二区久久| 国产男靠女视频免费网站| 国产麻豆69| 日韩制服丝袜自拍偷拍| 午夜精品久久久久久毛片777| 欧美成人午夜精品| 91国产中文字幕| 亚洲三区欧美一区| 国产精华一区二区三区| 又紧又爽又黄一区二区| 又大又爽又粗| 久久香蕉精品热| 又大又爽又粗| 超碰97精品在线观看| 国产精品偷伦视频观看了| 国产免费现黄频在线看| 中文字幕最新亚洲高清| 亚洲av美国av| 国产激情欧美一区二区| 19禁男女啪啪无遮挡网站| 脱女人内裤的视频| videosex国产| 亚洲一区二区三区不卡视频| 久久人妻福利社区极品人妻图片| 热99国产精品久久久久久7| 亚洲精品中文字幕一二三四区| 老司机深夜福利视频在线观看| 国产亚洲精品久久久久5区| 又黄又粗又硬又大视频| 天天操日日干夜夜撸| 曰老女人黄片| 99riav亚洲国产免费| 麻豆乱淫一区二区| 两性夫妻黄色片| 亚洲精品成人av观看孕妇| 国产精品 国内视频| 亚洲色图av天堂| 大型av网站在线播放| 欧美不卡视频在线免费观看 | 久久草成人影院| 午夜影院日韩av| 国产精品亚洲av一区麻豆| 亚洲少妇的诱惑av| 777米奇影视久久| 国产又爽黄色视频| 国产精品免费大片| 国产精品国产av在线观看| av天堂久久9| 人妻一区二区av| 精品国产乱子伦一区二区三区| 一二三四社区在线视频社区8| 精品国内亚洲2022精品成人 | 欧美精品av麻豆av| 亚洲久久久国产精品| 99精品在免费线老司机午夜| 久久国产精品大桥未久av| 美国免费a级毛片| 性色av乱码一区二区三区2| 女人爽到高潮嗷嗷叫在线视频| 久久人妻熟女aⅴ| 亚洲自偷自拍图片 自拍| 黄频高清免费视频| 国产精品99久久99久久久不卡| 久久久久久久久久久久大奶| 亚洲av成人不卡在线观看播放网| 亚洲精品乱久久久久久| 一区二区日韩欧美中文字幕| 欧美久久黑人一区二区| av有码第一页| 亚洲专区字幕在线| 久久久久久久精品吃奶| 亚洲成人免费电影在线观看| 久99久视频精品免费| 人人妻,人人澡人人爽秒播| 国产精品亚洲av一区麻豆| 精品一区二区三卡| 欧美精品av麻豆av| 午夜福利乱码中文字幕| 免费不卡黄色视频| 欧美在线黄色| 高清av免费在线| 免费看a级黄色片| 亚洲色图 男人天堂 中文字幕| 中文字幕制服av| aaaaa片日本免费| 无遮挡黄片免费观看| 熟女少妇亚洲综合色aaa.| 国产欧美日韩一区二区三| 精品第一国产精品| 国产欧美亚洲国产| 韩国av一区二区三区四区| 国产有黄有色有爽视频| 国产精品99久久99久久久不卡| 男人的好看免费观看在线视频 | 日本黄色日本黄色录像| 欧美乱码精品一区二区三区| 夜夜爽天天搞| 一二三四在线观看免费中文在| 久久精品成人免费网站| 老熟妇仑乱视频hdxx| 国产亚洲欧美98| 国产不卡一卡二| 免费av中文字幕在线| 亚洲视频免费观看视频| 真人做人爱边吃奶动态| 亚洲七黄色美女视频| 麻豆成人av在线观看| 欧美色视频一区免费| 99国产极品粉嫩在线观看| 亚洲一区中文字幕在线| 最近最新中文字幕大全免费视频| 黄网站色视频无遮挡免费观看| 麻豆国产av国片精品| 欧美+亚洲+日韩+国产| 国产区一区二久久| 午夜福利一区二区在线看| 久久久久精品国产欧美久久久| 精品人妻熟女毛片av久久网站| 国产精品电影一区二区三区 | 一级黄色大片毛片| 久99久视频精品免费| 天天躁狠狠躁夜夜躁狠狠躁| av天堂久久9| 大香蕉久久网| 在线十欧美十亚洲十日本专区| 久久久久国内视频| 午夜视频精品福利| 中出人妻视频一区二区| 99热只有精品国产| 9191精品国产免费久久| 电影成人av| 999精品在线视频| 免费不卡黄色视频| 另类亚洲欧美激情| 亚洲精品久久午夜乱码| 国产亚洲精品久久久久5区| 国产精品免费大片| 亚洲第一av免费看| 国产人伦9x9x在线观看| 久久久国产精品麻豆| 亚洲自偷自拍图片 自拍| 视频在线观看一区二区三区| 一进一出抽搐gif免费好疼 | 免费在线观看视频国产中文字幕亚洲| 交换朋友夫妻互换小说| 12—13女人毛片做爰片一| 夜夜夜夜夜久久久久| 久久精品熟女亚洲av麻豆精品| 久久久久久久久免费视频了| 精品国产一区二区三区久久久樱花| 欧美激情久久久久久爽电影 | 在线看a的网站| 丰满饥渴人妻一区二区三| aaaaa片日本免费| 成年动漫av网址| 亚洲精品久久午夜乱码| 日本a在线网址| 丰满饥渴人妻一区二区三| 久久这里只有精品19| 久久这里只有精品中国| 天堂av国产一区二区熟女人妻| 两个人视频免费观看高清| 午夜福利在线观看免费完整高清在 | 国产精品野战在线观看| 久久6这里有精品| 亚洲成人免费电影在线观看| 一级黄片播放器| 国产精品av视频在线免费观看| 成人一区二区视频在线观看| 国产高清有码在线观看视频| 三级国产精品欧美在线观看| 国产97色在线日韩免费| 黄片小视频在线播放| 中文资源天堂在线| 欧美xxxx黑人xx丫x性爽| 国产精品综合久久久久久久免费| 午夜福利成人在线免费观看| 国产高清视频在线观看网站| 两性午夜刺激爽爽歪歪视频在线观看| 黄片大片在线免费观看| 久久国产乱子伦精品免费另类| 又黄又爽又免费观看的视频| 免费观看的影片在线观看| 2021天堂中文幕一二区在线观| 在线播放国产精品三级| 精品久久久久久久毛片微露脸| 欧美最新免费一区二区三区 | 亚洲av电影不卡..在线观看| 国产黄a三级三级三级人| 岛国在线观看网站| 亚洲人成电影免费在线| 一级a爱片免费观看的视频| 国产成人av激情在线播放| 99国产综合亚洲精品| 亚洲中文字幕日韩| 国产亚洲欧美98| 日韩欧美三级三区| 一区二区三区国产精品乱码| 久久天躁狠狠躁夜夜2o2o| 日韩欧美免费精品| 一区二区三区激情视频| 免费在线观看成人毛片| 久久中文看片网| 国产精品99久久久久久久久| 亚洲最大成人手机在线| 精华霜和精华液先用哪个| 脱女人内裤的视频| 国产高清有码在线观看视频| 久久久久久人人人人人| 一卡2卡三卡四卡精品乱码亚洲| 床上黄色一级片| 成年版毛片免费区| 非洲黑人性xxxx精品又粗又长| 免费av毛片视频| 久久久久免费精品人妻一区二区| 日韩欧美精品免费久久 | 欧美一区二区亚洲| 中文亚洲av片在线观看爽| 女人被狂操c到高潮| 亚洲熟妇中文字幕五十中出| 国产精品一区二区三区四区免费观看 | 成人欧美大片| 日韩av在线大香蕉| 久久欧美精品欧美久久欧美| 黄色丝袜av网址大全| 深爱激情五月婷婷| 身体一侧抽搐| 熟女少妇亚洲综合色aaa.| 久久久久久久午夜电影| 亚洲精品一卡2卡三卡4卡5卡| 老司机午夜十八禁免费视频| 99热只有精品国产| 岛国在线观看网站| 午夜激情欧美在线| 国产精品,欧美在线| 99国产精品一区二区三区| 精品熟女少妇八av免费久了| 日韩欧美一区二区三区在线观看| 在线播放无遮挡| 欧美成狂野欧美在线观看| 国产精品香港三级国产av潘金莲| 午夜免费男女啪啪视频观看 | 亚洲精品亚洲一区二区| 黄色丝袜av网址大全| 制服丝袜大香蕉在线| 一进一出抽搐gif免费好疼| 国产av一区在线观看免费| 在线观看美女被高潮喷水网站 | 最好的美女福利视频网| 高潮久久久久久久久久久不卡| 啪啪无遮挡十八禁网站| 国产av在哪里看| 怎么达到女性高潮| 亚洲国产精品成人综合色| 午夜免费成人在线视频| 亚洲欧美日韩高清在线视频| 老鸭窝网址在线观看| 久久人人精品亚洲av| 99精品在免费线老司机午夜| 国模一区二区三区四区视频| 成人三级黄色视频| 小蜜桃在线观看免费完整版高清| 亚洲五月婷婷丁香| 少妇丰满av| 搡老熟女国产l中国老女人| 久久九九热精品免费| 久久亚洲精品不卡| 国产午夜精品论理片| 精品熟女少妇八av免费久了| 国产91精品成人一区二区三区| 脱女人内裤的视频| 午夜老司机福利剧场|