發(fā)現(xiàn)興趣模式的高效方法.pdf

1、如今，數(shù)據(jù)量的快速增長帶領(lǐng)我們進(jìn)入了大數(shù)據(jù)時代。同時，大數(shù)據(jù)類型多樣，如社交數(shù)據(jù)、企業(yè)數(shù)據(jù)、傳感器數(shù)據(jù)及機器生成數(shù)據(jù)等。因此，我們迫切地需要快速及有效的數(shù)據(jù)挖掘方法來利用“大數(shù)據(jù)”。這些方法可用于開發(fā)強大的多功能分析工具，并將數(shù)據(jù)轉(zhuǎn)化為有用的知識。模式挖掘是數(shù)據(jù)挖掘中最重要的主題之一，即開發(fā)/使用一些數(shù)據(jù)挖掘算法來發(fā)現(xiàn)數(shù)據(jù)庫中有趣且意想不到的模式。其中，頻繁模式挖掘（FPM）應(yīng)用廣泛，是消費者市場分析，推薦系統(tǒng)，網(wǎng)絡(luò)挖掘和網(wǎng)絡(luò)入侵檢測等

2、應(yīng)用的基礎(chǔ)。頻繁模式是出現(xiàn)在數(shù)據(jù)集中的頻率不小于用戶指定的最小閾值的項集，子序列或子結(jié)構(gòu)。在現(xiàn)實生活的應(yīng)用場景中，零售商可能更感興趣的是找到產(chǎn)生高利潤而不是發(fā)現(xiàn)頻繁出現(xiàn)的那些項目集。因此，發(fā)現(xiàn)高效用/利潤項目集（HUIs）的問題已經(jīng)成為一項新興的任務(wù)。許多研究者已經(jīng)開始研發(fā)高效用項目集挖掘（HUIM）算法。然而，他們大多數(shù)假設(shè)物品的利潤/權(quán)重是積極的，且所有物品都在售。同時，在現(xiàn)實世界中，一些產(chǎn)品只在特定的時間段出售。例如，某些產(chǎn)品只在

3、夏季出售，或者在節(jié)日虧本促銷出售。為了解決上述兩個限制，HUIM的問題已經(jīng)被分別重新定義為發(fā)現(xiàn)高效用/利潤項目集（HOUs）的問題。它比傳統(tǒng)的HUIM更難，因為需要考慮物品的擱置時間，并且區(qū)別具有負(fù)單位利潤的物品。因此，傳統(tǒng)HUIM和FPM中使用的技術(shù)不能直接應(yīng)用于這個問題。此外，傳統(tǒng)FPM，HUI和HOU挖掘算法的不足之處在于，用戶難以找到合適的最小閾值參數(shù)。如果用戶將閾值設(shè)置得太高，則找不到足夠的匹配模式。并且如果用戶將閾值設(shè)置得太

4、低，則將找到大量的匹配模式，且算法可能消耗過多的運行時間和內(nèi)存。為了找到適當(dāng)?shù)拈撝?，用戶通常需要反?fù)試錯的方法來運行多次挖掘算法，這將非常耗時。即使用戶已經(jīng)預(yù)先知道適當(dāng)?shù)拈撝?，傳統(tǒng)的挖掘算法通常產(chǎn)生非常大的結(jié)果模式集合，這對用戶來說是不方便的，并使得所需模式的發(fā)現(xiàn)在執(zhí)行時間和存儲器使用方面效率較低。為了解決這些限制，在本文中，我們專注于開發(fā)高效的方法來發(fā)現(xiàn)有趣的模式，這就是top-rank-k頻繁模式、封閉的高效用項目集和top-k現(xiàn)貨

5、高效用項目集。我們的方法簡要描述如下。
　　在本文中，我們首先考慮top-rank-k頻繁模式挖掘問題，用于挖掘前k個支持度最高的模式。針對這個問題，目前所提出的算法效率都不高。基于此，本文提出一個BTK算法來解決這個問題。BTK依賴于一種名為TB-tree（遍歷構(gòu)建樹）的新型樹結(jié)構(gòu)來存儲關(guān)于頻繁模式的關(guān)鍵信息。TB-樹的構(gòu)造只需掃描一次數(shù)據(jù)庫而不必按照文獻(xiàn)中基于PPC-樹的算法對樹進(jìn)行先序和后序遍歷。此外，我們引入了兩種有效的過

