[發(fā)明專利]一種基于稀疏表示和Fréchet距離融合的軌跡相似度計(jì)算方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202010026567.1
• 申請(qǐng)日: 2020-01-10
• 公開(kāi)（公告）號(hào): CN111259098B
• 公開(kāi)（公告）日: 2023-04-11
• 發(fā)明（設(shè)計(jì)）人: 李芳;趙文婷;藍(lán)如師;劉憶寧;鐘艷如;臧美美;鄭金云;王如月;羅笑南
• 申請(qǐng)（專利權(quán)）人: 桂林電子科技大學(xué)
• 主分類號(hào): G06F16/29
• 分類號(hào): G06F16/29;G06F16/28
• 代理公司: 桂林市華杰專利商標(biāo)事務(wù)所有限責(zé)任公司 45112
• 代理人: 陸夢(mèng)云

1.一種基于稀疏表示和Fréchet距離融合的軌跡相似度計(jì)算方法，其特征是：包括如下步驟：

(1)稀疏表示系數(shù)求解相似度sim1，將需要求解相似鄰居的軌跡表示為測(cè)試樣本，數(shù)據(jù)集中除測(cè)試樣本之外其他的軌跡表示為訓(xùn)練樣本，建立用戶軌跡的矩陣形式：

其中每一行表示的是該軌跡上等時(shí)間間隔選取的m個(gè)軌跡點(diǎn)，每個(gè)軌跡點(diǎn)有v個(gè)屬性，R_m.v′代表軌跡上第m個(gè)軌跡點(diǎn)的第v個(gè)屬性值；

(2)對(duì)矩陣軌跡數(shù)據(jù)預(yù)先處理，稀疏表示形式如下：

β＝a₁α₁++a₂α₂+…+a_nα_n

其中，β為測(cè)試樣本，α_i為訓(xùn)練樣本(i＝1，2…n)，a_i為需要求解的系數(shù)；

建立用戶軌跡的矩陣數(shù)據(jù)時(shí)，軌跡上的取點(diǎn)數(shù)m多于它的屬性個(gè)數(shù)v；因此將原用戶軌跡矩陣全部做轉(zhuǎn)置處理：

y＝a₁x₁+a₂x₂+…a_nx_n

x_i(i＝1，2…n)為轉(zhuǎn)置后的軌跡矩陣t的表示；

(3)每個(gè)矩陣有n個(gè)屬性，每個(gè)屬性的取值范圍不同，對(duì)軌跡矩陣做歸一化處理；

(4)軌跡間的稀疏表示：

y＝a₁x₁++a₂x₂+…+a_nx_n

y為需要測(cè)試的軌跡樣本，x_i(i＝1，2…n)為訓(xùn)練的軌跡樣本，a_i可理解為第i個(gè)訓(xùn)練樣本對(duì)測(cè)試樣本的貢獻(xiàn)值，將以上公式改寫(xiě)為：

y＝XA

其中A＝[a₁?…?a_n]^T，X＝[x₁?…?x_n]，并且x₁?…?x_n和y都是n*m的矩陣(m＞n)；如果A是一個(gè)非奇異矩陣，可以這樣得到A，

A＝X^-1y

否則，便這樣得到A，

A＝(X^TX+μI)^-1X^Ty

其中μ是一個(gè)很小的正數(shù)，I是一個(gè)單位矩陣；得到A之后，也即是求得了對(duì)應(yīng)的a₁?…?a_n各個(gè)系數(shù)的解，得到了第i個(gè)訓(xùn)練樣本對(duì)測(cè)試樣本的貢獻(xiàn)值，這個(gè)值越大，也就間接說(shuō)明了訓(xùn)練樣本和測(cè)試樣本相似度越高；

(5)Fréchet距離求解軌跡直接相似度sim2

任選軌跡集中；兩條軌跡P和Q，P軌跡長(zhǎng)度為M，Q軌跡長(zhǎng)度為N，將變量t約束到區(qū)間[0，1]內(nèi)，α(t)和β(t)是運(yùn)動(dòng)位置描述函數(shù)；那么有α(0)＝0，α(1)＝N，β(0)＝0，β(0)＝M；用P(α(t))和Q(β(t))分別表示t時(shí)刻P和Q在各自軌跡上的空間位置：

采用合適的離散弗雷歇距離算法來(lái)刻畫(huà)兩條曲線之間的距離，并作為其弗雷歇距離；

(6)基于多相似度融合的軌跡聚類：

通過(guò)以上相似度計(jì)算方法，需要測(cè)試的每條軌跡都可以得到相應(yīng)的前Top-k條軌跡：

