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

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

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

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

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

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

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

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

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

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

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

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