不確定數(shù)據(jù)頻繁項集挖掘算法研究

趙學(xué)健，熊肖肖，張欣慧，孫知信

(1.南京郵電大學(xué) 現(xiàn)代郵政學(xué)院，江蘇 南京 210003；2.南京郵電大學(xué) 物聯(lián)網(wǎng)學(xué)院，江蘇 南京 210003)

0 引 言

作為數(shù)據(jù)挖掘領(lǐng)域研究的重要分支之一，頻繁項集挖掘的主要目的是以頻繁出現(xiàn)的項目集的形式發(fā)掘嵌入在海量數(shù)據(jù)中的隱式的、先前未知的、潛在的有用知識[1-4]。當(dāng)前，頻繁項集挖掘在各領(lǐng)域應(yīng)用廣泛，如銀行數(shù)據(jù)分析、市場營銷、醫(yī)療診斷、氣象數(shù)據(jù)分析等[5]。上述應(yīng)用中廣泛存在不確定數(shù)據(jù)，造成數(shù)據(jù)不確定性的原因主要有：對現(xiàn)實世界的有限感知和理解能力；感知監(jiān)測設(shè)備的局限性；用于收集、儲存、轉(zhuǎn)換或數(shù)據(jù)分析的可用資源的限制；無線傳輸錯誤或網(wǎng)絡(luò)延遲；數(shù)據(jù)粒度或隱私保護。因此，針對不確定數(shù)據(jù)的頻繁項集挖掘引起了學(xué)者的廣泛關(guān)注。

文中首先介紹了不確定數(shù)據(jù)的定義，并分析不確定數(shù)據(jù)頻繁項集挖掘的概率模型。接著詳細介紹了當(dāng)前針對不確定數(shù)據(jù)的主流頻繁項集挖掘算法，將主流頻繁項集挖掘算法分為3類：基于候選項集生成和測試的頻繁項集挖掘算法，基于模式增長的頻繁項集挖掘算法和基于生物啟發(fā)的頻繁項集挖掘算法，分別介紹3類算法的代表性算法，并對相關(guān)算法的性能進行了簡單分析。最后進行總結(jié)與展望。

1 定義及模型

在早期，最常見的頻繁項集挖掘算法主要用于搜索傳統(tǒng)的確定數(shù)據(jù)庫。然而，在各種實際應(yīng)用中，數(shù)據(jù)庫中的每一條事務(wù)中項目的存在不是百分百確定的，而是依據(jù)某種相似性度量或是概率形式存在，比如說通過分析購物籃數(shù)據(jù)來預(yù)測商品需求量時，購物籃中的商品用戶并不是肯定要購買的，而是存在一個不確定性。

在過去幾年中，許多模型被提出用于不確定數(shù)據(jù)的分析[6-7]，其中概率模型受到了眾多研究者的青睞。從概率模型的角度來看，在不確定數(shù)據(jù)集D中，用戶可能無法確定事務(wù)Tq中是否存在某個項目集X，這種不確定性可以用存在概率p(X,Tq)來表示，p(X,Tq)表示X存在于事務(wù)Tq中的可能性。存在概率p(X,Tq)的取值最小為一個接近0的正值，表示X在D中存在的可能性不大，趨近于0；存在概率p(X,Tq)的取值最大為1，表示項目集X絕對存在。從這個意義上說，傳統(tǒng)的確定數(shù)據(jù)庫可以看作每一個項目在事務(wù)Tq中的存在概率均為100%的不確定數(shù)據(jù)庫。不確定數(shù)據(jù)的概率模型涉及以下三個定義。

定義1(項集在事務(wù)中的存在概率)：項集X在事務(wù)Tq中的出現(xiàn)概率記為p(X,Tq)，等于項集中各項目在事務(wù)Tq中存在概率的乘積。

即：

其中，Ij為項集X的第j個項目。

定義2(項集的期望支持度)：項集X在不確定數(shù)據(jù)庫D中的期望支持度記為expSup(X)，等于項集X在包含該項集的所有事務(wù)中的出現(xiàn)概率之和。

即：

