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

有效

• 申請?zhí)枺?/td>: 201611154069.5
• 申請日: 2016-12-14
• 公開（公告）號: CN108228607B
• 公開（公告）日: 2021-10-15
• 發(fā)明（設(shè)計）人: 郭鵬;孫允明
• 申請（專利權(quán)）人: 中國航空工業(yè)集團(tuán)公司西安航空計算技術(shù)研究所
• 主分類號: G06F16/2458
• 分類號: G06F16/2458
• 代理公司: 中國航空專利中心 11008
• 代理人: 杜永保

1.一種基于連通度的最大頻繁項集挖掘方法，其特征在于，包含以下步驟：

步驟1：掃描事務(wù)數(shù)據(jù)庫生成有序的事務(wù)集并構(gòu)造出ppc-tree：

1)掃描一遍事務(wù)數(shù)據(jù)庫，得到事務(wù)數(shù)據(jù)庫中的每一個項的支持度，將事務(wù)數(shù)據(jù)庫中的所有項按照支持度的降序排列；然后，再將事務(wù)數(shù)據(jù)庫中的事務(wù)按照上述降序重新排列得到一個新的有序的事務(wù)集；此事務(wù)集中的每一項都按照事務(wù)數(shù)據(jù)庫中的每一項的支持度的降序排列；

2)根據(jù)得到的新的事務(wù)集構(gòu)造一棵ppc-tree來表示原有的事務(wù)數(shù)據(jù)庫，ppc-tree的每一個分支都表示了事務(wù)數(shù)據(jù)庫中的一個事務(wù)，一個分支中的父子結(jié)點則表示了其代表項的支持度的大小關(guān)系；

步驟2：根據(jù)項與項之間的連通度縮小搜索空間：

1)掃描數(shù)據(jù)庫，得到事務(wù)數(shù)據(jù)庫中的任意一項與其它項的連通度，將事務(wù)數(shù)據(jù)庫中的項按照連通度從大到小的順序排序；在最大頻繁項集搜索過程中，可以根據(jù)項的連通度確定出該項一定不能加入已知的最大頻繁項集或者該項可以加入已知的最大頻繁項集，然后再用超集檢測的方法確定加入了新項的集是否滿足最大頻繁項集的要求；

2)當(dāng)已知的最大頻繁項集R的長度為N，另一個不屬于R的項i的連通度若小于N，那么項集R∪{i}就一定不是最大頻繁項集，所以在最大頻繁項集的挖掘過程中不用考慮項集R∪{i}；

利用上述性質(zhì)，可以大大減少最大頻繁項集挖掘過程中需要考察的項集數(shù)量，提高了算法的效率；

步驟3：超集檢測并生成最大頻繁項集的集合：

上述過程可以避免搜索過程中，搜索那些根本不可能是最大頻繁項集的頂集；最終生成的項集再使用超集檢測的方法確定它是一個最大頻繁項集；最后，生成的所有最大頻繁項集的集合便是最大頻繁項集挖掘的最終結(jié)果。