6、程來分別產(chǎn)生子包索引和相交B-列表。我們使用真實和合成數(shù)據(jù)集進(jìn)行全面的性能研究，以評估所提出算法的效率。實驗結(jié)果表明，BTK是高效的，并且效率優(yōu)于當(dāng)前已有的top-rank-k頻繁模式挖掘算法。
　　雖然BTK算法解決了挖掘top-rank-k頻繁模式的問題，其中用戶需要指定k，并且返回前k個支持度最高的模式。本文第二個工作旨在發(fā)現(xiàn)閉合高效用項目集（CHUI），它是HUI的簡明和無損表示。閉合高效用項目集，CHUI，可以比所有HU

7、I的集合小幾個數(shù)量級，并且允許導(dǎo)出所有HUI。雖然挖掘CHUI是有用且可取的，但它的計算代價仍然非常昂貴。因為當(dāng)前算法經(jīng)常產(chǎn)生大量的候選項集，并且不能有效地剪枝搜索空間。因此本文提出一個CLS-Miner算法來解決這個問題。我們利用實用程序列表結(jié)構(gòu)直接計算項集的效用而不產(chǎn)生候選項。CLS-Miner引入了三種有效的剪枝策略來減少算法的搜索空間。第一種策略稱為Chain-EUCP，它使用項目共現(xiàn)的估計效用來確定是否應(yīng)該剪枝項目集。第二種策

8、略，即下行分支剪枝（LBP），使用對項目集傳遞擴(kuò)展的效用的新上限減少搜索空間。這兩個策略允許在沒有完全構(gòu)建實用程序列表的情況下消除候選項。最后一個策略是基于一個名為覆蓋的新概念，它受到閉包項集的定義的啟發(fā)。這個概念可以用于剪枝低效用項目集，以及快速計算項目集的閉包。所提出的剪枝策略可以大大減少用于構(gòu)造實用程序列表的連接操作的數(shù)量，大大減少算法搜索空間。此外，我們引入了一種高效的預(yù)檢查包含方法來檢查項集X是否包含另一個項集Y，其主要用于包

9、含檢查和閉包計算。這兩個操作在閉合模式挖掘中必不可少。如實驗評估部分所示，所提出的CLS-Miner算法是有效的，并且可以大大減少這兩個操作的執(zhí)行時間。為了評估所提出的算法和策略的性能，我們已經(jīng)對具有各種特征的六個基準(zhǔn)進(jìn)行了大量的實驗，包括實際數(shù)據(jù)集和合成數(shù)據(jù)集。結(jié)果表明，所提出的剪枝策略高效有效，CLS-Miner算法具有線性可伸縮性，并優(yōu)于當(dāng)前最優(yōu)的CHUI挖掘算法。
　　最后，我們首次定義了“挖掘top-k現(xiàn)貨高效用項目集”

10、的問題，并考慮了正項和負(fù)項單位利潤，以及每個項目的保質(zhì)期。同時，我們提出一個名為“有或沒有負(fù)單位利潤（KOSHU）的top-k貨架高效用項目集礦工”的法，這是一種基于實用程序列表的算法，其中包括EMPRP（估計最大周期速率修剪）、PUP（周期效用修剪）和CE2P（一對雙項集合修剪的同時存在）三種新穎項目集修剪策略。這些策略可以刪除大量的連接操作，從而節(jié)省了大部分的搜索空。該算法還采用了一些策略，在top-k HOU挖掘過程中對內(nèi)部最小相

11、對效用閾值進(jìn)行初始化（RIRU）和動態(tài)調(diào)整（RIRU2）。這些策略可以有效地提高相對效用閾值，從而有助于基于一種全新EMPRS結(jié)構(gòu)的EMPRP策略的有效性。此外，我們提出了一種低復(fù)雜度的程序，在挖掘過程中構(gòu)建實用程序列表。它使用快速二分搜索方法來實現(xiàn)，即記住最后搜索位置的索引，下一次搜索則從該位置開始，而不是從第一位置開始。這些技術(shù)能夠極大地提高性能效率。我們對實際數(shù)據(jù)集和模擬數(shù)據(jù)集都進(jìn)行了廣泛的實驗評估，結(jié)果表明，所提出的算法時空效率