[發明專利]基于F函數和改進KD樹的犯罪大數據點模式分析方法

在審

• 申請號: 201910203946.0
• 申請日: 2019-03-18
• 公開（公告）號: CN109960702A
• 公開（公告）日: 2019-07-02
• 發明（設計）人: 何雨情;楊立濤;白璐斌;黃舒哲
• 申請（專利權）人: 武漢大學
• 主分類號: G06F16/2458
• 分類號: G06F16/2458;G06K9/62;G06Q50/26
• 代理公司: 武漢科皓知識產權代理事務所(特殊普通合伙) 42222
• 代理人: 魏波

1.一種基于F函數和改進KD樹的犯罪大數據點模式分析方法，其特征在于，包括以下步驟：

步驟1：生成隨機點集；

輸入所有待處理的犯罪事件點，即坐標，設定每個事件點的研究區域半徑，基于每一事件點在研究區域內生成隨機點集，基于隨機點集建立KD樹；

步驟2：搜索最鄰近點；

在KD樹中搜索每個點的最鄰近隨機點，計算最鄰近隨機點到事件點之間的距離d_min，直到所有輸入的點都計算完畢，得到所有點的最鄰近距離；

步驟3：計算F函數；

將得到的所有點的最鄰近距離按照大小排序，計算最鄰近距離的變程R和組距D，其中R＝max(d_min)-min(d_min)，根據組距上限值累積計數點的數量，并計算累積頻率F(d)；

步驟4：進行顯著性檢驗并得到分析結果；

若計算結果滿足顯著性檢驗指標，輸出F(d)關于距離d的曲線圖，判斷點數據的空間分布模式；對于F函數來說，如果F函數值開始時增加得較慢，但到距離d較大時，F函數開始快速增加，則判斷點事件在空間中趨于聚集分布；如果F函數值開始時增加得較快，距離d較大時增加得較慢，則點事件在空間中趨向分散分布。

2.根據權利要求1所述的基于F函數和改進KD樹的犯罪大數據點模式分析方法，其特征在于：步驟1中所述建立KD樹，首先計算每一個簇中所有數據的每一維方差，然后選取方差最大的那一維中所有數據的中位數作為分割超面，即根結點，最后確定左子樹右子樹，遞歸進行，直到葉子結點。

3.根據權利要求1所述的基于F函數和改進KD樹的犯罪大數據點模式分析方法，其特征在于：步驟2中，采用多線程并行搜索在KD樹中搜索最鄰近點。

4.根據權利要求1所述的基于F函數和改進KD樹的犯罪大數據點模式分析方法，其特征在于：步驟3中，用最鄰近距離的累積頻率分布F(d)描述鄰近測度，通過隨機點和點事件間的分散程度來描述分布模式；

其中，d_min(p_i,S)表示從隨機選擇的p_i點到研究區域的點模式S的最鄰近距離，m表示隨機點的個數，d是距離。

5.根據權利要求1-4任意一項所述的基于F函數和改進KD樹的犯罪大數據點模式分析方法，其特征在于：步驟4中，使用蒙特卡洛隨機模擬的方法，若隨機模擬分布函數大于上界U(d)的概率和小于下界L(d)的概率符合則計算結果滿足顯著性檢驗指標。