[發明專利]頻繁co-location模式的無損壓縮方法

有效

• 申請號: 201710430303.0
• 申請日: 2017-06-09
• 公開（公告）號: CN107291854B
• 公開（公告）日: 2018-10-19
• 發明（設計）人: 王麗珍;陳紅梅;肖清;包旭光
• 申請（專利權）人: 云南大學
• 主分類號: G06F17/30
• 分類號: G06F17/30;H03M7/30
• 代理公司: 北京科億知識產權代理事務所(普通合伙) 11350
• 代理人: 湯東鳳

1.頻繁co-location模式的無損壓縮方法，其特征在于，首先定義SPI-閉co-location模式：

定義1.對于兩個給定的co-location模式c和c′且c在c′中的超參與度SPI(c|c')被定義為通過c'的表實例計算得到的c中所有特征參與率的最小值，即：SPI(c|c')＝min{PR(c',f_i),f_i∈c}；

定義2.一個co-location模式c是SPI-閉co-location模式，當且僅當c的PI值大于c在它所有SPI-閉的超模式c'中的SPI值，即：當且僅當c'是SPI-閉co-location模式，同時PI(c)>SPI(c|c')→c是一個SPI-閉co-location模式；

定義3.若一個SPI-閉co-location模式c是SPI-閉頻繁co-location模式，當且僅當c是SPI-閉的且PI(c)≥M，其中M表示的是用戶指定的頻繁性閾值；而對于一個co-location模式c，如果存在一個co-location模式c'使得且PI(c)＝SPI(c|c')，那么稱“c'SPI-覆蓋c”，如果存在一個co-location模式c'使得且PI(c)＝PI(c')，稱“c'PI-覆蓋c”；

然后，按照以下步驟進行：

步驟1，預處理輸入數據：生成鄰居事務集NT和特征鄰居事務集ENT；

步驟2，使用字典序前綴樹結構來存儲特征鄰居事務集ENT，基于特征鄰居事務集的前綴樹結構，生成星型SPI-閉候選模式，組合星型SPI-閉候選模式生成團SPI-閉候選模式；

步驟3，生成了團SPI-閉候選模式之后，通過掃描鄰居事務集NT，得到候選模式的候選表實例，再通過檢測其它實例的鄰近關系，得到真正符合團關系的表實例；基于表實例計算模式的參與度PI，同時通過以下方法判定一個模式是否是SPI-閉co-location模式：

對于k階候選模式c，若PI(c)＝UPI(c)，那么c一定是SPI-閉co-location模式，UPI為上界參與度；否則，就需要先生成模式c的所有k-1階被剪枝的子模式作為候選，接下來，若PI(c)<M，那么c就被剪枝掉；如若大于等于M，則需要根據定義2和定義3來判定c是否是一個SPI-閉co-location模式。

2.根據權利要求1所述的頻繁co-location模式的無損壓縮方法，其特征在于，所述步驟1中，預處理輸入數據具體過程為：使用給定的鄰近距離閾值處理輸入數據集，得到所有的鄰近實例對，通過分組鄰近實例對，生成鄰居事務集NT，然后，根據鄰居事務集NT生成特征鄰居事務集ENT；S表示空間特征實例的集合，對于一個空間特征實例f.i∈S，它的鄰居事務集NT是一個包含f.i和所有與f.i具有鄰近關系的其它空間特征實例的集合，也就是NT(f.i)＝{f.i,g.j∈S|NR(f.i,g.j)＝true and f≠g}，其中NR表示空間實例之間的鄰近關系，g.j表示特征g的第j個實例，f.i被稱為參考實例，所有實例的鄰居事務集的集合稱為空間數據的鄰居事務集，記為NT；鄰居事務集NT中不同空間特征的字典序集，稱為特征鄰居事務集ENT。

3.根據權利要求1所述的頻繁co-location模式的無損壓縮方法，其特征在于，所述步驟2使用字典序前綴樹結構來存儲特征鄰居事務集ENT的具體過程為：

步驟1.定義字典序前綴樹；以參考實例的特征類型為根節點，以特征鄰居事務集中鄰居特征為子節點；每個子節點由三部分內容構成：特征類型，計數值和節點連線；其中，特征類型用來標識節點；計數值代表在整個特征事務集中有幾條路徑可從參考實例的特征類型到達該特征類型；節點連線連接的是在這棵樹中與該節點擁有相同特征類型的節點；

步驟2.由于在字典序前綴樹中，所有的子節點都與根節點具有鄰近關系，所以生成星型SPI-閉候選co-location模式；而且通過字典序前綴樹，還得到此星型SPI-閉co-location模式的參與率上界值；若在同一棵樹中，某個候選的上界參與率等于它的超候選的上界參與率，那么，就標紅這個星型候選；但若某個候選的上界參與率小于閾值M，那么就把它刪除掉；

步驟3，通過組合k個相關星型SPI-閉co-location候選模式，生成k階團SPI-閉co-location候選模式，且這k個星型候選中最小的上界參與率便是k階團SPI-閉co-location候選模式的上界參與度值。