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

在審

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

本發明公開了一種基于F函數和改進KD樹并行計算的犯罪大數據點模式分析方法，本發明針對當下犯罪大數據處理的需求，通過將改進的KD樹并行計算結合最鄰近距離點模式分析方法(F函數)提供了一種能快速地分析犯罪空間分布模式的方法——基于F函數和改進KD樹并行計算的犯罪大數據點模式分析方法。該方法將空間中的犯罪點事件分簇構建KD樹，并行計算每個KD樹中犯罪點事件的最鄰近距離，以起到化整為散，分塊并行處理的效果，加快計算效率，提高計算資源的利用率。

技術領域

本發明屬于大數據挖掘領域，涉及一種犯罪大數據點模式分析方法，具體涉及一種新型的基于F函數和改進KD樹并行計算的犯罪大數據點模式分析方法。

背景技術

隨著互聯網技術的發展，當今世界已經進入了大數據時代。大數據在形式上是海量有關聯數據的集合，在實際應用上泛指收集和分析大量信息的能力。近十幾年來，公安機關信息化建設取得了突飛猛進的進展，建立起縱向到底、橫向到邊的公安信息化網絡，各警種業務全面實現了信息化管理，積累起海量的基礎業務數據。其中，犯罪數據量大而分散、構成復雜、信息提取困難，使傳統的犯罪事件分析管理模式難堪重負，急需深刻轉型。而通過對海量數據的收集、整理、歸類、分析，可以得出傳統手段不易發現的犯罪空間分布特征，進而挖掘數據中蘊藏的巨大價值。

地理學中最為著名的空間點模式研究的例子當推Snow的霍亂地圖，該研究終止了1853年發生在倫敦的霍亂病流行。定量化地計算分析空間點分布模式自20世紀60年代計量革命時代盛行，在地學研究中被廣泛應用。例如居民點分布的研究(Dacey,1962；King,1962)和冰區內的冰丘分布(Trenhaile,1971)等。隨著地理空間信息系統技術的興起，點模式作為空間分析的重要內容，得到深入研究和廣泛應用，出現了最鄰近距離算法F函數等模型。

最鄰近距離算法F函數可以分析犯罪事件點的空間分布特征，在計算時需要求所有點事件的最鄰近點。面對如今海量的犯罪原始數據，傳統的遍歷搜索方法計算最鄰近距離時需要逐個計算中心點與范圍內所有點之間的距離，計算時間過長，資源浪費嚴重，效率低下。

發明內容

為了解決上述技術問題，本發明提供了一種新型的基于F函數和改進KD樹并行計算的犯罪大數據點模式分析方法。

本發明所采用的技術方案是：一種基于F函數和改進KD樹并行計算的犯罪大數據點模式分析方法，其特征在于，包括以下步驟：

步驟1：生成隨機點集；

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

步驟2：搜索最鄰近點；

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

步驟3：計算F函數；

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

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

使用蒙特卡洛隨機模擬的方法，若隨機模擬分布函數大于上界U(d)的概率和小于下界L(d)的概率符合則計算結果滿足顯著性檢驗指標，輸出F(d)關于距離d的曲線圖，判斷點數據的空間分布模式；對于F函數來說，如果F函數值開始時增加得較慢，但到距離d較大時，F函數開始快速增加，則判斷點事件在空間中趨于聚集分布；如果F函數值開始時增加得較快，距離d較大時增加得較慢，則點事件在空間中趨向分散分布。