基于iceberg概念格的最大頻繁項集挖掘研究.pdf

1、關聯(lián)規(guī)則挖掘過程中頻繁項集(Frequent Itemset，F(xiàn)I)的求解是關聯(lián)規(guī)則挖掘的基礎和前提，也是關聯(lián)規(guī)則挖掘中最耗時的一步。降低候選項集的數量是減小開銷的最好手段。由于最大頻繁項集(Maximal Frequent Itemset，MFI)中已經隱含了所有頻繁項集，所以可把發(fā)現(xiàn)頻繁項集的問題轉化為發(fā)現(xiàn)最大頻繁項集的問題。挖掘最大頻繁項集可有效地縮小項集的規(guī)模，便于用戶迅速發(fā)現(xiàn)稠密數據集中的知識。
　　 然而，隨著數據收

2、集和數據存儲技術的快速進步，使得各組織機構積累了海量的數據，造成現(xiàn)有的最大頻繁項集挖掘算法挖掘效率低下，主要表現(xiàn)為：多次掃描數據庫需要大量I/O開銷；候選集規(guī)模過大導致無法計算和存儲；增量挖掘困難；大量冗余的和用戶不感興趣的規(guī)則等等。為了解決上述問題，論文將具有完備特性的iceberg概念格模型引入到最大頻繁項集挖掘的研究中。iceberg概念格是在用戶指定的支持度閾值的條件下概念格中所有頻繁概念構成的半序格結構，每個頻繁概念的內涵都是

3、一個頻繁閉項集，描述了數據集中對象和屬性之間的關系。利用頻繁閉項集與最大頻繁項集之間的隸屬關系和頻繁概念之間良好的泛化和特化關系，提出了基于iceberg概念格的最大頻繁項集和屬性增長的最大頻繁項集增量挖掘算法。論文還對基于iceberg概念格的正相關的無冗余關聯(lián)規(guī)則進行研究，解決了從最大頻繁項集中挖掘的關聯(lián)規(guī)則會導致支持度信息的損失和存在大量冗余的用戶不感興趣的規(guī)則的問題。論文的主要工作如下；
　　 (1)提出基于iceber

4、g概念格的最大頻繁項集挖掘算法ICMFIA(IcebergConcept Lattice Maxmal Frequent Itemset Alogithm)。該算法通過一次掃描數據集構建iceberg概念格，利用iceberg概念格中頻繁概念之間良好的覆蓋關系，能快速計算出最大頻繁項集所對應的最大頻繁概念，所有最大頻繁概念的內涵就是所求的最大頻繁項集的集合。理論證明和實驗測試結果表明，所提算法與現(xiàn)有算法相比，具有掃描數據集次數少和挖掘效

5、率高的優(yōu)點。
　　 (2)提出基于iceberg概念格的最大頻繁項集增量挖掘算法MAI-AI(MaximalFrequent Itemset-Attribute Incremental)。該算法主要針對數據集的屬性增加后最大頻繁項集挖掘問題。在原始iceberg概念格的基礎上構建新的iceberg概念格并計算新增的最大頻繁概念和需要更新的最大頻繁概念。然后只需挖掘新增的最大頻繁項集和最大頻繁項集集合中需要更新的最大頻繁項集。避免

6、了數據集中屬性增加后需要重新挖掘所有的最大頻繁項集問題。實驗結果表明，算法具有重復工作少和重用率高的優(yōu)點。
　　 (3)提出了在iceberg概念格中挖掘正相關的無冗余關聯(lián)規(guī)則的方法，以解決最大頻繁項集挖掘出的關聯(lián)規(guī)則支持度信息的損失和存在大量用戶不感興趣的規(guī)則等問題。通過提出無冗余關聯(lián)規(guī)則來縮小挖掘規(guī)則的規(guī)模，其它有效的關聯(lián)規(guī)則的支持度和置信度都能通過無冗余關聯(lián)規(guī)則計算出來。由于使用支持度-置信度框架計算的強關聯(lián)規(guī)則不一定是有