黃江東

游覽故宮的人們（木易 攝）

目前，旅游業(yè)發(fā)展迅速，旅游市場持續(xù)較快增長。伴隨互聯(lián)網(wǎng)的井噴式發(fā)展，在信息不對稱條件下以新景點(diǎn)、新線路吸引游客從而獲取傭金的傳統(tǒng)旅游商業(yè)運(yùn)作模式已經(jīng)發(fā)生了根本變化。梁昌勇等人認(rèn)為旅游業(yè)服務(wù)游客需要挖掘大量的數(shù)據(jù)，而其中挖掘出的有意義的信息即是本文關(guān)注的內(nèi)容。徐宏等則認(rèn)為通過關(guān)聯(lián)規(guī)則對用戶需求進(jìn)行分析，可以發(fā)現(xiàn)更好的產(chǎn)品和適當(dāng)?shù)姆?wù)。陳文娟認(rèn)為大數(shù)據(jù)時代比數(shù)據(jù)更為重要的是解決方案，本文則設(shè)計(jì)了一個用于挖掘套餐的解決模型。

由于關(guān)聯(lián)規(guī)則挖掘應(yīng)用廣泛，在數(shù)據(jù)挖掘領(lǐng)域是一個重要的分支。著名算法Apriori首先由Agrawal & Srikant等提出。然而傳統(tǒng)的關(guān)聯(lián)規(guī)則算法是從頻繁項(xiàng)目集中派生的，這些項(xiàng)目集的產(chǎn)生只考慮項(xiàng)目是否發(fā)生，但忽略了其他因素，比如價(jià)格或者分類。由于對待數(shù)據(jù)庫中的所有項(xiàng)目均采用相同的重要性，因此采用此算法無法簡單的識別出項(xiàng)目和項(xiàng)目集的實(shí)際重要性。Chan等人考慮效益和數(shù)量，并使用它們來找出項(xiàng)目集的實(shí)際效用值，從而提出了一種新的方式來挖掘數(shù)據(jù)，稱之為“高效項(xiàng)目集”（HUI）。但是效用挖掘的挑戰(zhàn)是對候選集的大小有限制。而如今的實(shí)際應(yīng)用中，數(shù)據(jù)集大小很容易達(dá)到數(shù)百兆字節(jié)或千兆字節(jié)，所以提出了一個算法來快速地找到HUI。

一、關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則指的是某些事件的發(fā)生而引發(fā)另外一些事件的發(fā)生，起源于超市的購物情況分析，其問題可形式化描述如下：

假設(shè)所有事件的集合為I={i1,i2……,in}（稱之為項(xiàng)目集），其中數(shù)據(jù)項(xiàng)為ij。事務(wù)數(shù)據(jù)庫記作D（也成為交易數(shù)據(jù)集），其中每一個交易T都是項(xiàng)目的集合，即TI。每條交易均包含交易標(biāo)識（Transaction identification，簡稱TID），

給定一個交易數(shù)據(jù)集D，進(jìn)行關(guān)聯(lián)規(guī)則挖掘就是判斷其產(chǎn)生支持度和可信度均比用戶給定的最小支持度閾值和最小置信度閾值大。若支持度和置信度均超過各自閾值，則AB可視為一個挖掘出的關(guān)聯(lián)規(guī)則。

二、效用挖掘

效用挖掘的目標(biāo)是發(fā)現(xiàn)其效用值超出交易數(shù)據(jù)集中用戶指定閾值的所有項(xiàng)目集。以下定義一些效用挖掘的術(shù)語。

①設(shè)項(xiàng)目集為I={i1,i2,……,in}

②D = {T1,T2,…,Tn}是交易數(shù)據(jù)庫，其中每個交易T1∈D是I的子集。

③o(ip，Tq)，本地交易效益值，表示交易Tq中的項(xiàng)目ip的數(shù)量。

④s(ip)，外部效益值，是在實(shí)用表中項(xiàng)目ip的關(guān)聯(lián)值。該值反映了項(xiàng)目的重要性。

⑤u(ip，Tq)，效用值，交易Tq中項(xiàng)目ip的效用，定義為 o(ip，Tq)×s(ip)。

⑥u(X，Tq)，交易Tq中項(xiàng)目集X的效用，定義為，且1≤k≤m。中X={i1,i2,……,ik}是一個k項(xiàng)集，

效用挖掘是找到所有高效用項(xiàng)目集。若u(X)≥ε，則項(xiàng)集X是高效用項(xiàng)集，其中XI和ε是最小效用閾值，否則，它是低效用項(xiàng)集。

三、快速效用挖掘算法

假設(shè)時間段t中的項(xiàng)目X的交易加權(quán)效益是該時間段中包含X的所有交易的效益總和。如果一個項(xiàng)目所有交易加權(quán)效益之和大于或等于預(yù)定義的閾值λ，就稱之為在t中的高效益加權(quán)項(xiàng)目集（The high transaction-weighted-utilization itemsets，簡稱HTWUI）。由于項(xiàng)目的交易加權(quán)效益值總是大于或等于項(xiàng)目的實(shí)際效益值，所以在t中只可能有一個高效益加權(quán)項(xiàng)目集。此外，至少一個時間段內(nèi)的高效益項(xiàng)目集是可能成為高效益頻繁項(xiàng)目集的一個候選集的。在其所有頻繁時間段里通過其實(shí)際效益值可以進(jìn)一步確定它是否是一個高效益頻繁項(xiàng)目集?；谏鲜龈拍?，過程如下所述。

