[發明專利]一種基于FP-樹的時空數據挖掘分析方法

在審

• 申請號: 201810877226.8
• 申請日: 2018-08-03
• 公開（公告）號: CN109344150A
• 公開（公告）日: 2019-02-15
• 發明（設計）人: 宋耀蓮;田榆杰;龍華;王慧東;徐文林;武雙新
• 申請（專利權）人: 昆明理工大學
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/2458
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明涉及一種基于FP?樹的時空數據挖掘分析方法，屬于時空數據挖掘技術領域。先建立一個時空數據信息記錄的數據庫，并對數據進行轉換處理后生成新的事務表；對事務表進行第一次掃描，計算并保留頻繁項；然后，對事務表進行第二次掃描，構建頻繁模式樹FP?樹，并提取出頻繁3?項集；其次，由各頻繁3?項集產生相應的強時空關聯規則，并計算出各強時空關聯規則的置信度大小；最后，將強時空關聯規則按照其置信度的大小進行排序，生成時空關聯規則表。本發明與現有技術相比，主要將單維度的FP?樹算法擴展到了三維時空數據的關聯規則分析中，從而對數據間的關聯關系起到了更加精準、深層次的分析作用。

技術領域

本發明涉及一種基于FP-樹的時空數據挖掘分析方法，屬于時空數據挖掘技術領域。

背景技術

FP-樹算法是韓家煒等人在2000年提出的關聯分析算法，它采取如下分治策略：將提供頻繁項集的數據庫壓縮到一棵頻繁模式樹(FP-樹)，但仍保留項集關聯信息。在算法中使用了一種稱為頻繁模式樹(Frequent Pattern Tree)的數據結構。FP-樹是一種特殊的前綴樹，由頻繁項頭表和項前綴樹構成。

FP-樹算法基于以上的結構加快整個挖掘過程，而且算法已經被廣泛的應用到商業、網絡安全等各個領域。但原始FP-樹算法僅能應用到單維度數據領域，無法對時空類的三維數據進行準確的挖掘分析。

發明內容

本發明要解決的技術問題是提供一種基于FP-樹的時空數據挖掘分析方法，將單維度的FP-樹算法擴展到了三維時空數據的關聯規則分析中，從而對數據間的關聯關系起到了更加精準、深層次的分析作用。

本發明的技術方案是：一種基于FP-樹的時空數據挖掘分析方法，包括如下步驟：

Step1、建立一個時空數據信息記錄的數據庫，并對數據進行轉換處理后生成新的事務表，表中主要包括以下字段：事務編號ID、空間謂詞、屬性值、時間值；

Step2、設置最小支持度閾值min_sup和最小置信度閾值min_conf，對事務表進行第一次掃描，去除掉事務表中所有支持度計數support_count_x小于最小支持度閾值的數據項，記錄剩余數據項的支持度計數并按降序排序，生成頻繁1-項集的新事務表；

Step3、對新事務表進行第二次掃描，初始化FP-樹。以字符null做為根節點，按照新事務表順序依次插入每條事務的數據項作為節點，生成對應的分支路徑同時建立項頭表。項頭表中，在加入數據項節點時需統計其出現的次數，形式為(X_i,N)，X_i為第i個數據項，N為出現的次數；

Step4、從FP-樹的每條路徑的結尾節點依次向上提取出相應的3-項集，3-項集的支持度計數support_count_xj大于等于min_sup時，該3-項集作為頻繁3-項集l保留，反之剔除；

Step5、設每個頻繁3-項集l中的空間謂詞為子集s，若屬性值與時間值的集合(l-s)與s的支持度計數之比大于等于最小置信度閾值min_conf，則輸出強時空關聯規則該強規則的置信度大小為l與s的支持度計數之比的值將所計算出來的所有強時空關聯規則按照其置信度confidence的大小進行排序，生成時空關聯規則表；

Step6、將時空關聯規則表結合實驗數據的背景知識，對該結果進行相應的意義分析、比較。

具體地，所述步驟Step1中，收集到的時空數據包括名稱、屬性值、地址和發生時間，對其進行數據的轉換處理，以使得數據可以更好的進行計算，主要包括以下幾個步驟：

(1)對收集的數據進行預處理，過濾掉不相關的冗余數據，包括不在研究目標時間與空間范圍內的數據；

(2)對空間數據進行形式化處理，按各對象與某一目標對象的空間距離關系來對各個對象數據賦予相應的空間謂詞；