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

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

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

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

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