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

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

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

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

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

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

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

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