定義3(頻繁項集)：在不確定數(shù)據(jù)庫D中，當(dāng)項集X的期望支持度大于等于最小期望支持度時(最小期望支持度為最小期望支持度閾值δ與數(shù)據(jù)庫D中所包含事務(wù)數(shù)的乘積)，則項集X為頻繁項集，即當(dāng)expSup(X)≥δ×|D|時，項集X為頻繁項集。

2 頻繁項集挖掘算法

2.1 基于候選項集生成和測試的頻繁項集挖掘算法

從不確定數(shù)據(jù)中挖掘頻繁項集的一種重要方法是首先生成候選頻繁項集然后掃描數(shù)據(jù)庫對候選頻繁項集進行測試?；谶@個思想，Chui等[8]提出了U-Apriori算法，該算法從不確定數(shù)據(jù)中挖掘頻繁模式的方法是分層的、寬度優(yōu)先的、自下而上的。具體來說，U-Apriori算法首先計算所有1-項集的期望支持度，通過掃描不確定數(shù)據(jù)庫，那些期望支持度大于最小期望支持度的項目最終組成頻繁1項集。然后，U-Apriori算法反復(fù)應(yīng)用候選項集生成和測試的過程，從頻繁k項集生成候選k+1項集，并測試它們是否是頻繁的k+1項集。U-Apriori算法與用于挖掘確定數(shù)據(jù)的Apriori算法[2]是一樣的，都依賴于Apriori屬性，即頻繁模式的所有子集也必須是頻繁的，反之任何非頻繁項集的所有超集也是非頻繁項集，該性質(zhì)也稱為向下閉包特性。

U-Apriori算法還通過采用LGS-修整策略來提高其效率，LGS-修整包括局部修整、全局剪枝和單次修補。

該策略從不確定數(shù)據(jù)的原始概率數(shù)據(jù)集D中剔除每一項存在概率低于用戶指定的修剪閾值的項，然后從修剪以后的數(shù)據(jù)集中挖掘頻繁項集。

Chui等[9]采用遞減修剪技術(shù)，進一步提高了U-Apriori的效率。遞減修剪技術(shù)通過估計候選頻繁項集的期望支持度的上限以減少候選模式的數(shù)量。如果候選頻繁項集X的估計期望支持度上限值低于最小期望支持度，則立即剪除該候選頻繁項集X。

2.2 基于模式增長的頻繁項集挖掘算法

基于模式增長的頻繁項集挖掘算法是基于候選項集生成和測試的頻繁項集挖掘方法的一種有效替代方法，能夠避免產(chǎn)生大量的候選項集。常用的模式增長頻繁項集挖掘算法又可以分為兩類：基于超鏈接結(jié)構(gòu)的頻繁項集挖掘算法和基于樹結(jié)構(gòu)的頻繁項集挖掘算法。

(1)基于超鏈接結(jié)構(gòu)的頻繁項集挖掘算法。

基于超鏈接結(jié)構(gòu)的頻繁項集挖掘算法以超鏈接結(jié)構(gòu)存儲數(shù)據(jù)集的內(nèi)容，在這類算法中，頻繁的模式以深度優(yōu)先、分而治之的方式被挖掘出來。

Aggarwal等[10]提出了一種基于超鏈接結(jié)構(gòu)的UH-mine算法，用于從不確定數(shù)據(jù)中挖掘頻繁項集。該算法用一個名為UH-struct的超鏈接結(jié)構(gòu)存儲不確定數(shù)據(jù)集D中的概率數(shù)據(jù)內(nèi)容。UH-struct中的每一行表示不確定數(shù)據(jù)集D中的一個事務(wù)，與用于挖掘確定性數(shù)據(jù)的H-struct不同的是，UH-struct還存儲了項目的存在概率。換句話說，對于存在于事務(wù)中的每個項目，通過UH-struct可以得到：項目本身；項目的存在概率；項目的超鏈接結(jié)構(gòu)。因此，在UH-mine算法中，通過建立的UH-struct可以遞歸地擴展每個頻繁項集并調(diào)整其在UH-struct中的超鏈接來實現(xiàn)頻繁項集的挖掘。

該算法在較小的數(shù)據(jù)集上可以獲得較好的效果，然而在大數(shù)據(jù)集上，由于H-struct需要較多的空間來存儲數(shù)據(jù)集，并且算法需要多次遞歸調(diào)用，因此時間效率并不理想。

