[發(fā)明專利]一種基于改進circle-based算法的路徑相似度計算方法

在審

• 申請?zhí)枺?/td>: 201811050203.6
• 申請日: 2018-09-10
• 公開（公告）號: CN109102129A
• 公開（公告）日: 2018-12-28
• 發(fā)明（設(shè)計）人: 邢建川;張易豐;丁志新;康亮;雷瞻遙
• 申請（專利權(quán)）人: 電子科技大學(xué)
• 主分類號: G06Q10/04
• 分類號: G06Q10/04
• 代理公司: 電子科技大學(xué)專利中心 51203
• 代理人: 周劉英

本發(fā)明提出了一種基于改進circle?based算法的路徑相似度計算方法，可以提高路徑相似度計算的精度。此方法主要包括以下步驟：步驟1：采集獲得基準路徑和待匹配路徑；步驟2：分別提取所述基準路徑和待匹配路徑中的路徑點，并作出一系列圓；步驟3：計算所述待匹配路徑中的路徑點落入所述基準路徑中每一個特征點所構(gòu)建的圓形區(qū)域內(nèi)以及落入這些圓形區(qū)域構(gòu)成的盲點區(qū)域的點的總個數(shù)；步驟4：通過步驟3中點的總個數(shù)與待匹配路徑上提取的路徑點總個數(shù)的比值計算路徑相似度。該方法能夠消除Circle?based算法存在的盲點區(qū)域，從而提高匹配算法的精確度。

技術(shù)領(lǐng)域

本發(fā)明屬于數(shù)據(jù)分析領(lǐng)域，具體的說是涉及一種基于改進circle-based算法的路徑相似度計算方法。

背景技術(shù)

現(xiàn)如今，隨著社會的飛速發(fā)展，擁有私家車的家庭越來越多。隨著私家車數(shù)量的急速上升，各大城市無不面臨著交通擁擠帶來的危害。例如交通擁擠為出行人們不但增加了出行的時間成本，同時造成了環(huán)境上的污染以及資源的浪費。在本方案中通過對車輛的出行路線研究發(fā)現(xiàn)，每個人每天的出行路線都具有一定的規(guī)律性以及重復(fù)性。可以通過對用戶間的路徑進行相似度的計算，為用戶之間提供服務(wù)，例如拼車服務(wù)。

通過對傳統(tǒng)的計算相似度算法Circle-based算法進行研究分析，發(fā)現(xiàn)傳統(tǒng)的Circle-ba sed算法構(gòu)建的圓形區(qū)域存在盲點區(qū)域，該盲點區(qū)域的存在會影響計算的精度。

發(fā)明內(nèi)容

鑒于己有技術(shù)存在的缺陷，本發(fā)明在原算法構(gòu)建的圓形區(qū)域的基礎(chǔ)上引入一種三角形面積對比法，目的是提供一種基于三角形面積對比的方法消除Circle-based算法存在的盲點區(qū)域，從而提高匹配算法的精確度。

為了實現(xiàn)上述目的，本發(fā)明采用如下技術(shù)方案：

一種基于改進circle-based算法的路徑相似度計算方法，其特征在于，包括如下步驟：

步驟1、采集獲得基準路徑和待匹配路徑；

步驟2、分別提取所述基準路徑和待匹配路徑中的路徑點，并依據(jù)Circle‐based算法分別以所述基準路徑中的每一個路徑點為圓心作出一系列圓；

步驟3、計算所述待匹配路徑中的路徑點落入所述基準路徑中每一個特征點所構(gòu)建的圓形區(qū)域內(nèi)以及落入這些圓形區(qū)域構(gòu)成的盲點區(qū)域的點的總個數(shù)。

步驟4、通過所述待匹配路徑中的路徑點落入基準路徑中每一個特征點所構(gòu)建的圓形區(qū)域內(nèi)以及落入這些圓形區(qū)域構(gòu)成的盲點區(qū)域的點的總個數(shù)與待匹配路徑上提取的路徑點總個數(shù)的比值計算路徑相似度。

所述步驟2中，提取所述基準路徑和待匹配路徑中的路徑點的方法為，分別從基準路徑和待匹配路徑的起點開始，以時間間隔T周期性地采集路徑點，其中，時間間隔T優(yōu)選取值為1秒。

所述步驟2中，圓的半徑計算方法為，對于基準路徑中采集的每個路徑點，計算該路徑點與基準路徑中相鄰兩個路徑點之間的距離，并選取其中較大的距離的一半作為以該路徑點為圓心作出的圓的半徑的預(yù)設(shè)值。