鐘新成，李慧芳

（長(zhǎng)治學(xué)院計(jì)算機(jī)系，山西長(zhǎng)治 046011）

高效用項(xiàng)集挖掘（high utility itemsets mining,HUIM）[1-3]是頻繁項(xiàng)集挖掘的一個(gè)重要分支。由于普通的頻繁項(xiàng)集挖掘只考慮各項(xiàng)出現(xiàn)的頻次，而不考慮各項(xiàng)的效用（如價(jià)格、利潤(rùn)、權(quán)重等），使得普通頻繁項(xiàng)集的挖掘在許多方面具有局限性。事實(shí)上，對(duì)于一系列購(gòu)物信息，商家更注重某種或某幾種商品組合所帶來(lái)的的利潤(rùn)，而不單單是出現(xiàn)的次數(shù)，比如某次購(gòu)物顧客購(gòu)買了10 包方便面，產(chǎn)生的利潤(rùn)為6元，而某次購(gòu)物顧客購(gòu)買了一個(gè)成色不錯(cuò)的玉手鐲，產(chǎn)生的利潤(rùn)為1 萬(wàn)元，可見前者出現(xiàn)的頻次高，但利潤(rùn)低，后者出現(xiàn)的頻次低，但利潤(rùn)高，商家自然會(huì)對(duì)后者投入更多的關(guān)注。

針對(duì)上述問題，許多國(guó)內(nèi)外學(xué)者已經(jīng)在該方向產(chǎn)出了非常多的研究成果，其中經(jīng)典的算法有Two-Phase[4]，IHUP[5]，F(xiàn)HM[6]，等。Two-Phase 算法分為兩個(gè)階段，第一階段主要利用事務(wù)權(quán)重向下閉包的屬性，可以實(shí)現(xiàn)大范圍的剪枝，第二階段在剩余解空間再逐個(gè)計(jì)算每個(gè)項(xiàng)集的實(shí)際效用，挑出滿足閾值的項(xiàng)集即為高效用項(xiàng)集，該方法實(shí)現(xiàn)邏輯簡(jiǎn)單，但第二階段需要反復(fù)訪問數(shù)據(jù)集，其效率有所欠缺。算法IHUP 為了克服算法Two-Phase 反復(fù)訪問數(shù)據(jù)集的弊端，設(shè)計(jì)了一種只需兩次訪問數(shù)據(jù)集的模式增長(zhǎng)方式以產(chǎn)生候選集，使得高效用項(xiàng)集挖掘性能有了較大改善，但候選項(xiàng)的規(guī)模并沒有從根本上改善。針對(duì)該問題，算法UP-Growth提出了一種基于樹結(jié)構(gòu)的剪枝方法，該方法又包含四種策略，在四種策略的配合下可以迅速降低候選項(xiàng)的規(guī)模，從而使算法的效率有質(zhì)的提升。HUI-Miner 算法提出了單階段高效用項(xiàng)集挖掘模式，以一種垂直的數(shù)據(jù)列表，輔以剩余效用列表的數(shù)據(jù)結(jié)構(gòu)進(jìn)行模式挖掘，算法邏輯簡(jiǎn)單，易于實(shí)現(xiàn)，但缺乏有效的剪枝特性，總體時(shí)間復(fù)雜度還有待優(yōu)化。針對(duì)該問題，算法FHM 考慮2-項(xiàng)集間的共現(xiàn)性，著眼于改善算法HUI-Miner 的剪枝特性，算法效率有較大提升。

在已有算法的基礎(chǔ)上，提出一種隨機(jī)高效用算法，擬在階段一通過隨機(jī)效應(yīng)加快剪枝進(jìn)程。

1 基本概念

高效用項(xiàng)集挖掘的一些基本概念，涉及項(xiàng)、項(xiàng)集、事務(wù)數(shù)據(jù)庫(kù)、外部效用、事務(wù)加權(quán)效用等，以及這些概念間的基本關(guān)系。

以一小型事務(wù)數(shù)據(jù)集為例，表1 和表2 分別表示事務(wù)數(shù)據(jù)集和效用表。

表1 事務(wù)數(shù)據(jù)集

表2 效用表

由表1 可知在事務(wù)t3中購(gòu)買了1 個(gè)A,2 個(gè)C,1 個(gè)D，產(chǎn)生的事務(wù)效用為105，項(xiàng)C的效用為u(C,T3)=2 × 25=50；項(xiàng)C在整個(gè)數(shù)據(jù)庫(kù)中產(chǎn)生的效用為100。項(xiàng)集BC在整個(gè)事務(wù)集中共出現(xiàn)2 次，在事務(wù)t3中u(BC,T3)=1× 30+2 × 25=80,在整個(gè)數(shù)據(jù)庫(kù)中項(xiàng)集BC的效用為u(BC)=80+85=165。假設(shè)minutil 為100，u(AC)=40，則BC是高效用項(xiàng)集，而AC不是。項(xiàng)C的TWU是t1，t3，t4和t5的效用總和twu=95+105+85+110=395，項(xiàng)集BC的twu是事務(wù)t3和t4的效用總和，twu(BC)=105+85=190。

2 算法描述