(2)基于樹結(jié)構(gòu)的頻繁項集挖掘算法。

基于候選項集生成和測試的頻繁項集挖掘算法使用了分層的自下而上的廣度優(yōu)先挖掘范式，但是往往生成的候選項集數(shù)量過多。基于超級鏈接結(jié)構(gòu)的頻繁項集挖掘算法通過遞歸地調(diào)整超鏈接結(jié)構(gòu)，以深度優(yōu)先的方式從不確定的數(shù)據(jù)中找到頻繁的模式，時間效率也不理想。

基于樹的頻繁項集挖掘算法使用樹結(jié)構(gòu)對不確定數(shù)據(jù)集進行存儲，并采用深度優(yōu)先、分而治之的方法挖掘頻繁項集，既可避免產(chǎn)生許多候選項集，又避免了遞歸地調(diào)整多個超鏈接結(jié)構(gòu)，具有較好的性能。

Leung等提出了一種基于樹的頻繁項集挖掘算法UF-Growth[11]，類似于用于挖掘確定性數(shù)據(jù)的頻繁項集挖掘算法FP-Growth[12]，UF-Growth也是通過構(gòu)造一個樹結(jié)構(gòu)來存儲數(shù)據(jù)集的內(nèi)容。但是，它不使用FP-tree，因為FP-tree中的每個節(jié)點都只能記錄項目及其在樹路徑中的出現(xiàn)數(shù)目。當(dāng)挖掘確定性數(shù)據(jù)集時，項集X的期望支持度取決于項集X中各項目的出現(xiàn)次數(shù)。然而，在挖掘不確定數(shù)據(jù)時，X的期望支持度是X中各項目的發(fā)生計數(shù)和存在概率的乘積之和。因此，UF-Growth算法采用了不同于FP-tree的樹結(jié)構(gòu)UF-tree。

UF-tree中的每個節(jié)點由三個部分組成：項目、存在概率、項目在路徑中的出現(xiàn)次數(shù)。UF-tree的構(gòu)造方式與FP-tree的構(gòu)造類似，但是只有當(dāng)事務(wù)和子節(jié)點中存在相同的項和相同的存在概率時，新事務(wù)才會與子節(jié)點合并。因此，UF-tree比原來的FP-tree具有更低的壓縮比。

Aggarwal等[13]提出了UFP-growth算法，與UF-growth算法一樣，UFP-growth算法也會通過兩次掃描不確定數(shù)據(jù)集來建立UFP-tree。UFP-tree中，當(dāng)項集X對應(yīng)的節(jié)點具有相似的存在概率值時，會聚集成一個超級節(jié)點。超級節(jié)點將會存儲項集X、存在概率值及其出現(xiàn)數(shù)信息。UFP-growth算法在第二次掃描不確定數(shù)據(jù)集時才能發(fā)現(xiàn)所有真正頻繁的模式，然而由于UFP-growth的近似性質(zhì)，UFP-growth算法除了能夠發(fā)現(xiàn)那些真正頻繁的項集之外，還會發(fā)現(xiàn)一些不常見的模式，稱為假陽性模式。

因此，需要對不確定數(shù)據(jù)集進行第三次掃描，以消除這些錯誤。

Leung和Tanbeer[14]提出了一種用于不確定數(shù)據(jù)集的頻繁項集挖掘算法，稱為CUF-growth算法。該算法構(gòu)建了一種叫做CUF-tree的樹結(jié)構(gòu)，與UFP-growth算法一樣，CUF-growth算法也對不確定數(shù)據(jù)集進行三次掃描，以挖掘頻繁項集。CUF-growth首先掃描數(shù)據(jù)集以計算事務(wù)上限，然后通過第二次掃描數(shù)據(jù)集構(gòu)建CUF-tree。在第二次掃描不確定數(shù)據(jù)集結(jié)束時，CUF-growth算法會發(fā)現(xiàn)所有潛在的頻繁項集。由于這些潛在的頻繁項集包括所有真正頻繁的項集和一些并不頻繁的項集，CUF-growth算法最后通過第三次快速掃描數(shù)據(jù)集，以檢查每個項目集，驗證它們是否是真正頻繁的，即修剪假陽性項目集。

