[發明專利]基于連通度的最大頻繁項集挖掘方法

有效

• 申請號: 201611154069.5
• 申請日: 2016-12-14
• 公開（公告）號: CN108228607B
• 公開（公告）日: 2021-10-15
• 發明（設計）人: 郭鵬;孫允明
• 申請（專利權）人: 中國航空工業集團公司西安航空計算技術研究所
• 主分類號: G06F16/2458
• 分類號: G06F16/2458
• 代理公司: 中國航空專利中心 11008
• 代理人: 杜永保

隨著計算機和因特網技術的迅猛發展，從各種各樣應用中收集到的數據量越來越龐大，從海量數據中挖掘出有價值的信息和知識已經成為數據挖掘研究領域中的重要任務之一。針對當前最大頻繁項集挖掘方法挖掘效率不高的問題，提出一種基于連通度的最大頻繁項集挖掘方法，掃描事務數據庫生成有序的事務集并構造出ppc?tree、根據事務數據庫中項與項之間的連通度縮小最大頻繁項集挖掘時的搜索空間、超集檢測并生成最大頻繁項集的集合。本方法在空間復雜度不增加的情況下，有效提升最大頻繁項集的挖掘效率。

技術領域

本發明涉及一種數據挖掘方法，更特別地說，是一種基于連通度的最大頻繁項集挖掘方法

背景技術

近年來開展了最大頻繁項集挖掘的各類算法，雖然在數據組織、處理流程等方面各有不同，但主要分為兩類，如表1所示。

產生候選集的典型算法為Aprioror，該類算法以產生候選集為基礎，再通過掃描數據庫排除不滿足最小支持度的項集來搜索最大頻繁項集。

不產生候選集的算法有基于FP-tree有效挖掘最大頻繁項集的算法，該類算法主要以FP-tree、ppc-tree、poc-tree為基礎，通過結點支持列表的方法來搜索最大頻繁項集。

基于層次的典型算法有基于層次的最大頻繁項集挖掘算法，該類算法將數據庫按照大小分為不同的層次來加速搜索最大頻繁項集的過程。

表1典型最大頻繁項集挖掘算法比較

類別	產生候選集	遍歷數據庫
1	產生	多次
2	不產生	一次
3	產生	次

從上述最大頻繁項集挖掘算法的發展不難看出，最大頻繁項集的產生方式主要分為產生候選集和不產生候選集兩大類。前者主要是基于Aproior算法做出了一些改進，設法避免產生重復的候選集或者加快候選集的產生；后者主要是基于FP-tree算法做出了相關的改進。其中增加結點上保存的相關信息可以提高算法的效率，基于ppc-tree的算法增加了結點在數據庫中的前后關系，而基于poc-tree的算法則在基于ppc-tree的算法上只保留前序關系或者后序關系，減少了一半的空間代價。在最大頻繁項集挖掘算法研究不斷發展中，算法的效率是在不斷地提高，但依然有進一步提高的空間。

發明內容

1.本發明的目的：