在普通頻繁項(xiàng)集挖掘過程中有一個(gè)非常關(guān)鍵的性質(zhì)——反單調(diào)性，即如果一個(gè)項(xiàng)集出現(xiàn)的頻率小于最小支持度，那么它的超集也一定小于最小支持度。利用該性質(zhì)，可以大大減少搜索空間。但該性質(zhì)并不適合高效用項(xiàng)集的挖掘，因?yàn)橛行└咝в庙?xiàng)集出現(xiàn)的頻率可能很低，卻是被重點(diǎn)關(guān)注的對(duì)象。基于此，提出了事務(wù)權(quán)重向下閉合屬性定理。

定理1（事務(wù)權(quán)重向下閉合屬性）假設(shè)Ik表示k-項(xiàng)集，Ik-1表示(k-1)-項(xiàng)集，且有Ik-1?Ik。若Ik是高事務(wù)權(quán)重項(xiàng)集，則Ik-1也是高事務(wù)權(quán)重項(xiàng)集。

定理1表明，任何低事務(wù)權(quán)重項(xiàng)集的超集一定是低事務(wù)權(quán)重項(xiàng)集。也就是說(shuō)只有高事務(wù)權(quán)重(k-1)-項(xiàng)集的組合方可加入到每個(gè)階段的候選集Ck中。

定理2假設(shè)HTWU是事務(wù)數(shù)據(jù)集中的高事務(wù)權(quán)重候選集，HU是高效用候選集，若兩者的閾值相等，則有HU?HTWU。

據(jù)定理2可知，高效用項(xiàng)集是高事務(wù)權(quán)重項(xiàng)集的子集。

基于算法Two-Phase，在搜索策略上稍作改變，提出一種隨機(jī)搜索算法Random-Two-Phase。在階段一，搜索過程中在解空間特定層置若干隨機(jī)數(shù)，每個(gè)搜索結(jié)點(diǎn)都對(duì)應(yīng)相應(yīng)的隨機(jī)數(shù)，然后計(jì)算該節(jié)點(diǎn)的事務(wù)權(quán)重。根據(jù)定理1，若某一項(xiàng)集的事務(wù)權(quán)重小于設(shè)定閾值，則不再搜索其所對(duì)應(yīng)的超集，此外，在圖1中出現(xiàn)0 次的項(xiàng)集也排除在搜索空間外，如此，在第一階段即可實(shí)現(xiàn)大范圍的剪枝。在第二階段，逐個(gè)掃描每個(gè)節(jié)點(diǎn)的真實(shí)效用并與設(shè)置閾值進(jìn)行比較以判定是否為高效用項(xiàng)集。

例如以表1、表2 為例，設(shè)定最小閾值為120，在第一階段時(shí)隨機(jī)置點(diǎn)數(shù)為10，其對(duì)應(yīng)的二進(jìn)制編碼為1010，其對(duì)應(yīng)的節(jié)點(diǎn)為AC，首先判斷其出現(xiàn)次數(shù)是否為0，然后計(jì)算其事務(wù)權(quán)重為110 低于120，于是其對(duì)應(yīng)的超集ABC，ACD，ABCD將被剪枝。如圖1 所示，矩形框內(nèi)95/1 表示該項(xiàng)集事務(wù)權(quán)重值為95，出現(xiàn)次數(shù)為1,圖2 矩形框內(nèi)100/4 則表示的是該項(xiàng)集的真實(shí)效用值為100，出現(xiàn)次數(shù)為1。白色部分為剪枝部分，淡灰色部分為剩余候選項(xiàng)。進(jìn)入二階段時(shí)自底向上進(jìn)行遍歷，逐個(gè)計(jì)算各項(xiàng)集的真實(shí)效用并判斷是否滿足閾值要求，該階段結(jié)束后的深灰色部分為高效用項(xiàng)集，如圖2所示。

圖1 一階段后的搜索空間

圖2 二階段后找到的高效用項(xiàng)集

實(shí)驗(yàn)采用合成數(shù)據(jù)庫(kù)T20I6D1000K，每個(gè)項(xiàng)目生成0 或1 的數(shù)量，每筆交易中項(xiàng)目的個(gè)數(shù)隨機(jī)范圍為1 到5，每個(gè)項(xiàng)的效用數(shù)值也居隨機(jī)范圍0.01 到10.00，并采用對(duì)數(shù)正態(tài)分布來(lái)生成效用值。

從表3 可見，利用事務(wù)權(quán)重向下閉包這一特性，候選集經(jīng)過階段一后剪枝效果非常明顯，平均運(yùn)行時(shí)間也較短，這與隨機(jī)搜索有一定關(guān)系。當(dāng)閾值設(shè)置較小時(shí)，候選項(xiàng)集會(huì)比較多，運(yùn)行時(shí)間也較長(zhǎng)，當(dāng)閾值設(shè)置較大時(shí)，候選項(xiàng)集會(huì)較少，運(yùn)行時(shí)間也較短。表3 同時(shí)表明Random-Two-Phase（以下簡(jiǎn)稱RTP）的平均運(yùn)行時(shí)間在各閾值下明顯優(yōu)于Two-Phase（以下簡(jiǎn)稱TP）的運(yùn)行時(shí)間。

表3 算法在合成數(shù)據(jù)集上的表現(xiàn)

4 結(jié)論

提出的隨機(jī)高效用算法相較原始算法雖具有一定優(yōu)勢(shì)，但只是建立在平均運(yùn)行時(shí)間上，有些時(shí)候并不一定較原始的好。接下來(lái)的工作是如何在階段二去尋找一個(gè)更加緊湊的界，而這個(gè)界擬采用群智能算法來(lái)解決。