閉項集挖掘算法研究綜述

劉文杰，秦偉德，張曉蝶

（蘭州財經大學，甘肅 蘭州 620020）

1 引言

頻繁項集挖掘算法和高效用項集挖掘算法是數據挖掘關聯規則領域非常重要的兩個分支，可以從數量和效用角度出發發現項之間隱藏的關聯性。頻繁項集挖掘旨在挖掘頻繁地同時出現在數據庫中的項，假定事務中每個項的價值都相同并且僅考慮項集在交易事務中出現的總次數。但在現實中，項集的出現次數并不能完全表達出數據的所有有用信息。高效用項集挖掘是在頻繁項集挖掘的基礎上發展而來的，其不僅考慮項集的出現次數，還考慮用戶偏好、重要性、利潤等因素對項集“有效性”影響。

然而，頻繁項集和高效用項集挖掘的結果通常是很大的集合，尤其是當數據集很密集或者閾值?很小時，因此閉項集的概念被提出，其中閉頻繁項集CFIs和閉高效用項集CHUIs就是為了解決這個問題而提出的，生成的CFIS、CHUIs集合中的元素數量明顯少于FIs、HUIs，但不會丟失任何信息，并且可以從所有挖掘出的閉頻繁項集和閉高效用項集恢復到全集頻繁項集和高效用項集。因此，可以挖掘閉項集而不是全集項集，以最大限度地減少存儲空間和內存使用。

2 基本概念

閉項集的概念是基于以下兩個函數提出來的：

其中函數f返回所有事務中共同包含的項集，函數g返回包含項集i的所有事務。

定義1 閉項集。當一個項集稱之為閉項集，當且僅當滿足：

其中fog（I）混合函數也被稱作伽羅瓦操作或者閉包[dci]操作。

定理1 對項集X和項集Y，如果滿足X ?Y以及 SC（X）=SC（Y）（|g（X）|=|g（Y）|， 則 X的閉包和Y的閉包相同，即C（X）=C（Y）。

定理2 對于一個項集X和一個項i，如果滿足g（X）?g（i），則項i是X的一個閉包，即i∈c（X）。

定義2 閉頻繁項集。如果項集X同時滿足在數據庫中不存在X的超集Y且與X的支持度相同且X的支持度不小于最小支持度閾值即SC（X）≥minsup，則稱X為閉頻繁項集。

定義3 閉高效用項集。閉高效用項集。如果項集X同時滿足在數據庫中不存在X的超集Y和與X的支持度相同和X的效用值不小于最小效用閾值即 U（X）≥mutil，則稱X為閉高效用項集。

3 閉頻繁項集挖掘算法

現有的經典的閉頻繁項集挖掘算法和頻繁項集挖掘算法一樣，大致分成基于水平層級機制、基于模式增長機制和基于垂直數據格式機制三種類型。

A-CLOSE采用Apriori算法的水平層級機制，延續了自底向上、廣度優先的搜索策略。首先通過Apriori策略逐層瀏覽頻繁項集格，挖掘每個等價類的最小元素。在第二步中，A-CLOSE計算之前找到的所有最小生成器的閉包。由于單個等價類可能有多個最小項集，因此可能會計算冗余閉包。此外，A-CLOSE性能受到離線閉包計算高成本和大量子集搜索的影響。

為了解決水平層級機制算法項集連接成本昂貴的問題，一些閉頻繁項集挖掘算法也采用了模式增長的機制。CLOSET+使用了FP-tree結構，但與CLOSET算法不同之處體現在以下幾方面：①采用混合樹投影方法，對稠密數據集使用自下而上的物理樹投影，對稀疏數據集使用自上而下的物理樹投影，有效提高了空間效率。②使用項集跳過技術來修剪搜索空間。③使用高效的子集檢查方法確保新發現的項集是閉項集。實驗表明，就運行時間、內存使用和可擴展性而言，CLOSE+相對于現有挖掘算法具有一定優勢。FPClose使用FP-tree結構的另一種變體——CFI樹，用于檢查頻繁項集的閉合性。此外，采用一種新的FP-array技術，來提高在CFI-tree上的操作性能。實驗結果表明，FPClose閉項集檢測方法比CLOSET+方法更有效。

