[發(fā)明專利]帶重要點(diǎn)約束的相似軌跡判斷方法

有效

• 申請?zhí)枺?/td>: 202010747219.3
• 申請日: 2020-07-30
• 公開（公告）號: CN111967504B
• 公開（公告）日: 2022-10-28
• 發(fā)明（設(shè)計）人: 王前東;謝衛(wèi);周德民;陳貽海;路高勇
• 申請（專利權(quán)）人: 西南電子技術(shù)研究所(中國電子科技集團(tuán)公司第十研究所)
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06F17/16
• 代理公司: 成飛(集團(tuán))公司專利中心 51121
• 代理人: 郭純武

1.一種帶重要點(diǎn)約束的相似軌跡判斷方法，包括如下步驟：首先，從大量時空軌跡序列里發(fā)現(xiàn)用戶頻繁重復(fù)的路徑，從海量的軌跡數(shù)據(jù)中發(fā)現(xiàn)用戶的相似軌跡，根據(jù)經(jīng)典目標(biāo)每次出行活動比較規(guī)律，尋找相似軌跡，將經(jīng)典軌跡輸入判斷矩陣計算模塊，利用判斷矩陣計算模塊計算經(jīng)典軌跡與實(shí)時軌跡之間的判斷矩陣；公共子序列長度計算模塊利用帶匹配路徑約束的多對1最長公共子序列長度算法，計算經(jīng)典軌跡與實(shí)時軌跡在重要點(diǎn)約束下的多對1最長公共子序列長度L(i,j)：

其中，M(i,j)為公式(1)計算的判斷矩陣，I_t為約束I_t＝(i₁,i₂,…,i_t)，i∈I_t表示i等于I_t中的一個元素，表示i不等于I_t中任何一個元素，max{L(i,j-1)+1,L(i-1,j)}表示L(i,j-1)+1與L(i-1,j)二者中的最大值，max{L(i,j-1),L(i-1,j)}表示L(i,j-1)與L(i-1,j)二者中的最大值；輸入判斷矩陣計算模塊的經(jīng)典軌跡為TC_m＝(C₁,C₂,…,C_m),實(shí)時軌跡為TR_n＝(R₁,R₂,…,R_n)，其中，I_t＝(i₁,i₂,…,i_t)為經(jīng)典軌跡TC_m中指定的重要點(diǎn)所在序號，1≤i₁＜i₂＜…＜i_t≤m，C₁,C₂,…,C_m與R₁,R₂,…,R_n為二維坐標(biāo)值,判斷矩陣計算模塊計算經(jīng)典軌跡與實(shí)時軌跡之間的判斷矩陣

1≤i≤m 1≤j≤n

其中，dis(C_i,R_j)為經(jīng)典軌跡的點(diǎn)C_i與實(shí)時軌跡的點(diǎn)R_j之間的歐式距離，

C_i表示經(jīng)典軌跡TC_m的第i個點(diǎn)，i＝1、2、……、m，R_j表示實(shí)時軌跡的第j個點(diǎn)，j＝1、2、…、n，ε為歐式距離門限閾值；相似度計算模塊利用帶重要點(diǎn)約束的多對1最長公共子序列長度與經(jīng)典軌跡長度，計算經(jīng)典軌跡與實(shí)時軌跡在重要點(diǎn)約束下的軌跡相似度，求出經(jīng)典軌跡與實(shí)時軌跡之間的帶重要點(diǎn)約束下的軌跡相似度，判斷經(jīng)典軌跡與待判斷的實(shí)時軌跡在重要點(diǎn)的約束下是否相似，若實(shí)時軌跡為帶重要點(diǎn)的經(jīng)典軌跡的相似軌跡，則將實(shí)時軌跡作為經(jīng)典軌跡的相似軌跡，否則將經(jīng)典軌跡和相似軌跡看作兩序列，重要點(diǎn)看作兩序列的約束序子序列，對重要點(diǎn)的判斷與普通點(diǎn)的判斷同時進(jìn)行；然后基于最長公共子序列距離的軌跡相似判斷，用經(jīng)典軌跡與實(shí)時軌跡在重要點(diǎn)約束下的多對1最長公共子序列長度與經(jīng)典軌跡長度的比值作為經(jīng)典軌跡與實(shí)時軌跡在重要點(diǎn)約束下的軌跡相似度輸出結(jié)果。

2.如權(quán)利要求1所述的帶重要點(diǎn)約束的相似軌跡判斷方法，其特征在于：判斷矩陣計算模塊根據(jù)C_i為經(jīng)典軌跡TC_m＝(C₁,C₂,…,C_m)中的一點(diǎn)和待判斷的相似軌跡TR_n＝(R₁,R₂,…,R_n)中的一點(diǎn)R_j，兩點(diǎn)C_i與R_j之間的歐氏距離dis(C_i,R_j)。