每次迭代從未聚類的軌跡集合(S_unclu)中隨機(jī)選擇一條軌跡作為聚類中心軌跡T_p，根據(jù)軌跡間的相似度從S_unclu中選出與T_p相似度較高的k-1條軌跡組成一個(gè)大小為k的軌跡集合S_now，并將其添加到聚類集合S_clu中，重復(fù)上述聚類操作直到S_unclu中軌跡數(shù)(S_unclu)不足k，即無(wú)法達(dá)到k聚類的條件為止。

2.根據(jù)權(quán)利要求1所述的一種基于稀疏表示和Fréchet距離融合的軌跡相似度計(jì)算方法，其特征是：步驟(5)所述采用合適的離散弗雷歇距離算法來(lái)刻畫(huà)兩條曲線之間的距離，并作為其弗雷歇距離，其實(shí)施過(guò)程如下：

1)待識(shí)別軌跡P可表示為

P＝{P(1)，P(2)，…，P(m)…，P(M)}

式中：P(m)＝(x_m，y_m)；m為軌跡P上的采樣點(diǎn)的序號(hào)，m＝1為起始采樣點(diǎn)，m＝M為末尾采樣點(diǎn)；x_m為第m個(gè)采樣點(diǎn)的橫坐標(biāo)，y_m為第m個(gè)采樣點(diǎn)的縱坐標(biāo)；橫坐標(biāo)表示的是軌跡采樣點(diǎn)的經(jīng)度，縱坐標(biāo)表示的是軌跡點(diǎn)的緯度；

2)待識(shí)別軌跡Q可表示為

Q＝{Q(1)，Q(2)，…，Q(n)…，Q(N)}

式中：Q(n)＝(x′_n，y′_n)；n為軌跡Q上的采樣點(diǎn)的序號(hào)，n＝1為起始采樣點(diǎn)，n＝N為末尾采樣點(diǎn)；x′_n為第n個(gè)采樣點(diǎn)的橫坐標(biāo)，y′_n為第n個(gè)采樣點(diǎn)的縱坐標(biāo)‘橫坐標(biāo)表示的是軌跡采樣點(diǎn)的經(jīng)度，縱坐標(biāo)表示的是軌跡點(diǎn)的緯度；

3)計(jì)算軌跡P上各采樣點(diǎn)到軌跡Q上的各采樣點(diǎn)之間的距離，得到距離矩陣D

式中：表示軌跡Q上的第n個(gè)采樣點(diǎn)到軌跡P上的第m個(gè)采樣點(diǎn)的距離，1≤m≤M，1≤n≤N；

4)找出距離矩陣D中的最大距離d_max＝max(D)以及最小距離d_min＝min(D)，初始化目標(biāo)距離f＝d_min，并設(shè)置循環(huán)間隔

5)將距離矩陣D中小于或等于f的元素設(shè)置為1，大于f的元素設(shè)置為0，從而得到二值矩陣D′如下：

式中：

6)在二值矩陣D′中搜索一條滿足以下條件的路徑R：R的起點(diǎn)為d′₁₁，終點(diǎn)為d′_MN；路徑在通過(guò)點(diǎn)d′_mn后，其下一個(gè)通過(guò)點(diǎn)只能為d′_(m+1)n，d′_m(n+1)，d＇_(m+1)(n+1)中的一個(gè)；路徑R中所有點(diǎn)的值都必須為1；用數(shù)學(xué)表達(dá)式的形式為，存在一條路徑R＝{d′₁₁，…，d′_mn，…，d′_MN}，滿足

d′₁₁*…*d′_mn*d′_(m+k)(n+k)*…*d′_MN＝1

式中：1≤m≤M，1≤n≤N，1≤m+k≤M，1≤n+k≤N，k＝{0，1}，k′＝{0，1}.

7)若在步驟6)中未找到滿足條件的路徑，則設(shè)置目標(biāo)距離f＝f+r，之后重復(fù)步驟5)和6)；若在步驟6)中找到滿足條件的路徑或者目標(biāo)距離f＝d_max，則進(jìn)入下一步；

8)待識(shí)別軌跡P和待識(shí)別軌跡Q之間的弗雷歇距離F＝f；

9)通過(guò)弗雷歇距離可以得到兩條軌跡點(diǎn)集之間的距離，距離越小，說(shuō)明兩條估計(jì)之間的相似度越高；距離越大，說(shuō)明兩條軌跡之間的相似程度越低，因此，對(duì)相似度S的定義如下：

式中：F為兩條軌跡之間的弗雷歇距離。