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

有效

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

本發明公開了頻繁co?location模式的無損壓縮方法，首先預處理輸入數據，使用字典序前綴樹結構來存儲特征鄰居事務集，基于特征鄰居事務集的前綴樹結構，生成星型SPI?閉候選模式，組合星型SPI?閉候選模式生成團SPI?閉候選模式；生成了團SPI?閉候選模式之后，通過掃描鄰居事務集NT，可以得到候選模式的候選表實例，再通過檢測其它實例的鄰近關系，可以得到真正符合團關系的表實例；基于表實例可以計算模式的參與度PI，同時可以判定一個模式是否是SPI?閉co?location模式。該方法提供了頻繁co?location模式集的更小的、不丟失參與度信息的壓縮表示。

技術領域

本發明屬于空間co-location(并置)模式挖掘技術領域，特別是涉及一種頻繁co-location(并置)模式的無損壓縮方法。

背景技術

空間co-location模式挖掘(mining prevalent co-location patterns fromspatial data sets)用于識別傳統地理空間數據集中頻繁地緊密相鄰出現的空間特征組。如圖1是一個空間數據集的例子。圖中以不同的圖標表示不同的空間特征，如房子。圖中共有5個特征，每個特征有4個空間實例。從圖中可以觀察到，空間特征枯樹和山火以及房子和鳥的實例趨于頻繁地緊密相鄰出現。這兩個模式暗示著“山火頻繁與枯樹太多有關”，而“房子與鳥的頻繁出現，說明人居環境得到了改善”。

空間co-location模式挖掘的應用包括找出生活(或生長)空間相互重疊的動(或植)物、識別特定人群經常聚集的地段以便有目的地放置特定廣告、理解地球氣候系統不同元素之間的聯系等。

由于此研究領域具有較高的理論研究與實際應用價值，國內外許多研究者提出了各種空間co-location模式挖掘算法。與從事務數據庫中挖掘頻繁項集類似，從大型空間數據庫中挖掘頻繁co-location模式集的主要挑戰是這種挖掘常常產生大量滿足最小頻繁性閾值M的空間co-location模式，當M設得很低時尤其如此。這是因為如果一個co-location模式是頻繁的，則他的所有子集也是頻繁的。為此，現有技術(J.S.Yoo and M.Bow.Miningtop-k closed co-location patterns[C].In Proceedings of IEEE InternationalConference on Spatial Data Mining and Geographical Knowledge Services(ICSDM),pp.100-105,2011.記為文獻2)提出了一種TOP-k閉co-location模式概念和相應的挖掘算法，在該文獻中，閉co-location模式的概念是：一個co-location模式c是閉的，當且僅當它的參與度值均大于它的任何超模式的參與度值，即：TOP-k閉co-location模式的概念是：設L是按參與度值降序排列的所有閉co-location模式的列表，p是列表L中第k個閉co-location模式的參與度，TOP-k閉co-location模式是指所有參與度值大于等于p的閉co-location模式的集合。TOP-k閉co-location模式挖掘的方法是：首先，把輸入數據組織成實例鄰居事務集和特征鄰居事務集。鄰居事務集的優點在于：1、它不會丟失任何具有鄰近關系的實例對；2、它易建成；3、由它可方便地產生候選co-location模式；4、它可以給出co-location模式參與度的上界值。其次，使用類FP-tree結構來存儲具有鄰近關系的空間特征，從而可以得到星型鄰居候選模式。然后，通過組合相關星型鄰居候選模式，可以得到候選co-location模式和候選模式參與度的上界值。接下來，利用內部最小頻繁性閾值θ可以定義一個剪枝框架，從而減少搜索空間中候選模式的數量。這個剪枝框架的基本思想是：設定當前top-k結果集中最小的參與度值為內部最小頻繁性閾值θ，如果下一個候選的參與度的上界值小于θ，則它及它所有的超集均可以剪枝。再然后，對于不能剪枝的候選模式，利用實例鄰居事務集獲得候選模式的表實例，從而可以計算候選模式的真實參與度值。最后，利用折半查找的方法在top-k有序結果集中對比co-location模式的參與度值，從而得到最終的top-k閉模式集。