基于快速效用挖掘的旅游套餐分析

黃江東

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

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

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

一、關聯規則

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

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

給定一個交易數據集D，進行關聯規則挖掘就是判斷其產生支持度和可信度均比用戶給定的最小支持度閾值和最小置信度閾值大。若支持度和置信度均超過各自閾值，則AB可視為一個挖掘出的關聯規則。

二、效用挖掘

效用挖掘的目標是發現其效用值超出交易數據集中用戶指定閾值的所有項目集。以下定義一些效用挖掘的術語。

①設項目集為I={i1,i2,……,in}

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

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

④s(ip)，外部效益值，是在實用表中項目ip的關聯值。該值反映了項目的重要性。

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

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

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

三、快速效用挖掘算法

假設時間段t中的項目X的交易加權效益是該時間段中包含X的所有交易的效益總和。如果一個項目所有交易加權效益之和大于或等于預定義的閾值λ，就稱之為在t中的高效益加權項目集（The high transaction-weighted-utilization itemsets，簡稱HTWUI）。由于項目的交易加權效益值總是大于或等于項目的實際效益值，所以在t中只可能有一個高效益加權項目集。此外，至少一個時間段內的高效益項目集是可能成為高效益頻繁項目集的一個候選集的。在其所有頻繁時間段里通過其實際效益值可以進一步確定它是否是一個高效益頻繁項目集。基于上述概念，過程如下所述。

尋找高效益HUI的過程：

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

輸出：高效益項目集HUIj。

第一步：設r=1，其中r表示當前待處理的候選交易加權效益項目集（Cjr）中的項目的數量。

第二步：一開始先設Cjr為時間段tj中所有項目的集合。

第三步：對于事務Transjy的每個Cjr中出現的候選r-項集Xjyz，將X的效益tujyz設置為：

tujyz=tujy.

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

第四步：計算每個時間段tj中每個r-項集Xjz的交易加權效益twujz，也就是計算tj時間段內所有交易的r-項集Xjz的交易效益值之和：

twujz=∑ytujyz.

第五步：計算每個時間段tj中候選r-項集Xjz的實際效益ujz為：

ujz=∑vujyz.

其中ujyz是交易Transjy中r-項集Xjz的效益值，ujyz也就是所有交易的r-項集Xjz的實際效益值之和。

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

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

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

第九步：如果HTWUIjr不為空，則設r=r+1，并重復執行第一步到第九步; 否則將返回一組高效益項目集HUIj及其實際效益值。

四、實驗

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

圖1 1000個項目效用值直方圖

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

?

五、結論

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