尋找高效益HUI的過程：

輸入：時間段tj中的一組交易Dj。

輸出：高效益項(xiàng)目集HUIj。

第一步：設(shè)r=1，其中r表示當(dāng)前待處理的候選交易加權(quán)效益項(xiàng)目集（Cjr）中的項(xiàng)目的數(shù)量。

第二步：一開始先設(shè)Cjr為時間段tj中所有項(xiàng)目的集合。

第三步：對于事務(wù)Transjy的每個Cjr中出現(xiàn)的候選r-項(xiàng)集Xjyz，將X的效益tujyz設(shè)置為：

tujyz=tujy.

其中tujy是交易Transjy的交易效益。

第四步：計(jì)算每個時間段tj中每個r-項(xiàng)集Xjz的交易加權(quán)效益twujz，也就是計(jì)算tj時間段內(nèi)所有交易的r-項(xiàng)集Xjz的交易效益值之和：

twujz=∑ytujyz.

第五步：計(jì)算每個時間段tj中候選r-項(xiàng)集Xjz的實(shí)際效益ujz為：

ujz=∑vujyz.

其中ujyz是交易Transjy中r-項(xiàng)集Xjz的效益值，ujyz也就是所有交易的r-項(xiàng)集Xjz的實(shí)際效益值之和。

第六步：檢查每個時間段tj中每個候選r-項(xiàng)集Xjz的交易加權(quán)效益twujz是否在時間段tj內(nèi)大于或等于閾值λ*pttuj。如果是，則將其放入tj的高效益加權(quán)r-項(xiàng)集的集合HTWUIjr中。即：

第七步：檢查每個時間段tj中每個候選r-項(xiàng)集Xjz的實(shí)際效益ujz是否在時間段tj內(nèi)大于或等于閾值λ*pttuj。如果是，則將其實(shí)際效益ujz放入集合HUIjr中。即：

第八步：從HTWUIjr中生成當(dāng)前時間段tj的候選集Cj(r+1)。其中Cj(r+1)中每個候選的r-項(xiàng)子集必須存在于HTWUIjr中。

第九步：如果HTWUIjr不為空，則設(shè)r=r+1，并重復(fù)執(zhí)行第一步到第九步; 否則將返回一組高效益項(xiàng)目集HUIj及其實(shí)際效益值。

四、實(shí)驗(yàn)

本文采用Windows版本的IBM市場籃筐合成數(shù)據(jù)產(chǎn)生器（IBM Quest Market-Basket Synthetic Data Generator）產(chǎn)生需要的數(shù)據(jù)集，將模擬的數(shù)據(jù)集用來進(jìn)行驗(yàn)證算法。產(chǎn)生兩組合成數(shù)據(jù)庫，交易數(shù)量從1000K改為8000K，項(xiàng)目數(shù)量從1K到8K不等。從真實(shí)數(shù)據(jù)庫中觀察到大多數(shù)項(xiàng)目處于低效益范圍，所以將使用對數(shù)正態(tài)分布生成效用值。圖1顯示了1000個項(xiàng)目的效用值的直方圖。

圖1 1000個項(xiàng)目效用值直方圖

我們還使用來自國內(nèi)在線旅行社（OTA）流水?dāng)?shù)據(jù)評估了算法。數(shù)據(jù)集在原數(shù)據(jù)庫基礎(chǔ)上進(jìn)行數(shù)據(jù)填補(bǔ)及擴(kuò)充后得到1,112,949條交易流水。為了評估效用挖掘結(jié)果是否對OTA有用，我們將高效項(xiàng)目集與傳統(tǒng)ARM挖掘的頻繁項(xiàng)集進(jìn)行比較。的確發(fā)現(xiàn)了許多有趣的項(xiàng)目集。例如，旅行社的一種交通擺渡車是一種常見的項(xiàng)目（支持率超過3%），但是其貢獻(xiàn)的總效用小于0.25%；而景點(diǎn)門票和文娛產(chǎn)品的組合發(fā)生超過1%，但貢獻(xiàn)的總效用小于0.25%。因此，效用挖掘可以幫助這家OTA作出更好的銷售決策，例如突出高利潤的項(xiàng)目集，并降低頻繁但利潤較低的項(xiàng)目集的成本。我們通過改變閾值來評估算法的可擴(kuò)展性。如表1所示，它快速且可以很好地?cái)U(kuò)展。

?

五、結(jié)論

本文提出一種可以高效找到HUI的算法，此算法需要較少的數(shù)據(jù)庫掃描，所以占用的內(nèi)存空間以及計(jì)算開銷將會更小。另一個重要特征是可以輕松處理非常大的數(shù)據(jù)庫。以某在線旅行網(wǎng)站交易流水情況為例，進(jìn)行關(guān)聯(lián)規(guī)則挖掘，取得了一定的效果。利用快速挖掘關(guān)聯(lián)規(guī)則還有許多亟待解決的問題，效用挖掘依舊只是關(guān)注產(chǎn)品本身的效益和數(shù)量從而忽略了序列和時間對產(chǎn)品的階段性影響，這將是以后要繼續(xù)研究的方向。