[發(fā)明專利]一種基于行車軌跡的改進(jìn)型GeoHash道路聚類方法

有效

• 申請?zhí)枺?/td>: 201910764610.1
• 申請日: 2019-08-19
• 公開（公告）號: CN110688436B
• 公開（公告）日: 2021-06-08
• 發(fā)明（設(shè)計(jì)）人: 張沛;劉科
• 申請（專利權(quán)）人: 成都海天數(shù)聯(lián)科技有限公司
• 主分類號: G06F16/29
• 分類號: G06F16/29;G06F16/906
• 代理公司: 北京天奇智新知識產(chǎn)權(quán)代理有限公司 11340
• 代理人: 楊春

1.一種基于行車軌跡的改進(jìn)型GeoHash道路聚類方法，其特征在于，包括以下步驟：

S1，由隨車采集的道路經(jīng)度、緯度及時間信息通過Hash運(yùn)算和base64編碼得到樣本集D；

S2，向服務(wù)端輸入樣本集、領(lǐng)域參數(shù)(hash,MinPts)，領(lǐng)域參數(shù)(hash,MinPts)描述領(lǐng)域的樣本分布緊密程度，其中hash描述了某一樣本的所處區(qū)域的hash值，MinPts描述了某一樣本在所處hash區(qū)域內(nèi)的樣本個數(shù)閾值；

設(shè)置樣本距離度量方式，服務(wù)端進(jìn)行第一次初始化設(shè)置：核心對象集合Ω為空集，未訪問樣本集合Γ＝D，簇劃分C為空集；

S3，遍歷樣本集中的所有點(diǎn)，找出其中的噪聲點(diǎn)和非噪聲點(diǎn)，若樣本集中的所有點(diǎn)均為噪聲點(diǎn)，則結(jié)束流程，若存在非噪聲點(diǎn)則進(jìn)行S4；

S4，樣本集中的所有非噪聲點(diǎn)集中為核心對象集Ω，服務(wù)端進(jìn)行第二次初始化設(shè)置：于Ω中隨機(jī)抽取核心對象O加入到簇核心對象隊(duì)列Ω_cur，且將O加入簇樣本集合C_k，將O從Γ中移除；

S5，遍歷Ω_cur中的所有點(diǎn)，找出其中的非噪聲點(diǎn)，服務(wù)端進(jìn)行第三次初始化設(shè)置：將Ω_cur的非噪聲點(diǎn)加入C_k，并將Ω_cur的非噪聲點(diǎn)從Γ中移除，將Ω_cur的非噪聲點(diǎn)加入Ω_cur，并將O從Ω_cur中移除；

S6，循環(huán)進(jìn)行S5至Ω_cur為空集，將C_k更新至簇劃分C＝{C₁,C₂,...,C_k}，并將C_k從Ω移除，跳轉(zhuǎn)入S3；

S7，輸出簇劃分C＝{C₁,C₂,...,C_k}，即得主干道路區(qū)域信息。

2.根據(jù)權(quán)利要求1所述的一種基于行車軌跡的改進(jìn)型GeoHash道路聚類方法，其特征在于，隨車采集的道路經(jīng)度/緯度/時間的Hash運(yùn)算過程如下：

隨車采集的道路經(jīng)度/緯度/時間范圍(X_min,X_max)均分為前區(qū)間(X_min, (X_min+X_max)/2)和后區(qū)間((X_min+X_max)/2,X_max)，若目標(biāo)經(jīng)度/緯度/時間X位于前區(qū)間，則編碼為0，否則編碼為1；

若編碼為0，則將前區(qū)間再次均分為前后兩個區(qū)間，若目標(biāo)經(jīng)度/緯度/時間X位于再次均分后的前區(qū)間，則編碼為0，否則編碼為1；

以此種方式均分經(jīng)度/緯度/時間范圍2n次至達(dá)到精度要求，得到經(jīng)度/緯度/時間編碼。

3.根據(jù)權(quán)利要求2所述的一種基于行車軌跡的改進(jìn)型GeoHash道路聚類方法，其特征在于，將經(jīng)度/緯度/時間編碼合并后進(jìn)行Base64編碼，Base64編碼長度n與誤差關(guān)系如下：

4.根據(jù)權(quán)利要求1所述的一種基于行車軌跡的改進(jìn)型GeoHash道路聚類方法，其特征在于，遍歷集合找出非噪聲點(diǎn)的方法如下：

于集合中取對象點(diǎn)，找到對象點(diǎn)同一Hash領(lǐng)域內(nèi)的子集，若子集中的點(diǎn)個數(shù)大于及等于MinPts，則該對象點(diǎn)為 非噪聲點(diǎn)，否則為噪聲點(diǎn)。