Leung和Tanbeer[15]引入了前綴項上限的概念，并提出了相應(yīng)的PUF-growth算法用于挖掘不確定數(shù)據(jù)集中的頻繁項集。與UFP-growth和CUF-growth一樣，PUF-growth算法也對不確定數(shù)據(jù)的概率數(shù)據(jù)集進行三次掃描，以挖掘頻繁項集。在第一次掃描中，PUF-growth計算前綴項上限。在第二次掃描中，PUF-growth構(gòu)建PUF-tree。PUF-growth算法也是在第二次掃描不確定數(shù)據(jù)集結(jié)束時找到所有潛在頻繁項集。因為這些潛在的頻繁項集包括所有真正頻繁的項集和一些罕見的項集。PUF-growth算法最后通過第三次快速掃描數(shù)據(jù)集，檢查每個數(shù)據(jù)集是否真的頻繁。PUF-growth算法采用的前綴項上限與CUF-tree算法的事務(wù)上限相比更加接近項集的期望支持度，因此在第三次掃描過程中，需要檢驗的假陽性項目集數(shù)量通常小于CUF-growth算法需要檢驗的項目集數(shù)量，速度更快。

2.3 基于生物啟發(fā)的頻繁項集挖掘算法

上述基于候選項集生成與測試的頻繁項集挖掘算法以及基于模式增長的頻繁項集挖掘算法都是精確挖掘算法，也就是說這些算法都可以挖掘出數(shù)據(jù)集中的所有頻繁項集。這類算法雖然精確度高，但是時間復(fù)雜度通常與數(shù)據(jù)集的規(guī)模成正比。當(dāng)數(shù)據(jù)集非常大時，比如社交網(wǎng)絡(luò)數(shù)據(jù)[16]或者大型生物信息數(shù)據(jù)集[17]，精確的頻繁項集挖掘算法幾乎是無能為力的[18]。

為了解決精確頻繁項集挖掘算法時間效率低下的問題，研究人員提出了基于生物啟發(fā)的頻繁項集挖掘算法，比如基于遺傳算法的頻繁項集挖掘算法[19-20]，基于群體智能的頻繁項集挖掘算法等[21]。基于生物啟發(fā)的頻繁項集挖掘算法可以在規(guī)定的合理時限內(nèi)完成，但是通常該類算法不能挖掘出所有的頻繁項集，稱之為模糊頻繁項集挖掘算法。因此，針對大型的不確定數(shù)據(jù)集，提出合適的生物啟發(fā)頻繁項集挖掘算法在保證時間效率的前提下獲得更高質(zhì)量的頻繁項集，將會是一個持續(xù)的挑戰(zhàn)。

文獻[19]提出的GA-FIM算法將每一個項目集看成由n個元素組成的向量，如果該項目集的第i個元素屬于該項目集，則將向量的第i個元素設(shè)置為1，否則設(shè)置為0。比如說數(shù)據(jù)集中包含5個項目，即I={a,b,c,d,e}，則項目集bde可以用向量{0,1,0,1,1}表示。接下來，在完成初始化后將執(zhí)行遺傳算法的交叉、變異和選擇操作，直到達到預(yù)先設(shè)置的輪數(shù)為止。最終，GA-FIM算法得到的頻繁項集為每一輪過程中發(fā)現(xiàn)的頻繁項集的集合。

文獻[21]最早提出了PSO-FIM算法，文獻[22]后期又對PSO-FIM算法進行了改進。在PSO-FIM算法中，群體中的每一個粒子代表一個項目集，粒子在初始化時隨機設(shè)置為項目集空間中的任意一個項目集。PSO-FIM算法初始化時首先構(gòu)造一群隨機粒子，接下來通過迭代找到最優(yōu)解。在每一次迭代中，粒子通過跟蹤兩個極值來進行更新，第一個值是本粒子找到的最優(yōu)解，即具有最大期望支持度的項目集，第二個值是整個粒子群找到的最優(yōu)解。

文獻[19]和文獻[21]表明，GA-FIM算法和PSO-FIM算法相對于當(dāng)前的精確頻繁項集挖掘算法具有更好的時間效率。然而，這兩種算法所得到的頻繁項目集結(jié)果并不理想，也就是說算法的最終輸出僅為頻繁項目集的一個子集。

