閉項(xiàng)集挖掘算法研究綜述

劉文杰，秦偉德，張曉蝶

（蘭州財(cái)經(jīng)大學(xué)，甘肅 蘭州 620020）

1 引言

頻繁項(xiàng)集挖掘算法和高效用項(xiàng)集挖掘算法是數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則領(lǐng)域非常重要的兩個(gè)分支，可以從數(shù)量和效用角度出發(fā)發(fā)現(xiàn)項(xiàng)之間隱藏的關(guān)聯(lián)性。頻繁項(xiàng)集挖掘旨在挖掘頻繁地同時(shí)出現(xiàn)在數(shù)據(jù)庫(kù)中的項(xiàng)，假定事務(wù)中每個(gè)項(xiàng)的價(jià)值都相同并且僅考慮項(xiàng)集在交易事務(wù)中出現(xiàn)的總次數(shù)。但在現(xiàn)實(shí)中，項(xiàng)集的出現(xiàn)次數(shù)并不能完全表達(dá)出數(shù)據(jù)的所有有用信息。高效用項(xiàng)集挖掘是在頻繁項(xiàng)集挖掘的基礎(chǔ)上發(fā)展而來(lái)的，其不僅考慮項(xiàng)集的出現(xiàn)次數(shù)，還考慮用戶偏好、重要性、利潤(rùn)等因素對(duì)項(xiàng)集“有效性”影響。

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

2 基本概念

閉項(xiàng)集的概念是基于以下兩個(gè)函數(shù)提出來(lái)的：

其中函數(shù)f返回所有事務(wù)中共同包含的項(xiàng)集，函數(shù)g返回包含項(xiàng)集i的所有事務(wù)。

定義1 閉項(xiàng)集。當(dāng)一個(gè)項(xiàng)集稱之為閉項(xiàng)集，當(dāng)且僅當(dāng)滿足：

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

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

定理2 對(duì)于一個(gè)項(xiàng)集X和一個(gè)項(xiàng)i，如果滿足g（X）?g（i），則項(xiàng)i是X的一個(gè)閉包，即i∈c（X）。

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

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

3 閉頻繁項(xiàng)集挖掘算法

現(xiàn)有的經(jīng)典的閉頻繁項(xiàng)集挖掘算法和頻繁項(xiàng)集挖掘算法一樣，大致分成基于水平層級(jí)機(jī)制、基于模式增長(zhǎng)機(jī)制和基于垂直數(shù)據(jù)格式機(jī)制三種類(lèi)型。

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

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

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

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

4 閉高效用項(xiàng)集挖掘算法

現(xiàn)有的閉高效用項(xiàng)集挖掘算法可分為一階段算法和兩階段算法。

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

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

5 總結(jié)與未來(lái)研究方向

閉項(xiàng)集可以有效地減少大量冗余的項(xiàng)集，從而減少算法的搜索空間提高算法效率，是全集項(xiàng)集一種精簡(jiǎn)高效且無(wú)損的模式。文章主要從閉頻繁項(xiàng)集和閉高項(xiàng)集這兩部分進(jìn)行算法性質(zhì)的歸納，未來(lái)也會(huì)在更多閉項(xiàng)集算法比如閉序列或者在數(shù)據(jù)流上的閉項(xiàng)集上進(jìn)行研究。