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

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

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

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

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

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

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

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

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