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

黄江东

游览故宫的人们（木易 摄）

目前，旅游业发展迅速，旅游市场持续较快增长。伴随互联网的井喷式发展，在信息不对称条件下以新景点、新线路吸引游客从而获取佣金的传统旅游商业运作模式已经发生了根本变化。梁昌勇等人认为旅游业服务游客需要挖掘大量的数据，而其中挖掘出的有意义的信息即是本文关注的内容。徐宏等则认为通过关联规则对用户需求进行分析，可以发现更好的产品和适当的服务。陈文娟认为大数据时代比数据更为重要的是解决方案，本文则设计了一个用于挖掘套餐的解决模型。

由于关联规则挖掘应用广泛，在数据挖掘领域是一个重要的分支。著名算法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的算法，此算法需要较少的数据库扫描，所以占用的内存空间以及计算开销将会更小。另一个重要特征是可以轻松处理非常大的数据库。以某在线旅行网站交易流水情况为例，进行关联规则挖掘，取得了一定的效果。利用快速挖掘关联规则还有许多亟待解决的问题，效用挖掘依旧只是关注产品本身的效益和数量从而忽略了序列和时间对产品的阶段性影响，这将是以后要继续研究的方向。