以上算法的數據格式均為水平的，一些算法將數據格式進行轉換，采用了垂直的數據格式。CHARM使用了一些創造性的思想：①不同于之前算法只探索項目集空間，CHARM通過IT-tree（itemset-tidset search Tree）結構同時探索項目集空間和事務空間。②使用一種混合搜索方法，可以跳過IT-tree的許多層級，提高搜索效率。③使用縱向數據表示diffsets技術減少TID交集計算的內存占用。④使用一種快速的基于散列的方法來移除在計算過程中發現的任何“非封閉”集合，顯著壓縮候選項集。在大量真實和合成數據庫上進行的廣泛實驗評估表明，CHARM明顯優于以前的方法，在事務數量上也是可線性擴展的。DCI-Closed的中心思想是引入兩個變量：PRE_SET和POST_SET。其中POST_SET用于構建所有可能的生成器，PRE_SET用于進行生成器重復檢查。實驗證明，DCI-Closed算法優于CLOSE+和FPClose。

近幾年，國內外學者在閉頻繁項集挖掘算法問題上積極探索創新，取得不錯的研究成果。黨紅恩等人提出一種基于數據變換與并行運算的DTPC算法，該算法利用質數對數運算的方法，將大量數據轉換成簡單的數字，在Spark平臺上進行閉頻繁項集的挖掘。實驗證明，DTPC算法在挖掘效率上得到顯著提升，并且節約了計算資源成本。Aryabarzan等人提出一種快速挖掘的NECLATCLOSED算法，該算法使用項目集搜索樹來表示搜索空間。對數據庫掃描以識別包含1-項集的TSets，基于TSets識別出所有的頻繁1-項集作為根目錄的子目錄。此外，算法還提出一種快速包容檢查的技術，使用一個hashmap結構將閉頻繁項集的有序列表與支持度關聯起來進行快速檢查。實驗證明NECLATCLOSED算法在大多數情況下都優于以上主流算法，尤其是在運行時間上。

4 閉高效用項集挖掘算法

現有的閉高效用項集挖掘算法可分為一階段算法和兩階段算法。

兩階段算法指的是在第一階段利用TWU值和最小效用閾值生成候選項集，第二階段利用候選項集真實效用值和最小效用閾值生成高效用項集，如 AprioriCH、EFIM-Closed。AprioriCH 在Apriori的基礎上進行擴展，利用橫向擴展數據庫和廣度優先搜索方式挖掘閉高效用項集。EFIMClosed使用新的子樹效用值和本地效用值上界，有效地修剪搜索空間。還提出了數據庫投影和事務合并技術來挖掘閉高效用項集，降低了數據庫掃描的成本。此外，采用了新的 CJ、FCC 和 BCC剪枝策略來刪除非閉合的高效用項集。實驗結果表明，與 CHUD相比，EFIM-Closed 速度可以提高一個數量級以上，消耗的內存可以減少一個數量級以上。

一階段算法直接比較項集的效用和最小閾值，不生成候選項集，如CHUI-Miner、CLS-Miner、IncCHUI。CHUI-Miner是首次用一階段方法挖掘閉高效用項集的算法。該算法提出了用于事務中維護項集效用信息的新結構擴展效用列表 EU-List，該結構可以在一階段中有效地計算項集效用和效用單元數組。該算法在不產生候選項的情況下，可以在數據庫中發現完整的 CHUIs。實驗結果表明，與 CHUD 算法相比時間快了兩個數量級以上。CLS-Miner利用效用列表結構直接計算項集效用而不產生候選；采用Chain-EUCP、LBP和 Coverage三種新的搜索空間剪枝策略，引入了子集檢查的高效方法，進一步減少了發現閉高效用項集所需的時間。實驗結果表明，在運行時間方面，CLS-Miner 比 CHUD和CHUIMiner 算法快幾個數量級。IncCHUI從增量數據庫中挖掘閉高效用項集。該算法采用了增量效用列表結構，只需要掃描一次數據庫就可以構建和更新數據；使用基于散列的方法來更新或插入找到的新的閉高效用項集。實驗結果表明，就速度而言，它明顯優于之前提出的以批處理模式運行的算法，并且在事務數量方面是可擴展的。

5 總結與未來研究方向

閉項集可以有效地減少大量冗余的項集，從而減少算法的搜索空間提高算法效率，是全集項集一種精簡高效且無損的模式。文章主要從閉頻繁項集和閉高項集這兩部分進行算法性質的歸納，未來也會在更多閉項集算法比如閉序列或者在數據流上的閉項集上進行研究。