An Efficient Algorithm for Discovering High Utility Itemsets with Negative Item Values in Large Databases.pdf

1、目前，在頻繁項(xiàng)目集挖掘處理上已經(jīng)發(fā)展的比較成熟，并在常規(guī)數(shù)據(jù)庫(kù)中得到了應(yīng)用。然而這種僅對(duì)頻繁集的挖掘并沒有多大的指導(dǎo)意義，因?yàn)檫@種挖掘只反映了數(shù)據(jù)庫(kù)中包含該項(xiàng)目集交易數(shù)量，它不能真實(shí)的反映那些能衡量成本效益或者其他的用戶偏好的項(xiàng)目集中。同時(shí)頻繁項(xiàng)目集往往只貢獻(xiàn)了總利潤(rùn)的小部分，而非頻繁項(xiàng)集則占了大部分的利潤(rùn)比例。
　　 通常數(shù)據(jù)集里蘊(yùn)含著不同價(jià)值的數(shù)據(jù)信息，一個(gè)零售企業(yè)的興趣更多的集中在一些最有價(jià)值的客戶（企業(yè)主要利潤(rùn)來源的客戶

2、）身上。因此頻率不能充分的回答那個(gè)項(xiàng)目集是高利潤(rùn)的項(xiàng)目集而那個(gè)項(xiàng)目集是具有重要影響的項(xiàng)目集這一問題。在大量重要的數(shù)據(jù)挖掘任務(wù)中，如關(guān)聯(lián)規(guī)則挖掘和長(zhǎng)模式，新興的模式和依賴規(guī)則挖掘等。從負(fù)項(xiàng)集中發(fā)現(xiàn)高利用價(jià)值項(xiàng)無論是在理論還是實(shí)踐中都起著至關(guān)重要的作用。效用挖掘的目標(biāo)是利用負(fù)項(xiàng)集找出實(shí)用價(jià)值高的項(xiàng)目集，這些項(xiàng)目集占了總效用的很大一部分。
　　 本研究的目的是通過效用挖掘以識(shí)別出高利用價(jià)值的數(shù)據(jù)集。在先前的一些應(yīng)用中，數(shù)據(jù)集的價(jià)值都是

3、來自具有正相關(guān)效用的數(shù)據(jù)集，然而數(shù)據(jù)集可能具有負(fù)相關(guān)的價(jià)值。從負(fù)相關(guān)的數(shù)據(jù)集中發(fā)現(xiàn)具有高價(jià)值的數(shù)據(jù)項(xiàng)，對(duì)于興趣挖掘模式來說是一個(gè)重要的處理過程，像利用關(guān)聯(lián)規(guī)則從大規(guī)模數(shù)據(jù)庫(kù)中的挖掘。同時(shí)實(shí)現(xiàn)從負(fù)相關(guān)的數(shù)據(jù)項(xiàng)中挖掘?qū)嵱脙r(jià)值高的數(shù)據(jù)集是一件有利的、意義重大的研究，我們的貢獻(xiàn)是能利用很少的計(jì)算資源有效的挖掘出高價(jià)值的數(shù)據(jù)集。通過這種方法，利用負(fù)相關(guān)項(xiàng)能有效的挖掘出高價(jià)值數(shù)據(jù)集，且僅需要很少的內(nèi)存空間。
　　 本文的目標(biāo)是提出一個(gè)利用負(fù)

4、項(xiàng)相關(guān)集挖掘出高利用價(jià)值數(shù)據(jù)集的高效算法，我們的算法HUIWNIV-Mine將聚焦在通過使用不帶負(fù)值交易的項(xiàng)目集，減少候選項(xiàng)目集和CPU的I/O上來加快響應(yīng)時(shí)間，本質(zhì)上就是在一個(gè)大型交易數(shù)據(jù)庫(kù)中消除負(fù)項(xiàng)值。
　　 為了理解HUIWNIV（High Utility Itemsets With Negative Item Values）的思想，我們通過例子來說明。例如：許多超市可能舉行一些購(gòu)買特殊商品獲贈(zèng)其他商品的促銷活動(dòng)，以吸引顧

5、客，而那些免費(fèi)贈(zèng)送的商品對(duì)于超市來說就是負(fù)項(xiàng)集（也就是沒有利潤(rùn)獲得反而虧損的商品）。然而，超市可能從其他交叉促銷商品項(xiàng)中獲得更高的利潤(rùn)。這種做法很常見。例如，如果一個(gè)消費(fèi)者買了4項(xiàng)A，他將同時(shí)獲得免費(fèi)贈(zèng)送的一個(gè)B。假設(shè)超市買出一個(gè)A獲得4美元的利潤(rùn)，贈(zèng)送一個(gè)B損失3美元。盡管贈(zèng)送一個(gè)B導(dǎo)致超市損失了3美元，但是能從交叉促銷商品A中賺16美元。最終超市從本次促銷中獲得了13美元的利潤(rùn)。
　　 我們可以定義數(shù)據(jù)項(xiàng)目集X的效用為u(X

6、)，它代表包含X的所有交易的總和。效用挖掘的目標(biāo)是要找出高實(shí)用性的項(xiàng)目集，這些項(xiàng)目集占了總效用的很大一部分。傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘模型假設(shè)每項(xiàng)的效用總為1并且銷售量為0或1，因此這只是效用挖掘中一種特殊情況。而在真正的效用挖掘中的每個(gè)項(xiàng)的效用和銷售量可以為任意值。如果u(X)比指定的效用門限好，X則為高效用項(xiàng)目集；否則為低效用項(xiàng)目集。
　　 HUIWNIV-Mine算法在數(shù)據(jù)庫(kù)中利用一個(gè)閾值來處理產(chǎn)生的交易權(quán)重效用值。該算法能舍棄一

7、些低價(jià)值數(shù)據(jù)集，但是不會(huì)遺漏任何的高價(jià)值的數(shù)據(jù)集，數(shù)據(jù)集中的每個(gè)負(fù)相關(guān)的數(shù)據(jù)項(xiàng)將不會(huì)是高價(jià)值數(shù)據(jù)集。在產(chǎn)生的數(shù)據(jù)集中至少有一個(gè)數(shù)據(jù)項(xiàng)是有正價(jià)值的，或者需要的數(shù)據(jù)集不必去掃描數(shù)據(jù)庫(kù)，因此，HUIWNIV-Mine算法通過一些數(shù)據(jù)項(xiàng)能輸出真正的具有高交易權(quán)重效用的候選數(shù)據(jù)集。
　　 HUIWNIV-Mine算法的新穎性在于它能有效的通過負(fù)相關(guān)集挖掘出高利用價(jià)值的數(shù)據(jù)集，同時(shí)只需要少量的處理利用率，像在大規(guī)模數(shù)據(jù)庫(kù)中挖掘出高價(jià)值的數(shù)據(jù)