發(fā)現(xiàn)Top-k高效用項(xiàng)集的算法.pdf

1、數(shù)據(jù)挖掘是一個(gè)重要的研究領(lǐng)域，這個(gè)研究領(lǐng)域是在數(shù)據(jù)庫中發(fā)現(xiàn)模式的計(jì)算過程。數(shù)據(jù)挖掘過程的總體目標(biāo)是從數(shù)據(jù)中提取有用的信息和知識，并將其轉(zhuǎn)換為一種可以理解的結(jié)構(gòu)進(jìn)行進(jìn)一步的使用。在數(shù)據(jù)挖掘中一個(gè)基本的任務(wù)是頻繁項(xiàng)集挖掘(FIM)。頻繁項(xiàng)集挖掘包括發(fā)現(xiàn)在事務(wù)數(shù)據(jù)庫中頻繁的一起出現(xiàn)的項(xiàng)集。有許多被開發(fā)出來的算法能有效地發(fā)現(xiàn)頻繁項(xiàng)集。但是為解決這個(gè)問題的這些算法存在著一些主要的缺陷。他們認(rèn)為所有項(xiàng)有相同的重要性（如單位利潤或重量）而且不考慮項(xiàng)的

2、數(shù)量，通常這些假設(shè)在真實(shí)的應(yīng)用中并不成立。
　　為了解決這個(gè)問題，發(fā)現(xiàn)高效用項(xiàng)集(HUIs)的任務(wù)具有的效用不低于用戶指定的最小效用閾值已成為一個(gè)主要的研究問題。高效用項(xiàng)集是一個(gè)重要的數(shù)據(jù)挖掘任務(wù)。然而對于用戶來說指定最小效用閾值并不是一項(xiàng)容易的任務(wù)。用戶通常不知道什么樣的閾值是最合適他們的需求而且他們也不能預(yù)測這個(gè)項(xiàng)集數(shù)量。選擇一個(gè)合適的閾值直接影響發(fā)現(xiàn)高效用項(xiàng)集的數(shù)量，因此它也直接影響算法的效率和有效性。為了解決這個(gè)問題，to

3、p-k高效用項(xiàng)集挖掘任務(wù)被提出。
　　在top-k高效用項(xiàng)集挖掘中，用戶必須指定一個(gè)用于指示項(xiàng)集數(shù)量的參數(shù)k而不是指定一個(gè)最小效用閾值。top-k高效用項(xiàng)集挖掘是在事務(wù)數(shù)據(jù)庫中具有最高效用的發(fā)現(xiàn)k項(xiàng)集的過程。近年來，針對這一任務(wù)已經(jīng)提出了一些算法。在這些算法中，結(jié)果項(xiàng)集的數(shù)量由用戶控制，返回的結(jié)果沒有被用戶用于數(shù)據(jù)分析。然而，即使這樣它仍然占用了昂貴的運(yùn)行時(shí)間和內(nèi)存消耗。這個(gè)是因?yàn)槟壳暗乃惴ㄍa(chǎn)生大量的候選項(xiàng)集但卻無法有效地修剪

4、搜索空間。在本文中，為了解決這個(gè)問題，提出了一個(gè)叫做KHMC的新穎算法，它能更有效的發(fā)現(xiàn)top-k高效用項(xiàng)集。與其他幾個(gè)top-k高效用項(xiàng)集挖掘算法不同的是KHMC利用一個(gè)單一的階段去搜尋發(fā)現(xiàn)高效用項(xiàng)集。此外，該算法海采用了RIU，CUD，和COV三種策略來更有效的提高其內(nèi)部最小效用閾值，從而減小了搜索空間。這個(gè)COV策略引入了一個(gè)新穎的覆蓋的概念。在本文中提出的這個(gè)覆蓋的概念可以在高效用項(xiàng)集挖掘中用來修剪搜索空間，或者在top-k高效