高效用關聯(lián)規(guī)則的挖掘.pdf

1、關聯(lián)規(guī)則的挖掘就是要發(fā)現(xiàn)大量數(shù)據(jù)中項集之間的關聯(lián)或相關聯(lián)系，它是數(shù)據(jù)挖掘研究的重要內(nèi)容之一，在科學研究、電信網(wǎng)絡、市場與風險管理、客戶關系管理(CRM)、存貨控制、軍事等方面得到了廣泛應用。但是，傳統(tǒng)的關聯(lián)規(guī)則以支持度衡量項集的重要性，會丟失一些支持度不高但效用很高、用戶很可能感興趣的規(guī)則。本文研究的高效用關聯(lián)規(guī)則彌補了傳統(tǒng)關聯(lián)規(guī)則無法表達項集效用的不足，能反映用戶偏好，更好地滿足決策需求。本文主要研究高維大數(shù)據(jù)集中高效用關聯(lián)規(guī)則的挖掘

2、算法，彌補了現(xiàn)有的基于效用關聯(lián)規(guī)則挖掘算法不能有效處理高維大數(shù)據(jù)集的不足。文中還結合效用與支持度的特點，提出了基于效用與支持度的關聯(lián)規(guī)則挖掘問題及算法，可發(fā)現(xiàn)更多的用戶感興趣的規(guī)則。本文的主要研究有：
　　 (1)提出了一種新的在高維大數(shù)據(jù)集中挖掘高效用長項集的算法Inter-transaction。該算法基于行枚舉，通過長事務的交集運算，直接得到長項集，不必從短項集逐步擴展得到長項集。在高維數(shù)據(jù)集中，長事務間共同項目很少，事務

3、進行交集運算后變短的速度很快，因此這種行枚舉方法具有很好的收斂性。Inter-transaction算法還把劃分的方法引入到效用挖掘中，僅掃描數(shù)據(jù)庫兩次，能很好地適應高維大數(shù)據(jù)集環(huán)境。同時，由于采用了新的剪枝策略，避免了大量的候選集的生成、檢驗。
　　 (2)提出了一種雙向搜索高效用項集的混雜算法?，F(xiàn)有的基于效用的關聯(lián)規(guī)則挖掘算法采用類似Apriori的搜索策略，需要多次掃描數(shù)據(jù)庫。當模式很長且數(shù)據(jù)集很大時，I/O負擔太重。本文

4、提出了一種從上下兩個方向搜索高效用項集的混雜算法。該算法把發(fā)現(xiàn)所有高效用項集的任務分解為發(fā)現(xiàn)高效用長項集和高效用短項集兩個相對容易解決的子問題，然后再選擇不同的算法完成挖掘任務，避免了從短項集逐步擴展到長項集的冗長過程。
　　 (3)提出了一種優(yōu)化長事務交集運算的方法。我們提出的挖掘高效用長項集的算法同時以水平項目向量(Horizontal item-vectot，簡稱HIV)和水平項目列表(Horizontal item-li

5、st，簡稱HIL)兩種格式存儲事務，并利用HIL格式數(shù)據(jù)提供的信息減少比特級邏輯“與”運算的次數(shù)，使邏輯“與”運算的次數(shù)等于HIL格式數(shù)據(jù)的長度，與比特向量(HIV格式)的長度無關。這種以空間換時間的方法解決了事務交集運算的性能隨比特向量長度的增長而降低的問題，保證了在高維環(huán)境下的高性能。這種優(yōu)化方法也可有效提高垂直挖掘算法挖掘頻繁長模式的效率。
　　 (4)提出了基于效用與支持度的關聯(lián)規(guī)則挖掘問題。支持度與效用分別反映了項集的

6、統(tǒng)計特性與語義特性，但人們對事物的興趣度(或事物對人們的重要性)不但取決于事物本身的客觀因素(如項集的支持度)，與人們的主觀因素(如人們對效用的不同理解)也密不可分。為克服單個度量(支持度或效用)的不足，本文提出了一種衡量項集重要性的新的度量：激勵。項集的激勵定義為支持度與效用的乘積，反映了用戶獲得某種效用的可能性或以某種可能性可獲得多大的效用。在基于效用與支持度的關聯(lián)規(guī)則挖掘中，高激勵項集的挖掘避免了那些支持度不高但效用較高、或效用不

7、高但支持度較高的項集的丟失，能發(fā)現(xiàn)更多的用戶感興趣的規(guī)則。
　　 (5)論證了激勵具有兩個重要的數(shù)學性質(zhì)：上界特性和事務權重激勵向下封閉特性。根據(jù)這兩個特性，設計了兩種挖掘高效用頻繁集的算法HM-Miner和HM-Two-Phase-Miner。兩種算法都采用了類似Apriori的自下而上的搜索方式，適合于短模式數(shù)據(jù)集的挖掘。HM-Miner利用激勵的上界特性剪枝，HM-Two-Phase-Miner則利用事務權重激勵向下封閉特

8、性剪枝。
　　 (6)給出了一個高效用關聯(lián)規(guī)則挖掘的應用系統(tǒng)，并用于購物籃分析中。該系統(tǒng)能同時輸出關聯(lián)規(guī)則(項集)的支持度、效用與激勵，以比較基于支持度的關聯(lián)規(guī)則與高效用關聯(lián)規(guī)則挖掘的區(qū)別與聯(lián)系。實際挖掘結果表明，高效用關聯(lián)規(guī)則的挖掘能發(fā)現(xiàn)一些基于支持度關聯(lián)規(guī)則無法發(fā)現(xiàn)的有趣模式，幫助商家找出高效用商品組合，促進高利潤商品的銷售。經(jīng)過數(shù)據(jù)的轉(zhuǎn)換處理，該系統(tǒng)還可應用于其他領域。例如，在網(wǎng)頁分析中，把網(wǎng)頁被訪問的次數(shù)與瀏覽時間作為評