[發明專利]一種出租車載客軌跡聚類算法Tr?OPTICS

在審

• 申請號: 201710591987.2
• 申請日: 2017-07-19
• 公開（公告）號: CN107392245A
• 公開（公告）日: 2017-11-24
• 發明（設計）人: 畢碩本;周浩;楊樹亮;凌德泉;那澤
• 申請（專利權）人: 南京信息工程大學
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06Q50/30;G01S19/42
• 代理公司: 南京瑞弘專利商標事務所(普通合伙)32249
• 代理人: 徐激波

1.一種出租車載客軌跡聚類算法Tr-OPTICS，其特征在于：具體包括如下步驟：

第一步：

一、指定載客軌跡數據集D，并且設置聚類參數ε和最小包含軌跡數目MinPts的閾值；

二、建立兩個集合：有序隊列集合S，用來臨時存儲核心載客軌跡對象及其鄰域內直接密度可達軌跡對象；結果隊列集合O，用來存儲樣本軌跡及處理次序的結果；

第二步：

如果集合D中的數據全部處理完，則算法結束；

如果未全部處理完，則從D中選擇一個核心軌跡對象，為該核心軌跡對象建立鄰接表，并且將該核心軌跡對象放入結果隊列集合O中，其直接密度可達軌跡放入有序隊列集合S中，并按可達距離升序排列；

第三步：

如果有序隊列集合S為空，則回到第二步；

如果有序隊列集合S不為空，則從有序隊列集合中取出第一個軌跡對象TR₁：

一、如果TR₁不是核心軌跡，則回到第二步；

二、如果TR₁是核心軌跡，則將TR₁放入結果隊列集合O中，并且找到其所有的直接密度可達軌跡對象TR₁-TR_n，將這些軌跡放入有序隊列S集合中按照可達距離重新排序；

如果TR₁-TR_n有已經在有序隊列集合中且新的可達距離比原來的值小，則更新該軌跡的可達距離；

三、重復第三步，直至有序隊列集合S為空；

第四步：算法結束，輸出結果隊列集合O。

2.根據權利要求1所述的一種出租車載客軌跡聚類算法Tr-OPTICS，其特征在于：所述算法采用軌跡的外包矩形作為核心軌跡對象的搜索鄰域，在聚類過程中，可達距離越小代表空間密度越大，算法中用一個可達距離升序排列的種子序列來儲存待擴張的子軌跡，通過搜索鄰域依次向空間稠密的方向擴張。

3.根據權利要求1所述的一種出租車載客軌跡聚類算法Tr-OPTICS，其特征在于：所述算法研究對象為載客軌跡，核心距離與可達距離是載客軌跡線段之間的軌跡距離；

設定Tr₁和Tr₂分別為參與距離計算的兩條載客子軌跡；點P_i1'與點P_i2'分別是點P_i1和點P_i2在子軌跡Tr₂上的投影點，θ是兩條子軌跡之間的夾角；

子軌跡Tr₁和Tr₂之間的軌跡距離為：d(Tr₁,Tr₂)＝d_水平+d_垂直+d_角度；其中水平距離、垂直距離、角度距離的定義如下：

水平距離：是指P_j1和P_j2分別到點P_i1和點P_i2在子軌跡Tr₂上的投影點的距離的平均值；

垂直距離：是指點P_i1和點P_i2分別到子軌跡Tr₂的垂直距離的平均值；

角度距離：θ為子軌跡Tr₁和Tr₂之間的夾角，|Tr₁|為子軌跡Tr₁的長度；當角度大于0小于90度時，角度距離為較短子軌跡長度乘以夾角的正弦值；當角度大于90度小于180度時，角度距離即為較長子軌跡的長度；

聚類算法中軌跡的核心距離與可達距離概念定義為：

軌跡核心距離：對于一條載客軌跡Tr₁，其軌跡核心距離就是使Tr₁成為核心軌跡的最小鄰域值ε；若Tr₁不是核心軌跡，則軌跡核心距離為空；

軌跡可達距離：一條載客軌跡Tr₁關于另一條載客軌跡Tr₂的軌跡可達距離為Tr₁的軌跡核心距離ε與Tr₁和Tr₂間軌跡距離d(Tr₁,Tr₂)之間的較大值。