[發明專利]基于泰森多邊形和K均值聚類的時空頻繁模式挖掘方法

在審

• 申請號: 202110591189.6
• 申請日: 2021-05-28
• 公開（公告）號: CN113344052A
• 公開（公告）日: 2021-09-03
• 發明（設計）人: 付曉;王大中;李琳華;楊晨;張奇
• 申請（專利權）人: 東南大學
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06N5/02
• 代理公司: 南京經緯專利商標代理有限公司 32200
• 代理人: 羅運紅

本發明公開了基于泰森多邊形和K均值聚類的時空頻繁模式挖掘方法，包括：在研究區域構建泰森多邊形，利用希爾伯特分形曲線對泰森多邊形內每一個多邊形進行編號；獲取研究區域內每個移動對象的位置信息，對數據集內對應的經緯度坐標轉換到泰森多邊形所在的坐標系；將移動對象的出行軌跡由時空立方體中的曲線轉換成新時空空間中的點；利用K?Means聚類對新時空空間中的點進行聚類；取聚類后每一類空間特征值表示該類頻繁模式，將聚類后的結果還原到三維空間。本發明利用泰森多邊形對研究區域進行描述，避免稀疏地方發生數據冗余的問題，對移動行為發生密集的地方給出更精確描述；為研究群體出行需求、出行推薦、交通規劃及管理提高重要參考價值。

技術領域

本發明涉及數據挖掘技術，特別涉及基于泰森多邊形和K均值聚類的時空頻繁模式挖掘方法。

背景技術

隨著地理信息采集設備快速發展，道路上移動對象的位置信息越來越豐富，數據量也越來越大。時空頻繁模式是在具有時空屬性的數據集中頻繁出現的模式，出行的起訖位置及發生時間直接體現了移動對象的出行需求和時間分布規律，出行模式挖掘的應用方向非常廣泛，為研究群體出行需求、出行推薦以及交通規劃與管理等問題提供重要參考。

傳統的行為模式挖掘技術多基于規則格網或交通小區進行研究，規則格網存在尺度不能很好適應移動對象行為的分布，存在大量數據冗余、位置精細程度不夠的問題；交通小區受路網、人口密度以及經濟發展等因素限制，使挖掘結果復雜。

發明內容

發明目的：針對以上問題，本發明目的是提供基于泰森多邊形和K均值聚類的時空頻繁模式挖掘方法。

技術方案：本發明的基于泰森多邊形和K均值聚類的時空頻繁模式挖掘方法，包括：

(1)根據研究區域內興趣點分布情況，在研究區域構建泰森多邊形，所述興趣點為研究區域對應的地名，利用希爾伯特分形曲線對泰森多邊形內每一個多邊形進行編號；

(2)獲取研究區域內每個移動對象的位置信息，將位置信息組成數據集，對數據集內有效數據對應的經緯度坐標轉換到泰森多邊形所在的坐標系，包括時間和空間兩個維度；

(3)對有效數據在時間和空間兩個維度進行數據預處理，將移動對象的出行軌跡由時空立方體中的曲線轉換成新時空空間中的點；

(4)利用K-Means聚類對步驟(3)新時空空間中的點進行聚類；

(5)取聚類后每一類空間特征值表示該類頻繁模式，將聚類后的結果還原到三維空間，包括位置信息和時間信息，在矢量地圖中進行可視化展示。

進一步，所述步驟1進行編號包括：

(11)計算泰森多邊形中每個多邊形的面積，以最小面積等面積建立正方形，將泰森多邊形劃分成網格；

(12)對每個正方形進行編號，將正方形的邊長設置為希爾伯特分形曲線的邊長，保證遵照分形曲線產生規則時能夠遍歷到泰森多邊形中每一個多邊形；

(13)每個多邊形按照覆蓋正方形所對應編號對每個多邊形編號，當覆蓋一個正方形時，多邊形編號為所覆蓋正方形編號，當覆蓋多個正方形時，多邊形編號為中間位置正方形編號。

進一步，建立坐標系，以研究區域的經度、緯度為x、y軸，以移動對象移動發生時間為z軸，所述步驟2中位置信息包括移動對象的起點經度Start_x、起點緯度Start_y、終點經度Stop_x、終點緯度Stop_y、開始時間Start_Time、結束時間Stop_Time，每個移動對象位置信息對應唯一的編號；所述數據集包括有效數據和無效數據，所述無效數據為位置信息內所有數據重復或起訖點經緯度未發生變化，除去無效數據剩下都為有效數據。

進一步，所述步驟3數據預處理包括：