3 算法性能對比分析

上述對不確定數(shù)據(jù)集的頻繁項目集挖掘算法進行了分類劃分，并對代表性算法進行了介紹，包括U-Apriori、UH-mine、UF-growth、UFP-growth、CUF-growth、PUF-growth、GA-FIM及PSO-FIM等。

在準(zhǔn)確性方面，U-Apriori、UH-mine、UF-growth、UFP-growth、CUF-growth、PUF-growth算法都可以返回滿足用戶指定最小期望支持度閾值的所有頻繁項集。然而，GA-FIM及PSO-FIM算法由于融合了啟發(fā)式智能算法的思想，不一定能夠返回所有符合條件的頻繁項目集，準(zhǔn)確性相對較差。

在內(nèi)存消耗方面，U-Apriori保留了候選頻繁項集列表，而基于樹和超鏈接結(jié)構(gòu)的算法則構(gòu)造內(nèi)存結(jié)構(gòu)，比如UF-tree及其變體，擴展的H-struct等。一方面，UF-tree比擴展的H-struct更緊湊，即需要更少的空間。然而，另一方面，UH-mine只保留一個擴展的H-struct，而基于樹的算法通常構(gòu)造不止一棵樹，樹的大小也可能不同。

因此，基于樹和超鏈接結(jié)構(gòu)的算法的內(nèi)存消耗要根據(jù)具體算法和數(shù)據(jù)集情況來確定。GA-FIM及PSO-FIM算法不需要保存大量候選頻繁項集或其他內(nèi)存結(jié)構(gòu)，內(nèi)存消耗較小。

就時間性能而言，GA-FIM及PSO-FIM等基于生物啟發(fā)的頻繁項集挖掘算法可以靈活設(shè)置，通常優(yōu)于其他幾種算法。

基于候選項集生成和測試及基于模式增長的頻繁項集挖掘算法的時間性能影響因素較多。首先，項目對應(yīng)的存在概率會影響算法的時間性能。通常不確定數(shù)據(jù)集中的項目呈現(xiàn)較低的存在概率時，大多數(shù)算法的性能都很好，因為這些數(shù)據(jù)集不會導(dǎo)致較長的頻繁模式。當(dāng)項目呈現(xiàn)較高的存在概率值時，U-Apriori算法會生成更多的候選頻繁項集，U-growth算法需要構(gòu)造更多更大的UF-tree，UH-mine算法需要調(diào)整更多的超鏈接結(jié)構(gòu)，自然都需要更長的運行時間。其次，當(dāng)最小期望支持度減小時，往往會得到更多的頻繁項目集，當(dāng)然也需要更長的運行時間。此外，數(shù)據(jù)集的密度也會影響運行時間。例如，當(dāng)數(shù)據(jù)集密集時，UF-tree獲得了更高的壓縮比，因此與稀疏數(shù)據(jù)集相比，遍歷所需的時間更短，時間性能更好。

4 結(jié)束語

頻繁項集挖掘是一項重要的數(shù)據(jù)挖掘任務(wù)，有助于發(fā)現(xiàn)隱式的、先前未知的潛在有用的知識，有助于揭示許多現(xiàn)實生活應(yīng)用中共同發(fā)生的項目。由于許多現(xiàn)實生活應(yīng)用中的數(shù)據(jù)都具有不確定性，因此，近年來不確定數(shù)據(jù)的頻繁項集成為研究者們關(guān)注的焦點。文中介紹了不確定數(shù)據(jù)頻繁項集挖掘算法的相關(guān)成果，其中包括基于候選項集生成和測試的、基于模式增長的以及基于生物啟發(fā)的頻繁項集挖掘算法，并對典型代表性算法進行了介紹，對其性能進行了分析。

未來的可能研究方向包括：(1)基于生物啟發(fā)的頻繁項集挖掘算法的改進創(chuàng)新；(2)在社交網(wǎng)絡(luò)分析等應(yīng)用領(lǐng)域的不確定數(shù)據(jù)中挖掘頻繁項集；(3)從不確定數(shù)據(jù)中挖掘頻繁序列和頻繁圖；(4)不確定頻繁模式的可視化分析。