[發明專利]基于MapReduce的并行頻繁項集增量數據挖掘方法

有效

• 申請號: 202110177059.8
• 申請日: 2021-02-07
• 公開（公告）號: CN112925821B
• 公開（公告）日: 2022-05-13
• 發明（設計）人: 毛伊敏;鄧千虎
• 申請（專利權）人: 韶關學院
• 主分類號: G06F16/2458
• 分類號: G06F16/2458;G06K9/62;G06N3/12
• 代理公司: 重慶天成卓越專利代理事務所(普通合伙) 50240
• 代理人: 王宏松

本發明提出了一種基于MapReduce的并行頻繁項集增量數據挖掘方法(MR?PARIMIEG)。S1，設計基于信息熵的SIM?IE策略來合并數據集中的相似數據項，根據合并后的數據集進行Can樹構造，降低了最終生成的Can樹結構的空間占用；S2，提出基于遺傳算法的DST?GA策略用于獲取大數據集中的相對最優動態支持度閾值，根據所述相對最優動態支持度閾值進行頻繁模式挖掘；S3，使用并行LZO數據壓縮算法對Map端輸出的數據進行壓縮來減少傳輸的數據規模，從而減少了內存與磁盤之間的IO操作頻次，最終加速Map與Reduce階段的數據傳輸過程。本發明實用簡便，與已有的基于MapReduce并行頻繁項集增量挖掘方法相比較，本發明提出的方法在時間復雜度和空間復雜度等方面都有明顯提高。

技術領域

本發明涉及大數據挖掘領域，特別是涉及一種基于MapReduce的并行頻繁項集增量數據挖掘方法。

背景技術

關聯規則(Association rule)是數據挖掘的一個主要研究領域，其目的在于發現數據集中有價值的潛在頻繁模式。目前，關聯規則挖掘已被廣泛應用于購物推薦、網站點擊分析、電子商務、金融和醫療診斷等領域，產生了極大的經濟與社會效益。靜態關聯規則挖掘是在固定的數據集以及支持度閾值下，對數據集中的頻繁模式進行挖掘，如Apriori、FP-Growth、Eclat等。但這些靜態關聯規則算法并未考慮到數據庫中的事務發生變化或是關鍵的支持度閾值發生變化的增量挖掘工作，這將導致算法需對整個數據集進行重復處理，造成大量的時空間消耗。針對此問題，Leung等人提出了一種基于CATS樹改進的Can樹(Canonical order tree)來簡化增量挖掘工作，極大地提高了算法的運行效率。但在大數據環境下，隨著數據量的指數級增長，運算時間過長和內存占用過高已經成為傳統關聯規則算法處理海量數據的重要瓶頸。因此，提高算法的并行化效率使之能高效地對海量數據進行處理是目前迫切需要解決的問題。

MapReduce是Google公司為解決海量數據處理提出的一種分布式并行運算框架，具有使用簡單、成本低廉、系統擴展性好以及負載均衡等優點，目前已被廣泛應用于大數據分析與處理等領域。基于此，Song等人提出了一種大數據環境下的并行頻繁項集挖掘算法IncMiningPFP，結合MapReduce計算框架實現了Can樹向并行化方向的遷移，極大地提高了基于Can樹的增量挖掘算法的并行化運算能力。但該算法在使用Can樹結構儲存所有數據信息以加快后續增量挖掘的同時，也會導致最終產生的樹結構極為龐大。針對此問題，胡軍等人使用一種基于數據量排序的Can樹構造方法，將各事務中的數據項按出現頻次進行排序，然后根據排序后的事務進行樹結構構建，使得各個事務中相同的數據項盡量共用一個樹節點，從而降低最終生成的樹結構的空間占用。但此方法在適用性與可行性方面具有較大的局限性，因此對Can樹結構空間占用過大的問題仍然有待進一步改進。

此外，支持度閾值的設定對于關聯規則算法而言也是極為關鍵的問題。大數據的數據規模更大，但數據的價值密度卻隨之下降，當設定的支持度閾值較小時，將會產生大量冗余的無效頻繁項集，而使用相對較大的支持度閾值時，則可能在減少冗余項集的同時丟失一些高質量的頻繁項信息，使得最終生成的頻繁項的整體質量偏低。針對該問題，Ragaventhiran等人在應用MapReduce框架并行化挖掘Can樹頻繁模式的同時，設計了基于多支持度的頻繁模式挖掘方法，在不同的支持度閾值下進行頻繁模式挖掘，根據挖掘結果來獲取最優的支持度閾值。但該算法僅支持特定的閾值取值范圍，并未對大數據環境下的閾值取值進行優化，難以根據相對最優的動態支持度閾值獲取最終結果。