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

在審

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

1.基于泰森多邊形和K均值聚類的時空頻繁模式挖掘方法，其特征在于，包括：

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

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

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

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

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

2.根據權利要求1所述的時空頻繁模式挖掘方法，其特征在于，所述步驟1編號包括：

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

(12)對每個正方形進行編號，將正方形的邊長設置為希爾伯特分形曲線的邊長；

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

3.根據權利要求2所述的時空頻繁模式挖掘方法，其特征在于，建立坐標系，以研究區域的經度、緯度分別為x軸和y軸，以移動對象移動發生時間為z軸，所述步驟2中位置信息包括移動對象的起點經度Start_x、起點緯度Start_y、終點經度Stop_x、終點緯度Stop_y、開始時間Start_Time、結束時間Stop_Time，每個移動對象位置信息對應唯一的編號；所述數據集包括有效數據和無效數據，所述無效數據為位置信息內所有數據重復或起訖點經緯度未發生變化，除去無效數據剩下都為有效數據。

4.根據權利要求3所述的時空頻繁模式挖掘方法，其特征在于，所述步驟3數據預處理包括：

(31)對有效數據空間維度屬性進行變換，用函數將每個有效數據的經緯度轉換成所在泰森多邊形編號值，表達式為：

Start_ID＝Thiessen(Start_x,Start_y)

Stop_ID＝Thiessen(Stop_x,Stop_y)

Thiessen()為轉換函數，Start_ID和Stop_ID分別為起訖點坐標對經過Thiessen()函數轉換后得到的起訖點對應一維值，將Start_ID和Stop_ID作為空間特征值；

(32)對有效數據時間維度屬性進行變換：每個有效數據持續時間為[Start_Time,Stop_Time]，取時間段中間值Act_Time作為變換后時間特征值，表達式為：

(33)將時間維度和空間維度數據分別進行歸一化處理，表達式為：

Normal_V alue為歸一化處理后得到的新值，Normal_V alue包括Normal_Time，Value為歸一化處理前時間或空間維度的數據值，Max和Min分別為與Value同一維度下數據集中的最大值和最小值；

(34)構建新時間變量New_Time，表達式為：

New_Time＝σ*Normal_Time

Normal_Time為時間變量歸一化處理后得到的值，σ為時間特征模式描述能力與空間特征模式描述能力之比，σ的取值與有效數據空間、時間特征有關，如當數據的時間屬性呈現某時間段內的聚集特征，應將時間屬性適當拉伸，σ＞1；當數據的空間屬性呈現空間上的分散特征，應將數據的空間屬性適當壓縮，σ＜1；

(35)將所有移動對象的出行軌跡轉換為新時空空間的點，坐標為(Start_ID,Stop_ID,New_Time)。