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

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

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

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

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

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

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

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

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

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

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

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